网易视频云：从 TNT 遇到的问题想到的另一种内存多版本的实现方案

[shipinyun2016]

前阵子的工作中发现 TNT 在事务生命周期中涉及到多次的内外存日志同步，多次的同步直接导致事务性能低下。

TNT 是基于另一个单独的存储引擎开发的，两个存储引擎会使很多问题复杂化，目前的 TNT 未实现完全的内外存分离，为得到数据的唯一性标识 Rowid ，目前数据的 Insert 是直接插入到外存中，同时产生外存日志。这就导致无论在事务提交或者回滚等等过程中，都需要涉及到外存的日志的操作和访问。并且在恢复过程中内外存的并行恢复设计变得十分复杂。

理想中的内存多版本数据库应当是多版本的数据完整得存在于内存中，因此无论是回滚或者是其他操作都是在内存中完成，而只有所有事务都可见的数据才物化到外存中。因此事务中的数据的插入，更新，删除，回滚等操作都是应该在内存中完成，只有在 purge 过程中才把数据刷到外存中，外存中的数据不保留任何版本的信息。

以下简单介绍一个简要的设想当中的内外存分离的内存多版本的实现方案（只针对和目前 TNT 设计中不同之处）：

针对 TNT 无法获取 rowid 的问题，这里提出一个虚拟 rowid 的概念，当数据进入内存，但是又未进入外存时，在数据库中利用一个唯一的虚拟 rowid 来标识。虚拟 rowid 由 insert 操作时系统统一分配。即在数据第一次物化到外存之前， 都利用这个虚拟的 rowid 来标识数据。

purge 操作会让数据进入外存，因此，过程中部分的数据会得到属于自己的真实 rowid 。 Purge 的操作分为两步，第一步将内存数据物化到外存中，第二步，将第一步中涉及到的内存数据从内存中删除。约定事务不跨越 purge 的两个阶段

为了保存真实 /虚拟 rowid 的映射关系，我们利用一个双向 hash 来保存。双向哈希在 purge 第一阶段中建立，在 purge 完成后删除，因此在 purge 第二阶段会发生双向 hash 中有虚拟 rowid,而内存中的数据已经被删除的情况发生。

purge 过程中的数据更新，当发现被更新的数据是利用虚拟 rowid 标识，那么我们需要检测双向 hash 中是否有对应的真实 rowid ，如果有真实 rowid ，那么就将原来记录的虚拟 rowid 更新成真实 rowid 。

purge 过程中数据的扫描，我们分成表扫描和索引扫描来讨论： 这里需要过滤 hash ：记录已经读取的虚拟 rowid

1. 表扫描： 内外存都要读取， a. 先读取外存数据，并寻找内存中的新版本。如果内存中的新版本是虚拟 rowid 标识，则选取外存数据。并将这个虚拟 rowid 加入到虚拟 rowid 过滤 hash 中， 否则选取内存数据。 b.读内存数据，当读到内存中一条虚拟 rowid 记录时，到虚拟 rowid 过滤 hash 中进行过滤，防止重复读。
2. 索引扫描： 内外存都要读取， 内外存一起读取，因为虚拟 rowid 的大小不一定和真实 rowid 一致，这里会发生内外存索引数据排序不同的情况。

在 scan 记录的过程中，内外存两个索引和 TNT 一样同时进行扫描，因为在同一个索引 key 值时会发生上图的情况，随之而来的就是如何防止数据重复读或者是漏读的情况。

一个简单的例子，当读到 key = a , vrid = 2 的内存索引项时，还未 purge ，然后 purge 这一项到外存中，然后读到外存对应的 key = a rrid = 6 的这项。这便产生了重复读。

因此，这里采取的方案如下： 1.若选取的内存项， a. 如果是虚拟 rowid ，则检测是否存在于双向 hash 中，若存在则跳过，若不存在，则返回。并将该虚拟 rowid 加入到虚拟 rowid 过滤 hash 中 b.如果是真实 rowid ，则直接返回。 2.若选取的外存索引项,去双向 hash 中查询是否存在对应的虚拟 rowid 的内存项 a. 如果存在，则用虚拟 rowid 过滤 hash 去重。 b. 如果不存在，则直接返回。

当读到不同的 key 值时，可重置过滤 hash 。

大对象： 由于当前的插入完全在内存中，新插入的大对象也需要在内存中维护，在 purge 过程中插入外存

恢复： 双向 hash 是需要持久化，因此对双向 hash 的修改需要记录日志，这是因为如果不记录真实 /虚拟 rowid 映射关系，在恢复时会导致数据多次插入。 双向 hash 的恢复需要依赖外存数据库的插入日志来生成，外存数据库中需要额外记录一个虚拟 rowid 的情况，这样虽然是破坏了外存数据库日志的独立性，但是这里如果双向 hash 日志独立出来，无论是先于还是后于外存日志写出都会出现问题。 在 purge 阶段会产生外存的日志。因此在 purge 阶段如果发生系统 crash ，做逻辑恢复时，当对外存做插入时需要比对已经恢复的双向 hash ，检查是否需要再次做插入操作。

方案的缺陷也很明显：在 purge 过程中，无论是扫描还是更新，都会访问双向 hash ，这里可能会成为一个并发瓶颈，然后每个扫描任务都要维护一个虚拟 rowid 过滤 hash ，这个成本在特定的场景下也可能会带来较大的负担。

以上是个人的一个简单的想法，可能会有很多疏漏没有考虑到，欢迎大家讨论。