Go 與 Badger#
上回我們談到 LSM🌲在 HDD 上由於出眾的寫入性能和優化後可以接受的讀取性能，在 B🌲混戰的資料庫領域獲得了一席之地，新型資料庫因為 LSM🌲相關的技術好學好寫，並發性好等一系列原因紛紛轉頭到 LSM🌲相關的儲存後端。
承上回，由於 HDD 是轉著寫的，所以隨機訪問性能比順序訪問慢了 100 倍...
但是，有一個跨時代的發明出現了！
他，就是一直在漲價，通過減低使用壽命減價的儲存介質 SSD！
通過上回的文章，我們了解到 LSM🌲快的原因主要有幾點：
- 新來的先到內存去
- 順序寫入磁盤
- 定期整理磁盤
第三步決定了冷數據從磁盤讀取的速度，但代價就是必須對數據分 level，比如 10M 是一個 level，100M 是另一個 level，從小的 level 在不斷的整理的時候 level 變大的過程叫compaction，升級的公式大部分 LSM 都是以下公式：
sizeof( L+1 ) = 10 * sizeof( L )
當一個 Level 撐不下這個 Level 裝的信息的時候需要整理到更大的 Level 和別人合併的時候這個叫做寫放大（畢竟多寫了 N 遍）
同理，當我在找一個 key 的時候，這個 key 存儲在不同的 level 上的時候我會找很多次，這個就叫做讀放大（畢竟多讀了 N 遍）
所以... 優化的空間就是使用 SSD 比 HDD 高效的隨機讀取性能去優化 LSM🌲從而降低讀放大和寫放大。
但是寫放大這個步驟會大幅度縮短 SSD 的壽命，所以我們要利用高效的隨機讀取能力的時候減少寫放大。
Badger 橫空出世#
創始人：老子是 Go 用戶，老子要寫 DB，一看 RocksDB，可以是可以，但是我咋得開 CGo，一開 CGo Goroutine 就被 pthread 拖慢成了💩，誒，咋還有內存泄漏？！垃圾 C 艹（本人也贊同），老子拿 Go 重寫（本人也贊同，畢竟 RocksDB 的開發者連怎麼寫 CMake 都不知道）
大概 Badger 只提供了如下功能
Get、Set、Delete和Iterate函數。在此基礎上，它還添加了CompareAndSet和CompareAndDelete原子操作
相較於 RocksDB，Badger 從一開始就對事務做出了一定的考量，使得寫資料庫更簡單。
Badger 和 HDD 上的 LSM🌲的區別#
把 KV pair 分開存儲，Key 存在一個 LSM🌲上，而 Value 存在 WAL 上（原文 value log），這樣 LSM🌲的大小就變成了 RocksDB 的一半，從而降低了寫放大的性能損耗，第二點就是通過使用 SSD 的隨機讀取功能直接從 WAL 裡取出來值。
實現細節#
KV 分別存儲#
由於原教旨 LSM🌲的主要成本就是compaction，在這期間要進行離線排序，所以產生了迭代，但是往往是對 Key 排序，Value 在這個過程中不會更改，所以 Badger 分配了 Key 和 Value 的存儲，這樣降低了一大半無用的 Value 被排序浪費的內存。第二，Badger 把 Value 的位置用delta encoding AKA 指針 的方式存儲在了 Key 的右邊，這樣就可以告訴 SSD 這個 key 對應了什麼位置的 Value，同時通過限制單個文件的大小提升了緩存的性能，假設一個 key 16 byte，一個指針 16byte 就可以在一個 64M 的文件中存儲超過 200 萬行的 KV。
寫放大縮小#
因為降低了 Value 部分存儲在 LSM🌲的大小，所以 Value 這部分就不會產生寫放大，也不會隨著 Key 到處亂竄，
如果我們假設 Value 大小 1kb，16byte 還是 key 的大小，那麼寫放大僅僅有
(10*16 + 1024)/(16 + 1024) ~= 1.14
也就是僅僅放大了一點點🤏
這體現在性能上就是寫入速度是 RocksDB 的 N 倍，N 取決於 Value 產生的寫放大落入磁盤的時間。
讀放大縮小#
還是因為 Value 沒在 LSM，所以 LSM 的大小大幅度縮小，這還意味著產生的層級變少了，進而在內存中存儲的部分就變多了，通過 bench 發現 RocksDB 在值固定在 1kb，有兩千兩百萬行數據的時候 RocksDB 用了 72gb 的資料集存在了 LSM 樹上，而 Badger 這邊只存 Key 和偏移，所以僅僅存了 1.7G，全部在內存裡…
所以讀取速度吊打了 RocksDB 3.5 倍....
迭代速度... 那就是 3.5*N
具體 bench mark 大概是這樣吊打的#
由於篇幅有限#
下期預告... 可能採訪一下老遲看看俺們 Agate 有什麼更先進的地方