分布式数据

《设计数据密集型应用》一书第二部分，分布式数据中涉及到了数据的复制,如何分区，分布式事务，讨论了分布式系统的麻烦及解决方案，一致性与共识的认知。

复制

复制代表着通过网络连接的多台机器上保留着相同的副本。一般情况下使用复制功能，我们更期望的是：

1.让用户在地理上更接近数据(从而减少延迟)

2.系统的一部分出现故障，系统也能继续工作(提高可用性)

3.伸缩可以接受读请求的机器数量(提高吞吐量)

如果复制的数据不会随着时间而改变，那复制就变得很简单：将数据复制到每节点，仅需一次就好了。但复制的困难往往出现在处理复制数据的变更。

本小结将会讨论三种流行的变更复制算法：单领导者（single leader，单主），多领导者（multi leader，多主） 和 无领导者（leaderless，无主）。几乎所有分布式数据库都使用这三种方法之一。

当然，在复制时也同样进行很多权衡，使用同步复制还是异步复制？如何处理失败的副本？

领导者与追随者

存储了数据拷贝的每个节点被称为**副本(replica)**。当多个副本存在时就有出现一个问题：如何确保所有数据都存在副本上？

每一次向数据库的写入操作都需要传播到所有副本上，否则副本数据就不能保持一致。

基于领导者的复制（leader-based replication） （也称 主动/被动（active/passive） 复制或 主/从（master/slave） 复制）

1.在多个副本中选一个副本指定其为领导者(leader),有时也被称为主库(master|primary)。当客户端发送写入请求时，它必须将请求发送给领导者，其会将新数据写入其本地存储。

2.其他副本被称为 追随者（followers），亦称为 只读副本（read replicas）、从库（slaves）、备库（ secondaries） 或 热备（hot-standby）1。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为 复制日志（replication log） 或 变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照与领导者相同的处理顺序来进行所有写入。

3.当客户想要从数据库中读取数据时，它可以向领导者或任一追随者进行查询。但只有领导者才能接受写入操作（从客户端的角度来看从库都是只读的）。

image-20230815174416749

同步复制和异步复制

复制系统的一个重要细节是：复制是 同步（synchronously） 发生的还是 异步（asynchronously） 发生的。

通常情况下复制的速度相当快：大多数数据库系统能在一秒内完成从库的同步，但它们不能提供复制用时的保证。在某些情况下从库可能落后主库几分钟或者更久：比如从库正在从故障中恢复，系统正在最大容量附近运行，或者当节点间存在网络问题时。

同步复制的优点：从库能保证与主库一致的最新数据副本。如果主库突然失效，我们依然能在从库上找到这些数据。

同步复制的缺点：如果同步从库没有响应(比如从库已经崩溃，或者网络出现故障)，主库就无法处理写入操作。主库会阻止所有写入，一直到从库再次可用。

所以将所有从库都设置为同步是不切实际的。因为任何一个节点的中断都会影响到整个系统，这对高可用来说是致命的。

在现实使用场景，如果在数据库上启用同步复制，通常指其中一个从库是同步的，其他从库是异步的。如果该同步从库变得不可用或缓慢，则将一个异步从库改为同步运行。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。 这种配置有时也被称为 半同步（semi-synchronous）。

通常情况下，基于领导者的复制都配置为完全异步。在这种情况下，如果主库失效且不可恢复，则任何尚未复制给从库的写入都会丢失。这意味着即使已经向客户端确认成功，写入也不能保证是 持久（Durable） 的。然而，一个完全异步的配置也有优点：即使所有的从库都落后了，主库也可以继续处理写入。

设置新从库

有时候需要临时设置一个新的从库，可能是负载更大需要增加副本的数量，或者替换掉集群中长期失败的节点。

设置新从库会有如下流程：

  1. 在某个时刻获取主库的一致性快照（如果可能，不必锁定整个数据库）。大多数数据库都具有这个功能，因为它是备份必需的。对于某些场景，可能需要第三方工具，例如用于 MySQL 的 innobackupex。
  2. 将快照复制到新的从库节点。
  3. 从库连接到主库，并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。该位置有不同的名称，例如 PostgreSQL 将其称为 日志序列号（log sequence number，LSN），MySQL 将其称为 二进制日志坐标（binlog coordinates）。
  4. 当从库处理完快照之后积累的数据变更，我们就说它 赶上（caught up） 了主库，现在它可以继续及时处理主库产生的数据变化了。

建立从库这个步骤需要根据不同的数据来进行配置，有些可能是自动化的，有些则需要管理手动操作。

处理节点宕机

从库失效：追赶恢复

在宿主机的本地磁盘中，会记录者从库收到的数据变更日志，如果从库崩溃并重新启动。从库可以从日志中得知，在发生故障之前处理的最后一个事务。因此，从库可以连接到主库，并请求在从库断开期间发生的所有数据变更。当应用完所有这些变更后，它就赶上了主库，并可以像以前一样继续接收数据变更流。

主库失效：故障切换

主库失效处理起来相当棘手：其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更。这个过程被称为 故障切换（failover）。

自动化切换：

1.确认主库失效。可以使用超时机制来确定主库是否挂了，类似于心跳包。

2.选举：剩余副本通过共识算法选举出一个新的主库。(也可以事先配置控制节点来指定新的主库)

3.重新配置系统以启用新的主库。如果旧主库恢复，让它成为一个从库。

故障自动切换过程中会相当麻烦且繁琐，不少运维团队更愿意手动执行故障切换。

复制日志的实现

1.基于语句的复制

主库记录它执行的每个写入请求(语句)并将该语句日志发送给从库。每个从库解析并执行SQL语句，就像直接从客户端收到一样。

但是下列问题会让第一种实现变得数据不一致：

  • 任何调用 非确定性函数（nondeterministic） 的语句，可能会在每个副本上生成不同的值。例如，使用 NOW() 获取当前日期时间，或使用 RAND() 获取一个随机数。
  • 如果语句使用了 自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。当有多个并发执行的事务时，这可能成为一个限制。
  • 有副作用的语句（例如：触发器、存储过程、用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定性的。

通常情况下都不会选用这种复制方法

2.传输预写式日志（WAL）

  • 对于日志结构存储引擎（请参阅 “SSTables 和 LSM 树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
  • 对于覆写单个磁盘块的 B 树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘之外，主库还可以通过网络将其发送给从库。

通过使用这个日志，从库可以构建一个与主库一模一样的数据结构拷贝。

缺点：日志记录的数据非常底层，可能存在版本不兼容。会对运维团队造成麻烦。

3.逻辑日志复制(基于行)

对复制和存储引擎使用不同的日志格式，这样可以将复制日志从存储引擎的内部实现中解耦出来。这种复制日志被称为逻辑日志（logical log），以将其与存储引擎的（物理）数据表示区分开来。

关系数据库的逻辑日志通常是以行的粒度来描述对数据库表的写入记录的序列：

  • 对于插入的行，日志包含所有列的新值。
  • 对于删除的行，日志包含足够的信息来唯一标识被删除的行，这通常是主键，但如果表上没有主键，则需要记录所有列的旧值。
  • 对于更新的行，日志包含足够的信息来唯一标识被更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

修改多行的事务会生成多条这样的日志记录，后面跟着一条指明事务已经提交的记录。 MySQL 的二进制日志(当配置为使用基于行的复制时)使用了这种方法。

4.基于触发器的复制

有一些工具可以通过读取数据库日志，使其他应用程序可以使用数据。或者使用关系数据库自带的功能：触发器和存储过程。

触发器允许将数据更改(写入事务)发生时自动执行自定义应用程序代码注册早数据库系统中，触发器可以将更改记录到一个单独的表中，然后再使用外部应用程序读这个表，再加上一点自定义的逻辑就可以将数据复制到另一个系统中去。

基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库内置的复制更容易出错，也有很多限制。然而由于其灵活性，它仍然是很有用的。

复制延迟问题

基于领导者的复制要求所有写入都由单个节点处理，但只读查询可以由任何一个副本来处理。所以对于读多写少的场景（Web 上的常见模式），一个有吸引力的选择是创建很多从库，并将读请求分散到所有的从库上去。这样能减小主库的负载，并允许由附近的副本来处理读请求。

在这种读伸缩（read-scaling）的体系结构中，只需添加更多的从库，就可以提高只读请求的服务容量。但是，这种方法实际上只适用于异步复制 —— 如果尝试同步复制到所有从库，则单个节点故障或网络中断将导致整个系统都无法写入。而且节点越多越有可能出现个别节点宕机的情况，所以完全同步的配置将是非常不可靠的。

但是异步会有一个问题，如果从库落后，会导致在某一个时间段存在数据不一致的问题。在正常操作中，复制延迟在实际中并不显眼，但是在极端情况下延迟会在几秒到几分钟钟不等。

这会造成三种情况：

1.读已之写

如果用户写入后马上查看数据，新数据可能没来得及到达副本，对于用户而言，看起来好像是刚提交的数据丢失了。

在这种情况下，我们需要 写后读一致性（read-after-write consistency），也称为 读己之写一致性（read-your-writes consistency）。这是一个保证，如果用户重新加载页面，他们总会看到他们自己提交的任何更新。它不会对其他用户的写入做出承诺：其他用户的更新可能稍等才会看到。它保证用户自己的输入已被正确保存。

如何在基于领导者的复制系统中实现写后读一致性？文中提供了几种解决：

1.1对于可能用户修改过的内容，总是从主库读取。这就要求得有办法不通过实际的查询就可以知道用户是否修改了某些东西。例如：总是从主库读取用户自己的档案，如果要读取其他用户的档案就去从库。

1.2通过跟踪上次更新时间，在上次更新后的一分钟内从主库读。还可以监控从库的复制延迟，防止向任何滞后主库超过一分钟的从库发出查询。

1.3客户端记录最近一次写入的时间戳，系统需要确保从库在处理该用户的读取请求时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从库读取，或者等待从库追赶上来。但是使用这个方法的时候要注意：时钟同步变得至关重要。

但是这种情况下记住用户上次更新时间戳的方法变得更加困难，因为一个设备上运行的程序不知道另一个设备上发生了什么。需要对这些元数据进行中心化的存储。

1.4如果副本分布在多个数据中心，还会变得更加复杂，因为任何需要主库提供服务的请求都必须路由到包含主库的数据中心。

如果副本分布在不同的数据中心，很难保证来自不同设备的连接会路由到同一数据中心。

2.单调读

如果先查询了一个延迟很小的从库，然后再查询一个延迟较大的从库。(数据可能也会存在差异，延迟较小的从库上存在，延迟较大的从库上可能不存在)这会让用户非常疑惑。

单调读（monotonic reads）可以保证这种异常不会发生。这是一个比 强一致性（strong consistency） 更弱，但比 最终一致性（eventual consistency） 更强的保证。当读取数据时，你可能会看到一个旧值；单调读仅意味着如果一个用户顺序地进行多次读取，则他们不会看到时间回退，也就是说，如果已经读取到较新的数据，后续的读取不会得到更旧的数据。

