openGauss 磁盤引擎之 ustore

ustore屬于In-place?Update更新模式，中文意思為：原地更新，是openGauss內(nèi)核新增的一種存儲模式。openGauss內(nèi)核當(dāng)前使用的行引擎采用的是Append Update（追加更新）模式，該模式在INSERT、DELETE、HOT UPDATE（頁面內(nèi)更新）的場景下有較好的表現(xiàn)。但對于非HOT UPDATE場景，垃圾回收不夠高效。

In-place Update存儲模式提供“原地更新”能力，主要思路是將最新版本的“有效數(shù)據(jù)”和歷史版本的“垃圾數(shù)據(jù)”分離存儲。將最新版本的“有效數(shù)據(jù)”存儲在數(shù)據(jù)頁面上，而單獨(dú)開辟一段undo（回滾）空間，用于統(tǒng)一管理歷史版本的“垃圾數(shù)據(jù)”，因此數(shù)據(jù)空間不會由于頻繁更新而膨脹，垃圾回收效率更高。通過NUMA-aware的undo子系統(tǒng)設(shè)計(jì)，使得undo子系統(tǒng)在多核平臺上高效擴(kuò)展。同時通過對元組和數(shù)據(jù)頁面結(jié)構(gòu)的重新設(shè)計(jì)，減少存儲空間的占用。采用多版本索引技術(shù)，解決索引膨脹問題，徹底去除autovacuum（垃圾清理線程）機(jī)制，提升存儲空間的回收復(fù)用效率。

一、整體框架及代碼概覽

數(shù)據(jù)庫中數(shù)據(jù)處理的本質(zhì)是在保證ACID的基礎(chǔ)上支持盡量高的并發(fā)查詢。這種狀況下，并發(fā)控制、頁面多版本控制以及頁面存儲結(jié)構(gòu)相互耦合在一起，數(shù)據(jù)庫存儲引擎需要進(jìn)行整體設(shè)計(jì)從而在高并發(fā)的狀況下保證各個事務(wù)處理看到類似串行執(zhí)行的效果。

在整個技術(shù)體系中多版本控制用來提升讀寫并發(fā)能力，按照多版本排列方式可以分為兩類。

在上面的描述中又引出一個設(shè)計(jì)點(diǎn)，如何組織新老數(shù)據(jù)，有如下幾種方式。

多版本控制設(shè)計(jì)維度

表?多版本控制設(shè)計(jì)維度

維度

備選

版本存儲方式

集中存儲

分離存儲

版本鏈組織方式

Oldest to New

Newest to Old

老版本管理方式

1、RCR

2、PCR

當(dāng)前openGauss在版本存儲方式、版本鏈組織方式上的設(shè)計(jì)選擇是集中存儲?+ Oldest to New，在清理數(shù)據(jù)舊版本時需要遍歷所有的頁面找到不可見的元組版本然后清除。商用及開源的常見數(shù)據(jù)庫的多版本控制設(shè)計(jì)三維度選擇如表所示。

表?當(dāng)前數(shù)據(jù)庫多版本控制設(shè)計(jì)選擇

數(shù)據(jù)庫

架構(gòu)設(shè)計(jì)選擇

版本存儲方式

版本鏈組織方式

老版本管理方式

常見數(shù)據(jù)庫

分離存儲

Newest to Old

PCR

集中存儲

Oldest to New

RCR

分離存儲

Oldest to New

RCR

不同的多版本控制設(shè)計(jì)都不能做到盡善盡美，都有些不足之處，相關(guān)的缺點(diǎn)如下。

openGauss的ustore存儲模式最大程度結(jié)合各種設(shè)計(jì)的優(yōu)勢，在多版本管理上的架構(gòu)設(shè)計(jì)采取的組合如表所示。

表?ustore在多版本管理上的架構(gòu)設(shè)計(jì)

維度

架構(gòu)設(shè)計(jì)選擇

版本存儲方式

分離存儲

版本鏈組織方式

Newest to old

老版本管理方式

PbRCR（Page Based RCR，基于頁面的行一致性讀）

同時為了事務(wù)能夠跨存儲格式查詢，并復(fù)用現(xiàn)有備份、恢復(fù)、升級等能力，openGauss定義如下的融合引擎架構(gòu)設(shè)計(jì)原則。

ustore架構(gòu)如圖所示。

ustore架構(gòu)示意圖

ustore和astore共用事務(wù)管理、并發(fā)控制、緩沖區(qū)管理、檢查點(diǎn)、故障恢復(fù)管理與介質(zhì)管理器管理。ustore主要功能模塊如表所示。

表? ustore主要功能模塊

模塊

說明

代碼位置

ustore表存取管理

向上對接SQL引擎，提供對ustore表的行級查詢、插入、刪除、修改等操作接口，向下根據(jù)ustore表頁間、頁內(nèi)結(jié)構(gòu)，以及ustore表元組結(jié)構(gòu)，完成對ustore表文件的遍歷和增刪改查操作

主要在“src/gausskernel/storage/access/ustore”目錄（單表文件管理）下

ustore索引存取管理

向上對接SQL引擎，提供對索引表的行級查詢、插入、刪除等操作接口，向下根據(jù)索引表頁間、頁內(nèi)結(jié)構(gòu)，以及索引表元組結(jié)構(gòu)，完成對指定索引鍵的查找和增刪操作

抽象框架代碼在“src/gausskernel/storage/access/ubtree”目錄下

ustore表頁面結(jié)構(gòu)

包括ustore表元組在頁面內(nèi)的具體組織形式，在頁面內(nèi)插入元組操作、頁面整理操作、頁面初始化操作等

主要代碼在“src/gausskernel/storage/access/ustore/knl_upage”目錄中

ustore表元組結(jié)構(gòu)

包括ustore表元組的結(jié)構(gòu)、填充、解構(gòu)、修改、字段查詢、變形等操作

主要代碼在“src/gausskernel/storage/access/ustore/knl_utuple.cpp”文件中

Undo記錄結(jié)構(gòu)

包括undo記錄的結(jié)構(gòu)、填充、編碼、解碼等操作

主要代碼在“src/gausskernel/storage/access/ustore/undo”目錄中

多版本索引

包括?ustore?專用多版本索引?ubtree?的頁面結(jié)構(gòu)、查詢、修改、可見性檢查、垃圾回收等模塊

