中国科学:信息科学第45卷第1期
(3)冗余消除(Redundancyelimination)
数据冗余是指数据的重复或过剩,这是许多数据集的常见问题.数据冗余无疑会增加传输开销,浪费存储空间,导致数据不一致,降低可靠性.因此许多研究提出了数据冗余减少机制,例如冗余检测[88]和数据压缩[89].这些方法能够用于不同的数据集和应用环境,提升性能,但同时也带来一定风险.例如,数据压缩方法在进行数据压缩和解压缩时带来了额外的计算负担,因此需要在冗余减少带来的好处和增加的负担之间进行折中.
由广泛部署的摄像头收集的图像和视频数据存在大量的数据冗余.在视频监控数据中,大量的图像和视频数据存在着时间、空间和统计上的冗余[90].视频压缩技术被用于减少视频数据的冗余,许多重要的标准(如MPEG-2,MPEG-4,H.263,H.264/AVC)已被应用以减少存储和传输的负担[91].Tsai等在[92]中研究了通过视频传感器网络进行智能视频监控的视频压缩技术.通过发现场景中背景和前景目标相联系的情境冗余,他们提出了一种新的冗余减少方法.
对于普遍的数据传输和存储,数据去重(datadeduplication)技术[93]是专用的数据压缩技术,用于消除重复数据的副本.在存储去重过程中,一个唯一的数据块或数据段将分配一个标识并存储,该标识会加入一个标识列表.当去重过程继续时,一个标识已存在于标识列表中的新数据块将被认为是冗余的块.该数据块将被一个指向已存储数据块指针的引用替代.通过这种方式,任何给定的数据块只有一个实例存在.去重技术能够显著地减少存储空间,对大数据存储系统具有非常重要的作用.除了前面提到的数据预处理方法,还有一些对特定数据对象进行预处理的技术,如特征提取技术,在多媒体搜索[94]和DNS分析[95,96]中起着重要的作用.这些数据对象通常具有高维特征矢量.数据变形技术[97]则通常用于处理分布式数据源产生的异构数据,对处理商业数据非常有用.Gunter在文献[98]中提出了MapLan,对瑞士国家银行的调查信息进行影射和变形.Wang等在[99]中提出了一种在分布式存储系统中异构感知的数据重生成机制,在异构链路上传递最少的数据以保持数据的完整性.
然而,没有一个统一的数据预处理过程和单一的技术能够用于多样化的数据集,必须考虑数据集的特性、需要解决的问题、性能需求和其他因素选择合适的数据预处理方案.
7阶段III:数据存储
大数据系统中的数据存储子系统将收集的信息以适当的格式存放以待分析和价值提取.为了实现这个目标,数据存储子系统应该具有如下两个特征:
?存储基础设施应能持久和可靠地容纳信息;
?存储子系统应提供可伸缩的访问接口供用户查询和分析巨量数据.
从功能上,数据存储子系统可以分为硬件基础设施和数据管理软件.
7.1
存储基础设施
硬件基础设施实现信息的物理存储,可以从不同的角度理解存储基础设施.首先,存储设备可以根据存储技术分类.典型的存储技术有如下几种.
?随机存取存储器(Randomaccessmemory,RAM):是计算机数据的一种存储形式,在断电时将丢
失存储信息.现代RAM包括静态RAM、动态RAM和相变RAM.
17
李学龙等:大数据系统综述
I/O requests
Virtualization layerSSDSASArray
STAT图6基于SSD的多层存储系统
Figure6
SSD-basedmulti-layerstoragesystem
?磁盘和磁盘阵列:磁盘(如硬盘驱动器HDD)是现代存储系统的主要部件.HDD由一个或多个快
速旋转的碟片构成,通过移动驱动臂上的磁头,从碟片表面完成数据的读写.与RAM不同,断电后硬盘仍能保留数据信息,并且具有更低的单位容量成本,但是硬盘的读写速度比RAM读写要慢得多.由于单个高容量磁盘的成本较高,因此磁盘阵列将大量磁盘整合以获取高容量、高吞吐率和高可用性.
?存储级存储器:是指非机械式存储媒体,如闪存.闪存通常用于构建固态驱动器SSD,SSD没有
类似HDD的机械部件,运行安静,并且具有更小的访问时间和延迟.但是SSD的单位存储成本要高于HDD.
这些存储设备具有不同的性能指标,可以用来构建可扩展的、高性能的大数据存储子系统.文献[100]更为详细地讨论了存储设备的发展.文献[101,102]则结合HDD和SSD的优点提出了一种混合层次存储系统,该存储系统包括一个大容量的硬盘和一个SSD缓存,经常访问的数据存放在SSD缓存中,从而提高存取性能.图6显示了一个典型的基于SSD的多层存储系统,该系统由三个部件构成,即I/O请求队列、虚拟化层和阵列[103].目前,IBM,EMC,3PAR等公司的基于SSD的商用多层存储系统已能获得较好的性能.
其次,可以从网络体系的观点理解存储基础设施[104],存储子系统可以通过不同的方式组织构建.
?直接附加存储(Directattachedstorage,DAS):存储设备通过主机总线直接连接到计算机,设备和
计算机之间没有存储网络.DAS是对已有服务器存储的最简单的扩展.
?网络附件存储(Networkattachedstorage,NAS):NAS是文件级别的存储技术,包含许多硬盘驱动
器,这些硬盘驱动器组织为逻辑的冗余的存储容器.和SAN相比,NAS可以同时提供存储和文件系统,并能作为一个文件服务器.
?存储区域网络(Storageareanetwork,SAN):SAN通过专用的存储网络在一组计算机中提供文件
块级别的数据存储.SAN能够合并多个存储设备,例如磁盘和磁盘阵列,使得它们能够通过计算机直接访问,就好象它们直接连接在计算机上一样.
这三种存储技术的存储网络体系架构如图7所示,SAN具有最复杂的网络架构,并依赖于特定的存储网络设备.
最后,尽管已有的存储系统架构得到了深入的研究,但是却无法直接应用于大数据系统中.为了适应大数据系统的“4Vs”特性,存储基础设施应该能够向上和向外扩展,以动态配置适应不同的应用.
18
中国科学:信息科学第45卷第1期
Server
ServerSCSI or fiber channelServer
LAN or WAN
Server
ServerServerServerStorage area networkDisk device
(a)
RAIDNetwork attached storage
(b)
RAID(c)
RAID图7存储系统网络架构
Figure7
Networkarchitectureofstoragesystem.(a)DAS;(b)NAS(?leoriented);(c)SAN(blockoriented)
Programming modelMapReducePregelDryadGraphLabData baseBigTableDynamoMongoDBSpannerFile system
GFSHayStackTFS
图8数据管理技术
Figure8
Datamanagementtechnology
一个解决这些需求的技术是云计算领域提出的存储虚拟化[105].存储虚拟化将多个网络存储设备合并为单个存储设备.目前可以在SAN和NAS架构上实现存储虚拟化[106].基于SAN的存储虚拟化在可扩展性、可靠性和安全方面能够比基于NAS的存储虚拟化具有更高的性能.但是SAN需要专用的存储基础设施,从而带来较高的成本.
7.2数据管理框架
数据管理框架解决的是如何以适当的方式组织信息以待有效地处理.在大数据出现之前,数据管理框架就得到了较为广泛的研究.本文从层次的角度将数据管理框架划分为3层:文件系统、数据库技术和编程模型,如图8所示.
(1)文件系统
文件系统是大数据系统的基础,因此得到了产业界和学术界的广泛关注.Google为大型分布式数据密集型应用设计和实现了一个可扩展的分布式文件系统GFS[21].GFS运行在廉价的商用服务器上,为大量用户提供容错和高性能服务.GFS适用于大文件存储和读操作远多于写操作的应用.但是GFS具有单点失效和处理小文件效率低下的缺点,Colossus[107]改进了GFS并克服了这些缺点.此
19
李学龙等:大数据系统综述
Key K
AGBNodes B, C and D store keys in range including K
FCED图9Dynamo环中键的分割和复制
Figure9
PartitionandreplicationofkeysinDynamoring
外,其他的企业和研究者们开发了各自的文件存储解决方案以适应不同的大数据存储需求.HDFS17)和Kosmosfs18)是GFS的开源产物;Microsoft开发了Cosmos支持其搜索和广告业务[108];Facebook实现了Haystack存储海量的小照片[109];淘宝则设计了两种类似的小文件分布式文件系统:TFS19)和FastFS20).由于分布式文件系统已较为成熟,因此本文将重点介绍数据管理框架的其余两层.
(2)数据库技术
数据库技术已经经历了30多年的发展,不同的数据库系统被设计用于不同规模的数据集和应用.传统的关系数据库系统难以解决大数据带来的多样性和规模的需求.由于具有模式自由、易于复制、提供简单API、最终一致性和支持海量数据的特性,NoSQL数据库逐渐成为处理大数据的标准.随后将根据数据模型的不同,讨论三种主流的NoSQL数据库:键值(key-value)存储数据库、列式存储数据库和文档存储数据库.
(a)键值存储数据库
键值存储是一种简单的数据存储模型,数据以键值对的形式储存,键是唯一的.近年出现的键值存储数据库受到Amazon公司的Dynamo影响特别大[110].在Dynamo中,数据被分割存储在不同的服务器集群中,并复制为多个副本.可扩展性和持久性(durability)依赖于以下两个关键机制.
?分割和复制:Dynamo的分割机制基于一致性哈希技术[111],将负载分散在存储主机上.哈希函数
的输出范围被看作是一个固定的循环空间或“环”.系统中的每个节点将随机分配该空间中的一个值,表示它在环中的位置.通过哈希标识数据项的键,可以获得该数据项在环中对应的节点.Dynamo系统中每条数据项存储在协调节点和N?1个后继节点上,其中N是实例化的配置参数.如图9所示,节点B是键k的协调节点,数据存储在节点B同时复制在节点C和D上.此外,节点D将存储在(A,B],(B,C]和(C,D]范围内的键.
?对象版本管理:由于每条唯一的数据项存在多个副本,Dynamo允许以异步的方式更新副本并提
供最终一致性.每次更新被认为是数据的一个新的不可改变的版本.一个对象的多个版本可以在系统中共存.
17)18)19)20)
HadoopDistributedFileSystem.http://hadoop.apache.org/docs/r1.0.4/hdfsdesign.html.https://code.google.com/p/kosmosfs/.
TaobaoFileSystem.http://code.taobao.org/p/tfs/src/.
FastDistributedFileSystem.https://code.google.com/p/fastdfs/.
20
