存储引擎 K/V 分离下的index回写问题

前言

近期在做on nvme hash引擎相关的事情，对于非全序的数据集的存储需求，相比于我们传统的LSM或者B-tree的数据结构来说 能够减少很多维护全序上的计算/存储资源。当然我们要保证hash场景下的高写入能力，append-only 还是比较友好的选择。

像 Riak的bitcask 基于索引都在内存的hash引擎这种，在后期的针对data-file 的merge 完成之后会将新的key-value-index回填到内存中的hash索引中，这个过程在实际的生产环境对性能有多大的影响还不太好确定。但是，很明显的一点是正确的hash引擎索引在高并发场景中的更新是需要加锁的。而一旦有了排他锁，也就意味着CPU的独占，这个时候用户的读取和插入 就会和merge 之后的index回填发生锁的竞争，从而影响引擎的外部性能。

而同样的问题在以 Wisckey 为首的 LSM-tree key-value 分离策略中尤为明显，包括Titan, rocksdb的BlobDB,BadgerDB 都会面临这样的问题，他们在compaction 之后的回填 大value-index 还需要产生I/O操作，这个代价可能会更高，那他们是怎么解决这个问题的呢？

探索他们的解决办法不一定完全能够借鉴到hash 引擎的实现中，不过是可以提供一个解决思路。

Titan 的回写策略

关于Titan的 GC 策略介绍可以参考：​​Titan GC策略实现​​ Titan 是 pingcap 早期基于wisckey 做出来的key-value 分离存储引擎，可以作为rocksdb 的一个插件来使用。
它的解决办法是提供一个可配置项​​gc_merge_rewrite​​：

1. 关闭：会在GC 过程中将key-value写入新的blobfile 之后，通过正常的Write with Callback + Put 接口回写blob-index到lsm-tree。这个也就是默认回写的方式，Titan的Callback 是一个Get操作，在写入之前会先尝试读一下这个key 是否在lsm-tree中，如果不在就不会写入了。而且会将新的key + key-index 完全写入。
2. 开启：则是一个回写产生的性能问题和读性能之间的一个trade-off。开启之后直接写入 一个​​kMergeType​​​ blob-index，这种情况下不需要去执行​​Callback​​了，而是直接写入Merge操作，后续通过compaction 进行 key的blob-index的合并 或者 读请求命中这个key的时候会进行merge。merge请求本省不会携带原本大小的value，所以不会产生较大的写放大，只是在读的时候需要将当前key之前的merge都进行合并，对读性能可能有较大的影响。

相关的实现代码可以参考：

void BlobGCJob::BatchWriteNewIndices(BlobFileBuilder::OutContexts& contexts,
                                     Status* s) {
   ...
   // 关闭merge，调用默认的写入方式
   if (!gc_merge_rewrite_) {
     merge_blob_index.EncodeToBase(&index_entry);
     // Store WriteBatch for rewriting new Key-Index pairs to LSM
     // 在这个策略下，rewrite_batches_ 最后的消费是通过 Rocksdb::WriteWithCallback实现
     // 的，在写入的时候会执行 Callback，里面会去查一下key是否存在。
     GarbageCollectionWriteCallback callback(cfh, ikey.user_key.ToString(),
                                             std::move(original_index));
     callback.value = index_entry;
     rewrite_batches_.emplace_back(
         std::make_pair(WriteBatch(), std::move(callback)));
     auto& wb = rewrite_batches_.back().first;
     *s = WriteBatchInternal::PutBlobIndex(&wb, cfh->GetID(), ikey.user_key,
                                           index_entry);
   } else { // 开启，rewrite_batches_without_callback_ 的消费过程是 直接写入Merge 类型的key
     merge_blob_index.EncodeTo(&index_entry);
     rewrite_batches_without_callback_.emplace_back(
         std::make_pair(WriteBatch(), original_index.blob_handle.size));
     auto& wb = rewrite_batches_without_callback_.back().first;
     *s = WriteBatchInternal::Merge(&wb, cfh->GetID(), ikey.user_key,
                                    index_entry);
   }
   ...
}

最终对两个数据结构的消费逻辑统一是在​​RewriteValidKeyToLSM​​函数中。

BlobDB 的回写策略

BlobDB 的大体特性可以参考​​BlobDB 特性及性能测试结果​​。
因为BlobDB 新版本是社区比较推荐的一个k/v分离的稳定版本，基本的Rocksdb特性都已经支持了，包括trasaction/checkpoint/backup 等这一些不常用但很重要的功能都已经支持了。除了像merge/ingest等更为偏的能力暂时还不支持。

BlobDB的在GC上的一个考虑就不想因为后续频繁的回写处理影响正常的请求。
如果开启了GC ​​​enable_blob_garbage_collection​​：

1. 则在compaction过程中，迭代器 处理 类型 ​​kTypeBlobIndex​​​ 的key时会进入到​​GarbageCollectBlobIfNeeded​​，因为分离存储的时候lsm中存放的value 是key-index，即这个value能够索引的到blobfile的一个index。
2. 确认当前blob能够参与GC 且 当前key需要被保留，则根据key-index 读取到blob_value 并 直接写入到新的blob-file中。并且将新的blob-index 作为当前key的value，提取出来。
3. key 和 新的key-index 继续参与compaction后续的落盘行为。

主体第二步，也就是想要GC的话会在compaction过程中直接将过期的blob-value直接回收，compaction完成之后 lsm的sst 以及 blob都会被更新到，只需要维护后续的旧的blob回收即可。

