参考学习《数据密集型应用系统设计》

当存在多台机器提供服务时，数据分布在多节点，存在两种方式:

• 复制。1) 可以提供冗余: 如果某些节点发生不可用，则可以通过其他节点提供数据访问服务。2)使用副本可以提高系统性能
• 分区。将一个大数据库拆分为多个子集。

1. 复制

1.1 复制基本概念

1.1.1 为什么使用复制

1. 高可用性: 即使在一台机器（或多台机器，或整个数据中心）停机的情况下也能保持系统正常运行
2. 延迟: 将数据放置在距离用户较近的地方，以便用户能够更快地与其交互
3. 可扩展性: 可以通过对副本进行读取来处理，从而处理比单个机器更高的读吞吐量

1.1.2 常见复制策略

1. 主从复制
2. 多主节点复制
3. 无主节点复制

1.1.3 复制日志的实现

1. 基于语句的复制
以mysql为例, insert/update/delete语句。
但是有如下问题:

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

​ 基于语句的复制在5.1版本前的MySQL中使用。因为它相当紧凑，现在有时候也还在用。但现在在默认情况下，如果语句中存在任何不确定性，MySQL会切换到基于行的复制（稍后讨论）。

2. 基于WAL传输

​ PostgreSQL和Oracle等使用这种复制方法【16】。主要缺点是日志记录的数据非常底层：WAL包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。

​ 看上去这可能只是一个微小的实现细节，但却可能对运维产生巨大的影响。如果复制协议允许从库使用比主库更新的软件版本，则可以先升级从库，然后执行故障切换，使升级后的节点之一成为新的主库，从而执行数据库软件的不停机升级。如果复制协议不允许版本不匹配（传输WAL经常出现这种情况），则此类升级需要停机。

3. 基于行的逻辑日志复制

​ 另一种方法是，复制和存储引擎使用不同的日志格式，这样可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。

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

• 对于插入的行，日志包含所有列的新值。
• 对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，但是如果表上没有主键，则需要记录所有列的旧值。
• 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。
• 修改多行的事务会生成多个这样的日志记录，后面跟着一条记录，指出事务已经提交。 MySQL的二进制日志（当配置为使用基于行的复制时）使用这种方法。

​ 优点
由于逻辑日志与存储引擎内部分离，因此可以更容易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件甚至不同的存储引擎。
​ 对于外部应用程序来说，逻辑日志格式也更容易解析。如果要将数据库的内容发送到外部系统（如数据），这一点很有用，例如复制到数据仓库进行离线分析，或建立自定义索引和缓存【。 这种技术被称为 数据变更捕获（change data capture），第11章将重新讲到它。

4. 基于触发器的复制

​ 触发器允许注册在数据库系统中发生数据更改（写入事务）时自动执行的自定义应用程序代码。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上任何业务逻辑处理，会后将数据变更复制到另一个系统去。基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库的内置复制更容易出错，也有很多限制。然而由于其灵活性，仍然是很有用的。

1.2 复制滞后问题

​基于主库的复制要求所有写入都由单个节点处理，但只读查询可以由任何副本处理。所以对于读多写少的场景（Web上的常见模式），一个有吸引力的选择是创建很多从库，并将读请求分散到所有的从库上去。这样能减小主库的负载，并允许向最近的副本发送读请求。在这种扩展体系结构中，只需添加更多的副本，就可以提高只读请求的服务容量。但是，这种方法实际上只适用于异步复制。而异步复制会带来副本的复制滞后问题。

主从强一致性不太现实，而“最终一致性”的保证又不能满足大多数场景，有几种一致性保证是最常见的:

1.2.1 read-after-writer一致性: 读自己的写

image.png

这种情形下，就需要“写后读一致性”，也称为读写一致性。

如何做到这一点呢？

读用户可能已经会修改的内容时，都从主库读
这就要求有一些方法，不用实际查询就可以知道用户是否可能会修改某些东西。举个例子，社交网络上的用户个人资料信息通常只能由用户本人编辑，而不能由其他人编辑。因此一个简单的规则是：从主库读取用户自己的档案，在从库读取其他用户的档案。

客户端更新以后，一分钟内总是在主节点读取
如果应用中的大部分内容都可能被用户编辑，那这种方法就没用了，因为大部分内容都必须从主库读取（扩容读就没效果了）。在这种情况下可以使用其他标准来决定是否从主库读取。例如可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止任向任何滞后超过一分钟到底从库发出查询。

客户端读请求中包含最近更新时间戳
客户端可以记住最近一次写入的时间戳，并附带在读请求中。据此信息，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。

这三种方法:

• 第一种方法适用场景很少
• 第二、三种方法，一方面面临时钟问题，另一方面无法处理多设备访问的场景

