LevelDB源码之SkipList原理
 
 
 
 分类： LevelDB源码系列
 2013-08-15 22:01 
 402人阅读 
 评论(0) 
 收藏 
 举报
 
 
 LevelDB源码系列
 
 
 
感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight()
 
 
 
 
 
  
 
   
 
    [cpp] 
    view plain
    copy 
    
 
    
 
   
 
  
 
  
 template<typename Key, class Comparator>  
 int SkipList<Key,Comparator>::RandomHeight() {  
   // Increase height with probability 1 in kBranching  
   static const unsigned int kBranching = 4;  
   int height = 1;  
   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  
     height++;  
   }  
   assert(height > 0);  
   assert(height <= kMaxHeight);  
   return height;  
 }  
 
 
 
 
 
 
插入操作：
 
 
 
 
 
  
 
   
 
    [cpp] 
    view plain
    copy 
    
 
    
 
   
 
  
 
  
 template<typename Key, class Comparator>  
 void SkipList<Key,Comparator>::Insert(const Key& key) {  
   // TODO(opt): We can use a barrier-free（(屏蔽，障碍/无障碍） variant(变种) of FindGreaterOrEqual()  
   // here since Insert() is externally synchronized.  
   //prev为各层的前置节点  
   Node* prev[kMaxHeight];  
   //查找插入的节点  
   Node* x = FindGreaterOrEqual(key, prev);  
   
   // Our data structure does not allow duplicate insertion  
   assert(x == NULL || !Equal(key, x->key));  
   //随机生成节点高度  
   int height = RandomHeight();  
   if (height > GetMaxHeight()) {  
     for (int i = GetMaxHeight(); i < height; i++) {  
       prev[i] = head_;  
     }  
     //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  
   
     // It is ok to mutate max_height_ without any synchronization  
     // with concurrent readers.  A concurrent reader that observes  
     // the new value of max_height_ will see either the old value of  
     // new level pointers from head_ (NULL), or a new value set in  
     // the loop below.  In the former case the reader will  
     // immediately drop to the next level since NULL sorts after all  
     // keys.  In the latter case the reader will use the new node.  
     //设置最大高度  
     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  
   }  
   //生成一个新的Node  
   x = NewNode(key, height);  
   for (int i = 0; i < height; i++) {  
     // NoBarrier_SetNext() suffices since we will add a barrier when  
     // we publish a pointer to "x" in prev[i].  
     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  
     prev[i]->SetNext(i, x);  
   }  
 }  
 
 
 查找操作： 
 
 
 
 
 
 
  
 
   
 
    [cpp] 
    view plain
    copy 
    
 
    
 
   
 
  
 
  
 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 != NULL) prev[level] = x;  
       if (level == 0) {  
         return next;  
       } else {  
         // Switch to next list  
         level--;  
       }  
     }  
   }  
 }  
 
 
 整个SkipList.h源码： 
 
 
 
 
 
 
  
 
   
 
    [cpp] 
    view plain
    copy 
    
 
    
 
   
 
  
 
  
 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.  
 // Use of this source code is governed by a BSD-style license that can be  
 // found in the LICENSE file. See the AUTHORS file for names of contributors.  
 //  
 // Thread safety  
 // -------------  
 //  
 // Writes require external synchronization, most likely a mutex.  
 // Reads require a guarantee that the SkipList will not be destroyed  
 // while the read is in progress.  Apart from that, reads progress  
 // without any internal locking or synchronization.  
 //  
 // Invariants:  
 //  
 // (1) Allocated nodes are never deleted until the SkipList is  
 // destroyed.  This is trivially guaranteed by the code since we  
 // never delete any skip list nodes.  
 //  
 // (2) The contents of a Node except for the next/prev pointers are  
 // immutable after the Node has been linked into the SkipList.  
 // Only Insert() modifies the list, and it is careful to initialize  
 // a node and use release-stores to publish the nodes in one or  
 // more lists.  
 //  
 // ... prev vs. next pointer ordering ...  
   
 #include <assert.h>  
 #include <stdlib.h>  
 #include "port/port.h"  
 #include "util/arena.h"  
 #include "util/random.h"  
 /** 
  * SkipList应用概率来保证平衡，平衡树采用严格的旋转来保证平衡 
  * 使用SkipList是的查找特定值得时间复杂度是O(logN)，与平衡树有着相同的复杂度，节省空间，每个检点平均1.33个指针 
  * leveldb的最高层数为12，只允许插入和修改，Record的key不允许重复，添加一个Sequene Num 
  * 规范：参数使用引用，返回值使用指针 
  * 
  */  
 namespace leveldb {  
   
 class Arena;  
   
 template<typename Key, class Comparator>  
 class SkipList {  
  private:  
   struct Node;  
   
  public:  
   // Create a new SkipList object that will use "cmp" for comparing keys,  
   // and will allocate memory using "*arena".  Objects allocated in the arena  
   // must remain allocated for the lifetime of the skiplist object.  
   explicit SkipList(Comparator cmp, Arena* arena);  
   
   // 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 {  
    public:  
     // Initialize an iterator over the specified list.  
     // The returned iterator is not valid.  
     explicit Iterator(const SkipList* list);  
   
     // 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_;  
     // Intentionally copyable  
   };  
   
   //跳表的最高level数  
  private:  
   enum { kMaxHeight = 12 };  
   
   // 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  
   
   inline int GetMaxHeight() const {  
     return static_cast<int>(  
         reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load()));  
   }  
   
   // Read/written only by Insert().  
   Random rnd_;  
   
   Node* NewNode(const Key& key, int height);  
   int RandomHeight();  
   bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }  
   
   // 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 NULL 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;  
   
   // No copying allowed  
   SkipList(const SkipList&);  
   void operator=(const SkipList&);  
 };  
   
 // Implementation details follow  
 template<typename Key, class Comparator>  
 struct SkipList<Key,Comparator>::Node {  
   explicit Node(const Key& k) : key(k) { }  
   
   Key const key;  
   
   // Accessors/mutators for links.  Wrapped in methods so we can  
   // add the appropriate barriers as necessary.  
   Node* Next(int n) {  
     assert(n >= 0);  
     // Use an 'acquire load' so that we observe a fully initialized  
     // version of the returned Node.  
     return reinterpret_cast<Node*>(next_[n].Acquire_Load());  
   }  
   void SetNext(int n, Node* x) {  
     assert(n >= 0);  
     // Use a 'release store' so that anybody who reads through this  
     // pointer observes a fully initialized version of the inserted node.  
     next_[n].Release_Store(x);  
   }  
   
   // No-barrier variants that can be safely used in a few locations.  
   Node* NoBarrier_Next(int n) {  
     assert(n >= 0);  
     return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());  
   }  
   void NoBarrier_SetNext(int n, Node* x) {  
     assert(n >= 0);  
     next_[n].NoBarrier_Store(x);  
   }  
   
  private:  
   // Array of length equal to the node height.  next_[0] is lowest level link.  
   port::AtomicPointer next_[1];  
 };  
   
 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);  
 }  
   
 template<typename Key, class Comparator>  
 inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {  
   list_ = list;  
   node_ = NULL;  
 }  
   
 template<typename Key, class Comparator>  
 inline bool SkipList<Key,Comparator>::Iterator::Valid() const {  
   return node_ != NULL;  
 }  
   
 template<typename Key, class Comparator>  
 inline const Key& SkipList<Key,Comparator>::Iterator::key() const {  
   assert(Valid());  
   return node_->key;  
 }  
   
 template<typename Key, class Comparator>  
 inline void SkipList<Key,Comparator>::Iterator::Next() {  
   assert(Valid());  
   node_ = node_->Next(0);  
 }  
   
 template<typename Key, class Comparator>  
 inline void SkipList<Key,Comparator>::Iterator::Prev() {  
   // Instead of using explicit "prev" links, we just search for the  
   // last node that falls before key.  
   assert(Valid());  
   node_ = list_->FindLessThan(node_->key);  
   if (node_ == list_->head_) {  
     node_ = NULL;  
   }  
 }  
   
 template<typename Key, class Comparator>  
 inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {  
   node_ = list_->FindGreaterOrEqual(target, NULL);  
 }  
   
 template<typename Key, class Comparator>  
 inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {  
   node_ = list_->head_->Next(0);  
 }  
   
 template<typename Key, class Comparator>  
 inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {  
   node_ = list_->FindLast();  
   if (node_ == list_->head_) {  
     node_ = NULL;  
   }  
 }  
   
 template<typename Key, class Comparator>  
 int SkipList<Key,Comparator>::RandomHeight() {  
   // Increase height with probability 1 in kBranching  
   static const unsigned int kBranching = 4;  
   int height = 1;  
   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  
     height++;  
   }  
   assert(height > 0);  
   assert(height <= kMaxHeight);  
   return height;  
 }  
   
 template<typename Key, class Comparator>  
 bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {  
   // NULL n is considered infinite  
   return (n != NULL) && (compare_(n->key, key) < 0);  
 }  
 /** 
  * 查找，从左向右，从上向下查找 
  */  
 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 != NULL) 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 == NULL || 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 == NULL) {  
       if (level == 0) {  
         return x;  
       } else {  
         // Switch to next list  
         level--;  
       }  
     } else {  
       x = next;  
     }  
   }  
 }  
 /** 
  * SkipList初始化 
  * 
  */  
 template<typename Key, class Comparator>  
 SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)  
     : compare_(cmp),  
       arena_(arena),  
       head_(NewNode(0 /* any key will do */, kMaxHeight)),  
       max_height_(reinterpret_cast<void*>(1)),  
       rnd_(0xdeadbeef) {  
   for (int i = 0; i < kMaxHeight; i++) {  
     head_->SetNext(i, NULL);  
   }  
 }  
 /** 
  * 插入一个新的key 
  * 
  */  
 template<typename Key, class Comparator>  
 void SkipList<Key,Comparator>::Insert(const Key& key) {  
   // TODO(opt): We can use a barrier-free（(屏蔽，障碍/无障碍） variant(变种) of FindGreaterOrEqual()  
   // here since Insert() is externally synchronized.  
   //prev为各层的前置节点  
   Node* prev[kMaxHeight];  
   //查找插入的节点  
   Node* x = FindGreaterOrEqual(key, prev);  
   
   // Our data structure does not allow duplicate insertion  
   assert(x == NULL || !Equal(key, x->key));  
   //随机生成节点高度  
   int height = RandomHeight();  
   if (height > GetMaxHeight()) {  
     for (int i = GetMaxHeight(); i < height; i++) {  
       prev[i] = head_;  
     }  
     //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  
   
     // It is ok to mutate max_height_ without any synchronization  
     // with concurrent readers.  A concurrent reader that observes  
     // the new value of max_height_ will see either the old value of  
     // new level pointers from head_ (NULL), or a new value set in  
     // the loop below.  In the former case the reader will  
     // immediately drop to the next level since NULL sorts after all  
     // keys.  In the latter case the reader will use the new node.  
     //设置最大高度  
     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  
   }  
   //生成一个新的Node  
   x = NewNode(key, height);  
   for (int i = 0; i < height; i++) {  
     // NoBarrier_SetNext() suffices since we will add a barrier when  
     // we publish a pointer to "x" in prev[i].  
     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  
     prev[i]->SetNext(i, x);  
   }  
 }  
 /** 
  * 包含 
  */  
 template<typename Key, class Comparator>  
 bool SkipList<Key,Comparator>::Contains(const Key& key) const {  
   Node* x = FindGreaterOrEqual(key, NULL);  
   if (x != NULL && Equal(key, x->key)) {  
     return true;  
   } else {  
     return false;  
   }  
 }  
   
 }  // namespace leveldb  
 
 
 

 
