SuRF: 一個優化的 Fast Succinct Tries
來自專欄 TiDB 的後花園
22 人贊了文章
作者：唐劉
在前一篇文章中，我簡單介紹了 Succinct Data Structure，這裡我們繼續介紹 SuRF。
Fast Succinct Tries
SuRF 的核心數據結構就是 Fast Succinct Tries（FST），一種空間節省，支持 point 和 range query 的靜態 trie。在很多時候，對於一棵樹來說，上層的 trie 節點較少，但訪問頻繁，也就是我們俗稱的 hot，而下層的節點則相對的 cold 一點。因此，SuRF 使用了兩種數據結構來分別處理 hot 和 cold 節點。在 upper 層上面使用了 LOUDS-Dedense，而在 lower 層上面使用 LOUDS-Sparse。
對於一個 trie 來說，SuRF 會將其編碼成：
LOUDS-Dense
LOUDS-Dense 對於每個 Node 都使用了三個 256 bit 大小的 bitmap。第一個 bitmap 叫做 D-labels，如果表示這個 node 是否有 label i，如果有，那麼第 i bit 位就是 1。譬如上面的例子，Dense 的 label 在 level 1 有 f，s 和 t，那麼在第 102（f），115（s） 和 116 （t）bit 位就會設置為 1。大家其實可以看到，具體哪一個 bit 位，就是 ASCII 碼的值。
第二個 bitmap 是 D-HasChild，如果一個 node 下面還有子節點，那麼就將該 label 對應的 bit 在 D-HasChild 裡面設置為 1。繼續上面的例子，f 和 t 都有子節點，而 s 沒有，所以 102 和 116 bit 都會設置為 1。
第三個 bitmap 是 D-IsPrefixKey，這個解釋其實有點繞，主要是用來表示一個 prefix 是否也是一個合法的 key。還是上面的例子，我們可以看到，f 這個 node 是有子節點的，所以它是一個 prefix，但同時，f 也是一個 key。在上圖中， SuRF 使用了 『$』 這個符號（實際對應的值是 0xFF）來表示這樣的情況。
最後一個位元組序列就是 D-Values，存儲的是固定大小的 value。Value 就是按照 每層 level 的順序存放的。
如果要進行遍歷 LOUDS-Dense，我們可以使用之前提到的 rank 和 select 操作。對於 bit 序列 bs 來說，我們用 rank1/select1(bs, pos) 來表示在 bs 上面 pos 的 rank 和 select 操作。譬如，假設 pos 是 D-Labels 上面的當前 bit pos，如果 D-HasChild[pos] = 1，那麼第一個子節點的 pos 則是 D-ChildNodePos(pos) = 256 x rank1(D-HasChild, pos)，而父節點則是 ParentNodePos(pos) = 256 x select1(D-HasChild, pos / 256)。
LOUDS-Sparse
不同於 LOUDS-Dense，LOUDS-Sparse 使用了 bytes 或者 bits 序列來編碼。第一個 bytes 序列，S-Labels，按照 level order 的方式記錄了所有 node 的 label。譬如上圖的 rst 這樣的 bytes 順序，Sparse 仍然使用了 0xFF（也就是上圖的 $ 符號）來表示一個 prefix key。因為這樣的 0xFF 只會出現在第一個子節點上面，所以是能跟實際的 0xFF label 進行區分的。
第二個 bit 序列就是 S-HasChild, 這個跟 D-HasChild 差不多，就不解釋了。
第三個 bit 序列 S-LOUDS 用來表示，如果一個 label 是第一個節點，那麼對應的 S-LOUDS 就設置為 1，否則為 0。譬如上圖第三層，r，p 和 i 都是第一個節點，那麼對應的 S-LOUDS 就設置為 1 了。
最後一個 bytes 序列是 S-Values，跟 D-Values 類似，不再解釋了。
如果要便利 Sparse，也是通過 rank 和 select 進行，譬如找到第一個子節點 S-ChildNodePos(pos) = select1(S-LOUDS, ranks(S-HasChild, pos) + 1)，而找到父節點則是 S-ParentNodePos(pos) = select1(S-HasChild, rank1(S-LOUDS, pos) - 1)。
Optimization
對於 SuRF 來說，為了提高查詢的速度，一個重要的優化手段就是提高 rank 和 select 執行的效率，在 SuRF 裡面，引入了 LookUp Table（LUT）。
而對於一個 pos 來說，它的 rank1(pos) = LUT[i / B] + popcount[i / B * B, i]，popcount 是一個 CPU 指令，用來快速的計算某一段區間的 1 的個數。假設我們現在要得到 pos 12 的 rank 值，先通過 LUT[12 / 5] = LUT[2] = 7，然後得到 range [12 / 5 * 5, 12] = [10, 12]，使用 popcount 得到 2，那麼 12 的 rank 就是 9。
對於 select 來說，也是使用的 LUT 方法，預先記錄算好的值。具體到上面，假設將採樣的周期設置為 3，那麼第三個 LUT 就保存的是 3 x 2，也就是第 6 的 1 的 pos 值，也就是 8。對於一個 pos 來說，select1(i) = LUT[i / S] + (selecting (i - i / S * S)th set bit starting from LUT[i / S] + 1) + 1。譬如，如果我們要得到 select1(8)，首先得到 LUT[8 / 3] = LUT[2] = 8，然後需要從 position LUT[8 / 3] + 1 = 9 這個位置，得到第 (8 - 8 / 3 * 3) = 2 個位置的 bit，也就是 1，所以 select1(8) 就是 10。
當然，SuRF 還有其它很多優化手段，譬如使用 SIMD 來提速 label 的查找，使用 prefetchj 技術等，這裡就不說明了。
Succinct Range Filter
對於通常的 SuRF 來說，它因為對這個 trie 都進行了編碼，所以它是完全精確的，雖然它是一種省空間的數據結構，但很多時候，我們仍然需要能保證在內存裡面存儲所有的 SuRF 數據，所以我們就需要對 SuRF 進行裁剪，不存儲所有的信息，也就是說，我們需要在查詢的 False Positive Rate（FPR）和空間上面做一個權衡。
在 SuRF 裡面，有幾種方式，Basic，Hash，Real 以及 Mixed。
為了解決 Hash range 查詢的問題，也可以使用 Real 方式，在最後面繼續保存 n bits 位的 key 數據。Real 雖然能處理 point get 和 range，但它的 FPR 其實是比 Hash 要高的。所以我們可以使用 Mixed 方式，將 Hash 和 Real 混合在一起使用。
Example
SuRF 的代碼已經開源，大家可以自己從 Github 獲取到，使用起來也非常的簡單，下面是一個非常簡單的例子：
vector<string> words = { "f", "farther", "fas" "trying"};SuRF s(words, true, 16, kNone, 0, 0);cout << "Find abc " << s.lookupKey("abc") << endl;cout << "Find trying " << s.lookupKey("trying") << endl;
上面我創建了一個 SuRF，傳入了一批 words，使用了 Full Trie 的模式，然後做了兩次點查。
具體代碼，大家可以自己去研究下，代碼質量還是很不錯的。Epilogue
SuRF 的研究就暫時到這裡結束了，對於 Succinct Data Structure，我個人還是覺得很有意思，可以探究的東西挺多的，畢竟如果能把查詢索引全放在內存，不走磁碟，性能還是非常不錯的。但我個人畢竟水平有限，僅僅限於了解，所以特別希望能跟業界的大牛多多交流。如果你也對這塊很感興趣，歡迎聯繫我 tl@pingcap.com。
推薦閱讀：