设计数据密集型应用程序 - Replication

设计数据密集型应用程序 - Replication

Replication 就是将相同数据的拷贝防止在多个通过网络连接在一起的机器上。

为什么需要 Replication

  • 让数据在地理位置上更靠近用户
  • 部分数据坏掉的时候,系统依然能持续工作
  • 可伸缩,增加机器即可增加吞吐量

如果你需要 replication 的数据不发生变化,那么 replication 的过程是及其简单的,你只需拷贝到其它各个机器上,然后你的任务就完成了。然而 replication 最难的地方也就在这个地方,如何处理变化的数据?接下来就介绍三种常见的处理 replication 中数据变化的算法: single-leader、multi-leader、leaderless。

Leaders 和 Followers

每一个存储一份数据库拷贝的节点称之为: replica。每一个 replica 都需要处理写数据的操作,久而久之,每一个节点之间存储的数据也就不再一致了。解决这种问题最常见的办法就是: leader-based replication (active/passive 或 master-slave replication),它的工作原理如下:

  • 其中某个 replica 被指定为 leader (master 或 primary),客户端想要写数据,那么必须将它们的写数据的请求发送给 leader,然后 leader 随后写入到自己的本地磁盘中。
  • 其余的 replica 称之为 follower (read replicas, slaves, secondaries, hot standbys),当 leader 写入数据到本地磁盘的时候,同时将数据改变的部分作为 replication log 或者 change stream 发送给它的 followers。每一个 follower 根据收到的 log 按照和 leader 处理不同写操作之间的相同的顺序,来更新它自己本地的数据。
  • 当一个客户端想要读取数据的时候,它可以发送读请求给 leader 或者任意一个 follower。但是写请求的话只能发送给 leader。

这种模式的 replication 内置在许多数据库中,例如: PostgreSQL、MySQL、Oracle Data Guard、SQL Server 的 AlwaysOn Availability Groups,甚至在许多非关系型数据库中也有它的身影,例如: MongoDB、RethinkDB、Espresso,这种模式也局限于数据库,像消息中间件 Kafka 和 RabbitMQ 高可用的队列都依赖它,一些网络文件系统和 replicated block devices 例如 DRBD 也是同样的道理。

同步和异步 Replication

replication 数据的过程可以分为同步或者异步。如下图所示,follower 1 配置为同步的,leader 等待 follower 1 确认它收到了 log 之后,才向 client 反馈更新成功;而被配置为异步的 follower 2 则无须这一步,leader 可以直接反馈更新成功。

显然在 leader 响应 OK 与 follower 2 接受并处理完毕 write 请求之间是存在延迟的,尽管多数数据库系统的 replication 的过程是非常快的,然而这个时间的上限谁也并没有保证。follower 可能刚刚重启、follower 系统满负载了、leader 到 follower 之间的网络出现故障了等等,都有可能导致 follower 的数据落后 leader 1分钟或者多分钟。

同步 replication 的优势在于 follower 总能保持和 leader 实时的一致性的数据,如果 leader 突然不可用了,我们可以确保数据在 follower 上仍然是可用的。缺点在于如果 follower 出现了问题,比如 crash 了,网络故障了,写这个操作就没办法进行下去了,leader 此刻必须阻塞等待 replica 变为可用状态才能继续处理其他 write 操作。

所以,维持整个系统的所有 replica 一致性状态是不切实际的。实际上,如果你在数据库中启用了同步 replication,它通常是指指定一个 follower 变为同步的,其它的 follower 依然是异步的,如果同步的 follower 变得不可用或者速度变慢,那么某一个异步的 follower 将会晋升为同步的 follower,这保证了总是有两个节点 leader 和一个 follower 始终维持最新的数据。这种配置有时候也称之为 semi-synchronous

通常,leader-based replication 被配置为全部是异步的,如果 leader 一旦失败不可恢复,那么所有的还未同步给 follower 节点的写数据将会丢失,这也就意味着写不保证一定写成功。它的优势在于即使所有的 follower 都不可用,leader 依然可以处理写请求。

对于异步 replication 来说,leader 失败后的数据丢失是很严重的,所以当前也有针对其不丢失数据同时提供良好性能和可用性的方法。例如链 replication ,其是同步复制的一个变种,它已经成功应用在 Microsoft Azure Storage 系统中。

配备新的 follower

  • 定时对 leader 的数据库构建快照。
  • 将快照拷贝到 follower 机器上。
  • follower 连接上 leader,请求所有自快照到最新版本之间变更的数据,这就需要快照本身关联到 leader 的 replication log 的一个精确的位置上。PostgreSQL 称之为 log sequence number,MySQL 称之为 binlog coordinates。
  • 当 follower 处理完自 snapshot 创建之后堆积的数据变化后,我们称它追赶上了 leader。接下来,它继续处理来自 leader 发送过来的 log 即可。

处理节点中断

我们的目标是在单个节点发生故障的情况下,保持系统作为一个整体运行,并使节点中断的影响尽可能小。

follower 失败: 赶快恢复

follower 每次收到 log 之后,都会先记录在本地磁盘中,所以当它恢复之后也能很快知道它发生故障时正在处理的最后一个事务,它可以继续连接上 leader,然后请求在这之间发生的数据变更的 log ,当它应用这些 log 后,也就追上了 leader,意味着可以继续像之前一样继续接受数据流了。

