数据库复制技术之三:最终一致性

19-01-07 banq
                   

前文讨论了数据库的多领导者复制,现在看看无领导者复制:

无领导者复制

亚马逊的DynamoDB推广的另一个想法 (虽然几十年前首次出现)就是没有领导者,每个副本都能接受写入(也许它应该被称为领导者?)。

看起来这将是一团糟,不是吗?如果我们与一些领导者有很多冲突需要处理,那么想象一下当到处都在进行写入时会发生什么。混沌!

好吧,事实证明这些数据库人员非常聪明,并且有一些聪明的方法来处理这种混乱。

基本思想是客户端不仅将写入发送到一个副本,而且发送到几个(或者在某些情况下,发送到所有副本)。

客户端将此写请求同时发送到多个副本,并且一旦得到其中一些副本的确认(我们将讨论有多少是“某些”)它可以认为写入成功并继续前进。

我们在这里的一个优点是我们可以更容易地容忍节点故障。想想在我们不得不向单个领导者发送写入的情况下会发生什么,并且出于某种原因,领导者没有回应。写入将失败,我们需要启动故障转移过程以选择可以再次开始接收写入的新领导者。没有领导者,没有故障转移,如果你还记得我们谈到的故障转移,你可能会明白为什么这可能是一个大问题。

但是,再次,没有免费的午餐,所以让我们来看看这里的价格标签。

例如,如果您的写入在2个副本中成功,但在1中失败(可能在您发送写入请求时该服务器正在重新启动)会发生什么?您现在有2个具有新值的副本和1个具有旧值的副本。请记住,这些副本不是相互通信的,没有领导者处理任何类型的同步。

现在,如果你从这个副本中读取BOOM,你会得到过时的数据。

为了解决这个问题,客户端不会从一个副本读取数据,而是同时向多个副本发送请求(就像写入一样)。然后,副本返回它们的值,以及某种版本号,客户端可以使用它们来决定应该使用哪个值,以及它应该丢弃哪个值。

不过,我们仍有问题。其中一个副本仍具有旧值,我们需要以某种方式将其与其余副本同步(毕竟,复制是将相同数据保存在多个位置的过程)。

通常有两种方法可以做到这一点:我们可以让客户负责此更新,或者我们可以让另一个流程负责查找数据中的差异并修复它们。

使客户端修复它在概念上很简单,当客户端从多个节点读取数据并检测到其中一个节点是陈旧的时,它会发送一个具有正确值的写入请求。这通常称为读修复。

具有修复数据的后台进程的另一个解决方案实际上取决于数据库实现,并且有几种方法可以实现,具体取决于数据的存储方式。例如,使用Merkle树DynamoDB进行反熵处理。

法定人数

所以我们说我们需要将写/读请求发送到“一些”副本。如果我们决定减少这个数字,是否有很好的方法来定义至少多少才是足够的。

让我们首先谈谈最明显的问题场景,当我们只需要一个成功的响应来考虑写入的值,并且只从一个副本中读取。从那里我们可以将问题扩展到更现实的场景。

由于这些副本之间没有同步,因此每次向另一个节点发送读取请求时,我们都会读取过时的值。

现在让我们假设我们有5个节点并且需要在其中2个节点中成功写入,并且还从这2个中读取。好吧,我们将遇到完全相同的问题。如果我们写的节点是A和B,但从节点C和D读取,我们总是会得到过时的数据。

我们需要的是一些方法来保证我们正在读取的节点中至少有一个节点是接收写入的节点,这就是法定数量。

例如,如果我们有5个副本并且要求其中3个接受写入,并且还要从3个副本中读取,我们可以确定我们正在读取的这些副本中的至少一个接受了写入,因此具有最新的副本数据。总是有重叠。

大多数数据库允许我们配置接受write(w)所需的副本数量以及我们想要读取的数量(r)。一个好的经验法则是永远有 w + r > number of replicas。

