面向持久化鍵值數(shù)據(jù)庫的自適應(yīng)熱點(diǎn)感知哈希索引

王楠 吳云

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

關(guān)鍵詞：持久化鍵值存儲；自適應(yīng)；熱點(diǎn)感知；哈希索引

中圖分類號：TP391.9?? 文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

研究人員通過研究發(fā)現(xiàn)，如果哈希表不存在任何哈希沖突，那么熱點(diǎn)問題將不復(fù)存在，因?yàn)樗乃胁僮鞫伎梢赃_(dá)到 O（1）的時(shí)間復(fù)雜度。于是最小完美哈希的核心思想就是構(gòu)建一個沒有沖突的哈希表，然而它無法支持插入操作。隨著人工智能技術(shù)的發(fā)展，研究學(xué)者們認(rèn)為機(jī)器學(xué)習(xí)模型的本質(zhì)是一個映射函數(shù)，故可以使用機(jī)器學(xué)習(xí)模型代替哈希函數(shù)，學(xué)習(xí)key和value之間CDF分布關(guān)系，從而有效地壓縮key的存儲空間并減少哈希沖突，然而結(jié)果卻是機(jī)器學(xué)習(xí)模型的計(jì)算代價(jià)太過昂貴，無法有效提升哈希索引的性能。

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

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

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

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

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

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

1 本文方法

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

1.1 模型概述

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

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

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

1.2 查找算法

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

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

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

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

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

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

1.3 插入算法

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

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

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

算法1 后臺插入算法

輸入：新的key值new_key，新的value值new_value，需要檢查的old_value元信息（記錄了在慢速設(shè)備中key的值以及value的值），溢出桶數(shù)組overflow_buckets，已經(jīng)分配了的溢出桶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；/*為溢出桶設(shè)置屬于的對象*/

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

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

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

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ù)更新，導(dǎo)致系統(tǒng)出現(xiàn)不必要的磁盤I/O與后臺線程開銷，那么會將當(dāng)前key值本身調(diào)入內(nèi)存；否則如果為新增操作，那么會再次分配一個新的溢出桶，并將key1，key2值全部調(diào)入內(nèi)存，避免后續(xù)無法精準(zhǔn)對比導(dǎo)致磁盤I/O以及后臺線程的開銷。

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

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

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

1.4 刪除算法

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

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

算法2 后臺刪除算法

輸入：需要刪除的key值del_key，需要檢查的old_value元信息（記錄了在慢速設(shè)備中old_key的值以及value的值），溢出桶數(shù)組overflow_buckets，已經(jīng)分配了的溢出桶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；/*為溢出桶設(shè)置屬于的對象*/

get old_key from slow storage；//從慢速設(shè)備中獲取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標(biāo)記為已刪除，并解鎖桶

unique_lock（bucket->lock）；

bucket->overflow_ids［pos］=-1；

bucket->key_digets［pos］=DELETED；

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

return；}

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

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

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)環(huán)境

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

2.2 數(shù)據(jù)集

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

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

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

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

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

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

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

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

2.3.1 負(fù)載因子對哈希表的影響

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

2.3.2 SIMD指令對哈希表的影響

如圖4所示，展示了當(dāng)負(fù)載因子為0.96時(shí)，在Workload B上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，相較于使用FOR LOOP進(jìn)行查找的哈希索引而言，使用SIMD指令進(jìn)行快速查找的哈希索引單次操作能夠平均減少30%的時(shí)間。FOR-LOOP性能較差是因?yàn)樵摲绞叫枰獙Ｍ爸械膋ey值直接比較，需要if else語句判斷比較結(jié)果，而CPU的分支預(yù)測技術(shù)有可能會導(dǎo)致指令流水線的失??；且當(dāng)key值較大且負(fù)載因子較高時(shí)，需要大量的字符串比較操作，會相當(dāng)耗時(shí)；如果key值沒有直接存放在哈希桶中時(shí)，更需要額外的指針操作取到key值本身，導(dǎo)致內(nèi)存的隨機(jī)訪問，造成cache失效。而SIMD指令利用數(shù)據(jù)級并行技術(shù)，可以使用幾條指令即可對多個數(shù)據(jù)進(jìn)行并行比較，且通過位運(yùn)算代替了if else命令，極大限度地保證了指令流水線的正常運(yùn)行。

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

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

2.3.4 自適應(yīng)熱點(diǎn)感知哈希索引與最新哈希表的性能對比

std：：unordered_map：C++標(biāo)準(zhǔn)庫中自帶的哈希表。

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

ska：：bytell_hash_map：類似谷歌的absl：：flat_hash_map。插入和擦除非?？?，查找速度還可以。內(nèi)存使用率相當(dāng)好。

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

ankerl：：unordered_dense：：map：robin_hood的升級版，目前速度最快的哈希表實(shí)現(xiàn)，通過結(jié)合robin_hood：：unordered_flat_map的思想并使用簡單的std：：vector作為存儲，搜索速度非常快，但是刪除一個元素可能相對較慢，它需要兩次查找，因?yàn)橛成涫冀K保持一個密集存儲的向量。

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

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

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

3 結(jié)束語

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

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

參考文獻(xiàn)：

［1］蔡盼，張少敏，劉沛然，等.智能數(shù)據(jù)庫學(xué)習(xí)型索引研究綜述［J］.計(jì)算機(jī)學(xué)報(bào)，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)化及其應(yīng)用［D］.南京：南京郵電大學(xué)，2021.（Deng Yingying.Optimization and application of cuckoo hash table［D］.Nanjing：Nanjing University of Posts and Telecommunications，2021.）

［8］Atikoglu B，Xu Yuehai，F(xiàn)rachtenberg 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.

（下轉(zhuǎn)第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］.計(jì)算機(jī)應(yīng)用研究，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.）