Percolator 分布式事务原理

简介

Percolator 提供了跨行、跨表的、基于快照隔离的 ACID 事务。

结构

Percolator 为了实现分布式事务，抽象了三个列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
列
    Data
        作用:
            具体存储数据集
        映射关系: {key, start_ts} => {value}
            key: 真实的 key
            start_ts: 事务开始时间戳
            value: 真实的数据值
    Lock
        作用:
            事务执行中产生的锁
            事务开启时获取锁
            事务提交时释放锁
        映射关系: {key, start_ts} => {primary_key, lock_type,..etc}
            key: 数据的 key
            start_ts: 事务开始时间戳
            primary_key: 该事务的 primary_key 的引用. primary_key 是在事务执行时，从待修改的 keys 中选择一个作为 primary_key, 其余的则作为 secondary key.
    Write
        作用:
            已提交事务信息，存储提交时间戳
            write 列记录着 key 的提交记录，当客户端读取一个 key 时，会从 write 列中读取 key 所对应数据在 data 列中的存储位置，然后从 data 列中读取真正的数据。
        映射关系:
            {key, commit_ts} => {start_ts}
                key: 数据的 key
                commit_ts: 事务的提交时间戳
                start_ts: 事务开始时间戳, 指向该数据在 data 中的实际存储位置

流程

写流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1.Prewrite阶段
    1.从 TSO 获取 start_ts
    2.尝试对所有被写元素加锁, percolator 为所有需要写的 key 选出一个作为 primary, 其余的作为 secondary
        1.每个 key 处理流程如下,中间出现失败,则 Prewrite 失败(先 Prewrite primary，成功后再 Prewrite secondaries)
            1.检查 write-write 冲突
                若 write 列当前 key 的最新数据 commit_ts 大于等于 start_ts,存在更新版本的已提交事务,失败,直接 Abort 整个事务
            2.检查 lock 列中该写入操作是否被上锁
                若 key 已被上锁,失败,直接 Abort 整个事务
        2.Lock 列写入 lock(start_ts, key, primary) 为当前 key 加锁
            若当前 key 被选为 primary, 则标记为 primary;
            若为 secondary, 则标明指向 primary 的信息
    3.Data 列写入 data(key, start_ts, value)
        由于此时 write 列尚未写入，因此数据对其它事务不可见
2.Commit阶段
    1.从 TSO 获取 commit_ts
    2.依次对各个 key 进行提交
        1.先 Commit primary , 如果失败则 Abort 事务
            检测 lock 列 primary 对应的锁是否存在，如果锁已经被其它事务清理（触发 failover 可能导致该情况），则失败。
            写入 Write 列: commit_ts -> data 列的 start_ts
            释放锁：删除 Lock 列当前 key
        2.再异步的进行 Commit secondary
            Commit seconary 无需检测 lock 列锁是否还存在，一定不会失败
            写入 Write 列: commit_ts -> data 列的 start_ts
            释放锁：删除 Lock 列当前 key

读流程

1
2
3
4
5
1.Get 操作首先检查 [0, start_ts] 时间区间内 Lock 是否存在
    1.若存在，则返回错误
    2.如果不存在有冲突的 Lock
        1.获取在 Write 中合法的最新提交记录指向的在 Data 中的位置
        2.从 Data 中获取到相应的数据并返回

异常处理流程（异步清理锁）

若 Client 在 Commit 一个事务时，出现了异常，Prewrite 时产生的锁会被留下。为避免将新事务 hang 住，Percolator 必须清理这些锁。

Percolator 用 lazy 方式处理这些锁：
当事务 A 在执行时，发现事务 B 造成的锁冲突，事务 A 将决定事务 B 是否失败，以及清理事务 B 的那些锁。

1
2
3
4
5
6
7
根据key 从 Lock 列查询 primary 锁
1.若 primary lock 存在
    事务B被 roll back
        因为我们总是最先提交 primary, 所以 primary 未被提交时，可以安全地执行回滚
2.若 primary lock 不存在
    说明 primary lock 已被 WRITE 所替代，也就是说该事务已被提交，事务需要 roll forword
        因为：在 B 提交 commit 之前, 它会先确保其 primary lock 被 write record 所替代（即往 primary 的 write 写提交数据，并删除对应的 lock）。

举例

// TODO

参考

Percolator论文