DDIA第二部分读后感（下）

一 事务

​ 由于大多数事情（系统宕机，网络中断等）都会导致整个系统故障，由此会产生许多不可挽回的错误。所以出现了事务，这是将多个读写操作组合成一个逻辑单元的一种方式。它将所有读写操作被视作单个操作来执行：整个事务要么成功 提交（commit），要么失败 中止（abort）或 回滚（rollback）。

​ 接下来主要讲隔离级别

1.1 概念

1.1.1 ACID

​ 老生常谈的话题了，ACID 代表 原子性（Atomicity），一致性（Consistency），隔离性（Isolation） 和 持久性（Durability）。有意思的是，书中说ACID 现在几乎已经变成了一个营销术语，因为这存在许多标准，很多系统并不知道能保证哪些。

原子性

​ 书中的解释大概是：多个操作被分组到一个原子事务中，并且该事务由于错误而不能完成（提交），则该事务将被中止，并且数据库必须丢弃或撤消该事务中迄今为止所做的任何写入。定义特性是：能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。

​ 我个人理解的定义是：事务包含多个操作，这些操作要么全部执行，要么全都不执行。（老八股了🤣）

一致性

​ 指的是：对数据的一组特定约束必须始终成立（也就是不会出现中间状态）。例如，在会计系统中，所有账户整体上必须借贷相抵。

​ 这里说，一致性的这种概念取决于应用程序对不变式的理解，应用程序负责正确定义它的事务，并保持一致性。这并不是数据库可以保证的事情：如果你写入违反不变式的脏数据，数据库也无法阻止你。这里指出的是一致性（在 ACID 意义上）是应用程序的属性。

隔离性

​ 也就是同时执行的事务是相互隔离的。

持久性

​ 持久性 是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

​ 在单节点数据库中，持久性通常意味着数据已被写入非易失性存储设备，如硬盘或 SSD，也可能是日志等。在带复制的数据库中，持久性可能意味着数据已成功复制到一些节点。

1.2 单对象和多对象操作

单对象写入

​ 对单节点上的单个对象（例如键值对）上提供原子性和隔离性。原子性可以通过使用日志来实现崩溃恢复，并且可以使用每个对象上的锁来实现隔离。单对象操作很有用，因为它们可以防止在多个客户端尝试同时写入同一个对象时丢失更新。

多对象事务需求

​ 这就复杂的多，先说一些场景：

• 关系型模型中，一个表中的行通常具有对另一个表中的行的外键引用。插入一个相互引用的记录，就需要保证都是最新的。
• 文档数据模型中，需要一次更新多个文档。事务在这种情况下非常有用，可以防止非规范化的数据不同步。
• 具有次级索引时，需要更新多个索引。

​ 文章解释可以在没有事务的情况下实现。但，没有原子性，错误处理就要复杂得多，缺乏隔离性，就会导致并发问题。后面会说说其他方法

处理错误和中止

​ ACID 数据库基于这样的哲学：如果数据库有违反其原子性，隔离性或持久性的危险，则宁愿完全放弃事务，而不是留下半成品。

​ 这里提出了处理重试中止事务的方法：

• d如果事务实际上成功了，但是在服务器试图向客户端确认提交成功时网络发生故障（所以客户端认为提交失败了），那么重试事务会导致事务被执行两次
• 如果错误是由于负载过大造成的，则重试事务将使问题变得更糟，而不是更好。为了避免这种正反馈循环，可以限制重试次数，使用指数退避算法，并单独处理与过载相关的错误（如果允许）。
• 仅在临时性错误（例如，由于死锁，异常情况，临时性网络中断和故障切换）后才值得重试。在发生永久性错误（例如，违反约束）之后重试是毫无意义的。

1.2 弱隔离级别

​ 对于事务隔离，可串行的隔离通常是无法接受的，而系统通常使用较弱的隔离级别来防止一部分并发问题，而不是全部。

1.2.1 读已提交

​ 提供了两个保证：没有脏读（只会看到已提交的数据）和没有脏写（只会覆盖已提交的数据）。

​ 某些数据库支持甚至更弱的隔离级别，称为 读未提交（Read uncommitted）。它可以防止脏写，但不防止脏读。

没有脏读

​ 保证用户只会看到已提交的数据

​ 防止脏读的原因是：

• 如果事务需要更新多个对象，脏读取意味着另一个事务可能会只看到一部分更新。
• 如果事务中止，则所有写入操作都需要回滚。如果数据库允许脏读，那就意味着一个事务可能会看到稍后需要回滚的数据，即从未实际提交给数据库的数据。

没有脏写

​ 保证用户不会覆写未提交的数据

• 如果事务更新多个对象，脏写会导致不好的结果。
• 读已提交并不能防止中两个计数器增量之间的竞争状态。

实现读已提交

​ 使用 行锁（row-level lock） 来防止脏写。

• 当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。
• 一次只有一个事务可持有任何给定对象的锁；如果另一个事务要写入同一个对象，则必须等到第一个事务提交或中止后，才能获取该锁并继续

​ 防止脏读：对于写入的每个对象，数据库都会记住旧的已提交值，和由当前持有写入锁的事务设置的新值。当事务正在进行时，任何其他读取对象的事务都会拿到旧值。 只有当新值提交后，事务才会切换到读取新值。

1.2.2 快照隔离和可重复读

​ 读已提交可以防止读取不完整的事务结果，但还是会有些问题。

​ 如图，用户在事务进行时和事务结束读取到的数据是不一样的。这种异常被称为 不可重复读（nonrepeatable read） 或 读取偏差（read skew）。

​ 虽然用户在刷新之后可能还是会看到正确的结果，但对于某些场景，这也是无法容忍的：

• 备份：如果需要备份整个数据库，这时候可能会包含一些旧的数据，到时候回滚就会覆盖掉之前的新数据。
• 分析查询和完整性检查：一些完整性查询会返回无意义的结果

​ 快照隔离也就是实现可重复读的方法，想法是，每个事务都从数据库的 一致快照（consistent snapshot） 中读取 —— 也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

实现快照隔离

​ 同样的，快照隔离的实现通常使用写锁来防止脏写。但是读取则不需要加锁。这符合一个原则：读不阻塞写，写不阻塞读。

​ 此外，数据库需要保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它同时维护着单个对象的多个版本，所以这种技术被称为 多版本并发控制（MVCC）。

​ 如果一个数据库只需要提供 读已提交 的隔离级别，而不提供 快照隔离，那么保留一个对象的两个版本就足够了：已提交的版本和被覆盖但尚未提交的版本。不过支持快照隔离的存储引擎通常也使用 MVCC 来实现 读已提交 隔离级别。一种典型的方法是 读已提交 为每个查询使用单独的快照，而 快照隔离 对整个事务使用相同的快照。

实现快照隔离

​ 事务 ID 用于决定它可以看见哪些对象，看不见哪些对象。

1. 在每次事务开始时，数据库列出当时所有其他（尚未提交或尚未中止）的事务清单，即使之后提交了，这些事务已执行的任何写入也都会被忽略。
2. 被中止事务所执行的任何写入都将被忽略。
3. 由具有较晚事务 ID（即，在当前事务开始之后开始的）的事务所做的任何写入都被忽略，而不管这些事务是否已经提交。
4. 所有其他写入，对应用都是可见的。

​ 如果以下两个条件都成立，则可见一个对象：

• 读事务开始时，创建该对象的事务已经提交。
• 对象未被标记为删除，或如果被标记为删除，请求删除的事务在读事务开始时尚未提交。

索引和快照隔离

​ 索引如何在多版本数据库中工作？可以让索引简单地指向对象的所有版本，并且需要索引查询来过滤掉当前事务不可见的任何对象版本。当垃圾收集删除任何事务不再可见的旧对象版本时，相应的索引条目也可以被删除。

​ 还有一种方法，对于B树，使用的是一种 仅追加 / 写时拷贝（append-only/copy-on-write） 的变体，它们在更新时不覆盖树的页面，而为每个修改页面创建一份副本。从父页面直到树根都会级联更新，以指向它们子页面的新版本。任何不受写入影响的页面都不需要被复制，并且保持不变。也就是说每个写入事务（或一批事务）都会创建一棵新的 B 树，当创建时，从该特定树根生长的树就是数据库的一个一致性快照。没必要根据事务 ID 过滤掉对象，因为后续写入不能修改现有的 B 树；它们只能创建新的树根。

1.2.3 防止丢失更新

​ 前面忽略了两个事务并发写入的问题。

​ 解决方案。

原子写

​ 一些数据库提供了原子更新操作。例如

UPDATE counters SET value = value + 1 WHERE key = 'foo';

​ 原子操作通常通过在读取对象时，获取其上的排它锁来实现。以便更新完成之前没有其他事务可以读取它。这种技术有时被称为 游标稳定性。另一个选择是简单地强制所有的原子操作在单一线程上执行。

显式锁定

​ 应用程序显式地锁定将要更新的对象。然后应用程序可以执行读取 - 修改 - 写入序列，如果任何其他事务尝试同时读取同一个对象，则强制等待，直到第一个 读取 - 修改 - 写入序列 完成。

自动检测丢失的更新

​ 允许它们并行执行，如果事务管理器检测到丢失更新，则中止事务并强制它们重试其 读取 - 修改 - 写入序列。

​ 优点在于可以结合快照隔离高效地执行此检查。值得注意的是，MySQL/InnoDB 的可重复读并不会检测 丢失更新（真的吗？）。

比较并设置（CAS）

​ 也是种原子操作，只有当前值从上次读取时一直未改变，才允许更新发生。如果当前值与先前读取的值不匹配，则更新不起作用，且必须重试读取 - 修改 - 写入序列。

冲突解决和复制

​ 在具有复制的条件下，防止丢失的更新需要考虑另一个维度：由于在多个节点上存在数据副本，并且在不同节点上的数据可能被并发地修改，因此需要采取一些额外的步骤来防止丢失更新。

​ 一般的方法是允许并发写入创建多个冲突版本的值（也称为兄弟），并使用应用代码或特殊数据结构在事实发生之后解决和合并这些版本。

​ 还有就是使用最后写入胜利（LWW）。

1.2.4 写入偏斜与幻读

​ 这也是讲的并发写入的一些问题。先看下图例子，两人并发写入导致没有人on_call。

写偏差的特征

​ 写偏差是指两个事务正在更新两个不同的对象。可以将写入偏差视为丢失更新问题的一般化。如果两个事务读取相同的对象，然后更新其中一些对象（不同的事务可能更新不同的对象），则可能发生写入偏差。

​ 对于写偏差，难点在于：

• 由于涉及多个对象，单对象的原子操作不起作用
• 在一些快照隔离的实现中，自动检测丢失更新对此并没有帮助
• 涉及多个对象的约束

幻读

​ 先阐述一种模式：

1. 一个 SELECT 查询找出符合条件的行，并检查是否符合一些要求。
2. 按照第一个查询的结果，应用代码决定是否继续。
3. 如果应用决定继续操作，就执行写入（插入、更新或删除），并提交事务。

​ 但最后写入的效果改变了步骤 2 中的先决条件。换句话说，如果在提交写入后，重复执行一次步骤 1 的 SELECT 查询，将会得到不同的结果。因为写入改变了符合搜索条件的行集

​ 一个事务中的写入改变另一个事务的搜索查询的结果，被称为 幻读。快照隔离避免了只读查询中幻读，但是在像我们讨论的例子那样的读写事务中，幻读会导致特别棘手的写入偏差情况。

物化冲突

​ 要创建预订的事务可以锁定（SELECT FOR UPDATE）表中与所需房间和时间段对应的行。在获得锁定之后，它可以检查重叠的预订并像以前一样插入新的预订。这种方法被称为 物化冲突（materializing conflicts）。

1.3 可串行化

1.3.1 真的串行执行

​ 避免并发问题的最简单方法就是完全不要并发：在单个线程上按顺序一次只执行一个事务。

​ 为什么允许这么做呢？

• RAM 足够便宜了，许多场景现在都可以将完整的活跃数据集保存在内存中。当事务需要访问的所有数据都在内存中时，事务处理的执行速度要比等待数据从磁盘加载时快得多。
• OLTP 事务通常很短，而且只进行少量的读写操作，而长时间运行的分析查询通常是只读的，因此它们可以在串行执行循环之外的一致快照（使用快照隔离）上运行。

在存储过程中封装事务

​ 使用存储过程也就是指提前将整个事务代码提交给数据库，如果事务所需的所有数据都在内存中，则存储过程可以非常快地执行，而不用等待任何网络或磁盘 I/O。

​ 缺点：

• 难以管理：与应用服务器相比，它更难调试，更难以保持版本控制和部署，更难测试，并且难以集成到指标收集系统来进行监控。
• 写的不好的存储过程会造成数据库性能的极大浪费

​ 优点：

• 使得在单个线程上执行所有事务变得可行。由于不需要等待 I/O，且避免了并发控制机制的开销，它们可以在单个线程上实现相当好的吞吐量。

​ 对于分区处理，如果为每个分区指派一个独立的 CPU 核，事务吞吐量就可以与 CPU 核数保持线性伸缩，但是要协调事务，这个开销是不能忽略的，事务是否可以是划分至单个分区很大程度上取决于应用数据的结构。简单的键值数据通常可以非常容易地进行分区，但是具有多个次级索引的数据可能需要大量的跨分区协调。

​ 什么时候使用这种方式最好？

• 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。
• 仅限于活跃数据集可以放入内存的情况。
• 写入吞吐量必须低到能在单个 CPU 核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
• 跨分区事务是可能的，但是它们能被使用的程度有很大的限制。

​ 如果事务需要访问不在内存中的数据，最好的解决方案可能是中止事务，异步地将数据提取到内存中，同时继续处理其他事务，然后在数据加载完毕时重新启动事务。这种方法被称为 反缓存。

3.2 两阶段锁定

​ 一种串行化算法：两阶段锁定（2PL，two-phase locking）。注意不是两阶段提交（2PC），这不是一个东西。

​ 两阶段锁定允许多个事务同时读取同一个对象。但对象只要有写入（修改或删除），就需要 独占访问（exclusive access） 权限：

• 如果事务 A 读取了一个对象，并且事务 B 想要写入该对象，那么 B 必须等到 A 提交或中止才能继续
• 如果事务 A 写入了一个对象，并且事务 B 想要读取该对象，则 B 必须等到 A 提交或中止才能继续

​ 在 2PL 中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。快照隔离使得 读不阻塞写，写也不阻塞读。这是其区别

实现两阶段锁

​ 2PL 用于 MySQL（InnoDB）和 SQL Server 中的可串行化隔离级别。读与写的阻塞是通过为每个对象加锁实现的，锁可以处于 共享模式（shared mode） 或 独占模式（exclusive mode）。

• 若事务要读取对象，则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有排它锁，则这些事务必须等待。
• 若事务要写入一个对象，它必须首先以独占模式获取该锁。没有其他事务可以同时持有锁（无论是共享模式还是独占模式），所以如果对象上存在任何锁，该事务必须等待。
• 如果事务先读取再写入对象，则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得独占锁相同。
• 事务获得锁之后，必须继续持有锁直到事务结束（提交或中止）。这就是 “两阶段” 这个名字的来源：第一阶段（当事务正在执行时）获取锁，第二阶段（在事务结束时）释放所有的锁。

