侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

TiDB分布式事务模型Percolator理解

林贤钦
2022-04-26 / 0 评论 / 0 点赞 / 313 阅读 / 4,645 字
温馨提示:
本文最后更新于 2022-04-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

TiDB分布式事务模型Percolator理解

Percolator简介

Percolator 是 Google 的上一代分布式事务解决方案,构建在 BigTable 之上,在 Google 内部 用于网页索引更新的业务,原始的论文

Percolator是在Bigtable的基础上实现的,它是以Client library的方式实现。Percolator 利用Bigtable的单行事务能力,仅仅依靠客户端侧的协议和一个全局的授权服务器TSO就实现了跨机器的多行事务。

总体来说:经过优化二段提交的实现,进行一个二级锁的优化。

Bigtable 是一个分布式的结构化数据存储系统,它被设计用来处理海量数据,从数据模型的角度,Bigtable可以理解为是一个稀疏的,多维的持久化的键值对Map,一个键值对的格式如下:

(row:string, column:string,timestamp:int64)->string

key 是行关键字(row),列关键字(column),以及时间戳(timestamp)的组合,value 是任意的 byte 数组。

在Bigtable中存在三列,分别为bal:data、bal:lock、bal:write

  1. bal:write中存事务提交时间戳 commit_ts => start_ts;
  2. bal:data 这个map中存事务开始时间戳start_ts =>实际列数据
  3. bal:lock 存start_ts => (primary cell), Primary cell 是 Rowkey和列名的组合,它在提交容错处理和事务冲突时使用,用来清理由于协调器失败导致的事务失败留下的锁信息。

Percolator 通过一个全局的授权服务器TSO给予事务一个全局的时间戳来解决分布式下事务的全局时序问题;通过经典的两段提交来解决分布式事务原子提交的问题。

Percolator不仅仅是一个改进版的两端提交,它覆盖的内容更多,可以以为是一个完整的分布式事务解决方案,它还包含了依据全局时间戳实现Snapshot Isolation 隔离级别的并发控制协议,并给出了在故障发生如何进行自动failover的细节。

Percolator架构

Percolator包含三个组件

  1. Client:Client 是整个协议的控制中心,是两阶段提交的协调者(Coordinator)。
  2. TSO:一个全局的授时服务,提供全局唯一且递增的时间戳 (timetamp)。
  3. Bigtable:实际持久化数据的分布式存储

Percolator流程

一个事务的所有Write在提交之前都会先缓存在Client,然后在提交阶段一次性写入;Percolator的事务提交是标准的两阶段提交,分为Prewrite和Commit。在每个Transaction 开始时会从TSO获取timestamp作为start_ts,在Prewrite成功后Commit前从TSO获取timestamp 作为commit_ts。

Prewrite

  1. 在事务开启时会从TSO获取一个timestamp作为start_ts;
  2. 选择一个Write作为primary,其它Write则是secondary;primary作为事务提交的sync point 来保 障故障恢复的安全性;
  3. 先Prewrite primary,成功后再Prewrite secondaries;先Prewrite primary 是failover的要求;
    • Write-write conflict 检查: 以Write.row 作为key,检查Write.col 对应的write列在[start_ts,max]之间是否存在相同的key。如果存在,直接Abort(中止)整个事务;
    • 检查lock列中Write 是否被上锁了,如果锁存在,Percolator不会等待锁被删除,而是直接Abort整个事务。这种简单粗暴的冲突处理方案避免了死锁发生的可能;
    • 上面成功之后,以start_ts 作为BigTable的timestamp,将数据写入data列。由于Write列尚未写入,因此数据对于其他事务不可见

对于一个 Write,3 中多个步骤都是在同一个 Bigtable 单行事务中进行,保证原子性,避免两个事务对同一行进行并发操作时的竞争;任意 Write Prewrite 失败都会导致整个事务 Abort;Prewrite 阶段写入 data 列的数据对其它事务并不可见。

Commit

如果 Prewrite 成功,则进入 Commit 阶段:

  1. 从TSO获取一个timestamp 作为commit_ts;
  2. 从Commit primary,如果失败则Abort事务;
    • 检测lock列primary对应的锁是否存在,如果锁已经被其他事务清理,则失败
    • 检查成功后,以commit_ts作为timestamp,以start_ts作为value写write列。读取操作会读write列获取start_ts,然后再以start_ts去读取data列中的value;
    • 删除lock列中对应的锁
  3. 异步的进行 Commit secondary 。步骤 2 成功意味着事务已提交成功,此时 Client 可以返回用户提交成功,Commit seconary 无需检测 lock 列锁是否还存在,一定不会失败,只需要执行 2.2 和 2.3。

Percolator流程举例

经典转账例子,一个账户表中,Bob 有 10 美元,Joe 有 2 美元。Bob转账7元给joe。

Prewrite

我们可以看到 Bob 的记录在 write 字段中最新的数据是 data@5,它表示当前最新的数据是 ts=5 那个版本的数据,ts=5 版本中的数据是 10 美元,这样读操作就会读到这个 10 美元。同理,Joe 的账号是 2 美元。

image-20220426204326735

