深入理解分布式事务Percolator(三)

转载请附本文链接：https://blog.csdn.net/maxlovezyy/article/details/99707690

本人在字节跳动，欢迎加入我司，欢迎自荐，私聊即可。

实现篇

这里设计实现的时候充分借鉴了TiDB相关的设计，当然也有一些自己的思考。

本篇在前一篇做了一些思考后，详尽地讲述一下分布式事务Percolator的具体实现，充分地考虑了工程问题。如果你是分布式的新手，相信在消化吸收之后会有一套自己对分布式事务以及分布式系统的注意点和设计有一个更深刻的认识。

数据模型

data	lock	write
key	{encoded_key}{start_ts}	{encoded_key}	{encoded_key}{commit_ts}
value	{value}	{flag}{pk}{start_ts(varint)}{ttl(varint)}{min_commit_ts(varint)}{committing}{has_short_value}{short_value}	{flag}{start_ts(varint)}{short_value}

每一个列对应数据层的3个列，意义参考Percolator。这里value相对于Percolator做了细化，主要是针对异常以及mvcc做的设计。

• lock value:

  flag

  触发上锁的动作，类型为put、delete、lock；

  pk

  即Percolator中的primary key；

  ttl

  是lock的生命周期，用于清锁超时等判定；

  min_commit_ts

  用于优化读事务，写不阻塞读，

  committing

  用于配合防止不停commit失败；

  has_short_value

  是针对short_value为empty时的效率优化(load prewrite的时候不需要额外load data列来判断data是否为空)；

  short_value

  是针对小value的优化，不写data列，直接放到write里。
• write value：flag类型为put、delete、lock、rollback；short_value参考lock value。
• 各个列key中的ts都是memcomparable的编码方式

关键设计

1.MVCC

目前大多数分布式事务都主要支持SI隔离级别，Percolator也一样，其通过mvcc机制实现SI隔离，达到读写互不干扰，提高并发能力。Row或者cell的不同版本通过单调递增的ts标识，为了保证事务的一致性，删除的时候并不in-place删除，而是标记删除。因为如果直接删除了，可能会导致其他的读事务得到不一致的数据，比如事务T1先后读a和b两行数据，假设是in-place删除，可能在T1读a和b中间，另一个事务T2把b删除了，之后T1再读b的时候就会拿到了不一致的a和b的视图。

2.Lock列flag字段

Lock列的value为什么要有flag呢？假设没有这个flag标识请求类型，通过事务client发请求commit时固然没问题，因为client可以缓存并传递过来，但是加入client已经把primary提交了，之后就挂了，当resolve lock的时候就没有办法决议请求类型了，所以lock列需要保存类型flag。

3.Lock

为了应对select … for update的需求(对于lock in share mode是不需要应对的，参考FAQ2)，需要支持行锁，这里拿具体例子来说，假设有如下事务：

txn start

select a … for update

update b …

txn commit

由于乐观的模型，遇到select a … for update之后依然只是添加了一项mutation，type是lock，遇到update b … 的时候依然是一项mutation，type是put，等到commit的时候走2PC。由于a又一个lock类型的mutation，所以prewrite的过程是完整存在的，如果过程中有其他事务先行执行了并与本事务的a mutation冲突了，则本事务失败，整个过程类似于一个CAS的过程。至于为什么write列要有一个Lock类型的记录，而不是在a mutation提交的时候直接删除a的lock列，请看FAQ4。

范围级的锁(比如表锁和range锁)和row级别的是各自独立的，范围级的锁走分布式锁的思路，在外围做锁管理，并不冲突。具体实现的时候，假设支持了范围级锁，对于不需要范围级锁的业务也可以通过hint或者配置的机制绕过对范围级锁check的性能损耗。

4. 死锁/活锁避免

不同事务之间可能出现相互依赖的死锁情况。比如两个事务t1和t2都依赖a和b两个资源，t1先拿到了a的锁，同时t2拿到了b的锁，这样就陷入了死锁。

这种情况对于本事务模型存在吗？显然是不存在的。Percolator对于并行事务的写冲突的处理办法是遵循First-Write-Wins(FWW)原则来防止lost-update异常，又因为当前设计都是事务接口访问存储层的锁，会通过这种类似乐观的方式发现锁冲突并取消自己，所以事实上Percolator是不存在死锁的情况的。但是却存在活锁的情况，就是t1和t2相互冲突来回取消。

