Dynamo的实现技术和去中心化

AmazonDynamo是一个分布式的key-value系统。最近看了Dynamo的原论文《Dynamo: Amazon's Highly Available Key-value Store》。本文想谈谈它的去中心化。既有阅读相关资料对其实现的理解，也有自己的思考。如有不妥之处，敬请指出。中心节点通常我们看到的分布式存储结构都有一个中心（总控）节点，比如GoogleFileSystem（GFS），包括中心Master和数据节点ChunckServer；另一个例子是HDFS，包括中心NameNode和数据节点DataNode。下面将以这两个为例，说明在设置中心节点时遇到的问题和解决方法。中心节点通常包含存储单元的分布信息和存储内容的元信息。“一致性”是分布式系统的核心内容，在处理一致性问题上，中心节点的引入可以带来很大的好处，但是，也很容易引发问题：单点故障：解决方案问题主要在于热备，比如GFS依赖ShadowMaster。HDFS的情况比较复杂。在Hadoop2.0之前，依赖于SecondaryNameNode，并不是真正的HA（HighAvailability）。它只是分阶段合并edits和fsimage以缩短集群启动时间。那时，它既不能保证立即服务，也不能保证数据完整性；现在HDFS有很多方法来保证NameNode的HA，包括（1）共享镜像或者（2）数据复制的方法，本文对此有系统的介绍。（上图来自《HDFS HA: 高可靠性分布式存储系统解决方案的历史演进》）可扩展性，我们可以这样解决这个问题：中心节点包括两个基本职责，一个是文件系统的维护，它需要知道每个数据节点上哪个空间有什么数据被储存了;另一个是数据请求的调度。这两个是可拆卸的。将单master变成多master，master之间的数据同步可以通过不同的方式实现。这种方式的好处是master的水平扩展变得容易了。问题仍然是一致性。如果不同的master要操作同一个datanode上的同一条数据，就需要有一种特殊的方式来处理冲突。图元文件信息量大的时候会比较麻烦。比如HDFS里面全是小文件，文件数量多，存储效率低（这是HDFS不适合使用的一个例子，我在这篇文章中提到过），NameNode内存消耗大。要么别这么用，GFS更适合存储大文件；或者从存储架构的角度来解决，软件系统常用的方法是引入一个新的层，比如在NameNode和DataNodeLayer之间引入区域自治，该层的每个节点自治管理一部分DataNode,都属于NameNode。有趣的是，整个互联网可以看作是一个庞大的分布式系统。经过实际测试，我们可以认为它确实是去中心化的，但并不是每个维度都“去中心化”。比如域名服务器，***域名服务器是一个中心节点。因此，如果只是为了分布，粗略地去掉中心节点是不明智的。当然，Dynamo已经尝试过了。下面我列出了一些由于移除中心节点而导致的问题及其解决方法。Dynamo的去中心化在上面提到的Dynamo2007论文中，直截了当地强调去中心化是Dynamo设计的一个重要原则：去中心化：对称性的延伸，设计应该倾向于去中心化的点对点技术而不是集中控制。过去，集中控制导致中断，目标是尽可能避免中断。这导致了一个更简单、更具可扩展性和更可用的系统。Dynamo的设计者已经意识到系统的中心化问题，包括服务中断，因此应该尽可能避免。其他设计原则包括：Incrementalscalability，增量扩展，减少对系统的影响；对称，对称，所有节点都相等；Heterogeneity，异质性（我不知道怎么翻译更好），systematicSc??alability可以在不同类型和能力的硬件上以不同的比例实现。下图来自论文，列出了遇到的问题和解决这些问题所用的技术。这是Dynamo的设计核心，大部分问题都与去中心化有关：以下是说明：Partitioning采用一致性哈希（ConsistentHashing）解决节点增加和水平扩展的问题，带来的好处与设计原则中的增量扩展。它本身并不是一个新话题。网上介绍的资料很多，这里就不赘述了。Dynamo的实现有两点需要指出：每个物理设备根据不同的能力转化为不同数量的虚拟节点；每一条数据映射到整个哈希环上的多个节点，形成复制，保证可用性。写高可用使用了向量时钟（VectorClock）来处理一致性问题。vectorclock实际上是一个(node,counter)对的列表，如下图：D1写，发生在节点Sx，形成一个vectorclock[Sx,1]，Sx又被写了，所以counter增加了由1变成[Sx,2]，然后D3和D4在它的基础上写了两次，于是出现了两个版本，([Sx,2],[Sy,1])和([Sx,2],[Sz,1])在D5协调，使得Sy发生在Sz之前，计数器加1。这里有两种协调方式：lastwritewins，取决于节点时钟，但client之间的时钟不能绝对一致决定Handlingtemporaryfailures著名的NWR机制，其中：N代表复制的数据备份数，W代表同步确认成功写操作的副本数（其余N-W个写操作异步执行），R代表副本数同步确认的成功读取操作（每次读取通过比较前序确定有效副本提到的矢量时钟/版本号）。当W+R>N时，可以保证强一致性。对于这个定理，分类例子如下：如果WR，比如W=2，R=1，N=2，两次写入都是同步写入，所以任何读取的数据都是有效的。通过协调N、W、R之间的取值，可以在一致性和可用性之间做出权衡（在CAP理论中，不能牺牲P，但可以权衡C和A），因为W或R是synchronized，所以基本上W或R的值越大，可用性越差。HintedHandoff：提示切换，如果节点A在写操作的过程中暂时不可用，该节点上的副本可以自动交给其他节点，这是为了保证副本总数不减少。并且转发的数据会设置一个提示标记，当节点A恢复时，会再次交还给A。从永久性故障中恢复使用默克尔树的反熵。Merkle就是这样一种数据结构。非叶子节点提供多层哈希的功能：使用反熵协议来帮助副本之间的同步。使用Merkle的主要优点是可以独立检查每个分支，而无需下载整棵树或整个数据集。成员资格和故障检测基于Gossip的成员资格协议和故障检测。Gossip协议本身就是为去中心化而设计的。虽然不能保证某个时刻所有节点的状态一致，但是可以保证在某个最终时刻一致。成员资格协议用于在哈希环上添加或减少节点。关于Dynamo的抱怨对于Dynamo的去中心化来说既有优点也有缺点。毕竟上面介绍的一堆复杂的机制都引入了，尤其是数据的一致性，更是争议不断。使用Master节点失去了中心化，但一致性问题更容易解决，系统也会更简单；退一步说，如果你想去中心化，但是用Paxos这样的协议选举一个“Master”出来，也能更简洁地保证一致性。但是Dynamo***的实现让用户解决冲突（有时用户无法确定使用哪个版本），确实有点别扭；而使用绝对时间来解决冲突的方法是该机制固有的。缺陷（时间不能绝对同步）。网上曾经有一个很火的投诉?，抱怨一些Dynamo的问题。新浪的TimYang写了一篇文章，简单翻译了一下，就不细说了。一般来说，抱怨包括：Dynamo没有办法保证避免脏读；Quorum机制中，只有R+W>N不能保证节点不可用时的强一致性；在跨IDC的情况下，HintedHandoff机制的性能会受到远程传输开销的影响Low；在容灾方面，当某个IDC挂了，丢失了多少数据，谁也说不准；论文中存在一些矛盾，一是对节点peering的描述，二是对最终一致性的描述；Dynamo误导了用户，认为CAP的C和A一直是trade-off。事实上，单个节点中心可以同时实现CA；Dynamo号称是去中心化的，但并未完全实现。例如，交换机故障导致网络碎片时，服务不可用。这篇文章的标题说的是part1，可惜没有出现part2。这篇文章引起了很大的争议。作者后来写了一篇文章《Dynamo – Part I: a followup and re-rebuttals》作为回应。文末总结了自己对Dynamo的看法：尽量避免脏读；不受控制的脏读在任何时候都是不可接受的，即使在发生灾难时——即使数据丢失也比它好得多，在大多数情况下，管理员会关闭部分或所有服务，而不是用丢失或损坏的数据来响应用户在一个数据中心内为了避免网络碎片化，在一个数据中心内考虑P（partitiontolerance）是不合理的；中心化并不意味着低可用性，高可用性服务是可能的，尽管可扩展性可能成为问题；开发设计系统的对称性不能很好地适应硬件和网络的不对称性；数据中心一致性、高可用和可扩展性是可以同时实现的，只要是在一个数据中心（也就是放弃P的时候），BigTable+GFS，HBase+HDFS，甚至OracleRAC都是很好的例子;Dynamo的读写即使在数据中心也会造成脏读；没有人知道哪里避免了脏读的时间边界；跨数据中心正常情况下，没有办法跟踪有多少数据需要更新，而在灾难恢复时，也没有办法知道丢失了多少数据。淘宝日照博客的一篇文章也谈到了Dynamo设计中的一些问题，尤其是关于一致性和分区容忍度的精彩吐槽。推荐阅读。原文链接：http://www.raychase.net/2396