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

互联网海量数据存储及处理调研综述摘要本文主要针对互联网应用中出现的新兴的海量数据存储和处理系统展开讨论，对比新兴系统与传统数据技术的差异，以及这些系统之间实现技术的不同特点，并总结出相应的关键技术问题。近些年来，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*20Bdocs=200TB每30天做一次索引：200TB/30days=6TB/daySNSFacebook（2008）PageView：0.5KB/pageviewevents*3Bpageviewevents/day=1.5TB/dayRelationship：100Musers*5events*100feed/event*0.1KB/feed=5TB/day图片共享Facebook（2007）65亿张原始图片，每张图片保存为4~5个不同尺寸图片总量达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年末，互联网视频的平均尺寸为63M[38]。而相对于视频而言，图片的平均大小为几百K而已；那些记录用户交互信息的数据则更小。数据类型多样，大小不一的特性对于海量数据存储、管理提出了严峻的考验。4）数据操作模式较为固定，一致性要求较弱。在互联网应用，虽然数据类型多样，大小不一，但是对于数据的操作模式相对固定。对数据的操作，主要包括增加、删除、修改、查询这四类。其中，删除和修改操作在互联网应用中并不频繁，基本上可以忽略。而查询和增加是互联网应用中最频繁的两种操作，据统计这两类操作的比例大概在80：20（或者90：10）左右35]。与金融行业的数据操作不同的是，互联网应用的数据操作没有很强的事务特性，也没有严格的一致性要求，但对读写时延的有定要求（读写时延影响互联网应用的用户体验）。图1GrowthinDurationofWebVideos38】互联网应用的海量数据特性，对数据存储和处理提出了新的挑战。这些挑战概括如下：1）TB级甚至PB级的存储系统，以适应海量数据的需求。2）良好的扩展性。在不中断服务的情况下，通过简单添置机器或者磁盘存储来扩展系统，满足不断增长的数据和用户群体需求。3）低时延、高吞吐的存储系统性能。4）丰富的存储类型，以满足互联网应用中结构化、半结构化甚至非结构化数据的存储需求。5）灵活简单的并行编程模型进行海量数据处理，隐藏分布式环境下数据分布、容错等复杂性。在这样的挑战下，一些传统技术已经开始不能胜任互联网应用的需求。新兴的海量数据存储、处理系统也相继涌现。在接下来的两个部分，文章将从数据存储和数据处理两个角度，讨论传统技术存在的问题，介绍一些新型系统，并分析这些新型系统在解决海量数据存储和处理时遇到的问题以及相应的解决方案。数据存储目前，大部分互联网应用仍然使用传统关系型数据库进行数据的存储管理，并通过编写SQL语句或者MPI程序来完成对数据的分析处理。这样的系统在用户规模、数据规模都相对比较小的情况下，可以高效地运行。但是，随着用户数量、存储管理的数据量不断增加，许多热门的互联网应用在扩展存储系统以应对更大规模的数据量和满足更高的访问量时都遇到了问题四，24,26,27,28,29,36］。2.1.传统关系型数据库传统关系型数据库在数据存储管理的发展史上是一个重要的里程碑。在互联网时代以前，数据的存储管理应用主要集中在金融、证券等商务领域中。这类应用主要面向结构化数据，聚焦于便捷的数据查询分析能力、严格的事务处理能力、多用户并发访问能力以及数据安全性的保证。而传统关系型数据库正是针对这种需求而设计，并以其结构化的数据组织形式，严格的一致性模型，简单便捷的查询语言，强大的数据分析能力以及较高的程序与数据独立性等优点被广泛应用。然而互联网时代的到来，数据已超出关系型数据库的管理范畴，电子邮件、超文本、Blog、Tag以及图片、音视频等各种非结构化数据逐渐成为了海量数据的重要组成部分。面向结构化数据存储的关系型数据库已经不能满足互联网数据快速访问、大规模数据分析的需求。•应用场景的局限性传统数据库在设计上，着眼于面向结构化的数据，致力于事务处理，要求保证严格的一致性，这些特性符合传统的金融、经济等应用场景。然而互联网应用主要面向于半结构化、非结构化的数据，这些应用大多没有事务特性，也不需要很严格的一致性保证。虽然传统数据库的厂商也针对海量数据应用特点提出了一系列改进方案，但是由于并不是从互联网应用的角度去寻找问题，使得传统数据库在应对互联网海量数据存储上效果并不理想。•关系模型束缚对海量数据的快速访问能力关系模型是一种按内容访问的模型⑵。即在传统的关系型数据库中，根据列的值来定位相应的行。这种访问模型，将在数据访问过程中引入耗时的IO,从而影响快速访问的能力。虽然，传统的数据库系统可以通过分区的技术（水平分区和垂直分区），来减少查询过程中数据IO的次数以缩减响应时间，提高数据处理能力；但是在海量数据的规模下，这种分区所带来的性能改善并不显著。关系模型中规格化的范式设计与web2.0的很多特性相互矛盾［26］。以Tag为例，Tag的分类模型是一种复杂的多对多关系模型。传统数据库的范式设计要求消除冗余性，因此Tag和内容将会被存储在不同的表中，导致对于Tag的操作需要跨表完成（在分区的情况下，可能需要跨磁盘、跨机器操作），性能低下。•缺乏对非结构化数据的处理能力传统的关系型数据库对数据的处理只局限于某些数据类型，比如数字、字符、字符串等，对非结构化数据（图片、音频等）的支持较差。然而随着用户应用需求的提高、硬件技术的发展和互联网上多媒体交流方式的推广，用户对多媒体处理的要求从简单的存储上升为识别、检索和深入加工，因此如何处理庞大的声音、图像、和视频、E-mail等复杂数据类型，是传统数据库面临的一个问题。•扩展性差在海量规模下，传统数据库面临着一个致命问题，就是其扩展性问题。解决数据库扩展性问题，通常有两种方式：Scaleup和Scaleout。这两种扩展方式分别从两个不同的维度来解决数据库在海量数据下的压力问题。Scaleup，简而言之就是通过硬件升级，提升速度来解决缓解压力问题；而Scaleout则是通过将海量数据按照一定的规则进行划分，将原来集中存储的数据分散到不同的物理数据库服务器上。Sharding［3］正是在Scaleout的理念指导下，传统数据库提出了一种解决扩展性的方案。Sharding通过叠加相对廉价设备的方式实现存储和计算能力的扩展，其主要目的是为突破单节点数据库服务器的I/O能力限制，提高快速访问能力，以及提供更大的读写带宽。但是，在互联网的应用场景下，这种解决扩展性的方案仍然存在着一定局限性制。比如，数据存储在多个节点，需要考虑负载均衡的问题，这需要互联应用需要实现复杂的负载自动平衡机制，引入较高代价；数据库严格的范式规定，使得表示成关系模型的数据很难进行划分到不同的shard中；同时，还存在一些数据可靠性和可用性的问题。新兴数据存储系统在传统关系型数据库已不能满足互联网应用需求的情况下，开始出现一些针对结构化、半结构化甚至非结构化数据的管理系统。在这些系统中，数据通常采用多副本的方式进行存储，保证系统的可用性和并发性；采用较弱的一致性模型（如最终一致性模型），在保证低延时的用户相应的同时，维持复本之间的一致状态；并且都提供良好的负载平衡策略和容错手段。按照数据管理方式划分，这些新兴的数据管理系统可以归为两大类：（一）集中式数据管理系统这类系统采用传统的serverfarm架构。整个系统需要一个主控节点维护各从节点的元信息，是一种集中控制的管理手段。其优势在于，集中管理的方式人为可控且维护方便，在处理数据同步时更为简单。其劣势在于，系统存在单点故障的危险。这类系统包括Google的Bigtable和Yahoo！的Pnuts。BigtableBigtable是Google开发的一套结构化存储系统⑸。数据以多维顺序表的方式进行存储。整个系统采用传统的serverfarm形式，由一个主控服务器和多个子表服务器构成，并使用分布式锁服务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哈希值来划分顺序表或者哈希表中的数据。数据一致性与可用性数据可用性是分布式环境下数据存储的基石;而数据一致性模型则保证数据操作的正确性。在分布式环境下，通常采用副本冗余、日志等方式来解决数据的可用性问题；但是副本冗余存储也带来了数据一致性的问题。在采用副本冗余方式的分布式系统中，数据一致性与系统性能是一对不可调和的矛盾：需要牺牲系统的性能来保证数据的严格一致性，或者牺牲一致性来保证系统的性能（响应时间等）。在互联网应用中，通常采用第二种手段来调和这种矛盾，即允许系统通过弱化一致性模型来保证高效的系统响应，同时通过异步复制的手段来保证数据的可用性。Dynamo，Bigtable，Pnuts都是通过副本冗余的方式来保证数据的高可用。但是，其具体实现又不尽相同。由于Dynamo采用非集中的管理方式，整个系统中无主从节点之分，Dynamo在整个哈希环上通过gossip机制进行通讯，完成副本的异步复制。而采用集中管理方式的Bigtable和Pnuts均采用日志的方式保证服务节点内存中数据的可用性。不同的是，在数据存储可用性方面，BigTable依赖于底层分布式文件系统的副本机制；而Pnuts则采用基于pub/sub通讯机制的主从式异步复制的方式来完成数据的冗余存储：数据首先被同步到主副本，然后通过pub/sub机制异步更新到所有副本。负载平衡负载均衡是分布式环境下进行高效数据管理的关键问题。它主要包括数据的均衡和访问压力的均衡这两个方面。在分布式环境中，数据通过一定的划分策略（哈希或者顺序分裂等）进行划分并存储在不同的节点上，用户的访问请求也将由不同的节点处理。由于用户访问请求的分布规律不可预测性导致最终数据存储分布的不均衡，以及节点访问压力的不均衡。在数据分布、访问负载不均衡的情况下，频繁的并发访问和持续的数据加载压力将会影响整个系统的性能。为了保证数据加载的高吞吐率、系统响应的低延时以及系统的稳定性，海量存储系统需要有一套良好的均衡机制来解决上述问题。Dynamo采用了虚拟节点技术，通过虚拟化的手段将节点的服务能力单元化，将访问压力较大的虚拟节点映射到服务能力较强的物理节点，达到访问压力的均衡。访问压力的均衡伴同时伴随着数据的均衡。为了使数据均衡过程中，数据迁移的开销尽可能小，Dynamo采用同样的虚拟化技术，量化节点的存储能力，将虚拟后的存储节点相对均匀地分散到集群哈希环上，避免数据均衡过程中全环的数据移动。在非集中式系统中，这些均衡操作可以由任一节点发起，通过gossip通讯机制与集群中的其他节点协调完成。与Dynamo这种非集中式管理不同的是，BigTable通过master来监控各个tabletserver上的访问负载状态，利用master调度管理tablet的分裂和迁移将访问压力均匀地分散到各个tabletserver上。由于BigTable采用分布式文件系统作为数据的底层存储，tablet的分裂和迁移过程中并不涉及到存储数据的迁移操作，以一种巧妙的方式避免了数据均衡的问题。在集中式管理系统中，PNUTS也采用类似的方式进行访问压力的均衡。不同的是，采用本地文件系统或者本地数据库系统的PNUTS在进行tablet的分裂和迁移时，需要进行存储数据迁移。有效的数据划分方式为系统扩展性提供了一个基础，但是同时也给系统带来了负载均衡的问题。通过虚拟化节点或者表分裂等方式改变数据分布格局，均衡访问负载的同时，尽可能减少存储数据迁移量或者避免数据迁移，是海量存储系统的一个挑战。容错容错是分布式系统健壮性的标志。节点的失效侦测以及失效恢复已经成为保证系统的可用性、可靠性的关键问题。1）失效侦测在非集中式系统中，各节点之间定期进行交互以了解节点的活动状态，从而侦测失效的存在，如Dynamo、Cassandra。而在集中式系统中，整个系统需要有专门的部件（节点）来维护整个分布式系统中节点的状态信息，并通过Heartbeat机制完成失效节点的侦测。如Bigtable通过分布式锁服务chubby来跟踪master和tablet节点的服务状态，来完成节点的失效侦测；Pnuts则利用tabllecontroler部件维护的活动节点路由信息来判断节点失效的存在。2）失效恢复在系统侦测到失效节点的存在后，需要一定的恢复策略来完成对失效节点的恢复，保证系统的可用性和可靠性。在分布式系统中，节点的失效分为临时失效（如网络分区等）和永久失效（如节点宕机、磁盘损坏等）两种情况。在副本冗余存储的分布式系统中，失效通常会造成了多副本之间的数据不一致，这时候需要对失效节点的数据进行同步来完成失效的恢复。同时，永久失效通常会造成失效节点内存中数据的丢失，日志重做通常是解决这类问题的一种办法。当然，具体的失效恢复策略在不同的系统中又各有特色。以BigTable为例。临时失效和永久失效在BigTable中并不做区分。BigTable依靠主控节点通过Heartbeat机制来侦测失效的存在，即在规定的时间内主控节点通过Heartbeat无法获取从节点的状态信息，主控节点将认为从节点已经永久失效。这时候，主控节点将失效节点上服务的tablet重新分配到集群中的其他从节点上去提供服务，并通过重做失效节点的日志来完成失效节点的内存数据恢复。即使临时失效的节点可能再次与主控节点建立连接，这些节点也将被主控节点停止，因为这些节点上的服务已经被重新分配到其他节点上。这种依赖于底层分布式文件系统的共享存储方式，简化了系统的失效恢复。在集中式系统中，主从节点的功能差异使得主节点失效恢复的方式不尽相同。由于主节点维护系统元信息，那么主节点的失效将是灾难性的。针对集中式系统，通常采用备份节点（双机、多机备份）来防止主节点失效的发生。Bigtable通过chubby来管理集群节点的状态信息，利用tabletserver来管理整个系统的存储元信息，来弱化主节点的管理功能，减小主节点失效导致灾难的可能性，同时也降低了主节点恢复的复杂性。而在以Dynamo为代表的非集中数据存储系统中，临时失效和永久失效被区别对待。在临时失效发生时，Dynamo将会把数据暂时放置在临时节点，待节点从临时失效中恢复过来后，数据将归还给目标节点。对于永久失效带来的数据不一致，Dynamo通过对失效节点的数据进行同步来完成失效恢复。在Dynamo中，这种同步通过对比节点间的Merkletree来完