LevelDB源码解读
 
提供的功能
read and write
Group commit
sequence number
    
delete
Atomic Updates
同步写Synchronous Writes
遍历 iteration
快照 Snapshots
Slice
比较器 Comparators
   
concurrency保证
compaction
LevelDB的性能优化参数
Block size
Compression
Cache
键分布 Key Layout
Filters
校验和 Checksum
Approximate Sizes
Environment
porting
   
参考链接
 

 
 
提供的功能
 
leveldb index
 
前面打开关闭数据库的方式略过
 
read and write
 
std::string value;
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);
if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);
 
写流程： 
  
找到合适的memtable(skiplist)并写入数据，如果memtable写完并且immutableTable还未完成持久化，或者L0文件太多，则等待。如果memtable满了，则换一个memtable，并触发compaction
写日志，下刷日志
写memtable
 
读流程： 
  
首先查找memtable，再查找immutable memtable
如果没有，查找下面所有持久化的levelVersion::Get，逐层向下搜索。搜索方法的策略是并不是遍历每一个sstable，而是先看需要查找的key是否落在sstable的范围内（每个sstable记录begin/end key），如果落在，对sstable搜索。
 
后台线程也会按需做compaction。通过MaybeScheduleCompaction()函数判断。
 
注意，日志只是为了保证内存中的数据不丢失（memtable和immutable），内存数据下刷完成之后，日志就可以删掉了
 