​ 如果产生死锁，数据库会自动检测事务之间的死锁，并中止其中一个，以便另一个继续执行。

​ 性能

​ 运行 2PL 的数据库可能具有相当不稳定的延迟，如果在工作负载中存在争用，那么可能高百分位点处的响应会非常的慢。可能只需要一个缓慢的事务，或者一个访问大量数据并获取许多锁的事务，就能把系统的其他部分拖慢，甚至迫使系统停机。

​ 另外，死锁的发生会频繁的多，这可能会造成些浪费。

谓词锁

​ 谓词锁属于所有符合某些搜索条件的对象。

• 如果事务 A 想要读取匹配某些条件的对象，就像在这个 SELECT 查询中那样，它必须获取查询条件上的 共享谓词锁（shared-mode predicate lock）。如果另一个事务 B 持有任何满足这一查询条件对象的排它锁，那么 A 必须等到 B 释放它的锁之后才允许进行查询。
• 如果事务 A 想要插入，更新或删除任何对象，则必须首先检查旧值或新值是否与任何现有的谓词锁匹配。如果事务 B 持有匹配的谓词锁，那么 A 必须等到 B 已经提交或中止后才能继续。

​ 性能

​ 不好。如果活跃事务持有很多锁，检查匹配的锁会非常耗时。

索引范围锁

​ 英译 next-key locking。索引范围锁并不像谓词锁那样精确（它们可能会锁定更大范围的对象，而不是维持可串行化所必需的范围），但是由于它们的开销较低，所以是一个很好的折衷。

例如，在房间预订数据库中，可能会在 room_id 列上有一个索引，并且 / 或者在 start_time 和 end_time 上有索引（否则前面的查询在大型数据库上的速度会非常慢）：

• 假设你的索引位于 room_id 上，并且数据库使用此索引查找 123 号房间的现有预订。现在数据库可以简单地将共享锁附加到这个索引项上，指示事务已搜索 123 号房间用于预订。
• 或者，如果数据库使用基于时间的索引来查找现有预订，那么它可以将共享锁附加到该索引中的一系列值，指示事务已经将 12:00~13:00 时间段标记为用于预定。

3.3 可串行化快照隔离

​ 文章介绍这是2008年首次提出的算法。

悲观与乐观的并发控制

​ 对于2PL，采用就是一种悲观策略：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。

​ 串行化快照隔离 是一种 乐观（optimistic） 的并发控制技术。在这种情况下，乐观意味着，如果存在潜在的危险也不阻止事务，而是继续执行事务，希望一切都会好起来。当一个事务想要提交时，数据库检查是否有什么不好的事情发生（即隔离是否被违反）；如果是的话，事务将被中止，并且必须重试。只有可串行化的事务才被允许提交。

​ 乐观优点是：如果有足够的空闲容量，并且事务之间的争用不是太高，性能会比悲观好；可交换的原子操作可以减少争用。

​ 缺点是：如果存在很多争用，导致很大一部分事务需要中止。

如何实现可串行化快照隔离

​ SSI在快照隔离的基础上，添加了一种算法来检测写入之间的串行化冲突，并确定要中止哪些事务。

​ 由于会产生写入偏差的原因是：事务会基于一个 前提（premise） 采取行动（例如读取一些数据，检查查询的结果，并根据它看到的结果决定采取一些操作）。所以为了提供可串行化的隔离级别，如果事务在过时的前提下执行操作，数据库必须能检测到这种情况，并中止事务。

​ 如何检测？需要考虑两种情况

• 检测对旧 MVCC 对象版本的读取（读之前存在未提交的写入）
• 检测影响先前读取的写入（读之后发生写入）

检测旧MVCC读取

​ 提例子🌰，如图，事务 43 认为 Alice 的 on_call = true ，因为事务 42（修改 Alice 的待命状态）未被提交。然而，在事务 43 想要提交时，事务 42 已经提交。这意味着在读一致性快照时被忽略的写入已经生效，事务 43 的前提不再为真。

​ 为了防止这种异常，数据库需要跟踪一个事务由于 MVCC 可见性规则而忽略另一个事务的写入。当事务想要提交时，数据库检查是否有任何被忽略的写入现在已经被提交。如果是这样，事务必须中止。

​ 为什么要等到提交？而不是检测则立即中止。

​ 因为如果事务 43 是只读事务，则不需要中止，因为没有写入偏差的风险。当事务 43 进行读取时，数据库还不知道事务是否要稍后执行写操作。此外，事务 42 可能在事务 43 被提交的时候中止或者可能仍然未被提交，因此读取可能终究不是陈旧的。通过避免不必要的中止，SSI 保留了快照隔离从一致快照中长时间读取的能力。

检测影响之前读取的写入

​ 也就是读取数据之后另一个事务修改了数据。

​ 通过记录事务 42 和 43 读取这个数据的事实（这个数据只保留在一个事务完成（提交或中止），并且所有的并发事务完成之后）。

​ 当事务写入数据库时，它必须在索引中查找最近曾读取受影响数据的其他事务。这个过程类似于在受影响的键范围上获取写锁，但锁并不会阻塞事务直到其他读事务完成，而是像警戒线一样只是简单通知其他事务：你们读过的数据可能不是最新的啦。

​ 性能

​ 与两阶段锁定相比，可串行化快照隔离的最大优点是一个事务不需要阻塞等待另一个事务所持有的锁。

​ 与串行执行相比，可串行化快照隔离并不局限于单个 CPU 核的吞吐量：FoundationDB 将串行化冲突的检测分布在多台机器上，允许扩展到很高的吞吐量。

二 分布式系统的麻烦

​ 这章主要讨论了分布式系统中可能出现的诸多问题，从网络，时钟和时序方面去讲。最后会说如何思考分布式系统的状态

2.1 前言

​ 这里原文是讲故障与部分失效，云计算与超级计算机。。我感觉像是扩展知识，收获并不是很大，就简单说一下吧。

​ 部分失效也就是指系统的某些部分被破坏，但其他部分正常。

​ 超级计算机中，作业通常会不时地将计算的状态存盘到持久存储中。如果一个节点出现故障，通常的解决方案是简单地停止整个集群的工作负载。故障节点修复后，计算从上一个检查点重新开始。这更像一个单节点计算机

​ 对于分布式系统通常有以下特点：

• 需要能够随时以低延迟服务用户。使服务不可用（例如，停止集群以进行修复）是不可接受的。
• 由于规模经济，需要以较低的成本提供相同的性能，而且具有较高的故障率。
• 通常基于 IP 和以太网，以 CLOS 拓扑排列的网络模型。
• 能容忍发生故障的节点，并继续保持整体工作状态（例如滚动升级）
• 在地理位置分散的部署中（保持数据在地理位置上接近用户以减少访问延迟）。

​ 分布式系统就是从不可靠的组件构建一个可靠的系统。

2.2 不可靠的网络

​ 网络问题可非常常见了，对于分布式系统这种无共享的系统，即通过网络连接的一堆机器。无共享的坏处显而易见，无法确保系统正常运行，而好处在于相对便宜，因为它不需要特殊的硬件，可以利用商品化的云计算服务，通过跨多个地理分布的数据中心进行冗余可以实现高可靠性。

​ 在这种架构中，通常节点之间通过传播数据包进行通信，但这会出现很多意外：

• 请求丢失
• 请求阻塞
• 节点失效
• 节点暂时停止响应
• 节点处理了请求，但响应丢失
• 节点处理了请求，但响应延迟

​ 由此，会使得发送方不知道数据是否被发送，通常处理方式是超时重传，但依然会存在一些问题。

网络故障

​ 也称 网络分区或 网络断裂。也就是网络的一部分由于网络故障而被切断。这有可能会导致集群可能会发生 死锁，永久无法为请求提供服务，甚至可能会删除所有的数据。

2.2.1 检测故障

​ 检测故障节点很重要。例如负载均衡器需要停止向已死亡的节点转发请求；单主复制功能的分布式数据库中，如果主库失效，则需要将从库之一升级为新主库。

​ 这里解释可能会收到故障节点反馈信息的几种情况

• 节点进程崩溃（或被管理员杀死），但节点的操作系统仍在运行，则脚本可以通知其他节点有关该崩溃的信息，以便另一个节点可以快速接管，而无需等待超时到期。
• 如果路由器确认你尝试连接的 IP 地址不可用，则可能会使用 ICMP 目标不可达数据包回复。

​ 但通常必须假设你可能根本就得不到任何回应。所以可以重试几次（TCP 重试是透明的，但是你也可以在应用程序级别重试），等待超时过期，并且如果在超时时间内没有收到响应，则最终声明节点已经死亡。

2.2.2 超时与无穷的延迟

​ 超时应该等待多久？太长会导致请求长时间等待，用户可能不得不等待，或者看到错误信息；太短可能会导致一些没有死亡的节点被宣告死亡，给其他节点和网络带来额外的负担，从而导致 级联失效。

网络阻塞和排队

​ 网络包的发送和处理是有很大可能阻塞的。 以下情况有可能发生：

• 多个不同的节点同时尝试将数据包发送到同一目的地，则网络交换机必须将它们排队并将它们逐个送入目标网络链路
• 所有 CPU 内核当前都处于繁忙状态，则来自网络的传入请求将被操作系统排队，直到应用程序准备好处理它为止
• 虚拟化环境中，正在运行的操作系统经常暂停几十毫秒，因为另一个虚拟机正在使用 CPU 内核
• TCP 执行 流量控制

​ 实际场景有：高利用率的系统中，很快就能积累很长的队列；公共云和多租户数据中心中，资源被许多客户共享：网络链接和交换机，甚至每个机器的网卡和 CPU（在虚拟机上运行时）；批处理工作负载能够很容易使网络链接饱和。

​ 所以通常系统不是使用配置的常量超时时间，而是连续测量响应时间及其变化（抖动），并根据观察到的响应时间分布自动调整超时时间。

2.2.3 同步网络与异步网络

​ 同步网络：即使数据经过多个路由器，也不会受到排队的影响，因为呼叫的 16 位空间已经在网络的下一跳中保留了下来。而且由于没有排队，网络的最大端到端延迟是固定的。我们称之为 有限延迟。

​ 对于以太网和IP，它们是分组交换协议，这就意味着不得不忍受排队的折磨，及其导致的网络无限延迟。

​ 为什么数据中心网络和互联网使用分组交换？答案是，它们针对 突发流量（bursty traffic） 进行了优化。例如一个电路适用于音频或视频通话，在通话期间需要每秒传送相当数量的比特。另一方面，请求网页，发送电子邮件或传输文件没有任何特定的带宽要求 —— 只是希望它尽快完成。

​ 但对于一些互联网服务提供商，通过 BGP 网关协议（BGP） 建立的路由，与 IP 协议相比，更接近于电路交换，这样可以购买专用带宽。

​ 延迟变化可以视为动态资源分区的结果。互联网动态分享网络带宽。发送者互相推挤和争夺，以让他们的数据包尽可能快地通过网络，并且网络交换机决定从一个时刻到另一个时刻发送哪个分组（即，带宽分配）。这种方法有排队的缺点，但其优点是它最大限度地利用了线路。

​ 而如果资源是静态分区的（例如，专用硬件和专用带宽分配），则在某些环境中可以实现 延迟保证。但是，这是以降低利用率为代价的 —— 换句话说，它是更昂贵的。另一方面，动态资源分配的多租户提供了更好的利用率，所以它更便宜，但它具有可变延迟的缺点。

2.3 不可靠的时钟

​ 时间或者时钟真的很重要。但只要涉及到时间的问题也会变的复杂，例如请求是否超时了？服务的第 99 百分位响应时间是多少？用户在我们的网站上花了多长时间？缓存条目何时到期？等等。

​ 在分布式机器中，每个机器都有自己的时间概念，有一种协议：网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟，服务器则从更精确的时间源（如 GPS 接收机）获取时间。

2.3.1 单调钟与日历时钟

日历时钟

​ 指根据某个日历（也称为 挂钟时间，即 wall-clock time）返回当前日期和时间。例如Linux 上的 clock_gettime(CLOCK_REALTIME) 和 Java 中的 System.currentTimeMillis() 返回自 epoch（UTC 时间 1970 年 1 月 1 日午夜）以来的秒数（或毫秒）。

​ 日历时钟通常与 NTP 同步，这意味着来自一台机器的时间戳（理想情况下）与另一台机器上的时间戳相同。但存在一种可能，本地时钟在 NTP 服务器之前太远，则它可能会被强制重置，看上去好像跳回了先前的时间点。

单调钟

​ 单调钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间：Linux 上的 clock_gettime(CLOCK_MONOTONIC)，和 Java 中的 System.nanoTime() 都是单调时钟。这是因为它是单调递增的，这也是它和日历时钟的不同吧。

​ 这里说比较来自两台不同计算机的单调钟的值是没有意义的，因为它们并不是一回事。我理解是这是计算机自己定义的时钟，有可能是计算机启动以来的纳秒数，或类似的任意值，只能用于经过时长。

​ os：在具有多个 CPU 插槽的服务器上，每个 CPU 可能有一个单独的计时器，但不一定与其他 CPU 同步。操作系统会补偿所有的差异，并尝试向应用线程表现出单调钟的样子，即使这些线程被调度到不同的 CPU 上。

​ 如果 NTP 协议检测到计算机的本地石英钟比 NTP 服务器要更快或更慢，则可以调整单调钟向前走的频率。

​ 在分布式系统中，使用单调钟测量 经过时间（elapsed time，比如超时）通常很好，因为它不假定不同节点的时钟之间存在任何同步，并且对测量的轻微不准确性不敏感。

2.3.2 时间同步与准确性

​ 这里举了几个例子阐述不同机器时间不一致（未能同步）的情况（单调钟不需要同步，因为仅用于经过时长）。

• 计算机中的石英钟不精确。这受机器温度影响
• 计算机的时钟与 NTP 服务器的时钟差别太大，可能会拒绝同步，或者本地时钟将被强制重置
• 某个节点被 NTP 服务器的防火墙意外阻塞
• NTP 服务器是错误的或者配置错误的
• 闰秒导致一分钟可能有 59 秒或 61 秒（todo：不太了解）
• 虚拟化的影响，例如当一个 CPU 核心在虚拟机之间共享时，每个虚拟机都会暂停几十毫秒，与此同时另一个虚拟机正在运行。

2.3.3 依赖同步时钟

​ 因为时钟的偏差是难以发现的，通常需要同步时钟的软件，仔细监控所有机器之间的时钟偏移。时钟偏离其他时钟太远的节点应当被宣告死亡，并从集群中移除。这样的监控可以确保在损失发生之前注意到破损的时钟。

​ 前面说过最终胜利写入（LWW），也就是在多主复制和无主数据库中会根据服务器时间戳快慢进行写入数据，但这有可能导致数据神秘消失，并且对顺序写入和并发写入是无法区分的。两个服务器有可能生成相同的时间戳，这时候就需要一个决胜值。

​ 即使LWW使用了使用严格同步的 NTP 时钟，一个数据包也可能在时间戳 100 毫秒（根据发送者的时钟）时发送，并在时间戳 99 毫秒（根据接收者的时钟）处到达 ， 看起来好像数据包在发送之前已经到达，这是不可能的。

​ 使用逻辑时钟基于递增计数器而不是振荡石英晶体，可以用来排序事件，逻辑时钟不测量一天中的时间或经过的秒数，而仅测量事件的相对顺序。

时间读数存在置信区间

​ 指时钟询问当前时间时，会得到两个值：[最早，最晚]。

全局快照的同步

​ 这里从快照隔离的角度讨论了全局时钟这一问题

​ 快照隔离需要单调递增的事务ID，但是当数据库分布在许多机器上，这个事务ID就需要协调生成，如雪花算法，但该算法分配的 ID 块的时间范围比数据库读取和写入的时间范围要长，这就很难 保证与因果关系一致的排序。

​ 通常，我们通过使用同步时钟的时间戳作为事务 ID，更晚的事务会有更大的时间戳。

​ Spanner用了置信区间的方式，如果你有两个置信区间，每个置信区间包含最早和最晚可能的时间戳（$A = [A_{earliest}, A_{latest}]， B=[B_{earliest}, B_{latest}]$），这两个区间不重叠（即：$A_{earliest} <A_{latest} <B_{earliest} <B_{latest}$）的话，那么 B 肯定发生在 A 之后 —— 这是毫无疑问的。只有当区间重叠时，我们才不确定 A 和 B 发生的顺序。

2.3.4 进程暂停

​ 讨论了一个节点如何知道它仍然是领导者（它并没有被别人宣告为死亡），并且它可以安全地接受写入？

​ 答：使用租约，任一时刻只有一个节点可以持有租约 —— 因此，当一个节点获得一个租约时，它知道它在某段时间内自己是领导者，直到租约到期。为了保持领导地位，节点必须周期性地在租约过期前续期。

​ 如果节点发生故障，就会停止续期，所以当租约过期时，另一个节点可以接管。

​ 可以发现又和时间扯上关系了，

1. 如果依赖于同步时钟，和本地系统时钟进行比较。如果时钟不同步超过几秒，这段代码将开始做奇怪的事情。

2. 如果是仅使用本地单调时钟，在执行剩余时间检查 System.currentTimeMillis() 和实际执行请求 process(request) 中间的时间间隔非常短。通常情况下，这段代码运行得非常快，所以 10 秒的缓冲区已经足够确保 租约 在请求处理到一半时不会过期。

3. 程序执行中出现了意外的停顿。

   • 程序正在进行GC
   • 虚拟化环境可能会挂起虚拟机
   • 设备关闭
   • 线程切换
   • IO操作

​ 所有这些事件都可以随时 抢占（preempt） 正在运行的线程，并在稍后的时间恢复运行，而线程甚至不会注意到这一点。当然，在单机中可以通过互斥量，信号量等工具保证安全，但分布式就要通过不可靠网络发送的消息。

响应时间保证

​ 感觉这里不是讲分布式的实时。硬实时（hard real-time） 系统，允许在指定的时间间隔内保证 CPU 时间的分配。

​ 对于大多数服务器端数据处理系统来说，实时保证是不经济或不合适的。因此，这些系统必须承受在非实时环境中运行的暂停和时钟不稳定性。

限制垃圾回收的影响

​ 一个新兴的想法是将 GC 暂停视为一个节点的短暂计划中断，并在这个节点收集其垃圾的同时，让其他节点处理来自客户端的请求。

​ 这个想法的一个变种是只用垃圾收集器来处理短命对象（这些对象可以快速收集），并定期在积累大量长寿对象（因此需要完整 GC）之前重新启动进程。

2.4 知识，真相和谎言

​ 如何思考分布式系统做出的假设和希望提供的保证。

2.4.1 真相由多数定义

​ 某些节点可能会因为网络故障，GC等原因导致半断开（也就是被其他节点宣布死亡）。从而说明分布式系统不能完全依赖单个节点，因为节点可能随时失效。

​ 所以，许多分布式算法都依赖于法定人数，即在节点之间进行投票：决策需要来自多个节点的最小投票数，以减少对于某个特定节点的依赖。

领导者和锁

​ 该部分似乎重复讲了，讲的也就是如果Leader获取租约准备写入文件时，由于GC等租约过期了，而错误的分布式锁会导致错误的写入。

防护令牌

​ 上述问题可以通过令牌解决，每次锁定服务器授予锁或租约时，它还会返回一个 防护令牌（fencing token），这个数字在每次授予锁定时都会增加（例如，由锁定服务增加）。客户端每次向存储服务发送写入请求时，都必须包含当前的防护令牌。

2.4.2 拜占庭故障

​ 前面讲的都是节点是不可靠但诚实的，但要注意存在节点可能 “撒谎”（发送任意错误或损坏的响应）的风险。

​ 当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作，称之为 拜占庭容错。啥？你问为什么节点会撒谎？

• 存在计算机内存或 CPU 寄存器中的数据可能被辐射破坏，导致其以任意不可预知的方式响应其他节点。
• 在多个参与组织的系统中，一些参与者可能会试图欺骗或诈骗他人。（我想是中心机构也不可信？）
• 漏洞，安全渗透和恶意攻击。所以，传统机制（认证，访问控制，加密，防火墙等）仍然是抵御攻击者的主要保护措施

​ 提高可靠性的方式还有：

• 可公开访问的应用程序必须仔细清理来自用户的任何输入，例如检查值是否在合理的范围内，并限制字符串的大小以防止通过大内存分配的拒绝服务。
• NTP 客户端可以配置多个服务器地址。同步时，客户端联系所有的服务器，估计它们的误差，并检查大多数服务器是否对某个时间范围达成一致。

2.4.3 系统模型与现实

​ 提出了两类模型

​ 时序模型

• 同步模型。假设网络延迟、进程暂停和和时钟误差都是受限的。这并不意味着完全同步的时钟或零网络延迟；这只意味着你知道网络延迟、暂停和时钟漂移将永远不会超过某个固定的上限
• 部分同步模型。一个系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的界限
• 异步模型。算法不允许对时序做任何假设 —— 事实上它甚至没有时钟（所以它不能使用超时）。

​ 节点失效模型

• 崩溃 - 停止故障。算法可能会假设一个节点只能以一种方式失效，即通过崩溃。这意味着节点可能在任意时刻突然停止响应，此后该节点永远消失 —— 它永远不会回来。
• 崩溃 - 恢复故障。节点可能会在任何时候崩溃，但也许会在未知的时间之后再次开始响应。
• 拜占庭（任意）故障。节点可以做（绝对意义上的）任何事情，包括试图戏弄和欺骗其他节点。

​ 对于真实系统的建模，具有 崩溃 - 恢复故障（crash-recovery） 的 部分同步模型（partial synchronous） 通常是最有用的模型。

​ 分布式算法应该保证其正确性，安全性，活性。安全通常被非正式地定义为：没有坏事发生，而活性通常就类似：最终好事发生。

三 一致性与共识

​ 事务隔离主要是为了 避免由于同时执行事务而导致的竞争状态，而分布式一致性主要关于 在面对延迟和故障时如何协调副本间的状态。

​ 接下来会讨论：

1. 最强一致性模型之一，线性一致性（linearizability）
2. 检查分布式系统中事件顺序的问题
3. 分布式事务

