*

（1.中國科學技術大學計算機科學與技術學院，合肥 230001；2.中國人民解放軍31002部隊，北京 100081）

0 引言

在過去的數十年中，由于存儲密度的限制，動態(tài)隨機訪問內存（Dynamic Random Access Memory，DRAM）的容量始終無法超越64 GB，不能滿足大數據應用對大容量內存的需求。近年來，非易失性內存（Non-Volatile Memory，NVM）得到了快速發(fā)展。特別是Intel 于2019 年4 月推出了單條512 GB 的傲騰非易失內存（Intel Optane DC Persistent Memory），支持8 TB的單機最大NVM 內存，為實現面向大數據實時存取的內存數據庫系統(tǒng)提供了有力的支持。在此背景下，如何使得數據庫技術（包括索引、緩存管理、查詢處理、事務管理等）能夠適應引入NVM 之后的數據庫系統(tǒng)，成為近些年國內外的研究熱點。

與DRAM 相比，NVM 的密度更高，容量更大，但同時也具有讀快寫慢、寫次數有限等限制［1］，因此傳統(tǒng)數據庫算法直接運行在NVM 上往往會導致較多的隨機寫操作，不僅會影響性能，也會影響NVM的使用壽命，因此需要重新進行設計。

索引是數據庫系統(tǒng)保證存取性能的重要技術。由于NVM 引入后人們希望構建純內存的數據庫系統(tǒng)來支持大數據應用，因此，未來基于NVM 的NoSQL數據庫系統(tǒng)（例如鍵值數據庫、列存儲數據庫等）將是一個主要的發(fā)展趨勢。NoSQL數據庫系統(tǒng)通常要求索引能夠支持Put、Get等操作，但對范圍查詢、連接查詢等一般不做要求，因此適合采用哈希索引。在哈希索引中，線性哈希索引因其良好的點查詢效率、空間代價以及低維護成本而被廣泛使用于數據庫系統(tǒng)中。但是，傳統(tǒng)的線性哈希索引并不能直接應用于NVM。首先，由于NVM具有寫慢讀快的特點，并且寫次數也有限制，這與傳統(tǒng)DRAM讀寫均衡以及寫次數不受限有著較大的區(qū)別，而傳統(tǒng)的線性哈希索引并未考慮NVM 的這一特性；其次，傳統(tǒng)基于DRAM的線性哈希索引需要借助先寫日志（Write-Ahead Logging，WAL）來實現數據的可恢復性和一致性，但如果在NVM 上也同樣采用WAL，將帶來大量的NVM 上的日志寫操作，同樣有損NVM的使用壽命。

近幾年，國內外研究人員相繼提出了若干針對NVM 的哈希索引算法，例如改進后的可擴展哈希索引CCEH（Cacheline-Conscious Extendible Hashing）［2］、布谷鳥哈希索引［3-4］、Path Hashing［5］、Level Hashing［6-7］等。因為NVM 讀快寫慢帶來的寫延遲問題以及持久性特性帶來的數據一致性問題之間互相矛盾，因此大家在設計算法時都需要在各項性能之間進行適當的取舍。從目前的研究現狀看，研究者考慮了靜態(tài)哈希和可擴展哈希，但在面向NVM的線性哈希索引方面還鮮有研究。

本文基于傳統(tǒng)的線性哈希索引［8］，提出并實現了一種NVM 友好的線性哈希索引NVM-LH（NVM-oriented Linear Hashing）。相較于傳統(tǒng)的線性哈希索引，NVM-LH 考慮了NVM 的持久性特性，增加了無日志的數據一致性策略，并根據NVM 數據存取的特點，設計了緩存行友好策略以優(yōu)化內存讀寫次數，減少寫延時帶來的額外開銷。本文并將NVM-LH與2019年提出的最新NVM可擴展哈希索引CCEH［2］進行了對比。結果表明，NVM-LH 在NVM 寫友好性、空間利用率等方面均優(yōu)于CCEH。

1 相關工作

1.1 研究面臨的挑戰(zhàn)

1）需要寫友好。

NVM 除了持久性之外，最大的特點就是讀快寫慢，寫操作的延遲甚至可以達到DRAM 的數十倍［1］，因此設計NVM 友好的算法時，首先要考慮的就是盡量減少寫操作的數量。

