摘 要：在樹型內存索引的研究過程中，由于傳統(tǒng)的片上預取不能適應索引的局部性，導致訪存成為該類型內存索引的性能瓶頸。提出了一種基于軟件層面的路徑預取算法，使用預取加速內存索引的訪問，并使得該算法可以快速部署到現(xiàn)實機器上。該算法基于對樹型索引訪存流程的分析，通過預取表保存鍵與索引訪問路徑的關系，通過基于鍵切片哈希的匹配算法對預取表中的數(shù)據(jù)進行匹配，顯著提高了索引性能。在當前較為先進的樹型內存索引上實現(xiàn)了該算法并進行了實驗評估，結果表明該算法在不同數(shù)據(jù)量和讀寫混合負載下提升了索引器的訪問性能。因此，基于路徑預取的算法可以有效加速樹型內存索引的訪存速度，提升索引器性能。

關鍵詞：內存索引； 預取； 緩存； 內存層次結構

中圖分類號：TP391.9 文獻標志碼：A

文章編號：1001-3695（2024）10-030-3093-07

doi：10.19734/j.issn.1001-3695.2024.02.0051

Tree-based in-memory index query optimization based on path prefetching

Lai Yirui， Li Yongkun， Xu Yinlong

（School of Computer Science & Technology， University of Science & Technology of China， Hefei 230027， China）

Abstract：In the process of researching tree-based in-memory indexes， traditional on-chip prefetching cannot adapt to the locality of index accesses， resulting in memory accesses becoming a performance bottleneck of this type of memory index. This paper proposed a path prefetching scheme at the software level to accelerate memory index accesses by prefetching， and enabled the algorithm to be quickly deployed on real machines. Based on the analysis of the tree-based indexes memory access process， this algorithm used a prefetch table to save the relationship between keys and index access paths， and matched data in the prefetch table through a matching algorithm based on key slice hashing. This paper implemented and evaluated the algorithm on current advanced tree-based memory indexes.The results indicate that it maintains stable performance improvement under different data scale and read-write-mixed workloads. Therefore， the algorithm based on path prefetching can effectively accelerate the memory access speed of tree-based in-memory index and improve index performance.

Key words：memory index; prefetch; cache; memory hierarchy

0 引言

內存索引被廣泛地使用在各種需要管理數(shù)據(jù)的場合，例如數(shù)據(jù)庫、文件系統(tǒng)、緩存系統(tǒng)等應用中。以B+樹和字典樹為代表的樹型內存索引，在提供高性能的點查詢訪問的同時，還可以支持高效的范圍查詢請求，在各個領域獲得了廣泛的研究和使用。在樹型內存索引中，中間節(jié)點和葉節(jié)點通過指針連接，形成一個樹型結構，通過從樹根到葉節(jié)點的查詢來進行訪問。由于樹型內存索引的訪存自上而下的特點，在樹結構中向下查找時會產生大量的緩存缺失，影響了索引的性能表現(xiàn)?，F(xiàn)有的預取技術［1～4］無法對內存索引的訪問提供正確的預測，或是由于采用了硬件預取方案［5］，無法部署到實際應用中，所以無法解決這一問題。本文提出了一種軟件層面實現(xiàn)的路徑預取算法，通過鍵與樹型索引訪問時的搜索路徑的關系，對索引節(jié)點進行預取，并通過高效的預取表和匹配算法設計，保證了算法在各種場景下的性能。不同于其他使用硬件預取算法的研究，該算法無須特殊硬件支持，并且可以快速地部署至各種環(huán)境中。本文在HOT索引上實現(xiàn)了該算法，實驗結果表明，該算法能提供15%～20%的讀性能提升，同時不影響寫性能。

1 研究背景

1.1 樹型內存索引

常見的內存索引通常以B+樹、字典樹和哈希索引為代表。本文重點討論以B+樹和字典樹為代表的，能夠提供范圍查詢的有序索引。這一類索引是通過多層樹型結構有序地組織數(shù)據(jù)，以提供較為高效的訪問，因此在下文中會將B+樹索引和字典樹索引統(tǒng)稱為樹型索引。

B+樹是一個經典的樹型索引。一棵m階的B+樹中，每個葉節(jié)點存儲指向數(shù)據(jù)的指針，中間節(jié)點不存儲數(shù)據(jù)，只存儲指向樹的下一層的指針。每個中間節(jié)點的孩子數(shù)量不小于m/2，同時不大于m。所有的葉節(jié)點通過一系列next指針組織成一個鏈表結構，以加快對數(shù)據(jù)的范圍查詢。相比B-樹，B+樹由于只在葉節(jié)點存儲數(shù)據(jù)，所以在同樣的樹高下可以存儲更多數(shù)據(jù)，同時中間節(jié)點的大小更小，有利于加速查詢。

字典樹，又叫trie樹、單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構。與二叉樹不同，字典樹的鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應的字符串，而根節(jié)點對應空字符串。一般情況下，不是所有的節(jié)點都有對應的值，只有葉子節(jié)點和部分內部節(jié)點所對應的鍵才有相關的值。GPT（generalized prefix tree）［6］是最早出現(xiàn)的將字典樹作為通用的數(shù)據(jù)庫的內存索引的嘗試。GPT將數(shù)據(jù)庫的主鍵通過前部添加0的方式固定到同一長度y，以支持可變長的鍵。在GPT中，每個層固定比較k個比特位的數(shù)據(jù)，最終樹上每個節(jié)點至多有2k個子節(jié)點，樹高為y/k，這個k值又被稱為span。GPT的節(jié)點大小是固定的，因此選擇較大的k會帶來較大的內存浪費，較小的k會導致樹高較大，點查詢的內存訪問次數(shù)較多，k的選擇需要在內存使用量和訪問性能之間進行平衡。

