cs-6.824第12讲 分布式事务
cs-6.824第12讲 分布式事务
分布式事务之所以出现，是因为很多业务拥有大量的数据，这些数据最终会被分割或分片到不同的服务器上。
例如，你正在运行一家银行，那么可能一半客户的银行余额存储在一台服务器上，而另一半客户的银行余额则存储在另一台服务器上。这样做就可以分散负载，分散负载包含包括分散处理和分散存储两个点。再例如，如果你正在网站上记录文章的投票数，或者存在数以百万计的文章，其中一半的票数统计在一个服务器上，而另一半则分布在另一个服务器上。
但是有一些操作需要接触、修改或读取分布在不同服务器上的数据。以上面的银行的例子，如果执行一个客户到另一个客户的银行转账，那么他们的余额可能存储在不同的服务器上，因此为了实现平衡，我们必须对两个不同的服务器上的数据进行修改、读取和写入操作。
我们希望做到的是试图隐藏数据分散到多个服务器上，尽量不让应用程序开发者感知到。这就是分布式事务所产生的背景，所谓事务其实就是并发控制和原子提交。程序员拥有一系列不同的操作，可能针对数据库中的不同的记录进行，希望这些操作可以作为一个整体，不受故障或者其他活动影响而分割。 事务处理系统将要求程序员标记读写及更新操作序列的起始和结束，以便明确事务的起始和结束。
再次看银行的例子：
我们希望从用户x的账户向用户y的账户进行转账，现在他们双方的余额初始状态都是10。现在有两个事务：
- T1：一笔交易时从账户X向账户y转账一美元
- T2：对该银行进行审计，以确保银行资金总量不变。
x = 10 y = 10
T1：
BEGIN_X
add(x, 1)
add(y, -1)
END_X
T2:AUDIT
BEGIN_X
t1 = get(x)
t2 = get(y)
print t1, t2
END_X
现在问题是，这两个事务的合法结果是什么?
再讨论这个之前，我们需要了解，什么样的结果是正确的。
数据库事务通常具有一个称为ACID的正确性概念，缩写为ACID。
- 原子性(A， atomic)，这意味着一个包含多个步骤的交易，可能涉及对多个不同记录的写入，若发生故障，无论何种故障，要么所有写入都完成，要么都不执行。(All or None on failure)
- 一致性(C， consistent)，数据库会执行应用程序所声明的不变量(不在本课讨论范围内)
- 隔离性(I，isolated)，两个同时运行的交易在完成之前是否能看到彼此变更的特性，期望值是不能看到。在技术层面，大多数人所指的隔离性，是指事务执行的可串行化（后续还会讲）。
- 持久性(D，durable)，在事务提交之后，事务的修改是持久的，它不会因为某些故障而被抹除。在实践中，这意味着数据必须被写入某种易失性戒指，如磁盘这样的持久存储设备。
这里面比较有意思的是隔离性（串行化）。如果存在某种顺序，使得事务串行执行的结果和实际并行执行的结果相同，则代表可以串行化。
这里回到上面的银行转账的例子， 由于只有两个事务T1和T2，所以只有两种顺序，先执行T1，再执行T2。或者先执行T2，再执行T1。因此我们分别看两种顺序所产生的结果,如下所示：
T1->T2:
x=11 y=9 "11,9"
T2->T1:
x=11 y=9 "10,10"
只要事务不使用相同的数据，就允许真正的并行。在上面的例子中，我们使用了相同的数据x和y，因此不能并行。如果你有一个分片的系统，那么并行度可能会更高，因为数据分布在不同的机器上。一个事务完全在第一台机器的第一个分片上执行，而另一个事务则同时在第二个机器上并行。
事务可能由于某种原因，在执行过程中基本失败或决定失败，我们必须应对那些在执行中突然决定无法继续进行的事务的必要性。
并发控制
并发控制是用来提供隔离性和串行化的主要方法。
并发控制主要有以下两种：
- 悲观并发控制
- 乐观并发控制
悲观并发控制，通常依赖于锁机制。其含义是事务在使用任何数据之前，它需要获取该数据的锁。若其他事务已占该数据，锁将被保持，我们需等待以获取锁的释放，等待占有锁的事务完成。
乐观并发控制，核心思想是，你无需顾虑其他事务是否可能与你同时进行数据的读写操作，你只需直接执行你计划中的读写操作，只有在最后才去检查是否可能有其他事务可能产生干扰。如果此时，其他人在以冲突的方式修改同一数据，那么您就必须中止该事务并重试。(第14讲会涉及这个话题)。
如果冲突非常频繁，可能使用悲观并发控制更好。因为如果冲突非常频繁，乐观方案将会因为冲突而导致大量事务中止。
如果冲突不太常见，那么乐观控制可能更快，因为它完全避免了锁的开销。
今天主要讨论的是悲观并发控制。今天我们将探讨两阶段锁定(two-phase locking)，这是最常见的锁定类型。
两阶段锁定的思想是，
- 一个事务将会使用一堆记录，例如例子中的x和y，在使用任何数据片段之前(无论是读还是写)，都必须先获取锁。
- 一个事务必须在提交或终止之后才能释放其所获取的任何锁。在事务执行的过程中，不允许中途释放锁。
为了理解锁定在此处的作用，典型的锁定系统存在许多变种。通常，这些系统为数据库中的每条记录、每行和每张表分别关联一个独立的锁。回到上面的例子，当T1使用x时，必须在使用前获取x上的锁，并且可能等待。同理，对于y，也需要获取y上的锁，事务完成后才能释放这两个锁。
如果同时运行这两个事务，它们将竞争获取对x的锁定，无论哪个事务获取对x的锁定，它将得以继续执行并完成。于此同时，另一个未能获取到x锁的事务将在此等待，直到能够获取，它才可以对x进行操作。这里可以看到由于事务需要获取对x的锁定，实际上就实现了串行化。
接下来讨论一个问题，为什么你需要保持锁定直到事务全部完成才可以释放？
这里主要有两个原因：
- 第一个原因可能会违背线性化的要求 假设T2在箭头处，释放了x的lock，那么T1就可以继续执行，这种交错是违背线性化的。
T2:AUDIT
BEGIN_X
t1 = get(x)
--->release x lock
t2 = get(y)
print t1, t2
END_X
同样，如果T1在完成对x加1操作后，释放了对x的锁定，这允许T2的所有操作在此处插入。这也会违背线性化。
T1：
BEGIN_X
add(x, 1)
---> release x lock
add(y, -1)
END_X
- 第一个原因就是提前释放锁对于事务提前终止会产生问题。
如果在add(x， 1)之后释放了锁，然后随后由于y的余额不足，而导致y扣款失败，那么事务将会终止，将会对撤销对于x的更新，以保持原子性。 这个时候，由于T2可能会提前执行，T2可能会看到一个"幽灵"的11，这个值11后续因为T1的终止而消失。
这里还需讨论关于锁定锁产生的死锁问题。
假设我们有两个事务，其中一个读取x，然后读取y，另一个事务读取y，再读取x，如果它们同时运行，就会死锁。
T1： T2:
Get(x) Get(y)
Get(y) Get(x)
事务通常会采取追踪循环或设置超时，以便检测到它们已陷入某种状态。当发现异常时，将终止其中一个事务。
到目前为止，我们所提到的概念都是标准数据库的行为，在单机数据库中如此，在分布式系统中也是如此。接下来将聚焦于分布式环境中支持事务处理。
我们有两台服务器，一台服务器存储我们的银行记录x。我们还有服务器2，可能它存储了记录y。因此它们都具有初始值10。还是以转账为例，将x加1，y进行减1。
S1 S2
|--------| |--------|
| x | 10 | | y | 10 |
| | | | | |
|--------| |--------|
如果我们不够谨慎，可能会遇到一种情况，服务器1为x增加余额，但随后发生了故障，导致我们未能完成对y的更新。
另一种情况下，服务器1为x增加余额，s2并未发生故障，但是可能y的值提示余额不足，无法扣款，但是x余额已经进行增加。
数据库事务的原子性要求交易要么完全完整，要么都不执行。上面两个场景显然违背了。在下一节中将讨论原子提交的问题，
原子提交
两阶段提交是一个原子提交协议，这个原理被很多分布式数据库采用，也被各种其他非传统数据库的分布式系统所应用。
我们假设有一个驱动事务的计算机，称为事务协调器。它可以向拥有不同数据片段的计算机发送消息。
S1
|--------|
| x | 10 |
| | |
|--------|
TC
S2
|--------|
| y | 10 |
| | |
|--------|
事务协调器实际上会维护一个关于事务ID的表。
为了遵守两阶段的锁定规则，每个参与者在执行事务的一部分时，都会锁定其读取的任何数据。可以想象在每个参与者的内部，都存在一张与该参与者存储的数据先关联的表。参与者们会在这些表格中锁定信息。
如果所有人都遵循此协议且无任何故障发生，那么两位参与者只在双方均承诺的情况下才会提交。若其中任何一方无法提交，则双方均会终止。因此我们得到了期望的结果，要么它们都执行，要么都不执行。
接下来我们考虑各种异常的场景，看看两阶段提交如何解决这些场景下的问题。
B可能在发送prepare确认消息之前就crash了
这里Morris的解释不够详细，这里结合自己的理解和Morris的讲解进行总结。
这种情况下，协调者还没有收到这个参与者的 prepare 响应（即"已准备"或"拒绝"），因此协调者无法得知该参与者的状态。我们从协调者和参与者两个角度来看这个问题：
协调者：
- 协调者会设置一个超时时间，等待所有参与者的 prepare 响应。如果在超时之前，某个参与者没有回复，协调者将默认认为该参与者无法参与事务并执行 回滚。
- 协调者会通知所有其他已经参与事务的服务器进行 rollback 操作，从而保证整个事务的回滚。
参与者：
当参与者恢复时，由于它崩溃前没有发送任何 prepare 回复，且事务没有提交，因此该参与者不应当提交事务。恢复后的处理方式可以是：
- 查看日志：参与者在崩溃恢复后会查看本地事务日志。如果日志中没有任何与该事务相关的记录，说明参与者在崩溃前未进行任何事务操作。因此，参与者应该安全地丢弃该事务，认为自己未参与其中。
- 与协调者重新协商：参与者也可以在恢复后联系协调者，询问该事务的最终决策（即提交或回滚）。由于参与者之前并未准备好，协调者会告知其进行 rollback。
B可能在发送prepare确认消息之后crash会怎么样？
这种场景将会麻烦一些。
参与者在回复 prepare 之后崩溃了，意味着该参与者已经告知协调者它已准备好提交事务（即已写入本地的 prepare 日志），但它可能还没有收到协调者的最终决策（commit 或 rollback）。仍然从协调者和参与者两个角度来看这个问题：
协调者：
在协调者完成了 prepare 阶段（即收到所有参与者的准备响应后），它会根据所有参与者的状态做出以下决策：
- 所有参与者都准备好： 协调者会发送 commit 请求给所有参与者。
- 有任何参与者拒绝： 协调者会发送 rollback 请求给所有参与者。
参与者:
检查本地日志：如果本地日志显示已经写入了 "准备好" 状态（prepared），参与者会发现它已经进入了 prepared 状态，但是由于它崩溃前可能没有收到最终的 commit 或 rollback 请求，因此参与者需要与协调者重新进行沟通。
与协调者同步状态：恢复后的参与者会向协调者询问该事务的最终决定。由于协调者在 prepare 阶段后仍持有该事务的最终状态（commit 或 rollback），它会告知崩溃恢复后的参与者如何操作：
- 如果事务已经提交，协调者会告知参与者进行 commit。
- 如果事务已经回滚，协调者会告知参与者进行 rollback。
这里需要强调的是，参与者在收到prepare请求之后会将一些必要的信息写入持久化存储中，这也是导致两阶段提交速度慢的原因之一。
B在接受到commit的消息之后崩溃，或者是处理完commit消息之后崩溃会怎么样？
这里其实有两种场景，morris主要解释了处理完commit消息之后崩溃的处理方式。
如果参与者在收到 commit 消息后崩溃：
在分布式事务的设计中，参与者在执行任何提交操作之前，通常会将 commit 请求记录到本地持久化的事务日志中。这是为了确保即使崩溃，恢复后仍然可以知道事务的最终状态。因此，推测其处理过程如下：
- 参与者在恢复时会检查它的事务日志。
- 如果它发现日志中已经记录了收到 commit 请求（即该事务处于“准备提交”或更高的状态），但没有标记事务为已提交完成，则意味着事务提交尚未执行。
- 根据日志中的 commit 记录，参与者会自动重新执行事务提交操作，以确保数据一致性。
如果处理完 commit 消息后崩溃：
在分布式系统中，事务的最终提交操作也是通过日志持久化的。在处理完 commit 操作后，参与者会将提交操作成功的状态记录到日志中。
恢复后的处理：
- 如果参与者在崩溃恢复后，检查日志发现已经成功记录了提交操作，说明该事务已经提交完成，无需再重复提交。
- 由于事务已经提交，系统不会重新尝试提交或回滚，事务状态是“已提交”，并且是不可逆的。
- 参与者在恢复后可以安全地忽略该事务，并继续处理其他任务。
如果收到两次commit消息会怎么样？
参与者的提交操作通常被设计为幂等的。这意味着无论执行多少次，最终结果都是相同的。因此，即使参与者收到两次 commit 消息，第二次提交不会改变任何状态，事务只会被提交一次。
参与者在处理 commit 消息时，通常会检查自己的事务状态。如果参与者已经记录该事务为已提交，第二次收到 commit 消息时，它会忽略该请求或确认已经提交，无需再次执行提交操作。
参与者会在提交操作后将状态写入日志。因此，即使重复接收 commit 消息，参与者会基于日志确认该事务已成功提交。
如果事务协调器在发送了一个或多个commit消息之后崩溃
恢复后的协调器会检查其日志，确定哪些事务已经发出了 commit 消息，哪些仍处于 prepared 状态。如果它发现某个事务的参与者已被告知提交但某些参与者未回复，则需要进行协调以确保一致性。
这里Morris强调在协调者发送commit请求之前，也需要将一些必要信息进行持久化存储，通常来讲是以日志的形式。同理，这也会导致速度降低。
事务协调器发送了prepare消息，但是尚未从所有参与者收到yes或no的消息
事务协调器在等待 prepare 响应时如果未收到所有消息，可以超时并决定 rollback，或者在崩溃后根据日志信息处理事务，确保最终一致性。当然也可以在超时之后，选择再次发送prepare消息，但是总体上也需要设置一个最大尝试次数。
假设参与者B已经收到prepare请求，并发送了同意响应，但是一直没有收到commit请求
这个时候B仍然持有记录的锁，作为B，他非常希望释放锁，因为可能还有很多事务还在等待获取该锁，问题是B等待了10分钟或者更久之后，他是否可以单方面中止该事务。
答案是否定的。B需要阻塞的等待事务协调器的commit消息，可以理解为无限期等待。其原因是，由于B返回了prepare ok的消息，事务协调器可能已经收到了该回复，它可能已经开始发送commit消息了，这意味着A可能已经收到了提交事务，进行了提交。因此B无权单方面决定超时中止。
这种阻塞其实是两阶段提交的一个关键特征，这是一个非常令人不愉快的特点。这意味着，如果出现问题，你可能会陷入一种情况，即你必须长时间持有锁，并阻碍其他事务的进行。后续的很多研究都是围绕这个阻塞时间开展的。
只有事务协调器可以决定中止事务或者提交事务，任何一个参与者都没有权力单方面决定是否提交事务或者终止事务。
事务协调器何时可以忘记其日志中关于事务的记录？
如果系统成功接受所有来自参与者的完整确认信息，那么它就可以清除所有相关信息，即该事务的所有记录。同样的，当参与者接受到commit消息之后处理完所有的事情后，发送完成事务的消息之后，也可以清除关于该事务的信息。
总结
两阶段提交被广泛用于许多数据分片的数据库中。存在许多更为专业的存储系统，它们不允许对多个记录进行事务管理，那么这种情况则无需两阶段提交。
两阶段提交的劣势：
两阶段提交由于多轮消息提交而显得缓慢，而且还有大量的写盘操作。
两阶段提交并不保证高可用，需要结合raft和paxos才可以实现高可用。后面提到的Spanner实际就运用了这种方法。