基于位圖的鍵值存儲(chǔ)哈希優(yōu)化

摘 要：內(nèi)存鍵值存儲(chǔ)系統(tǒng)中索引方法決定了系統(tǒng)的時(shí)間性能和空間開銷，是改進(jìn)和優(yōu)化的關(guān)鍵因素。哈希索引提供了O（1）時(shí)間復(fù)雜度的訪問操作，但會(huì)產(chǎn)生存儲(chǔ)沖突，引起訪問性能下降。為此，提出了一種基于位圖的鍵值存儲(chǔ)哈希優(yōu)化方法，可以避免存儲(chǔ)沖突提升訪問性能。該方法將共前綴的鍵哈希到同一個(gè)塊，減少鍵存儲(chǔ)空間；在塊內(nèi)使用層次位圖結(jié)構(gòu)，全域位圖表示所有鍵的后綴部分來避免存儲(chǔ)沖突，摘要位圖支持快速定位和范圍查詢加速。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的哈希索引在多種負(fù)載上均能取得較高吞吐量并具有良好的并發(fā)性能，同時(shí)內(nèi)存占用較現(xiàn)有方案大大降低。

關(guān)鍵詞：內(nèi)存鍵值存儲(chǔ)； 索引結(jié)構(gòu)； 哈希表； 位圖

中圖分類號(hào)：TP392

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2023）07-028-2106-05

doi：10.19734/j.issn.1001-3695.2022.12.0773

Bitmap-based optimization of hash index for key value storage

Wang Tianyu， Xu Yun^?， Wang Biao

（School of Computer Science amp; Technology， University of Science amp; Technology of China， Hefei 230000， China）

Abstract：The index method of in-memory key value storage determines the time performance and space overhead of the system， which is a key factor for improvement and optimization. Hash index provides access operations in O（1） time complexity， but it generates storage conflicts and causes access performance degradation. To this end， this paper proposed a bitmap-based hash optimization method for key value storage， which can avoid storage conflicts and improve access performance. This method divided the keys with common prefixes into the same block to reduce the storage space of keys， used a hierarchical bitmap structure in the block， where the global bitmap represented the suffix part of all keys to avoid storage conflicts， and the summary bitmap supported quick positioning and acceleration for range queries. The experimental results show that the optimized hash index can achieve high throughput and good concurrency performance on various workloads， and the memory consumption is greatly reduced compared with existing schemes.

Key words：in-memory key value storage; index structure; hash table; bitmap

0 引言

隨著大數(shù)據(jù)時(shí)代的到來，海量數(shù)據(jù)開始呈現(xiàn)非結(jié)構(gòu)化、小尺寸等特點(diǎn)，內(nèi)存鍵值存儲(chǔ)系統(tǒng)以其數(shù)據(jù)格式靈活、一致性開銷低、可擴(kuò)展性良好等優(yōu)勢(shì)受到廣泛應(yīng)用。內(nèi)存鍵值存儲(chǔ)的基本思想是將數(shù)據(jù)按照鍵值對(duì)的形式進(jìn)行存儲(chǔ)，通過在鍵上建立合適的索引結(jié)構(gòu)，系統(tǒng)可以根據(jù)鍵快速獲取對(duì)應(yīng)的值。索引結(jié)構(gòu)作為鍵值存儲(chǔ)的核心部件，決定了查詢、插入、更新等基本操作的性能。目前，內(nèi)存鍵值存儲(chǔ)中的索引結(jié)構(gòu)大體可以分為基于哈希的索引、基于樹的索引和學(xué)習(xí)型索引。

基于哈希的索引結(jié)構(gòu)基本思想是通過哈希函數(shù)形成鍵到值的映射關(guān)系，可以使所有操作達(dá)到O（1）的時(shí)間復(fù)雜度，因此在REDIS^［1］、memcached^［2］等內(nèi)存鍵值存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用。哈希索引的主要問題在于哈希函數(shù)會(huì)將不同的鍵映射到同一個(gè)位置繼而引發(fā)沖突，索引需要采取一定的策略解決沖突數(shù)據(jù)的存儲(chǔ)，常見的策略有鏈地址法^［3］、開放尋址法^［4］等。鏈地址法將哈希到同一位置的多個(gè)沖突項(xiàng)使用一個(gè)鏈表進(jìn)行組織，提供簡(jiǎn)單高效的插入操作。鏈地址法的缺點(diǎn)是需要存儲(chǔ)額外的指針用于組織鏈表，并且查詢、刪除時(shí)的多次間接訪存會(huì)影響操作性能。開放尋址法通過將數(shù)據(jù)直接存儲(chǔ)在哈希表的槽中避免了使用指針的空間開銷。然而，開放尋址法在插入數(shù)據(jù)時(shí)需要遍歷一個(gè)探查序列以找到可插入的空槽，探查的代價(jià)會(huì)隨著哈希表的負(fù)載因子提高而增大。針對(duì)上述兩種策略存在的缺陷，最小完美哈希^［5］通過構(gòu)建一個(gè)沒有沖突的哈希表達(dá)到O（1）的最壞訪存代價(jià)，但無法支持包含插入操作的動(dòng)態(tài)負(fù)載集。由于哈希沖突的存在，基于哈希的索引大多需要額外的操作次數(shù)或存儲(chǔ)空間以解決沖突，一定程度上影響了索引的操作性能。哈希表難以對(duì)范圍查詢進(jìn)行優(yōu)化的缺點(diǎn)也使其大多應(yīng)用于單點(diǎn)查詢的場(chǎng)景。

