谈一谈分布式事务

在传统的数据库中，有一个叫事务的东西，他的特性是ACID，对这个不了解的可以参考我的(数据库系列文集)[https://www.jianshu.com/nb/36265841]，里面第13篇是讲单机下的数据库的事务。

在单机版的事务中，有并发控制理论和保证原子性持久性的策略。

所谓并发控制理论，主要分为两类。乐观派和悲观派。乐观派认为事务间的冲突是稀少的，没有必要做什么防范，当真的遇到了再去补救。而悲观派认为事务之间冲突的经常的，与其事后补救不如提前预防。上面的补救就是事务间的写读冲突或写写冲突检测。而提前预防就是加锁保护事务需要的资源。

所谓原子性和持久性的保证是通过一个2维概念决定的。其中分为STEAL, NO STEAL。 FORCE 和 NO FORCE。 所谓STEAL就是DBMS允许一个未提交的事务刷进磁盘。NO STEAL就是不允许。 而FORCE是DMBS强制事务提交时所有改动都刷进硬盘，而NO FORCE是不强制（只要LOG落库即可）。 根据上述选择，我们会有不需要LOG,只要REDO LOG, 只要UNDO LOG，2者都要，4种可能。

image.png

那么总结下单机事务的关键词。
悲观策略是2阶段锁定，乐观策略是TC或者OCC，配合MVCC。2阶段锁定需要死锁预防或死锁检测。

介绍完了单机事务，我们来聊下分布式的事务。

还是一个最简单的例子，银行转账。
A,B账户上初始各有10块， A给B转1块。
另外一个事务读A的账户的余额，和B的账户的余额
那么如果是事务，读要么看到2个还是10块，或者是A 9块，B 11块。不可能看到其他状态。这在单机事务中被保证了。可是分布式的环境下，可能会由于网络是延迟，服务的宕机，造成其他状态的出现。一致性是问题，持久性也是问题，原子性也是问题。

事务也需要ABORT。比如做事务的时候发现这个ACCOUNT不存在。或者发现了死锁，需要打破死锁。或者处理事务的服务器挂了，事务也需要回滚。

如何验证事务的可序列化属性呢？也就是说存在一个顺序，使得结果是和一个一个完成事务的结果是一致的。比如上面2个事务

  T1:
    begin_transaction()
    add(x, 1)
    add(y, -1)
    end_transaction()
  T2:
    begin_transaction()
    tmp1 = get(x)
    tmp2 = get(y)
    print tmp1, tmp2
    end_transaction()

下面2种顺序都可以。

for our example, the possible serial orders are
    T1; T2
    T2; T1
  so the correct (serializable) results are:
    T1; T2 : x=11 y=9 "11,9"
    T2; T1 : x=11 y=9 "10,10"

如果T1的执行发现在2个T2的GET之间，T2就会输出10，9
如果T2跑在T1 2个ADD间，T2就会打出11， 10

事务的好处就是可以方便程序员去写程序。
那么2类分布式控制的手段有悲观的，在使用前上锁，冲突会引起延时（因为要等待锁）。乐观的，冲突会引起回滚。但是如果没有冲突要比悲观的快的多。

下面我先介绍悲观的方案，随后通过FARM来介绍乐观的方案。
上面我们提到在单机下有2阶段锁定可以来实现可序列化。它的定义是，一个事务在使用一个数据库条目前，必须要拿到它的锁。这个事务必须要一直持有这把锁直到事务被提交或者回滚。
具体细节可以参见CMU 15445 14.二阶段锁定 + homework 4

为什么要一直持有这把锁直到事务提交或回滚呢？ 不可以这个条目用完了就直接释放锁吗？
下面举一个反例。（根据上面的例子）
假设T2 释放了X的锁在get(x)之后。这个时候T1就可以执行在2个T2的GET之间。
那么T2就会打印出10,9；
所以这是会有问题的。

还有一个就是，如果T1写了X，随后释放了X的锁。随后T2就可以读X了，这个时候T1 ABORT，这样T2就使用了一个根本没存在的值。

有了2阶段锁定，我们在分布式的环境下还需要2阶段提交。
具体细节可以参考第8章 二阶段提交

因为在分布式的环境下，我们要确保所有涉及到的SERVER要么全COMMIT，要么全ABORT。不能有一半COMMIT，一半ABORT的情况。那么SERVER挂了就需要有应对手段。

这二阶段提交里，有一个机器被称为协调者（TC）,CLIENT把要做的事务发给TC，TC会知道这些事务涉及的数据会去哪些不同的机器。随后把这些命令发到那些机器上。当TC看到这个事务里的操作都发完了。他会向所有涉及的机器，发送PREPARE消息。
如果A 或B认为可以COMMIT，就会回复TC，YES。否则,NO
如果全部的机器SAY YES， 那么TC就会发送COMMIT消息。只要有一个SAY NO， TC就会发送ABORT。
A和B会在自己的DB LEVEL去做COMMIT，当收到COMMIT消息时。

如果B 挂了并且重启会如何？

如果B是在发了YES后挂的，B肯定会记得，因为YES会落库。然后重启之后，B会拿着YES继续发给TC，如果TC是COMMIT，B会COMMIT。

如果TC挂了重启会如何？

如果TC发出了COMMIT在挂之前，因为COMMIT会落库，所以TC一定记得。所以TC会回复COMMIT，如果有人来问他。

如果TC没有收到B的YES/NO会如何？

可能由于B挂了没有恢复，可能网络坏了。TC会TIME OUT然后发送ABORT。好处就是可以让其余SERVER释放掉锁。

如果B超时或者挂了在等来自TC的PREPARE怎么办？

B可以自己先ABORT掉，如果将来TC发来了PREPARE，B只要告诉TC NO就可以了。

如果B发了YES，但是没有收到TC的COMMIT或ABORT怎么办？

B只能一直等待，除非他知道有别的机器发了NO。不然只能等TC的结果。

上面介绍了2阶段锁定，他可以使得分片的DB支持事务，但是他有很多不好的地方。比如，多轮的消息很慢，有很多硬盘的写也会很慢。锁会被持有在PREPARE/COMMIT的阶段里。
所以这个技术通常被用在一些特定的领域。比如没有跨行，跨地区，跨大范围的时候。

RAFT 和 2阶段提交是解决不同的问题的

RAFT 是获得高可用性通过复制，2PC是确保所有的机器做好自己的事的。
所以2PC不能帮助可用性，RAFT也不能确保所有机器做好了自己部分的事。

如何同时保证高可用和原子提交？
每一个机器都是RAFT-复制的服务。当然TC也需要是RAFT复制的。
那么跑2阶段提交在这些复制的服务上。我们就可以容错，并且不会阻塞住。LAB4就是这么一个LAB，我们需要构建这样一个系统来TRANSFER SHARD。

乐观控制

上述的方案虽然解决了分布式的事务，可是性能并不理想。有没有一种方案可以更高效的解决分布式事务这个问题呢？

微软研究院在2015年发了一篇(FARM)[http://nil.csail.mit.edu/6.824/2018/papers/farm-2015.pdf]的PAPER，使用了2种新的技术使得分布式事务变得非常快。

速度有多快呢？
像MEMCACHE这种内存里的CACHE大概可以只吃大吉 100万个操作每秒。这套FARM的分布式事务可以支持单机100万个事务每秒。非常惊人。

这么高的性能主要是通过一个非易失的内存 + 单边RDMA 这2个技术实现的。具体内容可以参见我的这篇博客No Compromises: Distributed Transactions with Consistency, Availability, and Performance
除了上述2种基础设施，这篇论文也主要说明了如何在这2个技术的帮助重新构建事务+复制的协议。

我们来看下性能比对。
FARM直接去写RAM，消除了磁盘的瓶颈。
写一次RAM需要200纳秒， 写硬盘需要10毫秒，写SSD需要100微妙。
有一种做法是去写F+1台机器的内存来容忍F台机器失效，为什么不这样做呢？
因为断电不是一个独立的失效事件，很有可能就100%的机器就一起断电了。所以这边采用了非易失的内存 ，大概原理是在断电的情况下，会启用自己的备用电池来把所有内存里的状态刷到SSD上，然后电力恢复后，把SSD的内容重新载入回内存。

那有没有可能因为软件的失效使得写SSD造成错误呢？比如BUG 在FARM或者KERNEL里
这个时候FARM会保证有F+1的COPY来容F个的错。在这里的错和断电不同，必须是独立的。

消除了写磁盘的瓶颈，还有一大瓶颈在分布式事务里就是网络通讯。
需要系统调用，复制消息，中断，RPC使得上面的步骤都是2次。
RPC调用是非常慢的

为了提升这方面的速度，必须要绕过内核。应用必须可以直接流式访问网卡硬件。直接和网卡交互，这样不需要系统调用，不需要内核。发送者直接给NIC（网卡）一个RDMA的命令。接收方软件轮训RMDA写入的内存。
从宏观上说，这里就是发送者可以直接去读写接受方的内存。而不需要经过接受方的CPU，接受方的硬件会返回一个硬件层面的ACK。这里面没有中断，没有KERNAL，没有复制消息。所以非常快。在单机的吞吐量可以达到1000W 每秒。
延迟达到5微妙。

FARM利用RDMA在3个方面：
单边读OBJECTS在事务的执行阶段（还有VALIDATE阶段）
由对主日志或消息队列的单边写组成的RPC
还有对备份的日志的单边写

下面就是一个难点，如何利用RDMA的单边读写来实现事务和复制。（在悲观的并发控制方案里，事务和复制是利用2阶段提交+RAFT来实现的）

FARM采用了乐观的并发控制（OCC）。原因是OCC使得FARM可以利用单边读，那么因为OCC就不需要加锁，就不需要CPU。那么FARM如何来VALIDATE事务提交时的读写，写写冲突呢？

在讲分布式的方案前，小伙伴们可以参考我这篇博客。了解非分布式环境的OCC是如何运作的CMU 15445 15. TO + OCC + MVCC

每一个FARM的服务器会运行应用的事务，这个应用事务就是自己的TC（事务协调者）

FARM事务API

  txCreate()
  o = txRead(oid)  -- RDMA
  o.f += 1
  txWrite(oid, o)  -- purely local
  ok = txCommit()  -- Figure 4

TXREAD 就是单边的RDMA去拿OBJECT从primary's 的内存，非常快。当然还需要那这个object's 的版本号，用来检测有没有并发写。

TXWRITE 必须在TXREAD之后，只写本地的COPY，没有网络通讯。

每个OID里会有<region #, address>
region # 索引到一组映射[ primary, backup1, ... ]
目标网卡可以直接使用address 去直接读写内存。所以目标CPU不会被涉及。

那么其他SERVER，非PRIMIARY，会去用RDMA写来的LOG，和消息队列到他们的non-volatile RAM。

每一个REGION复制到一个PRIMARY, 和F个BACKUP，组成了F + 1个REPLICAS
只有PRIMARY提供读，所有的F+1会看到提交和写。 复制提供了可用性当挂掉的机器<=F个，所以要比RAFT更好（2F+1容错F个）

下面我们来看当没有失败时事务是如何执行提交的？

image.png

STEP 1. LOCK（在COMMIT阶段的第一个消息）
TC发送给每个写对象的primary
TC使用RDMA去APPEND LOG 给每个primary
LOCK记录包含一个OID, VERSION # 和一个NEW VALUE
primary 会轮训LOG，看到LOCK，回去验证，然后发送YES 或NO的验证结果。
LOCK会同时记录在primary's NVRAM 和RPC交互里。

验证逻辑

(for each object)
  if object locked, or version != what xaction read, reply "no"
    implemented with atomic compare-and-swap
    "locked" flag is high-order bit in version number
  otherwise set the lock flag and return "yes"

TC等待所有LOCK返回消息，如果有一个NO，就ABORT.就会发送ABORT给那些primaries ，他们会释放LOCKS，然后return no from txCommit()

如果全部为YES，TC会发送COMMIT-PRIMARY给写对象的primary
使用RDMA去APPEND LOG。随后TC只要等到硬件的ACK，TC就可以returns "yes" from txCommit()

primary 当发现COMMIT-PRIMARY在他的LOG里需要被处理时，会做：

1. 把新的VALUE复制进OBJECT的内存
2. 增加OBJECT的版本号
3. 清除OBJECT的LOCK FLAG

例子

  T1 and T2 both want to increment x
  both say
    tmp = txRead(x)
    tmp += 1
    txWrite(x)
    ok = txCommit()

R代表READ,L代表LOCK，C代表COMMIT

T1: Rx0 Lx Cx
T2: Rx0 Lx Cx

  T1:       Rx0 Lx Cx
  T2: Rx0                 Lx  Cx

or
  T1: Rx0  Lx  Cx
  T2:                     Rx0  Lx  Cx

如果没有冲突，版本号不会变，COMMIT是可以的
如果冲突了，一个人会看到LOCK，或者版本号变了。

图片4的VALIDATE，和OCC的VALIDATE不是一个概念。他是一个优化对那些OBJECT只读的事务，VALIDATE = 单边RDMA读OBJECT的版本号和锁标志。如果锁被SET了，或者让版本号在读的时候改变了，那么TC可以直接ABORT，就不需要去SET LOCK，所以比上面的LOCK+COMMIT要更快。

OCC的VALIDATE例子

x and y initially zero
T1:
  if x == 0:
    y = 1
T2:
  if y == 0:
    x = 1
(this is a classic test example for consistency)
T1,T2 yields y=1,x=0
T2,T1 yields x=1,y=0
aborts could leave x=0,y=0
but serializability forbids x=1,y=1

假设T1,T2同时

  T1:  Rx  Ly  Vx  Cy
  T2:  Ry  Lx  Vy  Cx

LOCK阶段2边会同时成功，但是VALIDATE阶段2边会同时失败。因为LOCK FLAG都被设置了。2个TX都ABORT是可以接受的。

另一种情况

  T1:  Rx  Ly  Vx       Cy
  T2:  Ry             Lx  Vy  Cx

那么T1可以提交，T2会ABORT。因为Vy的时候会发现T1的锁或更高的版本号。
因为我们不能使得2个V都在另一个L之前，所以不会发生X=1,Y=1的情况。

容错

如何保证持久性，可用性？，正在进行的交易的完整性，尽管崩溃，网络发生了分区怎么办？

每个region的f+1副本，以容忍<= f故障在每个区域
TCs向所有副本发送所有的写操作(TC的COMMIT-BACKUP)
如果服务器崩溃，不能立即使用。事务读取和提交将等待。但是CM（configuration manager）很快就会注意到，做一个新的拷贝，恢复事务

重新配置
一个zoo keeper集群(少量副本)
仅存储配置号、此配置中的服务器集和CM。 如果多个服务器试图成为CM，则打破平局，使得只有一个服务器可以成为CM。
如果分区发生了，则选择活动分区(多数的分区)

一个Configuration Manager(CM)(未复制)
通过快速ping监视所有服务器的活动
管理重新配置

1. 更新租赁，只有当它得到大多数机器的响应时才会激活
2. 检查每个区域至少有一个副本存在
3. 将区域分配给主/备份集
4. 告诉服务器创建新的副本
5. 管理中断事务的完成

任何提交的事务都是可见的，尽管服务器出现了故障

当TC从所有LOCKS或者VALIDATES看到“yes”，TC将提交备份附加到每个备份的日志中
在全部ack后，会将COMMIT-PRIMARY附加到每个primary的日志中
在一个ack之后，报告“commit”到应用程序

注意TC复制到backup;primaries 不复制. COMMIT-BACKUP包含写值，足以更新备份的状态

为了容F的错，所以必须全部的BACKUP回复YES，才可以进入COMMIT-PRIMARY的阶段。不然只要有一个BACKUP没有（F-1的BACKUP 有），那么F失败了（唯独那个没有BACKUP的没失败），我们就expose一个COMMIT，可能永远的丢失了这个写。

TC只需要等待一个COMMIT-PRIMARY的ACK。因为可以确保有一个完整的F+1的REGION 确保了COMMIT。因为F个BACK UP肯定都ACK了，加上这个，就可以容忍F个机器的失败。