并行迁移压缩算法的研究与实现

• 作 者: 周双鹏
• 机 构: 华中科技大学
• 出 处: 华中科技大学
• 发表日期: 2016年期
• 关键词: 滑动窗口 迁移压缩 并行化 数据块预取

随着近年来数据规模的爆炸式增长,数据去重和数据压缩作为削减数据冗余的两种关键技术,受到了更多的关注。和数据去重技术相比,数据压缩技术能够消除更多的数据冗余。在检测冗余数据的过程中,数据压缩技术一般采用“滑动窗口”的方式来限制查找范围,因此在相似数据相距较远从而超出滑动窗口的检索范围时,便没有机会削减这部分数据冗余。现有的迁移压缩算法通过基于相似数据块检测的数据置换操作,将相似的数据块集中存放到一起,使得传统压缩算法在有限的滑动窗口范围内检测出更多数据冗余的机会大大增加,从而改善其数据压缩率。然而,该算法仅针对单个文件内的相似数据进行处理,并且采用的是串行编程的思想,因此成为海量存储系统及传输网络数据压缩处理的瓶颈。为了解决这一问题,提出了一种并行迁移压缩算法。该算法一方面对迁移压缩算法中计算密集型的功能模块(数据分块、数据去重以及相似性检测)进行并行化和流水化的设计,以降低时间开销;另一方面采用非对称极值分块算法加速数据分块过程,引入数据去重技术来提高相似性检测的处理效率。与此同时,针对并行化设计所导致的重组压缩模块吞吐量严重下降的问题,提出了一种基于迁移文件谱的数据块预取策略,有效减少了分块重组过程中的磁盘等待时延,提高了重组压缩模块的吞吐量。实验结果表明,并行迁移压缩算法可以使传统压缩算法的压缩率提升65%~85%,同时有效降低整体的时间开销。