HOT: A Height Optimized Trie Index for Main-memory Database System

摘要

高效 節(jié)省空間
核心思想是每個(gè)節(jié)點(diǎn)的bits(span)動(dòng)態(tài)變化以實(shí)現(xiàn)高的fanout和好的cache效率

節(jié)點(diǎn)的設(shè)計(jì) 緊湊，用SIMD能快速查找

HOT在String關(guān)鍵字上性能和空間表現(xiàn)極好，在整型關(guān)鍵字上也很有競(jìng)爭力

介紹

在內(nèi)存數(shù)據(jù)庫中，好的Trie樹索引要比B樹索引性能好得多。但Trie樹也有問題，如ART在整型key上的fanout大，性能好，但在字符串key上，平均fanout就小得多了。這種由于數(shù)據(jù)的稀疏導(dǎo)致fanout小在Trie樹上是普遍存在的。

基于以上問題，本文中提出了HOT，完全的索引功能，好的查找性能，極小的空間消耗（尤其是string data，索引本身要比string data小很多）。

HOT最重要的特性是不論數(shù)據(jù)分布如何（稀疏/稠密）它都能達(dá)到一個(gè)很大的平均fanout。與其他Trie樹相比，HOT的span是不定的隨著數(shù)據(jù)分布而調(diào)整，而保持fanout的穩(wěn)定來避免數(shù)據(jù)稀疏的問題?！臻g消耗減少、樹的高度降低，提高了cache efficient。

另外HOT在節(jié)點(diǎn)的layout上針對(duì)現(xiàn)代CPU進(jìn)行了特殊設(shè)計(jì)。節(jié)點(diǎn)為cache efficient進(jìn)行了優(yōu)化，并支持SIMD優(yōu)化查詢。

同步用的ROWEX

項(xiàng)目

相關(guān)工作

Trie樹已經(jīng)證明了在內(nèi)存數(shù)據(jù)庫上性能更好。之前的研究都是如何降低樹的高度。下面來看一下在binary trie上進(jìn)行的優(yōu)化。

如圖，一共有13個(gè)key插入到了一個(gè)binary trie(a)中，一個(gè)簡單的優(yōu)化就是將路徑中沒有分支(區(qū)分)的節(jié)點(diǎn)進(jìn)行合并，也就是Radix Tree(b)，合并之后的樹就是一個(gè)滿二叉樹了。雖然radix大大減少了節(jié)點(diǎn)數(shù)，但是span為1時(shí)樹的高度實(shí)在是太高了，所以有了增大span，來降低樹的高度(c)。增大span帶來一個(gè)問題就是在存儲(chǔ)稀疏數(shù)據(jù)時(shí)，節(jié)點(diǎn)太空了，造成了空間的浪費(fèi)。在c的基礎(chǔ)上，把那些只有一個(gè)孩子的節(jié)點(diǎn)進(jìn)行合并到區(qū)分節(jié)點(diǎn)上（不應(yīng)該叫作合并，兩種解決方法，樂觀方法是只記錄跳過的個(gè)數(shù)，悲觀方法會(huì)記錄前綴，最后圖中叫omit。和radix tree一個(gè)意思，也是ART中的路徑壓縮path compression），這樣又省下了兩個(gè)節(jié)點(diǎn)。為了解決span大空間浪費(fèi)的問題，ART提出了adaptive node，極大的減少了空間消耗。但ART還有一個(gè)問題就是，在稀疏數(shù)據(jù)上，樹的下層節(jié)點(diǎn)fanout都很小，沒有影響到fanout和整體樹的高度。

對(duì)以上方法做一個(gè)總結(jié)，那就是他們都是把多個(gè)binary trie的節(jié)點(diǎn)結(jié)合成一個(gè)，以降低高度增加fanout。但是這些方法選取的結(jié)合標(biāo)準(zhǔn)，也就是每個(gè)節(jié)點(diǎn)的span，這與數(shù)據(jù)的存儲(chǔ)是獨(dú)立的。——這也就導(dǎo)致空間消耗與訪問性能都嚴(yán)重依賴于數(shù)據(jù)是如何存儲(chǔ)的

基于以上工作，本文提出了HOT，結(jié)合多個(gè)BiNode成一個(gè)Node，使得Node達(dá)到預(yù)先定義的fanout k來優(yōu)化最終的高度。每個(gè)節(jié)點(diǎn)調(diào)整相應(yīng)的span來表示區(qū)分的bits，忽略其他(不能用作區(qū)分key的)bits(如跳過)。

HOT

