基于分布式存储系统的数据布局策略研究

赵媛媛，王珂，周瑶

（西安建筑科技大学，西安710055）

0 引言

随着互联网和物联网在生活中的不断普及和完善，网络社交媒体的数据呈现几何增长的状态，大数据已融入到各个领域，成为企业最重要的生产因素，决定了企业以后的发展。如何有效对大数据进行存储和管理来更深层次的挖掘和利用数据中的信息已成为当前需要解决的一个重要问题。分布式存储系统成为目前存储大数据的主要方式。然而，随着存储数据量越来越多，原有的存储系统中设备不断进行更替，系统规模的不断扩大，人们对于数据存储有了更高的要求，需要设计一个可靠的数据管理方法来根据系统存储规模的变化来动态调整数据布局，保证系统在处理过程中能够快速地对数据进行存储并且使得系统负载保持均衡，这对于系统性能的提升至关重要。

1 传统的数据布局策略及其缺陷

数据布局策略是指为了达到存储目标，将数据通过某种映射机制来指派到合适的存储节点中。在存储系统中，存储目标在一定程度上决定了其所采用的数据布局策略。对于分布式存储系统来说，数据布局策略在系统响应、访问速率和负载均衡等方面有着更高的要求。数据布局的标准有以下几点：公平性、冗余、自适应性以及时空有效性[1]，在研究数据布局方面，为了提高系统性能，通常从降低系统平均响应时间、提高可用性和可靠性、保证系统负载均衡这几个方面来进行考虑。

在现有的布局策略中，Round-Robin[2]策略较为简单，但是对数据布局公平性和自适应性方面表现较差，SLAS 策略[3]在Round-Robin 策略的基础上考虑到了系统规模的扩展，但是需要迁移的数据量较大。在同构存储环境中，一致性Hash 策略[4]虽然能够解决迁移数据量大的问题，但是这种策略不适用于异构存储环境。基于聚类和一致性Hash 布局算法[5]在一定程度上降低了定位的时空复杂度，但是这种布局算法较为复杂。为了避免一致Hash 的异构扩展所引入大量虚拟节点造成了空间的浪费，引入设备容量的权重提出了线性方法和对数方法，然而这种策略公平性较低，需要定位数据的时间也长。在异构存储环境中，基于动态区间映射的数据布局算法需要较高的时空复杂度去定位数据对象，不适用于大量存储设备的存储系统。启发式算法中的SP、HP 和SOR 策略虽然考虑了数据特性，但是却没有考虑到数据布局的公平性和自适应性，无法动态适应系统规模的增长。

基于对上述策略的分析，本文在对数据文件进行布局时，主要考虑数据传输时间和负载均衡方面的问题。

2 数据布局算法的改进

2.1 改进的数据布局算法

在数据布局算法中，针对系统性能进行布局的启发式算法主要包括SP、HP 和SOR 三种策略。SP 策略[6]通过最小化磁盘上数据的服务时间来提高系统性能，将服务时间接近的数据采用Greedy 算法分配到同一磁盘上，对大小数据进行分类存储，然而热点数据的集中存放却容易造成磁盘访问过热，Lee 在SP 的基础上进一步提出了动态布局算法HP[7]，对成批到达的每一批数据采用SP 策略进行分配。SOR 策略[8]则克服了SP 算法中数据集中存放而造成的磁盘访问过热的问题，通过轮询方式对数据进行分配，然而这种算法却没有对大小数据进行分离。

本节在SP 和SOR 策略的基础上进行改进，根据数据节点负载的情况来对数据文件进行分配，基本思路是：首先获取数据节点的负载情况，根据平均负载将节点划分为两类，将请求数据按照大小进行降序排列，首先，先将数据通过Greedy 的方式存放到比平均负载低的这一类节点上，然后，再将剩余数据采用轮询方式存放到所有节点上。这种处理方式避免了数据的集中存放，另一方面提高了数据节点利用率，更好地实现系统负载均衡。

2.2 系统模型

在分布式存储系统中通常利用主节点的数据布局来对数据进行合理分配，客户端对存储在数据节点的数据进行访问，在一定程度上数据布局策略影响着系统的响应时间和负载。在设计数据布局策略时首先需要构建数据指派模型，即对数据和节点之间建立映射关系。

数据节点和数据之间的映射关系用决策函数φ(i,j)来表示，如果数据fi存储在节点dnj上，则φ(i,j)=1，反之为 0。由于数据只存储在单个节点上，因此

数据请求的响应时间包括等待时间和服务时间，其中服务时间为ti，等待时间为节点上正在等待处理的所有请求的服务时间，假设该节点上有请求集合Q 等待处理，那么等待时间，其中，rest(t)为当前节点正在处理请求的剩余时间，wri为等待处理的请求。

本文主要从系统响应时间和负载情况两个方面来研究数据布局策略对系统性能的影响。系统对请求的处理速度在一定程度上影响着系统性能，数据的合理放置有利于降低系统的响应时间。设tij为数据fi在节点dnj上的服务时间，则因此系统的平均响应时间为：