主要代碼在“src/gausskernel/storage/access/ubtree”目錄中

二、頁面元組結(jié)構(gòu)

本節(jié)介紹行存儲引擎ustore表的頁面元組結(jié)構(gòu)。

元組結(jié)構(gòu)的定義如下：

typedef struct UHeapDiskTupleData {

ShortTransactionId xid;

uint16 td_id : 8, locker_td_id : 8;

uint16 flag;

uint16 flag2;

uint8 t_hoff;

uint8 data[FLEXIBLE_ARRAY_MEMBER];

} UHeapDiskTupleData;

該結(jié)構(gòu)體只是元組頭部的定義，真正的元組內(nèi)容跟在該結(jié)構(gòu)體之后，距離元組頭部起始處的偏移由t_hoff成員保存。上面元組頭部結(jié)構(gòu)體部分成員信息同時也構(gòu)成了該元組的系統(tǒng)字段（字段序號小于0的那些字段）。對各個結(jié)構(gòu)體成員的含義說明如下。

ustore元組頭部比astore元組頭部小一半，因此在相同大小的頁面上，ustore可以放置更多的元組。

在內(nèi)存中，上述元組結(jié)構(gòu)體使用時被嵌入在一個更大的元組數(shù)據(jù)結(jié)構(gòu)體中，除了保存元組內(nèi)容的disk_tuple成員之外，其他的成員保存了該元組的一些其他系統(tǒng)信息，并構(gòu)成了該元組剩余的一些系統(tǒng)字段內(nèi)容，定義如下：

typedef struct UHeapTupleData {

uint32 ?????????????????disk_tuple_size;

uint1 ??????????????????tupTableType = UHEAP_TUPLE;

uint1 ??????????????????tupInfo;

int2 ???????????????????t_bucketId;

ItemPointerData ??????ctid;

Oid ????????????????????table_oid;

TransactionId ????????t_xid_base;

TransactionId ????????t_multi_base;

UHeapDiskTupleData* ?disk_tuple;

} UHeapTupleData;

該結(jié)構(gòu)體幾個主要成員的含義如下。

常用的元組操作接口和說明如表所示。

表? 常用的元組操作接口

函數(shù)名

操作含義

UHeapFormTuple

利用傳入的、各個元組字段的值數(shù)組，生成一條完整的元組，一般用于插入操作

UHeapDeformTuple

利用傳入的完整元組以及各個字段的類型定義，解構(gòu)各個字段的值，生成值數(shù)組，一般用于更新前的準(zhǔn)備工作

UHeapFreetuple

釋放一條元組對應(yīng)的內(nèi)存空間

UHeapCopyTuple

復(fù)制一條完整的元組，包括元組頭和元組內(nèi)容

UHeapSlotGetAttr

獲取一條元組中指定的用戶或系統(tǒng)字段值

UHeapGetSysAttr

獲取一條元組中指定的系統(tǒng)字段值

UHeapCopyHeapTuple

從ustore槽位構(gòu)造一條astore元組

UHeapToHeap

將一條ustore元組轉(zhuǎn)換為一條astore元組

HeapToUHeap

將一條astore元組轉(zhuǎn)換為一條ustore元組

ustore與astore相同，在openGauss中也使用默認(rèn)的8kB頁面。其結(jié)構(gòu)如圖所示。

ustore引擎頁面結(jié)構(gòu)示意圖

在一個頁面中，頁面頭部分對應(yīng)的UHeapPageHeaderData結(jié)構(gòu)體存儲了整個頁面的重要元信息。UHeapPageHeaderData之后有一個共享的頁內(nèi)事務(wù)目錄（Transaction Directory，TD），對應(yīng)元組指針變長數(shù)組。元組指針變長數(shù)組的每個數(shù)組成員存儲了頁面中從后往前的、每個元組的起始偏移和元組長度。如圖4-12所示，真正的元組內(nèi)容從頁面尾部開始插入，向頁面頭部擴(kuò)展；相應(yīng)地，TD插槽目錄與記錄每條元組的元組指針從頁面頭定長成員之后插入，往頁面尾部擴(kuò)展。這樣整個頁面中間就會形成一個空洞，以供后續(xù)插入的元組和元組指針使用。每一個ustore表里的一條具體元組都有一個全局唯一的邏輯地址（和astore表里的元組相同），它由元組所在的頁面號和頁面內(nèi)元組指針數(shù)組下標(biāo)組成。

頁面頭具體結(jié)構(gòu)體定義如下：

typedef struct UHeapPageHeaderData {

PageXLogRecPtr pd_lsn;

uint16 pd_checksum;

uint16 pd_flags;

uint16 pd_lower;

uint16 pd_upper;

uint16 pd_special;

uint16 pd_pagesize_version;

uint16 potential_freespace;

uint16 td_count;

TransactionId pd_prune_xid;

TransactionId pd_xid_base;

TransactionId pd_multi_base;

uint32 reserved;

} UHeapPageHeaderData;

其中各個成員的含義如下。

頁面的主要管理接口如表所示。

表??頁面管理接口函數(shù)

函數(shù)名

操作含義

UPageInit

初始化一個新的ustore頁面

UPageAddItem

在頁面中插入一條新的元組

UHeapPagePruneOptPage

頁面空閑空間整理

為了節(jié)省每個元組存儲空間，元組頭部UHeapDiskTupleData采用32位元組XID的組合設(shè)計(jì)方式。64位的pd_xid_base和pd_multi_base儲存在頁面上，元組上儲存32位的XID。頁面上pd_xid_base和pd_multi_base也需要通過額外的邏輯進(jìn)行維護(hù)：同一個頁面中所有元組實(shí)際的64位XID，一定要在pd_xid_base和pd_xid_base+232之間，所以如果新寫入的事務(wù)號和頁面上現(xiàn)有任意一個元組的XID事務(wù)號差距已經(jīng)超過232，那么需要嘗試對現(xiàn)有元組進(jìn)行基線移位操作，更新pd_xid_base和pd_multi_base。

事務(wù)目錄是一種常用的共享資源。它可以為數(shù)據(jù)頁上的元組（tuple）鏈接相應(yīng)的事務(wù)表（Transaction?Table）及undo子系統(tǒng)中的undo頁面。數(shù)據(jù)庫中的每個表可以自定義事務(wù)目錄的數(shù)量，并可以復(fù)用那些已完成事務(wù)占據(jù)的事務(wù)目錄。

