罗保山，张鑫,，王 栩，谭支鹏

(1.武汉软件工程职业学院 计算机学院，湖北 武汉 430205；2.华中科技大学 计算机学院，湖北 武汉 430074)

混合存储数据迁移策略研究

罗保山1，张鑫1,2，王 栩2，谭支鹏2

(1.武汉软件工程职业学院 计算机学院，湖北 武汉 430205；2.华中科技大学 计算机学院，湖北 武汉 430074)

大数据环境下海量增长的数据对存储介质的实时响应和超高容量带来了极大的挑战。传统机械硬盘的性能瓶颈日益突出，以固态盘为代表的拥有高性能的新型存储器不断涌现，但其价格远高于机械硬盘。为了降低总体成本同时利用HDD的超大容量，又充分利用SSD的高速性能，以固态盘与机械硬盘构建的混合存储阵列成为一种不错的选择。文中设计实现了一种基于文件级数据迁移的混合存储方案。通过数据分析器统计每个文件的随机访问度和热度，并通过数学模型量化出文件价值来衡量文件的重要性，基于0/1背包模型提出了一种迁移算法，完成文件集合的迁入迁出并实现了对已迁移文件的访问重定向。测试表明，该方案较另外两种存储方案平均提升了10%左右，而且减少了对SSD的写操作，延长了SSD的使用寿命。

固态盘；混合存储；文件价值；数据迁移

1 概 述

大数据环境下数据呈海量爆炸式增长，快速增长的海量数据的产生、保存和访问对数据存储和管理提出了更高的要求，它既希望对数据的处理能得到快速响应，又希望存储系统有足够多的容量来存储海量数据。以闪存为代表的新型存储器使用较少的容量和物理空间却拥有高速的性能，但其价格昂贵，只适用于高性能应用，价格低廉、容量巨大的传统机械硬盘仍是很多企业作为存储数据的首选。为了满足海量数据的实时响应和超高容量的需求，同时又节约成本，混合存储系统成为一种折中的选择。

硬盘驱动器是如今主要的电脑存储媒介，它对性能密集型的在线应用程序有着很好的支撑。借助垂直磁记录技术，磁盘的单盘容量已经发展到现在的1.5 T，多个磁盘阵列能提供更大的容量和更高的性能。但是磁盘的数据存取速度、寻道时间和定位时间越发成为瓶颈。虽然通过SATA、光纤磁盘等新技术可以缓解这一矛盾，但其本身的机械结构却使这些高速外部接口并不能充分发挥它们的速度优势。使用NAND Flash芯片作存储介质的固态盘(Solid State Drive)[1]提供了高读写速度和可靠性，它不存在寻道时间，读写延迟比机械硬盘小，很好地支持了数据的随机访问，但其经济成本相对较高且容量有限，并因NAND有限的擦写次数降低了固态盘的使用寿命。

用户对存储器的选择有三个主要指标[2]：容量、速度和价格。如今，CPU、内存等设备大致根据摩尔定律[3]在性能和集成速度上有很大提高，处理器和内存容量都得到了飞速提升，但海量数据的爆炸式增长对存储器速度的要求也不断提高。存储介质的选择一般从价格和性能两方面考虑。侧重价格的应选择拥有足够容量且价格低廉的存储介质；侧重性能的应选择价格昂贵但性能优越的快速存储器。但人们往往希望以较低的价格得到性能不错的存储器，混合存储系统(Hybrid Storage System)较好地解决了这一困境，实现了闪存的高性能同时兼具磁盘的低成本优势，从而优化了存储系统的整体性能。国内外学术界和企业界对混合存储系统[4]已进行了很多深入的研究，也有很多成熟的混合存储产品问世，如早期的Hybrid Storage Alliance (HSA)、希捷Momentus XT系列固态混合硬盘及Facebook的Flashcache等。

在混合存储方案的设计中应从以下三方面考虑：

(1)迁移算法的选择[5]，即确定一个最优的待迁移集合，使得该迁移操作能最大程度地提升整个存储系统的性能；