Group commit
 
为了防止写日志在高并发下成为瓶颈，LevelDB将不同线程同时产生的日志数据聚合在一起写入文件并进行一次fsync()，而非对每个线程写的数据进行单独fsync()。这个做法称为group commit。
 
具体的commit见added group commit
 
具体的实现上，通过在构造writer的时候控制mutex，只有一个线程会顺利进行BuildBatchGroup，而其他没有拿到mutex的线程会在随后将日志操作写进队列。重复这个过程，最终只有排在队首的线程会真正flush日志，其他的线程都在等待。
 
sequence number
 
sequence number 是一个由VersionSet直接持有的全局的编号，每次写入（注意批量写入时sequence number是相同的），就会递增。key的排序以及snapshot都要依赖它。
 
当我们进行Get操作时，我们只需要找到目标key，同时其sequence number 小于等于sequence number：
 
普通的读取，sepcific sequence number =last sequence number
snapshot读取，sepcific sequenc number =snapshot sequence number
 
delete
 
delete仍然是通过write batch的形式向存储引擎下发的。只不过ValueType是特殊的kTypeDeletion。但是delete在compact的时候需要特殊对待
 
Atomic Updates
 
将一系列的操作作为一个batch，提供原子性。这里猜测做法是在WAL中增加一些特殊的LogEntry如Transaction begin/end等。
 