每個數(shù)據(jù)頁默認(rèn)會有4個事務(wù)目錄。根據(jù)并發(fā)需求的不同，事務(wù)目錄的數(shù)量可設(shè)置為2到128之間的任意值。在使用CREATE TABLE命令創(chuàng)建表時添加了一個新的選項(xiàng)INIT_TD以聲明所需的事務(wù)目錄數(shù)量：

CREATE TABLE t1

(

c1 integer;

c2 boolean;

) WITH (INIT_TD=16);

當(dāng)需要為新事務(wù)目錄留位置時，系統(tǒng)會先查找當(dāng)前頁面中是否有空事務(wù)目錄。若無空事務(wù)目錄，系統(tǒng)將遍歷事務(wù)目錄列表來尋找可以復(fù)用的條目。條目是否可以復(fù)用取決于與該條目關(guān)聯(lián)的事務(wù)的狀態(tài)。

通?？梢詮?fù)用那些與已凍結(jié)或已中止的事務(wù)關(guān)聯(lián)的事務(wù)目錄。

對于astore而言，凍結(jié)的XID代表著事務(wù)在所有的會話中都已經(jīng)不再活躍。

而在ustore中，僅當(dāng)一個事務(wù)創(chuàng)建的所有的回滾記錄都被丟棄后，或者說沒有其他的Snapshot需要再觀察該事務(wù)創(chuàng)建的元組歷史版本（tuple version）時，才將該XID視為凍結(jié)。ustore中的undo回收進(jìn)程會維護(hù)一個oldestXidInUndo變量，系統(tǒng)將通過比較XID與該變量來確定XID是否含有回滾記錄。如果XID < oldestXidInUndo，代表所有該XID產(chǎn)生的回滾記錄都已經(jīng)被丟棄。

當(dāng)沒有事務(wù)目錄可以復(fù)用時，事務(wù)目錄將會自動擴(kuò)容以容納更多的條目。需注意的是，事務(wù)目錄的后面跟隨著元組指針區(qū)，在擴(kuò)展時，首先需要將row pointer array向右挪動來騰出空間。擴(kuò)展后，新的事務(wù)目錄條目將會在先前的事務(wù)目錄條目之后依序添加。設(shè)計(jì)上，允許事務(wù)目錄的容量最多擴(kuò)至頁面大小的約25%，即約100個事務(wù)目錄（在8kB大小的頁面中，約20Bytes/事務(wù)目錄）。目前，系統(tǒng)將以每次增加兩個事務(wù)目錄的方式逐步擴(kuò)容，最多擴(kuò)至128個事務(wù)目錄。ustore暫不支持收縮事務(wù)目錄空間。

在擴(kuò)容時，可以增加的總條目數(shù)也取決于當(dāng)前頁面中的可用空間。有時，頁面中的總剩余空間并不能支持事務(wù)目錄的擴(kuò)容。此時若當(dāng)前操作為INSERT或MULTI-INSERT，事務(wù)將會索取一個新的頁面來進(jìn)行操作。若操作為UPDATE或DELETE，事務(wù)將等待10毫秒后重試獲取事務(wù)目錄。Lock timeout設(shè)置可以控制獲取事務(wù)目錄的最大等待時間。在多由短事務(wù)組成的工作負(fù)載中，等待是可以接受的。

PG stats會報告事務(wù)目錄等待等信息，以方便監(jiān)測系統(tǒng)及描述工作負(fù)載。

事務(wù)目錄申請的過程（UHeapPageReserveTransactionSlot函數(shù)）如圖所示。

事務(wù)目錄申請?zhí)幚砹鞒?/p>

如果當(dāng)前事務(wù)需要申請一個新的事務(wù)目錄，且系統(tǒng)中不存在空的事務(wù)目錄時，系統(tǒng)會遍歷所有事務(wù)目錄并尋找可復(fù)用的事務(wù)目錄。

①??系統(tǒng)把已刪除的元組標(biāo)記為死亡，其余的標(biāo)記為閑置。

②??如果系統(tǒng)發(fā)現(xiàn)元組還在活躍狀態(tài)，且相應(yīng)的TD條目存在于步驟（1）給出的凍結(jié)列表之中，系統(tǒng)會把該事務(wù)目錄設(shè)置為UHEAPTUP_SLOT_FROZEN（凍結(jié)）。

③??設(shè)置為凍結(jié)之后，事務(wù)目錄中的XID及Undo指針會被無效化。

①??如果系統(tǒng)發(fā)現(xiàn)元組關(guān)聯(lián)的事務(wù)目錄存在于步驟（3）給出的已提交列表中，系統(tǒng)就把該TD條目的flag設(shè)為UHEAP_INVALID_XACT_SLOT（無效）。

②??此外，這些事務(wù)目錄的XID被重設(shè)為無效XID。但為了維護(hù)undo鏈的完整，undo指針將被保留。

3.?回滾段設(shè)計(jì)與MVCC

舊版本數(shù)據(jù)會集中在回滾段的undo目錄中，為了減少讀寫沖突，舊版本數(shù)據(jù)（回滾記錄）采用追加寫的方式寫入數(shù)據(jù)目錄的undo目錄下。這樣舊版本數(shù)據(jù)的讀取和寫入不會發(fā)生沖突，同一個事務(wù)的舊版本數(shù)據(jù)也會連續(xù)存放，便于進(jìn)行回滾操作。為了減少并發(fā)寫入時的競爭，undo目錄空間被劃分成多個邏輯區(qū)域（UndoZone，回滾段邏輯區(qū)域）。線程會在自己的邏輯區(qū)域上進(jìn)行分配，與其他線程完全隔離，從而寫入舊數(shù)據(jù)分配空間時就不會有額外的鎖開銷。UndoZone還可以按照CPU的NUMA核進(jìn)行劃分，每個線程會從當(dāng)前的NUMA核上的UndoZone進(jìn)行分配，進(jìn)一步提升分配效率。在分配undo空間時會按照事務(wù)粒度進(jìn)行記錄，舊版本數(shù)據(jù)一旦確認(rèn)沒有事務(wù)進(jìn)行訪問，就會進(jìn)行回收。

