LSM 優化系列（四） -- Rocksdb和Lethe 對Delete問題的優化

文章目錄

• ​​前言​​
• ​​1. 問題背景​​
• ​​2. 問題複現​​
• ​​3. Rocksdb 的 Delete-Aware 優化​​

• ​​3.1 可配置的 Delete-Aware排程​​
• ​​3.2 Compaction 邏輯對 delete key的優化​​

• ​​4. Lethe: A Tunable Delete-Aware LSM Engine . SIGMOD'20​​

前言

本文介紹過程中涉及到的源代碼是基于​

​rocksdb 6.4.6​

​ 版本的。

同時需要對rocksdb的Compaction邏輯以及源代碼有較為深入的了解，相關的原理介紹之前有一些粗淺的分析，對了解不夠深入的同學應該有幫助。

​1. SST檔案詳細格式源碼解析​​

​​2. Compaction 完整實作過程 概覽​​

1. 問題背景

基于LSM的存儲引擎 在提供了優秀的寫性能的基礎上 卻因為compaction帶來了很多其他問題。

本文所要描述的一個場景是LSM引擎的标記删除（将對一個key的删除作為一個key-value 追加寫入到引擎之中），這種删除邏輯會帶來如下幾個問題：

• 讀放大：range scan 的時候需要掃描更多的記錄，點查詢Bloom Filter 的false positive機率增加。
• 空間放大：因為delete的type 也是一個key-value,而這種類型的key隻有在compaction到最後一層才會被删除，中間層的很多空間就會被浪費在delete的存儲之上。
• 寫放大：本身LSM compaction帶來的原有問題，而針對delete key的頻繁排程compaction 帶來的寫放大問題更不友好。
• 使用者隐私：使用者已經标記删除的資料并沒有及時删除，未到最後一層，無法真正删除。

如上圖：标記D的都是含有delete 的sst檔案，加入我們想要查找的key在L2，這個key其實之前已經被删除了。但是資料并沒有被清理，對應sst檔案的bloom filter也沒有更新，是以無法準确判斷改key是否還在，則需要一直讀到 purpose key所在的sst檔案的data block，發現這個key時delete type，最後才向用戶端傳回not found。

這個查找過程存在數次I/O操作，讀sst檔案的 filter block,index block, 整個data block，真删除的不存在key的查找 多了 兩個block的IO流程（index block 和 data block），代價可想而知。

2. 問題複現

因為業務中存在這樣的問題，是以直接上代碼，更加直覺。

複現如下簡單且經典場景（sql删除了一個表中80%的資料，後來想scan剩下的一部分資料）：

寫入1千萬的相同字首 且字典序遞增的key，删除其中的的9百萬，從頭周遊 直到取得未删除的前500條key。

站在使用者的角度：

删除了一批key， 讀取剩下的key中的100條

引擎的角度：

使用者調用了删除接口，寫入了大量的delete type的key。但是 delete type的key還在LSM 上層，一點一點做compaction到最後一層。是以使用者調用一批scan 查找的過程相當于将已經标記delete 但是還未清理資料的key都得掃一遍。

通過實作一段rocksdb的複現代碼如下:

#include <unistd.h>
#include <atomic>
#include <iostream>
#include <random>
#include <string>
#include <thread>

#include <sys/time.h>

#include "rocksdb/db.h"
#include "rocksdb/table.h"
#include "rocksdb/cache.h"
#include "rocksdb/filter_policy.h"
#include "rocksdb/write_batch.h"
#include "rocksdb/rate_limiter.h"
#include "rocksdb/perf_context.h"
#include "rocksdb/iostats_context.h"
#include "rocksdb/table_properties.h"
#include "utilities/table_properties_collectors.h"
#include "gflags/gflags.h"

#define VALUE_LEN 500 

using namespace google;

DEFINE_int64(time,1200,"read threads' ratio");
DEFINE_int64(thread_num,64,"total threads ");
DEFINE_string(db_dir, "srd_delete", "db's dir is delete");
DEFINE_bool(use_fullcompaction, false, "use full compaction to db");
DEFINE_int64(num_keys, 1000000,"write keys' num");
DEFINE_int64(wait_compaction,10,"wait");
DEFINE_bool(traverse, true, "use traverse");
DEFINE_bool(use_delete_collector, false, "use traverse");

std::atomic<long> g_op_W;

rocksdb::DB* src_db;
rocksdb::Options options;
std::mt19937_64 generator_; // 生成僞随機數

