BitDegradeTree詳解[多圖]

BitDegradeTree的前身是CritBitTree, 這是一個十分冷門卻又強力的數據結構.

引理1: 給定兩組字元串, 如不同則必然存在差異.

比如, AAABB與ABABB是兩組不同的字元串. 我們不考慮AAABB與AAABBB, 因為總是可以用一個不存在於實際內容的特殊符號來表示結束, 從而避免前綴包含關係. AAABB$與AAABBB$顯然不同, $在這裡就是休止符.

存在差異的字元串必然可以用一個整數來表示分歧位置. 我叫它分歧點. AAABB與ABABB的分歧點在位置2. 用分歧點進行分割之後, 樹結構是這樣的,

綠色部分是CBT真正記載的信息, 藍色部分就是原有的數據, 箭頭是指針. CBT不需要拷貝或者移動原有的數據, 這也是CBT可以做到在WAL上直接做索引的原因. 我們進一步推廣開來, 將其用二進位表達, 左邊是0, 右邊是1. AAABB變為00011, ABABB變為01011, 有樹如下,

假設現在來了一個請求是檢測00011是否在樹中, 根節點告訴我們第一個分歧點在位置2, 00011的位置2是0, 那麼向左走, 發現已有00011, 全匹配成功.

如果請求是檢測00010, 我們一樣會先向左走遇到00011, 但最終全匹配時失敗. 因此若key的長度為N bits, CBT至多進行N次基於分歧點的匹配(向左走或向右走), 並最終僅進行一次全匹配(藍色節點, 也就是原值).

假設請求是插入01010呢? 照舊, 先看分歧點是2,01010在位置2是1, 向右走, 遇到了01011, 全匹配失敗(memcmp!=0). 那麼要插入的話, 發現01010與01011的分歧點在位置5, 樹變為,

CBT還有可能觸發回溯來插入值, 不過那也很容易明白. 比方說, 插入10011. 樹中的值都是0開頭的, 怎麼辦? 沒關係! 繼續走流程. 10011在位置2上是0, 向左走, 遇到00011, 最早分歧點在1, 回溯尋找合適的位置, 樹變為,

這個操作的正確性由引理2保證,

即兩個藍色節點共享了一個綠色父節點, 則藍色節點共享前綴, 長度為分歧位置減一.

怎麼說呢? 可以看到01010藍色節點和01011藍色節點, 他們共享了數值為5的綠色節點, 說明他們的前4位都是相同的. 所以我們在插入10011時發現分歧點是1, 發生回溯時, 相當於已經和這個樹中別的數值比較過了. 為啥? 因為它們都有共享的前綴.

CBT可以做成fine-grained locking的多線程小粒度鎖並發的形式, 核心就是回溯插入時檢查引理2是否成立, 不成立就重試. 我在這個問題上花了大量的時間踩了大坑, 因為對於多線程高性能編程了解不透徹, 最終這個效果很差勁. 在雙核機器上, 多線程版本僅領先單線程版本20-30%. 這也是如何評價ffwd？嘗試解釋的. 大多數數據結構, 單線程版本如果很複雜, 即使存在著fine-grined locking的可能, 多線程表現也往往不盡如人意. 目前我最鍾愛Skiplist, 如此簡單實用, 問題是多線程下也好優化好使啊!

不知道CBT部分讓各位明白了嗎? 不明白的話, 評論本文或者看原發表者GitHub agl/critbit

那麼BDT做了什麼改進工作呢? 我們先看看CBT作為索引優越性在哪裡?

首先, CBT是有序的, 又因為是trie-like, 存在支持正則表達式/前綴查詢的可能性(我寫過). 作為硬碟索引的話, CBT最最重要的是CBT本身的尺寸可以很小很小. 無論key有多長, CBT需要記錄的數據僅僅就是一個整形, 表示分歧點在哪裡. 這意味著很可能100MB的key, 1GB的value, 整個CBT索引就5MB, 甚至可以整個裝進L3 cache.

除了小之外, CBT的IO需要量也遠遠低於B-Tree家族或者LSMT的SSTable的Skiplist. 拿平衡樹來說, 1W的數據量, 最佳情況(完美平衡)也要跟13(log2(1W))個key做全匹配. CBT的綠色節點小, 且至多跟藍色原數據key比較一次. 那麼硬碟IO讀需求量就是13:1的關係. 這難道不誇張嗎? 至於寫, CBT可以直接在WAL做, 那就是2:1的關係, 也不錯了.

可以說CBT在我看來就是被遺失的上古神器!

CBT的問題也不是沒有, 指針跳轉太頻繁, 既耗費性能又浪費空間. 如果說我的key長100 bits, 該死的正好有了100個分歧點. 那麼為了找尋一個key, CPU要連續跳100個位置嗎? 我們都知道鏈表遠遜vector, C++老爹也明確表示他不喜歡鏈表.

我覺得B-Tree的思路完全可以引入進來啊. 我的設計是這樣的,

這有著許許多多優良特性, 首先這很符合直覺, 就是把CBT直接拍匾就好了.

其次是有序的, 遍歷方便是一方面, 還意味著我無論是插入還是刪除, 直接memmove就搞定了! 天吶! Perfect! 我實現的時候, 4KB內可以裝600多個key, 一般B-Tree/Skiplist能裝多少呢?

