Amazon Dynamo 是分布式的 key-value 系统,最近阅读了 Dynamo 最初的论文 《Dynamo: Amazon's Highly Available Key-value Store》,本文想聊一聊它的去中心化(decentralization)。既有阅读相关材料后对其实现的理解,也有自己的思考,其中如有不正确言论欢迎指出。
中心节点
通常,我们见到的分布式存储结构都是具备中心(总控)节点的,比如 Google File System(GFS),包括了中心的 Master 和数据节点 Chunck Server;再比如 HDFS,包括了中心的 Name Node 和数据节点 Data Node。下面就以这两者为例来说明设置中心节点遇到的问题和解决。
中心节点通常包含了存储单元的分布信息,存储内容的元信息,“ 一致性” 是分布式系统的核心内容,而在处理一致性问题上,引入中心节点可以带来莫大的好处,但是,也容易引发问题:
(上图来自《HDFS HA: 高可靠性分布式存储系统解决方案的历史演进》)
有趣的是,整个互联网就可以看做是一个巨大的分布式系统,经过了实践检验,我们可以认为它的的确确是去中心化的,但它也并不是每个维度都“ 去中心”,比如域名服务器,顶级域名服务器就是一个中心节点。因此如果仅仅是为了分布式,而粗暴地把中心节点去掉不是明智的,当然,Dynamo 做了尝试,下面我列出了一些去掉中心节点后带来的问题,和它的解决办法。
Dynamo 的去中心化
在上面提到了的 Dynamo 2007 年的论文中,就直白地强调了去中心化是 Dynamo 设计的一条重要原则:
Decentralization: An extension of symmetry, the design should favor decentralized peer-to-peer techniques over centralized control. In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.
Dynamo 的设计者已经意识到了中心化系统带来的问题,包括服务中断,因此要尽可能避免。其它还包括的设计原则有:
下图来自该论文,列出了遇到的问题和解决问题采用的技术,这是 Dynamo 设计的核心,而其中的大部分问题都是和去中心化相关的:
下面逐条叙述:
Partioning
采用一致性 Hash(Consistent Hashing)来解决节点增加和水平扩展的问题,带来的好处和设计原则中的增量扩展是一致的。它本身已经不是一个新话题了,介绍它的材料互联网上有很多,在此不赘述。Dynamo 的实现上有两点特别需要指出:
High availablity for writes
采用向量时钟(Vector Clock)来处理一致性问题,向量时钟实际上是一个 (node,counter) 对的列表,如下图:
D1 写入,发生在节点 Sx,形成向量时钟 Sx,1,Sx 又发生一次写,于是 counter 增加 1,变成了 Sx,2,之后基于它发生了 D3 和 D4 两次写入,于是出现了两个版本,(Sx,2,Sy,1) 和 (Sx,2,Sz,1),在 D5 的时候协调,协调成 Sy 先于 Sz 发生,counter 再加 1。这里的协调有两种方式:
Handling temporary failures
Sloppy Quorum:草率的法定人数(这个不知道如何翻译),这里有一个有名的 NWR 机制,其中:
当 W+R>N 的时候,可以保证强一致性,对于这个定理,分类举例说明如下:
通过协调 N、W、R 之间的值,就可以在一致性和可用性之间做 tradeoff(CAP 理论中 P 是无法牺牲的,而 C 和 A 是可以取舍的),因为 W 或 R 是同步的,因此基本上 W 或 R 的值越大,Availability 就越差。
Hinted Handoff:暗示的转交,如果写操作过程中节点 A 暂时不可用,可以自动将
该节点上的副本转交到别的节点去,这是为了保证副本总数不减少。而这个转交的数据会设置一个暗示的标记,等到节点 A 恢复了,会被重新转交回 A。
Recovering from permanent failures
使用 Merkle Tree 的反熵(anti-entropy)。Merkle 是这样一种数据结构,非叶子节点提供了多层 Hash 的功能:
反熵协议是用来帮助副本之间的同步的,使用 Merkle 的主要优点是每个分支可以独立地检查,而不需要下载整个树或整个数据集。
Membership and failure detection
基于 Gossip 的成员协议(membership protocol)和故障检测。Gossip 协议本身就是为了去中心化而设计的,虽然无法保证在某个时刻所有节点状态一致,但可以保证在某个最终的时刻一致。成员协议用于在 hash 环上增加或减去节点。
关于 Dynamo 的吐槽
对于 Dynamo 的去中心化,实在是功过兼备,毕竟引入了上面介绍的一堆复杂的机制,尤其对于数据的一致性问题,更是争议不小。使用一个 Master 节点,丢失了中心化,但是一致性的问题就容易解决得多,系统也会更简单;退一步说,如果要去中心化,但是使用 Paxos 这样的协议,来选举一个“Master” 出来,那也能比较简洁地保证一致性。但是 Dynamo 最后的实现,让用户来解决冲突的做法(有时候用户也没法确定该用哪个版本),确实有些别扭;而采用绝对时间来解决冲突的方法,则是在机制上有天生的缺陷(时间无法做到绝对同步)。
网上曾经有一篇很火的吐槽 《Dynamo: A flawed architecture – Part 1》,抱怨了一些 Dynamo 的问题,新浪的 Tim Yang 写了一篇文章简单翻译了一下,我就不再赘述,大致上抱怨的问题包括:
这篇文章的标题写着 part 1,只可惜 part 2 没有出现。这篇文章引起了不少争议,作者后来自己写了一篇 《Dynamo – Part I: a followup and re-rebuttals》来回应,文章结尾总结了一下他对 Dynamo 的观点:
淘宝日照博客中的一篇文章,也谈到了 Dynamo 设计上的一些问题,特别是对于一致性和分区容忍性上面精彩的吐槽,推荐阅读。
文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》