实现单调读的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取）。例如，可以基于用户 ID 的散列来选择副本，而不是随机选择副本。但是，如果该副本出现故障，用户的查询将需要重新路由到另一个副本。

要防止某些分区的复制速度慢于其他分区造成的异常状态，需要另一种类型保证：一致前缀读（consistent prefix reads），如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

一种解决方案是，确保任何因果相关的写入都写入相同的分区，但在一些应用中可能无法高效地完成这种操作。

复制延迟最终解决方案：

  • 在应用程序出做处理，但是容易出错且复杂。
  • 使用分布式事务，但是不是所有数据库都支持。

多主复制

基于领导者的复制有一个主要的缺点：只有一个主库，而且所有的写入都必须通过它 4。如果出于任何原因（例如和主库之间的网络连接中断）无法连接到主库， 就无法向数据库写入。

基于领导者的复制模型的自然延伸是允许多个节点接受写入。复制仍然以同样的方式发生：处理写入的每个节点都必须将该数据变更转发给所有其他节点。我们将其称之为 多领导者配置（multi-leader configuration，也称多主、多活复制，即 master-master replication 或 active/active replication）。在这种情况下，每个主库同时是其他主库的从库。

多主复制的应用场景

单个数据中心使用多个主库的配置没有什么意义，复杂性已经超过了能带来的好处。

假设你有一个数据库，副本分散在好几个不同的数据中心，如果使用常规的基于领导者的复制设置，主库必须位于其中一个数据中心，且所有写入都必须经过该数据中心。

但是如果使用多主配置，这样每个数据中心都有一个主库。在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。

多主配置的优点：

1.在多个数据中心的情况下，多主配置的性能可能要好于单主配置。

2.在多主配置中，每个数据中心可以独立于其他数据中心继续运行，并且当发生故障的数据中心归队时，复制会自动赶上。从这一点来说多主配置的可用性要高于单主配置。

3.采用异步复制功能的多主配置通常能更好地承受网络问题：临时的网络中断并不会妨碍正在处理的写入。

缺点：

1.两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的。

2.由于多主复制在许多数据库中都属于改装的功能，所以常常存在微妙的配置缺陷，且经常与其他数据库功能之间出现意外的反应。比如自增主键、触发器、完整性约束等都可能会有麻烦。因此，多主复制往往被认为是危险的领域，应尽可能避免。

多主复制的另一种适用场景是：应用程序在断网之后仍然需要继续工作。

在这种情况下，每个设备都有一个充当主库的本地数据库（它接受写请求），并且在所有设备上的日历副本之间同步时，存在异步的多主复制过程。复制延迟可能是几小时甚至几天，具体取决于何时可以访问互联网。

从架构的角度来看，这种设置实际上与数据中心之间的多主复制类似，每个设备都是一个 “数据中心”，而它们之间的网络连接是极度不可靠的。从历史上各类日历同步功能的破烂实现可以看出，想把多主复制用好是多么困难的一件事。

协同编辑场景下也适合

当一个用户编辑文档时，所做的更改将立即应用到其本地副本（Web 浏览器或客户端应用程序中的文档状态），并异步复制到服务器和编辑同一文档的任何其他用户。

但是依旧要保证不会发生编辑冲突的问题，还需要应用文档的锁，然后用户才能对其编辑。如果另一个用户想要编辑同一个文档，他们首先必须等到第一个用户提交修改并释放锁定。这种协作模式相当于主从复制模型下在主节点上执行事务操作。

处理写入冲突

多主复制的最大问题是可能发生写冲突，这意味着需要解决冲突。

原则上，可以使冲突检测同步 - 即等待写入被复制到所有副本，然后再告诉用户写入成功。但是，通过这样做，你将失去多主复制的主要优点：允许每个副本独立地接受写入。如果你想要同步冲突检测，那么你可能不如直接使用单主复制。

解决方案：

1.避免冲突，如果应用程序可以确保特定记录的所有写入都通过同一个主库，那么冲突就不会发生。例如，在一个用户可以编辑自己数据的应用程序中，可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的主库进行读写。不同的用户可能有不同的 “主” 数据中心（可能根据用户的地理位置选择），但从任何一位用户的角度来看，本质上就是单主配置了。

但是也会出现另一种情况：因为某个数据中心出现故障，需要将流量重新路由到另一个数据中心，在这种情况下，无法避免冲突。必须处理不同主库同时写入的可能性。

2.收敛至一致的状态，这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。

  • 给每个写入一个唯一的 ID（例如时间戳、长随机数、UUID 或者键和值的哈希），挑选最高 ID 的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为 最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失。
  • 为每个副本分配一个唯一的 ID，ID 编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
  • 以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们。
  • 用一种可保留所有信息的显式数据结构来记录冲突，并编写解决冲突的应用程序代码（也许通过提示用户的方式，类似Git？）。

解决冲突的最合适的方法可能取决于应用程序：

写时执行：只要数据库检测到复制更改日志中存在冲突，就调用冲突处理程序。

读时执行：当检测到冲突时，所有冲突写入被存储。下一次读取数据时，会将这些多个版本的数据返回给应用程序。应用程序可以提示用户或自动解决冲突，并将结果写回数据库。

自动冲突解决会随着时间推移变得越来越复杂，自定义的代码也可能出错。

多主复制拓扑

复制拓扑（replication topology）用来描述写入操作从一个节点传播到另一个节点的通信路径。比如主库1将所有的写入发送到主库2中。

常见的三种拓扑：

1.全部到全部(all-to-all)

环形拓扑，其中每一个节点都从一个节点接受写入，并将这些写入(及自己的写入)全都转发给另外一个节点。

星型形状，一个指定的根节点将写入转发给所有其他节点。星型拓扑可以推广到树。

在环形和星形拓扑中，写入可能需要在到达所有副本之前通过多个节点。因此，节点需要转发从其他节点收到的数据更改。为了防止无限复制循环，每个节点被赋予一个唯一的标识符，并且在复制日志中，每次写入都会使用其经过的所有节点的标识符进行标记。当一个节点收到用自己的标识符标记的数据更改时，该数据更改将被忽略，因为节点知道它已经被处理过。

如果只有一个节点发生故障，则可能会中断其他节点之间的复制消息流，导致它们无法通信，除非节点被修复。

也可以重新配置为跳过发生故障的节点，但是大多数部署中，这种操作必须手动完成。

更密集连接的拓扑结构（例如全部到全部）的容错性更好，因为它允许消息沿着不同的路径传播，可以避免单点故障。

可能出现的问题：

多主复制时使用All-to-all 可能会因为网络拥塞，不同主库可能写入顺序不一致。更新取决于先前的插入，所以我们需要确保所有节点先处理插入，然后再处理更新。

要正确的排序这些时间，可以使用**版本向量(**version vectors)技术

注意：很多多主复制系统中的冲突检测技术实现的并不好，如果你正在使用基于多主复制的系统，那么你应该多了解这些问题，仔细阅读文档，并彻底测试你的数据库，以确保它确实提供了你想要的保证。

无主复制

一些数据存储系统采用不同的方法，放弃主库的概念，允许任何副本直接接受来自客户端的写入。最早的一些的复制数据系统是 无主的（leaderless）。

在一些无主复制的实现中，客户端直接将写入发送到几个副本中，而另一些情况下，由一个 协调者（coordinator） 节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。我们将会看到，这种设计上的差异对数据库的使用方式有着深远的影响。

当节点故障时写入数据库

如果是基于领导者的配置中，从库中某个副本不可用时，要继续处理写入，则可能需要执行故障切换。

但是在无主配置中，不存在故障转移这种情况。某个副本在不接受写入时，会直接忽略错过写入的事实。这种情况下用户从这个副本上拿取数据可能会拿到过时的值。

所以为了解决这个问题，当一个客户端从数据库中读取数据时，它不仅仅把它的请求发送到一个副本：读请求将被并行地发送到多个节点。客户可能会从不同的节点获得不同的响应，即来自一个节点的最新值和来自另一个节点的陈旧值。版本号将被用于确定哪个值是更新的。

两种机制保证不可用节点恢复后，使它的数据与最新的数据保持一致：

  • 读修复（Read repair）：当客户端并行读取多个节点时，它可以检测到任何陈旧的响应。如果发现具有陈旧值，将新值写回到该副本。这种方法适用于读频繁的值。
  • 反熵过程（Anti-entropy process）：此外，一些数据存储具有后台进程，该进程不断查找副本之间的数据差异，并将任何缺少的数据从一个副本复制到另一个副本。与基于领导者的复制中的复制日志不同，此反熵过程不会以任何特定的顺序复制写入，并且在复制数据之前可能会有显著的延迟。

如果没有反熵过程，很少被读取的值可能会从某些副本中丢失，从而降低了持久性，因为只有在应用程序读取值时才执行读修复。

在Dynamo风格的数据库中，需要配置副本数量(n个)以及每个写入必须由 w 个节点确认才能被认为是成功的，并且至少为每个读取查询 r 个节点。通常情况下这样设计是为了数学中的公式推理。

image-20230817104712279

尽管法定人数似乎保证读取返回最新的写入值，但在实践中并不那么简单。 Dynamo 风格的数据库通常针对可以忍受最终一致性的用例进行优化。你可以通过参数 w 和 r 来调整读取到陈旧值的概率，但把它们当成绝对的保证是不明智的。

无主复制的系统中，没有固定的写入顺序会让监控变得更加困难。而且，如果数据库只使用读修复（没有反熵过程），那么对于一个值可能会有多陈旧其实是没有限制的 - 如果一个值很少被读取，那么由一个陈旧副本返回的值可能是古老的(甚至几乎是废弃的)。

数据库冲突会出现以下几种情况：

最后写入胜利(丢弃并发写入)

实现最终收敛的一种方法是声明每个副本只需要存储 “最近” 的值，并允许 “更旧” 的值被覆盖和抛弃。然后，只要我们有一种明确的方式来确定哪个写是 “最近的”，并且每个写入最终都被复制到每个副本，那么复制最终会收敛到相同的值。

可以为每个写入附加一个时间戳，然后挑选最大的时间戳作为 “最近的”，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为 最后写入胜利（LWW, last write wins）。

LWW 实现了最终收敛的目标，但以 持久性 为代价：如果同一个键有多个并发写入，即使它们反馈给客户端的结果都是成功的（因为它们被写入 w 个副本），也只有一个写入将被保留，而其他写入将被默默地丢弃。

在类似缓存的一些情况下，写入丢失可能是可以接受的。但如果数据丢失不可接受，LWW 是解决冲突的一个很烂的选择。

在数据库中使用 LWW 的唯一安全方法是确保一个键只写入一次，然后视为不可变，从而避免对同一个键进行并发更新。

