Dynamo的实现技术和去中心化

标签: Distributed System CAP Dynamo HDFS 一致性 | 发表时间:2014-04-28 17:06 | 作者:四火
出处:http://www.raychase.net

Dynamo的实现技术和去中心化

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。下面就以这两者为例来说明设置中心节点遇到的问题和解决。

中心节点通常包含了存储单元的分布信息,存储内容的元信息,“一致性”是分布式系统的核心内容,而在处理一致性问题上,引入中心节点可以带来莫大的好处,但是,也容易引发问题:

  • 单点故障:这个问题的解决主要靠热备,比如GFS就靠Shadow Master。而HDFS情况比较复杂,在Hadoop 2.0以前靠的是Secondary NameNode,它不是真正的HA(High Availability),它只是阶段性的合并edits和fsimage,以缩短集群启动的时间,因此在Name Node出问题的时候,它既不能保证立即提供服务,也不能保证数据的完整性;现在HDFS为保证Name Node的HA,做法就很多了,包括了(1)shared image或者是(2)data replication的方法, 这篇文章有系统的介绍

Dynamo的实现技术和去中心化

(上图来自《 HDFS HA: 高可靠性分布式存储系统解决方案的历史演进》)

  • 扩展性,我们可以按照这样的思路来解决这个问题:
    • 中心节点包括了两个基本职责,一个是文件系统的维护,它需要知道每个数据节点上的哪块空间存放了哪些数据;还有一个是对于数据请求的调度。这两个是可以拆开来的。
    • 把单Master变成Multi-master,Master之间可以用不同的方式实现数据同步,这个方法的好处在于Master的水平扩展变得容易,问题还是在于一致性,如果不同的Master要操纵同一个数据节点上同一片数据,需要有专门的方式来处理冲突。
    • 对于元文件信息量较大时会比较麻烦,比如HDFS上都是小文件,文件数量众多,存储效率低(这是HDFS不适宜的一个使用例子,在 这篇文章里面我提到过),Name Node的内存消耗大。要么就不要这么用,GFS就比较适用于存放大文件;要么就从存储架构上解决,软件系统一个通用的办法是引入新的一个层,比如在Name Node和Data Node之间引入一个区域自治的层,这一层每一个节点分别自治管理一部分Data Node,而都从属于Name Node。

有趣的是,整个互联网就可以看做是一个巨大的分布式系统,经过了实践检验,我们可以认为它的的确确是去中心化的,但它也并不是每个维度都“去中心”,比如域名服务器,顶级域名服务器就是一个中心节点。因此如果仅仅是为了分布式,而粗暴地把中心节点去掉不是明智的,当然,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的设计者已经意识到了中心化系统带来的问题,包括服务中断,因此要尽可能避免。其它还包括的设计原则有:

  • Incremental scalability,增量扩展,减少对系统的影响;
  • Symmetry,对称性,节点之间都是对等的;
  • Heterogeneity,多相性(不知道怎么翻译更好),系统的扩展性可以按不同的比例落实到不同类型和能力的硬件上面去。

下图来自该论文,列出了遇到的问题和解决问题采用的技术,这是Dynamo设计的核心,而其中的大部分问题都是和去中心化相关的:

Dynamo的实现技术和去中心化

下面逐条叙述:

Partioning

采用一致性Hash( Consistent Hashing)来解决节点增加和水平扩展的问题,带来的好处和设计原则中的增量扩展是一致的。它本身已经不是一个新话题了,介绍它的材料互联网上有很多,在此不赘述。Dynamo的实现上有两点特别需要指出:

  • 每一台物理设备都根据不同的能力折合成不同数量的虚拟节点数目;
  • 每份数据都被映射到整个hash环上面的多个节点,从而形成replication,保证可用性。

High availablity for writes

采用向量时钟(Vector Clock)来处理一致性问题,向量时钟实际上是一个(node,counter)对的列表,如下图:

Dynamo的实现技术和去中心化

D1写入,发生在节点Sx,形成向量时钟[Sx,1],Sx又发生一次写,于是counter增加1,变成了[Sx,2],之后基于它发生了D3和D4两次写入,于是出现了两个版本,([Sx,2],[Sy,1])和([Sx,2],[Sz,1]),在D5的时候协调,协调成Sy先于Sz发生,counter再加1。这里的协调有两种方式:

  • last write wins,依赖于节点时钟,但是时钟之间无法做到绝对一致
  • 客户端来决定

