Dynamo

[levy5307]

https://levy5307.github.io/blog/Dynamo/

Dynamo是Amazon实现的一款KV存储。为了支持Amazon大规模且持续增长的用户，具有高可用、高扩展性的特性。Dynamo有一个重要的设计目标：允许应用自己控制自己的系统特性（例如持久性和一致性）让应用自己决定如何在功能、性能和成本效率之间取得折中。

Background

我们对我们的存储服务有如下几个要求：

Query Model: 通过唯一的key来对数据进行读写。状态以二进制的形式存储，并以唯一的key标识。没有操作跨越多个data item，并且没有relational schema。该需求是基于我们观察到很大部分的Amazon内部的服务只需要加单的query model、而不需要relational schema。Dynamo面向的是存储数据小于1MB的应用。

ACID properties: ACID是一组保证数据库事务可靠执行的特性。在数据库领域，对数据的单词逻辑操作成为事务。在Amazon的经验表明，让数据仓库支持ACID会使得它的可用性非常差。Dynamo不提供任何隔离保证，并且只允许单个key的操作。

Efficiency: 系统需要运行在通用硬件上。Amazon内部对服务的延迟有着严格的要求，通常使用p999来衡量。另外，服务需要有配置Dynamo的能力，以便能满足服务的延迟和吞吐要求。最终在性能、成本效率、可用性和持久性之间取得折中。

Other Assumptions: Dynamo仅仅在Amazon内部使用，因此假设其运行环境是安全的，因此没有authentication和authorization方面的需求。另外，每个服务使用其自己独立的Dynamo集群，因此我们的初始设计中，Dynamo的存储规模是几百个存储节点。

Design Considerations

商业系统中的数据复制都是同步的，这样可以提供一个强一致的数据访问接口。为了达到这种级别的一致性，这些算法强制牺牲了在某种错误场景下的可用性。其实对于服务器和网络故障比较容易出现的场景，可以通过使用乐观复制技术来提高可用性。在这种复制技术中，数据变更在后台同步到其他节点，并发更新和网络失联也是可以容忍的，这种方式也叫做异步复制，其无法满足强一致性。Dynamo设计为最终一致性的存储服务，即所有的更新最终会到达所有的副本。但是这种模式的挑战在于如何检测和解决冲突。而解决冲突也会带来两个问题：何时解决冲突以及谁来解决冲突。

何时解决冲突

一个非常重要的设计考虑是决定何时执行解决更新冲突，例如，是在读的时候还是写的时候去解决冲突。一些传统的数据仓库是在写的时候解决冲突，这样可以保证读流程足够简单。在这种系统中，如果写入不能到达全部或者大多数的副本，写入将会被拒绝。与此相反，Dynamo被设计为永远可写的数据仓库。对于Amazon的许多服务来说，拒绝写入会导致非常差的客户体验。例如，尽管在发生网络或者服务器故障的时候，也应该允许用户向购物车中添加或者删除商品。这种需求导致我们将冲突解决放在了读取操作，以保证写入永远不会被拒绝。

谁来解决冲突

下一个问题在于，谁来执行冲突解决。存储和应用都可以解决这件事情。如果是由存储来做，那么选择将会相当受限，因为存储系统只能选用比较简单的策略，例如：最新写入有效。另外一方面，应用更加理解其data schema，其可以选择一个更适合自己的冲突解决方案。例如，购物车可以选择合并冲突的版本，返回一个合并后的购物车。不过尽管这样会带来很大的灵活性，但是很多应用并不想实现自己的一套冲突解决机制，因此这种情况下可以由存储系统来解决，采用一些简单的策略，例如前面所说的最新写入有效。

另外，还有一些其他的关键设计：

Incremental scalability（增量扩展性）: Dynamo应该可以逐台机器的扩容，并且对系统及其运维人员的影响尽量小。

Symmetry（对称性）：每个节点的职责应该是相同的，不应当出现某些节点承担特殊角色或者特殊职责。根据我们的经验来说，对称性简化了系统的交付和运维。

Decentralization（去中心化）：去中心化是Symmetry的扩展，系统应该是去中心化、点对点的，而不应该是中心化的。在过去中心化导致了很多故障，现在的设计目标应该是尽量避免它。去中心化使得系统更加简单、更容易扩展并且更加高可用。

Heterogeneity（异构性）：系统要能够利用到基础设施的异构性。例如，负载的分布要和存储节点的能力成正比。对于逐步加入能力更强的新节点、且一次性升级现有节点的情况下，异构性支持是至关重要的。

System Architecture

