[论文笔记] Ac-Key: Adaptive Caching for LSM-based Key-Value Stores

LSM Tree 是一种对写友好但是对读不友好的数据库。LSM Tree 在查找一个 key-value 的时候需要先在 memtable 中查找，然后是各个层级的 SST 中去查找，所以查找一个 key-value 的时候需要多次 I/O 操作，这对于读多场景下的性能是有很大的影响的。

有多种方法可以优化 LSM Tree 下的读取性能，AC-Key 这篇文章是从缓存角度来进行优化。

给 LSM-Tree 实现 cache 有几个挑战：

1. LSM是一个分层的数据结构，那么根据kv对所处的层级不同，cache命中带来的收益也是不同的。根据LSM读取数据的方式，一般来说，kv对所处的层级越深，那么cache命中带来的收益就越大。因为KV对的大小并不是固定的，所以LSM树的缓冲策略需要做到缓冲的数据所占用的DRAM空间与节省的IO之间的平衡。
2. 对于点查与范围查询这两种类型的工作负载需要采用不同的缓冲策略。依赖来说缓冲kv对有助于调查，缓冲blockcache有助于范围查询和点查，另外，对于大value可以选择缓冲value的pointer。对于这三种类型的cache，如何动态调整它们的内存占比，以便获取最大的收益是一个挑战。

因此单一的传统的缓存算法在 LSM-Tree 上的效果并不好。

设计 #

需要考虑4个点：

1. 缓存KV和KP条目的优点应该结合起来，以有效地提供点查找服务。
2. 缓存块和KV/KP条目各自具有支持范围查询和点查找的优势。
3. 缓存算法应该考虑不同缓存条目所占用的DRAM大小和节省的存储I/O数量的差异，尊重LSM-KVS的独特分层结构。
4. 缓存算法应该适应工作负载的变化。

Caching Efficiency Factor #

论文提出了一个缓存因子 E 来权衡 cache benefit 和 cache cost 之间的关系。

1. ARC 中 L1 和 L2 之间容量的调整
2. LRU 替换策略

（这个 E 是否可以使用 AI 来辅助确定？）

Leveldb 源码解析—— Arena 内存池

内存池的主要作用是减少 malloc 和 new 的次数，因为每次内存分配都需要经过系统调用，这种开销是十分巨大的，所以通过内存池可以减少这种开销。

Leveldb 的内存池代码放在 util/arena.cc 和 util/arena.h 中。

class Arena {
 public:
  // ...
 private:
  // ...

  // Allocation state
  char* alloc_ptr_;
  size_t alloc_bytes_remaining_;

  // Array of new[] allocated memory blocks
  std::vector<char*> blocks_;

  // Total memory usage of the arena.
  //
  // TODO(costan): This member is accessed via atomics, but the others are
  //               accessed without any locking. Is this OK?
  std::atomic<size_t> memory_usage_;
};

alloc_ptr_ 指向的是内存块中未分配内存的其实地址的指针