key / value 數(shù)據(jù)庫的選型

2018-07-20 來源：importnew

原文出處： keakon的涂鴉館

引言

一直以來在我的觀念中，key/value 數(shù)據(jù)庫就三種選項：

內(nèi)存可存放：Redis
單機磁盤可存放：RocksDB
超過 TB 級：Cassandra、HBase……

然而在實際項目中使用 RocksDB 時，才發(fā)現(xiàn)了一堆問題，折騰許久才搞定。

使用 RocksDB 的背景

先介紹下我使用 RocksDB 的背景。

這個項目有很多 key/value 數(shù)據(jù)（約 100 GB）需要使用，使用時基本是只讀的，偶爾更新時才會批量導入，且可以忍受短暫的停機導入。我一想?TiKV?和?Pika?等很多 key/value 數(shù)據(jù)庫都選用了 RocksDB，應該是比較靠譜的，于是就選它了。

接著就發(fā)現(xiàn)這東西的編譯依賴有點多。我的項目是用 Go 寫的，而這個玩意需要安裝一堆 C 庫，并且不能交叉編譯到其他平臺。不但不能在 Mac OS X 上編譯 Linux 的版本，甚至 Ubuntu 16.04 上編譯的都不能在 CentOS 7 上運行（后者的 GCC 版本較低，動態(tài)鏈接庫版本也低）。因為懶得降級 GCC，最后我選擇用 docker 來編譯了。

而且我發(fā)現(xiàn)數(shù)據(jù)量小時還挺快，但是數(shù)據(jù)量大了就越來越慢。平時插入 10 萬條數(shù)據(jù)（約 50 MB）大概 0.2 ~ 0.5 秒，但一段時間后就會持續(xù)遇到需要幾秒甚至幾十秒的情況。

于是我又開始尋找其他的替代品，諸如?LMDB、BadgerDB?和?TerarkDB?等。在這個過程中我開始了解到它們實現(xiàn)的原理，也算有不少收獲。

傳統(tǒng)的關系型數(shù)據(jù)庫大多是使用 B+ 樹，這種數(shù)據(jù)結構可以很快地進行順序讀寫，也能以 O(log(N)) 的時間復雜度來進行隨機讀，但不適合隨機寫（會導致 B+ 樹重新調(diào)整平衡，造成寫放大）。

而 LevelDB 引入了 LSM 樹，就是為了解決 B+ 樹隨機寫性能低的問題，它把隨機寫以跳躍表的形式保留在內(nèi)存中（memtable），積累到足夠的大小就不再改寫它了，并將其寫入到磁盤（L0 SST file），這樣就只有順序?qū)懥�。因�?memtable 和 L0 中的數(shù)據(jù)可能會重復，而且 key 很分散，所以搜索時需要遍歷它們。如果沒找到的話，還要向下層查找（關于層數(shù)下文會解釋），不過 L1 之后的 SST file 都是有序分段的，因此可以用二分查找來找到 key 所在的數(shù)據(jù)文件，再在這個文件中用二分查找來找到這個 key。為了降低搜索的代價，RocksDB 還使用了 Bloom filter 來判斷數(shù)據(jù)是否在某個文件中（有誤判，但能顯著減少需要搜索的文件數(shù)）。由此可見，LSM 樹對寫入做了優(yōu)化，但降低了隨機讀的性能，順序讀則和 B+ 樹差不多。

此外，L0 的數(shù)據(jù)可能會有很多過期數(shù)據(jù)（被更新或刪除過），因此需要在達到閾值后進行合并（compact），去掉這些重復和無效的數(shù)據(jù)，并寫入 L1。而 L1 也可能會有過期的數(shù)據(jù)，也需要被合并寫入 L2……這就相當于數(shù)據(jù)要多次寫入不同的文件中，也就造成了寫放大。而合并不重疊的數(shù)據(jù)文件是很快的，因此順序?qū)戇€是要比隨機寫快，但合并可以在其他線程中執(zhí)行，在不會持續(xù)隨機寫入大量數(shù)據(jù)的情況下，基本能保持 O(1) 的寫入。

事實上，我遇到的 RocksDB 變慢的問題就是 compact 引起的，默認配置下它只使用一個線程來 compact，如果 compact 跟不上寫入的速度，RocksDB 就會降低寫入速度，甚至停止寫入�？紤]到我的電腦有 4 個核，于是我把線程數(shù)改成了 4：

