欢迎阅读新一期的数据库内核杂谈。前两期杂谈介绍了 DynamoDB 的设计理念，分布式架构，和如何做到大规模数据下的性能保障。这一期是精读 DynamoDB 技术论文的最后一期。这期会关注在 DynamoDB 服务的高可用和数据持久性以及正确性。

本期的博客有些特殊，我邀请到了 IT 届的"新星"ChatGPT 同我一起研读了 DynamoDB USENIX 2022 论文的第五章和第六章，并讨论了一些我们关于 DynamoDB 高可用的看法和观点。当然，我并没能让 GPT 直接输出大纲或者完整的博客。在整个对话中，我会要求它帮我翻译，或者是对于某些技术方案做更通俗易懂的解释，亦会和它进行技术讨论。

数据的持久性和正确性

作为重要的基础数据存储服务，DynamoDB 存储着超大规模的，来自各种业务和租户的重要数据。DynamoDB 的目标是，一旦数据的写操作被提交后，这些数据就不会丢失。在实际应用中，由于硬件故障、软件错误或硬件错误等原因，都有可能导致数据丢失。 DynamoDB 通过具有预防、检测和纠正任何潜在数据丢失机制的方式，来尽量减少数据出错和丢失的概率。

写前日志 WAL 和冗余存储

和大多数数据库管理系统一样，DynamoDB 中的写前日志（WAL）对于保证数据持久性和崩溃恢复至关重要。写前日志（WAL）是一种被许多数据库系统采用的技术，用以确保数据持久性和系统在崩溃后的恢复。在进行数据修改操作之前，WAL 要求先将所有的修改记录到日志中。这些日志记录包含了足够的信息，以便在系统崩溃后重建所做的更改。当数据库需要进行数据更新时，首先将更改写入日志，然后才更新数据库中的实际数据。在发生系统崩溃时，尚未完全写入数据库的更改仍然可以从日志中恢复，从而避免数据丢失。WAL 的核心优势在于其将数据的持久化与实际的数据更新分离。这样可以确保在发生故障时，已经记录在日志中的更改不会丢失。此外，WAL 还有助于减少对磁盘的写入操作次数（通常，WAL 都是顺序写磁盘），从而提高系统的整体性能。

为了避免单节点的硬盘故障，DynamoDB 的 WAL 会存储在所有的三个副本中（这些副本通常分布在不同的可用区（AZ）上）。同时，为了减少每个副本的存储压力，以及进一步提升数据的持久性，WAL 会定期存档到 S3 中（S3 是一个设计持久性为 11 个 9 的对象存储）。每个副本仍包含最新的 WAL，通常处于等待存档的状态。未存档的日志通常大小为几百兆字节。在 DynamoDB 这类大型服务中，硬件故障，如内存和磁盘故障很常见。当一个节点发生故障时，所有托管在该节点上的复制组都会降至两个副本。修复存储副本的过程可能需要几分钟，因为修复过程涉及复制 B 树和 WAL。一旦检测到存储副本出现问题，复制组的 leader 会添加一个日志副本以确保不会对耐久性造成影响。添加日志副本只需几秒钟，因为系统只需从健康副本复制最近的写前日志到新副本而无需复制 B 树。因此，使用日志副本快速修复受影响的复制组，来确保分区可以在最快的速度下满足 quorum 写的数量。

大量地使用校验和（checksum）

一些硬件故障可能导致错误的数据被存储。这些错误可能是由存储介质、CPU 或内存引起的。不幸的是，这些错误很难检测到，并且可能发生在系统的任何地方。为此，DynamoDB 大量地使用校验和（checksum）来检测静默错误。通过在每个日志条目、消息和日志文件中维护校验和，DynamoDB 可以在两个节点之间的每次数据传输中验证数据的完整性。这些校验和可以防止错误传播到系统的其他部分。例如，在节点或组件之间的每个消息上都会计算校验和，并在消息经过各种转换层次之前抵达目的地时进行验证。如果没有这样的检查，任何一层都可能引入很难发现的错误。

每个归档到 S3 的日志文件同样都有一个包含日志信息的清单，例如表、分区以及存储在日志文件中的数据的起始和结束标记。负责将日志文件归档到 S3 的代理程序在上传数据之前执行各种检查。这些检查包括，但不限于，验证每个日志条目以确保它属于正确的表和分区，验证校验和以检测任何静默错误，以及验证日志文件在序列号中是否有任何空洞。一旦所有检查都通过了，日志文件及其清单就会被归档。日志归档代理在复制组的所有三个副本上都会运行。如果其中一个代理发现日志文件已经归档，该代理将下载已上传的文件，通过将其与本地写前日志进行比较来验证数据的完整性。每个日志文件和清单文件都会带有内容校验和上传到 S3。S3 在执行 put 操作时会检查内容校验和，以防止在数据传输到 S3 过程中出现任何错误。

