一致性与共识
分布式系统存在太对可能出错的场景，如果不能接受服务终止，就需要更加容错的解决方案，这样即使某些内部组件发生了故障，整个系统依然可以对外提供服务。为了构建容错系统，最好先建立一套通用的抽象机制和与之对应的技术保证，这样只需实现一次 ，其上的各种应用程序都可以安全地信赖底层的保证。本章我们将讨论构建容错式分布式系统的相关算注和协议。
一致性保证
大多数多副本的数据库者I）至少提供了最终的一致性，这意味着如果停止更新数据库，并等待一段时间（长度未知）之后，最终所有读请求会返回相同的内容。但是，这是一个非常弱的保证，它无能告诉我们系统何时会收敛。
当面对只提供了弱保证的数据库时，应用可能在大多数情况下都运行良好，只有当系统出现故障（例如网络中断）或高井发压力时，最终一致性的临界条件或者错误才会对外暴露出来，因而测试与发现错误变得非常困难。
分布式－致性模型与我们之前讨论过的多种事务隔离级别有相似之处。事务隔离主要是为了处理并发执行事务时的各种临界条件，而分布式一致性则主要是针对延迟和故障等问题来协调副本之间的状态。
可线性化
可线性化基本的想怯是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。
在一个可线性化的系统中， 一旦某个客户端成功提交写请求 ，所有客户端的读请求一定都能看到刚刚写入的值。这种看似单一副本的假象意味着它可以保证读取最近最新值，而不是过期的缓存。
如何达到线性化
为使系统可线性化 ，我们需要添加一个重要的约束：一旦某个读操悻返回了新值 ， 之后所有的读（包括相同或不同的客户端）都必须返回新值。
通过记录所有请求和响应的时序，然后检查它们是否可以顺序排列，可以用来测试系统是否可线性化。
可串行化是事务的隔离属性，它确保事务执行的结果与串行执行的结果完全相同，可线性化是读写寄存器的最新值保证。数据库可以同时支持可串行化与线性化，这种组合又被称为严格的可串行化或者强的单副本可串行化。
线性化的依赖条件
在有些场景下，线性化对于保证系统正确工作至关重要。
加锁与主节点选举
选举新的主节点常见的方法是使用锁：即每个启动的节点都试图获得锁，其中只有一个可以成功即成为主节点。不管锁具体如何实现，它必须满足可线性化：所有节点都必须同意哪个节点持有锁，否则就会出现问题 。
约束与唯一性保证
硬性的唯一性约束，常见如关系型数据库中主键的约束，需要线性化保证。
其他如外键或属性约束，则并不要求一定线性化
跨通道的时间依赖
可能一个信息会有不同的传输通道，而不同的通道之间会有竞争关系，会根据到达时间决定竞争结果，并导致竞争失败的一方的数据丢失。
实现线性化系统
实现线性化最简单的方案就是单个副本，复制机制也有些可以满足可线性化：
- 主从复制（部分支持可线性化）：如果从主节点或者同步更新的从节点上读取，则可以满足线性化。而从主节点上读取的前提是你确定知道哪个节点是主节点。
- 共识算法（可线性化）：共识协议通常内置一些措施来防止裂脑和过期的副本。正是由于这些专门的设计，共识算法可以安全地实现线性化存储。
- 多主复制（不可线性化）：具有多主节点复制的系统通常无怯线性化的，主要由于它们同时在多个节点上执行并发写入，并将数据异步复制到其他节点 。
- 无主复制（可能不可线性化）：不规范的quorum会破坏线性化，甚至即使是严格的 quorum ，正如之后即将介绍的，也会发生违背线性化的情况 。
线性化与quorum
由于写的延迟，可能导致多个用户访问数据时，有的用户先访问得到了新值，而后访问的用户却得到了旧值，因此尽管使用了严悟的quorum ，仍然不满足线性化。
线性化的代价
由于写请求和线性化读取都必须发送给主节点，如果网络中断，则无法保证线性化，连接从节点的客户端可以提供读服务，但内容可能是过期的（非线性化保证），如果应用程序要求线性化读写，则网络中断一定会违背这样的要求。否则只能等到网络恢复才能继续正常工作。
CAP理论
如果要求线性化，网络中断会导致服务不可用，如果不要求线性化，则服务不能保证线性化。
因此，不要求线性化的应用更能容忍网络故障。这种思路通常被称为CAP定理。
分布式数据库仍热衷于在集中共享的存储集群上提供可线性化的语义。而CAP则事实上在鼓励大家去探索无共享系统，后者更适合于大规模的Web服务，拥有更广阔的发展前景。
CAP是指一致性，可用性，分区容错性，而分区容错是无法逃避的，因此只能是在网络故障时，选择一致性（线性化）还是可用性。
CAP只考虑了一种一致性模型（线性化）和一种故障（网络分区故障）而没有考虑网络延迟、节点失败或其他需要折中的情况。因此可能并没有太大的实际价值。
可线性化与网络延迟
虽然线性化很有用，但是很少有系统真正满足线性化，放弃线性化的原因是因为性能，而不是为了容错。无论是否发生了网络故障，线性化对性能的影响都是巨大的。
顺序保证
排序、可线性化与共识之间存在着某种深刻的联系。
顺序与因果关系
顺序有助于保持因果关系。
因果关系对所发生的事件施加了某种排序，果关系的依赖链条定义了系统中的因果顺序，即某件事应该发生另一件事情之前。如果系统服从因果关系所规定的顺序，我们称之为因果一致性。
因果顺序并非全序
全序关系支持任何两个元素之间进行比较，即对于任意两个元素，总是可以指出哪个更大，哪个更小。而有些情况下无法直接比较，例如数学集合只能是偏序。
在可线性化数据存储中不存在并发操作，一定有一个时间线将所有操作都全序执行。
井发意味着时间线会出现分支和合井，而不同分支上的操作无怯直接比较。
如果两个事件是因果关系（一个发生在另一个之前），那么这两个事件可以被排序；而井发的事件则无法排序比较。这表明因果关系至少可以定义为偏序，而非全序。
可线性化强于因果一致性
可线性化一定意味着因果关系，可线性化确保了因果关系会自动全部保留，而不需要额外的工作。但线性化会显著降低性能和l可用性。
是线性化并非是保证因果关系的唯一途径 ，还有其他方位使得系统可以满足因果一致性而免于线性化所带来的性能问题。
因果一致性可以认为是 ，不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型
捕获因果依赖关系
为保持因果关系，需要知道哪个操作发生在前。
为了确定因果关系，数据库需要知道应用程序读取的是哪个版本的数据。
序列号排序
虽然因果关系很重要，但实际上跟踪所有的因果关系不切实际 。
可以使用序列号或时间戳来排序事件。它可以只是一个逻辑时钟，例如采用算桂来产生一个数字序列用以识别操作，通常是递增的计数器。
可以按照与因果关系一致的顺序来创建序列号，井行操作的序列可能是任意的。这样的全局排序可以捕获所有的因果信息，但也强加了比因果关系更为严格的顺序性。
从节点按照复制日志出现的顺序来应用写操作，那结果一定满足因果一致性。
非因果序列发生器
如果系统不存在这样唯一的主节点，则可以使用奇偶、时间戳、序号分区等方法确保区分不同的操作，但都存在一个问题，所产生的序列号与因果关系井不严格一致。
lamport时间戳
Lamport时间戳包括计数器信息，还有节点编号，可以保证每个键值对是唯一的。Lamport时间戳可以保证全序与因果关系一致【Lamport时间戳并不是真的时间戳，比较时计数器相同的话就比较节点编号，节点编号越大，则Lamport时间戳越大】
每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，井在每个请求中附带该最大计数器值。当节点收到某个请求（或者回复）时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值。
版本向 量用以区分两个操作是并发还是因果依赖，而Lamport时间戳则主要用于确保全序关系。即使Lamport时－间戳与因果序一致，但根据其全序关系却无怯区分两个操作属于并发关系，还是因果依赖关系 。 Lamport时间戳优于版本向量之处在于它更加紧凑和高效。
时间戳排序依然不够
根据时间戳方法确定胜利者有这样一个前提条件：需要收集系统中所有的用户创建请求，然后才可以比较它们的时间戳。但是节点根本不知道是否有另一个节点在同时创建相同用户名（以及那个请求所附带的时间戳）。而为了获得上述两点信息，系统就必须检查每个节点，如果万一某个节点出现故障或者由于网络问题而无法连接，那么方陆就无主主正常运转。
为了实现像用户名唯一性约束这样的目标，仅仅对操作进行全序排列还是不够的，还需要知道这些操作是否发生、何时确定等
全序关系广播
如何扩展系统的吞吐量使之突破单一主节点的限制，以及如何处理主节点失效时的故障切换，在分布式系统研究文献中，这些问题被称为全序关系广播或者原子广播
全序关系广播通常指节点之间 交换消息的某种协议。它要求满足两个基本安全属性：
- 可靠发送：没有悄息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点。
- 严格有序：消息总是以相同的顺序发送给每个节点。
即使节点或网络出现了故障，全序关系广播算法的正确实现也必须保证上述两条。算法要继续重试，直到最终网络修复，消息发送成功（且必须以正确的顺序发送）。
使用全序关系广播
如果每条消息代表数据库写请求，并且每个副本都按相同的顺序处理这些写请求，那么所有副本可以保持一致，该原则也被称为状态机复制。
可以使用全序关系广播来实现可串行化事务。
理解全序关系广播的另 一种方式是将其视为日志（如复制日志，事务日志或预写日志）。传递消息就像追加方式更新日志。由于所有节点必须以相同的顺序发送消息，因此所有节点都可以读取日志井看到相同的消息序列。
采用全序关系广播实现线性化存储
全序关系广播是基于异步模型 ：保证消息以固定的 )II页序可靠地发送 ，但是不保证消息何时发送成功 （因此某个接收者可能明显落后于其他接收者 ）。而可线性化则强调就近性：读取时保证能够看到最新的写入值。
如果有了全序关系广播，就可以在其上构建线性化的存储系统。
采用线性化存储实现全序关系广播
对于每个要通过全序关系广播的消息，原子递增井读取该线性化的计数，然后将其作为序列号附加到消息中。接下来，将消息广播到所有节点（如果发生丢失， 则重新发送），而接受者也严格按照序列化来发送回复消息。
分布式事务与共识
有很多重要的场景都需要集群节点达成某种一致，例如：
- 主节点选举
- 原子事务提交
FLP结论表明如果节点存在可能崩溃的风险，则不存在总是能够达成共识的稳定算法 。在分布式系统中，我们必须假设节点可能会崩溃。FLP结论是基于异步系统模型而做的证明，这是一个非常受限的模型，它假定确定性算法都不能使用任何时钟或超时机制 。FLP结论有其重妥的理论意义，但对于实际的分布式系统通常达成共识是可行的 。
原子提交与两阶段提交
原子性可以防止失败的事务破坏系统，避免形成部分成功夹杂着部分失败。
从单节点到分布式的原子提交
对于在单个数据库节点上执行的事务，原子性通常由存储引擎来负责。当客户端请求数据库节点提交事务时，数据库首先使事务的写入持久化，然后把提交记录追加写入到磁盘的日志文件中，因此，在单节点上，事务提交非常依赖于数据持久写入磁盘的顺序关系：先写入数据，然后提交记录。
如果一个事务涉及多个节点，向所有节点简单地发送一个提交请求，然后各个节点独立执行事务提交是绝对不够的。这样做很容易发生部分节点提交成功，而其他一些节点发生失败，从而违反了原子性保证。
而且某个节点一且提交了事务，即使事后发现其他节点发生中止，它也无故再撤销已提交的事务，因为一旦数据提交，就被其他事务可见，继而其他客户端会基于此做出相应的决策。如果允许事务在提交后还能中止，会违背之后所有读－提交的事务，进而被迫产生级联式的追溯和撤销。
两阶段提交
两阶段提交（2PC ）是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。【不要混淆两阶段提交2PC和两阶段加锁2PL】
2PC引入了单节点事务所没有的一个新组件 ： 协调者（ 也称为事务管理器）。协调者通常实现为共享库，运行在请求事务相同进程中，但也可以是单独的进程或服务。
通常，2PC事务从应用程序在多个数据库节点上执行数据读／写开始。我们将这些数据库节点称为事务中的参与者。当应用程序准备提交事务时 ，协调者开始阶段l：发送一个准备请求到所有节点，询问他们是否可以提交。协调者然后跟踪参与者的回应 ：如果所有参与者回答：是，则提交开始实际执行，否则放弃请求。
系统的承诺
参与者在收到准备请求之后 ，确保在任何情况下都可以提交事务 ，包括安全地将事务数据写入磁盘，不能以任何借口稍后拒绝提交，包括系统崩愤，电源故障或磁盘空间不足等，并检查是否存在冲突或约束违规。 一且向协调者回答“是”，节点就承诺会提交事务。换句话说，尽管还没有真正提交，但参与者已表态此后不会行使放弃事务的权利。
协调者的决定写入磁盘之后 ，接下来向所有参与者发送提交（或放弃）请求。 如果此请求出现失败或超时，则协调者必须一直重试 ，直到成功为止。
当参与者投票“是”时，它做出了肯定提交的承诺。其次，协调者做出了提交（或者放弃）的决定，这个决定也是不可撤销。正是这两个承诺确保了 2PC的原子性（而单节点原子提交其实是将两个事件合二为一，写入事务日志即提交）。
协调者发生故障
如果协调者在发送准备请求之前就已失败， 则参与者可以安全地中止交易。
参与者发出是的投票后，必须等待协调者的决定，如果在决定到达之前，出现协调者崩愤或网络故障， 则参与者只能无奈等待。
理论上，参与者之间可以互相通信，通过了解每个参与者的投票情况并最终达成一致，不过这已经不是2PC协议的范畴了。2PC能够顺利完成的唯一方法是等待协调者恢复。这也就是为什么协调者在发送请求之前要写入日志，以便恢复后继续执行。
三阶段提交
两阶段提交也被称为阻塞式原子提交协议，因为2PC可能在等待协调者恢复时卡住。
3PC假定一个有界的网络延迟和节点在规定时间内 H向应。考虑到目前大多数具有无限网络延迟和进程暂停的实际情况，它无法保证原子性 。
非阻塞原子提交依赖于一个完美的故障检测器，但超时机制并不是可靠的故障检测器。因此目前还在普遍使用2PC。
实践中的分布式事务
分布式事务的某些实现存在严重的性能问题。两阶段提交性能下降的主要原因是为了防崩愤恢复而做的磁盘I/O 以及额外的网络往返开销。
目前由两种截然不同的分布式事务概念 ：
- 数据库内部的分布式事务：某些分布式数据库（例如那些标配支持复制和分区的数据库）支持跨数据库节点的内部事务。
- 异构分布式事务：在异构分布式事务中，存在两种或两种以上不同的参与者实现技术。即使是完全不同的系统，跨系统的分布式事务业必须确保原子提交，
Exactly-once消息处理
异构的分布式事务旨在无缝集成多种不同的系统。
当且仅当数据库中处理消息的事务成功提交，消息队列才会标记该消息已处理完毕。这个过程是通过自动提交消息确认和数据库写入来实现的。即使消息系统和数据库两种不同的技术运行在不同的节点上，采用分布式事务也能达到上述目标。
XA交易
XA交易是异构环境下实施两阶段提交的一个工业标准，是一个与事务协调者进行通信的API
XA假定应用程序通过网络或客户端的库函数与参与者（包括数据库、消息服务）节点进行通信。
事务协调者需要实现XAAPI。协调者通常也是一个 API库，它与产生事务的应用程序运行在相同的进程中 。
停顿时仍持有锁
在两阶段提交时， 事务在整个停顿期间一直持有锁。如果协调者崩溃，那么这些对象会一直被锁定。这可能会导致很多上层应用基本处于不可用状态，所以必须解决处于停顿状态的那些事务。
从协调者故障中恢复
唯一的出路只能是让管理员手动决定究竟是执行提交还是回滚。
许多 XA的实现都支持某种紧急避险措施称之为启发式决策：这样参与者节点可以在紧急情况下单方面做出决定，放弃或者继续那些停顿的事务，而不需要等到协调者发出指令
但这里的启发式可能破坏原子性，违背了两阶段提交所做出的承诺。
分布式事务的限制
- 如果协调者不支持数据复制，而是在单节点上运行，那么它就是整个系统的单点故障
- 评多服务器端应用程序都倾向于无状态模式，但协调者的日志成为可靠系统的重要组成部分，它要求与数据库本身一样重要（需要协调者日志恢复那些有疑问的事务）。这样的应用服务器已经不再是无状态。
- 由 于XA需要与各种数据系统保持兼容 ，它最终其实是多系统可兼容的最低标准。
- 2PC要成功提交事务还是存在潜在的限制，它要求必须所有参与者都投票赞成， 如果有任何部分发生故障，整个事务只能失败。
支持容错的共识
通俗理解，共识是让几个节点就某项提议达成一致。共识算法必须满足以下性质：
- 协商一致性，所有的节点都接受相同的决议。
- 诚实性，所有节点不能反悔， 即对一项提议不能有两次决定。
- 合法性，如果决定了值v ，则v一定是由某个节点所提议的。
- 可终止性，节点如果不崩溃则最终一定可以达成决议。
可终止性属于一种活性，而另外三种则属于安全性方面的属性。
可以证明任何共识算怯都需要至少大部分节点正确运行才能确保终止性。可终止性的前提是，发生崩愤或者不可用的节点数必须小于半数节点。
共识算法与全序广播
许多著名的容错式共识算法大部分其实并不是直接使用上述的形式化模型（提议井决定某个值，同时满足上面4个属性），相反，他们是决定了一系列值，然后采用全序关系广播算法。
全序关系广播的要点是，消息按照相同的顺序发送到所有节点，有且只有一次 。 如果仔细想想，这其实相当于进行了多轮的共识过程 ： 在每一轮，节点提出他们接下来想要发送的消息，然后决定下一个消息的全局顺序，所以，全序关系广播相当于持续的多轮共识。
主从复制与共识
如果主节点是 由运营人员手动选择和配置的 ，那基本上就是一个独裁性质的 “一致性算法”
一些数据库支持自动选举主节点和故障切换，通过选举把某个从节点者提升为新的主节点。这样更接近容错式全序关系广播，从而达成共识。我们需要共识算在去选出一位主节点，但主从复制现在又需要选举主节点。
Epoch和Quorum
如果发现当前的主节点失效，节点就开始一轮投票选举新的主节点 。 选举会赋予一个单调递增的巳epoch号。如果出现了两个不同的主节点对应于不同epoch号码,则具有更高epoch号码的主节点将获胜。在主节点做出任何决定之前，它必须首先检查是否存在比它更高的epoch号码，否则
就会产生冲突的决定。主节点如何知道它是否已被其他节点所取代了呢,它必须从quorum节点中收集投票.
共识的局限性
- 在达成一致性决议之前，节点投票的过程是一个同步复制过程。数据库通常配置为异步复制，存在某些已提交的数据在故障切换时丢失的风险，即使这样，很多系统还是采用异步复制（而非同步复制），原因正是为了更好的性能。
- 共识体系需要严格的多数节点才能运行。
- 多数共识算在是假定一组固定参与投票的节点集，这意味着不能动态、添加或删除节点 。
- 共识系统通常依靠超时机制来检测节点失效。误判会导致频繁的选举从而浪费资源。
- 共识算法往往对网络问题特别敏感。
成员与协调服务
ZooKeeper的实现其实模仿了 Google的 Chubby分布式锁服务，但它不仅实现了全序广播（因此实现了共识），还提供了其他很多有趣的特性：
- 线性化的原子操作
- 操作全序
- 故障检测
- 更改通知
ZooKeeper集成了所有这些功能，在分布式协调服务中发挥了关键作用。
节点任务分配
ZooKeeper可以非常方便地使应用程序达到自动故障中恢复，减少人工干预。
ZooKeeper通常是在固定数量的节点（通常三到五个）上运行投票，可以非常高效地支持大量的客户端。
服务发现
每当节点启动时将其网络端口信息向 ZooKeeper等服务注册，然后其他人只需向 ZooKeeper的住册表中询问即可。
成员服务
ZooKeeper等还可以看作是成员服务范畴的一部分。成员服务用来确定当前哪些节点处于活动状态井属于集群的有效成员。可以将故障检测与共识绑定在一起，让所有节点就节点的存活达成一致意见。