DDIA(九)

一致性保证

大多数复制的数据库至少提供了最终一致性，这意味着如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值。换句话说，不一致性是暂时的，最终会自行解决（假设网络中的任何故障最终都会被修复）。最终一致性的一个更好的名字可能是收敛（convergence），因为我们预计所有的副本最终会收敛到相同的值。最终一致性是非常弱的保证——没有说什么时候会收敛。

线性一致性

在最终一致的数据库，如果你在同一时刻问两个不同副本相同的问题，可能会得到两个不同的答案。这很让人困惑。如果数据库可以提供只有一个副本的假象（即，只有一个数据副本），那么事情就简单太多了。那么每个客户端都会有相同的数据视图，且不必担心复制滞后了 这就是线性一致性（linearizability）背后的想法（也称为原子一致性（atomic consistency），强一致性（strong consistency），立即一致性（immediate consistency）或外部一致性（external consistency ））

这个系统是非线性一致的，导致了球迷的困惑

展示了一个关于体育网站的非线性一致例子。Alice和Bob正坐在同一个房间里，都盯着各自的手机，关注着2014年FIFA世界杯决赛的结果。在最后得分公布后，Alice刷新页面，看到宣布了获胜者，并兴奋地告诉Bob。Bob难以置信地刷新了自己的手机，但他的请求路由到了一个落后的数据库副本上，手机显示比赛仍在进行。

如何使得系统线性一致？

客户端 C 修改了 x 的值，客户端 A 和 B 在与写操作时间上有重叠的任何读操作，看到的 x 的值可能不一致。

如果读取请求与写入请求并发，则可能会返回旧值或新值

在变量 x 从 0 变成 1 的时候，一定有一个确切的时间点。如果一个客户端读取返回的新值是 1，即使写操作尚未完成，所有后续读取也必须返回新值。

任何一个读取返回新值后，所有后续读取（在相同或其他客户端上）也必须返回新值。

除了读写之外，还增加了第三种类型的操作：

表示客户端请求进行原子性的[比较与设置]操作。如果寄存器 的当前值等于 ，则应该原子地设置为 。如果 ，则操作应该保持寄存器不变并返回一个错误。 是数据库的响应（正确或错误）。

可视化读取和写入看起来已经生效的时间点。 B的最后读取不是线性一致性的

● 每个条形图中间的黑线，表示读取和修改变量 x 的确切时刻。
● 客户端 B 的最后一次读取不是线性一致的。该操作与C的cas写操作并发（它将 x 从 2 更新为 4 ）。在没有其他请求的情况下，B的读取返回 2 是可以的。然而，在B的读取开始之前，客户端A已经读取了新的值 4 ，因此不允许B读取比A更旧的值。

依赖线性一致性

锁定和领导选举

约束和唯一性保证

跨信道的时序依赖

上传图片后要进行图片压缩，分成了两个服务：文件存储图片、通过消息队列传递压缩指令。
如果消息队列运行的更快，那么就找不到图片或者压缩了老的图片。

实现线性一致的系统

线性一致性和法定人数

可以让上述法定人数的读写线性化吗？
● 通过牺牲性能，可以：
○ 读取者必须在将结果返回给应用之前，同步执行读修复
○ 并且写入者必须在发送写入之前，读取法定数量节点的最新状态
● 实际上数据库系统都没有做
● 而且，这种方式只能实现线性一致的读写；不能实现线性一致的「比较和设置」（CAS）操作，因为它需要一个共识算法(为什么需要共识算法)。

线性一致性的代价

网络中断迫使在线性一致性和可用性之间做出选择

但是如果两个数据中心之间发生网络中断会发生什么？

1. 使用多主数据库：
   ○ 每个数据中心都可以继续正常运行：由于在一个数据中心写入的数据是异步复制到另一个数据中心的，所以只有恢复网络连接后，写操作才会继续同步。
2. 使用单主复制：
   ○ 则主库必须位于其中一个数据中心。
   ○ 任何写入和任何线性一致的读取请求都必须发送给该主库，因此对于连接到从库所在数据中心的客户端，这些读取和写入请求必须通过网络同步发送到主库所在的数据中心。
   ○ 只能连接到从库所在的数据中心的客户端，当数据中心之间的网络被中断时：
   ■ 客户端无法对数据库执行任何写入，也不能执行任何线性一致的读取。它们仍能从从库读取，但结果可能是陈旧的（非线性一致）。
   ■ 如果应用需要线性一致的读写，却又位于与主库网络中断的数据中心，则网络中断将导致这些应用不可用。
   ○ 可以直接连接到主库所在的数据中心的客户端：
   ■ 可以继续正常工作。

CAP定理

