分布式系统的一致性算法------《Designing Data-Intensive Applications》读书笔记13

一致性算法是分布式系统中最重要的问题之一。表面上看，这似乎很简单，只是让几个节点在某些方面达成一致。在本篇之中，会带大家完整的梳理分布式系统之中的共识算法，来更加深刻的理解分布式系统的设计。

1.原子提交和两阶段提交（2PC）

原子提交防止了数据库处于半更新的状态，这对于需要满足多对象事务和维护次级索引的数据库尤为重要。每个次级索引都是从主数据中分离出来的数据结构，因此，如果修改某些数据，也需要在次级索引中做出相应的更改。通过原子性保证二级索引能够与原数据保持一致。

分布式系统下的原子提交

我们先来看看，在一个单一的节点上是如何实现原子提交的： 对于执行在一个单一数据库节点的事务，当客户端向数据库提交事务时，数据库首先将事务信息添加到磁盘上的日志进行提交。如果数据库在这个过程中间崩溃，则在节点重新启动时从日志中恢复事务。如果在崩溃前将提交记录成功写入磁盘，则认为事务被提交，如果没有，则该事务的任何写入都回滚。在单一的节点的数据库下，事务的原子提交取决于持久化写入磁盘的顺序，使得事务的提交原子化。

如果事务中涉及多个节点呢？情况就变得十分复杂了：

• 有些节点可能检测到约束违反或冲突，需要中止，而其他节点能够成功地提交。
• 一些提交请求可以在网络中丢失，最终中止由于超时，而其他提交请求获得通过。
• 某些节点可能在提交记录完全写入和回滚恢复之前崩溃，而另一些节点则成功提交。

所以，一个节点必须确定事务在所有其他节点也要提交时才能进行提交。我们必须要有一种算法能够让分布式节点达成共识。

两阶段提交（2PC）。

两阶段提交协议就是我们要谈到的第一个分布式共识协议。如下图所示

• 通过一个协调器，当应用程序准备提交时，协调器节点开始的第1阶段。它向每个参与的数据库节点发送一个准备请求，询问它们是否能够提交？然后协调器跟踪参与者的响应，如果所有参与者都能回答：是，表示他们准备提交，那么协调器在第2阶段发出一个提交请求，则所有参与者同时进行提交，如果任何参与者回答：否，则协调器向第2阶段的所有节点发送一个中止请求。

一个成功提交的两阶段协议

两阶段提交的问题

一旦出现了网络故障或参与者失效，协调器节点可以通过超时机制来中止事务。二如果在阶段二出现提交或中止事务失败，协调器节点可以无限重试直到故障恢复。但是，如果这个过程之中协调器节点崩溃了，将会产生许多头疼的问题：

如果协调器在发送准备请求之前失败，参与者可以安全地中止事务。但是，一旦参与者收到了一个准备请求并回答了：是，它就必须等待从协调器节点的指令，事务是被提交还是中止。而一旦协调器节点崩溃或出现网路故障，参与者只能无限期的等待。如下图所示：

Database1陷入无限等待之中，所有资源被锁住

由于协调器在将提交请求发送到Database 1之前崩溃了，因此Database 1不知道事务是否提交。如果数据库1单方面中止暂停之后，它的结果与Database 2产生不一致。 唯一的办法是等待协调器恢复，这就是为什么在向参与者提交或中止事务请求之前，协调器必须将其提交或中止的结果写入本地磁盘上的事务日志。当协调器恢复时，它通过读取其事务日志确定所有可疑事务的状态。任何在协调器日志中没有提交记录的事务都会被中止。

2.协商一致性

由上文我们可以了解，在分布式系统之中可以使用两阶段提交协议来实现的事务(也可以使用两阶段提交协议的升级版三阶段提交协议)。分布式事务虽然解决了分布式数据库之中的事务实现，但是它也引入了新的问题，事务协调器本身也是一种数据库（在其中存储事务的结果）。如果协调器只在一台机器上运行，很容易就会产生单点故障问题。而默认情况下，许多协调器实现不是高可用的，只有基本的副本备份功能。许多服务器端应用程序以无状态模型为基础，将持久性状态都存储在数据库中，其优点是可以随意添加和删除应用服务器。但是，当协调器成为应用程序服务器的一部分时，它会改变部署的性质。因为协调器的日志同样成为了需要持久化状态存储的内容。一方面，分布式事务很难实现完整的一致性保障。另一方面，由于协调器节点的存在，分布式事务会大大降低数据库的性能，所以很多数据系统放弃了对分布式事务的支持。

协商一致性

其实分布式事务困难点就在于实现一致性，它要求系统之中多个节点达成共识。例如，如果有几个人同时尝试预订飞机上的最后一个座位或同一个剧院的座位，或者试图用相同的用户名注册一个帐户，则可以使用一致性算法来最终确定哪种哪个操作是成功的，并且在分布式系统的节点之中达成一致的共识。

