用于云存储数据服务器的I/O请求调度算法

李　宇

(北京交通大学软件学院, 北京 100044)

在大数据时代,人们日常会产生大量的数据(如视频、照片、个人状态等),以Facebook为例,其每天存储三亿张用户上传的照片[1].为了吸引用户,国内外互联网公司纷纷推出相应的云存储产品,如Dropbox[2]、百度云网盘[3]、腾讯微云[4]、360云盘[5]等.在云存储应用环境中,用户的数据(如视频、语音、图片、文字等)集中存放在分布式文件系统(distributed file system, DFS)中,用户通过浏览器/云存储客户端向应用服务器发送数据请求,由应用服务器连接DFS来获取数据并返回给用户在上述应用环境中,用户的数据请求具有以下特点:一方面,云存储的用户量非常庞大,数据服务器会收到大量的并发I/O请求;另一方面,不同类型I/O请求的发送频率和对响应时间的要求也不尽相同(如在线播放视频和浏览图片时,对端到端的延迟和数据传输带宽的要求有很大差别).

目前，在云计算存储环境下的I/O调度相关研究主要集中在虚拟机资源的合理调度上.同时考虑能耗和负载的虚机调度算法[6],允许虚机重新声明CPU片段供使用.面向云存储的I/O资源效用优化调度算法[7]通过服务水平目标,采用最早截止时间优先算法或者预计效益来提高总收益率.动态优先级排序[8]基于多属性决策理论,以离差最大化方法计算I/O任务的优先级评估属性权重并综合评估,将虚拟域的差异体现在虚拟机的I/O调度上.

当前常用DFS(如Ceph[9]、GlusterFS[10]、HDFS[11]等)的设计关注点均在如何高效地存储和查询元数据、如何把数据均匀地分散到不同的数据服务器,以及数据的可靠性等方面,对数据服务器守护进程(data server daemon, DSD)的I/O请求调度并没有进行特别的设计,采用的是先来先服务(first in first out, FIFO)策略,将所有并发请求同等对待,以尽力而为(best effort)的方式顺序处理.这种调度策略侧重于减小开销和有效利用网络带宽,能够提高系统整体的平均响应时间.然而,它并未考虑不同类型I/O请求的时效性要求,使得需要实时响应的I/O请求(如在线视频播放)和普通I/O请求(如图片浏览)一同排队等待,前者可能会被阻塞相当长的时间而无法得到及时处理,从而导致整个系统服务质量降低.

针对上述问题,本文提出一种用于DSD基于优先级的周期性调度算法(priority-based periodic scheduling algorithm, PPSA).PPSA首先对来自客户端的I/O请求进行分类,并赋予不同的优先级;然后以合适的时长作为周期,以分时间片的方式对不同优先级的I/O请求进行周期性的调度.PPSA在保障实时请求响应性能的同时,也兼顾了其他优先级请求的响应性能.

1　算法概述

当前主流的云存储应用环境中,用户使用数据的方式基本都是“一次写、多次读”(write once, read everywhere)模式:用户上传的文件或者分享给别的用户,或者是对已有数据的备份,只有很小部分文件在上传之后会被修改[12].因此,本文主要研究DFS中数据服务器读I/O请求的调度问题,写I/O请求仍采用原来的调度方式.后文如无特别说明,所有出现的I/O请求均指读I/O请求.

1.1　工作原理

PPSA的工作原理见图1,它工作在DFS的DSD内.客户端收到上层应用发出的I/O请求后,通过网络将其发送到存储相应数据的服务器DSD缓冲队列中;之后,分类器根据分类配置文件对I/O请求进行分类,并把分类后的I/O请求放入对应优先级的请求队列;最后由调度器统一进行调度.

图1　PPSA工作原理Fig.1　Working principle of PPSA

1.2　I/O请求分类

在云存储应用环境中,用户的数据请求最终由应用服务器进行处理,而应用服务器则通过访问DFS中的数据服务器来获取用户需要的数据,并将其传回给用户.根据当前主流云存储系统的业务类型,可以把应用服务器发出的I/O请求分为如下4类:

(1) 实时I/O请求:通常为在线视频/音频播放类I/O请求.这类请求可对应于实时可变比特率(real-time variable bit rate, rt-VBR)类[13],其生成和发送具有突发性和一定的连续性,要求最小的延迟和一定范围内的传输带宽保证,用符号t0表示;

(2) 非实时I/O请求:通常为文件浏览类(如在线浏览图片、文档等)I/O请求.这类请求可对应于非实时可变比特率(non-real-time variable bit rate, nrt-VBR)类,允许一定程度的数据响应延迟,用符号t1表示;