饱和式验证

DynamoDB 非常激进地对归档的数据做饱和式的验证，目的是检测系统中的任何静默数据错误。一个持续验证系统的例子是 scrub 过程。Scrub 的目标是检测到我们未预料到的错误，例如位衰减（bit rot）。Scrub 过程主要验证两件事：复制组中所有三个副本的数据相同，且实时副本的数据与使用归档的写前日志离线构建的数据一模一样。通过计算实时副本的校验和并将其与从 S3 归档的日志条目生成的快照进行匹配来进行验证。Scrub 机制充当了深度防御，检测实时存储副本与使用表创建历史日志构建的副本之间的差异。这些全面的检查对于提高运行系统的信心非常有益。用于验证全球表副本的类似持续验证技术。多年来，根据 AWS 的经验，静止数据的持续验证是防止硬件故障、静默数据损坏乃至软件错误的最可靠方法。

形式化验证（Formal Verification）和充分测试

DynamoDB 是一个基于复杂底层子系统构建的分布式键值存储。高复杂性增加了设计、代码和操作中人为错误的概率。系统中的错误可能导致数据丢失或损坏，或者违反客户所依赖的其他接口契约。开发过程中，工程师广泛使用形式化验证方法来确保复制协议的正确性。核心复制协议使用 TLA+进行了规范。当添加影响复制协议的新功能时，它们会被纳入规范并进行模型检查。模型检查使我们能够在代码投入生产之前捕捉到可能导致持久性和正确性问题的微妙错误。其他服务（如 S3）在类似情况下也发现模型检查非常有用。

（ChatGPT 解释 TLA+）

DynamoDB 还采用广泛的故障注入测试和压力测试来确保每个部署的软件的正确性。除了测试和验证数据平面的复制协议外，形式化方法还被用于验证控制面板和分布式事务等功能的正确性。

DynamoDB 的高可用性

为实现高可用性，DynamoDB 表在一个区域内的多个可用区（AZ）之间进行分布和复制。DynamoDB 定期测试对节点、机架和 AZ 故障的弹性。例如，为了测试整个服务的可用性和持久性，进行断电测试。使用逼真的模拟流量，通过作业调度器随机关闭节点。在所有断电测试结束后，测试工具验证数据库中存储的数据在逻辑上是有效的且未被损坏。下面将详细介绍在过去十年中解决的一些关键挑战。

如何保证高可用写和强一致读

分区的写入可用性取决于其是否具有健康的 leader 和健康的写入 quorum 数副本。在 DynamoDB 的情况下，一个健康的写入 quorum 数由来自不同可用区的三个副本中的两个组成。如果达到最小 quorum 数所需的副本数量不可用，分区将无法进行写入操作。如果出现一个副本无响应，leader 会向组中添加一个日志副本。添加日志副本是确保写入 quorum 数得到满足的最快方法。Leader 副本同时提供一致性读取。引入日志副本对系统产生了很大的变化，Paxos 的正式验证实现让我们有信心安全地调整和尝试系统，以实现更高的可用性。我们已经能够在一个区域内使用日志副本运行数百万个 Paxos 组。最终一致性读取可以由任何副本提供。如果 leader 副本出现故障，其他副本会检测到其故障并选举新的 leader，以尽量减少对一致性读取可用性的影响。

如何避免 leader 被误认为不可用

新选出的 leader 在提供任何流量之前，需要等待旧 leader 租约到期。虽然这只需要几秒钟，但在此期间，选定的 leader 节点无法接受任何新的写入或一致性读取流量，从而影响可用性。对于高可用系统来说，leader 的故障检测是关键组件之一。故障检测必须快速且稳定，以尽量减少中断。故障检测中的误报反而会进一步恶化可用性。故障检测对于每个副本组都失去与 leader 的连接的故障情况表现良好。然而，节点可能会遇到灰色网络故障。灰色网络故障可能是由于 leader 和 follower 之间的通信问题、节点的出站或入站通信问题，或者即使 leader 和 follower 之间可以相互通信，前端路由器也面临与 leader 通信的问题。灰色故障可能会影响可用性，因为故障检测可能存在误报或无故障检测。例如，一个没有收到 leader 心跳信号的副本将尝试选举新的 leader。如上一节所提到的，这可能会影响可用性。为解决灰色故障引起的可用性问题，希望触发故障切换的 follower 会向复制组中的其他副本发送消息，询问它们是否能与 leader 通信。如果副本回复表示 leader 状况良好，follower 就会放弃触发 leader 选举的尝试。这种对 DynamoDB 所使用的故障检测算法的改进显著减少了系统中的误报数量，从而减少了错误的 leader 选举次数。

