一种SSD存储系统中的先应式垃圾回收算法

doi:10.11959/j.issn.1000-0801.2019075

电信科学 ›› 2019, Vol. 35 ›› Issue (5): 86-96.doi: 10.11959/j.issn.1000-0801.2019075

一种SSD存储系统中的先应式垃圾回收算法

屠雪真¹,黄震江²,陈正光²

¹ 河南大学计算机与信息工程学院，河南开封 475001
² 中兴通讯股份有限公司，江苏南京 210012

修回日期:2019-04-12 出版日期:2019-05-20 发布日期:2019-05-21
作者简介:屠雪真（1998- ），女，河南大学在读，主要研究方向为云计算和大数据。|黄震江（1976- ），男，中兴通讯股份有限公司高级工程师，主要研究方向为云计算和大数据。|陈正光（1976- ），男，中兴通讯股份有限公司高级工程师，主要研究方向为数据库及存储。
基金资助:
科技部云计算和大数据重点专项基金资助项目(2018YFB1003300);深圳市科技计划项目(SF20170036)

Provident garbage collection algorithm for SSD storage system

Xuezhen TU¹,Zhenjiang Huang²,Zhengguang CHEN²

¹ School of Computer and Information Engineering,Henan University,Kaifeng 475001,China
² Zhongxing Telecommunication Equipment Corporation,Nanjing 210012,China

Revised:2019-04-12 Online:2019-05-20 Published:2019-05-21
Supported by:
Ministry of Science and Technology Cloud Computing and Big Data Key Project(2018YFB1003300);Shenzhen Science and Technology Plan Project(SF20170036)

摘要/Abstract

摘要：

提出了一种基于预测的先应式垃圾回收算法，首先根据不同的热度因子对数据进行读、写热度分离，然后对未来将达到的不同类型的页面分配请求（page allocation request，PAR）数量进行上位和下位预测，在满足页面分配请求PAR下位预测的同时，最大程度地满足PAR上位预测需求，优化了WA问题，减少了不必要的有效数据迁移，从而最大化垃圾回收效用。对此问题定义了数学模型，并给出了一种获取近似最优解的算法，对模型适用场景进行了分析。实践结果表明，本算法能够获取最大收益，提升SSD读写性能并降低成本。

关键词: SSD, 垃圾回收, 数据迁移, 写入放大, 碎片整理

Abstract:

A predictive based proactive garbage collection algorithm was proposed.Firstly,the data was separated according to different heat factors,then the upper and lower predictions were performed on the number of different types of page allocation requests (PAR) that would be reached in the future.While satisfying the page allocation request lower prediction,the PAR upper prediction requirement was maximally satisfied,the WA problem was optimized,and invalid effective data migration was reduced,thereby maximizing the garbage collection utility.A mathematical model was defined for this problem,and an algorithm for obtaining the approximate optimal solution was given.The applicable scenario of the model was analyzed.The practical results show that the algorithm can obtain the maximum benefit and can significantly improve the performance of SSD and reduce the cost.

Key words: solid state drive, garbage collection, data migration, write amplification, defragmentation

中图分类号:

TP333

屠雪真,黄震江,陈正光. 一种SSD存储系统中的先应式垃圾回收算法[J]. 电信科学, 2019, 35(5): 86-96.

Xuezhen TU,Zhenjiang Huang,Zhengguang CHEN. Provident garbage collection algorithm for SSD storage system[J]. Telecommunications Science, 2019, 35(5): 86-96.

图/表 6

图1

图2

图3

表1

图4

图5

参考文献 12

[1]	黄平 . 基于固态盘特征的存储优化研究[D]. 武汉:华中科技大学, 2013: 31-35.
	HUANG P . Research on storage optimization based on solid state disk characteristics[D]. Wuhan:Huazhong University of Science and Technology, 2013: 31-35.