在增加新數據時，至少會有一次寫操作來將數據的指針加入到索引中，而其他寫操作則可能來自于哈希值沖突的處理，因此應當盡量避免處理沖突時進行寫操作，比如強行設置沖突項移動的次數上限［6］。除此之外動態(tài)哈希在增加新數據后桶溢出時要進行分裂和擴展，此時也會出現寫操作，因此減少在哈希表分裂時產生的寫操作也是一種值得考慮的方法，例如分裂后不立刻刪除原桶中已經遷移出的數據，而是在后續(xù)插入新數據時再覆蓋這些可以判斷出不合法的數據［2］。

2）需要緩存行（Cacheline）友好。

因為中央處理器（Central Processing Unit，CPU）緩存（Cache）從內存取數據時，通常以緩存行為單位進行（一般為64 B），因此，NVM 中的數據在存儲時應保持按緩存行對齊，并將經常一起使用的數據放到同一個緩存行中以提高緩存的效率［2］。

3）需要減少CPU緩存對NVM的影響。

在現有計算機架構中，CPU 緩存和內存之間的數據交互是必要的，但某些操作對于NVM 并不友好，例如強制將緩存數據刷入NVM 的clflush 操作會增加NVM 寫操作，mfence 操作強制規(guī)定寫操作執(zhí)行順序會增加NVM 上的寫等待時間［7，9-10］。

4）需要減少指針操作。

NVM 既可以作為計算用的內存，也可作為持久數據存儲介質。當NVM 作為存儲介質時，程序可能會使用較多的指針操作來訪問NVM，這些指針操作可能會導致運行的錯誤，因而減少指針操作也是一個需要考慮的問題。

5）需要保證數據一致性。

NVM 具有非易失性，因此相較于DRAM 不需要考慮斷電時的工作狀態(tài)。但由于64 位CPU 一次只能操作8 B 的數據，在CPU與NVM之間按64 B的緩存行進行交互時，仍然需要保證失敗原子性［11］。如果寫緩存行時斷電，不會造成只寫入了一半的情況，重啟后要么完全寫入，要么完全沒寫入。

另一個與一致性相關的問題是如何保證多個寫操作之間的順序（例如WAL 寫操作與隨后的數據寫操作之間的順序）。為了控制寫數據的順序，系統(tǒng)需要經常使用mfence 和clflush操作或者使用日志記錄或寫時復制機制，而這又會給NVM 的運行帶來極大的時間開銷［7，10-11］，因此，算法要求在保證一致性的同時具有較低的時間開銷。

6）需要較高的空間利用率。

雖然NVM 具有大容量的特點，但只是相對于現有的內存而言的，與磁盤等設備相比，NVM 的容量仍顯不足。因此，提高NVM 的空間利用率量也是需要考慮的一個重要方面。尤其對于基于NVM 的索引而言，空間利用率高意味著同等情況下索引的大小更小，更有利于存取性能的提升。

1.2 面向NVM的哈希索引研究

哈希索引作為一種基本的索引結構，既可以作為磁盤數據庫索引，也可以作為內存數據庫索引。本項目針對的是內存數據庫索引，因此本節(jié)主要以內存哈希索引為基礎進行討論。下面從靜態(tài)哈希和動態(tài)哈希兩個方面討論NVM 感知的哈希索引研究現狀。

1）NVM感知的靜態(tài)哈希索引。

布谷鳥哈希（Cuckoo Hash）是常用的內存哈希結構，具有空間利用率高、查詢速度快等特點。布谷鳥哈希通過多次置換的方式尋找可分配的空間以解決哈希沖突問題。然而，大量的級聯(lián)更新會引發(fā)額外的寫操作，因此不能保證對NVM 的寫友好性。為了解決這個問題，DEBNATH 等在布谷鳥哈希上進行了一系列的優(yōu)化，提出PFHT（PCM-Friendly Hash Table）索引結構［9］。PFHT 由Main Table 和Stash Table 組成。在解決哈希沖突策略上，Main Table 使用布谷鳥策略，Stash Table 使用鏈式策略。通過限制Main Table 的置換次數，可以減少NVM 的寫操作；然而，由于Stash Table 的鏈式結構存在大量的指針，使得讀操作時會導致大量的CPU 緩存的丟失因而降低讀性能，同時寫性能也會由于指針的額外更新操作而下降。

