面向持久化鍵值數據庫的自適應熱點感知哈希索引

王楠 吳云

摘 要：針對現有鍵值數據庫存儲系統缺乏熱點意識，導致系統在高度傾斜的工作負載下性能較差且不可靠，提出了一種自適應熱點感知哈希索引模型，該模型基于key值摘要信息實現了一個高性能哈希表。首先，利用key的摘要信息代替key值，壓縮key的存儲空間，優(yōu)化哈希表中桶的數據結構；其次，利用CPU的數據級并行技術以及CPU cache line，對哈希表的探查操作進行優(yōu)化；最后，為解決摘要信息導致key值無法精準比較，需要額外磁盤I/O的問題，設計了一種自適應key值調度算法，該算法根據當前可用內存大小、哈希索引負載以及訪問熱點情況動態(tài)地調整key值的存儲位置。在YCSB仿真數據集上進行了實驗，實驗表明，相較于最先進的哈希表，自適應熱點感知哈希索引在相同內存使用率的情況下，將速度提升至1.2倍。

關鍵詞：持久化鍵值存儲；自適應；熱點感知；哈希索引

中圖分類號：TP391.9?? 文獻標志碼：A?? 文章編號：1001-3695（2024）01-035-0226-05

doi：10.19734/j.issn.1001-3695.2023.04.0188

Adaptive hot-aware hash index for persistent key-value databases

Abstract：In view of the lack of hotspot awareness in existing key-value database storage systems，which leads to poor perfor-mance and unreliability under highly tilted workloads，this paper proposed an adaptive hot-spot aware hash index model，which implemented a high-performance hash table based on key summary information.Firstly，the paper used the abstract information of key to replace the key value，compressed the storage space of key，and optimized the data structure of the bucket in the hash table.Secondly，the paper optimized the probe operation of hash table by using the data level parallel technique of CPU and CPU cache line.Finally，in order to solve the problem of extra disk I/O due to the inaccurate comparison of key values caused by summary information，this paper designed an adaptive key scheduling algorithm，which dynamically adjusted the storage location of key values according to the current available memory size，hash index load and access hotspot.Experiments on YCSB simulation datasets show that the adaptive hot-spot aware hash index is up to 1.2 times faster than the most advanced hash table for the same memory usage.

Key words：persistent key-value store；self-adaptation；hot spot perception；hash index

0 引言

早期的索引技術是基于人類經驗構造的啟發(fā)式數據結構［1］，常見的索引結構有哈希表［2］、平衡/前綴樹（如B樹［3］、tire樹以及mass tree等）、跳表（skip list）、日志合并樹［4］（log structure merge tree，LSM-Tree）等。由于數據查詢條件的多樣性，不同的索引結構有著不同的設計實現與應用場景。其中哈希表因其超快的讀寫速度成為了鍵值數據庫存儲系統中最常用的索引結構，如Redis［5］、Memcached［6］等內存鍵值數據庫存儲系統。特別是當上層應用程序不需要范圍查詢時，哈希表的性能直接影響了系統插入、刪除、更新、查詢等基本操作的性能［7］。哈希索引常用于對海量數據的高效檢索或者對熱點數據的緩存。熱點問題是現實應用場景中常見的問題，在文獻［8～12］中已被廣泛研究。有許多解決方案用于解決集群范圍內的熱點問題，例如一致性哈希［13］、數據遷移［14～16］和前端數據緩存［17～20］等。此外，單機熱點問題也得到了很好的解決。例如，計算機體系結構利用分層存儲布局（例如：磁盤、RAM、CPU緩存）來緩存頻繁訪問的數據。然而，鍵值數據庫存儲系統內部的熱點問題通常被忽視。且在如今的實際生產環(huán)境中，工作負載愈加復雜多樣化，即使在單個工作負載中，這些特征也會隨著時間的推移而變化。

