基于纠删码的细粒度云存储调度方案

doi:10.11772/j.issn.1001-9081.2017.03.613

计算机应用 ›› 2017, Vol. 37 ›› Issue (3): 613-619.DOI: 10.11772/j.issn.1001-9081.2017.03.613

• 第四届大数据学术会议(CCF BIGDATA2016) • 下一篇

基于纠删码的细粒度云存储调度方案

廖辉, 薛广涛, 钱诗友, 李明禄

上海交通大学计算机科学与工程系, 上海 200240

收稿日期:2016-09-21 修回日期:2016-10-18 出版日期:2017-03-10 发布日期:2017-03-22
通讯作者: 薛广涛
作者简介:廖辉(1991-),男,江西南丰人,硕士研究生,主要研究方向:云计算、大数据;薛广涛(1976-),男,山东济南人,教授,博士,CCF会员,主要研究方向:移动和无线计算、社交网络、分布式计算、无线传感网、云计算、大数据;钱诗友(1977-),男,江苏连云港人,助理研究员,博士,主要研究方向:云计算、大数据;李明禄(1965-),男,重庆人,教授,博士,CCF会员,主要研究方向:车辆自组网、无线传感器网络、云计算、大数据分析。
基金资助:
国家863计划项目（2015AA01A2020）。

Fine-grained scheduling policy based on erasure code

LIAO Hui, XUE Guangtao, QIAN Shiyou, LI Minglu

Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Received:2016-09-21 Revised:2016-10-18 Online:2017-03-10 Published:2017-03-22
Supported by:
This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2015AA01A202).

摘要/Abstract

摘要： 针对云存储系统中数据获取时延长以及数据下载不稳定的问题，提出了一种基于存储节点负载信息和纠删码技术的调度方案。首先，利用纠删码对文件进行编码存储以降低每份数据拷贝的大小，同时利用多个线程并发下载以提高数据获取的速度；其次，通过分析大量存储节点的负载信息确定影响时延的性能指标并对现有的云存储系统架构进行优化，设计了一种基于负载信息的云存储调度算法LOAD-ALGORITHM；最后，利用开源项目OpenStack搭建了一个云计算平台，根据真实的用户请求数据在云平台上进行部署和测试。实验结果表明，相比于现有的工作，调度算法在数据获取时延方面最高能减少15%的平均时延，在数据下载稳定性方面最高能降低40%的时延波动。该调度方案在真实的云平台环境下能有效地提高数据获取速度和稳定性，降低数据获取时延，达到更好的用户体验。

关键词: 云存储系统, 纠删码, 调度算法, 平均时延, 稳定性

Abstract: Aiming at the problems of long data acquisition delay and unstable data download in cloud storage system, a scheduling scheme based on storage node load information and erasure code technique was proposed. Firstly, erasure code was utilized to improve the delay performance of data retrieving in cloud storage, and parallel threads were used to download multiple data copies simultaneously. Secondly, a lot of load information about storage nodes was analyzed to figure out which performance indicators would affect delay performance, and a new scheduling algorithm was proposed based on load information. Finally, the open-source project OpenStack was used to build a real cloud computing platform to test algorithm performance based on real user request tracing and erasure coding. A large number of experiments show that the proposed scheme not only can achieve 15% lower average delay but also reduce 40% volatility of delay compared with other scheduling policies. It proves that the scheduling policy can effectively improve delay performance and stability of data retrieving in real cloud computing platform, achieving a better user experience.

Key words: cloud storage system, erasure code, scheduling algorithm, average delay, stability

中图分类号:

TP391.9

廖辉, 薛广涛, 钱诗友, 李明禄. 基于纠删码的细粒度云存储调度方案[J]. 计算机应用, 2017, 37(3): 613-619.

LIAO Hui, XUE Guangtao, QIAN Shiyou, LI Minglu. Fine-grained scheduling policy based on erasure code[J]. Journal of Computer Applications, 2017, 37(3): 613-619.

参考文献