基于樹的索引結(jié)構(gòu)主要可以分為基于B樹的索引和基于前綴樹的索引。基于B樹的索引^［6］通過在每個(gè)中間節(jié)點(diǎn)保存多個(gè)鍵的信息，樹高相較二叉搜索樹大大降低，在InnoDB^［7］等存儲(chǔ)引擎中得到廣泛應(yīng)用。B-link樹^［8］通過給樹的葉子節(jié)點(diǎn)添加兄弟指針字段，提供了高效的范圍查能力，逐漸成為基于RDMA的鍵值存儲(chǔ)系統(tǒng)中的關(guān)鍵索引結(jié)構(gòu)^［8～12］。然而，B樹索引的節(jié)點(diǎn)具有分裂合并的特點(diǎn)，在處理插入、刪除等操作時(shí)節(jié)點(diǎn)的重新組織會(huì)帶來額外的性能開銷?；谇熬Y樹的索引主要思想在于將前綴相同的鍵通過同一個(gè)根節(jié)點(diǎn)進(jìn)行索引，但前綴樹索引的樹高取決于鍵的長(zhǎng)度，當(dāng)鍵的分布較為稀疏時(shí)樹的空間利用率較低。ART（adaptive radix tree）^［13］通過設(shè)計(jì)四種不同大小的內(nèi)部節(jié)點(diǎn)以及動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的算法，在保證索引時(shí)間效率的前提下，極大降低了索引的空間開銷。然而，在數(shù)據(jù)規(guī)模較大和數(shù)據(jù)分布松散時(shí)，ART的樹高會(huì)快速升高導(dǎo)致系統(tǒng)性能下降。HOT（height optimized trie）^［14］為了解決ART存在的問題，提出了通過動(dòng)態(tài)調(diào)整內(nèi)部節(jié)點(diǎn)的扇出度以降低樹高的方案，同時(shí)在節(jié)點(diǎn)內(nèi)部進(jìn)行了有損壓縮，進(jìn)一步降低索引所占用的空間。與B樹索引的缺陷類似，HOT的索引結(jié)構(gòu)維護(hù)代價(jià)高，在處理插入、刪除等寫操作時(shí)性能較差?；跇涞乃饕Y(jié)構(gòu)雖然支持動(dòng)態(tài)負(fù)載和范圍查詢，但索引操作復(fù)雜并且需要多次內(nèi)存訪問，存儲(chǔ)用于組織樹結(jié)構(gòu)的指針也帶來了較大的空間開銷。

近年來，學(xué)習(xí)型索引將機(jī)器學(xué)習(xí)的方法引入傳統(tǒng)的索引領(lǐng)域，可以利用極低內(nèi)存空間構(gòu)建高性能索引，為索引研究帶來了新的思路。學(xué)習(xí)型索引的基本思想在于，當(dāng)鍵值對(duì)按鍵有序排列后，鍵及其在序列中的位置呈一定的規(guī)律，表現(xiàn)為二維平面上的一條曲線，通過機(jī)器學(xué)習(xí)或深度學(xué)習(xí)的方式擬合這條曲線，即學(xué)習(xí)數(shù)據(jù)的累計(jì)分布函數(shù)，記錄模型對(duì)應(yīng)的參數(shù)就能實(shí)現(xiàn)對(duì)所要查詢鍵位置的預(yù)測(cè)。由于現(xiàn)實(shí)中的數(shù)據(jù)往往難以用一條曲線擬合，RMI（recursive-model indexes）^［15］通過將鍵進(jìn)行層級(jí)劃分，使用多個(gè)子模型擬合各個(gè)層級(jí)的數(shù)據(jù)達(dá)到更高的預(yù)測(cè)精度。然而，RMI對(duì)數(shù)據(jù)的劃分較為簡(jiǎn)單，在已訓(xùn)練的模型范圍內(nèi)出現(xiàn)鍵值對(duì)插入和刪除時(shí)，整個(gè)模型需要重新訓(xùn)練，嚴(yán)重降低系統(tǒng)性能。Fiting-tree^［16］使用B+樹的中間節(jié)點(diǎn)作為索引的一部分，并使用機(jī)器學(xué)習(xí)模型擬合葉子節(jié)點(diǎn)，實(shí)現(xiàn)了在索引空間占用較小的情況下，避免數(shù)據(jù)更新導(dǎo)致整個(gè)模型重新訓(xùn)練的問題。針對(duì)學(xué)習(xí)型索引難以處理動(dòng)態(tài)數(shù)據(jù)的問題，PGM-index^［17］借鑒了LSM-tree^［18］的思想，插入數(shù)據(jù)僅需重訓(xùn)練最后一個(gè)模型。學(xué)習(xí)型索引通過模型擬合的方式構(gòu)造索引結(jié)構(gòu)，不僅空間占用小且查詢效率高。然而，目前的學(xué)習(xí)型索引只能模擬有序序列和對(duì)動(dòng)態(tài)數(shù)據(jù)支持差的缺陷，限制了其應(yīng)用場(chǎng)景。

