DDIA(五)

作者: 冰菓_ | 来源:发表于2022-04-22 18:46 被阅读0次

复制😱

复制的目的：

使得数据与用户在地理上接近（从而减少延迟）
即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）
伸缩可以接受读请求的机器数量（从而提高读取吞吐量）

领导者与追随者

存储数据库副本的每个节点称为副本（replica）。当存在多个副本时，会不可避免的出现一个问题：如何确保所有数据都落在了所有的副本上？

每一次向数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据。最常见的解决方案被称为基于领导者的复制（leader-based replication）（也称主动/被动（active/passive）或主/从（master/slave）复制）

主从复制工作原理：

副本之一被指定为领导者（leader，也被称作主库）
a. 客户端写数据时，要把请求发送给领导者
b. 领导者把新输入写入本地存储
其他副本被称为追随者（followers，也被称作只读副本、从库、热备）
a. 每当领导者将新数据写入本地存储时，他会把数据变更发送给所有的追随者，称之为复制日志或变更刘
b. 每个追随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）

基于领导者(主-从)的复制

同步复制与异步复制

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

基于领导者的复制：一个同步从库和一个异步从库

● 从库 1 的复制是同步的
● 从库 2 的复制是异步的

同步复制：
● 优点：从库保证和主库一直的最新数据副本
● 缺点：如果从库没有响应（如已崩溃、网络故障），主库就无法处理写入操作。主库必须阻止所有的写入，等待副本再次可用。

半同步：通常使用一个从库与主库是同步的，而其他从库是异步的。这保证了至少两个节点拥有最新的数据副本。

通常情况下，基于领导者的复制都配置为完全异步。注意，主库故障可能导致丢失数据。

设置新从库

有时候需要设置一个新的从库：也许是为了增加副本的数量，或替换失败的节点。如何确保新的从库拥有主库数据的精确副本？简单地将数据文件从一个节点复制到另一个节点通常是不够的：客户端不断向数据库写入数据，数据总是在不断变化，标准的数据副本会在不同的时间点总是不一样。复制的结果可能没有任何意义。

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

处理节点宕机

从库失效：追赶恢复

从库可以从日志知道，在发生故障前处理的最后一个事务。

主库失效：故障切换

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

自动故障切换：

确认主库失效。有很多事情可能会出错：崩溃，停电，网络问题等等。没有万无一失的方法来检测出现了什么问题，所以大多数系统只是简单使用 超时（Timeout） ：节点频繁地相互来回传递消息，并且如果一个节点在一段时间内（例如30秒）没有响应，就认为它挂了（因为计划内维护而故意关闭主库不算）。
选择一个新的主库。这可以通过选举过程（主库由剩余副本以多数选举产生）来完成，或者可以由之前选定的控制器节点（controller node） 来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库（最小化数据损失）。让所有的节点同意一个新的领导者，是一个共识问题
重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库。如果老领导回来，可能仍然认为自己是主库，没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导，成为一个从库。

故障切换会出现很多大麻烦：

如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果老主库重新加入集群，新主库在此期间可能会收到冲突的写入，那这些写入该如何处理？最常见的解决方案是简单丢弃老主库未复制的写入，这很可能打破客户对于数据持久性的期望。
如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。
发生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为 脑裂(split brain)，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。
主库被宣告死亡之前的正确超时应该怎么配置？在主库失效的情况下，超时时间越长，意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。

复制日志的实现

基于语句的复制

在最简单的情况下，主库记录下它执行的每个写入请求（语句（statement））并将该语句日志发送给其从库。

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

传输预写式日志（WAL）

对于日志结构存储引擎（SSTables 和 LSM 树），日志是主要存储位置。日志段在后台压缩，并进行垃圾回收。
覆盖单个磁盘块的 B 树，每次修改会先写入预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。
日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本：主库把日志发送给从库

缺点：

复制与存储引擎紧密耦合。
不可能使主库和从库上运行不同版本的数据库软件。
运维时如果升级软件版本，有可能会要求停机。

逻辑日志复制（基于行）

采用逻辑日志，可以把复制与存储逻辑分离。
关系型数据库通常以行作为粒度描述数据库写入的记录序列：

对于插入的行，日志包含所有列的新值；
对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，或者所有列的旧值。
对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列（至少是更新列）的新值。

优点：

逻辑日志与存储引擎分离，方便向后兼容。可以让领导者和跟随者运行不同版本的数据库软件。
对于外部应用，逻辑日志也更容易解析。比如复制到数据仓库，或者自定义索引和缓存。被称为数据变更捕获。

基于触发器的复制