3.1 线性一致性

​ 线性一致性可以保证数据库提供只有一个副本的假象（即，只有一个数据副本）。这可以防止同一时刻得到两个不同副本的问题。

3.1.1 什么使得系统线性一致性？

​ 在一个线性一致的系统中，我们可以想象，在 x 的值从 0 自动翻转到 1 的时候（在写操作的开始和结束之间）必定有一个时间点。因此，如果一个客户端的读取返回新的值 1，即使写操作尚未完成，所有后续读取也必须返回新值。
​ 在添加一个新操作，CAS（具体含义可以百度），展示每个操作是如何在特定时刻原子性生效的。

​ 见栗子，

​ 前面的操作都是线性一致性的，因为其都是按照生效时间点进行反馈，但B的最后一次读取不是，该操作与 C 的 cas 写操作并发（它将 x 从 2 更新为 4 ）。在没有其他请求的情况下，B 的读取返回 2 是可以的。然而，在 B 的读取开始之前，客户端 A 已经读取了新的值 4 ，因此不允许 B 读取比 A 更旧的值。

​ 区分线性一致性与可串行化：

• 可串行化（Serializability） 是事务的隔离属性，确保事务的行为，与它们按照 某种 顺序依次执行的结果相同。
• 线性一致性（Linearizability） 是读取和写入寄存器（单个对象）的 新鲜度保证。它不会将操作组合为事务，因此它也不会阻止写入偏差等问题。

​ 一个数据库可以提供可串行化和线性一致性，这种组合被称为严格的可串行化或 强的单副本可串行化。基于两阶段锁定的可串行化实现或 真的串行执行通常是线性一致性的。

​ 但一致性快照的要点就在于 它不会包括该快照之后的写入，因此从快照读取不是线性一致性的。

3.1.2 依赖线性一致性

​ 我没太看懂这里想讲什么。。。似乎是啥情况需要线性一致性？

​ 为了防止脑裂，每个节点在启动时尝试获取锁，成功者成为领导者。

​ 一个硬性的唯一性约束（关系型数据库中常见的那种）需要线性一致性。

​ 一个图像缩放器，通常是以下架构，

​ 如果文件存储服务是线性一致的，那么这个系统应该可以正常工作。如果它不是线性一致的，则存在竞争条件的风险，消息队列可能比存储服务内部的复制（replication）更快。在这种情况下，当缩放器读取图像（步骤 5）时，可能会看到图像的旧版本，或者什么都没有。

3.1.3 实现线性一致性的系统

​ 线性一致性本质上意味着 “表现得好像只有一个数据副本，而且所有的操作都是原子的”。那么如何实现一个提供线性一致性的系统？

比较之前的复制算法，并看它们是否可以满足线性一致性：

• 单主复制（可能线性一致）

  ​ 如果从主库或同步更新的从库读取数据，它们 可能（potential） 是线性一致性的。但是这取决于单主数据库是否是线性一致性的。

  ​ 注意：对单主数据库进行分区（分片），使得每个分区有一个单独的领导者，不会影响线性一致性，因为线性一致性只是对单一对象的保证。

• 共识算法（线性一致性）

  ​ 共识协议包含防止脑裂和陈旧副本的措施。正是由于这些细节，共识算法可以安全地实现线性一致性存储。

• 多主复制（非线性一致性）

  ​ 多主程序复制的系统通常不是线性一致的，因为它们同时在多个节点上处理写入，并将其异步复制到其他节点。因此，它们可能会产生需要被解决的写入冲突。

• 无主复制（也许不是线性一致的）

  ​ 通过要求法定人数读写（ w + r > n ）可以获得 “强一致性”。这取决于法定人数的具体配置，以及强一致性如何定义（通常不完全正确）。

  ​ 基于日历时钟的 “最后写入胜利” 冲突解决方法几乎可以确定是非线性一致的，由于时钟偏差，不能保证时钟的时间戳与实际事件顺序一致。

3.1.4 线性一致性的代价

​ 对于多主或单主复制，都会出现非线性一致性的情况，其中很大部分原因是网络。

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

​ 也就是CP（在网络分区下一致但不可用）和 AP（在网络分区下可用但不一致）。

​ 值得说明的是，现代多核 CPU 上的内存甚至都不是线性一致的：如果一个 CPU 核上运行的线程写入某个内存地址，而另一个 CPU 核上运行的线程不久之后读取相同的地址，并没有保证一定能读到第一个线程写入的值（除非使用了 内存屏障（memory barrier））

​ 原因是每个 CPU 核都有自己的内存缓存和存储缓冲区。默认情况下，内存访问首先走缓存，任何变更会异步写入主存。因为缓存访问比主存要快得多。

​ 牺牲线性一致性的原因是 性能（performance），而不是容错。

3.2 顺序保证

3.2.1 顺序和因果关系

因果顺序不是全序的

​ 全序就是允许任意两个元素进行比较，总能说出谁大谁小。例如，自然数集是全序的。

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

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

​ 值得说的是，一个系统可以是因果一致的，而无需承担线性一致带来的性能折损，在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一致性，且性能与可用性与最终一致的系统类似。（期待.jpg）

捕获因果关系

​ 为了维持因果性，需要知道哪个操作发生在哪个其他操作之前。这是一个偏序：并发操作可以以任意顺序进行，但如果一个操作发生在另一个操作之前，那它们必须在所有副本上以那个顺序被处理。

​ 因此，当一个副本处理一个操作时，它必须确保所有因果前驱的操作（之前发生的所有操作）已经被处理；如果前面的某个操作丢失了，后面的操作必须等待，直到前面的操作被处理完毕。

3.2.2 序列号顺序

​ 如果有一次巨大的读取后进行写入，我们很难弄清写入因果依赖于先前全部的读取内容，还是仅包括其中一部分。显式跟踪所有已读数据意味着巨大的额外开销。

​ 另一个方法是：使用 序列号（sequence nunber） 或 时间戳（timestamp） 来排序事件。时间戳不一定来自日历时钟，可以来自一个 逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

​ 这样的序列号或时间戳是紧凑的（只有几个字节大小），它提供了一个全序关系：也就是说每个操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大。

非因果序列号生成器

​ 如果不需要维护操作的因果序列，只是为了区分每个操作或者为每个操作分配节点处理。那么可以用下述方法：

• 每个节点都可以生成自己独立的一组序列号。例如有两个节点，一个节点只能生成奇数，而另一个节点只能生成偶数。
• 可以将日历时钟（物理时钟）的时间戳附加到每个操作上
• 可以预先分配序列号区块。

​ 当然，这些方法都无法保证因果。

兰伯特时间戳

​ 大概是：每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合：（计数器，节点 ID）。

​ 兰伯特时间戳与物理的日历时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则 计数器 值大者是更大的时间戳。如果计数器值相同，则节点 ID 越大的，时间戳越大。

​ 使兰伯特时间戳因果一致的关键思想如下所示：每个节点和每个客户端跟踪迄今为止所见到的最大 计数器 值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。

​ 该与版本向量的区别是：版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳总是施行一个全序。从兰伯特时间戳的全序中，你无法分辨两个操作是并发的还是因果依赖的。 兰伯特时间戳优于版本向量的地方是，它更加紧凑。

光有时间戳排序还不够

​ 但还有一个问题 是：兰伯特时间只有只有在所有的操作都被收集之后，操作的全序才会出现。

​ 例如，考虑一个需要确保用户名能唯一标识用户帐户的系统。如果两个用户同时尝试使用相同的用户名创建帐户，则其中一个应该成功，另一个应该失败。但节点在处理某个请求时，并不知道是否存在其他节点正在并发执行创建同样用户名的操作，罔论其它节点可能分配给那个操作的时间戳。

​ 所以，为了实现诸如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定。

3.2.3 全序广播

​ 在单主复制中，通过选择一个节点作为主库来确定操作的全序，并在主库的单个 CPU 核上对所有操作进行排序。但是，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效，如何处理故障切换？

全序广播通常被描述为在节点间交换消息的协议。 非正式地讲，它要满足两个安全属性：

• 可靠交付（reliable delivery）

  没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。

• 全序交付（totally ordered delivery）

  消息以相同的顺序传递给每个节点。

使用全序广播

​ 全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（除了临时的复制延迟）。这个原理被称为 **状态机复制（state machine replication）**。

​ 全序广播的一个重要表现是，顺序在消息送达时被固化：如果后续的消息已经送达，节点就不允许追溯地将（先前）消息插入顺序中的较早位置。这个事实使得全序广播比时间戳排序更强。

​ 考量全序广播的另一种方式是，这是一种创建日志的方式（如在复制日志、事务日志或预写式日志中）：传递消息就像追加写入日志。由于所有节点必须以相同的顺序传递相同的消息，因此所有节点都可以读取日志，并看到相同的消息序列。

​ 全序广播对于实现提供防护令牌的锁服务也很有用。每个获取锁的请求都作为一条消息追加到日志末尾，并且所有的消息都按它们在日志中出现的顺序依次编号。序列号可以当成防护令牌用，因为它是单调递增的。

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

​ 全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息 **何时** 被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

​ 但如果有了全序广播，就可以在此基础上构建线性一致的存储。例如，可以确保用户名能唯一标识用户帐户，使用CAS，如果多个用户试图同时获取相同的用户名，则只有一个 CAS 操作会成功，因为其他用户会看到非空的值（由于线性一致性）。

​ 通过将全序广播当成仅追加日志的方式来实现这种线性一致的 CAS 操作：

1. 在日志中追加一条消息，试探性地指明你要声明的用户名
2. 读日志，并等待你刚才追加的消息被读回
3. 检查是否有任何消息声称目标用户名的所有权。如果这些消息中的第一条就是你自己的消息，那么你就成功了：你可以提交声称的用户名（也许是通过向日志追加另一条消息）并向客户端确认。如果所需用户名的第一条消息来自其他用户，则中止操作

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

​ 也就是和上面反过来，算法很简单：每个要通过全序广播发送的消息首先对线性一致寄存器执行 **自增并返回** 操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点（重新发送任何丢失的消息），而收件人将按序列号依序传递（deliver）消息。

3.3 分布式事务与共识

​ 共识也就是指 让几个节点达成一致。开头就说对于共识领导选举和原子提交对于节点一致很重要。

​ 原子提交的形式化与共识稍有不同：原子事务只有在 所有 参与者投票提交的情况下才能提交，如果有任何参与者需要中止，则必须中止。 共识则允许就 任意一个 被参与者提出的候选值达成一致。（？啥叫被参与者提出的候选值达成一致）

3.3.1 原子提交与两阶段提交

​ 事务原子性的目的是在多次写操作中途出错的情况下，提供一种简单的语义。事务的结果要么是成功提交，在这种情况下，事务的所有写入都是持久化的；要么是中止，在这种情况下，事务的所有写入都被回滚（即撤消或丢弃）。

单节点到分布式原子提交的变化

​ 单节点提交，客户端请求数据库节点提交事务时，数据库将使事务的写入持久化，然后将提交记录追加到磁盘中的日志里。（不是WSL）：如果数据库在这个过程中间崩溃，当节点重启时，事务会从日志中恢复：如果提交记录在崩溃之前成功地写入磁盘，则认为事务被提交；否则来自该事务的任何写入都被回滚。

​ 单节点主要是 事务的提交主要取决于数据持久化落盘的 顺序。

​ 分节点情况，例如前面提到的按关键词分区的次级索引。在这些情况下，仅向所有节点发送提交请求并独立提交每个节点的事务是不够的。这样很容易发生违反原子性的情况：提交在某些节点上成功，而在其他节点上失败。例如某节点由于约束或冲突，网络请求丢失，节点崩溃等中止或回滚，而其他节点提交了。。如果放弃该节点。

​ 注意，已经提交的事务是无法撤回的，所以，一旦确定事务中的所有其他节点也将提交，节点就必须进行提交。啥？你问为啥，读已提交啊。如果一个事务在提交后被允许中止，所有那些读取了 已提交却又被追溯声明不存在数据 的事务也必须回滚。

两阶段提交

​ 两阶段提交（two-phase commit） 是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。

​ 2PC 使用一个新组件：协调者（coordinator，也称为 事务管理器，即 transaction manager）。流程如下：

​ 2PC 事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为 参与者（participants）。当应用准备提交时，协调者开始阶段 1 ：它发送一个 准备（prepare） 请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：

• 如果所有参与者都回答 “是”，表示它们已经准备好提交，那么协调者在阶段 2 发出 提交（commit） 请求，然后提交真正发生。
• 如果任意一个参与者回复了 “否”，则协调者在阶段 2 中向所有节点发送 中止（abort） 请求。

⚠️：两阶段提交（2PC）和两阶段锁定（2PL）是不一样的，2PC 在分布式数据库中提供原子提交，而 2PL 提供可串行化的隔离等级。

为什么两阶段提交可行？

​ 看具体流程：

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

​ 总结：其将提交记录写入事务日志结合到了一起，保证了其原子性。

协调者失效咋办？

​ 如果协调者在发送 准备 请求之前失败，参与者可以安全地中止事务。但是，一旦参与者收到了准备请求并投了 “是”，就不能再单方面放弃 —— 必须等待协调者回答事务是否已经提交或中止。如果此时协调者崩溃或网络出现故障，参与者什么也做不了只能等待。参与者的这种事务状态称为 存疑（in doubt） 的或 不确定（uncertain） 的。

​ 所以唯一办法就是等待协调者恢复。

​ 具体流程4的提交点原因也正是如此，协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志：协调者恢复后，通过读取其事务日志来确定所有存疑事务的状态。

​ 所以，两阶段提交被称为 阻塞（blocking）- 原子提交协议，因为存在 2PC 可能卡住并等待协调者恢复的情况。

三阶段提交

​ 作为 2PC 的替代方案，已经提出了一种称为 三阶段提交。然而，3PC 假定网络延迟有界，节点响应时间有限；在大多数具有无限网络延迟和进程暂停的实际系统中，它并不能保证原子性。

​ 通常，非阻塞原子提交需要一个 完美的故障检测器，即一个可靠的机制来判断一个节点是否已经崩溃。

3.3.2 实践中的分布式事务

​ 开头就泼了冷水，分布式事务会产生运维和性能等问题，很多时候基本不使用。

​ 分布式事务的分类：

• 数据库内部的分布式事务

  ​ 指所有参与事务的节点都运行相同的数据库软件。

• 异构分布式事务

  ​ 参与者是由两种或两种以上的不同技术组成的：例如来自不同供应商的两个数据库，甚至非数据库（例如消息队列等）。

恰好一次的消息处理

​ 指的是异构分布式事务集成不同的系统。例如MQ和DB协作，需要DB的一条数据库事务成功提交，MQ的一条消息才可以被确认为已处理。这需要事务中原子提交 消息确认 和 数据库写入 两个操作。

​ 这样的实现需要所有受事务影响的系统都使用同样的 原子提交协议。

XA事务

​ XA是一个用来与事务协调者连接的 C API。其他语言也有：例如在 Java EE 应用的世界中，XA 事务是使用 Java 事务 API（JTA, Java Transaction API） 实现的。