// 傳回微秒
inline int64_t now() {
  struct timeval t;
  gettimeofday(&t, NULL);
  return static_cast<int64_t>(t.tv_sec)*1000000 + t.tv_usec;
}

// 打開rocksdb
void OpenDB() {
  options.create_if_missing = true;
  options.compression = rocksdb::kNoCompression;
  options.disable_auto_compactions = FLAGS_use_fullcompaction;
  
  if(FLAGS_use_delete_collector) {
    options.table_properties_collector_factories.emplace_back(rocksdb::NewCompactOnDeletionCollectorFactory(1000000, 1000));
  }
  std::shared_ptr<rocksdb::Cache> cache = rocksdb::NewLRUCache(10737418240);

  rocksdb::BlockBasedTableOptions bbto;
  bbto.whole_key_filtering = true;
  bbto.cache_index_and_filter_blocks = true;
  bbto.filter_policy.reset(rocksdb::NewBloomFilterPolicy(16,false));
  bbto.block_cache = cache;
  options.table_factory.reset(rocksdb::NewBlockBasedTableFactory(bbto));

  options.max_background_compactions = 32;
  auto s = rocksdb::DB::Open(options, FLAGS_db_dir, &src_db);
  std::cout << "open src_db" <<  s.ToString() << std::endl;

}

// 配置手動執行full compaction
void FullCompaction() {
  rocksdb::Slice begin("");

  rocksdb::Iterator *it = src_db->NewIterator(rocksdb::ReadOptions());
  it->SeekToLast();
  std::string end_str = it->key().ToString();
  delete it;

  rocksdb::Slice end(end_str);
  auto s = src_db->CompactRange(rocksdb::CompactRangeOptions(), &begin, &end);
  if (!s.ok()) {
    std::cout << "CompactRange failed " << s.ToString() << std::endl;
  }
}

// 寫入 + 删除
void DOWrite(int num) {
  int count = FLAGS_num_keys;
  std::string value(VALUE_LEN, 'x'); 
  while(count > 0) {
    src_db -> Put(rocksdb::WriteOptions(), std::string("test_compaction_129_")+std::to_string(count),value);
    ++ g_op_W;
    count --;
  }

  // 删除90% 的key
  std::cout << "Begin delete "<< std::endl;
  for (int i = 0;i < FLAGS_num_keys - FLAGS_num_keys / 10; ++i) {
    src_db->Delete(rocksdb::WriteOptions(), std::string("test_compaction_129_")+std::to_string(i));
  }
  src_db->SetOptions(src_db->DefaultColumnFamily(),{{"diable_auto_compactions","true"}});
  std::cout << "End delete \n";

  // 開啟full compaction
  if(FLAGS_use_fullcompaction) {
    FullCompaction();
    sleep(FLAGS_wait_compaction);
  }
}

void Traverse() {
  // open perf 
  rocksdb::SetPerfLevel(rocksdb::PerfLevel::kEnableTimeExceptForMutex);
  rocksdb::get_perf_context()->Reset();
  rocksdb::get_iostats_context()->Reset();

  rocksdb::Iterator *it = src_db->NewIterator(rocksdb::ReadOptions());
  it->Seek("");
  
  std::cout << "Traverse begin :" << std::endl;
  int64_t ts = now();
  int seek_count = 0;
  for(; it->Valid()&& seek_count<500;  it->Next() ) {
    std::cout << it->key().ToString() << std::endl; 
    seek_count++;
  }

  delete it;
  
  // close perf，檢視internal_delete_skipped_count名額
  rocksdb::SetPerfLevel(rocksdb::PerfLevel::kDisable);
  std::cout << "Traverse use time :" << now() - ts << std::endl;
  std::cout << "internal_delete_skipped_count "  
            << rocksdb::get_perf_context()->internal_delete_skipped_count
            << std::endl;
}


int main(int argc, char** argv) {
  ParseCommandLineFlags(&argc,&argv, true);

  OpenDB();

  for(int i = 0;i < FLAGS_thread_num; i++) {
    new std::thread(DOWrite,i);
  }


  long last_opn_W = 0;
  int count = FLAGS_time;
  while(count > 0) {
    sleep(1);
    long nopn_W = g_op_W;
    
    std::cout << "write_speed : " << nopn_W - last_opn_W << std::endl;
    last_opn_W = nopn_W;
    count --;
  }

  if(FLAGS_traverse){
    Traverse();
  }
  return 0;
}      

