[转帖]Percolator - 分布式事务的理解与分析

percolator,分布式,事务,理解,分析 · 浏览次数 : 0

小编点评

# Percolator 分布式事务实现原理解读TiDB 新特性漫谈:悲观事务Percolator 和 TiDB 事务算法。归纳总结以上内容,生成内容时需要带简单的排版 **1. Percolator 分布式事务实现** Percolator 是基于BigTable单行事务实现的分布式事务。它其实是一个乐观事务模型。只有在事务提交时,才会检测写-写冲突。 **2. 原理解读TiDB 新特性漫谈** TiDB 的悲观事务模型是针对并发事务冲突的。它在每个DML语句执行的时候加锁,并等待其他事务获取锁才能进行修改。 **3. 悲观事务Percolator 和 TiDB 事务算法** 悲观事务Percolator 和 TiDB 事务算法都是针对并发事务冲突的。悲观事务Percolator 通过设置死锁检测机制来防止事务在提交前被阻塞。而TiDB 事务算法通过在每个DML语句执行的时候加锁来实现悲观事务的机制。 **4. 总结** Percolator 分布式事务实现原理解读TiDB 新特性漫谈。悲观事务Percolator 和 TiDB 事务算法都是针对并发事务冲突的机制,通过设置死锁检测机制或在DML语句执行的时候加锁等方式来实现悲观事务的机制。

正文

https://zhuanlan.zhihu.com/p/261115166

 

Percolator - 分布式事务的理解与分析

概述

一个web页面能不能被Google搜索到,取决于它是否被Google抓取并存入了它的倒排索引。Google管理着万亿级别的倒排索引,并且每天都有着几十亿级别的数据更新。通过MapReduce批处理,可以高效地将整个数据库全量构建成倒排索引。但是对于增量数据来说,全量构建是不经济且不及时的。所以Google研发了Percolator,用于处理这些大规模的增量数据。

为了确保系统故障时的数据一致性,Percolator在BigTable的基础之上,提供了Snapshot Isolation语义的分布式事务能力。本文讨论的重点就在于:Percolator如何基于BigTable的单行事务和一个Timestamp Oracle(全局授时服务器,后称TSO)实现上述的分布式事务。

 

模型

Percolator实现分布式事务主要基于3个实体:Client、TSO、BigTable。

  • Client是事务的发起者和协调者
  • TSO为分布式服务器提供一个精确的,严格单调递增的时间戳服务。
  • BigTable是Google实现的一个多维持久化Map,格式如下:

实际上Percolator存储一列数据的时候,会在BigTable中存储多列数据:

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

对于上表来说,它表示的是k1这一行,c1这一列数据的3个版本(timestamp分别为5、6、7)。

因为write列中,最新的数据是data@5,表明最新的一次commit_timestamp为5。所以看timestamp=5时,data列的数据为foobar。并且这一行这一列最新的数据也为:foobar。

在timestamp=7的时候,data列的数据被改为了barbaz,lock列也被标记为锁定,意味着此时有一个事务正在修改数据。一旦这个数据成功提交,在未来个某个timestamp上,会将它的write列写为7,并把7中的lock列清理掉。

可以看出,Percolator使用了lock和write这额外的2列来表达事务的状态。下面会具体说明,如何使用这2列作为元数据来实现分布式事务。

“写”事务

Percolator的分布式写事务是由2阶段提交(后称2PC)实现的。不过它对传统2PC做了一些修改,可见后文的“Percolator特色的2PC”。

一个写事务可以包含多个写操作,事务开启时,Client会从TSO处获取一个timestamp作为事务的开始时间(后称为start_ts)。在提交之前,所有的写操作都只是缓存在内存里。提交时会经过prewrite阶段和commit阶段。

Prewrite阶段

  1. 随机取一个写操作作为primary,其他的写操作则自动成为secondary。Percolator总是先操作primary,“Percolator特色的2PC”会讨论到为什么总是先操作primary。
  2. 冲突检测:
  3. 如果在start_ts之后,发现write列有数据,则说明有其他事务在当前事务开始之后提交了。这相当于2个事务的并发写冲突,所以需要将当前事务abort。
  4. 如果在任何timestamp上发现lock列有数据,则有可能有其他事务正在修改数据,也将当前事务abort。当然也有可能另一个事务已经因为崩溃而失败了,但lock列还在,对于这一问题后面的故障恢复会讨论到。
  5. 锁定和写入:对于每一行每一列要写入的数据,先将它锁定(通过标记lock列,secondary的lock列会指向primary),然后将数据写入它的data列(timestamp就是start_ts)。此时,因为该数据的write列还没有被写入,所以其他事务看不到这次修改。

