分布式算法与云平台研究

摘  要：云计算是一种基于互联网的计算方式。它通过互联网上异构、自治的服务为个人和企业用户提供按需即取的计算。云计算平台，是指平台通过一套软件系统把分布式部署的资源集中调度使用。本文针对亚马逊的Dynamo，以及谷歌的GFS、BigTable和MapReduce，这四个典型的云计算平台进行项目研究，对其设计思想和实现的关键算法原理进行了阐述。并基于此，提出了对未来云计算技术和云平台的进一步发展的展望。

关键词：云计算;分布式算法;云平台

中图分类号：TP393.09;TP301.6      文献标识码：A 文章编号：2096-4706（2019）08-0096-03

Abstract：Cloud computing is an internet-based computing method. It provides on-demand computing for individual and enterprise users through heterogeneous and autonomous services on the internet. Cloud computing platform refers to the centralized scheduling of distributed deployed resources through a software system. This paper focuses on the project research of Amazon’s Dynamo，Google’s GFS，BigTable and MapReduce，which are four typical cloud computing platforms，and elaborates on their design ideas and key algorithmic principles. Based on this，the future development prospects of cloud computing technology and cloud platform are put forward.

Keywords：cloud computing;distributed algorithms;cloud platform

0  引  言

云计算是一种基于互联网的计算方式。它可以为个人和企业用户提供按需即取的计算，并天然带有异构、自治的性质。它的特点有：超大规模、虚拟化、按需服务、可伸缩性、服务可度量。它对整个IT产业带来非常深远的影响，其中包括软件开发商、服务器供应商和云终端供应商这三个云计算建设者和作为云计算运维者的云供应商。

当前世界的云计算规模在不断扩大，在未来几年，全球云计算服务市场仍有较大概率保持在15%左右的增长率平稳增长。中国互联网公司三巨头（BAT）、华为等中国企业将持续发力云的基础设施建设和相关技术的迭代更新。根据公开资料显示的趋势来看，预计到2020年，云服务市场规模将达到4114亿美元。

尽管如此，这种方兴未艾的计算模型在技术上仍然需要面对诸多挑战。如：用户隐私安全、云服务标准缺失，等等。在云计算充满机遇和挑战的今天，我们有必要去探讨和回顾一些较为成功的、影响力较大的几个云计算平台的设计模式，并从中汲取养分。

1  亚马逊的Dynamo及其算法原理

Dynamo是Amazon的Key-Value模式的存储平台。它是一个具有键值结构的分布式存储系统，至今已有诸多应用。Dynamo使用了分布式哈希表（DHT），这可以让数据在环中均匀存储，并保证各节点相互独立，不需要主节点进行统一的调控，从而令发生单节点故障的风险大大地降低。

Amazon大量的用户服务数据被存储在Dynamo中。可以说它为Amazon的电子商务平台及其云计算服务提供了最基础的支持。

Dynamo中应用了诸多算法去解决数据存储和处理的各种难题，这些算法很多都是分布式算法中的经典。下面是其使用的最主要的一些算法，以及对应解决的问题。

（1）改进的一致性哈希算法=>数据均衡分布。

（2）参数可调的弱quorum机制=>数据备份。

（3）向量时钟=>数据冲突处理。

（4）Gossip=>成员资格及错误检测。

（5）Hinted Handoff（数据回传机制）=>临时故障处理。

（6）Merkle哈希树=>永久故障处理。

本文对其中的一些算法和模型的主要思想进行介绍，这里将忽略算法细节。

1.1  使用改进的一致性哈希算法解决Dynamo中的数据均衡分布问题

哈希函数经常用于常数时间的数据查找。通常意义上看，哈希查找有以下两个主要的步骤。

（1）使用哈希函数将想要查找的键映射成数组或物理存储地址的索引。这么做的意义在于，我们在查找某个键时，可以使用同一个哈希函数将其迅速映射到它的存储位置，从而实现常数时间的查找。

（2）处理哈希碰撞冲突。由于第一个步骤中的映射方式可能导致不同数据映射到同一个地址，我们需要处理这种“哈希碰撞冲突”。实际应用中常见的方法有拉链法、线性探测法等等。

哈希函数的确可以做到数据的快速查找，但这对于一个合格的云平台却远远不够。在新增存储机器的情况下，由于物理地址索引范围的变化，哈希函数必须重新调整，这使得我们必须迅速将所有数据按照新的哈希函数重新计算并存储。

