知識星球（點選上方公眾號，可快速關註）
來源：keakon的塗鴉館 ，
www.keakon.net/2018/07/13/key%20/%20value%20資料庫的選型
引言
一直以來在我的觀念中，key/value 資料庫就三種選項：
-
記憶體可存放：Redis
-
單機磁碟可存放：RocksDB
-
超過 TB 級：Cassandra、HBase……
然而在實際專案中使用 RocksDB 時，才發現了一堆問題，折騰許久才搞定。
使用 RocksDB 的背景
先介紹下我使用 RocksDB 的背景。
這個專案有很多 key/value 資料（約 100 GB）需要使用，使用時基本是隻讀的，偶爾更新時才會批次匯入，且可以忍受短暫的停機匯入。我一想 TiKV 和 Pika 等很多 key/value 資料庫都選用了 RocksDB，應該是比較靠譜的，於是就選它了。
接著就發現這東西的編譯依賴有點多。我的專案是用 Go 寫的，而這個玩意需要安裝一堆 C 庫，並且不能交叉編譯到其他平臺。不但不能在 Mac OS X 上編譯 Linux 的版本，甚至 Ubuntu 16.04 上編譯的都不能在 CentOS 7 上執行（後者的 GCC 版本較低，動態連結庫版本也低）。因為懶得降級 GCC，最後我選擇用 docker 來編譯了。
而且我發現資料量小時還挺快，但是資料量大了就越來越慢。平時插入 10 萬條資料（約 50 MB）大概 0.2 ~ 0.5 秒，但一段時間後就會持續遇到需要幾秒甚至幾十秒的情況。
於是我又開始尋找其他的替代品，諸如 LMDB、BadgerDB 和 TerarkDB 等。在這個過程中我開始瞭解到它們實現的原理，也算有不少收穫。
傳統的關係型資料庫大多是使用 B+ 樹，這種資料結構可以很快地進行順序讀寫，也能以 O(log(N)) 的時間複雜度來進行隨機讀，但不適合隨機寫（會導致 B+ 樹重新調整平衡，造成寫放大）。
而 LevelDB 引入了 LSM 樹，就是為瞭解決 B+ 樹隨機寫效能低的問題，它把隨機寫以跳躍表的形式保留在記憶體中（memtable），積累到足夠的大小就不再改寫它了，並將其寫入到磁碟（L0 SST file），這樣就只有順序寫了。因為 memtable 和 L0 中的資料可能會重覆，而且 key 很分散，所以搜尋時需要遍歷它們。如果沒找到的話，還要向下層查詢（關於層數下文會解釋），不過 L1 之後的 SST file 都是有序分段的，因此可以用二分查詢來找到 key 所在的資料檔案，再在這個檔案中用二分查詢來找到這個 key。為了降低搜尋的代價，RocksDB 還使用了 Bloom filter 來判斷資料是否在某個檔案中（有誤判，但能顯著減少需要搜尋的檔案數）。由此可見，LSM 樹對寫入做了最佳化，但降低了隨機讀的效能，順序讀則和 B+ 樹差不多。
此外，L0 的資料可能會有很多過期資料（被更新或刪除過），因此需要在達到閾值後進行合併（compact），去掉這些重覆和無效的資料，並寫入 L1。而 L1 也可能會有過期的資料，也需要被合併寫入 L2……這就相當於資料要多次寫入不同的檔案中，也就造成了寫放大。而合併不重疊的資料檔案是很快的，因此順序寫還是要比隨機寫快，但合併可以在其他執行緒中執行，在不會持續隨機寫入大量資料的情況下，基本能保持 O(1) 的寫入。
事實上，我遇到的 RocksDB 變慢的問題就是 compact 引起的，預設配置下它只使用一個執行緒來 compact，如果 compact 跟不上寫入的速度，RocksDB 就會降低寫入速度，甚至停止寫入。考慮到我的電腦有 4 個核，於是我把執行緒數改成了 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”)
修改後就發現插入時間基本穩定在 0.2 ~ 0.5 秒之間了，CPU 佔用率超過了 400%，磁碟寫入速度超過了 800 MB/s……
另外，RocksDB 還提供了 db.GetProperty(“rocksdb.stats”) 這個方法來檢視狀態，需要關註的資料主要有 W-Amp（寫入放大倍數）和 Stalls（因為 compact 而降速）。
RocksDB 有 3 種 compact 的方式：leveled、universal 和 FIFO。
Leveled
Leveled 是從 LevelDB 繼承過來的傳統形式，也就是當一層的資料檔案超過該層的閾值時，就往它的下層來 compact。L0 之間因為可能有重覆的資料，因此需要全合併後寫入 L1。而 L1 之後的資料檔案不會有重覆的 key，因此在 key 範圍不重合的情況下，可以併發地向下合併。RocksDB 預設有 L0 ~ L6 這 7 層，L1 容量是 256 MB（建議把 L0 和 L1 大小設為一樣，可以減小寫入放大），之後每層都是上一層容量的 10 倍。很顯然，層數越高就表示寫入放大倍數越高。
Universal
那麼可不可以不分這麼多層，以減小寫入放大倍數呢？Universal 這種風格就是儘量只用 L0，並將新的 SST 不斷合併到老的 SST，因此資料檔案的大小是不等的。但單個 SST 也是有上限的，不然記憶體扛不住，二分查詢也會變慢，於是達到上限時，就往 L6 寫，而 L0 以外的層不會有重疊的 key 範圍，所以合併時只需要簡單地拼接就行了。如果 L6 也不夠用，就繼續往 L5、L4 等層寫入。這種策略增大了每層能容納的大小，並且因為先寫 L6，而 L6 是容量最大的，資料量較小時就不需要用到 L5 等其他層了，也就減少了層數，對應著也就降低了寫入放大倍數。但是因為 L0 的上限變大了，單個 SST 的上限也變大了，所以讀效能可能會稍微下降（部分情況下因為層數和 SST 少，讀取速度可能更快）。此外，L0 變大也會影響開啟資料庫的耗時，因為需要讀取到記憶體中。
FIFO
FIFO 嚴格來說不算是合併策略，它的做法是所有的資料都放在 L0，當資料量達到上限時，就把最老的 SST 刪掉。它還能搭配 TTL 使用，也就是優先把過期時間較早的資料刪掉。這種策略一般只用於快取，但是對於不超過記憶體容量的快取，我更傾向於放 Redis 裡。
TiKV 和 Pika 都選擇了 leveled 風格，也是 RocksDB 的預設值，應該是適合大部分情況的。但如果需要更高的寫入效能，並且總資料容量不大（例如少於 100 GB），可以選擇 universal。
其實 RocksDB 還有挺多可以調優的引數，但是都需要做測試，在 SSD 和 HDD 上表現也可能不一樣，這裡我只列幾點：
在我的電腦上（用 SSD），允許 MMAP 讀取會稍微拖慢讀取速度，允許 MMAP 寫入可以稍微加快寫入速度。設定合理的 block cache 可以加快讀取速度，而填充讀快取則可以加快頻繁訪問的 key 讀取。關閉 WAL 會極大地加快寫入速度（時間約減少 1/3），因為需要寫入的資料量少了一半，對於不是實時寫入的場景（例如批次匯入）推薦關閉。
RocksDB 還提供了一個 Column Family 的功能，設計上就和 MySQL 的分表差不多，就是人為地將資料分散到多個 Column Families 中（例如按 key 的首位元組或 hash 來分庫），使多個 Column Families 可以併發讀寫。相對於手動分到多個 db 而言，利用 Column Family 可以原子性地操作多個 Column Families 中的資料，並且能保持它們在一個事務中的一致性。
RocksDB 就講到這裡，接下來看看其他的選項。
LMDB
我最先看中的是 LMDB，因為很多評測都說它比 RocksDB 更快，效能波動更小。它的原理是用 MMAP 將資料檔案對映到記憶體中，也就避免了寫入時的系統呼叫（實際上 RocksDB 將資料合併後一次性的順序寫也沒有多少開銷），但是一頁（4 KB）只能存放 2 條資料，而且不會進行塊壓縮，所以比較費空間；資料結構選的是 B+ 樹，因此讀效能是很好的。
直覺上我覺得 B+ 樹的隨機寫入會很慢，實際測試確實如此，並且隨著資料量的增大，寫入速度基本是指數級下降的，於是果斷放棄了。
BadgerDB
接著就找到了 BadgerDB，它的原理和 LevelDB 差不多，但是又做了個重要的最佳化：將 key 和 value 分開存放。因為 key 的空間佔用會小很多，所以更容易放入記憶體中，能加快查詢速度。而在合併時，合併 key 的開銷很小（只是修改 value 的索引地址），合併 value 也只是刪掉老的 value 即可，甚至不需要和 key 的合併同步進行，定期清理下就行了。而且因為 key 單獨存放，所以遍歷 key 和測試 key 是否存在也會快很多。不過如果 value 長度很小，那麼分開存放反而增加了一次隨機讀，這是要結合實際專案來考慮的。
我測試發現隨機讀確實挺快，大概是 RocksDB 的 100 倍；但隨機寫沒有太大優勢，和 universal 的 RocksDB 差不多，而後者可以關閉 WAL 以大幅提高寫入速度。
雖然空間佔用比 RocksDB 要高一些（大概 10%），但是開啟資料庫的速度卻要快幾倍，也許是隻需要載入 key 的原因。
而在記憶體佔用方面，BadgerDB 比 RocksDB 更吃記憶體些，並且隨著資料量的增長，佔用的記憶體也越來越多，如果物理記憶體不夠的話，就會使用 SWAP，並導致寫入速度變慢。
在我的 SSD 上測試時發現 LoadToRAM 和 MemoryMap 相對於 FileIO 沒有太大的優勢，但是記憶體佔用會多很多，所以我將預設的配置各降了一級：
opts.TableLoadingMode = options.MemoryMap
opts.ValueLogLoadingMode = options.FileIO
對於記憶體足夠的場景而言，BadgerDB 確實是一個很好的 RocksDB 替代品，因為大部分情況下是讀多寫少的。而它的缺點也很明顯，只有 Go 語言的版本，沒有其他語言的 binding。
TerarkDB
最後一個吸引我眼球的是 TerarkDB。它在 RocksDB 的基礎上進行了改進，將所有 key 進行了可檢索壓縮，這個壓縮演演算法能在不解壓的情況下進行搜尋，而 value 則進行了可定點訪問的壓縮，可以直接定位並解壓需要的部分。這種實現使得快取能更高效地使用，也能利用上 SSD 的隨機讀較快的優點，相當於把很多需要讀磁碟的操作在記憶體中搞定了。另外，全域性壓縮比 RocksDB 使用的塊壓縮的壓縮率更高，所以需要寫入的資料會減少，也會改善寫入速度。而在合併時，它選擇採用 universal 的風格以減少寫入放大。
它最大的缺點就是核心程式碼沒有開源，壓縮演演算法也是專利，需要購買商業版來使用，所以我就不測試了。
總結
綜上，對於幾十 GB ~ 幾百 GB 的 key / value 資料而言，如果只使用 Go 來開發的話，BadgerDB 在很多情況下是很好的選擇，否則也只剩 RocksDB 了。
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