#include "leveldb/write_batch.h"
...
std::string value;
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
if (s.ok()) {
  leveldb::WriteBatch batch;
  batch.Delete(key1);
  batch.Put(key2, value);
  s = db->Write(leveldb::WriteOptions(), &batch);
}
 
同步写Synchronous Writes
 
leveldb::WriteOptions write_options;
write_options.sync = true;
db->Put(write_options, ...);
 
异步写比同步写块上千倍，但是默认的异步写有可能导致丢数据（系统crash的时候异步写还没完成）
 
 
 
Note that a crash of just the writing process (i.e., not a reboot) will not cause any loss since even when sync is false, an update is pushed from the process memory into the operating system before it is considered done.
 
 
如果系统希望避免丢数据，可以用以下几种方式实现：
 
只要上层应用知道当前写的数据是什么，那么就算crash了也没关系，重试就行了
另外可以每隔N个async write写一个sync write作为checkpoint，如果crash了，从上一个checkpoint处开始写就行了。
另外可以用atomic write提供的batch写。
 
遍历 iteration
 
scan table
 
leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
for (it->SeekToFirst(); it->Valid(); it->Next()) {
  cout << it->key().ToString() << ": "  << it->value().ToString() << endl;
}
assert(it->status().ok());  // Check for any errors found during the scan
delete it;
 
范围搜索
 
for (it->Seek(start);
   it->Valid() && it->key().ToString() < limit;
   it->Next()) {
  ...
}
 
倒序，注意，这里和正序的时间复杂度不一致。
 
for (it->SeekToLast(); it->Valid(); it->Prev()) {
  ...
}
 
快照 Snapshots
 
快照只读，并且读时可以不用加锁，我们使用DB:GetSnapshot()创建快照：
 
leveldb::ReadOptions options;
options.snapshot = db->GetSnapshot();
... apply some updates to db ...
leveldb::Iterator* iter = db->NewIterator(options);
... read using iter to view the state when the snapshot was created ...
delete iter;
db->ReleaseSnapshot(options.snapshot);
 
Slice
 
Slice用来存放levelDB存储的数据类型，它存放数据的length和指针。使用Slice是一种比std::string更为轻量化的方法。LevelDB不允许返回末尾是null的C-Style字符串，LevelDB允许字符串含有\0。另外slice持有的是指针，而不是对象，所以要注意指针指向的对象的生命周期
 
class LEVELDB_EXPORT Slice {
 public:
  // 各种构造函数，成员函数...