现在你可以开始玩这些数字了。例如,如果您的应用程序很少写入数据库,但非常频繁地读取,也许您可​​以设置 w = number of replicas和n = 1。这意味着每个副本都需要确认写入,但是您可以从其中一个副本中读取,因为您确定每个副本都具有最新值。当然,您正在使写入速度变慢且可用性降低,因为只有一个副本故障会阻止任何写入发生,因此您需要测量您的特定需求以及什么是正确的平衡。

复制滞后

在基于领导的复制中,正如我们所看到的,写入需要发送给领导者,但读取可以由任何副本执行。当我们的应用程序主要从数据库中读取并且写入频率较低时(这是最常见的情况),可能很容易添加许多副本来处理所有这些读取请求,从而创建可称为读取扩展的内容架构。不仅如此,我们还可以在地理位置上拥有许多与客户相近的复制品,以改善延迟。

但是,我们拥有的副本越多,使用同步复制就越困难,因为当我们需要复制更新时,这些节点中的一个节点出现故障的概率会增加,并且我们的可用性会降低。在这种情况下唯一可行的解​​决方案是使用异步复制,即,即使节点没有响应,我们仍然可以执行更新,并且当此副本备份时,它应该赶上领导者。

我们已经讨论了使用同步和异步复制的好处和挑战,所以我不会再谈这个,但假设我们是异步复制更新,我们需要了解复制延迟可能带来的问题,换句话说,在领导节点中应用更新的时间与在给定副本中应用更新的时间之间的延迟。

如果客户端在此期间从该副本中读取,则会收到过期信息,因为尚未应用最新更新。换句话说,如果您将相同的查询发送到2个不同的服务器,您可能会得到2个不同的答案。您可能还记得当我们谈到CAP定理时,这会破坏一致性保证。这只是暂时的,最终所有节点副本都将获得此更新,如果您停止编写新数据,它们将最终完全相同。这就是我们所说的最终一致性。

从理论上讲,复制者与其领导者保持一致需要多长时间是没有限制的(我们唯一的保证就是它最终将会是这样),但实际上我们通常希望这种情况发生得相当快,也许是在几毫秒。

不幸的是,我们不能指望总是如此,我们需要计划最坏的情况。也许网络速度很慢,或者服务器在容量附近运行,并且没有像我们那样快速地复制更新,并且这种复制滞后会增加。也许它会增加几秒钟,也许是几分钟。那么会发生什么?

那么,第一步是了解我们需要提供的保证。例如,当面临一个增加滞后的问题时,你的朋友需要30秒才能看到你刚刚在Facebook上发布的最后一张猫图片,这真的是一个问题吗?可能不是。

在很多情况下,这种复制滞后以及最终的一致性都不会成为问题(毕竟,物理世界最终是一致的),所以让我们关注一些可能存在问题的情况,并看一些替代方案。处理它们。

读写一致性

我们可以使用异步副本的最常见问题是当客户端向领导者发送写入时,以及尝试从副本中读取相同值后不久。如果在领导者在复制更新这段时间之前发生了这种读取,那么复制看起来实际上并不起作用。

因此,虽然如果客户端没有立即看到其他客户端的更新可能不是一个大问题,但如果他们没有看到自己的写入,则会非常糟糕。这就是所谓的读写一致性,我们希望确保客户端永远不会在执行写入之前的状态下读取数据库。

我们来谈谈可以用来实现这种一致性的一些技术。

一个简单的解决方案是:当读取用户尝试读取可能已更改的内容时,让它从领导者处读取。例如,如果我们正在实施类似Twitter的内容,我们可以从副本中读取其他人的时间线(因为用户将无法编写/更改它),但在查看自己的时间轴时,请从领导者处阅读,以确保我们不要错过任何更新。

但是,如果有很多内容可以被每个用户改变,那么这并不能很好地工作,因为我们最终会将所有读取发送给领导者,从而破坏了复制品的全部目的,所以在这种情况下我们需要一个不同的策略。