成。2.4.总结这些新兴系统通过不同的技术都为用户呈现了一个扩展性良好，且高度可用的大规模数据管理系统。但是，不同的系统都具有各自不同的特性，也采用了不同的技术方案来解决大规模数据存储的关键问题：数据划分、负载均衡和容错。这些差异归纳如表2所示。DynamoBigtableCassandraPnuts一致性模型最终一致性较弱一致性最终一致性Record-leveltimeline一致性数据管理方式非集中化集中式。非集中化集中式数据模型原始数据，Key-Value多维表多维表类似RDBMS的表数据划分方式一致性哈希。顺序表分裂一致性哈希顺序表、哈希表数据高可用副本冗余，gossip机制异步复制数据记日志，底层文件系统的副本冗余策略以及同步策略。副本冗余，gossip机制异步复制副本冗余，主从式异步复制负载均衡虚拟节点Master集中调度不详Master集中调度失效侦测Gossip机制Chubby锁服务，MasterHeartbeat侦测容错技术gossip机制失效检测，利用MerkleTree进行失效恢复利用Chubby锁服务进行节点失效恢复。底层文件系统自动进行存储失效恢复。Gossip机制进行失效检测YMB通过将消息记日志的方式防止在更新过程中的节点失效。通过从远程副本的拷贝实现失效恢复部署方式广域网集群集群广域网表2几种新兴数据管理系统的对比2.5.案例分析在这一小节中，我们将对Dynamo和BigTable进行详细分析，阐述这些系统如何实现上面所讨论的海量数据管理关键技术。DynamoDynamo是一个基于分布式哈希的非集中式的大规模数据管理系统。在Dynamo中，数据按照key-value进行组织，主要面向原始数据的存储。这种架构下，系统中每个节点都能相互感知，自我管理性能较强，没有单点失效。1）数据划分在数据划分方面，Dynamo通过ConsistentHashing算法［8进行。Key经过hash函数哈希得到值，按照值域首尾相接形成一个ring。这个Hash值形成的ring被划分成不同的范围，分配给集群系统中的不同节点进行管理。当对数据进行请求（读取/插入）时，通过计算该key/value中key的hash值，定位到相应的节点进行服务请求。整个过程如图2所示。