现在我们要做一个转账操作,从 Bob 账户转 7 美元到 Joe 账户。这需要操作多行数据,这里是两行。首先需要加锁,Percolator 从要操作的行中随机选择一行作为 Primary Row,其余为 Secondary Row。对 Primary Row 加锁,成功后再对 Secondary Row 加锁。

image-20220426204348388

从上图我们看到,在 ts=7 的行 lock 列写入了一个锁:I am primary,该行的 write 列是空的,数据列值为 3(10-7=3)。 此时 ts=7 为 start_ts。然后对 Joe 账户加锁,同样是 ts=7,在 Joe 账户的加锁信息中包含了指向 Primary lock 的引用,如此这般处于同一个事务的行就关联起来了。Joe 的数据列写入 9(2+7=9),write 列为空,至此完成 Prewrite 阶段。

image-20220426204523920

Commit

Primary Row 首先执行 Commit,只要 Primary Row Commit 成功了,事务就成功了。Secondary Row 失败了也不要紧,后续会有补救措施。Commit 操作首先清除 Primary Row 的锁,然后写入 ts=8 的行(因为时间是单向递增的,这里是 commit_ts),该行可以称为 Commit Row,因为它不包含数据,只是在 write 列中写入 data@7,标识 ts=7 的数据已经可见了,此刻以后的读操作可以读到版本 ts=7 的数据了。

image-20220426204625133

接下来就是 commit Secondary Row 了,和 Primary Row 的逻辑是一样的。Secondary Row 成功 commit,事务就完成了。

image-20220426204634724

如果 Primary Row commit 成功,Secondary Row commit 失败会怎么样,数据的一致性如何保障?由于 Percolator 没有中心化的事务管理器组件,处理这种异常,只能在下次读操作发起时进行。

如果一个读请求发现要读的数据存在 Secondary 锁,它会根据 Secondary Row 锁去检查其对应的 Primary Row 的锁是不是还存在,若存在说明事务还没有完成;若不存在则说明,Primary Row 已经 Commit 了,它会清除 Secondary Row 的锁,使该行数据变为可见状态(commit)。这是一个 Roll forward 的概念。

该事务另一个问题就是冲突处理。在Snapshot Isolation(快照隔离)中对于同一行的冲突可以采用先提交先获胜的模式。

Snapshot Isolation

Percolator 实现的隔离级别是Snapshot Isolation,Snapshot Isolaton 是一种在多个数据库被广泛采用的隔离级别,它最早见于数据库领域的经典论文 3,从隔离性的角度完胜Read-Committed,和 Repeatable-Read 互有胜负。Snapshot Isolation 存在写偏斜(Write-skew) 但是不存在幻读(Phantom), 而 Repeatable-Read 正好相反。

Snapshot Isolation要求:

  1. 当一个事务 T1 准备提交时获取一个 Commit-timestamp(commit_ts),大于所有已存在的 Commit-timemstap 和 Start-timestamp(start_ts)。
  2. First-committer-wins。一个事务T1能够提交成功当且仅当在[T1.start_ts, T2.commit_ts] 范围内不存在另一个事务T2,T2 和T1 修改了同一行,T1.start_ts < T2.commit_ts < T1.commit_ts,即 T2 在 [T1.start_ts, T1.commit_ts] 之间提交,且T2提交成功。不然 T1 应当 Abort。
  3. Snapshot-read。事务的读操作都满足 Snapshot-read:即对于一个事务T1而言,所有 commit_ts <= T1.start_ts的事务的修改都对T1可见,所有commit_ts > start_ts的事务的修改都对T1不可见。

Failover

对于分布式事务一个完备的 failover 机制要求满足两点:

  1. Safety:针对 Percolator场景即是同一个事务的两个 Write,不存在一个 Write 的状态为 Committed,另一个则是 Aborted。
  2. Liveness: 所有 Write 最终都会处于 Committed 或者 Aborted。

Liveness 要求 failover 最终能够被触发,对此 Percolator 采用 lazzy 的方式,一个事务的 failover 由另一个事务的读操作触发:如果一个事务读某个 key 时发现该 key 被锁住,Snapshot-read 要求等待锁删除后才能发起读取;在等待超过一段时间后,会认为锁住该 key 的事务可能由于 Client crash 或者网络分区等原因而 hang 住,尝试通过回滚或者继续提交锁对应的事务的方式来清理锁。

保证 Safety 的一个核心点是如何判定一个分布式事务是否已经被提交:即什么情况下,可以判定事务已 Committed,什么情况下判定事务未 Committed,可以发起 rollback。Percolator 的解法是选择一个 Write 作为 primary,以 primary 作为整个事务的 sync point。

总结

Percolator 基于 Bigtable 的单行事务提供了多行事务的能力,无论并发控制还是 failover 都设计得简洁而优雅,但又强而有力,即严格保证了的 Snapshot Isolation 隔离级别,也保证了 failover 的 Safety。另一方面,从性能的角度它也存在一些不足,它为 Bigtable 定制的特点导致其采取持久化 lock 列和将数据拆成 data 和 write 两列的设计,这些设计对读写吞吐会有不同程度的影响。

0

评论区