负载均衡的大数据分布存储方法研究与实现
本文关键词：负载均衡的大数据分布存储方法研究与实现
【摘要】：随着大数据的发展,用户对于数据存储的需求越来越高。这些需求主要体现在可存储的数据规模、存储系统的可扩展性、可靠性以及读写性能等方面。传统的集中式存储由于成本或可扩展性的限制,不能满足如今EB或以上数量级的存储需求,因此各种分布式存储系统应运而生。数据分配策略,作为决定数据及其副本的存储位置和存取方式的基本规则,是设计和实现分布式存储系统所需要考虑的一个关键因素。CRUSH(Controlled Replication Under Scalable Hashing)算法是应用于Ceph分布式存储系统中的一种伪随机数据分配算法,具有高效率、高可扩展性的特点。然而,CRUSH算法在实现系统负载均衡上存在不足,具体表现在两个方面:首先,该算法对用户数据在系统中各存储设备上的分布不够均衡,设备间存储数据量之差可达到20%。这导致了存储数据多的设备接受更多的读写请求,在总数据量大、负载并发度高时成为系统的性能瓶颈。其次,CRUSH算法为了解决同一份数据的不同备份在失效域(Failure Domain)间均衡分布的问题,提出了一套副本存放规则。但该规则提供的原语有限,限制了副本的灵活分配,用户只能指定数据的不同副本在同一等级的失效域间分布,而不能跨多级失效域。针对上述两个问题,本文分别提出了解决方案。其中,对于数据在系统中各存储设备上分布不均衡的问题,我们设计并实现了B-CRUSH算法,它是基于CRUSH算法的一种均衡数据分布算法,通过引入新的哈希函数、新的选择分配算法以及自适应预分配模型这三个步骤来改进现有的CRUSH算法,使得产生的数据分配结果更加均衡,以达到消除系统“热点”和瓶颈的目的。对于有限的副本存放规则原语问题,我们通过引入新的关键字原语ignore,设计并实现了可以跨多级失效域的副本存放规则。该规则提供了对副本更细粒度的控制,能够一一指定数据每个副本的分配策略,并且保证同一数据的当前副本不会被分配到与之前的副本相同的失效域中。此外,本文还通过实验对于上述两种解决方案进行了验证。通过与现有CRUSH算法的对比,我们提出的B-CRUSH算法有效地提高了数据分布均衡性,并且将系统的随机读性能提升了10%以上;而新的副本存放规则成功地解决了数据副本跨多级失效域均衡存放的问题,为用户提供了更灵活的副本分配策略。
【关键词】：大数据 分布式存储 数据分布 负载均衡
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13;TP333
【目录】：
- 摘要3-5
- ABSTRACT5-13
- 第一章 绪论13-21
- 1.1 研究背景及意义13-15
- 1.2 国内外研究现状15-19
- 1.3 研究目标与内容19
- 1.4 论文组织结构19-21
- 第二章 背景工作21-31
- 2.1 Ceph分布式存储系统21-23
- 2.2 RADOS组件23-24
- 2.3 CRUSH算法24-30
- 2.3.1 CRUSH Map24-29
- 2.3.2 副本存放规则29-30
- 2.4 本章小结30-31
- 第三章 问题定义31-35
- 3.1 数据空间分布均衡性31-33
- 3.2 副本存放规则原语33-34
- 3.3 本章小结34-35
- 第四章 算法设计35-53
- 4.1 B-CRUSH算法的设计35-44
- 4.1.1 pps哈希算法37-39
- 4.1.2 linear类型bucket39-42
- 4.1.3 自适应模型42-44
- 4.2 副本存放规则原语的设计44-51
- 4.2.1 同级失效域间的副本存放规则47
- 4.2.2 跨多级失效域的副本存放规则47-51
- 4.3 本章小结51-53
- 第五章 算法实现53-61
- 5.1 B-CRUSH算法实现55-57
- 5.2 副本存放规则原语实现57-59
- 5.3 本章小结59-61
- 第六章 实验验证61-77
- 6.1 B-CRUSH算法实验验证61-71
- 6.1.1 B-CRUSH算法验证环境61-63
- 6.1.2 B-CRUSH算法验证方法63-64
- 6.1.3 B-CRUSH算法验证结果64-71
- 6.2 副本存放规则原语实验验证71-76
- 6.2.1 副本存放规则原语验证环境71
- 6.2.2 副本存放规则原语验证方法71
- 6.2.3 副本存放规则原语验证结果71-76
- 6.3 本章小结76-77
- 第七章 总结与展望77-81
- 7.1 全文总结77-78
- 7.2 研究展望78-81
- 参考文献81-85
- 致谢85-86
- 攻读学位期间发表的学术论文目录86-88
【相似文献】
中国期刊全文数据库 前10条
1 袁茵;;数据分布服务推动了注重数据的系统发展[J];电子技术;2006年11期
2 夏军;庞征斌;张峻;李永进;;一种基于0-1整数规划的全局数据分布优化方法[J];国防科技大学学报;2009年04期
3 郑胜;郝毫毫;;基于贝努利大数定律的数据分布算法[J];计算机工程;2009年19期
4 丁莹;几种数据分布设计方法的比较与进一步探讨[J];计算机时代;1994年04期
5 丁莹;几种数据分布设计方法的探讨[J];微型电脑应用;1994年04期
6 武继刚，庞淑萍;堆上的数据分布与堆选择算法[J];计算技术与自动化;1995年04期
7 陈楠;分布式数据库系统数据分布策略分析[J];计算机时代;1998年10期
8 钱旭明;;数据分布规划的数学模型[J];宁波大学学报(理工版);1992年02期
9 王于同;一种以负载平衡为目标的分布式数据分布算法[J];杭州电子工业学院学报;1995年02期
10 王秀坤,吴月堂,张盛;一种有效的数据分布算法[J];计算机工程与应用;2000年12期
中国重要会议论文全文数据库 前10条
1 胥永康;岳筱玲;潘泽友;;基于数据分布的劳动力市场信息系统[A];第六届全国计算机应用联合学术会议论文集[C];2002年
2 李宏;;港口企业信息系统数据分布技术[A];全国飞机与船舶通信导航学术研讨会论文集（下）[C];2000年
3 陈楠;;分布式数据库系统的数据分布策略研究[A];信息科学与微电子技术:中国科协第三届青年学术年会论文集[C];1998年
4 王e，
本文编号：577773
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/577773.html
