重复数据删除与压缩:数据缩减中的两个概念

2020年12月28日17:14:57 发表评论 125 次浏览

本文概述

通过重复数据删除和压缩来减少数据

据市场调查公司IDC, 世界上存在的数据量每24个月翻一番。以这个速度, 数字宇宙到2020年, 该数据量将达到44 ZB。该数字是通过转换一年中产生或复制的44万亿GB数据来计算的。这种发展主要影响到存储技术, 备份过程和恢复系统, 它们必须能够承载和处理大量数据。技术实施的概念着重于减少物理存储的信息, 从而降低数据管理的成本。这些方法基本上基于两个概念:数据压缩和重复数据删除。无损压缩使用冗余在文件内要压缩数据, 重复数据删除算法将镜像数据跨文件避免重复。因此, 重复数据删除的主要应用是数据备份。

重复数据删除

重复数据删除是一种数据缩减过程, 其本质上基于防止数据冗余在存储系统中。为此, 使用了重复数据删除引擎, 该引擎会生成特殊算法以识别和消除冗余文件和数据块。可以将其集成到用于存储信息的备份软件或硬件中, 或实现为中间设备。

存储技术中重复数据删除的目的是在非易失性存储介质上只写尽可能多的信息, 以便能够无损地重建文件。删除的重复项越多, 需要存储或传输的数据量就越小。例如, 可以使用Git或Dropbox在文件级别完成重复项的标识。但是, 一种更有效的方法是使用重复数据删除算法, 该算法在子文件级别上起作用。为此, 首先将文件分解为数据块(大块)并授予唯一的校验和, 或者散列值。的跟踪数据库包含每个校验和, 作为中央监管实体。

基于块的重复数据删除方法可以分为两种变体:

  • 具有固定块大小的重复数据删除:对于具有固定块大小的重复数据删除, 算法将文件划分为完全相同长度的部分。这通常基于文件或RAID系统的群集大小(通常为4KB), 但有时也可以手动配置。在这种情况下, 采用单独调整的块大小作为所有数据块的标准大小。
  • 具有可变块大小的重复数据删除:另一方面, 具有可变块大小的重复数据删除, 未定义特定的标准大小。相反, 该算法将数据划分为不同的块, 其长度根据要处理的数据类型而变化。

块划分的类型对数据复制的效率有很大的影响。当随后删除重复数据删除的文件时, 这一点尤其明显。

如果一个数据块带有固定块边界如果扩展了附加信息, 则通常还会相对于固定块边界重新定位所有后续块的内容。尽管更改仅影响一个数据块, 但由于重复数据删除算法导致块边界发生变化, 因此文件的所有后续段也将被归类为新的。除非修改后的字节正好是固定块大小的整数倍。由于将这些数据保存为新近重新分类的数据块, 因此在具有固定块大小的重复数据删除备份的情况下, 计算量和带宽容量都会增加。

另一方面, 如果算法使用可变块边界, 单个数据块的修改不会影响下一个段。取而代之的是, 修改后的数据块只是简单地扩展并与新字节一起存储。由于在备份过程中传输的数据较少, 因此减轻了网络负担。但是, 文件更改的灵活性需要更多的计算量, 因为该算法必须首先找出如何拆分块。

识别冗余块是基于以下假设:具有相同哈希值的数据块包含相同信息。要过滤掉冗余块, 重复数据删除算法只需要将新计算的哈希值与跟踪数据库同步即可。如果找到相同的校验和, 则通过使用指针标识相同数据块的存储位置来替换冗余块。这样的指针所占空间比数据块本身少得多。文件中可以用占位符替换的块越多, 所需的内存空间就越少。然而数据缩减效率重复数据删除算法无法预测, 因为这很大程度上取决于输出文件及其数据结构。此外, 重复数据删除仅适用于未加密的数据。加密系统有意避免冗余。这使得不可能进行任何模式识别。

重复数据删除既可以在存储目标中也可以在数据源中进行。

源重复数据删除

如果冗余数据在传输到存储目标之前被删除, 则称为源重复数据删除。在这种情况下, 重复数据删除引擎为集成到备份软件中。冗余信息直接在数据源的文件系统中消除。为此, 备份软件会定期扫描新创建的数据块, 并将它们与备份服务器上已保存的数据块进行比较。如果找到了冗余数据块, 则在下一个备份过程中将跳过该数据块。如果文件被修改, 则备份软件仅传输文件的新部分。

这些重复数据删除方法的主要优点是, 只有新信息才作为数据备份的一部分传输到备份服务器。这样可以减少带宽使用以及存储目标的必要容量。但是, 与在存储目标处进行重复数据删除不同, 基于源的方法需要大量的计算工作, 因此它不适用于每种情况。

目标重复数据删除

