leveldb删除的数据恢复

墨阳羽

2023-12-01

1. 前言

.leveldb包含三个操作，Put插入item、Get根据key获取item、Delete删除特定的item，但是leveldb所有的写相关操作都是追加，Delete相当于一个Put(key, kdeletetype)操作，向数据库中插入一个delete标志，标明该key对应的数据已经删除了。本文章使用的代码为leveldb-1.12.

2. 本文分析内容安排

leveldb Delete从操作原理介绍
对leveldb源代码的更改
恢复代码

3. leveldb Delete操作原理介绍

3.1 Iterator迭代器

leveldb的迭代器实现比较复杂，因为leveldb的数据存在mutable、immutable和sstable中，所以其迭代器由这三者组成，因为只有sstable是实际存储在磁盘中的数据，其他两个是存储在内存中的，所以我们只讨论sstable的iterator。另外，因为leveldb只支持append写操作，同一个key在数据库中会对应多个版本号的数据，所以在实现上leveldb提供给用户的Iterator是基于key的，其Next()函数返回下一个不同的key的item；同时，其内部的iter_在key不同、同一个key但版本号不同是都是不同的，所以其Next()函数返回的是同一个key下一个seq的item或者是下一个key的数据。

3.2 Get获取数据过程

leveldb在执行Get(key, &value)操作取数据时，会首先从mutable中读取、其次immutable，最后读sstable，这里我们只涉及读取sstable中的数据。其在读取到的数据type为value时返回该value值，读到的type为delete值返回空。

4. 对leveldb源代码的更改

这里主要分为三步，第一步找出删除的item对应的key，第二步获取到该key在delete前存在磁盘中的数据，第三步使用获取到的数据再执行一个Put操作。其中，前两步都需要更改leveldb的源码，在此节介绍；第三步仅在恢复代码中实现，下节介绍。

4.1 找出所有删除的item对应的key

主要是在sstable对应的Get函数，即db/version_set.cc中的Get函数中添加一个bool* del参数，返回该key是否已经删除，更改代码如下（这里只提供version_set.cc和其头文件中的更改，其基类中继承函数的声明可以自己修改）:
version_set.h这里注意为了适配现有代码中调用该函数的地方，将del赋初值

Status Get(const ReadOptions&, const LookupKey& key, std::string* val, GetStats* stats, bool* del = NULL);

version_set.cc这里主要是在读取磁盘数据类型的时候，当key对象数据已经删除时做下记录

switch (saver.state) {
        case kNotFound:
          break;     
        case kFound:
          return s;
        case kDeleted:
         *del = true;    //this is we add
          s = Status::NotFound(Slice());  
          return s;
        case kCorrupt:
          s = Status::Corruption("corrupted key for ", user_key);
          return s;
      }

4.2 获取delete操作之前的数据

在原有的Iterator.Next()函数实现中，db/db_iter.cc文件的FindNextUserEntry()函数里，leveldb的内部iter_中当遍历到一个key包含delete操作时，会跳过该key所有后续seq数据直接跳到下一个key对应的Iter_；我们更改为仅会跳过该key的delete操作，而跳到delete操作之前的一次写入操作对应的item处，可以得到其value().

void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
  assert(iter_->Valid());
  assert(direction_ == kForward);
  do {
    ParsedInternalKey ikey;
    if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
      switch (ikey.type) {
        case kTypeDeletion:
          //we annotate next two lines, so traversal does not skip all seqs of a key, just skip this delete operation and get next value before delete operation
          //SaveKey(ikey.user_key, skip);
          //skipping = true;
          break;
        case kTypeValue:
          if (skipping &&
              user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
          } else {
            valid_ = true;
            saved_key_.clear();
            return;
          }
          break;
      }
    }
    iter_->Next();
  } while (iter_->Valid());
  saved_key_.clear();
  valid_ = false;
}

5. 恢复代码

我们用的代码是leveldb-1.12，当下载的源码和机器上原有leveldb.so库对应版本不一致时，用我们上面更改源码后编译的leveldb动态库替代系统中原有库后，还需要用源码中leveldb/include下的头文件替代系统中/usr/include/leveldb的头文件后再使用，负责可能导致头文件和库文件不一致

#include <assert.h>
#include <string>
#include <iostream>
#include <fstream>
#include "leveldb/db.h"
#include "leveldb/env.h"
#include "leveldb/write_batch.h"
#include "leveldb/cache.h"
#include "leveldb/slice.h"
#include "leveldb/write_batch.h"

using namespace std;

int main()
{
    leveldb::DB* db;
    leveldb::Options options;
    options.create_if_missing = true;
    leveldb::Status status = leveldb::DB::Open(options, "/home/Arvin/test", &db);
    assert(status.ok());

    ofstream outfile;
    outfile.open("levelDBFile1.txt",ios::out);
    if(!outfile)
    {
        cout <<"Cannot open file!" << endl;
        return 0;
    }
    leveldb::WriteBatch batch;
    int j = 0;
    //make a db for testing
    /*for(long long i  = 0; i < 1000000000; i++)
    {
      batch.Put(leveldb::Slice(std::to_string(i)) , leveldb::Slice(std::to_string(i)));
      //batch.Put(leveldb::Slice("2") , leveldb::Slice("111"));
      j++;
      if(j%100 == 0)
      {
        batch.Delete(leveldb::Slice(std::to_string(i)));
        db->Write(leveldb::WriteOptions(), &batch);
        cout<<"the j = "<<j<<endl;
        j = 0;
      }
    }*/
    leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
    //reput the deleted item
    for (it->SeekToFirst(); it->Valid(); it->Next()) {
      std::string value;
      bool del = false;
      db->Get(leveldb::ReadOptions(), it->key().ToString(), &value, &del);
      if(del) {
        db->Put(leveldb::WriteOptions(), it->key(), it->value());
      }
    }
    //after reput the deleted item, get the result to prove correctness
    /*for (it->SeekToFirst(); it->Valid(); it->Next()) {
      outfile << it->key().ToString() << " : "  << it->value().ToString() << endl;
    }*/
    outfile.close();
    assert(it->status().ok());  // Check for any errors found during the scan
    delete it;
    delete db;
    return 0;
}

这里，Get(key, &value)函数是根据key获取value，仅返回该key对应的最后一次操作，当最后一个操作为delete时返回空串，只不过我们加的del赋值为true，用于确定哪些key最后一次操作是delete；而迭代器的value()函数返回的是leveldb内部迭代器iter_对应的value值，因为我们已经跳过了delete操作，所以返回的是delete操作之前的seq对应的一份数据，改数据被再次Put进leveldb用于数据恢复。

注意： 执行Get操作时，会一层层访问sst直到获取到key对应的item，因为逐层访问sst文件本身就耗资源，所以Get操作会增加sst的统计计数，最终会引起Compaction归并操作，所以执行Get后会发现sst文件越来越少，delete操作对应的key也变少。由此可知，想恢复更多的数据，要使用最开始的sst目录做恢复，或者将sst目录多复制几份做备用。

6. 总结

本文主要说明了一种leveldb已经删除的item并且其还未compaction的数据恢复方法。

7. 作者介绍

梁明远，国防科大并行与分布式计算国家重点实验室(PDL)应届研究生，14年入学伊始便开始接触docker，准备在余下的读研时间在docker相关开源社区贡献自己的代码，毕业后准备继续从事该方面研究。邮箱：liangmingyuanneo@gmail.com
##7. 参考文献