数据恢复"/>
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目录多复制几份做备用。
6. 总结
本文主要说明了一种leveldb已经删除的item并且其还未compaction的数据恢复方法。
7. 作者介绍
梁明远,国防科大并行与分布式计算国家重点实验室(PDL)应届研究生,14年入学伊始便开始接触docker,准备在余下的读研时间在docker相关开源社区贡献自己的代码,毕业后准备继续从事该方面研究。邮箱:liangmingyuanneo@gmail
##7. 参考文献
更多推荐
leveldb删除的数据恢复
发布评论