綜上，現(xiàn)有的基于樹的索引和學(xué)習(xí)型索引存在結(jié)構(gòu)復(fù)雜難以維護(hù)、對(duì)寫操作支持較差等缺陷，在處理包含插入、刪除操作的動(dòng)態(tài)負(fù)載時(shí)會(huì)遇到嚴(yán)重的性能下降問題，而哈希索引簡(jiǎn)單高效的設(shè)計(jì)不僅易維護(hù)且對(duì)動(dòng)態(tài)負(fù)載支持更好。改進(jìn)哈希索引的沖突和空間開銷問題能夠進(jìn)一步提升內(nèi)存鍵值存儲(chǔ)系統(tǒng)的時(shí)間性能和空間性能，是系統(tǒng)優(yōu)化的關(guān)鍵因素。受位圖結(jié)構(gòu)空間占用低、結(jié)構(gòu)簡(jiǎn)單易維護(hù)的啟發(fā)，本文設(shè)計(jì)了一種基于位圖的優(yōu)化哈希索引BitHash。BitHash通過數(shù)據(jù)分塊的設(shè)計(jì)壓縮鍵的存儲(chǔ)空間，在數(shù)據(jù)塊內(nèi)通過層級(jí)位圖的設(shè)計(jì)避免沖突并提供高效范圍查詢的能力。實(shí)驗(yàn)結(jié)果表明，BitHash不僅在多種負(fù)載上擁有較高吞吐量，內(nèi)存占用也遠(yuǎn)遠(yuǎn)優(yōu)于已有的方案。

1 BitHash索引結(jié)構(gòu)設(shè)計(jì)

1.1 位圖結(jié)構(gòu)

位圖是一種基于枚舉的數(shù)據(jù)結(jié)構(gòu)，對(duì)于全域U中的每個(gè)元素，位圖使用一個(gè)比特表示該元素是否存在，比特位為1表示該元素存在，為0則表示不存在。在位圖索引上進(jìn)行查詢、插入、刪除鍵的操作時(shí)，僅需查詢、修改對(duì)應(yīng)的比特位即可完成，操作的時(shí)間復(fù)雜度為O（1）。通過在大小為u bit的全域位圖上疊加一個(gè)大小為u bit的摘要位圖，可以組成一個(gè)層次位圖。摘要位圖中的每個(gè)比特位記錄了全域位圖中對(duì)應(yīng)u個(gè)比特位進(jìn)行邏輯或運(yùn)算的結(jié)果。通過摘要位圖的設(shè)計(jì)，在進(jìn)行范圍查詢操作時(shí)，算法可以過濾全域位圖中比特位連續(xù)為0的區(qū)域。圖1展示了一個(gè)全域U為0～15的層次位圖，全域位圖的第0個(gè)比特到第15個(gè)比特分別對(duì)應(yīng)全域的一個(gè)數(shù)據(jù)。索引中存儲(chǔ)了鍵等于2，3，4，5，7，14，15的數(shù)據(jù)。查詢鍵x是否存在即查詢?nèi)蛭粓D第x個(gè)比特是否為1，例如圖1中第13個(gè)比特位為0表示鍵等于13的數(shù)據(jù)不存在，而第14個(gè)比特位為1表示鍵等于14的數(shù)據(jù)存在。插入或刪除鍵x即將全域位圖第x個(gè)比特置為1或0，例如在圖1中插入鍵等于13的數(shù)據(jù)即將全域位圖的第13個(gè)比特位置為1。在進(jìn)行范圍查詢時(shí)可以首先查詢摘要位圖進(jìn)行過濾，例如圖1中查詢鍵大于等于7的全部數(shù)據(jù)時(shí)，摘要位圖的第2個(gè)比特為0表示全域位圖中第8個(gè)到第11個(gè)比特均為0，可以避免對(duì)鍵大于等于8小于等于11的數(shù)據(jù)進(jìn)行遍歷。雖然位圖結(jié)構(gòu)簡(jiǎn)單易維護(hù)并提供了高效的查詢、插入、刪除操作，但直接使用位圖結(jié)構(gòu)索引鍵的全域會(huì)帶來極大的空間開銷。例如，對(duì)于8 Byte的鍵，位圖索引需要至少2⁶⁴ bit才能將鍵的所有可能表示出來。

1.2 基于位圖的哈希索引BitHash

為了避免全域較大時(shí)位圖索引空間開銷較高的問題，本文設(shè)計(jì)了基于位圖的哈希索引BitHash。BitHash使用一個(gè)哈希表索引鍵的前綴部分，使用位塊BitChunk索引鍵的后綴部分。如圖2所示，對(duì)于鍵的大小為8 Byte的情況，BitHash通過一個(gè)哈希索引鍵的前6 Byte，再使用BitChunk索引鍵的后2 Byte。用于索引鍵前6 Byte的哈希表采取鏈地址法解決沖突，哈希表的每個(gè)桶bucket包含一個(gè)指向BitChunk鏈頭的指針，對(duì)鍵的前6 Byte進(jìn)行哈希運(yùn)算并遍歷BitChunk鏈表可以找到鍵所在的位塊。用于索引鍵后2 Byte的BitChunk由底層和頂層兩部分組成，分別用于單點(diǎn)查詢和范圍查詢：