图2一致性哈希的工作方式[43]采用一致性哈希进行数据划分的优势还在于，一致性哈希最大限度地抑制了节点变化（添加/移除）时数据需要进行迁移重新分布的数量，这有利于系统的扩展性。如图3所示，当前系统访问压力过大时，通过增加新的节点可以缓解压力；而此时，新节点的加入仅仅影响它的邻居节点，避免了大量数据进行迁移的开销。图3一致性哈希处理节点添加/移除时的情况[43]在Dynamo中，没有专门节点进行元数据信息（数据存放位置等）的存储和管理°Dynamo中的节点在本地维护系统中存储节点的列表，并利用gossip机制感知其他节点的存在，以及相应数据存储的位置。针对某一个key的读写操作，每个节点根据本地存放的相关信息，快速定位到正确的节点集进行操作。相比集中管理的策略，Dynamo避免了单点失效带来的灾难。2）负载均衡一致性哈希算法在某种程度上地解决了系统扩展性的问题。但是用户访问的随机性以及节点的异构特性所带来的负载不均衡，并不是一致性哈希算法可以解决的问题。Dynamo利用虚拟节点技术，有效地将数据均匀存储到各个节点上，将访问请求的压力分散出去，保证了系统的健壮性和负载的均衡性。虚拟节点的概念是对ConsistentHash的扩充，它将一个物理节点拆分成多个虚拟节点映射到哈希环上的不同位置，取代了传统一致性哈希中一个物理节点只对应哈希环上一个点的映射关系。从而在Dynamo中，虚拟节点作为一个资源容器，而存储作为一个服务运行于其中。通过引入虚拟节点，Dynamo将资源管理粒度单元化。这样，资源多的节点可以多部署一些虚拟节点，而资源少的节点可以少部署一些虚拟节点，进而达到一种相对均衡的状态，以此解决了节点异构带来的负载不均衡问题。同时，虚拟节点的引入，也解决了用户访问随机性带来的负载不均衡问题：将访问压力较大的虚拟节点分配给服务能力强的物理节点进行服务;而将那些访问压力较小的虚拟节点成组分配给服务能力强的物理节点或者逐一分配给服务能力弱的物理节点；最终，达到动态的负载均衡。在解决访问压力均衡的同时，虚拟节点也方便进行数据的均衡，并且能在最大程度上降低因为数据均衡进行数据迁移带来的系统开销。比如，当在哈希ring中加入一个新节点时，为了保持数据均匀分布的特性，那么进行数据均衡需要涉及全环节点的数据迁移，这样大大增加了网络的开销。而采用虚拟节点的方法，一个物理节点可能管理哈希环上的多个虚拟节点，进行数据均衡的时候，只需要涉及全环节点上的部分虚拟节点进行数据迁移，减少了迁移的数据量，缓解集群网络的压力。3）容错以及数据的高可用Dynamo通过对数据进行冗余存放来提高数据访问的并发性和保证系统的高可用。多副本带来的一致性问题，Dynamo通过客户端采用Quorum算法进行解决。针对不同的SLA服务，提供不同程度的定制策略，在提供低延时读操作的同时，保证用户请求“总是可写”。在系统容错方面，Dynamo采用多副本机制来保证系统的高可用性，并通过gossip机制来进行节点失效侦测、数据同步。对于临时失效和永久失效的情况，Dynamo采用不同的策略来容忍失效的发生。在临时失效（网络分区等）发生时，系统通过寻找一台可用节点，将数据临时写在其上，待故障恢复后，临时表中的数据会自动写回原目的地。这样，当临时故障出现时，保证用户总处于可写的状态。而对于永久失效（比如磁盘损坏等），则需要通过副本进行数据恢复。Dynamo利用MerkleTree来保证节点失效后副本的同步：系统中每个节点都为每个keyrange维护一个独立的MerkleTree，当两个节点不一致时（如一个节点宕机一段时间），通过gossip机制来对比各自的MerkleTree，快速定位不一致的数据项来进行数据同步。BigtableBigtable是Google开发的一套结构化存储系统。数据以多维顺序表的方式进行存储。整个系统采用传统的serverfarm形式，由一个主控服务器和多个子表服务器构成，并使用分布式锁服务Chubby进行容错等管理。1）数据划分Bigtabl中所有的数据按照行的字典序进行有序存放。多行数据组成一个tablet，由一个tablet服务器提供服务。每个多维表中的数据按照行的字典序划分成一系列大小相等的tablet。当一个tablet中的数据慢慢增加，达到阈值后，相应的tablet服务器对这个tablet进行分裂（split）0Split后新的tablet由master进行调度分配到其他tablet服务器上进行服务。这种数据的划分策略是一种渐进式的策略：在数据量小的时候，使用较少的资源进行服务；当数据变大的时候，通过数据的分裂操作，使用更多的资源提供服务。这种渐进式的数据划分方式合理地利用了系统的资源，也具有很好的扩展性。与Dynamo非集中式管理方法不同的是，BigTable采用master来负责集群中tabletserver状态的监控，以及tablet的调度和分配。其优势在于方便进行控制和维护，并且易于进行数据同步。虽然这种集中式的管理方法，存在单点失效的隐患；但是Google通过最小化master的作用，并使用分布式锁服务chubby［9］对master进行失效恢复操作，保证系统服务的高可用。2）负载平衡Bigtable的负载均衡采用传统serverfarm的负载均衡策略：依靠一个master服务器通过Heartbeat机制监控tabletserver的负载情况，并依据这些负载情况进行数据迁移。比如将访问很热的列表迁移到压力轻的tablet服务器上，将增长到阈值的tablet切分后放置到负载较轻的节点上。利用这种方式可以将用户的请求均衡的分布到不同的tablet服务器上，达到tablet服务节点的负载均衡。而Bigtable的数据采用GFSU0］进行存储，数据在存储节点上的均衡由GoogleFS完成。3）容错及数据高可用Bigtable通过分布式锁服务Chubby来解决节点失效的问题。Bigtable利用chubby追踪master和tablet服务器的状态，并完成对master失效或者tablet服务器失效的处理。在BigTable中，元数据存储与节点管理被分开在不同节点上提供服务。元数据以METATablet的方式，存放在GFS上，并由tabletserver提供服务。而Master只进行节点的管理和Tablet的调度分配。这样，当master失效后，重新加入的master只需要通过扫描chubby了解RootTablet存放的位置以及集群中tabletserver列表信息，并重新与tabletserver进行通信，进行系统的重建，重新提供服务。而对于tabletserver的失效，master可以利用chubby了解tabletserver的状态，感知tabletserver的失效，进而进行相应的失效处理：比如，将该tabletserver上服务的tablet进行重新分配到其他tabletserver上，并根据该tabletserver保存在GFS上的日志对数据进行恢复。对于存储（数据、日志）的容错主要由GFS完成。GFS通过多副本机制来保证系统的高可用：文件被划分成一个个chunk，每个chunk以pipeline的方式将多副本写入多台chunk服务器。同时，文件中所有chunk的位置信息都会被记录在GFS的Namenode中。客户端对某个文件进行读操作时，从Namenode中获取chunk信息和相应的chunkserver列表，再从可用的chunk服务器中读取数据。多副本机制在一定程度上保证了数据可用性。海量数据处理在信息时代，互联网已经成为了世界范围内最大的数据仓库。如何快速地从这些海量数据中抽取出关键的信息用以提高互联网应用的质量、用户体验等，已经成为了互联网企业之间竞争的关键技术问题。同时，大规模数据处理的研究，也是DISC应用研究的关键问题。并行计算解决大规模数据处理的方法就是并行计算。将大量数据分散到多个节点上，将计算并行化，利用多机的计算资源，从而加快数据处理的速度。目前，这种并行计算主要分为三大类，一类是广泛应用于高性能计算的MPI［12］技术，一类是以Google/Yahoo为代表的互联网企业兴起的Map/Reduce［13］计算，一类是微软提出的Dryad［14］并行计算模型。MPIMPI（MessagePassingInterface，消息传递接口）是一种工业标准的API规范，专为在多处理器计算机和计算机集群上进行高性能计算而设计。该标准是由大量计算机供应商和软件开发商共同设计完成。MPI作为目前国际上最流行的并行编程环境之一，以可移植性和易用性、完备的异步通信功能等优点，广泛应用在机群高性能计算中。在基于MPI编程模型中，计算是由一个或多个彼此通过调用库函数进行消息收、发通信的进程所组成。绝大部分MPI实现中，一组固定的进程在程序初始化时生成。这些进程在不同的节点上运行（通常一个处理器一个进程），执行着相同或不同的程序，以点对点通信或者集合通信的方式进行进程间交互，共同协作完成同一个计算任务。以任务之间的消息传递方式进行数据交换的MPI，其进行并行数据处理的基本思路就是，将任务划分成为可以独立完成的不同计算部分，将每个计算部分需要处理的数据分发到相应的计算节点分别进行计算，计算完成后各个节点将各自的结果汇总到主计算节点进行结果的最终汇总。MapReduceMapReduce是Google在2004年提出的应用于大规模集群进行大规模数据处理的并行计算模型。Map（映射）和Reduce（化简）的概念，以及他们的主要思想，都来自于函数式语言U5]在一个计算任务中，计算被抽象并简化成为两个阶段：Map和ReduceoMap阶段，系统调用用户提供的Map函数，完成从一组键值到新一组键值的映射计算；而Reduce阶段，用户指定的Reduce函数则被用来将所有Map计算完成的结果进行一次化简归约。与MPI有所不同的是，Map/Reduce是通过将计算（Map或者Reduce）分发到或者靠近相应的数据存储节点，让计算（Map或者Reduce）在数据存储节点就地或者就近完成，从而减少了大数据量在网络上传输的压力。DryadDryad是微软在2007年提出的数据并行计算模型。目前已经在MicrosoftAd’Center投入使用。与MapReduce的思路相同，Dryad也是通过将划分出来的小计算移动到或者靠近相应的数据存储节点，让计算就地或者就近完成，减少网络上大规模数据传输的压力。在Dryad中，每个任务将被表示成一个有向无环图（DAG），计算按照有向无环图的方向依赖进行。DAG相对于两阶段式的MapReduce，可以表达更加丰富的计算类型；同时，它支持TCPPipes>Shared-memoryFIFOs进行计算间结果的传递，可以避免一些不必要的磁盘IO,利用更高效的传输手段，加速计算的过程。关键技术不论是MPI、MapReduce还是Dryad，都被广泛地应用在真实的生产系统中。但是这些并行计算的技术在设计理念和实现手段上都有很大的不同，且针对的领域也有不相同的地方，如表4所示。在接下来这一节，对比这几种技术之间的相同和不同点，以及它们特有的特点。MPIMapReduceDryad部署方式计算节点与数据存储节点分开部署（移动数据到计算节点）计算和数据存储部署在同一节点上（移动计算尽可能靠近数据）计算和数据存储部署在同一节点上（移动计算尽可能靠近数据）资源管理/调度--Workqueue(Google)、HOD(Yahoo!)不详低层次编程MPIAPIMapReduceAPIDryadAPI高层次编程无Pig，Hive，Jaql等Scope、DryadLINQ数据存储本地文件系统、NFS等GFS(Google)、HDFS(Hadoop)、KFS、NTFS、CosmosDFSAmazonS3等任务划分用户手动进行任务划分自动化自动化通信消息传递、远端内存访问Files(LocalFS,DFS)Files,TCPPipes,shared-memeoryFIFOs容错Checkpoint任务重做任务重做表3不同并行计算技术的对比数据/计算的部署方式存储和计算能力是一个集群的主要性能指标。通常，一个集群的存储和计算有两种组织方式：一种是将存储和计算部署在相同的节点上；一种是存储节点和计算节点分离开，独立部署。Mapreduce和Dryad都采用前一种方式，其使用的节点是普通的PC（廉价的处理器、几GB的内存，附加2~6块磁盘）。这种“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的云计算服务中。计算的划分方式在大规模数据处理这种应用下，并行计算不仅需要考虑算法层面上计算的划分问题，而且需要考虑海量数据在相同计算下的划分问题（并行化）。不论是Mapreduce还是Dryad，其计算的数据以分块（64M或者128M）的方式分散存放在集群的各个节点上。同时，“移动计算到存储节点”使得每个计算任务只需要处理一部分数据（通常是文件的一个分块，64M或者128M），自然地实现了海量数据的并行处理。但是，这种按照存储特性进行计算划分的方式，只适合于不存在数据依赖的单一计算。面对复杂的计算（存在依赖关系），Mapreduce通过将复杂的计算转化成一系列的单一MR计算，利用Chain机制串联完成多个MR任务来实现复杂计算。这种转化通常是由程序员在算法层面上手工完成。不过，随着Pig[16]、Hive[17]、Cascading】18】等基于Mapreduce的高层次并行计算工具的出现，一类特定的复杂计算可以通过这些工具自动实现划分。与Mapreduce这种由小（单一计算）到大（复杂计算）的思路不同，Dryad将存在依赖关系的复杂计算表示成有向无环图，利用图论的理论对计算自动进行依赖性分析和优化，最后转化成高效的子任务依赖执行。在MPI广泛应用的集群中，存储节点和计算节点通常被分开进行部署，数据在计算之间通过网络进行传输°MPI提供了一套完整的消息传递机制进行任务间数据以及计算结果的传递，并且依赖这套机制进行各种消息控制，完成各种任务同步协作的逻辑；但是，计算任务和处理数据的划分需要程序员自己完成。通信手段在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的远端内存访问，TCPPipes，shared-memoryFIFOs等比磁盘IO更高效的通信手段。容错技术失效是大规模集群经常遇见的问题。任何大规模集群必须能够检测、容忍失效的存在，并且能自动从失效中恢复过来。利用MPI进行并行计算的任务，通常由一组分布在多个节点上运行的进程组成。这些进程通过消息进行通信，共同协作完成某一特定的计算°MPI中，大量的数据和计算结果是被缓存在不同节点的内存中；节点或者进程的失效可能导致整个任务的失败。为了容忍失效的存在，MPI通常采用checkpoint的方式，周期性地记录所有进程的状态；在失效发生时，将所有进程的状态回滚到上一次checkpoint的状态，重新开始执行。Checkpoint的周期是一个比较难以把握的参数。如果checkpoint的周期较长，那么失效恢复后，所有失效的进程需要重新进行大量的计算；如果checkpoint的周期较短，那么需要频繁地进行checkpoint操作，大量增加了冗余的I/O操作。与MPI不同的是，Mapreduce采用TaskRe-execute的方式来处理节点或者进程的失效。在Mapreduce中，一个计算任务被分成许多执行时间较短（相对于MPI的子进程而言）的子任务（mapper、reducer）来完成，并且使用磁盘存储子任务相应的临时结果。这样，在失效发生的时候，只需要通过重做失效的子任务，就可以将整个计算任务恢复到正确的状态，不会影响正在执行或者已经执行完成的子任务。不过利用磁盘存储作为任务之间通信和临时状态保存的手段，将会引入较高的性能开销，使得整个任务执行的速度受限于磁盘的I/O。类似地，Dryad同样使用TaskRe-execute的方法来处理节点或者进程的失效问题。略有不同的是，Dryad的子任务之间存在依赖关系，导致某个子任务因失效重做可能需要回溯重做它所依赖的一些子任务。这样会引入较大的重做开销。总结在面向海量数据的并行计算领域中，移动数据到计算节点已经是不现实的技术。大量的网络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，声明式SQL，声明式命令式，结合SQL查询数据定义ProtocolbufferTuple简单关系模型简单关系模型简单关系模型数据操作Aggregation大部分SQL操作SQL操作SQL操作SQL操作编译执行Sawzall代码被编译后嵌入map阶段进行执行；reduce阶段执行系统提供的AggregatorsPig脚本或者SQL语句被编译成一组存在依赖关系MR任务，按照任务的依赖关系有序执行。Scope或者DryadLINQ脚本被编译成一个Dryad的任务执行。优化用户只能定义filter操作，由系统提供高效的Aggregator实现。消重、提前filter、减少I/O等表4各种高层次并行编程语言的对比3.3.1.命令式VS声明式设计一门高层次的语法，首先需要考虑语法的定义。目前的编程语言，大体上可以分为两类：命令式(Imperativelanguage)和声明式(Declarativelanguage)。我们所熟知的C、C++、Java、Python等语言基本上都是命令式语言；而SQL则属于声明式语言的范畴。命令式语言，不论是面向过程的C,还是面向对象的C++、Java,都是以图灵机为基础。它们通过指定一系列可执行的运算以及运算的次序来描述计算过程。在命令式语言中，变量对应于存储单元，对变量的访问就是对相应存储单元的访问；各个语句在程序中的书写顺序以及转向语句的控制则明确规定了机器的执行步骤。这给程序员提供了自由控制机器的灵活性，但是迫使程序员需要去关心比较低级的细节。而声明式语言，比如SQL，它不要求用户指定对数据的存放方法，也不需要用户了解其具体的数据存放方式。SQL定义一系列标准化的数据查询、定义、操作和控制的API。这使得具有底层结构完全不同的数据库系统和不同数据库之间，可以使用相同的SQL语言进行数据的输入与管理。声明式语言，让程序员摆脱了“该怎么做”的苦恼，可以更专注于“需要做什么”的逻辑上。目前出现的基于Mapreduce或者Dryad的高层次编程语言，大部分都使用或者借鉴了SQL的语法。Hive和Scope"］直接使用SQL作为其使用的语言，将大规模数据处理的复杂性隐藏在声明语句的背后；而Pig和DryadLINQ［20］则在命令式语言中，引入了SQL的语法，在保存了命令式语言控制灵活特性的同时，吸收了声明式语言进行数据查询、定义、操作的精华。Sawzall［2i］虽然采用了命令式语法，但是它通过“Filter-Aggregation”这种两阶段操作，将程序员的逻辑限制在Filter阶段，使程序员可以专注于数据处理的本身，又不失命令式语言的灵活性。如何隐藏分布式环境的复杂性，使程序员更加专注于处理数据的逻辑本身，是这些高层次编程语言在选择语法时需要考虑的问题。数据定义语法的确定从一定程度上也确定了数据的表达方式。使用或者借鉴SQL的语言中，比如Pig、Hive、Scope以及DryadLINQ都采用了简单的关系模型，来表征需要处理的数据。整个数据集在这些语言中被表示成“表”的形式（Pig中为Bag，DryadLINQ中为Collection）0每张“表”中由一组“记录”（Pig中为Tuple，DryadLINQ中为Element）组成。而“记录”由一些基本类型值构成，称之为字段。而在Sawzall中，一条数据被解析成一个结构（Struct）。用户通过ProtocolBuffer的数据定义语言（DDL，DataDefineLanguage）来定义数据的格式。用户在Sawzall脚本中，只需要考虑对一个结构（一条数据）的处理，而数据的解析和IO有Sawzall系统来完成。不论是使用简单的关系模型进行数据的表达，还是使用类C的Struct进行数据格式定义，大规模的数据在这些语言中都被抽象成结构化的数据：数据集由一个个结构化数据组成，该结构化数据由一组基本类型值（整型、浮点型、字符、字符串等）构成。数据操作Sawzall实现了大部分C/C++的语法操作。利用命令式语言的控制灵活性，Sawzall在处理单条数据记录（Filter阶段）时，可以灵活地写出复杂的计算逻辑，处理复杂的计算。Pig、Hive、Scope以及DryadLINQ在不同程度上实现了SQL的操作，诸如GroupBy、Join等。Hive和Scope实现的是SQL的语法，可以通过一系列嵌套的SQL语句，描述复杂的数据处理，但是失去命令式语言控制的灵活性，对于一些自定义的计算逻辑显得比较无能为力。而Pig和DryadLINQ，保存了命令式语言的灵活性，并且在描述计算流程的命令式语句中使用SQL的操作因子（GroupBy、Join、CoGroup等）来描述编译与优化一段高层次并行编程语言描述的计算，需要通过编译和优化，转化成为一个或者一组