leader 失败: 故障转移

leader 失败后: 某一个 follower 被提拔为 leader,客户端需要将 write 请求发送至新的 leader,其它 follower 需要从新的 leader 消费数据,这个过程称之为 failover (故障转移)。

failover 既可以自动执行,也可以手动执行,一个自动执行的 failover 包含如下步骤:

  • 检测 leader 是否失败了。多数都是使用超时时间来检测节点是否存活。
  • 选择新的 leader。这可以通过一个选举过程来完成(在这种过程中,leader 是由剩余副本的大多数选择的),也可以由先前选择的控制器节点指定新的 leader。leader 的最佳人选通常是具有最新数据更改的副本(以尽量减少数据丢失)。让所有节点都同意一个新的 leader 是一个共识问题。
  • 重新配置系统以使用新的领导者。client 现在需要将他们的写请求发送给新的 leader 。如果原来的 leader 恢复了,它可能仍然相信自己是 leader,却没有意识到其他 replicas 已经迫使它下台了。系统需要确保旧的 leader 成为 follower,并识别新的 leader。

故障切换充满了风险:

  • 如果采用的是异步 replication,那么新推选出来的 leader 可能还没有接收完所有的 old leader 在失败前发送的写请求。如果前一个 leader 又回来了,那么应该如何协调?新的 leader 同样可能收到写请求。最常见的做法是,直接丢弃 old leader 未被 replicated 的写请求,但这可能和客户端的高可用性原则相违背。
  • 如果数据库之外的其他存储系统需要和数据库内容进行协调,丢弃写请求则是非常危险的行为。
  • 某些情况下,可能出现两个节点都认为自己是 leader 的情况,这称之为 split brain。这是及其危险的,如果二者均接受到了写的请求,而又没有其他进程去协调,那么数据有可能出现混乱或者丢失。作为一种安全保护,部分系统在检测到出现了两个 leader 的时候,会强制性关闭某个 leader,但是如果设计的不好的话,也可能会出现两个 leader 都被关闭的尴尬状态。
  • 宣告 leader 死亡的合适的超时时间是多久?时间久一点的意味着久一点才能恢复,时间短一点的,会造成不必要的故障切换,占用不必要的网络带宽和系统资源。

这些问题并没有简单的方法来去解决。鉴于此,部分系统默认需要手动进行故障切换,即使它本身能够支持自动鼓掌切换。

实现 replication log

面向语句的 replication

最简单的是,将每次需要执行的语句 (statement) 的 log 发送给 follower。在关系型数据库中,每一次的 INSERT、UPDATE、DELETE 等语句需要发送给 follower,follower 需要解析并处理这些语句。这种方式听起来还可以,然而还是有一些情况会出现问题:

  • 某些语句调用了 NOW() 或者 RAND() 这样的函数,每次得到的都是不同的数值,应该如何同步过去?
  • 如果语句使用了自增列,或者他们依赖数据中已有的数据进行判断 (UPDATE … WHERE 某些条件),他们就必须在每一个 replica 上严格按照顺序执行,否则就可能产生不同的结果,这显然不利于并发事务的执行。
  • 有副作用的语句 (触发器、存储过程、用户自定义函数等) 可能在不同节点上会造成不同的副作用,除非这种副作用是明确的,能提前预测到的。

解决这些问题是可能的,例如,当记录语句时,leader 可以用一个固定的返回值替换任何不确定的函数调用,以便 follower 都获得相同的值。但是,由于存在太多的边缘情况,现在通常首选其他复制方法。

基于语句的复制在 5.1 版之前的MySQL中使用。由于它非常紧凑,所以现在仍然使用它,但是默认情况下,如果语句中存在任何不确定性,MySQL 现在会切换到基于行的复制

预写日志 (WAL)

WAL 中的内容: 哪一块磁盘的哪几个字节的数据被修改了,这使得 WAL 日志和存储引擎关联到一起了。如果数据库将存储格式换为另外一个版本,那么不太可能运行不同的数据库软件。

如果复制协议允许 follower 使用更新的软件版本与 leader 相比,您可以执行数据库软件的零停机升级,方法是先升级 follower,然后执行故障转移,使升级的节点之一成为新的leader。如果复制协议不允许这种版本不匹配,就像 WAL-shipping 的情况一样,这种升级需要停机。

逻辑(基于行) 的 log replication

另一种方法是对复制和存储使用不同的日志格式引擎,它允许复制日志与存储引擎内部分离。这种复制日志称为逻辑日志,以区别于存储引擎的(物理)数据表示。

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

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

一个修改多行的事务会生成多个这样的日志记录,后面跟着一个指示事务已提交的记录。MySQL的 binlog(当配置为使用基于行的复制时)使用的就是这种方法。

由于逻辑日志与存储引擎内部分离,因此可以更容易地保持向后兼容,从而允许 leader 和 follower 运行不同版本的数据库软件,甚至不同的存储引擎。

逻辑日志格式也更易于外部应用程序解析。如果要将数据库的内容发送到外部系统(如用于脱机分析的数据仓库或用于构建自定义索引和缓存)的话,此特性非常有用。这种技术称为变更数据捕获。