对于上面提到的活锁，一个naive的解决办法就是每一个事务都对其所有buffer的row进行全排序且按序prewrite，这样first prewrite的txn就会win。但存在的问题一个是one by one的方式性能太差，一个是存在大事务buffer过大的资源限制和排序性能损耗。

本设计采用的办法是参考了常用的解决死锁的两个方法：Wait-Die和Wound-Wait，采用的是Wound-Die的方式。即对于任意一个事务，如果在prewrite的时候遇到比它年轻的事务加了lock，则尝试直接强制resolve lock(不等)；反之则abort自己。可以看出，解决的原理就是对并行事务进行优先级的排序。为什么不采用Wait-Die或者Wound-Wait？因为Percolator为了通过FWW的方式解决lost-upadte异常，所以wait的事务之后必然会冲突，没有任何wait的意义。

5. 单条GC

由于mvcc机制，随着服务的运行，会有越来越多的冗余数据存在，必须有垃圾回收机制对旧版本的无用数据进行清除。GC设计的关键是找一个safepoint，之后开始清除全局的所有key对应的write列ts小于safepoint的数据。

1. 准备阶段

   事务的提交是2PC，在commit的过程中是可能出现某个Secondary commit过程中崩溃把lock和data留下的情况，这种情况是需要读请求去resolve的。在GC过程中如果遇到了lock时间戳在safepoint之前的这种锁，就必须进行resolve，所有涉及GC的row都resolve之后才可以进入执行阶段。因为如果不resolve，存在其primary的write记录被GC掉了导致这个未决议的Secondary无法决议，数据不一致出现的情况。

2. 执行阶段

   GC遇到类型为put的记录不能直接删除，因为有可能这是唯一一个记录，删除了数据就丢失了。GC遇到类型为delete的记录也不能直接删除，需要删除比其ts小的其他记录后再删除本记录，因为如果其后面跟着一条类型为put的记录，这时候如果先删除当前delete记录，则后面的put就是可见的了，这是错误的。具体流程如下：

   初始化can_remove = false，need_delete_ts = invalid, next_ts = safepoint

   i.扫描小于等于next_ts的版本，如果为空，则转到iv；否则得到当前key的commit_ts，next_ts = commit_ts - 1转到ii

   ii.如果can_remove为true，则删除当前版本的key，后转到i；如果can_remove为false，则转到iii

   iii.如果当前数据类型为put，则标记can_remove为true，后转到i；如果类型为delete，则标记can_remove为true，设置need_deleted_ts为commit_ts，后转到i；如果类型为rollback或lock，删除commit_ts数据，后转到i

   iv.如果need_deleted_ts有效，则删除need_deleted_ts版本的数据(清理前面遇到的delete类型的write，delete不能直接删，需要GC的最后删，否则会暴漏它下面的类型为put的write)，GC结束

6. 分布式GC

a.safepoint

一般而言可以配置一个mvcc的多版本数据的生命周期，通过TSO的now减去lifetime得到safepoint。Lifetime也必须大于事务的最大生命周期，这样能保证每一次的GC遇到ts小于safepoint的包括primary row可以直接处理，无需担心一致性（参考FAQ6）。

当然，safepoint的确定不能单单是通过【当前所有事务的start time的最小值】 确定，还需要考虑未决议的锁。因为假设数据现场是下图这样，如果gc的safepoint确定为7，那么一旦k1的write列[email protected]被gc之后，k2就没法决议了。所以gc发起之前要扫描集群所有小于初始safepoint的锁，有的话就resolve，等都resolve了就可以执行gc了。

b.分布式

对于上面提到的naive形式的GC，有几个显而易见的问题：

i.单点处理GC逻辑，集群大的时候可能受限于CPU、网络、QoS(比如可能有表格存储服务针对单ip的限流)等方面导致忙不过来，集群的GC速度过慢

ii.当集群数据量大了或者负载高的时候，可能出现一轮GC时间过长，具体执行partition GC时有滞后情况的出现。比如当前判定GC的safepoint是t1, 当GC处理某一tablet数据的时候，其实时间已经很滞后了，这时候其实safepoint早都可以更新为t2了，tablet扫出来的时间小于t2的数据而非小于t1的数据其实都可以清理了。

针对上面提到的问题，可以通过下面的优化点解决：

i.safepoint的计算独立出来

ii.GC master实时根据safepoint计算生成tablet级的GC task

iii.GC worker向master认领GC task

7. 长事务的支持

