MIT6.824：分布式事务

# Before-or-After Atomicity: Coordinating Concurrent Threads

before-or-after 原子性指的是一个并发操作发生在另一个并发操作的之前（before）或者之后（after）对于结果并没有影响。

Concurrent actions have the before-or-after property if their effect from the point of view of their invokers is the same as if the actions occurred either completely before or completely after one another.

同时也提到要实现这种 before-or-after actions 的并发正确性，需要在每个 action 使用共享变量时遵循 locking protocol，说白了就是加锁。

以一个转账为例：

A 账号初始有 300 元，B 账户初始为 100 元。现在有这样一个转账：

$Trans(A, B, 10)$

A 账号向 B 账号转账了 10 元，同时此时有一个 C 账号，其初始金额为 290 元，并且 B 账号向 C 账号转账 25 元：

$Trans(B,C,25)$

这两个操作可以并发执行，那么就会出现错误：

# Correctness and Serialization

首先必须明确：

There is such a correctness concept: coordination among concurrent actions can be considered to be correct if every result is guaranteed to be one that could have been obtained by some purely serial application of those same actions.

只要 actions 的结果能够被一些串行的应用所执行得到，那么这些并发操作就是正确的。

我这句话其实没怎么表述清除。。。

如果一个 action 仅仅由单个线程所执行，并且再执行之前是正确的，那么执行之后也一定是正确的。

当有多个 actions 同时并发，如果这些 actions 是 before-or-after 并且执行之前是 correct，那么新状态也是 correct。

这里就引出了可串行性：

serializable: there exists some serial order of those concurrent transactions that would, if followed, lead to the same ending state.

这里的可串行性一般指的是冲突可串行性也就是 CSR。冲突操作可以被定义为：

两个数据操作 $o_j$ 和 $ o_i$ 是一对 冲突操作（conflicting operations)，如果它们满足： 它们属于不同的 transaction；以及 其中至少一个操作是写操作。

只要我们满足冲突操作的排序顺序和某个串行事务 schedule 一致，那么就是满足了冲突可串行性。

# 听课

这里老师讲了 serializable ，算是明白了到底是啥。如果一系列事务（这里就是线性）执行可以得到相同结果（这里的结果指的是外部观测得到的结果）

就像上面的图中所示，T1 和 T2 两个事务执行结果只有两种情况，所以其他观察到的结果就是非可串行性。

# 消极锁

# simple Lock

简单锁就是在使用 record 之前进行加锁，知道事务结束后才会释放锁，这样有一个好处就是保证了 serializable，但是缺点也很明显，因为不能并发这就意味着其性能很差。

# Two-Phase Locking

2PL 很简单，它就是把加锁和解锁分为了两个阶段，一个阶段只能加锁，一个阶段只能释放锁。在 2PL 协议下，每个 transaction 都会经过两个阶段：在第一个阶段里，transaction 根据需要不断地获取锁，叫做 growing phase (expanding phase)；在第二个阶段里，transaction 开始释放其持有的锁，根据 2PL 的规则，这个 transaction 不能再获得新的锁，所以它所持有的锁逐渐减少，叫做 shrinking phase (contracting phase)。

2PL 可以满足 CRS 冲突一致性，这位博主给出了 2PC 一定可以满足 CRS 的证明：

Transaction management：两阶段锁（two-phase locking） - 王子旭的文章 - 知乎 https://zhuanlan.zhihu.com/p/59535337

2PL 虽然允许一定程度的并发，但是 2PL 会导致死锁。

# 分布式事务

# 2PC

这个 2PC 看起来简单，但还是有各种各样的情况需要考虑。

2PC 协议：

1. coordinate 发送命令（也就是图中的 get、put），participate 收到命令后就去申请锁。
2. 接着，coordinate 发送 prepare 指令，如果 participate 没有 fail，数据没有丢失，record 一致性完好，申请到了锁等等，participate 检查自身状态认为自己可以完成命令就返回 yes，否则返回 No。注意在 participate 返回之前，它必须先写 LOG 到磁盘 persist。participate 回复 prepare yes 之后就开始执行操作。
3. 如果有一个返回 NO，coordinate 就会认为事务失败并且让 client retry。如果 coordinate 收到了所有的 prepare yes，那么它就会把这个事务写入 LOG。之后及时 coordinate crash，它恢复之后也必须执行这个事务。
4. 接着 coordinate 发送 commit 指令，所有 participate 收到后，就释放锁，并且在 LOG 将操作修改为 commit 状态，这样即使 participate crash 了，那么它也知道自己 commit 了。participate 返回 ACK。
5. coordinate 收到所有 ACK 之后就返回 client 事务成功。

2PC 会导致死锁，在 prepare 阶段后如果 coordinate fail 或者 crash 之后，participate 并不会超时释放锁，它只会一直持有锁，这就导致 time-block。

2PC 性能很差，一方面由于它需要很多网络，另一方面由于 participate 返回 prepare 之前必须写 LOG，同时 coordinate 发 commit 之前也必须写 LOG。

# 留下的问题

如何将 raft 和 2PC 结合起来，使得其既可以满足事务又可以有 availability？