海量对象存储系统数据组织算法的研究

论文摘要

在网络存储系统中,数据的组织优化是提高存储系统性能的有效方法之一。合理的数据组织算法可提高存储系统的性能,使存储系统具有高可靠性、可用性和可扩展性。网络存储系统中的数据组织包括两个方面的内容:存储空间的数据组织和传输路径上的数据组织。存储空间的数据组织利用存储节点间的并行性,提高存储系统的I/O性能,通过不同存储节点的数据副本提高数据的可靠性和可用性;传输路径上的数据组织则是通过传输路径上的Cache合理配置和替换算法的选择,达到提高I/O性能的目的。本文根据对象存储系统的特点,研究数据组织的算法及相关问题,包括以下几方面的内容:对象存储区别于其它网络存储系统之处在于它将文件系统的存储管理和用户管理分离,存储管理由存储节点来完成,而用户管理则通过元数据服务器来实现。这种功能的分离使得元数据服务器成为瘦服务器,便于存储系统的扩展。对象有丰富的语义,通过对象的语义,对象存储为存储系统提供安全保障,还可以为应用提供基于QoS的I/O服务。对象存储系统的体系结构使其有两种数据传输模式:NAS模式和三方传送模式,传输模式结合Cache方案可达到提高存储系统性能的目的。对象存储系统的存储空间的数据组织就是要实现数据对象在存储节点间按存储节点的容量分布,数据组织算法应尽可能减小算法的时间和空间开销,同时要保证算法适应存储系统的扩展,为此,设计了一种数据定位算法及扩展数据迁移算法。算法有以下特点:将存储节点分组,采用组间按容量分布和组内均匀分布的机制实现数据按容量分布;算法采用映射函数实现用户空间到存储空间的映射,使得算法的时间开销和空间开销最小;算法的适应性则通过记录系统的扩展信息来实现;相应的扩展迁移算法则保证系统扩展引起的数据迁移量最小。应用要求存储系统提供基于QoS的I/O服务,而数据迁移对存储系统的服务质量有影响。通过对基于QoS的I/O服务模型的分析,定义迁移任务附加收益,并将迁移任务细分为迁移请求,在此基础上建立一个基于QoS的数据迁移模型,并设计出相应的最大收益迁移调度算法。实验表明,该迁移调度算法对I/O服务质量的影响小于常用的迁移算法。数据传输路径上的数据组织涉及到Cache替换算法,而Cache替换算法的好坏标准是存储系统的性能是否提高。通过对对象存储系统的加速比进行分析得出结论:Cache对存储系统的性能改善不仅与Cache命中率有关,还与数据对象的设备访问时间有关。根据这一结论,设计出两种Cache替换算法:LAT算法和WLFRU算法。LAT算法选择Cache中设备访问时间短、命中率低的数据对象作为替换的对象;WLFRU算法则通过对访问频率的加权达到同时考虑访问的局部性和数据对象的访问成本的目的。两种算法的性能都优于常用的LRU算法。数据传输路径上的Cache设置必须结合数据的访问特点,而对象存储系统的三种实体的特点各不相同,所以,它们的Cache方案也各不相同。根据存储节点的读写速度慢的特点,将其Cache设置为预取Buffer和写Buffer,前者利用预取缩短数据对象的读响应时间,后者通过延迟写,及时响应写请求。元数据服务器和客户端的Cache方案则和数据传送模式相联系,元数据服务器Cache在负载轻时缓存小数据对象,而客户端的Cache除了对两类数据对象都缓存外,还使用磁盘Cache积累采用三方传送的数据对象,达到减少网络通信量的目的。实验显示三类Cache的设置有助于存储系统的性能改善。

论文目录

• 摘要
• ABSTRACT
• 1 存储系统概述
• 1.1 信息存储需求新特点
• 1.2 信息存储的现状
• 1.2.1 存储设备的现状
• 1.2.2 存储系统的现状
• 1.2.3 信息存储的研究热点
• 1.3 存储系统的数据分布和组织
• 1.3.1 计算机系统层次存储模型
• 1.3.2 网络存储系统的性能模型
• 1.3.3 网络存储系统中的数据组织
• 1.3.4 数据组织的重要性
• 1.4 本文的主要内容
• 1.5 课题来源
• 2 海量对象存储系统
• 2.1 对象存储思路
• 2.1.1 NAS
• 2.1.2 SAN
• 2.1.3 对象存储
• 2.2 对象存储系统的体系结构
• 2.2.1 硬件体系结构
• 2.2.2 软件结构
• 2.3 三方传送模式和NAS 模式
• 2.3.1 对象存储中的数据传输模式
• 2.3.2 两种模式的性能比较
• 2.4 基于三方传送的对象存储安全方案
• 2.5 对象存储应用方向
• 2.6 本章小结
• 3 可扩展对象存储系统的数据分配算法
• 3.1 分布式存储系统数据分配算法
• 3.2 分布式存储系统模型及相关定义
• 3.2.1 分布式对象存储系统模型
• 3.2.2 存储模型的相关定义
• 3.3 可扩展的存储系统数据分配算法
• 3.3.1 数据分配算法的设计原则
• 3.3.2 存储系统数据分配算法
• 3.3.3 数据分配算法的时间和空间开销
• 3.3.4 数据重新组织算法
• 3.3.5 异构存储节点的数据分配和重组算法
• 3.4 本章小结
• 4 基于QOS 的数据迁移模型的设计
• 4.1 基于QOS 的I/O 模型
• 4.1.1 OSD 协议
• 4.1.2 基于QoS 的I/O 响应调度模型
• 4.2 基于QOS 数据迁移调度算法
• 4.2.1 基于QoS 的迁移思想
• 4.2.2 迁移收益
• 4.2.3 基于QoS 的迁移体系结构
• 4.2.4 最大收益调度算法
• 4.3 实验及结果分析
• 4.4 本章小结
• 5 存储系统的CACHE 替换算法的研究
• 5.1 存储系统模型及其性能公式
• 5.1.1 层次存储系统模型
• 5.1.2 存储系统的性能公式
• 5.2 存储系统的CACHE 替换算法
• 5.2.1 LAT 算法
• 5.2.2 WLFRU 算法
• 5.3 CACHE 替换算法的模拟及性能分析
• 5.4 本章小结
• 6 对象存储系统中的CACHE 方案
• 6.1 存储系统CACHE 方案的整体思路
• 6.2 存储节点的CACHE 方案
• 6.2.1 存储节点的数据对象访问特点
• 6.2.2 MEMS 存储设备
• 6.2.3 存储节点的写Buffer
• 6.2.4 存储节点的预取Buffer
• 6.2.5 存储节点控制器Cache 替换算法
• 6.3 元数据服务器CACHE 方案
• 6.3.1 元数据服务器Cache 的设计
• 6.3.2 准入控制策略
• 6.3.3 Cache 替换算法
• 6.4 客户端Cache 方案
• 6.4.1 客户端数据访问特点
• 6.4.2 客户端Cache 的设计
• 6.5 性能评价
• 6.5.1 存储节点Cache 性能
• 6.5.2 元数据服务器及客户端Cache 性能评价
• 6.6 本章小结
• 7 全文总结
• 7.1 本文取得的主要研究成果
• 7.2 进一步研究工作的考虑
• 致谢
• 参考文献
• 附录 攻读博士学位期间发表论文目录