目标重复数据删除是指数据缩减过程在数据源之外进行。重复数据删除引擎或者集成在硬件阵列中, 或者作为上游集成在独立设备。在这两种情况下, 目标重复数据删除都会减少所需的存储容量, 但是与源重复数据删除不同, 目标重复数据删除不会影响从源系统通过LAN或WAN备份到存储目标的备份过程中传输的数据量。根据为目标重复数据删除选择哪种结构, 可以选择两种类型的目标重复数据删除:后处理重复数据删除和内联重复数据删除.

  • 后处理重复数据删除:如果重复数据删除引擎集成在阵列中, 则备份数据的非操纵版本将首先保存在存储设备上, 然后再进行重复数据删除。这称为后处理重复数据删除。这种重复数据删除的优点是可以相对快速地将数据传输到存储目标。但是, 数据在传输后无法立即获得, 因为必须先完成备份过程, 然后才能消除冗余。在将硬盘驱动器上的数据用于复制或检索之前, 需要对其进行三遍寻址。这会增加内存系统的工作量。此外, 备份系统必须首先提供两个单独的存储区:一个用于输出数据, 另一个用于重复数据删除的数据。与内联重复数据删除相比, 这需要更多的物理内存。但是, 相比之下, 后处理重复数据删除可基于可变数据块实现更有效的数据缩减。
  • 内联重复数据删除:如果重复数据删除引擎位于存储介质之前, 则有可能在传输过程中直接删除冗余数据, 甚至无需将其写入存储介质。这会降低写入的吞吐量, 并限制具有固定大小的数据块上的重复数据删除。但是, 与后处理重复数据删除相比, 它还大大减少了目标系统上必需的物理内存量。此外, 已在线进行重复数据删除的数据将立即可用;例如, 用于数据恢复或复制。

资料压缩

在数据压缩中, 文件被转换为替代格式, 该格式比原始格式更有效。此过程的目的是减少所需的存储空间以及传输时间。一种编码增益这样可以通过两种不同的方法来实现:

  • 冗余压缩:在基于冗余减少的无损压缩的情况下, 可以在压缩后精确地对数据进行解压缩。因此, 输入和输出数据是相同的。仅当文件包含冗余信息时, 才可以进行这种压缩。
  • 不相关压缩:在有损压缩的情况下, 删除不相关的信息以压缩文件。这总是伴随着数据丢失。在不相关的压缩之后, 原始数据只能大致恢复。分类为不相关的数据是任意的。例如, 在通过MP3进行的音频压缩中, 删除的频率模式是假定为人类几乎听不到或根本听不到的那些。

虽然存储系统级别的压缩基本上是无损失的, 但故意减少其他区域的数据丢失, 例如图像, 视频和音频传输, 以减小文件大小。

编码和解码都需要计算量。这主要取决于所使用的压缩方法。尽管某些技术旨在用于最紧凑地表示输出数据, 但其他技术则专注于减少所需的计算时间。因此, 压缩方法的选择始终取决于应用程序的要求。

例如, 在实时视频或声音传输的情况下, 建议使用最快的压缩方法和数据恢复。在这种情况下, 较低的编码增益和可能的质量损失是合理的。通过文件服务器将文件提供给大量用户的情况则不同。在此, 可以忍受更多的压缩时间, 因此可以使用功能强大的压缩算法。这允许高编码增益而不会损失质量。

无损数据压缩

重复数据删除算法在不同文件中搜索相同的数据段, 并用链接的占位符替换冗余数据段, 而无损数据压缩方法则与表示法一起使用。在这种情况下, 在一个文件中重复多次的节将替换为更短的表示。

在下面的示例中显示:

源文本:ABCDEABCEEABCEE

编码:ABC = 1; EE = 2

压缩文字:1DE1212

使用此编码, 可以将长度为15个字符的源文本缩短为7个字符。编码增益达到50%以上。但是, 进行这种压缩的前提是编码和解码系统都可以识别编码。

大多数无损方法在单个文件中重复字符或字符组合。已知的基于重复的压缩方法包括单词编码和Lempel-Ziv方法(LZ77)。

  • 文字编码:基于文字编码的压缩方法最适合文本文件。这里的基本原理是用较短的表示替换单词。为此, 首先创建一个列表, 然后为文件中的每个单词分配一个值。然后可以将整个文本转换为数字。

源文本:生存还是毁灭

编码:至= 1;是= 2;或= 3;不= 4

压缩文字:123412

由于在这种压缩方法中, 除了有效载荷数据之外, 还必须保存单词列表, 因此单词编码对于具有许多重复的较长文本最有效。

  • Lempel-Ziv方法:Lempel-Ziv方法是一种基于字典的方法, 可以基于冗余来压缩字符串。为此, 压缩算法使用的内容像字典一样被读取, 因此不必单独存储。在读取的数据流中对相同字符串的引用由所谓的三元组执行, 该三元组对要复制的部分和第一个非一致字符的位置和长度进行编码。匹配由搜索缓冲区和预览缓冲区执行。如果一个字符不匹配, 则三元组为(0, 0, x), 其中x为对应的字符。以下示例显示了单词BANANA的LZ77编码:
Lempel-Ziv方法

将预览缓冲区中的字符或字符串与已经读取的搜索缓冲区字符进行比较。如果找到匹配项, 则在预览缓冲区中将相应的字符替换为引用三元组。

