目录
- 理解最终一致性和线性一致性（2个线性一致性解决的问题）
- 2种线性一致性的实现 （CAP对线性一致性的解释）
- 线性一致性和因果一致性的关系（LAMPORT 时间戳 和 全序广播）
- 二阶段提交 和 分布式事务
- 容错共识的思想和代价
分布式系统最重要的抽象之一就是共识（consensus）：就是让所有的节点对某件事达成一致。正如我们在本章中将会看到的那样，尽管存在网络故障和流程故障，可靠地达成共识是一个令人惊讶的棘手问题。
一旦达成共识，应用可以将其用于各种目的。例如，假设你有一个单主复制的数据库。如果主库挂点，并且需要故障切换到另一个节点，剩余的数据库节点可以使用共识来选举新的领导者。
在讲共识之前，我们先来介绍下一致性。
最终一致性
大多数分布式数据库至少提供了最终一致性，这意味着如果停止对数据库的写操作并等待一段时间，最终所有读请求将返回相同的值。但是，这是一个非常弱的一致性保证，所谓的一段时间并不确定。如果写入一个值，然后立即读取它，就不能保证读取到刚才写入的值。
最终一致性的模型对于应用程序开发人员来说是个大烦恼，当使用只提供弱一致性的数据库时，开发人员需要意识到它的问题，数据库可能会有很微妙的错误，因为应用程序可能大部分时间都工作得很好。而当系统中有故障（例如网络中断）或高并发性时，最终一致性的数据模型将会暴露很多问题。所以数据系统可以选择提供的更强的一致性模型,但是又会引入新的Trade-off:有更强一致性的系统虽然更容易正确使用，但是它可能比弱一致性的系统的性能更差或容错性更低，我们需要更好的理解它并且选择最适合需求的数据模型。
线性一致性
线性一致性的思想很简单，我们用下面两幅图来说明：
在一个线性系统之中，一定会有某个时间点（开始和结束的写操作之间），x的值从0变成了1。因此，如果一个客户端的读取x时返回了新值1，所有后续的读取也必须返回新的值。
线性化与串行化
线性化与串行化不同，它不构成事务。因此不能完全保证并发写的安全性。数据库可以同时提供串行化和线性化，如两阶段锁便是可以同时提供串行化与线性化，而序列化的快照隔离不是线性化的。
线性一致性可以解决什么问题？
分布式锁和Leader选举
单Leader的系统需要确保只有一个Leader，多个Leader会导致脑裂的发生。而Leader选举的本质是锁的争用，每个节点试图获取锁，获取成功的节点成为Leader。而无论如何，这把锁必须是线性化：所有节点都必须同意哪个节点拥有锁，成为Leader唯一性约束
唯一性约束在数据库中很常见：例如，用户名或电子邮件地址必须唯一地标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。如果你想为数据写入执行这一约束（例如，如果两人试图同时创建一个用户或一个具有相同名称的文件，其中将返回一个错误），你需要线性化。
实现线性一致的系统
线性化意味着：如同一个单拷贝的数据，并对其所有的操作都是原子的。最简单的答案就是真的只使用一个单一的数据复制。这种方式显然就失去了容错性，单一节点出现异常则系统将无法访问。而使系统容错的最常用方法是使用副本技术：
单Leader多Follower机制
在单Leader多Follower机制之中，Leader拥有主副本，Follower在其他节点上维护数据的备份副本。可以选择从Leader上读，或同步更新的Follower，可以在这个基础之上实现线性化系统。
一致性算法
通过协商一致性协议算法可以防止脑裂和读取过期数据，通过一致性算法可以实现核心数据线性化的安全存储。这是ZooKeeper与Chubby等分布式协调服务的基础算法。
CAP理论与一致性的代价
Eric Brewer在2000年提出CAP理论，简而言之便是：数据系统必须在一致性、可用性、分区容忍性的三角关系之中有所权衡，任何系统没有办法同时满足三种特性。
所以使用线性化的一致性自然会需要在可用性上做一些妥协， 在单Leader多Follower机制之下，需要满足线性化一致性的写入和读取的客户端必须连接到Leader。如果Leader产生中断，仍然可以读取Follower的数据，但此时就无法保证线性化的要求了。
许多分布式数据库也是如此：它们是为了提高性能而选择了牺牲线性一致性，而不是为了容错。线性一致的速度很慢——这始终是事实，而不仅仅是网络故障期间。
能找到一个更高效的线性一致存储实现吗？看起来答案是否定的：Attiya和Welch 证明，如果你想要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比。
顺序与因果
线性一致性
在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。这个全序图9-4中以时间线表示。
因果性
我们说过，如果两个操作都没有在彼此之前发生，那么这两个操作是并发的。换句话说，如果两个事件是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。
因此，根据这个定义，在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。可能有几个请求在等待处理，但是数据存储确保了每个请求都是在唯一时间线上的某个时间点自动处理的，不存在任何并发。
并发意味着时间线会分岔然后合并 —— 在这种情况下，不同分支上的操作是无法比较的（即并发操作）。如果你熟悉像Git这样的分布式版本控制系统，那么其版本历史与因果关系图极其相似。通常，一个提交（Commit）发生在另一个提交之后，在一条直线上。但是有时你会遇到分支（当多个人同时在一个项目上工作时），合并（Merge）会在这些并发创建的提交相融合时创建。
那么因果顺序和线性一致性之间的关系是什么？答案是线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性。
在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一致性，且性能与可用性与最终一致的系统类似。
Lamport时间戳
Lamport时间戳是生成因果关系的序列号的一种方法，我们可以通过它理清分布式系统之中操作的顺序，Leslie Lamport 在1978年提出。Lamport时间戳的实现很简单，每个节点有一个唯一计数器标识符，并且每个节点都保存它的计数器。两个节点有时可能具有相同的计数器值，但在计数器值之中都包含节点id，所以每个计数器值都可以认为是唯一的时间戳。
Lamport时间戳没有确切的物理时间，但它可以分布式系统之中的事件排序：存在两个时间戳，一个更大计数器的时间戳是更新的值；如果计数器的值是相同的，一个更大的节点ID是更大的时间戳。下图展示了Lamport时间戳的工作原理，它能够符合分布式系统之中的因果关系：
但是从Lamport时间戳的总顺序来看，无法判断两个操作是并发的，还是它们是因果相关的。虽然Lamport时间戳能够确认操作的因果关系，但是在分布式系统之中仍然存在一些问题：
请考虑一个系统，该系统需要确保用户名唯一标识用户帐户。如果两个用户同时尝试创建具有相同用户名的帐户，则其中一个应该成功，另一个应该失败。显然，如果两个相同的用户名的账户创建，选择具有较低的时间戳的操作成功，因为Lamport时间戳是完全有序的，这种比较是有效的。但是为了确保没有其他节点在同时在较早的时间创建帐户，所以节点不得不与其他每个节点通信进行确认。如果出现网络问题，其他节点中的一个已经失效或无法到达，则系统也将失效。
Lamport时间戳的问题在于：需要收集所有操作之后，操作的总顺序才会出现。如果另一个节点有其他操作，在不知道的情况下，无法构造操作的最终顺序。
全序广播
全序广播的机制是使用：通过单Leader多Follower机制，在Leader节点上对所有操作进行排序，从而决定了整个操作顺序，并将操作顺序进行广播。全序广播可以保证全局知晓信息，而解决Lamport时间戳面临的问题。但是全序广播同样要解决这样几个问题：如果吞吐量大于单Leader的处理量，那么如何扩展系统，以及出现Leader失效的情况，如何进行故障转移。
全序广播要求满足如下两个属性总是被满足：
可靠的交付,没有消息丢失：如果消息被传递到一个节点，它将被传递给所有节点。
完全有序传递，消息以相同的顺序传递给每个节点。
一个正确的全序广播算法必须保证节点和网络故障时的可靠性和有序性。一旦出现网路分化的现象，算法可以保持重试，仍然保持信息的有序性。全序广播对于分布式系统来说有十分重要的意义：如果每个消息表示对数据库的写入，并且每个副本以相同的顺序处理相同的写入，则副本将保持彼此一致，而各个节点的状态机也能够保持一致，可以通过这样的方式来实现状态机复制（RSM,replicated state machine）。
通过全序广播实现线性化一致性
全序广播是异步的：消息保证以固定的顺序可靠地传递，但不能保证何时传递消息（因此存在节点可能落后于其他节点）。而线性化一致性能够保证：每次读操作能够读到最新值的写入。我们可以依托于全序广播，在存储上实现线性化一致性：
1.将消息append到日志中，添加要声明的用户名。
2.节点通过内存之中的状态机检查，如果该用户名的第一条消息，则用户名写入成功。否则，终止该操作。
由于全序广播保证了，消息是以相同的顺序传递给所有节点，假设存在并发写入，所有节点都会达成共识，第一个写入用户名的消息。虽然全序广播可以保证程序的线性写入，但是假设进行读操作的节点却不能保证线性读取，因为消息传递的延迟性，所以读操作的结果可能是过时的。
当然这里可以通过返回最新日志消息的位置，通过查询位置，等待所有条目需要读取的条目被写入，再进行读操作，便能够达到读操作的线性一致性。（在ZooKeeper中通过sync()操作实现），或者可以通过强制读取Leader节点的副，显然Leader节点上的数据一定是最新的结果。
共识
2PC,二阶段提交
实践中的分布式事务
XA事务
X/Open XA（扩展架构（eXtended Architecture）的缩写）是跨异构技术实现两阶段提交的标准。它于1991年推出并得到了广泛的实现：许多传统关系数据库（包括PostgreSQL，MySQL，DB2，SQL Server和Oracle）和消息代理（包括ActiveMQ，HornetQ，MSMQ和IBM MQ） 都支持XA。
XA不是一个网络协议——它只是一个用来与事务协调者连接的C API。其他语言也有这种API的绑定；例如在Java EE应用的世界中，XA事务是使用Java事务API（JTA, Java Transaction API）实现的，而许多使用Java数据库连接（JDBC, Java Database Connectivity）的数据库驱动，以及许多使用Java消息服务（JMS）API的消息代理都支持Java事务API（JTA）。
事务协调者需要实现XA API。标准没有指明应该如何实现，但实际上协调者通常只是一个库，被加载到发起事务的应用的同一个进程中（而不是单独的服务）。它在事务中个跟踪所有的参与者，并在要求它们准备之后收集参与者的响应（通过驱动回调），并使用本地磁盘上的日志记录每次事务的决定（提交/中止）。
如果应用进程崩溃，或者运行应用的机器报销了，协调者也随之往生极乐。然后任何带有准备了但未提交事务的参与者都会在疑虑中卡死。由于协调程序的日志位于应用服务器的本地磁盘上，因此必须重启该服务器，且协调程序库必须读取日志以恢复每个事务的提交/中止结果。只有这样，协调者才能使用数据库驱动的XA回调来要求参与者提交或中止。数据库服务器不能直接联系协调者，因为所有通信都必须通过客户端库。
分布式事务的限制
XA事务解决了保持多个参与者（数据系统）相互一致的现实的重要问题，但正如我们所看到的那样，它也引入了严重的运维问题。
- 如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点（因为它的失效会导致其他应用服务器阻塞在存疑事务持有的锁上）。
- 许多服务器端应用都是使用无状态模式开发的。但是协调者的日志成为持久系统状态的关键部分，因为协调者日志是为了在崩溃后恢复存疑事务所必需的。这样的应用服务器不再是无状态的了。
- 由于XA需要兼容各种数据系统，因此它必须是所有系统的最小公分母。例如，它不能检测不同系统间的死锁。
- 对于数据库内部的分布式事务（不是XA），限制没有这么大，例如，分布式版本的SSI 是可能的。然而仍然存在问题：2PC成功提交一个事务需要所有参与者的响应。因此，如果系统的任何部分损坏，事务也会失败。因此，分布式事务又有扩大失效（amplifying failures）的趋势，这又与我们构建容错系统的目标背道而驰。
容错共识
其实分布式事务困难点就在于实现一致性，它要求系统之中多个节点达成共识。例如，如果有几个人同时尝试预订飞机上的最后一个座位或同一个剧院的座位，或者试图用相同的用户名注册一个帐户，则可以使用一致性算法来最终确定哪种哪个操作是成功的，并且在分布式系统的节点之中达成一致的共识。
而协商一致性通常的形式如下：一个或多个节点可以提出取值，而协商一致性算法决定其中一个值。 协商一致性的核心理念：每个人都决定相同的结果，一旦你决定了，你就不能改变你的想法。我们可以先简化这个模型，摒弃容错性：可以指定一个节点成为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，然后它可以安全地提交结果。(可以用反证法证明) 这个投票过程虽然看起来类似于两阶段提交。最大的差异是协调器节点的容错，来保证协商一致算法高度可用性。
容错共识的代价
协商过程之中需要对提案进行表决，而这个表决的过程本质上是一种同步复制。前文我们已经探讨过同步复制与异步复制的优缺点。而在实践之中，我们通常配置使用异步复制。某些提交的数据可能在故障转移时丢失，但为了更好的性能，许多人选择接受这种风险。
协商一致性严格要求需要多数决。这意味着你需要至少三个节点来容忍一个故障（剩下的两个组成多数），或者至少五个节点来容忍两个故障（剩下的三个组成多数）。
大多数协商一致算法假设一组固定的节点参与投票，这意味着不能动态的添加或删除集群中的节点。
如何检测失效的节点也是一个问题。在具有高度可变网络延迟的环境中，经常发生一个节点错误地认为Leader的失效。虽然这个错误不会损害系统的安全性，但是频繁的Leader选举会导致系统糟糕的表现，因为系统最终会花费更多的时间去选择一个领导者而不是做任何有用的工作。
