一致性保证

最终一致性是一个非常弱的保证。当系统提供了弱保证的数据库时，要认清系统的局限性。（最终一致性数据库不同副本的状态可能不同）
需要更强的一致性保证来满足一些业务的需求。

可线性化

基本思想：让系统看起来好像只有一个副本，并且所有的操作都是原子的

非线性化，看世界杯直播的例子

用户可以发现不一致是因为有系统外部的信息通道。

如何达到线性化？

问题，三个用户同时读写变量x

从用户的角度来讲，标红的request在没有线性一致保证时候可能返回任何值。

实现线性一致，要添加一个约束

由于B的读取严格在发生于A的读取之后，因此即使C的写入仍在进行中，也必须返回 1。

增加CAS操作

可串行化 VS 可线性化

可串行化

是事务隔离属性。
确保了事务执行的结果与串行执行结果一样。

可线性化

是读写寄存器的最新值保证。
跟事务没有关系。

需要线性化的场景

加锁与主节点选举

主从复制数据库，只能有一个主节点，否则会产生脑裂。

常见方法是使用锁。先获得锁的人成为主节点。

不管这个锁是如何实现的，它必须是线性一致的：所有节点必须就哪个节点拥有锁达成一致，否则就没用了。

诸如Apache ZooKeeper 和etcd之类的协调服务通常用于实现分布式锁和领导者选举。它们使用一致性算法，以容错的方式实现线性一致的操作（在本章后面的“容错共识”中讨论此类算法）。还有许多微妙的细节来正确地实现锁和领导者选择（例如，参阅“领导者和锁”中的屏蔽问题）。
线性一致性存储服务是这些协调任务的基础。

约束与唯一性保证

注册用户名/邮箱唯一。

这种情况实际上类似于一个锁：当一个用户注册你的服务时，可以认为他们获得了所选用户名的“锁定”。

跨通道的时间依赖

看球赛中的例子。由于系统中存在额外的信道（Alice的声音传到了Bob的耳朵中），线性一致性的违背才被注意到。

如果你可以控制额外信道（例如消息队列的例子，而不是在Alice和Bob的例子），则可以使用在“读己之写”讨论过的备选方法，不过会有额外的复杂度代价。

实现线性化系统

系统容错做常见的解决方案是复制。

单主系统可能实现线性化。从主节点读或者同步更新从节点。
共识算法。通过协商一致性协议算法可以防止脑裂和读取过期数据，通过一致性算法可以实现核心数据线性化的安全存储。这是ZooKeeper与Chubby等分布式协调服务的基础算法。

法定人数读Quorum

在某些情况，即使w + r > n，也会不是线性的。

线性化的代价

许多分布式数据库也是如此：它们是为了提高性能而选择了牺牲线性一致性，而不是为了容错。线性一致的速度很慢——这始终是事实，而不仅仅是网络故障期间。

CAP理论

CAP理论，简而言之便是：数据系统必须在一致性、可用性、分区容忍性的三角关系之中有所权衡，任何系统没有办法同时满足三种特性。

所以使用线性化的一致性自然会需要在可用性上做一些妥协，在单Leader多Follower机制之下，需要满足线性化一致性的写入和读取的客户端必须连接到Leader。如果Leader产生中断，仍然可以读取Follower的数据，但此时就无法保证线性化的要求了。

顺序

顺序与因果关系

顺序有助于保证因果关系。

因果顺序不是全序。

可线性化强于因果一致性。

线性一致性

在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。

因果性

我们说过，如果两个操作都没有在彼此之前发生，那么这两个操作是并发的（参阅“Happens-Before”的关系和并发）。换句话说，如果两个事件是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

那么因果顺序和线性一致性之间的关系是什么？答案是线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性。

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。

序列号排序

我们可以使用序列号（sequence nunber）或时间戳（timestamp）来排序事件。时间戳不一定来自时钟（或物理时钟，存在许多问题，如 “不可靠时钟” 中所述）。它可以来自一个逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

这些序列号生成器不能正确地捕获跨节点的操作顺序。

Lamport时间戳

每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。兰伯特时间戳就是两者的简单组合：（计数器，节点ID）$(counter, node ID)$。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点ID，每个时间戳都是唯一的。

