【LevelDB 源码阅读】05 WriteBatch:原子写的载体

db/write_batch.cc 开头的格式注释是全篇最重要的一段信息（write_batch.cc:5-14）：

// WriteBatch::rep_ :=//    sequence: fixed64//    count: fixed32//    data: record[count]// record :=//    kTypeValue varstring varstring         |//    kTypeDeletion varstring// varstring :=//    len: varint32//    data: uint8[len]

翻译一下：头部 12 字节——8 字节序列号（小端 fixed64）加 4 字节条目数（小端 fixed32）；头部后面是 count 条变长 record，每条以 1 字节 tag 开头，kTypeValue（值是 0x1）后面跟两段“长度前缀字符串”（key、value），kTypeDeletion（值是 0x0）后面只跟 key。这两个 tag 值定义在 dbformat.h:54：

enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 };

顺带提一嘴：这不是 WriteBatch 专用的枚举，MemTable 里的每条记录、SSTable 里的每条 KV，用的都是同一对 type 值——一个编码从 batch 一路贯穿到最终的磁盘文件，后面讲 InternalKey 时会再遇到它。

构造函数只是调用 Clear()（write_batch.cc:29），而 Clear 是把 rep_ 清空后 resize 出 12 个字节（write_batch.cc:35-38）：一个新生的 batch 就是 12 个零字节，seq 是 0，count 是 0。

void WriteBatch::Clear() {  rep_.clear();  rep_.resize(kHeader);}

往 WriteBatch 里写入数据的代码同样十分简单。Put（write_batch.cc:98-103）：

void WriteBatch::Put(const Slice& key, const Slice& value) {  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);  rep_.push_back(static_cast<char>(kTypeValue));  PutLengthPrefixedSlice(&rep_, key);  PutLengthPrefixedSlice(&rep_, value);}

Delete（write_batch.cc:105-109）方法就少了一段操作 value 的代码：

void WriteBatch::Delete(const Slice& key) {  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);  rep_.push_back(static_cast<char>(kTypeDeletion));  PutLengthPrefixedSlice(&rep_, key);}

count 加一，tag 一字节，key 和 value 各自带上变长长度前缀，追加，结束。没有其它操作——往 WriteBatch 里 Put 同一个 key 一百次，它就老老实实存一百条 record。头文件的注释特意强调了顺序语义（write_batch.h:7-14）：

// The updates are applied in the order in which they are added// to the WriteBatch.  For example, the value of "key" will be "v3"// after the following batch is written:////    batch.Put("key", "v1");//    batch.Delete("key");//    batch.Put("key", "v2");//    batch.Put("key", "v3");

为什么“按加入顺序生效”能成立？答案在序列号的分配方式上，下一节展开。

把短链“三合一”batch 的字节画出来（假设它分到的序列号是 1）：

偏移    字节                         含义------  ---------------------------  -------------------------------0       01 00 00 00 00 00 00 00      seq = 1        （fixed64，8B）8       03 00 00 00                  count = 3      （fixed32，4B）12      01                           kTypeValue13      07                           key_len = 7    （varint32）14      "c:Ab3xK"                    key21      23                           val_len = 35   （varint32，0x23）22      "https://example.com/..."    value（35B）57      01                           kTypeValue58      0f                           key_len = 1559      "u:robin:c:Ab3xK"            key74      01                           val_len = 175      "1"                          value76      01                           kTypeValue77      0d                           key_len = 1378      "c:Ab3xK:click"              key91      01                           val_len = 192      "0"                          value------  ---------------------------  -------------------------------93                                   总计 93 字节

三个逻辑写入，93 字节，不需要标记事务“开始/结束”，原子性靠后续流程保证这一批数据要么同时成功，要么同时失败。

还有个细节值得注意：seq 在这份布局里占了头 8 个字节，但用户 API 里对它完全无感——构造出来是 0，Put / Delete 也不更新它。它是留给 Write 路径的，调用方塞完数据把 batch 交出去之后，库会回头来填这个字段。