什么是并发性？

如果两个操作“同时”发生，似乎应该成为并发。但是实际上由于分布式系统中的时钟问题，很难判断两个事件是否是同时发生的。

如果两个操作都意识不到对方的存在，就成为这两个操作并发。

在计算机系统中，即使光速原则上允许一个操作影响另一个操作，但两个操作也可能是 并发的。例如，如果网络缓慢或中断，两个操作间可能会出现一段时间间隔，但仍然是并发的，因为网络问题阻止一个操作意识到另一个操作的存在。

本章小结

复制的目的：

高可用性，无论是数据中心，还是服务器宕机时，都能保持系统正常运行;允许程序在网络中断时继续工作;将数据存放在离用户相对较近的地理位置;可伸缩性，通过副本读的方式，可以处理比单机更大的读取量。

复制的三种主要方法：

单主复制：客户端将所有写入操作发送到单个节点（主库），该节点将数据更改事件流发送到其他副本（从库）。读取可以在任何副本上执行，但从库的读取结果可能是陈旧的。

多主复制：客户端将每个写入发送到几个主库节点之一，其中任何一个主库都可以接受写入。主库将数据更改事件流发送给彼此以及任何从库节点。

无主复制：客户端将每个写入发送到几个节点，并从多个节点并行读取，以检测和纠正具有陈旧数据的节点。

上述复制方法都有不同的优点及缺点，在不同场景下要考虑好使用那种复制方法。

由于复制延迟引起的效应，文中也记录了一些应用程序在复制延迟时的行为一致性模型。

写后读一致性：用户应该总是能看到自己提交的数据。

单调读：用户在看到某个时间点的数据后，不应该看到这个数据在时间点前的情况。

一致前缀读：用户应该看到数据处于一种具有因果意义的状态：例如，按正确的顺序看到一个问题和对应的回答。

最后本章还讲述了多主复制和无主复制方法遇到的并发问题，还记录了通过合并并发更新来解决冲突。

分区

对于非常大的数据集，或非常高的吞吐量，我们需要将数据分区（partitions），也称为 分片（sharding）。

每个分区都是自己的小型数据库，尽管数据库可能支持同时进行多个分区的操作。

分区主要是为了可伸缩性，不同的分区可以放在不共享集群中的不同节点上。因此，大数据集可以分布在多个磁盘上，并且查询负载可以分布在多个处理器上。

对于在单个分区上运行的查询，每个节点可以独立执行对自己的查询，因此可以通过添加更多的节点来扩大查询吞吐量。大型，复杂的查询可能会跨越多个节点并行处理，尽管这也带来了新的困难。

分区和复制

分区通常和复制结合使用，使每个分区的副本存储在多个节点上。这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。

一个节点可能存储多个分区。如果使用主从复制模型则每个分区的主库被分配给一个节点，从库被分配给其他节点。所以每个节点可能是某些分区的主库，同时是其他分区的从库。

大多数情况下，分区方案的选择与复制方案的选择是独立的。

键值数据的分区

分区的目的是将数据和查询负载均匀分布在各个节点上，理论上如果每个节点公平分享数据和负载，那么处理的数据量和读写吞吐量应该是呈N倍(节点数量)增长。

但是如果分区不是公平的，一些分区有比其他分区更多的数据或查询，这被称为偏斜。数据偏斜会导致分区效率下降很多，极端情况下所有的负载可能压在一个分区上，瓶颈落在一个节点上。不均衡的高负载分区被称为热点。

避免热点最简单的方法是将记录随机分配给节点。这将在所有节点上平均分配数据，但是它有一个很大的缺点：当你试图读取一个特定的值时，你无法知道它在哪个节点上，所以你必须并行地查询所有的节点。

Key Range 分区的缺点是某些特定的访问模式会导致热点。 如果主键是时间戳，则分区对应于时间范围，例如，给每天分配一个分区。 不幸的是，由于我们在测量发生时将数据从传感器写入数据库，因此所有写入操作都会转到同一个分区（即今天的分区），这样分区可能会因写入而过载，而其他分区则处于空闲状态。

为了避免传感器数据库中的这个问题，需要使用除了时间戳以外的其他东西作为主键的第一个部分。 例如，可以在每个时间戳前添加传感器名称，这样会首先按传感器名称，然后按时间进行分区。 假设有多个传感器同时运行，写入负载将最终均匀分布在不同分区上。 现在，当想要在一个时间范围内获取多个传感器的值时，你需要为每个传感器名称执行一个单独的范围查询。

根据键的散列分区

很多分布式数据存储使用散列函数来确定给定键的分区。

一个好的散列函数可以将偏斜的数据均匀分布。假设你有一个 32 位散列函数，无论何时给定一个新的字符串输入，它将返回一个 0 到 232 -1 之间的 “随机” 数。即使输入的字符串非常相似，它们的散列也会均匀分布在这个数字范围内。

按哈希键分区

这种技术擅长在分区之间公平地分配键。分区边界可以是均匀间隔的，也可以是伪随机选择的（在这种情况下，该技术有时也被称为 一致性哈希，即 consistent hashing）。

不幸的是，通过使用键散列进行分区，我们失去了键范围分区的一个很好的属性：高效执行范围查询的能力。曾经相邻的键现在分散在所有分区中，所以它们之间的顺序就丢失了。

但是有一种折衷的策略，可以由多个列组成的复合主键来声明。键中只有第一列会作为散列的依据，而其他列则被用作SSTables 中排序数据的连接索引。尽管查询无法在复合主键的第一列中按范围扫表，但如果第一列已经指定了固定值，则可以对该键的其他列执行有效的范围扫描。

组合索引方法为一对多关系提供了一个优雅的数据模型。可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。不同的用户可以存储在不同的分区上，对于每个用户，更新按时间戳顺序存储在单个分区上。

负载偏斜与热点消除

哈希分区可以帮助减少热点。但是，它不能完全避免它们：在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。

大多数数据系统都无法自动补偿这种高度偏斜的负载，因此将减少偏斜的责任放在应用程序上。例如，如果一个主键被认为是非常火爆的，一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为 100 种不同的主键，从而存储在不同的分区中。

主键分割以后，任何读取都必须要做额外的工作，因为他们必须从所有 100 个主键分布中读取数据并将其合并。此技术还需要额外的记录：只需要对少量热点附加随机数；对于写入吞吐量低的绝大多数主键来说是不必要的开销。因此，你还需要一些方法来跟踪哪些键需要被分割。

分区与次级索引

上文中内容都依赖于键值数据模型。如果只通过主键访问记录，我们可以从该键确定分区，并使用它来将读写请求路由到负责该键的分区。

如果涉及次级索引，情况就会变得更加复杂。次级索引通常并不能唯一地标识记录，而是一种搜索记录中出现特定值的方法：查找用户的所有操作，查找包含某个关键词的文章等等。

次级索引是关系性数据库等基础，并且在文档数据库中也很普遍。许多键值存储为了减少实现的复杂度而放弃了次级索引，但是一些（如 Riak）已经开始添加它们，因为它们对于数据模型实在是太有用了。并且次级索引也是 Solr 和 Elasticsearch 等搜索服务器的基石。

次级索引的问题是它们不能整齐地映射到分区。有两种用次级索引对数据库进行分区的方法：

基于文档的次级索引进行分区

在这种索引方法中，每个分区是完全独立的：每个分区维护自己的次级索引，仅覆盖该分区中的文档。它不关心存储在其他分区的数据。无论何时你需要写入数据库（添加，删除或更新文档），只需处理包含你正在编写的文档 ID 的分区即可。出于这个原因，文档分区索引 也被称为 本地索引。

注意：除非对文档ID做了特别的处理，否则不能按照某一特性将对象放在同一个分区中。

这种查询分区数据库的方法有时被称为 分散 / 聚集（scatter/gather），并且可能会使次级索引上的读取查询相当昂贵。即使并行查询分区，分散 / 聚集也容易导致尾部延迟放大。

基于关键词(Term)的次级索引进行分区

我们可以构建一个覆盖所有分区数据的 全局索引，而不是给每个分区创建自己的次级索引（本地索引）。但是，我们不能只把这个索引存储在一个节点上，因为它可能会成为瓶颈，违背了分区的目的。全局索引也必须进行分区，但可以采用与主键不同的分区方式。

我们将这种索引称为 关键词分区（term-partitioned），因为我们寻找的关键词决定了索引的分区方式。例如，一个关键词可能是：color:red。关键词（Term） 这个名称来源于全文搜索索引（一种特殊的次级索引），指文档中出现的所有单词。

通过关键词本身或它的散列进行索引分区。根据关键词本身来分区对于范围扫描非常有用，而关键词的哈希分区提供了负载均衡的能力。

关键词分区的全局索引优于文档分区索引的地方点是它可以使读取更有效率：不需要 分散 / 收集 所有分区，客户端只需要向包含关键词的分区发出请求。

全局索引的缺点在于写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区（文档中的每个关键词可能位于不同的分区或者不同的节点上） 。

注意，在关键词分区索引中，需要跨分区的分布式事务，并不是所有数据库都支持。

实际中，全局次级索引的更新通常是异步的，如果在写入之后不久读取索引，刚才所做的更改可能尚未反映在索引中。

分区再平衡

随着时间的推移，数据库会有各种变化，比如查询吞吐量增加，数据集大小增加，机器出故障。为了应用这些变化，所以我们需要添加更多的CPU来处理吞吐量;增加更多的磁盘和RAM来存储;需要其他的机器接管故障的机器。

这些更改都需要数据和请求从一个节点移动到另一个节点。负载从集群中的一个节点向另一个节点移动的过程称为 再平衡。

无论使用哪种分区方案，再平衡通常都要满足一些最低要求：

  • 再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
  • 再平衡发生时，数据库应该继续接受读取和写入。
  • 节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘 I/O 负载。

再平衡策略

1.固定数量分区：创建比节点更多的分区，并为每个节点分配多个分区。如果一个新节点添加到集群中，新节点可以从当前每一个节点中窃取一些分区，直至分区再次公平分配。

只有分区在节点之间移动。分区数量不会改变，所指定的分区也不会改变。唯一改变的是分区所在的节点。这种变更并不是即时的 — 在网络上传输大量的数据需要一些时间 — 所以在传输过程中，原有分区仍然会接受读写操作。

原则上，你甚至可以解决集群中的硬件不匹配问题：通过为更强大的节点分配更多的分区，可以强制这些节点承载更多的负载。

许多固定分区数据库选择不实施分区分割。因此，一开始配置的分区数就是你可以拥有的最大节点数量，所以你需要选择足够多的分区以适应未来的增长。但是，每个分区也有管理开销，所以选择太大的数字会适得其反。

如果数据的大小难以估量，选择正确的分区是很困难的。如果分区非常大，再平衡和从节点故障恢复变得昂贵。但是，如果分区太小，则会产生太多的开销。当分区大小 “恰到好处” 的时候才能获得很好的性能，如果分区数量固定，但数据量变动很大，则难以达到最佳性能。