在第4行中, 字符ANA被三元组(2、3, $)替换, 这意味着:

2 =将当前字符串替换为搜索缓冲区(A)中位置2之后的字符串。

3 =替换字符串长3个字符。因为它比包含字符A和N的其余搜索缓冲区长, 所以将重复替换字符串(A, N, 并再次是A)。

$ =替换后不再有字符, 压缩完成。

由于使用LZ77可以有效地压缩大多数数据, 因此该算法的后继者(例如LZSS)现在得到了广泛使用, 包括zip文件格式, PNG图像和PDF。

除了基于重复的方法之外, 诸如游程长度编码或霍夫曼编码的基于频率的方法也用于无损压缩。

  • 游程长度编码:游程长度编码针对的是由相同字符序列导致的冗余。这由黑白图形的单个图像线的示意图表示。

初始数据:WWWWWBBBBWWBBWWWWWWBBBBBBBBWWW

重复的字符将明显减少要保存的数据, 这些重复的字符被记录为字符对的值对和重复次数。

压缩数据:5W4B2W2B6W6B3W

游程长度编码用于图像压缩, 但是由于需要编码更多的颜色状态而降低了效率。虽然可以使用两种颜色状态创建黑白轮廓, 但对于8位灰度图像, 则需要256种灰度。因此, 在具有细微颜色渐变的复杂图像中, 两个以上连续像素具有相同颜色值的可能性将大大降低。由于示例中的编码基于两位数字值对, 因此仅当序列中至少有两个相同的字符彼此跟随时才出现编码增益。游程长度编码的一种修改形式是已知JPEG图像压缩方法的一部分。

  • 霍夫曼编码:在数据压缩期间, 霍夫曼编码首先确定文件中出现的所有字符的频率。在下一步中, 将字符转换为位序列, 其中表示的长度由频率确定。在图形上, 霍夫曼编码表示为一棵树, 编码的字符形成叶子。例句"这是霍夫曼树的一个例​​子"证明了这一点。
性格 空间 一种 Ë F H 一世 ñ s Ť Ø p [R ü X
频率 7 4 4 3 2 2 2 2 2 2 1 1 1 1 1 1

字符的相应二进制编码来自从根到叶的路径。在此, 0表示向左分支, 而1表示向右分支。

霍夫曼编码

来源:https://en.wikipedia.org/wiki/Huffman_coding#/media/File:Huffman_tree_2.svg /公共领域

以下代码可用于例句中的字符:

空间 一种 Ë F H 一世 ñ
111 10   1101 1010 1000 111 10
s Ť Ø p [R ü X
1011 110 11001 110 10011 11000 111 10010

而经常出现的字符如空间, 一种和Ë在此示例中仅使用3位编码, 较少使用的字符例如[R, ü和X需要5位。相比之下, 例如, ASCII字符集每个字符使用7位。但是, 在诸如UTF-8或ISO 8859-1(Latin-1)之类的与ASCII兼容的字符集中, 现代计算机通常添加八位, 可以使用8、16、32或64位。这表明使用霍夫曼编码可以更紧凑地保存文本。

以下二进制序列显示了根据霍夫曼编码的例句"这是霍夫曼树的一个例​​子":

0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000

相比之下, 以下是根据ASCII编码的相同内容的位序列, 其中增加了第八位(分别是第一个零):

01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 011001 01101110110100100

使用霍夫曼编码, 根据字符频率的分布, 数据最多可减少至其原始大小的1/3。用户应注意, 但是, 必须为所有后续解码保存该树。

霍夫曼编码还有其他用途压缩文本文件但是;该方法也可以在JPEG格式图像压缩过程和压缩格式这是LZSS和Huffman的组合。

有损压缩

虽然只有在文件中找到冗余时才可以进行无损数据压缩, 但有损数据压缩是基于不相关减少, 始终是可能的-如果接受数据丢失。作为基本原理, 容易丢失的数据压缩总是由决定原始数据的哪一部分是可分配的决定。最大压缩的理论极限可以用速率失真理论, 它描述了压缩和信号质量之间的关系。

有损压缩方法通常适用于人类的感知。例如, 在音频文件(即, MP3, AAC或WMA)的压缩期间, 位于人类听觉范围之外的频率分量被删除。图像扇区中不相关性减少的一个常见示例是JPEG方法, 该方法结合了无损和有损压缩方法。后者包括, 例如颜色转换RGB光谱到YCbCr颜色模型中, 离散余弦变换(DCT), 以及量化.

重复数据删除和数据压缩:比较

公司通常使用重复数据删除技术来执行备份过程或优化标准文件系统中的存储方法。这是因为如果要存储相同的文件, 重复数据删除系统将非常有效地工作。

另一方面, 数据压缩方法通常会导致更高的计算量, 从而需要更加复杂的平台。存储系统在两种数据缩减方法的组合。通过重复数据删除, 首先从要保存的文件中删除冗余, 然后压缩剩余的数据。

一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: