LevelDB源码分析-MemTable
MemTable（db/memtable.h db/memtable.cc db/skiplist.h）
LevelDB中存储在内存中的那部分KV数据都存储在memtable中，而memtable中的数据实际是用跳表来存储的。MemTable使用Arena进行内存管理，并提供了添加、查找、迭代器的接口，而实际上这些接口都是调用SkipList的添加和迭代器接口来实现的。
MemTable类
MemTable类的声明：
class MemTable
{
public:
// ...
// Increase reference count.
void Ref() { ++refs_; }
// Drop reference count. Delete if no more references exist.
void Unref()
{
--refs_;
assert(refs_ >= 0);
if (refs_ <= 0)
{
delete this;
}
}
// ...
// Return an iterator that yields the contents of the memtable.
//
// The caller must ensure that the underlying MemTable remains live
// while the returned iterator is live. The keys returned by this
// iterator are internal keys encoded by AppendInternalKey in the
// db/format.{h,cc} module.
Iterator *NewIterator();
// Add an entry into memtable that maps key to value at the
// specified sequence number and with the specified type.
// Typically value will be empty if type==kTypeDeletion.
void Add(SequenceNumber seq, ValueType type,
const Slice &key,
const Slice &value);
// If memtable contains a value for key, store it in *value and return true.
// If memtable contains a deletion for key, store a NotFound() error
// in *status and return true.
// Else, return false.
bool Get(const LookupKey &key, std::string *value, Status *s);
private:
// ...
struct KeyComparator
{
const InternalKeyComparator comparator;
explicit KeyComparator(const InternalKeyComparator &c) : comparator(c) {}
int operator()(const char *a, const char *b) const;
};
friend class MemTableIterator;
friend class MemTableBackwardIterator;
typedef SkipList<const char *, KeyComparator> Table;
KeyComparator comparator_;
int refs_;
Arena arena_;
Table table_;
// ...
};
MemTable的成员变量
table_变量即为实际存储KV数据的跳表，arena_用于内存管理，refs_用于引用计数，comparator_用于key之间的比较。
其中最简单的是ref_，调用Ref()函数则增加引用计数，调用Unref()函数减少引用次数，并且当引用次数为0时，Unref()函数会将对象自身delete。
Arena类
然后是arena_。Arena类为：
class Arena
{
public:
// ...
// Return a pointer to a newly allocated memory block of "bytes" bytes.
char *Allocate(size_t bytes);
// Allocate memory with the normal alignment guarantees provided by malloc
char *AllocateAligned(size_t bytes);
// ...
private:
char *AllocateFallback(size_t bytes);
char *AllocateNewBlock(size_t block_bytes);
// Allocation state
char *alloc_ptr_;
size_t alloc_bytes_remaining_;
// Array of new[] allocated memory blocks
std::vector<char *> blocks_;
// Total memory usage of the arena.
port::AtomicPointer memory_usage_;
// ...
};
alloc_ptr_指向当前可以被分配的内存起始位置（在某一个block中），alloc_bytes_remaining_为当前可以被分配的内存的大小，blocks_中包含了指向每一个block的指针，memory_usage_为使用的内存总量，并且使用了AtomicPointer，可以通过内存屏障或者c++的atomic接口实现原子操作。
Arena类提供的方法主要有两个，一个是Allocate(size_t bytes)：
inline char *Arena::Allocate(size_t bytes)
char *Arena::AllocateFallback(size_t bytes)
char *Arena::AllocateNewBlock(size_t block_bytes)
{
char *result = new char[block_bytes];
blocks_.push_back(result);
memory_usage_.NoBarrier_Store(
reinterpret_cast<void *>(MemoryUsage() + block_bytes + sizeof(char *)));
return result;
}
Allocate(size_t bytes)函数分配的内存不保证对齐。首先检查当前可以被分配的内存空间是否足够，如果够的话，直接将从alloc_ptr_指向的位置开始的bytes个字节分配给调用者，并移动alloc_ptr_指向新的位置，调整alloc_bytes_remaining_：
// The semantics of what to return are a bit messy if we allow
// 0-byte allocations, so we disallow them here (we don't need
// them for our internal use).
assert(bytes > 0);
if (bytes <= alloc_bytes_remaining_)
{
char *result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
}
如果不够，就调用AllocateFallback(size_t bytes)函数：
return AllocateFallback(bytes);
AllocateFallback(size_t bytes)函数首先检查bytes大小是否超过1/4个block，如果超过，则直接调用AllocateNewBlock(size_t block_bytes)函数分配一个新的block给调用者，并且这个新的block中除了当前的bytes个字节，其余部分将不会被使用，而alloc_ptr_的指向却不变，也就是说当前可以被分配的内存保持不变，因为此时剩余空间至少为1/4个block，这样设计就可以减少大块的内存碎片：
if (bytes > kBlockSize / 4)
{
// Object is more than a quarter of our block size. Allocate it separately
// to avoid wasting too much space in leftover bytes.
char *result = AllocateNewBlock(bytes);
return result;
}
如果没有超过1/4个block，就分配一个新的block，并且将alloc_ptr_指向新的block中的剩余空间：
// We waste the remaining space in the current block.
alloc_ptr_ = AllocateNewBlock(kBlockSize);
alloc_bytes_remaining_ = kBlockSize;
char *result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
还有一个内存分配函数是AllocateAligned(size_t bytes)：
char *Arena::AllocateAligned(size_t bytes)
这个函数保证内存对齐。首先，以下代码会调整alloc_ptr_的位置使其对齐：
const int align = (sizeof(void *) > 8) ? sizeof(void *) : 8;
assert((align & (align - 1)) == 0); // Pointer size should be a power of 2
size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);
size_t slop = (current_mod == 0 ? 0 : align - current_mod);
size_t needed = bytes + slop;
char *result;
剩下的代码和Allocate(size_t bytes)中实现一致：
if (needed <= alloc_bytes_remaining_)
{
result = alloc_ptr_ + slop;
alloc_ptr_ += needed;
alloc_bytes_remaining_ -= needed;
}
else
{
// AllocateFallback always returned aligned memory
result = AllocateFallback(bytes);
}
assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0);
return result;
SkipList类
最后是最重要的跳表，跳表由SkipList类实现：
template <typename Key, class Comparator>
class SkipList
{
private:
struct Node;
public:
// ...
// Insert key into the list.
// REQUIRES: nothing that compares equal to key is currently in the list.
void Insert(const Key &key);
// Returns true iff an entry that compares equal to key is in the list.
bool Contains(const Key &key) const;
// Iteration over the contents of a skip list
class Iterator
{
// ...
};
private:
// ...
// Immutable after construction
Comparator const compare_;
Arena *const arena_; // Arena used for allocations of nodes
Node *const head_;
// Modified only by Insert(). Read racily by readers, but stale
// values are ok.
port::AtomicPointer max_height_; // Height of the entire list
// ...
Node *NewNode(const Key &key, int height);
// ...
// Return true if key is greater than the data stored in "n"
bool KeyIsAfterNode(const Key &key, Node *n) const;
// Return the earliest node that comes at or after key.
// Return nullptr if there is no such node.
//
// If prev is non-null, fills prev[level] with pointer to previous
// node at "level" for every level in [0..max_height_-1].
Node *FindGreaterOrEqual(const Key &key, Node **prev) const;
// Return the latest node with a key < key.
// Return head_ if there is no such node.
Node *FindLessThan(const Key &key) const;
// Return the last node in the list.
// Return head_ if list is empty.
Node *FindLast() const;
// ...
};
跳表中主要有四个成员，一个是compare_用于key的比较，一个是arena_用于内存管理，一个是head_指向跳表开头的节点，最后一个是max_height_为跳表最大的高度。
当然跳表中还需要两个类和结构，一个是Iterator类，用于跳表的遍历，另一个是Node结构，用于表示跳表中的节点。
Node结构
首先是Node结构：
template <typename Key, class Comparator>
struct SkipList<Key, Comparator>::Node
{
// ...
Key const key;
// Accessors/mutators for links. Wrapped in methods so we can
// add the appropriate barriers as necessary.
Node *Next(int n)
// ...
void SetNext(int n, Node *x)
// ...
// No-barrier variants that can be safely used in a few locations.
Node *NoBarrier_Next(int n)
// ...
void NoBarrier_SetNext(int n, Node *x)
// ...
private:
// Array of length equal to the node height. next_[0] is lowest level link.
port::AtomicPointer next_[1];
};
Node中key存储了节点中实际存储的KV值，next_为一个变长数组（struct最后一个元素如果是数组，则长度可变），用于存储该节点在不同高度的链表上指向下一个节点的指针。
创建Node使用了一个很神奇的函数：
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node *
SkipList<Key, Comparator>::NewNode(const Key &key, int height)
{
char *mem = arena_->AllocateAligned(
sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
return new (mem) Node(key);
}
这个函数首先分配了一块对齐的内存，然后通过new (mem) Node(key)这个语句创建一个节点，我也不是很懂。
Iterator类
其次是iterator类：
// Iteration over the contents of a skip list
class Iterator
{
public:
// ...
// Returns true iff the iterator is positioned at a valid node.
bool Valid() const;
// Returns the key at the current position.
// REQUIRES: Valid()
const Key &key() const;
// Advances to the next position.
// REQUIRES: Valid()
void Next();
// Advances to the previous position.
// REQUIRES: Valid()
void Prev();
// Advance to the first entry with a key >= target
void Seek(const Key &target);
// Position at the first entry in list.
// Final state of iterator is Valid() iff list is not empty.
void SeekToFirst();
// Position at the last entry in list.
// Final state of iterator is Valid() iff list is not empty.
void SeekToLast();
private:
const SkipList *list_;
Node *node_;
// ...
};
这个类主要有两个成员，一个list_指向迭代的跳表，node_指向当前迭代的节点。
对跳表的遍历操作需要获取一个Iterator类型的迭代器，然后通过调用Iterator类提供的接口函数对跳表进行遍历。而Iterator类提供的接口函数实际上通过调用SkipList类提供的私有接口函数实现。
SkipList类的私有接口函数如下：
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node *SkipList<Key, Comparator>::FindGreaterOrEqual(const Key &key, Node **prev)
const
{
Node *x = head_;
int level = GetMaxHeight() - 1;
while (true)
{
Node *next = x->Next(level);
if (KeyIsAfterNode(key, next))
{
// Keep searching in this list
x = next;
}
else
{
if (prev != nullptr)
prev[level] = x;
if (level == 0)
{
return next;
}
else
{
// Switch to next list
level--;
}
}
}
}
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node *
SkipList<Key, Comparator>::FindLessThan(const Key &key) const
{
Node *x = head_;
int level = GetMaxHeight() - 1;
while (true)
{
assert(x == head_ || compare_(x->key, key) < 0);
Node *next = x->Next(level);
if (next == nullptr || compare_(next->key, key) >= 0)
{
if (level == 0)
{
return x;
}
else
{
// Switch to next list
level--;
}
}
else
{
x = next;
}
}
}
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node *SkipList<Key, Comparator>::FindLast()
const
{
Node *x = head_;
int level = GetMaxHeight() - 1;
while (true)
{
Node *next = x->Next(level);
if (next == nullptr)
{
if (level == 0)
{
return x;
}
else
{
// Switch to next list
level--;
}
}
else
{
x = next;
}
}
}
这三个函数的实现比较简单，类似于链表的遍历，就不做具体分析了。
另外，跳表还有两个接口函数用于插入和检查是否包含某个key，这两个函数的实现也使用了跳表的私有接口函数：
template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key &key)
template <typename Key, class Comparator>
bool SkipList<Key, Comparator>::Contains(const Key &key) const
MemTable成员函数
分析完以上这些，我们开始分析MemTable提供的接口函数：
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);
}
Add函数将key和value组成key_size | sequencenumber | type | key | value_size | value这样的形式，然后调用SkipList类提供的Insert函数插入跳表中。
bool MemTable::Get(const LookupKey &key, std::string *value, Status *s)
Get函数先用跳表的迭代器找到包含key的节点：
Slice memkey = key.memtable_key();
Table::Iterator iter(&table_);
iter.Seek(memkey.data());
然后将节点中的数据解码后封装为Slice存入value：
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);
if (comparator_.comparator.user_comparator()->Compare(
Slice(key_ptr, key_length - 8),
key.user_key()) == 0)
{
// Correct user key
const 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;
MemTableIterator类
MemTable还封装了一个MemTableIterator类用于MemTable的迭代：
class MemTableIterator : public Iterator
{
public:
explicit MemTableIterator(MemTable::Table *table) : iter_(table) {}
virtual bool Valid() const { return iter_.Valid(); }
virtual void Seek(const Slice &k) { iter_.Seek(EncodeKey(&tmp_, k)); }
virtual void SeekToFirst() { iter_.SeekToFirst(); }
virtual void SeekToLast() { iter_.SeekToLast(); }
virtual void Next() { iter_.Next(); }
virtual void Prev() { iter_.Prev(); }
virtual Slice key() const { return GetLengthPrefixedSlice(iter_.key()); }
virtual Slice value() const
{
Slice key_slice = GetLengthPrefixedSlice(iter_.key());
return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());
}
virtual Status status() const { return Status::OK(); }
private:
MemTable::Table::Iterator iter_;
std::string tmp_; // For passing to EncodeKey
// No copying allowed
MemTableIterator(const MemTableIterator &);
void operator=(const MemTableIterator &);
};
遍历MemTable就需要获得一个MemTableIterator类的迭代器，然后通过调用MemTableIterator类提供的接口函数进行遍历。MemTableIterator类其实就是实现了对跳表迭代器的封装，成员为一个跳表的迭代器iter_，接口函数通过调用跳表迭代器的接口函数实现。
227 Love u