可以使用的另一种技术是跟踪上次写入请求的时间戳,并且对于下一次写入请求,例如10秒,将所有读取请求发送给领导者。然后你需要在这里找到合适的平衡点,因为如果每9秒钟有一次新的写入,你最终也会将所有的读数发送给领导者。此外,您可能希望监视复制滞后,以确保落后超过10秒的副本保持停止接收新请求直到它们赶上来。

然后还有更复杂的方法来处理这个问题,这需要您的数据库进行更多协作。例如,当您向领导者写东西时,Berkeley DB 将生成一个提交令牌。然后,客户端可以将此令牌发送到它尝试读取的副本,并使用此令牌,副本知道它是否足够当前最新数据(即,它是否已应用该提交)。如果是这样,它可以毫无问题地提供读取,否则它可以阻止直到它收到该更新,然后回答请求,或者它可以拒绝它,并且客户端可以尝试另一个副本。

和往常一样,这里没有正确的答案,我确信还有很多其他技术可以用来解决这个问题,但你需要知道你的系统在遇到大的复制延迟时会如何表现,read-your-writes应该是您真正需要提供的保证,因为有不少数据库和复制工具会忽略此问题。

单调读取一致性

这是一个奇特的名称,我们不希望客户看到时间向后移动:如果我读取的一个副本已经接受了提交1,2和3,我不希望我的下一次读取转到另外副本中,你们只有提交1和2,缺了3。

想象一下,例如,我正在阅读博客文章的评论。当我刷新页面以检查是否有任何新评论时,实际发生的是最后一条评论消失,就像它被删除一样。然后我再次刷新,它又回到了那里。很混乱。

虽然您仍然可以看到过时的数据,但是单调读取保证的是,如果对给定值进行多次读取,则所有连续读取将至少与前一次读取一样。时间永远不会倒退。

实现单调读取的最简单方法是使每个客户端将其读取请求发送到同一副本。不同的客户端仍然可以从不同的副本读取,但是始终(或者至少在会话期间)连接到同一副本的给定客户端将确保它永远不会从过去读取数据。

另一种方法是使用类似于我们在read-your-writes讨论中谈到的提交令牌。每次客户端从副本中读取时,它都会收到最新的提交令牌,然后在下一次读取时发送,该令牌可以转到另一个副本。然后,此副本可以检查此提交令牌以了解它是否有资格回答该查询(即,它自己的提交令牌是否比收到的更大)。如果不是这种情况,它可以等到响应之前复制更多数据,否则它可能会返回错误。

有界陈旧的一致性

正如名称所示,这种一致性保证意味着对我们正在阅读的数据的陈旧程度应该有一个限制。例如,我们可能希望保证客户端不会读取超过3分钟的数据。或者,可以根据缺失更新的数量或对应用程序有意义的任何内容来定义此陈旧性。

延迟复制

我们谈到了复制滞后,当这种滞后增加太多时我们可以遇到的一些问题,以及如何处理这些问题,但有时我们可能真的想要这种滞后。换句话说,我们想要一个延迟复制。

我们不会真正从这个复制品中读取(或写入)它只会坐在那里,落后于领导者,可能需要几个小时,而没有人使用它。那么,为什么有人想要呢?

好吧,假设你发布了一个新版本的应用程序,本版本中引入了一个错误:开始删除orders 表中的所有记录。您注意到此问题并回滚此版本,但已删除的数据已消失。您的副本在此时不是很有用,因为所有这些删除都已被复制,并且您复制了相同的混乱数据库。您可以开始恢复备份,但如果您有一个大型数据库,则可能不会每隔几分钟就运行一次备份,并且恢复数据库的过程可能会花费大量时间。

这是一个延迟复制品可以节省一天。假设你的副本总是落后领导者1小时。只要你在不到1个小时内注意到这个问题(你可能会在你的订单消失的时候),你可以开始使用这个副本,尽管你仍然可能会丢失一些数据,但损害可能会更糟。

