leveldb中数据存储过程
当向leveldb写入数据时，首先将数据写入log文件，然后在写入memtable内存中。log文件主要是用在当断电时，内存中数据会丢失，数据可以从log文件中恢复。当memtable数据达到一定大小，会变为immemtable，并自动生成新的memtable，然后log文件也生成一个新的log文件。Immutable Memtable则被新的线程Dump到磁盘中，Dump结束则该Immutable Memtable就可以释放了。memtable提供了写入KV记录，删除以及读取KV记录的接口，但是事实上memtable并不执行真正的删除操作,删除某个Key的Value在memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作在后面的 Compaction过程中(是不是感觉和前面介绍的skiplist很相似，没错，memtable的核心结构就是skiplist)
leveldb 中的 Key
user_key
Slice类，实质上就是一个string，只不过稍微封装了一下
class Slice {
public:
//something...和本文关系不大，不全部贴出来了
private:
const char* data_;
size_t size_;
};
ParsedInternalKey
struct ParsedInternalKey {
Slice user_key;
SequenceNumber sequence;
ValueType type;
ParsedInternalKey() { } // Intentionally left uninitialized (for speed)
ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
: user_key(u), sequence(seq), type(t) { }
std::string DebugString() const;
};
ParsedInternalKey就是一个struct，其中SequenceNumber和ValueType定义如下:
enum ValueType {
kTypeDeletion = 0x0,
kTypeValue = 0x1
};
typedef uint64_t SequenceNumber;
InternalKey
class InternalKey {
private:
std::string rep_;
public:
InternalKey() { } // Leave rep_ as empty to indicate it is invalid
InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
}
void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }
Slice Encode() const {
assert(!rep_.empty());
return rep_;
}
Slice user_key() const { return ExtractUserKey(rep_); }
void SetFrom(const ParsedInternalKey& p) {
rep_.clear();
AppendInternalKey(&rep_, p);
}
void Clear() { rep_.clear(); }
std::string DebugString() const;
};
通过源码我们可以看到InternalKey本质上也是一个字符串，这个字符串是由ParsedInternalKey转换而来的。下面看看具体的转换函数
void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
result->append(key.user_key.data(), key.user_key.size());
PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
}
static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
assert(seq <= kMaxSequenceNumber);
assert(t <= kValueTypeForSeek);
return (seq << 8) | t;
}
实质上就是一个字符串拼接的过程。(其中涉及到coding)
根据这个我们也能得到InternalKey的组成形式实际上就是
| User key (string) | sequence number (7 bytes) | value type (1 byte) |
同样从InternalKey中我们能获得user_key,操作也十分简单
inline Slice ExtractUserKey(const Slice& internal_key) {
assert(internal_key.size() >= 8);
return Slice(internal_key.data(), internal_key.size() - 8);
}
从InternalKey中我们能获得TypeValue:
inline ValueType ExtractValueType(const Slice& internal_key) {
assert(internal_key.size() >= 8);
const size_t n = internal_key.size();
uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
unsigned char c = num & 0xff;
return static_cast<ValueType>(c);
}
LookupKey
memtable的查询接口传入的就是LookuoKey
bool Get(const LookupKey& key, std::string* value, Status* s);
先看一下LookupKey是怎么定义的
class LookupKey {
public:
LookupKey(const Slice& user_key, SequenceNumber sequence);
~LookupKey();
Slice memtable_key() const { return Slice(start_, end_ - start_); }
Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
private:
const char* start_;
const char* kstart_;
const char* end_;
char space_[200]; // Avoid allocation for short keys
// No copying allowed
LookupKey(const LookupKey&);
void operator=(const LookupKey&);
};
再看看构造函数
LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
size_t usize = user_key.size();
size_t needed = usize + 13; // A conservative estimate
char* dst;
if (needed <= sizeof(space_)) {
dst = space_;
} else {
dst = new char[needed];
}
start_ = dst;
dst = EncodeVarint32(dst, usize + 8);
kstart_ = dst;
memcpy(dst, user_key.data(), usize);
dst += usize;
EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
dst += 8;
end_ = dst;
}
这样的话不难分析出，LookupKey的结构如下:
| Size (varint32)| User key (string) | sequence number (7 bytes) | value type (1 byte) |
这里的size其实就是user_key的长度加8.
start_是LookupKey字符串的开始，end_是结束，kstart_是user key字符串的起始地址
======
Key分析完了=。=明天再继续分析memtable，啦啦啦啦啦啦啦
