首页 > 数据库技术 > 详细

leveldb memtable

时间：2014-08-11 11:41:02      阅读：523      评论：0      收藏：0      [点我收藏+]

memtable常驻于内存，需要按照key进行排序，通常意义上的话，可以使用二叉查找树来实现，跟进一步可以使用红黑树保证树的平衡，但是leveldb中使用了另外的一种数据结构：跳表Skip List。

memtable声明在db/memtable.h中，定义如下：

view plain
  1. class MemTable  
  2. {  
  3. public:  
  4.     // MemTables are reference counted.  The initial reference count  
  5.     // is zero and the caller must call Ref() at least once.  
  6.     explicit MemTable(const InternalKeyComparator& comparator);  
  7.   
  8.     // Increase reference count.  
  9.     void Ref()  
  10.     {  
  11.         ++refs_;  
  12.     }  
  13.   
  14.     // Drop reference count.  Delete if no more references exist.  
  15.     void Unref()  
  16.     {  
  17.         --refs_;  
  18.         assert(refs_ >= 0);  
  19.         if (refs_ <= 0)     // 如果引用数为0,删除该对象  
  20.         {  
  21.             delete this;  
  22.         }  
  23.     }  
  24.   
  25.     // Returns an estimate of the number of bytes of data in use by this  
  26.     // data structure.  
  27.     //  
  28.     // REQUIRES: external synchronization to prevent simultaneous  
  29.     // operations on the same MemTable.  
  30.     // 返回使用的内存量  
  31.     size_t ApproximateMemoryUsage();  
  32.   
  33.     // Return an iterator that yields the contents of the memtable.  
  34.     //  
  35.     // The caller must ensure that the underlying MemTable remains live  
  36.     // while the returned iterator is live.  The keys returned by this  
  37.     // iterator are internal keys encoded by AppendInternalKey in the  
  38.     // db/format.{h,cc} module.  
  39.     // 返回迭代器，遍历该memtable  
  40.     Iterator* NewIterator();  
  41.   
  42.     // Add an entry into memtable that maps key to value at the  
  43.     // specified sequence number and with the specified type.  
  44.     // Typically value will be empty if type==kTypeDeletion.  
  45.     // 由于采用了LSM结构，所以没有数据删除，只有数据的添加，如果type=  
  46.     // kTypeDeletion，这时value为空  
  47.     // sequence number：递增的序列，用于数据的恢复  
  48.     void Add(SequenceNumber seq, ValueType type,  
  49.              const Slice& key,  
  50.              const Slice& value);  
  51.   
  52.     // If memtable contains a value for key, store it in *value and return true.  
  53.     // If memtable contains a deletion for key, store a NotFound() error  
  54.     // in *status and return true.  
  55.     // Else, return false.  
  56.     // 查询该memtable  
  57.     bool Get(const LookupKey& key, std::string* value, Status* s);  
  58.   
  59. private:  
  60.     // 私有化析构函数，这样保证只有Unref()方法能够删除该对象  
  61.     ~MemTable();  // Private since only Unref() should be used to delete it  
  62.   
  63.     struct KeyComparator  
  64.     {  
  65.         const InternalKeyComparator comparator;  
  66.         explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { }  
  67.         int operator()(const char* a, const char* b) const;  
  68.     };  
  69.     // 迭代器  
  70.     friend class MemTableIterator;  
  71.     friend class MemTableBackwardIterator;  
  72.   
  73.     // 跳表类型？作用  
  74.     typedef SkipList<const char*, KeyComparator> Table;  
  75.   
  76.     // key比较器  
  77.     KeyComparator comparator_;  
  78.     // 对象被引用的数量，如果该值为0，则删除该对象  
  79.     int refs_;  
  80.   
  81.     // 内存区域的封装  
  82.     Arena arena_;  
  83.     // 使用跳表数据结构保证内存数据按照key排序  
  84.     Table table_;  
  85.   
  86.     // No copying allowed  
  87.     MemTable(const MemTable&);  
  88.     void operator=(const MemTable&);  
  89. };  


这里面有几个注意点，首先Arena对象实现了一套leveldb的内存管理策略，将在下面的文章中进行分析，这里仅仅将其想象成一个内存分配器即可；另外就是Table类型（实际上就是SkipList类型）也将在下面的文章中进行分析。下面主要关注memtable初始化、插入key、查询key，由于LSM模型中memtable中没有数据的“实际”删除，这里并没有实现删除方法。

初始化函数定义如下：

view plain
  1. MemTable::MemTable(const InternalKeyComparator& cmp)  
  2.     : comparator_(cmp),  
  3.     refs_(0),  
  4.     table_(comparator_, &arena_)  
  5. {  
  6. }  


就是简单的完成refs_和table_的初始化。插入的函数定义如下：

