LevelDB TTL Lab Report

朱维清 10215300402 ### commitID——VirgilZhu 谷杰 10222140408 ### commitID——GUJIEJASON Github 仓库地址：https://github.com/VirgilZhu/LevelDB-course-Lab

一、实验背景

TTL(Time To Live，生存时间)：

LevelDB 中，根据 TTL 设置了死亡时间的 KV 数据对应在被读取、合并过程中，判断其是否存活（数据对有效），若超过死亡时间，则进行丢弃处理。对所有 KV 数据对加入 TTL 属性后，能使 LevelDB 的 SStable 所占空间有效降低，存储数据回收机制进一步合理化。

实验要求：
1. 在 LevelDB 中实现键值对的 TTL 功能，使得过期的数据在读取时自动失效，并在适当的时候被合并清理:
  - Put()：键值对插入函数，使得调用它时每个插入的键值对应包含 TTL 属性，便于读取、合并过程中被访问时，进行 TTL 相关处理；
  - Get()：获取键值对的 Key、Value，使得调用它时能触发相应 TTL 判断流程，若数据对已过期，在相应函数进行键值对丢弃处理；
  - Compaction 流程相关函数：厘清 Minor Compaction、Major Compaction 的具体实现流程，在相关函数对数据对粒度的处理部分的适当位置加入判断数据对是否过期的代码，并触发可能的相应回收处理。
2. 编写/修改测试用例，验证 TTL 功能的正确性和稳定性

二、具体实现

Put() 函数实现

Q：测试用例在传入 TTL 参数后，Put() 函数应将死亡时间deadtime信息存入键值对的key还是value部分？

A：我们选择将deadtime存在value中，好处是存在value中我们可以更容易地实现不同的过期策略，也可以更方便地修改过期时间，同时也不需要更新更加复杂的key匹配和查找机制，更重要的是在value中添加会有更好的扩展性，未来也可以在value中添加更多其他的信息。

/* TODO: Add TTL Version Put() */
Status DBImpl::Put(const WriteOptions& opt, const Slice& key, const Slice& value, uint64_t ttl){
  WriteBatch batch;
  auto now = std::chrono::duration_cast<std::chrono::seconds>(std::chrono::steady_clock::now().time_since_epoch()).count();
  auto end = now + ttl;
  Slice value_timestamp = Slice(value.ToString() + "_ts_" + std::to_string(end));
  batch.Put(key, value_timestamp);
  return Write(opt, &batch);
}
/* --------------------------- */

对于Put操作，我们选择在保留原有的Put接口的基础上，增加一个新的Put接口，其包含TTL参数，单位为秒。如果我们调用原本的Put接口，则该键值对不会有TTL，如果调用新的Put接口，则会在value部分的末段加上_ts_字段和该键值对的deadtime。
同时，对于如何获取时间，我们选择的是调用 C++ 标准库中的**std::chrono::steady_clock**这一时钟类型，它的特点是单调递增，不会受到系统时间调整的影响。我们先是使用now()这一静态成员函数返回当前时间点的time_point对象，再调用time_point中的一个成员函数time_since_epoch()返回从纪元开始到当前时间点的时间间隔，这是一个duration对象，接着通过std::chrono::duration_cast将时间间隔的单位转换为秒，最后调用duration的count()函数返回一个表示秒数的整数。
这样，我们就成功地得到了当前时间的时间戳，单位为秒，接着只需要加上我们传入的ttl，便是该键值对的deadtime，最后将带有deadtime的value和key封装成Slice，使用 WriteBatch 对象的 Put 方法将带有时间戳的新键值对加入到批处理操作中，再调用 Write 方法将 WriteBatch 中的所有操作应用到数据库中，并返回操作的状态。这样便完成了带有ttl的写入操作。
同时，由于我们是重新定义了一个Put接口，别忘了在头文件中加入新Put接口的声明。

/* TODO: Add TTL Version Put() */
  Status Put(const WriteOptions&, const Slice& key,
             const Slice& value, uint64_t ttl) override;
  /* --------------------------- */