写侧是纯追加，读侧是 Iterate（write_batch.cc:42-80）：跳过 12 字节头，循环读 tag、按 tag 解出 key/value、回调 Handler 的对应方法：

Status WriteBatch::Iterate(Handler* handler) const {  Slice input(rep_);  if (input.size() < kHeader) {    return Status::Corruption("malformed WriteBatch (too small)");  }  input.remove_prefix(kHeader);  Slice key, value;  int found = 0;  while (!input.empty()) {    found++;    char tag = input[0];    input.remove_prefix(1);    switch (tag) {      case kTypeValue:        if (GetLengthPrefixedSlice(&input, &key) &&            GetLengthPrefixedSlice(&input, &value)) {          handler->Put(key, value);        } else {          return Status::Corruption("bad WriteBatch Put");        }        break;      case kTypeDeletion:        if (GetLengthPrefixedSlice(&input, &key)) {          handler->Delete(key);        } else {          return Status::Corruption("bad WriteBatch Delete");        }        break;      default:        return Status::Corruption("unknown WriteBatch tag");    }  }  if (found != WriteBatchInternal::Count(this)) {    return Status::Corruption("WriteBatch has wrong count");  } else {    return Status::OK();  }}

注意两点。

// WriteBatchInternal provides static methods for manipulating a// WriteBatch that we don't want in the public WriteBatch interface.

一批不想暴露给用户的内部操作：Count / SetCount、Sequence / SetSequence、Contents / SetContents、ByteSize、InsertInto、Append。前几个的实现就是对着 rep_ 的固定位置做定点读写（write_batch.cc:82-96）：

int WriteBatchInternal::Count(const WriteBatch* b) {  return DecodeFixed32(b->rep_.data() + 8);}SequenceNumber WriteBatchInternal::Sequence(const WriteBatch* b) {  return SequenceNumber(DecodeFixed64(b->rep_.data()));}void WriteBatchInternal::SetSequence(WriteBatch* b, SequenceNumber seq) {  EncodeFixed64(&b->rep_[0], seq);}

现在可以回答上一节遗留的的问题了：batch 的 seq 头是什么时候填的？回到 04 篇读过的 DBImpl::Write，leader 合并完之后有这三行（db_impl.cc:1220-1222）：

WriteBatch* write_batch = BuildBatchGroup(&last_writer);WriteBatchInternal::SetSequence(write_batch, last_sequence + 1);last_sequence += WriteBatchInternal::Count(write_batch);

假设当前全局序列号是 s，这个 batch 有 n 条 record：头部 seq 被填成 s+1，然后全局序列号一口气推进 n，变成 s+n。也就是说，这个 batch 占用了 [s+1, s+n] 这一段连续序列号。

序列号具体怎么落到每条 record 上？看 InsertInto（write_batch.cc:132-137）和它用的 Handler（write_batch.cc:115-130）：

// write_batch.cc:132-137Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) {  MemTableInserter inserter;  inserter.sequence_ = WriteBatchInternal::Sequence(b);  inserter.mem_ = memtable;  return b->Iterate(&inserter);}

// write_batch.cc:115-130namespace {class MemTableInserter : public WriteBatch::Handler { public:  SequenceNumber sequence_;  MemTable* mem_;  void Put(const Slice& key, const Slice& value) override {    mem_->Add(sequence_, kTypeValue, key, value);    sequence_++;  }  void Delete(const Slice& key) override {    mem_->Add(sequence_, kTypeDeletion, key, Slice());    sequence_++;  }};}  // namespace

