详解RocksDB如何通过组提交提升性能
详解RocksDB如何通过组提交提升性能
0. Intro
从维基百科的ACID词条，我们可以看到：
ACID，是指数据库管理系统（DBMS）在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。
特别地，为了保证事务的原子性和持久性，在对数据库内存中维护的各种数据结构修改之前，会将该事务的对数据库的所有操作信息先写入磁盘中日志文件，这个过程被称为预写日志(Write-Ahead Logging，缩写为WAL)。当数据库发生崩溃时，预写日志也可以作为故障恢复的依据。
而假如每次提交事务需要调用一次fsync将日志刷入磁盘，而一次fsync本身是开销是比较大的，那么事务提交将是数据库的一个瓶颈。而当好几个事务要提交时，将它们合并一次fsync来做，即可以显著提高数据库系统的TPS，这也是Group Commit的含义。
1. RocksDB的写过程
MyRocks的写入过程分成以下三步：
- 将一条或者多条操作的记录封装到WriteBatch
- 将记录对应的日志写到WAL文件中
- 将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如下：
- 写WAL：leader线程本身与follower线程的操作记录由leader线程负责批量写入WAL文件。
- 写memtable: 在设置allow_concurrent_memtable_write时，由leader线程通知所有follower线程并发写入memtable；否则，由leader线程串行将所有follower线程的操作写入memtable中。
这里存在另一个问题，leader是怎么选出来并且是怎么进行Group Commit？
当写线程要提交事务时会将自己对应的Write实例添加到Write链表的尾部。 此时存在一种特殊情况，即当前待提交的线程是加入Write链表的第一个线程。在RocksDB的逻辑中，第一个加入链表的线程将成为leader线程。
当线程成为leader线程之后，将开始进入提交逻辑(以下简略部份逻辑)：
- 调用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中。
- 检查是否可以并发写入memtable，条件有：1. memtable本身支持；2. 没有merge操作 3. 设置allow_concurrent_memtable_write
- 写WAL文件，将write_group合并成一个新的WriteGroup实例merge_group，将merge_group中的记录fsync到WAL文件中。
- 如果不支持并发写memtable，则由leader串行将write_group的所有数据串行地写到memtable；否则，leader线程将通过调用LaunchParallelMemTableWriter函数通知所有的follower线程并发写memtable。
- 待所有的线程（不管leader线程或者follower线程）写完memtable，都会调用CompleteParallelMemTableWriter判断自己是否是最后一个完成写memtable的线程，如果不是最后一个则等待被通知；如果是最后一个是follower线程，通过调用ExitAsBatchGroupFollower函数，调用ExitAsBatchGroupLeader通知所有follower可以退出，并且通知leader线程。如果最后一个完成的是leader线程，则可以直接调用ExitAsBatchGroupLeader函数。
- 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