论文学习：Austere Flash Caching with Deduplication and Compression
论文题目 ：Austere Flash Caching with Deduplication and Compression
来源：USENIX ATC 2020
链接：https://www.usenix.org/conference/atc20/presentation/wang-qiuping
关键概念
deduplication（去重）
重复数据删除以粗粒度但轻量级的方式删除块级重复数据。通过将数据划分成一个个chunk（KB级别），对每个chunk的内容做hash，若算出的hash值（fingerprint，FP）一样（不同），则视为冗余（唯一）数据。通过在物理空间上（SSD上）只保存一份冗余数据的副本，从而进行数据缩减，但在逻辑空间上，所有冗余数据不会被删除，而是都指向同一块物理地址。此外还会将每个chunk和其FP的映射存储下来，用于重复检查和chunk查找。块（chunk）的大小可能是固定也可能是变化的，本文主要关注去重固定大小的块。
compression（压缩）
压缩通过将数据转换为更紧凑的形式，旨在字节级进行细粒度的数据减少。压缩通常在去重后进行，一般应用于那些唯一数据块。压缩后的数据块大小一般是可变的。本文使用顺序压缩算法(例如Ziv-Lempel算法)，对每个块的字节进行操作。
deduplication&compression是两种data eduction技术，相辅相成。
flash
flash存储器又称闪存，它结合了ROM和RAM的长处，不仅具备电子可擦除可编程（EEPROM）的性能，还可以快速读取数据（NVRAM的优势），使数据不会因为断电而丢失。固态硬盘和传统的机械硬盘最大的区别就是不再采用盘片进行数据存储，而采用存储芯片进行数据存储。固态硬盘的存储芯片主要分为两种：一种是采用闪存作为存储介质的；另一种是采用DRAM作为存储介质的。目前使用较多的主要是采用闪存作为存储介质的固态硬盘
flashcache
Flashcache是Facebook技术团队的一个开源项目，最初目的是为加速MySQL的数据库引擎InnoDB，是一个开源的混合存储方案，兼顾了机械硬盘和固态硬盘两者的优点，即有HHD的高容量、高顺序访问，也有SSD的高随机访问，低延迟，且这个方案成本也相对较低。Flashcache利用了Linux的device mapping机制，将Flash disk和普通硬盘的块设备做了一层映射，在OS中变现为一块普通的磁盘，使用简单。通过在文件系统和设备驱动之间新增了一层缓存层，用来实现对热点数据的缓存。通常用SSD固态硬盘作为缓存，通过将传统硬盘上的热门数据缓存到SSD上，然后利用SSD优秀的读性能，来加速系统。参考https://my.oschina.net/u/658505/blog/544599
上图是一般的带有去重和压缩功能的flashcache架构。带有去重和压缩功能的flashcache保证SSD中的数据块都是唯一且压缩过的。而传统的flashcache不带有去重和压缩功能，因此只用维护一种索引结构：LBA->CA。经过假设计算后，带有去重和压缩的flashcache由于要维护两个index（LBA-index、FP-index），其内存开销要是传统的flashcache的16倍（4G/256MB）。此外还可能产生额外的CPU开销（计算FP、压缩数据、寻找索引对等）
LBA-index：LBA->FP
逻辑地址索引，即将存于HDD中的数据的逻辑地址（LBA）与数据块的FP值进行映射（多对一，可能有多个不同的逻辑地址指向相同内容的数据）
FP-index：FP->CA,length
FP索引，即将每个数据块的FP值与该数据块经过压缩后位于SSD中的物理地址（CA）以及该块的大小进行映射（一对一）
Write-through（直写模式）
在数据更新时，同时写入缓存Cache和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢
Write-back（回写模式）
在数据更新时只写入缓存Cache。只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快，因为不需要写存储；缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况，数据将无法找回。
解决问题
目前SSD被广泛用作RAM和HDD之间的一个缓存层（即flashcache技术，通过将热点数据存储在SSD，可以提高整体I/O性能），但其使用寿命和容量都有限。为了解决这一问题，本文提出一种框架AustereCache，其拥有高效的数据去重和压缩机制，能够尽可能的延长SSD寿命和扩大其容量，而且也能很好的降低由于数据压缩/去重导致的索引管理所带来的巨大内存开销。这相比于目前最新的flashcache框架CacheDedup所需的内存代价要低69.9-97.0%，且能提供相似的性能。
核心技术
AustereCache强调严格的cache数据管理，使用多种技术来进行有效的数据组织和cache数据替换，主要包括三个核心技术点：
bucketization（桶化）
如下图所示，为了消除在LBA-index和FP-index中维护地址映射的内存开销，AustereCache将索引项散列到大小相等的分区(称为桶，每个桶分为多个槽)中，每个桶保存部分LBA和FP（通过hash后取其前缀码，如前16bit）以节省内存。根据桶位置，将数据块映射到SSD中。并将SSD分为元数据区(metadata)和数据区(chunk data)，这两个区也都被分为多个桶，每个桶包含多个槽(slot)，数量与FP-index保持一致（1对1映射）。
固定大小的压缩数据管理
为了避免在FP-index中跟踪块的长度，AustereCache将可变大小的压缩块划分为较小的固定大小的子块，并在不记录压缩块长度的情况下管理子块。如下图所示，在FP-index中会选取多个连续的槽来存放属于同一个压缩块的子块，并且不会在FP-index中记录压缩块的大小，而是在SSD中记录压缩块的大小，从而减小FP-index大小，减小内存开销。这样做既可以很好的使用桶—槽（bucket—slot）机制来管理每个数据块（将大小变化的压缩块分为多个固定大小的子块），也可以节省内存开销。
基于bucket的缓存替换
AustereCache为了增加缓存命中的可能性，其结合了基于引用计数（即引用每个唯一块的重复副本的计数）的最近性和去重性原则，以实现有效的SSD缓存数据替换。但是，记录引用计数会产生不可忽略的内存开销。因此，AustereCache利用固定大小的紧凑型草图数据结构在有限的内存空间中使用有限的误差进行参考计数估计。
对于LBA-index，其替换策略为LRU，每当新加入或者新访问一个LBA就会将这个LBA移动到最前面（偏移量为0），其余所有entry往后移动一格，处于最后一个的entry（偏移量最大）会被替换掉。
对于FP-index，其替换策略是要将去重（deduplication）和最近访问性（recency，相当于局部性原理）结合起来，通过一个额外的数据结构：引用计数（count）来表明冗余LBA的程度，当FP-index满后，会替换掉count最小的entry来满足去重性。此外还通过将LBA-index分为Recent、Old两个区，位于Recent区中的entry，每次被访问，或者新加入的entry，其count+2；当从Recent进入Old，或者在Old中被替换掉的entry，其count-1；当Old中的entry被访问进入Recent区，其count+1。通过这种规则既兼顾了去重也兼顾了局部性原理。
性能评估
数据集
①FIU从三种不同设备上采集到的traces（I/O访问序列？），分别是Web服务器上的虚拟机、文件服务器、邮件服务器
②自定义trace，为了测量吞吐量而设计的一个trace生成器，通过设置两个参数来生成一个trace：a.I/O去重比率（感觉可以理解成I/O请求中所请求的数据的冗余程度）; b.读写比
实验
通过基于数据集①的多组使用证明了，AustereCache在整体内存节省率上、读取命中率上、写入减少率上都比目前最新的CacheDedup要高很多。
此外也通过基于数据集①的多组实验证明了，AustereCache对于其参数的敏感性，包括块和子块大小设定对于内存开销的影响、LBA-index大小对于内存开销的影响等。事实证明，当块越大内存开销就越低，LBA-index越大，内存开销就越大。
还通过基于数据集②对整体的I/O吞吐量进行的实验，证明当I/O请求的数据中，冗余数据越多，代表需要访问SSD次数就越少，从而提升整体吞吐量。也证明了I/O请求中，读请求占比越高，吞吐量也越会有小幅增加。
还基于数据集②对CPU的开销进行了测量，表明主要计算开销基本还是计算块数据的FP值。后续也通过开启多线程证明，可以一定程度上减少CPU开销，并且线程数越高，吞吐量也越高。
总结
优点
文章详细的阐述了AustereCache的三大关键技术，并通过非常丰富的实验论证了AustereCache在于管理索引数据结构上的优越性，极大的降低了内存开销，同时也能维持与目前最新架构相同水准的读取命中率和写减少率。
个人觉得存在的问题
但是文章对于AustereCache的块大小设置并没有继续考虑，块越大，内存开销越低，但可能会带来额外的读写操作。因为一个块太大，可能对于一些处理小规格数据块的操作来说并不合适。
且文章也没有继续证明通过降低对SSD的写入次数，对于SSD寿命有何影响，只是定性的说会延长寿命。
本文专注于节省内存空间开销，但实际上可能加大了时间开销，比如文中对于LBA-index的置换策略使用的是LRU算法，但没有给出与其他置换算法的比较，如FIFO、CLOCK算法等，文中每次插入、删除、置换新的entry时，均会移动其余所有entry位置，这感觉会带来大量时间开销，存在进一步优化空间。
而且对于得到FP-index中每个entry的count，文中是使用估计的方法得到，会有一定误差，这感觉不太精确，且reference counter也会带来很大的内存开销。但可能直接将count存在FP-index带来的内存开销会更高。
还有一个疑问是，为什么在FP-index中count越低的越容易被替换掉这一策略体现了deduplication，count越低不代表数据重复度越低吗，从局部性原来上来说，优先替换掉count最低的是没问题的，但感觉和deduplication有些矛盾。。