華中科技大學的華宇教授等提出了Path Hashing 索引［5］，其邏輯結構類似于一棵倒置的二叉樹。Path Hashing 通過多個哈希函數和數據置換操作等優(yōu)化技巧，提高了索引結構的內存利用率。同時，底層的結構和Stash Table 的效果是相同的，但它通過類似二叉樹的結構消除了指針帶來的影響，從而提高了寫性能。在物理組織上，將相鄰的兩層中具有連接關系的節(jié)點組織在同一個緩存行中，從而提高查詢時CPU 緩存的命中率。

面向NVM 的哈希索引不僅需要考慮到NVM 的讀寫特性，還需要考慮數據的可恢復性。因此，研究者提出了Group Hashing［12］，它利用原子更新和相關指令，保證了索引結構的可恢復性。Group Hashing 將存儲空間分成多個組（類似頁面結構），通過共享組的方式，解決哈希沖突。此外，通過原子更新位圖，實現數據的更新和刪除，從而保證索引更新時的數據一致性。

2）NVM感知的動態(tài)哈希索引。

靜態(tài)哈希適合數據集大小相對穩(wěn)定的應用場景，然而，在插入/刪除頻繁的應用場景下，由于數據的波動較大，靜態(tài)哈希需要通過重建哈希索引的方式進行擴容。這一過程不僅會導致對NVM 的大量寫操作，造成性能的抖動和下降，而且在并發(fā)操作時需要對擴容的哈希索引進行加鎖，導致索引的訪問被阻塞。動態(tài)哈希通過桶分裂的方式進行增量式擴容，擴容過程不需要重建整個哈希索引，而且不需要對整個索引進行加鎖，因此可以較好地平衡可擴展性和性能。

目前在面向NVM 的動態(tài)哈希索引方面的研究工作相對較少，主要有2019 年提出的Level Hashing 和CCEH。Level Hashing［6-7］采用雙層結構：Top Level 和Bottom Level。當Bottom Level 無法插入新的數據時，觸發(fā)哈希桶目錄的擴容操作。首先，創(chuàng)建新的Top Level 并將舊的Bottom Level 中的數據進行拷貝；接著，將舊的Top Level 作為新的Bottom Level 并丟棄舊的Bottom Level 完成擴容操作。CCEH 索引［2］是2019年提出的另一種NVM 優(yōu)化的可擴展哈希索引。區(qū)別于傳統(tǒng)的可擴展哈希結構，它在哈希桶目錄和桶之間增加了一個段結構以減少目錄結構帶來的空間開銷，但由于CCEH 采用了可擴展哈希的設計，每次成倍地增加段結構的數量，使得每次增長后的哈希索引空間利用率都會降低，這與NVM 索引的空間高效性設計目標相背離。

2 基于NVM的線性哈希索引

目前，如何在現有的計算機系統(tǒng)中合理地使用NVM 仍是一個未完全解決的問題。目前Intel 推出的傲騰持久化內存支持兩種架構，即Memory Mode 和App-Direct Mode。在Memory Mode下，DRAM 作為NVM 的緩存使用，數據存取會首先訪問DRAM，DRAM 沒有命中時再訪問NVM。Memory Mode 方式并不適合數據庫系統(tǒng)。首先，由于DRAM 只是作為NVM 的緩存，因此系統(tǒng)可見的內存僅為NVM 的空間，因此在內存空間使用上不合算；其次，這一架構只是利用了NVM 比DRAM 容量大的優(yōu)點，所有數據訪問依然還是通過DRAM，沒有充分利用NVM 的非易失性特點。在App-Direct Mode下，系統(tǒng)可用的內存空間等于DRAM 和NVM 的容量之和，而且操作系統(tǒng)可以感知兩類內存的特性，可以充分利用DRAM 和NVM各自的優(yōu)點。從目前DRAM 和NVM 的發(fā)展趨勢來看，DRAM和NVM 并存的App-Direct Mode 對于數據庫系統(tǒng)更具有可行性和發(fā)展前景。因此，本文的研究也基于App-Direct Mode 架構開展設計。