生产环境的存储系统的架构是很复杂的。除了数据持久化之外，系统还要为以下组件设计高扩展与健壮的解决方案，这些组件包括：负载均衡、成员管理、故障检测、故障恢复、副本同步、过载处理、状态转换、并发与任务调度、请求压缩、请求路由、系统监控和报警、以及配置管理。在这篇文章里主要关注Dynamo使用到的、分布式系统中的几个核心技术：分区、复制、版本化（versioning）、成员管理、错误处理、规模扩展（scaling)。

System Interface

Dynamo使用key通过一个非常简单的接口来访问对象，它提供两个操作：

get(key): 该操作会定位到该key对应的所有的副本，并返回单个对象或者一个包含冲突版本的对象列表，以及一个context上下文。

put(key, context, object):该操作先根据key获取该object的存放位置，然后将其写入磁盘。

其中context包含了对象相关的元数据，例如对象的版本。其对调用方是不透明的。context信息和对象时存储到一起的，这样可以很容易验证put请求的context是否是合法的。

Dynamo将调用方提供的key和对象都视为不透明的字节序列。它对key应用MD5 hash产生一个128bit的ID，并根据该ID计算应该存储到哪个节点。

Partitioning Algorithm

Dynamo的设计核心需求之一就必须支持增量扩展（scale incrementally）。这要求需要有一个机制将数据动态分散到系统中的不同节点上。Dynamo的数据分片机制依赖于一致性hash。在一致性hash中，hash函数的输出范围通常作为一个固定的环。每个节点会随机分配一个落在该环上的值，其代表了该节点所在环上的位置。对一个数据项，通过如下步骤找到对应的存储节点：

首先对key取hash值

在环上沿着顺时针方向找到第一个所对应的hash值比该key的hash值更大的节点。

因此，每个节点都负责环上它的前继节点与自己范围内的区域。一致性hash的好处在于，添加或者删除节点只会影响相邻的节点，其他节点不受影响。

但是基础的一致性hash有如下缺点：

给每个节点随机分配一个位置会导致数据和负载的非均匀分布。

没有考虑到节点的异构因素，导致性能不理想。

为了克服这些问题，Dynamo使用了一致性hash的变种，即：每个节点并不是映射到环上的一个点、而是多个点（Cassandra采用了一致性hash的另一个变种，具体可以参考）。Dynamo使用虚拟节点的概念。一个虚拟节点看上去和一个普通节点一样，但是一个实际节点对应的不止一个虚拟节点。具体来说货，当一个新的节点添加到系统后，它将会被分配环上的多个位置。

虚拟节点会带来如下好处：

当一个节点不可用时（故障或例行维护），这个节点的负载会均匀分散到其他可用节点上

当一个节点重新可用时，或新加入一个节点时，这个节点会获得与其他节点大致相同的负载

一个节点负责的虚拟节点的数量可用根据节点容量来决定，这样可用充分利用物理基础设施中的异构性信息

Replication

为了实现高可用和持久性，Dynamo将数据复制到多个节点上。每个数据被复制到N个节点上，这里的N是由每个Dynamo集群自己配置的。每一个key都会被分配到一个coordinator节点，coordinator节点负责落到它管理范围内数据的复制。它除了自己复制一份之外，还会向环上沿着顺时针方向的N-1个节点上存储一个副本。因此每个节点都要负责从自己开始向前N个前继节点的数据范围。

如上图所示，当N=2时，Key的coordinator是节点D，但是其也会被复制到E和F。所以对于节点F，其负责的key范围是(A, F]。

存储某个特定key的所有节点组成一个列表，成为preference list。另外需要注意，由于Dynamo引入了虚拟节点，所以存储一个key的N个preference list，其物理节点可能少于N个，为了避免这个问题，preference list在选择节点的时候会跳过一些位置，以保证preference list里面的节点都在不同的物理节点上。

Data Versioning

Dynamo提供了最终一致性，所有更新都会异步的复制到所有副本。put()操作可以在应用到所有副本之前返回给调用者，因此将会导致紧接着的get()操作可能获取不到最新的数据。在没有故障的情况下，更新传播都是有一个时间上限的。然而在某些特定的故障场景下（服务器故障或者网络分区），更新可能在限定的时间内无法传递到所有副本。

Amazon有些场景可以容忍这种不一致性，并且可以在这种场景下继续运行。例如，购物车应用要求所有的“Add to Cart”操作永远不能丢失或者被拒绝。如果购物车当前最新的状态不可用，那么用户可以在一个稍老的版本上做修改，并且这种修改也是有意义的、并且需要保留。但是他不能取代购物车最新的状态，因为最新的状态也有一些改变需要保留。在这里需要注意的是，“add to cart”和“delete iter from cart”在Dynamo中都是使用put请求。当一个顾客想要向购物车中添加或者删除一个商品时，如果购物车当前最新的状态不可用，那么该商品将会被添加到老版本的购物车中，并由随后的步骤来解决冲突。