leveldb源码阅读-memtable

本文主要是介绍leveldb源码阅读-memtable，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

memtable在leveldb中扮演着及其重要的地位，用于存储最新的数据修改信息，当数据的规模达到一定的上限之后，就会将数据转存储为immutable memtable，这时候就会被存储到sstale中；因此总的来说，所有在内存的数据都是以memtable进行存储的；

memtable的接口如下：

void Ref() { ++refs_; }//引用次数// Drop reference count.  Delete if no more references exist.
void Unref() {--refs_;assert(refs_ >= 0);if (refs_ <= 0) {delete this;}}
size_t ApproximateMemoryUsage();
Iterator* NewIterator();
void Add(SequenceNumber seq, ValueType type,const Slice& key,const Slice& value);
bool Get(const LookupKey& key, std::string* value, Status* s);

从公开的接口来看，memtable作为kv存储系统，并没有提供删除数据的接口，主要是在leveldb中，数据的删除是以标记来实现的，因此memtable只需要支持数据的增加就可以了；

enum ValueType {kTypeDeletion = 0x0,kTypeValue = 0x1
};

ValueType用来表示增加数据信息的类型，包括删除和新增，对于数据的修改，也是以新增数据来实现的；

Slice 是String的简单实现；

SequenceNumber是用。。来执行数据恢复的，这里还不是很懂。。 从SequenceNumber的定义可以看出来，SequenceNumber 是一个64为的int，但是为了和ValueType组成新的部分，只试用了其中的56位，也就是7字节；

typedef uint64_t SequenceNumber;// We leave eight bits empty at the bottom so a type and sequence#
// can be packed together into 64-bits.
static const SequenceNumber kMaxSequenceNumber =((0x1ull << 56) - 1);

LookupKey用于查找相应的数据，其定义如下:

// A helper class useful for DBImpl::Get()
class LookupKey {public:// Initialize *this for looking up user_key at a snapshot with// the specified sequence number.LookupKey(const Slice& user_key, SequenceNumber sequence);~LookupKey();// Return a key suitable for lookup in a MemTable.Slice memtable_key() const { return Slice(start_, end_ - start_); }// Return an internal key (suitable for passing to an internal iterator)Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }// Return the user keySlice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }private:// We construct a char array of the form://    klength  varint32               <-- start_//    userkey  char[klength]          <-- kstart_//    tag      uint64//                                    <-- end_// The array is a suitable MemTable key.// The suffix starting with "userkey" can be used as an InternalKey.const char* start_;const char* kstart_;const char* end_;char space_[200];      // Avoid allocation for short keys// No copying allowedLookupKey(const LookupKey&);void operator=(const LookupKey&);
};inline LookupKey::~LookupKey() {if (start_ != space_) delete[] start_;
}

从LookupKey的构造函数如下：

LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {size_t usize = user_key.size();size_t needed = usize + 13;  // A conservative estimatechar* 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将sequenceNumber 和user_key进行捆绑了，这里面使用到了一个很重要的函数，EncodeVarint32，它将int整形转换为char数组，Varint是一种紧凑的表示数字的方法。它用一个或多个字节来表示一个数字，值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。比如对于int32类型的数字，一般需要4个byte来表示。但是采用Varint，对于很小的int32类型的数字，则可以用1个byte来表示。当然凡事都有好的也有不好的一面，采用Varint表示法，大的数字则需要5个byte来表示。从统计的角度来说，一般不会所有的消息中的数字都是大数，因此大多数情况下，采用Varint 后，可以用更少的字节数来表示数字信息。Varint中的每个byte的最高位bit有特殊的含义，如果该位为 1，表示后续的byte也是该数字的一部分，如果该位为0，则结束。其他的7 个bit都用来表示数字。因此小于128的数字都可以用一个byte表示。大于 128的数字，比如300，会用两个字节来表示：1010 1100 0000 0010

其中，EncodeVarint32的实现如下：

char* EncodeVarint32(char* dst, uint32_t v) {// Operate on characters as unsignedsunsigned char* ptr = reinterpret_cast<unsigned char*>(dst);static const int B = 128;if (v < (1<<7)) {*(ptr++) = v;} else if (v < (1<<14)) {*(ptr++) = v | B;*(ptr++) = v>>7;} else if (v < (1<<21)) {*(ptr++) = v | B;*(ptr++) = (v>>7) | B;*(ptr++) = v>>14;} else if (v < (1<<28)) {*(ptr++) = v | B;*(ptr++) = (v>>7) | B;*(ptr++) = (v>>14) | B;*(ptr++) = v>>21;} else {*(ptr++) = v | B;*(ptr++) = (v>>7) | B;*(ptr++) = (v>>14) | B;*(ptr++) = (v>>21) | B;*(ptr++) = v>>28;}return reinterpret_cast<char*>(ptr);
}

上面这段代码就是实现32整数转换为varint的过程；

回到LookupKey构造函数，可以看出三个私有变量 start kstart end在整个布局中的关系如下：

（start :  varint ）| (kstart : user data) | (sequence number : end)

这里需要提到的一句是，在lookupkey的构造函数中，采用的是最大的利用空间，我想这可能是由于对memtable而言， 内存中由于这几个字节所带来的内存额外开销很小，但是如果去计算varint长度会影响计算效率，所以直接采用最大的5个字节吧；

回到memtale的add函数，该函数的实现如下：

/**key value 组成的联合数组内存布局结构如下：*keysize + 8 (varint 32)*key bytes （keysize）*sequence+type (8)*value size (varint 32)*value bytes （value size） */
void MemTable::Add(SequenceNumber s, ValueType type,const Slice& key,const Slice& value) {// Format of an entry is concatenation of://  key_size     : varint32 of internal_key.size()//  key bytes    : char[internal_key.size()]//  value_size   : varint32 of value.size()//  value bytes  : char[value.size()]size_t key_size = key.size();size_t val_size = value.size();size_t internal_key_size = key_size + 8;const size_t encoded_len =VarintLength(internal_key_size) + internal_key_size +VarintLength(val_size) + val_size;char* buf = arena_.Allocate(encoded_len);char* p = EncodeVarint32(buf, internal_key_size);memcpy(p, key.data(), key_size);p += key_size;EncodeFixed64(p, (s << 8) | type);p += 8;p = EncodeVarint32(p, val_size);memcpy(p, value.data(), val_size);assert((p + val_size) - buf == encoded_len);table_.Insert(buf);
}

memtable主要使用table 和 arena进行数据的管理和内存的管理， table是skiplist结构，arena则是简单的内存管理模块；

类似的，可以看到get的实现如下;

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {Slice memkey = key.memtable_key();Table::Iterator iter(&table_);iter.Seek(memkey.data());//查找数据是否存在if (iter.Valid()) {// entry format is://    klength  varint32//    userkey  char[klength]//    tag      uint64//    vlength  varint32//    value    char[vlength]// Check that it belongs to same user key.  We do not check the// sequence number since the Seek() call above should have skipped// all entries with overly large sequence numbers.const char* entry = iter.key();uint32_t key_length;const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);//获得key 的位置以及长度if (comparator_.comparator.user_comparator()->Compare(Slice(key_ptr, key_length - 8),key.user_key()) == 0) {//对key根据add的逆操作进行解析// Correct user keyconst uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);switch (static_cast<ValueType>(tag & 0xff)) {case kTypeValue: {Slice v = GetLengthPrefixedSlice(key_ptr + key_length);value->assign(v.data(), v.size());return true;}case kTypeDeletion:*s = Status::NotFound(Slice());return true;}}}return false;
}

至此，memtable的基本操作就结束了；

可以看出，memtable对于采用了比较简单的方式，实现了数据的有序管理，采用varint 可以有效地减少磁盘上数据的空间节省；

这篇关于leveldb源码阅读-memtable的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---