隨著研究的進一步深入，越來越多針對字典樹的優(yōu)化技術被提出，字典樹結構的內存占用和訪問性能都得到了極大的優(yōu)化。這些優(yōu)化可以大致分為通過優(yōu)化樹結構提高字典樹性能和通過壓縮節(jié)點減少字典樹的內存使用兩類。

通過優(yōu)化樹結構提高字典樹性能的工作中，較為典型的有ART［7］和HOT［8］。ART（adaptive radix tree）通過路徑壓縮和延遲擴張，消除在原始的字典樹中只包含單個子節(jié)點的節(jié)點，以減少樹高。HOT（height optimized trie）在ART的基礎上進一步降低樹高以優(yōu)化字典樹性能。HOT放棄了傳統(tǒng)字典樹的固定span值的思想，通過采用可變的span值，將每個中間節(jié)點的子節(jié)點數(shù)，即fanout值限制在確定的范圍。fanout值的限制是通過一個類似平衡樹的插入算法實現(xiàn)的，這使得所有中間節(jié)點的fanout的最小值不小于預設值的一半。HOT的樹高相比ART減少了50%，也因此獲得了相似量級的性能提升。HOT與其他B+樹以及B+樹與trie混合結構的工作（例如STX B+ tree［9］、Masstree［10］）也進行了性能上的比較，結果表明，HOT可以在讀、寫、范圍查詢方面達到優(yōu)于B+樹類型索引的性能，同時具有更低的內存占用量。同時，最新的字典樹索引研究［8，10］中已經擯棄了統(tǒng)一鍵長度的操作，而直接使用變長鍵進行數(shù)據(jù)存儲，因此在鍵長度變化較大時，字典樹相比B+樹也能更好地進行索引工作。

通過壓縮節(jié)點減少字典樹的內存使用的工作中，較為典型的有Hyperion［11］和Hybrid Indexes［12］。Hyperion通過將樹結構的指針替換為偏移量，并將部分節(jié)點于它的子節(jié)點壓縮合并，來減少內存開銷。Hybrid Indexes則是將樹分為冷熱兩部分，熱樹采用傳統(tǒng)的內存索引，而冷樹改為只讀的索引。由于冷樹只讀的特性，可以進行大量的壓縮合并工作以減少內存使用。

1.2 預取技術

在存儲層次結構中，預取是一種將數(shù)據(jù)從慢速介質提前讀取到快速介質，以加速數(shù)據(jù)訪問的技術。這一技術被廣泛地用于內存-磁盤和L3緩存-內存等不同層次之間。在本文中主要討論L3緩存-內存之間的預取。

從實現(xiàn)方式層面，預取技術可以分為軟件預取和硬件預取。軟件預取是通過系統(tǒng)提供的特定接口，由編譯器自動，或由用戶指定的方式，將特定數(shù)據(jù)從內存中預取至L3緩存。硬件預取則是由CPU片上電路實現(xiàn)，通過特定硬件和電路保存一定數(shù)量的訪問信息，并以此為依據(jù)直接進行預取。這兩種方式最大的不同在于，用戶可以自行決定軟件預取的實現(xiàn)細節(jié)，并可以將其部署在不同機器上；而硬件預取則是無法由用戶修改，且不同的CPU默認搭載的預取算法也有所不同。學術界中現(xiàn)有的預取技術［1～5］都屬于硬件預取。對這些預取算法進行的實驗評估都需要在模擬CPU運行的模擬器例如McSimA+［13］和ChampSim中進行，只有被硬件制造商實現(xiàn)后才能用于實際應用。

從依據(jù)的訪存局部性層面，常見的通用預取算法主要有以下幾種：a）基于時間相關性的預取算法［14，15］，主要是基于最近一段時間訪問的數(shù)據(jù)，來推測未來可能被訪問的數(shù)據(jù)，并將其載入快速介質中；b）基于空間相關性的預取算法，以SMS［16］和STeMS［17］為代表，它們是針對磁盤數(shù)據(jù)庫等在塊設備上工作的任務設計的預取算法，基于訪問的數(shù)據(jù)在塊中的位置，和訪問的空間相關性來推測；c）基于指針的預取算法，以Jump-pointer prefetching［18］和Pointer Cache［19］為代表，是針對鏈表等依賴指針結構設計的預取算法，通過建立指針和被指向的數(shù)據(jù)對象的相關性，或者提前記錄將鏈表中的后續(xù)數(shù)據(jù)，來預測后續(xù)的訪問地址。

2 問題分析

2.1 樹型內存索引的訪存瓶頸

點查詢是樹型索引中的核心操作，對應于索引的獲取和插入操作。其訪問特性為從根節(jié)點開始，根據(jù)提供的鍵值，在子節(jié)點中進行搜索，直至找到目標或達到葉節(jié)點。因此，一次點查詢可能涉及多次內存訪問，平均訪問次數(shù)與樹的平均高度成正比?；谶@一特性，諸如ART和HOT等研究試圖通過降低樹的平均高度來減少訪問次數(shù)，從而提高索引性能。

然而，這種訪問模式導致下一層需要訪問的節(jié)點在本層搜索完成后才能確定。此外，由于上層應用提供給索引器的負載具有不確定性，系統(tǒng)管理的L1至L3緩存對這些節(jié)點的緩存效果不佳。這導致每次索引點查詢操作中，多個內存訪問會導致多個緩存未命中（cache miss），CPU必須等待數(shù)據(jù)從內存加載到緩存后才能繼續(xù)執(zhí)行，這無疑增加了索引查詢的時間開銷。