代码实现如下：

1. compaciton过程中（迭代器按key处理阶段） 调度GC

void CompactionIterator::PrepareOutput() {
  if (valid_) {
    if (ikey_.type == kTypeValue) {
      ExtractLargeValueIfNeeded();
    } else if (ikey_.type == kTypeBlobIndex) {
      // 调度GC
      GarbageCollectBlobIfNeeded();
    }
    ...
}

1. 按照上面的步骤进行处理：

void CompactionIterator::GarbageCollectBlobIfNeeded() {
  ...
  // 开启GC
  if (compaction_->enable_blob_garbage_collection()) {
    BlobIndex blob_index;
    {
      // 1. 获取blobindex
      const Status s = blob_index.DecodeFrom(value_);
      if (!s.ok()) {
        status_ = s;
        valid_ = false
        return;
      }
    }
    if (blob_index.IsInlined() || blob_index.HasTTL()) {
      status_ = Status::Corruption("Unexpected TTL/inlined blob index");
      valid_ = false;
      return;
    }
    // 2. 确认当前blob-index 允许参与GC
    if (blob_index.file_number() >=
        blob_garbage_collection_cutoff_file_number_) {
      return;
    }

    const Version* const version = compaction_->input_version();
    assert(version);
    {
      // 3. 解析读出来当前blob数据
      const Status s =
          version->GetBlob(ReadOptions(), user_key(), blob_index, &blob_value_);
      if (!s.ok()) {
        status_ = s;
        valid_ = false;
        return;
      }
    }
    value_ = blob_value_;
    // 4. 将读出来的blob数据写入到新的blob file，并构造新的 value-index 作为当前lsm-tree
    // 即将存储的key的value.
    if (ExtractLargeValueIfNeededImpl()) {
      return;
    }

    ikey_.type = kTypeValue;
    current_key_.UpdateInternalKey(ikey_.sequence, ikey_.type);
    return;
  }
  ...
}

问题1： compaction过程中读取大value和我们rocksdb 未k/v分离 场景下的读取有什么区别？

这里的读取只会是保留的key的real value，对于那一些要清理的key，则不会读取。为了避免业务峰值触发大量的compaciton以及 GC的读取，GC的触发可以通过​​SetOption​​ 来动态调整。

问题2: 相比于 Titan GC 调度的优劣？

个人觉得，BlobDB的GC调度更为简洁高效低成本。
来，我们对比一下GC过程中产生I/O的步骤：

1. TitanDB，通过EventListener 在compaction过程中拿到需要参与GC 的blobfile 集合，compaction完成之后 对待GC的 blobfile 进行iter 迭代。
   a. 拿到每一个key 去 LSM 点查 是否存在。
   b. 存在，则读取其所在blobfile 的 大value，写入到新的blobfile
   c. 写入key 以及 新的value-index 到 LSM -tree（伴随着后续的逐层compaction，或者 merge的合并）。
2. BlobDB，直接在compaction过程中一起调度GC。
   a. 不需要反查，compaction过程中知道这个key是要keep还是要skip，直接对keep下来的key 读取blobfile的大value，写入到新的blobfile.
   b. 继续compaction时直接将当前要keep下来的key 以及 新的 value-index 写入 lsm即可。

可以看到，blobdb 的第二个步骤是正常的compaction写入逻辑，相比于Titan来说，其实也就只进行了 Titan有效的第二步，少了第一步的点查和第三步的回写。除此之外，Rocksdb的可调性更高一些，可以针对必要的GC时的大value读写进行控制，允许动态调整，从而最大程度得减少了GC对上层请求的性能影响。

具体在 GC 过程中的性能差异会在后续补充上。

BadgerDB 的回写策略

Badger 作为 dGraph 社区备受 cgo 折磨之后推出的自研k/v 分离存储引擎，在go 语言中还是非常受欢迎的。
本文仅讨论BadgerDB 在k/v 分离场景的回写策略，对于其测试优于Rocksdb（rocksdb的默认参数） 以及 其相比于Rocksdb 的其他优秀设计暂不展开讨论。

Badger的大value是存放在value log文件中，它很聪明的一点是GC 接口只交给用户来调度，而不是自己内部自主触发，这样的责任划分就非常清晰了，用户自己选择开启关闭GC，来自己承担GC引入的读写问题，真是机智。
当然BadgerDB 这里的GC回写并没有看到太亮眼的设计，就是在对 value log 进行GC的时候和Titan不开启​​​gc_merge_rewrite​​ 逻辑差不多。

1. 选择好了待GC的value-log文件，先从lsm中尝试读取key，存在则需要将value写入到新的value log中。
2. 完成写入新的value-log之后，会将最终的key, value-index 更新到lsm-tree中。

回写源代码基本在​​RunValueLogGC​​​ 函数中的​​rewrite​​处理逻辑中，感兴趣的可以看一下。

总结

可以看到为了解决在LSM-tree中大value 不随着compaction一起调度而造成的性能问题，大家可谓是煞费苦心。Titan 尝试做了一些优化，但整体来看还是不尽人意。Rocksdb 的 Blobdb 还是更加成熟，可以说是考虑得很全面了，从实现上看确实有很明显的效果。而BadgerDB的做法更为彻底，这个问题我们不管，交给用户自由调度，因为用户大多数情况还是知道自己的业务什么时候处于高峰，什么时候处于低谷，产生的I/O竞争问题那是你们自己调度造成的，自己解决哈，