云备份系统中闪存辅助分段式布隆过滤器的研究

摘要

为了能够在网络带宽较低或中等的区域实现云备份应用,网络上传输的数据量应越低越好,通过对备份数据使用重复数据删除技术,能够显著降低网络传输数据量。重复数据删除的方法很多,其中一个解决方案是将文件切分成比较小的片段,这需要使用到大布隆过滤器。在空间/时间效率方面,布隆过滤器相比其他数据结构具有明显的优势。但布隆过滤器在哈希函数个数增加或者它装载的元素个数增加时,误判率会有升高的趋势。由于云备份系统重复数据删除将产生大量指纹,若布隆过滤器的长度较小则会产生较高的误判率,长度增大则会增加内存消耗。
　　针对如何降低内存消耗,提高重复数据删除的整体性能,本文提出了一种闪存辅助分段式的布隆过滤器(FASBF)方法,即在大规模云备份系统中将布隆过滤器部署在SSD上。由于SSD没有机械磁头,因此其读速度很快;而分段式的布隆过滤器则可以方便划分存储空间。在本文的方法中,布隆过滤器全部保存在SSD中,只有部分保存在RAM中。保存在RAM中的部分布隆过滤器的大小决定了整个应用的RAM空间消耗。当部分分段式布隆过滤器阵列(PSBFA)大小占整个分段式布隆过滤器阵列(FSBFA)大小的一半时,应用的内存消耗就减少为原来的一半。本文使用三种方法优化了重复数据删除的数据检索过程:首先布隆过滤器的长度可以充分大,其次可以使用更多的哈希函数来减少误判率,最后由于布隆过滤器占用的内存空间减少,内存中可以缓存更多的指纹,这将极大地减少由误判率导致的磁盘I/O开销。为了最大化利用SSD,文件和数据块的指纹哈希桶(在初始状态时)部分被保存在SSD上,而随着布隆过滤器的增大,SSD上分配给指纹哈希桶的空间将逐渐减少,这时将会把哈希桶保存到磁盘上。
　　本文基于一个云备份系统,对FASBF方法进行了原型实现及性能测试。结果表明本方法能够节省可观的内存空间,同时又能达到100MB/S左右的备份吞吐率。

目录

封面

声明

中文摘要

英文摘要

目录

1 Introduction

1.1 Cloud Backup

1.2 Motivation

1.3 Problem Statement and the solution

1.4 Overview of the Thesis

2 Related Works

3 Background and key technologies

3.1 Architecture and Design of Standard Bloom Filters

3.2 Rabin fingerprinting

3.3 MD5 hashing

3.4 Data Deduplication

3.5 Solid State Drives

4 Architecture and Design of FASBF

4.1 Segmented Bloom Filter Array in RAM and SSD

4.2 Hash Buckets in SSD and HDD

4.3 FASBF work flow

5 Prototype Implementation and Evaluation

5.1 Prototype Implementation

5.2 Evaluation

6 Conclusion

致谢

参考文献

Appendix