Get() 函数实现

    /* TODO: Add TTL Version Get() */
    if (mem->Get(lkey, value, &s)) {
      isLive(key, value, s, ttl);
      // Done
    } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
      isLive(key, value, s, ttl);
      // Done
    } else {
      s = current->Get(options, lkey, value, &stats);
      if (s.ok()) isLive(key, value, s, ttl);
      have_stat_update = true;
    }
    /* --------------------------- */

对于Get即读取操作，我们在原本的基础上只是增加了一个判断是否过期的功能，即对读取的键值对加一个判断，如果存在ttl且已经过期则不再读取。代码上在原本的基础上只是增加了一个isLive的判断函数。

/* TODO: Add TTL Version isLive() */
Status isLive(const Slice& key, std::string* value, Status& s) {
  if (value->empty()) {
    s = Status::NotFound(key);
    return s;
  }
  uint64_t now = std::chrono::duration_cast<std::chrono::seconds>(std::chrono::steady_clock::now().time_since_epoch()).count();
  size_t pos = value->rfind("_ts_");
  if (pos != std::string::npos){
     std::string timestampStr = value->substr(pos + 4);
     if (isAllDigits(timestampStr)) {
        uint64_t deadtime = std::stoull(timestampStr);
            if (now >= deadtime) {
              s = Status::NotFound(key);
            }
      }
  }
  return s;
}
/* --------------------------- */

/* TODO: Check if a string consists entirely of digits */
bool isAllDigits(const std::string& str) {
    for (char c : str) {
        if (!isdigit(c)) {
            return false;
        }
    }
    return true;
}
/* --------------------------- */

首先是先判断value是否为空，若为空则表示该键不存在或已被删除，返回NotFound。接着便是同Put操作中一样通过调用std::chrono::steady_clock来获取当前时间的时间戳。
通过rfind函数从后向前找到第一个_ts_字段的pos。若存在_ts_字段，则通过pos和substr函数来获取_ts_字段后面的内容，类型为字符串。接着这里有一个isAllDigits函数来判断一个字符串的内容是否全为数字，用到的是isdigit()函数。在确认全为数字后便通过std::stoull函数转换为unsigned long long整数，再与当前时间戳比较，若已过期，则返回NotFound。
⭐std::stoull 只能解析字符串中有效的数字部分，直到遇到第一个无法解析为数字的字符为止。例如如果我们调用原本的Put接口，设置value为“aaaaaa_ts_5678aaaaaaa”，对于获取的字符串timestampStr "5678aaaaaaa"，std::stoull 会解析出前缀的数字部分 "5678"，然后停止解析，忽略后续的非数字字符，这样本来一个无ttl的键值对被当成了有ttl，会导致数据丢失（在有无 TTL 参数与有 TTL 参数的 Put() 函数同时随机调用来插入数据对的情况下可能发生的情况）。

Compaction 流程相关函数实现

LevelDB 触发一次 Compaction 流程的函数调用关系：

参阅源码可知，每次 Compaction 流程的调用源头均为 DBImpl::MaybeScheduleCompaction() 函数，该函数判断当前是否可以调度一次 Compaction 流程后，若符合条件，会在“background”调度DBImpl::BGWork，触发DBImpl::BackgroundCall()函数，再通过加锁与判断，触发BackgroundCompaction()函数，正式进行一次 Compaction 流程；

BackgroundCompaction()函数详细解释了一次完整的 Compaction 流程，包括：

当前 LevelDB 并不存在 immutable memtable 的情况下会进行一次CompactMemtable() ，使 memtable 转变为一个 immutable table；

判断是否为手动合并（manual compaction），即传入的键值对合并范围 begin、end 是否均为 nullptr，若是，则调用确定合并范围的函数CompactionRange()；

实现一些 Compaction 流程的 Log 工作与回收工作；

