魏征^1,2,窦禹^1,2,高艳珍^1,2,马捷¹,孙凝晖¹,邢晶¹

¹（计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190);²（中国科学院大学 北京 100190) (weizheng@ncic.ac.cn)

出版日期: 2021-04-01


基金资助:国家重点发展计划项目(2018YFC0809300)；国家自然科学基金项目(61502454);联想研究院ECR团队分布式闪存项目

A Consistent Hash Data Placement Algorithm Based on Stripe

Wei Zheng^1,2, Dou Yu^1,2, Gao Yanzhen^1,2, Ma Jie¹, Sun Ninghui¹, Xing Jing¹

¹（State Key Laboratory of Computer Architecture (Institute of Computing Technology,Chinese Academy of Sciences),Beijing 100190);²（University of Chinese Academy of Sciences,Beijing 100190)

Online: 2021-04-01


Supported by:This work was supported by the National Key Research and Development Program of China (2018YFC0809300), the National Natural Science Foundation of China (61502454), and the Distributed Full Flash Project of ECR Team of Lenovo Research Institute.

摘要/Abstract

摘要： 分布式存储系统作为数据存储的载体，广泛应用于大数据领域.纠删码存储方式相对副本方式，既具有较高的空间利用效率，又能保证数据存储的可靠性，因此被越来多的应用于存储系统当中.在EB级大规模纠删码分布式存储系统中，元数据管理成本较大，位置信息等元数据查询效率影响了I/O时延和吞吐量.基于位置信息记录的有中心数据放置算法需要频繁访问元数据服务器，导致性能优化受限，基于Hash映射的无中心数据放置算法越来越多地得到应用.但面向纠删码的无中心放置算法，在节点变更和数据恢复过程中，存在位置变更困难、迁移数据量大、数据恢复和迁移并发度低等问题.提出了一种基于条带的一致性Hash数据放置算法(consistent Hash data placement algorithm based on stripe, SCHash)，SCHash以条带为单位放置数据，通过把数据块到节点的映射转化为条带到节点组的映射过程，减少节点变动过程中的数据迁移量，从而在恢复过程中降低了变动数据的比例，加速了恢复带宽.并基于SCHash算法设计了一种基于条带的并发I/O调度恢复策略，通过避免选取同一节点的数据块进行I/O操作，提升了I/O并行度，通过调度恢复I/O和迁移I/O的执行顺序，减少了数据恢复的执行时间.相比APHash数据放置算法，SCHash在数据恢复过程中，减少了46.71%~85.28%数据的迁移.在条带内重建时，恢复带宽提升了48.16%，在条带外节点重建时，恢复带宽提升了138.44%.

参考文献

相关文章 15

[1]	蒲勇霖, 于炯, 鲁亮, 李梓杨, 国冰磊, 廖彬. 基于Storm平台的数据恢复节能策略[J]. 计算机研究与发展, 2021, 58(3): 479-496.
[2]	徐光伟, 史春红, 冯向阳, 罗辛, 石秀金, 韩松桦, 李玮. 基于多级网络编码的多副本云数据存储[J]. 计算机研究与发展, 2021, 58(2): 293-304.
[3]	李乾, 胡玉鹏, 叶振宇, 肖叶, 秦拯. 基于蚁群优化算法的纠删码存储系统数据更新方案[J]. 计算机研究与发展, 2021, 58(2): 305-318.
[4]	陈茂棠, 郑圣安, 游理通, 王晶钰, 闫田, 屠要峰, 韩银俊, 黄林鹏. 一种基于RDMA多播机制的分布式持久性内存文件系统[J]. 计算机研究与发展, 2021, 58(2): 384-396.
[5]	陈波, 陆游游, 蔡涛, 陈游旻, 屠要峰, 舒继武. 一种分布式持久性内存文件系统的一致性机制[J]. 计算机研究与发展, 2020, 57(3): 660-667.
[6]	包涵, 王意洁, 许方亮. 基于生成矩阵变换的跨数据中心纠删码写入方法[J]. 计算机研究与发展, 2020, 57(2): 291-305.
[7]	张耀, 储佳佳, 翁楚良. 纠删码存储系统数据更新方法研究综述[J]. 计算机研究与发展, 2020, 57(11): 2419-2431.
[8]	唐英杰,王芳,谢燕文. 纠删码存储系统中基于网络计算的高效故障重建方法[J]. 计算机研究与发展, 2019, 56(4): 767-778.
[9]	傅颖勋,文士林,马礼,舒继武. 纠删码存储系统单磁盘错误重构优化方法综述[J]. 计算机研究与发展, 2018, 55(1): 1-13.
[10]	卞建超,查雅行,罗守山,李伟. 一种基于磁盘内和磁盘间冗余的混合编码方案[J]. 计算机研究与发展, 2016, 53(9): 1906-1917.
[11]	毛波,叶阁焰,蓝琰佳,张杨松,吴素贞. 一种基于重复数据删除技术的云中云存储系统[J]. 计算机研究与发展, 2015, 52(6): 1278-1287.
[12]	肖中正, 陈宁江, 魏峻, 张文博. 一种面向海量存储系统的高效元数据集群管理方案[J]. 计算机研究与发展, 2015, 52(4): 929-942.
[13]	周 江, 王伟平, 孟 丹, 马 灿, 古晓艳, 蒋 杰,. 面向大数据分析的分布式文件系统关键技术[J]. 计算机研究与发展, 2014, 51(2): 382-394.
[14]	王强, 李雄飞, 王婧. 云计算中的数据放置与任务调度算法[J]. 计算机研究与发展, 2014, 51(11): 2416-2426.
[15]	朱 夏 罗军舟 宋爱波 东 方. 云计算环境下支持复杂查询的多维数据索引机制[J]. , 2013, 50(8): 1592-1603.

PDF全文下载地址:

https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4408