大数据存储架构和算法研究综述

杨俊杰　廖卓凡　冯超超

摘要：

随着大数据计算需求的增长，集群的处理速度需要得到快速的提升，然而目前大数据处理框架的处理性能已逐渐满足不了这种快速增长的需求。由于集群的存储架构是分布式存储，因此数据的存放在大数据处理过程中成为影响集群的处理性能的因素之一。首先，对当今的分布式文件存储系统的结构进行了介绍；接着，根据不同的优化目标，例如减少网络负载、负载均衡、降低能耗和高容错性等，对近年国内外大数据存储算法的研究进行了总结，分析和对比了已有算法的优点以及存在的问题；最后，对大数据存储架构和优化算法设计的挑战和未来研究方向作了展望。

关键词：

大数据；数据部署；分布式文件系统；MapReduce；Hadoop

中图分类号：

TP393

文献标志码：A

Abstract：

With the growing demand of big data computing， the processing speed of the cluster needs to be improved rapidly. However， the processing performance of the existing big data framework can not satisfy the requirement of the computing development gradually. As the framework of the storage is distributed， the placement of data to be processed has become one of the key factors affecting the performance of the cluster. Firstly， the current distributed file system structure was introduced. Then the popular data placement algorithms were summarized and classified according to different optimization goals， such as network load balance， energy saving and fault tolerance. Finally， future challenges and research directions in the area of storage framework and algorithms were presented.

英文關键词Key words：

big data； data placement； distributed file system； MapReduce； Hadoop

0引言

随着互联网的高速发展和迅速普及，我们已经进入了一个信息爆炸型的时代，大数据处理的需求正在迅速增加，在科学、工业、商业等领域，信息处理量达到TB级甚至PB级已是正常现象。因此，寻求优秀的大数据处理模型对于处理数据密集型应用是非常重要的。

相对于传统的数据，人们将大数据的特征总结为5个 V，即数据量大（Volume）、速度快（Velocity）、类型多（Variety）、难辨识（Veracity）和价值密度低（Value）[1]。数据量大仍可以靠扩展储存在一定程度上缓解，然而要求及时响应、数据多样性和数据不确定性是传统数据处理方法所不能解决的。

为了应对这种大数据所带来的困难和挑战，诸多大型互联网公司近几年推出了各种类型的大数据处理系统。2004年，Google公司提出的MapReduce编程模型是面向大数据处理技术的具体实现，在学术界和工业界引起了很大反响[1]。随后Apache基金会根据MapReduce模型开发出开源的大数据处理框架Hadoop在Yahoo！、IBM、百度等公司得到了大量的应用和快速的发展[2]。然而，作为一个新兴的技术，大数据处理技术在很多地方还存在着很多不足，如调用分布式的数据所造成的延迟、巨大的数据吞吐量与不相符的网络速率所造成的网络负载严重的问题等。因此，国内外诸多学者们一直在找寻较好的数据存储方法以加强大数据处理的综合能力。本文首先对目前较为流行的大数据存储结构进行了介绍，然后对近几年的大数据存储策略方面的优化进行了总结，最后对全文进行了总结并提出对未来的展望。

1数据存储结构

1.1传统集中式数据存储

传统互联网数据的创造和使用多以企业为主，数据的种类较为单一，又多以结构化数据为主，数据的管理以数据库的形式存在；企业根据自身对数据需求的不同，制定适用于自身的数据库模式（schema），而后才产生数据；数据仅作为一种处理对象，并不能用来辅助解决其他问题； 数据多是由企业自身来访问，因此集中式存储是比较合适的存储方式[3]。

在互联网快速发展的过程中，随着网络应用的数据量的加大，企业已感觉到存储的容量和性能逐渐落后互联网发展的需求。在此背景下，一些满足企业需求的数据存储技术便应运而生，可总结为直连式存储、网络附加存储和存储区域网络三大类

1.1.1直连式存储

直连式存储（Direct Attached Storage， DAS）是指将外部存储设备通过数据接口直接挂载在服务器的内部总线上，存储设备是整个服务器的一部分。这种存储方式适用于一些对存储要求不高的小型服务器，但由于存储设备与服务服务器之间的连接通常使用小型计算机系统接口（Small Computer System Interface， SCSI），其传输速度较慢，且服务器的SCSI接口资源有限，随着存储需求的不断增大和服务器运行速度的提升，存储设备的输入输出将成为服务器的瓶颈。

1.1.2网络附加存储

网络附加存储（Network Attached Storage， NAS）则将外部存储设备与服务器通过网络技术（如以太网）连接，存储设备不再是服务器的一部分，而是网络中的独立节点。NAS虽然能解决接口资源的限制，但是因数据的存取转移至网络，反而会加重网络的负载，而且随着存储容量的扩展，性能会进一步下降。

1.1.3存储区域网络