由于TransactionProxy需要缓存mutations，内存空间有限，如果支持的话就需要分批prewrite并记录key(keys空间很大还需要持久化)而非commit的时候再一起。另外为了避免GC等导致resolve长事务，需要为其lock续ttl或者压根写死大事务lifetime上限(存在挂掉之后事务很久不结束的可用性问题，但心跳续ttl不存在此问题)。大事务的方案需要解决三个问题：

1. 目前mutations是完全缓存在内存的，对于大事务理论上proxy的内存是会撑不住。

   解决方式有两种，一种是限定大事务的最大batch大小，比如说1G。目前的服务器支持这样的大小应该都还OK。还有一种是分批prewrite，但这里有一个问题就是不能全局排序，导致可能出现活锁，或者性能问题。比如两个事务有交叠，a、b、c，如果一个事务t1 prewrite了b，另一个事务t2 prewrite了a、c，假设t2 prewrite b发现冲突之后abort，可能与此同时t1也发现了a、c冲突abort b，都失败了。而如果全局排序了，以order的方式进行prewrite就不会有这个问题。一期先全攒在内存。

2. 每一个事务根据大小都有一个默认的ttl为了防止事务的coordinator hang或者crash。对于大事务会有lifetime大于初始ttl，导致事务中途大概率会被resolve的情况。

   通过keep-alive的方式解决这个问题。Coordinator会启动一个异步线程对primary的ttl进行续约，同时也会结合GCMaster把safepoint统一起来，以防止因此带来的数据不一致和可用性问题。

3. 大事务会影响读的可用性。因为Percolator的设计上目前读遇到锁是需要等待或lock超时进行resolve的，是不可以直接返回最新数据的，会出现幻读、不可重复读问题。

   通过给lock列加一个min_commit_ts解决这个问题。当读遇到lock的时候，就把min_commit_ts改成读事务的start_ts + 1。当写事务commit的时候遇到由于commit_ts expire错误时修改commit_ts为min_commit_ts再进行commit。这里可能存在的一个问题就是对于热读可能导致commit频繁失败重来。可以在lock列增加一个committing状态位，当commit发起失败是因为commit_ts expire导致的，则改committing状态为true，如果处于committing了则不可以更改min_commit_ts了。

4. 大事务会影响GC的回收时效性。因为朴素的实现方式下GC需要先resolve所有在next candidate safepoint时间点之前的lock之后才可以进行GC，否则有可能把primary的commit(Percolator write列) ROLLBACK/COMMIT记录删掉了但secondary的lock还在进而无法决议了的问题。

   参考3中提到的优化，resolve lock时可以这样解决此问题。对于primary lock在的情况，直接提高primary lock的min_commit_ts到一个大于next candidate safepoint的值即认为GC需求下的resolve lock行为成功了；对于primary lock已经不在了的情况(已提交或回滚)，直接resolve secondary即可。所有在next candidate safepoint时间点下的lock都resolve了之后就可以以它作为ready的safepoint进行GC了。与此同时大事务/长事务依然没有被cancel掉。

   值得注意的是，直接这样做其实隐藏了一个问题就是这样做会破坏一致性快照，出现幻读。 为什么呢？比如当前有一个事务时间戳是t1，它是可以见到时间戳小于等于t1的数据的，但其实当时可能有t2版本的数据存在的。如果通过上面的方式使得大于t2时间的safepoint得以生效开始GC，那么t1版本的数据会被回收掉，会导致事务出现幻读。解决这个问题其实也很简单，而且这其实是一个普适的解决方案：每个事务在提交的时候都需要去gc master获取一下当前的safepoint，如果safepoint大于事务的start_ts，则可能有问题，事务需要abort。为什么说是普适的呢？因为即便没有本优化，对于一个事务，如果单单靠定死的超时来控制gc带来的可能的破坏快照的问题也是会存在问题的，因为client和server是可能存在时钟漂移的，gc master开始生成新的safepoint并开始gc的时候safepoint之前开始的事务的client可能还没有超时，它有可能读到被GC破坏了的快照。所以要保证绝对的一致性就必须在提交的时候获取一次safepoint进行比较。那么有没有可能某一个事务频繁地被这种case(safepoint更新)abort呢？对于小事务，一般是不会的，retry大概率会成功，因为gc周期就算再小也不会太小(比如60s够不够小)，retry很难碰上safepoint再次更新。如果这时候要有一个稍微大的事务(执行时间超过了gc周期)进来确实是可能会出现一直被abort无法成功，但这个问题其实不能算是本优化引入的问题(但也算是因本优化而起，因为本优化的目的就是要缩短gc周期以应对高ops系统的gc回收迟滞导致版本过多性能退化问题)，而是gc的周期设置本身就和业务不相配的问题，也可能是gc周期是静态的，本身太泛泛，无法满足各种case。这种其实可以提供一种hint机制让用户可以显式地动态修改gc的周期，甚至系统可以主动探测到这样的问题进行自动优化。

   不过这里其实还隐藏了另外一个问题，那就是大事务本身会被abort的问题，一旦提升safepoint，大事务本身也就会被abort了。 怎么办？可以有一个比较trick的解决方案，就是每一个事务都要向gc master申请一个指定ts的gc lock(事务的start_ts即可)，gc master的safepoint不可以大于所有gc lock的最小时间。什么时候解锁呢？当事务进入到committing状态时或者干脆加一个类似于FreezeRead接口(不会再有读了)就解锁。

   到这，也会惊喜地发现这样解决的话上一个问题也就不是问题了哈哈。