然而現有的哈希索引結構通過相同的策略來管理所有的鍵值對，缺乏熱點意識，無法感知外部工作負載的規(guī)律，也無法動態(tài)調整自身結構以提升性能，導致它在高度傾斜的工作負載下性能較差且不可靠。例如在傳統的基于鏈式沖突的哈希索引中，熱點key與冷key隨機放置在碰撞鏈表中，因此它們的訪問成本是相同的。即假設有N個鍵值對存儲在一個包含B個桶的哈希表中，每個桶的沖突鏈表的平均長度為L=N/B。在沖突鏈中檢索一個key的內存平均訪問次數為1+L/2，其中1代表哈希表中桶的查找。在一個理想的熱點感知哈希索引中，查詢一個key所需的內存訪問次數應該與這個熱點成負相關，即越頻繁訪問的key，它的訪問代價越低。

雖然可以通過擴大哈希表（即通過重新哈希）以減少沖突鏈的長度，從而減少內存訪問次數，然而內存有限，哈希表的長度無法無限擴展，對于兩個連續(xù)的rehash操作，第二個操作需要兩倍的內存空間，但只帶來一半的效率（就鏈長度減少而言），且重新哈希的代價不小。于是研究人員提出了許多緩存友好的索引結構，例如利用CPU的cache加速對熱點數據的訪問（即以64 Byte大小的cache line為單位），然而對于大多數服務器而言，CPU的cache大小約為32 MB，然而整個內存大小可以超過256 GB，導致只有0.012%的內存可以被緩存，遠低于現實應用場景中的熱點比率。

研究人員通過研究發(fā)現，如果哈希表不存在任何哈希沖突，那么熱點問題將不復存在，因為它的所有操作都可以達到 O（1）的時間復雜度。于是最小完美哈希的核心思想就是構建一個沒有沖突的哈希表，然而它無法支持插入操作。隨著人工智能技術的發(fā)展，研究學者們認為機器學習模型的本質是一個映射函數，故可以使用機器學習模型代替哈希函數，學習key和value之間CDF分布關系，從而有效地壓縮key的存儲空間并減少哈希沖突，然而結果卻是機器學習模型的計算代價太過昂貴，無法有效提升哈希索引的性能。

Hot-Ring［21］使用鏈地址法解決哈希沖突，并將碰撞鏈表替換為有序環(huán)結構，通過移動頭部指針靠近熱點項來提供對熱點項的快速訪問。它還應用了一種輕量級策略來解決運行時的熱點漂移問題。為顯著提高該結構在并發(fā)場景下的吞吐量，Hot-Ring在設計上全面采用無鎖結構，例如基于原子的讀-拷貝-更新（read-copy-upadate，RCU）［22］和危險指針［23］比較（CAS）。這種方法依舊沒有從根源上解決熱點問題，它只支持沖突鏈上的單熱點問題；它為了支持對哈希索引的無鎖訪問使用了鏈表結構，需要使用額外內存空間存放指針，并且指針的訪問效率較低，這種方法適用于哈希沖突非常嚴重以及將數據主要存放于內存中的場景，但對于將哈希索引應用到對慢速設備中數據進行索引的場景，該方法的性能存在巨大瓶頸。

BitHash［24］提出了一種基于位圖的哈希優(yōu)化方案，使用數據分塊的設計，提取鍵的公共前綴，從而壓縮鍵的存儲空間，并在數據塊內通過層級位圖的設計避免沖突，最終提供高效范圍查詢的能力。這種方法由于使用了布隆過濾器作為輔助結構，導致它無法應對哈希索引的刪除場景，且該方法的性能不盡如人意。

綜上所述，所有現有的方法都只能在一定程度上緩解熱點問題，為了解決上述模型存在的問題，本文提出一個自適應熱點感知哈希索引模型。本文主要貢獻如下：

a）針對哈希索引使用內存空間有限，導致哈希沖突概率較高的問題，提出了一種key值壓縮方案，利用簡要key值摘要信息代替key值本身，優(yōu)化哈希表中桶的數據結構，有效增大了哈希索引的可用內存空間，從根源上極大地避免了哈希沖突，提高哈希索引的訪問效率。

b）針對開放尋址法的線性探查代價會隨著哈希索引負載因子的提高而增大的問題，提出了一種探查優(yōu)化方案，利用CPU的SIMD指令以及cache優(yōu)化哈希索引在探查過程中的查找比較操作，避免在使用開放地址法解決哈希沖突時因多次探測造成的效率下降問題。