a）BitChunk的底層包括一個(gè)指針數(shù)組bottom.pointers和對(duì)應(yīng)的全域位圖bottom.bitmap。bottom.pointers中的每個(gè)指針指向一個(gè)值塊value block，每個(gè)value block可以存儲(chǔ)連續(xù)64個(gè)鍵所對(duì)應(yīng)的值，即第j個(gè)value block用于存儲(chǔ)第64j個(gè)鍵對(duì)應(yīng)的值到第64j+63個(gè)鍵對(duì)應(yīng)的值。當(dāng)某一段連續(xù)的64個(gè)鍵均不存在時(shí)，對(duì)應(yīng)的value block空間不會(huì)被分配且bottom.poin-ters中對(duì)應(yīng)的指針值為空。bottom.bitmap用于指示bottom.pointers中對(duì)應(yīng)的指針是否為空，當(dāng)bottom.pointers中某一指針為空時(shí)，bottom.bitmap中對(duì)應(yīng)的比特位為0，否則為1。bottom.pointers和bottom.bitmap均包含1 024個(gè)元素且成一一對(duì)應(yīng)的關(guān)系。經(jīng)過這樣設(shè)計(jì)，2 Byte的鍵后綴總共可以生成2¹⁶個(gè)不同的鍵值對(duì)，均被有序劃分到1 024個(gè)value block中進(jìn)行存儲(chǔ)并由bottom.pointers和bottom.bitmap進(jìn)行指向。

b）BitChunk的頂層為一個(gè)32 bit的位圖top.bitmap，是底層bottom.bitmap的摘要位圖。top.bitmap中的第i個(gè)比特記錄了bottom.bitmap中第32i個(gè)比特到第32i+31個(gè)比特進(jìn)行邏輯或運(yùn)算的結(jié)果。在BitChunk內(nèi)部進(jìn)行范圍查詢時(shí)，首先查詢top.bitmap可以快速過濾bottom.bitmap中連續(xù)為0的區(qū)域。當(dāng)top.bitmap中某一比特為0時(shí)，說明連續(xù)的32×64個(gè)鍵在索引中都不存在，減少了對(duì)2 048個(gè)鍵的遍歷。

使用BitHash進(jìn)行查詢操作的具體流程如算法1所示。首先，對(duì)鍵進(jìn)行截取，取鍵的前6 Byte進(jìn)行哈希運(yùn)算，得到bucket的序號(hào)i。然后遍歷bucket i指向的BitChunk鏈，比較每個(gè)BitChunk中存儲(chǔ)的鍵前綴，找到該鍵對(duì)應(yīng)的BitChunk。最后在BitChunk內(nèi)檢查bottom.bitmap并獲取bottom.pointers中對(duì)應(yīng)指針的值，根據(jù)指針的值讀取value block并返回。

算法1 BitHash查詢算法

輸入：待查找的鍵key，一個(gè)BitHash的實(shí)例index。

輸出：待查找的鍵key對(duì)應(yīng)的值value，若key不存在則輸出NULL。

a） i=hash（key.prefix） % index→bucket_size; /*對(duì)鍵的前綴進(jìn)行哈希運(yùn)算，確定其所在的bucket序號(hào)i*/

b） bitchunk=index.bucket［i］-gt;chain_head; /*獲取BitChunk鏈的第一個(gè)元素*/

c） if（bitchunk==NULL） return NULL; /*BitChunk鏈為空說明key不存在*/

d）while（bitchunk！=NULLamp;amp;key.prefix！=bitchunk-gt;key_prefix）

bitchunk=bitchunk-gt;next; //對(duì)比BitChunk鏈中的每個(gè)元素

e）

if（bitchunk==NULL） return NULL; /*遍歷完BitChunk鏈都沒有前綴匹配的BitChunk，說明key不存在*/

f）

if（bitchunk-gt;bottom.bitmap［key.suffix］==0）

return NULL; /*BitChunk中bottom.bitmap對(duì)應(yīng)的比特位為0說明該key不存在*/

g）

value_block=bitchunk-gt;bottom.pointers［key.suffix］; /*獲取對(duì)應(yīng)value_block的首地址*/

h） return value_block［key.suffix amp; 0x3F］; /*根據(jù)key在連續(xù)64個(gè)鍵中的排序，獲得value_block中對(duì)應(yīng)的value*/

使用BitHash進(jìn)行范圍查詢的過程分為兩步。第一步是在哈希表中定位查找范圍的起始鍵key所在的BitChunk，第二步是在該BitChunk中查找大于key的所有鍵值對(duì)。第一步的流程和算法1中a）～e）的過程一致。第二步的關(guān)鍵在于如何利用top.bitmap快速過濾bottom.bitmap中連續(xù)32個(gè)比特為0的區(qū)域，即快速查找下一個(gè)非空的value block，具體流程如算法2所示。首先，在當(dāng)前value block j所在的bottom.bitmap中查找該連續(xù)32 bit中是否存在bottom.bitmap［k］為1且kgt;j。如果存在滿足條件的序號(hào)k，則value block k就是下一個(gè)非空的value block，返回k。如果不存在滿足條件的k，則查找top.bitmap中下一個(gè)為1的位置i。如果不存在top.bitmap為1的位置，則將i置為-1，算法返回NULL。如果存在top.bitmap為1的位置，在top.bitmap［i］對(duì)應(yīng)bottom.bitmap的連續(xù)32個(gè)比特中選擇第一個(gè)使bottom.bitmap［k］為1的序號(hào)k，則value block k就是下一個(gè)非空的value block，返回k。

