FlashCache位运算替换算法的设计与实现

论文摘要

人类已迈入一个信息以几何级数增长的时代,对存储系统的要求不断提高,存储系统中性能、容量、与成本之间的矛盾日益突出。分层存储作为一种能够有效解决上述矛盾的技术,受到企业界和学术界的广泛关注,在近年来成为研究热点。所谓分层存储,就是通过分层存储软件实现数据客体在不同层次存储设备之间的自动迁移。近十年来,企业界、学术界推动分层存储系统向自动化、智能化方向发展,研制出了众多新型的分层存储系统。FlashCache是由Facebook开发的一种优秀的分层存储软件,可以显著提高存储系统的IOPS(I/O per second)性能。论文以FlashCache软件为基础,研究了FlashCache的工作机制,分析其优缺点,并在其基础上设计并实现了FlashCache位运算替换算法。论文主要工作包括:1)对现有分层存储技术深入研究和分析;2)对固态硬盘SSD和硬盘的特性深入研究和分析;3)深入研究FlashCache的数据结构和算法,分析它的优点和缺点;4)详细设计了FlashCache位运算替换算法。测试表明论文设计的FlashCache位运算替换算法能够提高FlashCache的读写性能,论文提出的算法可以减少数据写入SSD的次数,从而对于延长SSD的使用寿命有一定效果。论文的成果对于其它Cache算法的设计也具有较好的借鉴价值。

论文目录

• 摘要
• ABSTRACT
• 图目录
• 表目录
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 数据信息的生命周期规律要求
• 1.1.2 在线存储的性能需求
• 1.2 研究内容及目标
• 1.3 论文结构
• 第二章 分层存储简介
• 2.1 分层存储工作原理
• 2.2 分层存储存储方式
• 2.3 数据信息的生命周期规律
• 2.4 分层存储管理关键技术
• 2.4.1 增量扫描技术
• 2.4.2 基于多指标的数据分级策略
• 2.4.3 在线迁移中的一致性保证技术
• 2.4.4 数据自动迁移存储技术
• 2.5 国内外相关机构研究现状
• 2.5.1 IBM Tivoli Storage Manager for Space Management
• 2.5.2 Dell Compellent 技术
• 2.5.3 EMC FAST 技术
• 2.5.4 3PAR 自适应优化软件
• 2.6 本章小结
• 第三章 固态硬盘SSD 与传统硬盘
• 3.1 固态硬盘SSD 简介
• 3.1.1 固态硬盘SSD 存储特性
• 3.1.2 固态硬盘SSD 的优势
• 3.1.3 固态硬盘SSD 的劣势
• 3.2 传统硬盘简介
• 3.2.1 硬盘的物理特性
• 3.2.2 硬盘的基本参数
• 3.3 SSD 盘与硬盘对比
• 3.4 本章小结
• 第四章 FLASHCACHE
• 4.1 LINUX 设备映射层
• 4.1.1 设备映射层的重要数据结构
• 4.1.2 设备映射层内核中建立过程
• 4.1.3 设备映射层I/O 流
• 4.1.4 用户空间部分
• 4.1.5 设备映射层与FlashCache
• 4.2 FLASHCACHE 的主要数据结构与算法
• 4.2.1 FlashCache 主要模块
• 4.2.2 FlashCache 写入方式
• 4.2.3 FlashCache 主要架构
• 4.2.4 FlashCache 读过程
• 4.2.5 FlashCache 写过程
• 4.2.6 FlashCache 替换算法
• 4.3 FLASHCACHE 优缺点分析
• 4.4 本章小结
• 第五章 FLASHCACHE 位运算替换算法
• 5.1 主要数据结构和算法
• 5.1.1 主要数据结构
• 5.1.2 位运算
• 5.2 主要访问流程
• 5.2.1 初始化流程
• 5.2.2 读数据流程
• 5.2.3 写数据流程
• 5.3 日志
• 5.4 优化
• 5.4.1 压缩位计数表
• 5.4.2 Cache 块位计数表索引
• 5.4.3 标记最近访问队列
• 5.5 本章小结
• 第六章 FLASHCACHE 位运算替换算法测试
• 6.1 测试环境
• 6.2 IOPS 测试
• 6.3 读I/O 测试
• 6.4 写I/O 测试
• 6.5 写SSD 次数分析
• 6.6 本章小结
• 第七章 总结与展望
• 7.1 本文总结
• 7.2 研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文