1. 如果应用需要线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求。请求必须等到网络问题解决，或直接返回错误。（无论哪种方式，服务都不可用（unavailable））。
2. 如果应用不需要线性一致性，那么某个副本即使与其他副本断开连接，也可以独立处理请求（例如多主复制）。在这种情况下，应用可以在网络问题前保持可用，但其行为不是线性一致的。

CAP更好的表述成：在分区时要么选择一致，要么选择可用。

线性一致性和网络延迟

● 它们是为了提高性能而选择了牺牲线性一致性，而不是为了容错。
● 线性一致的速度很慢——这始终是事实，而不仅仅是网络故障期间。
● 更快地线性一致算法不存在，但更弱的一致性模型可以快得多，所以对延迟敏感的系统而言，这类权衡非常重要。

顺序保证

顺序与因果

什么是因果一致？

● 因果关系对事件施加了一种顺序：因在果之前；消息发送在消息收取之前。
● 这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。
● 如果一个系统服从因果关系所规定的顺序，我们说它是因果一致（causally consistent） 的。

因果顺序不是全序的

● 全序（total order） 允许任意两个元素进行比较，所以如果有两个元素，你总是可以说出哪个更大，哪个更小。
● 数学集合 {a, b} 比 {b, c} 更大吗？你没法真正比较它们，因为二者都不是对方的子集。我们说它们是无法比较（incomparable） 的，因此数学集合是偏序（partially order） 的：在某些情况下，可以说一个集合大于另一个（如果一个集合包含另一个集合的所有元素），但在其他情况下它们是无法比较的。

全序和偏序之间的差异反映在不同的数据库一致性模型中：
线性一致性
● 操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。
因果性
● 着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的（先后），但有些则是无法比较的（并发）。

线性一致性强于因果一致性

因果顺序和线性一致性之间的关系是什么？
● 线性一致性隐含着（implies） 因果关系：任何线性一致的系统都能正确保持因果性。

捕获因果关系

因果一致性则更进一步：它需要跟踪整个数据库中的因果依赖，而不仅仅是一个键。可以推广版本向量以解决此类问题。

序列号顺序

有更好的办法排序事件吗？
● 更好的办法：我们可以使用序列号（sequence nunber） 或时间戳（timestamp） 来排序事件。
● 时间戳不一定来自日历时钟（或物理时钟，它们存在许多问题，如 “不可靠的时钟” 中所述）。它可以来自一个逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

怎么生成序列号？
● 这样的序列号或时间戳是紧凑的（只有几个字节大小），它提供了一个全序关系：也就是说每个操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大（即哪些操作后发生）。
● 特别是，我们可以使用与因果一致（consistent with causality） 的全序来生成序列号：我们保证，如果操作 A 因果地发生在操作 B 前，那么在这个全序中 A 在 B 前（ A 具有比 B 更小的序列号）。并行操作之间可以任意排序。这样一个全序关系捕获了所有关于因果的信息，但也施加了一个比因果性要求更为严格的顺序。
● 在单主复制的数据库中（请参阅“领导者与追随者”），复制日志定义了与因果一致的写操作。主库可以简单地为每个操作自增一个计数器，从而为复制日志中的每个操作分配一个单调递增的序列号。如果一个从库按照它们在复制日志中出现的顺序来应用写操作，那么从库的状态始终是因果一致的（即使它落后于领导者）。

非因果序列号生成器

如果主库不存在（可能因为使用了多主数据库或无主数据库，或者因为使用了分区的数据库）怎么生成序列号？

兰伯特时间戳

● 每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。
● 兰伯特时间戳就是两者的简单组合：（计数器，节点ID）。
● 两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点ID，每个时间戳都是唯一的。

Lamport时间戳提供了与因果关系一致的总排序

如上图，客户端 A 从节点2 接收计数器值 5 ，然后将最大值 5 发送到节点1 。此时，节点1 的计数器仅为 1 ，但是它立即前移至 5 ，所以下一个操作的计数器的值为 6

光有时间戳排序还不够

兰伯特时间戳的问题：
● 虽然它定义了一个与因果一致的全序，但它还不足以解决分布式系统中的许多常见问题。
● 例如，考虑一个需要确保用户名能唯一标识用户帐户的系统。如果两个用户同时尝试使用相同的用户名创建帐户，则其中一个应该成功，另一个应该失败。

实际上，上面是一种事后确定胜利者：一旦你收集了系统中的所有用户名创建操作，就可以比较它们的时间戳。

全序广播

全序广播通常被描述为在节点间交换消息的协议。 非正式地讲，它要满足两个安全属性：
可靠交付（reliable delivery）
没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。
全序交付（totally ordered delivery）
消息以相同的顺序传递给每个节点。
当网络出现故障的时候，算法需要不断重试，以便网络恢复的时候，消息能及时通知并送达（按照正确顺序）