而协商一致性通常的形式如下：一个或多个节点可以提出取值，而协商一致性算法决定其中一个值。 协商一致性的核心理念：每个人都决定相同的结果，一旦你决定了，你就不能改变你的想法。我们可以先简化这个模型，摒弃容错性：可以指定一个节点成为Leader，由Leader节点做出所有的决定。但是，如果Leader节点失效，则系统陷入瘫痪。两阶段提交协议之中的协调器就是一个Leader，一旦协调器失效了，系统无法进行工作。而更好的协商一致性算法要求，即使某些节点失效了，系统仍然能够正常工作。当然，如果所有节点都崩溃了，并且没有一个节点正在运行，那么任何算法都不可能鸡血运行，所以说算法可以容忍的故障数量是有限的：事实上，可以证明任何协商一致算法至少需要大多数节点正常运行，来确保协商一致。

一致性算法与全序广播

在分布式系统之中存在许多协商一致性算法算法如：Paxos，Raft，Zab等等。本篇之中，不会涉及到不同算法的全部细节，会通过他们来了解一些高级思想。（后续大家有兴趣会给大家来详解这些算法）

这里的一致性算法符合全序广播的特性，全序广播需要以相同的顺序向所有节点精确地传递一次消息。在每一轮的协商之中，每个节点都可以提出下一个要发送的消息，然后由协商达成一致，并在系统之中传递的下一条消息。所有节点共同决定以相同的顺序传递相同的消息，且消息不重复，消息不会被破坏，也不会凭空产生。（这里忽略拜占庭问题，如果需要引入拜占庭容错，需要采用类似于区块链之中的Pow算法）

epoch编号和Leader选举

每一轮的消息都进行协商，是缺乏效率的行为。所以类似于Raft与Zab等协议都利用Leader机制来进行优化。所以协商一致协议需要选举出Leader，并且保证Leader是独一无二的。如何来保证分布式节点对Leader节点的选举结果的共识呢？这里利用分布式的时序机制，每一个通过合法选举出的Leader存在一个epoch编号，来确保Leader是独特的。 一旦Leader节点失效，则各个节点之间开始投票选出新的Leader，新的Leader会产生一个新的epoch值，所以epoch值是根据Leader选举顺序单调递增的。如果两个不同的Leader在发生冲突（也许是因为前一个领导人实际上并没有死），那么所有节点会认同更高的epoch值。

Leader需要做出的每一个决策，它都必须将提议的值发送给其他节点，并等待节点的集合来响应提议。此时协商一致需要达到法定人数，也就是组成集群的大多数节点。一个节点会投票赞成一个提案，只有当它不知道任何其他Leader具有更高的epoch值。协商一致性分为两个运行阶段：一:选择一个Leader，二：投票表决Leader的提议。当Leader收到法定人数的投票结果同意提案，则可以断定，没有一个具有更高epoch值的Leader，然后它可以安全地提交结果。(可以用反证法证明) 这个投票过程虽然看起来类似于两阶段提交。最大的差异是协调器节点的容错，来保证协商一致算法高度可用性。

3.协商一致性的代价

协商一致性算法是分布式系统的一个重大突破：它给所有其他不确定的系统带来了具体的解决方案，并且它仍然是容错的（只要大多数节点都能正常工作），并且提供全序广播的特性，因此他们也可以在容错的方式实现线性化的原子操作。

天下没有免费的午餐，这种好处是有代价的。

• 协商过程之中需要对提案进行表决，而这个表决的过程本质上是一种同步复制。前文我们已经探讨过同步复制与异步复制的优缺点。而在实践之中，我们通常配置使用异步复制。某些提交的数据可能在故障转移时丢失，但为了更好的性能，许多人选择接受这种风险。
• 协商一致性严格要求需要多数决。这意味着你需要至少三个节点来容忍一个故障（剩下的两个组成多数），或者至少五个节点来容忍两个故障（剩下的三个组成多数）。
• 大多数协商一致算法假设一组固定的节点参与投票，这意味着不能动态的添加或删除集群中的节点。
• 如何检测失效的节点也是一个问题。在具有高度可变网络延迟的环境中，经常发生一个节点错误地认为Leader的失效。虽然这个错误不会损害系统的安全性，但是频繁的Leader选举会导致系统糟糕的表现，因为系统最终会花费更多的时间去选择一个领导者而不是做任何有用的工作。

所以设计对不可靠网络更健壮的算法仍然是我们计算机工作者需要挑战和研究的问题。

小结：

从两阶段提交协议起步，我们梳理了分布式系统下的一致性算法，并且分析了它们的优劣。通过这些外包出去的分布式协调服务作为基础模型，我们才能实现更多，更加复杂的分布式服务。