互联网海量数据存储及处理的调研综述

互联网海量数据存储及处理调研综述摘要本文主要针对互联网应用中出现的新兴的海量数据存储和处理系统展开讨论，对比新兴 系统与传统数据技术的差异，以及这些系统之间实现技术的不同特点，并总结出相应的关键 技术问题。近些年来，blog、wiki spaces的兴起导致互联网内容的提供方式出现转变；用户创造 内容的web2.0时代的到来，带动着视频应用、网络游戏、搜索引擎等互联网衍生业务迅速 发展。互联网正处于一个信息爆炸的时代。面对信息爆炸的互联网，如何去存储和处理这些 海量数据，对诸如Facebook、YouTube等大规模互联网企业提出了巨大的技术挑战，同时也 开启了开阔的研究空间。本文将综述互联网数据存储以及处理技术的发展、研究状况，指出 这方面研究的技术挑战和研究问题。互联网应用种类繁多，包括Facebook、MySpace为代表的社会关系网络、Flickr为代表 的图片共享应用、Youtube为代表的视频共享应用以及以Google、Yahoo为代表的搜索引擎 应用等。这些互联网应用因为自己的应用特性不同，面对不断增长的互联网用户带来的不断 增长的数据（视频、图片、blog等）所采用的技术路线不尽相似。但是，这些技术路线从本质 上可以分为两个方面：海量数据的存储管理技术以及针对海量数据的处理技术（日志分析、 搜索引擎应用等）。本文剩下的部分主要从这三个部分展开论述。第1部分介绍互联网应用的特点，阐述海 量数据带来的新特性；第2部分主要分析传统数据库在互联网应用中的局限性，并对比新兴 系统与传统数据库系统的差异，讨论海量数据管理的关键技术；第3部分则介绍一些用于海 量数据处理的系统，讨论它们的技术特点；最后，总结全文。1.背景随着互联网的快速发展，Blog、RSS、视频共享、图片共享等Web2.0应用的不断加入 使得海量数据存储、管理和处理已经成为当今互联网公司面临的严峻问题。以c2c网站淘宝 为例，2007年度淘宝的注册用户已经超过了 4500万，商品总数也多达9000万，每天的页 面点击率可达2亿多次；并且每天都有大量新用户注册，交易也在无时无刻进行甲卓这些 信息保存在存储设备上，便是高速膨胀的海量数据。同样的问题也出现在Google、Facebook、 Flickr等互联网应用上，如表1所示。应用类型应用名称规模搜索引擎Google总量：10KB / doc * 20B docs = 200TB每 30 天做一次索引：200TB / 30 days = 6TB / daySNSFacebook（2008）Page View： 0.5KB / page view events * 3B page view events / day = 1.5TB / dayRelationship： 100M users * 5 events * 100 feed/event * 0.1KB/feed = 5TB / day图片共享Facebook（2007）65亿张原始图片，每张图片保存为45个不同尺寸 图片总量达300亿张，共540TB请求数：47.5万张/秒（读）1亿张/周（上传）Flickr（2007）原始图片存储总量达2PB请求数：40亿张/天（读）40万张/天（上传）视频共享Youtube（2007）视频总量达600万个，共45TB观看率超过一亿次/天，上传率达65000次/天电子商务淘宝（2007）4500万注册用户，9000万件商品，2亿次/天页面点击率eBay（2007）2.12亿注册用户，10亿张图片，1.05亿张商品列表，2PB数据 页面点击率10亿次/天，并且从1999年至2006年页面点击率增 长因子为35表1不同互联网应用的规模A1，39, 40, 41, 42这些互联网应用由于不同的应用特性在用户规模、存储数据规模等方面表现不尽相同。 但是，从表1中我们依然可以看到这些互联网应用在面对海量数据时的一些共性，归纳如下：1）用户群体大，增长速度快。以电子商务领域为例，淘宝和eBay在2007年度的注册用户数量分别达到了 4500万和 2.12亿，并且用户数量在不断增长。在过去将近10年内，eBay的页面点击率增长到日均10 亿次，并且增长因子为35。虽然页面点击量不能直接等同于用户数，但是高页面点击率以 及增长率也从一定程度反应了该应用的用户群体规模和增长规模。同样，拥有上亿次上十亿 次日均页面点击率的图片视频共享、SNS等互联网应用，也具有上述特点。2）数据总量大，增长速度快。不论是存储大量静态数据的图片视频共享服务，还是存在大量用户交互消息的SNS、 电子商务服务，它们存储的数据总量均达到TB级别甚至PB级别。同时，每天40万张图片 （Flickr）、每天6万个视频（Youtube）的上载速率使得这些数据总量变得越来越大。3）数据类型多样，大小不一。在Web2.0时代，互联网应用需要处理大量用户创作或者分享的数据，比如图片、视频、 Blog日志等；同时还需要处理一些用户交互的信息，比如邮件、消息、点击事件等。这些 数据类型多样，并且大小也不尽相同。如图1所示，2007年末互联网络中的视频平均长度 为192.6秒。视频比特率从2005年的200kbit/s增长到2007年的328kbit/s。因此，2007年 末，互联网视频的平均尺寸为63M38。而相对于视频而言，图片的平均大小为几百K而已； 那些记录用户交互信息的数据则更小。数据类型多样，大小不一的特性对于海量数据存储、 管理提出了严峻的考验。4）数据操作模式较为固定，一致性要求较弱。在互联网应用，虽然数据类型多样，大小不一，但是对于数据的操作模式相对固定。对 数据的操作，主要包括增加、删除、修改、查询这四类。其中，删除和修改操作在互联网应 用中并不频繁，基本上可以忽略。而查询和增加是互联网应用中最频繁的两种操作，据统计 这两类操作的比例大概在80： 20（或者90： 10）左右35。与金融行业的数据操作不同的是， 互联网应用的数据操作没有很强的事务特性，也没有严格的一致性要求，但对读写时延的有定要求（读写时延影响互联网应用的用户体验）。图 1 Growth in Duration of Web Videos38】互联网应用的海量数据特性，对数据存储和处理提出了新的挑战。这些挑战概括如下：1）TB级甚至PB级的存储系统，以适应海量数据的需求。2）良好的扩展性。在不中断服务的情况下，通过简单添置机器或者磁盘存储来扩展系 统，满足不断增长的数据和用户群体需求。3）低时延、高吞吐的存储系统性能。4）丰富的存储类型，以满足互联网应用中结构化、半结构化甚至非结构化数据的存储 需求。5）灵活简单的并行编程模型进行海量数据处理，隐藏分布式环境下数据分布、容错等 复杂性。在这样的挑战下，一些传统技术已经开始不能胜任互联网应用的需求。新兴的海量数据 存储、处理系统也相继涌现。在接下来的两个部分，文章将从数据存储和数据处理两个角度， 讨论传统技术存在的问题，介绍一些新型系统，并分析这些新型系统在解决海量数据存储和 处理时遇到的问题以及相应的解决方案。2. 数据存储目前，大部分互联网应用仍然使用传统关系型数据库进行数据的存储管理，并通过编写 SQL语句或者MPI程序来完成对数据的分析处理。这样的系统在用户规模、数据规模都相 对比较小的情况下，可以高效地运行。但是，随着用户数量、存储管理的数据量不断增加， 许多热门的互联网应用在扩展存储系统以应对更大规模的数据量和满足更高的访问量时都 遇到了 问题四，24, 26, 27, 28, 29, 36。2.1 .传统关系型数据库传统关系型数据库在数据存储管理的发展史上是一个重要的里程碑。在互联网时代以前， 数据的存储管理应用主要集中在金融、证券等商务领域中。这类应用主要面向结构化数据，聚焦 于便捷的数据查询分析能力、严格的事务处理能力、多用户并发访问能力以及数据安全性的保证。 而传统关系型数据库正是针对这种需求而设计，并以其结构化的数据组织形式，严格的一致性模 型，简单便捷的查询语言，强大的数据分析能力以及较高的程序与数据独立性等优点被广泛应用。然而互联网时代的到来，数据已超出关系型数据库的管理范畴，电子邮件、超文本、 Blog、Tag以及图片、音视频等各种非结构化数据逐渐成为了海量数据的重要组成部分。面 向结构化数据存储的关系型数据库已经不能满足互联网数据快速访问、大规模数据分析的需 求。应用场景的局限性传统数据库在设计上，着眼于面向结构化的数据，致力于事务处理，要求保证严格的一 致性，这些特性符合传统的金融、经济等应用场景。然而互联网应用主要面向于半结构化、 非结构化的数据，这些应用大多没有事务特性，也不需要很严格的一致性保证。虽然传统数 据库的厂商也针对海量数据应用特点提出了一系列改进方案，但是由于并不是从互联网应用 的角度去寻找问题，使得传统数据库在应对互联网海量数据存储上效果并不理想。 关系模型束缚对海量数据的快速访问能力关系模型是一种按内容访问的模型。即在传统的关系型数据库中，根据列的值来定位 相应的行。这种访问模型，将在数据访问过程中引入耗时的IO,从而影响快速访问的能力。 虽然，传统的数据库系统可以通过分区的技术（水平分区和垂直分区），来减少查询过程中 数据IO的次数以缩减响应时间，提高数据处理能力；但是在海量数据的规模下，这种分区 所带来的性能改善并不显著。关系模型中规格化的范式设计与web2.0的很多特性相互矛盾26。以Tag为例，Tag的 分类模型是一种复杂的多对多关系模型。传统数据库的范式设计要求消除冗余性，因此Tag 和内容将会被存储在不同的表中，导致对于Tag的操作需要跨表完成（在分区的情况下，可 能需要跨磁盘、跨机器操作），性能低下。缺乏对非结构化数据的处理能力传统的关系型数据库对数据的处理只局限于某些数据类型，比如数字、字符、字符串等， 对非结构化数据（图片、音频等）的支持较差。然而随着用户应用需求的提高、硬件技术的 发展和互联网上多媒体交流方式的推广，用户对多媒体处理的要求从简单的存储上升为识 别、检索和深入加工，因此如何处理庞大的声音、图像、和视频、E-mail等复杂数据类型， 是传统数据库面临的一个问题。扩展性差在海量规模下，传统数据库面临着一个致命问题，就是其扩展性问题。解决数据库扩展 性问题，通常有两种方式：Scale up和Scale out。这两种扩展方式分别从两个不同的维度来 解决数据库在海量数据下的压力问题。Scale up，简而言之就是通过硬件升级，提升速度来 解决缓解压力问题；而Scale out则是通过将海量数据按照一定的规则进行划分，将原来集 中存储的数据分散到不同的物理数据库服务器上。Sharding3正是在Scale out的理念指导下， 传统数据库提出了一种解决扩展性的方案。Sharding通过叠加相对廉价设备的方式实现存储 和计算能力的扩展，其主要目的是为突破单节点数据库服务器的I/O能力限制，提高快速 访问能力，以及提供更大的读写带宽。但是，在互联网的应用场景下，这种解决扩展性的方 案仍然存在着一定局限性制。比如，数据存储在多个节点，需要考虑负载均衡的问题，这需 要互联应用需要实现复杂的负载自动平衡机制，引入较高代价；数据库严格的范式规定，使 得表示成关系模型的数据很难进行划分到不同的shard中；同时，还存在一些数据可靠性和 可用性的问题。2.2. 新兴数据存储系统在传统关系型数据库已不能满足互联网应用需求的情况下，开始出现一些针对结构化、 半结构化甚至非结构化数据的管理系统。在这些系统中，数据通常采用多副本的方式进行存 储，保证系统的可用性和并发性；采用较弱的一致性模型（如最终一致性模型），在保证低 延时的用户相应的同时，维持复本之间的一致状态；并且都提供良好的负载平衡策略和容错 手段。按照数据管理方式划分，这些新兴的数据管理系统可以归为两大类：（一）集中式数据管理系统这类系统采用传统的server farm架构。整个系统需要一个主控节点维护各从节点的元信 息，是一种集中控制的管理手段。其优势在于，集中管理的方式人为可控且维护方便，在处 理数据同步时更为简单。其劣势在于，系统存在单点故障的危险。这类系统包括Google的 Bigtable 和 Yahoo！的 Pnuts。 BigtableBigtable是Google开发的一套结构化存储系统。数据以多维顺序表的方式进行存储。 整个系统采用传统的server farm形式，由一个主控服务器和多个子表服务器构成，并使用 分布式锁服务Chubby进行容错等管理。 PnutsPnuts是Yahoo内部使用的，用于跨数据中心进行部署的大规模并行数据管理系统回。 它与bigtable类似的集中管理体系。它支持顺序表和哈希表两种方式进行结构化数据的组织 存储，并通过一定的优化手段在保证用户低延时访问服务的同时，提高数据批量载入的性能 7。（二）非集中式数据管理系统系统中各节点无主从之分，各节点通过相应的通信机制相互感知，自我管理性较强。其 优势在于：由于没有主控节点，因而避免单点失效带来的危险；不需要过多人工干预。其劣 势在于：由于无主控节点因而对于一些元数据更新操作，实现较为复杂；不易进行人工控制。 Amazon的Dynamo和Facebook的Cassandra则采用这种方式。 DynamoDynamo是一个基于分布式哈希的去中心化的大规模数据管理系统4。在Dynamo中， 数据按照key-value进行形式，主要面向原始数据的存储。这种架构下，系统中每个节点都 能相互感知，自我管理性能较强，没有单点失效。 CassandraCassandra是Facebook开发的一套采用P2P技术实现的结构化数据存储系统25。与 Dynamo有所不同的是，Cassandra采用类似Bigtable的多维表数据模型进行数据的存储管理。在下面的章节，我们将探讨互联网背景下海量存储的关键技术问题，并对比这些系统在 解决这些问题上所采用的技术手段。2.3.关键技术分析扩展性是互联网应用需求下海量数据存储的首要问题。构建一个TB级甚至PB级的数 据存储系统，需要有自适应的数据划分方式、良好的负载均衡策略来满足数据、用户规模的 不断增长需求。同时，在保证系统可靠性的同时，需要权衡数据一致性与数据可用性，来满 足互联网应用低延时、高吞吐率的特点。在这一节中，我们主要从数据划分、数据一致性与 可用性、负载均衡、容错机制等四个主要方面来讨论构建一个高可靠、可扩展的海量数据存 储系统的关键问题和技术。2.3.1.数据划分在分布式环境下，数据存储需要跨越多个存储单元。如何进行数据的划分是影响扩展性， 负载平衡，以及系统性能的关键问题。为了提供低延时的系统响应，抑制系统性能的瓶颈， 系统必须在用户请求到来时将请求进行合理分发。现有的海量数据管理系统主要采用哈希映 射和顺序分裂这两种方式。在互联网应用中，数据通常以key-value方式进行组织以适应数 据的多样性和处理的灵活性。哈希映射是根据数据记录的key值进行哈希，根据哈希值将记 录映射到相应的存储单元。但是这种数据划分方式带来的性能收益依赖于哈希算法的优劣。 而顺序分裂则是一种渐进式的数据划分方式。数据按key排序写入数据表中，数据表在其大 小达到阈值后进行分裂，分裂后的数据将被分配到不同的节点上去提供服务。这样，新流入 的数据根据key找到相应的分片插入表中。Dynamo和Cassandra都采用了一致性哈希的方式进行数据划分。这种方式在数据流入 时就将数据均匀地映射到相应的存储单元，因而最大限度地避免系统的热点存在。同时一致 性哈希算法，也为系统带来了良好的扩展性。而Bigtable则使用顺序分裂的方式进行数据划分。这种渐进式的数据划分方式，可以有 效利用系统资源，并能提供很好的扩展性。但是对于某个key值范围的频繁插入可能造成负 载热点存在。与哈希方式不同的是，顺序分裂的数据与存储节点并未存在直接映射的关系， 在Bigtable中需要有一个主控节点来集中管理这种分裂和映射行为。因此，整个系统的扩展 性最终受限于主控节点的管理能力。虽然PNUTS提供了顺序表和哈希表两种数据的组织形式，但是其哈希表中的数据按照 key的哈希值有序存放。这样，PNUTS采用了顺序分裂的方式来按照Key或者Key哈希值 来划分顺序表或者哈希表中的数据。2.3.2. 数据一致性与可用性数据可用性是分布式环境下数据存储的基石;而数据一致性模型则保证数据操作的正确 性。在分布式环境下，通常采用副本冗余、日志等方式来解决数据的可用性问题；但是副本 冗余存储也带来了数据一致性的问题。在采用副本冗余方式的分布式系统中，数据一致性与 系统性能是一对不可调和的矛盾：需要牺牲系统的性能来保证数据的严格一致性，或者牺牲 一致性来保证系统的性能（响应时间等）。在互联网应用中，通常采用第二种手段来调和这 种矛盾，即允许系统通过弱化一致性模型来保证高效的系统响应，同时通过异步复制的手段 来保证数据的可用性。Dynamo，Bigtable，Pnuts都是通过副本冗余的方式来保证数据的高可用。但是，其具 体实现又不尽相同。由于Dynamo采用非集中的管理方式，整个系统中无主从节点之分， Dynamo在整个哈希环上通过gossip机制进行通讯，完成副本的异步复制。而采用集中管理 方式的Bigtable和Pnuts均采用日志的方式保证服务节点内存中数据的可用性。不同的是， 在数据存储可用性方面，BigTable依赖于底层分布式文件系统的副本机制；而Pnuts则采用 基于pub/sub通讯机制的主从式异步复制的方式来完成数据的冗余存储：数据首先被同步到 主副本，然后通过pub/sub机制异步更新到所有副本。2.3.3. 负载平衡负载均衡是分布式环境下进行高效数据管理的关键问题。它主要包括数据的均衡和访问 压力的均衡这两个方面。在分布式环境中，数据通过一定的划分策略（哈希或者顺序分裂等） 进行划分并存储在不同的节点上，用户的访问请求也将由不同的节点处理。由于用户访问请 求的分布规律不可预测性导致最终数据存储分布的不均衡，以及节点访问压力的不均衡。在 数据分布、访问负载不均衡的情况下，频繁的并发访问和持续的数据加载压力将会影响整个 系统的性能。为了保证数据加载的高吞吐率、系统响应的低延时以及系统的稳定性，海量存 储系统需要有一套良好的均衡机制来解决上述问题。Dynamo采用了虚拟节点技术，通过虚拟化的手段将节点的服务能力单元化，将访问压 力较大的虚拟节点映射到服务能力较强的物理节点，达到访问压力的均衡。访问压力的均衡 伴同时伴随着数据的均衡。为了使数据均衡过程中，数据迁移的开销尽可能小，Dynamo采 用同样的虚拟化技术，量化节点的存储能力，将虚拟后的存储节点相对均匀地分散到集群哈 希环上，避免数据均衡过程中全环的数据移动。在非集中式系统中，这些均衡操作可以由任 一节点发起，通过gossip通讯机制与集群中的其他节点协调完成。与Dynamo这种非集中式管理不同的是，BigTable通过master来监控各个tablet server 上的访问负载状态，利用master调度管理tablet的分裂和迁移将访问压力均匀地分散到各个 tablet server上。由于BigTable采用分布式文件系统作为数据的底层存储，tablet的分裂和迁 移过程中并不涉及到存储数据的迁移操作，以一种巧妙的方式避免了数据均衡的问题。在集 中式管理系统中，PNUTS也采用类似的方式进行访问压力的均衡。不同的是，采用本地文 件系统或者本地数据库系统的PNUTS在进行tablet的分裂和迁移时，需要进行存储数据迁 移。有效的数据划分方式为系统扩展性提供了一个基础，但是同时也给系统带来了负载均衡 的问题。通过虚拟化节点或者表分裂等方式改变数据分布格局，均衡访问负载的同时，尽可 能减少存储数据迁移量或者避免数据迁移，是海量存储系统的一个挑战。2.3.4. 容错容错是分布式系统健壮性的标志。节点的失效侦测以及失效恢复已经成为保证系统的可 用性、可靠性的关键问题。1）失效侦测在非集中式系统中，各节点之间定期进行交互以了解节点的活动状态，从而侦测失效的 存在，如Dynamo、Cassandra。而在集中式系统中，整个系统需要有专门的部件（节点）来 维护整个分布式系统中节点的状态信息，并通过Heartbeat机制完成失效节点的侦测。如 Bigtable通过分布式锁服务chubby来跟踪master和tablet节点的服务状态，来完成节点的失 效侦测；Pnuts则利用tablle controler部件维护的活动节点路由信息来判断节点失效的存在。2）失效恢复在系统侦测到失效节点的存在后，需要一定的恢复策略来完成对失效节点的恢复，保证 系统的可用性和可靠性。在分布式系统中，节点的失效分为临时失效（如网络分区等）和永 久失效（如节点宕机、磁盘损坏等）两种情况。在副本冗余存储的分布式系统中，失效通常 会造成了多副本之间的数据不一致，这时候需要对失效节点的数据进行同步来完成失效的恢 复。同时，永久失效通常会造成失效节点内存中数据的丢失，日志重做通常是解决这类问题 的一种办法。当然，具体的失效恢复策略在不同的系统中又各有特色。以BigTable为例。临时失效和永久失效在BigTable中并不做区分。BigTable依靠主控 节点通过Heartbeat机制来侦测失效的存在，即在规定的时间内主控节点通过Heartbeat无法 获取从节点的状态信息，主控节点将认为从节点已经永久失效。这时候，主控节点将失效节 点上服务的tablet重新分配到集群中的其他从节点上去提供服务，并通过重做失效节点的日 志来完成失效节点的内存数据恢复。即使临时失效的节点可能再次与主控节点建立连接，这 些节点也将被主控节点停止，因为这些节点上的服务已经被重新分配到其他节点上。这种依 赖于底层分布式文件系统的共享存储方式，简化了系统的失效恢复。在集中式系统中，主从节点的功能差异使得主节点失效恢复的方式不尽相同。由于主节 点维护系统元信息，那么主节点的失效将是灾难性的。针对集中式系统，通常采用备份节点 （双机、多机备份）来防止主节点失效的发生。Bigtable通过chubby来管理集群节点的状 态信息，利用tablet server来管理整个系统的存储元信息，来弱化主节点的管理功能，减小 主节点失效导致灾难的可能性，同时也降低了主节点恢复的复杂性。而在以Dynamo为代表的非集中数据存储系统中，临时失效和永久失效被区别对待。在 临时失效发生时，Dynamo将会把数据暂时放置在临时节点，待节点从临时失效中恢复过来 后，数据将归还给目标节点。对于永久失效带来的数据不一致，Dynamo通过对失效节点的 数据进行同步来完成失效恢复。在Dynamo中，这种同步通过对比节点间的Merkle tree来完成。2.4 .总结这些新兴系统通过不同的技术都为用户呈现了一个扩展性良好，且高度可用的大规模数 据管理系统。但是，不同的系统都具有各自不同的特性，也采用了不同的技术方案来解决大 规模数据存储的关键问题：数据划分、负载均衡和容错。这些差异归纳如表2所示。DynamoBigtableCassandraPnuts一致性模型最终一致性较弱一致性最终一致性Record-level timeline 一致性数据管理方式非集中化集中式。非集中化集中式数据模型原始数据，Key-Value多维表多维表类似RDBMS的表数据划分方式一致性哈希。顺序表分裂一致性哈希顺序表、哈希表数据高可用副本冗余， gossip机制异 步复制数据记日志，底层文 件系统的副本冗余 策略以及同步策略。副本冗余， gossip机制异 步复制副本冗余，主从式 异步复制负载均衡虚拟节点Master集中调度不详Master集中调度失效侦测Gossip机制Chubby锁服务， Master Heartbeat 侦 测容错技术gossip机制失 效检测，利用 Merkle Tree 进行失效恢 复利用Chubby锁服务 进行节点失效恢复。 底层文件系统自动 进行存储失效恢复。Gossip机制进 行失效检测YMB通过将消息 记日志的方式防 止在更新过程中 的节点失效。通过 从远程副本的拷 贝实现失效恢复部署方式广域网集群集群广域网表2几种新兴数据管理系统的对比2.5.案例分析在这一小节中，我们将对Dynamo和BigTable进行详细分析，阐述这些系统如何实现 上面所讨论的海量数据管理关键技术。2.5.1. DynamoDynamo是一个基于分布式哈希的非集中式的大规模数据管理系统。在Dynamo中，数 据按照key-value进行组织，主要面向原始数据的存储。这种架构下，系统中每个节点都能 相互感知，自我管理性能较强，没有单点失效。1）数据划分在数据划分方面，Dynamo通过Consistent Hashing算法8进行。Key经过hash函数哈希 得到值，按照值域首尾相接形成一个ring。这个Hash值形成的ring被划分成不同的范围， 分配给集群系统中的不同节点进行管理。当对数据进行请求（读取/插入）时，通过计算该 key/value中key的hash值，定位到相应的节点进行服务请求。整个过程如图2所示。图2 一致性哈希的工作方式43采用一致性哈希进行数据划分的优势还在于，一致性哈希最大限度地抑制了节点变化 （添加/移除）时数据需要进行迁移重新分布的数量，这有利于系统的扩展性。如图3所示， 当前系统访问压力过大时，通过增加新的节点可以缓解压力；而此时，新节点的加入仅仅影 响它的邻居节点，避免了大量数据进行迁移的开销。图3 一致性哈希处理节点添加/移除时的情况43在Dynamo中，没有专门节点进行元数据信息（数据存放位置等）的存储和管理Dynamo 中的节点在本地维护系统中存储节点的列表，并利用gossip机制感知其他节点的存在，以及 相应数据存储的位置。针对某一个key的读写操作，每个节点根据本地存放的相关信息，快 速定位到正确的节点集进行操作。相比集中管理的策略，Dynamo避免了单点失效带来的灾 难。2）负载均衡一致性哈希算法在某种程度上地解决了系统扩展性的问题。但是用户访问的随机性以及 节点的异构特性所带来的负载不均衡，并不是一致性哈希算法可以解决的问题。Dynamo利 用虚拟节点技术，有效地将数据均匀存储到各个节点上，将访问请求的压力分散出去，保证 了系统的健壮性和负载的均衡性。虚拟节点的概念是对Consistent Hash的扩充，它将一个物理节点拆分成多个虚拟节点映 射到哈希环上的不同位置，取代了传统一致性哈希中一个物理节点只对应哈希环上一个点的 映射关系。从而在Dynamo中，虚拟节点作为一个资源容器，而存储作为一个服务运行于其中。通过引 入虚拟节点，Dynamo将资源管理粒度单元化。这样，资源多的节点可以多部署一些虚拟节 点，而资源少的节点可以少部署一些虚拟节点，进而达到一种相对均衡的状态，以此解决了 节点异构带来的负载不均衡问题。同时，虚拟节点的引入，也解决了用户访问随机性带来的负载不均衡问题：将访问压力 较大的虚拟节点分配给服务能力强的物理节点进行服务;而将那些访问压力较小的虚拟节点 成组分配给服务能力强的物理节点或者逐一分配给服务能力弱的物理节点；最终，达到动态 的负载均衡。在解决访问压力均衡的同时，虚拟节点也方便进行数据的均衡，并且能在最大程度上降 低因为数据均衡进行数据迁移带来的系统开销。比如，当在哈希ring中加入一个新节点时， 为了保持数据均匀分布的特性，那么进行数据均衡需要涉及全环节点的数据迁移，这样大大 增加了网络的开销。而采用虚拟节点的方法，一个物理节点可能管理哈希环上的多个虚拟节 点，进行数据均衡的时候，只需要涉及全环节点上的部分虚拟节点进行数据迁移，减少了迁 移的数据量，缓解集群网络的压力。3）容错以及数据的高可用Dynamo通过对数据进行冗余存放来提高数据访问的并发性和保证系统的高可用。多副 本带来的一致性问题，Dynamo通过客户端采用Quorum算法进行解决。针对不同的SLA服 务，提供不同程度的定制策略，在提供低延时读操作的同时，保证用户请求“总是可写”。在系统容错方面，Dynamo采用多副本机制来保证系统的高可用性，并通过gossip机制 来进行节点失效侦测、数据同步。对于临时失效和永久失效的情况，Dynamo采用不同的策略来容忍失效的发生。在临时 失效（网络分区等）发生时，系统通过寻找一台可用节点，将数据临时写在其上，待故障恢 复后，临时表中的数据会自动写回原目的地。这样，当临时故障出现时，保证用户总处于可 写的状态。而对于永久失效（比如磁盘损坏等），则需要通过副本进行数据恢复。Dynamo 利用Merkle Tree来保证节点失效后副本的同步：系统中每个节点都为每个key range维护一 个独立的Merkle Tree，当两个节点不一致时（如一个节点宕机一段时间），通过gossip机制 来对比各自的Merkle Tree，快速定位不一致的数据项来进行数据同步。2.5.2. BigtableBigtable是Google开发的一套结构化存储系统。数据以多维顺序表的方式进行存储。 整个系统采用传统的server farm形式，由一个主控服务器和多个子表服务器构成，并使用 分布式锁服务Chubby进行容错等管理。1）数据划分Bigtabl中所有的数据按照行的字典序进行有序存放。多行数据组成一个tablet，由一个 tablet服务器提供服务。每个多维表中的数据按照行的字典序划分成一系列大小相等的 tablet。当一个tablet中的数据慢慢增加，达到阈值后，相应的tablet服务器对这个tablet进 行分裂（split）0 Split后新的tablet由master进行调度分配到其他tablet服务器上进行服务。 这种数据的划分策略是一种渐进式的策略：在数据量小的时候，使用较少的资源进行服务； 当数据变大的时候，通过数据的分裂操作，使用更多的资源提供服务。这种渐进式的数据划 分方式合理地利用了系统的资源，也具有很好的扩展性。与Dynamo非集中式管理方法不同的是，BigTable采用master来负责集群中tablet server 状态的监控，以及tablet的调度和分配。其优势在于方便进行控制和维护，并且易于进行数 据同步。虽然这种集中式的管理方法，存在单点失效的隐患；但是Google通过最小化master 的作用，并使用分布式锁服务chubby9对master进行失效恢复操作，保证系统服务的高可 用。2）负载平衡Bigtable的负载均衡采用传统server farm的负载均衡策略：依靠一个master服务器通过 Heartbeat机制监控tablet server的负载情况，并依据这些负载情况进行数据迁移。比如将访 问很热的列表迁移到压力轻的tablet服务器上，将增长到阈值的tablet切分后放置到负载较 轻的节点上。利用这种方式可以将用户的请求均衡的分布到不同的tablet服务器上，达到 tablet服务节点的负载均衡。而Bigtable的数据采用GFSU0进行存储，数据在存储节点上的 均衡由Google FS完成。3）容错及数据高可用Bigtable通过分布式锁服务Chubby来解决节点失效的问题。Bigtable利用chubby追踪 master和tablet服务器的状态，并完成对master失效或者tablet服务器失效的处理。在BigTable中，元数据存储与节点管理被分开在不同节点上提供服务。元数据以META Tablet的方式，存放在GFS上，并由tablet server提供服务。而Master只进行节点的管理和 Tablet的调度分配。这样，当master失效后，重新加入的master只需要通过扫描chubby 了 解Root Tablet存放的位置以及集群中tablet server列表信息，并重新与tablet server进行通信， 进行系统的重建，重新提供服务。而对于tablet server的失效，master可以利用chubby 了解 tablet server的状态，感知tablet server的失效，进而进行相应的失效处理：比如，将该tablet server上服务的tablet进行重新分配到其他tablet server上，并根据该tablet server保存在GFS 上的日志对数据进行恢复。对于存储（数据、日志）的容错主要由GFS完成。GFS通过多副本机制来保证系统的 高可用：文件被划分成一个个chunk，每个chunk以pipeline的方式将多副本写入多台chunk 服务器。同时，文件中所有chunk的位置信息都会被记录在GFS的Namenode中。客户端 对某个文件进行读操作时，从Namenode中获取chunk信息和相应的chunkserver列表，再 从可用的chunk服务器中读取数据。多副本机制在一定程度上保证了数据可用性。3. 海量数据处理在信息时代，互联网已经成为了世界范围内最大的数据仓库。如何快速地从这些海量数 据中抽取出关键的信息用以提高互联网应用的质量、用户体验等，已经成为了互联网企业之 间竞争的关键技术问题。同时，大规模数据处理的研究，也是DISC应用研究的关键问题。3.1. 并行计算解决大规模数据处理的方法就是并行计算。将大量数据分散到多个节点上，将计算并行 化，利用多机的计算资源，从而加快数据处理的速度。目前，这种并行计算主要分为三大类， 一类是广泛应用于高性能计算的MPI12技术，一类是以Google/Yahoo为代表的互联网企业 兴起的Map/Reduce13计算，一类是微软提出的Dryad14并行计算模型。3.1.1. MPIMPI（Message Passing Interface，消息传递接口）是一种工业标准的API规范，专为在多 处理器计算机和计算机集群上进行高性能计算而设计。该标准是由大量计算机供应商和软件 开发商共同设计完成。MPI作为目前国际上最流行的并行编程环境之一，以可移植性和易用性、完备的异步通 信功能等优点，广泛应用在机群高性能计算中。在基于MPI编程模型中，计算是由一个或 多个彼此通过调用库函数进行消息收、发通信的进程所组成。绝大部分MPI实现中，一组 固定的进程在程序初始化时生成。这些进程在不同的节点上运行（通常一个处理器一个进 程），执行着相同或不同的程序，以点对点通信或者集合通信的方式进行进程间交互，共同 协作完成同一个计算任务。以任务之间的消息传递方式进行数据交换的MPI，其进行并行数据处理的基本思路就 是，将任务划分成为可以独立完成的不同计算部分，将每个计算部分需要处理的数据分发到 相应的计算节点分别进行计算，计算完成后各个节点将各自的结果汇总到主计算节点进行结 果的最终汇总。3.1.2. MapReduceMapReduce是Google在2004年提出的应用于大规模集群进行大规模数据处理的并行计 算模型。Map （映射）和Reduce （化简）的概念，以及他们的主要思想，都来自于函数式语言U5 在一个计算任务中，计算被抽象并简化成为两个阶段：Map和Reduceo Map阶段，系统调 用用户提供的Map函数，完成从一组键值到新一组键值的映射计算；而Reduce阶段，用户 指定的Reduce函数则被用来将所有Map计算完成的结果进行一次化简归约。与MPI有所不同的是，Map/Reduce是通过将计算（Map或者Reduce）分发到或者靠近 相应的数据存储节点，让计算（Map或者Reduce）在数据存储节点就地或者就近完成，从 而减少了大数据量在网络上传输的压力。3.1.3. DryadDryad是微软在2007年提出的数据并行计算模型。目前已经在Microsoft AdCenter投 入使用。与MapReduce的思路相同，Dryad也是通过将划分出来的小计算移动到或者靠近相 应的数据存储节点，让计算就地或者就近完成，减少网络上大规模数据传输的压力。在Dryad中，每个任务将被表示成一个有向无环图（DAG），计算按照有向无环图的方 向依赖进行。DAG相对于两阶段式的MapReduce，可以表达更加丰富的计算类型；同时， 它支持TCP Pipes Shared-memory FIFOs进行计算间结果的传递，可以避免一些不必要的磁 盘IO,利用更高效的传输手段，加速计算的过程。3.2. 关键技术不论是MPI、MapReduce还是Dryad，都被广泛地应用在真实的生产系统中。但是这些 并行计算的技术在设计理念和实现手段上都有很大的不同，且针对的领域也有不相同的地 方，如表4所示。在接下来这一节，对比这几种技术之间的相同和不同点，以及它们特有的 特点。MPIMapReduceDryad部署方式计算节点与数据存储节 点分开部署（移动数据到 计算节点）计算和数据存储部署 在同一节点上（移动计 算尽可能靠近数据）计算和数据存储部署在 同一节点上（移动计算 尽可能靠近数据）资源管理/调 度-Workqueue(Google)、 HOD(Yahoo!)不详低层次编程MPI APIMapReduce APIDryad API高层次编程无Pig，Hive， Jaql 等Scope、DryadLINQ数据存储本地文件系统、NFS等GFS (Google)、HDFS (Hadoop)、KFS、NTFS、Cosmos DFSAmazon S3 等任务划分用户手动进行任务划分自动化自动化通信消息传递、远端内存访问Files(Local FS, DFS)Files, TCP Pipes, shared-memeory FIFOs容错Checkpoint任务重做任务重做表3不同并行计算技术的对比3.2.1. 数据/计算的部署方式存储和计算能力是一个集群的主要性能指标。通常，一个集群的存储和计算有两种组织 方式：一种是将存储和计算部署在相同的节点上；一种是存储节点和计算节点分离开，独立 部署。Mapreduce和Dryad都采用前一种方式，其使用的节点是普通的PC （廉价的处理器、 几GB的内存，附加26块磁盘）。这种“disk-per-node”模型非常适合Mapreduce和Dryad 所提倡的计算方式一一移动计算到存储节点。这种模型，减少了网络IO的负载压力，通过 在每个节点上部署存储高效地增加了集群的带宽。而广泛使用MPI进行并行计算的高性能计算集群，通常采用存储服务器与计算服务器 分离的策略，将存储服务器聚合在一起以获得较高的并行存储I/O带宽。同时，分离存储节 点可以方便地进行可靠性以及管理方案的优化。不过，与“disk-per-node”模型相比，在这 种方式下，MPI通常采用“移动数据到计算节点”的方式进行数据处理，网络IO的能力将 成为影响性能的因素。不论是Mapreduce、Dryad还是MPI，任何一种并行计算模型并不只局限于某种特定的 集群组织方式（数据/计算的部署方式）。比如，存储节点和计算节点分离的模型，同样被应 用在一些互联网服务、云计算服务（Amazon）中。在Amazon的云计算服务中，计算节点 （EC2）与底层存储设施（EBS、S3）分离部署；EBS存储系统独立于EC2，提供高可用性、 无缝数据迁移、数据备份等服务特性。Mapreduce和MPI这两种并行计算模型均被应用在 Amazon的云计算服务中。3.2.2. 计算的划分方式在大规模数据处理这种应用下，并行计算不仅需要考虑算法层面上计算的划分问题，而 且需要考虑海量数据在相同计算下的划分问题（并行化）。不论是Mapreduce还是Dryad，其计算的数据以分块（64M或者128M）的方式分散存 放在集群的各个节点上。同时，“移动计算到存储节点”使得每个计算任务只需要处理一部 分数据（通常是文件的一个分块，64M或者128M），自然地实现了海量数据的并行处理。 但是，这种按照存储特性进行计算划分的方式，只适合于不存在数据依赖的单一计算。面对 复杂的计算（存在依赖关系），Mapreduce通过将复杂的计算转化成一系列的单一 MR计算， 利用Chain机制串联完成多个MR任务来实现复杂计算。这种转化通常是由程序员在算法层 面上手工完成。不过，随着Pig16、Hive17、Cascading】18】等基于Mapreduce的高层次并行计 算工具的出现，一类特定的复杂计算可以通过这些工具自动实现划分。与Mapreduce这种由 小（单一计算）到大（复杂计算）的思路不同，Dryad将存在依赖关系的复杂计算表示成有 向无环图，利用图论的理论对计算自动进行依赖性分析和优化，最后转化成高效的子任务依 赖执行。在MPI广泛应用的集群中，存储节点和计算节点通常被分开进行部署，数据在计算之 间通过网络进行传输MPI提供了一套完整的消息传递机制进行任务间数据以及计算结果的 传递，并且依赖这套机制进行各种消息控制，完成各种任务同步协作的逻辑；但是，计算任 务和处理数据的划分需要程序员自己完成。3.2.3. 通信手段在MPI中，数据以及计算结果通过消息机制在任务之间进行传递，并且所有的数据都 被存放在计算节点的内存中（可以通过远程内存访问的方式进行访问），速度快，并且需要 很高的通信带宽。而单个Mapreduce任务处理的数据集之间不存在相互依赖的关系，因此map任务之间、 reduce任务之间不需要进行任何的通信或同步操作。唯一需要进行协同的是，所有reduce 任务必须在所有map任务完成后才能开始执行。Reduce任务与map任务之间通过一些临时 文件进行访问：map任务完成map操作后，将map的结果输出到map任务所在节点的本地 文件系统上；reduce任务通过读取（本地或者远端）map的结果输出文件，开始执行reduce 操作。更复杂的计算通过Pig、Hive等高层次并行计算工具的转化，形成一组存在依赖次序的 Mapreduce任务依次执行。每个Mapreduce任务依赖于前一个（组）Mapreduce任务的完成； 前一个（组）Mapreduce任务的输出结果将作为下一个Mapreduce任务的输入，任务与任务之 间通过文件的I/O进行通信。与Mapreduce类似的是，Dryad也支持任务之间通过本地或者远端访问前一个任务的输 出结果文件进行通信。不过，Dryad也提供类似 MPI的远端内存访问，TCP Pipes， shared-memory FIFOs等比磁盘IO更高效的通信手段。3.2.4. 容错技术失效是大规模集群经常遇见的问题。任何大规模集群必须能够检测、容忍失效的存在， 并且能自动从失效中恢复过来。利用MPI进行并行计算的任务，通常由一组分布在多个节点上运行的进程组成。这些 进程通过消息进行通信，共同协作完成某一特定的计算MPI中，大量的数据和计算结果是 被缓存在不同节点的内存中；节点或者进程的失效可能导致整个任务的失败。为了容忍失效 的存在，MPI通常采用checkpoint的方式，周期性地记录所有进程的状态；在失效发生时， 将所有进程的状态回滚到上一次checkpoint的状态，重新开始执行。Checkpoint的周期是一 个比较难以把握的参数。如果checkpoint的周期较长，那么失效恢复后，所有失效的进程需 要重新进行大量的计算；如果checkpoint的周期较短，那么需要频繁地进行checkpoint操作， 大量增加了冗余的I/O操作。与MPI不同的是，Mapreduce采用Task Re-execute的方式来处理节点或者进程的失效。在 Mapreduce中，一个计算任务被分成许多执行时间较短（相对于MPI的子进程而言）的子任务（mapper、 reducer）来完成，并且使用磁盘存储子任务相应的临时结果。这样，在失效发生的时候，只需要通过 重做失效的子任务，就可以将整个计算任务恢复到正确的状态，不会影响正在执行或者已经执行完成 的子任务。不过利用磁盘存储作为任务之间通信和临时状态保存的手段，将会引入较高的性能开销， 使得整个任务执行的速度受限于磁盘的I/O。类似地，Dryad同样使用Task Re-execute的方法来处理节点或者进程的失效问题。略有不同的是， Dryad的子任务之间存在依赖关系，导致某个子任务因失效重做可能需要回溯重做它所依赖的一些子 任务。这样会引入较大的重做开销。3.2.5. 总结在面向海量数据的并行计算领域中，移动数据到计算节点已经是不现实的技术。大量的 网络I/O会对集群网络造成很大的压力，同时大大影响了数据处理的性能。Mapreduce和Dryad使用“移动计算到存储节点”的理念，通过将计算执行本地化达到 并行化，减轻了集群中网络负载的压力，提供了数据处理的性能。但是，这种利用数据分块 存储的特点来达到数据处理并行化的方式，适合的计算应用范围有限。比如Dryad只针对能 表示成有向无环图的计算任务进行并行执行，对于需要进行反复迭代(有向有环图)这一类 应用(聚类、矩阵运算等)束手无策。Mapreduce也是如此。即使Dryad、Mapreduce能通 过某种手段处理这类需要反复迭代的计算任务，但是利用磁盘IO进行任务之间的通信会影 响这类计算执行的性能。针对反复迭代的计算任务，目前比较高效的实现是采用MPI完成。MPI提供灵活的消 息传递和控制机制。利用MPI可以编写较为灵活的并行计算逻辑。不过需要人为地进行任 务的划分、数据的划分，以及利用checkpoint机制进行容错，限制了 MPI应用在更大规模 的数据处理中。“移动计算到存储节点”，解决任务/数据自动划分的问题，提供一种高效的自动容错机 制，是解决大规模数据处理的三个关键技术问题。3.3.高级语言利用MPI、Mapreduce或者Dryad，都可以高效地完成一类或者几类问题。但是，这些 并行计算系统或者工具都比较低层次，程序员学习和利用这些工具进行开发的周期都比较 长，甚至需要详细了解系统的构架才能写出比较高效的执行代码。因此，一些基于这些系统的高层次并行编程工具或者语言开始出现，如表4所示。本小节将主要讨论这些高层次语言 或工具的差异。SawzallPigHiveScopeDryadLINQ基础MR(Google)MR(Hadoop)MR(Hadoop)DryadDryad语法命令式，C/C+语法命令式，借用SQL的语法SQL，声明式