Percolator

Percolator

论文链接 #

Paper: Large-scale Incremental Processing Using Distributed Transactions and Notifications

算法描述 #

BigTable 提供了单行的事务操作，但是有些事务是需要多行操作的，Percolator 解决的就是在 BigTable 上的多行事务操作。

Percolator 实现的分布式事务依赖于三个实体： Percolator worker、TSO（timestamp oracle）、BigTable。TSO 是一个全局严格递增的时间戳服务。

Percolator 存储一行数据时，会在 BigTable 存储多列数据：

  • data 列： 存储 value
  • lock 列： 存储用于分布式事务的锁信息
  • write 列： 存储用于分布式事务的提交时间（commit_timestamp）

Transaction: Write #

Percolator 的分布式写事务是由两阶段提交实现的。一个写事务包含了多个写操作，事务开启时，Percolator 会从 TSO 获得一个 ts 作为事务的开始时间。包含两个阶段。

PreWrite阶段

  1. 在所有的写操作中随机选取一个作为 primary，其他的写操作作为 secondary。首先操作 primary。
  2. 进行冲突检测。
    1. 如果在 start_ts 之后，发现 write 列存在数据，说明其他事务在当前事务开始之后提交了。说明两个事务并发写冲突，需要 abort 当前的事务。
    2. 如果在任何 ts 上发现 lock 列有数据，说明其他事务正在修改数据，仍然 abort 当前事务。也可能是另一个事务崩溃失败，需要故障恢复。
  3. 锁定和写入。对于每一行每一列要写入的数据，先将其锁定（primary 写 lock 列，secondary 的 lock 列写入指向 primary），然后写入到 data 列中。

Commit阶段

  1. 从 TSO 获得一个 ts 作为 commit_ts。
  2. 提交 primary，如果失败则 abort。
    • 检查 primary 上的 lock 信息是否还在，不在则 abort（其他事务认为当前事务失败，清理掉 lock）。
    • 以 commit_ts 为 timestamp，写入 write 列，value 为 start_ts。清理 lock 列。此时为 commit point，一旦完成此步骤则视为事务成功。在此之前出错都 abort 回滚。
  3. 提交成功后给 Percolator 返回成功，secondary 异步写入，即使失败也可以通过 primary 的数据状态来判断 secondary 的结果。

Transaction: Read #

在 Percolator 中的事务隔离级别是 Snapshot Isolation。写事物主要负责清理锁。

一些细节：

  1. 让 pre-write 阶段先于（happens-before）获取 commit_ts。所以在 commit_ts 之后，prewrite 的数据必然被锁定了。
  2. 如果读取时，发现当前数据已被锁定（锁定意味着其他写事务正在执行），则等待并重试。当然也有可能另一个事务已经崩溃。

缺点 #

Percolator 基于 BigTable 单行事务实现的分布式事务，其实是一个乐观事务模型。只有在事务提交时，才会检测写-写冲突。Percolator 事务模型的优点在于原理简单方便理解，不再需要一个中心化的单独 Coordinator，而是把 Coordinator 角色的职责进行细分，把能持久化的部分交给 BigTable 处理，后续也不再依赖 Client 的恢复。但它的缺点也是显而易见的：

  1. Client 和 BigTable 之间的 RPC、BigTable 和 ChunkServer 之间的RPC都会比较耗费网络资源；
  2. TSO 是一个中心化的点。并发事务很多的时候，会占用很多内存；
  3. 并发大事务可能会频繁冲突，而重试有可能会导致雪崩效应（这时候就用悲观事务模型会更好）；
  4. 懒处理事务 crash 导致一个事务的延迟可能会比较高；
  5. 依靠读操作清理锁，如果清理不及时，会增加其他正常事务写冲突的概率；
  6. 考虑另一个场景：有一个大事务和很多小事务，且它们的热点overlap，那么大事务可能受小事务的影响进入饥饿状态（即很长时间内无法执行）。