編譯時需要加入gflags 的連結，最終可以通過如下指令進行測試:

測試原生compaction邏輯下 traverse過程的耗時

​

​./test_delete -use_fullcompaction=false -time=300 -db_dir=./src_delete -thread_num=1 -num_keys=10000000 -use_delete_collector=false​

​

可以發現最終的輸出：

Traverse use time :2018292      

也就是在用戶端看來，隻擷取100個存在的key就話費2s的時間。。。這簡直不能忍，這樣的存儲引擎如何讓使用者安心使用。

這裡嘗試使用 Full Compaction 進行優化，即rocksdb自己提供的手動compaction接口​

​CompacRange​

​，在删除操作執行完成之後對整個db進行了一次全量的compaction操作，再次進行周遊擷取100個存在key的耗時統計。

以上的代碼也有增加，使用如下指令運作

​

​./test_delete -use_fullcompaction=true -time=300 -db_dir=./src_delete -thread_num=1 -num_keys=10000000 -use_delete_collector=false​

​

可以看到這次的運作耗時下降了3個量級，僅僅隻有364us：

Traverse use time :364      

那是不是我們這個問題就解決了呢？顯然不可能。

全量compaction 帶來的代價是極大的，所有的sst檔案不論之前有沒有參與過compaction都會被排程起來，巨量的I/O 和 CPU 洪峰，且跟随本節點資料量的大小持續一段時間；這個過程可能直接讓系統的可用性極低甚至掉零，更為嚴重的是某位不講武德的仁兄看到優化效果如此給力，不經過嚴格的測試直接線上跑 ，那這位仁兄就可以準備好挂個p0 走人了。

況且存儲引擎作為持久化存儲的核心，這樣的危險操作顯然不會交給使用者來做，是以本身引擎内部要有足量機制降低 未compaction清理的delete key對scan性能的影響，這也是引擎的職責所在。

總結這個問題放在引擎中處理 的幾個關節點 如下:

• delete的過程是通過compaction進行的，而compaction對于使用者來說是黑盒，使用者很難精确控制compaction過程中的delete key清理時機。
• 實際LSM的應用場景中 使用者驅動删除的workload 相對較少，除了使用者主動删除之外LSM 引擎也會應用在關系資料庫之中 出現drop 表等被動删除場景，是以在使用者不知道的情況下引擎也會産生大範圍的資料清理和遷移。
• 對非連續的key的删除排程。比如key的相同字首是基于table id,删除時則基于某一時間戳進行删除。這個過程需要排程seek進行大量的查找，代價極大。

接下來将介紹一下 rocksdb 以及 業界對該場景的優化手段。rocksdb這裡比較熟悉，會深入源代碼詳細介紹一番；業界對該優化的過程将介紹幾篇已有的優化論文。

3. Rocksdb 的 Delete-Aware 優化

基于以上問題，接下來會介紹Rocksdb 在該場景所做的兩個優化feature。

Rocksdb 在保證不增加LSM 的讀代價的情況下 針對delete type的key增加了兩方面的優化邏輯：

• 使用者态可配置的delete 密集型 sst檔案的compaction優先級排程。
• compaction本身針對 delete key 邏輯的 處理優化。

3.1 可配置的 Delete-Aware排程

​

​OpenDB​

​函數中增加如下rocksdb配置：

options.table_properties_collector_factories.emplace_back(rocksdb::NewCompactOnDeletionCollectorFactory(10000, 1000));      

同時需要包含頭檔案：

#include "rocksdb/table_properties.h"
#include "utilities/table_properties_collectors.h"      

檢視以上函數聲明：

std::shared_ptr<CompactOnDeletionCollectorFactory>
    NewCompactOnDeletionCollectorFactory(
        size_t sliding_window_size,
        size_t deletion_trigger) {
  return std::shared_ptr<CompactOnDeletionCollectorFactory>(
      new CompactOnDeletionCollectorFactory(
          sliding_window_size, deletion_trigger));
}

// A factory of a table property collector that marks a SST
// file as need-compaction when it observe at least "D" deletion
// entries in any "N" consecutive entires.
//
// @param sliding_window_size "N"
// @param deletion_trigger "D"
CompactOnDeletionCollectorFactory(size_t sliding_window_size,
                                  size_t deletion_trigger)
  : sliding_window_size_(sliding_window_size),