本文基于傳統(tǒng)的線性哈希索引，提出了NVM 友好的NVM-LH 索引。該索引通過存儲數據時的緩存行對齊實現了緩存行友好性，并增加了無日志式的一致性保證，從而在保證數據一致性的基礎上進一步減少NVM上的寫操作。

2.1 緩存行對齊

為了實現CPU 緩存友好，需要實現緩存行對齊，并盡可能將一起使用的數據存在同一個緩存行中，同時盡量將讀寫操作分開在不同的緩存行上執(zhí)行。

當鍵值長度小于一個緩存行時，圖1 所示的一個桶可以存儲多條同哈希值的數據并實現緩存行對齊。在讀取數據時，可以一次性讀入多條同哈希值的數據，這有助于提高查詢性能。

圖1 緩存行友好的結構設計Fig.1 Cacheline-friendly structure design

2.2 NVM-LH的操作

索引初始分配n個桶（編號0～n-1），每個桶有m個slot。為了便于統(tǒng)計，n、m均取2 的整數次冪。線性哈希索引需要設定一個加載因子上限，當索引的加載因子達到這個上限時，需要對索引進行分裂操作。加載因子也決定了線性哈希索引的空間利用率。索引還需要維護一個深度值i（i≥1），表示當前索引中的桶數n應滿足2i-1≤n＜2i。

1）插入。

對于插入key 的請求，NVM-LH 先計算出key 的哈希值，取哈希值的二進制后i位得到桶編號x。若x＜n，則說明該桶已存在，可以存入數據；若x≥n，則說明x指向的桶還未被分裂出來，因此應當將數據存入未分裂的桶，即編號為（x-2i-1)的桶。找出對應的桶，然后在桶中的空slot處存入鍵值，若桶中已滿，則申請一個新的溢出桶，將鍵值存入溢出桶中，并將指向溢出桶的指針存在原桶中。

以上操作需要保證失敗原子性，2.3 節(jié)將會對此問題進行詳細討論。每次插入完成后，都需要計算當前索引的加載因子，若加載因子超過了初始設定的上限，則執(zhí)行分裂操作。

2）分裂。

當索引的加載因子超過了設定的上限時，需要對索引進行分裂操作（分裂操作不被允許在用戶界面調用），這也是動態(tài)索引與靜態(tài)索引的不同之處。索引維護一個指針p，其始終指向下一個需要分裂的桶，創(chuàng)建索引時p指向第一個桶。

當需要執(zhí)行分裂操作時，算法先找到p所指向的原桶，然后再申請一個新桶，并將新桶添加到索引中，編號為n。遍歷原桶，將原桶中滿足其key 的哈希值的二進制第i位為1 的記錄存入新桶，然后標記原桶中的該條記錄位置為空。全部執(zhí)行完成后，將n加1，并將p指向原桶的下一個桶。若此時桶的總數n和索引的深度i滿足：n≥2i，則索引深度加1，更新p重新指向第一個桶。圖2 顯示了一輪完整的分裂過程（取加載因子上限為0.75，哈希函數即為其自身，每個桶有3個slot，帶有P標識的桶為即將分裂的桶）。圖2（a）顯示了初始索引，其中深度i=3，桶數n=4，總記錄數r=8。圖2（b）中，插入13 到索引后由于對應的桶已滿，但加載因子未達到上限，故將13 存入溢出桶，同時導致加載因子達到上限，觸發(fā)桶0 分裂。圖2（c）中，插入23、16 成功，插入11 出現沖突并觸發(fā)桶1 分裂。圖2（d）中，插入33成功，插入35觸發(fā)桶2分裂。圖2（e）中，插入24 成功，插入6 導致桶3 分裂。此時桶數n=2i，說明一輪（共2i-1次）分裂操作完成，p重新指向桶0，索引深度更新為i=4）

完成分裂操作后，算法再檢查索引的加載因子是否超過上限，如果超過，則再執(zhí)行一次分裂操作。需要注意的是，如果分裂操作導致原桶的溢出桶為空，則立刻釋放溢出桶。

3）查詢。

查詢操作確定桶編號的過程與插入記錄時的操作類似，這里不再多述。利用key 的哈希值找出對應的桶后，在桶中遍歷找出與給定key相同的記錄，返回該記錄的value即可。

4）刪除。

為了減少寫內存的操作，刪除數據時可以采用只刪除key的方法（或將key的值改為invalid），這樣既不影響后續(xù)數據的插入、分裂和查詢，也減少了相當數量的寫操作。