為了驗證這一點，本文使用了一個包含2億條8 Byte鍵的數(shù)據(jù)集，對STX B+樹、Wormhole［20］和HOT樹型內存索引進行了測試。Wormhole是一種混合了B+樹、字典樹和哈希表的樹型內存索引結構。通過CPU計數(shù)器，本文統(tǒng)計了平均每次訪問所需的CPU周期數(shù)以及CPU處于停頓狀態(tài)的周期數(shù)，結果如表1所示。停頓狀態(tài)主要由CPU等待內存訪問結果引起，由分支預測錯誤引起的停頓周期數(shù)小于10%。測試結果顯示，這些內存索引在停頓狀態(tài)中浪費的CPU時間占總CPU時間的70%～80%，這與學術界的其他研究結果［21］一致，表明了訪存延遲是制約樹型內存索引的一個瓶頸。

2.2 現(xiàn)有的預取算法在索引預取時的問題

現(xiàn)有的預取算法主要基于時間相關性、空間相關性和指針相關性三類局部性。但是，這些局部性并不能正確概括索引的訪問特征，導致傳統(tǒng)的預取算法在內存索引的工作場景中性能不佳。具體分析如下：

首先，樹型內存索引的結構由內存中的節(jié)點組成，這些節(jié)點通過指針相互連接，形成一個多叉樹的結構。盡管基于B+樹和字典樹的索引在節(jié)點內部結構和孩子數(shù)量等方面有所不同，但它們都屬于這種結構。由于節(jié)點被分配到不同的內存位置，并不具備塊設備上數(shù)據(jù)位于固定偏移量的特性，所以基于空間相關性的預取算法無法有效地工作。

其次，索引的工作負載是由外部應用提供的鍵值序列，其不確定性較高。即使是確定訪問冷熱分布的負載，也不會出現(xiàn)嚴格的訪問順序，因此基于時間相關性的預取算法同樣無法有效工作。

最后，多叉樹結構可以視為由大量具有公共節(jié)點的鏈表組成的集合，這似乎為基于指針的預取算法提供了應用場景。然而，樹型索引的一個節(jié)點往往擁有數(shù)十個子節(jié)點，例如HOT的平均子節(jié)點數(shù)量為18，基于指針的預取算法對特定的指針只能給出一個后繼的預測。這意味著基于指針的預取算法只能對少量的訪問進行預測，而對大部分訪問則效果有限。

學術界的其他研究［5］也針對這些預取算法在樹型索引中的準確率和覆蓋率進行了測試?；跁r間相關性或空間相關性的預取算法的覆蓋率約為25%的同時，準確率在40%～50%，反映出它們對索引局部性的預測缺陷；而基于指針的預取算法雖然準確率超過90%，但覆蓋率低于10%，反映出它對索引中龐大路徑的預測缺陷。由于這些預取算法的固有缺陷，將其應用于索引時的性能提升小于3%。

3 算法設計

3.1 針對索引的預取算法的三個挑戰(zhàn)

第2章深入探討了內存索引所面臨的問題，即訪存瓶頸的問題?，F(xiàn)有的預取算法在處理這一問題時效果并不理想。為了顯著提升內存索引的性能，必須通過預取策略降低緩存缺失的數(shù)量，從而加速內存訪問。要實現(xiàn)該目的，需要面臨以下三個挑戰(zhàn)：

a）設計適應內存索引訪問特性的預取算法。索引的內存訪問模式并不僅僅由其自身的結構決定，還受到外部應用提供的工作負載的影響。因此，為了構建適用于索引的預取算法，需要深入研究并理解內存索引的獨特訪問模式，并根據(jù)這些模式的訪存特性進行針對性的設計。

b）優(yōu)化預取表的結構與訪問方式。預取要實現(xiàn)其預期的性能提升，前提是預取表訪問和預測算法的運行成本必須低于通過預取加速內存訪問所帶來的收益。在實際的索引訪問過程中，除了從樹根到葉節(jié)點的常規(guī)內存訪問外，還包括鍵解析、節(jié)點內部查詢以及最終驗證鍵值正確性等多個步驟。以HOT索引為例，在處理包含1億個鍵值對的數(shù)據(jù)集時，單次讀取操作的平均時間在500～700 ns。如果預取算法能夠在每次訪問中，通過將所需數(shù)據(jù)提前加載到L3緩存中，平均減少一次緩存缺失，那么每次訪問的時間節(jié)約量可達到約100 ns。這就要求在設計預取表結構和訪問方式時，必須將預取表訪問等操作的代價控制在百納秒量級內。盡管學術界已經有一些針對索引設計的預取算法［5］，但由于在控制預取表訪問成本方面的不足，這些算法在數(shù)據(jù)量增長時性能下降較快。具體來說，當處理的鍵值對數(shù)量從1百萬增長到1億時，它對B+樹索引性能的提升幅度由50%降低到了10%以下。因此，為了構建適用于索引的預取算法，本文需要設計出高效的預取表結構和訪問方式。