(3) 下载I/O请求:通常为数据下载类I/O请求.这类请求可对应于不指明比特率(unspecified bit rate, UBR)类,对传输带宽和延迟没有要求,可采用“尽力而为”的方式提供服务,用符号t2表示;

(4) 预取I/O请求:为提高系统I/O性能,可通过对历史访问信息的分析,由DFS客户端预测未来的I/O请求并进行预取操作[14].这类请求对应于可用比特率(available bit rate, ABR)类[15],对传输带宽和延迟没有要求,且不要求一定被处理.这类I/O请求可在系统空闲时进行处理,若系统负载较重,在一定期限内未得到处理,则可直接丢弃,用符号t3表示.

在云存储应用环境中,可采用专一功能的应用服务器/集群来处理不同类型的用户数据请求(如视频播放服务器/集群、文件服务器/集群、下载服务器/集群).因此,可以通过分类配置文件来配置与应用服务器/集群相对应的I/O请求类别.此外,在该配置文件中还可以配置不同I/O请求类型的其他要求(如在线视频播放时所要求的最小传输带宽、最大传输延迟等),以便分类器对I/O请求进行更加精确的分类.

对于预取请求,由DFS客户端在发送请求时设置一个PREFETCH标志,PPSA分类器可根据该标志识别出这类I/O请求.

1.3　算法参数

在PPSA中,来自DFS客户端的I/O请求经分类器后进入4个不同的请求队列(队列0～3).其中,队列0中的I/O请求均为实时请求(t0类),队列1中的I/O请求均为非实时请求(t1类),以此类推.这4个队列的优先级分别为Pri0、Pri1、Pri2和Pri3,则有Pri0>Pri1>Pri2>Pri3.

对I/O请求进行基于优先级的调度时,高优先级队列中的请求应当优先处理.但若严格按照优先级的大小顺序来进行处理,在有大量突发高优先级请求的情况下,低优先级的I/O请求可能会长时间等待,甚至发生超时.基于公平性的考虑,PPSA中的I/O请求处理采用一种周期性的调度策略——选取一个适当长度的时间段T作为调度周期,并把每个周期分为4个时间段:实时请求处理阶段、非实时请求处理阶段、下载请求处理阶段和预取请求处理阶段,各时间段内的时间片优先用于处理对应类型的I/O请求.在一个调度周期内,把实时请求、非实时请求、下载请求和预取请求对应的时间段时长分别记为Trt、Tnrt、Tdld和Tpre,如图2所示,其计算方法如式(1)～(4).

(1)

Tnrt=(T-Trt-Tpre)β,

(2)

Tdld=(T-Trt-Tpre)(1-β),

(3)

Tpre=Tσ,

(4)

式中:vi为调度周期T内的实时请求对应的DFS客户端与DSD之间的一条I/O流所需的传输带宽,则∑vi表示一个调度周期T内所有实时I/O流所需的传输带宽之和;V为DS的总网络传输带宽;α为调节因子,以确保预留的时间片能够满足所有实时请求的需求;β为调节因子,用于平衡非实时请求和下载请求的处理时长;σ为比例系数,可由用户自行设定.

图2　周期性调度示意Fig.2　Periodic scheduling process

1.4　数据结构

对PPSA来说,请求队列中I/O请求的组织是影响算法性能的一个重要因素,因此,必须对这些请求进行有效的组织和管理.由于所有I/O请求的目标均是数据服务器(DS)上的文件,所以,可以I/O请求的目标文件为依据来组织它们.

PPSA的每个请求队列中I/O请求的组织方式如图3所示.其中,哈希表存放的是DS上文件的全路径与请求列表的映射,格式为:.每一个进入队列的请求,根据其目标文件在DS上全路径的哈希值被插入相应请求队列的队尾.

图3　请求队列数据结构Fig.3　Data structure of a request queue

为了提高效率,PPSA还对哈希表中每个队列内的所有请求建立了一棵红黑树,并以每个请求数据在其目标文件内的偏移量作为关键字.由于红黑树中不同节点的关键字必须不同,所以,对于偏移量相同的I/O请求,在树的相应节点中使用不同的指针指向对应的请求即可.

2　算法流程

PPSA在一个调度周期T内为各类I/O请求分配时间片配额,配额内的时间片优先用于处理对应类型的I/O请求.在同一时刻如果有多类请求满足调度条件,则根据其优先级的高低来依次处理实时请求、非实时请求和下载请求.在调度周期内如果某类I/O请求的时间片配额有剩余,则剩余的时间片可被其他种类的I/O请求按优先级从高到低的顺序来使用.在前三类请求均处理完毕后,若仍有空闲时间片,则进行预取请求的处理.

PPSA优先考虑高优先级请求的响应性能,同时,通过时间片资源的预分配,可有效保障其他种类I/O请求所需的数据传输带宽.PPSA的处理流程如下:

Algorithm PPSA

Output:时间片配额分配

Begin

loop

统计当前所有I/O流的传输带宽之和∑vi

步骤1基于时间片配额处理取请求

/*一个调度周期即为一个统计窗口*/

更新一个统计窗口内队列Q的相关统计数据,包括:每条实时I/O请求流成功传送给目标DFS客户端的数据总量Rrti

callhandle_Q(非实时请求队列Q(t1),Tnrt)

更新一个统计窗口内队列Q的相关统计数据,包括:队列Q成功传送给所有DFS客户端的数据总量Rnrt

callhandle_Q(下载请求队列Q(t2),Tdld)

更新一个统计窗口内队列Q的相关统计数据,包括:队列Q成功传送给所有DFS客户端的数据总量Rdld

步骤2基于优先级处理请求

/*分别计算当前调度周期内剩余的时间片Trt、Tnrt和Tdld的长度.按优先级从高到低进行处理*/

for eachQin {Q(t0),Q(t1),Q(t2)}; do

callhandle_Q(Q,trest)

end for

步骤3处理预取请求

callhandle_Q(Q(t3),trest)

/*采用bestjofk策略(j=8,k=10)预测I/O请求的未来趋势,并根据预测结果来调节算法参数.之前对Tnrt、Tdld和Tpre的值进行了修改*/

根据式(2)～(4)重新计算Tnrt、Tdld和Tpre

Unrt←Rnrt/(TnrtV)

/*对最近10个统计窗口的8个,当Unrt超过100%或小于90%时,对参数β做正或负0.1的修正,对参数α做正或负0.05的修正*/

Udld←Rdld/(TdldV)

/*对最近10个统计窗口的8个,当Udld超过100%或者小于90%时,对参数β做负或正0.1的修正,对参数α做负或正0.05的修正*/

/*设置参数边界为0.10和0.90*/

/*设置参数边界为0.05和0.30*/

end loop

End

Algorithmhandle_Q

Input:请求队列Q,Q对应的处理时长为Tq

Output:队列Q相关的统计数据

Begin

if队列Q非空 andTq>0 then

N←队列Q哈希表的大小

for 队列Q哈希表中的每文件file; do

/*时间片用完则返回,计算分配给每个目标文件的处理时长*/

t←Tq/N

pre_offset←上一次访问的file的offset

ifpre_offset<0 orpre_offset>file对应的红黑树中的最大offsetthen

pre_offset←0

end if

whilet>0 do

req←file对应的红黑树中offset≥pre_offset且offset最小的请求

ifreq为预取请求andreq的等待时间超过设定的阈值 then

丢弃请求req

else

处理请求req

t←t—处理req的时间

Tq←Tq—处理req的时间

pre_offsetreq的offset

end if

end while

记录file的pre_offset属性

end for

end if

End

3　实验及结果分析

为了检验PPSA的性能,使用PFSsim[16]进行了仿真实验.PFSsim是一款基于OMNeT++[17]和DiskSim[18]的DFS仿真器,它是跟踪驱动(trace-driven)的,主要用来测试和验证DFS的I/O管理策略和一些新的设计思想.

PFSsim模拟的DFS的配置为1个元数据服务器和4个数据服务器(DS).设置DS的内存容量为8 GB,其本地文件系统(包括缓存)使用的内存为6.4 GB,缓存策略为LRU (least recently used );根据Linux的默认脏数据率(dirty_ratio,默认为内存大小的40%),设置最大脏数据大小为3.2 GB;页面/块大小均设置为4 KB;硬盘的访问速度则根据真实的测量结果来设定(被测服务器配置8 GB内存,8块15 000转SAS硬盘组成RAID5阵列).客户端和数据/元数据服务器之间的网络带宽设置为1 Gbit/s,网络延迟为0.2 ms.

实验中使用的工作负载特性为实时请求(t0类)和下载请求(t2类)的分布均为均匀分布,非实时请求(t1类)和预取请求(t3类)的分布均为泊松分布.

在实验中,每个请求流由PFSsim中的一个客户端组件来处理,每个请求所需的数据大小均为128 KB.t1类请求的平均到达速率为每秒2个请求,t2/t3类请求的平均到达速率为每秒1个请求.所有I/O请求均为同步读请求,DFS客户端收到一个请求的响应后,才会发送下一个请求.PPSA的调度周期为50 ms.

3.1　响应时间

该实验用于测试在不同的系统负荷条件下,分别采用FIFO和PPSA方式进行调度时,系统对不同类型请求的响应时间.实验设定了2种不同的负载环境,分别为

(1) 轻负载环境:每个DSD均接受20个t0类请求流(每个请求流要求的最小数据传输速度均为5 Mbit/s),50个t1类请求流,100个t2类请求流和50个t3类请求流.

