leveldb删除的数据恢复

编程入门行业动态更新时间:2024-10-24 18:15:51

leveldb删除的<a href=https://www.elefans.com/category/jswz/34/1758223.html style= 数据恢复"/>

leveldb删除的数据恢复

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

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

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

switch (saver.state) {case kNotFound:break;     case kFound:return s;case kDeleted:*del = true;    //this is we adds = 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文件的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 itemfor (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 scandelete 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目录多复制几份做备用。