基于触发的 replication

到目前为止描述的复制方法是由数据库系统实现的,不涉及任何应用程序代码。在许多情况下,这正是您想要的,但有些情况下需要更大的灵活性。例如,如果您只想复制数据的一个子集,或者想从一种数据库复制到另一种数据库,或者需要冲突解决逻辑,则可能需要将复制向上移动到应用程序层。

一些工具,如 Oracle GoldenGate,可以通过读取数据库日志使数据更改对应用程序可用。另一种方法是使用许多关系数据库中可用的特性:触发器和存储过程。

触发器允许您注册在数据库系统中发生数据更改(写入事务)时自动执行的自定义应用程序代码。可以把它从一个外部进程读成一个独立的进程,这个进程可以从这个进程中读出来。然后,该外部进程可以应用任何必要的应用程序逻辑,并将数据更改复制到另一个系统。例如,Oracle的 Databus 和 Postgres 的 Bucardo 都是这样工作的。

基于触发器的复制通常比其他复制方法的开销更大,而且比数据库的内置复制更容易出现错误和限制。然而,由于其灵活性,它仍然是有用的。

复制延迟问题

基于 Leader 的复制要求所有写操作都通过单个节点,但只读查询可以转到任何副本。对于主要由读操作和少量写入操作组成的工作负载(web上的一种常见模式),有一个很有吸引力的选项:创建许多 follower,并在这些 follower 之间分发读取请求。这将从 leader 中移除负载,并允许附近的副本为读请求提供服务。

在这种读扩展架构中,只需添加更多 follower,就可以增加为只读请求提供服务的容量。但是,这种方法只适用于异步复制,如果您尝试同步复制到所有 follower,单个节点故障或网络中断将使整个系统无法写入。你拥有的节点越多,就越有可能出现故障,因此完全同步的配置就非常不可靠。

不幸的是,如果应用程序从异步 follower 读取数据,那么如果 follower 落后,它可能会看到过时的信息。这会导致数据库中明显的不一致性:如果同时对 leader 和 follower 运行相同的查询,可能会得到不同的结果,因为并非所有的写入都能即时地反映在 follower 中。这种不一致只是一种暂时的状态,如果你停止对数据库的写入并等待一段时间,follower 最终会赶上并与 leader 保持一致。因此,这种效果被称为最终一致性

“最终”一词故意含糊其辞:一般来说,replica 节点的落后程度没有限制。在正常操作中,在主服务器上执行写入操作与在从服务器上反映复制延迟之间的延迟可能只有几秒钟,在实践中并不明显。但是,如果系统在接近负载容量的情况下运行,或者网络出现问题,延迟很容易增加到几秒钟甚至几分钟。

当滞后如此之大时,它所带来的不一致性不仅仅是一个理论问题,而是一个实际的应用问题。在本节中,我们将重点介绍三个复制延迟时可能出现的问题,并概述一些解决这些问题的方法。

读取你自己写入的数据

许多应用程序允许用户提交一些数据,然后查看他们提交的内容。这可能是客户数据库中的一条记录,或者是论坛上的评论,或者其他类似的东西。当新数据被提交时,它必须被发送给 leader,但是当用户查看数据时,它可以从 follower 那里读取。如果经常查看数据但只是偶尔写入数据,这一点尤其合适。

在这种情况下,我们需要 read-after-write 一致性,也称为 read-your-writes 一致性。这是一个保证,如果用户重新加载页面,他们将始终看到自己提交的任何更新。它对其他用户不做任何承诺:其他用户的更新可能要等到以后才能看到。但是,它保证用户自己的输入已经正确保存。

如何在 leader-based 系统中实现 read-after-write 一致性:

  • 读取用户可能已修改的内容时,请从 leader 那读取;否则,从 follower 那里读。这需要您有某种方法来知道某些内容是否已被修改,而无需实际查询它。例如,社交网络上的用户配置文件信息通常只能由个人资料的所有者编辑,而不能由其他任何人编辑。因此,一个简单的规则是:始终从 leader 处读取用户自己的配置文件,从 follower 读取任何其他用户的配置文件。
  • 如果应用程序中的大多数内容都有可能被用户编辑,那么这种方法就不会有效,因为大多数内容都必须从 leader 那里读取(否定了读伸缩的好处)。在这种情况下,可以使用其他标准来决定是否向 leader 读取。例如,您可以跟踪最后一次更新的时间,并在最后一次更新后的一分钟内,从 leader 读取所有数据。您还可以监视 followers 上的复制延迟,并防止对任何落后于 leader 一分钟以上的 follower 进行查询。
  • 客户端可以记住其最近写入的时间戳,然后系统可以确保服务于该用户的任何读取的副本,至少要能够反映出那个时间点之前的更新都是最新的。如果副本不够及时,则可以由另一个副本处理读取,或者查询可以等到复制副本追上那个时间点为止。时间戳可以是逻辑时间戳(指示写入顺序的东西,例如日志序列号)或实际系统时钟(在这种情况下时钟同步变得至关重要)。
  • 如果您的副本分布在多个数据中心(地理位置上更接近用户或更可用),还有额外的复杂性。任何需要由 leader 提供服务的请求都必须路由到包含该 leader 的数据中心。

