Austere Flash Cache with Deduplication and Compression

有关闪存缓存

当计算机处理大量数据密集型工作时，对于硬盘的IO吞吐率和读写性能要求尤其高，但目前硬盘的性能远没有达到处理机的性能。因此，当想要更高效地去处理这类工作，可以在硬盘之上增加一层闪存缓存。

而在过去的很多研究中都使用了SSD作为闪存缓存介质，因本身具有的性质能够保证它作为闪存缓存介质有着很好的表现。比如说SSD具有

  1. 高IO吞吐率
  2. 低能耗
  3. 高可靠性
  4. 价格较低
  5. 非易失性（？）

为什么一定要用非易失性cache？是因为HDD是非易失的吗？

然而，由于SSD只有有限的储存空间，并且有写次数限制，想要将SSD作为闪存缓存，还需要克服如下问题：

  1. 最大利用有限的SSD存储空间
  2. 极大减少写操作

对于解决第一个问题，直观的想法就是去删除SSD缓存中的重复数据，并将缓存中的数据压缩地尽可能紧凑。这也是经常被运用到的两种技术：deduplication和compression。相对应的，不同于使用硬件实现的逻辑地址-物理地址的映射，在cache中实现去重和压缩必然会增加SSD的写次数，并且给内存带来负担。有时，因为data reduction的效率过低，只能放弃deduplication和compression。

Background

为了能将这两个技术应用的flash cache中，首先需要去了解deduplication和compression的概念和基本的操作流程，以及因为什么会导致大量的内存消耗。

Deduplication & Compression

首先是deduplication。首先，在论文中，或者是在flash cache中，是以块大小来存储的，因此关注的也是块级别，KB级别的数据重复。为了能快速判断两个chunk内容是否完全相等，可以使用统一的加密哈希计算得到footprint(FP)。由于两个不同的chunk对应完全相同的FP的概率几乎可以忽略不计，我们认为FP不同，chunk不同；FP相同，chunk相同。

那么我们期望的deduplication后的结果，在SSD中储存的所有chunk都是不同的，并且在请求访问HDD中的某一个位置时，如果有缓存，能够知道它对应的SSD中的chunk是哪个。

“有关chunk是大小可变的还是固定大小的的选择“

压缩操作一般来说会在去重操作之后执行。它是在字节级别将数据进行压缩，因此压缩之后的chunk都是大小可变的。

在论文中提出的Austere Cache management，在实现deduplication和compression的基础上，又保证了较小的内存消耗，同时也保证了缓存本身的读命中和较小的写次数，并极大地提高了IO吞吐率，是理论上非常理想的flash cache。

Flash Caching

在了解完deduplication和compression的基本概念之后，我们可以看到相较于传统的flash cache（即使用的是写回和写穿机制），他们需要的是在HDD和SSD之间的进行逻辑地址与物理地址转换的翻译层。
一个flash cache如果想应用这两种技术，还需要考虑到逻辑地址（也就是HDD中的LBA）与物理地址（SSD中的CA）是如何映射的问题。

而在Austere Cache中，在使用了上述的两种方法之后，在cache中，映射的是HDD中的逻辑块地址（LBA）到SSD中的块地址（CA）。在其中，我们会引入两个索引结构：

  1. LBA索引：它跟踪了HDD中的LBA映射到了哪一个FP中。因为使用了deduplication技术，LBA和CA是多对一的关系。
  2. FP索引：FP索引会记录每一个FP映射到CA的关系。由于在compression之后，chunk的大小是可变的，因此在FP索引条目中还需要增加chunk的大小保存。
  3. dirty list

总结一下，如果需要查找HDD中某一个位置的数据，首先需要从它的cache，SSD中进行查找。首先会查LBA索引，找到对应的FP，如果找到了再查找FP索引找到对应的CA，再去SSD中获取。

那么，查找两次真的好麻烦，为什么不能LBA直接映射到CA上呢？
这也是为了deduplication服务。

这是读操作的基本步骤。

那么对于一个写操作来说，首先写的数据需要被分成多个chunk（因为需要储存在SSD中），系统会进行检查，查看每个chunk是否和已经储存的内容相同。如果不相同，就会进行进一步的压缩，储存到 SSD之后对两个索引表进行更新。当然，如果是写穿模式，还需要将没有压缩的内容进行写入。