 private:
  const char* data_;
  size_t size_;
};
 
leveldb::Slice s1 = "hello";  // null-termicated C-style string
std::string str("world");  // C++ string
leveldb::Slice s2 = str;

// Slice输出为std::string
std::string str = s1.ToString();
assert(str == std::string("hello"));
 
比较器 Comparators
 
levelDB可以针对自定义的Slice数据类型使用自定义的比较器。只要在打开数据的时候指定比较器options.comparator = &cmp;就行了。该比较器的名字会在数据库初始化的时候持久化进数据库，如果后面使用不同命的比较器打开数据库，会失败。
 
concurrency保证
 
每个database（文件系统的一个对应目录）只能同一时刻被一个进程打开，level启动的时候会获取一个文件锁。在一个进程内，DB对象leveldb::DB可以被多个线程并发访问。由levelDB负责线程间同步。当然如果要做事务的话（writebatch）可能要外部进行并发控制（加锁）。
 
compaction
 
之前已经谈到了memtable、immutable、各个level。除了l0中每个run是可以重叠的（其实l0就是一个个的memtable），其他level都是只有一个run，被分配成很多2M的小文件。
 
做compaction的时候，只有l0层是将所有文件一起合并，其它层都是以2M为单位进行合并，写入合并的文件，丢弃之前的文件。
 
LevelDB Compaction分三种：
 
minor compaction 
  
将immutable memtable dump成sstable
 
major compaction 
  
如果某个level文件过多或过大、seek的次数过多都会引发Major compaction，每一层都有一个target size，通过比较算出一个score，然后对score较高的某个level的sstable进行major compaction
通过PickLevelForMemTableOutput判断产生文件位于哪一层
 
Manual Compaction 
  
通过接口DBImpl::CompactRange(const Slice begin, const Slice end)接口调用
可以看到，如果某层一直没有进行Major compaction，可能会造成compaction在高层的数据一直无法和低层的delete进行merge，导致数据无法被回收。这是可以主动调用Manual Compaction，手动对某个范围进行compaction，也就是说，通过一次全量的compaction，消除delete特别是range delete带来的负面影响
数据无法被回收只是影响的一方面，在数据库应用中，delete会导致统计信息不准，影响sql优化器的决策
 
 
LevelDB的性能优化参数
 
Block size
 
levelDB默认最小存储单元Block默认是4K（压缩前），如果上层应用经常做全表扫描的话，可以增大Block size。如果上层应用经常做各种小的随机读，可以缩小Block size。实践表明Block大于几M或者小于1K是没有任何益处。有一点要注意的是，Blocksize越大Compression越高效。
 
Compression
 
每个block在持久化之前默认都需要被压缩。当然用户也可以显式指定不需要压缩
 
leveldb::Options options;
options.compression = leveldb::kNoCompression;
... leveldb::DB::Open(options, name, ...) ....
 
Cache
 
LevelDB可以指定Cache的大小，Cache中存放的是已经持久化的数据，注意这个cache不是文件系统的buffer cache。buffer cache存储的是已经被压缩的数据，levelDB中的cache存储的是解压后的数据。
 
如果上层应用进行一系列的读例如table scan，我们希望将cache disable掉，以防上面的cache全被刷掉，下面的代码，就是在当前的遍历中disable掉cache。
 
leveldb::ReadOptions options;
options.fill_cache = false;
leveldb::Iterator* it = db->NewIterator(options);
for (it->SeekToFirst(); it->Valid(); it->Next()) {
  ...
}
 
键分布 Key Layout
 
LevelDB中的键是顺序分布的，所以可以将经常访问的key放一起，不长访问的key放一起。
 
Filters
 
因为LevelDB使用了LSM tree，因此一个简单的Get()操作可能会设计多个对磁盘的read，为了优化读性能，LevelDB使用了布隆过滤器(Bloom Filter)判断某个键是否存在。
 
leveldb::Options options;
options.filter_policy = NewBloomFilterPolicy(10);
leveldb::DB* db;
leveldb::DB::Open(options, "/tmp/testdb", &db);
... use the database ...
delete db;
delete options.filter_policy;
 
实际应用中，我们需要对过滤器的大小和过滤器的精度进行取舍。这部分的代码放在leveldb/filter_policy.h
 