存储区域网络（Storage Area Network， SAN）是通过光纤交换机为存储设备建立高速专用网络，采用光纤通道（Fibre Channel， FC）技术将服务器和存储设备相连接。这种结构扩展能力强，且允许任何服务器可连接到任何存储阵列，实现了高速共享存储；而且由于采用光纤接口，SAN还具有更高的带宽。但由于光纤成本较高，且技术实现较复杂，会导致后期管理和升级成本较高。

1.2分布式数据存储

传统的集中式存储对搭建和管理的要求较高。由于硬件设备的集中存放，机房的空间、散热和承重等都有严格的要求；存储设备要求性能较好，对主干网络的带宽也有较高的要求[4]。信息爆炸的时代，人们可以获取的数据呈指数倍的增长，单纯在固定某个地点进行硬盘的扩充在容量大小、扩充速度、读写速度和数据备份等方面上的表现都无法达到要求；而且大数据处理系统的数据多是来自于客户，数据的种类多，存储系统需要存储各种半结构化、非结构化的数据，如文档、图片、视频等，因此大数据的存储宜使用分布式文件系统来管理这些非结构化数据。

分布式数据存储，即存储设备分布在不同的地理位置，数据就近存储，带宽上没有太大压力。可采用多套低端的小容量的存储设备分布部署，设备价格和维护成本较低。小容量设备分布部署，对机房环境要求也较低。分布式数据存储将数据分散在多个存储节点上，各个节点通过网络相连，对这些节点的资源进行统一的管理。这种设计对用户是透明的，系统为用户提供文件系统的访问接口，使之与传统的本地文件系统操作方式类似。这样的设计解决了传统的本地文件系统在文件大小、文件数量等方面的限制。

传统的分布式计算系统中通常计算节点与存储节点是分开的。当执行计算任务时，首先要把数据从数据节点传输至计算节点（数据向计算迁移），这种处理方式会使外存文件数

据I/O访问成为一个制约系统性能的瓶颈。为了减少大数据并行计算系统中的数据通信开销，应当考虑将计算向数据靠拢和迁移。如MapReduce模型采用了数据/代码互定位的技术方法，该方法让计算节点首先尽量负责计算其本地存储的数据，以发挥数据本地化特点；仅当节点无法处理本地数据时，再采用就近原则寻找其他可用计算节点，并把数据传送到该可用计算节点。

1.3分布式數据存储的典型结构

目前比较主流的分布式文件系统结构是主/从（master/slave）体系结构，如图1所示，通常包括主控节点（或称元数据服务器，通常会配置一个活动节点和一个备用节点以实现高可用性）、多个数据节点（或称存储节点）和各种大数据应用或者终端用户组成的客户端。分布式存储的目的是将大数据划分为小数据，均匀分布至多个数据节点上，将数据的规模降到单个节点可以处理的程度。

1.3.1主控节点

主控节点主要负责管理文件系统名字空间（namespace）和管理客户端的访问。常见的命名空间结构有经典的目录树结构如Hadoop分布式文件系统（Hadoop Distributed File System， HDFS）等，扁平化结构如【淘宝分布式文件系统（Taobao Distributed File System， TFS）等。为了维护命名空间，主控节点需要存储一些元数据（metadata），如文件的所有者和权限、文件到数据节点的映射关系等。除了管理命名空间，主控节点还要集中管理数据节点。通过对数据节点轮询或接收来自数据节点的定期心跳（heartbeat）消息。除了管理命名空间，主控节点还要对数据节点轮询或接收来自数据节点的定期心跳（heartbeat）来集中管理数据节点。

主控节点根据得到的消息可以验证文件系统的元数据；若发现数据节点有故障，主控节点将采取修复措施，重新复制在该节点丢失的数据块；若有新的数据节点加入或某个数据节点负载过高，主控节点会根据情况执行负载均衡。

1.3.2数据节点

数据节点负责数据在集群上的持久化储存。数据节点通常以机架的形式组织，机架通过交换机连接起来。数据节点响应来自客户端的读写请求，还响应来自主控节点的删除和复制命令。

类似于磁盘的结构，在数据节点中也有块（block）的概念，这是数据读写的最小单位，不过这里的块是一个很大的单元，在很多文件系统中通常为64MB，如google的GFS、HDFS和TFS等。对于小文件的储存，可以将多个文件储存在一个块中，并建立索引，提高空间利用率；对于大文件的储存，则会将数据划分为多个数据块，并作为独立的单元进行储存。

为了保证数据的安全性和容错性，分布式文件系统会存储多个数据副本在数据节点上。当数据不可用时，可调用存放在其他节点上的副本。在HDFS系统中，副本的基本存储策略是：在任务运行的节点上存储第一个副本；在任务所在机架内的其他节点中的某一节点存储第二个副本；在集群的其他机架中的某一节点存储第三个副本。

1.4分布式存储系统存在的挑战