bbto := gorocksdb.NewDefaultBlockBasedTableOptions()
opts := gorocksdb.NewDefaultOptions()
opts.SetBlockBasedTableFactory(bbto)
opts.SetCreateIfMissing(true)
opts.OptimizeLevelStyleCompaction(1 << 30)
opts.IncreaseParallelism(4)
opts.SetMaxBackgroundCompactions(4)
env := gorocksdb.NewDefaultEnv()
env.SetBackgroundThreads(4)
opts.SetEnv(env)
db, err := gorocksdb.OpenDb(opts, "db")

修改后就發(fā)現(xiàn)插入時間基本穩(wěn)定在 0.2 ~ 0.5 秒之間了，CPU 占用率超過了 400%，磁盤寫入速度超過了 800 MB/s……
另外，RocksDB 還提供了?db.GetProperty("rocksdb.stats")?這個方法來查看狀態(tài)，需要關注的數(shù)據(jù)主要有 W-Amp（寫入放大倍數(shù)）和 Stalls（因為 compact 而降速）。

RocksDB 有 3 種 compact 的方式：leveled、universal 和 FIFO。

Leveled

Leveled 是從 LevelDB 繼承過來的傳統(tǒng)形式，也就是當一層的數(shù)據(jù)文件超過該層的閾值時，就往它的下層來 compact。L0 之間因為可能有重復的數(shù)據(jù)，因此需要全合并后寫入 L1。而 L1 之后的數(shù)據(jù)文件不會有重復的 key，因此在 key 范圍不重合的情況下，可以并發(fā)地向下合并。RocksDB 默認有 L0 ~ L6 這 7 層，L1 容量是 256 MB（建議把 L0 和 L1 大小設為一樣，可以減小寫入放大），之后每層都是上一層容量的 10 倍。很顯然，層數(shù)越高就表示寫入放大倍數(shù)越高。

Universal

那么可不可以不分這么多層，以減小寫入放大倍數(shù)呢？Universal 這種風格就是盡量只用 L0，并將新的 SST 不斷合并到老的 SST，因此數(shù)據(jù)文件的大小是不等的。但單個 SST 也是有上限的，不然內(nèi)存扛不住，二分查找也會變慢，于是達到上限時，就往 L6 寫，而 L0 以外的層不會有重疊的 key 范圍，所以合并時只需要簡單地拼接就行了。如果 L6 也不夠用，就繼續(xù)往 L5、L4 等層寫入。這種策略增大了每層能容納的大小，并且因為先寫 L6，而 L6 是容量最大的，數(shù)據(jù)量較小時就不需要用到 L5 等其他層了，也就減少了層數(shù)，對應著也就降低了寫入放大倍數(shù)。但是因為 L0 的上限變大了，單個 SST 的上限也變大了，所以讀性能可能會稍微下降（部分情況下因為層數(shù)和 SST 少，讀取速度可能更快）。此外，L0 變大也會影響打開數(shù)據(jù)庫的耗時，因為需要讀取到內(nèi)存中。

FIFO

FIFO 嚴格來說不算是合并策略，它的做法是所有的數(shù)據(jù)都放在 L0，當數(shù)據(jù)量達到上限時，就把最老的 SST 刪掉。它還能搭配 TTL 使用，也就是優(yōu)先把過期時間較早的數(shù)據(jù)刪掉。這種策略一般只用于緩存，但是對于不超過內(nèi)存容量的緩存，我更傾向于放 Redis 里。
TiKV 和 Pika 都選擇了 leveled 風格，也是 RocksDB 的默認值，應該是適合大部分情況的。但如果需要更高的寫入性能，并且總數(shù)據(jù)容量不大（例如少于 100 GB），可以選擇 universal。

其實 RocksDB 還有挺多可以調(diào)優(yōu)的參數(shù)，但是都需要做測試，在 SSD 和 HDD 上表現(xiàn)也可能不一樣，這里我只列幾點：
在我的電腦上（用 SSD），允許 MMAP 讀取會稍微拖慢讀取速度，允許 MMAP 寫入可以稍微加快寫入速度。設置合理的 block cache 可以加快讀取速度，而填充讀緩存則可以加快頻繁訪問的 key 讀取。關閉 WAL 會極大地加快寫入速度（時間約減少 1/3），因為需要寫入的數(shù)據(jù)量少了一半，對于不是實時寫入的場景（例如批量導入）推薦關閉。