校验和 Checksum
 
LevelDB使用Checksum校验持久化数据，ReadOptions::verify_checksums将对每一个read都做校验。Options::paranoid_checks将在数据库打开时校验整个数据库的Checksum
 
如果发现数据损坏，可以使用leveldb::RepairDB来修复数据。
 
Approximate Sizes
 
使用GetApproximateSizes用来获取大概占用的空间
 
leveldb::Range ranges[2];
ranges[0] = leveldb::Range("a", "c");
ranges[1] = leveldb::Range("x", "z");
uint64_t sizes[2];
db->GetApproximateSizes(ranges, 2, sizes);
 
Environment
 
LevelDB可以使用用户自定义的环境参数、接口函数，例如，用户可以在磁盘IO路径上加入一些delay
 
class SlowEnv : public leveldb::Env {
  ... implementation of the Env interface ...
};

SlowEnv env;
leveldb::Options options;
options.env = &env;
Status s = leveldb::DB::Open(options, ...);
 
porting
 
LevelDB可以引入不同的系统实现，例如：mutex、condition variable等。从而在不同的系统上实现LevelDB。
 
参考链接
 
[leveldb] 3.put/delete操作
LevelDB设计与实现 - 基础篇

 
 
 
 阅读本文可参考：
 
 LevelDB源码分析之一：coding
 
 
 LevelDB源码分析之二：comparator
 
 LevelDB源码分析之三：arena
 
 LevelDB源码分析之四：AtomicPointer
 
 LevelDb源码分析之五：skiplist（1）
 
 LevelDb源码分析之六：skiplist（2）
 
 
 LevelDB源码分析之七：Random
 
        在LevelDB中所有KV数据都是存储在Memtable，Immutable Memtable和SSTable中的，Immutable Memtable从结构上讲和Memtable是完全一样的，区别仅仅在于其是只读的，不允许写入操作，而Memtable则是允许写入和读取的。当Memtable写入的数据占用内存到达指定数量，则自动转换为Immutable Memtable，等待Dump到磁盘中，系统会自动生成新的Memtable供写操作写入新数据，理解了Memtable，那么Immutable Memtable自然不在话下。
         LevelDB的MemTable提供了将KV数据写入，删除以及读取KV记录的操作接口，但是事实上Memtable并不存在真正的删除操作，删除某个Key的Value在Memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作是延后的，会在以后的Compaction过程中去掉这个KV。 需要注意的是，LevelDB的Memtable中KV对是根据Key大小有序存储的，在系统插入新的KV时，LevelDB要把这个KV插到合适的位置上以保持这种Key有序性。其实，LevelDb的Memtable类只是一个接口类，真正的操作是通过背后的SkipList来做的，包括插入操作和读取操作等，所以Memtable的核心数据结构是一个SkipList。

 
        Memtable主要作用是对skiplist、arena、comparator进行组合和管理，接口函数屏蔽了底层操作，对使用者更加优雅。
 
一.构造函数
 
 
MemTable::MemTable(const InternalKeyComparator& cmp)
    : comparator_(cmp),
      refs_(0),
      table_(comparator_, &arena_) {
}
构造函数对私有成员变量进行了初始化，table_是SkipList类型，将&aerna_当做key传入，arena_是Arena类型。 
 
二.内存估算函数
 
 
size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }
这里直接调用的是Arena类的MemoryUsage方法，该方法返回整个内存池使用内存的总大小（不精确）。 
 
三.添加函数
 
 
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();
  // 参考LevelDB源码分析之二：comparator中关于Internal Key的介绍，
  // 因为Internal Key由user_key、sequence和type三个字段组成，user_key
  // 也就是这里的key，sequence和type会打包成一个uint64_t类型的数据，
  // 所以这里的长度为key_size+8
  size_t internal_key_size = key_size + 8;
  // 参考LevelDB源码分析之一：coding，为了节约空间，数字都是编码存储的，
  // VarintLength方法求出的是编码后的长度。关于encoded_len的组成详见下图。
  const size_t encoded_len =
      VarintLength(internal_key_size) + internal_key_size +
      VarintLength(val_size) + val_size;
  // 分配内存
  char* buf = arena_.Allocate(encoded_len);
  // 编码internal_key_size，编码后存放到buf中，p指向internal_key_size的结尾
  char* p = EncodeVarint32(buf, internal_key_size);
  // 将key拷贝到buf中，占用key_size大小
  memcpy(p, key.data(), key_size);
  p += key_size;
  // 将sequence和type打包后存放到buf中，大小为8字节，EncodeFixed64只是进行了简单的拷贝（考虑的大端或小端）。
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  // 编码val_size，编码后存放到buf中，p指向val_size的结尾
  p = EncodeVarint32(p, val_size);
  // 将value拷贝到buf中，占用val_size大小
  memcpy(p, value.data(), val_size);
  // 判断存储完后所占内存的大小，是否与初始计算的大小相等
  assert((p + val_size) - buf == encoded_len);
  // 插入到SkipList中
  table_.Insert(buf);
}
一个完整的buf内容如下图所示。 
 

 
 