DynamoDB 部署

作为 SAAS，DynamoDB 不需要用户来维护和升级软件，会自动定期推送软件更新。部署将软件从一个状态转移到另一个状态。新部署的软件经过完整的开发和测试周期，以建立对代码正确性的信心。多年来，在多次部署过程中，工程师发现，确保软件可以正确回滚非常重要，因为有时候新部署的软件无法正常工作。而有时候回滚后的状态可能与软件的初始状态不同。回滚过程经常在测试中被忽略，可能导致对客户的影响。在每次部署之前，DynamoDB 都会在组件级别运行一套升级和降级测试。然后，故意回滚软件，并通过运行功能测试来进行测试。

在单个节点上部署软件与在多个节点上部署软件完全不同。分布式系统中的部署不是原子性的，任何时候，一些节点上都会运行旧代码，而其他部分节点上会运行新代码。分布式部署的额外挑战在于，新软件可能引入一种新类型的消息，或以系统中的旧软件无法理解的方式更改协议。DynamoDB 通过读写操作分开部署来处理这类变化。读写部署作为一个多步骤过程完成：第一步是部署软件用来支持读取新的消息格式或协议。一旦所有节点都能处理新消息，软件就会更新为支持发送新消息。读写分开部署确保两种类型的消息可以在系统中共存。即使在回滚的情况下，系统也能理解新旧消息。

在将所有部署推送到整个节点群之前，所有部署都是在一小部分节点上完成的。该策略降低了故障部署可能带来的影响。DynamoDB 在可用性指标上设置报警阈值。如果在部署过程中，错误率或延迟超过阈值，系统将触发自动回滚。

元数据服务（Metadata Service）稳定性保障

元数据服务存储了路由器需要的表的主键与存储节点之间的映射。此路由信息包括表的所有分区、每个分区的键范围以及托管分区的存储节点。当路由器收到一个之前未见过的表的请求时，它会下载整个表的路由信息并将其缓存到本地。由于关于分区副本的配置信息很少更改，缓存命中率约为 99.75%。但在扩容路由器的时候，会有冷启动，请求路由器的缓存为空，每个请求都会导致直接命中元数据服务。实践中观察到，当请求路由器群增加新容量时，会出现这种效果。偶尔，元数据服务流量可能飙升至 75%（考虑到平时缓存命中率为 99.75%，这对元数据服务来说是瞬间的流量 spike）。因此，引入新的请求路由器会影响性能，可能使系统不稳定。此外，无效缓存可能导致其他系统部分的级联故障，因为数据源由于直接负载过大而崩溃。

为了避免这个问题，DynamoDB 引入了下面两个措施：

1）在请求路由器和元数据服务之间添加一个分布式内存缓存 MemDS。在请求路由器的本地缓存未命中时，它不会直接访问元数据服务，而是首先访问 MemDS，然后 MemDS 在后台访问元数据服务以填充数据。通过添加一个用于削峰填谷的缓存层，相当于添加了另一层保险，这是一种常见的方法。

2）第二种措施是一个非常值得借鉴的设计方案。刚才提到请求路由器上有个本地缓存，如果本地缓存没有命中，会通过 MemDS 获取元数据，这很容易理解。但真正聪明的是：即使本地缓存命中，也会异步地发消息到 MemDS 去更新缓存。这样做的好处在于：1）确保了 MemDS 中现有的缓存尽快更新；2）确保了打到 MemDS 的请求数是稳定的(虽然流量可能很大)， 这也为元数据服务带来“稳定”的流量（尽管可能也较大）。 稳定的好处在于，可以提前 scope 好容量。 对于 DynamoDB 这样体量的服务，稳定的大流量要比瞬间的几百倍的流量陡增要更加可控。

总结

这一期，我们围绕 DynamoDB 在数据持久性，正确性以及整体服务如何做到高可用，进行了学习。论文中介绍了十几年服务沉淀下来的经验，无论是 WAL 冗余存储，饱和式验证，形式化验证，读写分步部署，等等，都是通用的，很有借鉴意义的建议。 最出彩的还是通过异步调用 MemDS（无论 cache hit or miss）确保了元数据服务接受稳定流量的做法。至此，精读 DynamoDB 系列文章完坑。感谢阅读！也非常感谢 ChatGPT 的帮助！

内核杂谈微信群和知识星球

内核杂谈有个微信群，大家会在上面讨论数据库相关话题。目前群人数快 400 人啦，所以已经不能分享群名片加入了，可以添加我的微信（zhongxiangu）或者是内核杂谈编辑的微信（wyp_34358），备注：内核杂谈。

除了数据库内核的专题 blog，我还会 push 自己分享每天看到的有趣的 IT 新闻，放在我的知识星球里（免费的，为爱发电），欢迎加入。