Dynamo 是一个高可用的 KV 存储系统。为了保证高可用和高性能，Dynamo 采用了最终一致性模型，它对开发人员提供一种新型 API，使用了版本机制，并通过用户侧辅助解决冲突。Dynamo 目标是提供不间断的服务，同时保证性能和可扩展性。由于亚马逊大量采用了去中心化、高度解耦微服务架构，因此对微服务状态的存储系统的可用性要求尤其高。
概览
S3 （Simple Storage Service）是 Amazon 另一款有名的存储服务，虽然也可以理解为 KV 存储，但它和 Dynamo 的目标场景并不一致。S3 是面向大文件的对象存储服务，主要存储二进制文件，不提供跨对象的事务。而 Dynamo 是一款面向小文件的文档存储服务，主要存储结构化数据（如 json），并且可以对数据设置索引，且支持跨数据条目的事务。
相对于传统的关系型数据库，Dynamo 可以认为是只提供主键索引，从而获取更高的性能和更好的扩展性。
为了实现可扩展性和高可用性，并保证最终一致性，Dynamo 综合使用了以下技术：
- 使用一致性哈希对数据进行分片（partition）和备份（replicate）。
- 使用版本号机制（Vector Clock）处理数据一致性问题。
- 使用多数票（Quorum）和去中心化同步协议来维持副本间的一致性（Merkle Tree）。
- 基于 Gossip Protocol 进行失败检测和副本维持。
实现上来说，Dynamo 有以下特点：
- 完全去中心化，没有中心节点，所有节点关系对等。
- 采用最终一致性，使用版本号解决冲突，甚至要求用户参与解决冲突。
- 使用哈希值进行数据分片，组织数据分布，均衡数据负载。
背景
目标和假设
不同的设计假设和要求会导致完全不同的设计，Dynamo 的设计目标有以下几个：
查询模型。使用 Dynamo 只会使用主键进行查询，一般没有跨数据条目，因此不需要关系模型。此外，Dynamo 假设其存储的数据都相对较小，通常小于 1M。
ACID 特性。传统关系型数据库（DBMS）为了保证事务的正确性和可靠性，通常需要具备 ACID 特性。但对 ACID 的支持会极大降低数据的性能，为了高可用性，Dynamo 只提供弱一致性（C），不提供隔离性（I），不允许单个 key 的并发更新。
效率。Amazon 中大部分服务对延迟有着严格的要求，为了能够满足此类服务的 SLA，Dynamo 须可配置，让用户自己在性能、效率、可用性和持久化间进行选择。
其他。Dynamo 只用在 Amazon 内部服务中，因此可以不考虑安全性。此外，很多服务会使用独立的 Dynamo 实例，因此最初针对可扩展性的目标在百台机器级别。
SLA
由于采用微服务架构，Amazon 购物网站的每个页面的渲染通常会涉及到上百个服务。为了保证用户体验，必须对每个服务的延迟做严格限制。Amazon 采用三个九（99.9% 的请求需要小于 300ms）的 SLA。而服务的状态存储环节则是提供该 SLA 的关键节点，为此 Dynamo 的一个关键设计是让服务可按需定制持久化和一致性等参数，以在性能、成本和正确性间进行抉择。
设计考量
对于多副本系统，高可用性和强一致性是一对矛盾。传统商用系统多为了保证强一致性而牺牲部分可用性，但 Dynamo 为高可用而生，因此选择了异步同步策略。但是由于网络和服务器故障的频发特性，系统必须处理这些故障所导致的不一致，或者说是冲突。这些冲突如何解决，主要包括两方面：在什么时候解决，以及，谁来解决。
何时解决。传统存储系统为了简化读取，通常在写入侧解决冲突，即当存在冲突的时候，拒绝写入。但 Dynamo 为了保证商城业务对用户任意时刻可用（比如随时能将商品加购物车，毕竟类似过程的体验稍微一下降，就会影响大把的收入），需要提供” 永远可写”（always writable）的保证，因此需要将解决冲突的复杂度推迟到读取时刻。
谁来解决。是由 Dynamo 来解决，还是应用侧来解决。如果是 Dynamo 系统来解决，通常会无脑选择” 后者胜 (last write win)”，即使用较新的更改覆盖偏旧的更改。如果交由应用来解决，则可以依据应用需求便宜行事，比如可以合并多次多次加购物车操作返回给用户。当然，这个是可选的，毕竟很多应用使用通用策略（”last write win”）就足够了。
其他关键设计原则还有：
增量扩展（incremental scalability）。支持节点的动态增删，而最小化对系统和运维的影响。
对称性（Symmetry）。系统中的每个节点职责相同，没有特殊节点，以简化构建和维护成本。
去中心化（Decentralization）。没有中心控制节点，使用点对点的技术以使系统高可用、易扩展。
异构性（Heterogeneity）。系统需要能够充分利用资源异构的节点，来按节点容量进行负载分配。
系统架构
围绕分区算法、备份策略、版本机制、成员组织，错误处理和可扩展性等分布式技术进行展开。
系统接口
Dynamo 暴露两个接口：put() 和 get():
get(key)：返回 key 对应的单个 object，或者有有版本冲突的 object 列表。
put(key, context, object)：根据 key 选出 object 要放的副本机器，并将数据落盘。context 会包含一些对调用者透明的系统元信息，比如 object 的版本号信息。context 会和 object 一块存储以验证 put 请求的合法性。
Dynamo 将 key 和 value 都视为字节数组，并且对 key 进行 MD5 算法以生成一个 128 位的标识符，以进行存储节点的选择。
分区算法 (Partitioning algorithm)
为了支持增量式扩容，Dynamo 使用一致性哈希算法进行负载分配。但基本版的一致性哈希算法有两个缺点：
- 不能够均匀的分摊负载。
- 照顾不到不同节点的资源差异。
为了解决些问题，Dynamo 使用了一致性哈希的变种：引入虚拟节点。具体算法为：
- 节点在接入系统时，根据其容量大小生成相应数量的虚拟节点，每个虚拟节点随机分配一个节点编号。
- 所有虚拟节点按编号的大小组织成一个首尾相接环状结构。
- 当有请求到来时，在与节点同样的编号空间内使用 key 加某种哈希算法生成一个数据编号。
- 根据此编号绕着虚拟节点环顺时针查找，找到第一个虚拟节点所对应的物理节点，将请求路由过去。
- 当有节点离开时，只需要移除其对应的虚拟节点即可，负载便会自动重新绕着环迁移。
其中，通过分配虚拟节点的数量来照顾到不同节点的容量差异，通过生成虚拟节点编号的随机算法保证节点增删时的流量均摊。
为了照顾节点的增删、备份的方便，Dynamo 先后使用了三种 Partition 策略：
1. 每个节点分配 T 个随机的数值编号（token），每个虚拟节点一个 token，哈希环中相邻两个虚拟节点的 token 所卡出的区间即为一个 partition。
这种最初的策略有以下几个缺点：
可以看出，这种策略的根本问题在于，数据分区（partition）和数据归置（placement）是耦合在一块的。这样我们就无法单独的对节点进行增删而不影响数据分区。因此，一个很自然的改进想法是，将数据分区与数据归置独立开来。
- 迁移扫描。当有新节点加入系统时，需要从其他节点偷过来一些数据。这需要扫描新增虚拟节点后继几个节点中所有数据条目以得到需要迁移的数据（猜测为了 serve get 请求，节点上的数据一般是按用户 key 进行索引组织的，而不是 key 的 hash 值，因此要获取某个 hash 值段的数据，需要全盘扫描）。这个操作挺重的，为了保证可用性需要降低迁移进程的运行权重，但这会使得迁移过程持续很久。
- Merkle Tree 重新计算。Merkle Tree 下面会讲到，可粗理解为以分区为单位对数据进行层次化签名。当有节点加入 / 离开集群时，会导致 key range 的拆分 / 合并，进而引起对应 Merkle Tree 的重新计算，这也是一个计算密集型操作，会导致很重的额外负载，在线上系统中不能忍受。
- 难以全局快照。由于数据在物理节点中的分布是按 key 的哈希值进行切分的，因此在 key 空间中是散乱的，很难在 key 空间中做全局快照，因为这要求所有节点上的数据进行全局归并排序，效率低下。
2. 每个节点仍随机分配 T 个编号，但是将 哈希空间等分作为分区。
在此策略下，节点的编号（token）只是用来构建虚拟节点的哈希环，而不再用来切分分区。我们将哈希空间等分为 Q 份，Q >> S*T，其中 S 是物理节点数。也就是说每个虚拟节点可以放很多分区。这种策略可以从另一种角度来理解，即节点 host 的最小单位不再是 key，而是一个分区，每次节点增删时，分区会整体进行移动。这样就解决了在节点增删时，迁移扫描和 Merkle Tree 重新计算的问题。
对于 key 的放置策略为，每次 key 进行路由时，首先算出其哈希值，依据哈希值所在分区（key range）的最后一个哈希值，在哈希环中查找。顺时针遇到的前 N 个物理节点作为偏好列表。
3. 每个节点 Q/S 个随机编号，哈希空间等分作为分区。
这种策略在上一种的基础上，强制每个物理节点拥有等量的分区。由于 Q 数量，甚至每个节点承载的分区数 （Q/S） 的数量远大于节点数（S），因此在节点离开时，很容易将其承载的节点数分配给其他节点，而仍然能维持该性质；当有节点加入时，每个节点给他匀点也容易。
备份策略 (Replication)
Dynamo 会将每条数据在 N 个节点上进行备份，其中 N 是可以配置的。对于每个 key，会有一个协调节点（coordinator）来负责其在多个节点的备份。具体来说，协调节点会负责一个键区段 （key range）。
在进行备份时，协调节点会选择一致性哈希环上，顺时针方向的后继 N - 1 节点，连同其本身，对数据条目进行 N 副本存储，如图二所示。这 N 个节点被称为偏好列表（preference list）。其中：
- key 到节点的映射根据上述三种不同的分区策略而不同。
- 节点可能会宕机重启，偏好列表有时候可能会多于 N 个节点。
- 由于使用的是虚拟节点，如果不加干涉，这 N 个节点可能会对应小于 N 个物理机。为此，我们在选择节点的时候需要进行跳选，以保证 N 个节点处于 N 台物理机上。
版本机制 (Data Versioning)
Dynamo 提供最终一致性保证，从而允许多副本进行异步同步，提高可用性。如果没有机器和网络故障，多副本将会在有限时间内同步完毕；如果出现故障，可能有些副本（replica）将永远无法正常完成同步。
Dynamo 提供任意时刻的可用性，如果最新的数据不能用，需要提供次新的。为了提供这种保证，Dynamo 将每个修改视为一个新版本、不可变数据。它允许多个版本的数据并存，大多数情况下，新版本数据能够对旧版本的进行覆盖，从而让系统可以自动的挑选出权威版本（syntactic reconciliation，语法和解）。但当发生故障或者存在并行操作时，可能会出现互相冲突的版本分支，此时系统无法自动进行合并，就须交由客户端来进行合并（collapse）多个版本数据（语义和解，semantic reconciliation）。
Dynamo 使用一种叫做矢量时钟 （vector clock）的逻辑时钟来表达同一数据多个版本间的因果关系（causality）。矢量时钟由一组 <节点， 计数> 序列组成，分别对应同一数据的同步版本。可以通多个数据版本的矢量时钟来确定这些数据版本间的关系：是并行发生（parallel branches）还是存在因果（casual ordering）：
- 如果矢量时钟 A 中的计数小于矢量时钟 B 中所有节点的计数，则 A 是 B 的前驱，可以被丢弃。比如，A 为 []，B 为 [, , ]
- 如果 A 不是 B 的前驱，B 也不是 A 的前驱，则 A 和 B 存在版本冲突，需要被和解。
在 Dynamo 中，客户端更新数据对象时，必须指明所要更新的数据对象的版本。具体方式为将之前从 Get 中获得的同一数据对象的版本信息（vector clock）传入更新操作中的 context。同样的，客户端在读取数据时，如果系统不能够进行自动合并（语法和解），则会将多个版本信息通过 context 返回给客户端，一旦客户端用此信息进行后续更新，系统就认为客户端对这多个版本进行了合并（语义和解）。下图是一个详细例子。
其中有几点需要注意：
- 每个服务器节点维护一个自增的计数器，当其处理更改请求前，更新计数器的值。
- 为了防止矢量时钟的尺寸无限增长，尤其是出现网络分区或者服务器失败时，Dynamo 的策略是，矢量时钟序列超过一定阈值时（比如说 10），将序列中最早的一个时钟对丢弃。
get () 和 put ()
本小节描述系统不产生故障时的交互。主要分为两个过程：
- 用某种方式选择一个 coordinator。
- coordinator 使用 quorum 机制进行数据多副本同步。
选择 coordinator
Dynamo 通过 HTTP 方式对外暴露服务，主要有两种策略来进行 coordinator 的选择：
- 使用一个负载均衡器来选出一个负载较轻的节点。
- 使用可以进行分区感知的客户端，直接路由到负责该 key 的相应 coordinator （即偏好列表中的第一个）。
第一种方式客户端不用保存服务器节点信息，第二种方式不需要转发，延迟更低。
对于第一种方式，如果是 put() 请求，选出的节点 S 不在首选列表 N 个节点中，S 会将请求转发到偏好列表中一个机器作为 coordinator。如果是 get() 请求，不管 S 在不在偏好列表中，都可以直接作为 coordinator。
Quorum 机制
Quorum 读写机制是一种有意思的读写方式，有两个关键配置参数 R 和 W，通常 R 和 W 需要满足 1.R + W > N 2. W > N/2，其中 N 是集群备份数。理解时可以从两个角度理解，一个是类比读写锁，即系统不能同时有多个写写、读写，但是 R 设置的小一些可以同时有多个读；另一个是需要半数以上写成功，以满足数据的持久化特性。但是在 Dynamo 这些都没有硬性要求，用户可以根据需求灵活配置。
当一个 put() 请求到达时，coordinator 为新数据生成一个新的 vector clock 版本信息，并将其写入本地，然后将数据发给 N 个偏好的 replica 节点，等到 W-1 节点回复，即可认为请求成功。
当一个 get() 请求到达时，coodinator 向保有该 key N 个首选节点（包括 / 不包括它自己）发送请求，等到其中 R 个节点返回时，将多版本结果列表返回给用户。然后通过 vector clock 规则进行语法和解，并将和解后的版本写回。
故障处理：Hinted Handoff
如果使用严格的 Quorum 机制处理读写，那么即使只有少量节点宕机或者网络分区也会使得系统不可用，因此 Dynamo 使用一种” 粗略仲裁”（sloppy quorum）算法，可以选择一致性哈希环中首选列表的前 N 个健康节点。
并且当首选 coordinator （比如说 A）故障时，请求在路由到其他节点（D）时，会在元信息中带上第一选择（A 的信息），D 后台会有个常驻线程，检测到 A 重新上线时，会将这些有标记的数据移到对应机器上，并且删除本机相应副本。Dynamo 通过这种 hinted handoff 的方式，保证有节点或网络故障时，也能正常完成请求。
当然，服务为了高可用，可以将 W 设置 1，这样首选列表中任何节点可用，都可以写成功。但在实践中为了保证持久化，一般都不会设这么低。后面章节将会详述 N，R 和 W 的配置问题。
此外，为了处理数据中心级别的故障，Dynamo 通过配置使得首选节点列表跨越不同中心，以进行容灾。
永久故障处理：副本同步
Hinted Handoff 只能处理偶然的、临时的节点宕机问题。为了处理其他更严重的故障带来的一致性问题，Dynamo 使用了去中心化的反熵算法（anti-entropy）来进行分片副本间的数据同步。
为了快速检测副本间数据是否一致、并且能够精确定位到不一样的区域，Dynamo 使用 Merkle Tree （也叫哈希树，区块链中也用）来以分片为单位对分片中所有数据进行层层签名。所有叶子节点是真实数据的 hash 值，而所有中间节点是其孩子节点的哈希值。这样的树有两个好处：
- 只要比对根节点，就可以知道分片的两个副本数据是否一致。
- 每个中间节点都代表某个范围的所有数据的签名，只要其相等，则对应数据一致。
- 如果只有少量不一致，可以从根节点出发，迅速定位到不一致的数据位置。
Dynamo 对每个数据分片（key range or shard，shard 是最小的逻辑存储单位）维护一个 Merkle Tree，借助 Merkle Tree 的性质，Dynamo 可以很快比较两个数据分片的副本数据是否一致。如果不一致，可以通过定位不一致位置，最少化数据传输。
这样做的缺点是，如果有节点加入或者离开集群，会引起大量的 key range 的变动，从而需要对变化的 key range 重新计算 Merkle Tree。当然，前面也讨论了，改进后的分区策略改进了这个问题。
成员关系和故障检测
显式管理成员关系。在 Amazon 的环境中，由于故障或人为失误造成的节点离开集群通常很少，或者不会持续太长时间。如果每次有节点下线都立即自动调整数据分片的放置位置，会引起不必要的数据震荡迁移。因此 Dynamo 采用显式管理成员的方式，提供相应接口给管理员对物理节点进行上下线。即，由于故障导致节点下线不会引起数据分片的移动。
类 Gossip 算法广播元信息。成员关系变动首先由处理成员增删请求的节点感知到，持久化到本地，然后利用类 Gossip 算法进行广播，每次随机选择一个节点进行传播，最终使得所有成员对此达成共识。此外，该算法也用于节点在刚启动时交换数据分片信息和数据分布信息。
每个节点刚启动时，只知道自己的节点信息和 token 信息，随着各个节点渐次启动，并通过算法互相交换信息，增量的在每个节点分别构建出整个哈希环的拓扑（key range 到虚拟节点，虚拟节点到物理节点的映射）。从而，当某个请求到来的时候，可以直接转发到对应的处理节点。
种子节点避免逻辑分区。引入功能性的种子节点做服务发现，每个节点都会直连种子节点，以使得每个加入的节点快速为其他节点所知，避免由于同时加入集群，互不知晓，出现逻辑分区。
故障检测。为了避免将 put/get 请求和同步元信息请求持续转发到不可达节点，仅使用局部的故障检测就足够了。即如果 A 发向 B 的请求得到不到回应，A 就将 B 标记为故障，然后开启心跳，以感知其恢复。如果 A 收到应该转向 B 的请求，并且发现 B 故障，就会在该 key 对应的首选节点列表中选择一个替代节点。
可以看出，Dynamo 将节点的永久离开和暂时离开分开处理。使用显示接口来增删永久成员，并将成员拓扑通过 gossip 算法进行广播；使用简单标记和心跳来处理偶发故障，合理进行流量转发。在故障较少的环境里，如此分而治之，能大大提高达成一致的效率，最大限度避免节点偶发故障和网络阵法抖动引起的不必要的数据搬迁。
增删节点
如下图，考虑三副本（N=3）并且采用最简单的分区策略的情况下，当在在节点 A 和 B 间加入一个节点 X 时，X 将会负责 Key Range： (F,G]，(G, A]，(A, X] ，同时 B 将不再负责 (F,G]，C 将不再负责 (G, A]，D 将不再负责 (A, X] ，Dynamo 通过 B，C，D 主动向 X 推送相关 Key Range 的方式来适应 X 的加入。在推送前有个等待 X 确认阶段，以避免重复推送。
实现
Dynamo 中每个节点主要包括四个组件：请求协调（request coordination），成员管理（membership），故障检测（failure detection）和一个本地的持久化引擎（local persistence engine）。所有组件都是用 Java 实现的。
Dynamo 的本地持久化组件，允许选择多种引擎，包括 Berkeley Database（BDB），MySQL 和一个基于内存 + 持久化的存储。用户可以根据业务场景进行选择，大部分的生产环境使用 BDB 。
请求协调组件使用 Java NIO 通道实现，采用事件驱动模型，将一个消息的处理过程被分为多个阶段。对于每个到来的读写请求都会初始化一个状态机来处理。比如对于读请求来说，实现了以下状态机：
- 发送请求到包含 key 所在分片的副本的所有节点。
- 等待读请求最小要求的节点数（R）个节点返回。
- 在设定时限内，没有收集到 R 个请求，返回客户端失败消息。
- 否则收集所有版本数据，并决定需要返回的版本数据。
- 如果启用了版本控制，就会进行语法和解，并将和解后版本写入上下文。
在读的过程中，如果发现某些副本数据过期了，会顺带将其更新，这叫做读修复（read repair）。
对于写请求，将会由首选 N 个节点中的一个作为协调者进行协调，通常是第一个。但为了提高吞吐，均衡负载，通常这 N 个节点都可以作为协调者。尤其是，大部分数据在读取之后，通常会紧跟着写入（读取获取版本，然后使用对应版本进行写入），因此常将写入调度到上次读取中回复最快的节点，该节点保存了读取时的上下文信息，从而能更快响应，提高吞吐。
引用
s3 和 Dynamo 对比：https://serverless.pub/s3-or-dynamodb/