c）實施基于軟件的預取方案。在當前的云存儲時代，越來越多的數(shù)據(jù)庫選擇在云上存儲數(shù)據(jù)。在這種環(huán)境下，用戶很難要求云服務提供商對硬件進行深度定制和改造，以實現(xiàn)特定的硬件預取算法。這就要求所設計的預取方案應當主要基于軟件層面。在現(xiàn)有對預取領域的學術研究中，絕大多數(shù)是基于硬件預取的實現(xiàn)方案 ［1～4］，這些方案只能依托McSimA+［13］等模擬程序進行實現(xiàn)和測試，無法部署到實際機器中進行性能對比。例如Li等人［5］針對索引設計的預取算法是硬件層面的方案，通過在芯片上增加一組存儲器作為預取表，通過截獲CPU發(fā)送給L1緩存的內存訪問指令和L3緩存發(fā)送給內存的緩存缺失信號來進行預取操作。該方案也僅僅通過模擬軟件對其進行了測試，而未能將其實際部署到任何硬件中。因此，為了構建一個可推廣的內存索引預取算法，需要設計一個基于軟件的預取方案。

3.2 基于路徑的預取算法

前文詳細分析了實現(xiàn)內存索引的預取設計的幾個關鍵挑戰(zhàn)，其中最核心的一點是預取算法需要緊密貼合內存索引的訪問模式。為了更有效地提高索引的性能，需要同時提高預取的準確率和覆蓋率，從而真正實現(xiàn)預取對索引的內存訪問速度的提升。在深入研究了索引的結構和訪問特征后，本文決定采用路徑預取算法來加速內存索引的訪問。

路徑預取算法的核心思想是利用鍵和路徑之間的對應關系進行預取。具體來說，對于某個鍵，其路徑被定義為從根節(jié)點到存儲該鍵的節(jié)點所需要訪問的節(jié)點序列。例如，在圖1中，可以看到一個樹型索引中保存了從1到15的不同鍵。為了簡潔起見，圖中省略了部分節(jié)點和節(jié)點內部存儲的值信息。通過圖示，可以清晰地看到鍵1對應的路徑是從根節(jié)點開始，經過節(jié)點A、C、G共四個節(jié)點。同樣地，鍵14的路徑是從根節(jié)點開始，經過節(jié)點B、F、J共四個節(jié)點。在這種索引結構下，鍵和路徑之間可以建立一一對應的關系：每個鍵擁有一個唯一的路徑，而根據(jù)這個路徑可以準確地訪問到存儲該鍵的節(jié)點。

值得注意的是，無論是基于B+樹的索引還是基于字典樹的索引，其本質都是有序結構的樹型索引。在這種結構下，越接近的兩個鍵往往具有更相似的訪問路徑。圖1標出了鍵1、3、14對應的路徑?？梢杂^察到，鍵1和3的路徑中存在根節(jié)點、節(jié)點A、C三個相同的節(jié)點；而鍵1和14的路徑中僅存在根節(jié)點這一個相同節(jié)點。在字典樹結構中，不同的鍵是根據(jù)其前x個比特分散到不同的子節(jié)點中，對應到它們的訪問路徑上則是：具有更長相同前綴的兩個鍵，它們的路徑中相同的節(jié)點會更多。

正是基于這種規(guī)律，可以通過保存鍵與路徑的關系來進行預取操作。首先，記錄部分鍵及其對應的路徑。當新的訪問請求到來時，查詢該鍵是否已被記錄。如果是，則將其路徑預取至L3 cache中；如果不是，則在已記錄的鍵中尋找一個與當前要訪問的鍵具有最長公共前綴的鍵x，并根據(jù)兩者的相似程度選擇將鍵x的部分路徑預取到L3 cache中。

路徑預取算法通過關注樹型內存索引中鍵和路徑的對應關系，成功捕捉到了樹型索引的局部性由鍵控制的特性。這使得該算法可以獲得遠超基于時間相關性或空間相關性的預取算法的準確率。同時，基于公共前綴提供的模糊匹配能力，使得路徑預取不需要保存所有鍵-路徑的對應信息，只需保存部分信息就能對大量請求進行預測，從而獲得了遠超基于指針的預取算法的覆蓋率。

使用了軟件層面路徑預取的索引結構架構如圖2所示。在路徑預取中，需要保存鍵與路徑的對應關系，以供后續(xù)預取使用，本文稱保存這一對應關系的數(shù)據(jù)結構為預取表。為獲得更好的訪問性能，預取表被放置在內存的一塊連續(xù)區(qū)域中。在索引查詢發(fā)生時，需要在預取表中匹配一個與查詢鍵相似的鍵，該算法在下文中稱為匹配算法。本文將在3.3節(jié)和3.4節(jié)詳細介紹預取表設計和匹配算法設計。

3.3 預取表設計

