-
LevelDB源码之SkipList原理LevelDB源码之SkipList原理
2014-04-07 21:51:29LevelDB源码之SkipList原理 分类: LevelDB源码系列2013-08-15 22:01 402人阅读 评论(0) 收藏 举报 LevelDB源码系列 感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight() ...感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight()
- 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>
- 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>
- 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--;
- }
- }
- }
- }
- // 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源码分析
2013-12-04 15:10:14leveldb源码分析 -
leveldb源码工程Windows版
2018-04-16 16:30:54leveldb源码工程Windows版,使用vs2010编译通过。有问题可以参考根目录下的Windows文件(使用notepad打开) -
特征 键和值是任意字节数组。 数据按键存储。 调用者可以提供自定义比较功能来覆盖排序顺序。...include / leveldb / table.h,include / leveldb / table_builder.h:大多数客户端可能不会直接使用的低层模块。
-
leveldb 源码解释 阅读情况
2019-05-07 20:18:19leveldb源码分析 比较全面讲解leveldb leveldb 是 Google 开源的持久化 KV 单机存储引擎,开源页面 http://code.google.com/p/leveldb/。 针对存储面对的普遍随机 IO 问题,leveldb 采用了 merge-dump 的方式,将... -
LevelDB源码分析之八:memtable
2017-12-26 14:18:11LevelDB源码分析之一:coding LevelDB源码分析之二:comparator LevelDB源码分析之三:arena LevelDB源码分析之四:AtomicPointer LevelDb源码分析之五:skiplist(1) LevelDb源码分析之六:skip...阅读本文可参考:
在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进行组合和管理,接口函数屏蔽了底层操作,对使用者更加优雅。
一.构造函数
构造函数对私有成员变量进行了初始化,table_是SkipList类型,将&aerna_当做key传入,arena_是Arena类型。MemTable::MemTable(const InternalKeyComparator& cmp) : comparator_(cmp), refs_(0), table_(comparator_, &arena_) { }
二.内存估算函数
这里直接调用的是Arena类的MemoryUsage方法,该方法返回整个内存池使用内存的总大小(不精确)。size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }
三.添加函数
一个完整的buf内容如下图所示。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); }
四.获取函数
获取函数的第一个参数是LookupKey类型,LookupKey是一个帮助类,通过它可以更方便的对Memtable进行操作。由于LookupKey的官方注释特别详细,这里就不分析了。// 如果能找到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; } }
参考链接:http://www.360doc.com/content/14/0325/16/15064667_363619194.shtml
-
cpp-详细且纯粹的leveldb源码注解
2019-08-16 05:46:23详细且纯粹的leveldb源码注解 -
Leveldb源码分析
2013-03-01 09:05:21 -
windows下可编译的leveldb源码
2019-12-25 15:02:18windows下可编译的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. 私有
-
state_
,一个指向字符常数的指针。如果是成功的那么state_
是null,否则,他是一个数组,索引0~3位是消息长度,4位是状态码,5位以后是消息本身。 -
返回的状态是可以枚举的,在Status类中,这些可枚举状态是私有变量
Code
,一共定义了成功、没找到、出错、不支持、不合法的参数、IO错误六种情况。 -
code函数,通过state_的第四位及状态值返回是哪种可枚举值
-
带参数的构造函数。这个是很重要的一个函数,因为public函数中主要使用这个函数返回状态和类型。
Status::Status(Code code, const Slice& msg, const Slice& msg2)
主要是使用了
memcpy
内存拷贝,把msg按照字节拷贝到返回结果中,具体过程如下:CopyState
函数,对状态进行深拷贝,即开辟了新的内存。
可以看到这里也使用了memcpy函数,我查了一下官方文档,有这样一句评论:
std::memcpy 理应是最快的内存到内存复制子程序。它通常比必须扫描其所复制数据的 std::strcpy ,或必须预防以处理重叠输入的 std::memmove 更高效。
2. public
2.1 the big three
- 构造函数
- 析构函数
- 拷贝构造函数-传参是const
- 赋值函数-传参是const
- 拷贝构造函数-传参是非const
- 赋值构造函数-传参是非const
2.2 是不是某一种状态
我们之前说过,一共有6种可枚举的状态,所以这里有六个公有成员函数,返回的都是布尔类型,来判断状态是不是OK的或者出错了等。主要使用的就是我们之前说的
Code
函数。2.3 把某种状态和相关信息封装返回
也是六个函数,使用的就是我们之前说的带参数的构造函数。
2.4 转字符串
把state转成字符串,方便打印。
-
-
leveldb源码学习之日志 log 读取
2020-04-03 09:51:41推荐结合leveldb-handbook来阅读源码 接上篇leveldb源码学习之日志 log 写入 -
LevelDB源码分析之六:skiplist(2)
2017-12-22 16:31:23LevelDB源码分析之一:coding LevelDB源码分析之二:comparator LevelDB源码分析之三:arena LevelDB源码分析之四:AtomicPointer LevelDb源码分析之五:skiplist(1) LevelDB源码分析之七:Random LevelDB中的... -
leveldb源码分析一一visual studio创建工程加载google leveldb
2018-11-15 19:02:20一、下载leveldb源码 从github上下载windows版本的leveldb源码:https://github.com/google/leveldb/tree/windows 下载完后,解压目录如下所示: 二、安装boost库 由于leveldb使用了boost库的依赖,所以需要... -
leveldb源码分析之Slice
2020-07-17 10:57:00leveldb和redis这样的优秀开源框架都没有使用C++...我把slice作为leveldb源码部分的第一个讲解,主要是slice是这个源码最基础的部分,都是别人使用它,它不使用别人。而且相对简单。 class Slice { public: // Create -
leveldb源码剖析1.1–基础概述之源码搭建
2020-08-19 21:00:57leveldb源码剖析01–基础概述之源码搭建引言1 源码下载2 环境配置3 源码简介 引言 leveldb是一个开源的单机KV存储库,其作者是谷歌工程师Jeff Dean和Sanjay Ghemawat。很多开源LSM存储引擎都基于或使用leveldb,例如... -
leveldb源码学习系列
2015-04-09 08:15:00楼主从2014年7月份开始学习<>,由于书籍比较抽象,为了加深思考,同时开始了Google ...如果有开始学习leveldb源码的同学,可以参照着我的文章来看源码。看leveldb的源码,收获颇深,读到精彩处,... -
LevelDB源码阅读-coding
2018-12-19 17:47:59LevelDB源码阅读-coding 原文:https://blog.csdn.net/caoshangpa/article/details/78815940 LevelDB默认使用的是小端字节序存储,低位字节排放在内存的低地址端,高位字节排放在内存的高地址端。 编码分为变长的... -
LevelDB源码分析之十五:table cache
2018-01-15 13:04:06LevelDB源码分析之十一:cache LevelDB源码分析之十二:block LevelDB源码分析之十三:table 由上面这三篇博客可知,LevelDB的Cache分为两种,分别是table cache和block cache。block是table文件内组织数据... -
LevelDB源码之SkipList原理
2014-03-23 09:13:15LevelDB源码之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
2019-07-15 13:40:40Leveldb源码解析之Bloom Filter Bloom Filter,即布隆过滤器,是一种空间效率很高的随机数据结构。 原理:开辟m个bit位数组的空间,并全部置零,使用k个哈希函数将元素映射到数组中,相应位置1.如下... -
leveldb源码剖析1.4–基础概述之存储格式
2020-08-19 21:03:09leveldb源码剖析04–基础概述之存储格式引言1 log文件1.1 WriteBatch 引言 前面讲了leveldb的关键文件,现在主要介绍各类关键文件的数据格式,这对我们阅读和理解leveldb源码是很有必要的。 1 log文件 1.1 ... -
LevelDB源码解读——简介及数据结构
2019-10-19 10:30:54久闻LevelDB大名,由于课程需要,借助此次机会对levelDB源码的几个主要模块进行解读,同时加强对c++的理解。 LevelDB简介 LevelDB是一个google开源的持久型K-V数据存储引擎,是一个很好的c++学习源码。LevelDB的主要... -
LevelDB源码阅读(2)
2017-01-01 15:51:05LevelDB源码阅读(2) C语言用的比较多一些,后面再阅读LevelDB源码的时候,同步做个C语言版本的如何?顺便看看和C++的版本性能比较。说干就干J 还有几个事情在思考: 1. C语言版本和C++版本到底性能有... -
leveldb源码剖析2.2–核心设计之mem缓存
2020-08-22 17:55:22leveldb源码剖析06–核心设计之mem缓存引言1 跳表原理1.1 数据结构1.2 数据查询1.3 插入节点1.4 删除节点2 源码解读 引言 无论是MemTable、还是immutable MemTable,在leveldb源码实现中都是MemTable类型。其核心... -
Leveldb源码分析--1
2018-07-19 23:32:16Leveldb源码分析 2012年1月21号开始研究下leveldb的代码,Google两位大牛开发的单机KV存储系统,涉及到了skip list、内存KV table、LRU cache管理、table文件存储、operation log系统等。先从边边角角的小角色开始... -
在netbeans下编译leveldb源码
2016-05-11 16:34:13https://code.google.com/p/leveldb 下载leveldb源码 #cd leveldb #sudo chmod +x build_platform 修改为可执行文件 第二步:下载netbeans8.1 sh xxxxxx.sh 即可安装 第三步:将le
-
云开发后台+微信扫码点餐小程序+cms网页管理后台 含后厨端和用户端
-
数值分析(1):数学模型和数值方法引论
-
实现 MySQL 读写分离的利器 mysql-proxy
-
MySQL 视图
-
Windows系统管理
-
交替方向块稀疏信号快速重构算法
-
对连续流量中的交互进行建模
-
java集成测试_基于TestNG+Mockito及自动装配注解的Spring MVC集成测试
-
数据驱动经验分享:从方法到实践
-
MySQL 高可用工具 heartbeat 实战部署详解
-
关于ZigBee的一切,全在这里了!
-
FFmpeg4.3系列之16:WebRTC之小白入门与视频聊天的实战
-
学习用高斯嵌入表示知识图
-
基于Kubernetes的Jenkins构建集群实践
-
Windows版本Redis启动报错
-
2021年软考系统规划与管理师-下午历年真题解析视频课程
-
富达国际Fidelity带领金融机构在2020年营业利润创下纪录,这是为什么?
-
可视化库----Matplotlib+Pandas高级篇及应用
-
3-数组
-
销售点系统的改进的可用性评估模型