deletion_trigger_(deletion_trigger) {}      

總結一下：

​

​NewCompactOnDeletionCollectorFactory​

​函數聲明一個使用者配置的表格屬性收集器，這裡的表格指的是sstable。

該函數需要傳入的兩個參數​

​sliding_window_size​

​​和 ​

​deletion_trigger​

​ 表示删除收集器 的滑動視窗 和 觸發删除的key的個數。

在每個sst檔案内維護一個滑動視窗，滑動視窗維護了一個視窗大小，在目前視窗大小内出現的delete-key的個數超過了視窗的大小，那麼這個sst檔案會被标記為​

​need_compaction_​

​，進而在下一次的compaction過程中被優先排程。

達到将delete-key較多的sst檔案快速下沉到底層，delete的資料被真正删除的目的，可以了解為這是一種更加激進的compaction排程政策。

使用者僅僅需要調整兩個參數的比例，即可決定該sst檔案是否應該被優先排程compaction。

接下來詳細說一下Rocksdb的這個配置如何實作deletes 超過一定比例之後被compaction優先排程：

使用者配置了​

​table_properties_collector_factories​

​

在Compaction的核心處理key-value的函數​

​CompactionJob::ProcessKeyValueCompaction​

​​ 中排程 ​

​BlockBasedTableBuilder::Add​

​​ 函數 構造sst檔案中不同存儲區域的builder，這裡面會使用使用者構造的collector 進行 指定key的收集，通過如下函數​

​NotifyCollectTableCollectorsOnAdd​

​​ 進入 ​

​InternalAdd​

​ 。

bool NotifyCollectTableCollectorsOnAdd(
    const Slice& key, const Slice& value, uint64_t file_size,
    const std::vector<std::unique_ptr<IntTblPropCollector>>& collectors,
    Logger* info_log) {
  bool all_succeeded = true;
  for (auto& collector : collectors) {
    Status s = collector->InternalAdd(key, value, file_size); 
    all_succeeded = all_succeeded && s.ok();
    if (!s.ok()) {
      LogPropertiesCollectionError(info_log, "Add" /* method */,
                                   collector->Name());
    }
  }
  return all_succeeded;
}      

因我我們reset的是​

​NewCompactOnDeletionCollectorFactory​

​​ collector，是以會通過​

​UserKeyTablePropertiesCollector::InternalAdd​

​​ 進入​

​CompactOnDeletionCollector::AddUserKey​

​​ collector的​

​AddUserKey​

​函數:

• 增加滑動視窗内 真正key的數量，并根據是否達到了視窗門檻值 來及時更新内部key的數量 以及 降低舊的delete key的數量
• 根據傳入的key的類型來 增加滑動視窗内 delete key的數量，達到删除門檻值時會打入​

  ​need_compaction_​

  ​标記（這個标記會在後續的compaction邏輯中将目前sst檔案标記為優先級較高的sst檔案）

Status CompactOnDeletionCollector::AddUserKey(const Slice& /*key*/,
                                              const Slice& /*value*/,
                                              EntryType type,
                                              SequenceNumber /*seq*/,
                                              uint64_t /*file_size*/) {
  ...
  // 這裡的bucket_size_可以了解為我們設定的滑動視窗大小
  // 第一個if語句中做的事情主要是更新滑動視窗中 key的數量 以及 舊的delete key的數量
  if (num_keys_in_current_bucket_ == bucket_size_) {
    // When the current bucket is full, advance the cursor of the
    // ring buffer to the next bucket.
    current_bucket_ = (current_bucket_ + 1) % kNumBuckets;

    // Update the current count of observed deletion keys by excluding
    // the number of deletion keys in the oldest bucket in the
    // observation window.
    assert(num_deletions_in_observation_window_ >=
        num_deletions_in_buckets_[current_bucket_]);
    num_deletions_in_observation_window_ -=
        num_deletions_in_buckets_[current_bucket_];
    num_deletions_in_buckets_[current_bucket_] = 0;
    num_keys_in_current_bucket_ = 0;
  }

  num_keys_in_current_bucket_++;
  // 根據key的類型來調整是否達到觸發删除的門檻值，進而打入need_compaction_标記
  if (type == kEntryDelete) { 
    num_deletions_in_observation_window_++;
    num_deletions_in_buckets_[current_bucket_]++;
    if (num_deletions_in_observation_window_ >= deletion_trigger_) {
      need_compaction_ = true;
    }
  }
  ...
}      