为了解决这个问题，一致性哈希算法引入了环的概念。我们将存储数据的机器抽象为一个个node，切分成的数据块称为block。一致性哈希算法中的哈希值的范围是一定的，将这个范围抽象成一个环，每个node并不是对应一个确定的哈希值，而是一个哈希值范围。当前node的哈希值范围就是它的哈希值和在环上的前一个节点的哈希值。只要block的哈希值落在了这个范围内，它就将被存储在这个node上。换句话说，block要存储在它的哈希值顺时针绕环遇见的第一个node上。一致性哈希算法在減少或者添加node时，可以尽可能地保证数据的较少迁移。数据只有一个备份的时候是危险的。因此，Dynamo对一致性哈希算法的进一步改进是：它放在环上作为一个node的是多台机器，这一组机器通过Dynamo独特的数据同步机制来保证数据的一致性。这就通过增加数据的备份更大地保证了数据安全。我们在下面的文字中介绍属于一个node的机器之间所使用的数据同步机制。

1.2  （N，R，W）模型解决Dynamo中的数据备份及一致性问题

Dynamo使用的方法是（N，R，W）模型。这个模型解决了同一个node内的不同机器上数据的不一致可能造成的读写问题。它让用户确定云平台以何种方式去存储、读和写数据。用户可以根据自己的需求，通过设定参数，在较高的读写性能与数据的高一致性之间进行取舍。

（N，R，W）模型需要客户端设定三个参数，即N、R、W。云平台将按照这三个参数来调整数据的读写操作。N表示数据复制的次数，当N越大时，用户的数据备份就越多;R表示读数据时候所需要参与的最小节点数，当R越大时，用户读取数据时需要参与的机器数就越多;W表示数据写成功所需要的最小分区数，当W越大时，用户写入数据时需要参与的机器数越多。因此，当我们将这三个参数都设置成很大的数字时，显然，系统的可用性就会减弱，但数据一致性会增强;当三者都很小时，就不能保证数据的安全备份。一般情况下，需要让“R+W>N”，这是为了保证用户读取的数据中至少有一份是正确的。

Dynamo使用（N，R，W）模型灵活地调整用户对数据的可用性与一致性的要求。而Dynamo的扩展性是其数据分区数所决定的，它通常是已经被设定好的。

1.3  使用Merkle Tree解决Dynamo中的数据恢复问题

以上两个算法基本解决了Dynamo平台的数据均衡存储和数据安全备份的问题。尽管（N，R，W）模型可以保证在正确设置了参数的情况下，我们拿到的数据至少有一份是正确的，但这并不意味着我们对错误的数据不进行修正和恢复。因此，我们现在考虑的是假如发生了两台机器的数据不一致，Dynamo如何根据其中存储正确数据的一台机器来对另一台机器中的数据进行恢复。

如果在數据错误发生时针对所有数据进行恢复，因为需要更新一台机器上的所有数据，必然导致大量且慢速的数据操作。Dynamo的做法是将每台机器针对数据块建立一棵Merkle Tree。

Merkle Tree又叫Hash Tree，它把一台机器上的数据块细分成几个更小的数据区块，每个数据区块计算出一个hash值，作为整棵树的叶子节点，被一层层合并计算上去，最终得到root节点的hash值。当数据发生错误时，我们只需要从root开始比较两棵Merkle Tree的hash值，就可以在对数时间内快速找到哪一段或几段数据中的hash值变化了。之后只要针对找出错误的数据区块进行更新就可以实现整台错误机器上的数据恢复了。这大大降低了数据恢复的代价。

1.4  使用Gossip Protocol解决Dynamo中的分布式的消息传播问题

Gossip Protocol也叫Epidemic Protocol（流行病协议），也叫“流言算法”“疫情传播算法”等。它解决的是在分布式集群中的消息传播问题。举个例子，假定三台机器存储的是相同的数据，现在我们将数据的一部分进行修改，在没有中心服务器的情况下，这条修改消息如何传递给另外的两台机器，就需要一种算法或协议进行确定。Gossip Protocol被实际应用在了Dynamo的成员资格及错误检测中。

Gossip过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机地选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

本文使用Java语言模拟了Gossip协议下的消息传播过程，链接地址如下：https：//gitee.com/willfree/antiEntropy_Gossip/blob/master/gossip.java。

2  谷歌的“三驾马车”和它们的设计思想

