Google关于BigTable的论文中分布式事务的实现

Google关于BigTable的论文中分布式事务的实现

Google在BigTable相关的论文中详细的解释了Percolator分布式事务的实现方式, 而且用简洁的伪代码示例怎么实现分布式事务;

Percolator算法在分布式数据库中运用广泛, 国内著名的开源分布式数据库TiDB的事务实现来源于Percolator, 腾讯TBase的分布式事务实现也来自于Percolator;

在讲Percolator之前, 我们先看几个问题:

1, 假设一个事务开始的时间戳是 T2 , 这个事务读取数据的原则是什么, 是读取最新的数据还是只能读取截止到 T2 的数据?

2, 假设一个事务里面需要访问很多表的记录, 而且都是截止到 T2 时间戳的快照, 怎么能获取到这些快照?

3, 假设一个事务操作很多记录, 这些记录落在多台服务器上, 怎么能保证多台服务器上的记录操作都是在原子锁的情况下进行?

4, 假如有多个 Worker 操作多个服务器上的多条记录上的锁, 这些记录和锁属于一个事务, 怎么能保证这些记录全部提交, 或者这些记录全部回滚?

 

我们直接摘抄Google的论文, 看看 Percolator 的实现:

 

假设有一个表, 有2个用户, Bob和Joe, Bob的账户余额是$10, Joe的账户余额是$2

 

 

下面开始一个事务, Bob转 7美金给Joe:

假设这个事务开始的时候, 时间戳是 7, 这个时间戳是事务开始时间戳;

第 1 步, 加主锁, 主锁只有一个;

 在Bob这条记录(row)的bal列(余额列)的data列, lock列, 都写入带有时间戳7的记录, row上的操作是行级别的事务;

第 2 步, 加从锁, 从锁关联主锁, 从锁可以有多个;

 

在Joe这条记录(row)的bal列(余额列)的data列, lock列, 都写入带有时间戳7的记录, row上的操作是行级别的事务;

上述流程是第1阶段, 预写入(Prewrite); 

Prewrite之后, 进入第 2 个阶段, 提交阶段(Commit阶段);

提交阶段会获取第2个时间戳---提交时间戳, 这里假设是8;

 

 

一旦清除主锁, 并写入write列, 则事务一定要完成; 从锁可以保证即使发生异常, 事务也能进行前向滚动从而完成整个事务; 而主锁可以确保事务加锁的原子性;

注意1: 需要说明一点, 因为对每一个记录的操作都会涉及到多个列, 所以会使用 row 事务, 保证对同一row的多个列的操作是原子性的;

 

上面就是Commit流程, 先处理主锁, 然后依次处理从锁, 主锁是关键, 是原子级的锁, 一旦主锁提交(这是一个row事务, 更新lock列和write列), 这个事务必须要提交;

如果主锁没有提交, 则这个事务是可以回滚的, 回滚时也必须先操作主锁, 确保对多个锁的原子性操作, 然后依次处理从锁, 事务提交者在Commit阶段发现主锁已经失效, 说明事务被其他worker回滚掉了, 不能进行提交;

 

可以看到, Percolator包括:

1. 两阶段提交, Prewrite阶段, Commit阶段;

2. 主从锁, 主锁作为多个锁当中的负责原子级操作的锁;

3. 多列(data, lock, write);

4. 每一个维度的列都带时间戳;

5. 数据多版本(MVCC);

我们看看Google论文里面的伪代码示例:

Get函数伪代码:

一个读操作需要等待lock列的锁, 范围是早于读取的时间戳, 一个前次的事务有可能还在Commit阶段, 而且Commit的时间戳也是小于读取操作的时间戳的;

Prewrite函数, 注意, 这只是Prewrite函数不是Prewrite阶段

 Commit函数, 里面实现了两阶段提交

 

一个事务的关键节点是--清除lock上的主锁, 并且在write列写入---这个操作是原子性的, 基于row事务---一旦这个操作完成, 事务必须完成, 即使事务的worker挂掉, 其他worker也有义务帮助这个事务完成前向滚动(rolled farward), 您可以把他看成是mysql的redo操作; 如果这个操作没有完成, 其他worker可以回滚掉这个事务, 一般是这个事务的worker产生了异常, 例如事务超过了一定的时限; 即使没有超过时限, 回滚也是安全的, 不违反一致性; 

 现在回到我们开始的问题;

1, 假设一个事务开始的时间戳是 T2 , 这个事务读取数据的原则是什么, 是读取最新的数据还是只能读取截止到 T2 的数据;

     只能读取T2时间戳的数据, 依据write列的时间戳, 这样是为了在事务里面获得一致性的快照(snapshot); 一般叫做可重复读(Read Repeatable)

2, 假设一个事务里面需要访问很多表的记录, 而且都是截止到 T2 时间戳的快照, 怎么能获取到这些快照?

     根据write列的时间戳来获取T2时间戳的快照;

3, 假设一个事务操作很多记录, 这些记录落在多台服务器上, 怎么能保证多台服务器上的记录操作都是在原子锁的情况下进行?

     主锁(Primary lock)和write列是关键;

4, 假如有多个 Worker 操作多个服务器上的多条记录上的锁, 这些记录和锁属于一个事务, 怎么能保证这些记录全部提交, 或者这些记录全部回滚?

     主锁和write列是判断事务成功提交的关键, 主锁和write列操作成功, 事务一定要提交, 如果提交事务的worker挂了, 其他的worker根据从锁(Secondary lock)帮助提交(rolled forward); 否则, 可以回滚(roll back), 回滚依赖于事务的超时时间和事务负责的worker的存活状态;

 

下篇博客, 我们一起看下TiDB里面分布式事务的实现代码;