上述复制都是数据库自己实现的。也可以自定义复制方法：数据库提供了触发器和存储过程。
允许数据库变更时，自动执行应用的程序代码。
开销更大，更容易出错。但更灵活。

复制延迟问题

当应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致：同时对主库和从库执行相同的查询，可能得到不同的结果，因为并非所有的写入都反映在从库中。这种不一致只是一个暂时的状态——如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致。出于这个原因，这种效应被称为 最终一致性（eventually consistency）

读己之写

用户写入后从旧副本中读取数据。需要写后读(read-after-write)的一致性来防止这种异常

此时需要「读写一致性」，也成为读己之写一致性。
技术：

读用户可能已经修改过的内容时，都从主库读；比如读个人资料都从主库读，读别人的资料可以读从库。
如果应用的部分内容都可能被用户编辑，上述方法无效。可以指定更新后的时间窗口，比如上次更新的一分钟内从主库读。
客户端记住最近一次写入的时间戳，从库提供查询时，保证该时间戳前的变更都已经传播到了本从库；否则从另外的从库读，或者等待从库追赶上来。（时间戳可以是逻辑时间戳，如日志序列号；或者要有准确的时间同步）
如果副本在多个数据中心，则比较复杂。任何需要从领导者提供服务的请求，都必须路由到包含主库的数据中心。
用户有多个设备时，还要考虑的问题：
记录更新时间戳变得更困难；因为一台设备上运行的程序不知道另一台设备上发生了什么。元数据需要一个中心存储。
不同设备可能路由到不同的数据中心。如果你的方法需要读主库，就需要把同一用户的请求路由到同一个数据中心。

单调读

用户可能会遇到时光倒流。
第一次请求到从库看到了评论，第二次请求到另外一个从库发现评论消失。

用户首先从新副本读取，然后从旧副本读取。时光倒流。为了防止这种异常，我们需要单调的读取

确保每个用户总是从同一副本来读取。比如基于用户 ID 的散列来选择副本，而不是随机选。
但是如果该副本失败，则需要路由到另一个副本。

一致前缀读

第三个复制延迟例子违反了因果律。想象一下Poons先生和Cake夫人之间的以下简短对话：

Mr. Poons Mrs. Cake，你能看到多远的未来？

Mrs. Cake 通常约十秒钟，Mr. Poons.

现在，想象第三个人正在通过从库来听这个对话。 Cake夫人说的内容是从一个延迟很低的从库读取的，但Poons先生所说的内容，从库的延迟要大的多,于是，这个观察者会听到以下内容：

Mrs. Cake 通常约十秒钟，Mr. Poons.

Mr. Poons Mrs. Cake，你能看到多远的未来？

如果某些分区的复制速度慢于其他分区，那么观察者在看到问题之前可能会看到答案。

方法：

任何因果相关的写入都写入相同的分区。

复制延迟的解决方案

可以信赖数据库：需要事务。
事务（transaction）存在的原因：数据库通过事务提供强大的保证，所以应用程序可以更加简单。
单节点事务存在了很长时间，但是分布式数据库中，许多系统放弃了事务。“因为事务的代价太高。”

多主复制

基于领导者的复制模型的自然延伸是允许多个节点接受写入。复制仍然以同样的方式发生：处理写入的每个节点都必须将该数据更改转发给所有其他节点。称之为多领导者配置（也称多主、多活复制）。在这种情况下，每个领导者同时扮演其他领导者的追随者。

多主复制的应用场景

运维多个数据中心

跨多个数据中心的多主复制

需要离线操作的客户端

多主复制的另一适用场景：应用程序在断网后仍然需要继续工作。
在这种情况下，每个设备都有一个充当领导者的本地数据库（它接受写请求），并且在所有设备上的日历副本之间同步时，存在异步的多主复制过程。复制延迟可能是几小时甚至几天，具体取决于何时可以访问互联网。
每个设备相当于一个“数据中心”

协同编辑

协作式编辑不能视为数据库复制问题，但是与离线编辑有许多相似
一个用户编辑文档时，所做的更改将立即应用到其本地副本（web 或者客户端），并异步复制到服务器和编辑同一文档的任何其他用户。
如果想要不发生编辑冲突，则应用程序需要先将文档锁定，然后用户才能进行编辑；如果另一用户想编辑，必须等待第一个用户提交修改并释放锁定。这种协作模式相当于主从复制模型下在主节点上执行事务操作。
但是，为了加速写作，可编辑的粒度需要非常小（例如单个按键，甚至全程无锁）。
也会面临所有多主复制都存在的挑战，即如何解决冲突。

处理写入冲突