需要注意的是，如果刪除操作導致目標桶的溢出桶為空，要即時釋放溢出桶。

圖2 NVM-LH的分裂過程示意圖Fig.2 Schematic diagram of NVM-LH splitting process

2.3 無日志的一致性保證

數據一致性要求當操作執(zhí)行到一半時如果發(fā)生了異常導致操作中斷，需要保證執(zhí)行到一半的操作可以回退到執(zhí)行之前的狀態(tài)，或者繼續(xù)執(zhí)行完成全部的操作并得到正確的結果。傳統(tǒng)數據庫系統(tǒng)中通常使用WAL 來實現數據一致性。WAL可以完整地記錄所有的數據更新操作細節(jié)，可以實現系統(tǒng)崩潰時的操作回滾，使數據恢復到崩潰前的一致性狀態(tài)。但是在NVM 上登記WAL 需要大量的寫操作，同時還需要使用大量的mfence 指令來保證日志的先寫順序，這不僅會對算法的執(zhí)行速度產生很大影響，同時大量的NVM 寫操作也會進一步加大系統(tǒng)的處理延遲，此外，NVM 寫操作過多也不利于NVM的壽命。本文給出了一種不需要記錄日志就能完成一致性狀態(tài)回退的算法，可以有效減少NVM寫操作次數。

2.3.1 非高并發(fā)狀態(tài)

本節(jié)首先討論非高并發(fā)狀態(tài)下的情況。本文的算法直接使用每條記錄的key 來判定該條記錄是否合法。如果一個slot 中key 的值為invalid（設置為一個不可能出現在數據庫中的數）時，該slot即認為是空slot，可以插入數據。

1）插入。

當插入key 時，NVM-LH 使用mfence 指令將key 的寫入放在整個插入操作的最后，只有當key 的值從invalid 修改為待插入的值時，該插入操作才算全部完成。如果插入操作執(zhí)行到一半時發(fā)生了中斷，重啟后因為key 的值仍為invalid，所以無論是否已經成功找到目標桶或slot，或是已經成功插入了value，該數據的插入都認為是失敗的。通過這種方式，NVMLH可以保證插入操作的失敗原子性。

2）分裂。

當進行分裂操作時，因為無論算法是否并發(fā)，同一時刻都只能至多有一個桶在執(zhí)行分裂操作，所以在開始分裂之前，算法先在NVM 中記下當前分裂的桶。從而在程序重啟后也可以立即找到操作中斷時的正在分裂的桶。由于NVM-LH先將申請的新桶添加到索引中，再遍歷原桶開始搬遷數據，因此重啟后新桶中的已經完成搬遷的數據不會丟失，并且也為后續(xù)的分裂操作奠定了基礎。

由于插入操作可以保證失敗原子性，因此分裂中斷時正在從原桶遷移至新桶的記錄肯定不會存儲在新桶中。算法需要保證在單條數據遷移完成之前，數據一定要在原桶中?；谶@一分析，可以發(fā)現，在執(zhí)行分裂操作時，將原桶中數據的key的值修改為invalid這一步應當放在整個遷移過程的最后，即先將數據插入新桶，再刪除原桶中的數據，這樣程序重啟后繼續(xù)完成分裂操作時不會丟失數據。同時，重復插入具有相同key 的數據在執(zhí)行插入操作時會被自動忽略（或者返回相應的錯誤碼），這樣就保證了在繼續(xù)執(zhí)行前面中斷的分裂操作時，數據既沒有丟失，也不會被重復插入。

顯然，算法不在執(zhí)行分裂操作時3 個全局數據n、p、i之間滿足關系式n=2i+p，因此在分裂操作時，先更新桶數n，再申請新桶，對數據進行搬遷，然后再根據需要更新深度i（由算法可知大部分情況下不需要更新深度），最后再更新指針p。如果中斷重啟后發(fā)現3 個參數之間的關系變成了n＞2i-1+p，說明只有桶數進行了更新，此時恢復該分裂操作只需要程序再重新完整地執(zhí)行一遍該分裂操作。同樣，如果中斷重啟后發(fā)現三個參數之間關系變成了n＜2i-1+p，則表明索引深度i的值已經更新，但在更新指針之前程序發(fā)生了中斷，說明只有指針還未更新，因此在繼續(xù)完成分裂操作時只需要完成指針更新即可。

