RocksDB 是 LSM-tree 結(jié)構(gòu)的 KV 存儲，寫入的數(shù)據(jù)先通過 WAL 持久化，再寫入到 memtable 中。WAL 的寫入需要保證順序性，只能由單個(gè)線程來進(jìn)行操作。但 memtable 在設(shè)計(jì)上是一個(gè)支持無鎖并發(fā)的 skiplist，可以通過多線程寫入進(jìn)行加速。為了提升寫入性能，RocksDB 引入了 group write 機(jī)制。

RocksDB group WAL write workflow

詳細(xì)流程

流程圖引用于SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage，本文將以流程圖的大致順序進(jìn)行展開討論。

Join Batch Group

對應(yīng)流程圖中的 1、2、3 步驟。第一個(gè)進(jìn)入到 batch group 的寫線程會成為 leader，隨后進(jìn)入到 batch group 的寫線程則作為 leader 線程。link as leader 的過程十分簡單，成功成為 leader 的線程會成功設(shè)置 newest_writer 變量，其余的 follower 線程則會以鏈表的形式將自己加入到 leader 的 writer 成員中。leader 線程會繼續(xù)執(zhí)行后續(xù)的 WAL 寫入操作，follower 線程將會等待 leader 線程通知。follower 線程的等待采用了自旋+條件變量的方式進(jìn)行，首先嘗試在原子變量上進(jìn)行一個(gè)短時(shí)間的自旋，再嘗試掛起進(jìn)程在 condition variable 上進(jìn)行等待。

bool WriteThread::LinkOne(Writer* w, std::atomic<Writer*>* newest_writer) {
  assert(newest_writer != nullptr);
  assert(w->state == STATE_INIT);
  Writer* writers = newest_writer->load(std::memory_order_relaxed);
  while (true) {
...
    w->link_older = writers;
    if (newest_writer->compare_exchange_weak(writers, w)) {
      return (writers == nullptr);
    }
  }
}

Write WAL

對應(yīng)流程圖中 4 步驟。因?yàn)?WAL 的寫入需要保證不同 batch group 之間寫入的順序性，只能通過單線程進(jìn)行寫入，因此leader 線程會執(zhí)行具體的 WAL 操作。在互斥鎖的保護(hù)之下，leader 線程會收集自身和來自 follower 線程的 writer，合并稱一個(gè) batch，并設(shè)置 batch 一個(gè) seq 值，隨后寫入 WAL 文件并進(jìn)行 fsync 操作。需要說明的是，每一個(gè) batch group 都會有一個(gè) leader 線程，但不同的 batch group leader 線程是互斥的，這一點(diǎn)由互斥鎖來保證。

Insert Into MemTables

leader 線程完成 WAL 寫入后，喚醒 follower 線程。隨后，leader 線程和 follower 線程均開始并行地執(zhí)行 memtable 寫操作。RocksDB 的 memtable 采用無鎖設(shè)計(jì)，通過 CAS 操作支持并發(fā)寫入。每個(gè)寫入線程的 writer 在開始寫入前會被賦值一個(gè) seq，保證每個(gè)線程寫入 key 的唯一性，因此無需考慮并發(fā)寫入導(dǎo)致 key 覆蓋的問題，這是 RocksDB 相對于其他存儲引擎的一大優(yōu)勢。

Complete

leader 線程會等待 batch group 所有的線程執(zhí)行完成，隨后退出，完成一個(gè) batch group 的寫入。