[2]	WU S Z , CHEN X X , MAO B . GC-RAIS:garbage collection aware and redundant array of independent SSDs[J]. Journal of Computer Research and Development, 2013,50(1): 60-68.
[3]	MAD Z , FENG J H , LI G L . A survey of address translation technologies for flash memories[J]. ACM Computing Surveys, 2014,46(3): 238-276.
[4]	GUPTA A , KIM Y , URGONKAR B . DFTL:a flash translation layer employing demand-based selective caching of page-level address mapping[J]. ACM Sigarch Computer Architecture News, 2009,37(1): 229-240.
[5]	HU X Y , ELEFTHERIOUS E , HAAS R ,et al. Write amplification analysis in flash-based solid state drivers[C]// The 2nd Int Systems and Storage Conference,May 4-6,2009,Haifa,Israel. New York:ACM Press, 2009: 10-19.
[6]	姚英彪, 杜晨杰, 王发宽 . 一种基于分类策略的聚簇页级闪存转换层算法[J]. 计算机研究与发展, 2017,54(1): 142-153.
	YAO Y B , DU C J , WANG F K . A clustered lpage-level flash translation layer algorithm based on classification strategy[J]. Journal of Computer Research and Development, 2017,54(1): 142-153.
[7]	JIANG S , ZHANG L , YUAN X ,et al. S-FTL:an efficient address translation for flash memory by exploiting spatial locality[C]// Mass Storage Systems and Technologies,May 23-27,2011,CO,USA. New York:ACM Press, 2011: 1-12.
[8]	张琦, 王林章, 张天 ,等. 一种优化的闪存地址映射方法[J]. 软件学报, 2014,25(2): 314-325.
	ZHANG Q , WANG L Z , ZHANG T ,et al. Optimized address translation method for flash memory[J]. Journal of Software, 2014,25(2): 314-325.
[9]	LEE D , CHOI J , KIM J H ,et al. LRFU:a spectrum of policies that subsumes the least recently used and least frequently used policies[J]. IEEE Transactions on Computers, 2001,50(12): 1352-1361.
[10]	MEGIDDO N , MODHA D S . ARC:a self-tuning,low overhead replacement cache[C]// Usenix Conference on File and Storage Technologies,Mar 31-Apr 2,2003,San Francisco,CA,USA. New York:ACM Press, 2003: 115-130.
[11]	JIANG S , ZHANG X . LIRS:an efficient low inter-reference recency set replacement policy to improve buffer cache performance[J]. ACM Sigmetrics Performance Evaluation Review, 2002,30(1): 31-42.
[12]	周权彪, 张兴军, 董小社 ,等. 基于缓存映射项重用距离的闪存地址映射方法[J]. 计算机研究与发展, 2018,55(5): 1065-1077.
	ZHOU Q B , ZHANG X J , DONG X S ,et al. FTL address mapping method based on mapping entry inter-reference recency[J]. Journal of Computer Research and Development, 2018,55(5): 1065-1077.

应用	应用来源	访问特点	文件大小
场景1	机顶盒	顺序读	1～16 MB
场景2	彩铃库	读多写少	64～1 MB
场景3	邮箱	少数文件访问热度高	4～32 KB
场景4	移动终端地理位置采集	顺序写	4 KB
场景5	用户互联网行为分析	连续读，随机写	128 byte～4 KB
场景6	话单生成与计费	随机写，随机读	32 byte

一种SSD存储系统中的先应式垃圾回收算法

Provident garbage collection algorithm for SSD storage system

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 12

相关文章 6

Metrics

推荐阅读 0

[1]	肖洁,陈跃斌,陈楚天,郑婷,钱继武. 基于信任度的可变门限能量检测算法[J]. 电信科学, 2018, 34(8): 129-135.
[2]	王美璎,冯景瑜,卢光跃,韩定坤. 协作频谱感知中的动态信任评估机制[J]. 电信科学, 2016, 32(3): 60-67.
[3]	李玉峰,胡乃瑞,王宇鹏. 一种基于信誉度的航空无线电协作频谱感知方法[J]. 电信科学, 2015, 31(9): 118-123.
[4]	冯景瑜,李金龙,卢光跃. 协作频谱感知中抗SSDF攻击的认知用户不确定性行为评估[J]. 电信科学, 2015, 31(2): 97-102.
[5]	冯景瑜. 协作频谱感知中的SSDF攻击及其对策研究[J]. 电信科学, 2014, 30(1): 67-72.
[6]	常希娟,费洪晓. 基于USSD构建手机支付平台[J]. 电信科学, 2004, 20(8): 18-22.