一种基于存储介质类型和加权配额的存储资源管理方法

摘要

本发明涉及一种基于存储介质类型和加权配额的存储资源管理方法，包括步骤：存储设备和用户空间文件系统的挂载和读写请求分发，其中读写请求分发采用的Weighting Jump算法引入了加权分配特性，具有较高的计算速度、无状态调度和极低的内存消耗，这种方法采用类似谷歌John Lamping和Eric Veach提出的依概率跳变的方法来实现。能够从概率的层面保证存储资源的分配服从设定的权重，最小化标准误，并且具有比原有Hadoop集群的资源管理系统Yarn中实现更低的时间复杂度和内存消耗。克服了之前资源管理系统Yarn中实现的磁盘资源分配算法轮询检索目录的低效性，具有可伸缩性，且在扩展时，能够依概率最小化原有数据的移动。

说明书

技术领域

本发明涉及一种基于存储介质类型和加权配额的存储资源管理方法，属于大数据存储和分布式计算领域。

背景技术

随着大数据存储和混合存储介质技术的发展，存储资源管理和分配方法变得越来越重要，也面临着越来越严重的考验。Apache开源社区开发的Hadoop大数据处理系统已经成为大数据领域最具代表性的解决方案。Hadoop包括HDFS(Hadoop Distributed FileSystem)分布式文件系统和Yarn(Yet Another Resource Negotiator)资源管理系统和MapReduce数据处理框架。其中运行的MapReduce应用对于数据的访问分为访问map阶段读取输入文件时、Reduce阶段写入输出文件时对HDFS分布式文件系统的访问和shuffle阶段读写中间数据时对于本地系统存储资源的访问。随着混合存储技术的发展，应用对于存储资源的访问也引入不同的考虑因素，因此基于存储介质和加权分配的存储资源分配技术也得到学术界和工业界越来越多的重视。

由于MapReduce应用在shuffle(数据混洗)阶段把中间数据存放于本地系统中，访问序列具有高随机性并对于特定应用会产生数倍于原始输入数据大小的中间数据文件。因此优化中间数据的存储效率有较高的研究价值。对于中间数据的存储资源管理，能否根据存储资源的存储空间容量平衡地分配存储数据是至关重要的。从存储效率的角度来看，存储资源管理技术需要满足的条件包括平衡性、低内存效率、存储介质的选择性、低算法复杂度、容错性和伸缩性。尤其是伸缩性，需要在新增存储设备时，最小化已有数据的移动。然而在现今已有的存储资源管理或分配方法中，还没有一种方法能有效的将上述条件全部满足。本发明提出了一种新的存储资源管理方法，能有效的利用混合存储介质的差异性并满足上述优化要求。

发明内容

本发明的技术解决解决问题：克服现有技术的不足，提供一种内存消耗小的高性能的存储资源管理方法，该方法将存储资源的介质信息和容量信息有效的结合起来进行加权一致性哈希计算，能够更平衡高效地管理存储资源。

本发明的技术解决方案：一种基于存储介质类型和加权配额的存储资源管理方法，包括：用户空间文件系统的挂载和读写请求的分发两个步骤；

所述用户空间文件系统的挂载步骤如下：

(11)将多块固态硬盘和机械硬盘成对分别挂载于当前文件系统中。将第1块固态硬盘和第1块机械硬盘分别挂载到有完全读写权限的目录/ssd-1和/hdd-1下，将第2块固态硬盘和第2块机械硬盘分别挂载到有完全读写权限的目录/ssd-2和/hdd-2下，将第n块固态硬盘和第n块机械硬盘分别挂载到有完全读写权限的目录/ssd-n和/hdd-n下，直至将全部存储设备挂载到/ssd1～/ssdn和/hddn～/hddn下；