8. TSO

a. Leader批量获取范围ts，以避免每次get ts都需要走raft。另外为了避免单机获取时间的系统调用有瓶颈，可以把ts做一个变换，仅保留毫秒或秒级的精度，其余位由该毫秒或秒内的一个单调递增的数字取代。感觉秒级精度完全能满足GC对于时效性的需求，还有什么其他问题没？ts其实需求就是一个单调递增的数字即可，如果不是GC有时间概念，ts完全可以仅是一个单调递增的数字。这里其实还可以有一种设计：TSO分配的ts就只是一个纯粹的单调递增的数字，但是定期(比如秒级)去记录当前秒内所分配的ts边界并同步GC master，由于ts和时间都是单调递增的，所以GC的时候可以通过GC master获取到safepoint点内最大已分配的ts，再进行GC，这样设计ops可能又会高很多。如果实在是要支持超高ops，也可以将ts扩展为<ts, id>的组合，其中id为uint64_t类型单调递增的数字，这样的话不考虑其他瓶颈因素理论上每秒可以支持uint64_t::MAX_VALUE的ts分配ops。目前采用秒级时间戳+id组合在一个int64_t中的方法。

b. TrueTime、extend HLC。好处是不冲突的情况下支持的 ops会增加，但是引入的问题是时间架构的复杂性以及请求增加的额外延迟。

9. 跨表事务

在Lock列value的primary中增加表信息。

10. 共享事务

有多个不同TransactionProxy client共享一个事务的需求。这个需求对整体事务模型来说是不具有侵入性的，看起来也是一个分布式下合理的需求。各个client可以共享一个事务session，session id其实就是事务的start_ts。有两个的方案（暂不考虑大事务）如下：

方案一

• Client

1. Client leader(request proposer)创建一个【共享】txn，记录session
2. Client leader向worker分发请求，其context中带有txn的session
3. Client worker各自通过session发起join txn请求，发起数据操作请求
4. Client leader收集worker的response发起commit/abort

• TransactionProxy

1. 创建的事务类型为共享事务，通过TransactionManager™创建事务session
2. 各个proxy有txn join之后，向TM注册
3. 各个proxy对于读立即执行，对于mutations缓存下来
4. TM收到commit之后，对注册在此session的Proxy发起PreCommit请求
5. 各个proxy收到PreCommit请求之后回复一个推荐的primary
6. TM确定一个primary，对其发起prewrite
7. Primary proxy成功后返回TM结果
8. TM对所有secondary并行发起prewrite，TM根据各个proxy的结果决定commit/abort
9. TM对primary发起commit/abort，返回给client leader结果，并根据结果对secondary作出相应处理

方案二

与方案一相比，方案二把各个client的事务请求归到了同一个proxy上，session中加入了proxy的ip，txn client sdk在处理的请求的时候通过session中的ip处理，这样与方案一的【TransactionProxy侧】相比，不需要TM的存在了，因为所有mutations信息都在一个proxy之中了。

当然上述方案细节上还需要考虑各种超时以及错误等cases，TM也是一个故障域和可能的性能瓶颈点（假如采用方案一）。另外对于大事务不能完全缓存mutations的情况下，也能有效支持，无非就是提前选一个primary分批次prewrite而已。

FAQ

Q1 为什么需要持久化对数据的lock到lock列，而不是仅仅在内存中？

