leveldb_assignment_ttl/README.md

# LevelDB TTL 实验报告
小组成员：

王雪飞 10225501435

马也驰 10215501408
## 1.实验目的
1. 深入了解LevelDB的内部原理和数据结构。
2. 掌握TTL（Time To Live，生存时间）功能的设计与实现方法。
3. 学习如何在开源项目中添加新功能，提升代码阅读和修改能力。
## 2.实验要求
1. 在LevelDB中实现键值对的TTL功能，使得过期的数据在读取时自动失效，并在适当的时候被合并清理。
2. 修改LevelDB的源码，实现对TTL的支持，包括数据的写入、读取和过期数据的清理。
3. 编写测试用例，验证TTL功能的正确性和稳定性。
## 3.实验内容
### 3.1. TTL功能介绍
TTL（Time To Live），即生存时间，是指数据在存储系统中的有效期。设置TTL可以使得过期的数据自动失效，减少存储空间占用，提高系统性能。

为什么需要TTL功能：
1. 数据自动过期：无需手动删除过期数据，简化数据管理。
2. 节省存储空间：定期清理无效数据，优化资源利用。
3. 提高性能：减少无效数据的干扰，提升读写效率。
### 3.2. 设计方案
在LevelDB中添加TTL功能的方案：
1. 数据编码方式修改：在键或值中增加过期时间的信息。
2. 读取时判断过期：在Get操作时，检查数据是否过期，过期则返回NotFound。
3. Compaction清理：在数据压缩过程中，删除过期的数据。
## 3.3. 实现步骤
#### 3.3.1. 修改数据结构
在 Put 操作中，将 TTL 与当前时间相加获得 DDL，DDL 为数据失效的时间，将 DDL 与值一起存储，存储格式为`<TTL_value>`。
```
Status DB::Put(const WriteOptions& opt, const Slice& key,
                   const Slice& value, uint64_t ttl) {
  WriteBatch batch;
  auto now = std::chrono::system_clock::now();
  auto timestamp = std::chrono::duration_cast<std::chrono::microseconds>(now.time_since_epoch()).count();
  auto microsecondsTimestamp = static_cast<uint64_t>(timestamp) + ttl*1000000;
  std::string value_ttl = value.ToString();
  value_ttl += "_" + std::to_string(microsecondsTimestamp);
  Slice new_value(value_ttl.c_str(), value_ttl.size());
  batch.Put(key, new_value);
  return Write(opt, &batch);
}
```
### 3.3.2 修改读取流程
在 Get 操作中，获得 value 之后，找到第一个下划线，下划线前面的数据为 DDL，然后用当前时间与 DDL 作比较，判断数据是否过期，过期则返回NotFound。
```
size_t pos = value->find_last_of('_');
if (pos != std::string::npos) {
std::string substring = value->substr(pos + 1);
auto ddl = static_cast<uint64_t>(std::stoll(substring));
auto now = std::chrono::system_clock::now();
auto timestamp = std::chrono::duration_cast<std::chrono::microseconds>(now.time_since_epoch()).count();
auto microsecondsTimestamp = static_cast<uint64_t>(timestamp);
if (ddl <= microsecondsTimestamp) {
    value->clear();
    Slice msg1("value not found!");
    Slice msg2("value has expired!");
    s = leveldb::Status::NotFound(msg1, msg2);
} else {
    value->resize(pos);
    }
}
```
### 3.3.3 修改Compaction流程
在CompactRange函数中选中的最后一层，也就是代码中的max_level_with_files选中进行合并，
确保合并过程选中所有应该被覆盖度文件。
```
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++) {
    TEST_CompactRange(level, begin, end);
  }
  TEST_CompactRange(max_level_with_files, begin, end);
}
```