2.动态分区：

按键的范围进行分区的数据库会动态创建分区。当分区增长到超过配置的大小时，会被分成两个分区,那么每个分区约占一半的数据。相对应的，如果数据太小缩至某个阈值以下，则可以将其与相邻分区合并。

每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。

优点：动态分区会让分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，开销也会变得更少；如果有大量的数据，每个分区的大小被限制在一个可配置的最大值。

一些数据库会使用预分割初始化分区，在这种情况下要提前预知如何进行分配。

动态分区不仅适用于数据的范围分区，而且也适用于散列分区。

3.按节点比例分区

通过动态分区，分区的数量与数据集的大小成正比，因为拆分和合并过程将每个分区的大小保持在固定的最小值和最大值之间。另一方面，对于固定数量的分区，每个分区的大小与数据集的大小成正比。在这两种情况下，分区的数量都与节点的数量无关。

分区数与节点数成正比：每个节点具有固定数量的分区。在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变，但是当增加节点数时，分区将再次变小。由于较大的数据量通常需要较大数量的节点进行存储，因此这种方法也使每个分区的大小较为稳定。

当一个新节点加入集群时，随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。随机化可能会产生不公平的分割，但是平均在更大数量的分区上时，新节点最终从现有节点获得公平的负载份额。

随机选择分区边界要求使用基于散列的分区。

请求路由

服务发现可以解决客户端请求时需要访问哪个IP地址和端口的问题。

一般有几种方案：

1.允许客户端访问所有节点。（例如，通过 循环策略的负载均衡，即 Round-Robin Load Balancer）。如果访问的节点恰好有请求的分区，则直接处理请求。如果没有则转发到存在分区的节点上，接收回复并传递给客户端。

2.通过一个路由层处理请求的节点，并相应转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。

3.客户端知道分区和节点的分配策略，客户端做逻辑判断，直接访问节点。

许多分布式数据系统都依赖于一个独立的协调服务，比如每个节点在中间件服务中注册自己，然后依靠中间件维护分区到节点的可靠映射。

本章小结

分区这章内容较多，但是主要了解将大数据集划分成更小的子集的不同方法。

分区的目标是在多台机器上均匀分布数据和查询负载，避免出现热点（负载不成比例的节点）。

文中记录了两种分区方法：

1.键范围分区：通过有序的键，分区拥有从某个最小值到某个最大值的所有键。排序可以进行有效的范围查询,但是如果应用程序经常访问相邻的键，则存在热点的风险。在这种方法中，当分区变得太大时，通常将分区分成两个子分区来动态地重新平衡分区。

2.散列分区:散列函数应用于每个键，分区拥有一定范围的散列。这会让查询效率变低，但是可以更均匀地分配负载。通过散列进行分区时，通常先提前创建固定数量的分区，为每个节点分配多个分区，并在添加或删除节点时将整个分区从一个节点移动到另一个节点。也可以使用动态分区。

当然，使用复合主键也行：使用键的一部分来标识分区，而使用另一部分作为排序顺序。

还讨论了分区和次级索引之间的相互作用。次级索引也需要分区，有两种方法：

  • 基于文档分区（本地索引），其中次级索引存储在与主键和值相同的分区中。这意味着只有一个分区需要在写入时更新，但是读取次级索引需要在所有分区之间进行分散 / 收集。
  • 基于关键词分区（全局索引），其中次级索引存在不同的分区中。次级索引中的条目可以包括来自主键的所有分区的记录。当文档写入时，需要更新多个分区中的次级索引；但是可以从单个分区中进行读取。

最后讨论了通过路由将查询分配到分区的技术。

事务

事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。从概念上讲，事务中的所有读写操作被视作单个操作来执行：整个事务要么成功 提交（commit），要么失败 中止（abort）或 回滚（rollback）。如果失败，应用程序可以安全地重试。对于事务来说，应用程序的错误处理变得简单多了，因为它不用再担心部分失败的情况了，即某些操作成功，某些失败（无论出于何种原因）。

事务的概念

ACID

ACID 代表 原子性（Atomicity），一致性（Consistency），隔离性（Isolation） 和 持久性（Durability）。

原子性

ACID的原子性并不是关于并发的。它的原子性是想表达在写入出错，例如应用程序崩溃，网络中断等情况。那么这些写操作被归纳为一个原子事物中，这个事务由于错误不能完成，则该事务将被中止，并且数据库必须丢弃或撤消该事务中迄今为止所做的任何写入。

如果没有原子性，在多处更改进行到一半时发生错误，很难知道哪些更改已经生效，哪些没有生效。该应用程序可以再试一次，但冒着进行两次相同变更的风险，可能会导致数据重复或错误的数据。原子性简化了这个问题：如果事务被 中止（abort），应用程序可以确定它没有改变任何东西，所以可以安全地重试。

ACID原子性的定义特征是：能够在错误时中止事务，丢弃该事物进行的所有写入变更的能力。

一致性

ACID 一致性的概念是，对数据的一组特定约束必须始终成立，即 不变式（invariants）。一致性的这种概念应该取决于应用程序来定义，数据库只管存储。

原子性、隔离性和持久性是数据库的属性，而一致性（在 ACID 意义上）是应用程序的属性。应用可能依赖数据库的原子性和隔离性来实现一致性，但这并不仅取决于数据库。因此，字母 C 不属于 ACID 1。

隔离性

数据库会被多个客户端同时访问，如果它们访问相同的数据记录，可能会遇到并发问题。

ACID 意义上的隔离性意味着，同时执行的事务是相互隔离的：它们不能相互冒犯。传统的数据库教科书将隔离性形式化为 可串行化（Serializability），这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。数据库确保当多个事务被提交时，结果与它们串行运行（一个接一个）是一样的，尽管实际上它们可能是并发运行的。

但是实践中很少会使用可串行的隔离，因为性能会存在损失。

持久性

数据库系统的目的是，提供一个安全的地方存储数据，而不用担心丢失。持久性 是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

完美的持久性是不存在的

实践中没有一种技术可以提供绝对保证，只有各种降低风险的技术。

单对象和多对象操作

原子性：如果一系列的写操作中途发生错误，那么应该中止事务处理，丢弃当前的所有写入。数据库至少保障了不会出现错误写入导致脏数据的产生，这是数据库对用户的保证。

隔离性：同时运行的事物不会相互干扰。如果一个事务进行多次写入，则另一个事务要么看到全部写入结果，要么什么都看不到。

多对象事务（multi-object transaction） 能保持多块数据同步。

多对象事务需要某种方式来确定哪些读写操作属于同一个事务。在关系型数据库中，通常基于客户端与数据库服务器的 TCP 连接：在任何特定连接上，BEGIN TRANSACTION 和 COMMIT 语句之间的所有内容，被认为是同一事务的一部分.

单对象写入

对单节点上的单个对象（例如键值对）上提供原子性和隔离性。原子性可以通过使用日志来实现崩溃恢复，并且可以使用每个对象上的锁来实现隔离（每次只允许一个线程访问对象） 。

一些数据库也提供更复杂的原子操作 4，例如自增操作，这样就不再需要像 图 7-1 那样的读取 - 修改 - 写入序列了。同样流行的是 比较和设置（CAS, compare-and-set） 操作，仅当值没有被其他并发修改过时，才允许执行写操作。

这些单对象操作很有用，因为它们可以防止在多个客户端尝试同时写入同一个对象时丢失更新（请参阅 “防止丢失更新”）。但它们不是通常意义上的事务。CAS 以及其他单一对象操作被称为 “轻量级事务”，甚至出于营销目的被称为 “ACID”，但是这个术语是误导性的。事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制。

多对象事务的需求

许多分布式数据存储已经放弃了多对象事务，因为多对象事务很难跨分区实现，而且在需要高可用性或高性能的情况下，它们可能会碍事。

有一些场景中，单对象插入，更新和删除是足够的。但是许多其他场景需要协调写入几个不同的对象：

  • 在关系数据模型中，一个表中的行通常具有对另一个表中的行的外键引用。（类似的是，在一个图数据模型中，一个顶点有着到其他顶点的边）。多对象事务使你确保这些引用始终有效：当插入几个相互引用的记录时，外键必须是正确的和最新的，不然数据就没有意义。
  • 在文档数据模型中，需要一起更新的字段通常在同一个文档中，这被视为单个对象 —— 更新单个文档时不需要多对象事务。但是，缺乏连接功能的文档数据库会鼓励非规范化（请参阅 “关系型数据库与文档数据库在今日的对比”）。当需要更新非规范化的信息时，如果需要一次更新多个文档。事务在这种情况下非常有用，可以防止非规范化的数据不同步。
  • 在具有次级索引的数据库中（除了纯粹的键值存储以外几乎都有），每次更改值时都需要更新索引。从事务角度来看，这些索引是不同的数据库对象：例如，如果没有事务隔离性，记录可能出现在一个索引中，但没有出现在另一个索引中，因为第二个索引的更新还没有发生。

处理错误和中止

事务的一个关键特性是，如果发生错误，它可以中止并安全地重试。 ACID 数据库基于这样的哲学：如果数据库有违反其原子性，隔离性或持久性的危险，则宁愿完全放弃事务，而不是留下半成品。

但是不是所有系统都会遵照这个原则。无主复制模式下的数据存储遇到错误时，不会撤销它已经完成的事情，需要由应用程序来负责。

尽管重试一个中止的事务是一个简单而有效的错误处理机制，但它并不完美：

  • 如果事务实际上成功了，但是在服务器试图向客户端确认提交成功时网络发生故障（所以客户端认为提交失败了），那么重试事务会导致事务被执行两次 —— 除非你有一个额外的应用级去重机制。
  • 如果错误是由于负载过大造成的，则重试事务将使问题变得更糟，而不是更好。为了避免这种正反馈循环，可以限制重试次数，使用指数退避算法，并单独处理与过载相关的错误（如果允许）。
  • 仅在临时性错误（例如，由于死锁，异常情况，临时性网络中断和故障切换）后才值得重试。在发生永久性错误（例如，违反约束）之后重试是毫无意义的。
  • 如果事务在数据库之外也有副作用，即使事务被中止，也可能发生这些副作用。例如，如果你正在发送电子邮件，那你肯定不希望每次重试事务时都重新发送电子邮件。如果你想确保几个不同的系统一起提交或放弃，两阶段提交（2PC, two-phase commit） 可以提供帮助（“原子提交与两阶段提交” 中将讨论这个问题）。
  • 如果客户端进程在重试中失效，任何试图写入数据库的数据都将丢失。

弱隔离级别

当一个事务读取，另一个事务同时修改数据时，或者当两个事务视图同时修改相同的数据时，并发问题才会出现。