在collector中達到觸發删除的标記之後會在​

​BlockBasedTableBuilder::NeedCompact()​

​​中展現，而這個函數則會被​

​CompactionJob::FinishCompactionOutputFile​

​調用

bool BlockBasedTableBuilder::NeedCompact() const {
  for (const auto& collector : rep_->table_properties_collectors) {
    if (collector->NeedCompact()) {
      return true;
    }
  }
  return false;
}      

​

​CompactionJob::FinishCompactionOutputFile​

​​同樣是在compaction的核心邏輯​

​ProcessKeyValueCompaciton​

​ 中調用，以sst檔案為機關 将構造好的一個個builder寫入到具體的sst檔案中的資料區域，寫入過程中對要寫入的sst檔案打入标記（如果collector中确認delete keys超過了設定的門檻值）

meta->marked_for_compaction = sub_compact->builder->NeedCompact();      

​

​marked_for_compaction​

​​标記會在函數​

​VersionStorageInfo::ComputeFilesMarkedForCompaction​

​​ 被使用，其中将有marked_for_compaction标記檔案添加到一個動态數組之中​

​files_marked_for_compaction_​

​，這個數組會在目前compaction完成之後再次被排程，将動态數組中的sst檔案優先進行compaction的排程。

void VersionStorageInfo::ComputeFilesMarkedForCompaction() {
  files_marked_for_compaction_.clear();
  int last_qualify_level = 0;

  // Do not include files from the last level with data
  // If table properties collector suggests a file on the last level,
  // we should not move it to a new level.
  for (int level = num_levels() - 1; level >= 1; level--) {
    if (!files_[level].empty()) {
      last_qualify_level = level - 1;
      break;
    }
  }

  for (int level = 0; level <= last_qualify_level; level++) {
    for (auto* f : files_[level]) {
      if (!f->being_compacted && f->marked_for_compaction) {
        // 将被打入标記的檔案添加到動态數組之中
        files_marked_for_compaction_.emplace_back(level, f); 
      }
    }
  }
}      

後續的排程過程會在​

​DBImpl::BackgroundCompaction​

​​中，通過如下邏輯調用 ​

​LevelCompactionPicker​

​​的​

​NeedsCompaction​

​​來進行判斷，判斷的過程主要是确認​

​files_marked_for_compaction_​

​​不為空即傳回true，進而再次将檔案添加到目前column family的待compaction隊列，最後通過​

​MaybeScheduleFlushOrCompaction​

​再次排程。

if (cfd->NeedsCompaction()) {
            // Yes, we need more compactions!
            AddToCompactionQueue(cfd);
            ++unscheduled_compactions_;
            MaybeScheduleFlushOrCompaction();
          }      

整個鍊路相對來說比較長且複雜的，需要對Compaction的排程代碼較為熟悉的話會更容易了解。

最後能夠在rocksdb的LOG日志來确認是否觸發了Marked的邏輯：

​

​"compaction_reason": "ManualCompaction",​

​​ 這樣的字段，且後續的Compaction job的輸出中能夠看到​

​records in​

​​的資料 和​

​records dropped​

​的資料的比例滿足我們設定的collector中的 sliding-window-size 和 delete-trigger的比例即可。

最後的性能可以通過上一章節中的 問題複現 的代碼看到。

運作如下指令：

​

​./test_delete -use_fullcompaction=false -time=300 -db_dir=./src_delete -thread_num=1 -num_keys=10000000 -use_delete_collector=true​

​

可以看到相同的delete場景，最後的traverse性能相比于原來能夠提升4倍，這個資料在不同的delete 比重以及collector設定的參數下有差異的。

Traverse use time :674629      

3.2 Compaction 邏輯對 delete key的優化

Compaction排程過程不再深入描述了，直接到上小節說過的​

​ProccessKeyValueCompaction​

​函數中會對key-value一個一個處理，會通過Compaction疊代器的移動（基本的SeekToFirst,Next等）來達到一個一個處理的目的。

處理的過程通過調用​

​NextFromInput​

​函數來進行，這個函數會處理不同的key-type，其中關于delete類型的主要處理邏輯如下代碼（這一部分全部粘貼到下面了，可以簡單看看）：

我們知道原本LSM 中的delete key 隻能在最後一層将之前所有的寫入包括自己都清理掉，因為到了最後一層就知道之前已經沒有人再使用這個key了。

