Hyperion: Building the Largest In memory Search Tree

2019 年 10 月 5 日
筆記

Introduction

　　索引在數據管理中起到很重要的作用，很多索引結構都會採用訪問速度快而且記憶體消耗少的trie樹，但一般常見的trie樹索引結構都強調效率而忽視記憶體的效率，他們的效率雖然高，但記憶體的消耗比較大。這篇文章提出了一種新的樹形結構—-Hyperion，在效率上做到對範圍查詢和點查詢都能夠有比較好支援的同時，也實現了記憶體效率使用的極大提升。

整篇論文大體上可以分層三個結構：

對常見的trie樹做一個調整，優化trie樹的編碼方式，從而減小對一棵trie樹編碼的開銷。
為了減小由於記憶體分配而導致的碎片，Hyperion提出了一個量身訂製的記憶體管理器，主要採用匿名記憶體映射的方式來實現記憶體分配。
對上述的結構從編碼方式、查找性能、關鍵字預處理等方面做了一定的優化。

編碼方式

　　我們通常用到的trie樹結構如下圖，但是這棵trie樹有點問題，就是樹的高度太高，不易於搜索，同時，每一個節點就存儲一個關鍵字，同時節點內還會包含節點的孩子指針等元素據資訊，導致一個節點存儲一個關鍵字的效率比較低。在這裡作者提出了容器的概念，容器可以存儲字元串中連續的兩個關鍵字，也就是16bit，且容器中可以有多個這樣的16位的關鍵字序列，最多可以有65536個16bit的關鍵字序列。容器對應著圖中用實現標出的框C1、C2以及C3。

更進一步可以表示成下圖所示，上圖的容器全部表現成下面的形式，在容器內，連續的兩個字元組成容器內的一個節點，如果末端只有一個，則用一個表示：

　　在圖中，會發現一個問題，將連續的兩個關鍵字的前綴作為一部分，後綴作為一部份，當容器內的某些關鍵字具有相同的前綴的時候，比如上圖的th和to兩個字元串有相同的前綴”t”，使得t被重複的存儲，為了避免浪費這種重複存儲所消耗的空間，在這裡作者使用了如下的結構，將連續的兩個字元分為兩部分k_i⁰k_i¹ $ ，即對應著T-Node()和S-Node()，其中T-Node是連續兩個字元的第一個字元，比如上圖的a，b，t；而S-Node則是以第一個字元為前綴的後綴集合，還是以th和to為例，它們的前綴是t(T-Node)，則S-Node是h和o，示例如下：$

下面開始對這個容器就行的編碼，首先對容器內的T-Node和S-Node進行編碼，兩種Node的編碼格式如下：

　　第一個標誌位表示類型，佔兩個比特大小，10和11表示葉子節點（是否帶值，對於這個標記還有疑問，但對文章影響不大），00表示指向無效的記憶體位置比如標誌記憶體碎片等等（相當於網路傳輸包的EOF標誌），其他節點都是內部節點，用01表示。標記位k表示節點是T-Node(0)還是S-Node(1)類型，C表示容器與容器之間的關係，下一段介紹，例如下面這兩種情況對他們的編碼如圖所示。

　　容器與容器的關係可以分為四種，佔兩個比特，用S-Node的c去表示，c=00時，表示容器已經到達最低端，下面再也沒有其它容器了；c=11時，表示會採用一種壓縮路徑的方法去處理下一個容器，當trie樹結構如下圖所示時，就會採用。

c等於01的時候，表示正常的引用子容器的地址，其中子容器的地址大小是5個位元組，為什麼是5個位元組具體在後面的記憶體管理器介紹。C=10 的時候，表示大容器裡面嵌入了一些小容器，這個小容器就直接連在了S-Node的後面，兩種情況的編碼方式具體如下圖。

container與container的嵌入關係還可以這樣表示更複雜的形式如下：

　　最後再介紹一下container的整個結構，Container頭部包含Size（已經分配的記憶體大小），Free（剩餘的記憶體大小），J（容器跳錶標誌位，後面介紹），S（延遲位，作為一個容器分裂的參數），而payload則存放的是跳錶資訊，在payload之後就開始對結點進行編碼：

　　當一個容器中嵌入的容器數目過多，導致容器的存儲容量過大的時候，就會進行分裂，分裂的條件如下:

<img style="display: block; margin-left: auto; margin-right: auto;" src="https://img2018.cnblogs.com/blog/1047362/201910/1047362-20191005201617566-1319473842.png" alt="" />

　　在作者的系統中a=16Kib，b=64Kib，其中延遲參數s在container中可以設置，因為s在container的編碼中只佔兩位，所以值只在0-3內。一旦開始分裂，分裂的過程以下圖為例，首先會為這個容器申請一塊新的記憶體，同時初始化容器的頭部參數，然後調用memory_copy函數，將容器的payload複製到新的容器中，將頭部參數的值更新，之前那部分空間被釋放後，就需要將後面的內容往前移，同時將容器尾部空間的那一塊記憶體初始化。

記憶體管理