(12)将每对固态硬盘目录和机械硬盘目录的访问封装到用户空间文件系统中，用户空间文件系统优先将访问重定向到固态硬盘目录中，当固态硬盘目录的存储空间不足时，使用近期最少使用算法(LRU)将固态硬盘目录中近期最少使用的文件置换到机械硬盘目录中。

(13)启动多个进程,运行步骤(12)中的用户空间文件系统，并将这多个进程提供的文件服务都挂载到Hadoop系统配置中的中间数据存储目录中，监听这些中间数据存储目录的读写请求；

所述读写请求的分发步骤如下：

(21)将步骤(13)中的多个进程从1开始进行顺序编号，检查这些进程所提供文件服务的剩余容量，将这多个剩余容量的值，记录为请求分发的权重比例数组W；

(22)当对于Hadoop集群(Hadoop是一个由Apache基金会所开发的分布式计算系统)中用户提交的计算任务产生读写请求时，将读写请求的路径名和文件名，以及步骤(21)中计算的权重比例数组W输入Weighting Jump算法，将输出的值作为进程编号，将读写请求分发到步骤(21)中符合该编号的进程中。完成请求分发的操作。

所述的用户空间文件系统的挂载步骤中，使用FUSE库封装固态硬盘目录和机械硬盘目录的文件操作，对外实现POSIX接口的文件操作。

所述用户空间文件系统中对外提供一个统一的逻辑视图，这种逻辑视图的实现是通过符号链接技术构建的。用户空间文件系统将固态硬盘目录作为逻辑视图，置换到机械硬盘目录中的文件以符号链接的形式存放到固态硬盘目录中，指向机械硬盘目录中的原文件。而置换到固态硬盘目录中的文件以原文件的形式存放到固态硬盘目录中。将固态硬盘目录中近期最少使用的文件置换到机械硬盘目录中的具体过程如下：

(31)当固态硬盘目录的空间不足并且置换算法使用的调度缓存队列不为空，弹出缓存队列首部的文件路径；

(32)将步骤(31)的文件路径下的该文件复制到机械硬盘目录中；

(33)删除固态硬盘目录下的该文件；

(34)在固态硬盘目录中建立该文件的符号链接，指向步骤(32)中的机械硬盘目录中的该文件。

将机械硬盘目录中访问较多的文件F置换到固态硬盘目录中的具体过程如下：

(31)若固态硬盘容量不足，则先执行步骤(31)到(35)；

(32)将文件F复制到固态硬盘中；

(33)删除固态硬盘目录中该文件的符号链接；

(34)将机械硬盘中文件F删除；

(35)更新缓存队列中文件F的位置。

Weighting Jump算法的具体实现逻辑如下：

(1)输入步骤(22)中的权重数组W、请求路径和文件名；

(2)将请求路径和文件名输入字符串哈希函数，哈希函数的输出是一个长整型；

(3)将步骤(2)中获得的长整型作为种子输入64位的线性同余随机数发生器；

(4)新建变量b为0，变量b为一个整数，代表本算法计算的进程编号。新建变量n，为步骤(21)中进程的数量；

(5)运行步骤(3)中的随机数发生器，随机数发生器的输出是一个随机数R；

(6)根据公式求出j的最大值。若j的值小于n，则将b的值更改为j；若j的值大于等于n，则维持b的值不变。公式中W_x为步骤(1)中权重数组W的第x项，而floor()函数表示求上确界，b为步骤(5)中定义的变量，R为步骤(5)中获得的随机数；

(7)重复步骤(5)至步骤(6)直至b的值不再变化，输出变量b。输出步骤(6)中所算出的变量b，即：算法输入的请求的路径、文件名时，应分发给编号为b的进程进行处理。因此，将此次读写请求分发给编号为b的进程。完成请求分发步骤。

本发明与现有技术相比的优点在于：本发明采用一致性哈希算法保证了技术的可伸缩性和容错性；并且技术中一致性哈希算法的实现Weighting Jump算法相比于Karger的割环法实现减少了内存消耗；由于本发明提出的基于存储介质和加权一致性哈希的存储资源管理方法能更全面得考虑存储介质和存储容量，并且Weighting Jump算法中使用的概率算法减少了内存消耗，因此具有更高的鲁棒性。