对于同一个写操作来说,data、lock、write列的修改由BigTable单行事务保证事务性。

由冲突检测的b可以推测:如果有多个并发的大事务,并且操作的数据有重合,则可能会频繁abort事务,这会是一个问题。在TiDB的改进中会谈到它们怎么解决这一问题。

Commit阶段

  1. 从TSO处获取一个timestamp作为事务的提交时间(后称为commit_ts)。
  2. 提交primary, 如果失败,则abort事务:
  3. 检查primary上的lock是否还存在,如果不存在,则abort。(其他事务有可能会认为当前事务已经失败,从而清理掉当前事务的lock)
  4. 以commit_ts为timestamp, 写入write列,value为start_ts。清理lock列的数据。注意,此时为Commit Point。“写write列”和“清理lock列”由BigTable的单行事务保证ACID。
  5. 一旦primary提交成功,则整个事务成功。此时已经可以给客户端返回成功了。secondary的数据可以异步的写入,即便发生了故障,此时也可以通过primary中数据的状态来判断出secondary的结果。具体分析可见故障恢复。

“读”事务

在早期的SQL标准中定义的四个事务隔离级别,只适用于基于锁的事务并发控制。后来有人写了一篇论文 A Critique of ANSI SQL Isolation Levels 来批判 SQL 标准对隔离级别的定义,并在论文里提到了一种新的隔离级别 —— Snapshot Isolation(快照隔离)。在Snapshot Isolation下,不会出现脏读、不可重复度和幻读的问题。并且读操作不会被阻塞,对于读多写少的应用,Snapshot Isolation是非常好的选择。所以,主流数据库都实现了Snapshot Isolation。更多关于Snapshot Isolation的内容和历史,可以查阅《Design Data-Intensive Applications》第7章第2节。

事务隔离级别,实际上规定的就是事务之间的可见行。对于Snapshot Isolation来说:事务只能看到早于它开始时刻之前提交的其他事务。

以下图为例:事务2看不到事务1的修改,因为事务1在事务2开始之后才提交;事务3可以看到事务1和事务2的修改,因为它们在事务3开始之前提交。PS:因为事务1和事务2是并发的,如果它们操作的数据有重合,则至少有一个事务会回滚。

 

 

精确地获取事务的start_ts和commit_ts是很重要的。因为它关系着事务之间的可见行,以及决定了多个事务是否并行。Percolator使用Timestamp Oracle模块来提供start_ts和commit_ts。

分布式下snapshot-read存在的问题

尽管我们可以通过TSO获取到精确的start_ts和commit_ts,但还是可能出现一个小问题:事务实际执行的顺序可能和时间戳的顺序不一致!

举个例子:T1的commit_ts < T2的start_ts, T2执行Read的时候,T1还没commit完成。按照标准,T2应该需要可以读取到T1的更改,但实际上因为T1还没有commit。

Percolator的解法是:

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

对于上面的例子来说,T2执行到Read时,发现row1被T1锁住了,就会等待直到T1 commit完成。这样T2就能读取到T1 commit的结果了,符合了snapshot-read的标准。

Percolator特色的2PC

不同于传统意义上的2PC,在Percolator中貌似看不到Transactional Coordinator的角色。其实只要是2PC都需要Coordinator,只是Percolator把Coordinator的职责作了更进一步的细分,从而不再需要一个中心化的节点。

在2PC中,最关键的莫过于Commit Point(提交点)。因为在Commit Point之前,事务都不算生效,并且随时可以回滚。而一旦过了Commit Point,事务必须生效,哪怕是发生了网络分区、机器故障,一旦恢复都必须继续下去。

传统的2PC的Commit Point在写本地磁盘的那一刻;Percolator 2PC的Commit Point在完成BigTable事务的那一刻。为什么会有这样的区别?因为传统的Coordinator是可恢复的,参与者可以在Coordinator恢复后去询问事务的结果。而Percolator Client很可能是不可恢复的,并且它的恢复也是没有意义的。

  传统Coordinator Percolator Client
发送Prewrite请求 无本质区别
判定是否可以Commit 无本质区别
写Commit Log(提交点) 写本地磁盘 写primary的write列
发送Commit请求 发送RPC 写Secondary的write列
rollback/roll-forward coordinator发送RPC/participant主动查询 懒处理+通过lock和write列状态判断

PS:至于上文提到的,Percolator总是先操作primary,最重要的原因在于Percolator把“写primary的write列、清理lock列”作为了commit point。

故障恢复

首先明确一点:一个事务是否执行成功,只取决于Commit Point。一旦一个事务的Commit Point确定,所有写操作都最终必须确定且必须一致地接受。传统2PC从Coordinator处获取全局最终一致性,而Percolator的2PC就只能从data、lock、write这3列的状态来判断全局最终一致性了。如何从这几列数据判断出事务的提交状态,就是问题的关键所在。