大問題來了, 這個要怎麼查詢呢??? 我前後想了3套方案, 別的亂七八糟的想法還有一堆, 不放出來見笑了.

1. Naive解決方案, 這是我第一版用的, 不斷找最小值法.

我要分辨01011在不在這個BDT Node中, 第一步是先遍曆數組[2,5,1], 看最小值是多少? 哦, 是1. 那麼01011的位置1是0, 向左走, 數組變為[2,5]. [2,5]的最小值是2, 01011在位置2上是多少? 1, 向右走, 數組變為[5], 僅有一個值, 最小值自然為5, 在位置5上, 值為1, 向右走, 遇到藍色節點"01011", 全匹配成功, 返回存在.

這其實就是根據CBT有序性和前綴性來查詢. 我們算一下複雜度, N個分歧點, N次最小值運算, 不用想了, 就是O(n^2). 我當時是覺得反正人人都說資料庫瓶頸在IO, 那麼CPU多花點時間無所謂.

現在我可以肯定說, 這都是放屁... 先不談現在SSD一個跑得比一個快, 光說系統高度優化的緩存就不得了了. 無論是RocksDB還是LevelDB默認都是不開sync的, 也就說數據只要落到系統頁就算完成了任務. 我就是SATA的硬碟, 1GB數據, 1秒多也寫完了, 可能嗎? 全都進系統頁了而已. 甚至主要寫入的瓶頸我看就是從用戶空間內存刷到系統. 我不flush的寫入速度是flush的2-3倍. 即使是資料庫這種人云亦云重IO的程序, CPU佔用也是重中之重.

我花了好長時間想明白我剛剛說的話, 才意識到為什麼LSMT席捲了整個DB界? 因為memtable+immemtable+SST太符合現代操作系統的尿性了. 爆發性的寫入你需要memtable立馬吸收掉, 然後慢慢轉化成硬性的硬碟IO慢慢寫. 如果一開始就用硬碟上的索引, 系統緩存根本幫不上忙, 然後大家一起卡住. 這些經驗如果不自己去做, 根本想不明白為什麼別人要這麼做.

2. O(n)解決方案, 還原法

我想起了刷LeetCode時, 經常不是做括弧匹配嘛. 什麼給你一大串((()()()()))), 然後最長的合法括弧對是多長啊? 這種瞎Beta問題, 我曾經一度以為沒用, 直到那時. 分歧點數組[2,5,1]可以用類似的手法, 開個棧, O(n)時間內還原成CBT.

T0: 棧: [空]

T1: 棧: [2] 入棧2

T2: 棧: [2,5] 入棧5, 因為5>2, 肯定在右邊

T3: 棧: [2,5] => [1], 出棧2,5, 入棧1, 因為1<2<5, 2肯定在1的左邊

看見沒有, 從BDT的node到CBT的tree, O(n)就能解決了. 我以為這就夠了. 現實又打了我一巴掌, 因為出棧入棧太花時間了, 常數項太大, 反而不如O(n^2)的naive演算法. 尼瑪啊!!! 工程和理論的差距有時候就是這麼大.

3. 終極方案 SSE4.2 O(n)金字塔構建法 O(log n)單次查詢

設CBT如下, 我省略了藍色節點, 因為那不重要.

轉化成BDT Node就是數組[3,2,3,1,3,4,6,5].

在此之上建立一個查詢金字塔, 我是這麼叫的, 如此簡單的演算法應該早有人想到了吧. 每n個作為一個小分區, 小分區記載兩個值, 一是最小值, 二是下標.

我要查詢[3,2,3,1,3,4,6,5]的最小值直接看最頂層的(Min 1 Pos 2, 純白色), 得知最小值是1, 再沿著向下走還原位置. 如果向左走, 那麼就要查詢[3, 2, 3]的最小值, 這樣會改動黃色的(Min 1 Pos 2)由此變成(Min 3, Pos 1), 就要更新上層到了灰色區, 變為(Min 2, Pos 1).

小分區尺寸完全沒必要是2, 我推薦是8. 這樣構造操作可以用SSE 4.2的minpos來做, 速度是直接比較的8倍. 金字塔是完全對稱的樹, 自身又可以再次壓縮成一個普通數組, 省掉指針空間和地址跳轉開銷. 本方法特別適合用於離線生成BDT. 至此, BDT所有能profile出來的瓶頸在這裡都被我解決掉了.

不知道我有沒有說明白呢? 你又有沒有覺得excited呢? 反正我是excited了半年... 現在發出來是發現超過RocksDB, 路漫漫其修遠兮.

我又又叕推翻了原有的設計方案. 上一次是我發現BDT動態構建根本承擔不起memtable的職責轉而抄了RocksDB的memtable. 這次, 我不準備推翻RocksDB了, 而要做RocksDB的緩存層. 數據進來之後, 先進InlineSkiplist, 滿了之後直接離線打一個BDT, 配合原有的WAL做臨時小資料庫, 然後實在滿了再直接一次性bulk load進RocksDB.

最後, 我實在是喵的寫煩躁了! 我要換個方向了!

所以我不ZS了. 我又回來了. 我留下這篇文章, 還有一點點經驗, 過去的六個月也不算虛度了吧.