此处有一个原来的ppt，即使不去考虑计算chunk内容的哈希等等的计算消耗，也可以通过索引条目直观感受到，内存因为deduplication和compression大大增加。可以看到，FP正是实现deduplication的重要数据内容，而FP-index中的长度是实现compression需要跟踪的数据。而这两者正是让结构表变得很大，让内存的负担变重的主要原因。

AustereCache Design

那么论文中提到的Austere Cache的设计目标就是既能保证使用deduplication和compression来保证存储和IO的节省，同时也极大减少了内存的开销。它提出了三个重要的技术：

  • bucketization：上面提到了正是由于增加了一个index，同时增加了chunk的size和FP字段，才让内存开销变得巨大。因此我们可以把索引中的LBA-hash和FP-hash缩短，只在内存中储存它们两个的前缀。

    当然，考虑到哈希碰撞的问题，还需要SSD中储存完整的FP和LBA，储存该数据的区域称为元数据区域。为了查找方便，它和FP-index拥有同样数量，同样大小的桶，储存的是FP与其映射的多个LBA。但实际上，如果前缀长度取得足够好，只有极小的概率会出现哈希前缀的冲突。

    这样，把LBA-index和FP-index分别划分成桶，每个桶中可以储存相同数量的数据，每一条数据称为slot。

    同时，在之前的规划中还需要在FP-index中储存CA，用来找到对应数据在SSD储存的位置。但实际上这也可以省略。对于FP-index中的每条数据，实际上是与SSD中储存数据的chunk一一对应的。我们把SSD中储存数据（chunk）的区域也分成和FP-index一样的，数量相同的桶，桶中的一个slot即一个对应的FP。

    Write Path 当需要在flash cache中写入一条数据时（这条数据可以使用（LBA, FP）进行标识），首先会使用LBA-hash的前缀来查找是否已经对应一个FP了。如果没有，则需要在LBA-index和FP-index中寻找到一个空位或者替换掉一个一个slot。在此之后，在SSD的metadata region的相同位置写入FP和LBA；在data region的相同位置写入chunk即可。

    check duplicate chunk 查找FP-index => metadata region，如果前缀出现冲突，那么就会按照Write Path的方式重新写入。

    Read Path hit or miss

    analysis

Fixed-sized Compressed Data Management

我们知道在压缩之后，chunk的大小会变，因此需要在index中追踪每一个FP对应的chunk大小，这对于内存也是一个很大的负担。因此，Austere Cache将压缩之后的chunk分为了固定大小的子chunk，如果没有完整切分，最后一个子chunk会进行填充。

这样，FP-index中以每两个slot为一组，放入一对FP-hash prefix和flag。相对应的，metadata也时两个slot为一组，只在第一个slot中放入FP，LBAs和subchunk的长度。对于data region来说，一个FP就可以对应两个subchunk。

虽然FP-index的需求会变大，但是仍然…还是比将长度放在内存中好得多。

Bucket-Based Cache Replacement

最后，再来讨论一下cache的替换策略。

对于LBA来说，我们会使用LRU算法，新加入或者最近访问的LBA会放置在最低的offset上，每次替换时只需要将最高offset的LBA弹出即可。

由于FP-index，metadata region和data region的储存内容是一一对应的，因此需要同时考虑三者。

首先，AustereCache会跟踪每个FP-hash对应的LBA总数。理由也非常简单，拥有更多FP-hash引用数意味着更可能被访问到。当有LBA被替换掉时，就需要对应-1，新加入就+1。当插入一个新的FP时，就需要把引用数最小的FP替换掉。

但这样的替换算法是不完整的，比如说加入了一个新的（LBA，FP）对，那么FP的引用计数肯定为1，下次替换它非常容易被替换掉，也就是还缺乏最近访问（recency）的考虑。为了解决这个问题，我们可以将LBA-index的每个桶分为两组计数权重不同的slots。对于最近访问的LBA，它对于FP的权重为2；对于不那么经常访问的LBA，FP权重为1。那么当一个LBA条目降级时，FP权重-1；当一个LBA条目被替换时，FP权重-1；当新增一个LBA条目时，FP权重+2。

如果需要维护这一张表，一个FP会对应一个数字，这个结构放置在内存中也是不小的开销（可以类比下在内存中存放chunk的长度）。

Austere Cache使用了一个Count-Min Sketch的数据结构来解决这个问题，进行较为准确的计数。$r$行，$w$列，它将每个FP-hash都哈希到每一行的某个counter中。上面所述的计数也是对每个counter去计数。在查询时，会使用这$r$个counter中的最小值进行表示。