預取表（prefetch table，PT）是一塊位于內存中的連續(xù)區(qū)域，用于保存鍵和路徑的對應關系。預取表的內部結構如圖3所示。預取表由若干個64 Byte的條目構成，以符合目前大多數(shù)CPU的cacheline大小，加快訪問速度，默認有8 192個條目。每個條目由鍵key slice、路徑path和標志位flags三個部分組成。將條目設計為64 Byte的目的是和緩存行對齊。key slice部分共16 Byte，保存了鍵的前16 Byte，若不足16 Byte則在后部補0。對于超過16 Byte的鍵，這些鍵往往是以字符串形式出現(xiàn)的變長鍵，對其進行壓縮的效果不佳，因此決定僅保存前16 Byte。路徑部分共40 Byte，用于存儲5個8 Byte的指針，這些指針分別指向了該鍵對應路徑中，除根節(jié)點之外的前5個節(jié)點。由于在索引中，根節(jié)點位于所有節(jié)點的共同路徑上，所以無須存儲，而又由于根節(jié)點被頻繁訪問而有極大概率位于片上緩存中，所以也無須對其進行額外的預取操作。在現(xiàn)代高性能的內存索引中，由于樹高和單次查詢的代價成正比，所以大量的工作都試圖降低樹高，以HOT索引為例，該索引在數(shù)據(jù)量為1億個鍵值對時，樹高為6。一般來說，基于B+樹的結構會擁有稍小于字典樹的樹高。因此可以認為，保存的路徑長度為5已經足夠應對大多數(shù)的情況。同時，由于路徑預取的特殊性，有大量的請求是通過對相似鍵-路徑對的部分預取進行的，所以即使對于樹高更高的索引，保存更長的路徑也不能更有效地提高性能。標志位則是用于保存部分控制信息和統(tǒng)計信息。一個預取表默認由8 192個條目組成，在這一設置下預取表的大小為0.5 MB，現(xiàn)代服務器CPU的L3緩存一般為20 MB以上，保持一個較小的預取表有助于保證預取表本身能常駐在L3緩存中而無須進行其他額外的預取工作，提高預取表的訪問性能; 同時較小的預取表也可以減少對索引和其他任務的L3緩存的搶占。

3.4 基于鍵切片哈希的匹配算法設計

匹配算法是路徑預取的核心，負責將本次要訪問的鍵與預取表中的鍵進行匹配，從而選擇合適的鍵-路徑對進行預取。理想情況下，匹配算法能夠找到與當前要訪問的鍵具有最長公共前綴的鍵。

一些常見的思路是掃描全表匹配，使用組相聯(lián)的預取表，在預取表中構建有序索引或通過鍵的哈希值進行匹配。通過分析這些設計的缺陷，并提出本文方案。對于掃描全表匹配，在面對一個擁有8 192個條目的預取表時，其計算成本過高。為了進行一個粗略的估計，本文實驗測得訪問單個預取表條目并完成匹配的相關工作需要20 ns以上。如果進行全表掃描，意味著要對比8 192個條目，這明顯超過了單次索引訪問所需的600 ns時間。學術界也有研究使用了組相聯(lián)的預取表結構［5］，該文使用了一個8路組相聯(lián)的預取表，但在組內依然需要進行完整的掃描，代價較高。該設計導致了其預取性能隨數(shù)據(jù)量提高而快速降低，第4章的實驗中驗證了這一觀點。如果在預取表上構建一個小型的樹型索引用于搜索，假設每個節(jié)點的平均子節(jié)點數(shù)量為4，那么也需要7次訪問，共140 ns的時間。這樣的代價很難通過預取來彌補。如果采用一個簡單的哈希索引，將每個鍵計算出一個1～8 192的哈希值，然后映射到對應的條目，由于哈希索引的性質，即使兩個鍵僅最后一比特不同，它們也會被映射到完全不同的條目，無法達到將當前要訪問的鍵映射到與其有相同前綴的鍵的目的。

從上述討論中可以看出，雖然全文匹配或有序索引可以更好地進行匹配，但它們的計算成本過高，很難實現(xiàn)整體性能的提升。而簡單的哈希索引雖然只需要一次預取表訪問，但無法滿足前綴匹配的要求。

因此，本文設計了一種基于哈希的匹配算法，即算法1。該算法的核心是對部分鍵進行哈希運算。在創(chuàng)建索引時，選擇一個哈希函數(shù)，將任意長度的二進制序列映射到1～8 192這一區(qū)間上。本文取鍵的前k個比特參與哈希運算，將這個參數(shù)稱為k值。在鍵-路徑對需要寫入預取表時，先取鍵的前k個比特，使用預先選定的函數(shù)進行哈希運算，將其映射到1～8 192中的一個值，然后將該鍵-路徑對存儲到該值對應的預取表條目中。在查詢預取表時，本文選擇要訪問的鍵的前k個比特，使用同一個哈希函數(shù)計算哈希值，然后讀取該值對應的預取表條目中存儲的內容，最后將該條目中的鍵與要訪問的鍵進行比較，通過兩者的相似度（即相同前綴的長度）來決定需要預取的節(jié)點數(shù)量。

通過這種算法，可以在僅進行一次預取表訪問的情況下，將要訪問的鍵映射到預取表的一個條目中。在未發(fā)生哈希碰撞的情況下，要訪問的鍵應當與條目中存儲的鍵的前k比特完全相同。這相當于通過一個O（1）的算法找到了一個與要訪問的鍵至少有前k比特共同前綴的鍵。顯然，k值的選擇會對該算法的效果產生顯著的影響。在本文的測試中，當鍵是隨機產生的均勻分布64 bit整數(shù)時，k值取16可以得到最佳的預取效果。

算法1 預取表查詢算法

輸入： 待查詢鍵request key。

輸出： 可能包含該鍵的預取表條目entry，和一個表示查詢鍵與該條目相關性的match值。

1 初始化KeySlice=request key［0…k］

2 h=hash（KeySlice）%8192

3 entry=PT.GetEntry（h） //從預取表中獲取第h個entry

4 CompareKey=entry.Key

5 match=0

6 for i=1 to 5 do //開始匹配request key與entry.Key的前綴

7 if i*k/2<request key.size

8 if CompareKey［（i-1）*k/2…i*k/2］==request key［（i-1）*k/2…i*k/2］ /*每有一段長度為k/2的key前綴相同，就多預取一個索引節(jié)點*/

9 match=match+1

10return entry， match

3.5 軟件層面的路徑預取工作流程

