一、什么是 Memtable?
Memtable 是 Rocksdb 在内存中保存数据的一种数据结构,一个 Memtable 的容量是固定的,在 Memtable 写满后,会转换为 Immutable Memtable,Immutable Memtable 中的数据会 Flush 到 SST File 中。
Memtable 和 Immutable Memtable 的唯一区别是 Memtable 可读可写,而 Immutable Memtable 是只读且不答应写入。Rocksdb 引入了 Column Family 的概念,在一个 Column Family 中只要一个 Memtable,但答应存在多个 Immutable Memtable。Rocksdb 支撑创建多数据结构类型的 Memtable,默许的是 SkipList,即跳动表。
二、Memtable 的数据结构
Rocksdb 中 Memtable 有多种完结方式 (SkipList / HashSkipList / HashLinkList / Vector),其间默许的完结方式为 SkipList。
一个 Memtable 中维护了两个 SkipList,其间规模删去刺进 range_del_table_,其他的操作写入 table_。
Memtable 定义的操作接口 Add () 如下:
bool MemTable::Add(SequenceNumber s, ValueType type,
const Slice& key, /* user key */
const Slice& value, bool allow_concurrent,
MemTablePostProcessInfo* post_process_info) {
// 一条key-value Entry的数据格式
// key_size : varint32 of internal_key.size()
// key bytes : char[internal_key.size()]
// value_size : varint32 of value.size()
// value bytes : char[value.size()]
uint32_t key_size = static_cast<uint32_t>(key.size());
uint32_t val_size = static_cast<uint32_t>(value.size());
uint32_t internal_key_size = key_size + 8;
const uint32_t encoded_len = VarintLength(internal_key_size) +
internal_key_size + VarintLength(val_size) +
val_size;
char* buf = nullptr;
// 经过判别key-value的类型来挑选memtable, 规模删去的kv刺进range_del_table_
std::unique_ptr<MemTableRep>& table =
type == kTypeRangeDeletion ? range_del_table_ : table_;
KeyHandle handle = table->Allocate(encoded_len, &buf);
//...
// 是否答应并发刺进
if (!allow_concurrent) {
// 是否拟定了函数提取key的前缀
if (insert_with_hint_prefix_extractor_ != nullptr &&
insert_with_hint_prefix_extractor_->InDomain(key_slice)) {
// ...
bool res = table->InsertWithHint(handle, &insert_hints_[prefix]);
} else {
// 刺进key-value pair
bool res = table->Insert(handle);
if (UNLIKELY(!res)) {
return res;
}
}
} else {
// 刺进key-value pair
bool res = table->InsertConcurrently(handle);
if (UNLIKELY(!res)) {
return res;
}
}
return true;
}
Add () 函数将用户的 key 和 value 封装成一个 buf,然后依据不同的条件调用 table->Insert () 刺进至 Memtable。table 就是 Memtable 的工厂类完结,默许 SkiplistRep, 即经过调用 SkipList 的 Insert () 完结 key 的刺进。
Memtable 定义的操作接口 Get () 如下:
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s,
MergeContext* merge_context,
RangeDelAggregator* range_del_agg, SequenceNumber* seq,
const ReadOptions& read_opts, ReadCallback* callback,
bool* is_blob_index) {
// 在range_del_table_上初始化一个迭代器
std::unique_ptr<InternalIterator> range_del_iter(
NewRangeTombstoneIterator(read_opts));
Status status = range_del_agg->AddTombstones(std::move(range_del_iter));
if (!status.ok()) {
*s = status;
return false;
}
Slice user_key = key.user_key();
// 利用前缀提取过滤判别key是否存在
bool const may_contain =
nullptr == prefix_bloom_
Memtable 的 Get () 调用了 SkipListRep 的 Get () 接口,最终是经过 SkipList 的 FindGreaterOrEqual () 来查找。查找出来的 key 会被传入的回调函数 SaveValu 并 e () 依据 type 处理,例如 ktypeDeletion 就回来 NotFound ()。
三、什么是 SkipList?
SkipList 即跳动表,在普通单向链表的基础上增加了一些索引,并且这些索引是分层的,然后能够快速地查到数据。如下是一个典型的跳动表构建进程:
初始咱们有个带头结点的有序链表 a,然后每相邻两个节点增加一个指针,让指针指向下下个节点,得到表 b。这样所有新增指针连成了一个新的链表,但它包含的节点个数只要原来的一半。其后咱们对第二层链表再次进行此操作,得到表 c。重复这个进程,直到采样出的节点只剩一个,如图 d。这样便完结了跳动表的构建。跳动表查找进程如下:
从 head 开端,head 的 level 为 4,判别 head 后继节点值小于 <12,此刻当时节点变为 6,持续查找;节点 6 的 level 为 3,判别后继节点值为 NIL,因此 level 降低到 2;判别 x -> forward [2] -> key (25) > 17,持续降低 level 到 1;判别 x -> forward [1] -> key (9) < 17,此刻 x 变为 x ->forward [1],x 成为节点 9;节点 9 的判别 x -> forward [1] -> key 为 17,因此找到节点,直接回来。
跳动表刺进进程如下:
咱们以上图为例,list -> leve=4,假如要刺进节点 17,首先确认查找途径,与之前过程相似。
创建新节点 Node (17),并为其生成 level (随机),该 level 或许值为 [1, MaxLevel],此刻需求比照,假如 level < list -> level,需求先将突出部分从 header 指向它,这儿新生成的节点 Node (17) 的 level 为 5,超过了 list 当时的最大 level,所以将 update [4] 设置为 header,后续直接将 Node (17) 作为 header 的后继。
最后是设置查找途径上每个节点的后继联系,这样咱们便完结了节点的刺进。咱们来看一下 SkipList 的具体代码完结:
InlineSkipList 数据结构 >>
class InlineSkipList {
private:
struct Node;
struct Splice;
public:
using DecodedKey = \
typename std::remove_reference<Comparator>::type::DecodedType;
…
Allocator* const allocator_;
Comparator const compare_;
Node* const head_;
std::atomic<int> max_height_;
Splice* seq_splice_;
};
Node 的数据结构 >>
template <class Comparator>
struct InlineSkipList<Comparator>::Node {
private:
// 寄存该节点的next_节点的数组
// 数组大小为该节点的height,当调用NewNode()分配内存初始化整个数组
std::atomic<Node*> next_[1];
};
Node 的数据结构如图,它将 key 和链表每层的指针连续存储,经过 next_[-n] 这种方式来访问每层的 next 指针,此外在 new 新节点时会把该节点高度写在 next_[0] 的前 4 个字节处,当完结刺进后,next_[0] 会恢复成指向同层的下一个节点的指针。
四、InlineSkipList 刺进
Memtable 的 Add () 经过 SkipList 的 Insert () 来查找,下面是 Insert () 的具体完结:
bool InlineSkipList<Comparator>::Insert(const char* key, Splice* splice,
bool allow_partial_splice_fix) {
Node* x = reinterpret_cast<Node*>(const_cast<char*>(key)) - 1; // x即为next_[0]
const DecodedKey key_decoded = compare_.decode_key(key);
int height = x->UnstashHeight();
assert(height >= 1 && height <= kMaxHeight_);
int max_height = max_height_.load(std::memory_order_relaxed);
// 更新max_height
while (height > max_height) {
if (max_height_.compare_exchange_weak(max_height, height)) {
// successfully updated it
max_height = height;
break;
}
// 否则重试,或许由于其他人增加了它而退出循环
}
assert(max_height <= kMaxPossibleHeight);
// 刺进节点的时候,需求借助一个Splice目标,该目标主要保存着最近一次刺进的节点快照
// 它保存着一个prev和next的节点指针数组,由Level能够索引到对应Level的节点
int recompute_height = 0;
if (splice->height_ < max_height) {
// 当重置splice
splice->prev_[max_height] = head_;
splice->next_[max_height] = nullptr;
splice->height_ = max_height;
recompute_height = max_height;
} else {
while (recompute_height < max_height) {
if (splice->prev_[recompute_height]->Next(recompute_height) !=
splice->next_[recompute_height]) { //判别该层的splice是否严密,即prev_->Next是否等于next_
++recompute_height;
} else if (splice->prev_[recompute_height] != head_ &&
!KeyIsAfterNode(key_decoded,
splice->prev_[recompute_height])) { //小于splice当时层的prev_
// ...
} else if (KeyIsAfterNode(key_decoded,
splice->next_[recompute_height])) { //大于splice当时层的prev_
// ...
} else {
// 找到了适宜的level
break;
}
}
}
assert(recompute_height <= max_height);
if (recompute_height > 0) {//计算splice
RecomputeSpliceLevels(key_decoded, splice, recompute_height); // 找到要刺进的key适宜的splice
}
bool splice_is_valid = true;
if (UseCAS) {//CAS无锁机制
//...
} else {
for (int i = 0; i < height; ++i) {
if (i >= recompute_height &&
splice->prev_[i]->Next(i) != splice->next_[i]) { // 保证splice此Level有效,假如无效的话再查找一次
FindSpliceForLevel<false>(key_decoded, splice->prev_[i], nullptr, i,
&splice->prev_[i], &splice->next_[i]);
}
// Checking for duplicate keys on the level 0 is sufficient
if (UNLIKELY(i == 0 && splice->next_[i] != nullptr &&
compare_(x->Key(), splice->next_[i]->Key()) >= 0)) {
// duplicate key
return false;
}
if (UNLIKELY(i == 0 && splice->prev_[i] != head_ &&
compare_(splice->prev_[i]->Key(), x->Key()) >= 0)) {
// duplicate key
return false;
}
//…
x->NoBarrier_SetNext(i, splice->next_[i]); //将新节点next指向对应的next节点
splice->prev_[i]->SetNext(i, x); //将splice的prev节点的next指向新节点
}
}
if (splice_is_valid) {//将新节点Height下的prev节点都设置为该节点,由于原先的prev和next之间已经不连续了。
for (int i = 0; i < height; ++i) {
splice->prev_[i] = x;
}
//...
} else {
splice->height_ = 0;
}
return true;
}
五、InlineSkipList 查找
Memtable 的 Get () 经过 SkipList 的 FindGreaterOrEqual () 来查找,下面是 FindGreaterOrEqual () 的具体完结:
InlineSkipList<Comparator>::FindGreaterOrEqual(const char* key) const {
Node* x = head_;
int level = GetMaxHeight() - 1;//从最高层开端查找
Node* last_bigger = nullptr;
const DecodedKey key_decoded = compare_.decode_key(key);
while (true) {
Node* next = x->Next(level);
if (next != nullptr) {
PREFETCH(next->Next(level), 0, 1);
}
// Make sure the lists are sorted
assert(x == head_ || next == nullptr || KeyIsAfterNode(next->Key(), x));
// Make sure we haven't overshot during our search
assert(x == head_ || KeyIsAfterNode(key_decoded, x));
int cmp = (next == nullptr || next == last_bigger)
? 1
: compare_(next->Key(), key_decoded);
if (cmp == 0 || (cmp > 0 && level == 0)) { // 找到相等的key或者查找的key不在此规模内
return next;
} else if (cmp < 0) { //待查找 key 比 next 大,则在该层持续查找
x = next;
} else { // 待查找 key 不大于 next,且没到底,则持续往基层查找
// Switch to next list, reuse compare_() result
last_bigger = next;
level--;
}
}
}