一致性保证
分布式一致性主要针对延迟和故障等问题来协调副本之间的状态。
- 线性化：最强一致性模型
- 顺序保证：保证时间顺序，特别是因果关系和全局顺序
- 最终一致性：一种非常弱的保证，参见最终一致性效应
可线性化
分布式语义下对寄存器（单个对象）顺序的读写。应区别与可串行化。
- 可串行化针对不同事务的隔离，用来确保事务执行的结果与串形执行的结果相同
- 可线性化是读写寄存器（单个对象）的最新值的保证。
线性化依赖的条件
加锁与主节点选举
每个启动节点都试图获得锁，其中只有一个可以成功成为主节点。通过加锁来保证主节点选举「线性化」。
约束与唯一性保证
同一个用户名、电子邮件或系统中文件名需要唯一性的保证，也应该进行「线性化」。
跨通道的时间依赖
系统中存在其他通信渠道也需要「线性化」。
实现线性化系统
- 主从复制（部分支持可线性化）
- 共识算法（可线性化）
- 多主复制（不可线性化）
- 无主复制（可能不可线性化）
线性化与Quorum 一致性
Dynamo 风格的复制模型，读写遵从严格的 quorum 是无法支持可线性化的。
线性化的代价
多主复制和主从复制，网络中断都会导致同步暂停，从而无法保证客户端要求的线性化读写。
CAP 理论
可线性化与网络延迟
很少有系统真正满足线性化，现代多个 CPU 对同一个内存地址的读写都不能满足（参见硬件内存模型），如果需要强一致则需要内存屏障（栅栏）指令。
之所以放弃线性化的原因就是性能，而不是为了容错。由于网络延迟的不确定性，无论是否发生网络故障，线性化对性能的影响都是巨大的。
顺序保证
顺序与因果关系
顺序有助于保持因果关系。
序列号排序
非因果序列发生器
适用于系统不存在唯一主节点。
- 每个节点都独立产生自己的一组序列号：一个奇数一个偶数，或者切入节点唯一标识符。
- 用足够高的分辨率的墙上时间戳附加到每个操作上。
- 预先分配区间范围，并及时扩容。
Lamport 时间戳
可以产生因果关系一致的序列号。Lamport 时间戳是一个值对 （计数器，节点 ID） ：
- 节点 ID：每个节点都有一个唯一标志符。
- 计数器：每个节点都有一个计数器记录各自处理的请求总数。
优点：
- 两个节点可能存在相同的计数器，但是时间戳中的节点 ID 可以确保每个时间戳都是唯一的。
- 保证全序：比较两个 Lamport 时间戳，计数器较大的时间戳越大，计数器相同则节点 ID 大的那个时间戳越大。
通过节点排序保证了全局因果关系。Lamport 不同于版本矢量：
- 版本矢量用以区分两个操作是并发还是因果依赖。
- Lamport 时间戳主要用于确保全序关系。
时间戳依然不够
某些场景下全序关系依然不能满足需求，比如用户名唯一性要求，为了确认用户名唯一，需要获取所有节点正在进行的请求，查看有没有相同的用户名请求，才能建立全序关系。
全序关系广播
分布式系统面临的问题：
- 分布式系统中让所有节点就全序关系达成一致。
- 如何扩展系统的吞吐量使之突破单一主节点的限制。
- 如何处理主节点失效时的故障切换。
全序关系广播通常指节点之间交换消息的某种协议。需要满足两个基本安全属性：
- 可靠发送：没有消息丢失，一定发送到所有节点。
- 严格有序：消息总是以相同顺序发送给每个节点。
全系关系广播使用场景
ZooKeeper 和 etcd 这样的共识服务实际上就实现了全序关系广播。
- 数据库复制：通过消息传递代表数据库写请求，让每个副本按照相同的顺序处理写请求，那么副本可以保持一致。
- 可串形化事务：通过消息表示确定性事务并且作为存储过程来执行，切每个节点都遵从相同的执行顺序。
- 提供 Fencing 令牌的锁服务：每个获取锁的请求都作为消息附加到日志中，所有消息按照日志中的顺序一次编号。（ZooKeeper 的 zxid）。
全序关系广播和可线性化
- 全系关系广播：基于异步模型，保证消息以固定顺序可靠的发送，但是不保证消息何时发送成功
- 可线性化强调就近性：读取时保证能够看到最新写入值。
采用全序关系广播实现线性化存储
可以通过使用全序关系广播以追加日志的方式来实现线性化的原子比较-设置操作：
- 日志中追加一条消息，并指明用户名
- 读取日志，将其广播给所有节点，并等待回复
- 检查是否有任何消息声称改用户名已被注册。如果第一条这样的回复来自当前节点，那么就成功获取用户名。
此过程只保证了线性化写入，无法保证线性化读取，这里只提供了顺序一致性有时也成为时间线一致性，弱与线性化的保证。
满足线性化读取的方案：
- ectd 的 quorum 读取：追加的方式把读取请求排序、广播，然后各个节点获取该日志，当本节点收到消息时才执行真正的操作。
- ZooKeeper 的 sync() 操作：如果可以以线性化的方式获取当前最新日志中的消息的位置，则查询位置，等待直到该位置之前的所有条目都已经发送给你，接下来再执行读取。
- 可以从同步更新的副本上进行读取，这样确保总是读取最新值。这种技术可以用于链式复制。
采用线性化存储实现全序关系广播
通过线性化存储递增一个计数，相比于 Lamport 时间戳 其具有连续性，可以检测消息可靠性。
实现线性化存储难点是失效。
分布式事务与共识
共识问题是分布式计算中最重要也是最基本的问题之一。
很多重要的场景需要集群节点达成一致，例如：
- 主节点选举：脑裂。
- 原子事务提交：跨节点或跨分区事务提交。所有节点要么全部成功，要么全部中止。
原子提交与两阶段提交
两阶段提交
- tags: 分布式共识
2PC 是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。
不同于单节点上请求提交，2PC 中的提交/中止过程分为两个阶段。
不要混淆 2PC 和 2PL。
2PL 引入了新的组件：协调者（也称为事务管理器）。协调者通常实现为共享库，运行在请求事务相同进程中，但也可以是单独的进程或服务。
数据库节点称为事务中的参与者。当应用程序准备提交事务时，协调者开始阶段1:发送一个准备请求到所有节点，询问它们是否可以提交。协调者然后跟踪参与者的回应：
- 全部回应「是」：表示准备好提交，协调者开始阶段 2 ，提交开始实际执行。
- 任何回应「否」：协调者发送放弃请求。
实践中的分布式事务
目前两种截然不同的分布式事务：
- 数据库内部的分布式事务：所有节点运行相同的软件，协议也是内部的无需考虑兼容性。
- 异构分布式事务：存在两种或两种以上的不同参与者实现技术。即使完全不同的系统，跨系统的分布式事务必须确保原子提交。
异构分布式事务充满挑战。
Exactly-once 消息处理
异构分布式事务旨在无缝集成多种不同的系统。消息队列通过自动提交消息和消息处理结果，可以确保消息可以有效处理有且仅有一次。 让系统可以进行安全的重试，来保持原子性。
X/A 交易
X/Open XA（eXtend Architectrue，XA）是异构环境下实施两阶段提交的一个工业标准。其并不是一个网络协议，而是一个 C API。 XA 假定应用程序通过网络或者客户端库函数与参与者节点进行通信。事务协调者需要实现 XA API。
应用程序崩溃，事务日志保存在应用服务本地磁盘，需要重启崩溃节点，XA API 读取日志，进而恢复事务的决定。
停顿扔持有锁
从协调者故障恢复
启发式决策：参与者节点可以在紧急情况下单方面做出决定，放弃或者继续那些停顿的事务，而不需要等到协调者发出指令。
分布式事务限制
- 如果协调者不支持数据复制，会造成单点故障。
- 破坏现在很多 HTTP 服务的无状态特性。
- X/A 需要保持多系统可兼容的最低标准，来兼容各种数据系统，无法实现诸如死锁检测和 SSI。
- 分布式事务有扩大事务失败的风险，与构建容错系统背道而驰。
支持容错的共识
共识就是让几个节点就某项协议达成一致。
需要满足的性质：
- 协商一致性（Uniform agreement）：所有节点都接受相同的决议。共识的核心思想：决定一致的结果，一旦决定，就不能改变。
- 诚实性（Integrity）：所有节点不能反悔，即对某一些提议不能有两次决定。
- 合法性（Validity）：如果决定了值 v，则 v 一定是由某个节点锁提议的。
- 可终止性：节点如果不崩溃则最终一定可以达成决议。引入容错思想：强调共识算法不能原地空转，必须取得实质性的进展。属于一种活性（安全性和活性)。
大部分节点都正常运行才能确保可终止性，这个多数就可能安全的构成 quorum。
可终止性的前提下，发生崩溃或者不可用的节点数必须小于半数节点。
大多数共识算法都假定系统不存在拜占庭故障。
共识算法与全序广播
最著名的容错式共识算法包括：VSR、Paxos、Raft 和 Zab。
这些算法实际上并没有直接采用上述的形式化模型：提议一个值，同时满足上面 4 个属性。 相反，他们是决定一个值，然后采用全序关系广播算法：在每一轮中，节点提出他们接下来想要发送的消息，然后决定下一个消息的全局顺序。
全序广播相当于持续多轮共识：
- 由与协商一致性，所有节点决定以相同的顺序发送相同的消息。
- 由于诚实性，消息不能重复。
- 由于合法性，消息不会被破坏，也不是凭空捏造。
- 由于可终止性，消息不会丢失。
全序关系广播比重复性的一轮共识只解决一个提议更加高效（VSR、Raft 和 Zab，Paxos 对应的是其优化版本 Multi-Paxios）。
主从复制与共识
主从复制的主节点一般是有运维人员手动选择和配置的，是一个独裁性质的“一致性算法”。 如果支持自动选举主节点和切换，这样更接近容错式全序广播，从而达成共识。
共识面临选举一个主节点需要一个主节点。要解决共识，必须先处理共识。
Epoch 和 Quorum
共识算法协议采用了一种弱化保证：协议定义了一个世代编号（epoch number，Paxos 的 ballot number，VSP 的 view number，Raft 中的 term number）， 并保证在每个世代里，主节点是唯一确定的。
如果当前主节点失效，节点就开始一轮投票。选举会赋予一个单调递增的 epoch 号。
主节点如果想做某个决定，需将提议发送给其他所有节点，等待 quorum 节点响应。
两轮不同的投票：首先决定谁是主节点，然后对主节点的提议进行投票。
和 2PC 最大的区别是：
- 2PC 的协调者不依靠选举产生。
- 2PC 要求每个参与者都必须做出“是”，容错共识算法只需要收到多数节点的投票结果即可通过决议。
- 共识算法定义了恢复过程，出现故障可重新选举主节点。
共识的局限性
- 节点投票过程是一个同步复制过程。
- 许多严格的多数节点才能允许。3节点允许1节点失效、5/2。
- 多数共识算法假定一组固定参与投票的节点集，无法动态缩扩容。
- 依靠超时来检测节点失效。
- 对网络特别敏感，比如 Raft 中两个节点如果网络持续不可靠会出现主从反复切换，从而性能下降。
成员协调服务
- ZooKeeper
- etcd
将成千上万节点的共识交由像 ZooKeeper 这样由三五节点组成的共识代理大大提高性能。