🪴 meox3259

RocksDB - Lethe & Rocksdb中针对delete的优化

8 min read

lsm tree是一个针对写优化的数据结构，所有写都是追加的形式，因此delete也是out-of-place-update的，显然这样会导致delete存在一定的性能问题。

性能问题

首先对lsm tree中的删除方式进行总结

  • Point delete
    • 插入tombstone
    • 写放大（所有tombstone到最后一层才会被删除）
    • 空间放大（tombstone会占据额外的空间，直到一段时间后才会被删除）
  • Range delete
    • 全量插入所有的tombstone
    • 大量的tombstone导致性能变差
  • Secondary Delete
    • 按非主键进行删除
    • 由于lsm tree中元素按照主键排序，因此对于一个范围的Secondary Key，不连续地分布在很多SST上，因此需要进行全量compaction。显然单次巨大的compaction导致集中出现大量I/O，导致出现毛刺，影响可用性

综上所述，可以发现delete存在以下问题

  • delete tombstone带来的读/写/空间放大
  • range delete每删除一个kv，都需要一个delete tombstone，导致空间放大
  • Secondary delete需要进行全量compaction

Rocksdb优化

Point delete

方法1：在到达最后一层之前，提前清理delete tombstone

  • 在compaction期间，处理delete tombstone时，如果发现更高层的SST里key range和delete tombstone没有重叠，则说明这些delete tombstone没有用了，直接删除。

方法2：优先compaction含tombstone率高的文件

  • 一般情况下，Rocksdb会选择一个和下层重叠较少的SST进行compaction来减小写放大。对于delete heavy的场景，考虑对这个策略进行修改，优先对tombstone多的SST进行compaction。由于SST的元数据中存储了tombstone的数量，所以可以不通过额外代价计算出来。

方法3：该方法基于特定无修改的场景，如果对于一个Key插入后不再修改，那么可以发现delete可以和已有的Key直接抵消。

Range delete

显然将Range delete中所有都一个一个加入tombstone是一个不好的做法。Rocksdb中提到了当前对于Range delete的实现及优化。

原本的Range delete一般有以下几种方法

  • scan-and-delete：scan一遍要删除的键，挨个删除，这样显然较慢，因为磁盘I/O不友好，同时产生大量tombstone。
  • compaction filter：通过设置compaction filter在compaction的时候异步地删除。问题是仍然在非最下层会存在tombstone，同时也无法保证readers一定无法看见在delete range中的key。
  • compact range：是一个rocksdb中的api，会手动触发compact，删除一定范围内的key。这样可能会导致毛刺，同时阻塞其他compaction任务。

在上文的官方文档中提到的方法，大致方法是同样地在SST中的元数据区域保存删除标记，在进行compaction的时候，对这些删除的区间进行合并，使得这些删除的区间形成和SST中键类似的区间，且不相交。由于还存在快照，因此还需要考虑seqnum的存储，因此一个删除标记应该保存成一个三元组的形式(start_key, end_key, seqnum)，因此可以视为一个二维平面上的长方形。为了对保存的数据大小尽量压缩，因此分割的方法实际上是矩形并，将这些长方形进行求并，然后将端点存储下来。具体图示如下 图1

图2

观察以上图片，可以发现存储的方式只用存储图2中标记的红点。具体查询的时候，只需要查询一个(key, seq)是否在这些长方形形成的图形内部。

Secondary delete

可以发现，以上两种优化并没有解决Secondary delete的问题。Lethe对该场景进行了优化，例如需要按时间戳而非Key删除一定范围内的值。

FADE

FADE实际上是一种compaction策略，针对tombstone进行优化

  • 对每个tombstone设立一个TTL，其中从上到下，每层的TTL是上一层的T倍。
  • 计算每层超过TTL的tombstone数量，并计算一个总和，每次compaction选择超过TTL最多的层，把其中超时的tombstone全部compaction到下一层。

KiWi

KiWi是一种针对SST结构的更改。原本SST的结构是SST(file)->Block(page)，文件内部按照主键排序，KiWi修改了这个结构，改成了SST(file)->delete tile->Block(page)的三层结构，其中delete tile是按照delete key进行排序的，而Block内部和delete tile之间则还是主键。

这样的好处比较显然，即可以让delete key变得有序，而不至于像之前一样是完全无序的。有序的程度可以自己进行配置，即h，表示一个delete tile内部包含h个Block(page)。

论文中给了一个例子如何计算h

  • 有一个大小为400G的数据库，page大小为4KB，在两个range delete之间进行50M次点查，10K个短的区间查询，且bloom filter的假阳性率为0.02，且level之前的大小比例T=10
  • h的计算方法为

考虑删除的过程，按顺序取出delete tile，由于delete tile内部Block之间是按delete key有序的，因此对于Key的范围在delete range内的block，直接drop。

这样存在的坏处是查询时，相比原来的Iterator能一次直接定位到对应的block，由于delete tile内部不是按照主键排序，因此需要访问多个block。同样由于block之间是无序的，因此KiWi需要每个block有一个bloom filter，而rocksdb中一个SST才有一个bloom filter。不过由于bloom filter的存在，如果假阳性率不搞，且由于bloom filter是内存操作，因此性能下降的并不厉害。

图3

可以从上图发现，对于bloom filter性能下降了，但是磁盘I/O的性能显著提升了，因此总而言之性能有明显提升。

Graph View