基于支持向量机的HDFS副本放置改进策略

罗 军，陈仕强

（重庆大学计算机学院，重庆400044）

基于支持向量机的HDFS副本放置改进策略

罗 军，陈仕强

（重庆大学计算机学院，重庆400044）

为实现超大规模数据的存储并提高容错性，Hadoop分布式文件系统（HDFS）采用一种机架感知的多副本放置策略。但在放置过程中没有综合考虑各节点服务器的差异性，导致集群出现负载失衡。由于放置时采用随机方式，造成节点之间的网络距离过长，使得传输数据会消耗大量时间。针对以上问题，提出一种基于SVM的副本放置策略。通过综合考虑节点负载情况、节点硬件性能、节点网络距离为副本找到最佳的放置节点。实验结果表明，与HDFS原有的副本放置策略相比，该策略能更有效地实现负载均衡。

支持向量机；云存储；副本放置策略；分布式文件系统；负载均衡；机架感知

1 概述

Hadoop是一个能够对大量数据进行分布式处理的开源软件框架，其思想来源于Google公司的Map Reduce框架［1］，分布式数据密集的并行应用程序利用该框架能将大的任务和数据集分解成为更小的任务和数据集，并使这些任务在不同的分区中平行处理。Hadoop利用分布式文件系统HDFS来存储这些数据，而HDFS的设计思想来自于Google的GFS［2］。

HDFS是一种能够运行在大量廉价硬件上的分布式文件系统［3］，它不仅具有分布式文件系统的大量优点，而且还做了许多改善：具有很高的容错性，对硬件性能要求不高，可以实现高吞吐量的数据访问，特别适合运用在超大规模数据集上。

为了能够应对超大量数据的存储和提供较好的容错性能，分布式文件系统需要采用多副本策略，而且需要将多个副本分布在集群中的不同位置上，但如果副本放置的方式不当将会极大影响系统的负载均衡，从而导致系统运行效率低下。HDFS采用一种机架感知的策略来放置副本，默认的副本数为3个。在放置多个副本时这种策略采用随机的方式，会使整个集群负载失衡，文献［4］利用数据在逻辑上的相关性，将HDFS改装成应用层可以自行控制数据要存放的节点集，使具有逻辑相关性的数据副本可以存在相同的几个节点上，提升了对节点数据和副本的管理效率。文献［5］提出一种根据节点文件访问热度来动态调节其相应的副本数，并且将集群的剩余空间也作为调节副本数的一项评价指标。

本文在这些方法的基础上，提出一种基于SVM的副本放置策略模型。

2 HDFS架构及其副本放置策略

2.1 原有副本放置策略

在分布式的文件系统架构中，为了提高整个集群的性能，通常会将元数据与数据分离，以实现对元数据和数据的高效管理，其中元数据节点的职责是管理文件系统命名空间和文件的各种属性，数据节点的职责是负责管理文件上的具体数据，并且直接处理来自客户端的文件读写请求，HDFS采用了主从式的分布式架构，图1展示了HDFS的架构。

图1 HDFS架构

在HDFS集群中有一个名字节点和多个数据节点。名字节点作为主服务器的职责是管理文件系统的元数据，记录对文件的操作，并维护文件系统中的块和存储位置等信息。数据节点作为从节点的任务是使用本地文件系统存储块数据，响应客户端的请求，接收或者传送数据［6］。HDFS文件存储的单位是块，并且块的大小默认为64 MB，这比一般的磁盘块要大很多，目的是为了配合大文件的存储，以减小文件的寻址开销。出于可靠性考虑，HDFS对每个块进行冗余存储，默认的副本数为3个。

由于元数据与数据的管理是分离的，因此对文件数据的读写操作并不需要通过元数据节点，这样就提高了文件的读写效率。图2为HDFS中文件的写入过程。

图2 HDFS文件写入过程

当有文件要写入时，HDFS客户端将请求发给名字节点，名字节点接收到请求时会先检查文件是否已经存在，若不存在还需要检查相关权限，如果成功则为这个请求的文件创建一个记录。客户端在写入文件时，最初是将数据写入到本地的临时文件中，如果数据大小达到一个块的大小时，客户端便从名字节点得到一个有许多数据节点的列表，这些数据节点是用来存放副本的，接收数据是从第1个数据节点开始一部分一部分接收，并且在将这部分数据写入的同时，还将这些数据传给第2个数据节点，第2个数据节点也和第1个数据节点一样开始写入数据的同时并将数据传给下一个节点，这种操作是以流水线的方式完成的［7］。

HDFS采用一种机架感知策略来组织集群，通过机架感知，名字节点可以获得所有数据节点的网络拓扑图，同一个机架上的节点之间的网络状况比不同机架的要理想。HDFS设法将副本保存在同一机架和不同机架中，其中保存在同一机架中能够减少网络传输开销，而放在不同机架中能提高数据安全性。HDFS默认采用的副本数为3，其存储结构如图3所示。

图3 HDFS默认数据放置策略

在图3中，第1个副本放置在和客户端同一的节点上，第2个副本放置在与第1个副本同一机架的不同节点上，第3个副本随机放置在不同机架的节点上。这种策略能够减少机架之间的传输，从而提高文件的读写效率，又由于有副本存放在不同机架上，因此也提高了数据的可靠性和安全性。

2.2 原有副本放置策略的不足

虽然HDFS原有的副本放置策略简单快捷，提高了整个集群的容错性，但是这种策略在存放副本的时候没有综合考虑节点负载情况、节点硬件性能、节点网络距离等因素，容易出现负载失衡。仍然有许多需要改进的地方：

（1）在选择副本放置节点时没有考虑节点的空间利用率，虽然HDFS提供了一个负载均衡的工具Balancer，它能够将负载较多的节点上的数据转移到负载较少的节点上，不过这个工具是在副本已经放置后手动触发的，所以并没有从源头上减少集群负载失衡的发生，而且Balancer在平衡负载的过程中还浪费了大量网络传输时间和网络带宽。

（2）没有考虑节点服务器的硬件性能，在集群中不同节点的机器是异构的，在具有相同负载的情况下，其对数据的读写速率是不一样的。

（3）没有考虑节点之间的网络距离，在将副本放置到不同节点时，距离越远的节点需要的传输时间越长。

3 改进的副本放置策略

3.1 基本思想

HDFS在副本放置过程中没有综合考虑各节点服务器的差异性，这会导致集群出现负载失衡。而HDFS在选择远程机架节点放置副本时采用随机方式，这有可能导致节点之间的网络距离过长，使得在节点之间传输数据会消耗大量时间。针对以上问题，SRPM采用SVM解决。

首先SRPM对集群中的每个节点服务器的负载、磁盘转速、CPU性能等硬件信息以及节点网络距离进行特征提取。

然后SRPM将这些提取的特征值以节点为单位组成SVM的输入数据，SVM根据输入数据将节点分为两类，一类是适合放副本的节点，一类是不适合放副本的节点。SRPM在适合放副本的节点中随机选择一个节点放置副本，这样便能有效避免随机选择到不适合放置副本的节点的情况。

3.2 问题描述

SVM是建立在统计学习理论基础上的一种数据挖掘方法，能非常成功地处理回归问题（时间序列分析）和模式识别（分类问题、判别分析）等诸多问题［8］。SVM是通过寻找一种结构化风险最小的方式进行学习分类的，即使在样本很少的情况下也能达到较好的分类效果［9］。

根据HDFS集群的特点，可以用一个有向图G=（V，E，ψ）来表示HDFS集群，其中，顶点vi∈V表示HDFS集群中的节点；边ei∈E表示节点中副本的流向；ψ（e）=（u，v）表示节点u上的数据在节点v上保存有副本；ψ（e）的值表示（u，v）之间的网络距离，节点连线箭头由u指向v。

假设现在有一节点u上的数据需要设置副本，该副本是否放置在另一节点v上可以表示为y=f（u，v，ψ），当y=+1表示u上的数据副本可以放置在节点v上，当y=-1表示u上的数据副本不能放置在节点v上。因此副本放置问题可以描述为在已知节点u，v和ψ的条件下，求解y=f（u，v，ψ）的值，y∈｛-1，1｝，可以看出该问题是一个典型的二分类问题，可以采用SVM的方法去解决。

但是传统的SVM在对大规模的数据集进行处理时需要消耗大量时间［9］，这是因为在SVM的算法中需要处理二次规划问题，当训练规模过于庞大的时候会导致求解时间过长［10］。

为了解决SVM在处理大规模数据时的问题，常用的解决方法主要有2种：（1）在不改变工作集的情况下提高训练速度；（2）减小工作集［11］，如常用的LIBSVM采用工作集方法。

本文采用了LIBLINEAR，一种继承自LIBSVM能够对大规模数据进行线性分类的工具，实验表明LIBLINEAR的训练速度非常快，例如对于一个6× 105条的数据训练只需要几秒钟，而用常规的LIBSVM则需要几个小时［12］。

3.3 节点特征选取

在整个分布式集群中，文件的读写效率会受到多种因素的影响，如节点服务器中磁盘的读写速度、CPU性能、内存大小以及节点之间的网络距离都会影响到数据的读写速率，所以如果数据副本放置过程中没有综合考虑这些因素将会导致严重的负载失衡问题，本文将从以下5个因素提取特征：

（1）相对负载率

在数据写的过程中，数据节点的磁盘利用率是影响整个集群负载均衡的重要因素之一，这是因为整个集群是建立在大量廉价设备上，不同的数据节点有着不同的磁盘容量，所以对于不同的节点应该区别对待，对于磁盘容量大的数据节点应该存储更多的数据，而较小的只需要存储较小的数据即可，针对集群里节点之间的差异性，可以用相对负载来衡量：

其中，λDNi为节点相对负载，当λDNi＞1时表示节点的负载率大于整个集群的平均负载率，当λDNi＜1时表示节点的负载率小于整个集群的平均负载率；P（DNi）表示节点的负载率：

其中，DNi（use）表示节点已使用的磁盘容量；DNi（total）表示节点的磁盘总容量，节点的磁盘总容量为一个固定值，单位为GB。

P（DNaverage）表示整个集群的平均负载率：

其中，n为整个集群的数据节点数。

（2）网络距离

节点网络距离表示存放数据的节点与要存放该数据副本节点之间的网络拓扑距离，网络距离的大小会对数据的读写时间造成很大的影响。如果网络距离过长，那么数据的读写时间也就会变得很长，本文中在同一机架中节点之间的网络距离为0，节点网络距离可用以下公式表示：

其中，L（DNij）表示节点i和节点j的网络距离；NetLength（DNi，DNj）表示节点i和节点j所在机架之间的网络拓扑距离，即两机架之间的交换机或路由器数目。

（3）磁盘性能

节点服务器磁盘性能也是影响集群节点文件读写快慢的重要因素之一，磁盘性能指标可以用以下公式表示：

其中，D（DNi）表示节点服务器磁盘的量化性能值；Size表示磁盘容量；R表示磁盘转速；Cache表示缓存大小；Vdata表示磁盘的数据传输率；表示平均寻道时间，即磁盘磁头移动到数据所在磁道时所用的时间。

（4）CPU性能

CPU的性能在很大程度上决定了计算机的性能，衡量CPU性能指标有多个，可以用以下公式来衡量：

其中，W（DNi）表示CPU的量化性能值；f表示CPU的主频；Cache表示CPU的缓存大小；NUM表示CPU的核心数量；Vbus表示CPU的总线速度。

（5）内存

对于经常被访问的数据，节点可以把这些数据放入内存中，这样能显著提高数据的访问速度。因此，节点内存的大小对负载均衡的效果也有显著影响。衡量内存性能采用下式：

其中，M（DNi）表示内存的量化性能值；V表示内存速度，即存取一次数据所需要的时间；Size表示内存的大小；Bandw idth表示内存的带宽；CAS表示等待时间，即指从读命令有效开始到输出端可以提供数据为止的一段时间，等待时间越短表示内存性能更好。

3.4 算法描述

算法思想：假设副本数为3，用SVM将各节点服务器依据各节点特征值分成2类：（1）适合放置副本的节点；（2）不适合放置副本的节点。在适合放置副本的节点中选一个节点作为副本放置的最佳节点。

输入 各节点服务器提取的特征值

输出 可以放置副本的最佳节点

算法伪代码如下：

4 实验与结果分析

4.1 改进策略的具体实现

为了检验改进策略的有效性，在Hadoop1.1.2中重写了HDFS的Replication Target Chooser类，该类主要负责副本放置，当有数据存储的时候就会调用ReplicationTargetChooser类。首先在该类初始化构造方法中将LibLinear引入进来，并根据NetworkTopology类的clusterMap对象获取集群中所有的节点，并获得各节点的负载情况，节点的硬件信息包括磁盘读写速度、内存大小及CPU性能以及节点之间的网络距离，利用SVM进行分类预测，将上述分类结果按放置策略的优先顺序从高到低排列。其次在Rep licationTargetChooser类中对节点进行选择时会分别调用3个方法，分别为chooseLocalNode方法，即选择本地节点，chooseLocalRack，即选择本地机架方法，chooseRemoteRack，即选择远程机架方法。在这3个方法中重写其随机选择的方式，改用SVM分类结果较好的节点。

4.2 实验环境

为了验证改进的副本放置策略模型的有效性，在Hadoop1.1.2集群上进行了改进策略模型的相关实验，并与HDFS原有的副本放置策略模型做了比较。实验操作系统采用CentOs6.4，JDK采用jdk1.6，通过虚拟机搭建了4个机架，每个机架5个节点，每个节点的容量为20 GB，在Hadoop集群中网络为树形拓扑结构，其中叶节点为节点服务器，非叶节点为路由器或交换机。在该树形拓扑结构中子节点到父节点的网络距离为1，两节点服务器的网络距离为这两节点到其最近公共祖先节点的距离之和，其网络拓扑距离如表1所示。

表1 Hadoop集群的网络拓扑距离

4.3 性能分析

在实验中，为了验证改进策略在网络距离上的效果，首先只在机架1中的节点1提交数据，该数据共有200块，其中每块大小为64 MB，集群默认的副本数为3，该提交数据存放在非机架1上的副本块数为200，而在机架1上的副本块数为400。假设初始时各节点都是空载状态。

若原有的副本放置策略、数据副本块数分布如图4和图5所示，如果采用改进的副本放置策略其分布如图6和图7所示。

图4 原有策略下数据块副本在本地机架的分布

图5 原有策略下数据块副本在远端机架的分布

图6 改进策略下数据块副本在本地机架的分布

图7 改进策略下数据块副本在远端机架的分布

由于改进的副本放置策略考虑了网络距离的影响，因此在放置副本时如果各节点负载相差不大的情况下改进的副本放置策略模型会优先考虑网络距离较近的机架上的节点。在本实验中，改进的副本放置策略相比于HDFS原有的副本放置策略其平均距离缩短了17.3%。

在比较了网络距离的效果后，为了验证节点硬件性能对集群负载的效果，分别在4个机架上的一个数据节点上提交了500个数据块，其中每个数据块大小都为64 MB。提交开始时，各数据节点都是空载状态。

采用默认的副本放置策略和改进的副本放置策略的结果如图5所示，其中纵坐标表示每个节点的负载率，即每一个节点已使用的容量与该节点总的容量的比值。

从图8中可以看出，通过4次提交数据块后，改进的策略模型中各节点的相对负载相比于原有的策略模型要均衡得多，改进的策略模型有效改善了集群的负载均衡。

图8 数据节点的负载率比较

表2展示了4次提交过程中的时间开销，即从文件提交到完成总的开销。由于改进的策略模型需要通过SVM算法寻找最优的副本放置处，这样就会增加一定的时间开销，但在改进的策略模型中，数据节点之间的距离也是算法的参考指标之一，所以在放置副本时改进的策略模型会优先考虑距离近的节点放置，这样就减少了副本放置的时间，改进策略模型相对于原有策略模型的时间开销差距并不是很大。

表2 2种策略的时间开销比较m s

5 结束语

HDFS原有的副本放置策略在副本放置过程中会导致集群负载失衡并且影响数据读写效率，针对以上问题，本文利用SVM提出了一种改进的副本放置策略SRPM。首先SRPM对集群中的每个节点服务器的负载、磁盘转速、CPU性能等硬件信息以及节点网络距离进行特征提取，然后SRPM利用提取的特征值将节点分类，最后SRPM在较优一类节点中选取适合放置副本的节点，实验结果证明，改进的策略模型可更好地实现负载均衡。下一步工作是进一步改进节点寻优方式，以减少其时间消耗。

［1］ Dean J，Ghemawat S.M ap Reduce：Simplified Data Processing on Large Clusters［J］.Communications of ACM，2008，51（1）：107-113.

［2］ Ghem awat S，Gobioff H，Leung S.The Google File System［J］.ACM SIGOPS Operating System s Review，2003，37（5）：29-43.

［3］ Shvachko K，Shvachko K，Kuang H，et al.The Hadoop Distributed File System［Z］.2010.

［4］ Eltabakh M Y，Tian Yuanyuan，Ozcan F，et al. CoHadoop：Flexible Data Placement and Its Exploitation in Hadoop［J］.Proceedings of VLDB Endow，2011，4（9）：575-585.

［5］ Khaneghah E M，Mirtaheri S L，Grandinetti L，et al.A Dynamic Replication Mechanism to Reduce Responsetime of I/O Operations in High Performance Computing Clusters［C］//Proceedings of International Conference on Social Computing.Berlin，Germ any：Springer，2013：110-130.

［6］ Kala K A.A Review on Hadoop-HDFS Infrastructure Extensions［C］//Proceedings of IEEE Conference on Information&Communication Technologies.Washington D.C.，USA：IEEE Press，2013：132-137.

［7］ Azzedin F.Towards a Scalable HDFS Architecture［Z］. 2013.

［8］ 丁世飞，齐丙娟，谭红艳.支持向量机理论与算法研究综述［J］.电子科技大学学报，2011，40（1）：2-10.

［9］ 范昕炜.支持向量机算法的研究及其应用［D］.杭州：浙江大学，2003.

［10］ 文益民，王耀南，吕宝粮，等.支持向量机处理大规模问题算法综述［J］.计算机科学，2009，36（7）：20-25.

［11］ 李红莲，王春花，袁保宗，等.针对大规模训练集的支持向量机的学习策略［J］.计算机学报，2004，26（5）：715-719.

［12］ Fan Rongen，Chang Kaiwei，Hsieh C，et al.LIBLINEAR：A Library for Large Linear Classifica-tion［J］.Journal of Machine Learning Research，2008，9（8）：1871-1874.

编辑 顾逸斐

Im p roved Strategy of HDFS Replica Placement Based on Support Vector Machine

LUO Jun，CHEN Shiqiang
（College of Computing Science，Chongqing University，Chongqing 400044，China）

A multiple copies of a rack awareness placement strategy is adopted in the Hadoop Distributed File System（HDFS）to cope with the storage of very large scale data and improve the fault tolerance.However，the HDFS does not consider the difference of each node server，which can result in load imbalance of clusters.Meanwhile，HDFS chooses remote rack node to place replica randomly，which may lead to a long distance between nodes，so that the transmission of data between nodes consumes a lot of time.To solve the aforementioned problems，this paper proposes an improved strategy of HDFS replica placement based on SVM.It can find the best node for replica by considering the disk utilization of each node，the node's hardware performance and network distance of nodes.Experimental results show that the proposed strategy effectively improves the load balancing in HDFS compared with the existing method used in HDFS system.

Support Vector Machine（SVM）；cloud storage；replica placement policy；Distributed File System（DFS）；load balancing；rack awareness

罗 军，陈仕强.基于支持向量机的HDFS副本放置改进策略［J］.计算机工程，2015，41（11）：114-119.

英文引用格式：Luo Jun，Chen Shiqiang.Improved Strategy of HDFS Replica Placement Based on Support Vector Machine［J］.Computing Engineering，2015，41（11）：114-119.

1000-3428（2015）11-0114-06

A

TP301.6

10.3969/j.issn.1000-3428.2015.11.020

罗 军（1961-），男，副教授、硕士，主研方向：数据库技术，系统建模及设计；陈仕强，硕士研究生。

2014-07-21

2014-11-12 E-m ail：chensqs@foxmail.com