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

互联网海量数据存储及处理调研综述摘要本文主要针对互联网应用中出现的新兴的海量数据存储和处理系统展开讨论，对比新兴系统与传统数据技术的差异，以及这些系统之间实现技术的不同特点，并总结出相应的关键技术问题。近些年来，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亿多次；并且每天都有大量新用户注册，交易也在无时无刻进行中[1]。这些信息保存在存储设备上，便是高速膨胀的海量数据。同样的问题也出现在Google、Facebook、Flickr等互联网应用上，如表1所示。国家智能计算机研究开发中心2应用类型应用名称规模搜索引擎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不同互联网应用的规模[1,11,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]。与金融行业的数据操作不同的是，互联网应用的数据操作没有很强的事务特性，也没有严格的一致性要求，但对读写时延的有互联网海量数据存储及处理调研综述3一定要求（读写时延影响互联网应用的用户体验）。图1GrowthinDurationofWebVideos[38]互联网应用的海量数据特性，对数据存储和处理提出了新的挑战。这些挑战概括如下：1）TB级甚至PB级的存储系统，以适应海量数据的需求。2）良好的扩展性。在不中断服务的情况下，通过简单添置机器或者磁盘存储来扩展系统，满足不断增长的数据和用户群体需求。3）低时延、高吞吐的存储系统性能。4）丰富的存储类型，以满足互联网应用中结构化、半结构化甚至非结构化数据的存储需求。5）灵活简单的并行编程模型进行海量数据处理，隐藏分布式环境下数据分布、容错等复杂性。在这样的挑战下，一些传统技术已经开始不能胜任互联网应用的需求。新兴的海量数据存储、处理系统也相继涌现。在接下来的两个部分，文章将从数据存储和数据处理两个角度，讨论传统技术存在的问题，介绍一些新型系统，并分析这些新型系统在解决海量数据存储和处理时遇到的问题以及相应的解决方案。2.数据存储目前，大部分互联网应用仍然使用传统关系型数据库进行数据的存储管理，并通过编写SQL语句或者MPI程序来完成对数据的分析处理。这样的系统在用户规模、数据规模都相对比较小的情况下，可以高效地运行。但是，随着用户数量、存储管理的数据量不断增加，许多热门的互联网应用在扩展存储系统以应对更大规模的数据量和满足更高的访问量时都遇到了问题[23,24,26,27,28,29,36]。2.1.传统关系型数据库传统关系型数据库在数据存储管理的发展史上是一个重要的里程碑。在互联网时代以前，数据的存储管理应用主要集中在金融、证券等商务领域中。这类应用主要面向结构化数据，聚焦于便捷的数据查询分析能力、严格的事务处理能力、多用户并发访问能力以及数据安全性的保证。而传统关系型数据库正是针对这种需求而设计，并以其结构化的数据组织形式，严格的一致性模型，简单便捷的查询语言，强大的数据分析能力以及较高的程序与数据独立性等优点被广泛应用。然而互联网时代的到来，数据已超出关系型数据库的管理范畴，电子邮件、超文本、Blog、Tag以及图片、音视频等各种非结构化数据逐渐成为了海量数据的重要组成部分。面向结构化数据存储的关系型数据库已经不能满足互联网数据快速访问、大规模数据分析的需求。国家智能计算机研究开发中心4应用场景的局限性传统数据库在设计上，着眼于面向结构化的数据，致力于事务处理，要求保证严格的一致性，这些特性符合传统的金融、经济等应用场景。然而互联网应用主要面向于半结构化、非结构化的数据，这些应用大多没有事务特性，也不需要很严格的一致性保证。虽然传统数据库的厂商也针对海量数据应用特点提出了一系列改进方案，但是由于并不是从互联网应用的角度去寻找问题，使得传统数据库在应对互联网海量数据存储上效果并不理想。关系模型束缚对海量数据的快速访问能力关系模型是一种按内容访问的模型[2]。即在传统的关系型数据库中，根据列的值来定位相应的行。这种访问模型，将在数据访问过程中引入耗时的IO，从而影响快速访问的能力。虽然，传统的数据库系统可以通过分区的技术（水平分区和垂直分区），来减少查询过程中数据IO的次数以缩减响应时间，提高数据处理能力；但是在海量数据的规模下，这种分区所带来的性能改善并不显著。关系模型中规格化的范式设计与web2.0的很多特性相互矛盾[26]。以Tag为例，Tag的分类模型是一种复杂的多对多关系模型。传统数据库的范式设计要求消除冗余性，因此Tag和内容将会被存储在不同的表中，导致对于Tag的操作需要跨表完成（在分区的情况下，可能需要跨磁盘、跨机器操作），性能低下。缺乏对非结构化数据的处理能力传统的关系型数据库对数据的处理只局限于某些数据类型，比如数字、字符、字符串等，对非结构化数据（图片、音频等）的支持较差。然而随着用户应用需求的提高、硬件技术的发展和互联网上多媒体交流方式的推广，用户对多媒体处理的要求从简单的存储上升为识别、检索和深入加工，因此如何处理庞大的声音、图像、和视频、E-mail等复杂数据类型，是传统数据库面临的一个问题。扩展性差在海量规模下，传统数据库面临着一个致命问题，就是其扩展性问题。解决数据库扩展性问题，通常有两种方式：Scaleup和Scaleout。这两种扩展方式分别从两个不同的维度来解决数据库在海量数据下的压力问题。Scaleup，简而言之就是通过硬件升级，提升速度来解决缓解压力问题；而Scaleout则是通过将海量数据按照一定的规则进行划分，将原来集中存储的数据分散到不同的物理数据库服务器上。Sharding[3]正是在Scaleout的理念指导下，传统数据库提出了一种解决扩展性的方案。Sharding通过叠加相对廉价设备的方式实现存储和计算能力的扩展，其主要目的是为突破单节点数据库服务器的I/O能力限制，提高快速访问能力，以及提供更大的读写带宽。但是，在互联网的应用场景下，这种解决扩展性的方案仍然存在着一定局限性制。比如，数据存储在多个节点，需要考虑负载均衡的问题，这需要互联应用需要实现复杂的负载自动平衡机制，引入较高代价；数据库严格的范式规定，使得表示成关系模型的数据很难进行划分到不同的shard中；同时，还存在一些数据可靠性和可用性的问题。2.2.新兴数据存储系统在传统关系型数据库已不能满足互联网应用需求的情况下，开始出现一些针对结构化、半结构化甚至非结构化数据的管理系统。在这些系统中，数据通常采用多副本的方式进行存储，保证系统的可用性和并发性；采用较弱的一致性模型（如最终一致性模型），在保证低延时的用户相应的同时，维持复本之间的一致状态；并且都提供良好的负载平衡策略和容错手段。按照数据管理方式划分，这些新兴的数据管理系统可以归为两大类：（一）集中式数据管理系统互联网海量数据存储及处理调研综述5这类系统采用传统的serverfarm架构。整个系统需要一个主控节点维护各从节点的元信息，是一种集中控制的管理手段。其优势在于，集中管理的方式人为可控且维护方便，在处理数据同步时更为简单。其劣势在于，系统存在单点故障的危险。这类系统