All-Flash Array Key-Value Cache for Large Objects

这篇文章是Eurosys23有关大对象缓存的文章，作者针对闪存（All-Flash Array）阵列场景下的存储架构提出了自己的设计，提高了系统的缓存命中率并减少了尾延迟。

Background

KV Cache是一种重要的存储系统，其可以减少用户延迟感知，减少后端的负载，比如在MySQL后端或者搜索引擎前加入缓存，提高系统的吞吐率。

然而用DRAM做KV Cache对于比较大对象（large objects）的存储存在缺陷：

• 大对象会消耗大量DRAM，很快导致系统中没有内存可以供进程使用了
• 需要建立分布式DRAM缓存池，开销大

由此提出用闪存阵列进行KV Cache，其容量可以达到PB级，价格也比单纯DRAM便宜36倍。

SSD vs AFA

SSD存储系统DRAM充足，SSD数量少（其实就是DRAM/SSD比例高）。AFA存储系统高性能、高容量，更少的DRAM和更大的SSD需要进行管理。

随着SSD容量提升速度（1.38x）高于DRAM容量提升速度（1.13x），未来的趋势更倾向于AFA。

Challenge

传统的SSD存储系统主要在三个问题上存在不足：索引（Indexing）、过期的数据（Expiration）、系统的容错性（Fault-tolerance）。

Indexing

在当前存储架构下Cache索引一般采用哈希表，数据会既存在于DRAM上，同时也会存在于SSD上。为了能找到一个数据对应的在SSD I/O的位置，我们需要先访问DRAM上的内存，再在SSD上面的哈希表遍历找到真正数据存储所在lba，最后再根据此访问数据。通过实验可以发现，哈希表操作如果放在SSD上会显著降低系统的性能，最坏可能达到51%的性能下落。但是矛盾点是，AFA存储系统的DRAM/SSD比例是相当低的，系统并没有都放在DRAM的空间。

Expiration

对于过时的数据，如果不去删掉这些过时的数据，会导致SSD上可用数据块越来越少，导致后期Cache命中率不断降低。

而完全扫描一遍整个SSD所花的开销非常非常大。

Fault-tolerance

SSD错误处理通常采用RAID机制完成，但是更高等级的RAID机制会导致性能的降低和存储空间的浪费。

Relation Work

Indexing optimize

• Kangaroo（SOSP21）：将log和data分开，仅对log设置哈希索引，减小了对象的元数据大小
• FlashShield（NSDI19）：减少元数据，仅保留小的FP（Fingerprint），采用链式索引
• SlickCache（SoCC18）：冷热哈希表，冷的存储在flash，热的存储在DRAM

Cross-layer optimization

• uDepot（FAST19）：优化IO栈

Design

Overall

整个系统设计包括三个part

• Indexing: 双层哈希，解决性能下降的问题
• Expiration：利用TTL处理过期数据，不再使用全扫描
• Fault-tolerance：反应式容错

indexing

当前哈希表结构：DRAM上存储最近操作的哈希表项，SSD上存储整个哈希表项和所有KV对象数据的位置。

哈希方式通常有两种：开放地址（Open-addressing）和链表式（Chained），前者在出现冲突后把数据对象存在相邻的位置，后者则把相同哈希值串成链表。

在读取data时，还存在FP冲突，因为相同的FP可能对应不同的value。然而在允许cache miss的前提下，系统是不存在FP冲突的，因为我们将直接替换相同FP对应的value，这样即使FP相同value不同，我们也可以触发cache miss。

在索引方面，DRAM上存储元数据，Flash上存储元数据和数据。DRAM上每个bucket大小64Byte，每个哈希表项16Byte，这是为了对齐cache line，整个DRAM分割成b个bucket，k个bucket组成SetCache，这个SetCache是同步到Flash上Htable的最小单位。在哈希过程中，创建新的哈希表项将不能越过临近的Htable，这样可以减少Flash上数据的读取量。

Expiration

针对过期数据的回收工作，本文采用了TTL进行估计和计算。TTL根据范围包括短时间、中时间和长时间，为了实现更好的过期数据回收，系统会把TTL相近的数据块集中在一块儿（这里把它们的元数据放在一块儿就行），然后到时间一块儿free。但是存在问题是如果所有请求都没有过期，系统需要空间的时候，将选择在全局队列中最靠后的数据进行evict，把其中有效的数据移出来，无效的数据丢弃，这样可以能更好保留热数据。

Fault-tolerance

RAID在速度和存储性能上都会产生额外开销。

如果采用全局RAID0条带化，一旦某个磁盘损坏了，整个系统将全部无法使用。

而采用分片的方式，损坏磁盘导致的大量cache miss也是一个非常重要的问题。

当系统发现某个磁盘出现问题时，请求将通过新的哈希函数发送到其他磁盘进行处理，这样可以减少cache miss ratio。与此同时，当磁盘重新恢复后，系统将本应该属于恢复节点的请求通过当前处理的节点转发到磁盘，这样当磁盘逐渐恢复后，就可以重新启用了。

元数据的持久化采用log-structure设计。

Experiments

Setup

实验设备：64GB DRAM，8块三星3.84TB盘

评价指标：整体性能、Cache hit ratio和错误处理

评价数据：YCSB、Twitter的Cache traces

Performance with YCSB

本文测量了在4KB、32KB、128KB和256KB的对象下，YCSB负载为0.99下系统的IOPS。整体来说，BigKV实现了99.3%和Cache Hit并将前3.1%的数据缓存在DRAM中。

SlickCache在性能测试中比较差，原因是Cache Miss后代价比较大，需要读取整个哈希表。

YCSB-A和YCSB-F（update占50percent）中，BigKV的性能要好于uDepot，主要原因对于FP的处理更好。

当对象大小超过128KB后，各种系统的IOPS占比接近，这是因为元数据命中均提高，而且读写成为系统的重要瓶颈。

Hit Rate with Traces

BigKV相比于uDepot，可以达到更高的Cache Hit最高点（2x）。同时尽管BigKV有热请求的回收操作，其申请新的空间依然接近0的开销。

Fault-tolerance

在处理错误时，系统比RAID会略降低Cache Hit Ratio，但在恢复之后不断提升，最终达到原来的Cache Hit Ratio。

8块SSD最终达到5.4倍提升。