谷歌的腾飞不仅仅因为它的搜索引擎，事实上也不仅仅因为接下来要介绍的“三驾马车”，但它在云计算上的“三驾马车”确实功勋卓著。它们是：GFS、MapReduce、BigTable。

GFS，谷歌文件系统，是一个可扩展的大型数据密集型应用的分布式文件系统。它具有很强的数据容错能力，可以提供极高的计算性能，更令人兴奋的是，由于可以被部署在相对廉价的机器上，其硬件投资和运营成本变得很低。GFS的架构由一台Master服务器和许多台文件服务器（chunk server）构成，并且有若干客户端（client）与之交互。它采用中心服务器模式。

MapReduce是一个超大集群的简单数据处理系统。Map函数是将输入参数映射到Worker;Reduce函数是将Worker归约，成为输出参数。其主要思想来源于函数式编程和分治思想。它将所有服务器中的处理器有效地利用起来计算保存在GFS中的海量数据并得到想要的结果。基于MapReduce编写的程序可以在相当多的普通PC机上被并行执行，这是MapReduce的最大魅力所在。

BigTable是一个结构化数据的分布式存储系统。它在其他的几个Google基础构件提供的服务之上被构建。例如：它实际使用了GFS来存储它的日志文件和数据文件。BigTable不仅仅带有分布式的特点，在GFS的基础上，正如其名称所讲，它实际对结构化数据进行了高效的存储和处理。它一般运行在一个共享的机器池中，这些机器会同时运行着其他的分布式应用程序，这种共享机器的状态也是BigTable的一大特色。BigTable有着自己的集群管理系统，用以监视集群中各个机器的状态、处理机器的故障、调度任务和管理资源。

谷歌的“三驾马车”直接为谷歌的一些应用提供了基础的分布式数据存储和处理服务。它们并非完全独立，比如MapReduce和BigTable都调用了GFS所提供的大量数据存储服务。此外，他们也并非仅仅是平台或系统的名称，MapReduce也代指了它所使用的云编程模式。它们不仅仅启发和推动了Hadoop的建立和崛起，也对后Hadoop时代的新“三驾马车”——Caffeine、Pregel、Dremel，有着深远的影响。

3  基于云计算技术的未来展望

云计算在不远的曾经是计算机学界一个火爆的名词，即使在现在，它的基础算法、技术和平台也在推陈出新。这很大程度上源自人们对于云计算发展到极致的美好时代的遐想。

通过以上对四个典型云平台的介绍，我们对云计算技术和它的一些基础算法有了一定的了解。基于此，本文对未来云技术的发展和应用场景作了一些展望。

在未来，在解决了云计算技术上的诸多痛点，出现了高质量、统一标准的云服务之后，将会出现这样一种美好的生活图景：算力和数据存储空间就像生活中的水和电一样，只需要按规定付费，打开“开关”就能随时随地方便的被使用。人们只需要一个支持高分辨率显示屏渲染的GPU，以及显示屏、音响设备等简单的I/O设备共同组成的“电脑”，就可以通过超高带宽的网络连接进行学习、办公等所有操作。不仅如此，除非地球爆炸这样大的灾难，人们几乎不用担心数据的丢失或者错误，因为云平台已经帮他们备份了足够多的数据，并通过一致性算法、同步算法来保证他们宝贵数据的绝对正确。

参考文献：

[1] Decandia G，Hastorun D，Jampani M，et al. Dynamo：amazon’s highly available key-value store [J]. ACM SIGOPS Operating Systems Review，2007，41（6）：205-220.

[2] Ghemawat S ，Gobioff H ，Leung S T. [ACM Press the nineteenth ACM symposium - Bolton Landing，NY，USA （2003，10，19-2003，10，22）] Proceedings of the nineteenth ACM symposium on Operating systems principles，- SOSP ＼"03 - The Google file system [C].// ACM，2003：29-43.

[3] Dean J ，Ghemawat S. MapReduce：Simplified Data Processing on Large Clusters [C].// Proceedings of Sixth Symposium on Operating System Design and Implementation （OSD2004），USENIX Association，2004.

[4] Chang F，Dean J，Ghemawat S，et al. Bigtable：A Distributed Storage System for Structured Data [J].ACM Transactions on Computer Systems，2008，26（2）：1-26.

作者簡介：王锋（1998.09-），男，汉族，河南濮阳人，本科在读，主要研究方向：云计算、数据挖掘、计算机视觉。