附图说明

图1为本地存储资源管理的系统结构图；

图2为本技术在实际分布式计算框架中应用的系统结构图；

图3为本技术与现有技术的内存消耗对比图；

图4为本技术与现有技术的运行时间对比图；

图5为本技术与现有技术的标准误对比图。

具体实施方式

下面结合附图详细解释本发明提出的基于存储介质和加权一致性哈希的存储资源管理方法。

本发明的存储资源管理方法应该包含以下几个步骤：存储设备的挂载、用户空间文件系统的挂载、运行Hadoop应用、Hadoop应用读写请求的分发。其系统结构如图1所示。首先将存储设备按照存储介质的不同挂载到不同的目录下，再通过用户空间文件系统封装对于这些目录的文件操作请求。然后通过多个进程启动用户空间文件系统提供FUSE文件服务，并挂载到Hadoop系统的中间数据存储目录，提高存储资源的并发利用率。然后通过修改Hadoop系统的源代码，添加请求分发模块，使用Weighting Jump算法平衡多个进程的负载。

本发明提出的基于存储介质和加权一致性哈希的存储资源管理方法主要涉及MapReduce大数据处理框架中shuffle阶段的中间数据读写这个环节，如图2所示，本发明将Map函数输出的缓冲区的溢写中间数据交由本地资源存储分配器管理。Hadoop应用的读写请求经由请求分发模块的Weighting Jump算法，分发到某个运行中的用户空间文件系统。用户空间文件系统通过数据操作模块封装的FUSE API实现，操作实际挂载的存储设备。当存储空间足够时，优先使用固态硬盘，否则使用置换算法在固态硬盘和机械硬盘间进行文件的置换。中间数据文件和存储目录的具体映射关系由一致性哈希算法的单调性保证，具体步骤如下：

1.用户空间文件系统的挂载

本发明提出在分布式计算框架(如MapReduce)的中缓冲区溢写到本地存储资源时，对于中间计算数据的临时文件，使用挂载的用户空间文件系统，具体步骤如下：

(1)将多块固态硬盘和机械硬盘成对分别挂载于当前文件系统中。将第1块固态硬盘和第1块机械硬盘分别挂载到有完全读写权限的目录/ssd-1和/hdd-1下，将第2块固态硬盘和第2块机械硬盘分别挂载到有完全读写权限的目录/ssd-2和/hdd-2下，将第n块固态硬盘和第n块机械硬盘分别挂载到有完全读写权限的目录/ssd-n和/hdd-n下，直至将全部存储设备挂载到/ssd1～/ssdn和/hddn～/hddn下；

(2)将每对固态硬盘目录和机械硬盘目录的访问封装到用户空间文件系统中，用户空间文件系统优先将访问重定向到固态硬盘目录中，当固态硬盘目录的存储空间不足时，使用近期最少使用算法(LRU)将固态硬盘目录中近期最少使用的文件置换到机械硬盘目录中。逻辑上的文件和目录通过符号链接操作物理上实际的文件和目录。如果文件置换模块将文件换出到机械硬盘中，则固态硬盘中则只剩下符号连接；如果文件置换模块将文件换入到固态硬盘中，则固态硬盘存放着实际的文件。使用符号链接而不使用哈希表的原因有两点：第一点是因为符号链接是持久化的，因此不需要担心内存和磁盘不一致的问题，可以保证强一致性；第二点是由于符号链接是类Unix系统中原生支持的；

(3)启动多个进程运行步骤(2)中的所有用户空间文件系统，并将多个进程提供的FUSE文件服务都挂载到Hadoop系统配置中的中间数据存储目录中，通过Linux内核的FUSE模块监听挂载目录的读写请求；