事务崩溃的边界如何划分?

判断出事务的提交状态后,接着就是故障恢复。Percolator使用了懒处理的方式。一个事务执行时,会判断先前事务的状态,如果发现先前的事务故障了,则帮助它进行相应的故障恢复。这边是没有办法100%确定某个事务崩溃的,比如事务A因为网络分区而阻塞了,那阻塞多久算事务A失败呢?量变和质变的边界不是100%清晰。或者说,量变到质变的转化不是客观存在的,而是由第三方事务来决定的!Percolator只能猜测(原文suspect)一个事务失败,从而对它进行abort或者rollback/roll-forward。同时Percolator也采用了一个lightweight lock service来使这个猜测过程更迅速。

PS:回头可以发现,Percolator 2PC的commit阶段,会先判断primary上的锁是否还在。就是因为任意事务可能会被其他事务认为已经崩溃了,从而被abort。

如何判断事务的最终状态

想象一下事务B正在执行,它要操作的一行数据只有可能是2种状态:有锁和无锁。有锁状态下,一定是有其他事务A并行,事务A可能正在运行,也有可能崩溃了。无锁状态下,可能是无其他事务并行,也有可能是事务崩溃并且锁已经被其他事务清理掉了。

PS:这里的有锁和无锁,全部指代的是primary的lock列是否有数据。如果事务B操作的是secondary,需要根据secondary的lock列寻址到相应的primary的lock列。

如下图:

 

  1. 事务B发现有锁,且该锁未超时,则认为事务A正在执行。
  2. 事务B发现有锁,且该锁超时,则认为事务A已crash。此时事务B可以将事务A rollback,并继续自己的事务。如果后续事务A又恢复了,它在提交前一定会检查自己的primary lock是否在存在。所以事务A和B永远只有一个能够提交成功。
  3. 事务B发现无锁,则可能无并发事务、或者事务A已cresh但已被事务C清理。

TiDB的对“写-写冲突”的改进

首先TiDB提供了良好的控制台工具,可以查看数据库的事务冲突数量、事务重试数量以及事务延迟。根据告警可以定位到数据,从而找到对应的代码,最终可以尝试通过修改代码解决问题。TiDB在v3.0.8之后也提供了悲观事务模型:会在每个 DML 语句执行的时候,加上悲观锁,用于防止其他事务修改相同 Key,从而保证在最后提交的 prewrite 阶段不会出现写写冲突的情况。

原先Percolator的DML语句只是缓存在内存里,直到Prewrite阶段才会进行冲突检测和加锁:

 

 

对于乐观锁的实现,TiDB官方描述如下:在悲观事务模型下,DML语句在最开始就必须进行冲突检测和加锁,这里的悲观锁的格式和乐观事务中的锁几乎一致,但是锁的内容是空的,只是一个占位符,待到 Commit 的时候,直接将这些悲观锁改写成标准的 Percolator 模型的锁,后续流程和原来保持一致即可。对于读请求,遇到这类悲观锁的时候,不用像乐观事务那样等待解锁,可以直接返回最新的数据即可(至于为什么,读者可以仔细想想)。

我的想法是:

在乐观模型下,Read看到锁必须等待是因为,Read不能确定是否会有一个commit_ts小于它start_ts的事务,会在它读取之后提交。

但在悲观模型下,Read看到的lock列可能只是一个占位符,也可能是Percolator模型的锁。如果是一个占位符的话,那表示此时该事务的commit_ts必定还没有获取,所以无需等待该事务。如果是Percolator模型的锁的话,则还需要像原本一样处理。

 

 

为了避免悲观事务模型引入的死锁,TiDB实现了一个死锁检测机制。事务1对A上了锁后,如果另外一个事务2对A进行等待,那么就会产生一个依赖关系:事务2依赖事务1,如果此时事务1打算去等待B(假设此时事务2已经持有了B的锁),那么死锁检测模块就会发现一个循环依赖,然后中止(或者重试)这个事务就好了,因为这个事务并没有实际的prewrite和commit,所以这个代价是比较小的。

总结

Percolator基于BigTable单行事务实现的分布式事务,其实是一个乐观事务模型。只有在事务提交时,才会检测写-写冲突。Percolator事务模型的优点在于原理简单方便理解,不再需要一个中心化的单独Coordinator,而是把Coordinator角色的职责进行细分,把能持久化的部分交给BigTable处理,后续也不再依赖Client的恢复。但它的缺点也是显而易见的:Client和BigTable之间的RPC、BigTable和ChunkServer之间的RPC都会比较耗费网络资源。TSO是一个中心化的点。并发事务很多的时候,会占用很多内存。并发大事务可能会频繁冲突,而重试有可能会导致雪崩效应(这时候就用悲观事务模型会更好)。懒处理事务crash导致一个事务的延迟可能会比较高。