預取算法主要在索引讀請求時工作，其工作流程見圖4。當索引接收到新的讀請求時，首要是對預取表進行查詢。查詢方法如3.4節(jié)所述，基于鍵的前綴進行哈希運算。查詢預取表后，將本次要訪問的鍵與表中的鍵進行比較，通過比對相同前綴的長度，得出一個0～5的匹配值，即算法1中的match值。該值表示預取表中對應鍵所對應的路徑中需要預取的節(jié)點數(shù)量。若匹配值為0，則表示完全不進行預取，可能原因是哈希碰撞導致的完全不匹配或預取表中無相關數(shù)據(jù)。在確定需要預取的節(jié)點數(shù)量后，調用編譯器提供的預取接口，將預取表中存儲的路徑上的節(jié)點預取至L3緩存。隨后，從根節(jié)點開始，發(fā)起一次索引查找過程，逐級向下查找數(shù)據(jù)。在此過程中，部分節(jié)點可能已被緩存在L3緩存中，從而減少了訪問時間。此外，還會記錄本次查找中實際訪問的索引節(jié)點的地址。查詢結束后，根據(jù)實際訪問情況，需要對預取表進行更新。

更新情況主要有以下幾種：

a）通過哈希查找到的條目中無數(shù)據(jù)，此時需要將本次訪問的鍵-路徑關系插入到預取表中，通過哈希運算確定條目位置后寫入數(shù)據(jù)。

b）匹配值為0，表示本次訪問的鍵與預取表中對應條目的鍵發(fā)生哈希碰撞。需要在預取表對應條目的標記位中記錄這種情況的發(fā)生次數(shù)，當次數(shù)達到閾值時，將該條目更新為本次訪問的鍵和它的路徑。

c）匹配值大于0，但實際訪問路徑和預取路徑完全不重合。這可能是由于索引結構改變等原因，導致預取表中存儲的鍵-路徑關系過時。此時需要將該條目更新為本次訪問的鍵和它的路徑。

路徑預取設計的主要目的是提升索引的讀性能。但在索引寫入時，查找插入位置的過程同樣可被預取加速。因此，本文在此預留了一個可開啟的預取選項。不過，在索引載入數(shù)據(jù)時，由于從零開始構建索引會導致索引節(jié)點的頻繁分裂、移動等操作，使得大量的預取條目失效，在索引載入數(shù)據(jù)時該選項默認關閉。

4 實驗評估

4.1 實驗環(huán)境和設置

本文選擇了學術界較為先進的HOT索引，以此為基礎來實現(xiàn)路徑預取算法，并將這一實現(xiàn)稱為HOT-with-PF。在單機的環(huán)境下，由于內存大小的限制，HOT索引管理的數(shù)據(jù)量通常在1 G個鍵值對以內，在該情況下的HOT樹高為6～7，而根節(jié)點由于被頻繁訪問，無須預取。因此在實踐中本文選擇了在預取表的條目中存儲長度為5的路徑。對于預取表條目數(shù)量的選擇，默認的8 192個會帶來較優(yōu)的性能，具體原因將在4.4節(jié)中討論。在k值的選擇上，對64 bit整數(shù)鍵的情況進行了分析，發(fā)現(xiàn)k值取16能獲取最好的性能。

學術界中最新的預取算法大多為硬件預取，對它們的性能評估通常使用模擬器模擬CPU的環(huán)境，運行特定的操作記錄來進行，無法與實際機器中的性能直接對比。作為對照，本文選擇了同樣針對索引設計的針對索引的硬件預取技術［5］，并將其算法實現(xiàn)在軟件層面，將這一實現(xiàn)稱為HOT-HD。本文實現(xiàn)了該算法的8路組相聯(lián)預取表和匹配算法，具體參數(shù)選擇與其論文中的默認設置相同。

本次測試的CPU配置為Intel Xeon Gold 5218R CPU @ 2.10 GHz 2×20 core，2×6通道96 GB內存；操作系統(tǒng)配置為Ubuntu 20.04，內核版本為Linux 5.4.72。涉及測試的索引分別為：

a）HOT［8］。一個基于字典樹的高性能內存索引，通過優(yōu)化的插入算法使得樹高降低，從而提高訪問性能。

b）HOT-HD。在HOT基礎上，在軟件層面實現(xiàn)已有工作［5］的預取算法，進行軟件層面預取的索引。

c）HOT-with-PF。在HOT基礎上實現(xiàn)的，增加了軟件層面路徑預取功能的索引。

測試中使用的鍵值對為8 Byte鍵+8 Byte值的組合，其中鍵為隨機生成的不重復的uint64整數(shù)。使用這一設置的原因是，分析了各種系統(tǒng)中索引的角色后發(fā)現(xiàn)，大多數(shù)情況下索引保存的是哈希值+指針的鍵值對，而非原始的鍵+值，這是由于初始的鍵-值往往是不定長的數(shù)據(jù)，存儲鍵-指針是一個更常用的方案。在測試過程中，將每個索引器分配在固定的CPU核心上，避免進程被調度至不同核心帶來的性能誤差。

4.2 路徑預取的性能表現(xiàn)

首先測試了在只讀場景下的讀性能對比，實驗結果如圖5所示。

從圖5可以看出，HOT-with-PF在不同數(shù)據(jù)量下相比HOT有10%～20%的讀性能提升，數(shù)據(jù)量越大，提升效果越高。而HOT-HD由于使用的匹配算法較為低效，在數(shù)據(jù)量較小時能獲得與HOT-with-PF類似的性能提升，但在數(shù)據(jù)量較高時性能劣于HOT本身。同時，如表2所示，在不同的數(shù)據(jù)量上，本文保證了預取表訪問的平均代價始終處在30 ns左右的一個水平，這表明本文設計的高性能的預取表結構達成了目的。