為了在回滾段的空間尋址，回滾記錄使用8字節(jié)的指針來進(jìn)行尋址，如圖所示。

回滾記錄尋址指針

其中各個字段的含義如下：

舊版本的數(shù)據(jù)采用回滾記錄的格式存入回滾段中，其中回滾記錄的格式如下所示：

Class UndoRecord {

…

UndoRecordHeader whdr_;

UndoRecordBlock wblk_;

UndoRecordTransaction wtxn_;

UndoRecordPayload wpay_;

UndoRecordOldTd wtd_;

UndoRecordPartition wpart_;

UndoRecordTablespace wtspc_;

StringInfoData rawdata_;

}

其中，除了rawdata_代表了舊版本數(shù)據(jù)，其他成員均為結(jié)構(gòu)體，下面對每個結(jié)構(gòu)體分別進(jìn)行說明。

whdr_成員由下面的結(jié)構(gòu)組成：

typedef struct {

TransactionId xid;

CommandId cid;

Oid reloid;

Oid relfilenode;

uint8 utype;

uint8 uinfo;

} UndoRecordHeader;

各個字段的含義如下。

wblk_成員由下面的結(jié)構(gòu)組成：

typedef struct {

UndoRecPtr blkprev;

BlockNumber blkno;

OffsetNumber offset;

} UndoRecordBlock;

wtxn_成員由下面的結(jié)構(gòu)組成。

typedef struct {

UndoRecPtr prevurp;

} UndoRecordTransaction;

prevurp：當(dāng)一個事務(wù)的回滾記錄跨越兩個UndoZone時，后續(xù)的回滾記錄使用此指針指向前一條回滾記錄。

wpay_成員由下面的結(jié)構(gòu)組成。

typedef struct {

UndoRecordSize payloadlen;

}

payloadlen：rawdata_的長度。

wtd_成員由下面的結(jié)構(gòu)組成。

typedef struct {

TransactionId oldxactid;

} UndoRecordOldTd;

oldxactid：舊版本數(shù)據(jù)里事務(wù)目錄的事務(wù)ID。

wpart_成員由下面的結(jié)構(gòu)組成。

typedef struct {

Oid partitionoid;

} UndoRecordPartition;

partitionoid：分區(qū)表的分區(qū)對象OID。

wtspc_成員由下面的結(jié)構(gòu)組成。

typedef struct {

Oid tablespace;

} UndoRecordTablespace;

tablespace：表空間的OID。

回滾段使用事務(wù)目錄來記錄每個事務(wù)分配的undo空間，便于事務(wù)回滾和回收。事務(wù)發(fā)生回滾時，會讀取事務(wù)目錄中記錄的undo空間的起始位置，再讀取undo空間中的回滾記錄進(jìn)行回滾操作，其中回滾記錄中的字段如下：

class TransactionSlot {

TransactionId xactId_;

UndoRecPtr startUndoPtr_;/*事務(wù)分配的undo空間開始*/

UndoRecPtr endUndoPtr_;/*事務(wù)分配的undo空間結(jié)束*/

uint8 info_;/*標(biāo)記：如事務(wù)回滾狀態(tài)*/

Oid dbId_;/*數(shù)據(jù)庫對象ID*/

}

回滾段提供分配undo空間和更新事務(wù)目錄的接口，主要接口如表所示。

表?回滾段主要接口

接口名

含義

AllocateUndoSpace

為回滾記錄分配undo空間

UpdateTransactionSlot

更新事務(wù)目錄

以ustore的刪除操作為例，undo空間分配流程如下。

undo空間需要回收回滾記錄來保證undo空間不會無限膨脹，一旦事務(wù)id小于當(dāng)前快照中最小的Xmin（oldestXmin），回滾記錄中的舊版本數(shù)據(jù)就不會被訪問，此時就可以對回滾記錄進(jìn)行回收。

如前述描述undo空間中的回滾記錄按照事務(wù)ID遞增的順序存放在UndoZone中，回收的條件如下所示。

undo回收過程

如上圖所示，UndoZone1中回收到小于oldestXmin的已提交事務(wù)16068，UndoZone2中回收到16050，UndoZone m回收到16056。而UndoZone n回收到事務(wù)16012，而事務(wù)16014待回滾但未發(fā)生回滾，因此UndoZone?n回收事務(wù)id上限只到16014。其他zone的上限是oldestXmin，oldestXidInUndo會取所有undozone上的上限最小值，因此oldestXidInUndo等于16014。undo回收主要函數(shù)如表所示。

表?undo回收主要函數(shù)

函數(shù)名

操作含義

UndoRecycleMain

回收線程的入口函數(shù)，會在每個zone上調(diào)用RecycleUndoSpace函數(shù)

RecycleUndoSpace

按照前述條件回收undo空間，記錄日志

ustore的可見性檢查和astore類似，將快照CSN和元組刪除和插入事務(wù)的CSN進(jìn)行比較，判斷元組是否可見。ustore和astore使用同一套事務(wù)管理機(jī)制和快照管理機(jī)制。

ustore和astore最大的區(qū)別在于astore會在頁面上保留舊版本數(shù)據(jù)，而ustore在將舊版本數(shù)據(jù)放到回滾段統(tǒng)一存放。在需要獲取舊版本數(shù)據(jù)時，astore可以直接從tuple的頭部讀取到元組的插入和刪除的事務(wù)號(XID)，來判斷元組的可見性。但是ustore需要從回滾段里讀取舊版本的事務(wù)信息，來判斷舊版本是否可見。由于從回滾段中讀取舊版本數(shù)據(jù)存在相對昂貴的開銷，ustore通過一系列的優(yōu)化手段來避免從回滾段中讀取舊版本數(shù)據(jù)。

ustore在獲取元組時，會先檢查對應(yīng)的事務(wù)目錄。事務(wù)目錄分成有效和無效兩種。當(dāng)事務(wù)目錄是有效的，ustore直接就會得到元組上最新的事務(wù)。

如果事務(wù)目錄被凍結(jié)（FROZEN），意味著元組已經(jīng)在所有的事務(wù)中都會可見。如果事務(wù)目錄中的事務(wù)id小于oldestXidInUndo，意味著元組已經(jīng)足夠舊在所有事務(wù)中都可見。同時會把事務(wù)目錄置成凍結(jié)，來加速后續(xù)的查詢。