不过Percolator论文只是指明了大的方向,很多细节应该也还是存在优化空间的。

彩蛋

在Percolator中,start_ts在事务最开始的时候获取,而Snapshot Isolation隔离级别决定了该事务只能看到commit_ts先于start_ts的事务的修改。

于是对于TiDB来说,下面2个并行的事务,T2能看到的记录只有5行,因为它的start_ts早与T1的commit_ts。

但是对于MySQL来说,它能看到6行。因为它的start_ts开始于第一条SQL语句执行的那一刻。

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

 

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

 

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

T1 T2
Begin  
select count(*); -> 5 Begin
insert;  
  select count(*);
MySQL -> 6 TiDB -> 5
commit;  
  commit

 

参考资料

Large-scale Incremental Processing Using Distributed Transactions and Notifications

Bigtable: A Distributed Storage System for Structured Data

Designing Data-Intensive Applications

Google Percolator 分布式事务实现原理解读

TiDB 新特性漫谈:悲观事务

Percolator 和 TiDB 事务算法

与[转帖]Percolator - 分布式事务的理解与分析相似的内容:

[转帖]Percolator - 分布式事务的理解与分析

https://zhuanlan.zhihu.com/p/261115166 Percolator - 分布式事务的理解与分析 概述 一个web页面能不能被Google搜索到,取决于它是否被Google抓取并存入了它的倒排索引。Google管理着万亿级别的倒排索引,并且每天都有着几十亿级别的数据更新

[转帖]Percolator分布式事务模型原理与应用

https://zhuanlan.zhihu.com/p/59115828 Percolator 模型 Percolator[1] 是 Google 发表在 OSDI‘2010 上的论文 Large-scale Incremental Processing Using Distributed Tra

[转帖]Percolator 和 TiDB 事务算法

https://cn.pingcap.com/blog/percolator-and-txn 本文先概括的讲一下 Google Percolator 的大致流程。Percolator 是 Google 的上一代分布式事务解决方案,构建在 BigTable 之上,在 Google 内部 用于网页索引更

[转帖]

Linux ubuntu20.04 网络配置(图文教程) 因为我是刚装好的最小系统,所以很多东西都没有,在开始配置之前需要做下准备 环境准备 系统:ubuntu20.04网卡:双网卡 网卡一:供连接互联网使用网卡二:供连接内网使用(看情况,如果一张网卡足够,没必要做第二张网卡) 工具: net-to

[转帖]

https://cloud.tencent.com/developer/article/2168105?areaSource=104001.13&traceId=zcVNsKTUApF9rNJSkcCbB 前言 Redis作为高性能的内存数据库,在大数据量的情况下也会遇到性能瓶颈,日常开发中只有时刻

[转帖]ISV 、OSV、 SIG 概念

ISV 、OSV、 SIG 概念 2022-10-14 12:29530原创大杂烩 本文链接:https://www.cndba.cn/dave/article/108699 1. ISV: Independent Software Vendors “独立软件开发商”,特指专门从事软件的开发、生产、

[转帖]Redis 7 参数 修改 说明

2022-06-16 14:491800原创Redis 本文链接:https://www.cndba.cn/dave/article/108066 在之前的博客我们介绍了Redis 7 的安装和配置,如下: Linux 7.8 平台 Redis 7 安装并配置开机自启动 操作手册https://ww

[转帖]HTTPS中间人攻击原理

https://www.zhihu.com/people/bei-ji-85/posts 背景 前一段时间,公司北京地区上线了一个HTTPS防火墙,用来监听HTTPS流量。防火墙上线之前,邮件通知给管理层,我从我老大那里听说这个事情的时候,说这个有风险,然后意外地发现,很多人原来都不知道HTTPS防

[转帖]关于字节序(大小端)的一点想法

https://www.zhihu.com/people/bei-ji-85/posts 今天在一个技术群里有人问起来了,当时有一些讨论(不完全都是我个人的观点),整理一下: 为什么网络字节序(多数情况下)是大端? 早年设备的缓存很小,先接收高字节能快速的判断报文信息:包长度(需要准备多大缓存)、地

[转帖]awk提取某一行某一列的数据

https://www.jianshu.com/p/dbcb7fe2da56 1、提取文件中第1列数据 awk '{print $1}' filename > out.txt 2、提取前2列的文件 awk `{print $1,$2}' filename > out.txt 3、打印完第一列,然后打