在BackgroundCompaction函数中禁止直接跨层移动文件，确保所有的文件都能通过DoCompactionWork
函数被合并。
```
} else if (!is_manual && c->IsTrivialMove()) {
//    // Move file to next level
//    assert(c->num_input_files(0) == 1);
//    FileMetaData* f = c->input(0, 0);
//    c->edit()->RemoveFile(c->level(), f->number);
//    c->edit()->AddFile(c->level() + 1, f->number, f->file_size, f->smallest,
//                       f->largest);
//    status = versions_->LogAndApply(c->edit(), &mutex_);
//    if (!status.ok()) {
//      RecordBackgroundError(status);
//    }
//    VersionSet::LevelSummaryStorage tmp;
//    Log(options_.info_log, "Moved #%lld to level-%d %lld bytes %s: %s\n",
//        static_cast<unsigned long long>(f->number), c->level() + 1,
//        static_cast<unsigned long long>(f->file_size),
//        status.ToString().c_str(), versions_->LevelSummary(&tmp));
  }
```

在DoCompactionWork函数中判断当前遍历的key所对应的value是否过期：如果已经过期，
就将该kv对应的drop标志设置为true，确保在合并是该kv被丢弃。
```
      Slice value_ddl = input->value();
      std::string value = value_ddl.ToString();
      size_t pos = value.find_last_of('_');
      if (pos != std::string::npos) {
        std::string substring = value.substr(pos + 1);
        auto ddl = static_cast<uint64_t>(std::stoll(substring));
        auto now = std::chrono::system_clock::now();
        auto timestamp = std::chrono::duration_cast<std::chrono::microseconds>(now.time_since_epoch()).count();
        auto microsecondsTimestamp = static_cast<uint64_t>(timestamp);
        if (ddl <= microsecondsTimestamp) {
          drop = true;
        }
      }
```
## 4. 实验结果
下面是我们跑仓库提供的test_ttl的结果：

![picture](picture/leveldb_ttl实验结果.png)

可以看到，两个test都能通过。
## 实验中遇到的问题
### 1. TTL存储的位置以及存储方式
我们最初的想法是把TTL跟value存储在一起，形式为`<TTL value>`，这样Put操作会很简单，仅仅把两个字符串拼接起来即可，但这样的话，在Get操作中时，无法判断从何处分割TTL和value，所以我们决定在TTL和value之间添加一个标志符，存放形式改为`<TTL_value>`,这样，在Get操作时，只需先找到第一个下划线，下划线前面的为TTL，后面的为value，这样就能把TTL和value区分开来。但还有一个问题，判断条件为：`写入数据的时间+ TTL < 读取数据的时间 `，如果仅存放TTL，虽然在调用get时我们可以获得读取数据的时间，并通过解码value获得TTL，但我们没有办法获得写入数据的时间，所以只能通过在Put操作时，把写入数据的时间也写入value中，这样在Get时，就能获得写入数据的时间，从而判断是否过期。所以，我们又把value的形式改为`<TTL_写入时间_value>`，这样，通过两个下划线把TTL、写入时间和value区分开来，就能实现在get操作时判断是否过期。但我们又想到，既然在get操作解码得到TTL和写入时间之后要加在一块，并且TTL和写入时间都是在get操作时与value进行编码，那么我们为什么不在get操作时就把TTL和写入时间加在一起，再与value编码呢，把写入时间+TTL记为DDL，这样就可以把value编码为`<DDL_value>`，在get操作时，只需解码得到DDL，然后拿当前时间跟DDL作比较，即可知道数据是否过期。

综上所述，我们的编码格式经过多次迭代：`<TTL value>`->`<TTL_value>`->`<TTL_写入时间_value>`->`<DDL_value>`,最终得到一个比较满意的编码方式。

### 2. Compaction流程
一开始我们只在DoCompactionWork函数中添加了一个解码value得到ddl，并于当前时间进行比较判断数据是否过期的过程，但发现测试无法通过。
后来参考助教的提示，我们原本打算修改测试用例，即修改写入数据量的大小，但是没有成功。之后我们决定修改Compact过程。具体来说，我们在CompactRange,BackgroundCompaction中进行修改，
确保每一次Compaction都能合并所有的文件，并且禁止leveldb直接跨层移动文件，最后通过了测试。

### 3. test_ttl编译以及数据库打开问题
test_ttl一开始无法通过编译，经过检查发现是重复定义了ranges和sizes两个数组。我们将两个数组进行了重命名解决了这个问题。同时，我们还遇到了第二个
测试数据库无法打开的问题，我们通过修改数据库名称的方法解决了这个问题。