四.获取函数
 
 
// 如果能找到key对应的value, 将该value存储到*value参数中，返回值为true。
// 如果这个key中的有删除标识,存放一个NotFound()错误到*status参数中，返回值为true。
// 否则返回值为false
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  // 得到memkey，memkey中实际上包含了klength|userkey|tag，也就是说它包含了internal_key_size
  // 和internal_key
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  // 找到SkipList中大于等于memkey的结点
  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;
	// 取出klength，并将key_ptr指到klength之后
	// 为什么加5？参考LevelDB源码分析之一：coding
    const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
	// 比较结点中的userkey和LookupKey中的userkey是否相等，如果相等，说明找到了这个结点。
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8),
            key.user_key()) == 0) {
      // 获取tag，tag等于(sequence<<8)|type
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
	  // 取出type并判断
      switch (static_cast<ValueType>(tag & 0xff)) {
        case kTypeValue: {
		  // 取出value的大小和内容
          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;
}

}
获取函数的第一个参数是LookupKey类型，LookupKey是一个帮助类，通过它可以更方便的对Memtable进行操作。由于LookupKey的官方注释特别详细，这里就不分析了。 
 

 
 
参考链接：http://www.360doc.com/content/14/0325/16/15064667_363619194.shtml
 

 
 

 
 
 
 
 

 
 

 
 
     
 

 

leveldb是key-value模式数据库，出自Jeff Dean和Sanjay Ghemawat之手，适用于顺序读写场景。各大厂均有以leveldb为积木搭建的成熟数据库产品，如google的bigtable，baidu的tera等，在工程实践上取得了广泛成功。leveldb以其良好的编程风格和设计理念为人称道，阅读leveldb源码对提升自己的编程能力大有裨益。
 
leveldb源码地址
 
https://github.com/google/leveldb
 
leveldb源码目录结构
 
 
db/
 
table/
 
util/
 
include/leveldb/
 
doc/
 
table/存放sstable相关实现，sstable即sorted string table，是leveldb的数据文件
 
db/存放数据库核心操作实现
 
util/存放公共方法集
 
include/leveldb/存放头文件
 
doc/下存放文档，描述诸如sstable文件格式、log文件格式等
 
leveldb源码阅读顺序
 
1、数据结构和基础组件
 
字符串 include/leveldb/slice.h
 
跳跃表 skiplist.h
 
整型 util/coding.h util/coding.cc
 
LRU缓存 util/cache.cc
 
2、log文件相关实现
 
文件格式：db/log_format.h
 
读文件：db/log_reader.h db/log_reader.cc
 
写文件：db/log_writer.h db/log_writer.cc
 
3、memtable相关实现
 
db/memtable.h db/memtable.cc
 
4、sorted string table相关实现
 
table/目录下代码，包含：
 
sst文件构建：block_builder.h block_builder.cc block.h block.cc
 
过滤块构建：flilter_block.h filter_blok.cc
 
迭代器：iterator_wrapper.h iterator.cc two_level_iterator.h two_level_iterator.cc
 
5、db核心实现
 
db/目录下代码，包含：
 
builder.h builder.cc
 
db格式：dbformat.h dbformat.cc
 
db实现：db_impl.h db_impl.cc
 
db遍历：db_iter.h db_iter.cc
 
table缓存：table_cache.h table_cache.cc
 
版本管理：vesion_edit.h version_edit.cc version_set.h version_set.cc
 
合并写：write_batch_internal.h write_batch.cc