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

關(guān)鍵詞：內(nèi)存索引； 預(yù)??； 緩存； 內(nèi)存層次結(jié)構(gòu)

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

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

1 研究背景

1.1 樹型內(nèi)存索引

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

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

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

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

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

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

1.2 預(yù)取技術(shù)

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

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

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

2 問題分析

2.1 樹型內(nèi)存索引的訪存瓶頸

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

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

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

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

3.2 基于路徑的預(yù)取算法

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

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

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

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

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

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

3.3 預(yù)取表設(shè)計(jì)

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

3.4 基于鍵切片哈希的匹配算法設(shè)計(jì)

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

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

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

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

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

算法1 預(yù)取表查詢算法

輸入： 待查詢鍵request key。

輸出： 可能包含該鍵的預(yù)取表?xiàng)l目entry，和一個(gè)表示查詢鍵與該條目相關(guān)性的match值。

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

2 h=hash（KeySlice）%8192

3 entry=PT.GetEntry（h） //從預(yù)取表中獲取第h個(gè)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前綴相同，就多預(yù)取一個(gè)索引節(jié)點(diǎn)*/

9 match=match+1

10return entry， match

3.5 軟件層面的路徑預(yù)取工作流程

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

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

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

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

c）匹配值大于0，但實(shí)際訪問路徑和預(yù)取路徑完全不重合。這可能是由于索引結(jié)構(gòu)改變等原因，導(dǎo)致預(yù)取表中存儲的鍵-路徑關(guān)系過時(shí)。此時(shí)需要將該條目更新為本次訪問的鍵和它的路徑。

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

4 實(shí)驗(yàn)評估

4.1 實(shí)驗(yàn)環(huán)境和設(shè)置

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

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

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

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

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

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

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

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

首先測試了在只讀場景下的讀性能對比，實(shí)驗(yàn)結(jié)果如圖5所示。

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

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

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

4.3 YCSB測試

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

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

4.4 預(yù)取表大小對性能的影響

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

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

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

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

5 結(jié)束語

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

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

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

參考文獻(xià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.