一致性与共识
date
Jan 6, 2022
slug
conformance
status
Published
tags
DDIA
summary
DDIA第九章读书笔记
type
Post
“错误地活着，还是正确地挂掉？”
这一章主要讲了分布式系统中的容错机制
可以尝试建立让分布式应用忽略内部各种问题的抽象机制，比如分布式系统最重要的抽象之一就是共识：所有的节点就某一项提议达成一致。
一致性保证
大多数多副本的数据库都至少提供了最终的一致性，最终一致性意味着“收敛“，即预期所有的副本最终会收敛到相同的值。（这是个比较弱的一致性保证，它无法告诉我们系统何时会收敛）
可线性化
线性化的基本想法是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。有了这个保证，应用程序就不需要关心系统内部的多个副本。
如何达到可线性化？
我们可以添加一个约束，一旦某个读操作返回了新值，之后的所有的读（包括相同或不同的客户端）都必须返回新值。
（使用了快照隔离的数据库并不是可线性化的）
CAP理论
- 如果应用要求线性化，但由于网络方面的问题，某些副本与其他副本断开连接之后无法继续处理请求，就必须等待网络修复，或者直接返回错误。无论哪种方式，结果是服务不可用。
- 如果应用不要求线性化，那么断开连接之后，每个副本可独立处理请求例如写操作（多主复制）。此时，服务可用，但结果行为不符合线性化。
顺序保证
全序关系支持任何两个元素之间进行比较
因果顺序并非全序，而是偏序（前面的《复制》章节其实提到了这个因果关系，其实只有后面的操作“知道”或者“依赖”前一个操作的时候，这两个操作被定义为因果顺序）
追踪所有的因果关系不切实际
倒是还有一种更好的方式就是使用序列号或者时间戳来排序事件，比如主从复制数据库中主节点中的复制日志定义了与因果关系一致的写操作全序关系（虽然从节点的数据可能会滞后于主节点）
Lamport时间戳
每个节点都有一个唯一的标识符，且每个节点都有一个计数器来记录各自己处理的请求总数。Lamport时间戳是一个值对（计数器，节点ID），两个节点可能会有相同的计数器值，但是时间戳里面还包含节点的ID信息，因此可以保证每个时间戳都是唯一的。
Lamport时间戳的核心亮点在于使他们与因果性保持一致，每个节点以及每个客户端都追踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到某个请求（或者回复）时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值。
全序关系广播
全序关系广播通常指节点之间交换消息的某种协议。下面是一个非正式的定义，它要求满足两个基本安全属性：
- 可靠发送：没有消息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点。
- 严格有序：消息总是以相同的顺序发送给每个节点。
（网络中断的话算法要重试直到最终网络修复，消息以正确的顺序发送成功）
理解全序关系广播的另一种方式是将其视为日志（如复制日志，事务日志或预写日志）传递消息就像追加方式更新日志。由于所有日志必须以相同的顺序发送消息，因此所有节点都可以读取日志并看到相同的消息序列。
- 全序关系广播是基于异步模型：保证消息以固定的顺序可靠地发送，但是并不保证消息何时发送成功（因此某个接收者可能明显落后于其他接收者）
- 可线性化则强调就近性：读取时保证能够看到最新的写入值
分布式事务与共识
很多场景都需要集群节点达成某种一致，例如：
主节点选举和原子事务提交
两阶段提交（two-phase commit，2PC）
两阶段提交需要一个协调者，书上一个很形象的比喻“2PC这个过程有点像西方传统的婚姻仪式：主持人会询问新郎和新娘是否愿意与对方结为夫妇，通常双方都会回答”我愿意“，在确认之后和所有与会者的共同见证下，方可宣布完成婚姻承诺。而万一新郎或者新娘没有肯定回复，理论上仪式应该中止。
2PC有两个关键点来保证原子性。首先当参与者投票”是“的时候，他做出了肯定提交的承诺。其次，协调者做出了提交（放弃）的决定，这个决定也是不可撤销的。正是这两个承诺确保了原子性。
共识算法
共识算法必须满足的几个性质：
- 协商一致性：所有的节点必须要接受相同的决议。
- 诚实性：所有节点不能反悔，即对一项提议不能有两次决定。
- 合法性：如果决定了值v，则v一定是由某个节点所提议的。
- 可终止性：节点如果不崩溃则最终一定可以达成决议。