本发明利用Hadoop应用对于中间数据的访问以随机I/O为主，且存活时间较短的特点，将中间数据优先存储于固态硬盘中，仅在空间不足时将文件置换到机械硬盘中。利用固态硬盘对于随机I/O的加速特性提高Hadoop应用的存储效率。

2.读写请求的分发

本发明提出采用Weighting Jump算法进行读写请求的分发。步骤中线性同余随机数发生器进行加权哈希值的计算，从而获得存储目录的编号。目标是为了解决存储设备的访问平衡性和效率问题，同时在存储设备发生故障或者新增存储设备时，最小化数据的移动。本发明采用的方法具有较好的平衡性、单调性、伸缩性、高效和极低的内存消耗。其中平衡性是指哈希的结果能够尽可能按照权重比分布到所有的存储目录中去，这样可以使得所有存储资源都得到利用。单调性是指虽然分配器没有存储已有的数据文件和存储目录的映射关系，哈希的结果能够保证原有已分配的内容可以通过设置随机数发生器的种子重新计算出映射关系。伸缩性是指当存储设备出现故障或者新增存储设备时，仅通过短暂的初始化分配器，即可适配新的存储环境，计算出最小数据移动的数据文件和存储目录的映射关系。高效是指算法的复杂度仅为O(lgn*lgn)，其中n为中间数据存储目录的数量；内存消耗仅为O(n)，且系数为一个极小的常数。具体步骤如下：

(1)输入步骤(22)中的权重数组W、请求路径和文件名；

(2)将请求路径和文件名输入字符串哈希函数，哈希函数的输出是一个长整型；

(3)将步骤(2)中获得的长整型作为种子输入64位的线性同余随机数发生器；

(4)新建变量b为0，变量n为步骤(21)中进程的数量；

(5)运行步骤(3)中的随机数发生器，随机数发生器的输出是一个随机数R；

(6)根据公式求出j的最大值。若j的值小于n，则将b的值更改为j；若j的值大于等于n，则维持b的值不变。公式中W_x为步骤(1)中权重数组W的第x项，而floor()函数表示求上确界，b为步骤(5)中定义的变量，R为步骤(4)中获得的随机数；

(7)重复步骤(5)至步骤(6)直至b的值不再变化，输出变量b。变量b是输出的进程编号。因此将此次读写请求分发给编号为b的进程。完成请求分发步骤。

需要指出的是，与Karger使用的割环法实现相比，本发明不要求读写请求中的路径名，或使用的字符串函数具有均匀性或平衡性，这是由于本发明使用内置64位的伪随机数生成器来对每一次输入参数做再哈希，所以结果分布的平衡性与输入参数的分布无关，由随机数生成器的均匀性保证。下面详细说明Weighting算法的实现和原理：

设算法的输出为文件置换模块的编号j，定义j＝ch(key,n)，其中key为计算任务编号的哈希值key，n为文件置换模块的数量。由于编号为0到n-1的整数，所以对于任意的key，有ch(key,1)＝0，此时n＝1。为了满足上文所述的设计目标中的平衡性，当n的数量增加到2时，对于一部分key，ch(key,2)的值需要保持与ch(key,1)一样，依旧为0，这部分的比例占总量的而另外比例的ch(key,2)的值则需要跳变为1。以此类推可以得出公式因此此时可以使用一个随机数发生器来决定某一个key的结果要不要跳变，这个随机数发生器的状态仅仅依赖于key。通过n次增大编号的范围，最终可以将所有key的结果按照权重分配到n个文件置换模块。

借鉴于John Lamping和Eric Veach的发现，大多数情况下，ch(key,k)的值是不会跳变的，而且随着n的值越来越大，这个概率也变得越来越低。因此可以直接追踪编号的跳变路径。记上一个跳变的编号为b，假设下一个发生跳变的编号以一定的概率为j，那么从b+1到j-1中间发生的多次增大编号的范围都不能发生跳变。因此对于在区间(b,j)内的任意整数i，j是下一个跳变编号的概率可以记为P(j≥i)＝P(ch(key,i)＝＝ch(key,b+1))。