当同一个用户从多个设备(例如桌面 web 浏览器和移动应用程序)访问您的服务时,另一个复杂的问题就会出现。在这种情况下,您可能需要提供跨设备的 read-after-write 一致性:如果用户在一个设备上输入一些信息,然后在另一个设备上查看它,那么他们应该看到他们刚刚输入的信息。

这种情况下,还需要考虑其它问题:

  • 需要记住用户上次更新的时间戳的方法变得更加困难,因为在一个设备上运行的代码不知道另一个设备上发生了什么更新。这个元数据需要集中化
  • 如果复制副本分布在不同的数据中心,则无法保证来自不同设备的连接将路由到同一个数据中心。(例如,如果用户的桌面计算机使用家庭宽带连接,而他们的移动设备使用蜂窝数据网络,则设备的网络路由可能完全不同。)如果您的方法需要从 leader 处读取,则您可能首先需要将请求从用户的所有设备路由到同一数据中心。

单调读

我们的第二个例子是,当从异步 follower 读取数据时,可能会发生异常,即用户可能会看到时间线上向后移动的东西。

如果用户从不同的副本进行多次读取,就会发生这种情况。例如,图 5-4 显示用户 2345 对同一个查询进行了两次,首先是对延迟较小的 follower,然后是延迟较大的 follower。(如果用户刷新一个网页,并且每个请求都被路由到一个随机服务器,这种情况很可能发生。)第一个查询返回用户 1234 最近添加的评论,但是第二个查询没有返回任何内容,因为滞后的 follower 还没有接收到该写入。实际上,第二个查询是在比第一个查询更早的时间点来观察系统。如果第一个查询没有返回任何内容,这不会太糟糕,因为用户 2345 可能不知道用户 1234 最近添加了一个评论。然而,如果用户 2345 首先看到用户 1234 的评论出现,然后又看到它消失,这会让他们非常困惑。

单调读保证了这种异常不会发生。这是比强一致性弱的保证,但比最终一致性更有力的保证。当您读取数据时,您可能会看到一个旧值;单调读取仅意味着如果一个用户按顺序进行多次读取,他们将看不到时间倒流,也就是说,在先前读取了较新的数据之后,他们不会再读取较旧的数据。

实现单调读取的一种方法是确保每个用户总是从同一个副本进行读取(不同的用户可以从不同的副本读取)。例如,可以根据用户 ID 的哈希值选择副本,而不是随机选择。但是,如果该复制副本失败,则需要将用户的查询重新路由到另一个副本。

一致的前缀读取

复制滞后异常的第三个例子涉及违反因果关系。你有可能先看到答案而非问题:

防止这种异常需要另一种类型的保证:一致的前缀读取。这个保证说,如果一个写入序列按一定的顺序发生,那么任何阅读这些写入的人都会看到它们以相同的顺序出现。

这是分区(分片)数据库中的一个特殊问题,我们将在第 6 章中讨论。如果数据库总是以相同的顺序应用写操作,那么读取总是会看到一致的前缀,因此不会发生这种异常情况。但是,在许多分布式数据库中,不同的分区是独立运行的,因此没有全局写入顺序:当用户从数据库中读取时,他们可能会看到数据库的某些部分处于旧状态,而另一些部分处于较新状态。

一种解决方案是确保任何与彼此有因果关系的写操作都写入同一个分区,但在某些应用程序中无法有效地执行。还有一些算法可以明确地跟踪因果依赖关系,我们后续继续讨论。

复制滞后的解决方案

在使用最终一致的系统时,如果复制延迟增加到几分钟甚至几个小时,那么应该考虑应用程序的行为。如果答案是“没问题”,那就太好了。但是,如果结果对用户来说是一种不好的体验,那么重要的是要设计出一个更强大的保证,比如先读后写。假装复制是同步的,而实际上它是异步的,这是导致问题的根本原因。

如前所述,应用程序可以提供比底层数据库更强的保证,例如,通过对 leader 只执行某些类型的读取。然而,在应用程序代码中处理这些问题很复杂,而且很容易出错。

如果应用程序开发人员不必担心细微的复制问题,而只需信任他们的数据库“做正确的事情”,那就更好了。这就是为什么存在事务:事务是数据库提供更强大保证的一种方式,这样应用程序可以更简单。

单节点事务已经存在很久了。然而,在向分布式(复制和分区)数据库转移的过程中,许多系统放弃了它们,声称事务在性能和可用性方面过于昂贵,并断言在可伸缩系统中,最终的一致性是不可避免的。这句话有些道理,但过于简单化了,我们将在本书的其余部分形成一个更细致的观点。

多 Leader 复制

Leader-based 的复制有一个主要的缺点:只有一个 leader,所有写入都必须经过它。如果你因为任何原因无法连接到 leader,例如由于你和 leader 之间的网络中断,你就不能写入数据库。

基于 leader 的复制模型的一个自然扩展是允许多个节点接受写操作。复制仍然以同样的方式进行:每个处理写操作的节点都必须将数据更改转发给所有其他节点。我们称之为多 leader 配置(也称为主-主或主动/主动复制)。在此设置中,每个 leader 同时充当其他 leader 的 follower。