兰伯特时间戳与物理时间时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则计数器值大者是更大的时间戳。如果计数器值相同，则节点ID越大的，时间戳越大。

光有时间戳排序还不够

只有在所有的操作都被收集之后，操作的全序才会出现。如果另一个节点已经产生了一些操作，但你还不知道那些操作是什么，那就无法构造所有操作最终的全序关系：来自另一个节点的未知操作可能需要被插入到全序中的不同位置。

总之：为了实诸如如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定。如果你有一个创建用户名的操作，并且确定在全序中，没有任何其他节点可以在你的操作之前插入对同一用户名的声称，那么你就可以安全地宣告操作执行成功。

全序广播

单主复制通过选择一个节点作为主库来确定操作的全序，并在主库的单个CPU核上对所有操作进行排序。

接下来的挑战是，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效（“处理节点宕机”），如何处理故障切换。

全序广播要满足两个安全属性：

可靠交付（reliable delivery）

没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。

全序交付（totally ordered delivery）*

消息以相同的顺序传递给每个节点。

正确的全序广播算法必须始终保证可靠性和有序性，即使节点或网络出现故障。（Retry等）

通过全序广播实现线性化一致性

全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息何时被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

你可以通过将全序广播当成仅追加日志的方式来实现这种线性一致的CAS操作：

在日志中追加一条消息，试探性地指明你要声明的用户名。
读日志，并等待你所附加的信息被回送。
检查是否有任何消息声称目标用户名的所有权。如果这些消息中的第一条就你自己的消息，那么你就成功了：你可以提交声称的用户名（也许是通过向日志追加另一条消息）并向客户端确认。如果所需用户名的第一条消息来自其他用户，则中止操作。

所有节点同意一个写请求到底是提交成功还是中止。可以保证线性化写入。

上述步骤在读取时不能保证线性。因为消息传递的延迟性，所以读操作的结果可能是过时的。

当然这里可以通过返回最新日志消息的位置，通过查询位置，等待所有条目需要读取的条目被写入，再进行读操作，便能够达到读操作的线性一致性。（在ZooKeeper中通过sync()操作实现），或者可以通过强制读取Leader节点，显然Leader节点上的数据一定是最新的结果。

分布式事务与共识

需要集群节点一致性的场景举例：

主节点选举
原子事务提交

原子提交与两阶段提交

提交事务的结果有可能通过事后执行另一个补偿事务来取消，即补偿事务。但从数据库的角度来看，这是一个单独的事务，因此任何关于跨事务正确性的保证都是应用层负责。

两阶段提交

两阶段提交（two-phase commit）是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。它是分布式数据库中的经典算法。 2PC在某些数据库内部使用，也以XA事务的形式对应用可用（例如Java Transaction API支持）或以SOAP Web服务的WS-AtomicTransaction 形式提供给应用。

新增组建协调者。协调者通常在请求事务的相同应用进程中以库的形式实现（例如，嵌入在Java EE容器中），但也可以是单独的进程或服务。

参与者不能单方面放弃，必须等待协调者决定

协调者崩溃，那么参与者不知道接下来如何行动。

可以完成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）。

数据库服务器不能直接联系协调者，因为所有通信都必须通过客户端库。

停顿时间仍持有锁

如果协调者已经崩溃，需要20分钟才能重启，那么这些锁将会被持有20分钟。如果协调者的日志由于某种原因彻底丢失，这些锁将被永久持有 —— 或至少在管理员手动解决该情况之前。

从协调者故障中恢复

许多XA的实现都有一个叫做启发式决策（heuristic decistions）的紧急逃生舱口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。要清楚的是，这里启发式是可能破坏原子性（probably breaking atomicity）的委婉说法，因为它违背了两阶段提交的系统承诺。因此，启发式决策只是为了逃出灾难性的情况而准备的，而不是为了日常使用的。

分布式事务的限制

运维问题：

如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点（因为它的失效会导致其他应用服务器阻塞在存疑事务持有的锁上）。令人惊讶的是，许多协调者实现默认情况下并不是高可用的，或者只有基本的复制支持。
许多服务器端应用都是使用无状态模式开发的（受HTTP的青睐），所有持久状态都存储在数据库中，因此具有应用服务器可随意按需添加删除的优点。但是，当协调者成为应用服务器的一部分时，它会改变部署的性质。突然间，协调者的日志成为持久系统状态的关键部分—— 与数据库本身一样重要，因为协调者日志是为了在崩溃后恢复存疑事务所必需的。这样的应用服务器不再是无状态的了。
由于XA需要兼容各种数据系统，因此它必须是所有系统的最低标准。例如，它不能检测不同系统间的死锁（因为这将需要一个标准协议来让系统交换每个事务正在等待的锁的信息），而且它无法与SSI 协同工作，因为这需要一个跨系统定位冲突的协议。
对于数据库内部的分布式事务（不是XA），限制没有这么大，例如，分布式版本的SSI 是可能的。然而仍然存在问题：2PC成功提交一个事务需要所有参与者的响应。因此，如果系统的任何部分损坏，事务也会失败。因此，分布式事务又有扩大失效（amplifying failures）的趋势，这又与我们构建容错系统的目标背道而驰。

支持容错共识

共识算法必须满足：

一致同意（Uniform agreement）

没有两个节点的决定不同。

完整性（Integrity）

没有节点决定两次。

有效性（Validity）

如果一个节点决定了值 v ，则 v 由某个节点所提议。

终止（Termination）由所有未崩溃的节点来最终决定值。

一致同意和完整性属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。

有效性属性主要是为了排除无意义的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为null的算法。

摒弃容错性：可以指定一个节点成为Leader，由Leader节点做出所有的决定。但是，如果Leader节点失效，则系统陷入瘫痪。两阶段提交协议之中的协调器就是一个Leader，一旦协调器失效了，系统无法进行工作。而更好的协商一致性算法要求，即使某些节点失效了，系统仍然能够正常工作。当然，如果所有节点都崩溃了，并且没有一个节点正在运行，那么任何算法都不可能鸡血运行，所以说算法可以容忍的故障数量是有限的：事实上，可以证明任何协商一致算法至少需要大多数节点正常运行，来确保协商一致。

共识算法

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

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

主从复制与共识

要选出一个领导者，我们首先需要一个领导者。要解决共识问题，我们首先需要解决共识问题。我们如何跳出这个先有鸡还是先有蛋的问题？

epoch number与法定人数（Quorum）

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个时代编号（epoch number）（在Paxos中称为投票编号（ballot number），视图戳复制中的视图编号（view number），以及Raft中的任期号码（term number）），并确保在每个世代中，领导者都是唯一的。

在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高时代编号的领导者，它们可能会做出相互冲突的决定。

因此，我们有两轮投票：
第一次是为了选出一位领导者，
第二次是对领导者的提议进行表决。

关键的洞察在于，这两次投票的法定人群必须相互重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举。

共识的局限性

性能
复杂

节点在做出决定之前对提议进行投票的过程是一种同步复制。
共识系统总是需要严格多数来运转。
共识系统通常依靠超时来检测失效的节点。
有时共识算法对网络问题特别敏感。

成员与协调服务

如何使用ZooKeeper这样的服务？

作为应用开发人员，你很少需要直接使用ZooKeeper，因为它实际上不适合当成通用数据库来用。更有可能的是，你会通过其他项目间接依赖它，例如HBase，Hadoop YARN，OpenStack Nova和Kafka都依赖ZooKeeper在后台运行。这些项目从它那里得到了什么？

ZooKeeper与etcd的特点：

不用保存大量数据
数据库复制中，每条消息代表的是数据库写请求

ZooKeeper模仿了Google的Chubby锁服务，不仅实现了全序广播（因此也实现了共识），而且还构建了一组有趣的其他特性，这些特性在构建分布式系统时变得特别有用：

线性一致性的原子操作
使用原子CAS操作可以实现锁
操作的全序排序
一个单调递增的事务ID（zxid）和版本号（cversion）
失效检测
心跳链接
变更通知
通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

场景1:
节点任务分配。主节点选举。分区资源（数据库，消息，文件，actor）分配。
场景2:
服务发现。查找需要服务的IP地址。
场景3:
成员服务。查看成员是否Live。