详解RocksDB如何通过组提交提升性能

0. Intro

从维基百科的ACID词条，我们可以看到：

ACID，是指数据库管理系统（DBMS）在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。

特别地，为了保证事务的原子性和持久性，在对数据库内存中维护的各种数据结构修改之前，会将该事务的对数据库的所有操作信息先写入磁盘中日志文件，这个过程被称为预写日志(Write-Ahead Logging，缩写为WAL)。当数据库发生崩溃时，预写日志也可以作为故障恢复的依据。

而假如每次提交事务需要调用一次fsync将日志刷入磁盘，而一次fsync本身是开销是比较大的，那么事务提交将是数据库的一个瓶颈。而当好几个事务要提交时，将它们合并一次fsync来做，即可以显著提高数据库系统的TPS，这也是Group Commit的含义。

1. RocksDB的写过程

MyRocks的写入过程分成以下三步：

1. 将一条或者多条操作的记录封装到WriteBatch
2. 将记录对应的日志写到WAL文件中
3. 将WriteBatch中的一条或者多条记录写到内存中的memtable中

其中，每个WriteBatch代表一个事务，可以包含多条操作，可以通过调用WriteBatch::Put/Delete等操作将对应多条的key/value记录加入WriteBatch中。

2. RocksDB的Group Commit

同样地，为了提高提交的性能，RocksDB引擎也使用Group Commit的机制。

每个写线程都会生成一个WriteThread::Write的实例，关联到对应的一个WriteBatch。

Write的数据结构如下：

struct Writer {
    WriteBatch* batch;
    bool sync;
    bool no_slowdown;
    bool disable_wal;
    bool disable_memtable;
    uint64_t log_used;  // log number that this batch was inserted into
    uint64_t log_ref;   // log number that memtable insert should reference
    WriteCallback* callback;
    bool made_waitable;          // records lazy construction of mutex and cv
    std::atomic<uint8_t> state;  // write under StateMutex() or pre-link
    WriteGroup* write_group;
    SequenceNumber sequence;  // the sequence number to use for the first key
    Status status;            // status of memtable inserter
    Status callback_status;   // status returned by callback->Callback()
    std::aligned_storage<sizeof(std::mutex)>::type state_mutex_bytes;
    std::aligned_storage<sizeof(std::condition_variable)>::type state_cv_bytes;
    Writer* link_older;  // read/write only before linking, or as leader
    Writer* link_newer;  // lazy, read/write only before linking, or as leader
}

可以看到它也是一个链表的结构，待提交的事务可以通过JoinBatchGroup(&w)函数将本WriteBatch对应的Write实例加到Write链表中。自然地，Write链表中的一个元素代表着一个待提交的写线程。写到WAL文件中的内容有先后顺序，这里也只需要按照链表中的先后顺序写入即可。多个Write对象的实例同样合并成一个写WAL操作，由一个线程负责进行fsync即可。

这里存在一个问题，由哪个线程来负责进行fsync操作将操作记录写入WAL文件中？

RocksDB将待提交阶段的线程分成两种: leader线程和follower线程。存在leader线程的Group Commit如下：

1. 写WAL：leader线程本身与follower线程的操作记录由leader线程负责批量写入WAL文件。
2. 写memtable: 在设置allow_concurrent_memtable_write时，由leader线程通知所有follower线程并发写入memtable；否则，由leader线程串行将所有follower线程的操作写入memtable中。

这里存在另一个问题，leader是怎么选出来并且是怎么进行Group Commit？

当写线程要提交事务时会将自己对应的Write实例添加到Write链表的尾部。 此时存在一种特殊情况，即当前待提交的线程是加入Write链表的第一个线程。在RocksDB的逻辑中，第一个加入链表的线程将成为leader线程。

当线程成为leader线程之后，将开始进入提交逻辑(以下简略部份逻辑)：

1. 调用WriteThread::EnterAsBatchGroupLeader函数，由leader线程构造一个WriteGroup对象的实例，WriteGroup对象的实例用于描述当作Group Commit要写入WAL的所有内容。
   • 确定本批次要提交的最大长度max_size。如果leader线程要写入WAL的记录长度大于128k，则本次max_size为1MB；如果leader的记录长度小于128k, 则max_size为leader的记录长度+128k。
   • 找到当前链表中最新的Write实例newestwriter，通过调用CreateMissingNewerLinks(newest_writer)，将整个链表的链接成一个双向链表。
   • 从leader所在的Write开始遍历，直至newestwrite。累加每个writer的size，超过max_size就提前截断；另外地，也检查writer的一些flag，与leaer不一致也提前截断。将符合的最后的一个write记录到WriteGroup::last_write中。
2. 检查是否可以并发写入memtable，条件有：1. memtable本身支持；2. 没有merge操作 3. 设置allow_concurrent_memtable_write
3. 写WAL文件，将write_group合并成一个新的WriteGroup实例merge_group，将merge_group中的记录fsync到WAL文件中。
4. 如果不支持并发写memtable，则由leader串行将write_group的所有数据串行地写到memtable；否则，leader线程将通过调用LaunchParallelMemTableWriter函数通知所有的follower线程并发写memtable。
5. 待所有的线程（不管leader线程或者follower线程）写完memtable，都会调用CompleteParallelMemTableWriter判断自己是否是最后一个完成写memtable的线程，如果不是最后一个则等待被通知；如果是最后一个是follower线程，通过调用ExitAsBatchGroupFollower函数，调用ExitAsBatchGroupLeader通知所有follower可以退出，并且通知leader线程。如果最后一个完成的是leader线程，则可以直接调用ExitAsBatchGroupLeader函数。
6. ExitAsBatchGroupLeader函数除了通知follower线程提交已经完成，还有另一个作用。在这一轮Group Commit进行过程中，writer链表可能新添加了许多待提交的事务。当退出本次Group Commit之前，如果writer链表上有新的待提交的事务，将它设置成leader。这个成为leader的线程将被唤醒，重复leader线程进行Group Commit的逻辑。

writer对象在Group Commit过程中有如下几种状态：

• STATE_INIT：write的初始状态
• STATE_GROUP_LEADER：被选为leader
• STATE_MEMTABLE_WRITER_LEADER：负责串行地将所有follower写入memtable的leader
• STATE_PARALLEL_MEMTABLE_WRITER：并发写memtable的follower
• STATE_COMPLETED：Group Commit完成
• STATE_LOCKED_WAITING：write等待自己状态变化

以下为简化的writer的状态变化图

3. 小结

本文介绍RocksDB存储引擎在写入数据时Group Commit的机制。

4. 参考资料

ACID: https://zh.wikipedia.org/wiki/ACID