c）針對摘要可能導致key值比較不準確，需要額外訪問磁盤的問題，設計了一種自適應key值調度算法，根據當前可用內存大小、哈希索引負載以及訪問熱點情況動態(tài)地調整key值的存儲位置。

1 本文方法

以往傳統鍵值數據庫存儲系統主要將數據以key-value pair的形式存儲在磁盤之中，并在內存中為key建立合適的索引結構，保存key值本身以及value的元信息（如value在磁盤中的存儲地址以及大小等信息），使得系統可以根據key快速精準檢索對應的value的元信息，然而這種哈希索引的方式需要付出大量的內存空間用于保存key值本身，導致哈希索引可用的內存急劇減少，尤其是當key值非常大時，使得哈希索引，不僅從根源上增大了哈希沖突的概率，使得哈希索引的效率不盡如人意；還導致哈希桶中無法存放key值本身，只能存放指向key值的指針，使得空間浪費且性能較低。本文提出的自適應熱點感知哈希表盡量使用定長且精簡的key值摘要信息替代key值本身，即只在內存中存放key的摘要信息，將key值放入慢速存儲設備。犧牲一定的準確性，獲取極大的內存使用率，從而增大哈希索引的可用內存量，從根源上極大減少了哈希沖突概率，并且對哈希桶的結構布局進行了優(yōu)化；且利用CPU SIMD指令以及cache保證模型在負載因子較高時的穩(wěn)定性能。當遇到摘要信息相同，但key值不相同時，該模型會將摘要信息相同的所有key全部調入內存，保證極端情況下模型的性能。并根據一定的策略識別熱點數據，將熱數據的key移入內存。

1.1 模型概述

自適應熱點感知哈希索引模型底層的數據結構是自適應熱點感知哈希表。圖1展示了自適應熱點感知哈希表的結構，為使得哈希表的性能最大化，哈希表使用空間緊湊的哈希桶數組作為底層基本數據結構。假設哈希桶數組的長度為N，每個哈希桶的大小與機器的cache line對齊（即單個哈希桶的大小為cache line大小的倍數）。其中哈希表中存放value代表的是key-value pair的元信息，該元信息包含鍵值對在磁盤中的起始地址、key的大小、value的大小等信息。哈希表中key代表的含義是key的摘要信息。例如將（good luck to you ，thank）鍵值對插入鍵值數據庫存儲系統時，其中good luck to you的摘要為66，鍵值對的元信息為meta，模型會將（66 ，meta）插入自適應熱點感知哈希索引。

該模型使用開地址法作為取模沖突的解決策略，即key的hash值對N取模相同時使用線性探測，最大的探測距離設置為MAX_HOPS。使用鏈地址法作為哈希碰撞的解決策略，即每個hash值相同的key使用溢出桶保存，并在哈希桶中使用overflow_id指向該溢出桶，溢出桶中也使用check_id表示該溢出桶屬于那個hash值，溢出桶中包含key_address（指向key在內存中的存儲位置）以及鍵值對元信息；該模型使用墓碑標記法作為刪除策略，每次刪除數據時只需要簡單地將對應位置的key_digest值置為DELETED即可。使用細粒度鎖作為自適應熱點感知哈希索引的并發(fā)解決方案，即在每個哈希桶中存放一個鎖。并充分利用x86系統的MESIF protocol協議，保證對短于一個字的內存讀寫的原子性，使得本文提出的哈希表能夠在查找階段支持無鎖并發(fā)。

圖2展示了自適應熱點感知索引查找、插入、刪除算法的運行流程。首先需要判斷在合理的跳數內能否在哈希桶數組中查詢到指定的摘要信息；隨后判斷摘要對應的key值本身是否存在內存中；最后驗證key值是否一致。

1.2 查找算法

