Hyperion: Building the Largest In memory Search Tree

Introduction

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

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

  • 對常見的trie樹做一個調整,優化trie樹的編碼方式,從而減小對一棵trie樹編碼的開銷。

  • 為了減小由于內存分配而導致的碎片,Hyperion提出了一個量身定制的內存管理器,主要采用匿名內存映射的方式來實現內存分配。

  • 對上述的結構從編碼方式、查找性能、關鍵字預處理等方面做了一定的優化。

編碼方式

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

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

  在圖中,會發現一個問題,將連續的兩個關鍵字的前綴作為一部分,后綴作為一部份,當容器內的某些關鍵字具有相同的前綴的時候,比如上圖的th和to兩個字符串有相同的前綴"t",使得t被重復的存儲,為了避免浪費這種重復存儲所消耗的空間,在這里作者使用了如下的結構,將連續的兩個字符分為兩部分ki0ki1?,即對應著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之后就開始對結點進行編碼:

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

  在作者的系統中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)個。可以使得一個容器放入更多的關鍵字信息。

posted @ 2019-10-05 20:20 曉乎 閱讀(...) 評論(...) 編輯 收藏
福彩快三怎么样