無論何種情況，程序都將更新桶數n作為分裂操作的開始信號，將更新完指針p作為分裂操作結束的信號。

3）刪除。

當進行刪除操作時，算法直接修改key 的值為invalid，其他部分不做變動，這一過程是一個原子操作，可以保證數據一致性。

2.3.2 高并發(fā)狀態(tài)

在高并發(fā)狀態(tài)下，2.3.1 節(jié)討論的無日志算法依然對單個線程有效，因此各操作的原子性依然可以得到保證。現在的問題是如何保證各線程之間的數據一致性。解決這一問題常見的方法是通過加鎖來實現線程間的數據一致性。本文也通過給操作增加以桶為粒度的S 鎖和X 鎖來實現線程間的操作約束。當執(zhí)行查詢操作時，線程需要先申請目標桶的S 鎖；當而執(zhí)行插入、刪除操作時則需要申請目標桶的X鎖。

下面討論由索引維護的全局數據：總記錄數r，桶數n，索引深度i和待分裂指針p。

1）r：r在算法中的作用是負責觸發(fā)索引的分裂操作，但因為索引的分裂操作的觸發(fā)僅僅由當前桶數和總記錄數（每個桶的容量和加載因子上限在創(chuàng)建索引時已經固定）決定，不需要由特定的線程觸發(fā)，且分裂操作的目標桶與觸發(fā)索引分裂的插入操作的目標桶之間毫無關系，因此分裂操作在一定范圍內是允許滯后的，即：總記錄數r的更新可以只保證弱一致性。這樣在應當分裂到執(zhí)行分裂之間的這段時間內，本來需要插入新桶的數據會被存進原桶中，但最終執(zhí)行分裂操作時仍會被遷移至新桶中。因為所有的插入操作都需要更新總記錄數，但只有極少數的插入操作會發(fā)生在應當分裂但未分裂的時間間隙中，因此在程序高并發(fā)時，和保證總記錄數強一致所導致的等待時間相比，這部分寫內存操作的代價可以忽略不計。

2）n：n是索引分裂的觸發(fā)條件之一，因此在允許r保持弱一致的情況下，n應當始終保持強一致。

3）i：i在算法的插入和分裂操作中都需要被讀取，因此深度i需要十分精確以確保大量的插入操作都能正確地執(zhí)行，所以i必須保持強一致性。

4）p：p在索引中的作用是提供下一個需要被分裂的桶的位置。在創(chuàng)建索引時，如果單個桶的大小m被設定得較大，則每次分裂之間的時間間隔也會足夠大，因此在這種特定初始情況下待分裂指針也就沒必要時刻保證一致性，只需要保證弱一致即可。

2.4 算法分析

NVM-LH 的數據結構與傳統(tǒng)線性哈希索引的結構類似，因此兩者具有相似的算法執(zhí)行順序，在查詢性能和空間利用率上沒有區(qū)別。與傳統(tǒng)線性哈希索引相比，NVM-LH 的性能提升主要體現在插入數據時的緩存行對齊和無日志一致性保證上。因為算法進行了緩存行對齊優(yōu)化，因此寫入一對鍵值只需要1 次寫內存操作：先將鍵值寫入緩存，再由緩存寫入NVM，因為緩存行對齊的緣故，鍵值由緩存寫入NVM 時理論上只需要一次寫操作。同理，索引進行分裂操作時因為緩存行對齊，有很多的相鄰數據都被寫入了同一個緩存行，故實際寫操次數作應小于遷移的鍵值對數。算法使用了無日志的一致性保證，避免了記錄日志產生的大量寫操作，但仍需要使用一定數量的mfence 指令來保證數據寫入的順序。每個插入操作都需要使用一次mfence 指令；對于每次分裂操作，如果更新了索引深度則需要三次mfence 指令，如果未更新索引深度則只需使用兩次mfence 指令。而對于傳統(tǒng)基于日志的線性哈希索引，每次插入數據時除了寫數據操作之外還需要額外的寫日志操作，因此NVM 寫操作次數將明顯高于NVMLH。