使用全序广播

使用全序广播实现线性一致的存储

使用线性一致性存储实现全序广播

分布式事务与共识

原子提交与二阶段提交（2PC）

从单节点到分布式原子提交

单节点中为什么能做到原子提交？
● 在单个节点上，事务的提交主要取决于数据持久化落盘的顺序：首先是数据，然后是提交记录。
● 事务提交或终止的关键决定时刻是磁盘完成写入提交记录的时刻：在此之前，仍有可能中止（由于崩溃），但在此之后，事务已经提交（即使数据库崩溃）。
● 因此，是单一的设备（连接到单个磁盘的控制器，且挂载在单台机器上）使得提交具有原子性。

如果一个事务中涉及多个节点呢？

事务提交可以撤销吗？为什么???

● 事务提交必须是不可撤销的 —— 事务提交之后，你不能改变主意，并追溯性地中止事务。
● 这个规则的原因是，一旦数据被提交，其结果就对其他事务可见，因此其他客户端可能会开始依赖这些数据。
● 这个原则构成了读已提交隔离等级的基础，在“读已提交”一节中讨论了这个问题。
● 如果一个事务在提交后被允许中止，所有那些读取了已提交却又被追溯声明不存在数据的事务也必须回滚。
● 如果想进行修改的话，必须新建一个事务。

两阶段提交简介

两阶段提交（2PC）的成功执行

2PC使用一个通常不会出现在单节点事务中的新组件：协调者（coordinator）（也称为事务管理器（transaction manager）） 当应用准备提交时，协调者开始阶段 1 ：它发送一个准备（prepare） 请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：如果所有参与者都回答“是”，表示它们已经准备好提交，那么协调者在阶段 2 发出提交（commit） 请求，然后提交真正发生。如果任意一个参与者回复了“否”，则协调者在阶段2 中向所有节点发送中止（abort） 请求。

系统承诺

1. 当应用想要启动一个分布式事务时，它向协调者请求一个事务ID。此事务ID是全局唯一的。
2. 应用在每个参与者上启动单节点事务，并在单节点事务上捎带上这个全局事务ID。所有的读写都是在这些单节点事务中各自完成的。如果在这个阶段出现任何问题（例如，节点崩溃或请求超时），则协调者或任何参与者都可以中止。
3. 当应用准备提交时，协调者向所有参与者发送一个准备请求，并打上全局事务ID的标记。如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务ID的中止请求。
4. 参与者收到准备请求时，需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写入磁盘（出现故障，电源故障，或硬盘空间不足都不能是稍后拒绝提交的理由）以及检查是否存在任何冲突或违反约束。通过向协调者回答“是”，节点承诺，只要请求，这个事务一定可以不出差错地提交。换句话说，参与者放弃了中止事务的权利，但没有实际提交。
5. 当协调者收到所有准备请求的答复时，会就提交或中止事务作出明确的决定（只有在所有参与者投赞成票的情况下才会提交）。协调者必须把这个决定写到磁盘上的事务日志中，如果它随后就崩溃，恢复后也能知道自己所做的决定。这被称为提交点（commit point）。
6. 一旦协调者的决定落盘，提交或放弃请求会发送给所有参与者。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。没有回头路：如果已经做出决定，不管需要多少次重试它都必须被执行。如果参与者在此期间崩溃，事务将在其恢复后提交——由于参与者投了赞成，因此恢复后它不能拒绝提交。

协调者失效

如果协调者崩溃，会发生什么？
● 如果协调者在发送准备请求之前失败，参与者可以安全地中止事务。
● 但是，一旦参与者收到了准备请求并投了“是”，就不能再单方面放弃 —— 必须等待协调者回答事务是否已经提交或中止。如果此时协调者崩溃或网络出现故障，参与者什么也做不了只能等待。参与者的这种事务状态称为存疑（in doubt） 的或不确定（uncertain） 的。
● 可以完成2PC的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志：协调者恢复后，通过读取其事务日志来确定所有存疑事务的状态。

三阶段提交

三阶段提交是什么，为什么大家还在用两阶段提交？
● 两阶段提交被称为阻塞（blocking）- 原子提交协议，因为存在2PC可能卡住并等待协调者恢复的情况。
● 理论上，可以使一个原子提交协议变为非阻塞（nonblocking） 的，但是比较麻烦。作为2PC的替代方案，已经提出了一种称为三阶段提交（3PC） 的算法，但它并不能保证原子性

实践中的分布式事务

恰好一次的消息处理:消息队列中的一条消息可以被确认为已处理，当且仅当用于处理消息的数据库事务成功提交

容错共识