如果元組被標(biāo)記有一個無效事務(wù)目錄，意味著修改元組的事務(wù)已經(jīng)提交，并且比當(dāng)前的事務(wù)目錄中的事務(wù)舊。此時ustore會使用事務(wù)目錄中的事務(wù)進(jìn)行可見性判斷。如果可見，意味著修改元組的事務(wù)更已經(jīng)可見，就不需要從undo目錄中再讀取事務(wù)信息。

元組查詢過程

元組不可見的場景，ustore會從undo目錄中讀取回滾記錄中的舊版本數(shù)據(jù)查找元組。例子如上圖所示。查找tbl表中c1=1的數(shù)據(jù)項(xiàng)，從索引中讀取到數(shù)據(jù)項(xiàng)位于block 1和offset 2，使用UHeapTupleFetch函數(shù)再從block 1中查詢到元組，需要判斷該元組的可見性。

（1）?從元組的TD讀到ITL2，和astore類似，根據(jù)CSN的大小，判斷TD2中的XID不可見，需要使用GetTupleFromUndo函數(shù)讀取回滾記錄。

（2）?GetTupleFromUndo函數(shù)調(diào)用GetTupleFromUndoRecord函數(shù)讀取回滾記錄，使用InplaceSatisfyUndoRecord函數(shù)判斷其中的block 1和offset 2是滿足要求的元組。但是XID=1610可以判斷出當(dāng)前頁面的tuple不可見，ustore繼續(xù)查詢更老的版本。由于舊元組的TD?1和當(dāng)前的TD 2不一致，使用UHeapUpdateTDInfo從TD?2 undo鏈條進(jìn)行切換，根據(jù)舊元組的TD 1找到當(dāng)前的undo指針找到前一次修改。

（3） 再次讀取到回滾記錄，其中的block 1和offset 1并非要找的元組，ustore繼續(xù)查詢更老的版本，根據(jù)blkprev指針讀取前一次修改。

（4）?讀取到回滾記錄，其中的block 1和offset 3并非要找的元組，ustore繼續(xù)查詢更老的版本，根據(jù)blkprev指針讀取前一次修改。

（5）?讀取到回滾記錄，其中的block 1和offset 2是要求的元組，ustore判斷可見性。根據(jù)CSN的大小，事務(wù)可見。因此前一次命中的元組可見，即(1, abc)可見，因此查找到元組的c2等于abc。

4.?多版本索引

在openGauss中實(shí)現(xiàn)了多版本索引ubtree，是專用于ustore的B-Tree索引變種，相比原有的B-Tree索引有如下差異點(diǎn)。

ubtree實(shí)現(xiàn)了索引訪問接口所要求的全部接口，如表所示：

表? ubtree訪問接口函數(shù)

接口名稱

對應(yīng)函數(shù)

接口含義

aminsert

ubtinsert

插入一個索引元組

ambeginscan

ubtbeginscan

開始一次索引掃描

amgettuple

ubtgettuple

獲取一個索引元組

amgetbitmap

ubtgetbitmap

通過索引掃描獲取所有元組

amrescan

ubtrescan

重新開始一次索引掃描

amendscan

ubtendscan

結(jié)束索引掃描

ammarkpos

ubtmarkpos

標(biāo)記一個掃描位置

amrestpos

ubtrestpos

恢復(fù)到一個掃描位置

ammerge

ubtmerge

合并多個索引

ambuild

ubtbuild

建立一個索引

ambuildempty

ubtbuildempty

建立一個空索引

ambulkdelete

ubtbulkdelete

批量刪除索引元組

amvacuumcleanup

ubtvacuumcleanup

索引后置清理

amcanreturn

ubtcanreturn

是否支持?Index?Only Scan

amcostestimate

ubtcostestimate

索引掃描代價估計(jì)

amoptions

ubtoptions

索引選項(xiàng)

此外，還實(shí)現(xiàn)了新增的的索引刪除函數(shù)UBTreeDelete。

多版本索引層次結(jié)構(gòu)與B-Tree索引基本相同，非葉子節(jié)點(diǎn)與B-Tree索引保持一致，僅頁尾的Special字段有所不同。ubtree中的Special字段UBTPageOpaqueDataInternal如下所示：

typedef struct UBTPageOpaqueDataInternal {

……

/*?以上部分與BTPageOpaqueDataInternal一致?*/

TransactionId last_delete_xid; ?/*?記錄頁面上最后一次刪除事務(wù)的?XID?*/

TransactionId xid_base; ??????????/*?頁面上的?xid-base?*/

int16 activeTupleCount; ??????????/*?頁面上活躍元組計(jì)數(shù)?*/

} UBTPageOpaqueDataInternal;

typedef UBTPageOpaqueDataInternal* UBTPageOpaqueInternal;

其中l(wèi)ast_delete_xid與activeTupleCount用于索引的自治式回收，會在ustore中的“6.?空間管理和回收”一節(jié)詳細(xì)講解。

通過xid_base字段，頁面上的XID可以僅儲存基于該xid_base的一個32位偏移（Offset），節(jié)省XID存儲的空間開銷。實(shí)際的XID為頁面上的xid_base加上存儲的XID（也就是偏移）得到。

多版本中的葉子頁面的結(jié)構(gòu)如圖所示。

ubtree?葉子頁面結(jié)構(gòu)示意圖

與astore堆頁面中維護(hù)版本信息的方法類似，ubtree的葉子節(jié)點(diǎn)中每個索引元組尾部都附加了對應(yīng)的xmin和xmax。由于索引只是用于加速搜索的結(jié)構(gòu)，本身不與歷史版本概念強(qiáng)相關(guān)，僅通過xmin和xmax來標(biāo)識這個索引元組是從什么時候開始有效的，又是什么時候被刪除的，而不像astore中堆元組一樣會有指向舊版本元組的指針。

新插入的索引元組尾部用于存放xmin和xmax?空間在ubtinsert函數(shù)執(zhí)行的過程中預(yù)留出來。預(yù)留的空間及xmin在索引元組插入時通過UBTreePageAddTuple函數(shù)中寫入頁面，而xmax在索引元組刪除時通過UBTreeDeleteOnPage函數(shù)中寫入頁面。