如圖2所示，先計算出需要查找key的哈希值，為了后續(xù)有效地查找、插入、刪除，并通過（hash & 0x7fffffffffffffff） + 1）計算出key值摘要信息，確保摘要一定恒大于0，一定不等于0xffffffffffffffff。因為摘要為EMPTY（0）代表該位置為空，摘要值為DELETED（0xffffffffffffffff）代表該位置存在過元素，但被刪除了；該自適應熱點感知哈希表使用細粒度鎖解決并發(fā)沖突；隨后從目標桶開始進行線性探測，在每個桶內使用SIMD指令快速比對桶內摘要信息，直到遇到以下五種情況：

case 1：哈希表中存在多個有相同摘要的鍵值對，根據本文模型方法，此時它們對應的鍵全部在內存中，且需要查找的key存在，直接返回該key對應的value元信息即可。

case 2：哈希表中存在多個有相同key_digest的鍵值對，根據論文模型方法，此時它們對應的鍵全部在內存中，但是需要查找的key并不存在，直接返回false。

case 3：哈希表中存在一個摘要，且與需要查找key的摘要相同，此時無法判斷哈希表中的鍵是否與key一致（可能存在hash（key1）=hash（key2）=key_digest，但是key1不等于key2的情況），此時只需要將該摘要對應的meta返回即可。后續(xù)由上層應用根據meta信息從慢速設備中讀取真正的real_key-real_value對，如果real_key與key相同，那么返回real_value，否則說明鍵值對不存在（對慢速設備中鍵值對的索引而言，索引本身只會存放value元信息，value數據是存放在慢速設備中，所以一次慢速設備的訪問必不可少）。為了避免外界對該索引的惡意訪問（即哈希表中存在key1，它的摘要為key_digest，但是用戶頻繁訪問的摘要也為key_digest的key2），導致慢速設備的不必要訪問，降低了整個系統的性能，所以模型需要將訪問過程中所有摘要相同的key值全部調入內存。

case 4：探查過程中遇到了存在空閑位置的哈希桶，說明需要查詢的key值不存在，返回false。

case 5：查找過程中超過了線性探測允許的最大跳數，即需要查詢的key值不存在，返回false。

1.3 插入算法

插入算法基于查找算法實現，故插入流程和查找流程一樣也有五種不同的情況。以下使用具體五個插入例子進行介紹，下面的插入依次進行。

a）向哈希表中插入（key1，value1），key1的摘要值為key_digest1，且哈希表中沒有摘要key_digest1，此時進入case 4，查找到空閑位置插入即可。為避免后續(xù)哈希表的性能下降，故優(yōu)先選擇摘要為DELETED的位置進行插入，隨后將key_digest1以及key1-value1 pair的元信息插入即可。

b）向哈希表中接著插入（key2，value2），key2的摘要值也為key_digest1，由于上面流程中哈希表內已經存在了一個摘要為key_digets1的鍵，但key_digest1不存在有效溢出桶，此時進入case 3，故首先為該key_digest1分配一個新的溢出桶，接著記錄上一個摘要為key_digest1的（key1，value1）的數據，并假設該操作為更新操作，直接更新當前key_digest1的key-value pair，隨后啟動后臺線程，檢查假設是否成立。

算法1 后臺插入算法

輸入：新的key值new_key，新的value值new_value，需要檢查的old_value元信息（記錄了在慢速設備中key的值以及value的值），溢出桶數組overflow_buckets，已經分配了的溢出桶id new_overflow_bucket_id，該溢出桶屬于哪個key_digest

auto overflow_bucket=overflow_buckets［new_overflow_bucket_id］；

unique_lock（overflow_bucket->lock）；//獲取溢出桶，并加鎖

overflow_bucket->check_id=key_digest；/*為溢出桶設置屬于的對象*/

//get old_key from slow storage；//從慢速設備中獲取old_key值

if（new_key==old_key）/*如果new_key與old_key相同，那么說明是更新操作*/

if（update num exceed threshold）/*如果該key更新操作超過了一定的閾值，那么將key從慢速設備中調入內存*/

insert key new_value into overflow_bucket；

else

overflow_bucket->check_id=-1；

recycle overflow_bucket；//回收溢出桶

return；

allocate another_overflow_bucket and its id is another_overflow_bucket_id；//如果是新增操作，那么再次分配一個溢出桶