1.2.2 单调读

image.png

单调读取仅意味着如果一个用户顺序地进行多次读取，则他们不会看到时间后退，即，如果先前读取到较新的数据，后续读取不会得到更旧的数据。

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

1.2.3 前缀一致读

image.png

防止这种异常，需要另一种类型的保证：一致前缀读（consistent prefix reads）。 这个保证说：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

​ 这是分区（partitioned）（分片（sharded））数据库中的一个特殊问题。如果数据库总是以相同的顺序应用写入，则读取总是会看到一致的前缀，所以这种异常不会发生。但是在许多分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序：当用户从数据库中读取数据时，可能会看到数据库的某些部分处于较旧的状态，而某些处于较新的状态。一种解决方案是，确保任何因果相关的写入都写入相同的分区。但是该方案真实实现效率会大打折扣，还有一些显式跟踪因果依赖关系的算法。

1.2.4 复制滞后问题的解决方案

最终一致性是否满足需求？
如果复制延迟增加到几分钟甚至几小时，应用程序行为是否可以符合预期？如果答案是“没问题”，那很好。但如果结果对于用户来说是不好体验，那么设计系统来提供更强的保证是很重要的，例如写后读。明明是异步复制却假设复制是同步的，这是很多麻烦的根源。

是否可以在应用层解决？
​ 如前所述，应用程序可以提供比底层数据库更强有力的保证，例如通过主库进行某种读取。但在应用程序代码中处理这些问题是复杂的，容易出错。

事务
​ 如果应用程序开发人员不必担心微妙的复制问题，并可以信赖他们的数据库“做了正确的事情”，那该多好呀。这就是事务（transaction）存在的原因：数据库通过事务提供强大的保证，所以应用程序可以更加简单。
​ 单节点事务已经存在了很长时间。然而在走向分布式（复制和分区）数据库时，许多系统放弃了事务。声称事务在性能和可用性上的代价太高，并断言在可扩展系统中最终一致性是不可避免的。这个叙述有一些道理，但过于简单了，本书其余部分将提出更为细致的观点。第七章和第九章将回到事务的话题，并讨论一些替代机制。

1.3 多主节点

1.3.1 多主节点适用场景

​主从复制有一个明显的缺点：只有一个主节点，而所有的写入都必须通过它。如果出于任何原因无法连接到主库， 就无法向数据库写入。此时，可以使用多主节点复制。
​在单数据中心内部使用多个主节点基本没有太大意义，其复杂性已经超过所能带来的好处，多主节点适用场景如下:

1. 多数据中心

image.png

在多数据中心情况下，多主节点复制方案相比于单主节点方案的好处是:
性能
​ 对于主从复制，每个写入都必须穿过互联网，进入主库所在的数据中心，这可能会增加写入时间，并偏离了设置多个数据中心的初衷(就近访问)。在多主节点模型中，每个写操作都可以在本地数据中心进行处理，并与其他数据中心异步复制。因此，数据中心之间的网络延迟对用户来说是透明的。

容忍数据中心停机
​ 对于主从复制，如果主库所在的数据中心发生故障，故障切换可以使另一个数据中心里的从节点成为主节点。在多主节点模型中，每个数据中心可以独立于其他数据中心继续运行，发生故障的数据中心在恢复之后更新至最新状态。

容忍网络问题

​ 数据中心之间的通信通常穿过公共互联网，这可能不如数据中心内的本地网络可靠。主从复制模型中，写请求是同步的，所以对这数据中心间的网络性能和稳定性更加敏感。多主节点通常采用异步复制，可以更好的容忍此问题。

2. 离线客户端操作

3. 协作编辑

1.3.2 多主节点模型的问题: 写冲突

• 尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的主节点可能会同时修改相同的数据，写冲突是必须解决的
• 由于多主复制在许多数据库中都属于改装的功能，所以常常存在微妙的配置缺陷，且经常与其他数据库功能之间出现意外的反应。例如自增主键、触发器、完整性约束等，都可能会有麻烦。因此，多主复制往往被认为是危险的领域，应尽可能避免。

1.3.2.1 什么是冲突

image.png

1.3.2.2 避免冲突

处理冲突的最简单的策略就是避免冲突：如果应用程序可以确保特定记录的所有写入都通过同一个主节点，那么冲突就不会发生。由于很多多主复制所实现的冲突解决方案存在瑕疵，避免冲突是一个经常推荐的方法。

但是，有时您可能需要更改指定的记录的主库——可能是因为一个数据中心出现故障，您需要将流量重新路由到另一个数据中心，或者可能是因为用户已经迁移到另一个位置，现在更接近新的数据中心。在这种情况下，冲突避免不再有效，你必须处理不同主库同时写入的可能性。