(2) 重负载环境:每个DSD均接受20个t0类请求流(每个请求流要求的最小数据传输速度均为10 Mbit/s),200个t1类请求流,100个t2类请求流和50个t3类请求流.

实验记录了进入平稳状态后,分别采用FIFO调度策略和PPSA调度策略时,DSD对不同类型I/O请求的响应时间.

从图4中可以看出,在轻负载环境下,采用PPSA调度方式时,t0类请求和t1类请求的响应速度比FIFO调度策略有提高(前者t0类请求和t1类请求的平均响应时间分别为1 981 μs和2 000 μs,后者对应类型请求的平均响应时间分别为2 005 μs和2 008 μs),但差别不大.

在重负载环境下,采用PPSA调度方式时,t0类请求的响应时间相比FIFO调度方式有较大降低(前者平均值为2 045 μs,后者平均值为2 201 μs);而t1类请求的响应时间相比FIFO调度方式有所降低,但差别不是很大(前者平均值为2 152 μs,后者平均值为2 196 μs)

由于系统对每个I/O请求的响应时间包含了数据在网络上的传输时间(约1 000 μs)和网络延迟(400 μs),所以,采用PPSA调度方式,在重负载情况下DSD对实时请求的响应速度提高了20%左右,而对非实时请求的响应速度也有一定的提升.当然,这种性能提升是以低优先级请求响应性能的降低为代价的,可以通过调节算法的参数来对不同优先级的请求进行平衡.

(a) 轻负载循环下t0类I/O请求(b) 轻负载循环下t1类I/O请求(c) 重负载循环下t0类I/O请求(d) 重负载循环下t1类I/O请求图4 不同调度策略的系统响应时间比较Fig.4 Comparison of system response times for different scheduling policies

3.2　平均等待队列长度

该实验用于比较DSD采用不同的调度算法时,系统在不同负荷下对各类请求的响应情况.统计各类请求的平均等待队列长度和最大等待队列长度,并将统计结果与FIFO算法及多队列优先级调度算法相比较.实验中,t0类请求流要求的最小数据传输速度均为5 Mbit/s.

表1为其他类型请求负载一定的条件下,t0类请求流的数量对不同类型请求队列的平均队列长度的影响.实验中,t1类请求流的数量为200,t2类请求流的数量为300,t3类请求流的数量为100.从表1中可以看出,采用FIFO调度策略时,所有类型请求的平均等待队列长度基本相同;这是因为在实验中设置的条件使响应数据所需的传输带宽超过了网络带宽,因此,不管t0类请求流的数量如何增加,系统对所有类型请求的响应性能都没有变化.

表1　t0类请求流数目对系统响应性能的影响Tab.1　Effect of the number of class t0 request flows on the system response performance

采用优先级调度策略时,随着t0类请求流数量的增加,系统优先保证高优先级请求的响应性能,但是对低优先级请求的性能不做保证;当t0类请求流的数量增加到100时,所有的t2类请求均无法得到响应.采用PPSA调度策略时,在算法的设定参数范围内,系统的响应性能与优先级调度策略相当;当t0类请求流的数量增加到80时,由于算法的调节作用,t0类、t1类和t2类请求的响应性能均优于优先级调度策略;当t0类请求流的数量增加到100时,不仅t0类和t1类请求的响应性能有较大提高,而且t2类请求也能够获得一定的处理机会.

表2为其他类型请求负载一定的条件下,t1类请求流的数量对系统响应性能的影响.实验中,t0类请求流的数量为80,t2类请求流的数量为200,t3类请求流的数量为100.从表2中可以得出和表1基本相同的结论,采用FIFO调度策略时,所有类型请求的响应性能基本相同;采用优先级调度策略时,在带宽资源不够时会牺牲低优先级请求的响应性能;采用PPSA调度策略时,虽然在带宽资源不够时会牺牲一些低优先级请求的响应性能,但算法保证这种性能牺牲不会超过一定的限度.

表2　t1类请求流数目对系统响应性能的影响Tab.2Effect of the number of class t1 request flows on the system response performance

4　结束语

PPSA算法在兼顾公平调度和更短的响应时间上,取得了更好的效果.在云存储应用环境中,用户数据一般存储在DFS中.为了更好地响应不同种类的IO请求,在提高调度效率的同时兼顾不同类型请求调度的公平性,PPSA结合实际应用场景对I/O请求进行分类,并赋予不同的优先级;然后以经验值为周期,以分时间片的方式对不同优先级的请求进行周期性的调度.仿真实验结果显示,PPSA在兼顾公平性的前提下,还能有效降低实时请求的响应时间,可以为云存储用户提供更好的使用体验.