写这篇文章的原因是之前在测试 6.824 Lab2B 时总是会出现几个错误，去提了 issue 后也没有得到令人信服的结果，自己有一点头绪但是没验证，这事就这么放着了。 然后最近有个同样做 6.824 的同学给我发了邮件，说他也遇到了同样的问题，重新分析了一下后，本来想简单回复一下的，结果回复的内容越写越多，就干脆直接整理为一篇文章，供大家参考。 异常情况 我之前在对 Lab2B 进行测试时，总是有几个简单的测试点过不了，仿佛代码即使正确，也总是可能出错。我经过分析后发现，都遵循以下这种错误模式： Leader 接收了来自上层的请求，还未提交该日志或者只有他提交了日志（该日志已经被 major 收到）时，就因为收到了其他 peer 的 RequestVote RPC 重新变回了 Follower。 重新选举后再次成为 Leader 后，由于旧任期的 Log 不能被新任期的 Leader 提交，所以之前的日志无法提交。 没有新的请求进来，导致该日志一致无法提交，然后 2 秒后超时，测试无法通过。 错误提示都是 one(xxx) failed to reach agreement。 为什么会出现 在 Lab2B 最开始的几个测试中，测试的编写者为了简化测试，测试代码中提交 command 的操作均为 cfg.one(cmd, servers, false)，这个函数的第三个参数名为 retry，控制的是对于一个请求，是否需要在超时后重新提交。 这里 retry 被设置为了 false，也就是说整个执行过程中只会调用 rf.Start() 一次，如果遇见了上文说的异常情况，就会被卡住，最后出现超时报错的情况。 也就是说，所谓的异常情况就是恰好遇见了一个 timing 加上 Lab2B 前面的几个测试有“缺陷”造成的。 no-op 机制 Raft 协议中本身是没有这个问题的，在论文第 13 页中说明了一个节点在当选 Leader 后会发送一个 no-op 的日志，这样新 Leader 就能把 no-op 以及它之前未提交的日志一起提交，就不会卡住了。 ...

ACID 中的一致性 我们现在关注的是其中的 C，即一致性 Consistency。它是什么意思呢？通俗地说，它指的是任何一个数据库事务的执行，都应该让整个数据库保持在「一致」的状态： ACID 中的「一致性」，是对于整个数据库的「一致」状态的维持。抽象来看，对数据库每进行一次事务操作，它的状态就发生一次变化。这相当于把数据库看成了状态机，只要数据库的起始状态是「一致」的，并且每次事务操作都能保持「一致性」，那么数据库就能始终保持在「一致」的状态上 (Consistency Preservation)。 所谓状态是不是「一致」，其实是由业务层规定的。比如转账的例子，“转账前后账户总额保持不变”，这个规定只对于「转账」这个特定的业务场景有效。如果换一个业务场景，「一致」的概念就不是这样规定了。所以说，ACID 中的「一致性」，其实是体现了业务逻辑上的合理性，并不是由数据库本身的技术特性所决定的。 为了让事务总是能保持 ACID 的一致性，我们需要在实现上考虑哪些因素呢？ 出错情况 (failure/error) 事务本身的实现逻辑可能存在错误，这需要应用层进行恰当的编码来保证。 需要 ACID 中的 A（原子性）来保障。简言之，原子性保障了事务的执行要么全部成功，要么全部失败，而不允许出现“只执行了一半”这种“部分成功”的情况。 并发行为 需要 ACID 中的 I（隔离性）来保障了。什么是隔离性呢？它对于并发执行的多个事务进行合理的排序，保障了不同事务的执行互不干扰。换言之，隔离性这种特性，能够让并发执行的多个事务就好像是按照「先后顺序」执行的一样。 Summary ACID 中的一致性，是个很偏应用层的概念。这跟 ACID 中的原子性、隔离性和持久性有很大的不同。原子性、隔离性和持久性，都是数据库本身所提供的技术特性；而一致性，则是由特定的业务场景规定的。 要真正做到 ACID 中的一致性，它是要依赖数据库的原子性和隔离性的（应对错误和并发）。 最后，ACID 中的一致性，甚至跟分布式都没什么直接关系。它跟分布式的唯一关联在于，在分布式环境下，它所依赖的数据库原子性和隔离性更难实现。 总之，ACID中的一致性，是一个非常特殊的概念。除了数据库事务处理，它很难扩展到其它场景，也跟分布式理论中的其它「一致性」概念没有什么关系。 分布式事务与共识算法的关系 共识问题 (consensus problem)。这是分布式系统中的一个十分基础而核心的问题，它表示如何在分布式系统中的多个节点之间就某事达成共识。 网上通常提到的「分布式一致性协议」，或者「分布式一致性算法」，一般来说就是解决这里的共识问题的算法。 这些算法或协议，经常包含 Paxos 之类，但也可能包括两阶段提交协议 (2 PC)或三阶段提交协议 (3 PC)。 ACID 中的原子性，要求事务的执行要么全部成功，要么全部失败，而不允许出现“部分成功”的情况。在分布式事务中，这要求参与事务的所有节点，要么全部执行 Commit 操作，要么全部执行 Abort 操作。换句话说，参与事务的所有节点，需要在“执行 Commit 还是 Abort”这一点上达成一致（其实就是共识）。这个问题在学术界被称为原子提交问题（Atomic Commitment Problem），而能够解决原子提交问题的算法，则被称为原子提交协议（Atomic Commitment Protocal，简称ACP）。2PC 和3PC，属于原子提交协议两种不同的具体实现。 我们可以发现原子提交问题和共识问题的关联： 共识问题，解决的是如何在分布式系统中的多个节点之间就某个提议达成共识。 原子提交问题，解决的是参与分布式事务的所有节点在“执行 Commit 还是 Abort”这一点上达成共识。 所以，原子提交问题是共识问题的一个特例。（？） 一些细节的不同，可能导致非常大的差异。当我们描述共识问题的时候，我们说的是在多个节点之间达成共识；而当我们描述原子提交问题的时候，我们说的是在所有节点之间达成共识。这个细微的差别，让这两类问题，几乎变成了完全不同的问题（谁也替代不了谁）： ...

