Rocksdb源码剖析⼀----Rocksdb概述与基本组件如需转载，请注明链接及作者，谢谢合作~~
因为本⼈对⼀些经典的开源项⽬很有兴趣，也想从⼤⽜设计的开源系统中学习架构设计经验，所以喜欢分析⼀些开源代码，这次因为项⽬中需要使⽤rocksdb，故在使⽤的时候仔细分析了rocksdb的实现细节，从2015年11⽉11⽇下决⼼整理出这⼀系列的blog，也算是对⼯作的总结吧。分享出来希望能帮到有需要的朋友。因为之前已经读完LevelDB的源码，读的过程中也参考了⽹上的相关⽂章，此⼩节的介绍会与LevelDB有些类似，毕竟rocksdb是基于LevelDB设计实现的，只在⼀些地⽅做了优化⽽已，有些代码甚⾄都是⼀样的。源码分析的后⾯章节会具体分析rocksdb的实现。
Rocksdb是facebook开源的NOSQL存储系统，其设计是基于Google开源的Leveldb，优化了LevelDB中存在的⼀些问题，其性能号称要⽐LevelDB强，rocksdb的设计跟Leveldb的极其类似，读过LevelDB源码的再读rocksdb的源码基本毫⽆压⼒，rocksdb也包括了内存memtable,LRUcache，磁盘上的sstable，operation log等等。本系列就是从rocksdb的源码级别来分析其设计实现与性能
既然rocksdb是基于leveldb设计实现并优化了⼀些细节，那我们先看⼀下leveldb的基本框架，
图1-1
由该架构图可以看到，Leveldb是由memtable, immute memtable，wal log，sstable组成内存中的memtalbe与imm memtable各为⼀个，imm memtable是由memtable达到阈值后转化⽽成的，其数据结构是⼀样的。这⾥对于Leveldb的具体实现细节这⾥不详细论述，有兴趣的可以参考下其它Leveldb的源码分析，或者继续看后续分析章节，对理解Leveldb也很有帮助。
rocksdb对leveldb的优化有:
1. 增加了column family，有了列簇的概念，可把⼀些相关的key存储在⼀起，column famiy的设计挺有意思的，后⾯会单独分析
2. 内存中有多个immute memtalbe，可防⽌Leveldb中的 write stall
3. 可⽀持多线程同时compation，理论上多线程同时comaption会⽐⼀个线程compation要快
4. 增加了merge operator，也就是原地更新，优化了modify的效率
5. ⽀持DB级的TTL
6. flush与compation分开不同的线程池来调度，并具有不同的优先级，flush要优于compation，这样可以加快flush，防⽌stall
7. 对SSD存储做了优化，可以以in-memory⽅式运⾏
8. 增加了对 write ahead log（WAL）的管理机制，更⽅便管理WAL，WAL是binlog⽂件
1. 上⾯只要简单的总结，更多的细节还需要进⼀步分析，rocksdb的基本框架如下图,
图1-2
从图1-1与图1-2可以看出，Leveldb的框架与Rocksdb的框架⼗分类似，rocksdb从3.0开始⽀持ColumnFamily的概念，所以我们从ColumnFamily的⾓度来看rocksdb的框架，
每个columnfamilyl的meltable与sstable都是分开的，所以每⼀个column family都可以单独配置，所有column family共⽤同⼀个WAL log⽂件，可以保证跨column family写⼊时的原⼦性
Rocksdb同样是⼀种基于operation log的⽂件系统，
由于采⽤了op log，将对磁盘的随机写转换成了对op log的顺序写，最新的数据是存储在内存的memrory中，可以提⾼IO效率。每⼀个的column family分别有⼀个memtable与sstablle.当某⼀coloumn family内存中的memory table超过阈值时， 转换成immute memtable并创建新的op log，immute memtable由⼀系列的memtable组成，它们是只读的，可供查询，不能更新数据。当immute memtable的数⽬超过设置的数值时，会触发flush，DB会调度后台线程将多个memtable合并后再dump到磁盘⽣成Level0中⼀个新的sstable⽂件，Level0中的sstable⽂件不断累积，会触发compaction，DB会调度后台compaction线程将Level0中的sstable⽂件根据key与Level1中的sstable合并并⽣成新的sstable，依次类推，根据key的空间从低层往上compact，最终形成了⼀层层的结构，层级数⽬是由⽤户设置的。
⼆.
在阅读rocksdb源码前，需要提前储备下⼀些基本知识，要是对LevelDB的架构已经⽐较熟悉的话，基本可以略过此处，开始关注后⾯的章节。
必备知识点
1. 字节序
rocksdb中与leveldb类似，数字的存储是little-endian的，也就是说在把int32与int64转换成char*的函数中，是按照先低位再⾼位的顺序存放的。
2. Varint
在把int32或int64转换到字符串中时，为减⼩存储空间，采⽤变长存储，也就是VarInt。变长存储的实现与PB中的基本⼀样，即每byte的有效存储是7bit的，最⾼的8bit位表⽰是否结束， 最⾼bit位为1时，表⽰后⾯还有⼀个byte的数字，为0时，表⽰已经结束，具体实现可参考Encodexxx和Decodexxx系列函数
3. 基本数据结构
3.1 Slice
rocksdb的基本数据结构，成员包括length与⼀个指向外部存储空间的指针，是⼆进制安全的，可以包含‘\0'，提供了⼀些可与string/char*相互转换的接⼝，
3.2 Status
rocksdb的状态类，将错误号与错误信息封装，同样是为了节省空间，Status类将返回码，错误信息与长度打包存储在⼀个字符数组中。
格式如下：
state_[0..3] == 消息长度
state_[4]    == 消息code
state_[5..]  ==消息
3.3 Arena
rocksdb的简单内存池，
申请内存时，将申请到的内存块放⼊std::vector blocks_中，在Arena的⽣命周期结束后，统⼀释放掉所有申请到的内存，内部结构如图1-3所⽰。
图1-3
另外，rocksdb同样可以使⽤tcmalloc与jemalloc，在性能⽅⾯还是会有不⼩的提升.
3.4memtable
leveldb中，memtable在内存中核⼼s的数据结构为skiplist，⽽在rocksdb中,memtable在内存中的形式有三种：skiplist、hash-skiplist、hash-linklist，从字⾯中就可以看出数据结构的⼤体形式，hash-skiplist就是每个hash bucket中是⼀个skiplist，hash-linklist中，每个hash bucket中是⼀个link-list，启⽤何⽤数据结构可在配置中选择，下⾯是skiplist的数据结构：
图1-4
下⾯是hash-skiplist的结构，
图1-5
下⾯是hash-linklist的框架图,
图1-6
3.5 Cache
rocksdb内部根据双向链表实现了⼀个标准的LRUCache，由于LRUCache的设计实现⽐较通⽤经典，这⾥详细分析⼀下LRUCache的实现过程，根据LRUCache的从⼩到⼤的顺序来看基本组件，
A. LRUHandle结构体，Cache中最⼩粒度的元素，代表了⼀个k/v存储对，下⾯是LRUHandle的所有信息，
struct LRUHandle {
void* value;  // value信息
void (*deleter)(const Slice&, void* value); //删除元素时，可调⽤的回调函数
LRUHandle* next_hash; //解决hash冲突时，使⽤链表法
LRUHandle* next;//next/prev构成了双链，由LRU算法使⽤
LRUHandle* prev;
size_t charge;      // TODO(opt): Only allow uint32_t?
size_t key_length; //key的长度
uint32_t refs;      // a number of refs to this entry
// cache itself is counted as 1
leveldb使用
bool in_cache;      // true, if this entry is referenced by the hash table
uint32_t hash;      // Hash of key(); used for fast sharding and comparisons
char key_data[1];  // Beginning of key
Slice key() const {
// For cheaper lookups, we allow a temporary Handle object
// to store a pointer to a key in "value".
if (next == this) {
return *(reinterpret_cast<Slice*>(value));
} else {
return Slice(key_data, key_length);
}
}
void Free() {
assert((refs == 1 && in_cache) || (refs == 0 && !in_cache));
(*deleter)(key(), value);
free(this);
}
};
B. 实现了rocksdb⾃⼰的HandleTable，其实就是实现了⾃⼰的hash table,  速度号称⽐g++4.4.3版本⾃带的hash table的速度要快不少class HandleTable {
public:
HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
template <typename T>
void ApplyToAllCacheEntries(T func) {
for (uint32_t i = 0; i < length_; i++) {
LRUHandle* h = list_[i];
while (h != nullptr) {
auto n = h->next_hash;
assert(h->in_cache);
func(h);
h = n;
}
}
}
~
HandleTable() {
ApplyToAllCacheEntries([](LRUHandle* h) {
if (h->refs == 1) {
h->Free();
}
});
delete[] list_;
}
LRUHandle* Lookup(const Slice& key, uint32_t hash) {
return *FindPointer(key, hash);
}
LRUHandle* Insert(LRUHandle* h) {
LRUHandle** ptr = FindPointer(h->key(), h->hash);
LRUHandle* old = *ptr;
h->next_hash = (old == nullptr ? nullptr : old->next_hash);
*ptr = h;
if (old == nullptr) {
++elems_;
if (elems_ > length_) {
// Since each cache entry is fairly large, we aim for a small
// average linked list length (<= 1).
Resize();
}
}
return old;
}
LRUHandle* Remove(const Slice& key, uint32_t hash) {
LRUHandle** ptr = FindPointer(key, hash);
LRUHandle* result = *ptr;
if (result != nullptr) {
*ptr = result->next_hash;
--elems_;
}
return result;
}
private:
// The table consists of an array of buckets where each bucket is
// a linked list of cache entries that hash into the bucket.
uint32_t length_;
uint32_t elems_;
LRUHandle** list_;
// Return a pointer to slot that points to a cache entry that
// matches key/hash.  If there is no such cache entry, return a
// pointer to the trailing slot in the corresponding linked list.
LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
LRUHandle** ptr = &list_[hash & (length_ - 1)];
while (*ptr != nullptr &&
((*ptr)->hash != hash || key != (*ptr)->key())) {
ptr = &(*ptr)->next_hash;
}
return ptr;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。