view plain
  1. void MemTable:Add(SequenceNumber s, ValueType type,  
  2.                    const Slice& key,  
  3.                    const Slice& value)  
  4. {  
  5.     // Format of an entry is concatenation of:  
  6.     //  key_size     : varint32 of internal_key.size()  
  7.     //  key bytes    : char[internal_key.size()]  
  8.     //  value_size   : varint32 of value.size()  
  9.     //  value bytes  : char[value.size()]  
  10.     // 首先格式化kv数据，之后分别写入,格式如下:  
  11.     // key_size, key_bytes, sequence_number|type(固定64位),  
  12.     // value_size,value  
  13.     size_t key_size = key.size();  
  14.     size_t val_size = value.size();  
  15.     size_t internal_key_size = key_size + 8;  
  16.     const size_t encoded_len =  
  17.         VarintLength(internal_key_size) + internal_key_size +  
  18.         VarintLength(val_size) + val_size;  
  19.     char* buf = arena_.Allocate(encoded_len);  
  20.     char* p = EncodeVarint32(buf, internal_key_size);  
  21.     memcpy(p, key.data(), key_size);  
  22.     p += key_size;  
  23.     EncodeFixed64(p, (s << 8) | type);  // (sequencenum << 8) | type  
  24.     p += 8;  
  25.     p = EncodeVarint32(p, val_size);  
  26.     memcpy(p, value.data(), val_size);  
  27.     assert((p + val_size) - buf == encoded_len);  
  28.   
  29.     // 插入数据  
  30.     table_.Insert(buf);  
  31. }  


思路上相对比较简单，首先对用户传递进来的kv进行格式化，之后调用table_的Insert方法插入到数据库中，需要注意：1. 新出现了Slice类型，基本上和std::string类型向类似，代码比较简单，这里略过；2. 用户传递进来的kv最终被封装到了一个char数组中，格式为key_size, key_bytes, (sequence_number << 8)|type,value_size, value_bytes（其中并没有,这里仅仅是为了区分）。

查询的操作代码如下：

view plain
  1. bool MemTable::Get(const LookupKey& key, std::string* value, Status* s)  
  2. {  
  3.     Slice memkey = key.memtable_key();  
  4.     Table::Iterator iter(&table_);  
  5.     // 查找key  
  6.     iter.Seek(memkey.data());  
  7.     if (iter.Valid())  
  8.     {  
  9.         // entry format is:  
  10.         //    klength  varint32  
  11.         //    userkey  char[klength]  
  12.         //    tag      uint64  
  13.         //    vlength  varint32  
  14.         //    value    char[vlength]  
  15.         // Check that it belongs to same user key.  We do not check the  
  16.         // sequence number since the Seek() call above should have skipped  
  17.         // all entries with overly large sequence numbers.  
  18.         const char* entry = iter.key();  
  19.         uint32_t key_length;  
  20.         const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);  
  21.         if (comparator_.comparator.user_comparator()->Compare(  
  22.                     Slice(key_ptr, key_length - 8),  
  23.                     key.user_key()) == 0)   // memtable找到的key和用户查找的key相同  
  24.         {  
  25.             // Correct user key  
  26.             const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);  
  27.             switch (static_cast<ValueType>(tag & 0xff)) // 屏蔽低8位  
  28.             {  
  29.             case kTypeValue:    // 如果是kTypeValue类型，表明找到  
  30.             {  
  31.                 Slice v = GetLengthPrefixedSlice(key_ptr + key_length);  
  32.                 value->assign(v.data(), v.size());  
  33.                 return true;  
  34.             }  
  35.             case kTypeDeletion: // 如果是kTypeDeletion删除的数据  
  36.                 *s = Status::NotFound(Slice());  
  37.                 return true;  
  38.             }  
  39.         }  
  40.     }  
  41.     return false;  
  42. }  


Get函数内首先通过Table查找key，如果找到该key，解析key的内容，如果是kTypeValue类型的，返回给客户端查找到的value，如果是kTypeDeletion类型的（参考leveldb源代码分析：理论基础），返回给客户端表明没有找到。这里需要注意的是Get的参数中使用了LookupKey，该类型实际上就是在用户输入的key/value和leveldb内部使用key的起到桥梁的作用，定义如下：

view plain
  1. // A helper class useful for DBImpl::Get()  
  2. class LookupKey{  
  3.  public:  
  4.   // Initialize *this for looking up user_key at a snapshot with  
  5.   // the specified sequence number.  
  6.   LookupKey(const Slice& user_key, SequenceNumber sequence);  
  7.   
  8.   ~LookupKey();  
  9.   
  10.   // Return a key suitable for lookup in a MemTable.  
  11.   Slice memtable_key() const { return Slice(start_, end_ - start_); }  
  12.   
  13.   // Return an internal key (suitable for passing to an internal iterator)  
  14.   Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }  
  15.   
  16.   // Return the user key  
  17.   Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }  
  18.   
  19.  private:  
  20.   // We construct a char array of the form:  
  21.   //    klength  varint32               <-- start_  
  22.   //    userkey  char[klength]          <-- kstart_  
  23.   //    tag      uint64  
  24.   //                                    <-- end_  
  25.   // The array is a suitable MemTable key.  
  26.   // The suffix starting with "userkey" can be used as an InternalKey.  
  27.   const char* start_;  
  28.   const char* kstart_;  
  29.   const char* end_;  
  30.   char space_[200];      // Avoid allocation for short keys  
  31.   
  32.   // No copying allowed  
  33.   LookupKey(const LookupKey&);  
  34.   void operator=(const LookupKey&);  
  35. };  


至此基本上memtable的初始化、读取、插入的操作分析完了，未解决问题如下：

1. SkipList数据结构

2. Arena内存分配策略

leveldb memtable,布布扣,bubuko.com

leveldb memtable

原文：http://www.cnblogs.com/shenzhaohai1989/p/3904166.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！