MPI、Mapreduce或者Dryad任务，才能在分布式集群环境中进行大规模数据处理。Sawzall语言编写的代码，将会以“Filter-Aggregation”这种两阶段式的方式进行运行。Sawzall代码将被Sawzall的编译器编译成本地可执行的代码，并链接到Mapreduce并行库上，作为某个Mapreduce任务的map子任务运行。而该Mapreduce任务的reduce子任务将会运行用户在Sawzall代码中指定的Aggregation，这部分Aggregation代码是用Sawzall系统提供的，经过高度优化后的代码。同样以Mapreduce为基础的Hive和Pig这两种高级语言，则采用不同于Sawzall的方式。一段Pig代码或者一条Hive的SQL语句将被编译成一组存在依赖关系的的Mapreduce任务，并且这组Mapreduce任务将按照人物之间的依赖关系依次运行。这种编译执行的方式，类似于一个表示成有向无环图的Dryad任务编译成一组存在依赖关系的子任务进行执行。一个Dryad任务通过有向无环图已经可以表达丰富的计算。不过，使用Dryad的程序员需要自己动手去构造能表达某个计算的有向无环图。这会加重程序员的负担。而Scope和DryadLINQ的出现，正好解决了这样的问题。程序员只需要编写一条Scope的SQL语句或者一段DryadLINQ的代码，而将这条语句或者这段代码转化成相应的Dryad任务则由Scope或者DryadLINQ系统完成。与Sawzall代码只需要对Aggregation阶段代码进行优化不同的是，一段代码或者一条SQL语句在编译成一个Mapreduce或者Dryad任务时需要进行不同程度的优化。不同的系统，其优化的时期、优化的具体实现手段都不尽相同。尽管有具体实现差异的存在，这些系统还是采用着类似的优化策略，都是在关注如何最小化网络和磁盘的IO[22]这些策略如下所示：流水化操作:将尽可能多的操作因子（filter、groupby等）聚合在一个子任务中，以pipeline的方式执行，尽量减少中间结果的磁盘IO操作。合并冗余操作：将一些重复或者不必要的操作进行删除或者合并。提早过滤：在Mapreduce和Dryad中，子任务之间通常采用临时文件的方式进行通讯。将需要进行过滤的操作尽可能提前执行，可以减少子任务之间通过网络进行传输的数据量。果集尽可能小，重写操作:与“提早过滤”一样，将可以提早聚合的操作尽可能提前，使得子任务的结果集尽可能小，重写操作:将一组操作因子重写成一个或另一组更优化的操作因子进行执行。3.3.5.总结不论是Sawzall、Pig、Hive，还是Scope、LINQ，这些高层次并行数据处理语言的出现，都是想从某种角度隐藏低层次编程工具（Mapreduce、Dryad等）的复杂性。命令式语言或者声明式语言，究竟孰优孰劣，是个因人而已的问题°Pig和DryadLINQ采用了将命令式语言和声明式语言的优点进行吸收和应用，形成的针对于大规模数据处理的特殊语言，是值得学习的方法。结构化、半结构化，是大规模数据处理中的数据特征。而关系模型是用来表示这一类数据的比较好的模型。弱化关系模型的范式约束，利用简单的关系模型实现来处理大规模数据，是这类高层次编程语言在实现上的共性。不论是Map/Reduce的两阶段式计算模型，还是Dryad的有向无环图，这些语言在编译成它们相应的低层次并行计算任务时，都需要考虑对任务进行优化，最小化整个任务依赖执行过程中的网络和磁盘的IO,提高执行的效率。提早过滤、提早聚合、重写操作都是这些语言在编译优化时考虑的优化手段。3.4.案例分析:Hadoop,Pig在这一小节中，我们将对广泛应用于Yahoo!中的大规模数据处理技术Hadoopt33!和Pig进行案例分析，阐述这些系统如何实现上两节讨论的关键技术。HadoopHadoop是模仿GoogleFileSystem和GoogleMapReduce实现的一套大规模互联网应用的软件基础设施°Hadoop发起于Apache的开源项目Nutch，由DougCutting和MikeCafarella完成最初设计。06年Hadoop成为Apache独立开源项目，被广泛部署运用于Yahoo！、Facebook等互联网企业。目前，最大的Hadoop集群运行在Yahoo！，共4000台节点⑶］，用于Yahoo！广告、财经数据以及用户日志等数据的处理分析。Hadoop由两部分组成，一部分是HDFS（HadoopDistributedFileSystem），一部分是MapReduceFramework。HDFS是MapReduce的数据存储来源。HDFS按照大小为64M的数据分块来划分文件，并将这些数据分块（Chunk）分散存放在集群中的不同节点，为MapReduce提供并行计算的可能性。同时，HDFS利用多复本存放策略来保证了数据的可靠性、可用性，并提供较高的数据IO吞吐率。在一个Hadoop集群中，MRFramework由一个JobTracker节点和多个TaskTracker节点构成。JobTracker用于任务划分、任务调度；而TaskTracker用于接收来自于JobTracker分配的Map或者Reduce任务，并执行这些任务，同时将任务的状态回馈给JobTracker0Hadoop集群的部署采用“disk-per-node”的模型，将存储和计算部署在集群中相同的节点上。因此Hadoop中用于TaskTracker的节点也是HDFS的存储节点。在用户提交任务到JobTracker后，JobTracker会向HDFS查询任务所需数据的分块信息以及相应存储节点的信息，并将任务按照分块信息划分成可以并行执行Map或者ReduceTask，分发给相信存储节点上的TaskTracker程序，由TaskTracker程序在存储节点本地执行Map或者Reduce任务。这种将计算移动到存储节点的方式，减少了网络IO负载压力，并提供了计算的并行性。任务的划分由JobTracker根据数据的存储信息自动进行计算完成°MapTask的输出结果被保存在TaskTracker节点的本地磁盘，并由TaskTracker内嵌的HttpServer向ReduceTask提供读取服务。ReduceTask利用Http协议向MapTask读取所需要处理的部分数据，并在本地完成对这些数据的排序，然后执行用户定义的Reduce操作，并将结果输出保存到HDFS中。Task的临时结果和最终结果均被保存在文件系统（本地文件系统和HDFS）中，HadoopMR可以方便地通过Taskre-execute的方式进行失效恢复。在Hadoop中，JobTracker与TaskTracker之间通过Heartbeat来监控Task的执行状况。当JobTracker发现某一个Task失效时，JobTracker通过re-execute该Task来完成恢复；当JobTracker发现某个TaskTracker失效,JobTracker将重新调度该TaskTracker上未完成执行的Task和部分已经完成执行的MapTask（TaskTracker失效可能是节点崩溃，那些已经完成执行但输出数据还未被ReduceTask读取的MapTask的输出数据就会丢失）来完成失效恢复。移动计算到存储节点，按照存储信息自动进行任务划分，简单的通信手段和有效的容错机制，Hadoop提供一套较为完善的大规模数据存储处理方案。PigPig是基于Hadoop实现的一套用于大规模数据处理的系统，使用PigLatin作为其高级处理语言。它是由Yahoo!在2006年夏天发起的研究项目，目的在于提供一种比Map-Reduce丰富的高层次语言，使程序员更加方便进行大规模数据处理应用的开发134］。PigLatin是一门吸收了SQL语法的过程式语言。它保存了过程式语言的灵活性，同时也很大程度上吸纳了声明式语言易于进行数据处理描述的特点。PigLatin采用一种灵活的嵌套式数据模型。这种数据模型与关系型数据库所采用的数据模型不同。在传统数据中，数据是按照表格的方式平坦组织。数据库表由一组记录组成，每条记录有固定的属性，每个属性值只能是数据库规定的原子数据(如int、double等)。而在Pig中，记录的域值允许为非原子的嵌套数据类型，如map、set、tuple等。这与互联网应用以嵌套数据结构存储数据的方式相近(搜索引擎中的爬虫以set的方式输出每个url对应的outlinkurls)，更符合程序员的思维，也允许程序员通过编写UDF(UserDefinedFunctions)来实现丰富于SQL的操作。一段PigLatin代码通常由一组PigLatin语句构成。每条PigLatin语句使用类似SQL的操作因子(Group、CoGroup、Order、Join等)来描述数据的处理方式。每段PigLatin代码需要经过三次编译，最终转换成一组Map/Reduce任务在Hadoop上进行执行完成。这三次编译分别为逻辑编译(LogicalCompile)>物理编译(PhysicalCompile)>MR编译(MapReduceCompile)0在逻辑编译阶段，Pig解释器将解析用户提交的PigLatin代码，同时检查语法和输入文件的正确性，然后生成一个逻辑执行计划(LogicalPlan)o逻辑编译阶段是语法级别的编译过程，与底层平台无关。生成的LogicalPlan将被交给PigCompiler进行下一步编译。在这个阶段，PigCompiler将会遍历LogicalPlan，进行一些操作因子的调整重写，形成物理执行计划(PhysicalPlan)o文献［22］提到优化手段将会被应用物理编译阶段。最后，优化后的PhysicalPlan将被PigMRCompiler编译成一组高效的MapReduce任务，在Hadoop上按依赖关系执行。目前Pig被广泛应用于Yahoo!AdIndexing、AdClickFeedback、WebMap等多个商业产品中网。4.总结Dynamo、BigTable等新兴数据管理系统的出现，是互联网应用在海量数据存储管理上的一个突破。它改善了互联网应用使用传统关系型数据库作存储其扩展性差的状况，为工业界、学术界探索海量数据存储提供了新的思路。同时，MapReduce、Dryad等并行编程框架的出现，使人们开始审视传统并行计算模型在互联网应用中的使用性，也为DISC技术的研究打开了局面。数据划分、负载平衡、容错机制、自动任务划分、编译优化等传统研究问题在互联网应用背景下重新被提出或者应用。而且，对于海量数据管理和海量数据处理的研究在现阶段还是相对独立的两个方向。即使，在Yahoo!、Facebook这些大型互联网公司中，如果要对海量数据管理系统(PNUTS、Cassandra)中的数据进行处理，都需要首先将数据导入到海量数据处理系统(Hadoop)中。数据管理和处理的整合，也是海量数据未来的挑战之一。参考文献［1］海量数据的挑战./index.asp?node1=12&node2=93&node3=124&node4=227&articleID=21348&page=2［2］数据原理编程与性能.P19［3］Shard(DatabaseArchitecture)./wiki/Shard_Cdatabase_architecture)G.DeCandiaetal.Dynamo:Amazon’shighlyavailablekey-valuestore.InSOSP,2007.F.Changetal.Bigtable:Adistributedstoragesystemforstructureddata.InOSDI,2006.BrianFetal.PNUTS:Yahoo!'sHostedDataServingPlatform.InVLDB,2008.AdamSilbersteinetal.EfficientBulkInsertionintoaDistributionOrderedTable.InSIGMOD,2008.Karger.Detal.Consistenthashingandrandomtrees.InProceedingsofthetwenty-ninthannualACMsymposiumonTheoryofcomputing,1997.MikeBurrows.TheChubbylockserviceforloosely-coupleddistributedsystems.InOSDI,2006.SanjayGhemawatetal.TheGoogleFileSystem.InSOSP,2003.ZhengShao.HadoopHiveGeneralIntroduction.PresentedtoHadoopSalon,Beijing,Nov,2008./hadoop/cgi-bin/moin.cgi/HadoopBeijingMeeting20081123_slides7action=AttachFile&do=get&target=Hadoop_Hive_General_Introduction_zshao(11-19-15-05-18).pdfMessagePassingInterface./wiki/Message_Passing_InterfaceJ.DeanandS.Ghemawat.MapReduce:Simpli_eddataprocessingonlargeclusters.InProc.OSDI,2004.MichaelIsardetal.Dryad:distributeddata-parallelprogramsfromsequentialbuildingblocks.InEuroSys,2007.RalfLammeletcal.Google’sMapReduceProgrammingModel一Revisited.PublishedinSCP.OLSTONetcal.PigLatin:Anot-so-foreignlanguagefordataprocessing.InSIGMOD,2008.ApacheHive./hive/Cascading./RonnieChaikenetcal.SCOPE:EasyandEfficientPara