A1 分布式的情况下，同一个事务的数据分布在不同的服务器上，如果lock仅仅在内存中，那么一旦某个secondary row所在机器挂了，lock信息就丢了，原子性也就没了。而且Percolator的lock列设计巧妙，lock中包含了primary信息，能把同一个事务中的数据串起来，这个串起来的信息也是必须持久化才能保证一致性(比如如果不持久化，假设primary已经commit，未提交的secondary挂了重启之后不知道自己的状态了)、原子性的。

Q2 锁的实现只提到了for update的写锁，lock in share mode的读锁呢？

A2 这就是SI隔离的好处，读是针对快照的，mvcc的写不会与读冲突，故不需要读锁。

Q3 为什么write列需要写rollback标志的数据？

A3 可防止处理迟到的无用prewrite。当然也可以不写rollback标记，有resolve逻辑不会影响正确性。

Q4 在lock的实现中，为什么write列需要写lock类型的数据，而不是commit的时候直接清除lock列类型为lock的数据？

A4 由于Percolator的mutation是buffer在client端的，一次性prewrite获取锁，整体上等于是乐观锁模型，所以没办法在事务中遇到select … for update就先在资源层lock住，只能造一个write type为lock类型的记录，在txn commit的时候根据prewrite的这个lock mutation做一个类似CAS的check，失败了说明这个txn开始的select … for update失败了。至于commit时为什么要真正把这个lock写到write里而不是遇到lock列的类型为lock直接简单删除，原因是如果不在write列写入一个commit，可能有stale的txn提交数据。而且有了这个标志还能保证幂等性，commit之后再commit不会出错。对于可以防止stale txn提交数据的情况，可参考如下例子(站在client使用的视角)：

1. Txn1
          t2 : create
          t3 : select a ... for update
          t5 : if(a.exist) update b.pid = a
          t6 : commit.prewrite(client commit事务之后proxy的第一阶段)
          t7 : commit.commit(client commit事务之后proxy的第二阶段)
      2. Txn2
          t1 : create
          t4 : select a ... for update
          t8 : if(a.child == empty) delete a
          t9 : commit.prewrite
          t10: commit.commit
           

如果txn1 commit的时候不在write写入lock类型的a，那么txn2这个start_ts小于txn1 start_ts的事务是可以提交成功的。这样txn1和txn2就依然有write skew的问题，b.pid指向的parent a还是会被删除掉而b成了孤儿。所以lock类型的mutation提交的时候必须在write列写入类型为lock的记录。

可能有的人会想语义上来看是没必要必须失败一个事务的啊，假设是Mysql非SI隔离级别比如RR级下这样做结果会是两个事务都成功，而本事务模型为什么出现这种case就必须失败一个？其实本质原因就是本文设计的事务是lazy的CAS check形式的锁，select … for update一行读取到的数据在当行及以后的使用中并没有处于受保护的临界区之中，而Mysql非SI隔离级别下则不同，其会是直接先lock住for update的row，之后的处理都处于lock的保护之中，不会出现隔离和一致性问题，所以都会成功，而本文涉及的事务模型就必须失败一个才能保证一致性。

Q5 为什么不能in-place删除而要标记删除？

A5 假设是in-place删除，可能在T1读a和b中间，另一个事务T2把b删除了，之后T1再读b的时候就会拿到了不一致的a和b的视图。

Q6 GC可不可能resolve的时候，判定事务超时了，进而rollback了事务导致一致性问题？GC可不可能回收了某个doing的start_ts小于safepoint的事务涉及的row的旧版本，进而 导致本能读取到这个row的一致性旧版本却读不到了？

A6 第一个问题不是问题，因为不会导致数据的不一致。第二个问题也不是问题，可以把lifetime设置的长一点，保证gc回收到的只能是老数据，保证safepoint之前的所有事务都要么已完成，要么已经处于超时的失效状态。对于失效状态的事务，客户端也造就cancel了，即便读到不一致的视图也无所谓， 因为用户压根见不到。

Q7 事务与二级索引的关系是怎样的？

A7 二级索引属于在另一套名字空间下的数据。如果要维护二级索引与数据的强一致性，那就需要跨表事务的支持。如果仅需要异步的二级索引，则二级索引的建立和事务没关系。

Q8 事务的lock ttl如何考虑？GC的lifetime如何考虑？

A8 事务lock的默认ttl应该配置为大于业务上一般情况下事务执行生命周期的一个值；GC的lifetime应该配置为大于事务ttl的一个值。这里涉及到了可用性与一致性理解上的语义问题，所以需要服务和业务方仔细斟酌配置。