前面說要把多個(gè)BiNode節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)使其達(dá)到fanout k。最重要的優(yōu)化是增加span，但是當(dāng)前的索引span都是固定的，全局的，不管存多少key——因此性能和內(nèi)存消耗都隨著數(shù)據(jù)集而變化。
為了解決稀疏數(shù)據(jù)的問題，HOT的每個(gè)節(jié)點(diǎn)根據(jù)數(shù)據(jù)分布適應(yīng)性變化span，稠密的數(shù)據(jù)span?。ㄈ绺?jié)點(diǎn)附近），稀疏的數(shù)據(jù)span較大（低層）?！狧OT兩個(gè)特性：基于數(shù)據(jù)的span和固定的fanout k。

準(zhǔn)備： k-約束 Trie

HOT的每個(gè)節(jié)點(diǎn)都代表一個(gè)fanout最大為k的binary radix tree。一個(gè)節(jié)點(diǎn)最多存k-1個(gè)內(nèi)部節(jié)點(diǎn)BiNode和k個(gè)葉子(指針)。

有多種節(jié)點(diǎn)組合方式，k=3，3.a的劃分節(jié)點(diǎn)少，3.b的劃分高度低。

插入

與B樹類似，一般情況下只影響插入的那個(gè)節(jié)點(diǎn)，其他情況需要對(duì)樹的結(jié)構(gòu)進(jìn)行調(diào)整。

下面看例子，k=3(每個(gè)節(jié)點(diǎn)可以有3個(gè)BiNode和兩個(gè)leaf)，4.a是初始狀態(tài)

• 一般情況，4.b，插入新key0010后節(jié)點(diǎn)沒有溢出，只需要?jiǎng)?chuàng)建新的區(qū)分節(jié)點(diǎn)BiNode，只適用于entries少于k個(gè)的情況
• 葉子節(jié)點(diǎn)下推：需要?jiǎng)?chuàng)建一個(gè)新的節(jié)點(diǎn)而不是向一個(gè)已經(jīng)存在的節(jié)點(diǎn)加一個(gè)BiNode。如果mismatching的BiNode本身一個(gè)葉子并且這個(gè)Node n是中間節(jié)點(diǎn)(h(n)>1)，那么就用一個(gè)新的節(jié)點(diǎn)來取代這個(gè)leaf。這個(gè)新節(jié)點(diǎn)包含一個(gè)BiNode和兩個(gè)leaf?！从绊憳涞母叨取Ｈ鐖D4.c
• 除了上面的一般情況和leaf-node pushdown還有溢出 ，如圖4.d，對(duì)于這種情況有兩種解決辦法，用哪種取決于當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)的高度：1) parent pull up，那這節(jié)點(diǎn)的根BiNode移到父節(jié)點(diǎn)，如果父節(jié)點(diǎn)也溢出遞歸移根BiNode直到根節(jié)點(diǎn)，根節(jié)點(diǎn)溢出分裂，適用于h(n)+1 = h(n.parent)——不需要修改中間的高度；2)創(chuàng)建中間節(jié)點(diǎn)：當(dāng)前節(jié)點(diǎn)直接分裂成兩個(gè)節(jié)點(diǎn)，直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)，把root BiNode移進(jìn)去，適用于h(n)+1<h(n.parent)，意味著在中間加個(gè)節(jié)點(diǎn)不會(huì)增加樹的高度。

HOT的屬性

HOT是純Trie樹，每個(gè)節(jié)點(diǎn)都代表著key的前綴。但它和基于比較的多路結(jié)構(gòu)又比較像(進(jìn)行l(wèi)og2(n)次比較)。像B樹，HOT的每個(gè)節(jié)點(diǎn)的最大fanout是有界的，通過動(dòng)態(tài)分布數(shù)據(jù)和節(jié)點(diǎn)來減少樹的高度。另一個(gè)相似就是都只有新建一個(gè)根節(jié)點(diǎn)才增加樹的高度。
Trie有一個(gè)通用的屬性，把給定的key插入到索引中，不論插入順序，最終的結(jié)果都是一樣的。

節(jié)點(diǎn)的實(shí)現(xiàn)

k，節(jié)點(diǎn)的物理組織， 節(jié)點(diǎn)內(nèi)的操作

概覽

節(jié)點(diǎn)內(nèi)可以直接用binary radix tree，但BiNode之間的的指針會(huì)浪費(fèi)空間，效率低可能導(dǎo)致Cache miss或數(shù)據(jù)依賴。HOT需要一個(gè)節(jié)省空間的、快的、緊湊的節(jié)點(diǎn)。

The key idea behind our node layout is to linearize a k-constrained trie to a compact bit string that can be searched in parallel using SIMD instructions.

