這不最近入職了 PingCAP，然後對自己從事的工作完全不了解，於是只能去惡補資料庫和存儲相關的知識，不過在我看來… 完全不懂並不是壞事，第一就是成長空間巨大，第二就是看待問題的角度並不一樣因此可能會產出一些🚢新的思路呢～
言歸正傳，今天我就用這麼幾天淺薄的技術 “積累”，簡單聊一聊 LSM🌲…
不知道從什麼時候開始，貌似是一家首頁 404 號稱不作惡的公司做出來了 Big Table，然後使用了一個論文，然後這篇論文提出了一條🚢新的道路，沒有 B🌲，寫入效率高於讀取效率，這咋聽起來並不怎麼靠譜的數據結構居然吊打了 MySQL 這種老牌資料庫，但可惜 Big Table 是閉源的… 不過！不久之後，隨著原創作者開源了根據這篇演算法寫的一個單機開源資料庫 LevelDB 直接引爆了生態，一下子各個號稱分佈式的存儲系統跟風就上，隨著 FaceBook 做出了RocksDB (也就是我現在負責填坑的項目，寫的是真的菜)，奠定了新一代分佈式資料庫的存儲引擎，我司 TiKV 也是在這個上建的，那今天柠檬帶大家看看究竟這個資料結構在幹啥…
所以這顆🌲幹啥的#
首先，所有技術的誕生都有當時時代的局限性，現在我們所處的這個時代，伺服器是用不起高吞吐量的隨機讀寫的 SSD 的，也沒有一個沒有性能損耗就可以達到高吞吐量隨機讀寫且穩定的存儲介質，所以在這個時代，大批量順序讀寫的效率要比隨機讀寫高出 20 倍以上 (真實數據並不是胡說)，所以為了加速資料寫入到存儲介質的速度，必須使用順序讀寫。
LSM🌲就誕生了！#
LSM🌲 全名: Log-Structured Merge Tree.
簡而言之，就是像我們寫 Log 一樣寫入資料，這樣就保證了順序寫入。
但同時帶來了一個巨大的問題，我們知道 log 就像一個鏈表，鏈表的隨機訪問如果沒有 index 結構的話那麼複雜度將會達到 O (N)，這玩意兒咋用啊！？這個問題將在後面讀取的時候進行解答。
我們在前面提到了 404 公司的 LevelDB，在 LevelDB 的裡面存儲引擎的 LSM🌲是搭配著 SSTable 進行使用的，
SSTable 全名: Sorted-String Table
404 公司是這麼描述的:
An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.
所以我們知道了 LSM🌲在 LevelDB 中是搭配了一個持久化有序不可變的鍵值存儲結構，存儲的一個鍵和一個數據的 offset。有了 offset 搭配 mmap 就可以瞬間找到俺們的 LSM🌲存的信息了～吆西！
所以 LSM🌲的寫入過程就是如下:
- 有人告訴我他要寫資料，我先打個 log，避免寫的時候裂開
- 把這個資料寫入到內存中的 SSTable 裡面 (也可能是要刪除資料，已知我們是打 log 所以這時候就是寫入「他死了」)，然後同時寫入到內存裡的一個表裡面。
- 內存裡的表大到一定程度之後就會開一個新的表，然後舊的表就不可寫入了
- 舊的表在合適的時機寫入到硬盤～
- 然後隨著硬盤上的小表越來越多，將會在合適的時機 (比如半夜三更) 進行一次 merge，變成一個大表，merge 的過程中會刪除掉標記了「他死了」的資料。由於這些表都是有序的，merge 過程就是一個簡單的離線 merge sort。
那麼讀取的過程也就簡單明了了～
- 內存看看表裡有沒有？-- 很快
- 沒有 -- 看看最近存的小表裡有沒有
- 還沒有 -- 看看最近的大一點的表裡有沒有
- 還沒有 -- 以此類推
那麼… 怎麼好像看起來讀取還是最慢的情況下是 O (N)？
那麼下面就是今天的重點了，大家拿出筆記本📓，但是不會考。
讀取優化#
🔴⚫🌲#
由於作者表示能夠用 20 行 Haskell 寫出紅黑樹，你們寫不出來你們菜，所以不講。
HashTable#
// 這裡是個遞迴
GOTO 0x00;
跳表#
好的，恭喜🎉你來到了大多數存儲引擎都在使用的優化，跳表。
level 2: [11] [21] [41] [70]
level 1: [11] [14] [21] [31] [41] [58] [70]
level 0: [11] [12] [14] [15] [21] [24] [31] [39] [41] [49] [58] [61] [70]
一個跳表有 N 個 level，
因為我們的 LSM🌲是一個有序的資料結構，所以理論上我們就可以達到無限接近 O (log N) 的讀取速度。
怎麼寫… 估計看我部落格的小朋友應該都已經腦子裡寫了個差不多的，那麼我們大概講一下生成多少層跳表空間浪費和時間增加能達到相對的平衡。
首先，現實生活中資料庫處理的資料量是非常龐大的，肯定不可能按照兩個建一層這麼粗暴的方法構建，這樣會帶來巨量的空間浪費，所以實際我們使用一個非常巧妙的概率策略:
拋硬幣
因為硬幣的正反面正好各占 50% 的概率所以嚴格和跳表的 log 吻合～
int 這個節點會在第幾層有緩存呢(){
var level = 0;
while ( true ){
var 隨機數 = random.nextInt();
if ( 隨機數 % 2 == 0 ) {
level += 1;
} else {
break;
}
}
return level;
}
這樣雖然很不公平，也可能出現一些非洲人節點訪問次數很多但就不是索引的情況，但是基於概率來講相對比較平穩。
下期預告：可能會講一下老遲的 AgateDB 借鑒的項目 Badger 的 SSD 優化以及如何吊打 RocksDB 的，敬請期待～