[發(fā)明專利]一種內(nèi)存數(shù)據(jù)庫KV存儲引擎索引的創(chuàng)建方法

有效

• 申請?zhí)枺?/td>: 202011201566.2
• 申請日: 2020-11-02
• 公開（公告）號: CN112269786B
• 公開（公告）日: 2023-02-03
• 發(fā)明（設(shè)計）人: 梁波;孫思清;張煒剛;賈德星;張暉;高傳集
• 申請（專利權(quán)）人: 浪潮云信息技術(shù)股份公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F16/2458;G06F16/27
• 代理公司: 濟南信達專利事務(wù)所有限公司 37100
• 代理人: 郗艷榮

本發(fā)明特別涉及一種內(nèi)存數(shù)據(jù)庫KV存儲引擎索引的創(chuàng)建方法。該內(nèi)存數(shù)據(jù)庫KV存儲引擎索引的創(chuàng)建方法，首先在CockroachDB數(shù)據(jù)庫插入ART樹，并在ART樹的葉子節(jié)點增加雙向鏈表，然后基于ART樹獲取大于某key的節(jié)點，并計算出待插入key值對應(yīng)的插入位置，將待插入key值對應(yīng)的節(jié)點插入到雙向鏈表中，最后遍歷Key值范圍即可。該內(nèi)存數(shù)據(jù)庫KV存儲引擎索引的創(chuàng)建方法，通過在ART樹的葉子節(jié)點增加雙向鏈表，實現(xiàn)了key值范圍遍歷的快速響應(yīng)以及對CockroachDB的排序規(guī)則的支持；通過ART樹使用樂觀鎖機制、雙向鏈表使用CAS無鎖算法的方式保證了插入/查詢操作時的高性能以及數(shù)據(jù)的一致性。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫技術(shù)領(lǐng)域，特別涉及一種內(nèi)存數(shù)據(jù)庫KV存儲引擎索引的創(chuàng)建方法。

背景技術(shù)

近年來，隨著動態(tài)隨機存儲器(DRAM)容量的上升和單位價格的下降，使大量數(shù)據(jù)在內(nèi)存中的存儲和處理成為可能，Redis、Memcached等內(nèi)存數(shù)據(jù)庫管理軟件逐漸成熟，應(yīng)用范圍越來越廣。

內(nèi)存數(shù)據(jù)庫(MMDB：Main Memory Database，也叫主存數(shù)據(jù)庫)，就是將數(shù)據(jù)全部或者大部分放在內(nèi)存中進行操作的數(shù)據(jù)庫管理系統(tǒng)，對查詢處理、并發(fā)控制與恢復(fù)的算法和數(shù)據(jù)結(jié)構(gòu)進行重新設(shè)計，以更有效地使用CPU周期和內(nèi)存。由于內(nèi)存數(shù)據(jù)庫與傳統(tǒng)的磁盤數(shù)據(jù)庫在設(shè)計和架構(gòu)上都大不相同，所以傳統(tǒng)的數(shù)據(jù)庫索引不適用于內(nèi)存數(shù)據(jù)庫。

CockroachDB是一款開源的分布式數(shù)據(jù)庫，具有NoSQL對海量數(shù)據(jù)的存儲管理能力，又保持了傳統(tǒng)數(shù)據(jù)庫支持的ACID和SQL等，還支持跨地域、去中心、高并發(fā)、多副本強一致和高可用等特性。支持OLTP場景，同時支持輕量級OLAP場景。

CockroachDB使用rocksdb作為KV存儲引擎，rocksdb不是內(nèi)存存儲引擎。如果將CockroachDB改造成內(nèi)存數(shù)據(jù)庫，需要研發(fā)替代rocksdb的KV內(nèi)存存儲引擎。ART樹在目前流行的幾種內(nèi)存數(shù)據(jù)庫索引中，具備最好的性能。因此，使用基于ART樹構(gòu)建的KV 內(nèi)存存儲引擎會具備很好的性能優(yōu)勢。

存儲引擎主要用作存儲數(shù)據(jù)、為存儲的數(shù)據(jù)建立索引、更新、查詢數(shù)據(jù)等技術(shù)的實現(xiàn)方法。KV存儲引擎是專門用于存儲KV類型表數(shù)據(jù)的一種存儲機制。

KV內(nèi)存存儲引擎是指使用內(nèi)存作為存儲數(shù)據(jù)介質(zhì)的KV存儲引擎。

ART(Adaptive Radix Tree，自適應(yīng)基數(shù)/前綴樹)，是以二進制位串為關(guān)鍵字的trie 樹，是一種多叉樹形結(jié)構(gòu)，同時又類似多層索引表，每個中間節(jié)點包含指向多個子節(jié)點的指針數(shù)組，葉子節(jié)點包含指向?qū)嶋H的對象的指針。中間節(jié)點根據(jù)長度的不同分成若干種不同類型，隨著數(shù)據(jù)的變化而自行調(diào)整。

ART樹節(jié)點所在層數(shù)：指從根節(jié)點開始每往下一移一層計數(shù)加一。根節(jié)點為第0層，根節(jié)點的子節(jié)點們?yōu)榈?層。

ART樹使用字節(jié)序作為key的排序規(guī)則，而CockroachDB使用自定義的key值排序規(guī)則，因此不能直接使用ART樹的排序作為輸出。并且在CockroachDB中大量使用scan 函數(shù)掃描特定范圍內(nèi)的所有key值，并通過迭代器循環(huán)獲取，ART樹的深度遍歷不能直接提供對這種操作的支撐。具體來說，如果ART樹葉子節(jié)點的迭代器使用樹的深度遍歷算法，需要從根節(jié)點到該葉子節(jié)點的路徑信息。由于ART樹不斷更新，內(nèi)部節(jié)點可能會擴展前綴成兩層內(nèi)部節(jié)點，如果迭代器一直保存著路徑的每個內(nèi)部節(jié)點，會導(dǎo)致迭代產(chǎn)生的下一個葉子節(jié)點不正確。因此，迭代器每次next時都需要重新計算根節(jié)點到葉子節(jié)點的路徑，但這樣產(chǎn)生大量的計算，性能較低。

同時，在高并發(fā)的場景下，如何保證并發(fā)插入/查詢數(shù)據(jù)一致性和處理性能，都是在創(chuàng)建KV存儲引擎索引時亟待解決的難題。

基于上述情況，本發(fā)明提出了一種內(nèi)存數(shù)據(jù)庫KV存儲引擎索引的創(chuàng)建方法。

發(fā)明內(nèi)容