1.3.2.3 多主收敛于一致状态

可能有以下方式:

• 给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入者获胜（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失。
• 为每个副本分配一个唯一的ID，并制定规则，例如ID编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
• 以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们（如合并的标题可能类似于“B/C”）。
• 利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突（也许通过提示用户的方式）。

作为解决冲突最合适的方法可能取决于应用程序，大多数多主复制工具允许使用应用程序代码编写冲突解决逻辑。该代码可以在写入或读取时执行：

写时执行
​ 只要数据库系统检测到复制更改日志中存在冲突，就会调用冲突处理程序。例如，Bucardo允许您为此编写一段Perl代码。这个处理程序通常不能提示用户——它在后台进程中运行，并且必须快速执行。
读时执行
​ 当检测到冲突时，所有冲突写入被存储。下一次读取数据时，会将这些多个版本的数据返回给应用程序。应用程序可能会提示用户或自动解决冲突，并将结果写回数据库。例如，CouchDB以这种方式工作。

1.3.2.3 多主复制拓扑结构

image.png

• 最普遍的拓扑是全部到全部，其中每个主节点将其写入每个主节点。
• 在圆形和星形拓扑中，写入可能需要在到达所有副本之前通过多个节点。因此，节点需要转发从其他节点收到的数据更改。为了防止无限复制循环，每个节点被赋予一个唯一的标识符，并且在复制日志中，每个写入都被标记了所有已经通过的节点的标识符。当一个节点收到用自己的标识符标记的数据更改时，该数据更改将被忽略，因为节点知道它已经被处理。
• 循环和星型拓扑的问题是，如果只有一个节点发生故障，则可能会中断其他节点之间的复制消息流，导致它们无法通信，直到节点修复。拓扑结构可以重新配置为在发生故障的节点上工作，但在大多数部署中，这种重新配置必须手动完成。更密集连接的拓扑结构（例如全部到全部）的容错性更好，因为它允许消息沿着不同的路径传播，避免单点故障。
• 另一方面，全能拓扑也可能有问题。特别是，一些网络链接可能比其他网络链接更快（例如，由于网络拥塞），结果是一些复制消息可能“超过”其他复制消息，从而导致违背因果关系:
  image.png
  要正确排序这些事件，可以使用一种称为版本向量（version vectors）的技术。

1.4 无主节点

在单主节点和多主节点的情形下: 客户端向一个主节点发送写请求，而数据库系统负责将写入复制到其他副本。主库决定写入的顺序，而从库按相同顺序应用主库的写入。

​一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端的写入。这可以称为无主节点（或者视为都是主节点）。在一些无主节点的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个协调者（coordinator）节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。我们将会看到，这种设计上的差异对数据库的使用方式有着深远的影响。

在无主节点模型中，一个重要的概念是版本，可以采用版本号技术确定哪个值更新。
对于多个主节点来说，必须要解决的问题是: 写冲突，这其中包含两个问题: 检测冲突和处理冲突

1.4.1 冲突处理

最后写入胜利（丢弃并发写入）

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

​ 正如“最近”的引号所表明的，关键问题在于定义“最新”。很多情况下是没有自然顺序的。即使写入没有自然的排序，我们也可以强制任意排序。例如，可以为每个写入附加一个时间戳，挑选最“最近”的最大时间戳，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为最后写入胜利（LWW, last write wins），是Cassandra唯一支持的冲突解决方法，也是Riak中的一个可选特征。

​ LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写入将被静默丢弃。此外，LWW甚至可能会删除不是并发的写入。有一些情况，如缓存，其中丢失的写入可能是可以接受的。如果丢失数据不可接受，LWW并不是解决冲突的良好选择。

​ 与LWW一起使用数据库的唯一安全方法是确保一个键只写入一次，然后视为不可变，从而避免对同一个key进行并发更新。例如，Cassandra推荐使用的方法是使用UUID作为键，从而为每个写操作提供一个唯一的。

其他合并: 合并和删除

• 以购物车为例，一种合理的合并兄弟方法就是集合求并。
• 然而，如果你想让人们也可以从他们的手推车中删除东西，而不是仅仅添加东西，那么把兄弟求并可能不会产生正确的结果：如果你合并了两个兄弟手推车，并且只在其中一个兄弟值里删掉了它，那么被删除的项目会重新出现在兄弟的并集中。为了防止这个问题，一个项目在删除时不能简单地从数据库中删除;相反，系统必须留下一个具有合适版本号的标记，以指示合并兄弟时该项目已被删除。这种删除标记被称为墓碑（tombstone）。

image.png

可以看到服务器可以通过查看版本号来确定两个操作是否是并发的——它不需要解释该值本身（因此该值可以是任何数据结构）。该算法的工作原理如下：