在记录 Log 的同时，调用DBImpl::DoCompactionWork()函数，该函数是对 KV 键值对粒度进行实际读取与处理的函数。在经过详细的判断流程后，通过drop这一变量，实时记录当前访问的键值对是否需要丢弃，而本次 Lab 需要实现的 Compaction 流程中丢弃过期数据对这一工作正是在此处实现——在原本的判断是否丢弃的条件（如已经遍历到最后有数据对存储的 SStable 层；上一层存有写入数据库更晚的相同 key 数据对；上一层有正要合并到此层的更新的相同 key 数据对）之后，加入判断该键值对是否过期，若过期则将drop置为True。

TTL 在 Compaction 流程的具体处理是在DBImpl::DoCompactionWork函数中多加一个if判断：

/* TODO: Add TTL Version Compaction Drop Condition */
else {
  std::string user_value = input->value().ToString();
  uint64_t now = std::chrono::duration_cast<std::chrono::seconds>(std::chrono::steady_clock::now().time_since_epoch()).count();
  size_t pos = user_value.rfind("_ts_");
    if (pos != std::string::npos){
      std::string timestampStr = user_value.substr(pos + 4);
      if (isAllDigits(timestampStr)) {
        uint64_t deadtime = std::stoull(timestampStr);
        if (now >= deadtime) {
          drop = true;
        }
      }
    }
}
/* ----------------------------------------------- */

首先先将value转换为一个字符串类型，再用之前同样的方法，调用std::chrono::steady_clock来获取当前时间的时间戳，后面便是与isLive函数类似，若存在_ts_字段并且成功获取deadtime来与当前时间戳进行比较从而判断是否过期，若过期则调用drop将其删除。

实验中遇到的问题和解决方案

TestTTL.ReadTTL 测试样例始终报错的情况：
- 两次测试调用 OpenDB() 函数时，修改dbName为不同名字，避免出现访问持有锁的 LevelDB 的情况；
- 在测试过程中打印所有 Put() 函数插入的数据对，以及 Get() 函数在读取到数据对后，打印该数据对是否过期，并打印该数据对的死亡时间与当前时钟信息：
- 修改srand()函数传入的随机种子为固定（srand(42)），保证查找读取的 key 为先前插入的相同的 key。
TestTTL.CompactionTTL 测试样例，打印信息ApproximateSizes after TTL始终不为0，且数值仅比ApproximateSizes before TTL小一部分：
- 查看测试样例可知，测试样例调用的 CompactRange(nullptr, nullptr) 函数仅触发了手动合并，而 LevelDB 内部的自动合并可能在手动合并前就已经把部分数据合并为有序并存入更深层的 SStable 中，对此的解决方案采取了强迫每次手动合并都要遍历、合并数据对直到存有数据对的最深层Level（或直接合并所有SStable）；
- 经查阅源码，确定每次合并的最大范围（即end参数）的设置在DBImpl::CompactRange()函数中，由max_level_with_files参数决定。该参数意为存有数据对的 SStable 所在的最深level，而该level参数将传入Test_CompactRange()函数中，被设置为ManualCompaction manual变量的字段，而该变量manual将被赋值到manual_compaction_中，决定了该次手动合并的最深层和最大key值——只需要修改max_level_with_files为测试样例插入的数据经自动合并后存储了 SStable 的最深层，或是 LevelDB 的 SStable 存储最深层config::kNumLevels - 1（需要 pass assert(level + 1 < config::kNumLevels) 判断条件，即每次合并的最深层和更深一层是最后一次 compaction 涉及的 SStables 所在的两层）：
```
void DBImpl::CompactRange(const Slice* begin, const Slice* end) {
  int max_level_with_files = 1;
  {
    MutexLock l(&mutex_);
    Version* base = versions_->current();
    for (int level = 1; level < config::kNumLevels; level++) {
      if (base->OverlapInLevel(level, begin, end)) {
        max_level_with_files = level;
      }
    }
  }
  TEST_CompactMemTable();  // TODO(sanjay): Skip if memtable does not overlap
  for (int level = 0; level <= max_level_with_files; level++) {
  // for (int level = 0; level < config::kNumLevels - 1; level++) {
  //Original: for (int level = 0; level < max_level_with_files; level++) {
    TEST_CompactRange(level, begin, end);
  }
}
```

13 KiB 原始文件 永久連結 Blame 歷史記錄 file_download