1.2.4 数据缩减技术

当前数据量以指数级速度迅猛增长，但是数据管理投资预算的增长率远远低于数据增长速度，以至于各种存储媒体介质的总容量增长慢于数字世界的数据增长率，造成全世界绝大部分生成的数据无法保存起来进行处理分析。著名国际咨询机构IDC公司统计表明2013年全世界可用的存储容量只占整个数据产生量的33%，预计到2020年这个比例将降低至15%[1]。因此，提高数据存储空间利用率的数据缩减技术对当前大数据存储管理至关重要。

数据缩减技术是指一类能够有效地删除数据冗余提升存储空间利用率的技术，主要包括：数据压缩（Data Compression）[9]、差分编码（Delta Encoding）[10]和重复数据删除（Data Deduplication）[11]这三类经典技术。

数据压缩是指采用编码方式用更少的比特位来表示数据对象内原始信息的技术。数据压缩的方式非常多，根据压缩后是否损失信息可分为无损压缩和有损压缩两大类。无损压缩是通过确定和删除统计冗余来减少数据对象存储的比特位。由于数据统计冗余度的理论限制，无损压缩的压缩比一般比较低，被广泛应用于文本数据、程序和特殊应用场合的图像数据等需要精确存储数据的压缩。典型的无损压缩算法有：香农-范诺编码（Shannon-Fano coding）、霍夫曼编码（Huffman coding）、算术编码（arithmetic coding）、游程编码（run-length coding）、词典编码（dictionary coding）等；词典编码算法中的Lempel-Ziv（LZ）压缩方法[15]是最流行的无损压缩算法，被广泛应用于WinRAR、GZIP和GIF等压缩软件。

有损压缩通过发现和删除数据对象中不重要的信息来减少存储所需的比特位。它利用人类视觉、听觉对图像、声音中的某些频率成分不敏感的特性，允许压缩的过程中损失一定的信息。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了比较大的压缩比，被广泛应用于语音、图像和视频数据的压缩。由于删除数据对象内部冗余的本质，数据压缩仅能获得有限的数据缩减率。经典的有损压缩算法有：图像压缩领域的JPEG标准和视频压缩领域的MPEG标准等。

差分编码是通过开发数据对象间相似性来压缩数据对象存储空间的技术。它能够定位两个相似的数据对象中的共同数据内容，并按它们存储的先后分为旧版本和新版本。通过差分算法可以获得反映数据对象新旧版本之间差异的Delta对象，数据对象的新版本可以由它们之间差异的数据内容与旧版本联合生成。由于Delta对象编码后往往可以远小于原数据对象，Delta编码能够有效地缩减数据对象的存储空间。为了确定两个数据对象是否相似的算法有很多，比如计算数据对象内所有固定窗口内容中的弱哈希值，选取几个最小或最大的哈希值作为特征来比较和判断两个数据对象是否相似。如果两个数据对象有相同的相似特征则认为它们的内容十分相似。相比于数据压缩，Delta编码通过额外的计算开销和内存资源开销能够发现和消除更多的数据冗余。

重复数据删除技术是一种能消除粗粒度数据冗余的特殊数据缩减技术，被广泛应用于基于硬盘的备份系统。它通过将数据流划分为若干数据对象，并对各个数据对象进行加密哈希指纹计算，基于数据对象指纹的索引查询检测出数据流中相同的数据对象，只传输或者存储唯一的数据对象副本，并使用指向唯一副本的指针替换其他副本。基于不同的区分原则，我们可以对重复数据删除技术进行不同的分类。根据进行重复数据删除操作位置的不同，可以分为源端重复数据删除和目标端重复数据删除。根据进行重复数据删除操作时机的不同，可以分为在线重复数据删除和离线重复数据删除。按进行重复数据删除操作粒度的差异，可以分为文件级、块级和字节／比特位级重复数据删除。根据进行重复数据删除处理的节点数目差异，可以分为单节点重复数据删除和分布式重复数据删除。根据重复数据删除操作范围的不同，可以分为全局重复数据删除和局部重复数据删除。根据重复数据匹配效果的差异，可以分为精确重复数据删除和近似重复数据删除。目前，重复数据删除技术不仅应用于备份、容灾和归档等二级存储中，还应用于虚拟化环境下的主存储系统。

如图1-7所示，数据缩减技术可以将数据集中重复数据块、相似数据块甚至重复字节分别通过重复数据删除、Delta编码和压缩分别进行存储空间缩减。在逻辑空间内，文件1划分为1号和2号数据块，文件2划分为3号、4号、5号数据块，块2和块3内容相同，块1和块5相似，块4含有大量重复字节。在物理空间里，重复数据删除可以避免存储块2，差分压缩可以根据块5计算出块1的差分块，只需对差分块进行压缩存储，并可与块4的压缩内容存储在同一数据块空间内。

图1-7 数据缩减技术原理

随着人们不断利用其数据缩减优势来改进和优化现有存储和网络系统，数据缩减技术的应用将会越来越广泛。近年来，工业界和学术界都对数据缩减技术进行了深入的探讨和研究，其应用范围正在从二级存储向主存储延伸，从存储领域向通信领域扩展。随着绿色IT进程的不断推进，数据缩减技术已成为云计算中的核心技术。比较传统的数据压缩技术，重复数据删除技术不仅可以消除数据对象内部的冗余，还能消除数据对象之间的冗余。而相比于差分编码，重复数据删除能够以更低的系统开销获得高数据缩减率。