多领导者复制的最大问题是可能发生写冲突，因此需要解决冲突。
单主数据库没有这个问题。
假如两个用户同时修改标题：用户1将页面的标题从A更改为B，并且用户2同时将标题从A更改为C。每个用户的更改已成功应用到其本地主库。但当异步复制时，会发现冲突

两个主库同时更新同一记录引起的写入冲突

同步与异步冲突检测

● 单主数据库：第二个写入被阻塞，并等待第一个写入完成，或被终止；
● 多主配置：两个写入都成功，稍后的时间点仅仅异步地监测到冲突。
● 如果想冲突检测同步-等待被写入到所有的副本，那么丢失了多主复制的优点。

避免冲突

● 处理冲突的最简单策略是避免它们：确保特定记录的写入都通过同一个领导者，就不会有冲突。
● 但是，如果更改指定的记录主库——比如数据中心故障，需要把流量重新路由；冲突避免会中断，必须处理不同主库同时写入的可能性。

收敛至一致的状态

● 单主数据库按顺序进行写操作：如果同一个字段有多个更新，则最后一个写操作将决定该字段的最终值。
● 在多主配置中，没有明确的写入顺序，所以最终值应该是什么并不清楚。
● 每个复制方案都必须确保数据在所有副本中最终都是相同的。
● 数据库必须以一种收敛（convergent）的方式解决冲突，这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。

实现冲突合并解决有多种途径：
● 给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。
● 为每个副本分配一个唯一的ID，ID编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
● 以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们
● 用一种可保留所有信息的显式数据结构来记录冲突，并编写解决冲突的应用程序代码（也许通过提示用户的方式）。

自定义冲突解决逻辑

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

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

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

自动冲突解决
规则复杂，容易出错。
● 无冲突复制数据类型（Conflict-free replicated datatypes）：是可以由多个用户同时编辑的集合，映射，有序列表，计数器等的一系列数据结构，它们以合理的方式自动解决冲突。一些CRDT已经在Riak 2.0中实现
● 可合并的持久数据结构（Mergeable persistent data structures）显式跟踪历史记录，类似于Git版本控制系统，并使用三向合并功能（而CRDT使用双向合并）。
● 可执行的转换（operational transformation）是 Etherpad 和Google Docs 等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列表而设计的，例如构成文本文档的字符列表。

什么是冲突？

● 显而易见的冲突：两个写操作并发地修改了同一条记录中的同一个字段。
● 微秒的冲突：一个房间接受了两个预定。

多主复制拓扑

● 复制拓扑（replication topology）描述写入从一个节点传播到另一个节点的通信路径。
● 只有两个领导者时，只有一个合理的拓扑：互相写入。
● 当有两个以上的领导，拓扑很多样：

三个可以设置多领导者复制的示例拓扑

全部到全部拓扑的问题
● 网络问题导致消息顺序错乱

使用多主程序复制时，可能会在某些副本中写入错误的顺序。

无主复制

在一些无领导者的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个协调者（coordinator）节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。

当节点故障时写入数据库

仲裁写入，法定读取，并在节点中断后读修复。

无主复制中，故障切换不存在。
如果一个副本故障或下线，重启后提供的数据是落后的。
解决办法：客户端同时请求多个副本，根据版本号确定最新值。

读修复和反熵

读写的法定人数

如果我们知道，每个成功的写操作意味着在三个副本中至少有两个出现，这意味着至多有一个副本可能是陈旧的。因此，如果我们从至少两个副本读取，我们可以确定至少有一个是最新的。如果第三个副本停机或响应速度缓慢，则读取仍可以继续返回最新值。

更一般地说，如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。（在我们的例子中， $n = 3，w = 2，r = 2$ ）。只要 $w + r> n$ ，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数

法定人数一致性的局限性

但是，即使在 $w + r> n$ 的情况下，也可能存在返回陈旧值的边缘情况。
● 如果使用了宽松的法定人数，w 个写入和 r 个读取落在完全不同的节点上。
● 两个写入同时发生，不清楚哪一个先发生。
● 写操作和读操作同时发生，写操作可能仅反映在某些副本上。
● 写操作在某些副本上成功，而在其他节点上失败，在小于w个副本上写入成功。
● 如果携带新值的节点失败，需要读取其他带有旧值的副本。
● 即使一切工作正常，有时也会不幸地出现关于时序（timing）的边缘情况。

不要把 w 和 r 当做绝对的保证，应该看做是概率。
强有力的保证需要事务和共识。

宽松的法定人数与提示移交

● 合理配置的法定人数可以使数据库无需故障切换即可容忍个别节点的故障。
● 需要高可用、低延时、且能够容忍偶尔读到陈旧值的应用场景来说，这些特性使无主复制的数据库很有吸引力。