但同时也存在以下缺点
- 事务提交操作比较重,延迟较大
- 事务都缓存在WriteBatch中,对大事务不友好
- 无法支持read uncommitted隔离级别
Write Policy
针对TransactionDB的以上缺点, rocksdb引入了新的提交策略(write policy), 共有以下write policy
WriteCommitted
即原有的方式,提交时才会写WriteBatch, 默认为WRITE_COMMITTED方式.
WritePrepared
将写memtable提前到prepare阶段。
prepare阶段写WAL, 并且写memtable
commit阶段写commit标记到WAL。 WritePrepared方式减轻了提交的操作,但并不能解大事务的问题。WriteUnPrepared
将写memtable提前到每次写操作。 目前此方式还在开发中。 WritePrepared方式减轻了提交的操作,同时也能解大事务的问题。
本文主要介绍WritePrepared的实现方式。
WritePrepared方式将写memtable提前到prepare阶段,会引入以下问题
写入memtable的记录如何判断可见性
WritePrepared方式记录中的sequence是在prepare阶段就分配的,对于某个snapshot来说,snapshot大于此sequence并不代表此记录对snapshot可见。如何回滚memtable中的记录
不像WriteCommitted方式直接释放WriteBatch就可以回滚事务,WritePrepared方式回滚时memtable中的记录需要以一定的方式回滚
WritePrepared方式在prepare阶段写memtable时会分配sequece, 设为prepare_seq, prepare_seq会存储到记录上。同时提交时会记录一个sequence, 设为commit_seq,commit_seq并不存在记录上,通过commit_seq可判断记录可见性。
这里就存在矛盾了,能判断记录可见性的commit_seq并不存储在记录上
事务可见性分析
对于下图中,设记录的key是唯一的,对于snapshot=8来说,R1, R2两个记录是可见的,因为R1,R2的commit_seq都小于8。而R3,R4,R5的commit_seq都大于8,所以R3,R4,R5是不可见的。
每个事务开始时, 获取当前已经开启但未提交的事务列表,称之为read_view. 在rocksdb中read_view为prepare_seq的集合, 其中min_seq 为read_view中的最小sequence, max_seq为readview中的最大sequence.
对于snapshot=S事务可见性规则如下:
- prepare_seq > max_seq, 事务在S后开启,不可见。例如上例R5
- prepare_seq exist in read_view, 对于S来说,事务已经开启,但未提交,不可见。例如上例R3R4
- 其它情况,可见。例如上例R2
上例中read_view = {4,5}, min_seq=4, max_seq=5
这种方式不需要commit_seq. 但每个事务都需要维护read_view.
第二种方式
commit_seq并没有存储在记录中,我们可以在内存中维护commit_seq信息,假设我们将每个已经提交的事务信息对(prepare_seq,commit_seq)都存储起来称为commit_cache
对于snapshot=S事务可见性规则如下
- prepare_seq > S 不可见,例如上例R5
- prepare_seq exist in commit_cache, 通过对应的commit_seq判断是否可见, 例如上例R1,R2的commit_seq <= S 可见,而R3,R4,R5的commit_seq > S 不可见。
- prepare_seq not exist in commit_cache, 未提交事务,不可见。
上例中commit_cache = {<1,2>, <4,9>,<5,10>,<6,7>, <11,12> }
这种方式简单,但需要存储所有已提交的信息,不太可行。
rocksdb WritePrepared的实现折中了以上两种方式。先介绍WritePrepared引入的一些数据结构
- commit_cache
commit_cache保存所有的已经提交的事务信息对, 但commit_cache会以CommitCache[prepare_seq % array_size] = 方式淘汰, prepared_seq是递增的,所以commit_cache的淘汰大体上是先进先出的, 这样commit_cache基本上保存的是最近提交的事务信息。
其中max_evicted_seq_记录淘汰出的最大的prepare_seq。
prepared_txns_
prepared_txns_是一个最小堆,保存当前prepare但未提交的事务。prepared_txns_在prepare时加入prepare_seq,在commit时踢除.delayed_prepared_
delayed_prepared_保存的是未提交事务。 Commitcache发生evict时, AdvanceMaxEvictedSeq推进max_evicted_seq_,prepared_txns_中小于max_evicted_seq_都踢除,并加入到delayed_prepared_. delayed_prepared_在commit时也会踢除, 小于max_evicted_seq_的未提交事务都在delayed_prepared_中
min_uncommitted_
min_uncommitted_事务开启快照时获取的最小未提交事务即prepared_txns_.top
事务可见性判断以max_evicted_seq_为界, prepare_seq小于等于max_evicted_seq_时按第一种方式处理, prepare_seq大于max_evicted_seq_时按第二种方式处理。
- prepare_seq大于max_evicted_seq_
直接应用第二种方式的规则
- prepare_seq > S 不可见
- prepare_seq exist in commit_cache,通过对应的commit_seq判断是否可见
- prepare_seq not exist in commit_cache, 未提交事务,不可见
- prepare_seq小于等于max_evicted_seq_
基本上对应于第一种方式的规则
- prepare_seq < min_uncommitted_, 事务在S前已提交,可见。
- snapshot > max_evicted_seq, 事务在S前已提交,可见。
- prepare_seq exist in old_commit_map_, 对于S来说,事务已经开启,但未提交,不可见。
- 其它情况,可见。
WritePrepared 可见性判断还是比较高效的 prepare_seq大于max_evicted_seq_时可以通过commit_cache快速判断
prepare_seq小于max_evicted_seq_时又分为以下几种情况 prepare_seq < min_uncommitted可以快速判断可见 min_uncommitted 和max_evicted_seq_之间, 未提交的在delayed_prepared_不可见,提交的有一部分在commit_cache,前面已判断。 > 另一部分提交的已evict掉,通过Snapshot > max_evicted_seq_ 可以快速判断可见。 最后的就通过old_commit_map_来判断prepare_seq是否在某个live snapshot中
这种方式对长事务不友好,如果有一个很老的事务未提交,那么min_uncommitted 和max_evicted_seq_之前的区间会比较大,判断就比较低效
如果commit_cache比较大_(默认8M个entry), 且都是短事务的场景,这样基本可以保证新开启事务的Snapshot > max_evicted_seq, 有这个条件就不需要去判断old_commit_map_。
举个例子
源码逻辑如下:
事务可见性的判断会用到数据的读取和compaction过程中的数据是否存在live snapshot上面。
WritePrepared 回滚处理
以prepare_seq-1为snapshot开启事务,如果查找不到,说明之前是第一次插入key, 则通过Delete回滚。如果存在老值,则用老值覆盖来回滚。
源码片段如下
&callback);
assert(s.ok() || s.IsNotFound());
if (s.ok()) {
assert(s.ok());
} else if (s.IsNotFound()) {
// There has been no readable value before txn. By adding a delete we
s = rollback_batch_->Delete(cf_handle, key);
assert(s.ok());
} else {
}