another_overflow_bucket->check_id=key_digest；

overflow_bucket->key=new_key，overflow_bucket->value=new_value

another_overflow_bucket->key=old_key，anothrer_overflow_bucket->value=old_value；//

overflow_bucket->next_id = another_overflow_bucket_id；

如果檢查為更新操作，且更新操作超過了一定的比例，為避免后續(xù)對該key的持續(xù)更新，導致系統出現不必要的磁盤I/O與后臺線程開銷，那么會將當前key值本身調入內存；否則如果為新增操作，那么會再次分配一個新的溢出桶，并將key1，key2值全部調入內存，避免后續(xù)無法精準對比導致磁盤I/O以及后臺線程的開銷。

c）向哈希表中接著插入（key1，value3），此時進入case 1，即哈希表存在key_digest1，且已經將摘要為key_digest1的所有key值全部調入內存，并且比較發(fā)現key1已經存在，所以可以直接更新key1對應的value值即可。

d）向哈希表接著插入（key3，value4），進入case2，即哈希表存在key_digest1，且已經將摘要為key_digest1的所有key值全部調入內存，并且比較發(fā)現key3不存在，所以可以判斷key3為新增操作，直接將key3插入溢出桶即可。

e）case 5代表插入失敗，此類情況只有在負載因子過高的情況下有極小的概率會出現，但由于自適應熱點感知哈希表對key值本身所占用的內存進行壓縮，增大了哈希桶數組的數量，有效減少了取模沖突的概率，使得插入失敗的概率幾乎忽略不計。算法也可通過調整MAX_HOPS參數值避免此類情況。

1.4 刪除算法

刪除算法是基于查找算法實現的，故刪除流程也有五種不同的情況，由于其中case 1、case 2、case 4、case 5都可以準確地判斷key值是否存在，故可以直接進行刪除操作，而case 3只能判斷摘要存在卻無法判斷key值是否存在，即哈希表中存在摘要為key_digest的鍵，且需要刪除鍵del_key的摘要也為key_digest，但無法判斷哈希表中存在的鍵是否與del_key一致。雖然這種情況的概率非常之低，如工業(yè)哈希函數能夠保證單個key為16 Byte時100 GB的測試中只有332次的哈希碰撞。但模型依然需要實現一個完善的解決方案。

模型會為key_digest分配一個新的溢出桶，接著記錄摘要為key_digest的（key1，value1）的數據，并假設key1與del_key一致，直接刪除當前key_digest的key-value pair，隨后啟動后臺線程，檢查假設是否成立。為避免后續(xù)線程立即查找key1，模型需要對key_digest的溢出桶進行加鎖，并在后臺線程執(zhí)行完畢后才會進行解鎖。檢查算法的偽代碼如算法2所示。

算法2 后臺刪除算法

輸入：需要刪除的key值del_key，需要檢查的old_value元信息（記錄了在慢速設備中old_key的值以及value的值），溢出桶數組overflow_buckets，已經分配了的溢出桶id new_overflow_bucket_id，該溢出桶屬于哪個key_digest，del_key屬于哪個哈希桶bucket，在哈希桶中的位置pos。

auto overflow_bucket=overflow_buckets［new_overflow_bucket_id］；

unique_lock（overflow_bucket->lock）；//獲取溢出桶，并加鎖

overflow_bucket->check_id=key_digest；/*為溢出桶設置屬于的對象*/

get old_key from slow storage；//從慢速設備中獲取old_key值

if（del_key==old_key）{/*如果del_key與old_key相同，那么說明刪除正確*/

insert old_key null into overflow_bucket；

Un_Lock（overflow_bucket->lock）；

//將溢出桶中的old_key標記為已刪除，并解鎖桶

unique_lock（bucket->lock）；

bucket->overflow_ids［pos］=-1；

bucket->key_digets［pos］=DELETED；

recycle overflow_bucket；/*嘗試將del_key所在哈希桶中的元素標記為已刪除，并回收溢出桶*/

return；}

insert old_key old_value into overflow_bucket；/*刪除錯誤，發(fā)生哈希沖突，將（old_key，old_value）調入內存*/