副本几乎永远不会替换正确的备份,但在某些情况下,具有延迟副本的副本可能非常有用(因为发送该bug的开发人员可以确认)。

引擎盖下的复制

我们讨论了几种不同的复制设置,一致性保证,每种方法的优缺点。现在让我们进入下面的一个级别,看看一个节点如何实际将数据发送到另一个节点,毕竟,复制就是将字节从一个地方复制到另一个地方,对吧?

基于语句的复制

基于语句的复制基本上意味着一个节点将收到的相同语句发送到其副本。例如,如果您向领导者发送一个UPDATE foo = bar语句,它将执行此更新并将相同的指令发送到其副本,这也将执行更新,希望获得相同的结果。

虽然这是一个非常简单的解决方案,但这里有一些事情需要考虑。主要问题是并非每个语句都是确定性的,这意味着每次执行它们都会得到不同的结果。考虑像CURRENT_TIME()或者RANDOM()这样的函数,如果你只是连续两次执行这些函数,你会得到不同的结果,所以让每个副本重新执行它们会导致数据不一致。

大多数使用基于语句的复制的数据库和复制工具(例如MySQL在5.1之前)将尝试用固定值替换这些非确定性函数调用以避免这些问题,但很难解释每种情况。例如,可以使用用户定义的函数,或者可以在更新后调用触发器,并且在这些情况下很难保证确定性。例如 VoltDB,使用逻辑复制,但 要求存储过程是确定性的

另一个重要的要求是我们需要确保所有事务都在每个副本上提交或中止,因此我们没有在某些副本中应用更改而在其他副本中没有应用更改。

日志传送复制

大多数数据库使用日志 (仅附加数据结构)来提供持久性和原子性(来自 ACID属性)。每个更改在应用之前首先写入此日志,因此在写入操作期间崩溃时数据库可以恢复。

该日志描述了数据库在非常低级别的更改,例如,描述了哪些字节已更改以及磁盘中的确切位置。它并不意味着被人类阅读,但机器可以非常有效地解释它们。

日志传送复制的想法是将这些日志文件传输到副本,然后可以应用它们以获得完全相同的结果。

我们在发送这些日志时遇到的主要限制是,由于它描述了如此低级别的更改,我们可能无法复制由不同版本的数据库生成的日志,例如,作为物理方式存储的数据可能已更改。

另一个问题是我们不能在日志传送中使用多主复制,因为没有办法将多个日志统一为一个,如果数据同时在多个位置发生变化,那么这是必要的。

Postgres“ 流式复制” 以及提供增量备份和时间点恢复使用此技术。

这也称为物理复制。

基于行的复制​​​​​​​

基于行或逻辑复制是这两种技术的混合。它不使用内部日志WAL,而是使用不同的日志进行复制。然后,该日志可以与存储引擎分离,因此在大多数情况下,可以使用跨不同数据库版本的副本数据。

基于行的日志将包含足以唯一标识行的信息,以及需要执行的一组更改。

使用基于行的方法的好处是,例如,我们可以在零停机时间内升级数据库版本。我们可以使用一个节点来升级它,同时其他副本处理所有请求,在备份之后,使用新版本,我们对其他节点执行相同的操作。

与基于语句的复制相比,这里的主要缺点是有时我们需要记录更多的数据。例如,如果我们想要复制UPDATE foo = bar,并且此更新更改了100行,使用基于语句的复制,我们将只记录这个简单SQL,而我们需要在使用基于行的技术时记录所有100行。同样,如果您使用生成大量数据的用户定义函数,则需要记录所有数据,而不仅仅是函数调用。

MySQL例如,允许我们定义一个MIXED日志格式,它将在语句和行基复制之间切换,尝试为每种情况使用最佳技术。

潜水更深​​​​​​​