Handling temporary failures

Sloppy Quorum:草率的法定人数(这个不知道如何翻译),这里有一个有名的NWR机制,其中:

  • N表示复制的数据备份数量,
  • W表示同步确认成功的写操作的副本数(剩下N-W的写操作是异步进行的),
  • R表示同步确认成功的读操作的副本数(每次读通过比较前面提到的向量时钟/版本号来确定有效的副本)。

当W+R>N的时候,可以保证强一致性,对于这个定理,分类举例说明如下:

  • 如果W<R,例如W=1,R=2,N=2,那么两份数据拷贝中,有一份同步写(有效数据),一份异步写(可能暂时无效),而有两份同步读,所以肯定能读到一份有效的数据;
  • 如果W=R,例如W=1,R=1,N=1,这是最简单的“单库模式”,没有异步写;
  • 如果W>R,例如W=2,R=1,N=2,两份写入都是同步写,因此读任意一份数据都是有效的。

通过协调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的功能:

Dynamo的实现技术和去中心化

反熵协议是用来帮助副本之间的同步的,使用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写了一篇文章简单 翻译了一下,我就不再赘述,大致上抱怨的问题包括:

  1. 一致性方面,Dynamo没有办法保证避免脏读;
  2. Quorum机制中只是R+W>N在遇到节点不可用的时候,并不能保证强一致性;
  3. Hinted Handoff机制在跨IDC的情况下,会因为异地传输开销而性能低下;
  4. 灾难恢复方面,某一个IDC挂掉的时候,没人可以计算到底丢了多少数据;
  5. 论文里面一些自相矛盾的地方,一个是对节点对等的描述,一个是对最终一致的描述;
  6. Dynamo给用户造成了误导,以为一直是在CAP的C和A中必须做一个取舍,其实单节点中心就可以同时做到CA;
  7. Dynamo宣称去中心化,但是并没有完全做到,比如交换机故障造成网络分片的时候,服务就不可用了。

这篇文章的标题写着part 1,只可惜part 2没有出现。这篇文章引起了不少争议,作者后来自己写了一篇 《Dynamo – Part I: a followup and re-rebuttals》来回应,文章结尾总结了一下他对Dynamo的观点:

  • 尽量去避免脏读;
  • 不受控的脏读任何时候都不可接受,即便在灾难发生的时候——就算数据丢失也比它要好得多,大多数情况下,管理员会关闭部分或者全部的服务,而不是去用丢失或者损坏的数据来响应用户
  • 一个数据中心内的网络分片要避免,在一个数据中心内考虑P(partition tolerance)是不合理的;
  • 中心化并不意味着低Availability,高可用的服务是可能的,虽然说scalability可能会成为问题;
  • 开发设计的对称性并不能很好适应硬件和网络的非对称性;
  • 数据中心一致性、高可用性和扩展性是可以同时达到的,只要在一个数据中心里面(也就是说P被放弃的时候),BigTable+GFS,HBase+HDFS,甚至Oracle RAC都是很好的例子;
  • Dynamo的读写即便在一个数据中心内也会引起脏读;
  • 谁也不知道脏读避免的时间边界在哪里;
  • 跨数据中心的情况下,没法跟踪有多少数据待更新,而灾难恢复的时候,也没法知道有多少数据丢失。

淘宝日照博客中的 一篇文章,也谈到了Dynamo设计上的一些问题,特别是对于一致性和分区容忍性上面精彩的吐槽,推荐阅读。

 

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

分享到:

相关 [dynamo 技术 去中心化] 推荐:

Dynamo的实现技术和去中心化

- - 四火的唠叨
Amazon Dynamo是分布式的key-value系统,最近阅读了Dynamo最初的论文 《Dynamo: Amazon's Highly Available Key-value Store》,本文想聊一聊它的去中心化(decentralization). 既有阅读相关材料后对其实现的理解,也有自己的思考,其中如有不正确言论欢迎指出.

Amazon Dynamo – 纠结的设计

