100 行代碼的壓縮前綴樹：50% smaller
本文介紹一個壓縮前綴樹實(shí)現(xiàn)的（sorted set（github：succinct.Set?[1]）區(qū)區(qū) 95 行代碼，包含了一組完整的功能：
用前綴樹存儲一個排序數(shù)組，去掉指針，壓縮掉 50% 的空間；例如在本文的例子中, 存儲 2.4 MB 的 200 萬個單詞, 只需要 1.2 MB。
創(chuàng)建：從 key 列表創(chuàng)建一個壓縮的前綴樹；
查詢：支持 Has()? 操作來查詢 1 個 key 是否存在；
優(yōu)化：通過索引來加速 bitmap 的操作，將較大的 bitmap 操作優(yōu)化到 O(1) 的時(shí)間開銷。
loc100?分支是本文中使用的最簡實(shí)現(xiàn)，沒有任何外部依賴，main 分支中的實(shí)現(xiàn)面向生產(chǎn)環(huán)境，要快 4 倍左右。
如果要生產(chǎn)環(huán)境使用，移步?slim?[2]。
用 20 萬個網(wǎng)上詞匯來測試本文實(shí)現(xiàn)的 succinctSet：
succinctSet 空間開銷是源數(shù)據(jù)的 57%。
Has()?開銷為 350 ns。
原始數(shù)據(jù)大?。?204 KB 跟 string 數(shù)組的 bsearch，以及?google btree?[3]?的對比：
場景和問題
計(jì)算機(jī)中的信息，為了查詢方便，幾乎都是排序存儲的（即使是 hash?結(jié)構(gòu)，hash map 中的 hash 值也是順序存儲的）。
數(shù)據(jù)存儲領(lǐng)域，大部分?jǐn)?shù)據(jù)也都是靜態(tài)的，例如數(shù)據(jù)庫底層的一個 page，rocksdb 的一個 sstable。數(shù)據(jù)越來越大后對存儲空間的開銷也越來越敏感，畢竟影響性能的主要瓶頸都在 IO 上，不論是 CPU 對主存的訪問延遲，還是內(nèi)存到磁盤的延遲，每 2 層之間的 IO 延遲，基本都在 1~2 個量級左右。于是更小的存儲開銷，不僅節(jié)省存儲成本，另一個 bonus 是幾乎毫無疑問的會提升性能。
本文針對這一個廣泛使用的場景：靜態(tài)排序數(shù)據(jù)，提供一個通用的實(shí)現(xiàn)方法來壓縮空間開銷。
生產(chǎn)環(huán)境中使用的算法，和本文介紹的方法同源，但包括更多的優(yōu)化，例如通過 SIMD 指令一次處理多個字節(jié)的比較，用 bitmap 來優(yōu)化 labels 的存儲，對只有一個出向 label 的節(jié)點(diǎn)的合并優(yōu)化等。
思路：前綴樹
前綴樹?[4]，或字典樹，prefix tree，trie，是解決這類問題的一個典型思路。例如要存儲 5 個 key：[ab, abc, abcd, axy, buv] 可以建立下面這樣一個前綴樹，省去大量重復(fù)的前綴，其中?^?是 root 節(jié)點(diǎn)（也記做0），1, 2, 3…是 trie 節(jié)點(diǎn)，$標(biāo)記一個葉子節(jié)點(diǎn)，字母?a, b...?表示一個節(jié)點(diǎn)到下級節(jié)點(diǎn)的邊（labeled branch）：
前綴樹的壓縮算法
在這個前綴樹中，每個節(jié)點(diǎn)至多有 256 個出向 label，指向下一級節(jié)點(diǎn)。一個節(jié)點(diǎn)可以是 inner 節(jié)點(diǎn)，例如 root 節(jié)點(diǎn)?^，或?1, 2, 3。也可以是葉子節(jié)點(diǎn)，例如?3, 6, 9。這里 3 既是一個 inner 節(jié)點(diǎn)也是一個 leaf 節(jié)點(diǎn)。
要壓縮這個 trie，對每個 trie 節(jié)點(diǎn)，我們需要的最核心的信息是：
一個節(jié)點(diǎn)的分支（label）都有哪些，
以及 label 指向的節(jié)點(diǎn)的位置。
我們有以下這種緊湊的結(jié)構(gòu)來描述這個 trie：
一個 trie 節(jié)點(diǎn)的出向 label 都存儲在一個 []byte 中，再用一個 bitmap 來描述每個節(jié)點(diǎn)的分支，后面通過這個 bitmap 來定位 label 對應(yīng)的節(jié)點(diǎn)。
先把每個節(jié)點(diǎn)對應(yīng)的 label 列出來，并為每個 label 分配一個bit 0?來標(biāo)記：
然后將所有的 label 保存在一個 []byte 中，再將對應(yīng)的標(biāo)記 label 的多個?0... 用 1 做分隔符連接到一起：這 2 塊信息是 succinctSet 核心的 2 個字段，有了這 2 部分?jǐn)?shù)據(jù)就可以實(shí)現(xiàn)（不算高效的）key 查找：
壓縮后的查詢：
在標(biāo)準(zhǔn)的 trie 中查找一個 key 很簡單，在第 L 層的一個節(jié)點(diǎn)上，查找 key[L] 的 byte 是否是 trie 節(jié)點(diǎn)的一個出向 label，如果是，走到下一個節(jié)點(diǎn)，否則終止。例如對?axy?的查找，要經(jīng)歷 3 次查找，^ -a-> ① -x-> ④ -y-> ⑦ $：
在 succinctSet 中的查找也是一樣，唯一不同的是如何在這個沒有指針的結(jié)構(gòu)中找到某個出向 label 對應(yīng)的子節(jié)點(diǎn)。我們把 trie 原來的 label 到子節(jié)點(diǎn)的關(guān)系，在壓縮后的結(jié)構(gòu)中畫出來，端詳端詳：
從上圖可以看出，
除了根節(jié)點(diǎn)
^，每個節(jié)點(diǎn)都有一個?0?與之對應(yīng)（節(jié)點(diǎn)入向 label 對應(yīng)位置的0）。?圖中上下箭頭，是 label 到節(jié)點(diǎn)的關(guān)系，也就是每個?0?跟它指向的子節(jié)點(diǎn)的對應(yīng)關(guān)系。每個節(jié)點(diǎn)也都有一個?
1?與之一一對應(yīng)，也就是每個節(jié)點(diǎn)都有一個結(jié)束標(biāo)記?1。
例如：
bitmap 中 第 0 個?
0?對應(yīng)節(jié)點(diǎn)?1:bx，第 1 個?0?對應(yīng)節(jié)點(diǎn)?2:u…同理節(jié)點(diǎn)與?
1?的關(guān)系也類似，第 0 個?1?對應(yīng) root 節(jié)點(diǎn)?^，0:ab，第 1 個?1?對應(yīng)節(jié)點(diǎn)?1:bx，第 2 個?1?對應(yīng)節(jié)點(diǎn)?2:u…
你品，你細(xì)品…品完后發(fā)現(xiàn)，要找到某個 label 指向的節(jié)點(diǎn)，只需要先數(shù)數(shù)這個 label 對應(yīng)第幾個?0，例如是第 i 個0，再找到 bitmap 中的第 i 個?1，第 i 個?1?后面就是 label 對應(yīng)的節(jié)點(diǎn)位置了。這就是在壓縮前綴樹中逐層定位節(jié)點(diǎn)的算法。舉個栗子 ??假設(shè)從根節(jié)點(diǎn)開始，要查找的 key 是 axy，
首先在根節(jié)點(diǎn)?
0:ab?中找到 label?a，label?
a?對應(yīng)第 0 個?0，然后找到第 0 個?1?的位置，也就是?1:bx?節(jié)點(diǎn)。再在?
1:bx?節(jié)點(diǎn)的 label 中找到 label?x，對應(yīng)第 3 個?0，再找到第 3 個?1?的位置，也就是?4:y?的節(jié)點(diǎn)。在?
4:y?中找到 label?y，對應(yīng)第 7 個?0，再找到第 7 個?1，也就是?7:??的節(jié)點(diǎn)。節(jié)點(diǎn) 7 沒有任何 label，結(jié)束。
在 succinctSet 數(shù)據(jù)結(jié)構(gòu)中畫出 axy 的查詢過程如下：
維護(hù) leaf 節(jié)點(diǎn)：
上面介紹的查詢算法還有一個問題，就是當(dāng)某些 key 是其他 key 的前綴時(shí)，它對應(yīng)的節(jié)點(diǎn)既是 inner 節(jié)點(diǎn)，也是 leaf 節(jié)點(diǎn)，這時(shí)無法通過 label 的不匹配結(jié)束查詢。例如 abc 對應(yīng)的節(jié)點(diǎn)?6:d，它本身有一個出向分支?d，是一個 inner 節(jié)點(diǎn)，同時(shí)也是一個 leaf 節(jié)點(diǎn)。
所以我們還需要額外的信息來標(biāo)識所有的 leaf 節(jié)點(diǎn)：再建立一個?leaves?的 bitmap，它的第?i?個 bit 為?1，表示 node-id 為?i?的節(jié)點(diǎn)是 leaf 節(jié)點(diǎn)：
leaves 的檢查在查詢的最后一步，如果一個要查詢的 key 匹配到一個 trie 中的節(jié)點(diǎn)，最后再檢查它是否是一個 leaf 節(jié)點(diǎn)。
優(yōu)化 bitmap 操作：
這個算法中最后還有一個問題沒有解決：我們提到從 label 定位 node 的過程是: 找到一個 label 之前的?0?的個數(shù) i，再找到第 i 個的?1?的位置。這 2 個操作都是 O(n) 的，要遍歷 bitmap，最終會導(dǎo)致一次查詢的時(shí)間效率變成 O(n2)。為了能讓查詢提升效率，我們需要建立 2 份額外的信息來優(yōu)化這 2 個操作。第一個是找出一個 bitmap 中第?i?個 bit 之前有多少個?1（或多少個?0），對定長整數(shù)，例如一個 uint64，它的有 O(1) 的實(shí)現(xiàn)，例如
在 cpp 里叫做?popcount?[5]，i.e.，count of population of ones；
在 go 里面它被封裝在?
bits.OnesCount64()?這個函數(shù)，數(shù)數(shù)一個 uint64 里有多少個 1;一般的，叫做 rank1(i)，如果要計(jì)算一個 bitmap 里有多少個 0，則是 rank0(i)。
第二個，要得到第?i?個 1 的位置的操作，叫做 select1(i)。我們現(xiàn)在需要為 rank1() 和 select1() 分別建立緩存：
rank：
建立一個數(shù)組?rank []int32：ranks[i]?記錄 bitmap 中前?i*64?個 bit 中的?1?的數(shù)量。. 這樣要計(jì)算 rank(i) 就只需要取 ranks[i/64]，再用一個 O(1) 的函數(shù)調(diào)用（如?bits.OnesCount64()）計(jì)算?bitmap[i:i % 64]?中的 1 的個數(shù)。
例如 bitmap 中第 0 個 uint64 有 25 個 1，第 1 個 uint64 有 11 個 1，那么建立的 ranks 索引如下：[0, 25, 36]
select：
select 索引也是一個?[]int32:?select[i]?記錄第?i*32?個?1?在 bitmap 中哪個位置。
例如第 0 個?1?在第 1 個 bit，第 32 個?1?在第 67 個 bit，第 64 個?1?出現(xiàn)在第 126 個 bit，那么 selects 的索引就是：[1, 67, 126]：
代碼實(shí)現(xiàn)
Set 結(jié)構(gòu)定義：
有了 ranks 的索引, 找出第 i 個 bit 之前的?1（或?0）的數(shù)量就可以確定用 O(1) 時(shí)間完成；而 select 索引，可以盡可能讓找出第 i 個 1 的開銷趨近于 O(1)；因?yàn)?selects 的 2 條索引之間可能跨越幾個 uint64，取決于 bitmap 中?1?的分布。
這樣，整個 succinctSet 的數(shù)據(jù)結(jié)構(gòu)就完整了：
我們接下來看看完整的代碼邏輯：
創(chuàng)建 Set：
依舊以?keys = [ab, abc, abcd, axy, buv]?為例，來描述 Set 的建立，
先掃描所有 keys 的第 1 列，找到 root 節(jié)點(diǎn)?
^?的出向分支，有 2 個 label:?a,b同時(shí)把整個 keys 列表按照前綴為?a?和前綴為?b?拆分成 2 部分，順次放到隊(duì)列尾部等待處理。.第 2 步，從隊(duì)列中拿出要處理的第 2 部分：前綴為?
a?的 keys，掃描這些 keys 的第 2 列，找到節(jié)點(diǎn)?1?的出向 label:?b,x再次把前綴為?a?的集合拆分為前綴為?ab?的集合和前綴為?ax?的集合，順次放到隊(duì)列尾部等待處理。第 3 步，掃描前綴為?
b?的 key 集合的第 2 列，找到 1 個出向 label?u，把所有前綴為?bu?的 key 放到隊(duì)列尾部等待處理。
最后直到所有隊(duì)列中的元素都處理完，trie 就建立完成。最后再通過?init()?給建好的 trie 做 rank 和 select 的索引。
掃描前綴的過程，也就是建立 trie 節(jié)點(diǎn)的順序，按照 node-id 標(biāo)識如下：
查詢：
trie 的查詢過程也很簡單：在要查詢的 key 中取出一個 byte，看它是否在當(dāng)前節(jié)點(diǎn)的 label 中，如果不在，就可以確認(rèn) key 不在 succinctSet 中。如果在，通過之前提到的?select1(rank0(i))?的方法走到下一個節(jié)點(diǎn)，繼續(xù)以上步驟。
當(dāng) key 中所有 byte 都檢查完后，看最后是否停在一個 leaf 節(jié)點(diǎn)，最終確認(rèn)是否匹配到一個在 Set 中存在的 key。
bitmap 的索引：
上面我們提到，從 label 定位節(jié)點(diǎn)的過程主要依賴于計(jì)算 bitmap 的 2 個操作：計(jì)算指定位置前有幾個 1:?rank0(i)，以及找出第 i 個 1 的位置：select1(i)。
go 里面提供了 uint64 的 rank 操作，bits.OnesCount64() 可以在 O(1) 的時(shí)間內(nèi)返回一個 uint64 中被置為?1?的 bit 數(shù)。我們用它來給 bitmap 中每個 unit64 提前計(jì)算好前面有幾個?1，這樣在使用的時(shí)候只需要再處理最后一個 uint64 就可以了。
select 的索引直接逐個計(jì)數(shù)?1?的個數(shù)，然后在個數(shù)滿 32 整數(shù)倍時(shí)添加一條索引。
當(dāng)我們要利用索引取第 i 個 bit 前有幾個?0?時(shí)，通過?rank0(i) = i - rank1(i)?來計(jì)算：
在查找第 i 個?1?所在位置時(shí)，我們先通過 selects 索引找到一個最接近的 uint64，再向后逐個查找直到見到第 i 個?1。這一步的性能不是嚴(yán)格的 O(1)：
性能分析
我們用網(wǎng)上搜集到的數(shù)據(jù)集做了下測試。測試中使用的負(fù)載模型都是?zipf?[6]?比較符合互聯(lián)網(wǎng)的真實(shí)場景，zipf 的參數(shù) s 取 1.5，細(xì)節(jié)參考?report??[7]?的代碼，結(jié)果如下：
20 萬個網(wǎng)上詞匯：
原始數(shù)據(jù)大小：2204 KB
跟 string 數(shù)組的 bsearch，以及 google btree 的對比：
succinctSet 空間開銷是源數(shù)據(jù)的 57%。
Has()?開銷為 350 ns。
87 萬個某站提供的 ipv4 列表：原始數(shù)據(jù)大?。?823 KB
succinctSet 空間開銷是源數(shù)據(jù)的 67%。
Has()?開銷為 528 ns。
可以看出在內(nèi)存方面：
succinctSet 對內(nèi)存開銷優(yōu)勢明顯，不僅容量沒有額外增加，還少很多。
go 中的 string 有 2 個字段：到 string 內(nèi)容的指針，以及一個 length，所以每條記錄開銷會多 16 字節(jié)。
btree 內(nèi)部因?yàn)檫€有 interface，額外存儲開銷更大。
對查詢性能:
短字符串查詢二分查找性能最好，一個字符串讀取一次差不多都能緩存在 L1 cache 里，對主存的訪問應(yīng)該非常趨近于 lg?(n)。
succinctSet 因?yàn)槊總€字符串的每個字符都被分散存儲了，以及 ranks 和 selects 的訪問也是跳躍的，在一個 key 的查詢中要訪問多個位置。所以對緩存的友好不如數(shù)組。
btree 的時(shí)間開銷更大，可能由于間接訪問比較多，導(dǎo)致 btree 的優(yōu)勢沒有發(fā)揮出來。
引用鏈接
[1]?succinct.Set :?https://github.com/openacid/succinct/tree/loc100
[2]?slim:?https://github.com/openacid/slim
[3]?google btree :?https://github.com/google/btree
[4]?前綴樹:?https://en.wikipedia.org/wiki/Trie
[5]?popcount :?https://en.cppreference.com/w/cpp/numeric/popcount
[6]?zipf:?https://blog.openacid.com/tech/zipf/
[7]?report :?https://github.com/openacid/succinct/blob/v0.1.0/report/main.go
關(guān)于 Databend
Databend 是一款開源、彈性、低成本，基于對象存儲也可以做實(shí)時(shí)分析的新式數(shù)倉。期待您的關(guān)注，一起探索云原生數(shù)倉解決方案，打造新一代開源 Data Cloud。
Databend 文檔：https://databend.rs/
Twitter：https://twitter.com/Datafuse_Labs
Slack：https://datafusecloud.slack.com/
Wechat：Databend
GitHub ：https://github.com/datafuselabs/databend
?文章首發(fā)于公眾號：Databend