本文同樣測試了在讀寫混合場景下，預取算法的表現(xiàn)。測試方式為：先向空索引中載入1億條數(shù)據(jù)，數(shù)據(jù)來自集合S1。再在該索引中進行1億次讀請求（讀取S1中的數(shù)據(jù)）和一定次數(shù)的寫請求（寫入集合S2，與S1無交集），讀寫請求交替進行。統(tǒng)計了該種工作條件下，索引的讀取時延。在當前條件下，寫請求并不會增加額外的樹高，整體樹高始終為6，不會由于數(shù)據(jù)量增加影響讀操作性能。測試結果如圖6所示。

從圖6可以看出，讀寫混合的負載對HOT-with-PF的讀性能不會產生影響。分析了預取算法的數(shù)據(jù)后，本文發(fā)現(xiàn)原因在于使用“存儲部分key對應的路徑”這一方法的前提下，能正確預取的最長路徑平均長度在4左右。這導致預取實際上只能加速從樹根開始的4層節(jié)點的訪問; 而更向下的訪問既無法被加速，對它們的修改也不會影響預取的性能。在讀寫混合情況下，每次寫入只會修改被寫入的葉節(jié)點，平均每20次寫入才會修改一個中間節(jié)點，因此讀寫混合負載對HOT-with-PF的讀取性能幾乎不產生影響。

4.3 YCSB測試

YCSB基準測試是數(shù)據(jù)庫領域常用的基準測試工具，最初由Yahoo公司的實際負載產生，被學術界和工業(yè)界廣泛使用。本文測試了上文提及的三種索引在YCSB數(shù)據(jù)集測試中的性能。YCSB測試的參數(shù)為： 5億個鍵值對，值的平均長度為20 Byte，整體數(shù)據(jù)量為10 GB，進行的操作數(shù)量為1億次。由于本文聚焦于索引的點查詢性能優(yōu)化，同時未對索引的寫、范圍查詢流程進行改動，所以本文并未測試著重于更新的Workload D和著重于范圍查詢的Workload E。使用的工作負載為以下幾個：a）workload A：50%讀，50%寫;b）workload B：95%讀，5%寫;c）workload C：100%讀。

實驗結果如圖7所示。從圖中可以看出，HOT-with-PF通過在索引性能上的提高，使得其整體吞吐量相比其他兩種索引更高。HOT-HD受限于其在大數(shù)據(jù)量下的性能問題，吞吐量遜于HOT本身。同時，由于在YCSB這一模擬實際數(shù)據(jù)庫的測試中，存在值讀取、值驗證等索引之外的數(shù)據(jù)庫操作開銷，導致HOT-with-PF的性能優(yōu)勢相比純索引測試略有降低。

4.4 預取表大小對性能的影響

本節(jié)測試主要探討預取表條目數(shù)量，下文稱PT entry number對性能的影響。在當前設計下，該值與預取表的整體大小成正相關關系。因此，本組實驗的目的是討論預取表大小對預取性能的影響，并佐證本文設計的合理性。在本組實驗中，本文向HOT-with-PF中載入1億個KV對后，進行1億次的索引讀訪問，訪問數(shù)據(jù)均勻分布在整個數(shù)據(jù)集上，并統(tǒng)計了使用不同數(shù)量PT entry number時，讀性能和與預取相關的各項參數(shù)。結果如圖8、9所示。

讀操作可以分為進行預取表查找和預取的search PT階段、在樹結構進行搜索的讀取段和讀取后更新預取表的update PT段，其中search PT和update PT兩段時間直接與預取表相關，而讀取段的運行時間與樹高、cache miss等多方面因素相關。圖7結果表示search PT和update PT兩段時間與預取表條目數(shù)量參數(shù)的關系。由圖8可知，越大的預取表條目數(shù)量，在訪問時的時間開銷越高; 同時預取表條目數(shù)量越大，發(fā)生哈希沖突的幾率也在降低，帶來的預取表更新次數(shù)減少，導致平均更新時間減少。兩者共同影響下，預取表條目數(shù)量越小，預取表帶來的額外開銷也越小。

預取覆蓋率coverage的定義為：預取表能給出預測的請求占所有讀請求的比例。從圖8、9可以發(fā)現(xiàn)，雖然越小的預取表，額外開銷越低，但覆蓋率也會降低，從而帶來的加速效果會降低。因此預取表的大小并非越小越好，而是需要在預取表開銷和預取效果中進行取舍。

本文也測量了不同條目數(shù)量下，索引器的整體吞吐量。從圖10可以發(fā)現(xiàn)，預取表條目數(shù)量為8 192時，索引器性能最優(yōu)，是因為該值可以兼顧預取效果和預取表開銷。因此，本文的默認設置中，將預取表大小設置為了8 192個條目，共0.5 MB，這是一個兼顧了預取表訪問性能和預取覆蓋率的選擇。

5 結束語

本文對當前主流的樹型內存索引進行了深入研究，發(fā)現(xiàn)其普遍存在的訪存瓶頸。為了解決這一問題，本文提出了一種基于軟件層面路徑預取的優(yōu)化方案，旨在通過正確地預測來提升索引性能。本文核心在于利用高效的預取表結構和匹配算法，實現(xiàn)對鍵與路徑關系的準確記錄與快速查詢。實驗結果表明，該方案在不同數(shù)據(jù)量和讀寫混合負載下均表現(xiàn)出良好的性能提升效果。