多 Leader 复制的案例

(1)多数据中心

假设您有一个数据库,在多个不同的数据中心中都有副本(可能是为了让您能够容忍整个数据中心的故障,或者是为了更接近您的用户)。对于普通的基于 leader 的复制设置,leader 必须位于其中一个数据中心中,并且所有的写操作都必须经过该数据中心。

在多 leader 配置中,每个数据中心都可以有一个 leader。下图显示了这个架构可能是什么样子。在每个数据中心内,使用常规的主从复制;在数据中心之间,每个数据中心的领导者将其更改复制到其他数据中心的领导者。

让我们比较一下 single-leader 和多 leader 配置在多数据中心部署中的表现:

  • 性能

在单 leader 配置中,每次写入都必须通过网络发送到数据中心。这可能会给写入操作增加很大的延迟,并且可能与首先拥有多个数据中心的目的相抵触。在多 leader 配置中,每个写入都可以在本地数据中心进行处理,并异步复制到其他数据中心。因此,数据中心间的网络延迟对用户是隐藏的,这意味着感知性能可能更好。

  • 数据中心中断容忍度

在单 leader 配置中,如果具有该 leader 的数据中心发生故障,则进行故障转移,可以将另一个数据中心的 follower 提升为 leader。在多 leader 配置中,每个数据中心都可以独立于其他数据中心继续运行,当出现故障的数据中心恢复联机时,复制将迎头赶上。

  • 网络问题容忍度

数据中心之间的通信通常通过公共互联网,这可能不如数据中心内的本地网络可靠。单 leader 配置对这个数据中心间链路中的问题非常敏感,因为写操作是在这个链路上同步进行的。具有异步复制的多 leader 配置通常可以更好地容忍网络问题:临时网络中断不会阻止正在处理的写操作。

一些数据库默认支持多 leader 配置,但也经常使用外部工具来实现,例如用于 MySQL 的 Tungsten Replicator、用于 PostgreSQL 的 BDR 和用于 Oracle 的 GoldenGate。

虽然多 leader 复制有其优点,但也有一个很大的缺点:相同的数据可能在两个不同的数据中心中被并发修改,并且这些写入冲突必须得到解决。

(2)脱机操作的客户端

另一种适合多 leader 复制的情况是,如果您的应用程序需要在与网络断开连接的情况下继续工作。

例如,考虑一下手机、笔记本电脑和其他设备上的日历应用程序。您需要能够随时查看您的会议(发出读取请求)和输入新会议(发出写入请求),而不管您的设备当前是否具有网络连接。如果在脱机时进行了任何更改,则需要在设备下次联机时与服务器和其他设备同步。

在这种情况下,每个设备都有一个本地数据库充当 leader 服务器(它接受写入请求),并且在所有设备上的日历副本之间有一个异步多 leader 复制过程(sync)。复制延迟可能是数小时甚至几天,这取决于您何时可以访问网络。

从体系结构的角度来看,这种设置本质上与数据中心之间的多 leader 复制相同,达到了极致:每个设备都是一个“数据中心”,它们之间的网络连接极其不可靠。正如有很多历史记录需要同步,复制是一个棘手的问题。

有一些工具旨在使这种多 leader 配置更容易。例如,CouchDB 就是为这种操作模式而设计的。

(3)协同编辑

实时协作编辑应用程序允许多人同时编辑文档。例如,Etherpad 和 Google Docs 允许多人同时编辑文本文档或电子表格。

我们通常不认为协作编辑是数据库复制问题,但它与前面提到的脱机编辑用例有很多共同之处。当一个用户编辑文档时,更改会立即应用到其本地副本(文档在其web浏览器或客户端应用程序中的状态),并异步复制到服务器和正在编辑同一文档的任何其他用户。

如果要保证不会发生编辑冲突,则应用程序必须先获得文档的锁定,然后用户才能编辑它。如果另一个用户想要编辑同一个文档,他们首先必须等到第一个用户提交了他们的更改并释放了锁。此协作模型相当于在主节点上使用事务进行单 leader 复制。

但是,为了更快的协作,您可能希望将更改单元设置得非常小(例如,一次击键)并避免锁定。这种方法允许多个用户同时编辑,但也带来了多 leader 复制的所有挑战,包括需要解决冲突。

处理写入冲突

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

例如,考虑一个由两个用户同时编辑的 wiki 页面,如图所示。用户1将页面标题从A更改为B,用户2同时将标题从A更改为C。每个用户的更改都成功地应用于其本地 leader。但是,当异步复制更改时,会检测到冲突。此问题不会出现在单个 leader 数据库中。

(1)同步冲突检测与异步冲突检测

在单 leader 数据库中,第二个写入程序将阻塞并等待第一次写入完成,或者中止第二次写入事务,迫使用户重试写入。另一方面,在多 leader 设置中,两次写入都是成功的,并且冲突只在稍后的某个时间点异步检测到。此时,要求用户解决冲突可能为时已晚。

