欢迎阅读新一期的数据库内核杂谈。 这是兔年后的第一篇内核杂谈，祝大家新年快乐，也希望内核杂谈新一年里不断更。这一期，我们一起来学习 AWS 在 USENIX 2022 上发表的关于Amazon DynamoDB 的最新论文： Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service。
自2012年发布以来（见下图），DynamoDB" 经历了多个版本的迭代，更新了很多功能。它作为底层的基础软件，支撑着 Amazon 和 AWS 的发展。这篇论文，汇聚了一些关键的系统设计和实现思路，介绍了DynamoDB如何从一个需要程序员自主维护，配置和使用的数据库系统，演进为一个超高可靠（highly available），超大规模（highly scale），超级稳定（predictable performant）的全自动化数据库服务（fully managed database as a service）。文中介绍了很多关键的设计细节，这些细节，不仅仅对数据库设计有帮助，对于通用的系统服务建设也很有启发。这篇文章是我很长一段时间内读到的最好的技术论文。借此博客，和大家一起学习，共同进步。
DynamoDB launch 时间线
DynamoDB历史和简介
论文的一开始，AWS肯定要先展示一下肌肉。DynamoDB是一款key-value（但同时也支持schema definition, document, secondary index等其他功能）的NoSQL数据库服务。在2021年的66个小时的Amazon Prime Day促销时，Amazon systems（包括Amazon.com, Alexa, Amazon fulfillment center等）总共调用DynamoDB 超过trillion级别（10^12次方， a million million），峰值更是将近9000万（89.2M）QPS。更大的肌肉在于，在如此高的峰值下，DynamoDB依然可以保证高可用以及几毫秒级别的返回时长（文中用的是single-digit milisecond）。
DyanmoDB最初是以自助维护（on-demand）的数据库系统的形式对外提供服务，即每个用户需要申请硬件资源，做好数据库配置，运维，甚至升级。使用DynamoDB的学习曲线非常高，团队通常需要配备一两个专业的DBA来运维DynamoDB。这使得DynamoDB的推广和使用并不是一帆风顺。
随后，AWS推出了S3，SimpleDB" 等的 SaaS 服务，这些服务完全是自动化运维，对于用户仅仅暴露API调用接口（插一句题外话，SimpleDB: https://en.wikipedia.org/wiki/Amazon_SimpleDB", 是一款用Erlang编写的分布式NoSQL系统，也具备弹性，高可用，高性能的特点，但也有其局限性，比如数据量大小限制等等）。因为其易用的特点，SimpleDB的推广远比当时的DynamoDB要好得多。这也推动了DynamoDB的研发团队的转型之路，TA们希望能够让DynamoDB集Dynamo Database以及SimpleDB SaaS的优点于一身。
DynamoDB Service作为基础底层软件，是绝大多数AWS服务（包括，但不限于，AWS Lambda，AWS lake formation, AWS SageMaker）等上层应用的构建基石。这些上层的AWS服务对于很多其他用户而言，却是平台级别的基础服务。也因此，这些服务本身对于性能，高可靠，高可用，高扩展就有极大的诉求。这些诉求传递到DynamoDB后，使得条件变得更加苛刻。尤其是稳定的性能表现（consistent low latency），这里稳定的性能表现不是均值，不是中位数，而是P90，甚至是P99。因为DynamoDB作为底层服务，任何性能抖动（高latency的return）就会在上层服务中被放大，致使影响整个上层服务不稳定甚至不可用。所以，DynamoDB的一个设计目标就是要确保所有的调用都能在几毫米级别返回。除了稳定的性能外，DynamoDB的设计挑战还在于需要支持大量不同类型的服务，这也意味着需要支持多租户。且逐渐需要添加新的功能进入新版本比如secondary-index，transaction支持等等。研发团队总结了DynamoDB演进过程中始终贯彻的6个设计理念：
1) DynamoDB是一个完全自动化运维的数据库SaaS服务。对于用户来说，就是100%的Serverless" API的调用。其他如软件升级，故障修复，硬件资源申请, 扩容，集群维护，故障恢复，对用户来说都是黑盒且无感知的。
2）DynamoDB是一个多租户SaaS服务。DynamoDB需要支持不同类型的用户和服务，但考虑到SaaS服务的收费模式以及服务SLA，需要保障高效的资源利用。底层的数据存储，以及计算节点在不同类型的服务和用户之间要做到物理共享，但又逻辑隔离。整体服务需要做好资源预留，服务监控，来保证不同类型的服务不会相互影响（最坏情况下造成雪崩效应）。
3）支持几乎无限制的横向扩展（典型的全球型分布式数据库）。DynamoDB并不限制一个表能存多少量的数据（表可以根据业务需求弹性地增加和扩容），也不限制有多少用户：一个表的数据会被分散存储到不同的物理机上，如果有需要，可以分配到上千台物理机上。
4）稳定的高性能（>P99）：当服务和DynamoDB部署在同一个AWS region里，对于读写，需要保证几毫秒的延时。挑战在于，这种稳定的延时，即使当数据增长到百亿千亿级别，仍然能够保持（文中也给出了和MySQL的对比，见下图，很能说明情况）。通过分布式数据存储和routing，DynamoDB可以做到几乎无限的横向扩展。
调用延时无关数据量大小，始终保持几毫秒级别
5）超级高可用：数据会被复制到多个数据中心，AWS中称为 availability zones（AZ）。默认情况下，数据会有3个备份。并且，当发现某一个replica出现了节点故障，会自动申请一个新的replica来保证高可用。文中写到DynamoDB的普通表数据提供4个9的高可用保障，全域表（global table）提供5个9的高可用保障（因为全域表会备份到多个region，一个region包含多个AZ）。
6）功能丰富，支持多类型的应用和服务：DynamoDB在功能上，不像其他服务（比如SimpleDB）来限制用户使用某个固定的Data model。支持多种收欢迎的功能如支持可扩展的Schema，支持不同的数据类型（包括array类型的数据），secondary index，transaction，强一致读（strong read）和最终一致读（eventual consistency read)等等。
研发团队在迭代过程中，确保上述的6个设计理念始终被贯彻，才造就了DynamoDB的成功。其实，在平时的系统研发中，我们也需要贯彻清晰的设计理念（虽然，不需要像DynamoDB那样苛刻），好的设计理念会让系统在迭代中不会点错技能树。
DynamoDB 数据模型和high-level架构
一个DynamoDB的表是一个Item数据的集合，每个Item都会分配一个全局唯一的key，即primary key。每个Item是一系列的attributes的集合。Primary key包含一个partition key或者是一个partition值+sort key（复合primary key）。Partition key的值的hash值，配合上sort key（如果存在的话）会决定这个数据存储在哪里。Partition key或者{partition value, sort key}需要保持唯一。 每个DynamoDB的表支持一个或者多个secondary index，来提升非primary key的查询速度。DynamoDB支持对Item对象进行操作的CRUD API，并且支持ACID transactions。
DynamoDB通过把一张表分成多个partitions来应对数据量增大带来的存储和读写压力。Partition可以被认作是存储和计算调度的基本单元。DynamoDB通过把不同的partition分配到不同的物理节点上来保证每个partition都分配到足够多的资源来保证读写的稳定表现，从而保证整个表的读写SLA。每个partition存储了一部分连续的key的item，而不同partition之间的item各无交集。每个partition都会有多个备份（默认情况是3备份），每个备份会被分配到不同的AZ来保证高可靠，节点间的通信和状态同步通过Multi-Paxos" consensus protocol来实现。只有leader replica支持写操作和强一致读。当接受到写操作时，leader replica会先生成一个WAL (write-ahead log），并将WAL同步给其他的replica，只有当满足quorum setting的replica也存储好了WAL，这个写操作才认为被执行。除了强一致读，其他replica节点支持最终一致读。
如果leader节点因为节点硬件，网络等原因故障导致unavailable，replica group会根据consensus protocol重新选择一个新节点来做leader。就partition而言，绝大部分的分布式数据库都有类似的设计。每个标准replica节点（storage replica）除了会存储WAL，也会存储 B-tree 形式的key-value数据。DynamoDB 的一个创新是，当 replica 节点发生故障，导致 3 备份被打破时，为了保证高可靠，引入了一种新的replica节点，log replica。Log replica节点只存储WAL，而不保留key-value。因此Log replica节点不接受读写操作，也不能被选为leader节点，只是确保写操作依然能满足quorum setting，比如2/3写成功。
下面两张图展示了storage replica和log replica的区别。
Storage replica
Log replica
除了replica节点，DynamoDB的组成包含了十几个辅助服务。这其中，关键的服务有metadata service，request routing service和autoadmin service（见下图的架构）。
DynamoDB architecture
Metadata service存储元信息包括表，partition，index存储的路由信息。Request routing service负责授权，验证和具体的路由工作（通过查询metadata service得到路由信息）。Autoadmin service负责DynamoDB的集群控制工作来确保集群的稳定性，每个partition的读写稳定性，以及scaling request等等。Autoadmin service会持续监控集群，replica节点，表，partition的关键信息来判断是否其出于不健康状态，并通过控制命令来恢复，比如，下线某个不健康的replica节点，将上面原先存储的partition转移到其他健康节点上，对某个partition做扩容分离（split）等。这些辅助服务的具体工作在后文中会详细介绍。
总结
这一期是DynamoDB 2022技术论文精读的第一篇。我们介绍了DyanmoDB的发展历史，6个具体的设计理念以及high-level架构。下一期，我们会深入学习Dynamo引入的新设计思路，看这些思路如何保证当数据规模超大的情况下，DynamoDB依然能够保证稳定的低延迟返回。感谢阅读。
相关阅读：
数据库内核杂谈 (二十二) 自动驾驶数据库 - Behavior Modeling"
数据库内核杂谈（二十三）- Hologres，支持 Hybrid serving/analytical Processing 的数据引擎"
数据库内核杂谈（二十四）- Hologres，支持 Hybrid serving/analytical Processing 的数据引擎"