虽然计算向数据迁移的方法在很大程度上提升了大数据集群的处理性能，但这种处理方式仍存在很多问题，性能仍然有很大的提升空间，如数据副本的存储造成的数据冗余过多，执行负载平衡或副本失效时进行的数据迁移产生的巨大的网络开销等。随着数据密集型的应用和大数据处理需求的急剧增长，以及处理框架仍不成熟，数据的存储策略成为了影响处理性能的重要因素，如何改进数据的存储策略来提升处理框架已成为当今学术界的研究热门。目前，分布式存储系统存在的挑战主要体现在如何减少跨数据节点的网络传输、如何在保证负载均衡的同时提升处理性能，以及如何在保证可靠性的前提下节约能耗等问题[4]。

2大数据集群中数据存储优化

根据上述分布式存储的基本架构和所存在的挑战可知，大数据处理系统在存储方面仍有很大的改进空间，改进数据的存储策略已成为提升大数据处理系统的性能的热点方向。大数据服务提供者可根据其所关注的重点不同，如数据传输、负载平衡、运营开销、运行效率等方面可以制定侧重点不同的优化方案。

在众多的大数据处理模型中，MapReduce以它良好的性价比和可扩展性、易于理解、易于使用，且能提供良好的数据处理性能等優点，受到大数据服务提供者广泛的欢迎并迅速得到应用[1]。MapReduce已成为一种经典的大数据处理模型。因此本文归纳的存储策略优化算法皆以MapReduce模型为基础。

2.1减少网络负载的优化

根据集群计算的特性，系统所运行的任务与之所需的数据可能不在同一处理节点上，此时便需要通过网络来进行数据的传输。然而根据如今的硬件水平，网络的传输速度远远小于计算机的处理和输入输出的速度，这会成为拖慢大数据集群作业的瓶颈。因此减少集群计算网络传输，增强数据的本地化存储是一种有效的改善集群处理能力的方法。

2.1.1根据数据相关性的存储优化

数据相关性是指某些任务所需要的数据具有某些特点（如使用频率、大小、与其他数据同时使用等），若尽可能将相关性高的数据存放在计算节点，则在计算时直接从本地硬盘调取，无需占用网络资源。Zhao等[6]对数据传输的流量计算方法进行了数学建模，提出当任务需要的数据分布在不同的节点时，根据存储在各节点数据大小，通过数学计算得出一种将所有数据移动到同一节点且使用网络流量最少的移动方案。然而这一算法只考虑了无数据副本的系统，并没有考虑数据多副本的情况，而多数分布式存储都需要通过数据副本来增强容错性，因此此算法并不能广泛适用。对于这个问题，Yu等[7]研究数据需求基本相同的同类任务，预测出此类任务的固定需求，记为一个需求模式。在运行前，使用超图划分算法将此模式所需的数据移动至负载较小的节点，当有数据副本时，选择数据选择副本中路径最短的一个，减少跨节点的数据调用。比起文献[6]算法，此算法研究了无数据副本和有数据副本两种情况，扩展了算法的适用范围。Jalaparti等[8]指出大数据作业有许多是重复的，有相同的资源需求，因此可以提前预测此类任务的资源需求，确定所需集群机架的数量。在预测的作业到达时间先后顺序下，按照所需机架数量降序排列分配负载最轻的机架，这样便同时增强了数据存储和任务调度的本地化程度。这种增强数据本地化的算法对于规模分布较集中的计算集群比较适用，而对于一些大规模、分布广泛的计算集群来说，数据过于本地化的放置可能意味着若本地数据不能使用时，调用数据副本可能是跨越全球的数据传输，反而加重了网络负载。Chen等[9]考虑了分布全球的大型计算集群的数据存储，设计了一个固定层数的树形拓扑结构来描述集群的结构，上层非叶子节点代表互联网、路由器、交换机、集群机架、计算机等硬件，叶子节点代表存储的数据。文献[9]中提出了一种被称为副本平衡树（Replica Bananced Tree， RBT）的树形结构，这种树形结构可将数据副本均匀放置在遍布全球的集群中；又提出了副本相关性树（Replica Similarity Tree， RST），通过数据相关系数（Data Dependency Value， DDV）公式计算，将所有数据划分为相关性最小的两个子节点，子节点继续计算和划分，直至计算至叶子节点。这种存储方法同时减少了全球范围内相同数据被调用时的网络传输和相关性较强的不同数据同时被调用的网络传输。

2.1.2通过修改大数据处理模型的网络优化

由于大数据的发展时间不长，现有的大数据处理模型如MapReduce仍然在不断发展中，通过对大数据处理模型的优化可以提升模型的处理能力，无需分析数据的特点进行特殊的优化，适用性较广。Wang等[10]研究了MapReduce 框架中Shuffle阶段先排序还是先归并的问题，得出了【两种不同处理顺序的数据传输量计算方法，根据任务Map阶段的具体结果特征选择数据传输量较低的Shuffle方式，提升了运行效率。Wang等[10]研究了MapReduce 框架中Shuffle阶段“先排序还是先归并？”的不同处理顺序下的数据传输量，然后选择数据传输量较小的一种顺序作为Shuffle阶段的处理顺序。这种根据任务Map阶段的具体结果特征来选择数据传输量较低的Shuffle方式，提升了运行效率。此算法虽然在一定程度上减少了数据的传输，但是依然无法改变Shuffle阶段需要同时将中间数据传输至Reduce任务，这一并行操作仍会带来巨大的网络负载。对于此问题，Yu等[11]借鉴了操作系统的虚拟内存段页式管理原理，提出了一个三级段表，将Shuffle过程以段表形式存储而不进行实际的数据传输，当Reduce程序需要数据时再通过段表查询和传输所需数据，将数据的传输分散开，降低了Shuffle过程的网络负载。

2.2保持负载均衡的优化

负载均衡即将收到的处理任务请求分摊到多个处理节点执行，根据处理节点的目前的性能为之分配合适的任务，以达到最小化任务的完成时间[12]，最后将处理结果返回至用户。但是大数据集群中存在一些不均衡因素，如不平衡的计算、不平衡的数据分配、不平衡的硬件等，这些因素可能会导致某些处理节点工作负荷重，而另一些节点空闲，造成效率下降和资源浪费。

Hadoop平台内置了一个名为Balancer的存储负载均衡程序[13]，其主要原理是统计所有数据节点的空间利用率并求出节点的平均利用率。数据节点对比自身的利用率与平均利用率，先在机架内进行平衡，再在机架间进行平衡。平衡时将负载较多的节点中的数据转移至负载较少的节点，从而达到空间利用率上的平衡。然而这样的负载平衡仅仅从储存空间利用率这单一方面考虑，并没有考虑其他因素，不当的使用反而可能会加重负载不均衡的程度。

2.2.1均衡复杂度不同的计算

计算的不均衡即分配至各个处理节点的任务计算复杂度不相同，因此可能造成许多节点等待一个计算较复杂的节点，造成资源的浪费。Xie等[14]对任务的调度进行了改进，在每一个处理节点上构造了一个任务队列，任务会被分配在存有所需数据副本的节点之中队列最短的一个，减少节点负载不均的情况。对于MapReduce 模型下，Map和Shuffle阶段持续时间长而Reduce阶段却很短这种计算不平衡情况，Le等[15]設计先执行部分作业样本，根据样本Map阶段后的结果中key的频率来预测此key整体频率，根据频率高低分配负载不同的选择处理节点进行Shuffle，加快Shuffle阶段的处理速度。

2.2.2均衡数据的分配

MapReduce模型中，数据被Map端处理后产生的中间数据要被分配至Reduce端，Hadoop平台默认的数据分配函数partitioner是静态哈希算法，即将Map端结果〈key，value〉与Reduce阶段处理程序Reducer的数目作为变量输入partitioner函数，将key的哈希值用Reducer数目取模，得出该数据被分配的Reducer，这样可以保证相同的key值分配在相同的reduce程序。然而当某些数据重复出现频率比其他多时，会使过多被数据分配至相同Reducer，造成数据失衡，Chen等[16]提出Map阶段结束后，根据中间数据的key值的重复比例将比例较大的key增加一个次级key，并以随机数赋值，根据次级key再进行数据分配，如此可将过于集中的相同数据分至其他Reduce程序处理，避免数据分配失衡。

MapReduce模型中，一个作业向集群申请计算资源，这样的资源称为slot。slot可分为Map slot和Reduce slot，可供一个Map或Reduce任务使用，通常一个大数据作业申请用于Map或Reduce的slot是固定的。当Map任务或Reduce任务的运行顺序不当时，可能造成Reduce任务等待Map任务的结果而用于Reduce的slot空闲，从而造成计算资源浪费。针对这一情况，Tang等[17]改进了约翰逊法则[18]来求得最短运行时间的任务顺序，又进一步循环测试得出一个作业用于Map和Reduce的slot的最佳分配比例。然而这里寻找最佳slot的分配比例使用的是枚举法，寻找效率较低。针对此问题，Yao等[19]对一个作业申请的Map和Reduce slot资源需求和运行时间进行数学建模，以Map和Reduce程序同时结束为目标，使用动态规划思想计算出最佳的slot分配方案。

与上述观点相反，Grandl等[20]提出了资源平等分配有时并不是最优的分配算法。由于资源的平等分配，某些大数据作业分配到的计算资源不足以一次完成所有任务，仍需要第二次甚至更多次资源分配，这样不仅影响作业的完成时间，再次进行资源分配和处理时，之前已完成的部分仍在占用存储资源等待后续数据。文献[20]中根据大数据作业的资源需求，构造并解决了一个装箱问题，进行合理的资源分配，减少资源的再分配次数，缩短任务处理时间。

2.2.3均衡因硬件不同造成的性能差异

由于如今的大数据处理框架如Hadoop可以部署在廉价机器上，且代码是开源的，对硬件有很好的适应性，当集群中处理机的硬件性能有差异时，便形成了异构系统。这种异构系统节点之间的处理能力不同，但分配的数据量是相同的，这是分布式文件系统的默认策略。处理能力强节点很快就完成本地数据处理，闲置下来。之后，调度器为它们分配远程的任务，这些任务会经过网络的传输，这不可避免地增加耗时。魏文娟等[21]制定了一个标准化测试，得出各个异构节点的处理速率，求出节点间的相对处理速率，根据相对速率按比例分配数据分块数进行存储和运行。这里的相对速率是通过标准化测试得到的固定值，而在实际运行时，由于任务的计算复杂度以及负载状况不同，此时计算出的固定速率与实际速率可能会有较大误差，并不能代表节点真实的处理速率。Wang等[22]以单位时间内处理数据块的量为评价标准，使用马尔可夫链来实时预测节点的处理性能，动态选择合适的存储节点。

2.3降低集群能耗的优化

2010年美国的数据中心的用电量已占美国总用电量的2%，并且以15%的速度逐年上升[23]。能源的开销已占数据中心日常运行开销的42%[24]，已经成为网络公司和数据中心运营的重要经济支出。因此无论从经济方面还是环保方面来说，降低集群的能源开销已经成为大数据服务供应商着重考虑的问题。

2.3.1休眠数据节点

廖彬等[25]将集群机架内部划分为活跃区和休眠区，并对休眠区节点进行休眠处理。定义阈值SleepCount和ActiveCount：一个文件在时间周期内访问次数小于阈值SleepCount，算法则会减小该文件的活动数据块的数量；相反如果访问次数大于阈值ActiveCount，则增加活动数据块的数量。算法在达到节能目的的同时保证了数据块的可用性。DeryaCavdar等[26]提出检测集群资源（如CPU、内存、网络等）在空闲时和运行时的功率，通过休眠时和运行时的功率，使用动态规划思想来找到一条使用能耗最低的数据传输路径，减少不必要的能源消耗。以上算法都仅从休眠节点或减少数据传输路径长度，这些单一角度来节约能耗，虽有一定成效，但无法确定整体节能效果是否最优。文献[27-28]对大数据处理模型的各个阶段进行细致的分析，建立完整详细的能耗计算模型。利用能耗模型，GuZeng等[27]详细定义了数据中心服务器数量、数据在本地传输开销、数据在网络中传输开销、激活一个服务器能源开销、数据的备份数量、任务到达率、最大响应时间等多种变量，得出一个能耗计算公式，将能耗的最小化问题转换成求解一个混合整数非线性规划问题（MINLP），全面地考虑了集群中可以影响能耗的各个因素。

2.3.2延缓非紧急任务

大数据任务中，存在一些非紧急的任务，这些任务虽然不要求完成时间最小，但是规定了最晚开始时间。延缓这些非紧急任务的执行，可减轻集群的计算负载，达到减少能耗的目的。Mashayekhy等[29]为Map端和Reduce端接受的任务建立了两个执行队列，通过任务的最晚开始时间和资源需求，以及目前集群个处理节点的负载情况，将Map任务和Reduce任务综合排序分别建立队列，放置在最佳的处理节点运行。Chen等[30]以租用公共云计算集群（如Amazon的AWS）中如何节省成本的问题为例进行，进一步对这种非紧急任务的能耗计算进行研究，分析了Map和Reduce阶段的开销并建立数学模型，对有成本有限制的作业和处理时间有限制的作业两种类型分别构造线性规划，根据具体作业类型求得最佳的Map和Reduce的slot分配数量。

2.3.3节能与性能的平衡

除了不必要的能源浪费之外，集群的计算性能和能耗节约其实是相互矛盾的两个方面，要求节能则可能意味着对集群处理能力的妥协。林彬等[31]将利用率较低、甚至空转的节点进行关闭；而对于数据完整性和性能影响问题，文中令集群机架内数据副本顺序存放，机架间数据副本随机存放，减少因关闭节点造成数据完整性被破坏的概率；同时还引入了关闭节点对集群的影响衡量指标，即关闭节点后能耗降低值与响应时间增加值的比值，比值越大表示节能越有效，关闭节点时选择比值大的节点，直到数据完整性被破坏。这种考虑性能

与節能的想法比较简单，但对数据的完整性和容错性等方面损伤较大。MinYoon等[28]研究了性能和节能两个问题的矛盾关系，对计算性能和能源消耗建立了数学模型，从性能和节能两个角度分别构造了两个线性规划，通过找到两个线性规划的帕累托最优点，使得性能和节能两方面达到一个平衡点。

2.4其他因素的数据存储优化

另有其他因素诸如集群可靠性、容错性、大数据处理框架的处理效率等都可作为提升大数据处理能力优化的研究方向。

当集群中的处理节点有突发故障，集群的部分甚至全部处理能力会下降或完全瘫痪，如何避免和处理故障是保证集群可用性的关键。Hadoop虽然提供了“推测执行策略”，即在作业运行过程中，不对运行慢的任务进行修复，而是启动一个相同任务来替代。这种简单的故障处理方式虽然简单，但是要以增加不必要的系统负载为代价。Xu等[32]提出当系统负载较低时，使用默认推测执行策略；当系统负载较高时，采用改进的微软Mantri差错预测算法[33]，进行问题的检测和任务转移。Mantri算法假定任务的处理速度是恒定的，以平均处理速度为判断节点是否有问题的标准。然而，在MapReduce中，一个任务的处理会经历若干个阶段，如map、combine、copy、sort和reduce等，不同的处理阶段由于任务难度和运行环境的不同，处理速度是有区别的，若使用平均处理速度作为判断标准，势必会出现判断错误。Chen等[34]分析了以往故障预测算法的不足，并且提出分阶段计算任务处理速度的指数加权移动平均数（Exponentially Weighted Moving Average， EWMA）作为判断标准，并对比任务在原节点、转移至同一机架不同节点和转移至不同机架三种处理方式预计的完成时间，选取最优的转移策略。

网络可靠性也是影响集群效果的一大因素，以往的网络状态检测是进行抽样检测，因此一些不良的通信会刻意回避检测，Fontugne等[35]将网络状态的异常检测转化为一个普通大数据作业始终运行，对网络进行实时检测。对通信数据的源IP地址和目的IP地址进行哈希运算来选择通信路径，为网络流量分流。宋宝燕等[36]使用范德蒙纠删码来检测和纠正出错的数据，增强了数据的容错性，同时减少了数据副本的数量，降低了存储空间的冗余。

2.5数据存储策略优化的分析与总结

由于MapReduce模型在大数据处理领域被广泛使用，占据主流地位，本文通过对近几年来大数据集群数据存储策略的研究，基于MapReduce处理模型对存储策略的优化算法及特点进行总结。如表1所示，目前数据存储策略的研究主要集中在减少网络负载、保证负载平衡和节约开销三个目标。而且在实际应用中，使用者可能不只有单一的优化目标，而是有多目标共同优化的需求，然而这些优化之间可能是相互矛盾的。例如，为了节约能源而休眠或关闭部分节点时，会使大部分任务都集中分配在活跃的节点，造成负载的不平衡；而为了负载平衡，需要进行数据副本的迁移时，又会造成大量的网络开销。由此可见，目前大部分数据存储算法的优化目标单一。如果使用者要根据自身的具体需求进行多目标优化，必须设计一种各方面都较为平衡的综合存储策略。

3总结与展望

本文对大数据处理系统的主流文件存储结构进行了简介，并总结了近几年来国内外学者们对存储策略的优化所作的贡献。从当前的研究结果来看，通过调整数据的存储策略从而提升系统性能的做法仍有很大的发展空间。在大数据处理需求急剧膨胀的时代下，大数据处理系统仍有很长的路要

走。

根据集群存储的特点和要求，未来数据存储算法的研究可以有以下几种趋势：

1）通过本文的总结归纳，不难发现，目前学者们对数据存储算法的研究大多数都着重于调整数据以配合已有的存储系统，并没有多少对存储系统本身的设计进行的优化。这种优化方向有很大的局限性，它只适用于特定的作业需求，而且可能会与其他优化方向产生矛盾。若对现有的存储系统进行优化，整体提升存储系统的性能，当优化足够好时则可无需针对数据特性设计不同的数据存储算法。对存储系统的优化可以作为未来研究的重点方向。

2）本地化、负载均衡和节能这几个目标是优化算法常见的研究方向，实际应用中同时要求多目标同时优化的要求也很常见。然而目前的优化算法优化目标单一，少有可以满足多目标同时优化。鉴于性能与节能、节能与负载均衡、负载均衡与数据本地化等多个优化方向之间的矛盾关系逐渐凸显，探索出可满足多目标同时优化的需求得到平衡和优化的方法是一个非常迫切需要解决的问题。

3）目前的大数据处理框架多用于进行海量数据批量地分析与处理，适用于先存储后计算，针对的是高吞吐量的作业，存储的优化算法也大多针对批处理或可预测特性的数据的存储。而在未来，需要将实时接受的大数据处理请求在秒级内完成处理的情况将成为常态，这将成为未来大数据处理的发展趋势，然而这方面的存储优化算法尚未有过多的研究，需要增强对此的关注和研究。

4结语

随着信息化时代的迅速发展，信息的数据规模和复杂度的快速增长对现有的数据处理能力提出了挑战。合理的数据存储算法是影响大数据处理框架的一个关键因素。本文首先对主流的大数据集群存储架构和算法进行了总结，然后对数据存储的优化算法进行了归纳和分析，最后对数据存储算法研究的挑战和发展进行了展望。从文中可以看出，目前数据放存储算法在针对单一目标的优化上已有很好的效果，但对于提升大数据处理系统整体性能方面的研究，仍有较大的探索空间。不过大数据还是一个正在发展的研究方向，未来大数据处理系统的性能得到大幅度提升是必然的。

参考文献：

[1]

程学旗，靳小龙，王元卓，等.大数据系统和分析技术综述[J].软件学报，2014，25（9）：1889-1908.（CHENG X Q， JIN X L， WANG Y Z， et al. Survey on big data system and analytic technology [J]. Journal of Software， 2014，25（9）：1889-1908.）

[2]

王元卓，靳小龍，程学旗.网络大数据：现状与展望[J].计算机学报，2013，36（6）：1125-1138.（WANG Y Z，JIN X L，CHENG X Q. Network big data： present and future[J]. Chinese Journal of Computers， 2013， 36（6）： 1125-1138.

[3]

孟小峰，慈祥.大数据管理：概念、技术与挑战[J].计算机研究与发展，2013，50（1）：146-169.（MENG X F， CI X. Big data management： concepts， techniques and challenges [J]. Journal of Computer Research and Development， 2013， 50（1）： 146-169.）

[4]

张滨，陈吉荣，乐嘉锦.大数据管理技术研究综述[J].计算机应用与软件，2014，31（11）：1-5.（ZHANG B， CHEN J R， LE J J. Overview on big data management technology research [J]. Computer Applications and Software， 2014， 31（11）： 1-5.）

[5]

ZICARI R V. Big data： challenges and opportunities [J]. Big Data Computing， 2014： 103-128.

ZICARI R V. Big data： challenges and opportunities [EB/OL]. [20160108]. http：//gotocon.com/dl/gotoaar2012/slides/RobertoV.Zicari_BigDataChallengesAndOpportunities.pdf.

[6]

