沧海一滴水 2014-05-19
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的观点: