分布式键值存储 Dynamo 的实现原理

在最近的一周时间里,一直都在研究和阅读 Amazon 的一篇论文 Dynamo: Amazon’s Highly Available Key-value Store,论文中描述了 Amazon 的高可用分布式键值存储服务 Dynamo 的实现原理。

之前在阅读 Google 的 Bigtable: A Distributed Storage System for Structured Data 时写了一篇 浅析 Bigtable 和 LevelDB 的实现 文章分析了 Bigtable 的单机版 LevelDB 的实现原理;在研究 Dynamo 时,作者发现 Dynamo 虽然和 Bigtable 同为 NoSQL,但是它们的实现却有着很大的不同,最主要的原因来自不同的应用场景和不同的目的。

Bigtable 和 Dynamo

Bigtable 和 Dynamo 两者分别是 Google 和 Amazon 两大巨头给出的存储海量数据的解决方法,作为 NoSQL 两者都具有分布式、容错以及可扩展的几大特性。


虽然两者都是 NoSQL,并且有着相似的特性,但是它们在侧重的方向上有非常明显的不同,从两个数据库论文的标题中,我们就能看到 Amazon 的 Dynamo 追求的是高可用性并且提供的是类似 MongoDB 的 Key-value 文档存储,而 Bigtable 中描述的数据库却可以用于结构化的数据存储。

由于 Bigtable 和 Dynamo 都属于同一个类别 - NoSQL,所以它们经常会被放在一起进行对比,这篇文章不仅会介绍 Dynamo 的设计理念以及架构等问题,还会就其中的部分问题与 Bigtable 中相对应的概念进行对比,这样能够让我们更加清楚地了解不同的数据库对不同问题,因设计理念的差异做出的权衡。

架构

在数据库领域中尤其是分布式数据库,最重要的就是服务的架构,多数的分布式系统在设计时都会假设服务运行在廉价的节点上,并没有出众的性能和也不能提供稳定的服务,所以水平扩展和容错的能力是分布式数据库的标配;但是不同的分布式数据库选用了不同的架构来组织大量的节点。

很多的分布式服务例如 GFS 和 Bigtable 都使用了带有主节点的架构来维护整个系统中的元数据,包括节点的位置等信息,而 Dynamo 的实现不同于这些中心化的分布式服务,在 Dynamo 中所有的节点都有着完全相同的职责,会对外界提供同样的服务,所以在整个系统中并不会出现单点故障的问题。

去中心化的架构使得系统的水平扩展非常容易,节点可以在任何时候直接加入到整个 Dynamo 的集群中,并且只会造成集群中少量数据的迁移。

Bigtable 使用了中心化的架构,通过主节点来维护整个系统中全部的元数据信息,但是 Bigtable 本身其实并不会处理来自客户端的读写请求,所有请求都会由客户端直接和从节点通信,不过由于有了中心化的主节点,所以主节点一旦发生故障宕机就会造成服务的不可用,虽然 Bigtable 以及类似的服务通过其他方式解决这个问题,但是这个问题仍然是中心化的设计所造成的。

中心化或者去中心化并不是一个绝对好或者绝对坏的选择,选择中心化的解决方案能够降低系统实现的复杂度,而去中心化的方式能够避免单点故障,让系统能够更好更快地增加新的节点,提供优秀的水平扩展能力。

分片和复制

Dynamo 在设计之初就定下了增量扩展(Incremental Scalability)的核心需求,这也就需要一种能够在一组节点中动态分片的机制,Dynamo 的分片策略依赖于一致性哈希,通过这种策略 Dynamo 能够将负载合理的分配到不同的存储节点上。
所有的键在存储之前都会通过哈希函数得到一个唯一的值,哈希函数的输出被看做是一个固定长度的环,也就是其输出的最大值和最小值是『连接』到一起的:

每一个节点都会被 Dynamo 在这个环中分配一个随机的位置,而这个节点会处理从哈希的输出在当前节点前的所有键;假设我们有一个键值对 (draven, developer)Hash(draven)的结果位于上图中的绿色区域,从环中的位置开始按照顺时针的顺序寻找,找到的以第一个节点 B 就会成为协调者(coordinator)负责处理当前的键值对,上图中的每一个节点都会负责与其颜色相同的部分。

由于 Dynamo 系统中的每一个节点在刚刚加入当前的集群时,会被分配一个随机的位置,所以由于算法的随机性可能会导致不同节点处理的范围有所不同,最终每一个节点的负载也并不相同;为了解决这个问题,Dynamo 使用了一致性哈希算法的变种,将同一个物理节点分配到环中的多个位置(标记),成为多个虚拟节点,但是在这种策略下,如果当前的 Dynamo 节点一天处理上百万的请求,那么新增节点为了不影响已有节点的性能,会在后台进行启动,整个过程大约会消耗一整天的时间,这其实是很难接受的,除此之外这种策略还会造成系统进行日常归档极其缓慢。

为了解决负载的不均衡的问题,除了上面使用虚拟节点的策略之外,Dynamo 论文中还提供了另外两种策略,其中性能相对较好的是将数据的哈希分成 Q 个大小相等的区域,S 个节点每一个处理 Q/S 个分区,当某一个节点因为故障或者其他原因需要退出集群时,会将它处理的数据分片随机分配给其它的节点,当有节点加入系统时,会从其它的节点中『接管』对应的数据分片。上图只是对这种策略下的分片情况简单展示,在真实环境中分片数 Q 的值远远大于节点数 S。

Dynamo 为了达到高可用性和持久性,防止由于节点宕机故障或者数据丢失,将同一份数据在协调者和随后的 N-1 个节点上备份了多次,N 是一个可以配置的值,在一般情况下都为 3。

也就是说,上图中黄色区域的值会存储在三个节点 A、B 和 C 中,绿色的区域会被 B、C、D 三个节点处理,从另一个角度来看,A 节点会处理范围在 (C, A] 之间的值,而 B 节点会处理从 (D, B] 区域内的值。

负责存储某一个特定键值对的节点列表叫做偏好列表(preference list),因为虚拟节点在环中会随机存在,为了保证出现节点故障时不会影响可用性和持久性,偏好列表中的全部节点必须都为不同的物理节点

Bigtable 中对分片和复制的实现其实就与 Dynamo 中完全不同,这不仅是因为 Bigtable 的节点有主从之分,还因为 Bigtable 的设计理念与 Dynamo 完全不同。在 Bigtable 中,数据是按照键的顺序存储的,数据存储的单位都是 tablet,每一张表都由多个 tablet 组成,而每一个的 tablet 都有一个 tablet 服务器来处理,而 tablet 的位置都存储在 METADATA 表中。

在 Bigtable 中,所有的 tablet 都在 GFS 中以 SSTable 的格式存储起来,这些 SSTable 都被分成了固定大小的块在 chunkserver 上存储,而每一个块也都会在存储在多个 chunkserver 中。

读写请求的执行

Dynamo 集群中的任意节点都能够接受来自客户端的对于任意键的读写请求,所有的请求都通过 RPC 调用执行,客户端在选择节点时有两种不同的策略:一种是通过一个负载均衡器根据负载选择不同的节点,另一种是通过一个清楚当前集群分片的库直接请求相应的节点。

从上面我们就已经知道了处理读写请求的节点就叫做协调者(coordinator),前 N 个『健康』的节点会参与读写请求的处理;Dynamo 使用了 Quorum 一致性协议来保证系统中的一致性,协议中有两个可以配置的值:R 和 W,其中 R 是成功参与一个读请求的最小节点数,而 W 是成功参与写请求的最小节点数。

top Created with Sketch.