sequence_ 从批头那个 seq 出发，每回调一次自增一。批内第 1 条 record 拿 s+1，第 2 条拿 s+2……第 n 条拿 s+n，严格按加入顺序。这些序列号跟着 key 一起进 MemTable：MemTable::Add（memtable.cc:76）把每个 user key 拼上一个 8 字节尾巴，尾巴由 EncodeFixed64(p, (s << 8) | type) 编码（memtable.cc:93）——56 位序列号压在高位，8 位 ValueType 留在低位，这也是 kMaxSequenceNumber = (1 << 56) - 1（dbformat.h:67）的来历。同一个 user key 的多条版本靠这个尾巴分出新旧，具体的排序规则后面会详细讲解。

到这里，头文件那个“v3 例子”的机制就理顺了：Put v1、Delete、Put v2、Put v3 在批内依次拿到递增的序列号，而读取时同 key 的新序列号永远盖过旧序列号——所以最后留下的是 v3。顺序语义不是靠“执行顺序”保证的，是靠序列号的大小关系保证的，即使这四条操作被写进 SSTable、经过 Compaction 反复搬运，这个大小关系都不变。

序列号的连续分配还说明：一个 batch 的所有 record 共享同一个可见点。DBImpl::Get 在持锁状态下取 versions_->LastSequence() 作为本次读取的可见上界（db_impl.cc:1124），而 Write 是在整批 InsertInto 完成之后才调 SetLastSequence 发布新序列号（db_impl.cc:1251）。于是并发的读线程要么看到整批，要么一条都看不到，不存在“看见了第 1 条、看不见第 2 条”的中间态——哪怕 MemTableInserter 是一条一条往跳表里插的。（跳表本身支持无锁读，细节过两篇展开。）

还有一个小发现：Iterate 是 const 方法，InsertInto 拿到的却是非 const 的 sequence_——每条 record 的序列号不存在 record 里，而是遍历时现场数出来的。每条 record 里如果存 seq 要多 8 字节 × n 条，而“批头一个 seq + 顺序计数”把这份冗余全省了。代价是 Iterate 不能随机跳到第 i 条，必须从头数——对这个一次顺序遍历到底的场景，不构成问题。

现在把 Write 方法中间的那段再拿出来（04 篇读过锁的部分，这次只看 batch 相关的三行，db_impl.cc:1229-1241）：

mutex_.Unlock();status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));bool sync_error = false;if (status.ok() && options.sync) {  status = logfile_->Sync();  if (!status.ok()) {    sync_error = true;  }}if (status.ok()) {  status = WriteBatchInternal::InsertInto(write_batch, mem_);}mutex_.Lock();

Contents 返回的就是 Slice(batch->rep_)（write_batch_internal.h:32）。也就是说——

01

落入 WAL：rep_ 的 93 个字节原样交给 log_->AddRecord，成为一条日志 record。没有“每条 KV 一条日志”的转译，没有再序列化，写路径对 batch 的磁盘表达就是它的内存表达本身；

02

进 MemTable：同一份字节掉头走一遍 Iterate，被 MemTableInserter 解析回一条条 KV 插进跳表。

同一份字节，两种用途，一份当日志写，一份当数据解。这是“一鱼两吃”。第三口在恢复路径：03 篇看过 RecoverLogFile 读 WAL 的现象，这次可以认出它的本质了（db_impl.cc:432-444）：

