一致性与共识
一致性保证
分布式一致性与事务隔离的区别
- 事务隔离主要是为了避免由于同时执行事务而导致的竞争状态
- 分布式一致性主要关于，面对延迟和故障时，如何协调副本间的状态
线性一致性
即原子一致性（atomic consistency），强一致性
满足标准：使系统看起来只有一个副本
-
对于多副本系统，如果第一次从A副本读取，第二次从B副本读取同样的数据，有可能第二次看到的是旧数据，不满足线性一致性
- 解决方法：为读取添加约束，如果第一次读取读到新值，则后续读取也必须保证读到新值
线性一致与可序列化
- 可序列化为事务隔离范畴，保证每个事务在下一个事务开始之前完成
- 线性一致性是读取和写入寄存器（单个对象）的新鲜度保证
依赖线性一致性(线性一致性的应用场景)
-
锁定和领导选举
- 如在单主复制的系统中，使用分布式锁，拿到锁的节点判定为主节点，其锁必须是线性一致的：所有节点对拿到锁的锁的节点的达成一致，如ZK、ETCD
-
约束和唯一性保证
- 在分布式数据库中，各节点对唯一键的存储，账户余额等，均要求所有节点都同意一个最新的值
-
跨信道的时序依赖
-
如图所示异步图片缩放服务，如果第5步取图片时，第2步存储未完成，则有可能拿到旧版本或是空的图像源导致错误
-
实现线性一致的系统
-
单节点无法满足容灾要求，考虑用复制解决问题
-
单主复制–如果读取时会访问到不同节点，由于延迟，有可能不会线性一致
-
共识算法–包含防止脑裂和陈旧副本的措施，线性一致
-
多主复制–由于在多个节点上写入，并异步复制到其它节点，非线性一致
-
无主复制
- 严格的法定人数下，针对读操作，在数据不一致的情况下可以实施同步读修复；进行写操作之前必须法定数量节点的最新状态。这会引起性能损失。当一个键有多个并发写入时，不能保证线性一致性。
-
线性一致性的代价
-
CAP定理
- 一致性，可用性和分区容错性：三者只能择其二。不幸的是这种说法很有误导性【32】，因为网络分区是一种错误，所以它并不是一个选项：不管你喜不喜欢它都会发生
-
线性一致性和网络延迟
- 即使单台计算机中，CPU上的内存都不是线性一致的
- Attiya和Welch 【47】证明，如果你想要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比
顺序保证
顺序与因果
-
因果顺序不是全序的
-
线性一致性
- 任意两个操作，都能判定其先后顺序
-
因果性
- 针对于具有因果关系的两个操作，其具备顺序性。线性一致性上的所有操作均有序。
-
-
线性一致性强于因果一致性
- 在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行的最强的一致性模型
-
捕获因果关系
- 基于数据版本
序列号顺序
-
针对于单主复制，可为每个操作赋与一个单独的递增操作序号
-
非因果序列号生成器（非单主复制）
-
例子与存在问题
-
总共两个节点，一个产生奇数，一个产生偶数
- 如果奇数或偶数节点产生操作数远大于另一节点，则无法根据数字大小判断操作因果关系
-
将物理时钟的时间戳加到每个操作上
- 时钟偏移问题导致因果偏差
-
预先分配序列号块，如节点A从序列号1-1000，节点B1001-2000
- 某操作被分配在1001-2000，而与其在因果上更晚的操作被赋予在1-1000
-
-
-
兰伯特时间戳
-
每个节点的时间戳由各自的计数器和节点ID构成，节点ID大的判定其因果在后
- 思想：每个节点和每个客户端跟踪迄今为止所见到的最大计数器值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。
- 版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳总是施行一个全序
-
-
光有时间戳排序还不够
- 如多个节点同时收到带有相同手机号唯一性约束的创建操作（非单主），需要判定最小具有时间戳的操作成功，其余失败。然而如果要实时向客户端返回创建结果，则需要收集所有节点的操作，形成操作全序列。
- 此外还需要知道操作全序列何时产生，由此引出全序广播
全序广播
-
基本特性
-
可靠性
- 如果消息被传递到一个节点，它将被传递到所有节点
-
有序性
- 消息以相同的顺序传递给每个节点
-
-
使用全序广播
-
ZK ETCD已实现全序广播
-
应用
- 可序列化事务
- 实现提供防护令牌的锁服务，如在ZK中，每个获取锁的请求都在日志后附加一条消息，且每个消息有唯一的自增序号(zxid)
-
-
使用全序广播实现线性一致的存储
-
使用线性一致性存储实现全序广播
- 如利用自增序列将自增时获取的数值附加消息中
分布式事务与共识
原子提交与二阶段提交（2PC）
-
两阶段提交
-
请求同步阻塞问题
-
在commit阶段中，如果协调者崩溃了，参与者将处于存疑状态，对于数据库节点，如果在prepare阶段锁定了某行数据，则有可能由于其它事务需要修改该行而被阻塞最终导致数据库不可用
-
在commit阶段如果出现了部分参与者的commit请求丢失，则有可能出现数据不一致的问题
-
在发出commit之后协调者崩溃，而接收commit的唯一参与者也崩溃，此时事务状态不可知
-
异常处理
-
Prepare
- 协调者接收PrepareACK超时，则About
-
Commit
- 协调者接收commitACK超时，则会一直重试Commit
-
-
-
三阶段提交
-
同步非阻塞，超时涉及协调者与参与者
-
将prepare阶段划分为CanCommit与PreCommit两阶段，确保在提交commit之前所有节点状态相同
-
在收到PreCommit请求后，参与者会在本地记录redo与undo日志，以便About时进行回滚
-
异常处理
-
CanCommit
- 参与者没收到CanCommit，不做任何操作
- 协调者没有收到参与者的CanCommit的ACK或超时，执行About
-
PreCommit
- 参与者接收PreCommit超时，则About
- 协调者接收PreCommitACK超时，则About
-
DoCommit
- 参与者接收DoCommit超时，则自动Commit
- 协调者接收DoCommitACK超时，则About
-
-
实践中的分布式事务
-
恰好一次的消息处理
- 在异构系统中，当且仅当所有参与者均支持分布式事务时，系统才可满足恰好一次的语义
-
XA事务
- XA是一套API，通常是一套集成在客户端的库，向参与者发出请求并接收参与者的回应，同时，使用磁盘记录启动/终止事务的日志
-
怀疑时持有锁
- 当参与者在Prepare阶段申请了锁，而在事务提交/终止前，协调者发生崩溃，这会导致参与者的锁无法释放（或超时才能释放）
-
从协调者故障中恢复
- 一旦出现协调者故障导致参与者锁不释放，唯一的解决方法是由管理员决定事务是提交还是回滚，尽管许多XA实现均实现了启发式决策：允许参与者主动提交或回滚事务，但这会破坏分布式事务的原子性
-
分布式事务的限制
- 协调者单点故障
- 由于应用服务器保存了协调者的中间结果，因此应用服务器变为非无状态，不能直接扩展
- 不能检测系统间的死锁（因为这将需要一个标准协议来让系统交换每个事务正在等待的锁的信息）
- 不能SSI协同工作（因为这需要一个跨系统定位冲突的协议）
- 系统中任何部分失效都会导致事务失败
容错共识
-
基本概念
-
满足性质
-
一致同意
- 没有两个节点的决定不同
-
完整性
- 每个节点只决定一次
-
有效性
- 如果一个节点决定了值 v ，则 v 由某个节点所提议
-
终止
-
由所有未崩溃的节点来最终决定值
- 即容错性，为了防止单节点独裁崩溃导致进程挂起，共识算法也必须基于存活的节点推进进程产生结果
-
-
-
-
共识算法和全序广播
- 全序广播相当于进了多轮共识，较著名的算法有VSR、Raft Zab Paxos，vsr raft 和zab实现了全序广播
-
单领导者复制和共识
- 对于单主的系统下，如果主崩溃，在没有人工干预的情况下，系统不满足终止性，只有在人工干预的情况下才可取得进展
-
时代编号和法定人数
- 当每次主崩溃时，会选出新的一任主节点，选举会赋与新的递增时代编号
- 选主与提案申请均会开始一轮投票，要求参与提案投票的节点至少有一个在选主中出现（如果没有则有脑裂的可能，参见https://arxiv.org/pdf/1608.06696.pdf）
- 2PC需要所有参与者同意，而共识协议只需要多数同意即可
-
共识的局限性
- 投票过程是一种同步复制过程，相比异步复制有性能损失
- 依赖于多数节点运转
- 大多数投票算法假定节点数量固定，添加/删除节点困难，即使采用了动态成员扩展，算法也很难理解
- 依靠超时检测失效节点，在网络延迟变化剧烈的环境中，可能会出现频繁选主的问题
成员与协调服务
-
ZK特性
- 线性一致性的原子操作。当有多个节点同时进行相同的操作，只有一个能成功
- 操作的全序排序。当使用锁或租约时，每次操作均会被赋与递增的ZXID与cversion作为令牌
- 失效检测。依赖于心跳检测
- 变更通知。可接收节点的加入与退出事件所产生的通知（基于客户端写入新的ZK的值与临时节点失效）
-
将工作分配给节点
- 主节点失效转移（可借助临时节点检测）
- 分区资源分配，当有节点加入系统时，可将现有分区转移至新节点
-
服务发现
-
成员服务