如果假設成立，那么先將溢出桶中的鍵值對標記為刪除狀態(tài)，隨后將該鍵所在哈希桶的位置標記為刪除，并回收溢出桶；如果假設不成立，說明發(fā)生了哈希碰撞，為避免后續(xù)應用連續(xù)針對該缺陷對系統進行攻擊，導致不必要的磁盤I/O與系統后臺線程啟動，那么此時需要將所有摘要為key_digest的所有key全部調入內存。

2 實驗

2.1 實驗環(huán)境

本文所有實驗均在Intel Xeon Gold 5220 CPU@2.20 GHz、64 GB內存、72核心的Linux系統中完成，該型號CPU 的L1數據/指令cache大小分別為32 KB、L2 cache大小為1 024 KB、L3 cache大小為25 344 KB、cache line大小為64 Byte、支持AVX512指令。算法實現語言為C++。設置插入key的大小恒為16 Byte，value大小恒為8 Byte，key的摘要大小為8 Byte。

2.2 數據集

為了評價提出的自適應熱點感知哈希索引的性能和泛化能力，本文參考阿里巴巴第四屆全球數據庫競賽以及YCSB數據集構建了6個測試數據集，分別測試索引的單線程下新增、查找、刪除、熱點更新、熱點查找性能以及多線程下操作性能。該數據集覆蓋了實際應用場景下常見的工作負載，能夠綜合全面地考量模型在復雜多變的實際工業(yè)應用場景下的表現性能。

a）Workload A：單線程負載，插入測試，隨機插入1千萬條鍵值對。

b）Workload B：單線程負載，熱點混合測試，隨機插入1千萬條鍵值對，隨后查找1千萬次，最后刪除1千萬次。其中刪除操作中有75%的操作具有熱點特征，即大部分的操作集中在少量的key上。

c）Workload C：單線程負載，泛化能力測試，插入1千萬條鍵值對，隨后順序查找所有元素，順序更新所有元素，按照75%的熱點比例查找1千萬次以及更新1千萬次。最后熱點刪除1千萬次數據。最后順序刪除所有數據。

d）Workload D：多線程負載，讀寫測試，每個線程分別寫入1千萬條數據，并隨后順序讀取所有數據，隨后更新數據。

e）Workload E：多線程負載，更新刪除測試，分別寫入1千萬條數據，并多線程對所有的元素進行刪除操作。

f）Workload F：多線程負載，熱點讀寫混合測試，每個線程以75%：25%的讀寫比例調用64 M次，其中75%的讀訪問具有熱點的特征，大部分的讀訪問集中在少量的key上面。

2.3 實驗結果分析

2.3.1 負載因子對哈希表的影響

圖3展示了自適應熱點感知哈希表使用不同的負載因子，在Workload A上內存訪問數量的變化趨勢。其中當負載因子為0.97時，哈希表超過了線性探查允許的最大跳數，導致插入失敗。當負載因子為0.1～0.6時，基本只需要一次內存訪問即可插入成功。隨著負載因子的增加，單次操作所需的內存訪問數量急劇上升，到最后負載因子為0.9時，每增加0.01的負載因子，內存訪問數量都會成線性遞增。負載因子較高導致哈希桶數組中空槽的數量減少，從而使得哈希表的單次操作需要多次key值的比較操作。

2.3.2 SIMD指令對哈希表的影響

如圖4所示，展示了當負載因子為0.96時，在Workload B上進行實驗，實驗結果表明，相較于使用FOR LOOP進行查找的哈希索引而言，使用SIMD指令進行快速查找的哈希索引單次操作能夠平均減少30%的時間。FOR-LOOP性能較差是因為該方式需要對哈希桶中的key值直接比較，需要if else語句判斷比較結果，而CPU的分支預測技術有可能會導致指令流水線的失敗；且當key值較大且負載因子較高時，需要大量的字符串比較操作，會相當耗時；如果key值沒有直接存放在哈希桶中時，更需要額外的指針操作取到key值本身，導致內存的隨機訪問，造成cache失效。而SIMD指令利用數據級并行技術，可以使用幾條指令即可對多個數據進行并行比較，且通過位運算代替了if else命令，極大限度地保證了指令流水線的正常運行。

