线性一致性
线性一致性（linearizability），也叫做原子一致性（atomic consistency）、强一致性（strong consistency）、立即一致性（immediate consistency）或外部一致性（external consistency ）
在线性一致性系统中，只要一个客户端完成写入，其他的客户端能够立即看到这个写入，系统能够保证读取到最新的值。
线性一致性的场景
master选举
在主从复制的数据库中，需要确保master只有一个，避免出现脑裂。一种方法就是通过锁：一个节点尝试获取锁，成功就成为了master。这个锁必须是线性一致的，所有节点都要就锁的所有者达成一致。比如ZooKeeper和etcd这类的协调服务，就会使用一致性算法，以容错的方式实现线性一致性的操作，从而用于分布式锁和master选举。
约束和唯一性保证
数据库中的唯一性约束，比如用户名不能重复，文件名不能重复等。此外，还有一些其他的约束，比如账户余额不能为负，商品不能超卖等，这些约束都要求所有节点同意一个最新的值，需要线性一致性的保证。
跨信道的时序依赖
上图中，系统要正常工作，需要线性一致性。但是如果不是，则会存在问题，第5步可能先于第2步完成，导致获取的是旧的图片，从而造成不一致。
实现线性一致性
- 主从复制 —— 如果只从主库或者同步更新的从库读取，那么是线性一致的。但其他场景则不一定满足，比如即使读发生于写之后，由于快照隔离，读的值仍然是旧的。再比如异步复制的场景，有可能会丢失写，同样也不满足线性一致。
- 共识算法 —— 线性一致的
- 多主复制 —— 不符合线性一致，因为要处理多个节点上的写入冲突，还需要异步复制到其他节点上。
- 无主复制 —— 不一定符合线性一致，比如下图所示，B在A之后发生，A读到了新值，B读到的却是旧值，违反了线性一致性的定义。
线性一致性的代价
许多分布式数据库为了性能的考虑，而选择牺牲了线性一致性。下文摘自作者的另一篇博客
CAP定义的狭隘
首先，CAP的定义都是一些特殊的场景：
- 一致性 (Consistency) 其实是线性一致性
- 可用性 (Availability) 定义为 “系统中的非故障节点针对收到的每个请求必须做出[非错误]响应”。所以只有单个节点能够处理请求是不够的，需要所有非故障节点都能工作。
- 分区容错性 (Partition Tolerance)，其实肯定会发生，是没有任何选择的。
此外，CAP定理描述的系统也是非常特定的系统：
- CAP没有描述涉及多个对象的事务。
- CAP考虑的故障场景仅有网络分区（network partition），但是现实中还有其他的故障，比如节点故障、重启等。在构建分布式系统时，需要考虑更多的因素。
- CAP完全没有提及延迟。
CAP-Availability
出现上图的情况，只能有两种处理方式：
- 继续允许写入，两个数据中心都是可用的。只不过由于网络中断，一个中心的写入无法复制到另一个中心，违反了线性一致性。
- 选举一个leader，处理所有的读写操作，而另外一个中心在网络恢复之前无法进行读写，从而违反了CAP的可用性。
但是第2中的处理方式，虽然理论上它不是CAP-available，但是leader仍然在处理所有的读写，客户端感受不到任何的停机时间。在实践中，可用性并不完全和CAP-available一致。可用性是通过SLA来衡量的，和系统是否CAP-available完全无关。
CP或AP：错误的权衡
- 根据CAP定理的描述，很多系统既不是CP，也不是AP，但并不妨碍这个系统有合理的设计。
- 简单的分类成两种，将会丢失很多细节。例如, 尽管 ZooKeeper 有一个”AP”只读模式, 但该模式仍然提供有序的历史写入记录，比Cassandra的”AP”提供更可靠的保障。
- CAP不应该是一个严格的数据系统分类方案
不同水平的一致性
| 一致性水平 | 描述 | 一致性 | 性能 | 可用性 |
|---|---|---|---|---|
| Strong Consistency | See all previous writes. | excellent | poor | poor |
| Eventual Consistency | See subset of previous writes. | poor | excellent | excellent |
| Consistent Prefix | See initial sequence of writes. 类似于snapshot isolation | okay | good | excellent |
| Bounded Staleness | See all “old” writes. 要求延迟不超过指定范围 | good | okay | poor |
| Monotonic Reads | See increasing subset of writes. 读取的数据总是更新 | okay | good | good |
| Read My Writes | See all writes performed by reader. | okay | okay | okay |
顺序保证
顺序与因果
因果关系在事件上加了顺序，因要在果之前，消息发送在消息接受之前。如果一个系统符合因果关系定下的顺序，那就可以说它是因果一致（casually）的。
因果关系不是全序（total order）
- 线性一致性系统中，操作是全序的，任何两个操作都可以定义先后关系。
- 在因果关系系统中，如果两个操作有因果关系，则它们是有序的。如果没有因果关系，则两者可以并发执行，无法比较顺序的
线性一致性强于因果一致性
线性一致性隐含着因果一致性，也就是说线性一致性系统肯定能够保持因果性，但是代价就是性能及可用性的损失。
在很多情况下，系统表面上是需要线性一致性，实际上因果一致性就可以满足需求，而且因果一致性可以更高效地实现。为了实现因果一致性，需要捕获到这种happened before关系。
序列号顺序
非因果序列号生成器
如果是主从复制的数据库，那么主库为每个操作添加自增序列号，这样从库从复制日中可以根据自增序号来顺序应用写操作，从而和主库保持一致。
但是如果没有主库，那么序号生成就比较麻烦了，实际中会这么做：
- 每个节点生成自己的序列号，比如一个节点生成奇数，一个节点生成偶数，或者序列号中有几个bit位来表示节点编号。
- 为每个操作带上物理时钟的时间戳。
- 每个节点分配不同的序号区间，从而让序列号错开。
但是上述几种方法生成的序号，无法表达因果关系。此外，物理时钟也不可靠，会有时钟漂移。
兰伯特时间戳
兰伯特时间戳，就是(counter, nodeId)的组合。每个节点都有自己的计数器，虽然两个节点会有相同的计数，但是加上节点ID后就保证了全局唯一。虽然它和物理时钟没有关系，但是提供了全序。
它的核心思想，就是客户端和节点都会维护着当前持有的最大计数，并在每个请求中包含这个计数。节点在收到请求的时候，如果请求中的计数大于自己的计数，则更新自己的计数为较大的值。
有序时间戳还不够
兰伯特时间戳有序的前提，是需要收集到其他节点的信息，才能产生全局有序的序号。但是在一些场景中，需要立即决定操作是否成功。比如判定一个用户名是否可以使用，其他节点有可能在做同样的操作，其他节点的操作在全局排序中处于什么样的位置，这个知识是未知的。
全序广播
全序广播（total order broadcast）用于在节点之间交换信息，需要满足
- 可靠性（reliable delivery）—— 不会有消息丢失，所有节点都会收到消息
- 有序性（totally ordered delivery）—— 所有节点收到的消息顺序相同
全序广播的应用
- 数据库复制 —— 每个消息都代表数据库的一次写入，且每个副本都按照相同的顺序处理写入，那么副本之间就会保持一致，被称为状态机复制（state machine replication）。
- 可串行化事务 —— 每个消息代表一个确定性的事务，且每个节点以相同的顺序处理这些事务，那么数据库的副本之间就可以保持一致。
- 提供令牌的锁服务 —— 每个获取锁的请求，作为消息加到日志的尾端，且所有的消息都是按照在日志中出现的顺序依次编号，这个序列号是单调递增的。比如zk中的zxid。
使用全序广播实现线性一致的存储
有了全序广播，可以在此基础上构建线性一致的存储，比如创建一个可用的用户名。这个存储对于用户来说，可以执行CAS操作。这种场景下，多个用户执行cas(null, ‘new user’)，只有一个用户会返回成功，由于线性一致，其他用户会返回这个新的值。
可以通过append-only日志来实现这个cas的操作，具体步骤如下：
- 在日志中追加一条记录，尝试获取这个新的用户名
- 读日志，并等待附加的消息回传
- 检查消息中新用户名处理的结果，如果消息中的第一条就是自己的消息，那么证明获取成功，向客户端返回成功。如果第一条消息来自其他客户，则中止操作。
尽管这一过程的写入是线性一致的，由于消息是异步的，读取不一定的线性一致的。为了让读取也做到线性一致，可以尝试：
- 可以在日志中追加一条消息，当处理该消息时，才执行实际的读取操作。
- 如果日志可以线性一致地查询最新日志位置，然后等待这个消息之前所有消息都达到之后，才执行实际的读取。（ZooKeeper的sync操作）
- 从同步更新的副本中读取数据，保证是最新的。
使用线性一致的存储实现全序广播
通过线性一致存储实现全序广播，算法其实很简单。每个要通过全序广播发送的消息首先对线性一致存储执行自增并返回操作。然后将获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点（重新发送任何丢失的消息），而收到消息的节点将按序列号连续发送消息。
实现带有自增并返回操作的线性一致的存储，可以简单将值放在单节点的变量里。但是当这个节点失效时，能够恢复出这个值。这就需要考虑共识（consensus）了。
分布式事务与共识
共识就是让一些节点就某个事情达成一致，在很多场景中都非常重要，比如：
- leader选举 —— 如果无法达成一致，容易产生脑裂，从而导致不一致或数据丢失。
- 原子提交 —— 如果是跨多节点事务，所有节点需要就事务提交或回滚达成一致。
原子提交及两阶段提交（2PC）
多节点的原子提交
对于在单节点执行的事务，原子性主要由存储引擎来实现。提交事务的时候，先写入数据到WAL日志中，再写入提交记录。只要提交记录成功写入磁盘，则事务提交成功。否则，事务的写入都会被回滚。
但是涉及到多节点的事务，按照单节点的提交策略是不够的，很容易造成某些节点成功，某些节点失败，从而造成数据的不一致。
两阶段提交
2PC中的协调者（也被称为事务管理器transaction manager），通常以库或者独立服务的形式存在。数据库节点被称为参与者（也被称为resource manager）。详细的过程如下：
- 启动一个分布式事务，需要向协调者申请一个全局唯一的事务ID
- 在每个参与者上启动单节点事务，并附带上事务ID。所有的读写都是发生在单节点的事务中，如果这个阶段发生问题，则协调者和参与者都可以中止事务。
- 当应用准备提交时，协调者向所有参与者发送prepare请求，并附带上事务ID。如果任意一个请求超时或者失败，则协调者向所有参与者发送abort请求。
- 参与者收到prepare请求后，需要保证在任何情况下都可以提交事务。所以在这个阶段，需要提前检查这个事务是否违反约束、是否有冲突等。只要回复了“是“，就相当于放弃了中止事务的权利。
- 当协调者收到所有参与者的请求后，就会做出事务提交或中止的决定，会将这个决定写入到日志中。后续即使协调者崩溃，也会从日志中恢复出自己的决定，这被称为commit point。
- 一旦这个决定写入到日志中，协调者就会将请求发送给所有参与者。请求失败或超时，会一直重试直到成功。如果参与者在这个期间崩溃，那么恢复后会继续事务的提交。因为之前回复了OK，所有需要保证事务能够提交成功。
但是，第6步的时候，如果协调者崩溃，参与者接受不到协调者的命令，那么就无法决定是提交还是回滚，只能等待协调者恢复。
三阶段提交
两阶段提交，又被称为阻塞（blocking）原子提交，因此存在上文中提到的等待协调者恢复的问题。理论上，可以将原子提交变成非阻塞，以便在节点失败时不会卡住。
三阶段提交（3PC）引入了超时机制，且协调者和参与者都有超时机制（2PC中，只有协调者设置了超时机制）。但3PC假定网络延迟有限，节点响应的时间有限。但在实际应用中，通过延迟判定节点故障不是十分可靠，且3PC同样无法避免节点之间的不一致，所以2PC仍然在被广泛使用。
实践中的分布式事务
分布式事务的局限
- 在事务提交或者中止前，数据库会持有一些行上的锁，且不能释放。如果协调者崩溃，在恢复之前，这些锁也无法释放，导致其他事务不能修改这些行。
- 当协调者恢复的时候，应当从日志中恢复其状态，并解决这些存疑的事务。但在实践中，这些存疑事务无法决定是提交还是回滚，只能由管理员来决定如何处理。
- 协调者的单点风险
- 许多应用都是无状态部署的，但是由于协调者的存在，它的日志成为持久系统状态的一个关键部分，这样应用部署不再是无状态的了。
- 分布式事务中，有任意节点失败都会导致整个事务失败，因此有失败放大的趋势，违背了我们构建容错系统的目标。
协调服务
ZooKeeper不仅实现了全序广播，还实现了一些其他的特性，这些特性在构建分布式系统时非常有用
- 线性一致性的原子操作 —— 通过CAS可以实现锁，多个节点尝试相同的操作，只有一个节点可以成功。这个分布式锁通常以租约（lease）的形式实现，并有一个到期时间。
- 操作的全序排序 —— 当某个资源受到锁的保护时，需要有一个令牌，防止在进程暂停的情况下多个客户端互相冲突。zk通过全序排序来实现这个令牌，为每个操作生成一个单调递增的事务ID（zxid）和版本号（cversion）。
- 失效检测 —— 客户端在zk上维护一个长期会话，客户端和zk周期性地交换心跳，从而检查节点是否存活。如果心跳停止的时间超过会话超时，则zk会宣告这个会话结束，其持有的锁都会被释放。
- 变更通知 —— 客户端不仅可以读取其他客户端创建的锁和值，还可以监听其他节点的变更，比如其他节点加入集群，或者发生故障被踢出集群。
给节点分配工作
比如分布式数据库，需要选择一个节点作为主库。主库失效的时候，需要选出一个节点作为新的主库。对作业调度或者其他有状态的系统同样有用。
再比如，有一些分区资源需要分配到节点上。当新的节点加入集群时，需要转移一些分区到这个新节点上。当一个节点失效时，其他节点需要接管这些资源。
应用发展到后面可能会有几千个节点，在这些多节点上进行投票是非常低效的。但是zk只需要很少数量的节点，就可以高效地投票，并同时支持非常多的客户端。因此可以说，zk提供了协调服务（共识、操作排序、故障检测等）的外包工作。
通常，zk的管理的状态改变非常缓慢，它不适合管理应用运行时的变化很多的状态。如果应用状态需要从一个节点复制到另一个节点，可以通过Apache BookKeeper。
服务发现
zk、etcd等还被用于服务发现，客户端可以找到提供特定服务的IP列表。
成员服务
zk可以用于确定一个集群中，哪些成员是存活的。比如选择leader的时候，需要选择编号最小的节点，这就需要知道集群中有哪些节点。虽然通过超时来判定一个节点是否存活，会存在一些错误的判断。但是只要就这个判断达成一致，就不会存在问题。