云存储与重删调研

Fast’2023

InftyDedup: Scalable and Cost-Effective Cloud Tiering with Deduplication 云与数据去重

• Cloud tiering是一种数据存储策略，它将数据分为不同的存储层级，并根据组织的需求在这些层级之间进行数据迁移，将频繁访问的数据存储在快速的云存储中，将较少使用的数据存储在较慢、更便宜的存储中。
• 云分层是将选定的数据从本地存储移动到云的过程，这一点最近对备份解决方案变得很重要。由于后续备份通常包含重复数据，因此云分层中的重复数据消除可以显著降低云存储利用率，从而降低成本。
• InftyDedup 带有去重的云分层系统, 不仅用于云服务也用于计算，最大限度地提高可扩展性，使用带动态分配云计算资源地分布式批处理方法，可以从多个源消除PB级重复数据；此外，系统还根据每个块的特性选择冷热数据

Fast’22

DedupSearch: Two-Phase Deduplication Aware Keyword Search 大型存储库与数据去重

• Dedup专注于在大型存储库中搜索关键字(字符串),传统搜索技术需要遍历整个文件树并读取数据块，以找到哪些被引用了;
• DedupSearch使用了两阶段的算法
  • 物理阶段：顺序扫描存储并处理每个chunk一次，在临时结果数据库中记录关键字的匹配情况
  • 逻辑阶段：在逻辑顺序上遍历文件系统的元数据，将块内匹配归因到对应文件
  • 难点是解决如何识别被相邻块分开的关键字，为了解决这一点，物理阶段会记录关键词浅醉和chunk边界的后缀，并在逻辑阶段文件元数据处理时做子串的匹配。

DeepSketch: A New Machine Learning-Based Reference Search Technique for Post-Deduplication Delta Compression 机器学习、增量压缩、数据去重

• 增量压缩更高效，因为即使对于非数据数据和高熵数据，也可以通过利用块内数据的相似性减少数据，但是现有的增量压缩后去重技术由于识别重复数据块的能力有限，导致压缩率低。
• DeepSketch，新的用于增量压缩后去的引用搜索技术，使用了learning-to-hash的方法以达到搜索准确率；
• DeepSketch, 使用DNN来提取数据块的草图(sketch)，草图是数据块的近似数据签名并且保持有与其他数据块的相似性

The what, The from, and The to: The Migration Games in Deduplicated Systems 去重系统的迁移问题

• 去重的引入增加了文件间的相关依赖, 使系统中的数据迁移复杂化
• 文章将一般的迁移问题建模为最优化问题，最小化系统大小；文章提出了三种方法以平衡计算实践和迁移效率，贪婪算法、理论最优算法和聚类算法

Fast’21

The Dilemma between Deduplication and Locality: Can Both be Achieved? 去重中局部性破坏和碎片化问题的应对

• 数据去重会破坏数据的局部性，还会导致数据碎片化，降低修复和GC的性能，现有研究通过写副本以保持局部性，但是碎片化问题尚未解决
• MFDedup：管理友好的去重框架，通过使用数据分类方法来生成最佳数据布局，从而维护备份工作负载的局部性
• 两个关键技术：聚焦邻居重复的索引NDF、跨版本感知重组方案AVAR，系统针对先前版本执行重复数据检测，再通过离线的迭代算法重组chunk成紧凑、连续的布局

ATC’23

Light-Dedup: A Light-weight Inline Deduplication Framework for Non-Volatile Memory File Systems 用于NVM文件系统的轻量级文件去重

• 重复数据删除可以降低NVM的成本, 现有设计缺乏对NVM IO机制的深入理解
• Light-dedup：用于NVM文件系统的轻量级的内联去重框架，有着快速的块级去重速度
• 关键技术：轻量级冗余块识别器LRBI，结合了非加密哈希的基于推测预取的逐字节比对方法；NVM内部的轻量级元数据表LMT，用于记录去重的元数据并于LRBI协同工作，LMT按区域粒度组织以降低IO元数据放大

TiDedup: A New Distributed Deduplication Architecture for Ceph 用于Ceph的分布式数据去重架构

• TiDedup:用于Ceph的集群级去重框架
  • Ceph的缺陷：(1)对唯一数据的去重会消耗过多元数据;(2)序列化分层对前台IO不利,且只提供了固定大小分块;(3)引用计数机制需要对对象进行低效的扫描，且无法于快照配合使用
  • TiDedup的改进：
    • 选择性的集群抓取:事件驱动的分层机制，使用基于内容的分块和引用修正方法

LoopDelta: Embedding Locality-aware Opportunistic Delta Compression in Inline Deduplication for Highly Efficient Data Reduction 增量压缩与数据去重

• 增量压缩通过数据块间的相似性，可以压缩没有重复数据的数据块以减小文件容量，但是现有的用于备份存储的去重后增量压缩计数方法，存在低相似性或没有潜在的相似块，也有由于备份系统读取基本块导致的额外IO开销、服务终端操作导致的低吞吐率
• loopDelta：非侵入式的内联增强的增量压缩模式的重复数据删除框架，增强的增量压缩包括了：
  • 双局部性相似块检测：基于逻辑局部性和物理局部性的相似块检测
  • 局部性感知：预取基本块以避免额外的IO开销
  • cache感知的过滤器：用于再基本块的读路劲上避免额外IO
  • 反向delta压缩：通过旨在提高恢复性能的重写技术，对原本禁止用作基本块的数据块做增量压缩

ATC’22

Building a High-performance Fine-grained Deduplication Framework for Backup Storage with High Deduplication Ratio 增量压缩与数据去重

• 细粒度的重复数据消除首先需要去除相同的块，然后消除相似却不相同的块之间的数据冗余(增量压缩)，这可以利用工作负载的可压缩性实现很高的去重率，但是这回导致较差的备份和恢复表现，这使得不如块级去重受欢迎。这是因为块级重复数据删除可以允许负载在相似块间共享更多的引用，降低空间和时间局部性，从而降低了恢复性能并增加更多的开销。
• MeGA：保留高去重率的同时备份和恢复开销接近块级去重，关键技术如下:
  • 面向工作负载的增量选择器，用于在读基本块时定位差局部性
  • 增量友好的数据布局和始终先前的引用，用以处理去重后的较差的时空局部性