2.3.3 cache line 對齊對哈希表的影響

如圖5所示，展示了在Workload B上cache line對齊對哈希表操作的影響，實驗結果表明，cache line對齊能有效提升20%左右的性能。cache line對齊是因為CPU訪問內存的最小粒度為cache line大小，如果哈希桶的大小不對齊cache line時，會導致不必要的內存訪問。如哈希桶雖然大小僅為63 Byte，但卻未對齊cache line，那CPU需要讀取內存兩次，分別將該桶放置在兩個緩存行中；因CPU cache保證了短于一個字大小的內存具有原子性，導致并發(fā)條件下對兩個獨立哈希桶的操作可能無法實現真正的并行；最后SIMD指令要求比較的數必須在一個cache line中。

2.3.4 自適應熱點感知哈希索引與最新哈希表的性能對比

std：：unordered_map：C++標準庫中自帶的哈希表。

ska：：flat_hash_map：搜索性能非常好，特別是對于少量的條目，但是內存使用率非常高。

ska：：bytell_hash_map：類似谷歌的absl：：flat_hash_map。插入和擦除非常快，查找速度還可以。內存使用率相當好。

robin_hood：：unordered_flat_map：對于整數的查找、插入和刪除非常快，迭代相對較慢。

ankerl：：unordered_dense：：map：robin_hood的升級版，目前速度最快的哈希表實現，通過結合robin_hood：：unordered_flat_map的思想并使用簡單的std：：vector作為存儲，搜索速度非常快，但是刪除一個元素可能相對較慢，它需要兩次查找，因為映射始終保持一個密集存儲的向量。

表1展示了在使用內存量相同的條件下，在Workload C上進行實驗，自適應熱點感知哈希表與最先進的哈希表的性能對比結果。實驗結果表明，自適應熱點感知哈希索引由于對key值的壓縮，增大了哈希桶數組的大小，有效減少了哈希沖突，在插入、查找以及熱點更新操作擁有更高的性能，相比最先進的哈希表，提升了接近20%的性能。但當遇到順序刪除以及順序更新的操作時，由于key值摘要導致key值無法精準比較，即使使用后臺線程以及提前預判盡可能地減少性能損耗，額外的磁盤I/O確認依然導致此類型的操作存在性能瓶頸。

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

圖6展示了本模型在Workload D、Workload E、Workload F三種負載下1 線程到 16 線程吞吐量的實驗結果，實驗表明在熱點操作為主的Workload F中，模型可以基本達到線性加速比。本模型使用細粒度鎖作為并發(fā)沖突解決方案，即在每個桶中存放一個鎖，可以簡單有效地提升哈希表的并發(fā)性能。本實驗中鎖使用自定義實現的細粒度鎖，并基于x86系統使用MESIF protocol協議，具有較強的memory order保證特性，在搜索操作的探查階段并不加鎖。

3 結束語

本文探討了負載因子、SIMD指令、cache line對齊對哈希表性能的具體影響，并意識到現有的哈希索引性能較低且缺乏熱點意識的根本原因是內存有限，導致哈希沖突加劇，且使用統一的策略來管理所有的鍵值對，故提出了自適應熱點感知哈希索引模型。本文將提出的模型在YCSB仿真數據集上與最新哈希表進行對比實驗，并表現出了較大的性能提升。

目前該自適應熱點感知哈希索引模型只適用于對慢速設備中的數據進行索引，無法將其應用在如Redis、Memcached等內存鍵值數據庫存儲系統中。因此在接下來的研究中，可以探索一種用于解決內存鍵值數據庫存儲系統熱點問題的模型。

參考文獻：

［1］蔡盼，張少敏，劉沛然，等.智能數據庫學習型索引研究綜述［J］.計算機學報，2023，46（1）：51-69.（Cai Pan，Zhang Shaomin，Liu Peiran，et al.A review of research on intelligent database learning index［J］.Chinese Journal of Computers，2023，46（1）：51-69.）

［2］Maurer W D，Lewis T G.Hash table methods［J］.ACM Computing Surveys，1975，7（1）：5-19.

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

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

