Succinct Data Structure

來自專欄 TiDB 的後花園

作者：唐劉

最近看了一篇論文 SuRF: Practical Range Query Filtering with Fast Succinct Tries，裡面提到使用一種新的數據結構 Succinct Range Filter(SuRF) 替換掉了 RocksDB 默認的 Bloom filter， 在一些性能測試上面，尤其是 seek 上面，性能提升了不少，並且也降低了很多 I/O 開銷，這一下子就引起了我的興趣。

大家都知道，RocksDB 裡面，為了加速 key 查詢的速度，使用了 Bloom filter，但 Bloom filter 只適用於 point get，對於 seek 就無能為力了。雖然 RocksDB 後面引入了 prefix seek，但對於 key 的格式有要求，使用比較受限。為了提高 RocksDB range query 的速度，論文的作者引入了一種省空間的數據結構，也就是 SuRF。

在了解 SuRF 之前，首先要了解掌握的就是 Succinct data structure 相關的知識，這篇文章主要是講 Succinct data structure 相關的東西，後面再討論 SuRF 如何實現的。

Rank 和 Select

Succinct data structure 第一次提出，應該是 Guy Jacobson 的論文 "Succinct static data structures"，但實話，我在網上找了半天，都沒找到這篇 paper，只是找到了作者另一篇 Space-efficient static trees and graphs。它的主要思想就是使用非常少量的空間（接近信息編碼的下界）來存儲數據。你可以認為就是使用了一種非常高效的壓縮演算法，但不同於壓縮，它同時來提供非常高效的查詢。

對於 Succinct data structure 來說，我們會將數據按 0 和 1 來編碼，所以可以用 bits，而不是 bytes。操作 succinct 數據，通常的就是幾個操作函數：

• rank1(x) - 返回在 range [0, x] 裡面 1 的個數
• select1(y) - 返回第 y 個 1 所在的位置

上面我們只是列舉了 rank1 和 select1，對應的也有 rank0 和 select0，這裡就不需要解釋了。這麼說有點過於抽象，這裡舉一個簡單的例子。假設我們有一個 bits 序列 11000001，那麼 rank1 和 select1 可以映射如下：

另外，大家可以注意到，rank 和 select 其實是相反的，上面的例子，select1(3) = 7，然後我們也會發現，rank1(7) = 3。

Level Order Unary Degree Sequence

上面簡單介紹了下 Succinct data structure 的 rank 和 select。 在 SuRF 裡面，它參考的基礎編碼方式，是 Level order unary degree sequence(LOUDS)，在 LOUDS 裡面，我們會將一顆樹，分層依次進行編碼。而規則也是非常的簡單，如果這個樹的節點有 N 個子節點，那麼就用 N 個 1 來編碼，然後最後加上 0。

假設我們有如下的 tree：

為了計算簡單，LOUDS 會加入一個 pseudo root 節點，這裡我們變成如下的 tree：

然後我們對這個 tree 進行編碼，得到：

那麼生成的 bits 序列為：

那麼我們拿到了這一個序列到底有什麼用呢？在 LOUDS 裡面，我們可以非常方便的進行很多操作，假設我們的 node 就是按照上面的，0，1，2，這樣的 number 來標記的，position 對應的就是 bits 裡面的 position。我們通常會用兩個計算公式來得到 node number 和 position 的對應關係：

• node-num = rank1(i)：在 position i 得到對應的 node number，譬如 rank1(2) = 2
• i = select1(node-num)，根據 node number，知道對應的 position，譬如 select1(2) = 2

有了上面的公式，我們就能對這個 tree 進行操作了：

• first_child(i) = select0(rank1(i)) + 1 - 得到第 i 個位置所在節點的第一個子節點所在的 position
• last_child(i) = select0(rank1(i) + 1) - 1 - 得到第 i 個位置所在節點的最後一個子節點所在的 position
• parent(i) = select1(rank0(i)) - 得到第 i 個位置所在節點的父節點所在的 position
• children(i) = last_child(i) - first_child(i) + 1 - 得到第 i 個位置所在節點的子節點的個數
• child(i, num) = first_child(i) + num 得到第 i 個位置所在節點的第 num 個子節點所在的 position，num >= 0

上面這些公式感覺好繞，那麼我們來一個簡單的例子，以節點 4 為例。從上面的 tree 可以知道，4 的 parent node 是 1，它的第一個子節點是 7，最後一個是 8，總共有兩個子節點。

首先我們需要計算節點 4 的位置，根據上面的公式 select1(4) 我們得到 position 是 4。那麼第一個子節點位置就是 first_child(4) = select0(rank1(4)) + 1 = select0(4) + 1 = 9 + 1 = 10，那麼第一個子節點就是 rank1(10) = 7。

我們再來計算最後一個子節點，根據公式，最後一個就是 last_child(4) = select0(rank1(4) + 1) - 1 = select0(4 + 1) - 1 = 12 - 1 = 11，那麼最後一個子節點就是 rank1(11) = 8。

再來看看父節點，就是 parent(4) = select1(rank0(4)) = select1(1) = 0，那麼父節點就是 rank1(0) = 1。

Epilogue

使用 LODUS，我們可以用 bits 方便的編碼一棵樹，然後用 rank 和 select 操作，就能方便的對 tree 進行遍歷，業內已經有很多 paper，能將 rank 和 select 做到 O(1) 的開銷，所以速度還是很快的。

但在實際中，如果光用 LODUS，性能還是沒法保證的，所以這也是為啥會有 SuRF 的原因，關於 SuRF，後面會在說明。

在資料庫領域，Succinct 是一個比較有趣的研究方向，也有很多資料庫採用了 succinct 來保存數據，畢竟如果能用更少的空間存放數據，memory 能裝的更多，cache 更友好，性能就更好。但現在 succinct 還沒有大規模的落地，可以看看後續的發展。如果你對構建新的存儲引擎有興趣，歡迎聯繫我 tl@pingcap.com。

原文鏈接