RocksDB 還提供了一個 Column Family 的功能，設計上就和 MySQL 的分表差不多，就是人為地將數(shù)據(jù)分散到多個 Column Families 中（例如按 key 的首字節(jié)或 hash 來分庫），使多個 Column Families 可以并發(fā)讀寫。相對于手動分到多個 db 而言，利用 Column Family 可以原子性地操作多個 Column Families 中的數(shù)據(jù)，并且能保持它們在一個事務中的一致性。

RocksDB 就講到這里，接下來看看其他的選項。

LMDB

我最先看中的是 LMDB，因為很多評測都說它比 RocksDB 更快，性能波動更小。它的原理是用 MMAP 將數(shù)據(jù)文件映射到內(nèi)存中，也就避免了寫入時的系統(tǒng)調(diào)用（實際上 RocksDB 將數(shù)據(jù)合并后一次性的順序?qū)懸矝]有多少開銷），但是一頁（4 KB）只能存放 2 條數(shù)據(jù)，而且不會進行塊壓縮，所以比較費空間；數(shù)據(jù)結構選的是 B+ 樹，因此讀性能是很好的。
直覺上我覺得 B+ 樹的隨機寫入會很慢，實際測試確實如此，并且隨著數(shù)據(jù)量的增大，寫入速度基本是指數(shù)級下降的，于是果斷放棄了。

BadgerDB

接著就找到了 BadgerDB，它的原理和 LevelDB 差不多，但是又做了個重要的優(yōu)化：將 key 和 value 分開存放。因為 key 的空間占用會小很多，所以更容易放入內(nèi)存中，能加快查詢速度。而在合并時，合并 key 的開銷很小（只是修改 value 的索引地址），合并 value 也只是刪掉老的 value 即可，甚至不需要和 key 的合并同步進行，定期清理下就行了。而且因為 key 單獨存放，所以遍歷 key 和測試 key 是否存在也會快很多。不過如果 value 長度很小，那么分開存放反而增加了一次隨機讀，這是要結合實際項目來考慮的。
我測試發(fā)現(xiàn)隨機讀確實挺快，大概是 RocksDB 的 100 倍；但隨機寫沒有太大優(yōu)勢，和 universal 的 RocksDB 差不多，而后者可以關閉 WAL 以大幅提高寫入速度。

雖然空間占用比 RocksDB 要高一些（大概 10%），但是打開數(shù)據(jù)庫的速度卻要快幾倍，也許是只需要加載 key 的原因。
而在內(nèi)存占用方面，BadgerDB 比 RocksDB 更吃內(nèi)存些，并且隨著數(shù)據(jù)量的增長，占用的內(nèi)存也越來越多，如果物理內(nèi)存不夠的話，就會使用 SWAP，并導致寫入速度變慢。

在我的 SSD 上測試時發(fā)現(xiàn) LoadToRAM 和 MemoryMap 相對于 FileIO 沒有太大的優(yōu)勢，但是內(nèi)存占用會多很多，所以我將默認的配置各降了一級：

opts.TableLoadingMode = options.MemoryMap
opts.ValueLogLoadingMode = options.FileIO

對于內(nèi)存足夠的場景而言，BadgerDB 確實是一個很好的 RocksDB 替代品，因為大部分情況下是讀多寫少的。而它的缺點也很明顯，只有 Go 語言的版本，沒有其他語言的 binding。

TerarkDB

最后一個吸引我眼球的是 TerarkDB。它在 RocksDB 的基礎上進行了改進，將所有 key 進行了可檢索壓縮，這個壓縮算法能在不解壓的情況下進行搜索，而 value 則進行了可定點訪問的壓縮，可以直接定位并解壓需要的部分。這種實現(xiàn)使得緩存能更高效地使用，也能利用上 SSD 的隨機讀較快的優(yōu)點，相當于把很多需要讀磁盤的操作在內(nèi)存中搞定了。另外，全局壓縮比 RocksDB 使用的塊壓縮的壓縮率更高，所以需要寫入的數(shù)據(jù)會減少，也會改善寫入速度。而在合并時，它選擇采用 universal 的風格以減少寫入放大。
它最大的缺點就是核心代碼沒有開源，壓縮算法也是專利，需要購買商業(yè)版來使用，所以我就不測試了。