第九章 一致性与共识
分布式一致性模型和事务隔离级别有相似之处；
可线性化
基本思想是将分布式系统看为一个节点，且操作均满足原子性；
核心思想是保证客户端在任意时刻都不会读到旧数据；
可线性化和可串行化 前者是读写单节点的最新值保证； 后者是事务的隔离级别，确保事务的执行如同串行执行事务般；
系统容错常用复制机制：
主从复制(部分支持 线性化)，即选用同步复制时，且需要做到并发安全时（即全局的操作顺序性），视为实现了线性一致性；当选用半同步或者异步复制时，仅满足最终一致性；
共识算法，可满足线性一致性，可降级写是线性一致性，读是最终一致性；
多主复制，不可线性化，只能通过异步复制，如 redis cluster；
无主复制，严格的quorum是实现线性一致性条件之一，即使满足仲裁条件 w+r＞n （w 为写入成功节点数量，r 为读取成功节点数量，n 为总节点数），也可能读到旧值(因为写入操作不需要达成共识)；
cap
正式定义的cap定义范围很窄，仅考虑了一种一致性模型(线性化)和一种故障(网络分区)，没有考虑网络延迟，节点失败等情况；（即ca的取舍是建立在发生网络分区的前提下的，即p的取值只能为0或者1）
podc：不要求全局有序，允许存在部分有序的操作，同样强调 局部一致性，而不是全局一致性，可容忍网络延迟、节点故障等问题，核心思想是降低全局要求，从而提高性能、容错性、可扩展性；
顺序保证
顺序有助于保证因果关系；
因果一致性即系统满足因果关系中的顺序；
注意，因果一致性偏序关系，无因果的操作无法被排序比较，可以并发或者无序执行；
偏序关系（Partial Order）
是定义在一个集合上的二元关系，它满足以下三个条件：
- 自反性（Reflexivity）：对于集合中的任何元素 。a，有 $a \leq a$；
- 反对称性（Antisymmetry）：如果 $a \leq b$ 且 $b \leq a$，则 $a = b$；
- 传递性（Transitivity）：如果 $a \leq b$ 且 $b \leq c$，则 $a \leq c$；
在偏序关系中，不要求任意两个元素之间都可以比较，这意味着某些元素可能无法直接比较，例如，集合中的元素 a 和 b 可能既不满足 $a \leq b$，也不满足 $b \leq a$，即它们是不可比较的；
eg：子集关系是一个典型的偏序关系。对于集合 $A = {1, 2}$、$B = {1}$、$C = {2}$，我们有 $B \subseteq A$ 和 $C \subseteq A$，但是 b 和 c 无法比较（因为它们之间既不是子集关系，也不是包含关系）；
全序关系（Total/Full Order）
是一种特殊的偏序关系，它满足偏序关系的所有条件，并且还具备一个额外的条件：
- 可比性（Comparability）：对于集合中的任意两个元素 a 和 b，要么 $a \leq b$，要么 $b \leq a$。即任何两个元素都可以进行比较；
全序关系表示的是一个线性排列，集合中的所有元素都可以按某种顺序排列起来；
实数集 上的大小关系 $\leq$ 是一个全序关系，因为对于任意两个实数 a 和 b，要么 $a \leq b$，要么 $b \leq a$；
而 可线性化 则是典型的 全序关系，全局有一条确定的时间线，操作可被比较先后；
可以发现 可线性化 包含 因果一致性，但是实际应用 线性一致性 时，性能和可用性显著被降低，而使用 因果一致性 可以保证业务逻辑不错的前提下，不会因为网络延迟而显著影响性能，又对网络故障提供容错，可视为实际上最优的一致性模型；
（注，仍然存在挑战，尚未投入生产 [52] Philippe Ajoux, Nathan Bronson, Sanjeev Kumar, et al:“Challenges to Adopting Stronger Consistency at Scale,” at 15th USENIX Workshop on Hot Topics in Operating Systems (HotOS),May 2015. [53] Peter Bailis:“Causality Is Expensive (and What to Do About It),” bailis.org, February5,2014.）
因果一致性在约束因果顺序方面比最终一致性更强；
在 最终一致性 中，系统只保证在没有进一步操作时，所有节点的状态最终会收敛为一致的状态，但不对操作顺序提出约束；
在 因果一致性 中，除了最终一致性要求的状态收敛外，系统还保证因果相关的操作按正确顺序发生，即写操作在副本之间传播时，系统要确保所有节点都遵守因果顺序；
因果一致性 的实现需要确保因果关系相关的操作顺序正确，实现：
操作标记：
为了保持因果关系，系统需要为每个操作添加一些元信息，用来表示操作的发生顺序:
逻辑时钟：每个操作都附带一个逻辑时钟（如 Lamport 时钟），表示该操作的顺序。通过比较时钟值，可以确定操作的先后顺序，但这仅适用于单一时间维度；
向量时钟（Vector Clocks）：向量时钟是因果一致性实现的常用方法，每个节点维护一个向量时钟，记录与其他节点的通信历史；通过比较向量时钟，系统可以判断操作之间是否存在因果关系；向量时钟比单一的逻辑时钟更准确地表示因果关系，因为它能够跟踪多个节点的状态；
注：类似uuid的序列号，无法区分有无因果关系，因为它有严格的顺序性，将所有操作都视为有因果关系；
通过维护 写后读依赖 来确保因果关系的顺序：
如果某个节点读取了另一个节点的写操作，那么该节点后续的写操作必须在前一个写操作的因果顺序之后进行；
每个节点会跟踪它读取的最新数据以及它产生的写操作，确保它的写操作在所有读取到的数据之后；
允许多个副本异步更新，但因果相关的写操作需要按顺序传播，如：
如果副本 A 依赖于从副本 B 读取的数据进行写操作，A 的更新必须在 B 的写操作之后被传播到其他节点；
在传播更新时，系统会检查并确保与之因果相关的操作已经传播到该节点，防止出现不一致的顺序；
实际应用场景
社交网络：用户发布消息和查看消息之间有因果关系；如，用户 A 发布了一条状态更新，用户 B 赞了这条状态，因果一致性会确保所有看到 B 的点赞行为的用户，已经看到了 A 发布的状态；
协同编辑系统：多个用户同时编辑文档，操作之间可能存在因果关系；因果一致性保证因果相关的修改操作会按正确的顺序进行传播和应用；
lamport时间戳
每个节点有唯一标识符，且维护一个计数器记录本身处理的请求总数，lamport是值对，保存计数器值和节点id，每个节点和客户端会追踪接收/处理最大的计数器值，并在每个请求附带该值，如果其他请求的值大于本身的计数器值，则修改为新的最大值；
相对于版本向量更紧凑和高效；
但很明显的缺点，节点间需要交换请求才会达成共识，即并发环境下可能出现同时创建相同的唯一数据，造成冲突；
故可引入全序关系广播解决；
全序关系广播
通常指节点间交换信息的某种协议，信息按照相同的顺序发送到所有节点，满足两个安全属性:
可靠发送，不出现信息丢失（允许重试）；
严格有序，信息不乱序；
可用于实现串行化事务；
也可理解为传递日志，顺序追加，所有节点上的日志序列相同；
状态机复制：每个副本都按照相同的顺序应用写操作；
同时也保证fencing令牌的顺序生成，序列号也可直接作为令牌，因为符合单增；
注：线性化和共识不等价，共识是分布式系统中的一种机制，而线性化是一种一致性模型
共识问题是指在分布式系统中，多个节点如何在存在故障或不可靠通信的情况下就某个值达成一致；
安全性：所有节点要么同意同一个值，要么不会作出决定；
终止性：只要大多数节点正常运行，最终系统会达成一致；
共识不直接涉及系统的操作顺序；
线性化是一种强一致性模型，它确保系统中的所有操作看起来都像是原子地、瞬时地发生在某个点上，且每个操作都必须反映之前的操作结果；
实时顺序：系统的所有操作必须遵循真实时间的顺序。如果一个操作在另一个操作之后开始，那么它的结果必须反映前一个操作的结果；
线性化用于保证分布式系统的操作顺序与顺序一致性不同，线性化还需要系统行为在全局上看起来就像是瞬时执行的，并与实际发生的时间顺序一致；
目标不同：共识算法关注的是让多个节点对某个值或操作达成一致，而线性化更关注操作的全局顺序及其对外表现的一致性;
线性化是一个更高层次的保证
如：基本的raft仅提供写入线性化，此时被称为共识算法（读请求是顺序一致性），当提供读写线性化时，才可被称为线性化算法；
read index：即 将读操作也写入日志进行同步，apply后server将结果响应回client；
lease read：即 leader 维护一个租期（至少小于选举超时时间），当收到 follower 的响应（append rpc均可）后，刷新租期，当读请求在租期内到达 leader 后，直接apply ok到 server 层，响应回client；（注:至少 leader 需要在当前任期已经发送过一次 append rpc后，才可使用该机制，否则可能出现图8的错误）
而全序关系广播是一种共识机制，基于异步模型，保证信息顺序发送，但是不保证信息在确定时间内发送成功；
可以在全序关系广播的基础上做线性化保证，如唯一标识下可做原子的cas时：
流程：
用户名注册请求：当一个客户端想要注册一个用户名时，客户端将该请求发送到任意一个节点；
全序广播注册请求：接收到注册请求的节点会通过全序广播机制，将该请求广播给系统中的所有节点，确保所有节点都能以相同的顺序处理这个注册请求；
一致性检查：节点接收到广播的注册请求后，先检查该用户名是否已经存在：
如果该用户名不存在，则将该用户名标记为已注册，并向客户端确认注册成功；
如果该用户名已经存在，则拒绝注册请求，并向客户端返回失败信息；
注意此时的读请求也是不满足线性化的，当选用多数派的响应时，满足顺序一致性；
线性化读的方案：
同样将读请求作为日志，排序，广播后达成多数派时，执行读操作并响应；(类似于etcd的quorum)
线性化获取当前最新日志中消息的位置，等待直到该位置之前所有条目都已经应用到所有节点上后，接下来再执行读取；(类似于zk的sync操作)
从同步更新的副本进行读取，确保读到最新值；(如链式复制)
分布式事务与共识
需要达成一致的场景:
主节点选举，防止出现脑裂；
原子事务提交:
即需要分布式事务，防止事务在部分节点成功，其他失败，为了保证所有节点必须对事物的结果达成一致；
共识的不可能性: FLP理论，表示如果节点存在崩溃的风险，则不存在总能达成共识的稳定算法； FLP理论是基于异步系统模型而建立的，如果算法可以使用超时或其他方法检测崩溃节点，则可实现稳定的共识方案；(随机数检测也可)
原子提交与两阶段提交
事务最后成功提交后，不可回溯，但可以开一个补偿性的事物抵消掉；
2pc
注：两阶段提交 负责在分布式下的原子提交，而两阶段加锁 提供可串行化的隔离；
支持容错的共识
共识算法的性质:
协商一致性，所有节点都接受相同的决议；
诚实性，所有节点不能反悔，对同一提案不得有两次决定；
合法性，如果确定一个值，则该值对应的日志一定为某个节点发起的提案；
可终止性，节点不崩溃的前提下，一定能达成决议；
2pc 就仅满足前三个属性，因为只有一个固定 leader，所以不支持可终止性，任何共识算法都需要大多数节点正常运行才可确保终止性，大多数就可以构成安全的quorum；
epoch和quorum
常见的共识算法都提供了一种弱化的，存在主节点的保证，协议都定义了一个 epoch number，（paxos 对应为 ballot number，vsp 对应为 view number，raft 对应为 term number）在每个epoch中主节点是唯一确定的；
如果存在不同epoch的主节点，将会以更高epoch的主节点为准，所以主节点为保证自己是最大epoch，在作出任何决定时，都需要从 quorum 节点中收集赞成票；
成员与协调服务
zk 特性:
线性化的原子操作，原子cas实现加锁服务；
操作全序，对所有操作进行全局排序，然后为每个操作都赋予一个单增的事务id(zxid)和版本号(cversion，用于跟踪该节点下子节点的变化（创建或删除子节点）)
故障检测，通过心跳检测客户端存活，如果挂了则会释放该会话持有的锁资源(可配置)；
更改通知，watch机制，一次性触发，异步通知，支持watch:数据变化，子节点变化，节点存在性变化；