project4

目录

project4 题解

概述

project4是实现percolator分布式事务协议，Percolator 是谷歌在2010发表的论文«Large-scale Incremental Processing Using Distributed Transactions and Notifications» 介绍的分布式事务协议。它是在 Bigtable 之上实现的，以 Client library 的方式实现，利用 Bigtable 的单行事务能力，仅仅依靠客户端侧的协议和一个全局的授时服务器 TSO 就实现了跨机器的多行事务。

完整的percolator分布式事务需要在tinysql和tinykv中同时实现。project4实现的是tinykv部分，主要是实现在单个节点上的操作，如：get，commit，prewrite等，更复杂的分布式流程则在tinysql实现。

要实现project4，需要了解以下点：

  1. Percolator分布式事务协议的原理、流程。
  2. 代码中三种种列族的含义，以及数据结构：lock，write，data。
  3. 需要实现的各种函数的含义和逻辑：get，prewrite，commit，rollback，checkTxnStatus，resolve，scan。

列族

Percolator 提供了 5 种 Column Family 分别为 lock，write，data，notify，ack_O。而在 TinyKV 中我们只需要使用 lock，write 和 data。

percolator的各种操作（prewrite，commit）都是围绕这三种列族进行的，因此理解这三种列族的含义和数据结构是至关重要的。

lock

