MIT6824笔记十 分布式事务
本节介绍了分布式事务，如何进行并发控制和原子提交，主要是2PL和2PC。
2PL区别于简单锁，事务锁数量是动态增长的，并在事务commit或abort之后才能释放锁。2PC其实有3阶段，包括inform、prepare、commit阶段。每一阶段为了防止数据丢失都要进行Write Ahead Log操作。每个服务器也要维护各自的锁表单，用来记录当前锁被哪个事务持有。
分布式事务背景
对于拥有大量数据的人来说，他们通常会将数据进行分割或者分片到许多不同的服务器上，人们需要跨机器的原子操作(cross-machine atomic ops)。
分布式事务主要有两部分组成。
- 第一个是并发控制（Concurrency Control）
- 第二个是原子提交（Atomic Commit）
可以这么理解事务：程序员有一些不同的操作，或许针对数据库不同的记录，他们希望所有这些操作作为一个整体，不会因为失败而被分割，也不会被其他活动看到中间状态。
事务原语
这里举例应用事务时的程序编写，假设有T1和T2两个正在进行的事务，我们只需要通过指定的事务原语编程程序，就能保证逻辑被原子地执行，而无需感知事务内部实现使用什么锁等机制。
- begin：声明一个事务的开始
- commit：提交事务，commit成功被执行后，begin～commit之间的逻辑被原子地执行
- abort：取消事务，begin～abort之间的逻辑将被撤销，即产生的影响会消除(比如put修改的值被改回去之类的)。除了人为在逻辑里使用abort，事务本身遇到死锁等情况时也会自动调用abort。
并发下的正确性——可序列化
在多个并发事务的存在下，我们需要一个概念来定义什么是正确的结果。一旦我们知道了这个概念，我们需要构建能执行这些事务的机制，在可能存在并发和失败的前提下，仍然得到正确的结果。
首先，什么是正确性？
数据库通常对于正确性有一个概念称为ACID。分别代表：
Atomic，原子性。它意味着，事务可能有多个步骤，比如说写多个数据记录，尽管可能存在故障，但是要么所有的写数据都完成了，要么没有写数据能完成。不应该发生类似这种情况：在一个特定的时间发生了故障，导致事务中一半的写数据完成并可见，另一半的写数据没有完成，这里要么全有，要么全没有（All or Nothing）。
Consistent，一致性。我们实际上不会担心这一条，它通常是指数据库会强制某些应用程序定义的数据不变，这不是我们今天要考虑的点。
Isolated，隔离性。这一点还比较重要。这是一个属性，它表明两个同时运行的事务，在事务结束前，能不能看到彼此的更新，能不能看到另一个事务中间的临时的更新。目标是不能。隔离在技术上的具体体现是，事务需要串行执行，我之后会再解释这一条。但是总结起来，事务不能看到彼此之间的中间状态，只能看到完成的事务结果。
Durable，持久化的。这意味着，在事务提交之后，在客户端或者程序提交事务之后，并从数据库得到了回复说，yes，我们执行了你的事务，那么这时，在数据库中的修改是持久化的，它们不会因为一些错误而被擦除。在实际中，这意味着数据需要被写入到一些非易失的存储（Non-Volatile Storage），持久化的存储，例如磁盘。
我们说可序列化是指，并行的执行一些事物得到的结果，与按照某种串行的顺序来执行这些事务，可以得到相同的结果。实际的执行过程或许会有大量的并行处理，但是这里要求得到的结果与按照某种顺序一次一个事务的串行执行结果是一样的。这里的结果包括两个方面：由任何事务中的修改行为产生的数据库记录的修改和任何事务生成的输出。
可序列化是一个应用广泛且实用的定义，背后的原因是，它定义了事务执行过程的正确性。可序列化特性确保你可以安全的写你的事务，就像没有其他事情发生一样。因为系统最终的结果必须表现的就像，你的事务在这种一次一个的顺序中是独占运行的。这是一个非常简单，非常好的编程模型。
可序列化的另一方面优势是，只要事务不使用相同的数据，它可以允许真正的并行执行事务。
并发控制
第一种主要策略是悲观并发控制（Pessimistic Concurrency Control）。那就是在事务使用任何数据之前，它需要获得数据的锁。如果一些其他的事务已经在使用这里的数据，锁会被它们持有，当前事务必须等待这些事务结束，之后当前事务才能获取到锁。在悲观系统中，如果有锁冲突，比如其他事务持有了锁，就会造成延时等待。所以这里需要为正确性而牺牲性能。
第二种主要策略是乐观并发控制（Optimistic Concurrency Control）。这里的基本思想是，你不用担心其他的事务是否正在读写你要使用的数据，你直接继续执行你的读写操作，通常来说这些执行会在一些临时区域，只有在事务最后的时候，你再检查是不是有一些其他的事务干扰了你。如果没有这样的其他事务，那么你的事务就完成了，并且你也不需要承受锁带来的性能损耗，因为操作锁的代价一般都比较高；但是如果有一些其他的事务在同一时间修改了你关心的数据，并造成了冲突，那么你必须要Abort当前事务，并重试。
如果冲突非常频繁，你或许会想要使用悲观并发控制，因为如果冲突非常频繁的话，在乐观并发控制中你会有大量的Abort操作。如果冲突非常少，那么乐观并发控制可以更快，因为它完全避免了锁带来的性能损耗。
两阶段锁2PL
所谓两阶段，第一个阶段是扩张，获得锁的数量不断增加，期间不能释放锁；第二阶段是收缩，锁的数量单调下降，不能获得锁。
第一个规则：acquing lock before using record
第二个规则：hold lock until done（commit） or abort
对于两阶段锁来说，第一个规则是在执行任何数据的读写之前，先获取锁。第二个规则是，事务必须持有任何已经获得的锁，直到事务提交或者Abort。换言之，持有锁直到事务结束。
为什么需要在事务结束前一直持有锁？假设事务在读写完记录后就释放了锁，另一个事务有机会运行，可能会得到非法的结果。
如图所示，T1，T2两个事务。只有两种一次一个的串行顺序，要么是T1，T2，要么是T2，T1。同样对应两种结果11，9和10，10。
假设T2读取了X，然后立刻释放了锁，那么在这个位置，T2不持有任何锁，因为它刚刚释放了对于X的锁。因为T2不持有任何锁，这意味着T1可以完全在这个位置执行。从前面的反例我们已经知道，这样的执行是错误的（因为T2会打印“10，9”），因为它没能生成正确结果。
对比
2PL是对简单锁(严格锁)的改进。
- 简单锁(simple locking)或严格锁(strict locking)，在事务开始前，你获取整个事务所需的所有锁，持有这些锁直到提交点进行commit或者abort，然后释放所有锁。
- 2PL的锁更细粒度一点，不需要在事务开始前直接获取所有锁，相反的，在事务运行时动态增量的获取锁，支持某些严格锁(简单锁)不允许的并发模式。
一般而言，使用2PL要比使用简单锁(严格锁)有更高的并发度。比如事务中读取的某个变量极小概率会是true，而变量为true时，才会执行后序事务逻辑，那么这里不需要在事务开始前就加锁，可以等读到变量时再加锁。
2PL死锁场景
两阶段锁非常容易造成死锁，比如以下这种情况：
1 | T1: T2: |
每个事务都获取了第一个读取数据的锁，直到事务结束了，它们都不会释放这个锁。接下来，它们都会等待另一个事务持有的锁。
不过好在事务系统提供了abort操作。如果事务系统可以检测到死锁(deadlock)，那么可以对T1或T2事务任意一个执行abort操作，使其中一个事务能正常获取lock完成事务，并中止另一个事务。而客户端client或应用程序可以自己决定如何处理事务被abort的情况，比如事务重试或放弃执行等等，但至少避免了死锁。
可以看出来2PL也会进入死锁的场景，但至少提供了abort操作，能够解决死锁问题，而不是永远停在死锁场景中。
问题：事务系统如何检测到死锁？
回答：人们用两种方法来检测，尽管不够可靠。一种是基于超时(timeout)的，比如几个事务执行了许久看似没有新进展，则中止其中一个。另一种更系统的方法是构造一个**等待图(wait-for graph)**，如果发现等待图中出现环，则说明有死锁（比如上面T1等待T2的Lock Y，T2等待T1的Lock X，T1和T2成环）。
问题：检测到死锁后，中止其中一个事务会发生什么？
回答：假设中止了T2，事务系统会安排T2没有result或者其result是可见的，此时abort强制释放T2占有的Lock Y，T1之后可获得Lock Y完成事务，而发起T2的客户端会知道T2被系统中止，一般情况下你可以选择重新发起T2。
原子性提交
在分布式场景下，我们希望涉及事务的所有机器要么全都完成提交，要么全都表现得事务没有发生一样。
两阶段提交2PC
通常情况下，我们需要执行的任务会以某种方式分包在多个服务器上，每个服务器需要完成任务的不同部分。我们需要一个计算机用来管理事务，它被称为事务协调者（Transaction Coordinator）。
通常协调者以试探的方式协调分布式事务。
以下为简单的示例，以及对应的崩溃处理：
下面所有的操作，都需要预写日志，即(WAL, write-ahead log)，先写日志，在做实际操作，确保崩溃恢复时能重现log完成已commit的操作，以及舍弃或恢复未commit的操作。
| 时序 | coordinator(协调器) | A服务器拥有X记录 | B服务器拥有Y记录 |
|---|---|---|---|
| 1 | 新建事务(tid)，告知A执行put(X), 告知B执行put(Y) | ||
| 2 | Lock X, put(X), log X(日志记录)。这里暂时没有实际操作数据库，只是log记录 | log Y(日志记录), Lock Y, log Y(日志记录)，这里暂时没有实际操作数据库，只是log记录 | |
| 3 | 对A、B发起prepare询问请求，询问A和B是否正常log了事物需要的操作 | ||
| 4 | A查看自己的状态，发现持有X的锁，并且log了需要执行的put操作，回应prepare请求YES | B查看自己的状态，发现持有Y的锁，并且log了需要执行的put操作，回应prepare请求YES | |
| 5 | 收到A和B的prepare响应YES后，得知A和B可以准备提交事务了，向A和B发起commit(tid)请求 | ||
| 6 | A看本地log，发现tid对应的事务可以提交了，于是install日志，即执行日志中记录的put(X)操作，然后释放X的锁，对commit请求响应OK | B看本地log，发现tid对应的事务可以提交了，于是install日志，即执行日志中记录的put(Y)操作，然后释放Y的锁，对commit请求响应OK | |
| 7 | 收到A和B的OK，知道A和B都成功执行完事务了 |
- 假设时序4准备执行事务时，A或者B由于死锁或者log空间不足等原因无法执行事务操作，那么A或者B会对prepare请求回应NO，拒绝执行事务。
- 此时协调者在时序5的位置发现有人不同意执行事务，于是改成向A和B发送abort请求，要求停止执行事务。
- 在时序6的位置，A和B接收到abort请求后，会根据log里的记录，对tid事务操作进行回滚。回滚完毕后，A和B回应OK
- 在时序7的位置，协调者收到A和B的OK后，得知A和B都回滚tid事务成功了。
下图展示了2PC的过程（忽略了最初的RPC）。
在一个完整的系统中，或许会有很多不同的并发运行事务。每个持有数据的服务器会维护一个锁的表单，用来记录锁被哪个事务所持有。
缺点
1.性能问题
无论是在第一阶段的过程中,还是在第二阶段,所有的参与者资源和协调者资源都是被锁住的,只有当所有节点准备完毕，事务 协调者 才会通知进行全局提交，参与者 进行本地事务提交后才会释放资源。这样的过程会比较漫长，对性能影响比较大。
2.单节点故障
由于协调者的重要性，一旦 协调者 发生故障。参与者 会一直阻塞下去。尤其在第二阶段，协调者 发生故障，那么所有的 参与者 还都处于锁定事务资源的状态中，而无法继续完成事务操作。（虽然协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
崩溃恢复分析
两阶段提交会发送3N条消息，故障可能出现在这3次交互中的任意一次。
- 场景1:事务参与者在回应prepare后崩溃
首先，B已经对prepare回应OK了，所以这里B恢复后不能反悔，必须继续执行事务。这里B恢复后，仍持有数据Y的锁，并且检查log中记录的状态（比如需要把一些状态值加载到内存之类的），然后后续就和没发生崩溃一样走原本的流程了。
- 场景2：协调者在发送commit(tid)请求后崩溃
假设协调者在时序5的位置，向A和B发送commit请求后崩溃，需要怎么确保整个流程顺利执行？
类似事务参与者，协调者在发送commit(pid)请求之前，需要记录log，崩溃后根据log继续执行事务流程。这里假设协调者崩溃前，A回应了OK，但是B回应协调者之前，协调者崩溃了。那么B必须等待协调者恢复后，再回应协调者OK，而不能私自中止事务。
这种情况下，B很不幸必须一直等待，这里其他事务如果要占用Y数据的锁就会失败，因为B需要等待协调者恢复后，能响应协调者时再释放锁。
- 场景3：A一直没有回应协调者prepare请求
假设A因为某些原因，在时序4的位置一直没有回应prepare，那么协调者会以超时等机制，在时序5的位置告知B执行abort来中止事务。后序A又和协调者联系上时，协调者会告诉A，tid这个事务已经中止了。这意味着B收到abort后可以释放Y数据的锁，然后后续尝试其他涉及Y数据的事务之类的。
MIT6824笔记十 分布式事务