互联网海量数据存储及处理的调研综述Word格式.doc
《互联网海量数据存储及处理的调研综述Word格式.doc》由会员分享，可在线阅读，更多相关《互联网海量数据存储及处理的调研综述Word格式.doc（21页珍藏版）》请在冰点文库上搜索。
Google
总量：
10KB/doc*20Bdocs=200TB
每30天做一次索引：
200TB/30days=6TB/day
SNS
Facebook
（2008）
PageView：
0.5KB/pageviewevents*3Bpageviewevents/day=1.5TB/day
Relationship：
100Musers*5events*100feed/event*0.1KB/feed=5TB/day
图片共享
（2007）
65亿张原始图片，每张图片保存为4~5个不同尺寸
图片总量达300亿张，共540TB
请求数：
47.5万张/秒（读）1亿张/周（上传）
Flickr
原始图片存储总量达2PB
40亿张/天（读）40万张/天（上传）
视频共享
Youtube
视频总量达600万个，共45TB
观看率超过一亿次/天，上传率达65000次/天
电子商务
淘宝
4500万注册用户，9000万件商品，2亿次/天页面点击率
eBay
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]。
与金融行业的数据操作不同的是，互联网应用的数据操作没有很强的事务特性，也没有严格的一致性要求，但对读写时延的有一定要求（读写时延影响互联网应用的用户体验）。
图1GrowthinDurationofWebVideos[38]
互联网应用的海量数据特性，对数据存储和处理提出了新的挑战。
这些挑战概括如下：
1）TB级甚至PB级的存储系统，以适应海量数据的需求。
2）良好的扩展性。
在不中断服务的情况下，通过简单添置机器或者磁盘存储来扩展系统，满足不断增长的数据和用户群体需求。
3）低时延、高吞吐的存储系统性能。
4）丰富的存储类型，以满足互联网应用中结构化、半结构化甚至非结构化数据的存储需求。
5）灵活简单的并行编程模型进行海量数据处理，隐藏分布式环境下数据分布、容错等复杂性。
在这样的挑战下，一些传统技术已经开始不能胜任互联网应用的需求。
新兴的海量数据存储、处理系统也相继涌现。
在接下来的两个部分，文章将从数据存储和数据处理两个角度，讨论传统技术存在的问题，介绍一些新型系统，并分析这些新型系统在解决海量数据存储和处理时遇到的问题以及相应的解决方案。
2.数据存储
目前，大部分互联网应用仍然使用传统关系型数据库进行数据的存储管理，并通过编写SQL语句或者MPI程序来完成对数据的分析处理。
这样的系统在用户规模、数据规模都相对比较小的情况下，可以高效地运行。
但是，随着用户数量、存储管理的数据量不断增加，许多热门的互联网应用在扩展存储系统以应对更大规模的数据量和满足更高的访问量时都遇到了问题[23,24,26,27,28,29,36]。
2.1.传统关系型数据库
传统关系型数据库在数据存储管理的发展史上是一个重要的里程碑。
在互联网时代以前，数据的存储管理应用主要集中在金融、证券等商务领域中。
这类应用主要面向结构化数据，聚焦于便捷的数据查询分析能力、严格的事务处理能力、多用户并发访问能力以及数据安全性的保证。
而传统关系型数据库正是针对这种需求而设计，并以其结构化的数据组织形式，严格的一致性模型，简单便捷的查询语言，强大的数据分析能力以及较高的程序与数据独立性等优点被广泛应用。
然而互联网时代的到来，数据已超出关系型数据库的管理范畴，电子邮件、超文本、Blog、Tag以及图片、音视频等各种非结构化数据逐渐成为了海量数据的重要组成部分。
面向结构化数据存储的关系型数据库已经不能满足互联网数据快速访问、大规模数据分析的需求。
l应用场景的局限性
传统数据库在设计上，着眼于面向结构化的数据，致力于事务处理，要求保证严格的一致性，这些特性符合传统的金融、经济等应用场景。
然而互联网应用主要面向于半结构化、非结构化的数据，这些应用大多没有事务特性，也不需要很严格的一致性保证。
虽然传统数据库的厂商也针对海量数据应用特点提出了一系列改进方案，但是由于并不是从互联网应用的角度去寻找问题，使得传统数据库在应对互联网海量数据存储上效果并不理想。
l关系模型束缚对海量数据的快速访问能力
关系模型是一种按内容访问的模型[2]。
即在传统的关系型数据库中，根据列的值来定位相应的行。
这种访问模型，将在数据访问过程中引入耗时的IO，从而影响快速访问的能力。
虽然，传统的数据库系统可以通过分区的技术（水平分区和垂直分区），来减少查询过程中数据IO的次数以缩减响应时间，提高数据处理能力；
但是在海量数据的规模下，这种分区所带来的性能改善并不显著。
关系模型中规格化的范式设计与web2.0的很多特性相互矛盾[26]。
以Tag为例，Tag的分类模型是一种复杂的多对多关系模型。
传统数据库的范式设计要求消除冗余性，因此Tag和内容将会被存储在不同的表中，导致对于Tag的操作需要跨表完成（在分区的情况下，可能需要跨磁盘、跨机器操作），性能低下。
l缺乏对非结构化数据的处理能力
传统的关系型数据库对数据的处理只局限于某些数据类型，比如数字、字符、字符串等，对非结构化数据（图片、音频等）的支持较差。
然而随着用户应用需求的提高、硬件技术的发展和互联网上多媒体交流方式的推广，用户对多媒体处理的要求从简单的存储上升为识别、检索和深入加工，因此如何处理庞大的声音、图像、和视频、E-mail等复杂数据类型，是传统数据库面临的一个问题。
l扩展性差
在海量规模下，传统数据库面临着一个致命问题，就是其扩展性问题。
解决数据库扩展性问题，通常有两种方式：
Scaleup和Scaleout。
这两种扩展方式分别从两个不同的维度来解决数据库在海量数据下的压力问题。
Scaleup，简而言之就是通过硬件升级，提升速度来解决缓解压力问题；
而Scaleout则是通过将海量数据按照一定的规则进行划分，将原来集中存储的数据分散到不同的物理数据库服务器上。
Sharding[3]正是在Scaleout的理念指导下，传统数据库提出了一种解决扩展性的方案。
Sharding通过叠加相对廉价设备的方式实现存储和计算能力的扩展，其主要目的是为突破单节点数据库服务器的I/O能力限制，提高快速访问能力，以及提供更大的读写带宽。
但是，在互联网的应用场景下，这种解决扩展性的方案仍然存在着一定局限性制。
比如，数据存储在多个节点，需要考虑负载均衡的问题，这需要互联应用需要实现复杂的负载自动平衡机制，引入较高代价；
数据库严格的范式规定，使得表示成关系模型的数据很难进行划分到不同的shard中；
同时，还存在一些数据可靠性和可用性的问题。
2.2.新兴数据存储系统
在传统关系型数据库已不能满足互联网应用需求的情况下，开始出现一些针对结构化、半结构化甚至非结构化数据的管理系统。
在这些系统中，数据通常采用多副本的方式进行存储，保证系统的可用性和并发性；
采用较弱的一致性模型（如最终一致性模型），在保证低延时的用户相应的同时，维持复本之间的一致状态；
并且都提供良好的负载平衡策略和容错手段。
按照数据管理方式划分，这些新兴的数据管理系统可以归为两大类：
（一）集中式数据管理系统
这类系统采用传统的serverfarm架构。
整个系统需要一个主控节点维护各从节点的元信息，是一种集中控制的管理手段。
其优势在于，集中管理的方式人为可控且维护方便，在处理数据同步时更为简单。
其劣势在于，系统存在单点故障的危险。
这类系统包括Google的Bigtable和Yahoo！
的Pnuts。
nBigtable
Bigtable是Google开发的一套结构化存储系统[5]。
数据以多维顺序表的方式进行存储。
整个系统采用传统的serverfarm形式，由一个主控服务器和多个子表服务器构成，并使用分布式锁服务Chubby进行容错等管理。
nPnuts
Pnuts是Yahoo内部使用的，用于跨数据中心进行部署的大规模并行数据管理系统[6]。
它与bigtable类似的集中管理体系。
它支持顺序表和哈希表两种方式进行结构化数据的组织存储，并通过一定的优化手段在保证用户低延时访问服务的同时，提高数据批量载入的性能[7]。
（二）非集中式数据管理系统
系统中各节点无主从之分，各节点通过相应的通信机制相互感知，自我管理性较强。
其优势在于：
由于没有主控节点，因而避免单点失效带来的危险；
不需要过多人工干预。
其劣势在于：
由于无主控节点因而对于一些元数据更新操作，实现较为复杂；
不易进行人工控制。
Amazon的Dynamo和Facebook的Cassandra则采用这种方式。
nDynamo
Dynamo是一个基于分布式哈希的去中心化的大规模数据管理系统[4]。
在Dynamo中，数据按照key-value进行形式，主要面向原始数据的存储。
这种架构下，系统中每个节点都能相互感知，自我管理性能较强，没有单点失效。
nCassandra
Cassandra是Facebook开发的一套采用P2P技术实现的结构化数据存储系统[25]。
与Dynamo有所不同的是，Cassandra采用类似Bigtable的多维表数据模型进行数据的存储管理。
在下面的章节，我们将探讨互联网背景下海量存储的关键技术问题，并对比这些系统在解决这些问题上所采用的技术手段。
2.3.关键技术分析
扩展性是互联网应用需求下海量数据存储的首要问题。
构建一个TB级甚至PB级的数据存储系统，需要有自适应的数据划分方式、良好的负载均衡策略来满足数据、用户规模的不断增长需求。
同时，在保证系统可靠性的同时，需要权衡数据一致性与数据可用性，来满足互联网应用低延时、高吞吐率的特点。
在这一节中，我们主要从数据划分、数据一致性与可用性、负载均衡、容错机制等四个主要方面来讨论构建一个高可靠、可扩展的海量数据存储系统的关键问题和技术。
2.3.1.数据划分
在分布式环境下，数据存储需要跨越多个存储单元。
如何进行数据的划分是影响扩展性，负载平衡，以及系统性能的关键问题。
为了提供低延时的系统响应，抑制系统性能的瓶颈，系统必须在用户请求到来时将请求进行合理分发。
现有的海量数据管理系统主要采用哈希映射和顺序分裂这两种方式。
在互联网应用中，数据通常以key-value方式进行组织以适应数据的多样性和处理的灵活性。
哈希映射是根据数据记录的key值进行哈希，根据哈希值将记录映射到相应的存储单元。
但是这种数据划分方式带来的性能收益依赖于哈希算法的优劣。
而顺序分裂则是一种渐进式的数据划分方式。
数据按key排序写入数据表中，数据表在其大小达到阈值后进行分裂，分裂后的数据将被分配到不同的节点上去提供服务。
这样，新流入的数据根据key找到相应的分片插入表中。
Dynamo和Cassandra都采用了一致性哈希的方式进行数据划分。
这种方式在数据流入时就将数据均匀地映射到相应的存储单元，因而最大限度地避免系统的热点存在。
同时一致性哈希算法，也为系统带来了良好的扩展性。
而B igtable则使用顺序分裂的方式进行数据划分。
这种渐进式的数据划分方式，可以有效利用系统资源，并能提供很好的扩展性。
但是对于某个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来监控各个tabletserver上的访问负载状态，利用master调度管理tablet的分裂和迁移将访问压力均匀地分散到各个tabletserver上。
由于BigTable采用分布式文件系统作为数据的底层存储，tablet的分裂和迁移过程中并不涉及到存储数据的迁移操作，以一种巧妙的方式避免了数据均衡的问题。
在集中式管理系统中，PNUTS也采用类似的方式进行访问压力的均衡。
不同的是，采用本地文件系统或者本地数据库系统的PNUTS在进行tablet的分裂和迁移时，需要进行存储数据迁移。
有效的数据划分方式为系统扩展性提供了一个基础，但是同时也给系统带来了负载均衡的问题。
通过虚拟化节点或者表分裂等方式改变数据分布格局，均衡访问负载的同时，尽可能减少存储数据迁移量或者避免数据迁移，是海量存储系统的一个挑战。
2.3.4.容错
容错是分布式系统健壮性的标志。
节点的失效侦测以及失效恢复已经成为保证系统的可用性、可靠性的关键问题。
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所示。
Dynamo
Bigtable
Cassandra
Pnuts
一致性模型
最终一致性
较弱一致性
Record-leveltimeline一致性
数据管理方式
非集中化
集中式。
集中式
数据模型
原始数据，Key-Value
多维表
类似RDBMS的表
数据划分方式
一致性哈希。
顺序表分裂
一致性哈希
顺序表、哈
升级会员 