這裡可能有人會問，使用者已經删除了，為什麼還一定要到最後一層才将key的資料清理掉呢?

因為rocksdb提供了snapshot功能，即在目前delete之前可能存在使用者打入的snapshot，即rocksdb需要保證那個時刻的key能夠被讀到，是以删除的過程中都需要确認目前key之前版本是否有snapshot的sequence number,如果沒有才允許後續的删除判斷。

} else if (compaction_ != nullptr && ikey_.type == kTypeDeletion &&
               IN_EARLIEST_SNAPSHOT(ikey_.sequence) &&
               ikeyNotNeededForIncrementalSnapshot() &&
               compaction_->KeyNotExistsBeyondOutputLevel(ikey_.user_key,
                                                          &level_ptrs_)) {
      // TODO(noetzli): This is the only place where we use compaction_
      // (besides the constructor). We should probably get rid of this
      // dependency and find a way to do similar filtering during flushes.
      //
      // For this user key:
      // (1) there is no data in higher levels
      // (2) data in lower levels will have larger sequence numbers
      // (3) data in layers that are being compacted here and have
      //     smaller sequence numbers will be dropped in the next
      //     few iterations of this loop (by rule (A) above).
      // Therefore this deletion marker is obsolete and can be dropped.
      //
      // Note:  Dropping this Delete will not affect TransactionDB
      // write-conflict checking since it is earlier than any snapshot.
      //
      // It seems that we can also drop deletion later than earliest snapshot
      // given that:
      // (1) The deletion is earlier than earliest_write_conflict_snapshot, and
      // (2) No value exist earlier than the deletion.
      ++iter_stats_.num_record_drop_obsolete;
      if (!bottommost_level_) {
        ++iter_stats_.num_optimized_del_drop_obsolete;
      }
      input_->Next();
    } else if ((ikey_.type == kTypeDeletion) && bottommost_level_ &&
               ikeyNotNeededForIncrementalSnapshot()) {
      // Handle the case where we have a delete key at the bottom most level
      // We can skip outputting the key iff there are no subsequent puts for this
      // key
      ParsedInternalKey next_ikey;
      input_->Next();
      // Skip over all versions of this key that happen to occur in the same snapshot
      // range as the delete
      while (input_->Valid() && ParseInternalKey(input_->key(), &next_ikey) &&
             cmp_->Equal(ikey_.user_key, next_ikey.user_key) &&
             (prev_snapshot == 0 ||
              DEFINITELY_NOT_IN_SNAPSHOT(next_ikey.sequence, prev_snapshot))) {
        input_->Next();
      }
      // If you find you still need to output a row with this key, we need to output the
      // delete too
      if (input_->Valid() && ParseInternalKey(input_->key(), &next_ikey) &&
          cmp_->Equal(ikey_.user_key, next_ikey.user_key)) {
        valid_ = true;
        at_next_ = true;
      }
    }      

以上邏輯的優化主要展現在第一個if語句之中，即目前delete 的key可能不在最後一層，通過這個函數​

​KeyNotExistsBeyondOutputLevel​

​判斷後續的層中沒有目前key了， 那麼就可以直接删除；這個邏輯會增加一定的CPU比較代價，但是它的收益是可觀的，能夠在較高的層中将key直接删除。

4. Lethe: A Tunable Delete-Aware LSM Engine . SIGMOD’20

這是一篇 今年頂會 SIGMOD中發表的論文，核心就是LSM 引擎帶來的delete問題。

在該篇論文中較長的描述了delete 對LSM帶來的問題，且現有的引擎沒有很好的辦法很好得解決大範圍删除的問題。

Lethe通過：

• 增加統計資訊和compaction政策，優化sort key大範圍删除帶來的問題
• 設計新的storage layout,來提升secondary key的大範圍删除。

提出了了兩種政策：

• FADE(fast deletion): 更加激進的compaction排程政策。相比于rocksdb的可配置政策，這裡增加了檔案的TTL，優先針對達到TTL的檔案進行挑選（可以根據TTL主動觸發排程），排程compaction删除。
• KiWi(Key Weaving storage layout): 提高支援非sort key的range delete,犧牲了一定的查詢代價，提升了範圍删除的效率。這個設計 感覺和rocksdb的DeleteRange有點類似，就是不知道性能差異大嗎？

一個X-engine的大佬已經有一篇該論文的詳細分享了。

​​Lethe 如何優化 LSM-Tree delete 難題​​