并发 BUG 很难通过测试找到，因为这样的错误只有在特殊时序下才会触发。这样的时序问题可能非常少发生，通常很难重现。

数据库一直试图通过提供 事务隔离（transaction isolation） 来隐藏应用程序开发者的并发问题。可串行的（serializable） 隔离等级意味着数据库保证事务的效果如同串行运行（即一次一个，没有任何并发）。

但是可串行的隔离会有性能损失，很多数据库不愿意支持这个代价。。因此，系统通常使用较弱的隔离级别来防止一部分，而不是全部的并发问题。这些隔离级别难以理解，并且会导致微妙的错误，但是它们仍然在实践中被使用。

读已提交

最基本的事务隔离级别是读已提交：

1.从数据库读时，只能看到已提交的数据(没有脏读)

什么是脏读？

事务没有提交或中止，这时另一个事务看到未提交的数据，这个叫做脏读。在 读已提交 隔离级别运行的事务必须防止脏读。这意味着事务的任何写入操作只有在该事务提交时才能被其他人看到（然后所有的写入操作都会立即变得可见）

为什么要防止脏读？

脏读会导致数据的不一致性，可能导致其他事务作出错误决定。

2.写入数据库时，只会覆盖已提交的数据(没有脏写)

什么是脏写？

如果事务没有提交或中止，这时另一个事务写入覆盖了一个尚未提交的值，这叫做脏写。

为什么要防止脏写？

脏写会导致各种应用程序的事故发生，比如错误修改了库存量，产生超卖。同时错误的数据记录会影响到后续的业务，从而导致整个应用程序的错误记录和展示。

读已提交是一个非常流行的隔离级别，最常见的情况是，数据库通过使用 行锁（row-level lock） 来防止脏写：当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。一次只有一个事务可持有任何给定对象的锁；如果另一个事务要写入同一个对象，则必须等到第一个事务提交或中止后，才能获取该锁并继续。这种锁定是读已提交模式（或更强的隔离级别）的数据库自动完成的。

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

快照隔离和可重复读

使用读已提交隔离级别依然会产生并发错误。

不可重复读（nonrepeatable read） 或 读取偏差（read skew）会导致数据库在某一段时间处于不一致的状态。

在读已提交的隔离条件下，不可重复读 被认为是可接受的

但是有些情况下不能容忍这种情况的出现：

备份，备份数据时候需要复制整个数据库，对大型数据库而言可能需要花费数小时才能完成。备份进程运行时，数据库仍然会接受写入操作。因此备份可能会包含一些旧的部分和一些新的部分。如果从这样的备份中恢复，数据机会永久不一致。

分析查询和完整性检查，有时候可能需要扫描大部分数据库。如果这些查询在不同时间点观察数据库的不同部分，则可能会返回毫无意义的结果。

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

快照隔离对长时间运行的只读查询（如备份和分析）非常有用。如果查询的数据在查询执行的同时发生变化，则很难理解查询的含义。当一个事务可以看到数据库在某个特定时间点冻结时的一致快照，理解起来就很容易了。

实现方式：快照隔离的实现通常使用写锁来防止脏写，写入事务会阻止另一个事务修改同一个对象，但是读取并不加。快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。这允许数据库在处理一致性快照上的长时间查询时，可以正常地同时处理写入操作，且两者间没有任何锁争用。

为了实现快照隔离，数据库使用了我们看到的用于防止脏读的机制的一般化。数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它同时维护着单个对象的多个版本，所以这种技术被称为 多版本并发控制（MVCC, multi-version concurrency control）。

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

索引和快照隔离

使用的是一种 仅追加 / 写时拷贝（append-only/copy-on-write） 的变体，它们在更新时不覆盖树的页面，而为每个修改页面创建一份副本。从父页面直到树根都会级联更新，以指向它们子页面的新版本。任何不受写入影响的页面都不需要被复制，并且保持不变。

使用仅追加的 B 树，每个写入事务（或一批事务）都会创建一棵新的 B 树，当创建时，从该特定树根生长的树就是数据库的一个一致性快照。没必要根据事务 ID 过滤掉对象，因为后续写入不能修改现有的 B 树；它们只能创建新的树根。但这种方法也需要一个负责压缩和垃圾收集的后台进程。

可重复读与命名混淆

快照隔离对于只读事务来说非常有用，但是很多数据库实现它但是在官方文档中使用不同的名字来称呼它。Oracle 中称为 可串行化（Serializable） 的，在 PostgreSQL 和 MySQL 中称为 可重复读（repeatable read）

这种命名混淆的原因是SQL标准没有快照隔离的概念。

SQL 标准对隔离级别的定义是有缺陷的 —— 模糊，不精确，并不像标准应有的样子独立于实现。

可串行化

可串行化（Serializability） 隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的，就好像它们没有任何并发性，连续挨个执行一样。因此数据库保证，如果事务在单独运行时正常运行，则它们在并发运行时继续保持正确 —— 换句话说，数据库可以防止 所有 可能的竞争条件。

串行化数据库使用三种技术来实现：

  • 使用真的串行顺序执行事务

避免并发问题的最简单方法就是完全不要并发：在单个线程上按顺序一次只执行一个事务。这样做就完全绕开了检测 / 防止事务间冲突的问题，由此产生的隔离，正是可串行化的定义。

设计用于单线程执行的系统有时可以比支持并发的系统性能更好，因为它可以避免锁的协调开销。但是其吞吐量仅限于单个 CPU 核的吞吐量。为了充分利用单一线程，需要有与传统形式的事务不同的结构。(例如Redis)

  • 两阶段锁定
  • 乐观并发控制，例如可串行化快照隔离

存储过程优点和缺点

缺点：

1.不同的数据库存储过程语言都不同

2.数据库中运行的代码很难管理，它更难调试，更难版本兼容和部署，更难测试

3.数据库中如果存在一个写的不好的存储过程，会比在应用服务器中相同的代码造成更多的麻烦。

在作者看来，存储过程几乎没什么优点，难以编写，难以版本迭代和兼容，复杂的逻辑也不适合直接在数据库中编写。至少作者本人不愿意接触存储过程泛滥的项目。

优点：

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

2.VoltDB 还使用存储过程进行复制：但不是将事务的写入结果从一个节点复制到另一个节点，而是在每个节点上执行相同的存储过程。因此 VoltDB 要求存储过程是 确定性的（在不同的节点上运行时，它们必须产生相同的结果）

串行执行小结

在特定约束条件下，真的串行执行事务，已经成为一种实现可串行化隔离等级的可行办法。

  • 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。
  • 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问这些磁盘中的数据，系统就会变得非常慢 12。
  • 写入吞吐量必须低到能在单个 CPU 核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
  • 跨分区事务是可能的，但是它们能被使用的程度有很大的限制。

分区，针对分区，数据库必须要在所有分区之间协调事务。存储过程需要跨分区锁定执行，确保整个系统的可串行性。由于跨分区事务具有额外的协调开销，所以它们比单分区事务慢得多。而且不能通过增加机器来增加吞吐量。

事务是否可以是划分至单个分区很大程度上取决于应用数据的结构。简单的键值数据通常可以非常容易地进行分区，但是具有多个次级索引的数据可能需要大量的跨分区协调。

两阶段锁定

两阶段锁定（2PL，two-phase locking）

锁通常用于防止脏写：如果两个事务同时尝试写入同一个对象，则锁可以确保第二个写入必须要等到第一个写入完成事务(中止或提交),然后才能继续。

两阶段锁定类似，但是锁定要求要强得多。

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

  • 如果事务 A 读取了一个对象，并且事务 B 想要写入该对象，那么 B 必须等到 A 提交或中止才能继续（这确保 B 不能在 A 底下意外地改变对象）。
  • 如果事务 A 写入了一个对象，并且事务 B 想要读取该对象，则 B 必须等到 A 提交或中止才能继续。

在 2PL 中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。快照隔离使得 读不阻塞写，写也不阻塞读），这是 2PL 和快照隔离之间的关键区别。另一方面，因为 2PL 提供了可串行化的性质，它可以防止早先讨论的所有竞争条件，包括丢失更新和写入偏差。

使用过多的锁会造成死锁。一般情况下数据库会自动检测事务之间的死锁，并中止其中一个，以便另外一个继续执行。被中止的事务需要由应用程序重试。

两阶段锁定的性能极低，两阶段锁定下的事务吞吐量与查询响应时间要比弱隔离级别下要差得多。

获取和释放这些锁的开销极大，并发性能也随着设计进一步降低，两个并发事务竞争锁，没有获得锁的事务必须等待获得锁的事务完成或中止。但是一般的关系性数据库并不限制事务的持续时间，所以事务等待锁释放的时间是没有上限的。

基于锁实现的读已提交隔离级别可能发生死锁，但在基于 2PL 实现的可串行化隔离级别中，它们会出现的频繁的多。还有一个问题是：当事务由于死锁而被中止并重试时，它需要重新做一遍工作。如果死锁很频繁，那会浪费很多资源。

一方面，我们实现了性能不好（2PL）或者伸缩性不好（串行执行）的可串行化隔离级别。另一方面，我们有性能良好的弱隔离级别，但容易出现各种竞争条件（丢失更新、写入偏差、幻读等）。串行化的隔离级别和高性能是从根本上相互矛盾的吗？

一个称为 可串行化快照隔离（SSI, serializable snapshot isolation） 的算法是非常有前途的。它提供了完整的可串行化隔离级别，但与快照隔离相比只有很小的性能损失。

两阶段锁是一种所谓的 悲观并发控制机制（pessimistic） ：它是基于这样的原则：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。这就像互斥，用于保护多线程编程中的数据结构。

在事务持续期间，每个事务对整个数据库（或数据库的一个分区）具有排它锁，作为对悲观的补偿，我们让每笔事务执行得非常快，所以只需要短时间持有 “锁”。

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

如果有足够的空闲容量，并且事务之间的争用不是太高，乐观的并发控制技术往往比悲观的性能要好。可交换的原子操作可以减少争用：例如，如果多个事务同时要增加一个计数器，那么应用增量的顺序（只要计数器不在同一个事务中读取）就无关紧要了，所以并发增量可以全部应用且不会有冲突。

本章小结

本章中讨论了并发控制提到了几种广泛使用的隔离级别，读已提交、快照隔离和 可串行化。

介绍了几种例子来描述隔离级别：脏读，脏写，读取偏差(不可重复度)，丢失更新，写入偏差，幻读。

弱隔离级别可以防止上述的一部分异常情况，但是要求开发人员手动处理剩余异常情况。只有可串行化的隔离才能防范所以问题。

实现可串行化事务三种不同方法：

  • 字面意义上的串行执行

    如果每个事务的执行速度非常快，并且事务吞吐量足够低，足以在单个 CPU 核上处理，这是一个简单而有效的选择。

  • 两阶段锁定

    数十年来，两阶段锁定一直是实现可串行化的标准方式，但是许多应用出于性能问题的考虑避免使用它。

  • 可串行化快照隔离（SSI）

    一个相当新的算法，避免了先前方法的大部分缺点。它使用乐观的方法，允许事务执行而无需阻塞。当一个事务想要提交时，它会进行检查，如果执行不可串行化，事务就会被中止。

分布式系统的麻烦

使用分布式系统与在一台计算机上编写程序有着根本区别。它们更容易出错。

故障与部分失效

如果发生内部错误，往往宁愿完全崩溃，而不是返回错误的结果，因为错误的结果很难处理。

在分布式系统中，不再处于理想化的系统模型中，各种各样的事情都可能出问题。

在分布式系统中，尽管系统的其他部分工作正常，但系统的某些部分可能会以某种不可预知的方式被破坏。这被称为 部分失效（partial failure）。难点在于部分失效是 不确定性的（nondeterministic）：如果你试图做任何涉及多个节点和网络的事情，它有时可能会工作，有时会出现不可预知的失败。甚至不知道是否成功了，因为消息通过网络传播的时间也是不确定的！

如果要使分布式系统工作，就必须接受部分故障的可能性，并在软件中建立容错机制。即使在少数节点的小型系统中，考虑部分故障也是很重要的。迟早会有一部分系统出现故障，软件必须以某种方式处理。故障处理必须是软件设计的一部分，并且作为软件的运维，工程师往往需要知道发生故障的情况下，软件会有怎样的表现。

不可靠的网络

分布式系统是无共享的系统，通过网络连接一堆机器。网络是这些机器可能通信的唯一途径。

无共享 并不是构建系统的唯一方式，但它已经成为构建互联网服务的主要方式，其原因如下：相对便宜，因为它不需要特殊的硬件，可以利用商品化的云计算服务，通过跨多个地理分布的数据中心进行冗余可以实现高可靠性。

互联网和数据中心（通常是以太网）中的大多数内部网络都是 异步分组网络（asynchronous packet networks）。在这种网络中，一个节点可以向另一个节点发送一个消息（一个数据包），但是网络不能保证它什么时候到达，或者是否到达。

请求可能已经丢失，请求可能正在排队；远程节点可能失效；远程节点暂时停止了响应；网络响应可能会丢失;响应可能会延迟;

发送者甚至不能分辨数据包是否被发送：唯一的选择是让接收者发送响应消息，这可能会丢失或延迟。这些问题在异步网络中难以区分：你所拥有的唯一信息是，你尚未收到响应。如果你向另一个节点发送请求并且没有收到响应，则不可能判断是什么原因。

处理这个问题的通常方法是 超时（Timeout）：在一段时间之后放弃等待，并且认为响应不会到达。但是，当发生超时时，你仍然不知道远程节点是否收到了请求（如果请求仍然在某个地方排队，那么即使发送者已经放弃了该请求，仍然可能会将其发送给接收者）。

我们要记住：即使网络故障非常罕见，故障也可能会发生，这意味着我们都要在软件中处理这些情况。无论何时通过网络进行通信，都可能会失败，这是无法避免的。

处理网络故障并不意味着容忍它们：如果你的网络通常是相当可靠的，一个有效的方法可能是当你的网络遇到问题时，简单地向用户显示一条错误信息。但是，你确实需要知道你的软件如何应对网络问题，并确保系统能够从中恢复。有意识地触发网络问题并测试系统响应。

一般的系统使用超时机制来检测故障，这是唯一可靠的方法，但是也延伸出一个问题：超时应该等待多久？

在文中没有这个问题的答案。

长时间的超时意味着长时间等待，直到一个节点崩溃(或宕机)。短的超时时间可以更快检测到故障，但是将一个节点误判为失效状态，又可能这个节点只是很慢(比如负载过大响应时间变慢)。

过早宣布一个节点死亡是有问题的，有可能该节点上正在执行一些任务，如果由另外一个节点接管，这个任务可能会被执行两次。

当一个节点被宣告死亡时，它的职责需要转移到其他节点，这会给其他节点和网络带来额外的负担。如果系统已经处于高负荷状态，则过早宣告节点死亡会使问题更严重。特别是如果节点实际上没有死亡，只是由于过载导致其响应缓慢；这时将其负载转移到其他节点可能会导致 级联失效（即 cascading failure，表示在极端情况下，所有节点都宣告对方死亡，所有节点都将停止工作）。

假设你可以保证一个非故障节点总是在一段时间 r 内处理一个请求。在这种情况下，你可以保证每个成功的请求在 2d + r 时间内都能收到响应，如果你在此时间内没有收到响应，则知道网络或远程节点不工作。如果这是成立的，$2d + r$ 会是一个合理的超时设置。

不可靠的时钟

在分布式系统中，时间是一件棘手的事情，因为通信不是即时的：消息通过网络从一台机器传送到另一台机器需要时间。收到消息的时间总是晚于发送的时间，但是由于网络中的可变延迟，我们不知道晚了多少时间。这个事实导致有时很难确定在涉及多台机器时发生事情的顺序。

可以在一定程度上同步时钟：最常用的机制是 网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟。服务器则从更精确的时间源（如 GPS 接收机）获取时间。

单调钟与日历时钟

日历时钟（time-of-day clock）和单调钟（monotonic clock）。尽管它们都衡量时间，但区分这两者很重要，因为它们有不同的目的。

日历时钟

日历时钟是你直观地了解时钟的依据：它根据某个日历（也称为 挂钟时间，即 wall-clock time）返回当前日期和时间。

日历时钟通常与 NTP 同步，这意味着来自一台机器的时间戳（理想情况下）与另一台机器上的时间戳相同。但是如下节所述，日历时钟也具有各种各样的奇特之处。特别是，如果本地时钟在 NTP 服务器之前太远，则它可能会被强制重置，看上去好像跳回了先前的时间点。这些跳跃以及他们经常忽略闰秒的事实，使日历时钟不能用于测量经过时间（elapsed time）。

单调钟

单调钟适用于测量持续时间（时间间隔），比如超时或服务的响应时间。

你可以在某个时间点检查单调钟的值，做一些事情，且稍后再次检查它。这两个值之间的差异告诉你两次检查之间经过了多长时间。但单调钟的绝对值是毫无意义的：它可能是计算机启动以来的纳秒数，或类似的任意值。特别是比较来自两台不同计算机的单调钟的值是没有意义的，因为它们并不是一回事。

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

全局快照的同步时钟

快照隔离最常见的实现需要单调递增的事务 ID。如果写入比快照晚（即，写入具有比快照更大的事务 ID），则该写入对于快照事务是不可见的。在单节点数据库上，一个简单的计数器就足以生成事务 ID。

但是当数据库分布在许多机器上，也许可能在多个数据中心中时，由于需要协调，（跨所有分区）全局单调递增的事务 ID 会很难生成。事务 ID 必须反映因果关系：如果事务 B 读取由事务 A 写入的值，则 B 必须具有比 A 更大的事务 ID，否则快照就无法保持一致。在有大量的小规模、高频率的事务情景下，在分布式系统中创建事务 ID 成为一个难以处理的瓶颈。

因为时钟的精确度的不稳定性。

为了确保事务时间戳反映因果关系，在提交读写事务之前，Spanner 在提交读写事务时，会故意等待置信区间长度的时间。通过这样，它可以确保任何可能读取数据的事务处于足够晚的时间，因此它们的置信区间不会重叠。为了保持尽可能短的等待时间，Spanner 需要保持尽可能小的时钟不确定性，为此，Google 在每个数据中心都部署了一个 GPS 接收器或原子钟，这允许时钟同步到大约 7 毫秒以内。

对分布式事务语义使用时钟同步是一个活跃的研究领域。这些想法很有趣，但是它们还没有在谷歌之外的主流数据库中实现。

进程暂停

假设你有一个数据库，每个分区只有一个领导者。只有领导被允许接受写入。一个节点如何知道它仍然是领导者（它并没有被别人宣告为死亡），并且它可以安全地接受写入？

一种选择是领导者从其他节点获得一个 租约（lease），类似一个带超时的锁。任一时刻只有一个节点可以持有租约 —— 因此，当一个节点获得一个租约时，它知道它在某段时间内自己是领导者，直到租约到期。为了保持领导地位，节点必须周期性地在租约过期前续期。

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

但是，如果程序执行中出现了意外的停顿呢？例如，想象一下，线程在 lease.isValid() 行周围停止 15 秒，然后才继续。在这种情况下，在请求被处理的时候，租约可能已经过期，而另一个节点已经接管了领导。然而，没有什么可以告诉这个线程已经暂停了这么长时间了，所以这段代码不会注意到租约已经到期了，直到循环的下一个迭代 —— 到那个时候它可能已经做了一些不安全的处理请求。

可能出现这种故障的原因：

1.GC需要停止所有正在运行的线程。。这些 “停止所有处理（stop-the-world）”GC 暂停有时会持续几分钟。

2.在虚拟化环境中，可以 挂起（suspend） 虚拟机（暂停执行所有进程并将内存内容保存到磁盘）并恢复（恢复内存内容并继续执行）。这个暂停可以在进程执行的任何时候发生，并且可以持续任意长的时间。这个功能有时用于虚拟机从一个主机到另一个主机的实时迁移，而不需要重新启动，在这种情况下，暂停的长度取决于进程写入内存的速。

3.当操作系统上下文切换到另一个线程时，或者当管理程序切换到另一个虚拟机时（在虚拟机中运行时），当前正在运行的线程可能在代码中的任意点处暂停。在虚拟机的情况下，在其他虚拟机中花费的 CPU 时间被称为 窃取时间（steal time）。如果机器处于沉重的负载下（即，如果等待运行的线程队列很长），暂停的线程再次运行可能需要一些时间。

…

所有这些事件都可以随时 抢占（preempt） 正在运行的线程，并在稍后的时间恢复运行，而线程甚至不会注意到这一点。这个问题类似于在单个机器上使多线程代码线程安全：你不能对时序做任何假设，因为随时可能发生上下文切换，或者出现并行运行。

当在一台机器上编写多线程代码时，我们有相当好的工具来实现线程安全：互斥量、信号量、原子计数器、无锁数据结构、阻塞队列等等。不幸的是，这些工具并不能直接转化为分布式系统操作，因为分布式系统没有共享内存，只有通过不可靠网络发送的消息。

分布式系统中的节点，必须假定其执行可能在任意时刻暂停相当长的时间，即使是在一个函数的中间。在暂停期间，世界的其它部分在继续运转，甚至可能因为该节点没有响应，而宣告暂停节点的死亡。最终暂停的节点可能会继续运行，在再次检查自己的时钟之前，甚至可能不会意识到自己进入了睡眠。

知识、真相与谎言

分布式系统与运行在单台计算机上的程序不同之处：没有共享内存，只有通过可变延迟的不可靠网络传递的消息，系统可能遭受部分失效，不可靠的时钟和处理暂停。