在UBTreePagePruneOpt函數(shù)中，索引元組通過其xmin和xmax信息來判斷該元組是否已經(jīng)無效（Dead），進(jìn)而進(jìn)行獨(dú)立的頁面清理。該函數(shù)會嘗試清除所有無效的元組，并進(jìn)行相應(yīng)的碎片整理。

索引掃描時會調(diào)用UBTreeFirst函數(shù)定位到第一個滿足掃描條件的索引元組，然后調(diào)用UBTreeReadPage獲取當(dāng)前頁面中符合索引掃描條件，且能夠通過可見性檢查的元組?？梢娦詸z查通過UBTreeVisibilityCheckXid函數(shù)及UBTreeVisibilityCheckCid函數(shù)處理，其基本邏輯與astore類似，通過xmin與xmax及當(dāng)前的快照進(jìn)行可見性判斷。

在ubtree中，索引元組除了按照索引列有序排列之外，對于索引列相同的元組，還將其對應(yīng)堆元組的TID作為第二關(guān)鍵字進(jìn)行排序。其具體實(shí)現(xiàn)大致都集中在ubtbuild函數(shù)及ubtinsert函數(shù)調(diào)用的過程中，這中間對索引列相同的元組會按照TID來進(jìn)行額外的比較。實(shí)現(xiàn)還借助了BTScanInsert結(jié)構(gòu)體，該結(jié)構(gòu)體定義如下：

typedef struct BTScanInsertData {

bool heapkeyspace; ???????/*?標(biāo)志索引是否額外按?TID?排序?*/

bool anynullkeys; ????????/*?標(biāo)志待查找的索引元組是否有為?NULL的列?*/

bool nextkey; ?????????????/*?標(biāo)志是否希望尋找第一個大于掃描條件的元組?*/

bool pivotsearch; ????????/*?標(biāo)志是否希望查找?Pivot?元組?*/

ItemPointer scantid; ?????/*?用于作為排序依據(jù)的?TID?*/

int keysz; ?????????????????/* scankeys?數(shù)組的大小?*/

ScanKeyData scankeys[INDEX_MAX_KEYS];

} BTScanInsertData;

在索引元組將TID作為第二關(guān)鍵字排序之后，用于劃分搜索空間的非葉子節(jié)點(diǎn)元組及葉子節(jié)點(diǎn)的Hikey元組（統(tǒng)稱Pivot元組）也需要攜帶對應(yīng)的TID信息。這會使得Pivot元組占用空間增加，非葉子的扇出（fan?out）降低。為了避免這一特性導(dǎo)致的扇出降低，若不需要比較TID即可區(qū)分兩個葉子頁面，則對應(yīng)的Pivot原則中就不需要儲存TID信息。類似地，Pivot元組中也可以去掉一些不需要進(jìn)行比較的索引列，這一邏輯在UBTreeTruncate函數(shù)中進(jìn)行處理。原則是當(dāng)比較前幾列就可以區(qū)分兩個葉子頁面時，Pivot元組中就不需要儲存后續(xù)的列。

對于原有的B-Tree索引而言，主要有四類操作：索引創(chuàng)建、索引掃描、索引插入以及索引刪除。下面將依次進(jìn)行介紹。

索引創(chuàng)建操作由索引上的ubtbuild函數(shù)及ustore上的IndexBuildUHeapScan函數(shù)配合完成。IndexBuildUHeapScan函數(shù)負(fù)責(zé)掃描對應(yīng)的ustore表，并取出每個元組的最新版本（遵循SnapshotNow的語義）以及其對應(yīng)的xmin和xmax。若發(fā)現(xiàn)某個元組存在被就地更新的舊版本，則會將該索引標(biāo)記為HotChainBroken。被標(biāo)記為HotChainBroken的索引，會復(fù)用astore原有的邏輯，禁止隔離級別為可重復(fù)讀（Read?Repeatable）的老事務(wù)訪問。ubtbuild函數(shù)會接收IndexBuildUHeapScan傳過來的元組，將其按照索引列及TID排序后依次插入到索引頁面中，并構(gòu)建相應(yīng)的元頁面及上層頁面。整個創(chuàng)建流程需要將所有頁面都記錄到XLOG中，并強(qiáng)制將存儲管理中的內(nèi)容刷到永久存儲介質(zhì)后才算成功結(jié)束。

索引掃描與B-Tree索引基本一致，但是需要對索引元組進(jìn)行可見性檢查。沒有通過可見性檢查的索引元組不會被返回，通過可見性檢查的元組仍需要在ustor?堆表上進(jìn)行可見性檢查，并找到正確的可見版本。在IndexOnlyScan場景中，通過可見性檢查的元組即可直接返回，不需要再訪問堆表。

不過索引進(jìn)行可見性檢查時，由于索引元組只存放了xmin和xmax而沒有CID（對應(yīng)“4.2.3??astore”節(jié)堆表元組中的t_cid字段）信息，如果發(fā)現(xiàn)了當(dāng)前事務(wù)修改過的索引元組則不能正確地通過CID來判斷其可見性。此時會將該元組視為可見，但會標(biāo)記xs_recheck_itup，告知ustore的數(shù)據(jù)頁面需要在取到對應(yīng)的數(shù)據(jù)元組后，再次構(gòu)建對應(yīng)的索引元組并與返回的索引元組進(jìn)行比較，來確認(rèn)該索引元組是不是真正可見。相關(guān)邏輯在?UBTreeVisibilityCheckXid、UBTreeVisibilityCheckCid以及RecheckIndexTuple函數(shù)中進(jìn)行處理。

索引元組需要存儲對應(yīng)的xmin和xmax版本信息，但其所占用的空間并不表現(xiàn)在IndexTupleSize中，而是對外部透明。索引插入的接口函數(shù)為ubtinsert，為了正確插入帶有版本信息的元組，需要在執(zhí)行插入前增加IndexTupleSize以預(yù)留用于儲存版本信息的空間。真正將元組插入到頁面的時候，會將版本信息所占用的空間大小從IndexTupleSize中去除。