原则上,您可以使冲突检测同步,即等待写入复制到所有副本,然后再告诉用户写入成功。但是,这样做,您将失去多 leader 复制的主要优势:允许每个复制副本独立地接受写操作。如果您希望使用单次复制,那么也可以使用单次复制。

(2)避免冲突

处理冲突的最简单策略是避免冲突:如果应用程序可以确保对特定记录的所有写入都经过同一个 leader,那么就不会发生冲突。由于许多多 leader 复制的实现处理冲突的能力相当差,因此避免冲突是一种经常被推荐的方法。

例如,在一个用户可以编辑自己的数据的应用程序中,可以确保来自特定用户的请求始终路由到同一个数据中心,并使用该数据中心中的 leader 进行读写。不同的用户可能有不同的“家庭”数据中心(可能是根据地理位置与用户的接近程度来选择的),但是从任何一个用户的角度来看,配置基本上是单一 leader 的。

但是,有时您可能需要更改记录的指定 leader,可能是因为一个数据中心发生故障,您需要将流量重新路由到另一个数据中心,或者可能是因为某个用户已移动到另一个位置,现在离另一个数据中心更近。在这种情况下,避免冲突就会失效,您必须处理在不同领导人身上并发写的可能性。

(3)向一致状态汇聚

单个 leader 的数据库按顺序执行写入:如果对同一字段进行多次更新,则最后一次的写入将确定字段的最终值。

在多 leader 配置中,没有定义写入顺序,因此不清楚最终值应该是什么。在上图中,在 leader 1,标题首先更新为B,然后更新为C;在leader 2,标题首先更新为C,然后更新到B。两个顺序都不比另一个“更正确”。

如果每个副本只是按照它看到写操作的顺序来执行写操作,那么数据库将以不一致的状态结束:在leader 1处,最终值为C,在leader 2处为B。这是不可接受的,每个复制方案都必须确保所有副本中的数据最终都是相同的。因此,数据库必须以一种收敛的方式解决冲突,这意味着当所有更新都被复制到子节点的时候,所有副本必须达到相同的最终值。

解决冲突的方法多种多样:

  • 给每个写操作一个唯一的ID(例如,一个时间戳、一个长随机数、一个UUID或一个键和值的散列),选择ID最高的写入作为赢家,并丢弃其他写操作。如果使用时间戳,这种技术称为最后写入胜利(LWW: last write wins)。尽管这种方法很流行,但它很容易导致数据丢失。
  • 为每个副本指定一个唯一的ID,并让源于编号较高的副本的写入始终优先于源于编号较低的副本的写入。这种方法还意味着数据丢失。
  • 以某种方式将这些值合并在一起—例如,按字母顺序排序,然后将它们连接起来(在上图中,合并的标题可能类似于“B/C”)。
  • 在保留所有信息的显式数据结构中记录冲突,并编写稍后解决冲突的应用程序代码(可能通过提示用户)。

(4)自定义冲突解决逻辑

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

当写入的时候: 一旦数据库系统在复制的更改日志中检测到冲突,它就会调用冲突处理程序。例如,Bucardo 允许您为此编写一个 Perl 代码片段。此处理程序通常无法提示在后台进程中运行的用户,必须快速执行。

当读的时候: 当检测到冲突时,将存储所有冲突的写入。下次读取数据时,这些数据的多个版本将返回到应用程序。应用程序可以提示用户或自动解决冲突,并将结果写回数据库。例如,CouchDB 就是这样工作的。

请注意,冲突解决通常适用于单个行或文档级别,而不是整个事务。因此,如果您有一个事务以原子方式进行多个不同的写入,出于解决冲突的目的,每个写入操作仍然是单独考虑的。

(5)冲突是什么

有些冲突是显而易见的。在上图的例子中,两个写操作同时修改了同一记录中的同一个字段,并将其设置为两个不同的值。毫无疑问,这是一场冲突。

其他类型的冲突可能更容易察觉。例如,考虑一个会议室预订系统:它跟踪哪个房间是由哪些人在某个时间预订的。此应用程序需要确保每个房间在同一时间仅由一组人预订(即,同一房间不得有任何重叠预订)。在这种情况下,如果同时为同一房间创建了两个不同的预订,则可能会发生冲突。即使应用程序在允许用户进行预订之前检查可用性,但如果两个预订是在两个不同的 leader 上进行的,则可能会发生冲突。

没有一个现成的快速答案,但是在下面的章节中,我们将追溯到一个好的理解这个问题的路径。

多 leader 复制拓扑

复制拓扑描述了写入从一个节点传播到另一个节点的通信路径。如果您有两个 leader,如上图所示,那么只有一个合理的拓扑:leader 1必须将它的所有写操作发送给leader 2,反之亦然。对于两个以上的 leader,可以使用各种不同的拓扑结构。一些例子如下图所示:

最普遍的拓扑结构是 all-to-all(图[c]),在这种拓扑中,每一个领导者都会将其写的内容发送给其他每一个领导者。然而,更严格的拓扑结构也有人使用:例如,MySQL默认只支持一个循环拓扑,其中每个节点接收来自一个节点的写操作,并将这些写入操作(加上自身的任何写入操作)转发到另一个节点。另一种流行的拓扑结构是星形的:一个指定的根节点将写操作转发给其他所有节点。星型拓扑可以推广到树。

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