[1] Wikipedia. Cloud storage[EB/OL].[2016-06-10]. https://en.wikipedia.org/wiki/Cloudstorage.
[2] 华为.大数据和云计算[EB/OL].[2016-07-19]. http://e.huawei.com/zh/publications/cn/ict_insights/hw_366755/horizons/HW_366714. (Huawei. Big data and cloud computing[EB/OL].[2016-07-19]. http://e.huawei.com/zh/publications/cn/ict_insights/hw_366755/horizons/HW_366714.)
[3] GHEMAWAT S, GOBIOFF H, LEUNG S T. The google file system[C]//Proceedings of the 19th ACM Symposium on Operating Systems Principles. New York:ACM, 2003:29-43.
[4] SHVACHKO K, KUANG H, RADIA S, et al. The Hadoop distributed file system[C]//Proceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies. Washington, DC:IEEE Computer Society, 2010:1-10.
[5] HUANG L, PAWAR S, ZHANG H, et al. Codes can reduce queueing delay in data centers[C]//Proceedings of the 2012 IEEE International Symposium on Information Theory. Piscataway, NJ:IEEE, 2012:2766-2770.
[6] LIANG G, KOZAT U C. Fast cloud:pushing the envelope on delay performance of cloud storage with coding[J]. IEEE/ACM Transactions on Networking, 2014, 22(6):2012-2025.
[7] SHAH N B, LEE K, RAMCHANDRAN K. The MDS queue:analysing latency performance of codes and redundant requests[EB/OL].[2016-01-07]. http://people.eecs.berkeley.edu/~nihar/publications/The_MDS_Queue.pdf.
[8] ROSENTHAL J, SMARANDACHE R. Maximum distance separable convolutional codes[J]. Applicable Algebra in Engineering, Communication and Computing, 1999, 10(1):15-32.
[9] RASHMI K, SHAH N B, GU D, et al. A solution to the network challenges of data recovery in erasure-coded distributed storage systems:a study on the facebook warehouse cluster[C]//Proceedings of the 5th USENIX Conference on Hot Topics in Storage and File Systems. Berkeley, CA:USENIX Association, 2013:8.
[10] Openstack. Swift service[EB/OL].[2016-06-10]. https://wiki.openstack.org/wiki/Swift/.
[11] Hadoop Wiki. HDFS-RAID[EB/OL].[2016-06-10]. http://wiki.apache.org/hadoop/HDFS-RAID.
[12] ZHANG B, IOSUP A, POUWELSE J, et al. The peer-to-peer trace archive:design and comparative trace analysis[C]//Proceedings of the ACM CoNEXT Student Workshop. New York:ACM, 2010:Article No. 21.
[13] YEUNG K H, SZETO C W. On the modeling of WWW request arrivals[C]//Proceedings of the 1999 International Workshops on Parallel Processing. Piscataway, NJ:IEEE, 1999:248-253.
[14] Wikipedia. Openstack[EB/OL].[2016-06-10]. https://en.wikipedia.org/wiki/OpenStack.
[15] Wikipedia. Prim's algorithm[EB/OL].[2016-06-10]. https://en.wikipedia.org/wiki/Prim%27salgorithm.
[16] LIU S, HUANG X, FU H, et al. Understanding data characteristics and access patterns in a cloud storage system[C]//Proceedings of the 201313th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ:IEEE, 2013:327-334.
[17] SUN Y, ZHENG Z, KOKSAL C E, et al. Provably delay efficient data retrieving in storage clouds[C]//Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ:IEEE, 2015:585-593.
[18] JOSHI G, LIU Y, SOLJANIN E. On the delay-storage trade-off in content download from coded distributed storage systems[J]. IEEE Journal on Selected Areas in Communications, 2013, 32(5):989-997.
[19] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable:a distributed storage system for structured data[J]. ACM Transactions on Computer Systems, 2008, 26(2):205-218.
[20] HUANG C, SIMITCI H, XU Y, et al. Erasure coding in windows azure storage[C]//Proceedings of the 2012 USENIX Conference on Annual Technical Conference. Berkeley, CA:USENIX Association, 2012:2.
[21] CHEN S, SUN Y, KOZAT U C, et al. When queueing meets coding:optimal-latency data retrieving scheme in storage clouds[C]//Proceedings of the 2014 Proceedings IEEE INFOCOM. Piscataway, NJ:IEEE, 2014:1042-1050.
[22] LIANG G, KOZAT U C. TOFEC:achieving optimal throughput-delay trade-off of cloud storage using erasure codes[C]//Proceedings of the 2014 Proceedings IEEE INFOCOM. Piscataway, NJ:IEEE, 2014:826-834.
[23] 罗象宏,舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展,2012,49(1):1-11.(LUO X H, SHU J W. Summary of research for erasure code in storage system[J]. Journal of Computer Research and Development, 2012, 49(1):1-11.)
[24] 蒋海波,王晓京,范明钰,等.基于水平纠删码的云存储数据布局方法[J].四川大学学报(工程科学版),2013,45(2):103-109.(JIANG H B, WANG X J, FAN M Y, et al. A data placement based on level array codes in cloud storage[J]. Journal of Sichuan University (Engineering Science Edition), 2013, 45(2):103-109.)
[25] 李晓恺,代翔,李文杰,等.基于纠删码和动态副本策略的HDFS改进系统[J].计算机应用,2012,32(8):2150-2158.(LI X K, DAI X, LI W J, et al. Improved HDFS scheme based on erasure code and dynamical-replication system[J]. Journal of Computer Applications, 2012, 32(8):2150-2158.)
[26] 葛君伟,李志强,方义秋.云存储环境下基于分散式服务器的Erasure Code算法[J].计算机应用,2011,31(11):2940-2942.(GE J W, LI Z Q, FANG Y Q. Erasure code algorithm based on distributed server in cloud storage environment[J]. Journal of Computer Applications, 2011, 31(11):2940-2942.)
[27] 程振东,栾钟治,孟由,等.云文件系统中纠删码技术的研究与实现[J].计算机科学与探索,2013,7(4):315-325.(CHENG Z D, LUAN Z Z, MENG Y, et al. Research and implementation on erasure code in cloud file system[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(4):315-325.)

基于纠删码的细粒度云存储调度方案

Fine-grained scheduling policy based on erasure code

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	祝永晋, 尹飞, 豆龙龙, 吴昆, 张志伟, 钱柱中. 基于前向纠错的自适应网络传输机制[J]. 计算机应用, 2021, 41(3): 825-832.
[2]	刘风. 基于防治策略的毒品滥用流行病学模型[J]. 计算机应用, 2020, 40(9): 2768-2773.
[3]	李明, 胡江平, 曹晓莉, 彭鹏. 面向差异化覆盖的异构有向传感器节点调度算法[J]. 计算机应用, 2020, 40(12): 3563-3570.
[4]	张航, 刘善政, 唐聃, 蔡红亮. 分布式存储系统中的低修复成本纠删码[J]. 计算机应用, 2020, 40(10): 2942-2950.
[5]	吴三柱, 李鹏, 吴三斌. 移动无线传感器网络中抑制病毒传播模型[J]. 计算机应用, 2020, 40(1): 129-135.
[6]	谭鑫, 李晓卉, 刘振兴, 丁月民, 赵敏, 王琦. 基于电网的采样感知加权循环调度算法[J]. 计算机应用, 2019, 39(7): 2061-2064.
[7]	刘风. 毒品滥用流行病模型的稳定性分析[J]. 计算机应用, 2019, 39(5): 1534-1539.
[8]	王妍, 马秀荣, 单云龙. 长期演进系统基于加权平均时延的下行资源调度[J]. 计算机应用, 2019, 39(5): 1429-1433.
[9]	纪艺, 史昕, 赵祥模. 基于多前车信息融合的智能网联车辆跟驰模型[J]. 计算机应用, 2019, 39(12): 3685-3690.
[10]	赵玉婷, 韩宝玲, 罗庆生. 基于deep Q-network双足机器人非平整地面行走稳定性控制方法[J]. 计算机应用, 2018, 38(9): 2459-2463.
[11]	李静, 刘冬实. 主动容错云存储系统的可靠性评价模型[J]. 计算机应用, 2018, 38(9): 2631-2636.
[12]	蔡秀梅, 刘超, 黄贤英, 刘小洋, 杨宏雨. 网络垃圾信息ILDR传播模型[J]. 计算机应用, 2018, 38(8): 2316-2322.
[13]	樊佳庆, 宋慧慧, 张开华. 通道稳定性加权补充学习的实时视觉跟踪算法[J]. 计算机应用, 2018, 38(6): 1751-1754.
[14]	陈晨, 赵建伟, 曹飞龙. 基于四通道卷积稀疏编码的图像超分辨率重建方法[J]. 计算机应用, 2018, 38(6): 1777-1783.
[15]	王珍珍, 吴英杰. 基于Logistic-Volterra模型的制造企业与物流企业联动发展稳定性分析[J]. 计算机应用, 2018, 38(2): 589-595.