[ATC' 20] Austere Flash Caching with Deduplication and Compression
作者： Qiuping Wang, Jinhong Li, Wen Xia, Erik Kruus, Biplob Debnath, and Patrick P. C. Lee
论文概要
Abstract
Introduction
现代的数据密集型计算，要求高I/O性能。因此许多研究都提出将SSD作为HDD的缓存层。
SSD的优点xxx（不再赘述），但是写耐久性差。因此为了支持高性能的工作负载，缓存尽可能多的对象，同时减少对ssd的写操作以避免损耗，这是一个至关重要的问题。
数据重删和数据压缩技术减少了I/O路径上的重复内容，因此减少了存储和I/O开销。这两项技术针对的是不同的数据粒度：
数据重删：消除了粗粒度（chunk-level）的重复数据，管理开销较小数据压缩：消除了chunk内byte-level的重复。
这两项技术可以相互补充。
然而现存的数据去重技术存在很大的memory overhead，本文主要关注logical-to-physical address mapping，主要有如下三种索引开销：
重删之后，每个逻辑地址到flash缓存中非重复的物理地址的映射；
用于重复数据删除检查的闪存缓存中所有存储块的加密哈希(也称为指纹)
所有大小可变的压缩块的长度
为了获得高性能，最好将所有这些索引元数据保存在内存中，但与传统的flash缓存相比，这样做会增加内存开销。额外的内存开销，我们称之为内存放大，可以达到至少16倍。
本文中我们，我们提出了AustereCache，一种内存高效的闪存缓存设计，采用重复数据删除和压缩存储和I/O节省，同时在类似的设计中大幅降低索引结构的内存开销。AustereCache提倡对数据布局和缓存替换策略进行严格的缓存管理，以限制重复数据删除和压缩导致的内存放大。它建立在三个核心技术之上：
bucketization：通过将chunk确定性地映射到固定大小的bucket，以实现轻量级的地址映射；
fixed-size compressed data management：它通过将可变大小的压缩块组织为固定大小的子块来避免跟踪内存中的块长度;
bucket-based cache replacement：它在每个桶的基础上执行内存高效的缓存替换，并利用一个紧凑的概要数据结构来跟踪有限内存空间中的重复数据删除和最近模式，以便做出缓存替换决策。
Background
Deduplication and Compression
Deduplication
本文关注基于chunk的重复数据删除，它将数据划分为不重叠的数据单元，称为chunk(大小为KiB)。每个chunk用一个指纹（fingerprint, FP）来唯一标识，指纹根据chunk的内容，用加密算法（如 SHA-1）计算得到。如果两个chunk的指纹是一样的，我们就认为这两个chunk是重复的。因为hash冲突的概率特别小，可以忽略不计。重复的chunk在物理介质上只存储一份，但是所有的逻辑chunk都通过一个small size的指针索引到指纹上。同时，通过一个索引结构将所有的FP索引到一个物理空间上，用于duplicate checking和chunk lookup。
块大小可以是固定的，也可以是可变的。虽然基于内容的可变大小分块通常可以实现高的重复数据删除节省，因为它对content shifts的鲁棒性，但它也会带来高计算开销。另一方面，固定大小的块更适合闪存单元。因此，这项工作侧重于固定大小的分块。
Compression
数据重删在块级提供粗粒度的数据缩减，而压缩则通过将数据转换为更紧凑的形式，在字节级实现细粒度的数据缩减。压缩通常应用于重复数据删除后的唯一chunk，而压缩后的输出chunk通常是可变大小的。为了提高性能，我们应用顺序压缩(例如，Ziv-Lempel算法)，它在one pass中对每个块的字节进行操作。
FLash Caching
我们专注于建立一个基于SSD的闪存缓存，通过将经常访问的数据存储在闪存缓存中，来提高基于HDD的主存储的I/O性能。闪存缓存已经被广泛研究，并在不同的存储架构中被采用。现有的闪存缓存设计，我们统称为传统的闪存缓存，大多支持写穿（write-through）和写回（write-back）两种策略，分别用于读密集型和写密集型工作负载；由于SSD的持久性，在Flash cache上使用回写策略是可行的。对于写穿，每个写在完成之前都会被持久化到SSD和HDD上；对于写回，每个写在被持久化到SSD上之后就会完成。为了支持这两种策略，传统的flash caching需要一个SSD-HDD转换层，将HDD中的每个逻辑块地址（LBA）映射到Flash Cache中的一个chunk地址（CA）。
一般都会维护一个两级的映射表，LBA->FP（n对1）以及FP->(CA,len)。对于读写流程：
写流程：首先将数据分成固定大小的chunk，然后计算指纹检查是否是重复写。如果不是重复写，就将chunk进行压缩，压缩后的数据写入SSD，并更新两级的地址映射。如果是写穿策略，就在HDD中也写入未压缩的chunk。
读流程：查询两级映射表看是否命中。命中就从SSD读取数据，并解压缩；未命中就从HDD中读取数据，并在SSD中进行压缩和写入（更新映射表）。
Memory Amplification
虽然重复数据删除和压缩通过消除I/O路径上的冗余内容，直观地降低了闪存缓存的存储和I/O成本，但这两种技术都不可避免地在其索引管理中产生了巨大的内存成本。具体来说，如果两个索引结构都完全存储在内存中以获得高性能，那么内存的使用量是很大的，比传统的闪存缓存要高得多；我们把这样的问题称为内存放大（比传统的闪存缓存），这可能会否定重复数据删除和压缩的数据减少的好处。
这里举了个简单例子来分析读放大：
512GB SSD + 4TB HDD，都是64位寻址。
重删的chunk size是32KB，使用SHA-1计算指纹（也就是20字节），使用4字节来存储压缩后的chunk长度。
在最坏的情况下：
(LBA, FP)映射需要 个，每个8字节的LBA + 20Byte的FP，一共3.5GB的空间。
(FP, CA)映射需要 个，每个需要20字节的FP、8字节的CA和4字节的长度，一共512MB
因此LBA索引和FP索引一共需要4GB的空间。而传统的SSD只需要个（LBA，CA），也就是256MB的空间。因此重删和压缩带来了16倍的读放大。如果我们使用一个更耐碰撞的哈希函数，内存放大率甚至更高；例如，如果每个FP是由SHA-256（32字节）形成的，则变成22.75。请注意，我们的分析没有考虑重复数据删除和压缩的其他元数据（例如，重复数据删除的参考计数），这比传统的闪存缓存进一步加剧了内存放大的情况。
除了内存放大之外，重删和压缩还带来了CPU开销。这主要来自于：
chunk的指纹计算
chunk的压缩
LBA索引和FP索引的查询开销
State-of-the-Art Flash Caches
我们回顾了两个最先进的闪存缓存设计，Nitro和CacheDedup，它们都支持重复数据删除和压缩。我们认为，这两种设计仍然容易受到内存放大的影响。
Nitro
Nitro是第一个部署了重复数据删除和压缩的闪存缓存。为了管理可变大小的压缩块（又称extents），Nitro将它们打包在被称为 "Write-Evict-Unit"（WEU）的大型数据单元中，作为缓存替换的基本单位。WEU的大小被设定为与闪存擦除块的大小一致，以便有效地进行垃圾收集。当缓存已满时，Nitro根据最近最少使用（LRU）的策略驱逐一个WEU。它在DRAM中管理索引结构（或NVRAM，以提供持久性）以跟踪WEU中的所有chunks。如果内存容量有限，Nitro会在内存中存储部分FP-索引，其代价是重复数据删除可能会错过检测和删除一些重复的数据。
除了内存放大问题，WEU组织块可能会导致WEU包含陈旧的chunk，这些chunk不会被LBA-index中的任何LBA引用，因为它们的原始LBA可能已经被更新。如果它们所在的WEU也包含其他最近被访问的有效chunk，由于LRU策略，这种陈旧的chunk不能被立即回收，而是占据了缓存空间，降低了缓存命中率。
CacheDedup
CacheDedup专注于减少orphaned entries数量的缓存替换算法，orphaned entries指的是在LBA-索引中但在FP-索引中没有相应的FP的LBA，或者是在FP-索引中但没有被任何LBA引用的FP。它提出了两个重复数据删除感知的缓存替换策略，即D-LRU和D-ARC，它们分别增强了LRU和自适应缓存替换（ARC）策略。
它还提出了一个D-ARC的压缩功能的变种，叫做CD-ARC，它像Nitro一样在WEU中管理可变大小的压缩块；注意，CD-ARC也存在上述的stale-chunk问题。CacheDedup维护的索引结构与前面所讲的相同，其中LBA-索引存储LBA到FP，FP-索引存储FP到CA和压缩块的长度。如果出于性能考虑，它将LBA-索引和FP-索引都保存在内存中，那么它仍然会受到同样的内存放大问题的影响。一项后续工作CDAC通过加入引用计数和访问模式，改进了CacheDedup的缓存替换，但由于维护额外的信息而产生了更高的内存开销。
Evaluation
Related Work
Discussion
我的思考
Last updated
Was this helpful?