视频访问负载的分级存储及迁移算法研究

蒋平川，冯圣中

（1.中国科学院 深圳先进技术研究院，广东 深圳518055；2.中国科学院 研究生院，北京100049）

0 引 言

信息化的发展，特别是云计算技术［1］的发展，带来了巨大的机遇和挑战。数据中心大规模的数据需要分布式存储这些数据，同时利用不同速度的访问设备来提高访问速度，提高数据的并发性。还可以通过优化数据迁移规则，加速重要数据和常用数据的访问，减少带宽消耗。在大规模数据中心存储中，分级存储是根据数据的重要性、访问频率、保留时间、容量、性能等指标，将数据采取不同的存储方式分别存储在不同性能的存储设备上。数据分级存储的工作原理是基于数据访问的局部性。通过将不经常访问的数据自动移到存储层次中较低的层次，释放出较高成本的存储空间给更频繁访问的数据，可以获得更好的性价比。在分级存储设备上，主要是利用不同的访问速度存储设备 （如SATA，SAS，SSD）的差异组成一个相互协作的系统 （如图1所示）。数据迁移主要是通过数据的访问性质，以少量系统内部带宽消耗，调整系统中数据的分布，到达优化系统性能目标。通过数据迁移算法，完成数据在不同的访问周期的数据重新分布。分级存储数据迁移算法设计主要来自于传统的cache－like算法，包括LRU、LFU、LFRU、LRFU、PLFRU、RBC等。另一方面是对一些传统算法的改进，包括一些资源消耗策略［2］，带有权重的分析策略［3－4］和高效、公平性考虑，以及针对具有历史访问时间统计分析的Cache［5］。同时Cache策略会带来的对访问响应时间的影响［6］。还有一些文章是对于传统的 Memory Cache作分析和改进［7－8］，包括在异质的移动存储系统上的利用［9］，或者对存储硬件设备上的Cache进行改进设计［10－12］。基于最近的绿色计算，出现了考虑如何设计有能耗意识的Cache策略［13－14］。本文主要从基于 web－intensive视频访问特性出发，提出了针对性的数据迁移算法，同时考虑了资源消耗，提出了以带宽节省率／命中率的为目标的应用评价。在Disk Cache策略上，进一步考虑并发问题，找到了带宽节省率／命中率的影响，从而实现Cache策略的优化。

图1 分级混合存储结构

1 视频负载模式和数据迁移模型

1.1 视频负载模式

Internet的发展，使得视频访问网站 （如youtube，youku）的发展迅速，而且人们生活的日常生活娱乐需求，使得能够上传、浏览视频变得越来越频繁。这种视频访问具有一定的模式，其主要特点是：

（1）Read－only after write once，由于这种访问特性，对文件的更改是十分不常见的，所以再设计存储加速时，不需要考虑一致性问题。

（2）File－level的 访问分级存储加速 （非 Block－level），较快速的访问设备相当于访问数据的一层 “Cache”。但是与传统 Memory－cache的替换算法或其改进算法的区别在于，不是对于每次的cache访问非命中都立即采取cache策略，而是周期性数据迁移和应急数据迁移相结合。

（3）在时序的访问特性上，有两种不同的特征。一种是长期流行的视频文件，具有比较稳定的访问频率，称为频率型访问；一种是就流行度来讲，具有很短时间急剧变化的访问频率，称为冲击型访问［15］。

1.2 数据迁移模型

1.2.1 Disk Cache模型

数据迁移的分级存储在一定程度上是一种缓存模型，即所谓的磁盘缓存，但是与传统的内存缓存存在一定的区别。内存缓存的工作原理是基于程序访问的局部性。分级存储中数据迁移主要是数据访问的局部性。这种利用数据访问的局部性，主要是频率分布局部性，采用高速访问存储设备作为 “cache”的工作原理，称为Disk Cache模型。由于在文件传输过程中，也存在资源消耗，而且随着文件大小，资源消耗周期性迁移量变化而变化。所以，我们可以对disk cache模型进行分析。地数据对象参数列表：

Tci：Disk cache访问时间 （快速设备）

Tdi：Disk访问时间 （慢速设备）

Tcpi：Server节点Disk到Disk cache的文件拷贝时（若考虑删除原节点文件，则

Hi：全局命中率

Si：文件大小

Ni：文件访问频次

Ri：文件替换频次

SC：Disk cache大小

采用Disk Cache策略，则

不使用Disk Cache策略，则

Cache效益S为

假设

1.2.2 并发模型和Disk Cache策略

在考虑一个分级存储系统的数据热点存储问题的同时，我们还应该考虑并发问题。对于一个服务器节点，其I／O性能，除了传输率外，还需要考虑其并发问题。服务器节点能支持的并发数为Np，若请求数超过Np。频繁的访问请求会带来额外的巨大开销，从而降低系统的反应速度，由此会抵消Disk Cache带来的好处。

Tni：响应时间，请求数NQ＜Np

Tui：响应时间，请求数NQ＞Np

以系统的整体带宽消耗节约率作为目标函数，那么我们可以得出模型：满足同时要求

这种模型下，即考虑单位命中率的带宽消耗。这是说通过Disk Cache达到同样的带宽优势，只需要使用较低的命中率即可减少对作为Cache的高速设备并发访问。

2 分级存储迁移算法

在分级存储的模型中，核心的是两个方面，一是如何区分数据的级别 （File－level文件的级别），另一个方面是在从数据迁移过程中从Cache（快速设备）如何替换出数据级别较低的数据。针对视频访问的数据访问模式，需要区分两种类别，进行不同的处理。我们需要识别出短时冲击型访问。

因此，其核心算法是，利用在系统运行的过程中，记录过去K周期的历史访问频率数据D （d0，d1，…，dk）。数据周期访问如图2所示。

图2 数据周期访问

利用D，计算出第K＋1个周期的预测值，V＝F（D），然后利用V的排序，进行Disk Cache的替换策略，完成数据迁移。

2.1 数据对象类别识别

由于我们只能获取历史数据，而没有取得所有数据然后进行识别，所以不能采用频率变换和小波分析等方法我们采用最基本的历史数据平均和方差波动方法。

该方法主要是实现简单，而且能够很好的监测到临时访问变化的初期和末期。

步骤如下：

（1）使用滑动窗口 （如窗口大小为N），共获取对象的历史访问数据向量D （d0，d1，d2，…，dn－1）。

（2）计算子向量D1 （d0，d1，…dn－2）的均值A1和方差V1，子向量D2（d1，d2，…dn－1）的均值A2和方差V2。

（3）计算A＝A2－A1，V＝V2／V1。

（4）对于V大于阈值δ的对象设定为冲击型C1类别访问，若A＞0，归结为冲击型访问前端C1－P；A＜0归结为冲击访问型后端C1－B。

（5）对于V小于阈值δ的对象设定为频率型C2类别访问，调用其他处理算法进行对象级别排序。

2.2 数据对象排序

对于冲击型访问C1类型，是我们必须处理的，根据数据是C1－P还是C1－B类型，决定数据对象在分级存储中的 “上浮”和 “下沉”操作。而对于C2类型访问，就复杂一些。主要的想法有两种思路，由于C2类型的访问具有 “比较”平稳的访问，所以可以从周期性的历史访问频率进行处理。但是若采取类LFU的方法，对于平稳访问中的周期性波动问题 （如LFU－1，对于一个周期单位的前后波动就失去很好的命中效果）。所以我们采用一种滑动窗口移动平均的方法处理，通过历史数据，计算下一周期的访问预测值，然后考虑不同的参数，进行不同的参数算法排序，我们通过比较可以得出较为更优处理。移动平均法能有效地消除预测中的随机波动，这是非常有用的。步骤如下：

（1）使用滑动窗口 （如窗口大小为N），由历史访问数据向量D （d0，d1，d2，…，dn－1），通过移动平均计算数据对象的下一个周期访问预测值dn。

（2）考虑数据对象的参数 （大小、带宽消耗），通过预测值dn计算出移动带宽消耗B＝sizeofObject×dn；

bandwidth strategy与frequency strategy分别在实施动态数据迁移策略中根据实际的反馈效果进行选择。在周期性数据迁移策略中，直接采取其中一种，不进行动态变化。

2.3 数据对象迁移

进行数据迁移之前根据数据对象类型和数据对象rank值确定待迁移的 “Cache”数据集，然后实施 “Cache Replacement”。步骤如下：

（1）获取数据对象的类型及rank值，降序排列数据对象。C1－P类型数据对象并入待迁移集合T。C2类型数据对象依次选择rank＞阈值θ的数据对象，并入待迁移集合T。

（2）对于每一个在集合T中数据对象，如果在Cache中，则不对该对象进行再次迁移。如果不在Cache中，则放入Cache。（存在Cache容量满时，则从Cache中选择出不在T中的数据对象进行替换。）

3 算法模拟和结果

3.1 算法参数设置

我们采用模拟实验，利用程序生成了不同数量级别的文件，文件具有不同大小及其均匀、非均匀分布的特性，同时模拟视频访问频率的分布。然后通过周期性的数据迁移进行Cache模拟。模拟中采用视频访问的一年访问历史记录，分别对参数列表的不同值进行排列对比实验。由此，我们得出了较好的实验结果数据。

表1 模拟实验参数

图3 文件大小的非均匀分布

3.2 算法结果

根据我们的实验，我们得出了以下的实验结论：

（1）随着C1类型比例上升，命中率和带宽节省率 （带宽节省率＝1－具有disk cache的带宽消耗／原始带宽消耗）都会下降。但是bandwidth strategy策略使得带宽节省率／命中率有所上升，而frequency strategy策略基本保持不变的带宽节省率／命中率，如图4所示。

（2）Cache大小比率上升，对于不同策略均可以提高命中率和带宽节省率，但降低了带宽节省率／命中率。

（3）Bandwidth strategy对于文件的大小分布敏感，不同的文件分布带来带宽节省率／命中率的很大不同。Frequency strategy对于文件大小分布不太敏感，呈现比较均衡的带宽节省率／命中率，如图5、图6所示。

（4）使用Bandwidth strategy带来的带宽节省率／命中率的提高，可以在使用并发控制、请求负载平衡上起到很好的效果。（H：hit rate；BSR：bandwidth saving rate）

4 结束语

在分级存储及数据迁移技术中，通过Disk Cache的策略，可以带来明显的系统性能优化 （总体带宽节省，访问请求加速等）。同时对于新提出的带宽策略，这可以明显的带来带宽节省率／命中率的提高。特别是针对具有特性差异分布的数据对象大小，在利用这种新手段来平衡节点间的并发是一个十分有价值的创新点。对于几乎一致的带宽资源消耗，不同的Cache策略的命中率区分，使得我们能够在系统并发处理、访问频率均衡、系统总体响应时间上进行优化。

［1］Jayant Baliga，Robert W A Ayre，Kerry Hinton.Tucker green cloud computing：Balancing energy in processing storage and transport［J］.Business，2010，99 （1）：149－167

［2］Ekow Otoo，Frank Olken，Arie Shoshani.Disk cache replacement algorithm for storage resource manager in data grids ［C］.SuperComputing， ACM／IEEE Conference， Los Alamitos，USA，2002.

［3］LUO Yihui，XIE Changsheng，ZHANG Chengfeng.Weighting cache replace algorithm for storage system ［C］.International Conference on Intelligent Systems and Knowledge Engineering，2007.

［4］Samiee K，Rad G A R.WRP：Weighting replacement policy to improve cahce performance ［C］.Computer Science and Application.Hobart，Australia，2008：38－41.

［5］YIN Yang，ZHU Xudong，XU Lu.A media sensitive cache replacement algorithm ［J］.IEIT Journal of Adaptive＆ Dynamic Computing，2011，1 （1）：9－14.

［6］Ekow Otoo，Doron Rotem，Arie Shoshani.Impact of admission and cache replacement policies on response times of jobs on data grids ［J］.Cluster Computing，2005，8 （4）：293－303.

［7］Kaveh Samiee.A replacement algorithm based on weighting and ranking cache objects ［J］.International Journal of Hybrid Information Technology，2009，2 （2）：93－104.

［8］SONG Jiang，ZHANG Xiaodong.ULC：A file block placement and replacement protocol to effectively exploit hierarchical locality in multi－level buffer caches ［C］.Proceedings of the 24th International Conference on Distributed Computing Systems.Tokyo，Japan，2004.

［9］Young Jin Kim，Jihong Kim.Device－aware cache replacement algorithm for heterogeneous mobile storage devices ［C］.Proceedings of the 3rd international conference on Embedded Software and Systems.Berlin，Heidelberg，2007：13－24.

［10］Seongcheol Hong，Dongkun Shin.NAND flash－based disk cache using SLC／MLC combined flash memory ［C］.Proceedings of the International Workshop on Storage Network Architecture and Parallel I／Os.Incline Village，USA，2010：21－30.

［11］CHEN Feng，David Koufaty，ZHANG Xiaodong.Hystor：Making the best use of solid state drives in high performance storage systems ［C］.Proceedings of the international conference on Supercomputing.Tucson，AZ，USA，2011：22－32.

［12］HUANG Miaoqing，Olivier Serres，Vikram K Narayana.Efficient cache design for solid－state drives ［C］.Proceedings of the 7th ACM international conference on Computing frontiers.New York，USA，ACM，2010：41－50.

［13］ZHU Qingbo，ZHOU Yuanyuan.Power aware storage cache management ［J］.IEEE Transaction on Computers，2005，54：587－602.

［14］TAO Xie.SEA：A striping－based energy－aware strategy for data placement in RAID－Structured storage system ［J］.IEEE Trans，2008，57 （6）：748－761.

［15］Gonca Gursun，Mark Crovella，Ibrahim Matta.Describing and forecasting video access pattern ［C］.Proceedings of the 21st International Workshop on Network and Operating Systems Support for Digital Audio and Video，2011：16－20.