與基于NVM 的可擴展哈希索引（如CCEH［2］）相比，NVMLH 的優(yōu)勢主要體現在兩個方面：首先，CCEH 索引由于在每次桶溢出時即成倍增加桶，因此空間利用率較低（這是由可擴展哈希索引的設計特性導致的），而NVM-LH采用的是線性擴展的設計，每次只增加一個桶，因此在同等數據集上的空間利用率將大大高于CCEH；其次，如果插入的數據具有較強的傾斜性，即大部分的數據都集中在某幾個桶中，CCEH 將產生較多的桶分裂操作，并且每一次桶分裂操作由于都是成倍增加桶數量，將帶來大量的NVM 寫操作。相比之下，NVM-LH 由于有溢出桶的存在，桶分裂次數將遠小于CCEH，因此理論上的NVM 寫次數也小于CCEH。在第3 章中的實驗結果也證明了這一點。

需要指出的是，CCEH 的理論查詢性能必定優(yōu)于NVMLH。這是因為可擴展哈希索引不存在著溢出桶，因此其查詢性能必定優(yōu)于需要訪問溢出桶的線性哈希索引。但是，線性哈希索引的優(yōu)點在于能夠提供時間性能和空間代價兩個方面的折中設計；并且，由于NVM-LH 采用了緩存行對齊、無日志一致性保證等技術，以及減少了桶分裂操作，因此在減少NVM 寫操作次數方面優(yōu)于CCEH。綜合而言，NVM-LH 為NVM 上的哈希索引設計提供了一種在空間利用率、插入性能、NVM寫友好三個方面都具有較好性能的設計思路。

3 性能驗證

3.1 實驗環(huán)境與準備

實驗平臺為Ubuntu-18.04.4-desktop-amd64，編譯環(huán)境為gcc-7.5.0，編譯命令為g++-std=c++17-I./-lrt-O3-c-o nvmlh.o nvmlh.cpp。

為了進行對比實驗，本文選擇了2019 年最新的NVM 感知哈希索引CCEH（https：//github.com/DICL/CCEH）［2］。實驗主要對比性能和空間利用率。實驗使用的數據集分為A、B兩組。A 組數據的key 為1～R按順序排列，其中R為數據集大??；B 組數據的key 為隨機生成的十進制16 位數字，兩種數據的value均為隨機生成的由字母構成的32位字符串。

實驗中涉及到的可調變量包括：NVM 寫延遲時間（測試中默認為300 ns），索引初始桶（段）數量n，單個桶（段）大小m，數據集大小R，NVM-LH 的加載因子上限u（測試中默認為75%）。實驗輸出的結果變量包括程序的運行時間、算法寫內存次數、算法的空間利用率。

3.2 最佳桶大小

CCEH 的論文中給出了其最優(yōu)段大小范圍為4～16 KB［2］，因此后續(xù)的實驗中CCEH 的單個段大小均設置為16 KB，即m=1 024。

NVM-LH 的最佳桶大小選取了插入操作的吞吐量和NVM 寫次數兩個指標：圖3（a）顯示了不同桶大小執(zhí)行插入操作時的吞吐量；圖3（b）顯示了不同桶大小執(zhí)行插入操作時的寫內存次數。

圖3 最佳桶大小搜尋結果Fig.3 Result of finding the best bucket size

由圖3 可以看出，寫內存次數隨m的增大而減少，但減少的趨勢越來越緩，而數據的吞吐量在512 B 時取到峰值，因此綜合考慮，可以將最佳桶大小范圍取在256～512 B。在后續(xù)的測試中，本文均設置單個桶大小為512 B，即m=32。

3.3 插入操作的效率

實驗選取的變量為初始桶（端）的數量n。因為NVM-LH和CCEH 的數據結構不同，因此需要按比例對齊坐標：CCEH中的一個段容量相當于NVM-LH 中的32 個桶，即m（CCEH）=32m（NVM-LH），因此n（NVM-LH）=32n（CCEH）。圖4（a）和圖4（b）分別展示了插入200萬B 組數據時二者的吞吐量和NVM寫次數對比結果。其中最后一組數據，即n（NVM-LH）=131 072，n（CCEH）=4 096 時，索引初始大小已經超出數據集大小，即此時理論上NVM-LH 不會觸發(fā)分裂操作，而CCEH 只會觸發(fā)極少的分裂操作，此時兩種算法的NVM 寫次數都等于或者接近數據集大小，即2 000 k。但是從圖4（b）中可以發(fā)現，NVM-LH 的NVM 寫次數多出了500 k，推測應為算法在實現過程中未能成功保證所有的緩存行對齊所致。

