精华内容
下载资源
问答
  • LevelDB源码之SkipList原理 分类: LevelDB源码系列2013-08-15 22:01 402人阅读 评论(0) 收藏 举报 LevelDB源码系列 感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight() ...

    LevelDB源码之SkipList原理

    分类: LevelDB源码系列 402人阅读 评论(0) 收藏 举报

    感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight()

    1. template<typename Key, class Comparator>  
    2. int SkipList<Key,Comparator>::RandomHeight() {  
    3.   // Increase height with probability 1 in kBranching  
    4.   static const unsigned int kBranching = 4;  
    5.   int height = 1;  
    6.   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  
    7.     height++;  
    8.   }  
    9.   assert(height > 0);  
    10.   assert(height <= kMaxHeight);  
    11.   return height;  
    12. }  

    插入操作:

    1. template<typename Key, class Comparator>  
    2. void SkipList<Key,Comparator>::Insert(const Key& key) {  
    3.   // TODO(opt): We can use a barrier-free((屏蔽,障碍/无障碍) variant(变种) of FindGreaterOrEqual()  
    4.   // here since Insert() is externally synchronized.  
    5.   //prev为各层的前置节点  
    6.   Node* prev[kMaxHeight];  
    7.   //查找插入的节点  
    8.   Node* x = FindGreaterOrEqual(key, prev);  
    9.   
    10.   // Our data structure does not allow duplicate insertion  
    11.   assert(x == NULL || !Equal(key, x->key));  
    12.   //随机生成节点高度  
    13.   int height = RandomHeight();  
    14.   if (height > GetMaxHeight()) {  
    15.     for (int i = GetMaxHeight(); i < height; i++) {  
    16.       prev[i] = head_;  
    17.     }  
    18.     //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  
    19.   
    20.     // It is ok to mutate max_height_ without any synchronization  
    21.     // with concurrent readers.  A concurrent reader that observes  
    22.     // the new value of max_height_ will see either the old value of  
    23.     // new level pointers from head_ (NULL), or a new value set in  
    24.     // the loop below.  In the former case the reader will  
    25.     // immediately drop to the next level since NULL sorts after all  
    26.     // keys.  In the latter case the reader will use the new node.  
    27.     //设置最大高度  
    28.     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  
    29.   }  
    30.   //生成一个新的Node  
    31.   x = NewNode(key, height);  
    32.   for (int i = 0; i < height; i++) {  
    33.     // NoBarrier_SetNext() suffices since we will add a barrier when  
    34.     // we publish a pointer to "x" in prev[i].  
    35.     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  
    36.     prev[i]->SetNext(i, x);  
    37.   }  
    38. }  
    查找操作:

    1. template<typename Key, class Comparator>  
    2. typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)  
    3.     const {  
    4.   Node* x = head_;  
    5.   //从最顶层开始查找  
    6.   int level = GetMaxHeight() - 1;  
    7.   while (true) {  
    8.     Node* next = x->Next(level);  
    9.     //向右查找  
    10.     if (KeyIsAfterNode(key, next)) {  
    11.       // Keep searching in this list  
    12.       x = next;  
    13.     } else {  
    14.         //向下查找  
    15.       if (prev != NULL) prev[level] = x;  
    16.       if (level == 0) {  
    17.         return next;  
    18.       } else {  
    19.         // Switch to next list  
    20.         level--;  
    21.       }  
    22.     }  
    23.   }  
    24. }  
    整个SkipList.h源码:

    1. // Copyright (c) 2011 The LevelDB Authors. All rights reserved.  
    2. // Use of this source code is governed by a BSD-style license that can be  
    3. // found in the LICENSE file. See the AUTHORS file for names of contributors.  
    4. //  
    5. // Thread safety  
    6. // -------------  
    7. //  
    8. // Writes require external synchronization, most likely a mutex.  
    9. // Reads require a guarantee that the SkipList will not be destroyed  
    10. // while the read is in progress.  Apart from that, reads progress  
    11. // without any internal locking or synchronization.  
    12. //  
    13. // Invariants:  
    14. //  
    15. // (1) Allocated nodes are never deleted until the SkipList is  
    16. // destroyed.  This is trivially guaranteed by the code since we  
    17. // never delete any skip list nodes.  
    18. //  
    19. // (2) The contents of a Node except for the next/prev pointers are  
    20. // immutable after the Node has been linked into the SkipList.  
    21. // Only Insert() modifies the list, and it is careful to initialize  
    22. // a node and use release-stores to publish the nodes in one or  
    23. // more lists.  
    24. //  
    25. // ... prev vs. next pointer ordering ...  
    26.   
    27. #include <assert.h>  
    28. #include <stdlib.h>  
    29. #include "port/port.h"  
    30. #include "util/arena.h"  
    31. #include "util/random.h"  
    32. /** 
    33.  * SkipList应用概率来保证平衡,平衡树采用严格的旋转来保证平衡 
    34.  * 使用SkipList是的查找特定值得时间复杂度是O(logN),与平衡树有着相同的复杂度,节省空间,每个检点平均1.33个指针 
    35.  * leveldb的最高层数为12,只允许插入和修改,Record的key不允许重复,添加一个Sequene Num 
    36.  * 规范:参数使用引用,返回值使用指针 
    37.  * 
    38.  */  
    39. namespace leveldb {  
    40.   
    41. class Arena;  
    42.   
    43. template<typename Key, class Comparator>  
    44. class SkipList {  
    45.  private:  
    46.   struct Node;  
    47.   
    48.  public:  
    49.   // Create a new SkipList object that will use "cmp" for comparing keys,  
    50.   // and will allocate memory using "*arena".  Objects allocated in the arena  
    51.   // must remain allocated for the lifetime of the skiplist object.  
    52.   explicit SkipList(Comparator cmp, Arena* arena);  
    53.   
    54.   // Insert key into the list.  
    55.   // REQUIRES: nothing that compares equal to key is currently in the list.  
    56.   void Insert(const Key& key);  
    57.   
    58.   // Returns true iff an entry that compares equal to key is in the list.  
    59.   bool Contains(const Key& key) const;  
    60.   
    61.   // Iteration over the contents of a skip list  
    62.   class Iterator {  
    63.    public:  
    64.     // Initialize an iterator over the specified list.  
    65.     // The returned iterator is not valid.  
    66.     explicit Iterator(const SkipList* list);  
    67.   
    68.     // Returns true iff the iterator is positioned at a valid node.  
    69.     bool Valid() const;  
    70.   
    71.     // Returns the key at the current position.  
    72.     // REQUIRES: Valid()  
    73.     const Key& key() const;  
    74.   
    75.     // Advances to the next position.  
    76.     // REQUIRES: Valid()  
    77.     void Next();  
    78.   
    79.     // Advances to the previous position.  
    80.     // REQUIRES: Valid()  
    81.     void Prev();  
    82.   
    83.     // Advance to the first entry with a key >= target  
    84.     void Seek(const Key& target);  
    85.   
    86.     // Position at the first entry in list.  
    87.     // Final state of iterator is Valid() iff list is not empty.  
    88.     void SeekToFirst();  
    89.   
    90.     // Position at the last entry in list.  
    91.     // Final state of iterator is Valid() iff list is not empty.  
    92.     void SeekToLast();  
    93.   
    94.    private:  
    95.     const SkipList* list_;  
    96.     Node* node_;  
    97.     // Intentionally copyable  
    98.   };  
    99.   
    100.   //跳表的最高level数  
    101.  private:  
    102.   enum { kMaxHeight = 12 };  
    103.   
    104.   // Immutable(不可变) after construction  
    105.   Comparator const compare_;  
    106.   //舞台,竞技场,场所(只负责申请空间的内存池)  
    107.   Arena* const arena_;    // Arena used for allocations of nodes  
    108.   
    109.   Node* const head_;  
    110.   
    111.   // Modified only by Insert().  Read racily by readers, but stale  
    112.   // values are ok.  
    113.   port::AtomicPointer max_height_;   // Height of the entire list  
    114.   
    115.   inline int GetMaxHeight() const {  
    116.     return static_cast<int>(  
    117.         reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load()));  
    118.   }  
    119.   
    120.   // Read/written only by Insert().  
    121.   Random rnd_;  
    122.   
    123.   Node* NewNode(const Key& key, int height);  
    124.   int RandomHeight();  
    125.   bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }  
    126.   
    127.   // Return true if key is greater than the data stored in "n"  
    128.   bool KeyIsAfterNode(const Key& key, Node* n) const;  
    129.   
    130.   // Return the earliest node that comes at or after key.  
    131.   // Return NULL if there is no such node.  
    132.   //  
    133.   // If prev is non-NULL, fills prev[level] with pointer to previous  
    134.   // node at "level" for every level in [0..max_height_-1].  
    135.   Node* FindGreaterOrEqual(const Key& key, Node** prev) const;  
    136.   
    137.   // Return the latest node with a key < key.  
    138.   // Return head_ if there is no such node.  
    139.   Node* FindLessThan(const Key& key) const;  
    140.   
    141.   // Return the last node in the list.  
    142.   // Return head_ if list is empty.  
    143.   Node* FindLast() const;  
    144.   
    145.   // No copying allowed  
    146.   SkipList(const SkipList&);  
    147.   void operator=(const SkipList&);  
    148. };  
    149.   
    150. // Implementation details follow  
    151. template<typename Key, class Comparator>  
    152. struct SkipList<Key,Comparator>::Node {  
    153.   explicit Node(const Key& k) : key(k) { }  
    154.   
    155.   Key const key;  
    156.   
    157.   // Accessors/mutators for links.  Wrapped in methods so we can  
    158.   // add the appropriate barriers as necessary.  
    159.   Node* Next(int n) {  
    160.     assert(n >= 0);  
    161.     // Use an 'acquire load' so that we observe a fully initialized  
    162.     // version of the returned Node.  
    163.     return reinterpret_cast<Node*>(next_[n].Acquire_Load());  
    164.   }  
    165.   void SetNext(int n, Node* x) {  
    166.     assert(n >= 0);  
    167.     // Use a 'release store' so that anybody who reads through this  
    168.     // pointer observes a fully initialized version of the inserted node.  
    169.     next_[n].Release_Store(x);  
    170.   }  
    171.   
    172.   // No-barrier variants that can be safely used in a few locations.  
    173.   Node* NoBarrier_Next(int n) {  
    174.     assert(n >= 0);  
    175.     return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());  
    176.   }  
    177.   void NoBarrier_SetNext(int n, Node* x) {  
    178.     assert(n >= 0);  
    179.     next_[n].NoBarrier_Store(x);  
    180.   }  
    181.   
    182.  private:  
    183.   // Array of length equal to the node height.  next_[0] is lowest level link.  
    184.   port::AtomicPointer next_[1];  
    185. };  
    186.   
    187. template<typename Key, class Comparator>  
    188. typename SkipList<Key,Comparator>::Node*  
    189. SkipList<Key,Comparator>::NewNode(const Key& key, int height) {  
    190.   char* mem = arena_->AllocateAligned(  
    191.       sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));  
    192.   return new (mem) Node(key);  
    193. }  
    194.   
    195. template<typename Key, class Comparator>  
    196. inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {  
    197.   list_ = list;  
    198.   node_ = NULL;  
    199. }  
    200.   
    201. template<typename Key, class Comparator>  
    202. inline bool SkipList<Key,Comparator>::Iterator::Valid() const {  
    203.   return node_ != NULL;  
    204. }  
    205.   
    206. template<typename Key, class Comparator>  
    207. inline const Key& SkipList<Key,Comparator>::Iterator::key() const {  
    208.   assert(Valid());  
    209.   return node_->key;  
    210. }  
    211.   
    212. template<typename Key, class Comparator>  
    213. inline void SkipList<Key,Comparator>::Iterator::Next() {  
    214.   assert(Valid());  
    215.   node_ = node_->Next(0);  
    216. }  
    217.   
    218. template<typename Key, class Comparator>  
    219. inline void SkipList<Key,Comparator>::Iterator::Prev() {  
    220.   // Instead of using explicit "prev" links, we just search for the  
    221.   // last node that falls before key.  
    222.   assert(Valid());  
    223.   node_ = list_->FindLessThan(node_->key);  
    224.   if (node_ == list_->head_) {  
    225.     node_ = NULL;  
    226.   }  
    227. }  
    228.   
    229. template<typename Key, class Comparator>  
    230. inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {  
    231.   node_ = list_->FindGreaterOrEqual(target, NULL);  
    232. }  
    233.   
    234. template<typename Key, class Comparator>  
    235. inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {  
    236.   node_ = list_->head_->Next(0);  
    237. }  
    238.   
    239. template<typename Key, class Comparator>  
    240. inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {  
    241.   node_ = list_->FindLast();  
    242.   if (node_ == list_->head_) {  
    243.     node_ = NULL;  
    244.   }  
    245. }  
    246.   
    247. template<typename Key, class Comparator>  
    248. int SkipList<Key,Comparator>::RandomHeight() {  
    249.   // Increase height with probability 1 in kBranching  
    250.   static const unsigned int kBranching = 4;  
    251.   int height = 1;  
    252.   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  
    253.     height++;  
    254.   }  
    255.   assert(height > 0);  
    256.   assert(height <= kMaxHeight);  
    257.   return height;  
    258. }  
    259.   
    260. template<typename Key, class Comparator>  
    261. bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {  
    262.   // NULL n is considered infinite  
    263.   return (n != NULL) && (compare_(n->key, key) < 0);  
    264. }  
    265. /** 
    266.  * 查找,从左向右,从上向下查找 
    267.  */  
    268. template<typename Key, class Comparator>  
    269. typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)  
    270.     const {  
    271.   Node* x = head_;  
    272.   //从最顶层开始查找  
    273.   int level = GetMaxHeight() - 1;  
    274.   while (true) {  
    275.     Node* next = x->Next(level);  
    276.     //向右查找  
    277.     if (KeyIsAfterNode(key, next)) {  
    278.       // Keep searching in this list  
    279.       x = next;  
    280.     } else {  
    281.         //向下查找  
    282.       if (prev != NULL) prev[level] = x;  
    283.       if (level == 0) {  
    284.         return next;  
    285.       } else {  
    286.         // Switch to next list  
    287.         level--;  
    288.       }  
    289.     }  
    290.   }  
    291. }  
    292.   
    293. template<typename Key, class Comparator>  
    294. typename SkipList<Key,Comparator>::Node*  
    295. SkipList<Key,Comparator>::FindLessThan(const Key& key) const {  
    296.   Node* x = head_;  
    297.   int level = GetMaxHeight() - 1;  
    298.   while (true) {  
    299.     assert(x == head_ || compare_(x->key, key) < 0);  
    300.     Node* next = x->Next(level);  
    301.     if (next == NULL || compare_(next->key, key) >= 0) {  
    302.       if (level == 0) {  
    303.         return x;  
    304.       } else {  
    305.         // Switch to next list  
    306.         level--;  
    307.       }  
    308.     } else {  
    309.       x = next;  
    310.     }  
    311.   }  
    312. }  
    313.   
    314. template<typename Key, class Comparator>  
    315. typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindLast()  
    316.     const {  
    317.   Node* x = head_;  
    318.   int level = GetMaxHeight() - 1;  
    319.   while (true) {  
    320.     Node* next = x->Next(level);  
    321.     if (next == NULL) {  
    322.       if (level == 0) {  
    323.         return x;  
    324.       } else {  
    325.         // Switch to next list  
    326.         level--;  
    327.       }  
    328.     } else {  
    329.       x = next;  
    330.     }  
    331.   }  
    332. }  
    333. /** 
    334.  * SkipList初始化 
    335.  * 
    336.  */  
    337. template<typename Key, class Comparator>  
    338. SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)  
    339.     : compare_(cmp),  
    340.       arena_(arena),  
    341.       head_(NewNode(0 /* any key will do */, kMaxHeight)),  
    342.       max_height_(reinterpret_cast<void*>(1)),  
    343.       rnd_(0xdeadbeef) {  
    344.   for (int i = 0; i < kMaxHeight; i++) {  
    345.     head_->SetNext(i, NULL);  
    346.   }  
    347. }  
    348. /** 
    349.  * 插入一个新的key 
    350.  * 
    351.  */  
    352. template<typename Key, class Comparator>  
    353. void SkipList<Key,Comparator>::Insert(const Key& key) {  
    354.   // TODO(opt): We can use a barrier-free((屏蔽,障碍/无障碍) variant(变种) of FindGreaterOrEqual()  
    355.   // here since Insert() is externally synchronized.  
    356.   //prev为各层的前置节点  
    357.   Node* prev[kMaxHeight];  
    358.   //查找插入的节点  
    359.   Node* x = FindGreaterOrEqual(key, prev);  
    360.   
    361.   // Our data structure does not allow duplicate insertion  
    362.   assert(x == NULL || !Equal(key, x->key));  
    363.   //随机生成节点高度  
    364.   int height = RandomHeight();  
    365.   if (height > GetMaxHeight()) {  
    366.     for (int i = GetMaxHeight(); i < height; i++) {  
    367.       prev[i] = head_;  
    368.     }  
    369.     //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  
    370.   
    371.     // It is ok to mutate max_height_ without any synchronization  
    372.     // with concurrent readers.  A concurrent reader that observes  
    373.     // the new value of max_height_ will see either the old value of  
    374.     // new level pointers from head_ (NULL), or a new value set in  
    375.     // the loop below.  In the former case the reader will  
    376.     // immediately drop to the next level since NULL sorts after all  
    377.     // keys.  In the latter case the reader will use the new node.  
    378.     //设置最大高度  
    379.     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  
    380.   }  
    381.   //生成一个新的Node  
    382.   x = NewNode(key, height);  
    383.   for (int i = 0; i < height; i++) {  
    384.     // NoBarrier_SetNext() suffices since we will add a barrier when  
    385.     // we publish a pointer to "x" in prev[i].  
    386.     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  
    387.     prev[i]->SetNext(i, x);  
    388.   }  
    389. }  
    390. /** 
    391.  * 包含 
    392.  */  
    393. template<typename Key, class Comparator>  
    394. bool SkipList<Key,Comparator>::Contains(const Key& key) const {  
    395.   Node* x = FindGreaterOrEqual(key, NULL);  
    396.   if (x != NULL && Equal(key, x->key)) {  
    397.     return true;  
    398.   } else {  
    399.     return false;  
    400.   }  
    401. }  
    402.   
    403. }  // namespace leveldb  
    展开全文
  • leveldb源码分析

    热门讨论 2013-12-04 15:10:14
    leveldb源码分析
  • leveldb源码工程Windows版,使用vs2010编译通过。有问题可以参考根目录下的Windows文件(使用notepad打开)
  • 特征 键和值是任意字节数组。 数据按键存储。 调用者可以提供自定义比较功能来覆盖排序顺序。...include / leveldb / table.h,include / leveldb / table_builder.h:大多数客户端可能不会直接使用的低层模块。
  • leveldb源码分析 比较全面讲解leveldb leveldb 是 Google 开源的持久化 KV 单机存储引擎,开源页面 http://code.google.com/p/leveldb/。 针对存储面对的普遍随机 IO 问题,leveldb 采用了 merge-dump 的方式,将...
  • LevelDB源码分析之一:coding LevelDB源码分析之二:comparator LevelDB源码分析之三:arena LevelDB源码分析之四:AtomicPointer LevelDb源码分析之五:skiplist(1) LevelDb源码分析之六:skip...

    阅读本文可参考:

    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源码注解
  • Leveldb源码分析

    2013-03-01 09:05:21
  • windows下可编译的leveldb源码,主要用boost库替代linux下移植代码。 修改源码部分: 1.db\c.cc文件中头文件unistd.h 2.port\port.h文件中注明使用的是windows系统 3.无法打开包括文件:“sys/mman.h”: No such ...
  • leveldb源码阅读—status

    2020-02-25 16:22:59
    leveldb源码阅读】系列status源码阅读。学习了memcpy和可枚举对象使用。

    在阅读log文件的时候,会发现使用了Status这个类,可以用它来得到函数返回的状态,比如:

    Status s = Function();
    if (!s.ok()) return false;
    return true
    

    今天就来认真学习一下相关实现方法。

    1. 私有

    1. state_,一个指向字符常数的指针。如果是成功的那么state_是null,否则,他是一个数组,索引0~3位是消息长度,4位是状态码,5位以后是消息本身。

    2. 返回的状态是可以枚举的,在Status类中,这些可枚举状态是私有变量Code,一共定义了成功、没找到、出错、不支持、不合法的参数、IO错误六种情况。

    3. code函数,通过state_的第四位及状态值返回是哪种可枚举值

    4. 带参数的构造函数。这个是很重要的一个函数,因为public函数中主要使用这个函数返回状态和类型。

    Status::Status(Code code, const Slice& msg, const Slice& msg2) 
    

    主要是使用了memcpy内存拷贝,把msg按照字节拷贝到返回结果中,具体过程如下:

    1. CopyState函数,对状态进行深拷贝,即开辟了新的内存。

    可以看到这里也使用了memcpy函数,我查了一下官方文档,有这样一句评论:

    std::memcpy 理应是最快的内存到内存复制子程序。它通常比必须扫描其所复制数据的 std::strcpy ,或必须预防以处理重叠输入的 std::memmove 更高效。

    2. public

    2.1 the big three

    1. 构造函数
    2. 析构函数
    3. 拷贝构造函数-传参是const
    4. 赋值函数-传参是const
    5. 拷贝构造函数-传参是非const
    6. 赋值构造函数-传参是非const

    2.2 是不是某一种状态

    我们之前说过,一共有6种可枚举的状态,所以这里有六个公有成员函数,返回的都是布尔类型,来判断状态是不是OK的或者出错了等。主要使用的就是我们之前说的Code函数。

    2.3 把某种状态和相关信息封装返回

    也是六个函数,使用的就是我们之前说的带参数的构造函数。

    2.4 转字符串

    把state转成字符串,方便打印。

    展开全文
  • 推荐结合leveldb-handbook来阅读源码 接上篇leveldb源码学习之日志 log 写入
  • LevelDB源码分析之一:coding LevelDB源码分析之二:comparator LevelDB源码分析之三:arena LevelDB源码分析之四:AtomicPointer LevelDb源码分析之五:skiplist(1) LevelDB源码分析之七:Random LevelDB中的...
  • 一、下载leveldb源码 从github上下载windows版本的leveldb源码:https://github.com/google/leveldb/tree/windows 下载完后,解压目录如下所示: 二、安装boost库 由于leveldb使用了boost库的依赖,所以需要...
  • leveldb源码分析之Slice

    2020-07-17 10:57:00
    leveldb和redis这样的优秀开源框架都没有使用C++...我把slice作为leveldb源码部分的第一个讲解,主要是slice是这个源码最基础的部分,都是别人使用它,它不使用别人。而且相对简单。 class Slice { public: // Create
  • leveldb源码剖析01–基础概述之源码搭建引言1 源码下载2 环境配置3 源码简介 引言 leveldb是一个开源的单机KV存储库,其作者是谷歌工程师Jeff Dean和Sanjay Ghemawat。很多开源LSM存储引擎都基于或使用leveldb,例如...
  • leveldb源码学习系列

    2015-04-09 08:15:00
    楼主从2014年7月份开始学习&lt;&gt;,由于书籍比较抽象,为了加深思考,同时开始了Google ...如果有开始学习leveldb源码的同学,可以参照着我的文章来看源码。看leveldb的源码,收获颇深,读到精彩处,...
  • LevelDB源码阅读-coding

    2018-12-19 17:47:59
    LevelDB源码阅读-coding 原文:https://blog.csdn.net/caoshangpa/article/details/78815940 LevelDB默认使用的是小端字节序存储,低位字节排放在内存的低地址端,高位字节排放在内存的高地址端。 编码分为变长的...
  • LevelDB源码分析之十五:table cache

    千次阅读 2018-01-15 13:04:06
    LevelDB源码分析之十一:cache LevelDB源码分析之十二:block LevelDB源码分析之十三:table 由上面这三篇博客可知,LevelDB的Cache分为两种,分别是table cache和block cache。block是table文件内组织数据...
  • LevelDB源码之SkipList原理 分类: LevelDB源码系列2013-08-15 22:01 374人阅读 评论(0) 收藏 举报 LevelDB源码系列 感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight() ...
  • LevelDB源码分析 - 汇总

    2017-08-29 09:09:10
    暂时更一个LevelDB源码分析得目录,后续补充完整。  1. Key in levelDB  2. 比较器  3. sstable格式  4. version  5. minor compaction  6. major compaction 之 size compaction  7. major ...
  • Leveldb源码解析之Bloom Filter Bloom Filter,即布隆过滤器,是一种空间效率很高的随机数据结构。 原理:开辟m个bit位数组的空间,并全部置零,使用k个哈希函数将元素映射到数组中,相应位置1.如下...
  • leveldb源码剖析04–基础概述之存储格式引言1 log文件1.1 WriteBatch 引言 前面讲了leveldb的关键文件,现在主要介绍各类关键文件的数据格式,这对我们阅读和理解leveldb源码是很有必要的。 1 log文件 1.1 ...
  • 久闻LevelDB大名,由于课程需要,借助此次机会对levelDB源码的几个主要模块进行解读,同时加强对c++的理解。 LevelDB简介 LevelDB是一个google开源的持久型K-V数据存储引擎,是一个很好的c++学习源码。LevelDB的主要...
  • LevelDB源码阅读(2)

    2017-01-01 15:51:05
    LevelDB源码阅读(2)   C语言用的比较多一些,后面再阅读LevelDB源码的时候,同步做个C语言版本的如何?顺便看看和C++的版本性能比较。说干就干J   还有几个事情在思考: 1. C语言版本和C++版本到底性能有...
  • leveldb源码剖析06–核心设计之mem缓存引言1 跳表原理1.1 数据结构1.2 数据查询1.3 插入节点1.4 删除节点2 源码解读 引言 无论是MemTable、还是immutable MemTable,在leveldb源码实现中都是MemTable类型。其核心...
  • Leveldb源码分析--1

    2018-07-19 23:32:16
    Leveldb源码分析 2012年1月21号开始研究下leveldb的代码,Google两位大牛开发的单机KV存储系统,涉及到了skip list、内存KV table、LRU cache管理、table文件存储、operation log系统等。先从边边角角的小角色开始...
  • https://code.google.com/p/leveldb 下载leveldb源码  #cd leveldb  #sudo chmod +x build_platform 修改为可执行文件 第二步:下载netbeans8.1  sh xxxxxx.sh 即可安装 第三步:将le

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 992
精华内容 396
关键字:

leveldb源码