网络中的一个节点无法确切地知道任何事情 —— 它只能根据它通过网络接收到（或没有接收到）的消息进行猜测。节点只能通过交换消息来找出另一个节点所处的状态（存储了哪些数据，是否正确运行等等）。如果远程节点没有响应，则无法知道它处于什么状态，因为网络中的问题不能可靠地与节点上的问题区分开来。

在分布式系统中，我们可以陈述关于行为（系统模型）的假设，并以满足这些假设的方式设计实际系统。算法可以被证明在某个系统模型中正确运行。这意味着即使底层系统模型提供了很少的保证，也可以实现可靠的行为。

节点不一定能相信自己对于情况的判断。分布式系统不能完全依赖单个节点，因为节点可能随时失效，可能会使系统卡死，无法恢复。相反，许多分布式算法都依赖于法定人数，即在节点之间进行投票（请参阅 “读写的法定人数”）：决策需要来自多个节点的最小投票数，以减少对于某个特定节点的依赖。

分布式锁的实现不正确：客户端1认为它仍具有有效的租约，即使它已经过期，从而破坏了存储中的文件。

如果持有租约的客户端暂停太久，它的租约将到期。另一个客户端可以获得同一文件的租约，并开始写入文件。当暂停的客户端回来时，它认为（不正确）它仍然有一个有效的租约，并继续写入文件。结果，客户的写入将产生冲突并损坏文件。

只允许以增加防护令牌的顺序进行写操作，从而保证存储安全

我们假设每次锁定服务器授予锁或租约时，它还会返回一个 防护令牌（fencing token），这个数字在每次授予锁定时都会增加（例如，由锁定服务增加）。然后，我们可以要求客户端每次向存储服务发送写入请求时，都必须包含当前的防护令牌。

本章小结

分布式系统可能遇到各种各样的问题，包括网络问题，时钟节点不同步问题，进程等待暂停问题。

这类 部分失效（partial failure） 可能发生的事实是分布式系统的决定性特征。每当软件试图做任何涉及其他节点的事情时，偶尔就有可能会失败，或者随机变慢，或者根本没有响应（最终超时）。在分布式系统中，我们试图在软件中建立 部分失效 的容错机制，这样整个系统在即使某些组成部分被破坏的情况下，也可以继续运行。

一致性与共识

分布式系统中的许多事情可能会出错。处理这种故障的最简单方法是简单地让整个服务失效，并向用户显示错误消息。如果无法接受这个解决方案，我们就需要找到容错的方法 —— 即使某些内部组件出现故障，服务也能正常运行。

构建容错系统的最好方法，是找到一些带有实用保证的通用抽象，实现一次，然后让应用依赖这些保证。

分布式系统最重要的抽象之一就是 共识（consensus）：就是让所有的节点对某件事达成一致。

一致性保证

大多数复制的数据库至少提供了 最终一致性，这意味着如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值。

不一致性是暂时的，最终会自行解决(理想情况下)。

但是上述是一个非常弱的保证，不确定副本收敛的时间，不确定执行多久，不确定最终一致性的时间。

对于应用开发人员而言，最终一致性是很困难的，因为它与普通单线程程序中变量的行为有很大区别。对于后者，如果将一个值赋给一个变量，然后很快地再次读取，不可能读到旧的值，或者读取失败。数据库表面上看起来像一个你可以读写的变量，但实际上它有更复杂的语义。

在与只提供弱保证的数据库打交道时，你需要始终意识到它的局限性，而不是意外地作出太多假设。错误往往是微妙的，很难找到，也很难测试，因为应用可能在大多数情况下运行良好。当系统出现故障（例如网络中断）或高并发时，最终一致性的边缘情况才会显现出来。

分布式一致性模型与事务隔离级别的区别

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

线性一致性

线性一致性的基本想法是：让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的。

在一个线性一致的系统中，只要一个客户端成功完成写操作，那么所有客户端从数据库中读取数据必须能够看到刚刚写入的值。要维护数据的单个副本的假象，系统应保障读到的值是最近的，最新的，而不是来自陈旧的缓存或副本。

任何一个读取返回新值后，所有后续读取都必须返回新值。

线性一致性与可串行化

线性一致性 容易和 可串行化 相混淆，因为两个词似乎都是类似 “可以按顺序排列” 的东西。但它们是两种完全不同的保证，区分两者非常重要：

可串行化

可串行化（Serializability） 是事务的隔离属性，每个事务可以读写多个对象（行，文档，记录）—— 请参阅 “单对象和多对象操作”。它确保事务的行为，与它们按照 某种 顺序依次执行的结果相同（每个事务在下一个事务开始之前运行完成）。这种执行顺序可以与事务实际执行的顺序不同。。

线性一致性

线性一致性（Linearizability） 是读取和写入寄存器（单个对象）的 新鲜度保证。它不会将操作组合为事务，因此它也不会阻止写入偏差等问题（请参阅 “写入偏差和幻读”），除非采取其他措施（例如 物化冲突）。

一个数据库可以提供可串行化和线性一致性，这种组合被称为严格的可串行化或 强的单副本可串行化（strong-1SR）。基于两阶段锁定的可串行化实现（请参阅 “两阶段锁定” 一节）或 真的串行执行（请参阅 “真的串行执行”一节）通常是线性一致性的。

但是，可串行化的快照隔离（请参阅 “可串行化快照隔离”）不是线性一致性的：按照设计，它从一致的快照中进行读取，以避免读者和写者之间的锁竞争。一致性快照的要点就在于 它不会包括该快照之后的写入，因此从快照读取不是线性一致性的。

一个使用单主复制的系统，需要确保领导者真的只有一个，而不是几个（脑裂）。一种选择领导者的方法是使用锁：每个节点在启动时尝试获取锁，成功者成为领导者。不管这个锁是如何实现的，它必须是线性一致的：所有节点必须就哪个节点拥有锁达成一致，否则就没用了。

分布式锁也在一些分布式数据库中有更细颗粒度级别的使用。RAC 对每个磁盘页面使用一个锁，多个节点共享对同一个磁盘存储系统的访问权限。由于这些线性一致的锁处于事务执行的关键路径上，RAC 部署通常具有用于数据库节点之间通信的专用集群互连网络。

由于线性一致性本质上意味着 “表现得好像只有一个数据副本，而且所有的操作都是原子的”，所以最简单的答案就是，真的只用一个数据副本。但是这种方法无法容错：如果持有该副本的节点失效，数据将会丢失，或者至少无法访问，直到节点重新启动。

单主复制(可能是线性一致)

共识算法(线性一致)

多主复制(非线性一致)

无主复制(可能不是线性一致)

线性一致的代价：

对多数据中心的复制而言，多主复制通常是理想的选择，使用多主数据库，每个数据中心都可以继续正常运行：由于在一个数据中心写入的数据是异步复制到另一个数据中心的，所以在恢复网络连接时，写入操作只是简单地排队并交换。

在单主配置的条件下，如果数据中心之间的网络被中断，则连接到从库数据中心的客户端无法联系到主库，因此它们无法对数据库执行任何写入，也不能执行任何线性一致的读取。它们仍能从从库读取，但结果可能是陈旧的（非线性一致）。如果应用需要线性一致的读写，却又位于与主库网络中断的数据中心，则网络中断将导致这些应用不可用。

如果客户端可以直接连接到主库所在的数据中心，这就不是问题了，那些应用可以继续正常工作。但只能访问从库数据中心的客户端会中断运行，直到网络连接得到修复。

CAP 有时以这种面目出现：一致性，可用性和分区容错性：三者只能择其二。不幸的是这种说法很有误导性，因为网络分区是一种故障类型，所以它并不是一个选项：不管你喜不喜欢它都会发生

CAP 更好的表述成：在分区时要么选择一致，要么选择可用。一个更可靠的网络需要减少这个选择，但是在某些时候选择是不可避免的。

CAP对于设计系统而言并没有实际价值。

围绕着 CAP 有很多误解和困惑，并不能帮助我们更好地理解系统，所以最好避免使用 CAP。

线性一致的系统很少。现代多核CPU上的内存甚至都不是线形一致的：如果一个CPU核上运行的线程写入某个内存地址，而另一个CPU核上运行的线程不久之后读取相同的地址，并没有保证一定能读到第一个线程写入的值(除非使用内存屏障或者围栏)。

因为每个CPU核都有自己的内存缓存和存储缓冲区。默认情况下，内存访问首先走缓存，任何变更会异步写入主存。访问缓存比主存要快得多，这个特性对于现代CPU的良好性能表现至关重要。但是如果有几个数据副本，而且这些副本是异步更新的，所以就失去了线性一致性。

对多核内存一致性模型而言，CAP 定理是没有意义的：在同一台计算机中，我们通常假定通信都是可靠的。并且我们并不指望一个 CPU 核能在脱离计算机其他部分的条件下继续正常工作。牺牲线性一致性的原因是 性能（performance），而不是容错。

分布式数据库是为了提高性能而选择牺牲线形一致性，而不是为了容错。即使没有网络故障影响，线形一致性速度也很慢。

顺序保证

顺序是什么？他在整本书中都是一个重要的基础性概念。

领导者在单主复制中的主要目的就是，在复制日志中确定 写入顺序，也就是从库写入的顺序。如果不存在一个领导者(多主复制或无主复制)，则并发操作可能导致冲突。

可串行化是关于事务表现按照某种先后顺序执行的保证。它可以字面意义上地以 串行顺序（serial order） 执行事务来实现，或者允许并行执行，但同时防止序列化冲突来实现（通过锁或中止事务）。

在不可靠的时钟中，使用时间戳确定两个写入操作哪一个更晚发生，其实也是一种顺序的保证。

顺序反复在本文中反复出现也是有原因的，因为它可能代表着直观意义上的因果依赖。比如IM系统中的聊天，对话，问句和回答…

在数据库中可能意味着：一条记录必须先被创建，然后才能被更新。

因果关系对事件施加了一种顺序：就像现实生活中，一件事会导致另一件事。某个节点读取了一些数据然后写入一些结果，另一个节点读取其写入的内容，并依次写入一些其他内容，等等。这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。

如果一个系统服从因果关系所规定的顺序，我们说它是 因果一致（causally consistent） 的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱（假设在此期间这些数据还没有被删除）。

因果性：如果两个事件是因果相关的，则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

一些分布式数据系统已经放弃了线性一致性，从而获得更好的性能，但它们用起来也更为困难。

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一致性，且性能与可用性与最终一致的系统类似。

但是这方面的研究很多未应用到生产系统。

序列号顺序

虽然因果是一个重要的理论概念，但实际上跟踪所有的因果关系是不切实际的。在许多应用中，客户端在写入内容之前会先读取大量数据，我们无法弄清写入因果依赖于先前全部的读取内容，还是仅包括其中一部分。显式跟踪所有已读数据意味着巨大的额外开销。