盡管本文預取算法在許多方面都取得了優(yōu)化，但仍存在一些局限性。在變長字符串鍵的工作負載下，面臨的挑戰(zhàn)是準確率的下降。由于字符串鍵的長度可變，數(shù)據(jù)的分布變得難以預測，導致使用固定k個比特計算哈希的方法將許多鍵映射到同一位置。為了解決這一問題，未來的研究方向是記錄和分析工作負載，支持動態(tài)調整各種參數(shù)，包括k值和預取表大小，以適應不同的工作負載。

綜上所述，本文路徑預取方案在樹型內存索引的性能優(yōu)化方面取得了顯著成果。然而，針對變長字符串鍵的工作負載，仍需進一步研究以實現(xiàn)更準確的哈希匹配算法。未來研究將致力于改進預取算法以適應不同數(shù)據(jù)分布的工作負載，并優(yōu)化參數(shù)調整機制，以提高索引性能的穩(wěn)定性和適應性。

參考文獻：

［1］Jiang Shizhi， Yang， Qiusong， Ci Yiwei. Merging similar patterns for hardware prefetching［C］//Proc of the 55th IEEE/ACM International Symposium on Microarchitecture. Piscataway， NJ： IEEE Press， 2022： 1012-1026.

［2］Navarro-Torres A， Panda B， Alastruey-Benedé J， et al. Berti： an accurate local-delta data prefetcher［C］//Proc of the 55th IEEE/ACM International Symposium on Microarchitecture. Piscataway， NJ： IEEE Press， 2022： 975-991.

［3］Bakhshalipour M， Shakerinava M， Lotfi-Kamran P， et al. Bingo spatial data prefetcher［C］//Proc of IEEE International Symposium on High Performance Computer Architecture. Piscataway， NJ： IEEE Press， 2019： 399-411.

［4］Vavouliotis G， Chacon G， Alvarez L， et al. Page size aware cache prefetching［C］//Proc of the 55th IEEE/ACM International Sympo-sium on Microarchitecture. Piscataway， NJ： IEEE Press， 2022： 956-974.

［5］Li Shuo， Chen Zhiguang， Xiao Nong， et al. Path prefetching： acce-lerating index searches for in-memory databases［C］//Proc of the 36th IEEE International Conference on Computer Design. Piscataway， NJ： IEEE Press， 2018： 274-277.

［6］Boehm M， Schlegel B， Volk P B， et al. Efficient in-memory indexing with generalized prefix trees［C］//Proc of the 14th BTW Conference on Database Systems for Business， Technology， and Web. 2011： 227-246.

［7］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.

［8］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.

［9］Kallman R， Kimura H， Natkins J， et al. H-store： a high-performance， distributed main memory transaction processing system［J］. Proceedings of the VLDB Endowment， 2008，1（2）： 1496-1499.

［10］Mao Yandong， Kohler E， Morris R T. Cache craftiness for fast multicore key-value storage［C］//Proc of the 7th ACM European Confe-rence on Computer Systems. New York： ACM Press， 2012： 183-196.

［11］Msker M， Sü T， Nagel L， et al. Hyperion： building the largest in-memory search tree［C］//Proc of International Conference on Ma-nagement of Data. New York： ACM Press， 2019： 1207-1222.

［12］Zhang Huanchen， Andersen D G， Pavlo A， et al. Reducing the sto-rage overhead of main-memory OLTP databases with hybrid indexes［C］//Proc of International Conference on Management of Data. New York： ACM Press， 2016： 1567-1581.

［13］Ahn J H， Li Sheng， Seongil O， et al. McSimA+： a manycore simulator with application-level+simulation and detailed microarchitecture modeling［C］//Proc of IEEE International Symposium on Performance Analysis of Systems and Software. Piscataway， NJ： IEEE Press， 2013： 74-85.

［14］

Wenisch T F， Somogyi S， Hardavellas N， et al. Temporal streaming of shared memory［C］//Proc of the 32nd International Symposium on Computer Architecture. Piscataway， NJ： IEEE Press， 2005： 222-233.

［15］Jain A， Lin C. Linearizing irregular memory accesses for improved correlated prefetching［C］//Proc of the 46th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway， NJ： IEEE Press， 2013： 247-259.

［16］Somogyi S， Wenisch T F， Ailamaki A， et al. Spatial memory strea-ming［J］. ACM SIGARCH Computer Architecture News， 2006， 34（2）： 252-263.

［17］Somogyi S， Wenisch T F， Ailamaki A， et al. Spatio-temporal memory streaming［J］. ACM SIGARCH Computer Architecture News， 2009， 37（3）： 69-80.

［18］Roth A， Sohi G S. Effective jump-pointer prefetching for linked data structures［C］//Proc of the 26th Annual International Symposium on Computer Architecture. Piscataway， NJ： IEEE Press， 1999： 111-121.

［19］Collins J， Sair S， Calder B， et al. Pointer cache assisted prefetching［C］//Proc of the 35th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway， NJ： IEEE Press， 2002： 62-73.

［20］Wu Xingbo， Ni Fan， Jiang Song. Wormhole： a fast ordered index for in-memory data management［C］//Proc of the 14th EuroSys Confe-rence. New York： ACM Press， 2019： 1-16.

［21］Zeitak A， Morrison A. Cuckoo trie： exploiting memory-level paralle-lism for efficient DRAM indexing［C］//Proc of the 28th Symposium on Operating Systems Principles. New York： ACM Press， 2021： 147-162.