(2)存储设备的选择比例[6-8]，即如何根据不同负载调整各种存储设备的比例，从而将混合存储系统的开销降到最低;

(3)延长存储器寿命，即如何延长磁盘的寿命又保证混合存储系统的性能[9-10]。

2 系统设计与实现

图1中的原始磁盘布局模式[11-12]阐述了本节讨论的问题，三个热点文件File1，File2，File3被访问的顺序如图1(a)所示，File1和File2为顺序访问，File3为随机访问。图中的黑点代表一次IO，三个文件以随机方式存储在磁盘上。磁盘性能在File2被访问的这段是比较好的，但整个过程并不好，原因是：

(1)存储位置的不连续性造成对File1和File3访问的寻道时间较长；

(2)由于对File1的访问会被对File3的访问所打断，因此对File1的访问是伪顺序的；

(3)由于File3是被随机访问的，所以当访问File3时需要频繁地移动磁头。

混合磁盘的布局模式如图1(b)所示。将File1和File3存储到SSD上大大提升了磁盘访问的顺序性。虽然实际存储系统中对磁盘的访问模式比这复杂很多，但将随机访问的文件和热点文件迁移到固态盘上能够大大降低对整个磁盘的访问延迟。

评析 试题源于成书1247年南宋时期秦九韶所著的《数书九章》，是对《九章算术》的继承和发展，概括了宋元时期中国传统数学的主要成就，标志着中国古代数学的高峰.例4考查的是几何形体圆台的体积计算，与例1、例2和例3一样，都是以典籍史料中的问题为背景，通过数形结合、化归与转化等数学思想方法的运用求得答案为3寸.例5不同于例1-4题，仅局限于把《数书九章》中的“多项式值的算法”作为一个材料背景，而是把其中的秦九韶思想与算法的程序框图结合起来进行再创造，让考生运用所学的基本知识和技能解决问题，正是这道题的创新点，值得推广.

图1 原始磁盘和混合磁盘布局模式

基于此,文中设计了一种基于文件级数据迁移的混合存储方案。

(1)利用SSD读写速度较快的特点，将热点数据放置到SSD上，使之成为磁盘的缓存；

(2)利用固态盘和磁盘在不同访问模式下的速度差异，让固态盘服务绝大多数的随机I/O访问，磁盘服务剩余的I/O访问；

(3)根据文件的随机度和热度估算出它的价值，衡量将该文件迁移到SSD上给系统带来的性能提升，并根据文件价值确定迁移集合[13]并进行数据迁移，同时利用FUSE[14]实现访问重定向。

图2是系统的基本架构图，图中右侧虚线框中包括五个功能模块。

数据收集器工作在FUSE的内核态，主要负责抓取文件访问的历史信息(被访问文件的路径、类型、扇区号、长度以及时间)。数据分析器为FUSE的用户态程序，它统计分析历史访问信息并通过随机度计算算法得出每个文件的随机度和热度，通过对SSD总访问量的读写比例及文件大小得出每个文件的价值。迁移算法基于0/1背包模型确定文件的存放位置，从而最大化混合存储系统中SSD的利用率。迁移管理器基于迁移算法完成SSD和HDD之间的数据迁移。数据库主要用于存储数据并协同其他模块完成数据库操作，使用FUSE的用户态程序实现访问的重定向。

图2 系统架构图

本节主要介绍随机度和热度的计算算法和文件在SSD和HDD之间的迁移算法。

随机度和热度的计算主要在数据分析器上完成，前者衡量对某一文件的连续前后请求在磁盘块上的距离，后者计算特定时间段内对某一文件的访问次数。举例说明如下，数据分析器分析某段时间内对File1访问的历史信息时，当发现对File1有一次访问，则将File1的热度值加1(hotness+1)，同时判断该访问的起始位置是否为对File1上次访问的结束位置，如果相同(顺序访问)且与上次访问类型相同，前后的时间间隔也在给定的阈值内，则随机度不变，否则随机度加1(randomness+1)，并更新File1的随机度与热度。分析结束后统计每个文件的随机度和热度值。如果File1在△t时间内有n次访问，则File1的热度为n。通过上述随机度计算算法，得出随机度为m，特殊情况下，m=n表示对File1的访问都是随机的，m=1表示对File1的访问都是顺序访问的。