- Lianhui Wang - NOSQL Notes
从09年第一次阅读Dynamo论文,到最近阅读Amazon S3的一篇专利,一路过来对论文的理解可以简单归结为两个字 – 纠结. 第一次看到Amazon Dynamo论文,有一种眼前一亮的感觉,Dynamo通过巧妙地组合一些P2P技术在Amazon构建了一个工程上可行的系统,CAP,NWR, Vector Clock一时成为流行词,更为神奇的是,Dynamo号称能够让用户设置不同的NWR策略从而在CAP三者之间获得一个很好的权衡,鱼和熊掌亦可兼得.

Dynamo和Cassandra海量存储基础

- - 忘我的追寻
提到这两个系统,他们在核心思路上是非常类似的,但有一些细节性的东西又有所偏重,在分布式系统中也算是独树一帜了,很有代表性的一个系列,这些不一致的地方,最明显的地方就在于一致性上. 可见,哪怕是从追求简单为上的工程化实现来说,各种不同的方式实现一致性也都有很大的不同,不过他们也有一些共性和一些独树一帜的概念,下面来做一下分别解说.

真正去中心化的BT客户端发布

- Furie - Solidot
BitTorrent是一种点对点的文件分享技术,但是它的下载仍然严重依赖集中化的中心服务器,依赖于BT搜索引擎和索引网站如海盗湾,tracker服务器;即使是号称去中心化的DHT技术也需要一台中心服务器. 然而,理想化的、完全去中心化的BT客户端已经现身. Tribler BitTorrent客户端的最新版本,整合了“零服务器”方法,功能包括实时视频流,高级防Spam控制,个性化内容频道等.

BitTorrent开发去中心化聊天应用

- jimmy54 - Solidot
即时聊天程序需要中心服务器,BitTorrent宣布推出了一个去中心化的聊天应用µChat(通过µTorrent的App Studio下载). 聊天应用需要解决三大挑战:选择聊天对象,寻找聊天室和列出聊天朋友列表. µChat使用磁链去解决了问题,用户通过磁链进入聊天室,从聊天室里看到聊天对象;当你和某人加为好友后,你们两人将加入一个相同的唯一磁链.

去中心化的招聘平台,会是Web3的应用典范吗?

- - 虎嗅网 - 首页资讯
本文来自微信公众号: 海外独角兽(ID:unicornobserver),作者:Packy McCormick,编辑:Siqi,原文标题:《Braintrust :去中心化的Boss直聘,Web3 融入现实的典范》,头图来自:视觉中国. DAO 的兴起让人们第一次开始认识到所有权经济:即由用户拥有、运营、维护、扩张自己正在使用的网络.

前端技术

- - CSDN博客综合推荐文章
随着互联网产业的爆炸式增长,与之伴生的Web前端技术也在历经洗礼和蜕变. 尤其是近几年随着移动终端的发展,越来越多的人开始投身或转行至新领域,这更为当今的IT产业注入了新的活力. 尽管Web前端技术诞生至今时日并不长,但随着Web技术的逐渐深入,今后将会在以下几方面发力. JavaScript的兄弟们.

SSI技术

- - 开源软件 - ITeye博客
1.       SSI,通常称为“服务器端包含”技术. 使用了SSI技术的文件默认的后缀名为.shtml,SSI技术通过在html文件中加入SSI指令让web服务器在输出标准HTML代码之前先解释SSI指令,并把解释完后的输出结果和HTML代码一起返回给客户端. 2.       SSI技术的优点:SSI技术是通用技术,它不受限于运行环境,在java、dotnet、CGI、ASP、PHP下都可以使用SSI技术;解释SSI的效率比解释JSP的效率快很多,因为JSP规范提供了太多的功能,这些功能都需要servlet引擎一一进行解释,所以效率比较低.

技术选型

- - 企业架构 - ITeye博客
MVC Framwork: SpringMVC3.0 Restful的风格终于回归了MVC框架的简单本质,对比之下Struts2概念太复杂更新又太懒了. Template:JSP2.0且尽量使用JSP EL而不是taglib,万一要写taglib也用纯JSP来编写,一向是SpringSide的推荐,Freemarker们始终有点小众, 而Thymeleaf与美工配合度非常高,可惜也是太少用户了.

技术 in Netflix

- - 后端技术杂谈 | 飒然Hang
综合市面上的公开资料总结了Netflix在技术上面的一些实践和创新,从中能够得到不少启发和提示.