为了能够观察系统负载的变化情况，本文采用标准差LB 来表示混合存储系统负载变化，通过标准差LB 可以观察系统负载是否均衡。LB 的值越低，系统中数据节点间的负载越均衡。假设对于存储在节点dnj上的数据fi的请求访问速率为vij，因此，该数据fi在节点dnj上的负载为lbij=vij×tij，数据节点dnj的负载为，系统的平均负载为

由此可得，系统负载变化即数据节点负载标准差：

在本文中对于数据布局策略主要针对上述两方面进行设计，因此在上述公式中，获得节点和数据之间的映射关系可对系统响应时间和负载均衡进行分析，判断该布局是否满足负载均衡条件。

2.3 算法步骤

该算法具体步骤如下：

（1）计算数据节点平均负载-lb；

（2）根据平均负载将数据节点进行分组；

（3）将数据按照大小进行排序；

（4）初始化决策变量aij；

（5）将数据按照Greedy 方式分配到小于平均负载的节点上；

（6）如果数据没有分配完，则采用轮询的方式分配到所有数据节点上。

本改进策略的优点主要有：

（1）在数据存放时，确保数据节点负载保持均衡，根据数据大小进行升序排序，保证了小型数据的性能，同时也降低数据节点因大型数据存储而造成的等待，提高了系统性能。

（2）当负载小于平均负载的节点放置完之后，通过轮询的方式在所有的数据节点上放置数据，避免数据集中放置造成的单个节点重载，提高磁盘利用率。

3 测试和分析

3.1 实验环境配置

为了使系统环境达到实验要求，本文采用VMware Workstation 作为模拟平台搭建Hadoop 集群环境，通过对虚拟机的内存、存储容量、处理器核心数目配置来达到系统实验环境要求。

本文实验基于Hadoop 环境，测试环境由实验室多台计算机构成Hadoop 分布式系统，配置包括一个主节点和5 个从节点，节点之间通过局域网连接。

实验硬件配置为：主节点：八核CPU，内存8GB，硬盘500TB，从节点配置：四核CPU，内存4GB，硬盘250GB。

实验软件环境如表1。

表1

本文通过数据量和数据节点两个因素对三种策略进行了对比实验，观察系统响应时间和负载情况的表现。在每次实验中对同一组数据进行了5 次重复实验，尽可能排除由于运行异常对响应时间的影响，并采用平均值来反映不同因素对系统性能的影响。

实验通过对客户端请求数据量，数据节点数和请求数据大小三个参数进行调控来比较三种策略在不同条件下对系统响应时间和负载的影响情况。具体设置如表2 所示。

表2

3.2 请求数据量

请求数据量反映了系统接收到多个数据请求时的处理能力。在该实验中设定数据节点数为8，请求的数据大小服从100～500MB 的随机分布。实验结果从系统响应时间和系统负载两方面来进行观察。实验结果如图1-2。

从图1 可以看出，随着请求数据数量的增多，系统响应时间也越来越长，改进策略相较于SP 和SOR 策略系统响应时间短，表明系统可以同时处理大量的数据请求；对于系统负载来说，图2 中SP 策略由于采用Greedy 算法来存放数据，使得数据节点存放的数据过多导致负载过重，而SOR 策略和改进策略随着请求数据量的增多，节点之间负载更均衡。

图1 系统响应时间变化

图2 数据节点负载变化

3.2 数据节点数量

在本次实验中，通过设置不同的数据节点数来比较三种策略对系统性能的影响，实验中默认采用100个大小服从100～500MB 随机分布的请求数据来进行实验。实验结果如图3-4。

从图3 的实验结果可以看出，随着数据节点个数的增多，系统响应时间明显降低，因为随着数据节点数的增多，每个节点处理的数据量减少，系统处理性能提升。从三种策略的实验结果对比来看，SP 和SOR 策略处理时间降低幅度较大，当节点数增多时，这两种策略对于系统性能提升较为明显，而对于本改进策略来说，在系统响应时间方面表现比另外两个策略要好。

图4 显示了三种策略在系统负载方面的变化，随着数据节点数的增加，SP 策略对于系统负载没有较大的优化，SOR 策略和改进策略则呈现明显的下降趋势，而改进策略相较于SOR 策略负载均衡方面要更好一些。

图3 系统响应时间变化

图4 系统负载变化

因此，从上述分析结果可以看出，随着数据节点数的增多，SP 策略在负载方面表现比较差，改进策略在数据节点数不同的系统中都表现比其他两种策略要好。

4 结语

本文针对现有布局策略中存在的问题进行分析，从系统响应时间和负载均衡两方面考虑分布式存储的系统性能，基于SP，SOR 策略提出了改进数据布局策略，并通过实验验证了该改进策略的有效性，通过利用数据节点的存储能力，解决在客户端访问频繁的情况下磁盘过热的问题，最后通过与SP 和SOR 策略进行比较，验证本改进算法的可行性，结果表明，该布局策略相较其他两种策略对系统性能的提升效果要好。