TRIAD: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores

TRIAD（USENIX ATC17），一個新的 LSM key-value 存儲引擎，開發這個引擎的公司叫 Nutanix，用 RocksDB 做核心企業系統 metadata 的管理。TRIAD 的設計以該公司的需求為基礎，出身於工業界的產品會有較強的可參考性。

With these workloads, TRIAD yields up to 193% improvement in throughput. It reduces write amplification by a factor of up to 4x, and decreases the amount of I/O by an order of magnitude.

通過某些優化，減少寫放大，減少 IO，blablabla，基本所有 paper 都如是。作為讀者面對這種說辭我們首先應該想到：

  1. 使用的機制是否好實現，侵入性小，或者複雜度和收益的性價比足夠高
  2. 基於什麼樣的 workload，是否具有實用價值，是否會對 common case 帶來負面影響

The first technique decreases compaction overhead for skewed workloads. We keep KV pairs that are updated frequently (i.e., hot entries) in the memory component, and we only flush the cold entries.

Paper $3.1 Data skew unawareness

第一個優化點是針對冷熱數據寫差別較大的場景（skewed workload），熱數據的頻繁更新會導致 memtable 很小而 commit log 卻很大，為了避免日誌過多而導致資料庫重啟恢復時間（recovery time）增加， memtable 必須頻繁地 flush 從而讓 commit log 可以清掉，而這對性能是一種損失。這點在 rocksdb wiki: memtable flush 中有詳細介紹，相關配置項為 (max_total_wal_size)。當然，memtable 達到一定大小也不可避免會被 flush，相關配置項為 (write_buffer_size)。

Paper $4.1 TRIAD-MEM

TRIAD-MEM tackles the data skew unawareness issue at the memory component level.

大概做法是，原來 rocksdb 只是簡單將數據從 memtable 轉移到 L0 SST；現在 TRIAD 改成只有冷數據轉移至 L0，熱數據保留在 memtable 原地不動，同時將這些熱數據寫一份到 commit log，此前的日誌都可以刪掉，這樣就解決了日誌膨脹的問題。

可以看到，後者的優勢在於熱數據仍然存留在 memtable，未來對它們的更新都會提前在內存中被 merged，日誌的 compaction 比 SST 的 compaction 更快也更簡單，直接刪文件即可，不需要讀文件。

舉個例子，我們假設一種極端情況，全部數據有 100k 條，每條 64KB，，其中固定 1k 條數據為熱數據，其餘 99k 條都為冷數據（1:99）。我們讓 max_total_wal_size=128MB，write_buffer_size=128MB，2k 的寫剛好可以塞滿 commit log。

在 2k 次寫之後，memtable 有 2k*1%=20 條冷數據，1k 條熱數據。20 條冷數據會被寫到 L0，memtable 剩下 1k 條。由於此時 commit log 已滿，1k 條數據會被寫到 commit log，舊日誌被刪掉。總的寫 IO = 2k log writes + 20 L0 writes + 1k log rewrites = 3k writes

而如果是在 rocksdb 下，寫 IO = 2k log writes + 1020 L0 writes + 1k compaction writes = 4k writes，顯然上述優化減小了寫放大。

Paper $4.2 TRIAD-DISK

使用 hyperloglog 來判斷是否應該進行 L0 和 L1 的 compaction。每個 L0 SST 文件頭存一個 HLL，可以推算如果 L0 和 L1 的 overlap ratio 大於給定 threshold，則進行 L0/L1 compaction。由於沒有具體演算法，不詳述。

有一點是 Cassandra 倒是用了 HLL 來確定 L0 的哪個文件 overlap ratio 最高。簡單就是 overlap ratio = UniqueKeys(fi) / SumKeys(fi)。最高的先做 compaction。我在reddit/rocksdb三年前的帖子里也發現了相關討論。

Paper $4.3 TRIAD-LOG

核心思想是把 commit log 當做 SST 來用。因為 commit log 有一份持久化數據，L0 SST 再寫一份的話是一種浪費（Paper $3.3 Duplicate writes）。把日誌文件直接 rename 成 SST 豈不美哉？

有個困難是，SST 是排好序的，我們可以在內存中維護 key -> latest log offset 的映射，這樣對 point read 沒有影響，但對 range read 影響很大。

基本上這個思想和 wisckey 很接近，已經被完整討論過，不做詳述。

Conclusion

個人覺得整篇 paper 最好的 idea 是 TRIAD-MEMTABLE，但因為這個 case 不夠 attractive，可能工程價值不大。整個項目開源在 github.com/epfl-labos/T ，有興趣可以看。

推薦閱讀：

相关文章