ZHAO Q， XIONG C， ZHAO X， et al. A data placement strategy for dataintensive scientific workflows in cloud [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster， Cloud and Grid Computing. Washington， DC： IEEE Computer Society， 2015： 928-934.

[7]

YU B， PAN J. Locationaware associated data placement for geodistributed dataintensive applications [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015：603-611.

[8]

JALAPARTI V， BODIK P， MENACHE I， et al. Networkaware scheduling for dataparallel jobs： plan when you can [C]// SIGCOMM 15： Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York： ACM， 2015： 407-420.

[9]

CHEN W， PAIK I， LI Z. Topologyaware optimal data placement algorithm for network traffic optimization [J]. IEEE Transactions on Computers， 2016，65（8）：2603-2617.

[10]

WANG J， QIU M， GUO B， et al. Phasereconfigurable shuffle optimization for Hadoop MapReduce [J]. IEEE Transactions on Cloud Computing， 2015（99）：1.

[11]

YU W， WANG Y， QUE X， et al. Virtual shuffling for efficient data movement in MapReduce [J]. IEEE Transactions on Computers， 2015， 64（2）：556-568.

[12]

BUYYA R. High Performance Cluster Computing： Architectures and Systems [M]. Upper Saddle River， NJ： Prentice Hall， 1999， 1： 823.

[13]

刘琨，肖琳，赵海燕.Hadoop中云数据负载均衡算法的研究及优化[J].微电子学与计算机，2012，29（9）：18-22.（LIU K， XIAO L， ZHAO H Y. Research and optimize of cloud data load balancing in hadoop [J]. Microelectronics & Computer， 2013， 29（9）： 18-22.

[14]

XIE Q， LU Y. Priority algorithm for neardata scheduling： throughput and heavytraffic optimality [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 963-972.

[15]

LE Y， LIU J， ERGUN F， et al. Online load balancing for MapReduce with skewed data input [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014： 2004-2012.

[16]

CHEN Q， YAO J， XIAO Z. LIBRA： lightweight data skew mitigation in MapReduce [J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（9）： 2520-2533.

[17]

TANG S， LEE B S， HE B. Dynamic job ordering and slot configurations for MapReduce workloads [J]. IEEE Transactions on Services Computing， 2016， 9（1）： 4-17.

[18]

JOHNSON S M. Optimal two and threestage production schedules with setup times included [J]. Naval Research Logistics Quarterly， 1954， 1（1）：61-68.

[19]

YAO Y， WANG J， SHENG B， et al. Selfadjusting slot configurations for homogeneous and heterogeneous Hadoop clusters [J]. IEEE Transactions on Cloud Computing， 2015（1）：1.

YAO Y， WANG J， SHENG B， et al. Selfadjusting slot configurations for homogeneous and heterogeneous Hadoop clusters [EB/OL]. [20160109]. http：//www.cs.umb.edu/～shengbo/paper/tcc15.pdf.

[20]

GRANDL R， ANANTHANARAYANAN G， KANDULA S， et al. Multiresource packing for cluster schedulers [C]// SIGCOMM 14： Proceedings of the 2014 ACM Conference on SIGCOMM. New York： ACM， 2014：455-466.

[21]

魏文娟，王黎明.異构Hadoop集群下的比例数据分配策略[J].计算机应用与软件，2015，32（6）：316-319.（WEI W J， WANG L M. Proportional data placement strategy in heterogeneous hadoop clusters [J]. Computer Applications and Software， 2015， 32（6）： 316-319.）

[22]

WANG B， JIANG J， YANG G. ActCap： accelerating MapReduce on heterogeneous clusters with capabilityaware data placement [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 1328-1336.

[23]

KOOMEY J. Growth in data center electricity use 2005 to 2010 [J]. A report by Analytical Press， completed at the request of The New York Times， 2011： 9.

KOOMEY J. Growth in data center electricity use 2005 to 2010 [EB/OL]. [20151104]. http：//cs.bennington.edu/courses/f2013/cs4125.01/koomeydatacenterelectuse2011finalversion.pdf.

[24]

HAMILTON J. Cooperative Expendable Microslice Servers （CEMS）： low cost， low power servers for Internetscale services[C]// Conference on Innovative Data Systems Research. 2009.

HAMILTON J. Cooperative Expendable Microslice Servers （CEMS）： low cost， low power servers for Internetscale services [EB/OL]. [20151104]. http：//database.cs.wisc.edu/cidr/cidr2009/JamesHamilton_CEMS.pdf.

[25]

廖彬，于炯，張陶，等.基于分布式文件系统HDFS的节能算法[J].计算机学报，2013，36（5）：1047-1064.（LIAO B， YU J， ZHANG T， et al. Energyefficient algorithms for distributed file system HDFS [J].Chinese Journal of Computers， 2013， 36（5）： 1047-1064.

[26]

CAVDAR D， CHEN L Y， ALAGOZ F. Green MapReduce for heterogeneous data centers [C]// Proceedings of the 2014 IEEE Global Communications Conference. Piscataway， NJ： IEEE， 2014： 1120-1126.

[27]

ZENG D， GU L， GUO S. Cost minimization for big data processing in geodistributed data centers [M]// Cloud Networking for Big Data. Berlin： Springer， 2015：314-323.

ZENG D， GU L， GUO S. Cost minimization for big data processing in geodistributed data centers [J]. IEEE Transactions on Emerging Topics in Computing， 2014， 2（3）： 314-323.

[28]

YOON M S， KAMAL A E. Optimal dataset allocation in distributed heterogeneous clouds [C]// Proceedings of the 2014 IEEE Globecom Workshops. Piscataway， NJ： IEEE， 2014： 75-80.

[29]

MASHAYEKHY L， NEJAD M M， GROSU D， et al. Energyaware scheduling of MapReduce jobs [C]// Proceedings of the 2014 IEEE International Congress on Big Data. Washington， DC： IEEE Computer Society， 2014：32-39.

[30]

CHEN K， POWERS J， GUO S， et al. CRESP： towards optimal resource provisioning for MapReduce computing in public clouds [J]. IEEE Transactions on Parallel & Distributed Systems， 2014， 25（6）：1403-1412.

[31]

林彬，李姗姗，廖湘科，等.Seadown：一种异构MapReduce集群中面向SLA的能耗管理方法[J].计算机学报，2013，36（5）：977-987.（LIN B， LI S S， LIAO X K， et al. Seadown： SLAaware sizescaling power management in heterogeneous MapReduce cluster [J]. Chinese Journal of Computers， 2013， 36（5）： 977-987.

[32]

XU H， LAU W C. Optimization for speculative execution in a MapReducelike cluster[C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 1071-1079.

[33]

ANANTHANARAYANAN G， KANDULA S， GREENBERG A， et al. Reining in the outliers in MapReduce clusters using Mantri [C]// OSDI 10： Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2010：265-278.

[34]

CHEN Q， LIU C， XIAO Z. Improving MapReduce performance using smart speculative execution strategy [J]. IEEE Transactions on Computers， 2014， 63（4）： 954-967.

[35]

FONTUGNE R， MAZEL J， FUKUDA K. Hashdoop： a MapReduce framework for network anomaly detection [C]// Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2014： 494-499.

[36]

宋寶燕，王俊陆，王妍.基于范德蒙码的HDFS优化存储策略研究[J].计算机学报，2015，38（9）：1825-1837.（SONG B Y， WANG J L， WANG Y. Optimized storage strategy research of HDFS based on Vandermonde code [J]. Chinese Journal of Computers， 2015， 38（9）： 1825-1837.