在索引插入的過程中若頁面空間不足，會首先調(diào)用UBTreePagePruneOpt函數(shù)嘗試對已經(jīng)無效的元組進(jìn)行清理。若清理失敗或清理成功后空間仍然不足，會進(jìn)行索引頁面分裂。索引頁面分裂會在UBTreeInsertOnPage函數(shù)中進(jìn)行。ubtree中存在兩種分裂策略：default以及insertpt。其中default策略會將原頁面上的內(nèi)容均勻地分配到兩個頁面上，而insertpt會根據(jù)新插入元組的插入規(guī)律、插入位置及TID等信息選擇合適的分裂點(diǎn)。

在ubtree需要申請新的頁面時，并不會像原有的B-Tree索引一樣調(diào)用_bt_getbuf通過FSM來查找可用頁面。ubtree帶有自治式的空間管理機(jī)制，通過UBtreeGetNewPage函數(shù)獲取新頁面。該自治式空間管理機(jī)制將在空間管理和回收部分介紹。

索引刪除操作用于在堆元組被刪除的同時，將對應(yīng)的索引元組也標(biāo)上對應(yīng)的xmax。索引刪除的流程與插入類似，通過二分查找定位到待刪除元組的位置，并將xmax寫入到對應(yīng)的位置。需要注意的是，要刪除的元組是索引列以及TID都匹配，且還未被寫入xmax的那個元組，這部分邏輯在UBTreeFindDeleteLoc函數(shù)中處理。在最后會調(diào)用UBTreeDeleteOnPage函數(shù)為對應(yīng)的索引元組寫上xmax，更新頁面上的last_delete_xid以及activeTupleCount，并在檢測到activeTupleCount為0時將該頁面放入潛在空頁隊(duì)列（Potential?Empty Page Queue）中。關(guān)于潛在空頁隊(duì)列會在空間管理和回收部分介紹。

openGauss中的ustore表訪存接口如表4-24所示。由于openGauss中ustore表只有一種頁面和元組結(jié)構(gòu)，因此在上述接口中，直接實(shí)現(xiàn)了底層的頁面和元組操作流程。

表? ustore表訪存接口

函數(shù)名稱

接口含義

heap_open

打開一個ustore表，得到表的相關(guān)元信息

heap_close

關(guān)閉一個ustore表，釋放該表的加鎖或引用

UHeapRescan

重新開始ustore表（順序）掃描操作

UHeapGetNext

（順序）獲取下一條元組

UHeapGetTupleFromPage

UHeapGetNext內(nèi)部實(shí)現(xiàn)，單頁校驗(yàn)?zāi)Ｊ?/p>

UHeapScanGetTuple

UHeapGetNext內(nèi)部實(shí)現(xiàn)，單條校驗(yàn)?zāi)Ｊ?/p>

UHeapGetPage

（順序）獲取并掃描下一個ustore表頁面

UHeapInsert

在ustore表中插入一條元組

UHeapMultiInsert

在ustore表中批量插入多條元組

UHeapDelete

在ustore表中刪除一條元組

UHeapUpdate

在ustore表中更新一條元組

UHeapLockTuple

在ustore表中對一條元組加鎖

6.?空間管理和回收

不同于astore的空間管理和回收機(jī)制，ustore實(shí)現(xiàn)了自治式的空間管理機(jī)制。ustore里堆以及索引的空間分配和回收都在業(yè)務(wù)運(yùn)行的過程中平穩(wěn)地進(jìn)行，不依賴中量級的VACUUM及AUTOVACUUM清理機(jī)制。

ustore中堆頁面的自治式空間管理，建立在與astore類似的輕量級堆頁面清理機(jī)制的基礎(chǔ)上。在執(zhí)行DML及DQL操作的過程中，ustore都會進(jìn)行堆數(shù)據(jù)頁面清理，以取代VACUUM清理機(jī)制。UHeapPagePruneOptPage函數(shù)是頁面清理的入口函數(shù)，會清理已經(jīng)提交的被刪除元組。

對于astore而言，復(fù)用數(shù)據(jù)元組的行指針前必須保證對應(yīng)的索引元組已經(jīng)被清理。這是為了防止通過索引元組訪問已經(jīng)被復(fù)用的行指針，導(dǎo)致取到錯誤的數(shù)據(jù)。在astore中需要通過VACUUM操作將這樣的無效索引元組統(tǒng)一清除掉后才能復(fù)用行指針，這使得堆頁面和索引頁面的清理邏輯耦合在一起，也會導(dǎo)致間斷性的大量I/O。在ustore中能高效地單獨(dú)進(jìn)行數(shù)據(jù)和索引頁面的清理，因?yàn)閹в邪姹拘畔⒌膗btree能夠獨(dú)立檢測并過濾掉無效的索引元組，不會通過無效索引元組訪問對應(yīng)的數(shù)據(jù)表。

堆頁面的空間管理機(jī)制復(fù)用openGauss中的FSM來管理UHeap中的可用空間。在UHeapPagePruneOptPage函數(shù)成功對頁面進(jìn)行清理后，會將其空閑空間刷新到對應(yīng)的FSM頁面中。為了避免每次頁面清理都需要更新整個樹狀結(jié)構(gòu)的FSM，從而帶來額外的開銷，引入了一個更新整個FSM的概率計(jì)算?？紤]當(dāng)前清理后的可用空間占預(yù)留可用空間（Reserved?Free Space）閾值的百分比，計(jì)算得出清理一個頁面后調(diào)用FreeSpaceMapVacuum函數(shù)的概率。也就是說，頁面清理獲得的可用空間越大，更新整個FSM的概率也就越大。

當(dāng)數(shù)據(jù)元組被刪除時，會在頁面上記錄對應(yīng)的潛在空閑空間（Potential?Free Space），該值用于估計(jì)頁面上的空閑空間。在運(yùn)行過程中，有多個場景會調(diào)用UHeapPagePruneOpt對頁面嘗試進(jìn)行清理。DML語句執(zhí)行過程中，INSERT、UPDATE以及DELETE操作都會拿到頁面的寫鎖。如果發(fā)現(xiàn)空間不足，或者檢測到潛在空閑空間到達(dá)某個閾值，會嘗試對頁面進(jìn)行清理。DQL查詢語句執(zhí)行的過程中若檢測到頁面上潛在空閑空間到達(dá)閾值，也同樣會嘗試申請頁面的寫鎖；如果拿到了頁面的寫鎖，會嘗試對頁面進(jìn)行清理。

