人人网分布式存储研究 陈震解读NoSQL科技代表作《迪纳摩》

类型：电子教程大小：8.5M语言：中文评分：8.3标签:立即下载NoSQL。在过去的一年里，它逐渐成为家喻户晓的名字。我(54chen)自从去年开始研发renren.com NoSQL系统核以来，一直看着NoSQL越来越热，吸引了越来越多人的围观。受InfoQ中文站编辑委托，特写此文。首先，它是对过去一年的总结。其次，希望对NoSQL体系在中国的发展和推广有所贡献。NoSQL背后的两种模式都不是怪物。相反，NoSQL的真正含义应该不仅仅是SQL。其背景是，随着数据量和访问量的不断增加，人工添加机器或把数据划分到不同机器的难度越来越大，人工成本也越来越高。因此，此类项目已经启动。他们的初衷是提高数据存储的自动化程度，减少人为干预的时间，让负载更加均匀。在国际上，真正有代表性的作品是谷歌的BigTable和亚马逊的Dynamo，它们分别使用了不同的基本原理。

MapReduce是最古老的模型，其典型代表是BigTable。地图代表映射，减少代表简化。MapReduce通过将数据集上的大规模操作分布到网络上的每个节点来实现可靠性(MAP)。每个节点定期报告已完成的工作和状态更新。大多数分布式操作可以抽象为MapReduce操作。Map将输入分解为中间键/值对，Reduce将键/值合成为最终输出。这两个功能由程序员提供给系统，底层设施分发Map和Reduce操作在集群上运行。

迪纳摩在这里，我特别把迪纳摩归为一类，因为它和MapReduce有很大的不同，有自己的学校。先说历史吧。亚马逊在2006年推出了自己的云存储服务S3，其CTO在2007年公布了S3的设计方案。从此江湖不再太平，开源项目一个接一个涌现。比较常见的有脸书开发的Cassandra(如果我没记错的话，去年我访问他们的项目网页的时候，上面还说其中一个是迪纳摩的设计师，现在风头正劲，已经撤了)、Linkedin的伏地魔、豆瓣的beansDB、人人网的nuclear等等。这里主要讨论迪纳摩方案的细节。

介绍基础发电机的意思是发电机。顾名思义，这整套解决方案就像一个发电机，持续不间断地提供服务。下面的话看起来有点教条，但基本上如果你想理解原理，你必须什么都知道。

CAP原则始于历史。Inktomi的创始人埃里克布鲁尔教授也是伯克利大学的计算机教授。Inktomi是雅虎的核心支持！的当前平台技术。最重要的是，他们(Inktomi公司)最早开始研究分配计算。CAP的原理可以追溯到2000年(我可以想象当时有多早！)，Brewer教授在一次对话中根据自己管理Inktomi和Berkeley大学的经验总结了CAP原理(文末参考文献中有他讲课资料的链接)。图1是布鲁尔教授过去画的一幅画：

图CAP原则年度PPT

一致性：即数据一致性。简单来说，就是数据复制到N台机器上。如果有更新，N台机器的数据要一起更新。可用性：响应性能好，主要指速度。分区容忍度：这是一个很好的分区方法，体现了一个具体的点，可以简单理解为节点的可扩展性。

定理：任何分布式系统只能同时满足两点，但不能兼顾三点。建议：架构师不应该把精力浪费在如何设计一个能够满足这三个需求的完美分布式系统上，而应该做出权衡。

分布式哈希表是分布式存储寻址方法的总称。就像普通的哈希表一样，它存储的是键和值的对应关系，一般可以根据一个键对应到对应的节点，从而得到对应的值。

这里，一致哈希作为DHT算法中第一个实用的算法，在大多数系统中使用。一致性哈希基本解决了P2P环境下最关键的问题：——如何在动态网络拓扑中分配存储和路由。每个节点只需要维护少量相邻节点的信息，当一个节点加入/退出系统时，只有少量相关节点参与拓扑的维护。至于一致哈希的细节，这里就不赘述了。需要指出的是，在Dynamo的数据分区方法之后，其实是内部一致哈希的一种转换。