算法2 BitChunk內(nèi)查找下一個(gè)非空value block的算法

輸入：當(dāng)前key所在的BitChunk實(shí)例bitchunk，當(dāng)前key所在的value block序號(hào)j。

輸出：下一個(gè)非空value block的序號(hào)k，若不存在輸出NULL。

a） for（iter=j+1 to iter=「（j+1）/32^┐*32）

if（bitchunk-gt;bottom.bitmap［iter］==1）

return k=iter;

/*對(duì)當(dāng)前top.bitmap對(duì)應(yīng)的bottom.bitmap中的連續(xù)32 bit進(jìn)行檢測(cè)，若bottom.bitmap［k］為1則說明bottom.pointers［k］指向的value block為下一個(gè)非空的value block */

b） i=find_next_1_bit（bitchunk-gt;top.bitmap， 「（j+1）/32┐）;/*當(dāng)前top.bitmap對(duì)應(yīng)的bottom.bitmap沒有1時(shí)，查找下一個(gè)top.bitmap為1的位置i*/

c） if（i==-1） return NULL; //top.bitmap中沒有為1的位置

d） for（iter=i*32 to iter=（j+1）*32）

if（bitchunk-gt;bottom.bitmap［iter］==1）

return k=iter;

/*查找下一個(gè)top.bitmap對(duì)應(yīng)的bottom.bitmap中第一個(gè)為1的位置，若bottom.bitmap［k］為1則說明bottom.pointers［k］指向的value block為下一個(gè)非空的value block */

2 BitHash并發(fā)一致性設(shè)計(jì)

隨著多核CPU的不斷發(fā)展，計(jì)算機(jī)的并行處理能力逐漸增強(qiáng)，支持并發(fā)操作的索引結(jié)構(gòu)能更大程度地利用硬件資源達(dá)到更高的系統(tǒng)吞吐量。本文使用讀寫鎖完成BitHash的并發(fā)實(shí)現(xiàn)，由于BitHash的結(jié)構(gòu)包括一個(gè)哈希表和若干個(gè)BitChunk，所以需要在各個(gè)層級(jí)設(shè)置合適粒度的鎖用于平衡操作性能和鎖的空間開銷。對(duì)于索引鍵前6 Byte的哈希表，在每個(gè)桶bucket中存放一個(gè)讀寫鎖用于控制對(duì)BitChunk鏈的并發(fā)訪問。當(dāng)某一線程在查找BitChunk鏈時(shí)，會(huì)給該BitChunk鏈上讀鎖，允許其他線程同時(shí)讀取鏈中的數(shù)據(jù)；當(dāng)某一線程需要插入或刪除一個(gè)BitChunk時(shí)，會(huì)給該BitChunk鏈上寫鎖，禁止其他線程對(duì)該BitChunk鏈的訪問。對(duì)于索引鍵后2 Byte的BitChunk，有三個(gè)位置可能被并發(fā)修改引起讀寫不一致問題：top.bitmap，bottom.bitmap和bottom.pointers。當(dāng)bottom.bitmap和bottom.pointers中的每個(gè)元素都擁有獨(dú)立的讀寫鎖時(shí)，鎖的空間占用將會(huì)遠(yuǎn)遠(yuǎn)大于BitChunk本身。因此本文在每個(gè)BitChunk中僅使用一個(gè)讀寫鎖，用于控制所有線程對(duì)top.bitmap，bottom.bitmap和bottom.pointers的訪問。除了索引結(jié)構(gòu)中的鎖設(shè)計(jì)，在存儲(chǔ)值的value block中也需要一個(gè)鎖用于保證多個(gè)線程對(duì)value block中值的并發(fā)修改。使用讀寫鎖在BitHash中進(jìn)行并發(fā)插入的具體流程如算法3所示。第一步在哈希表中進(jìn)行操作：對(duì)key的前6 Byte進(jìn)行哈希運(yùn)算確定其所在的bucket序號(hào)i，給bucket i上寫鎖，查找key所在的BitChunk是否存在，若不存在則新建一個(gè)BitChunk并使用頭插法插入BitChunk鏈中，最后釋放bucket i的鎖。第二步在BitChunk中進(jìn)行操作：給BitChunk上寫鎖，根據(jù)key的后2 Byte將bottom.bitmap中對(duì)應(yīng)比特置為1，判斷bottom.pointers中對(duì)應(yīng)指針的值是否為空，若為空則新建一個(gè)value block并讓該指針指向它，最后釋放BitChunk的鎖。第三步在value block中進(jìn)行操作：給value block上寫鎖，插入value至對(duì)應(yīng)的位置，最后釋放value block的鎖返回value。

算法3 BitHash并發(fā)插入算法

輸入：待插入的鍵key和值value，一個(gè)BitHash的實(shí)例index。

輸出：輸出value。

a） i=hash（key.prefix） % index-gt;bucket_size; /*對(duì)鍵的前綴進(jìn)行哈希運(yùn)算，確定其所在的bucket序號(hào)i*/

b） LOCK_WR（index.bucket［i］-gt;lock）; //給BitChunk鏈上寫鎖

c） bitchunk=index.bucket［i］-gt;chain_head; /*獲取BitChunk鏈的第一個(gè)元素*/

d） if（bitchunk==NULL） goto g）; /*BitChunk鏈為空說明key不存在，跳到步驟g）*/

e）while（bitchunk！=NULLamp;amp;key.prefix！=bitchunk-gt;key_

prefix）

bitchunk=bitchunk-gt;next; //對(duì)比BitChunk鏈中的每個(gè)元素

f） if（bitchunk==NULL） goto g）; /*遍歷完BitChunk鏈都沒有前綴匹配的BitChunk，說明key對(duì)應(yīng)的BitChunk不存在*/

else go to h）

g）

bitchunk=new BitChunk; /*key對(duì)應(yīng)的BitChunk不存在，新建該BitChunk*/

h）

bitchunk-gt;next=index.bucket［i］-gt;chain_head;

index.bucket［i］-gt;chain_head=bitchunk; /*將新建的BitChunk使用頭插法插入bucket［i］對(duì)應(yīng)的鏈表中*/

i）

UNLOCK（index.bucket［i］-gt;lock）; /*釋放BitChunk鏈上的鎖*/

j）

LOCK_WR（bitchunk-gt;lock）; //給BitChunk上寫鎖

k）

bitchunk-gt;bottom.bitmap［key.suffix］=1;

l）

if（bitchunk-gt;bottom.pointers［key.suffix］==NULL）

bitchunk-gt;bottom.pointers［key.suffix］=new Value_Block;

//如果對(duì)應(yīng)的value block不存在，新建對(duì)應(yīng)的value block//

m） value_block=bitchunk-gt;bottom.pointers［key.suffix］;

//獲取key所在的value block//

n）

UNLOCK（bitchunk-gt;lock）;// 釋放BitChunk中的鎖

o）

LOCK_WR（value_block-gt;lock）;

value_block［key.suffix amp; 0x3F］=value;

UNLOCK（value_block-gt;lock）;

return value;

//給value block上寫鎖，插入數(shù)據(jù)后釋放鎖

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境和對(duì)比系統(tǒng)

本文的實(shí)驗(yàn)機(jī)器為單臺(tái)服務(wù)器，其中CPU為22核2.2 GHz的Intel Xeon Gold 6161，內(nèi)存大小為376 GB，操作系統(tǒng)為4.15內(nèi)核版本的Ubuntu 18.04 LTS。編譯器使用GCC。本文實(shí)驗(yàn)所用的鍵值數(shù)據(jù)為8 Byte的鍵和8 Byte的值組成的鍵值對(duì)。本文將對(duì)BitHash的吞吐量、空間占用、并發(fā)性能進(jìn)行測(cè)試。

本文選取了以下三種廣泛應(yīng)用的索引結(jié)構(gòu)作為BitHash的對(duì)比系統(tǒng)：

a）ART：The Adaptive Radix Tree（ART）是專為內(nèi)存數(shù)據(jù)庫設(shè)計(jì)的前綴樹索引結(jié)構(gòu)，其通過設(shè)計(jì)尺寸不同的節(jié)點(diǎn)和使用SIMD指令加速達(dá)到空間性能和時(shí)間效率的均衡。

b）STX B+tree^［6］：B+tree作為數(shù)據(jù)庫中常見的索引結(jié)構(gòu)，本文選擇了STX B+tree的實(shí)現(xiàn)作為對(duì)比。本文使用默認(rèn)的256 Byte的節(jié)點(diǎn)以達(dá)到STX B+tree的最高性能。

c）PGM-index：PGM-index是第一個(gè)支持動(dòng)態(tài)負(fù)載的學(xué)習(xí)型索引，本文將其epsilon設(shè)為默認(rèn)的64以達(dá)到時(shí)間效率和空間性能的均衡。

3.2 YCSB性能測(cè)試

YCSB（Yahoo！ Cloud Serving Benchmark）^［19］作為一款開源的數(shù)據(jù)庫性能測(cè)試工具，在學(xué)術(shù)界和工業(yè)界得到廣泛應(yīng)用。YCSB包括讀?。╮ead）、更新（update）、插入（insert）、范圍查找（scan）、讀修改寫回（read-modify-write）四種操作，根據(jù)每種操作比例的不同可以將YCSB劃分為YCSB-A（50% reads 50% updates）、YCSB-B（YCSB-A（95% reads 5% updates）、YCSB-C（100% reads）、YCSB-D（95% reads 5% inserts））、YCSB-E（95% scans 5% inserts）、YCSB-F（50% reads 50% read-modify-writes）共六種負(fù)載。

