精华内容
下载资源
问答
  • leveldb源码

    2017-10-31 18:51:15
    leveldb 源码,源于google 官方github 源码,解压缩即可
  • leveldb 源码

    2018-11-15 14:37:11
    googl开源文件数据库,使用key-value方式存储,可作为本地文件缓存。
  • levelDB源码

    2014-05-10 19:18:26
    包含两个版本的levelDB,1.15.0和1.4.0
  • read_and_analyse_levelDB LevelDB源码剖析
  • LevelDB源码之SkipList原理 分类: LevelDB源码系列2013-08-15 22:01 402人阅读 评论(0) 收藏 举报 LevelDB源码系列 感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight() ...

    LevelDB源码之SkipList原理

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

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

    [cpp]  view plain copy
    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. }  

    插入操作:

    [cpp]  view plain copy
    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. }  
    查找操作:

    [cpp]  view plain copy
    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源码:

    [cpp]  view plain copy
    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打开)
  • LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values. Authors: Sanjay Ghemawat (sanjay@google.com) and Jeff Dean (jeff@...
  • LevelDB源码解读

    2021-04-27 09:31:14
    LevelDB源码解读提供的功能read and writeGroup commitsequence numberdeleteAtomic Updates同步写Synchronous Writes遍历 iteration快照 SnapshotsSlice比较器 Comparatorsconcurrency保证compactionLevelDB的性能...


    提供的功能

    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);
    
    1. 写流程:
      1. 找到合适的memtable(skiplist)并写入数据,如果memtable写完并且immutableTable还未完成持久化,或者L0文件太多,则等待。如果memtable满了,则换一个memtable,并触发compaction
      2. 写日志,下刷日志
      3. 写memtable
    2. 读流程:
      1. 首先查找memtable,再查找immutable memtable
      2. 如果没有,查找下面所有持久化的levelVersion::Get,逐层向下搜索。搜索方法的策略是并不是遍历每一个sstable,而是先看需要查找的key是否落在sstable的范围内(每个sstable记录begin/end key),如果落在,对sstable搜索。
    3. 后台线程也会按需做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.

    如果系统希望避免丢数据,可以用以下几种方式实现:

    1. 只要上层应用知道当前写的数据是什么,那么就算crash了也没关系,重试就行了
    2. 另外可以每隔N个async write写一个sync write作为checkpoint,如果crash了,从上一个checkpoint处开始写就行了。
    3. 另外可以用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较高的某个levelsstable进行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。

    参考链接

    1. [leveldb] 3.put/delete操作
    2. LevelDB设计与实现 - 基础篇
    展开全文
  • 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 leveldb 是 Google 开源的持久化 KV 单机存储引擎,开源页面 http://code.google.com/p/leveldb/。 针对存储面对的普遍随机 IO 问题,leveldb 采用了 merge-dump 的方式,将...
  • 详细且纯粹的leveldb源码注解
  • 特征 键和值是任意字节数组。 数据按键存储。 调用者可以提供自定义比较功能来覆盖排序顺序。...include / leveldb / table.h,include / leveldb / table_builder.h:大多数客户端可能不会直接使用的低层模块。
  • windows下可编译的leveldb源码,主要用boost库替代linux下移植代码。 修改源码部分: 1.db\c.cc文件中头文件unistd.h 2.port\port.h文件中注明使用的是windows系统 3.无法打开包括文件:“sys/mman.h”: No such ...
  • Windows下使用VS2012编译成功的leveldb源码工程文件,下载后直接点击.sln文件打开,更改配置后直接可用。生成的LevleDB.lib文件在Debug文件夹中。如果不想编译,也可以直接在自己工程中使用生成的LevleDB.lib库,亲...
  • leveldb是key-value模式数据库...leveldb以其良好的编程风格和设计理念为人称道,阅读leveldb源码对提升自己的编程能力大有裨益。 leveldb源码地址 https://github.com/google/leveldb leveldb源码目录结构 db

    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

    展开全文
  • Leveldb源码分析

    2013-03-01 09:05:21
    Leveldb源码分析
  • leveldb源码阅读—status

    2020-02-25 16:22:59
    leveldb源码阅读】系列status源码阅读。学习了memcpy和可枚举对象使用。
  • LevelDB源码分析之一:coding LevelDB源码分析之二:comparator LevelDB源码分析之三:arena LevelDB源码分析之四:AtomicPointer LevelDb源码分析之五:skiplist(1) LevelDB源码分析之七:Random LevelDB中的...
  • 推荐结合leveldb-handbook来阅读源码 接上篇leveldb源码学习之日志 log 写入
  • leveldb源码剖析01–基础概述之源码搭建引言1 源码下载2 环境配置3 源码简介 引言 leveldb是一个开源的单机KV存储库,其作者是谷歌工程师Jeff Dean和Sanjay Ghemawat。很多开源LSM存储引擎都基于或使用leveldb,例如...
  • LevelDB源码阅读-coding

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

    2020-07-17 10:57:00
    leveldb和redis这样的优秀开源框架都没有使用C++...我把slice作为leveldb源码部分的第一个讲解,主要是slice是这个源码最基础的部分,都是别人使用它,它不使用别人。而且相对简单。 class Slice { public: // Create
  • LevelDB源码分析之十五:table cache

    千次阅读 2018-01-15 13:04:06
    LevelDB源码分析之十一:cache LevelDB源码分析之十二:block LevelDB源码分析之十三:table 由上面这三篇博客可知,LevelDB的Cache分为两种,分别是table cache和block cache。block是table文件内组织数据...
  • 一、下载leveldb源码 从github上下载windows版本的leveldb源码:https://github.com/google/leveldb/tree/windows 下载完后,解压目录如下所示: 二、安装boost库 由于leveldb使用了boost库的依赖,所以需要...
  • leveldb源码学习系列

    2015-04-09 08:15:00
    楼主从2014年7月份开始学习&lt;&gt;,由于书籍比较抽象,为了加深思考,同时开始了Google ...如果有开始学习leveldb源码的同学,可以参照着我的文章来看源码。看leveldb的源码,收获颇深,读到精彩处,...
  • 源码笔记 线程安全性分析: emplace_back可以避免使用参数构造对象时额外的构造操作,直接原地通过参数构造对象,如果是push_back,需要调用构造函数构造临时对象,再调用移动构造函数构造对象. PosixWritableFile使用写...
  • LevelDB源码阅读(2)

    2017-01-01 15:51:05
    LevelDB源码阅读(2)   C语言用的比较多一些,后面再阅读LevelDB源码的时候,同步做个C语言版本的如何?顺便看看和C++的版本性能比较。说干就干J   还有几个事情在思考: 1. C语言版本和C++版本到底性能有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,044
精华内容 2,417
关键字:

leveldb源码