Lecture #13 & #14

数据压缩

调查 - 您最大的两个存储难点是什么？

管理存储增长排第一

存储效率策略和最佳实践

不要存储太多
把数据存放在正确的位置

一系列基本技术可实现存储效率

停止存储这么多

• 数据压缩
• 重复数据删除
  §将数据移动到正确的位置
• 自动数据迁移

压缩和重复数据删除使用较少的物理存储，这两者是不冲突的

§更有效地存储数据
§降低运营费用：电力，冷却，占地面积§在线保存更多数据，以便进行分析和快速恢复

数据压缩

§数据压缩对存储系统很重要，因为它允许将更多字节打包到给定的存储介质中，反过来说就是用更少的字节来表达相同的信息量。
§某些存储设备（特别是磁带）会在写入时自动压缩数据，从而减少磁带消耗并显着加快备份操作。
§压缩还可以缩短文件传输时间，节省时间和通信带宽

介绍

§压缩的一个好指标是由下式给出的压缩因子（或压缩比）：

§如果我们有一个100KB的文件压缩到40KB，我们的压缩系数为：

§整个消息的熵是各个符号熵的总和
Σn-P（xi）×log2 P（xi）i
§长度为l的消息中每个字符的平均冗余度由下式给出
P（xi）×li - -P（xi）×log2 P（xi）ΣnΣn

统计编码

§考虑一下这个信息：HELLO WORLD！

• 字母L的概率为3/12 = 1/4
  信息。 编码此符号所需的位数为：2
  §使用公式平均熵是3.022
• 这意味着每个字符的理论最小位数为3.022
  §理论上，消息只能使用37位发送 - 3.022×12 = 36.264

§刚才描述的熵度量是统计数据压缩的基础
§两种广泛使用的统计编码算法是霍夫曼编码和算术编码
§Huffman编码根据消息中的字母频率构建二叉树

• 直接从树中读取每个字符的二进制符号§具有最高频率的符号最终位于树的顶部
  树，并导致最短的代码

构建树的过程首先计算要编码的文本中每个符号的出现次数，出现频率最低的是在二叉树中最深的。这样频率最高的编码最短。

§对于大多数数据，统计编码方法提供了出色的压缩比
§它们的主要缺点是它们需要对要编码的数据进行两次传递

• 第一遍计算概率，第二遍编码消息
  §对于存储系统而言，这种方法速度慢得令人无法接受，因为存储系统必须在文件中一次读取，写入和压缩数据

LZ字典系统

Ziv-Lempel（LZ）字典系统通过使用数据中的值作为字典对自身进行编码来解决双遍问题
§LZ77压缩算法采用文本窗口和前瞻缓冲区

• 文本窗口用作字典。 如果在先行缓冲区中找到与字典中的文本匹配的文本，则输出窗口中文本的起始位置和长度

数据压缩摘要

§数据压缩的两种方法是统计数据压缩和字典系统
§统计编码需要两次输入，字典系统只需要一次
§LZ77和LZ78是两种流行的字典系统

数据重复删除Deduplication

§通常称为单实例存储
§在重复数据删除过程中，删除重复数据，只留下一个要存储的数据副本

• 重复数据删除将传入数据转换为段，唯一标识数据段，并将这些段与已存储的数据进行比较
• 如果传入的数据是新的，那么它存储在磁盘上，但是如果它与已存储的数据重复，那么它不会再次存储，并且会为其创建一个引用
  §“实际上只有一个唯一的数据实例保留在存储介质上，例如磁盘或磁带。 冗余数据被替换为指向唯一数据副本的指针。“

Deduplication 架构

有很多层次来做
deduplication，各有利弊。
客户端

• 减少服务器上的负载
• 减少带宽
• 向客户端添加负载
• 多个客户端之间没有交叉关联

服务端

• 可以有多个客户端的关联
• 增加了服务端的负载，每个客户端把数据送到服务端

§块存储设备

• 对客户和服务器透明
• 减少服务器和客户端的负载
• 向存储设备添加负载
• 没有文件或格式意识

重复数据删除过程（简化）

§假设数据对象或-Stream作为重复数据删除的主题
§数据对象以chunk块为单位（固定或可变大小）
§对于每个Chunk，确定身份特征
§识别出重复的块

• 使用指针引用相同的块，引用。
• 有效存储不同的块或单个实例
• 可以另外执行压缩
  所需的磁盘缓存减少了

数据块方法

§基于文件

• 一个块是一个文件，最适合文件系统
  §固定块
• 数据对象被拆分为固定块
• 由块存储设备使用
  §格式识别逻辑上
• 根据需要了解显式数据格式和块数据对象格式。 示例：将ppt分成单独的幻灯片
  §格式不可知
• Chunking基于在数据对象中查找逻辑中断或类似元素的算法

分块方法影响重复数据删除率

确定重复的方法

§哈希

• 为每个数据块计算哈希值（MD-5，SHA-256）
• 将哈希值与现有数据的所有哈希值进行比较
• 相同的哈希意味着最可能相同的数据
• 哈希冲突的潜在（小）风险：相同的哈希和非相同数据
• 必须通过二次比较（附加元数据，第二个哈希方法，二进制比较）来防止

§二元比较

• 比较相似块的所有位

in-Line重复数据删除

§数据在实际存储之前进行重复数据删除，而不是在数据产生之前就进行deduplation
§重复数据删除是在数据流入辅助数据时执行的存储系统
§ 好处

• 处理数据一次，消除额外的后处理任务
• §缺点
• CPU密集型重复数据删除过程可能会产生性能瓶颈
• 每个I / O流一个进程

out-Band重复数据删除（后处理）

§数据首先在后台存储和重复数据删除
§ 好处

• 重复数据删除CPU开销不再影响备份窗口
• 支持多个I / O流
• 第一版（或非重复数据删除）的恢复速度可能更快
  §缺点
• 数据被写入，读取和写入 - 因此I / O密集程度更高
• 重复数据删除窗口必须与备份窗口协调，因为它通常比内联处理更长
• 需要更大的辅助存储，因为第一个版本未进行重复数据删除

重复数据删除摘要

§潜在的优势

• 减少给定数据量所需的存储容量
• 能够在给定数量的磁盘上存储更多数据
• 节省网络带宽（客户端重复数据删除）
• 降低存储需求，降低存储管理和能源成本
  §潜在的权衡/限制
• 重复数据删除处理所需的大量CPU和I / O资源
• 增加了对介质故障的敏感性，因为许多文件可能会因丢失公共块而受到影响
• 重复数据删除可能不适合磁带上的数据，因为增加的数据碎片可能会大大增加访问时间