其中：fi为文件i的热度；ri为文件i的随机度；si为文件i的大小。

虽然小文件对固态盘更有优势，但固态盘存在写性能下降的问题，且擦写次数有限的NAND芯片降低了使用寿命，因此区分SSD的读写操作且适当减少对SSD的写操作是很有必要的。假设在某段时间内对File1的总访问长度为T，读操作长度为R，对于两个根据上述数学模型设计计算出的具有相同V值的文件而言，如果两者总的访问量T相同，那么拥有更多读访问R的文件对SSD更有利。如果R相同，总访问量S小的文件对SSD更有利。由此得出计算value值的数学模型的改进版：

其中，Ri为对文件i读操作的数据量；Ti为对文件i访问的总数据量。

通过功能模块数据分析器分析得到每个文件在某时间段内的访问随机度、访问热度、访问总数据量和读操作数据量，再根据上述计算模型计算出各自的Value值。

需要根据持续变化的系统IO动态地在SSD和HDD之间进行数据迁移，将更多对SSD更有利的数据迁移到SSD上，将不利于SSD的数据迁移到HDD上。使用0/1背包模型分析SSD和HDD之间文件的数据迁移问题。

假设整个混合存储系统中有n个不同的文件，每个文件的大小为si，文件价值为Vi，变量xi为该文件的存储位置，1为存储到SSD，0为存储到HDD。该迁移算法的目的在于选取一个更利于存储到SSD上的文件集合，集合中所有文件大小之和应尽可能等同于SSD的容量，且它们的Value值之和也应尽可能得大。由此得出计算模型：

其中，CAPACITYSSD为SSD的总容量(实际情况中因SSD上有写操作，CAPACITYSSD要小于SSD的总容量)。

上述模型得到的文件集合是整个存储系统中最利于SSD的文件集合，但在得出该集合之前可能该文件集合中的部分文件已经迁移到SSD了，造成该集合的不准确性。真实地迁入和迁出的文件集合见图3。

图中，MoveSet为整个系统中最利于SSD的文件集合，FileSetSSD为该时刻下SSD上已存在的文件集合，二者的交集为利于SSD的文件集合中已迁入SSD上的文件子集，SETHDD为SSD上已存在的文件集合中不利于SSD的文件子集，SETSSD为HDD上更利于SSD的文件子集。

图3 迁入集合和迁出集合

根据该算法，交集不需要迁入迁出即保持不变即可，将SSD上不利于SSD的文件子集SETHDD迁移至HDD上，将HDD上利于SSD的文件子集SETSSD迁移至SDD上。

数据迁移工作在同一主机内部SSD和HDD之间进行，无需考虑网络带宽、安全性等的影响，但需保证对用户的透明性且不影响用户对数据的访问功能，尽可能降低迁移所带来的IO负载。因此适当的迁移时间，即系统空闲时间，能基本满足这一要求。

当数据迁移工作完成后，部分文件在磁盘上的位置已经发生变化，需要考虑重定向的功能实现。使用FUSE(FilesysteminUSErspace)工具实现了一个用户态文件系统hybridfs完成访问重定向功能。举例说明其具体实现过程，现需要对文件/home/file1进行对操作，FUSE的内核态程序将自动截获来自内核软件层(VFS)的访问请求，主要获得访问的文件路径名(file_name)、访问偏移量(offset)、访问长度(length)、访问类型(R/W)等信息，并将其传递给用户态程序。用户态程序首先查询/home/file1在数据库中的记录位置，若返回空或为“H”，表示该文件存储位置为HDD，直接对该文件进行操作即可；若返回为“S”，表示该文件迁移至SSD，位置为/mnt/ssd/home/file1，用户态程序将访问路径/home/file1更改为/mnt/ssd/home/file1。然后对该路径进行open操作并返回对应的fd，再对该fd进行相应的读写操作。操作完成后查询数据库中/home/file1的need_fsync位，若返回“Y”，表示该文件在之前已经被修改，若返回“N”，则更改为“Y”，表明该文件已迁移至SSD。至此完成了对已迁移文件的访问重定向功能。

3 系统测试与分析

系统是在局域网内的两台机器上进行测试，其中一台为具备系统所需的全部功能的混合存储系统的客户端，另一台为协助完成系统性能测试的服务器端。主机操作系统采用RedHatEnterpriseLinuxServerrelease6.0 (Santiago)，CPU为Intel(R)Xeon(R)CPUE5620 2.40GHz，8GB内存，机械硬盘为Seagate1TB7200RPM，固态盘为OCZ-DriveR4PCI-EXPRESSSolidStateDrive300GB。

使用debench[16]作为测试工具，测试trace[17]为三个IO密集型的服务器trace：邮件服务器工作负载(MailServer)、研究中心工作负载(Research)和桌面环境工作负载(Office)。这三个trace的分析数据如表1所示。

表1 三种trace的分析数据

将文中提出的综合考虑访问随机度与热度的混合存储系统(RHS)，与只考虑热点访问数据的混合存储系统(HOT)，以及只有一块硬盘的存储系统(HDD)，分别在上述trace上进行测试。

第一项指标为平均访问延迟测试，测试结果如图4所示。

图4 三种trace工作负载对比

对于MailServer而言，RHS相对于HDD和HOT提升了10%和8%，读为20%和10%，写为12%和10%；在Office的Workload上提升了20%和15%，读为22%和16%，写为28%和13%；在Research的Workload上提升了15%和8%，读为20%和13%，写为25%和12%。通过读写性能的对比分析说明了将随机访问和热点访问的文件迁移到固态盘上能有效减少整个系统的访问延迟。

第二项指标为系统平均带宽测试，测试结果如图5所示。

图5 三种trace平均带宽对比

在MailServer上，RHS相对于HDD和HOT提升了大约15%和6%；OfficeWorkload上的带宽提升了38%和20%；ResearchWorkload因读写比例为0.5从而使提升小一些。因此将文件价值高的文件迁移到SSD上便于对已迁移至SSD上的文件的下次访问改为访问SSD而非HDD，这对系统性能的提升有显著的作用。

4 结束语

文中提出了一种有效的将文件价值高的文件迁移到SSD上的混合存储方案。通过统计分析每个文件的历史访问信息得到它们的随机度和热度，并通过数学模型将随机度和热度抽象量化为文件价值，用以衡量迁移该文件对整个系统带来的性能提升。系统借鉴0/1背包模型，设计出了文件迁移算法并对计算出的迁移集合进行数据迁移，同时在迁移工作完成后实现了对已迁移文件的访问重定向。通过在不同的服务器trace上的测试对比，结果表明该系统在平均访问延迟与系统带宽这两项指标上都有一定的性能优势。

[1]NarayananD,ThereskaE,DonnellyA,etal.MigratingserverstoragetoSSDs:analysisoftradeoffs[C]//Proceedingsofthe4thACMEuropeanconferenceoncomputersystems.NewYork:ACM,2009:145-158.

[2] 王志英,张春元,戴 葵,等.计算机体系结构[M].北京:高等教育出版社,2000:173-174.

[3]MooreGE.Crammingmorecomponentsontointegratedcircuits[J].Electronics,1965,38(8):114-117.

[4]ChangLP.Hybridsolid-statedisks:combiningheterogeneousNANDflashinlargeSSDs[C]//ProcofAsiaandSouthPacificdesignautomationconference.Seoul:IEEE,2008:428-433.

[5]KoltsidasI,ViglasSD.Flashingupthestoragelayer[J].ProceedingsoftheVLDBEndowment,2008,1(1):514-525.

[6]GuerraJ,PuchaH,GliderJS,etal.Costeffectivestorageusingextentbaseddynamictiering[C]//Proceedingsofthe9thUSENIXconferenceonfileandstoragetechnologies.[s.l.]:USENIX,2011.