但是可以使用序列号或时间戳来排序事件。时间戳可以来自逻辑时钟，这事一个用来生成标识操作的数字序列的算法(例如一个每次操作自增的计数器)。

这样的序列号是紧凑的，提供了一个全序关系：意味着每个操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大。

这里要注意，如果使用单主复制，我们可以这样做，但是在多主复制或无主复制，或分区数据库，那么我们生成序列号就会出现一些问题：

每个节点都可以生成自己独立的一组序列号，这种时间戳不连续，需要应用注明标识来识别它们。

还可以预先分配序列号区块来解决，比如节点A拥有1-10000区块的所有权，节点B拥有10001-20000区块的所有权。

兰伯特时间戳

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

它提供了与因果关系一致的全序。

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

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

全序广播

在分布式系统中，让所有节点对同一个全局操作顺序达成一致可能相当棘手。单主复制通过选择一个节点作为主库来确定操作的全序，并在主库的单个 CPU 核上对所有操作进行排序。如果吞吐量超出单个主库等处理能力，在这种情况下如何扩展系统？

全序广播通常被描述为在节点间交换消息的协议。

正确的全序广播算法必须始终保证可靠性和有序性，即使节点或网络出现故障。当然在网络中断的时候，消息是传不出去的，但是算法可以不断重试，以便在网络最终修复时，消息能及时通过并送达（当然它们必须仍然按照正确的顺序传递）。

ZooKeeper 和 etcd 这样的共识服务实际上实现了全序广播。

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

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

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

尽管写入是线形一致的，但不保证读取也是线形一致的。为了使读取也线形一致，有几个方案：

1.通过日志追加消息，然后读取日志，直到该消息被读回才执行实际的读取操作。(etcd方案)

2.如果日志允许以线性一致的方式获取最新日志消息的位置，则可以查询该位置，等待该位置前的所有消息都传达到你，然后执行读取。(Zookeeper Sync 操作思想)

3.从同步更新的副本中进行读取，因此可以确保结果是最新的(这种技术用于链式复制)。

分布式事务与共识

共识：目的只是为了让几个节点达成一致。

领导选举，所有节点需要选出某个节点成为领导者而达成一致。如果因为发生故障，重新选举领导者，或出现脑裂等问题造成数据发生分歧，从而导致不一致或数据丢失。共识在里面就显得非常重要，因为这是共识需要去解决的问题，从而避免这些情况发生。

原子提交，在支持跨多节点或跨多分区事务的数据库中，一个事务可能在某些节点上失败，但在其他节点上成功。如果我们想要维护事务的原子性，那么必须让所有节点对事务的结果达成一致。要么全部中止/回滚，要么全部提交。这个共识的例子被称为 原子提交（atomic commit） 问题。

在分布式系统中，我们必须假设节点可能会崩溃，所以可靠的共识是不可能的。然而这里我们正在讨论达成共识的算法，到底是怎么回事？

答案是 FLP 结果是在 异步系统模型 中被证明的（请参阅 “系统模型与现实”），而这是一种限制性很强的模型，它假定确定性算法不能使用任何时钟或超时。如果允许算法使用 超时 或其他方法来识别可疑的崩溃节点（即使怀疑有时是错误的），则共识变为一个可解的问题。即使仅仅允许算法使用随机数，也足以绕过这个不可能的结果。

因此，虽然 FLP 是关于共识不可能性的重要理论结果，但现实中的分布式系统通常是可以达成共识的。

原子提交与两阶段提交

单数据库节点执行事务情况下，原子性通常由存储引擎实现。

执行过程：

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

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

多节点数据库事务

分区数据库中可能会存在一个多对象事务，可能位于与主数据不同的节点上。大多数”NoSQL”分布式数据存储不支持这种分布式事务。但是很多关系性数据库集群支持。

在这些情况下，仅向所有节点发送提交请求并独立提交每个节点的事务是不够的。这样很容易发生违反原子性的情况：提交在某些节点上成功，而在其他节点上失败：

  • 某些节点可能会检测到违反约束或冲突，因此需要中止，而其他节点则可以成功进行提交。
  • 某些提交请求可能在网络中丢失，最终由于超时而中止，而其他提交请求则通过。
  • 在提交记录完全写入之前，某些节点可能会崩溃，并在恢复时回滚，而其他节点则成功提交。

如果某些节点提交了事务，但其他节点却放弃了这些事务，那么这些节点就会彼此不一致。而且一旦在某个节点上提交了一个事务，如果事后发现它在其它节点上被中止了，它是无法撤回的。出于这个原因，一旦确定事务中的所有其他节点也将提交，节点就必须进行提交。

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

两阶段提交

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

2PC使用一个通常不会出现在单节点事务中的新组件：协调者，也成为 事务管理器。协调者通常在请求事务的相同应用进程中以库的形式实现(例如，嵌入在Java EE人容器中)，但也可以是单独的进程或服务。

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

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

但是要注意，一旦协调者作出决定，这个决定是不可撤销的。当参与投票的节点投完票后，它保证肯定能够提交。

在2PC期间，如果任何一个准备请求失败或者超时，协调者就会中止事务。如果任何提交或中止请求失败，协调者将无条件重试。

XA事务

X/Open XA（扩展架构（eXtended Architecture） 的缩写）是跨异构技术实现两阶段提交的标准。

XA不是一个网络协议，它只是一个用来与食物协调者链接的C API.

XA 假定你的应用使用网络驱动或客户端库来与参与者进行通信。如果驱动支持XA，则意味着它会调用XA API 以查明操作是否为分布式事务的一部分。如果是，则将必要的信息发往数据库服务器。驱动还会向协调者暴露回调接口，协调者可以通过回调来要求参与者准备，提交或中止。

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

实践中，存疑的事务确实会出现，而且协调者无法确认事务的结果。这些事务无法自动解决，所以它们会永远待在数据库中，持有锁并阻塞其他事务。
唯一的解决方式是管理员手动决定提交还是回滚事务。

许多 XA 的实现都有一个叫做 启发式决策（heuristic decisions） 的紧急逃生舱口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。要清楚的是，这里 启发式 是 可能破坏原子性（probably breaking atomicity） 的委婉说法，因为它违背了两阶段提交的系统承诺。因此，启发式决策只是为了逃出灾难性的情况而准备的，而不是为了日常使用的。

容错共识

共识算法可以用来确定 互不相容的操作中，哪一个才是最终结果。

共识算法必须满足：一致同意，完整性，有效性，终止。

一致同意 和 完整性 属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。有效性 属性主要是为了排除平凡的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为 null 的算法，该算法满足 一致同意 和 完整性 属性，但不满足 有效性 属性。

终止，这个属性形式化了容错的思想。即使部分节点出现故障，其他节点也必须达成一项决定。

共识的系统模型假设，当一个节点“崩溃”时，它会突然消失而且永远不会回来。在这个系统模型中，任何需要等待节点恢复的算法都不能满足 终止 属性。特别是，2PC 不符合终止属性的要求。

算法可以容忍的失效数量是有限的：事实上可以证明，任何共识算法都需要至少占总体 多数（majority） 的节点正确工作，以确保终止属性。

共识的局限性

共识算法对于分布式系统来说是一个巨大的突破：它为其他充满不确定性的系统带来了基础的安全属性（一致同意，完整性和有效性），然而它们还能保持容错（只要多数节点正常工作且可达，就能取得进展）。它们提供了全序广播，因此它们也可以以一种容错的方式实现线性一致的原子操作。

节点在作出决定前提议进行投票的过程是一种同步复制。通常数据库会配置为异步复制的模式，在这种情况下如果发生故障切换，一些已提交的数据可能会丢失(但是为了获得更好的性能，大部分人选择接受这种风险)。

本章小结

本章深入研究了线性一致性：让多个副本数据看起来好像只有一个副本一样，并让所有操作都原子性生效。虽然线性一致性因为简单易懂而很吸引人 —— 它使数据库表现的好像单线程程序中的一个变量一样，但它有着速度缓慢的缺点，特别是在网络延迟很大的环境中。

本章还讨论了因果性，因果性对系统中的事件施加了顺序。与线性一致不同，线性一致性将所有操作放在单一的全序时间线中，因果一致性为我们提供了一个较弱的一致性模型：某些事件可以是 并发 的，所以版本历史就像是一条不断分叉与合并的时间线。因果一致性没有线性一致性的协调开销，而且对网络问题的敏感性要低得多。

剩下篇章对共识进行了讨论，达成共识意味着以一个统一的标准来决定一件事的结果。所有节点一致同意所做决定，且这一决定不可撤销。

  • 线性一致性的 CAS 寄存器

    寄存器需要基于当前值是否等于操作给出的参数，原子地 决定 是否设置新值。

  • 原子事务提交

    数据库必须 决定 是否提交或中止分布式事务。

  • 全序广播

    消息系统必须 决定 传递消息的顺序。

  • 锁和租约

    当几个客户端争抢锁或租约时，由锁来 决定 哪个客户端成功获得锁。

  • 成员 / 协调服务

    给定某种故障检测器（例如超时），系统必须 决定 哪些节点活着，哪些节点因为会话超时需要被宣告死亡。

  • 唯一性约束

    当多个事务同时尝试使用相同的键创建冲突记录时，约束必须 决定 哪一个被允许，哪些因为违反约束而失败。

如果你只有一个节点，或者你愿意将决策的权能分配给单个节点，所有这些事都很简单。这就是在单领导者数据库中发生的事情：所有决策权归属于领导者，这就是为什么这样的数据库能够提供线性一致的操作，唯一性约束，完全有序的复制日志，以及更多。

但如果该领导者失效，或者如果网络中断导致领导者不可达，这样的系统就无法取得任何进展。应对这种情况可以有三种方法：

  1. 等待领导者恢复，接受系统将在这段时间阻塞的事实。许多 XA/JTA 事务协调者选择这个选项。这种方法并不能完全达成共识，因为它不能满足 终止 属性的要求：如果领导者续命失败，系统可能会永久阻塞。
  2. 人工故障切换，让人类选择一个新的领导者节点，并重新配置系统使之生效，许多关系型数据库都采用这种方方式。这是一种来自 “天意” 的共识 —— 由计算机系统之外的运维人员做出决定。故障切换的速度受到人类行动速度的限制，通常要比计算机慢（得多）。
  3. 使用算法自动选择一个新的领导者。这种方法需要一种共识算法，使用成熟的算法来正确处理恶劣的网络条件是明智之举【107】。

尽管单领导者数据库可以提供线性一致性，且无需对每个写操作都执行共识算法，但共识对于保持及变更领导权仍然是必须的。因此从某种意义上说，使用单个领导者不过是 “缓兵之计”：共识仍然是需要的，只是在另一个地方，而且没那么频繁。好消息是，容错的共识算法与容错的共识系统是存在的，我们在本章中简要地讨论了它们。