本文的實(shí)驗(yàn)分為兩個(gè)階段：首先在各系統(tǒng)中插入50M個(gè)鍵值對(duì)，然后對(duì)于YCSB的每種負(fù)載在各系統(tǒng)上執(zhí)行10M個(gè)操作并記錄每秒的操作數(shù)（Mops）作為其吞吐量。四個(gè)系統(tǒng)在YCSB六種負(fù)載上的吞吐量如圖3所示。圖3中ART和Bit-Hash在六種負(fù)載上的吞吐量均遠(yuǎn)超B+tree和PGM-index。在性能差距最大的YCSB-D負(fù)載上，BitHash的吞吐量比ART高19.94%，且BitHash的吞吐量分別是B+tree、PGM-index的7.01倍和21.23倍；在性能差距最小的YCSB-E負(fù)載上，Bit-Hash的吞吐量比ART高5.95%，同時(shí)BitHash的吞吐量分別是B+tree、PGM-index的3.07倍和4.53倍。

BitHash的高性能受益于索引結(jié)構(gòu)扁平化的設(shè)計(jì)，最好情況下僅需一次哈希查找和一次位圖查找即可獲取或修改對(duì)應(yīng)的值，而樹型結(jié)構(gòu)需要從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的遍歷才能完成查找。除此之外，BitHash中層次位圖的設(shè)計(jì)也提供了快速過濾的機(jī)制，能夠加速范圍查找的過程，提高scan操作的吞吐量。

3.3 內(nèi)存開銷測(cè)試

隨著數(shù)據(jù)規(guī)模的不斷增大，內(nèi)存開銷逐漸成為了索引系統(tǒng)的性能瓶頸。本文分別測(cè)試了存儲(chǔ)50M、75M、100M、125M鍵值對(duì)情況下各索引系統(tǒng)的內(nèi)存占用情況如圖4所示。對(duì)于不同的數(shù)據(jù)規(guī)模，BitHash都保持了較低的內(nèi)存占用，并且沒有出現(xiàn)索引大小隨著數(shù)據(jù)增加而迅速增大的情況。ART得益于多種尺寸節(jié)點(diǎn)的設(shè)計(jì)和動(dòng)態(tài)調(diào)整節(jié)點(diǎn)大小的算法，空間占用與BitHash相近。數(shù)據(jù)規(guī)模為50M時(shí)，BitHash的空間占用分別比B+tree、PGM-index低75.30%和45.33%；數(shù)據(jù)規(guī)模為125M時(shí)，BitHash的空間占用分別比B+tree、PGM-index低76.33%和47.31%。

BitHash的兩個(gè)獨(dú)特設(shè)計(jì)使其擁有低空間占用的優(yōu)勢(shì)：第一是使用哈希表索引鍵的前6 Byte，因此對(duì)于2¹⁶個(gè)共前綴的鍵僅需保存一份6 Byte的前綴在BitChunk中，節(jié)省了存儲(chǔ)空間；第二是使用層次位圖表示鍵的后2 Byte，每個(gè)鍵一個(gè)比特位的存儲(chǔ)空間大大低于存儲(chǔ)完整后綴2 Byte的空間。具體來說，若不使用層次位圖的形式壓縮鍵后綴，則所有2" Byte鍵后綴占用的存儲(chǔ)空間為2¹⁶×2 Byte=2¹⁷ Byte；若使用層次位圖表示鍵后綴，則所有2 Byte鍵后綴占用的存儲(chǔ)空間為2¹⁰ bit（全域位圖）+25 bit（摘要位圖）=132 Byte。對(duì)于鍵對(duì)應(yīng)的值的存儲(chǔ)，由于BitHash將連續(xù)的64個(gè)值存儲(chǔ)在一個(gè)value block中，所以在BitChunk中需要額外2¹⁰×8 Byte=2¹³ Byte的空間存儲(chǔ)所有指向value block的指針，即bottom.pointers。bottom.pointers的引入雖然帶來了額外的開銷，但這種設(shè)計(jì)在值為不定長(zhǎng)的情況下使用更為靈活。總的來說，BitChunk的設(shè)計(jì)主要貢獻(xiàn)點(diǎn)在于壓縮鍵的存儲(chǔ)空間，值的空間占用與其他方法近似。

3.4 多線程并發(fā)性能

隨著CPU核數(shù)的不斷增多，能否更好利用多核CPU的計(jì)算能力達(dá)到更高吞吐量成為了衡量索引性能的新因素。本文測(cè)試了BitHash在YCSB六種負(fù)載下，1線程到16線程的吞吐量結(jié)果，如圖5所示。對(duì)于寫操作占比較小的負(fù)載如YCSB-C、YCSB-B和YCSB-D，1線程到16線程BitHash可以達(dá)到線性加速比。16線程時(shí)BitHash在YCSB-B上的吞吐量約為1線程時(shí)的15.95倍；16線程時(shí)BitHash在YCSB-D上的吞吐量約為1線程時(shí)的15.33倍。

BitHash中哈希表的讀寫鎖設(shè)計(jì)和BitChunk中讀寫鎖的設(shè)計(jì)不僅保證了索引在多線程下具有較好的并發(fā)性能，還未產(chǎn)生過大的空間開銷。BitHash中的索引查找算法會(huì)在查找某一區(qū)域后及時(shí)釋放對(duì)應(yīng)的鎖資源，一定程度上減少了多線程競(jìng)爭(zhēng)情況的發(fā)生。