［5］Carlson J.Redis in action［M］.［S.l.］：Manning Publications，2013.

［6］Fitzpatrick B.Distributed caching with Memcached［J］.Linux Journal，2004（124）：72-76.

［7］鄧瑩瑩.布谷鳥哈希表的優(yōu)化及其應用［D］.南京：南京郵電大學，2021.（Deng Yingying.Optimization and application of cuckoo hash table［D］.Nanjing：Nanjing University of Posts and Telecommunications，2021.）

［8］Atikoglu B，Xu Yuehai，Frachtenberg E，et al.Workload analysis of a large-scale key-value store［C］//Proc of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems.2012：53-64.

［9］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.2010：143-154.

［10］Harter T，Borthakur D，Dong S，et al.Analysis of{HDFS}under HBase：a Facebook messages case study［C］//Proc of the 12th USENIX Conference on File and Storage Technologies.2014：199-212.

（下轉第253頁）

（上接第230頁）

［11］Huang Qi，Gudmundsdottir H，Vigfusson Y，et al.Characterizing load imbalance in real-world networked caches［C］//Proc of the 13th ACM Workshop on Hot Topics in Networks.2014：1-7.

［12］Jung J，Krishnamurthy B，Rabinovich M.Flash crowds and denial of service attacks：characterization and implications for CDNs and Web sites［C］//Proc of the 11th International Conference on World Wide Web.2002：293-304.

［13］David K，Eric L，Tom L，et al.Consistent hashing and random trees：distributed caching protocols for relieving hot spots on the World Wide Web［C］//Proc of the 29th Annual ACM Symposium on Theory of Computing.1997：654-663.

［14］Cheng Yue，Gupta A，Butt A R.An in-memory object caching framework with adaptive load balancing［C］//Proc of the 10th European Conference on Computer Systems.2015：1-16.

［15］Dabek F，Kaashoek M F，Karger D，et al.Wide-area cooperative sto-rage with CFS［J］.ACM SIGOPS Operating Systems Review，2001，35（5）：202-215.

［16］Taft R，Mansour E，Serafini M，et al.E-store：fine-grained elastic partitioning for distributed transaction processing systems［J］.Procee-dings of the VLDB Endowment，2014，8（3）：245-256.

［17］Fan B，Lim H，Andersen D G，et al.Small cache，big effect：provable load balancing for randomly partitioned cluster services［C］//Proc of the 2nd ACM Symposium on Cloud Computing.2011：1-12.

［18］Jin Xin，Li Xiaozhou，Zhang Haoyu，et al.Netcache：balancing key-value stores with fast in-network caching［C］// Proc of the 26th Symposium on Operating Systems Principles.2017：121-136.

［19］Li Xiaozhou，Sethi R，Kaminsky M，et al.Be fast，cheap and in control with SwitchKV［C］// Proc of the 13th USENIX Symposium on Networked Systems Design and Implementation.2016：31-44.

［20］Mattson R L，Gecsei J，Slutz D R，et al.Evaluation techniques for sto-rage hierarchies［J］.IBM Systems journal，1970，9（2）：78-117.

［21］Chen Jiqiang，Chen Liang，Wang Sheng，et al.Hot-Ring：a hotspot-aware in-memory key-value store［C］//Proc of the 18th USENIX Conference on File and Storage Technologies.2020：239-252.

［22］Desnoyers M，McKenney P E，Stern A S，et al.User-level implementations of read-copy update［J］.IEEE Trans on Parallel and Distributed Systems，2011，23（2）：375-382.

［23］Michael M M.Safe memory reclamation for dynamic lock-free objects using atomic reads and writes［C］// Proc of the 21st Annual Sympo-sium on Principles of Distributed Computing.2002：21-30.

［24］王天宇，徐云，王彪.基于位圖的鍵值存儲哈希優(yōu)化［J］.計算機應用研究，2023，40（7）：2106-2110.（Wang Tianyu，Xu Yun，Wang Biao.Optimization of key value storage hash based on bitmap［J］.Application Research of Computers，2023，40（7）：2106-2110.）