🚶🏻♂️漫步在“发电机”博物馆 - 看看Dynamo 走过的这20年
date
Aug 1, 2024
slug
dynamodb
status
Published
tags
Database
Distributed System
summary
申明：这篇文章既不关于发电机，也不关于博物馆，更和休斯敦发电机队没有一点关系。20年间，Dynamo DB已经逐渐成为亚马逊内部服务的基石，只要一有数据库的需求，所有人都会想到用Dynamo DB。为什么大家都喜欢用Dynamo DB？它到底好用在哪？Dynamo DB在这20年间有着几个阶段的改变，从这些改变中我们可能就会找到更好的答案。
type
Tech
lang
zh
申明：这篇文章既不关于发电机，也不关于博物馆，更和休斯敦发电机队没有一点关系。
大约在20年前，那时候还没有这么多奇奇怪怪的数据库，很多公司都还用着Postgres和MySQL（或者Oracle和SQL Server），一群亚马逊的员工却犯了难：单机数据库的可用性真是太TM差了。亚马逊是最早就开始采用微服务架构的公司，所以数据库是各个服务之间沟通和协调最主要的渠道之一。数据库一崩溃，好多服务都会受到影响，可以想象那些oncall的工程师会被满天飞的sev2 tickets所淹没（所有在亚马逊呆过的人都知道这就是噩梦）。并且亚马逊作为电商平台，服务崩溃所造成的损失是以秒来计算的。所有这些烦恼都指向了数据库，因为单机数据库，或者是那些只做了简单的Primary-Backup的数据库，太脆弱了。亚马逊的基架大的超乎想象，网络丢包，网络分区，服务器崩溃随时都在发生，所以亚马逊需要一个可靠的，不会被任何灾难所影响的数据库。除了可靠性，可扩容性也是亚马逊的考虑之一，因为传统数据库已经跟不上亚马逊的高速增长了。新的数据库必须解决这两个问题，而Dynamo DB则是一份当之无愧的满分答卷。
20年间，Dynamo DB已经逐渐成为亚马逊内部服务的基石，只要一有数据库的需求，所有人都会想到用Dynamo DB。这完全归功于亚马逊内部一条不成文的规定：如果不是有着很强烈的理由需要用SQL 数据库，一律都用No SQL，而想到No SQL大家当然就会想到Dynamo DB，这就导致只要有存储数据的需求，大大小小的服务都会考虑把东西丢到Dynamo DB。自然而然的就会有这么几个问题值得探讨：为什么大家都喜欢用Dynamo DB？它到底好用在哪？Dynamo DB在这20年间有着几个阶段的改变，从这些改变中我们可能就会找到更好的答案。其实在它刚出来的时候，很多亚马逊的工程师不怎么玩的转这个数据库。
Dynamo：高可用，高可用，还是高可用数据分区数据复制数据版本快速恢复Dynamo - 我的看法🥸问题所在Dynamo DB：上云之路多租户模式Dynamo DB的目标新架构量化Dynamo DB的容量容量爆发自动分区把分区配给到合适的节点按需供给可用性和数据持久化机器崩溃leader崩溃检测量化可用性维护依赖部署我的看法🥸
Dynamo：高可用，高可用，还是高可用
最开始的时候，大家都还把这个项目叫做Dynamo。
就像我前面所说的，Dynamo的目标就是高可用和高扩容，其他的一切都是二等公民：没有一致性，只支持简单的数据库操作(get 和 put)，不考虑隔离性等。带着这个想法，它的系统架构就很容易理解了。
数据分区
可以把Dynamo的架构抽象的非常简单一个环。
因为需要高扩容性的关系，所以Dynamo就用了hashing ring把数据平均分到每个节点上。但是普通的hashing有一个严重问题，如果之后有新节点加入的话，所有的老节点会重新分配数据，而这个时间系统是没办法服务新的put/get 请求，可用性就大大减少了。Dynamo用了一致性哈希来解决这个问题，这也就是“环”的由来。一致性哈希的思想也非常简单：数据会通过hash分布在这个环上，每个节点只负责环的一部分。新节点加入以后，不需要重新分配所有数据，只需要一个节点把自己的数据给一部分给新节点就行。同样的，如果有节点要退出，也不需要重新分配数据。但一致性哈希有个严重的缺陷，当节点有所变动时，数据迁移只是点对点的，如果一旦数据量大了的话，迁移时间就会变得很长。举个例子：
如果蓝色server离开的话，所有数据只能迁移到红色server上。在亚马逊这么大的数据量下，迁移时间会变得十分漫长，这会大大影响可用性，因为迁移的过程中没有办法提供服务。Dynamo采用了一致性哈希中的一个非常经典的变种：虚拟节点。背后的想法很简单：与其让一个server负责圆上的连续的一整块儿，还不如随机分散到这个圆上的各个角落。这样当蓝色server离开之后，它负责的数据会同时迁移到不同的server上去，这样不仅迁移时间大大减少，同时数据分区也更加均衡。
数据复制
数据分区只能解决扩容性，而高可用性则需要把数据复制到不同的server上，这样如果一个server倒下了不会直接让整个系统不可用。当然，数据不能无脑去复制到其他随机的节点，不然会影响崩溃后数据恢复的速度。Dynamo采用的quorum十分灵活：当Dynamo接受到一个get请求时，会请求N个节点(其中N位分区数量)，当有R个节点返回结果时，就会认为该get操作是成功的。同样，当Dynamo接受到put请求时，会请求N个节点，当有W个节点返回success后，就会认为该put操作是成功的。W, R, 和N用户都可以自由设置，但是W+R必须得大于N，这样才能保证拿到最新的value。假设用户设置N=8，如果put x=4只放进了前4个节点，而get x恰巧只能请求到了后四个节点，那么最新x的value并不能get到。所以只有保证了W+R>N，才保证了W和R有交集。
在这样的quorum下，只要N个server里面有R个是工作的，那么就能正常服务于get请求；N个server里面W个是工作的，那么就能正常服务于put请求。但是，这样的可用性对亚马逊而言还是远远不够，比如突然一个工人把大街上的电缆挖坏网络分区了，导致client只能和server A, E, 和F沟通，而不能和其余任何server沟通了。假设client把N设置成3，W设置成2，然后需要把x=1 写入server A 和 B。按照我们之前的系统构架，那Dynamo就完全不可用了，因为client完全没办法和B沟通。
但显然这不是亚马逊想要的，毕竟他们需要追求极致的可用性，于是他们在这里玩了个小技巧。如果client没办法写入B，就会尝试写入C。如果C也没办法沟通，就尝试写入D……一直顺着圆圈向下走直到能碰到一个正常的server。在上面的例子中，client最终会找到E，然后把x=1写入E。当然，E只是暂时帮助B保管这份数据。E会周期性的尝试去和B沟通，以确保当B回归正常后能第一时间把数据还回去。所以，Dynamo的可用性并不被分区的机器数量N所限制，只要是整个集群里有足够的机器去完成这个操作就行。亚马逊把这个操作称之为Hinted Handoff，个人认为这是Dynamo的亮点之一。
但天下没有免费的午餐，灵活往往会伴随着代价。
数据版本
想象一下如下的一种情况：假设在N = 3, W = 2, R = 2（一个分区有3个server，每次put的时候需要至少写入两个server，每次读取的时候需要至少从两个server中读取）的Dynamo中，server A，B，和C在一个分区。
client1 把x = 2 写入了A和B。
然后client2 准备把x = 4写入B和C。但是当它写完B后，还没写入C之前突然挂掉了。这下好玩了，client1 和 client2 一顿骚操作后，同一个分区的server中的值完全不一样：A觉得x = 2，B觉得x = 4，C觉得x = 1。数据的不一致还是小事儿，这时如果client 3 想来读取x的值就懵逼了：我到底该信谁？
而在这个系统加上前面一章节提到的Hinted Handoff后会变得更加复杂。
当C崩溃后，有些put请求可能会被一些其他分区的备用server接受，比如E。这时候不仅同一分区内的数据会不一样，可能某些备用server的值也不一样。这就导致一个系统里会充斥着同一个值的大量不同的版本，让人摸不着头脑。
所以至少需要提出一个解决这些分歧的方法。Dynamo的提议是给每个值不同的标识符，也就是版本号，这样能区分出数据的新与旧。听着是不是和我们上一篇文章的概念很像？其实就是在分布式系统中判断事件的时间先后顺序。只不过在Dynamo的第一篇论文发表的时候还没有那么多解决方法（如Google的True Time，或者Hybrid Logic Clock），所以他们用的是最古老的vector clock来当作数据的版本。vector clock简单来讲就是数据每经过一个server就会被赋予一个该server的时间戳，这样就会形成一个时间戳数组。然后通过比较该数组就能得出哪些数据是最新的。具体的细节大家可以去看看其他专门分析vector clock的文章。
有了数据版本，解决数据不一致的方法就有很多种了。Dynamo把这个方法留给了用户自己：用户可以决定用什么方式解决冲突：一般来讲都会采取Last Write Win，也就是时间戳最新的数据。
Vector clock有一个老生常谈的问题，就是扩容性不太好，版本数组的大小和Dynamo的server数量成正相关。扩容性当然是亚马逊的考量之一，而解决办法也十分粗暴：如果vector clock的版本数组长度超过一定的大小，Dynamo会直接pop掉在数组中的第一个版本。这确实有点太粗暴了，也肯定会存在问题，但是论文中却说道这并没有在prod环境中产生任何不良影响。So, what can I say 🤷♂️? 能跑就行。
灵活的读写方式加上多种数据版本，就已经说明了Dynamo不可能保证数据的强一致性（比如我put了一个新的值之后，get可能依旧会返回老旧的值）。但是亚马逊提供了让用户自己解决数据冲突的方式，也就让数据最终会是一致的，只是到底需要多长的时间谁也不能保证。
快速恢复
如果一个server下线太久，数据就会变得非常的老旧，也就需要更长时间去恢复到最新的数据。这个过程可以非常漫长，因为需要找到哪些数据不一样，然后才能依次进行更新。Again，这种恢复速度并不是亚马逊能接受的，所以需要一个快速找出老旧数据的方法。亚马逊的解决思路是Merkle Tree。
可能很多搞虚拟货币的人会很兴奋：Merkle Tree和Merkle Chain有着异曲同工之妙。Merkle Tree能通过一层一层的哈希最后快速判断出不一样的地方。
如果我们想找到具体哪块数据不一样，通过比较这颗树就行了。如果父节点的哈希值是一样的，则证明两份数据完全一样。如果父节点的哈希值不一样，则递归比较两个子节点。这样Dynamo就能以log N的复杂度快速定位。
同时，构建这个树也不会特别复杂。通过哈希数据块一层一层搭积木即可。
Dynamo - 我的看法🥸
Dynamo作为最早的几个大型分布式项目是带来了足够多的内容与惊喜的，一些分布式理论知识，比如一致性哈希，RW quorum，vector clock，还有Merkle Tree，很少被直接应用在如此大规模的系统里。它给工业界和学术界都提供了宝贵的经验。
同时，Dynamo也是非常成功的。它以极高的扩容性和可用性支撑着亚马逊庞大的业务量所带来的rps。据他们自己所讲，Dynamo在最繁忙的季节服务了百万级请求，没有哪一段时间是不可用的。
我们也发现，在现实的大部分业务当中可以适当的牺牲“正确性“以换取其他方面的收益，比如很多业务其实并不需要数据的强一致性，又比如vector clock可以”适当“的减少大小而不对业务造成任何影响。
但Dynamo团队再向内部大规模推广Dynamo的时候却遇到了一些问题。他们发现很多人都不是很愿意去使用Dynamo，相反更愿意去用亚马逊的另一个产品Simple DB，一个和S3差不多古老的数据库服务。 (Simple DB今天也在AWS上面可以购买）而令人很费解的是，Simple DB相比于Dynamo还是有许多明显不足的：
- 扩容性不足：Simple DB分区大小最多只有10个GB。应用层需要写很多复杂逻辑去应对这个限制。
- 性能差：每个data field强制index，这就导致了写的性能很不理想。
这么一对比Dynamo多好啊，扩容性高，性能也好，而且也特别灵活。为什么现实生活中大家更愿意去选择SimpleDB呢？
是啊，为什么呢？
问题所在
程序员不仅要写代码，而且也需要负责后期的部署和维护，这是有些人忽视了的事实。所以使用一个服务不仅要考虑开发时的难度，还要衡量后期部署和维护的成本。Dynamo恰恰在这个方面非常不尽人意。Dynamo不是一个managed service。你不能简单用aws account去连Dynamo endpoint就能调用它的API。Dynamo在交付的时候是一个binary（甚至有可能就是一堆源码需要去编译），用户需要自己去部署到机器上去，后期出了问题也需要自己修。想象一下你在半夜oncall的时候，Dynamo里的数据版本出问题导致程序崩溃了，你需要去看Dynamo的源码才能找到问题的根源，这是有多痛苦！所以，Dynamo的使用门槛非常的高，至少也得是Dynamo专家才行。大部分亚马逊的组都没有人有时间静下心来学习Dynamo到底是如何工作的，结果就是大家更愿意去使用Simple DB，一个能简单用aws account和endpoint就能轻松调用其API的数据库，不需要亲自去部署和维护。
第二个问题就是Dynamo需要程序员自己去设置的参数有点过于多了。比如前文提到过的N，W和R，又比如如何解决冲突。扩容和缩容也需要程序员自己做。这些参数如果不仔细研究的话，很容易造成不理想的performance。
其实从现在来讲，数据库基本上都是像Simple DB一样上云，成为managed service。用户很少花费大把时间考虑部署和后期运维。但是在2008年前后并不是一个属于云计算的时代，数据库也很少被考虑到要上云。Dynamo团队也在这个方面吃了亏。
大部分程序员只想要一个服务，而不是一个binary或者一堆源码。
Dynamo DB：上云之路
managed service和一个binary不同，服务是更高层次的抽象。变成服务的DynamoDB向程序员隐藏了更多的细节，这也给了它更多的自由，可以玩一些把戏，就像多租户模式。
多租户模式
以前的Dynamo部署之后只能有一个客户使用，但是如果上云的话，会有多个用户一起使用，这也就是多租户模式。举个例子，Dynamo就像在家里做饭一样，一般都是自家人吃。而Dynamo DB上了云变成了服务，就像变成了餐馆，会有不同的人一起吃。这当然就不一样。比如在餐厅里，几桌客人点了相同的菜，但餐厅也必须用不同的盘子来盛。同时餐厅也必须保证每个客人只能吃到自己桌上的饭而不能吃到别人桌上的。餐厅自己也可以偷懒，比如一锅出几桌人的菜。
用更程序员的方式来讲：如果你在aws上买一个mysql，aws并不会帮你创建一个新的MySQL 环境然后把mysql binary放里面，而是有可能多个用户共享一个mysql instance，然后用一些方法把每个用户隔离出来，给你一种mysql只有自己在用的错觉。
所以我们不难理解出，Dynamo DB需要很大的架构方面的变化。实际上，根据作者自己讲的，Dynamo DB和Dynamo的架构完全不一样。老Dynamo的架构完全不适合于多租户模式。想象一下，老的Dynamo架构是一个环，因为其独特的可用性，所有数据会混乱的出现在环里。如果变成多租户的话，会让数据管理十分混乱，维护相当困难。
Dynamo DB的目标
aws也希望把Dynamo DB卖给外部用户。内部服务和外部服务是有本质区别的。简单来讲，内部服务可以耍流氓但是外部服务不行。如果内部用户提出一个需求，可以适当的让他们“将就”一下。但是外部用户就不行了，你让他们“将就”他们只能让你滚蛋。所以Dynamo DB必须能满足更多用户的要求：
- Dynamo DB可以无限scale：不管你业务量的大小，Dynamo DB都能出色的完成crud的需求。
- Dynamo DB的performance必须是稳定且可预测的：所有crud的操作都给了延迟上的保证。用户不会被突然高延迟惊吓到。
- Dynamo DB必须是高可用的：保证至少4个9的可用性。
- Dynamo DB灵活适应大部分的业务：Dynamo不仅支持最终一致性的操作，也支持强一致性的操作。所以对正确性要求不高的业务，比如社交业务，能用它。高正确性的业务，比如分布式锁，也能用它。
新架构
DynamoDB的架构虽然重新设计了，但并没有什么特别的地方。事实上，他们采用的就是已经被业内证明了无数次的分区+paxos(Raft)的架构。具体这个架构的讨论可以看我Spanner那篇文章。这样的架构兼顾了可扩展性和可用性，同时有着多租户的案例，比如Spanner。因为用的是Paxos的缘故，强一致性也能得到保障，这样也就能服务尽可能多的用户。Dynamo DB甚至也支持transaction，这同样归功于分区+Paxos的架构。
当然，如果用户的业务不要求强一致性，read request能直接去读Paxos的replica，这样throughput能得到提升。read request的可用性也能受益，因为Paxos group里只需要有一个replica存活request便能成功。
在后面的章节我们会讲到Dynamo DB是如何魔改Paxos去以最小的代价最大化可用性的。
最后我想说一句，分区+Paxos已经成为绝大多数高扩容性分布式数据库的首选标准答案。Dynamo DB也证明了NoSQL也能从这个架构中受益，而不仅仅局限于NewSQL。
量化Dynamo DB的容量
当我们自己部署一个服务的时候，有一个问题总是最难的：我到底需要多少个服务器才能满足业务throughput的要求。虽然Dynamo DB已经变成了一个managed service，但是类似的问题对顾客来讲依旧存在：我到底需要多“大”的Dynamo DB才够我的业务的需求？作为一个合格的Managed service，它不能直接把多少个物理节点作为参数暴露出来让顾客选择，所以需要一个方法去量化容量。
首先想到的肯定是用throughput去量化容量。但是Dynamo DB支持的操作很多，不同的操作所需要计算资源是不一样的。为每个操作都去设置一个throughput也不现实。所以Dynamo DB给出的解决办法就是抽象一个新的概念叫read capacity unit(RCU)和write capacity unit(WCU)，然后不同的操作有不同的capacity unit。比如一个4KB的eventual consistent read值一个RCU，一个8KB的write值两个WCU。这样客户就能很轻松的计算出他们需要的Dynamo DB的大小。
这样的量化也能帮助Dynamo DB规划如何去储存这些数据。Dynamo DB有如下几个特点：
- 数据是分区的，所以容量会被平均分到每个分区。比如一张表设置了3000RCU，然后有5个分区，那么每个分区就会有600RCU。
- 数据库采用的多租户模式，所以一个物理节点可能会存在不同客户的数据分区。
所以通过每个客户提供的容量预估，DynamoDB就能很均衡的把不同客户的分区放在同一个储存节点上，而不会让该节点过载。但这样分配会给客户造成几个困扰
- 热分区：很少有业务的workload是均衡的，很容易部分分区太多请求过热而部分分区过冷。过热的区域会造成该分区容量不够，虽然总体容量并没有超过用户设定的总容量。
- 分区容量稀释：因为DynamoDB是根据数据量大小来决定分区，如果一个分区数据量过大，便会触发自动分区而把该区细分。假设该分区有600RCU，细分之后就只会有300RCU，容量便被稀释了。
容量不够的后果很简单：请求会被直接拒绝，毕竟亚马逊也是需要赚钱的，想要更多的容量得用钱来买。但这会造成即使DynamoDB是可用的，客户的请求因为容量不够的关系给他们造成一种服务不可用的错觉。客户当然很不爽，而亚马逊是以客户至上著称，那必须得给客户服务好！
容量爆发
亚马逊的第一招就是允许请求短暂的容量爆发。因为一个物理节点上有多个客户的数据分区，每个客户不太可能同时用到他们数据分区的容量上限，所以物理节点上大概率是有空间去允许一些分区请求突然爆发。DynamoDB的做法如下：
他们建立了一个Global Admission Control。这个control 服务会用token buckets去记录每一个request。只要没有超过总体的容量限制或者最大的分区爆发容量限制，GAC都不会去阻止这个请求。同时每个物理节点也会储存这么一个token bucket以确保物理节点不会过载。所以即使有热分区的出现，DynamoDB可以“借用”其他分区的容量来帮助处理这些热分区的请求。
自动分区
容量爆发只能解决临时过热的分区。如果有一些分区一直大规模的过热，比如占用了总容量的80%，那么客户的过热请求还是会被拒绝。所以亚马逊的第二招就是自动根据细分该分区，如果DynamoDB发现该分区过于热了，它会把这个分区分成两个小分区，然后通过它会选择最优的key(一般是根据观察请求的分布)确保两个小分区的容量类似。这样的话两个小分区就会在两个不同的机器上，然后可以更好的利用该机器进行容量爆发。
把分区配给到合适的节点
DynamoDB是多租户的关系，一个物理节点可以有多个客户的分区，所以如何配给到具体的物理节点也是一个麻烦。论文里没有提到亚马逊是如何具体用什么算法进行配给的，但是因为亚马逊有分区各种信息，比如分区容量，大小等，所以大概也能想象到需要把这些因素都考虑到。同时，物理节点的预设容量需要比该节点所有分区容量加起来还要大，这样才能更好的进行容量爆发，给客户最好的体验。如果DynamoDB发现某个节点容量已经快要被榨干了，就会选一个客户的分区进行重新配给，以免造成服务的不可用。
按需供给
实现完了这么多功能，DynamoDB团队突然发现，其实用户也根本不需要设定一个具体的容量。他们提供了一个选项叫按需供给：数据库会根据用户的请求容量自动扩容缩容。具体的实现方式则是会根据客户现在请求量估一个基础的容量，如果突然容量增多，则会通过GAC和自动分区去扩容。扩容时间一般在几分钟左右，所以那段时间请求会失败或者有延迟，扩容需要不那么频繁。DynamoDB采用的2倍定律：它自动给的容量会是客户目前容量的两倍。只要客户请求增加的量小于两倍，扩容都不会触发，有点类似于数组的实现方式。
按需供给的功能客户可太喜欢了。大家可以回想一下你们自己使用DynamoDB的经历，是不是很少挠破脑袋去想到底需要多大容量？一般都是直接选on demand开箱即用，节省了大量精力。
可用性和数据持久化
DynamoDB的视角里，可用性仍然是最重要的一环。面对内部客户时，可以稍微耍耍“trust me bro”的把戏，但是一旦要把DynamoDB卖给外部客户，可用性需要被量化，同时也需要告诉客户数字背后的意义。
DynamoDB采用了业界标准的办法：用9来衡量可用性。根据不同的设置，DynamoDB可以保证4个9或者5个9（99.99% 和 99.999%）的可用性，这也就意味着一个月以内数据库最多只能有4分钟（99.99%）或者26秒（99.999%）崩溃的时间，不然亚马逊就要赔钱。涉及到钱这个话题就无比严肃了。
机器崩溃
从理论上来讲，在Paxos里你可以无限去增加机器的方式暴力的增加可用性。但这当然是笨办法，因为这不仅成本大大增加，而且每个write request延迟也会增加，因为需要在更多的机器上达成一致。这也是为什么DynamoDB的每个paxos group只有少量的（我猜测大约五个？）机器。
但是五个机器的Paxos太脆弱了，如果有三个机器崩溃了整个分区也就挂掉了。而恢复一个机器需要花费好几分钟，也就是说这样的事故如果一个月内发生两次亚马逊就要赔钱。你想想，DynamoDB管理着成千上万个Paxos集群，太有可能发生这样的事故了，那不是得赔钱赔傻啦？
解决方法就是当发生这样不幸运的事件时，快速恢复。我个人觉得这也是工业界解决麻烦的特点之一，和学术界刨根问底的从根源上解决问题不同，工业界只需要找到确保问题影响最小化的方法就行。
我们可以先想一想假设Paxos group里有两个机器崩溃掉了，哪些服务会受到影响。
- eventual consistent read：因为是最终一致性的关系，只要Paxos group里的机器里有一个是好的，read便能返回成功。
- consistent read：因为是强一致性，所以完成这个请求必须发起一次Paxos quorum。现在group里超过一半的机器都挂掉了，所以请求便不可用了
- write：所有的write都是强一致性的，所以该请求也不可用，理由如上。
我们可以发现，只要是涉及到强一致性的操作便会不可用，理由则都是没办法发起一个Paxos quorum，因为在该group里超过一半的机器都挂掉了。
（看下去之前建议大家先学习一下Paxos/Raft是如何运作的）
首先先说一个众所周知的事实：DynamoDB背靠亚马逊云，而亚马逊云基本上有着无限多的虚拟机器。理论上来讲，如果Paxos group里有成员挂掉了，我们可以新开一个机器，并且用一种方法把该成员的之前所有log放到新机器上，该机器就能正常加入group恢复Paxos quorum的运行。亚马逊采用的也是这样的方式，但是现在问题就是恢复一个机器太困难了：
- log太多。把大量的log复制到另一个机器会消耗大量的时间，复制的时候是没办法服务请求的，所以可用性便会减少
- 要重新构造B tree index：恢复log的同时也得重新构造状态机的index，这这台机器才能服务正常服务请求
DynamoDB的解决办法也很直接
- 每隔一会儿就把当前所有log备用到S3上，然后在本地删掉。这样机器上只会有备用之前的最新的log。复制时只需要复制最新的log就行，速度大大增加。
- 让新加入的机器成为Paxos 里learner一样的角色，只储存log，不服务任何请求，也就不需要重新构造B tree index。新加入的机器被称之为log replica。
这样，DynamoDB可以花费几秒钟的时间快速恢复一个挂掉的Paxos group。当然，从论文上来看，它采取的是更加稳妥的办法：只要Paxos group里有一台机器挂掉了，就马上新起一个log replica。这样基本上给客户带来了“永不崩溃”的体验。
leader崩溃检测
在Paxos里，如果一个成员发觉leader有可能挂掉了，便会重新进行选举。在选举的过程中服务是不可用的。亚马逊在维护DynamoDB的时候就发现大部分的重新选举都是false positive，意思就是leader并没有挂掉，但因为网络延迟的原因，成员没有收到leader的“续约”消息便自作主张的重新进行选举。这造成了大量不必要的不可用时间。DynamoDB稍微修改了一下Paxos，在成员触发重新选举之前，需要联系一下其他成员，询问他们leader是否真的挂掉了。这样会大大减少错误的选举，增加可用性。
量化可用性
就像之前所说的，可用性是用9来描述的，通过可用性我们大概知道一个月最多有多少分钟服务不可用。但是DynamoDB是一个超大型的分布式系统，有着很多服务。可能会有部分服务挂掉了，部分服务依旧可用。这样使得它的可用性难以量化。
亚马逊每五分钟计算一次DynamoDB的可用性，通过 （成功完成的请求）/（总请求）来计算。当可用性低到临界值时就会报警，DynamoDB程序员就会介入。同时系统也会为每个客户产生专属于他们的可用性报告。客户可以很清晰的体会到他们购买的服务质量。
维护
维护这么大一个分布式系统肯定不是一件容易的事情。Dynamo DB的很多运维经验有不少都来自于血与泪的教训，非常具有启发性。
依赖
作为一个高可用的服务，选择自己依靠的其他服务必须很小心。比如DynamoDB依赖AWS IAM和AWS KMS来管理数据库权限，但是它们会反过来影响Dynamo DB的可用性。Dynamo DB需要在依赖不可用的情况下依旧正常工作。
所以亚马逊避免让IAM和KMS出现在数据库的关键路径上，而是间接引用这些依赖。DynamoDB会定期去缓存这些服务的数据，这样即使这些服务不可用了，DynamoDB也能用缓存过的数据正常服务客户。不仅如此用缓存也大大减少了调用这些服务的延迟。而对这些依赖服务本身而言也是利好，因为DynamoDB体量太大了，如果每次都要去请求这些依赖的话，这些外部依赖很有可能被天量请求给击溃掉。使用缓存的唯一问题就是不能及时拿到最新的数据，但是Dynamo DB专门设计了他们使用这些数据的方式。使用过期的数据也不会对实际生产环境造成太大的影响。
🤓：我之前在设计，或者观摩别人的系统的时候总是对使用第三方的服务过于保守，觉得使用别人的服务就跟他是一根绳上的蚂蚱了。如果它崩溃了，或者它的上游服务崩溃了，就会连锁崩溃最后造成大面积的服务瘫痪。从Dynamo DB的经验来看，只要做好依赖服务崩溃的后备方案，就能大幅度控制这些服务所带来的一些”意外“
部署
分布式系统的部署也是很有学问的一件事，稍有失误就出大事，而像DynamoDB这样体量的系统，一点点错误都会放大一百倍，所以部署更应该小心。首先，部署一个新功能或者新补丁时，肯定不能所有机器一起同时部署。你想想，Dynamo DB在超过100个数据中心运行，如果里面所有机器一起部署，然后代码出问题了，那就会在超过100个数据中心同时一起瘫痪。所以Dynamo DB必须分批部署，以确保新的代码有任何问题都能及时roll back，最小化影响。
但是分批部署也会有问题。在分布式系统中有一部分机器是新代码，有一部分机器是老代码，很有可能它们之间的沟通就会出现问题。DynamoDB 采用的read-write 部署方式。如果机器之间沟通的方式有变更，会先部署能让”理解”这些交流格式的代码，然后再部署“说”这样交流方式的代码。举个粗暴的例子：如果几个机器之间要从英文交流换成中文交流，DynamoDB会先部署能让机器听懂中文的代码，然后再部署能让机器说中文的代码，这样以确保不会出现一部分机器开始说中文了，一部分机器还不能理解中文。
我的看法🥸
DynamoDB已经无需再证明自己的成功了，这十多年来持续稳定的服务便是他们最好的明信片。 但是我相信这一路肯定不会像是表面上这么顺利，很多经验与设计都是来自于惨痛的经验与教训，比如2015年在US-East的服务瘫痪。因为DynamoDB是一个多分区架构，后面的paxos group需要不停的去pull整个table的最新路由列表，以便知道最新的数据分区情况，比如它需要分裂或者和其他分区合并。而这个表则是又反过来存到了DynamoDB自己里，构成了一种循环依赖，在某些极端情况下会显得非常不灵活与脆弱。结果在2015年的时候真的就酿成大错：因为DynamoDB才发布了GSI（Global Secondary Index 次键）这个新功能，导致路由列表膨胀的无比之大。同时，每一个secondary index都是独立分区的，客户每多设置一个GSI，路由列表就会膨胀超过一倍。结果在那天凌晨，因为网络波动的原因，所有机器同时去pull 它们分区的路由列表，但路由列表太大，并且同一时间的请求太多了，这就导致很多请求无法完成，机器无法得到最新的路由，于是这些机器一边自我下线，一边重试。但其实这没什么，就像我们之前说的如果Paxos Group里一些机器下线了，DynamoDB会马上安排新的机器上去，但是这些新的机器也会尝试去pull 路由列表。下线的机器在不断重试，越来越多新上线的机器也在不断请求，最终就把路由服务崩溃了，导致超过半数客户的DynamoDB的流量无法完成。
我个人总结了一下根本原因：
- 每个机器完全不需要把整个table的路由表给pull下来，只需要pull和它自己相关的就行。
- 把路由表存在DynamoDB自己太不灵活了，一旦发生意外便会造成服务的连锁崩溃。
当然DynamoDB也有做的很好的地方，比如分批部署确保只有一个区域受到影响，比如每五分钟去计算可用性能确保第一时间发现异常。在这件事情之后，DynamoDB便不把路由表存给自己了，而是专门创建了一个内存数据库，并且用Perkle Tree（很可惜我并没有在网上找到关于Perkle Tree的介绍）去优化查询效率，能让机器更快的找到只跟自己分区相关的路由列表。（说句题外话，我个人觉得把这些metadata存给自己不是一个好主意，“外包”给其他数据库是更方便快捷的做法，比如Snowflake 把metadata存到了FoundationDB https://www.snowflake.com/blog/how-foundationdb-powers-snowflake-metadata-forward/）
这是这十年来Dynamo DB最大的事故，一共持续了三个小时。在那之前DynamoDB基本上是以100%的可用性在运作。
抛开DynamoDB成功的维护经验，DynamoDB如何去改善开发人员使用体验最让我眼前一亮。使用数据库永远不是一个轻松的活。程序员需要想清楚schema，数据库的各种参数，数据库要多大的容量，如何部署等，所以很多公司都要专门招一个DBA去专门做这方面的苦活。但是DynamoDB帮你把这些事情抽象走了：DynamoDB不需要schema；DynamoDB可以自动扩容，DynamoDB无需部署。使用Dynamo DB可以最大化开发效率，用户的体验当然就是最好的。说句玩笑话，亚马逊是最能哄用户开心的，毕竟customer obsession已经融进了他们的血液中。
最后，Dynamo到DynamoDB的这20年变化也证明了DBaaS比起单纯的数据库更符合大部分开发人员的偏好。数据库太重要了，几乎世界上所有的业务都会用到。数据库同时也太复杂了，SQL解析，语句重写与优化，调度，执行，储存，index，事务ACID，WAL等等，每一个领域都能成为一个课题。在一个开发效率为王的时代，大部分程序员不可能对一个数据库了如指掌，也没有那么多时间去深入学习数据库的原理。所以一个好的数据库都能把所有复杂的细节都隐藏起来，只给用户暴露出恰到好处的功能使用。而上云变成managed service则是必经之路。
如果一个数据库，用户必须深入研读它的源代码，仔细摸索它的架构才能使用，那该数据库设计的是不是有些太过于失败了呢？
最后，感谢Junxi，Youheng和Haojia帮我读稿和提出宝贵建议😘
以上的所有信息均来自于亚马逊自己发布的两篇论文和博客和我自己的一些想法🥸：
[1] Dynamo: Amazon’s Highly Available Key-value Store https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
[2] Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service https://www.usenix.org/system/files/atc22-elhemali.pdf
[3] Summary of the Amazon DynamoDB Service Disruption and Related Impacts in the US-East Region https://aws.amazon.com/message/5467D2/