4 結(jié)束語

隨著數(shù)據(jù)規(guī)模的不斷增大，現(xiàn)有的索引結(jié)構(gòu)難以實(shí)現(xiàn)時(shí)間性能和空間性能的均衡，在處理動(dòng)態(tài)負(fù)載時(shí)還會(huì)出現(xiàn)嚴(yán)重的性能下降問題。本文將位圖結(jié)構(gòu)與哈希表結(jié)合在一起設(shè)計(jì)了基于位圖的哈希索引BitHash，不僅可以避免存儲(chǔ)沖突，保證操作的時(shí)間性能，還能減少索引的內(nèi)存開銷支持更大規(guī)模的數(shù)據(jù)。BitHash通過一個(gè)哈希表索引鍵的前6 Byte達(dá)到空間壓縮的效果，使用包含層次位圖的BitChunk索引鍵的后2 Byte避免存儲(chǔ)沖突并加速范圍查詢操作。實(shí)驗(yàn)結(jié)果表明，BitHash在時(shí)間性能和空間性能方面均優(yōu)于現(xiàn)有的索引系統(tǒng)，且在多線程環(huán)境下具有良好的并發(fā)性能。BitHash作為一種優(yōu)化的哈希索引具有良好的增刪改查性能，可以用于使用哈希表作為索引的鍵值存儲(chǔ)系統(tǒng)中，如基于RDMA的分布式鍵值存儲(chǔ)等。

參考文獻(xiàn)：

[1]REDIS［EB/OL］.https：//redis. io/.

［2]Fitzpatrick B. Distributed caching with memcached［J］.Linux Journal，2004，11（124）：5.

［3]Cormen T H， Leiserson C E， Rivest R L， et al. Introduction to algorithms［M］.Cambridge，MA：MIT Press，2022.

［4]Kurpicz F， Lehmann H P， Sanders P. PaCHash： packed and compressed hash tables［C］//Proc of Symposium on Algorithm Enginee-ring and Experiments.2023：162-175.

［5]Majewski B S， Wormald N C， Havas G， et al. A family of perfect hashing methods［J］.The Computer Journal，1996，39（6）：547-554.

［6]Graefe G. Modern B-tree techniques［J］.Foundations and Trends in Databases，2011，3（4）：203-402.

［7]Frühwirt P， Huber M， Mulazzani M， et al. InnoDB database forensics［C］//Proc of the 24th IEEE International Conference on Advanced Information Networking and Applications.Piscataway，NJ：IEEE Press，2010：1028-1036.

［8]Mitchell C， Montgomery K， Nelson L， et al. Balancing CPU and network in the cell distributed B-tree store［C］//Proc of USENIX Annual Technical Conference.2016：451-464.

［9]Wei Xingda， Chen Rong， Chen Haibo. Fast RDMA-based ordered key-value store using remote learned cache［C］//Proc of the 14th USENIX Symposium on Operating Systems Design and Implementation.2020：117-135.

［10]Wang Qing， Lu Youyou， Shu Jiwu. Sherman： a write-optimized distributed B+tree index on disaggregated memory［C］//Proc of International Conference on Management of Data.New York：ACM Press，2022：1033-1048.

［11]魏星達(dá).高效可靠的基于HTM和RDMA的內(nèi)存事務(wù)計(jì)算［D］.上海：上海交通大學(xué)，2017.（Wei Xingda. Efficient and reliable tran-sactional processing using HTM and RDMA［D］.Shanghai：Shanghai Jiao Tong University，2017.）

［12]魏星達(dá)，陳榕，陳海波.基于RDMA高速網(wǎng)絡(luò)的高性能分布式系統(tǒng)［J］.大數(shù)據(jù)，2018，4（4）：2018036.（Wei Xingda， Chen Rong， Chen Haibo. Optimizing distributed systems with remote direct memory access［J］.Big Data Research，2018，4（4）：3-14.）

［13]Leis V， Kemper A， Neumann T. The adaptive radix tree： ARTful indexing for main-memory databases［C］//Proc of the 29th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2013：38-49.

［14]Binna R， Zangerle E， Pichl M， et al. HOT： a height optimized trie index for main-memory database systems［C］//Proc of International Conference on Management of Data.New York：ACM Press，2018：521-534.

［15]Kraska T， Beutel A， Chi E H， et al. The case for learned index structures［C］//Proc of International Conference on Management of Data.New York：ACM Press，2018：489-504.

［16]Galakatos A， Markovitch M， Binnig C， et al. Fiting-tree： a data-aware index structure［C］//Proc of International Conference on Mana-gement of Data.New York：ACM Press，2019：1189-1206.

［17]Ferragina P， Vinciguerra G. The PGM-index： a fully-dynamic compressed learned index with provable worst-case bounds［J］.Procee-dings of the VLDB Endowment，2020，13（8）：1162-1175.

［18]O’Neil P， Cheng E， Gawlick D， et al. The log-structured merge-tree （LSM-tree）［J］.Acta Informatica，1996，33（4）：351-385.

［19]Cooper B F， Silberstein A， Tam E， et al. Benchmarking cloud serving systems with YCSB［C］//Proc of the 1st ACM Symposium on Cloud Computing.New York：ACM Press，2010：143-154.