《数据密集型应用系统设计》第九章《一致性与共识》笔记
一致性保证
最终一致性（eventual consistency）：如果停止更新数据，等待一段时间（时间长度未知），则最终所有读请求将返回相同的内容。
然而最终一致性是一种非常弱的一致性保证，因为无法知道何时（when）系统会收敛。而在收敛之前，读请求都可能返回任何值。
可线性化（Linearizability）
可线性化（Lineariazability），也被称为原子一致性（atomic consistency）、强一致性（strong consistency），其基本的思想是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。有了这个保证，应用程序不需要再关系系统内部有多少个副本。
在一个可线性化的系统中，一旦客户端成功提交写请求，所有客户端的读请求一定能看到刚刚写入的值。这一保证让客户端认为只有一个副本，这样任何一次读取都能读到最新的值，而不是过期的数据。
下图来解释在一个非线性化的系统中，可能出现什么问题。
上图中，alice和bob同时等待2014年世界杯决赛的结果。在宣布最终比分之后，alice看到了最终的结果，然后将此结果告诉了bob，bob马上在自己的手机上刷新想看最新的结果，但是却返回了过期的数据，显示当前比赛还在进行中。
如何实现可线性化？
前面只是简单介绍了可线性化的思想：使系统看起来只有一个数据副本。为了更好的理解可线性化，看下面的图示例子。
在上图中，分为两种操作：针对某个值进行read和write操作。
客户端A的第一次和最后一次read操作，分别返回0和1，这没有问题，因为在这两次操作中间有客户端C的write操作将数据x更新为了1。
但是，在写操作还在进行的时候，如果读操作返回的值会来回的跳变，即某次读请求返回的是旧值，而某一次又返回的是新值，这对于一个可线性化系统而言是不可接受的。
为此，需要加入一个约束条件，如下图所示：
在上图中，箭头表示时序依赖关系。即先有客户端A的第二次read(x)操作，再有客户端B的第二次read(x)操作。客户端A的第二次读请求返回了x的新值1，而客户端B在这次读请求之后也去读x的值，此时应该返回的也是新值1。
即：在一个可线性化的系统中，有一个很重要的约束条件，在写操作开始和结束之间必然存在一个时间段，此时读到x的值会在旧值与新值之间跳变。但是，如果某个客户端的读请求返回了新值，那么即使这时写操作还未真正完成，后续的所有读请求也应该返回新值。
以下的例子进一步解释可线性化的操作，除了读写之外又引入另一种操作：
- cas(x, old, new)：表示一次原子的比较-设置操作（compare-and-set，简称CAS），如果此时x的值为old，则原子设置这个值为new；否则保留原有值不变，这个操作的返回值表示这次x原有的值是否为old，即设置操作是否发生。
上图中的每个操作都有一个竖线，表示可能的执行时间点。可线性化要求，连接这些标记的竖线，必须总是按时间（即从左到右）向前移动，而不能向后移动。因此，一旦新值被写入或读取，所有后续的值读到的都是新值，直到被覆盖。
在上图中，有一些细节需要注意：
- 客户端B首先read(x)，接下来客户端D write(x,0)，然后客户端A在write(x,1)，而最终返回给客户端B的值是1（客户端A写入的值）。这个结果是可能的，这意味着数据库执行的顺序是：先处理客户端D的写请求，然后是A的写入操作，最后才是B的读请求。虽然这个顺序并不是上面请求的顺序，但是考虑到请求有网络延迟的情况，比如可能B的请求延迟很大，导致在两次写请求之后才打到数据库，因此只能返回最后A写入的值。
- 客户端A在收到写请求的应答之前，B就收到了新的值1，这表明写入成功。这也是可能的，这并不意味着B的读请求在A的写请求之前发生，只是意味着由于网络延迟等原因导致A稍后才收到响应。
- 客户端的最后一次读取不满足线性化。因为在此之前，A已经读到了由C进行cas(x,2,4)操作设置的新值4，B的最后一次读请求在A读取到4之后，因此B不能读到旧值2了。
注意可线性化（Lineariazability）和可串行化（Serializability）的区别：
- 可串行化：可串行化是事务的隔离属性，其中每个事务可以读写多个对象。用来确保事务执行的结果与串行执行的结果完全相同，即使串行执行的顺序可能与事务实际执行顺序不同。
- 可线性化：可线性化是读写寄存器（单个对象）的最新值保证，并不要求将操作组合到事务中，因此无法避免写倾斜等问题。
数据库可以同时支持可串行化与可线性化，这种组合又被称为严格的可串行化或者强的单副本可串行化（strong one-copy Serializability）。
线性化的依赖条件
实现线性化系统
由于线性化本质上意味着“表现的好像只有一个数据副本，其上的操作都是原子操作”。最简单的方案就是只用一个数据副本，但是这样无法容错。
系统容错最常见的方法是采用复制机制，回顾一下之前的多种复制方案：
- 主从复制（部分支持可线性化）：主从复制系统中，只有主节点写入数据，而从节点保存副本数据。如果从主节点或者同步更新的从节点读取数据，则可以满足线性化。
- 共识算法（可线性化）。
- 多主复制（不可线性化）：用于同时在多个节点上执行写入操作，并将数据异步复制到其他节点，因此可能产生写入冲突。
- 无主复制（可能不可线性化）：对于无主节点复制的系统，依赖于具体的quorum配置，以及如何定义强一致性，可能并不能保证线性化。
线性化与quorum
上图中，x的初始值为0，写客户端向所有三副本（n=3，w=3）写入更新x为1。而客户端A从两个节点（r=2）读数据，其中一个节点返回1，而客户端B则从两个节点都得到了0。
显然这是违反线性化要求的：客户端B在客户端A之后读取数据，但是仍然得到了旧值。
总而言之，最安全的假定是类似Dynamo风格的无主复制系统无法保证线性化。
线性化的代价
CAP理论
在一个数据中心内部，主要存在不可靠的网络，就可能会违背线性化的风险，需要做出权衡考虑：
- 如果应用要求线性化，但是由于网络的原因，某些副本和其他副本断开连接之后无法继续处理请求，就必须等待网络恢复，或者直接返回错误。无论哪种方式，结果都是服务不可用。
- 如果应用不要求线性化，那么断开连接之后，每个副本可独立处理请求，此时服务可用但是行为不符合线性化。
因此，不要求线性化的应用更能容忍网络故障。这种思路称为“CAP定力”。
CAP定理，表示一致性、可用性、分区容错性，三者之间只能同时满足两个特性。不过，这种表示具有误导性，因为网络分区是一种故障，不管喜欢与否，都可能发生，而无法选择或者逃避这个问题。
网络在发生故障以后，必须从一致性和可用性之间做出选择。因此，更准确的应该是“网络分区情况下，选择一致还是可用”。
顺序保证
因果关系对所发生的事件施加了某种顺序：发送消息先于收到消息，问题出现在答案之前等。
如果系统满足因果关系所规定的顺序，称之为“因果一致性（causally consistent）”。
因果顺序并非全序
全序关系（total order）支持任何两个元素之间进行比较，即对于任意元素，总是可以指出哪个大哪个小。
但是有些集合并不符合全序关系，例如集合{a,b}大于集合{b,c}么？因为它们都不是对方的子集，所以无法直接进行比较。这种情况称之为不可比较（incomparable），数学集合只能是偏序关系（partially ordered）。
全序和偏序的差异也体现在数据库一致性问题中：
- 可线性化：在一个可线性化的系统中，存在全序操作关系。系统的行为好像就只有一个数据副本，且每个操作都是原子的，这意味着任何两个操作，都可以指出操作的先后顺序来。
- 因果关系：如果两个操作都没有发送在对方之前，那么两个操作是并发关系（concurrent）。即，如果两个事件是因果关系，那么这两个事件就可以被排序；而并发的事件则无法排序比较。因此因果关系是偏序，而非全序。
根据上面的定义，在可线性化的系统中不存在并发操作。一定有一个时间线将所有操作都全序执行，可能存在多个请求处于等待处理的状态，但是数据存储保证了在特定的时间点执行特定的操作，所以是单个时间轴、单个数据副本，没有并发。
并发意味着时间线会出现分支和合并，而不同分支上的操作无法直接比较，一定有一个时间线将所有操作都全序执行。
可线性化强于因果一致性
可线性化意味着一定满足因果关系，任何可线性化的系统一定能够正确满足因果关系。
在许多情况下，系统只要能够满足因果一致性就足够了，可线性化的代价太高。
序列号排序
可以使用序列号或时间戳来排序事件。时间戳不一定来自物理时钟，可以只是逻辑时钟。
特别地，还可以按照与因果关系一致的顺序来创建序列号：保证如果操作A发生在B之前，那么A的序列号一定比B更小。
在主从复制数据库中，复制日志中可以定义与因果关系一致的写全序关系，即由主节点为每个操作递增计数器，从而系统中的每个操作都赋值一个单调递增的序列号。
但是如果系统中不存在唯一的主节点，比如是多主或无主类型的数据库，可以采用以下的方式：
- 每个节点独立生成自己的一组序列号，比如两个节点一个节点生成奇数，另一个节点生成偶数。另外还可以在序列号中加入所属节点的唯一标识，确保不同的节点用于不会生成相同的序列号。
- 可以把时间戳信息（物理时钟）加到每个操作上。
- 可以预先分配序列号的区间范围。
Lamport时间戳
如下图所示，每个节点都有唯一的标识符，且每个节点都有一个计数器来记录自己处理的请求总数，Lamport时间戳是一个值对：（计数器，节点ID），这样就能确保每个Lamport时间戳都是唯一的。
给定两个Lamport时间戳，可以这样来对比得到全序关系：计数器大的时间戳大，如果计数器相同，那么节点ID大的时间戳更大。
Lamport时间戳与版本向量的区别在于：版本向量用于区分两个操作是并发的还是因果依赖的，而Lamport时间戳用于确保全序关系。即使Lamport时间戳不能用于区分两个操作属于并发关系，还是因果依赖关系。
但是，即便有了全序的时间戳排序，有一些问题仍然无法解决。
比如注册一个网站时，要求用户名需要唯一，虽然两个同样名字的创建用户请求过来，可以根据全序关系来决定究竟哪个请求在先抢占了这个用户名，但是这并不够，因为这个是在请求写入之后才进行的判断，在应答写请求时无法立刻知道结果，因为还需要查询所有节点，如果有节点失败的情况下还需要等待，等等。
为了解决类似的问题，就需要引入”全序关系广播“这个概念了。
全序关系广播（Total Oder Broadcast）
全序关系广播指节点间交换消息的某种协议，要求满足以下两个基本安全属性：
- 可靠发送：没有消息丢失，如果消息发送到了一个节点，也必须要发送到其他节点。
- 严格有序：消息总是以相同的顺序发送给每个节点。
即使节点或者网络发生故障，全序关系广播算法的正确实现也必须保证上述两条。在网络中断时发送失败的消息，在恢复之后要继续重试。
全序关系广播正是数据库复制所需要的：如果每条消息代表数据库写请求，并且每个副本都按照相同的顺序处理这些写请求，那么所有副本可以保持一致。该原则称为“状态机复制”，ZK和etcd这样的服务就实现了全序关系广播。
理解全序关系广播的另一种方式是将其视为日志（如复制日志），传递消息就像追加方式更新日志。由于所有节点必须以相同的顺序发送消息，因此所有节点都可以获取日志并看到相同的消息序列。
分布式事务与共识
两阶段提交（two-phase commit，简称2PC）
以上是简单的2PC的操作示意图，图中引入了一个协调者（Coordinator）的角色。当应用程序开始提交事务时，协调者开始阶段1：发送一个准备请求给事务中的参与者，询问是否可以提交。协调者然后跟踪参与者的回应：
- 如果所有参与者都应答”是“，表示它们已经准备好提交，协调者接下来在阶段2发出提交请求，提交才开始执行。
- 如果任何参与者回答了”否“，则协调者在阶段2中向所有节点发送放弃请求。
如果参与者在2PC期间失败，那么协调者将中断事务提交；如果在第二阶段发送提交时失败，协调者将无限期重试。
2PC的原理
以下详细分解2PC流程：
- 启动分布式事务时，首先向协调者请求事务ID，该ID全局唯一。
- 在每个参与节点上执行单节点事务，并将全局唯一事务ID附加到事务上。此时，读写都是在单节点内完成的，如果这个阶段出现问题，如节点崩溃或者请求超时，则协调者和其他参与者都可以安全中止。
- 当准备提交事务时，协调者向所有参与者发送准备请求，并附带全局事务ID，如果准备请求有任何一个发生问题，协调者可以通知参与者放弃事务。
- 参与者在收到准备请求之后，确保在任何情况下都可以提交事务，包括安全地将事务数据写入磁盘。一旦协调者回答“是”，节点就提交事务。
- 当协调者收到所有准备请求的答复时，就是否提交（或放弃） 事务做出明确的决定（即只有所有参与者都投赞成票时才会提交）。协调者将最后的决定写入磁盘，这个时刻称为“提交点（commit point）”。
- 协调者决定写入磁盘之后，向所有参与者发送提交请求。如果请求失败，就需要一直重试。此时，所有节点不允许有任何反悔。一旦做出了决定，就必须执行，即使需要重试。
由此可见，该协议两个关键的“不归路”：首先，当参与者投票“是”时，做了肯定提交的承诺；其次，协调者做了提交的决定之后，这个决定也是不可撤销的。
正是以上两点保证了2PC的原子性，而单节点事务提交实际上将两个事件合二为一，写入事务日志即提交。
协调者发生故障
但是，如果是协调者自身发生了故障，后面的行为无法预计，如下图所示。
2PC能够顺利完成的唯一方法是等待协调者恢复，这就是为什么协调者必须在向参与者发送提交请求之前需要先写入磁盘事务的日志：这是因为一旦协调者崩溃，恢复之后可以根据读取事务日志来确定所有未决的事务。
支持容错的共识算法
所有支持容错的共识算法都有以下的性质：
- 协商一致性（Uniform agreement）：所有的节点都接受相同的决议。
- 诚实性（Integrity）：所有节点都不能反悔，即对一项决议不能有两次不同的结果。
- 合法性（Validity）：如果决定了v值，则v一定是某个节点所提议的。即：不能有一个凭空的决议产生。
- 可终止性（Termination）：节点如果不崩溃则最终一定可以达成协议。
协商一致性和诚实性属性定义了共识算法的核心思想：决定一致的结果，而一旦决定就不能再变更决定。 有效性属性排除了无意义的方案。
如果不考虑容错性，以上三点很容易实现：强行指定某个节点为”独裁者“，由它做出所有的决定。但是，如果该节点失败，系统就无法再继续做出任何决定。这就是在2PC时看到的：如果协调者失败了，那些处于不确定状态的参与者无从知道应该怎么做。
可终止性引入了容错的思想。它强调一个共识算法不能原地空转，永远不做事情。即使某些节点出现了故障，其它节点也必须最终做出决定。
因此，可终止性属于一种活性属性（liveness property），而其它三个性质属于安全性方面的属性。
任何共识性算法，都需要至少大部分节点正确运行才能保证终止性，这个”大多数节点“又被称为”quorum“。
因此，可终止性的前提是，发生崩溃或者不可用的节点必须小于小半数节点。另外，共识算法也界定系统不存在拜占庭错误。
共识算法与全序广播
共识算法一般都是：决定了一系列值，然后采用全序关系广播算法传播数据。
全序广播的要点是：消息按照相同的顺序发送到所有节点，有且只有一次。
所以，全序广播算法相当于持续的多轮共识：
- 由于协商一致性，所有节点决定以相同顺序发送相同的消息。
- 由于诚实性：消息不能重复。
- 由于合法性，消息不能被破坏和捏造。
- 由于可终止性，消息不能丢失。
主从复制与共识
主从复制，也是所有写入操作由主节点负责，并以相同顺序发送到从节点来保持副本数据更新，为什么那时候没有考虑共识问题？
如果主节点由人手动选择和配置，那就是一个独裁性质的一致性算法，出现故障的时候需要人工干预。
然而，共识算法由需要首先选择出一个主节点来，否则会出现脑裂问题。如何选举主节点呢？
epoch和quorum
共识算法中，每个协议会定义一个世代编号（epoch number），这个编号是递增唯一的，对应于paxos中的ballot number、vsp中的view number、raft中的term number。
当主节点失效时，马上进行一轮新的投票来选举出新的主节点。选举会赋予一个单调递增的epoch号，如果出现不同的主节点，那么就看谁的epoch号更大的胜出。
在主节点做出任何决定之前，必须首先检查是否存在比它更高的epoch号，如何检查呢？基于前面做分布式系统的一个准则”真理由多数决定“，节点不能依靠自己掌握的信息来决策，而应该从quorum节点中收集投票。节点只有当没有发现更高epoch的主节点存在的情况下，才会对当前的提议进行投票。
因此实际上这里是两轮不同的投票：首先投票决定谁是主节点，然后是对主节点的提议进行投票。
投票过程看起来像2PC，区别在于：2PC的协调者不是依靠选举产生；另外共识算法只需要收到quorum节点的应答就可以通过决议，而2PC需要所有参与者都通过才能通过决议。