循环拓扑和星型拓扑的一个问题是,如果只有一个节点发生故障,它可能会中断其他节点之间的复制消息流,导致它们在节点修复之前无法通信。可以对拓扑进行重新配置,以解决出现故障的节点,但在大多数部署中,这种重新配置必须手动完成。更密集连接的拓扑(如all-to-all)的容错性更好,因为它允许消息沿着不同的路径传输,避免了单点故障。

另一方面,all-to-all 拓扑也可能有问题。特别是,某些网络链路可能比其他链路快(例如,由于网络拥塞),结果是一些复制消息可能“超过”其他的,如图所示。

在上图中,client A 在 leader 1 的表中插入一行,client B 更新 leader 3 上的该行。但是,leader 2 可能以不同的顺序接收写入:它可能首先接收更新(从它的角度来看,这是对数据库中不存在的行的更新),然后才接收相应的 insert(应该在更新之前)。

这是一个因果关系的问题,类似于我们在“一致前缀读取”中看到的问题:更新依赖于先前的插入,所以我们需要确保所有节点首先处理插入,然后处理更新。仅仅在每次写操作上附加一个时间戳是不够的,因为不能相信时钟足够同步,以便在 leader 2 中正确地对这些事件排序。

为了对这些事件进行正确的排序,可以使用一种称为版本向量的技术,我们将在本章后面讨论。然而,在许多多 leader 复制系统中,冲突检测技术的实现并不理想。例如,在撰写本文时,PostgreSQL BDR 不提供写入的因果顺序,Tungsten Replicator For MySQL 甚至不尝试检测冲突。

如果您使用的是具有多 leader 复制的系统,那么有必要了解这些问题,仔细阅读文档,并彻底测试数据库,以确保它确实提供了您认为它具有的保证。

无 leader 复制

到目前为止,我们在本章中讨论的复制方法是基于这样一种思想:客户端向一个节点(主站)发送写请求,而数据库系统负责将写操作复制到其他副本。leader 决定了处理写操作的顺序,follower 以相同的顺序执行 leader 的写操作。

有些数据存储系统采用了不同的方法,放弃了 leader 的概念,允许任何复制副本直接接受来自客户端的写操作。一些最早的复制数据系统是无领导的,但在关系数据库占主导地位的时代,这一想法基本上被遗忘了。在亚马逊将其用于内部发电机系统之后,它再次成为一种流行的数据库架构。Riak、Cassandra 和 Voldemort 都是源代码开放的数据存储库,采用的是受 Dynamo 启发的无领导复制模型,因此这种数据库也被称为 Dynamo 样式。

在一些无领导的实现中,客户端直接将其写操作发送到多个副本,而在其他一些实现中,协调器节点代表客户端执行此操作。但是,与 leader 数据库不同,该协调器不强制执行特定的写入顺序。我们将看到,这种设计上的差异对数据库的使用方式有着深远的影响。

节点 down 时写入数据库

假设您有一个包含三个副本的数据库,其中一个副本当前不可用—可能它正在重新启动以安装系统更新。在基于 leader 的配置中,如果要继续处理写操作,则可能需要执行故障转移。

另一方面,在无 leader 配置中,不存在故障转移。下图显示了发生的情况:客户端(用户1234)并行地向所有三个副本发送写操作,两个可用副本接受写入操作,但未写入不可用的副本。假设三个副本中有两个确认写入就足够了:在用户1234收到两个ok响应之后,我们认为写入是成功的。客户端只是忽略了其中一个副本没有写入的事实。

现在假设不可用的节点重新联机,客户端开始从中读取数据。节点关闭时发生的任何写入操作都将从该节点中丢失。因此,如果从该节点读取,可能会得到过时(过时)的值作为响应。

为了解决这个问题,当客户端从数据库中读取数据时,它不仅仅将其请求发送到一个副本:读取请求还被并行地发送到多个节点。客户端可能从不同的节点得到不同的响应;即,一个节点的最新值和另一个节点的过时值。版本号用于确定哪个值更新。

(1)读修复与反熵

复制方案应确保最终将所有数据复制到每个副本。当一个不可用的节点恢复联机后,它如何弥补它丢失的写操作?

Dynamo 式的数据存储中通常使用两种机制:

读修复: 当客户端从多个节点并行读取时,它可以检测到任何过时的响应。例如,在上图中,用户2345从副本3获取版本6值,从副本1和副本2获取版本7值。客户端发现副本3有一个过时的值,并将较新的值写回该副本。这种方法适用于经常读取的值

反熵过程: 此外,一些数据存储有一个后台进程,该进程不断查找副本之间的数据差异,并将丢失的数据从一个副本复制到另一个副本。与基于 leader 的复制中的复制日志不同,此反熵过程不会以任何特定的顺序复制写操作,而且在复制数据之前可能会有一个明显的延迟。

并不是所有的系统都实现了这两个功能;例如,Voldemort 目前还没有反熵过程。请注意,如果没有反熵过程,则很少读取的值可能会从某些副本中丢失,从而降低了持久性,因为只有在应用程序读取值时才会执行读取修复。

(2)仲裁读写