What is CAP Consistency: 数据一致性 Availability: 可用性 Partition Tolerance: 分区容忍性 Consistency 指的是系统能够返回一致性的数据。 Gilbert 和 Lynch 的论文中是这样描述一致性的： Any read operation that begins after a write operation completes must return that value, or the result of a later write operation. 在某个写操作完成之后的任何读操作都必须返回该写操作写入的值，或者再之后的写操作写入的值。 在一个一致性的系统中，如果一个客户端写入了某个值到任意一个服务端上，并且得到了服务端的确认，那么客户端再去读的时候，不管是读的哪个服务，都期望拿到写入后的值或者是更新的值。 Available 指的是系统能保持在可用的状态。 Gilbert 和 Lynch 的论文对可用性的描述如下： Every request received by a non-failing node in the system must result in a response. 任何一个在线的节点收到的请求必须都做出相应。 在保证可用性的系统中，如果客户端向某个没有宕机的服务端发送了请求，服务端必须响应客户端的请求，不能选择忽略掉客户端的请求。 它要求系统内的节点们接收到了无论是写请求还是读请求，都要能处理并给回响应结果。只是它有两点必须满足的条件： 返回结果必须在合理的时间以内，这个合理的时间是根据业务来定的。 需要系统内能正常接收请求的所有节点都返回结果。 如果节点不能正常接收请求了，比如宕机了，系统崩溃了，而其他节点依然能正常接收请求，那么，我们说系统依然是可用的，也就是说，部分宕机没事儿，不影响可用性指标。 如果节点能正常接收请求，但是发现节点内部数据有问题，那么也必须返回结果，哪怕返回的结果是有问题的。 Partition Tolerance 指的是系统能够容忍分区问题。 ...

FAQ Is chain replication used in practice over other things like Raft or Paxos? Systems often use both. A common way of building distributed systems is to use a configuration server (called the master in the paper) for maintaining configuration info (e.g., who is primary) and a replication system for replicating data. Paxos/Raft are commonly-used to build the configuration server while the replication system often uses primary-backup or chain replication. ...

Happened Before 关系 论文先从事件之间的 Happened Before 关系开始讲起 结合上图我们举例解释一下「Happened Before」关系： 同一进程内部先后发生的两个事件之间，具有「Happened Before」关系。比如，在进程 Q 内部，q_2 表示一个消息接收事件，q_4表示另一个消息的发送事件，q_2 排在 q_4 前面执行，所以 q_2 → q_4。 同一个消息的发送事件和接收事件，具有「Happened Before」关系。比如，p_1 和 q_2分别表示同一个消息的发送事件和接收事件，所以 p_1→ q_2；同理， q_4→ r_3。 「Happened Before」满足传递关系。比如，由 p_1→ q_2， q_2→_q_4和 q_4→ r_3，可以推出 p_1 → r_3。 作者然后说明了并发的概念： Two distinct events a and b are said to be concurrent if a !→ b and b !→ a. 同时作者也描述了与因果性的关系： Another way of viewing the definition is to say that a→b means that it is possible for event a to causally affect event b. Two events are concurrent if neither can causally affect the other. ...