[發(fā)明專利]一種內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法

有效

• 申請?zhí)枺?/td>: 202110894627.6
• 申請日: 2021-08-05
• 公開（公告）號(hào): CN113688130B
• 公開（公告）日: 2023-10-13
• 發(fā)明（設(shè)計(jì)）人: 張華海
• 申請（專利權(quán)）人: 上海沄熹科技有限公司
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2455
• 代理公司: 濟(jì)南信達(dá)專利事務(wù)所有限公司 37100
• 代理人: 郗艷榮

1.一種內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：基于RocksDB存儲(chǔ)引擎的Memtable管理機(jī)制，在Memtable內(nèi)部新建ART索引用以取代skiplist索引，采用ART索引加Hash索引的雙索引機(jī)制查詢key-value，優(yōu)化RocksDB存儲(chǔ)引擎的讀性能，從而實(shí)現(xiàn)RocksDB內(nèi)存引擎模式，減少磁盤讀寫，提高查詢速度。

2.根據(jù)權(quán)利要求1所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于，具體實(shí)現(xiàn)過程如下：

1)將插入Memtable的數(shù)據(jù)轉(zhuǎn)為插入到ART算法管理的內(nèi)存塊中，并將ART算法的葉節(jié)點(diǎn)地址加入Hash索引中；

2)修改Memtable刷盤的邏輯，使得Memtable永不轉(zhuǎn)換imMemtable，通過內(nèi)存塊的形式進(jìn)行刷盤，內(nèi)存塊通過雙向鏈表進(jìn)行管理；

3)執(zhí)行查詢操作時(shí)，先從Hash表中查詢，然后查詢ART樹，最后查詢磁盤SST文件。

3.根據(jù)權(quán)利要求2所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟1)中，寫入的數(shù)據(jù)在內(nèi)存中以內(nèi)存塊的形式存儲(chǔ)，通過雙向鏈表對key進(jìn)行排序，雙向鏈表的每個(gè)節(jié)點(diǎn)內(nèi)存儲(chǔ)當(dāng)前key對應(yīng)的多個(gè)版本數(shù)據(jù)形成的鏈表，雙向鏈表的每個(gè)節(jié)點(diǎn)指向內(nèi)存塊存儲(chǔ)的該key對應(yīng)的key-value；所述ART索引用于快速定位雙向鏈表的特定節(jié)點(diǎn)，所述Hash索引用于快速查詢ART樹的葉子節(jié)點(diǎn)的地址；

寫入數(shù)據(jù)時(shí)，首先通過Hash索引與ART索引計(jì)算待插入的葉子結(jié)點(diǎn)位置，然后根據(jù)ART的葉子節(jié)點(diǎn)添加雙向鏈表，通過雙向鏈表對業(yè)務(wù)key進(jìn)行排序。

4.根據(jù)權(quán)利要求3所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟1)中，當(dāng)有新的key插入葉子節(jié)點(diǎn)時(shí)，使用ART算法快速定位到雙向鏈表的插入節(jié)點(diǎn)進(jìn)行插入，同時(shí)增加hash表的插入邏輯，對Hash表加鎖；將key的String類型作為Hash表中的key，將葉子節(jié)點(diǎn)指針位置作為Hash表中的value插入到Hash表中。

5.根據(jù)權(quán)利要求2所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟1)中，新建一個(gè)ART索引維護(hù)類，使用ART算法替換Memtable中的skiplist算法；在ART索引維護(hù)類中新建一個(gè)Hash索引類成員HashMap，用于ART索引葉節(jié)點(diǎn)的快速查詢。

6.根據(jù)權(quán)利要求5所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟1)中，使用PureMemRep類繼承public MemtableRep，新增Memtable的內(nèi)存?zhèn)}庫管理類，使用InlineART類替換InlinSkiplist類，用以實(shí)現(xiàn)基于ART算法的內(nèi)存數(shù)據(jù)索引；在InlineART類中增加類成員HashTable，hash表中存放ART葉節(jié)點(diǎn)和key。

7.根據(jù)權(quán)利要求2所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟2)中，啟用異步刷盤線程，維護(hù)所有內(nèi)存塊的隊(duì)列，隊(duì)列按照內(nèi)存塊的上次刷盤時(shí)間排序；線程從隊(duì)列取內(nèi)存塊，并將內(nèi)存塊增量的kv數(shù)據(jù)進(jìn)行落盤，追加到文件末尾或形成新的磁盤SST文件。

8.根據(jù)權(quán)利要求2所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟3)中，調(diào)用Memtable::NewIterator接口創(chuàng)建基于ART樹的Iterator，用于遍歷ART樹中的節(jié)點(diǎn)；

新建Memtable::NewHashIterator接口，增加ReadOptions參數(shù)，用于判斷是否為MVCCGet讀?。蝗绻莿t調(diào)用NewHashIterator接口，直接從Hash表中查找存儲(chǔ)key的雙向鏈表所對應(yīng)的葉子節(jié)點(diǎn)，如果不是則調(diào)用NewIterator接口在hash索引中查找葉子節(jié)點(diǎn)，若沒有再去ART索引查詢；

最終得到ART樹的葉子節(jié)點(diǎn)，得到存儲(chǔ)多版本key的雙向鏈表，通過遍歷雙向鏈表得到內(nèi)存塊中的數(shù)據(jù)。

9.根據(jù)權(quán)利要求8所述的內(nèi)存數(shù)據(jù)庫存儲(chǔ)引擎管理方法，其特征在于：所述步驟3)中，當(dāng)讀取多版本數(shù)據(jù)即MVCCGet數(shù)據(jù)時(shí)，在Hash表中取出key對應(yīng)的葉子節(jié)點(diǎn)，然后從葉子節(jié)點(diǎn)對應(yīng)的雙向鏈表中取出對應(yīng)的key；如果hash索引中沒有查到key，說明已經(jīng)數(shù)據(jù)已經(jīng)落盤，則去磁盤SST文件中查找；

當(dāng)讀取非MVCCGet數(shù)據(jù)時(shí)，則在hash索引中查找對應(yīng)的葉子節(jié)點(diǎn)，若沒找到對應(yīng)的葉子節(jié)點(diǎn)，則在ART樹中查找葉子節(jié)點(diǎn)，若ART樹中沒有找到對應(yīng)的葉子節(jié)點(diǎn)，則去磁盤SST文件中查找。