[7]GarrisonJA,ReddyAL.Umbrellafilesystem:storagemanagementacrossheterogeneousdevices[J].ACMTransactionsonStorage,2009,5(1):1-24.

[8]HuY,YangQ.DCD-diskcachingdisk:anewapproachforboostingI/Operformance[C]//ProceedingsofACMSIGARCHcomputerarchitecturenews.[s.l.]:ACM,1996:169-178.

[9]SoundararajanG,PrabhakaranV,BalakrishnanM,etal.ExtendingSSDlifetimeswithdisk-basedwritecaches[C]//Proceedingsofthe9thUSENIXconferenceonfileandstoragetechnologies.[s.l.]:USENIX,2010:101-114.

[10]AguileraMK,KeetonK,MerchantA,etal.Improvingrecoverabilityinmulti-tierstoragesystems[C]//Proceedingsofthe37thannualIEEE/IFIPinternationalconferenceondependablesystemsandnetworks.[s.l.]:IEEE,2007:677-686.

[11]LinL,ZhuY,YueJ,etal.Hotrandomoff-loading:ahybridstoragesystemwithdynamicdatamigration[C]//ProceedingsofIEEE19thinternationalsymposiumonmodeling,analysis&simulationofcomputerandtelecommunicationsystems.[s.l.]:IEEE,2011:318-325.

[12]SomasundaramG,ShrivastavaA.信息存储与管理—数字信息的存储、管理和保护[M].罗英伟，汪小林，尹冬生,等,译.北京：人民邮电出版社，2010:36-37.

[13] 余祥宣，崔国华，邹海明.计算机算法基础[M].第3版.武汉：华中科技大学出版社，2006:101-118.

[14]HenkC,SzerediM.FUSE:filesysteminuserspace[EB/OL].2012.http://sourceforge.net/projects/fuse.

[15] 刘次华，万建平.概率论与数理统计[M].第3版.北京：高等教育出版社，2008:98-101.

[16]KanounK,ArlatJ,CostaD,etal.DBench:dependabilitybenchmarking[C]//Procof2001internationalconferenceondependablesystemsandnetworks.[s.l.]:[s.n.],2001:12-15.

[17]EllardD,LedlieJ,MalkaniP,etal.PassiveNFStracingofemailandresearchworkloads[C]//ProceedingsofthesecondannualUSENIXfileandstoragetechnologiesconference.SanFrancisco,California:USENIX,2003:203-216.

Research on Hybrid Storage Data Migration Strategy

LUO Bao-shan1,ZHANG Xin-yan1,2,WANG Xu2,TAN Zhi-peng2

(1.School of Computer Science,Wuhan Vocational College of Software and Engineering,Wuhan 430205,China;2.School of Computer Science,Huazhong University of Science and Technology,Wuhan 430074,China)

The explosion of data in the big data environment brings great challenges to the real-time response and high capacity of storage medium.The performance bottleneck of traditional hard disk is becoming increasingly prominent.New type of memory with the high performance represented by the solid state disk is emerging constantly,but its price-performance ratio is not better than that of the hard disk drive.The hybrid storage system that combines HDD with SSD becomes inevitable for reducing the overall costs while leveraging the large capacity of HDD and making full use of high-speed performance of SSD.It analyzes and designs a file-level hybrid storage system in this paper,which uses the data analyzer to count the degree of random access and hotspot for each file.Through establishing the mathematical model,it quantifies file value to measure the importance of files,and it uses the 0/1 knapsack problem model to design a migration algorithm that helps determine the migration set and realizes the redirection for access of each file.Through test,it improves 10% on average compared with the other two storage schemes,reduces the write operations to SSD and prolongs the service life of SSD.

SSD;hybrid storage;file value;data migration

2015-08-25

2015-11-27

时间：2016-05-05

中央高校财政专项基金(2015XJGH010)

罗保山(1973-)，男，副教授，研究方向为计算机体系结构、网络存储;张鑫(1988-)，男，硕士，研究方向为存储安全与高可用技术、存储服务与应用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0829.098.html

TP301

A

1673-629X(2016)06-0082-05

10.3969/j.issn.1673-629X.2016.06.018