badger 事务过程笔记

badger 是 dgraph 开源的 LSMTree 的 KV 引擎，它相比 leveldb 有 KV 分离、事务、并发合并等增强，是 go 生态中比较生产级的存储引擎了。这里看一下它的事务实现。

badger 实现了 Serializable Snapshot 隔离级别（简称 SSI）的乐观并发控制的事务，相比 Snapshot 隔离级别（简称 SI），SSI 除了跟踪写操作进行冲突检测，也会对事务中的读操作进行跟踪，在 Commit 时进行冲突检查，当前事务读取过的数据，如果在事务执行的期间被其他事务修改过，则会提交失败：

事务的生命周期

乐观并发控制事务的生命周期大致上分为四段，授时、跟踪读写、提交、清理：

• 事务启动：获取事务开始时刻的授时
• 事务过程：跟踪事务的读写操作涉及到的 key，事务期间读操作按启动时刻的快照为准，事务中的写入内容在内存中暂存
• 事务提交：根据事务中跟踪的 key 进行冲突检测，获取事务提交时刻的授时，使写入生效
• 清理旧事务：当活跃的事务完成后，可以使已经不再需要的快照数据、冲突检测数据等事务相关数据得到释放

为了管理事务的生命周期，需要为每个事务和全局层面记录两部分元信息：

• 每个事务层面，需要记录自己读写的 key 列表，以及事务的开始时间戳和提交时间戳，这部分信息维护在 Txn 结构体中
• 全局层面，需要管理全局时间戳，以及近提交的事务列表，用于在新的事务提交中对事务开始与提交时间戳中间提交过的事务范围进行冲突检查，乃至当前活跃的事务的小时间戳，用于清理旧事务信息，这部分信息维护在 oracle 结构体中

这里授时得到的时间戳并非物理时间，而是逻辑上的：所有的数据变化均来自事务提交的时刻，因此仅当事务提交时使时间戳递增。

以上面的图为例，事务 4 在提交时需要与事务 3 和事务 1 进行冲突检测，因为事务 3 和事务 1 的提交时间位于事务 4 的开始与提交之间，事务 3 和事务 1 写入的 key 如果与事务 4 读写的 key 列表存在重叠，则认为存在冲突。

接下来我们顺着这四段生命周期，过一下 badger 中的相关过程。

事务开始

启动一个新事务的入口在 db.newTransaction() 函数。这个函数比较简单，除了初始化几个字段，有行为语义的部分就是 txn.readTs = db.orc.readTs() 这一行申请授时的地方了。

看一下 readTs() 函数的实现：

func (o *oracle) readTs() uint64 {
	// 忽略 isManaged 部分逻辑

	var readTs uint64
	o.Lock()
	readTs = o.nextTxnTs - 1
	o.readMark.Begin(readTs)
	o.Unlock()

	// Wait for all txns which have no conflicts, have been assigned a commit
	// timestamp and are going through the write to value log and LSM tree
	// process. Not waiting here could mean that some txns which have been
	// committed would not be read.
	y.Check(o.txnMark.WaitForMark(context.Background(), readTs))
	return readTs
}