进入迪纳摩的世界通过上一章的两个基本介绍，我们开始进入迪纳摩的世界。

Dynamo的数据分区和功能在Dynamo的实现中提到的一个关键点是数据分区。我们假设我们的数据的密钥范围是0到2的64次方(毫无疑问你的数据量会超过它，在正常甚至异常的情况下你都无法超过它，甚至像伏地魔这样的其他Dynamo系统也使用2到32次方)，然后设置一个常数，比如说1000，把我们的密钥范围分成1000份。然后将1000个密钥的范围平均分配给所有节点(s个节点)，使每个节点负责的分区数为1000个/s个分区。

如图2所示，假设我们有三台机器A、B和C，然后我们定义了12个分区。

图2:分成12个区域的三个节点的数据

因为数据在这个环上是均匀分散的(有些人会认为数据的关键是从1、2、3、4 …开始的，其实不是，哈希计算出来的值都是离散的结果)，所以每个分区的数据量大致相等。从图中我们可以看到，每台机器都是将数据分为三个分区，而且由于分区是统一的，当分区数量相当大的时候，数据分布会更加均匀，同时负载也会均匀分离(当然如果你坚持你的负载只集中在一个分区，这里就不讨论这个问题了，可能是你的hash函数有问题)。

为什么要做这个分配？分布式的优点是，当新机器加入时，它只需要替换原来的分区，如图3所示：

图3:添加新的节点D

在图2的相同情况下，12个分区被分成三个ABC节点，并且在图3中输入了一个新的节点D。从图中的重新分配情况可以得出，所有节点只需要将四分之一的数据转移到新节点，同时新节点的负载也随着分区转移而转移(这里12个分区太少，如果有1200个分区甚至12000个分区，这个结论是正确的。

从迪纳摩的NRW看CAP规则，NRW方法首次在迪纳摩系统中提出。n:份数；r:读取数据的最小节点数；w:成功分区的最小数量。这三个数字用于灵活调整Dynamo系统的可用性和一致性。

比如R=1，表示你至少只需要去一个节点读取数据，然后读取完就会返回。此时可用性很高，但不能保证数据一致性。如果W同时为1，那么可用性更新是最高的情况，但不能保证此时的数据一致性，因为在可以复制的N个节点中，只需要写成功一次就可以返回，这意味着是有可能的。如果W=R=N=3，也就是说每次写的时候，都要保证所有要复制的点都写成功，读的时候都读。这样，读取的数据必须是正确的，但其性能会大大降低。也就是说，数据一致性很高，但系统可用性很低。如果R W N能保证我们“读我们写的东西”，Dynamo推荐使用322的组合。

Dynamo系统的数据分区使得整个网络的可扩展性实际上是一个固定值(你划分了多少个分区，其实网络中扩展节点的上限就是这个数)，另外两个方向用NRW实现调整。

一些提高Dynamo可用性的补救措施是针对一些可能经常出现的问题，Dynamo也提供了一些解决方案。

第一种是添加提示切换数据：当一个节点暂时出现故障时，数据会自动进入列表中下一个节点进行写入操作，并被标记为切换数据，收到通知后需要恢复原节点时，数据会被再次推回。这样可以大大提高系统的写作成功率。

第二个是版本控制的向量时钟：用一个向量(例如，[a，1]表示这个数据是在节点A第一次写入的)来标记数据的版本，这样当出现版本冲突时，就可以追溯到问题发生的地方。这使得数据最终保持一致成为可能。(卡珊德拉没有使用矢量时钟，只是客户端时间戳也达到了同样的效果。)

第三种是Merkle树，在数据发生变化时加快搜索速度：Merkle树用于索引数据，任何数据变化都会快速反馈。

第四种是Gossip协议：一种通信协议，旨在使节点之间进行通信，省略中心节点的存在，使网络分散。提高系统的可用性。

Postscript Dynamo的理论使得CAP原理中的可扩展性易于实现，并通过创造性的NRW平衡了系统的可用性和一致性，为系统在实际情况下遇到问题增加了选择。同样，在NoSQL的道路上，这只是一个开始，而在分布式计算的道路上，这是继MapReduce之后的一场革命。