因此经过代入约分有：

上述推导的实际意义即为j>＝i的概率为此时通过取一个在(0,1)区间内的随机数R，规定当时，意义为j>＝i，所以有这样就得到了i的上界。

由于对于任意的i都要有j>＝i，因此有这样算法就可以根据一个随机数R得到下一个跳变的编号值j(满足公式的最大j取值)，也即步骤(3)中的循环过程。

对采用上述Weighting Jump计算方法的请求分发模块，本发明不需要存储数据文件和存储目录的映射关系，这一点节省了大量的存储空间，可以从图3的内存消耗对比图看出这一优势：随着挂载目录的规模的增大Kager算法的内存消耗很快达到4500MB，而谷歌的Jump Consist Hash算法和本发明中的Weighting Jump算法的内存消耗依然能维持在一个较小的范围(4MB和8.1MB)。本发明与现有的Kager割环法相比，由于不需要维护虚节点环，节省了大量内存垃圾回收的时间，同时增加了加权配比的功能；本发明与谷歌的跳变式实现的一致性哈希计算的方法相比，增加了加权配比的功能，同时能够维持与其相近的时间消耗和标准误；本发明与传统的轮询法或轮盘赌技术相比，将读取的时间复杂度从O(n)降低到了O(logn)，这些从图4的平均耗时和图5的标准误对比图可以看出。图4中Karger算法在虚拟节点的数量K＝100或K＝1000时的平均执行时间随着挂载目录的规模的增大，也随着明显增大。而Weighting Jump算法和Karge算法虚拟节点数量K＝10时，请求分发的平均时间能够依然维持较小的数字。另一个很重要的因素就是请求分发的均衡性通过图5的标准误对比图进行比较，由图5可以看出Karge算法的虚拟节点数量K＝4或K＝10时，标准误明显高于后续几个其他的实现。而Weighting Jump算法在上述两个比较中在平均执行时间、内存消耗和标准误上的表现都比较优秀。Karge算法在虚拟节点数量多时消耗的执行时间较多，而虚拟节点数量较少时却有标准误较大的缺点。谷歌的Jump算法在上述三个方面的表现最为优秀，但却缺少了根据权重分发请求的功能。

如上所述，本发明利用具有一致性哈希计算具有单调性的优点减去了中间数据文件和存储目录的映射关系的保存，与传统的Kager割环法实现技术相比，这种方法能有效的同时减少内存消耗，同时加入了用户配置选择存储介质和不同应用对于存储介质的依赖程度的考虑因素，因此能够更加全面的应对大数据存储领域的需求，从而提高存储性能。另外，本发明利用一个在概率算法的基础上提出的线性同余伪随机数来减少输入参数不均匀时受到的字符串哈希函数的干扰，因此能够使得存储负载的平衡性更加有效可靠，从而进一步提高存储性能。这种方法采用类似谷歌John Lamping和Eric Veach提出的依概率跳变的方法来实现。能够从概率的层面保证存储资源的分配服从设定的权重，最小化标准误，并且具有比原有Hadoop集群的资源管理系统Yarn中实现更低的时间复杂度和内存消耗。克服了之前资源管理系统Yarn中实现的磁盘资源分配算法轮询检索目录的低效性，具有可伸缩性，且在扩展时，能够依概率最小化原有数据的移动。

上面所述的仅是体现本发明基于存储介质类型和加权配额的存储资源管理方法的实施例。本发明并不限于上述实施例。本发明的说明书是用于进行说明，不限制权利要求的范围。对于本领域的技术人员，很显然可以有很多的替换、改进和变化。凡采用等同替换或等效变换形成的技术方案，均落在本发明要求的保护范围内。