主要思想是把k-約束的trie線性化為一個(gè)緊湊的能使用SIMD并行查找的bit String。為此，把區(qū)分bits連續(xù)存儲(chǔ)。

圖5a包含7個(gè)key，區(qū)分bits位是{3,4,6,8,9}。把每個(gè)key這5個(gè)區(qū)分位組成了partial key(dense)。把Partial key連續(xù)存儲(chǔ)就能用SIMD進(jìn)行并行查找所有key了而不用再遍歷相應(yīng)的Trie。但是為了插入的簡化，事實(shí)上節(jié)點(diǎn)內(nèi)用的并不是這個(gè)dense partial key，而用的是sparse partial key，下面插入會(huì)講。

最大fanout設(shè)為32，對(duì)CPU Cache夠大，對(duì)快速更新夠小。一個(gè)node最多有31個(gè)區(qū)分bit positions（足夠區(qū)分32個(gè)key，想想最壞的情況，32bit從第0位到第32位依次為1，其余為0）。為了SIMD操作，Partial key需要對(duì)齊。在物理層面上，Partial key有三種存儲(chǔ)表示，8-bit, 16-bit和32-bit數(shù)組。對(duì)每個(gè)節(jié)點(diǎn)總選最小的。

除了partial key，每個(gè)節(jié)點(diǎn)還需要存bit positions(存哪些位能用來區(qū)分不同的key)。最簡單的方法就是存到一個(gè)數(shù)組中(圖5cI，把34689存了起來)，但是比較慢，因?yàn)樵谶M(jìn)行數(shù)據(jù)并行的key比較前需要從search key中先提取bit positions相應(yīng)的數(shù)據(jù)形成comparison key再和Partial key進(jìn)行比較。

（PEXT指令就是A通過B指定的掩碼把A中相應(yīng)的比特位傳輸?shù)紺的低比特位中）

為了加速key的提取，這里充分利用了BMI2的PEXT指令——通過位掩碼從一個(gè)integer中提取指定bit(把原始key和位掩碼作與操作)。圖5.c.II是單掩碼，在最大bit Position和最小bit position接近時(shí)可以用(小于64)，否則要用圖5.c.III，多掩碼，用多個(gè)8bit掩碼來表示，PEXT對(duì)它進(jìn)行快速的并行抽取。
PEXT介紹

到這里，node的layout有兩個(gè)需要自適應(yīng)調(diào)整的地方，第一是Partial keys，有8bit, 16bit和32bit的數(shù)組可選，選擇的依據(jù)是區(qū)分bits的個(gè)數(shù)(如需要15位bit來區(qū)分這32個(gè)key，就選擇16bit的partial keys;最好的情況是用5bit區(qū)分，選8bit partial key；最壞的情況需要31位，選32bit Partial key)；第二是單掩碼和多掩碼的區(qū)別，選擇的依據(jù)是最小bit position和最大bit position之間的距離，小于64用單掩碼，多余64用多掩碼。

物理節(jié)點(diǎn)的layout

一個(gè)節(jié)點(diǎn)包含四部分內(nèi)容，頭文件、bit positions、Partial key和value
頭文件中包含的信息有子樹的高度，描述used entries的位掩碼(這是什么)和同步版本的鎖

bit Positions部分包含offset和掩碼。offset記錄的是位掩碼開始的地址。

總是用最小的節(jié)點(diǎn)。對(duì)于一個(gè)節(jié)點(diǎn)存了n個(gè)entries，就分配n個(gè)partial keys和n個(gè)values，當(dāng)需要修改節(jié)點(diǎn)的時(shí)候用copy-on-write。value中存的是指針還是tid，用最高有效位進(jìn)行區(qū)分。

這9種節(jié)點(diǎn)的選擇總是依賴于discriminative bits的分布，從中選取最小的。一個(gè)節(jié)點(diǎn)中有n個(gè)數(shù)據(jù)就分配n個(gè)partical key和n個(gè)value，修改(插入與刪除)時(shí)用copy-on-right進(jìn)行節(jié)點(diǎn)的替換。除了節(jié)省空間外，copy-on-write可以幫助并發(fā)。

查找

查找的最后一步得到Tid取到相應(yīng)的元組后需要與search key進(jìn)行比較——這是必須的，因?yàn)樵趓adix tree上查找可能出現(xiàn)假陽性（它把中間的給刪掉了）。

節(jié)點(diǎn)的查找分成兩步：1.從search key中提取dense partial key 2.與節(jié)點(diǎn)的sparse partial key比較。

插入