while (reader.ReadRecord(&record, &scratch) && status.ok()) {  if (record.size() < 12) {    reporter.Corruption(record.size(),                        Status::Corruption("log record too small"));    continue;  }  WriteBatchInternal::SetContents(&batch, record);  if (mem == nullptr) {    mem = new MemTable(internal_comparator_);    mem->Ref();  }  status = WriteBatchInternal::InsertInto(&batch, mem);

从 WAL 读出的 record 字节被 SetContents 直接灌进一个 batch（还会顺手挡掉不足 12 字节头的残片），然后走与写路径完全相同的 InsertInto 进 MemTable。所谓恢复，就是把这批字节最后再吃一遍。

原子性的答案也藏在这份字节流的待遇里。WAL 的每条 record 自带 CRC 和长度（物理格式下一篇展开）：写一半断电，残缺 record 在恢复时整个被丢弃，不会出现半截；record 完整，整批重放。提交的最小单位是“WAL 的一条 record”，而一条 record 恰好就是一个完整的 batch——三合一的原子性就是这么来的，不需要任何 undo 日志。

要说边界，也有一个容易误会的地方：WriteBatch 有原子性，但没有回滚能力。InsertInto 只在字节流损坏时返回 Corruption，正常的内存插入不会半途失败；真正的危险点是 fsync 失败，而那种情况下库的处理是 04 篇读过的 RecordBackgroundError——直接关闭写通道，因为那条 record 在不在已经不可知了，宁可停机等人工介入，也不能假装无事发生。换句话说，LevelDB 的原子性是“提交点原子”：一批要么整体跨过崩溃边界，要么整体没跨过去；它不像关系数据库那样支持“执行到一半撤销已做的部分”。这个差别我们在对比小节详细展开。

AddRecord 之后数据还只是在页缓存里，sync=false 时进程崩溃不丢、操作系统崩溃可能丢——这是下一篇的入场券，篇幅有限，这一篇我们先不讲。

void WriteBatchInternal::Append(WriteBatch* dst, const WriteBatch* src) {  SetCount(dst, Count(dst) + Count(src));  assert(src->rep_.size() >= kHeader);  dst->rep_.append(src->rep_.data() + kHeader, src->rep_.size() - kHeader);}

机制读完，回到短链服务。创建短链的三合一代码（完整版见文末附录 create_link.cc）：

leveldb::WriteBatch batch;batch.Put("c:" + code, target);               // 短码主体batch.Put("u:" + user + ":c:" + code, "1");   // 用户 → 短码索引batch.Put("c:" + code + ":click", "0");       // 点击计数初始化s = db->Write(leveldb::WriteOptions(), &batch);

跑一下，三个 key 都在；再往同一个 batch 里对同一个 key 做 Put("1")、Delete、Put("2")，读回来是 2——批内顺序语义实测成立：

after batch:  c:Ab3xK            -> https://example.com/a-very-long-url  u:robin:c:Ab3xK    -> 1  c:Ab3xK:click      -> 0after put/delete/put on same key:  c:Ab3xK:click      -> 2

原子性之外，batch 还有一层很现实的收益：摊薄固定成本。一次 db->Write 的固定成本——抢锁、排队、一条 WAL record 的封装，尤其是 sync=true 时的一次 fsync——与批大小基本无关。用 batch_bench（代码见附录）固定总写入量、扫描批大小，本机（macOS，fsync 很慢，见 04 篇附注）实测，先看 sync=false，总量 100000 条：

sync=false

批大小	吞吐（ops/s）	相对逐条写
1	145,511	1.00x
10	542,076	3.73x
100	930,657	6.39x
1000	958,911	6.59x
10000	1,078,935	7.42x
100000	1,236,354	8.50x

收益从批大小 10 就开始显现，100 之后趋于平缓——锁与队列的固定成本被摊得差不多了，剩下的提升来自更少的系统调用。

真正悬殊的是 sync=true，总量降到 2000 条（fsync 单价约 6～9ms）：

sync=true

批大小	耗时	吞吐（ops/s）	相对逐条写
1	12.883s	155	1.00x
10	1.388s	1,441	9.30x
100	0.166s	12,043	77.70x
1000	0.018s	111,539	719.00x
2000	0.008s	257,931	1,663.00x

逐条写 2000 条要 12.9 秒——每条一次 fsync；攒成 2000 条一个 batch，0.008 秒，快 1600 多倍。一个更有意思的对照：sync=true + 批 1000（111,539 ops/s）已经追平 sync=false + 逐条写（145,511 ops/s）。在这台 fsync 极慢的机器上，每 1000 条攒一次盘，就把持久化的钱基本赚了回来。数字与机器强相关，但“批越大、fsync 越摊越薄”的相对关系是通用的。