​ 如果驱动支持XA，则会调用 XA API 以查明操作是否为分布式事务的一部分 —— 如果是，则将必要的信息发往数据库服务器。驱动还会向协调者暴露回调接口，协调者可以通过回调来要求参与者准备、提交或中止。

​ 事务协调者需要实现 XA API。标准没有指明应该如何实现，但实际上协调者通常只是一个库，被加载到发起事务的应用的同一个进程中（而不是单独的服务）。它在事务中跟踪所有的参与者，并在要求它们 准备 之后收集参与者的响应（通过驱动回调），并使用本地磁盘上的日志记录每次事务的决定（提交 / 中止）。

​ 当然，问题还是一样，如果协调者崩溃了，则任何带有 准备了 但未提交事务的参与者都会在疑虑中卡死。

协调者故障的问题

​ 由于协调者崩溃有可能会导致参与者进入存疑状态，在使用两阶段提交时，事务必须在整个存疑期间（可能是永久）持有这些锁。这会导致其他事务阻塞。

​ 唯一的办法是让管理员手动决定提交还是回滚事务。管理员必须检查每个存疑事务的参与者，确定是否有任何参与者已经提交或中止，然后将相同的结果应用于其他参与者。

​ 还有一种方法是启发式决策，允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。（感觉是机器学习那种？）

分布式事务的限制

​ 除了运维和性能，还有几点是分布式事务要考虑的：

• 协调者不一定是高可用的，而且其本身就是一种数据库，很难保证其不失效
• 许多服务器端应用都是使用无状态模式开发的（我理解是不会存在某一时刻该应用会变化啥的），所有持久状态都存储在数据库中，因此具有应用服务器可随意按需添加删除的优点。但是一旦加入协调者，日志成为持久系统状态的关键部分 —— 与数据库本身一样重要，因为协调者日志是为了在崩溃后恢复存疑事务所必需的。这样的应用服务器不再是无状态的了。
• XA必须是所有系统的最小公分母。例如不能检测不同系统间的死锁，无法与 SSI协同工作。

3.3.3 容错共识

​ 共识问题通常是：一个或多个节点可以 提议（propose） 某些值，而共识算法 决定（decides） 采用其中的某个值。

​ 算法一般要保证：

• 一致同意：没有两个节点的决定不同
• 完整性：没有节点决定两次
• 有效性：如果一个节点决定了值 v ，则 v 由某个节点所提议
• 终止：由所有未崩溃的节点来最终决定值

​ 前两个保证了所有人都决定了相同的结果，一旦决定了，你就不能改变主意。有效性 属性主要是为了排除平凡的解决方案。终止 属性形式化了容错的思想，指的是节点必须取得进展。

​ 大多数共识算法假设不存在 拜占庭式错误，克服拜占庭故障，稳健地达成共识是可能的，只要少于三分之一的节点存在拜占庭故障。

共识算法和全序广播

​ 最著名的容错共识算法是 **视图戳复制**（raft，paxos，zab）。它们也是全序广播算法，要求将消息按照相同的顺序，恰好传递一次，准确传送到所有节点。

​ 全序广播相当于重复进行多轮共识（每次共识决定与一次消息传递相对应）：

• 由于 一致同意 属性，所有节点决定以相同的顺序传递相同的消息。
• 由于 完整性 属性，消息不会重复。
• 由于 有效性 属性，消息不会被损坏，也不能凭空编造。
• 由于 终止 属性，消息不会丢失。

​ 视图戳复制，Raft 和 Zab 直接实现了全序广播，因为这样做比重复 一次一值（one value a time） 的共识更高效。

单主复制与共识

纪元编号和法定人数

​ 也就是共识协议通常会为了保证只使用一个领导者，而做出更弱的保证：协议定义了一个 **纪元编号**（例如raft的任期）。保证在该时期，leader唯一。

​ 每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的纪元编号，因此纪元编号是全序且单调递增的。如果两个不同的时代的领导者之间出现冲突（也许是因为前任领导者实际上并未死亡），那么带有更高纪元编号的领导说了算。（懂raft的老熟了- -）

​ 对领导者想要做出的每一个决定，都必须将提议值发送给其他节点，并等待法定人数的节点响应并赞成提案。

​ 也就是有两轮投票

• 选出一位领导者
• 对领导者的提议进行表决

​ 这里说了个我不懂的，两次投票的 法定人群 必须相互 重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举。（但没说咋保证呀）

​ 和2PC的区别是协调者不是由选举产生的，而且 2PC 则要求 所有 参与者都投赞成票，而容错共识算法只需要多数节点的投票。

共识的局限性

- 通常数据库会配置为异步复制模式。在这种配置中发生故障切换时，一些**已经提交的数据可能会丢失** - **共识系统总是需要严格多数来运转**。如果网络故障切断了某些节点同其他节点的连接，则只有多数节点所在的网络可以继续工作，其余部分将被阻塞。 - 共识系统通常**依靠超时来检测失效的节点**。在地理上散布的系统中，经常发生一个节点由于暂时的网络问题，错误地认为领导者已经失效。 - 对网络问题敏感。如果整个网络工作正常，但只有一条特定的网络连接一直不可靠，Raft 可能会进入领导者在两个节点间频繁切换的局面，或者当前领导者不断被迫辞职以致系统实质上毫无进展。

3.3.4 成员与协调服务

​ ZooKeeper 模仿了 Google 的 Chubby 锁服务（chubby？todo！），实现了全序广播，还有一些其他特性。

• 线性一致性的原子操作

  ​ 使用原子 CAS 操作可以实现锁：如果多个节点同时尝试执行相同的操作，只有一个节点会成功。共识协议保证了操作的原子性和线性一致性，即使节点发生故障或网络在任意时刻中断。

• 操作的全序排序

  ​ 当某个资源受到锁或租约的保护时，你需要一个防护令牌来防止客户端在进程暂停的情况下彼此冲突。防护令牌是每次锁被获取时单调增加的数字。ZooKeeper 通过全序化所有操作来提供这个功能，它为每个操作提供一个单调递增的事务 ID（zxid）和版本号（cversion）

• 失效检测

  ​ 当然就是通过心跳啦，客户端在 ZooKeeper 服务器上维护一个长期会话，客户端和服务器周期性地交换心跳包来检查节点是否还活着。

• 变更通知

  ​ 客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。因此，客户端可以知道另一个客户端何时加入集群（基于新客户端写入 ZooKeeper 的值），或发生故障（因其会话超时，而其临时节点消失）。通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

将工作分配给节点

​ Zookeeper和Chubby可以作为几个进程或服务的调度，还有就是分区资源的管理（数据库，消息流，文件存储等）。通过在 ZooKeeper 中明智地使用原子操作，临时节点与通知来实现。

​ ZooKeeper 在固定数量的节点（通常是三到五个）上运行，并在这些节点之间执行其多数票，同时支持潜在的大量客户端。因此，ZooKeeper 提供了一种将协调节点（共识，操作排序和故障检测）的一些工作 “外包” 到外部服务的方式。

服务发现

​ ZooKeeper、etcd 和 Consul 也经常用于服务发现 —— 也就是找出你需要连接到哪个 IP 地址才能到达特定的服务。可以配置你的服务，使其在启动时注册服务注册表中的网络端点，然后可以由其他服务找到它们。

​ 在共识系统中，也会用到服务发现，支持只读缓存副本。这些副本异步接收共识算法所有决策的日志，但不主动参与投票。因此，它们能够提供不需要线性一致性的读取请求。

成员资格服务

​ 成员资格服务确定哪些节点当前处于活动状态并且是集群的活动成员。

​