在上图的例子中,我们认为写入是成功的,即使它只在三个副本中的两个上处理。如果三个副本中只有一个接受了写操作呢?我们能强行得出这个结论吗?

如果我们知道每一次成功的写入都保证在三个副本中至少有两个副本上,这意味着最多只有一个副本过时。因此,如果我们从至少两个副本中读取,我们就可以确定其中至少有一个是最新的。如果第三个副本停止运行或响应速度慢,则读取仍可以继续返回最新值。

更一般地说,如果有 n 个副本,则每次写入都必须由 w 个节点确认为成功,并且每次读取都必须至少查询 r 个节点。(在我们的例子中,n = 3w = 2r = 2。)只要 w + r > n,我们就期望在读取时得到一个最新的值,因为至少有一个我们正在读取的 r 节点必须是最新的。遵循这些 rw 值的读和写被称为仲裁读写。你可以把 rw 看作读写有效所需的最低票数。

在 Dynamo 风格的数据库中,参数 nwr 通常是可配置的。一个常见的选择是将 n 设为奇数(通常为 3 或 5),并设置 w = r =(n + 1)/2(四舍五入)。但是,您可以根据需要改变数字。例如,一个写得少而读得多的工作负载可以从设置 w = nr = 1 中获益。这使得读取速度更快,但缺点是只有一个失败的节点会导致所有数据库写入失败。

仲裁条件 w + r > n 允许系统容忍不可用节点,如下所示:

  • 如果 w < n,如果某个节点不可用的时候,系统可以继续处理写请求
  • 如果 r < n,如果某个节点不可用的时候,系统可以继续处理读请求
  • n = 3w = 2r = 2 我们可以容忍一个节点不可用
  • n = 5w = 3r = 3 我们可以容忍两个节点不可用 (见下图)

通常,读写总是并行地发送到所有 n 个副本。参数 wr 决定了我们等待多少个节点,也就是说,在我们认为读或写成功之前,n 个节点中有多少个需要报告成功。

如果可用的 wr 节点少于所需数量,则写入或读取将返回错误。节点不可用的原因有很多:节点关闭(崩溃、断电)、执行操作时出错(磁盘已满而无法写入)、客户端和节点之间的网络中断,或其他任何原因。我们只关心节点是否返回成功的响应,而不需要区分不同类型的错误。

仲裁一致性的限制

如果有 n 个副本,并且选择 wr 使 w + r > n,则通常可以期望每次读取都返回为 key 写入的最新值。这种情况是因为您写入的节点集和从中读取的节点集必须重叠。也就是说,在您读取的节点中,必须至少有一个具有最新值的节点。

通常,rw 被选为节点的大多数(超过 n/2),因为这样可以确保 w + r > n,同时仍然可以容忍多达 n/2 个节点故障。但是 quorums 不一定是多数,它只关心读写操作使用的节点集至少在一个节点上重叠。其他的仲裁分配也是可能的,这使得分布式算法的设计具有一定的灵活性。

您还可以将 wr 设置为较小的数字,使 w + r ≤ n(即不满足法定人数条件)。在这种情况下,读和写操作仍将发送到 n 个节点,但操作成功所需的成功响应数较少。

对于较小的 wr,您更有可能读取过时的值,因为您的读取更有可能没有包含具有最新值的节点。有利的一面是,这种配置允许更低的延迟和更高的可用性:如果出现网络中断,并且许多副本变得无法访问,则您可以继续处理读写操作的可能性更大。只有当可访问副本的数量降到 wr 以下时,数据库才会分别变得不可写入或读取。

然而,即使 w + r > n ,也可能存在返回过时值的边缘情况。这些取决于实施情况,但可能的情况包括:

  • 如果使用草率仲裁w 写入可能会在不同的节点上结束,而 r 节点和 w 节点之间不再有保证的重叠。
  • 如果两个写操作同时发生,则不清楚哪一个先发生。在这种情况下,唯一安全的解决方案是合并并发写入。如果根据时间戳(最后一次写入获胜)选择赢家,则可能会由于时钟偏差而丢失写入。
  • 如果写操作与读操作同时进行,则写操作可能只反映在部分副本上。在本例中,无法确定读取是返回旧值还是新值。
  • 如果在某些副本上写入成功,但在其他副本上失败(例如,由于某些节点上的磁盘已满),并且在少于 w 个副本上总体成功,则不会在成功的副本上回滚。这意味着,如果写入被报告为失败,随后的读取可能会返回该写入的值,也可能不会返回。
  • 如果承载新值的节点出现故障,并且从承载旧值的副本恢复其数据,则存储新值的副本数可能会低于 w,从而破坏仲裁条件。
  • 即使一切工作正常,也有一些边缘情况,你可能会在时间上不走运,正如我们将在后续章节“线性化和量化”中看到的。

因此,尽管 quorums 看起来保证读返回最新的写入值,但实际上并不简单。Dynamo 风格的数据库通常针对能够容忍最终一致性的用例进行优化。参数 wr 允许您调整读取过时值的概率,但最好不要将它们作为绝对保证。

特别是,您通常得不到“复制延迟的问题”中讨论的保证(读写、单调读或一致前缀读),因此前面提到的异常可能会出现在应用程序中。更强有力的担保通常需要事务协商一致