分布式文件系统中的若干关键算法研究

论文摘要

随着社会、经济、互联网的高速发展,全球每年产生的数据量正呈几何数量级的速度增长,人类已经进入了大数据的时代。如何高效、可靠的存储、访问这些大数据,一直是企业界、学术界研究的热点。过去的数据存储大都是集中式的存储方式,而随着数据量的高速增长,集中式的存储方式在面对日益增长的存储、访问需求时,计算资源、IO资源、网络资源和存储资源都将会出现瓶颈。近十年来,人们意识到,可以利用大量廉价的计算机组成的计算机集群来解决日益增长的存储、计算、网络访问需求。现在,集群已经成为主流的高性能计算机体系架构。在集群上搭建分布式文件系统,也成为当今解决海量数据存储、访问的主流解决方案。本文针对面向集群计算的分布式文件系统中的若干关键问题进行了研究,主要工作如下：◇提出并实现了一种锁无关的消息队列访问算法。当前市场上流行的分布式文件系统中的每个服务器大都采取了多线程的架构方案。网络模块是一个单独的线程,通过一个基于锁的消息队列和其它处理业务逻辑的线程进行通信。当分布式文件系统中访问量增大时,锁冲突造成的效率下降是网络模块的一个性能瓶颈。本文提出了一种锁无关的网络消息队列访问算法,有效地解决了一个读者、一个写者环境下锁带来的性能问题。◇提出并实现了一种支持流水线式访问的多数据服务器访问算法。分布式文件系统中的数据是分散存储在不同数据服务器上的,同时访问多个数据需要一个分布式互斥算法,当前的分布式文件系统大多采取锁管理器的方法。本文提出了一种新的分布式互斥算法,充分利用了分布式集群中数据访问的“流水线”特征,使得资源利用最大化,有效解决了锁管理服务器带来的访问延迟问题。◇提出并实现了一种支持动态增减决策者的分布式一致性算法。分布式一致性算法是分布式文件系统中使用的基础算法之一,传统的分布式一致性算法,例如Paxos算法,大都不支持增减决策者。本文提出了改进的Paxos算法,可以在决策的过程中动态增减决策者,有效解决了使用传统一致性算法时无法扩展系统的问题。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景与意义
• 1.1.1 分布式文件系统架构
• 1.2 锁无关消息队列
• 1.3 多数据服务器访问
• 1.3.1 基于令牌环的算法
• 1.3.2 基于集中管理的算法
• 1.3.3 基于许可的算法
• 1.3.4 基于流水线的分布式锁算法
• 1.4 动态分布式系统中的一致性
• 1.4.1 一致性问题概述
• 1.4.2 经典Paxos算法与动态集群
• 1.4.3 改进的Paxos算法
• 1.5 本文的主要工作及章节安排
• 1.5.1 主要工作
• 1.5.2 章节安排
• 第二章 一种锁无关的消息队列访问算法
• 2.1 “忙等待”锁
• 2.2 锁无关数据结构
• 2.3 锁无关消息队列
• 2.3.1 锁无关消息队列数据结构
• 2.3.2 消息队列初始化
• 2.3.3 消息队列的Push操作
• 2.3.4 消息队列的Pop函数
• 2.4 实验对比
• 2.4.1 不间断读写测试
• 2.4.2 写者、读者先后运行
• 2.4.3 读者间或运行
• 2.5 本章小结
• 第三章 支持流水线访问的多数据服务器访问算法
• 3.1 分布式系统互斥问题场景分析
• 3.2 现有的分布式互斥算法分析
• 3.2.1 基于令牌环网的分布式互斥算法
• 3.2.2 基于许可请求的分布式锁算法
• 3.2.3 基于集中管理的分布式锁算法
• 3.2.3.1 GFS中更新多个数据副本的方式
• 3.2.3.2 锁住多个文件的需求
• 3.3 基于流水线的分布式锁算法
• 3.3.1 分布式系统中隐含的流水线性
• 3.3.2 基于流水线的分布式锁
• 3.3.2.1 本节使用的符号概念
• 3.3.2.2 分布式锁数据结构
• 3.3.2.3 基于锁数据结构进一步阐述流水线性质
• 3.3.2.4 服务器上锁的冲突点
• 3.3.2.5 基于流水线的锁算法描述
• 3.4 具有循环结构的基于流水线的锁
• 3.5 实验结果
• 3.5.1 从客户端角度分析
• 3.5.2 从服务器角度分析
• 3.5.3 网络环境差时分析
• 3.5.4 网络数据包量分析
• 3.6 本章小结
• 第四章 一种支持动态集群的分布式一致性算法
• 4.1 分布式一致性问题
• 4.2 动态集群
• 4.3 经典的PAXOS算法
• 4.3.1 Paxos算法中的几个概念
• 4.3.2 Paxos算法概述
• 4.3.3 动态集群中的Paxos算法
• 4.4 改进的PAXOS算法
• 4.4.1 决策者版本号
• 4.4.2 动态集群下的一致性要求
• 4.4.3 改进的Paxos算法
• 4.4.3.1 经典Paxos算法中规则解释
• 4.4.3.2 对Paxos算法规则进行扩展
• 4.4.3.3 规则2可操作性的演化
• 4.4.3.4 规则3、4的可操作性的规则演化
• 4.4.3.5 改进的Paxos算法规则总结
• 4.4.3.6 改进的Paxos算法具体描述
• 4.5 实验结果及分析
• 4.5.1 经典Paxos算法测试
• 4.5.2 改进的Paxos算法测试
• 4.5.3 新算法数据包分析
• 4.6 本章小结
• 第五章 总结和展望
• 5.1 本文工作总结
• 5.2 进一步的研究工作
• 参考文献
• 攻读硕士学位期间主要工作
• 致谢