存在可清理的元組，但一直不被訪問的頁面不能通過這一機(jī)制正確地清理。為了解決這一問題，引入了基于概率的清理方案。在RelationGetBufferForUTuple函數(shù)尋找新的可用空間時，若通過FSM發(fā)現(xiàn)沒有足夠的可用空間，在對物理文件進(jìn)行擴(kuò)展前，會“隨機(jī)”選取一些頁面進(jìn)行清理。該機(jī)制并非完全隨機(jī)選取，在多次嘗試后選取的頁面會覆蓋到整個關(guān)系的全部頁面。為了性能考慮，該過程中默認(rèn)最多選取10個頁面進(jìn)行清理，該數(shù)量可以通過GUC參數(shù)max_search_length_for_prune進(jìn)行設(shè)置。具體的頁面選取數(shù)量通過DeadTupleRatio以及PruneSuccessRatio計(jì)算得出。其中DeadTupleRatio表示該表中無效元組的大致比例，該變量以統(tǒng)計(jì)信息的方式進(jìn)行收集，在進(jìn)行DML的過程中會進(jìn)行更新；PruneSuccessRatio大致表示近幾次嘗試清理的成功率。

索引頁面的空間管理不依靠FSM數(shù)據(jù)結(jié)構(gòu)，而是依靠特有的URQ（UBtree Recycle Queue）結(jié)構(gòu)，簡稱為回收隊(duì)列。索引回收隊(duì)列單獨(dú)儲存在ubtree索引對應(yīng)的.urq文件中，沒有原有B-Tree索引的.fsm文件。索引回收隊(duì)列相關(guān)代碼在“ubtrecycle.cpp”文件中。涉及到的主要函數(shù)接口見表。

表??索引回收隊(duì)列主要接口

函數(shù)名稱

接口含義

UBTreeTryRecycleEmptyPage

嘗試從潛在空頁隊(duì)列回收一個頁面

UBTreeGetAvailablePage

獲取有效頁面（潛在空頁或空閑頁面）

UBTreeRecordUsedPage

記錄被成功使用的頁面

UBTreeRecordEmptyPage

記錄潛在的空頁

UBTreeGetNewPage

獲取新的可用頁面

索引中的回收隊(duì)列分為兩部分，一部分是潛在空頁隊(duì)列（Potential Empty Page Queue），一部分是可用頁面隊(duì)列（Available Page Queue）。兩個隊(duì)列都是跨頁面的循環(huán)隊(duì)列，其中每個元素都會儲存blkno以及XID。其中blkno表示該元素對應(yīng)索引頁面的block number；XID表示該頁面在哪個時刻能夠被回收或復(fù)用。這些元素在循環(huán)隊(duì)列單個頁內(nèi)按照XID的順序進(jìn)行排序，以便于快速找到XID??。ㄗ羁赡鼙换厥栈驈?fù)用）的頁面。其結(jié)構(gòu)如圖所示。

ubtree回收隊(duì)列結(jié)構(gòu)示意圖

對于潛在空頁隊(duì)列而言，里面存放頁內(nèi)元組已經(jīng)被全部刪除但還沒有全部無效的頁面，其中的XID就標(biāo)志頁面中最后一個元組無效的可能時機(jī)。在系統(tǒng)整體的oldestXmin超過該XID后，該頁面就有可能被從索引上刪除，但也可能因?yàn)樾虏迦朐M或刪除元組的事務(wù)中止而導(dǎo)致頁面不能被刪除。潛在空頁隊(duì)列中的頁面在成功被刪除后會被放入可用頁面隊(duì)列，并記錄刪除時最新事務(wù)的XID。

對于可用頁面隊(duì)列而言，里面存放已經(jīng)被刪除，可以或即將可以被復(fù)用的頁面。其中XID就表示該頁面可以被復(fù)用的時機(jī)。這樣的頁面復(fù)用時延是來自B-Tree索引頁面刪除時可能的并發(fā)訪問導(dǎo)致的，可以參考nbtree文件夾下README?關(guān)于頁面刪除的部分。

在ubtree進(jìn)行索引刪除時，會更新頁面上的last_delete_xid字段以及activeTupleCount字段。若更新后activeTupleCount變?yōu)?，會將該頁面放入潛在空頁隊(duì)列，并將此時的last_delete_xid作為對應(yīng)的可回收時間點(diǎn)。

在業(yè)務(wù)運(yùn)行的過程中，索引會通過UBTreeTryRecycleEmptyPage函數(shù)不斷嘗試對潛在空頁隊(duì)列中的頁面進(jìn)行回收。在索引申請新的頁面時，會通過UBTreeGetNewPage函數(shù)與可用頁面隊(duì)列交互，查找當(dāng)前可用的空閑頁面。當(dāng)可用頁面隊(duì)列中沒有可用頁面時，一般會通過擴(kuò)展索引物理文件的方式來獲得新的頁面。但也存在物理文件批量擴(kuò)展，或擴(kuò)展后還未來得及使用就出錯退出的情況。此時在回收隊(duì)列的元信息頁面中保存了已正確追蹤的頁面數(shù)量，若該數(shù)量少于整個索引表的頁面數(shù)量，會嘗試去使用這一部分未追蹤的頁面，并更新已追蹤的頁面數(shù)量。

與astore相同，ustore也提供VACUUM語句來讓用戶主動執(zhí)行對某個ustore表及其上的索引進(jìn)行中量級清理。其對外表現(xiàn)與astore一致，可參考astore的空間管理和回收內(nèi)容。

在ustore中，中量級清理同樣通過lazy_vacuum_rel函數(shù)進(jìn)入，但不會調(diào)用lazy_scan_heap，而是調(diào)用LazyScanUHeap函數(shù)來進(jìn)行數(shù)據(jù)頁面的清理。在進(jìn)行索引清理時，會調(diào)用lazy_vacuum_index接口及LazyVacuumHeap函數(shù)來清理索引文件和堆表文件，索引清理時會調(diào)用ubtbulkdelete函數(shù)。

重量級的VACUUM FULL也與astore一致，會清理無效數(shù)據(jù)并對數(shù)據(jù)空間和索引空間重新進(jìn)行組織。重量級清理的對外接口是cluster_rel函數(shù)，本質(zhì)上是重新對數(shù)據(jù)進(jìn)行聚簇，清理過程中會阻塞對該表的所有操作。

數(shù)據(jù)庫

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。