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 有什麼更先進的地方