格式：(key) → (primary_key, kind_of_lock, start_ts, ttl）

存储percolator的锁，一个事务在prewrite的时候尝试获取它要写的key的锁。

value中包含多种数据：

  • primary_key: 用于找到该事务的primary_key
  • kind_of_lock: 操作类型：‘put’, ‘delete’, or ‘rollback’
  • start_ts: 事务开始的时间戳
  • ttl: lock具有time-to-live时间，超时后需要解掉（被其他等待的事务）

在论文中，lock的 key部分是 (key, start_ts)，和data CF一样，但tinykv中的实现是把start_ts放在了后面，lock用来表示全范围ts的事务的lock，因为这个lock和write不一样，它只能同时存在一个版本。

write

格式：(key, commit_ts) → (start_ts, kind_of_write)

事务进行commit的时候，将它写的key写入write中。一个key可能有多个commit_ts。commit_ts只有write列族有，因为在创建data和lock列族的时候还没有进行commit。

  • start_ts: 通过value中的 start_ts可以找到data数据。
  • kind_of_write: ‘put’, ‘delete’, or ‘rollback’

data

格式：(key, start_ts) → (value)

存储value的列族，通过 key+start_ts来查找value。

实现

Part A

project4分为三个part，其中part A上实现操作mvcc事务的一些方法如：GetLock，PutLock，DeleteLock，GetValue，PutValue，DeleteValue，PutWrite，CurrentWrite，MostRecentWrite。这些方法将会在实现4B，4C的percolator接口的时候被调用。

这些方法的实现类似，主要是对三种列族进行put，get和delete。

例如PutWrite方法，是在txn.writes中append一个storage.Modify结构，该结构的Data项是一个storage.Put类型，其列族为engine_util.CfWrite，Key为EncodeKey(key, ts)，Value为write.ToBytes()的Put结构。

Delete操作基本类似，差别是将storage.Put换成storage.Delete。Get操作则是调用reader.GetCF来获取对应列族的键值。

较为复杂的是write的CurrentWrite和MostRecentWrite方法。

CurrentWrite会根据传入的start timestamp找事务的write，因为start ts在value中，所以需要通过迭代器搜索，然后不断地比较start ts来找到对应的write。被比较的start ts是事务的start ts。

查询当前事务下，传入 key 的最新 Write。

  1. 通过 iter.Seek(EncodeKey(key, math.MaxUint64)) 查询该 key 的最新 Write。
  2. 如果 write.StartTS > txn.StartTS，继续遍历，直到找到 write.StartTS == txn.StartTS 的 Write。
  3. 返回这个 Write 和 commitTs。

MostRecentWrite则是找到当前key的最新的write，相对CurrentWrite的实现更简单，因为他不需要迭代只需要对Seek到的第一个write结果进行判断其key是否匹配，之后就可以解析出write结构进行返回。

Part B & C

Part B和Part C被分为两个part，但实现的功能是类似的，都是实现percolator的接口。以下对每个接口进行介绍。

KvGet

  1. 检查要读的key是否存在lock，如果存在检查是否需要阻塞key（ttl在这里发挥作用）
  2. 获取一个mvcc reader，获取对当前事务可见的最新的数据版本（commit_ts小于start_ts的数据）

KvPrewrite

在prewrite阶段，有如下操作：

  1. 检查是否有冲突的writes，如果有报告一个“write conflict”错误。如果当前prewrite的key的commit_ts要大于当前事务的start_ts，说明有其他事务在当前事务开始后提交了，则意味着发生了write conflict, 那么当前事务需要回滚。
  2. 检查是否有冲突的 lock，如果有则报告locked error。这意味着可能同时有其他的事务正在写这个key。因此发生“写写冲突”，需要回滚。
  3. 写入 lock CF
  4. 写入 data CF

KvCommit

  1. 检查它对应的lock是否存在，如果不存在则报告错误。
  2. 删除对应的lock
  3. 向write CF中写入write信息

重复commit（例如RPC的retry）需要都返回成功，因此commit的时候需要判断一下是否有自己这个事务对应的write已经写入了，如果是直接返回成功。

KvBatchRollback

如果事务决定aborted，那么需要rollback并且清理所有的lock。

对某一个key进行rollback。和checkTxnStatus不同，checkTxnStatus虽然可能有rollback，但它是针对primary进行操作，而这里的rollback则是普通的key，即secondary key（我的理解）。

  • 首先检查当前key上是否有锁
    • 如果没有匹配的锁（不存在lock或者lock的start_ts不匹配），那么检查write 列
      • 如果不存在write，说明key没有rollback过，那么需要进行rollback，在write列写入
      • 如果存在write
        • 如果write的kind是rollback kind，那么说明已经rollback过了，不操作
        • 如果write的kind不是rollback， 说明它commit了，需要返回Abort错误
    • 如果匹配到锁
      • 并且锁类型是put，那么回滚需要删除数据，然后写一个rollback的write，再删除锁
      • 如果锁类型是其他，说明没有数据写入，那么直接写入一个rollback的write，然后删除锁

疑问：如果锁类型是 delete，这里似乎没有处理。但delete的话，是不是删除了data列的数据，那么rollback的时候不需要恢复这个被删除的data数据吗？

KvCheckTxnStatus

  1. 如果锁是一个secondary lock，那么获取（fetch）他的primary key的事务状态
  2. 如果ttl到期了，那么尝试rollback这个primary key

TODO：如何不阻塞读请求？

rollback怎么处理？

从测试代码中看到，checkTxnStatus命令是对PrimaryKey操作的，是获取primary状态的步骤。

代码中的步骤：

  1. 尝试获取锁，如果有锁且start_ts对应，那么判断是否ttl过期
    1. 如果ttl过期，那么删除其锁，并且删除data，向write列写入一个rollback类型（进行rollback）
    2. 否则说明锁没有过期，那么返回正常
  2. 如果没有锁，那么检查是否有存在的 write
    1. 如果没有write，说明这个事务abort了（如果commit了会有write记录），因此需要rollback
    2. 如果有write（currentWrite，会用start_ts来匹配该事务）
      1. 而write类型是rollback，说明它已经rollback过了，不操作（例如其他的secondary的查询，这里需要用到latches）
      2. 如果有write，且write不是rollback，说明它已提交，返回正确的commit_ts

KvResolveLock

对secondary key进行处理，根据commitTs选择进行commit还是rollback。会清理掉某个start_ts对应的所有的锁。

如果阻塞的key对应的primary已经commit了，那么当前这个secondary key也需要commit；同样，如果primary的状态是abort的，那么需要rollback。这个状态根据commitVersion来判断（0或者非0）

primary的状态代表了事务真实的状态。

这个过程在crash 恢复中非常重要。

KvScan

和get类似，区别在于scan可能获取多个值，因此ScanRequest中有一个limit参数表示扫描的结果数量。当成功找到一个符合条件的结果后，不会像get一样直接返回，而是将结果数+1，然后继续遍历，知道到了结尾或limit。

其他优化

Async commit

向客户端返回时机的优化

可以在primary key中记一些其他key的信息（适合小事务）

commit_ts的优化，它是可以计算出来的，从而优化一个从TSO获取时间戳的过程。

1PC

如果涉及到的数据都在一个node里，就可以直接第一阶段搞定了。

总结

优化会使得crash更复杂

问题

lock列，write列分别是什么含义？

write column记录了key的提交记录

  • c:lock ，在事务Prewrite的时候，会在此column中插入一条记录
  • c:write ，在事务commit的时候，会在此column中插入一条记录
  • c:data ，存储数据本身

primary列commit成功就可以直接向客户端返回成功，为什么？其他的key不会失败吗？

因为primary的commit是原子的。commit成功后，就算失败了也没事。因为会有锁留下来，然后查数据的时候，看到有锁，就会找他的primary key，如果是commit了，那么secondary也commit并且去掉锁，这样就实现了异步的commit。

在Day2 - 2.1节讲得非常好。

percolator中有哪些冲突？除了写写冲突，是否有读写冲突？

~~应该是没有读写冲突的，否则就不会有 write skew 问题了，参见 ~~快照隔离里面的“一个更生动的例子”一节, 写写之间没有交集，但A的读是B的写，而A的写是B的读，没有冲突。

有读写冲突！ 上面的例子并不是读写冲突，而是 写偏斜。

当读的时候，key被lock了，那么是要等待的。这就是读写冲突！

那如果读到的key的commit_ts比当前读的事务的start_ts更大呢？需要像写事务一样rollback吗？

不需要！因为percolator是基于MVCC的，他会保存一些历史版本信息，只需要在版本链上找到小于start_ts的最大的commit_ts对应的data就可以了！

而之所以这时会有写读冲突并不是要rollback，而是不确定这个key的commit ts是不是会小于读的start ts，因而不知道读哪个版本，而不是不能读。

先读后写就无所谓了，因为读的时候并不需要获取锁，读的时候当前key没有锁就意味着在当前key上没有正在进行的写（否则lock了）。

如果进行区分一下，读写冲突 和 写读冲突，

如果lock冲突就rollback了，为什么会有write冲突？不是同一时间只有一个事务操作一个key吗？

一个事务有多个key，可能分布在不同的region，因此可能txn1 lock了某些key，然后txn2 lock了另外一些key并且commit了，等到txn1 想lock另外一些key的时候发现这个key已经被更新了，所以发生了write冲突。

所以即使有lock也是会有write冲突的。

lock保证的是正在进行的事务间不会有写冲突。

write则保证一个正在进行的事务和已完成的事务不会写冲突。

读的时候遇到了lock要怎么处理？

首先等待一个ttl，如果到时间了lock还在，那么查询其对应的primary的状态。

这之后应该是 checkTxnStatus和resolve以及rolblack的工作了。

percolator相对于2PC有哪些改进？

将第二阶段改成了primary和secondary两种，secondary keys可以异步提交，primary的状态作为整个过程的状态，而primary可以是原子的。

因为在进行prewrite之后，整个事务就可以执行了，至于是否执行成功，percolator将这个状态保存到primary key上，它成功了，那么其他的secondary key也可以看作是成功了，就可以直接向客户端返回成功。即使后面有secondary key失败了，也可以重试。

传统的2PC要等所有的key在第二阶段都返回成功才能向客户端，因为它没有primary，所以无法保存状态，这导致当第二阶段协调者crash之后，事务就会失败。

percolator用primary key巧妙地优化了这个问题。

lock和latches的区别

lock是用来锁percolator事务的，而latches则是控制mvcc内部并发的锁。

总结

project4和project1有一定的相似之处，和project2，3之间相比较为独立，不依赖于project2，3，因此我是在实现project2之后就直接实现了project4。

实现这部分需要对percolator分布式事务协议的原理和细节非常了解，能够知道每个方法的具体步骤然后实现。遇到一些问题可以通过测试逻辑来反推一些思路，测试也是给出了各种情况下的调用。