　　介紹了容器與節點這種緊湊的編碼方式之後，文章為Hyperion設計了一個記憶體管理器，因為不斷的使用堆去分配記憶體會造成外部碎片。在Hyperion的記憶體管理器中，為了避免這些記憶體碎片，於是主要使用匿名記憶體映射的方式去申請記憶體，採用這種方式申請記憶體的時候會返回一個與頁對其的記憶體塊。在申請記憶體大小小於2016個位元組的時候，採用剛剛說過匿名記憶體映射的方法，大於2016個位元組的時候，還是採用堆分配的方式去申請記憶體，因為通過堆申請記憶體比較快，記憶體管理器採用分層結構去定位已事先分配好的記憶體塊，如下圖：

　　記憶體管理器的最上層有64個superbin，每一個superbin下面的chunk大小不一樣，從superbin1到superbin63依次按32個位元組的大小遞增，其中superbin1的每一個chunk大小是32byte。而SB0的chunk是大於2016byte的（即剛剛說的採用對分配的方式去分配，因為對分配的方式比較快，而且對於大塊記憶體不易產生外部碎片）。每一個superbin中有2的14次方個metabin，而每個metabin有256個bins，每一個bins則有2的12次方4096個chunk。通過這個記憶體管理器，定位一塊記憶體空間只需要5個位元組的大小。

使用這個記憶體分配器後，不僅可以減少記憶體中外部碎片的數量，還可以減少一些記憶體開銷，比如通常在一台64位的機器上，指向某一塊記憶體的指針大小通常是8位元組，在這裡只需要5個位元組。第二個就是使用堆分配記憶體的時候，還要額外的花費8位元組去存儲這個堆的元素據資訊。最後就是在這個記憶體管理器的每一層，都會維護一個數組去標記還有空chunk的superbin/metabin/bins，這樣可以快速的去定位空的記憶體塊，從而去申請記憶體。

這裡要注意的是SB0，它處理的是申請的記憶體大於2016byte的請求，它下面的bin被稱為Extended Bin，與普通的bin不同，它是包含了一個普通指針（8位元組）和其他欄位的bin（共16位元組），它分配的chunk大小也是隨著請求的不同，記憶體塊大小的遞增速度申請也不同。Chained Extended Bins (CEB)是SB0中連續的8個記憶體塊，通過一個chained point去引用，並且這八個記憶體塊統一由它管理，這樣就避免了在容器分裂的時候不用在trie樹中再把這些分裂的指針添加進節點裡去，避免一些繁雜的記憶體移動操作和一些更新開銷。

性能和記憶體優化

　　為了提升性能和減少記憶體空間，作者又幾種方法去優化。

Delta Encoding(d)

　　同一層的節點之間按升序排列，可以對他們進行增量編碼，就比如這兩個圖，超過了3bits的表示範圍，無法做Delta Encoding。此時將標值d全部置為0，將增量寫道原先存值的位置。

2.Jump Successor (js)

　　第二個優化是在T-Node中維護了一個Jump Successor，用來從一個T-Node直接跳到下一個T-Node，而不需要遍歷該T-Node下的S-Node，從而才能找到下一個T-Node的位置。若T-Node的js標記1說明使用了Jump Successor，此時該T-Node後面有一個16bits的reference，存儲下一個T-Node距離該T-Node的距離。

3. Jump Tables

　　JumpTable有兩類，第一類是在T-Node中的T-Node jump table，第二類則是在容器內的Container Jump Table。

T-Node jump table

　　如果T-Node的jt位設置為1，表明T-Node啟用了jump table這個表。T-Node jump table是一個長度是15的數組，（數組的每個元素佔用2B。）它將S-Node所有可能的範圍【0-255】等分成16份，記錄每一位置相對T-Node的偏移量，從而可以快速的從T-node到S-Node的訪問。

Container Jump Table

　　這裡的Container Jump Table是為了在容器中快速定位T-Node，J佔了3bits，最大表示7，每一個表示7個Entries，因此最多表示49個Entries。每個Entry佔用4B，1B存儲T-Node的Key，3B的Offset用來定位T-Node的位置，可以直接利用這個表定位到最接近目標T-Node的位置.

如圖，這裡的J設置為2，則表示有2*7=14個，就會將容器中所有的T-Node等分14分，然後在數組中記錄每一份的關鍵字以及它的偏移量。

Key Pre-processing

　　這是一個可選項，關鍵字預處理函數的作用就是為了將關鍵字通過一定的函數轉換後得到的值更加符合我們所期望的分布，比如一些原來很分散的數據，通過一些函數處理後，可以讓這些數據的分布變得緊密。通常，關鍵字的預處理函數是一個單射函數。對於範圍查詢來說，還要求經過單射函數得到的值也要滿足原先關鍵字所遵守的順序。在Hyperion中，作者使用的方法是在第二，第三，第四個byte中插入兩個0，這樣就會使得容器的數量由2（16）2（16）=2（32）個容器減少到2（14）2（12）=2（26）個。可以使得一個容器放入更多的關鍵字資訊。