我希望对数据库复制背后的不同想法和概念的介绍让您对了解更多内容感到好奇。如果是这种情况,这里是我在自己的研究中使用(并且仍在使用)的资源列表,可以推荐:

  • 设计数据密集型应用程序这是我读过的最好的书籍之一。它涵盖了许多与分布式系统相关的不同主题,在第5章中,作者主要关注复制。虽然它不是特定于数据库,但涵盖的大多数主题都适用。
  • 有趣和利润的分布式系统这是另一本书,它不仅仅关注数据库,而是一般分布式系统,但第4章和第5章侧重于复制。它以一种简单(有趣)的方式解释了许多重要的主题,这些主题在这里没有深入讨论。
  • PostgreSQL复制本书当然是关注的PostgreSQL,但它也提出了一些适用于其他RDBMS的概念。此外,这是了解如何在实践中应用这些想法的好方法。它解释了如何设置同步/异步复制,WAL运输以及使用各种技术的工具(例如Bucardo,使用触发器,并 BDR使用我们在此讨论的基于行的复制)。
  • 了解数据库和分布式系统中的复制本文比较了分布式系统和数据库文献中讨论的复制技术。它首先描述了一个抽象模型,然后检查了它如何应用于同步/异步复制(本文中称为惰性 /急切复制),以及单引导/无引线设置(即分布式系统的主动/被动调用)主数据库复制/更新 -数据库无处不在)。
  • Dynamo:亚马逊高度可用的键值商店Dynamo是亚马逊创造的关键价值数据存储,它推广了无领导数据库的理念。这篇论文解释了(至少表面上看)它是如何工作的。看看他们如何处理冲突(让客户解决冲突)并使用本文未探讨的一些技术,如草率的仲裁(与严格的法定人数相对)和暗示切换以获得更多可用性,这很有趣。这篇论文已经有10年了,我确信有些事情发生了变化,但无论如何这都是一个有趣的读物。
  • 对CAP定理的批判本文解释了为什么CAP定理并不总是在推理分布式系统时使用的最佳工具。作者解释了他在CAP定义中看到的问题(或者在某些情况下缺乏定义)。例如,CAP的一致性意味着非常特定的一致性(线性化),但是有一系列不同的一致性保证被忽略。
  • (论文)通过棒球解释的复制数据一致性本文描述了六种一致性保证,并尝试定义棒球比赛中每个参与者(记分员,裁判等)如何需要不同的保证。我认为本文中有趣的是它表明每个一致性模型都可以根据具体情况使用,有时候最终的一致性很好,有时你需要更强的保证(例如,上面描述的读写) 。
  • (论文)VoltDB如何进行交易本文中有一节专门解释了如何VoltDB处理复制。有趣的是,使用一种基于语句的复制来查看相对较新的数据库,以及它们如何强制执行确定性以避免数据不一致。
  • (研究报告)分布式数据库的注释79(!)的研究报告涵盖了很多不同的主题,但第一章专门用于复制。令人惊讶的是,由于网络限制仍然相同,我们所面临的问题变化不大。
  • (文章)最终一致这篇文章由亚马逊的首席技术官Werner Vogels撰写,非常好地介绍了最终的一致性意味着什么。他谈到了为了在大规模系统(如亚马逊运营的系统)中实现高可用性而需要进行的权衡。
  • (文章)时钟和同步本文解释了物理时钟不可靠的原因。摘要是:在构建分布式系统时,不要理所当然地认为您可以简单地信任执行代码的机器上的时钟。
  • (文章)CAP十二年后:“规则”如何变更这是一篇由Eric Brewer撰写的文章,他是2000年首次提出CAP定理的人,因此看看作者12年后所说的内容很有意思。尽管该定理对于让我们考虑特定设计决策中的权衡是有用的,但在某些情况下它也可能会产生误导。
  • (文档)Berkeley DB Read-Your-Writes一致性本文档的这一部分解释了如何Berkeley使用我们在此讨论的提交令牌技术实现Read-Your-Writes一致性。
  • (文档)VoltDB数据库复制本文档的这一部分专门用于解释VoltDB如何处理复制。它解释了两个可用选项:单主机和多主机(它们分别称为单向和双向复制)。

主文 原文点击标题。