考慮如果節(jié)點(diǎn)內(nèi)存的是dense partial key，那么在圖5中再插入一個(gè)新的節(jié)點(diǎn)0110101101之后，原來的bit positions就不足夠區(qū)分這7+1個(gè)key了，需要再添加一位bit position，bit position添加后那原來的dense Partial key也全部需要修改，代價(jià)非常大。
為了解決以上問題，節(jié)點(diǎn)中存的實(shí)際上是sparse Partial key。兩者的區(qū)別是稀疏Partial key是從根BiNode沿著路徑只把那些與內(nèi)部BiNode不同的區(qū)分bit設(shè)為1，其他都是0.

The difference to dense partial keys is that for sparse partial keys, only those discriminative bits are extracted that correspond to inner BiNodes along the path from the root BiNode and that all other bits are set to 0. Thus, sparse partial key bits set to 0 are intentionally left undefined. In case of a deletion this allows to remove unused discriminative bits.
(還是沒有搞懂)

一個(gè)新的key如何插入HOT節(jié)點(diǎn)中的：在bianry trie中插入前會(huì)檢查是否已經(jīng)存在，如果沒有匹配，可以確定mismatching bit。與bianry radix tree比，精確的確定mismatching bit是不可能的，因?yàn)镠OT節(jié)點(diǎn)內(nèi)已經(jīng)不是顯式的bianry radix tree了。但是可以直接確定這個(gè)mismatching的子樹（也就是HOT節(jié)點(diǎn)）中所有的leaf entries并把這些entries標(biāo)記為受影響的entries。用SIMD指令，把那些具有與search key相同前綴假陽性匹配上的的Partial key標(biāo)記為受影響(we therefore mark all partial keys that have the same prefix up to the mismatching bit position as the initially matching false positive partial key as affected. )。然后，如果這個(gè)節(jié)點(diǎn)的bit Positions不包含這個(gè)mismatching bit，所有的sparse Partial key都要用PDEP指令記錄并創(chuàng)建包含mismatching bit position的的Partial key。
（PDEP與PEXT相反，它是把A的低比特位通過掩碼B映射到C相應(yīng)的位置上）
為了直接構(gòu)建新的sparse Partial key表示，利用了它與受影響的entries共享了mismatching bit前的的公共前綴。

同步協(xié)議

ROWEX
讀不阻塞，不重啟；寫需要保證任何時(shí)候數(shù)據(jù)結(jié)構(gòu)都是合法的

修改操作（插入與刪除）分成五步：1) 遍歷的時(shí)候決定哪些節(jié)點(diǎn)需要修改，放到棧里，這些節(jié)點(diǎn)稱作受影響節(jié)點(diǎn)；2) 對(duì)受影響的節(jié)點(diǎn)自底向上加鎖以防止死鎖；3) 驗(yàn)證階段檢查有沒有受影響節(jié)點(diǎn)廢棄了，也就是在同時(shí)被刪除掉了，如果有，該操作需要restart(需要先把之前鎖住的節(jié)點(diǎn)unlock); 4)如果驗(yàn)證成功，進(jìn)行插入操作，換成新節(jié)點(diǎn)(copy-on-write)，之前的節(jié)點(diǎn)標(biāo)記廢棄；5) 自上而下unlock

最重要的是決定哪些節(jié)點(diǎn)是受影響節(jié)點(diǎn)：一般情況是 包含mismatching BiNode的節(jié)點(diǎn)以及其父節(jié)點(diǎn)；leaf node pushdown，受影響節(jié)點(diǎn)只有包含mismatching BiNode的節(jié)點(diǎn)，一旦發(fā)生溢出需要遍歷其祖先節(jié)點(diǎn)把其加入到受影響節(jié)點(diǎn)中去，直到1) parent pull up，一個(gè)節(jié)點(diǎn)有足夠的空間或者到了根節(jié)點(diǎn) 2) 創(chuàng)建中間節(jié)點(diǎn)，到一個(gè)節(jié)點(diǎn)n滿足 height(n.parent)>= height(n)。 最后在最后一個(gè)訪問的節(jié)點(diǎn)上加一個(gè)父節(jié)點(diǎn)。

刪除的時(shí)候給節(jié)點(diǎn)標(biāo)記為廢棄而不是直接刪除，兩個(gè)好處，一是廢棄標(biāo)記可以讓writer檢測(cè)受影響節(jié)點(diǎn)有沒有廢棄的，然后restart；二是reader與并發(fā)的寫之間不需要鎖，因?yàn)閷懙倪^程中要把原來的節(jié)點(diǎn)標(biāo)記為廢棄但沒有刪除，reader還是可以讀，又不耽誤寫。

回收策略是epoch-based reclaim，沒有reader和writer訪問時(shí)刪除標(biāo)記為廢棄的節(jié)點(diǎn)。