• 服务器为每个键保留一个版本号，每次写入键时都增加版本号，并将新版本号与写入的值一起存储。
• 当客户端读取键时，服务器将返回所有(未被覆盖的)值以及最新的版本号。且要求写之前必须先读取。
• 客户端写入键时，必须包含之前读取的版本号，读到的值和新值合并后的集合。 （来自写入请求的响应可以像读取一样，返回所有当前值，这使得我们可以像购物车示例那样连接多个写入。）
• 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持更高版本号所有值（因为这些值与当前的写操作属于并发）。

1.4.2 冲突检测

可以使用版本向量来检测冲突，为每个副本和每个主键均定义一个版本号，每个副本在处理写入时增加自己的版本号，并追踪其他副本的版本号。
https://xenojoshua.com/2012/11/vector-clock-algorithm/
https://blog.xiaohansong.com/vertor-clock.html

前面我们提到向量时钟可以用来检测分布式系统中多副本更新的数据冲突问题，注意是检测（发现问题），它并不能解决问题。数据冲突的解决是另一个课题，这里不展开了。
亚马逊的 Dynamo 是一个分布式Key/Value存储系统，为了高可用，即使在出现网络分区或者机器宕机时依然可读可写。当网络分区恢复之后，多个副本同步数据一定会出现数据不一致的情况，那么如何检测数据冲突呢？参考向量时钟（Vector clock）的思想，Dynamo 中使用了版本向量（Version vector）来检测数据冲突，下面我们来看看算法的实现。

image
(1) client 端写入数据，该请求被 Sx 处理并创建相应的 vector ([Sx, 1])，记为数据 D1
(2) 第 2 次请求也被 Sx 处理，数据修改为 D2，vector 修改为([Sx, 2])
(3) 第 3、4 次请求分别被 Sy、Sz 处理，client 端先读取到 D2，然后 D3、D4 被写入 Sy、Sz
(4) 第 5 次更新时 client 端读取到 D2、D3 和 D4 3个数据版本，通过类似向量时钟判断同时发生关系的方法可判断 D3、D4 是同时发生的事件，因此存在数据冲突，最终通过一定方法解决数据冲突并写入 D5
注意，向量时钟和版本向量并不是同一个东西，版本向量借鉴了向量时钟中利用向量来判断事件的因果关系的思想，用于检测数据冲突。向量时钟还有其他的应用，例如强制因果通信（Enforcing Causal Communication），这里不展开了，有兴趣的读者自行谷歌。

1.4.3 读写策略

可以看到，冲突的检测和处理，是需要客户端并发读取&写入来实现的。
如果你有n个副本，写入需要w个节点确定，读取需要r个节点确认，只要w + r> n，读取中必然包含最新值。
​通常，r和w被选为奇数节点，w=r=(n+1)/2。也可以根据需求灵活调整。例如，对于读多写少的情况，w=n和r=1比较合适。

读修复（Read repair）

​ 当客户端并行读取多个副本时，它可以检测到任何过期的返回值。例如，用户2345获得了来自副本3的版本6和来自副本1和2的版本7。客户端发现副本3的值已经过期，并将新值写回该副本。这种方法适用于频繁读取的场景。

反熵过程（Anti-entropy process）
​ 此外，一些数据存储具有后台进程，该进程不断查找副本之间的数据差异，并将任何缺少的数据从一个副本复制到另一个副本。与基于主节点复制中的复制日志不同，此反熵过程不会以任何特定的顺序复制写入。

2. 分区

分区没啥好说的。

主要的分区方法

基于关键字区间的分区

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

哈希分区

​散列函数应用于每个键，分区拥有一定范围的散列。这种方法破坏了键的排序，使得范围查询效率低下，但可以更均匀地分配负载。通过散列进行分区时，通常先提前创建固定数量的分区，为每个节点分配多个分区，并在添加或删除节点时将整个分区从一个节点移动到另一个节点。也可以使用动态分区。

哈希分区的加强版是一致性哈希: https://zhuanlan.zhihu.com/p/34985026

两种方法搭配使用也是可行的，例如使用复合主键：使用键的一部分来标识分区，而使用另一部分作为排序顺序。

二级索引分区方法

按文档分区（本地索引），其中二级索引存储在与主键和值相同的分区中。这意味着只有一个分区需要在写入时更新，但是读取二级索引需要在所有分区之间进行分散/收集。

image.png

按关键词分区（全局索引），其中二级索引存在不同的分区中。辅助索引中的条目可以包括来自主键的所有分区的记录。当文档写入时，需要更新多个分区中的二级索引；但是可以从单个分区中进行读取。

image.png