圖4 插入操作性能Fig.4 Performance of insertion operation

3.4 空間利用率

圖5 給出了NVM-LH 和CCEH 在不同的桶/段大小下插入200 萬條數據后的空間利用率（NVM-LH 的分裂上限設置為80%）。從圖中可以看出，NVM-LH 的平均空間利用率達到了70%以上，而CCEH 的平均空間利用率在40%左右。而且，NVM-LH 的空間利用率隨著桶/段大小的增加呈現上升趨勢，而CCEH 則呈現下降趨勢。這是因為兩個算法中影響空間利用率的主要因素不同。影響NVM-LH空間利用率的主要因素是分裂過于頻繁而產生的空slot；而影響CCEH 空間利用率的主要因素是段分裂而產生的空slot。因此NVM-LH 桶容量越大，分裂的頻率就越小，產生的空slot就越少；而CCEH 的段容量越大，分裂后未使用的slot就越多。

圖5 不同桶/段大小下的空間利用率Fig.5 Space utilization under different buckets/segment sizes

3.5 結果分析

由圖4 的插入操作實驗結果可以看到，在初始條件相同的情況下，NVM-LH 和CCEH 的插入性能相差不大，且吞吐量和NVM 寫次數均符合指數增長（下降），與橫坐標的增加趨勢保持一致。而NVM-LH 在減少NVM 寫操作方面的表現更為出色，同時在空間利用率上平均比CCEH 高了30%。雖然NVM-LH的插入性能略低于CCEH，但NVM-LH的插入性能可以通過調低加載因子上限加以提升，因為這時索引需要更加頻繁的觸發(fā)分裂操作來降低自己的加載因子，從而減少了溢出桶的數量，但相對的，NVM 寫次數會有所增加。綜合而言，NVM-LH 的優(yōu)勢在于提供了一種在時間性能和空間利用率兩個方面運行用戶進行折中設計的靈活選擇，而CCEH 則無法實現這一點。

由于CCEH 采用了無溢出桶的可擴展哈希設計，因此它的理論查詢性能優(yōu)于NVM-LH。由于這是顯而易見的結果，因此本文中未對查詢性能加以對比。但NVM-LH作為線性哈希索引，其優(yōu)勢在于更高的空間利用率和更少的NVM 寫次數。

在高并發(fā)狀態(tài)下，因為NVM-LH 索引中分裂操作是以m=32 的桶為單位進行，而CCEH 中則是以m=1 024 的段為單位來進行的，而且CCEH 是只要發(fā)生沖突就會觸發(fā)分裂，因此NVM-LH 在分裂時的開銷要比CCEH 小。事實上圖4（b）中NVM-LH 的NVM 寫次數始終保持在CCEH 的85%左右，比CCEH 減少了15%左右。其主要原因在于NVM-LH 在分裂時產生的額外開銷要更小。

4 結語

本文基于傳統(tǒng)的線性哈希索引結構，提出了一種新的NVM 友好的線性哈希索引NVM-LH 并進行了實驗驗證。通過與現有的NVM 友好的動態(tài)哈希索引CCEH 進行對比，表明NVM-LH具有更好的空間利用率和NVM寫次數。

在實際的數據庫系統(tǒng)中，索引不僅要考慮查詢和更新的性能，也要考慮空間利用率，體現時間和空間代價上的綜合考量。本文提出的NVM-LH 以線性哈希索引為基礎，利用了線性哈希索引良好的空間利用率以及較好的綜合性能，為構建面向通用數據庫系統(tǒng)上的NVM感知索引提供了設計參考。

在未來工作中，如何優(yōu)化哈希索引使其能夠適應基于DRAM 和NVM 的異構混合內存［13］以及哈希連接算法［14］是值得研究的方向。此外，高并發(fā)環(huán)境下的索引一致性問題也是未來值得研究的一個重要問題［15-16］。采用鎖機制很顯然會帶來較大的代價，但無鎖化的線性哈希索引設計目前還存在難點，需要研究創(chuàng)新的方法。