基于闪存的乐观数据复制技术研究

摘要

随着计算机科技与互联网技术的高速发展，全球的应用系统产生了海量的数据。这些数据系统一方面要求较高的访问性能，另一方面也要求较高的可用性，同时也要求具有容量与地理的高可扩展性。所以，分布式存储系统的大规模使用就成为了满足以上需求的必然选择，而其中，数据复制技术尤其是乐观数据复制技术是最为核心的技术之一。乐观数据复制的本质是在各个分布节点上数据副本的创建与维护，那么就必然需要和存储介质发生关联。传统的存储介质一般以机械磁盘为主，但是机械磁盘是上个世纪70年代的产物，已经远远落后于整体的计算机发展进度，不能满足对数据的高吞吐率读写要求，所以一种新型的电子存储器:闪存，应运而生。闪存相比传统磁盘，具有读写吞吐率高，随机读写性能优越，并发读写优势明显等优点，但是，由于其特殊的物理结构，也存在着“写放大”与“重写前擦除”等缺点。所以，传统的应用系统虽然直接通过硬件的升级就可以收到良好的性能提升，但是系统仍然需要进一步的调整与优化，解决“闪存并发写入优势的合理应用”与“闪存写入操作缺陷的规避”这两大问题，才可以充分地发挥闪存的特性。那么，作为与存储介质关系紧密的乐观数据复制系统，在采用闪存作为存储介质之后，也需要进行算法本身的改进与优化，才可以解决上述两大问题，实现数据复制性能等指标的迸一步提升。
　　乐观数据复制根据数据更新的数据流，可以分为5个过程，即操作提交，数据更新分发，数据更新调度，冲突检测/解决，以及数据更新提交。其中与存储系统紧密相关的为三个过程，即数据更新分发，数据更新调度与数据更新提交。所以，针对基于闪存的系统需要解决的两大问题，从上述三个过程出发，本文的主要内容如下:
　　本文首先针对在数据更新的分发过程中，一般以单一数据更新为单位，容易产生大量不适合闪存写入特点的随机小数据量写操作的缺陷，提出了闪存感知的成组数据更新分发算法FAGUA。该算法以相关数据集为数据更新分发的基本单位，并只在相关数据集的修改比率达到一定阈值的时候才触发分发过程，从而实现了以闪存数据块或其整数倍为基准的写对齐，解决了基于闪存特性的数据更新分发时机选择问题。之后，又基于FAGUA，提出了改进的数据更新分发算法IRN-FAGUA，即基于理想数据副本的FAGUA算法。该算法首先对每个相关数据集的理想数据副本数目进行计算，然后以此为依据，解决了在数据更新的分发过程中是否需要创建或替换数据副本的问题。FAGUA与IRN-FAGUA规避了闪存的写入缺陷，降低了闪存的擦写次数，提高了整体的数据复制性能，同时由于数据相关性的引入，也大大地提高了数据副本的本地命中率。
　　之后，本文又针对数据更新调度过程中的缺陷，即调度结构往往为单队列设计，无法充分发挥闪存的并发写入优势，提出了基于闪存的多队列数据更新调度算法，FBSA。FBSA以数据修改集作为数据分发内容，通过对不同数据修改集之间的依赖关系判断，以最小化其非本队列数据依赖集中的元素个数为目标，实现了多队列的调度结构创建。同时，以最大化后台提交过程的并行度为目标，尽可能同时从所有的调度队列中获取头元素用于并发提交，从而实现了多队列调度结构的充分使用。该算法可以充分地发挥闪存的并发写入优势，有利于闪存利用率与数据复制性能的提升。
　　最后，针对数据更新的提交过程中，提交一般以单独的操作为单位，从而也会产生大量小数据量随机写，不适合闪存写入特点的缺陷，本文提出了基于上下文的数据更新提交算法，CBCA。CBCA通过对一定时间窗口内所有操作的上下文分析，得出所有操作之间的可合并，可覆盖或可回滚关系，然后对操作进行合并或者消除，实现了以闪存数据块大小为基准的组提交。从而规避了闪存的写入缺陷，有利于每个操作所消耗的底层I/O数的降低与整体数据复制性能的提升。

目录

声明

致谢

摘要

1 绪论

1．1 研究背景

1．2 研究意义

1．3 研究内容

1．4 研究成果

1．5 论文结构

2 闪存与乐观数据复制

2．1 闪存及基于闪存的系统优化

2．2 数据复制

2．3 乐观数据复制技术

2．4 基于闪存的数据复制技术

2．5 目前研究的不足与下一步方向

2．6 本章小结

3 闪存感知的数据更新分发算法

3．1 引言

3．2 相关研究

3．3 算法整体描述

3．4 数据更新成组分发

3．5 数据副本创建替换

3．6 实验

3．7 本章小结

4 基于闪存的数据更新调度算法

4．1 引言

4．2 相关研究

4．3 系统构架与定义

4．4 算法描述

4．5 实验

4．6 本章小结

5 基于上下文的数据更新提交算法

5．1 引言

5．2 相关工作

5．3 算法描述

5．4 实验

5．5 本章小结

6 总结与展望

6．1 全文总结

6．2 下一步展望

参考文献

作者简历

攻读博士学位期间主要的研究成果