知识图谱初探（八）- RocksDB存储结构

前面有说neo4j的底层存储，现在我们再来看看另一个图数据库Nebula ，其底层存储用的 RocksDB。

RocksDB的数据写入过程：

写入步骤：

1. 写入WAL(write ahead log)，用来保证异常时的数据一致性。Rocksdb所在节点出现断电异常，节点死机 等情况，内存中的数据是会丢失的。WAL机制，能够在这种异常情况下尽可能挽回多的数据。
2. 数据写入缓存，先保存入Memtable
3. Memtable达到一定阈值，会切换为Immutable Memtable
4. 后台进程对Immutable Memtable刷盘，生成Level 0 SST文件
5. 后台进程将L0-SST文件合并生成下层SST文件

Memtable结构

Memtable默认实现是SkipList ，有序的跳跃表（类似链表，在单链表之上增加多层索引增加查找性能）结构，其基本结构单元如下：

class Node {  // LevelDB SkipList
  const Key          key_;
  std::atomic<Node*> next_[1];
}

class Node {  // RocksDB InlineSkipList
  std::atomic<Node*>  next_[1];
}

如图看到其内存结构：

再来看SkipList本身结构

class SkipList {
  struct Node;
  Node* const head_;
  std::atomic<int> max_height_;
  Node** prev_;
  int32_t prev_height_;
}
class InlineSkipList {
  struct Node;
  struct Splice;
  Node* const head_;
  std::atomic<int> max_height_;
  Splice* seq_splice_;
}
struct Splice { 
  int height_ = 0;
  Node** prev_;
  Node** next_;
};

InlineSkipList 多了seq_splice_，少了prev_数组，移动到Splice里面。

Splice里面的prev和next数组用来存储插入key的时候的前缀和后缀，从最高层向下比较，可以有效减少比较范围

SSTable结构

Hbase底层硬盘存储即基于SSTable结构，SST是Sorted String Table的简写

如图：

1. Footer存储IndexBlock和MetaIndexBlock的位置，存储于SST文件末尾，占用48byte
2. MetaIndexBlock存储MetaBlock的位置
3. MetaBlock存储布隆过滤器的数据，占多个block
4. IndexBlock存储DataBlock的位置

布隆过滤器Bloom Filter的作用是对于任意集合的key，基于BitMap可以用来构建一个bit数组的算法。给出任意key，这个bit数组可以用于决定这个key是不是可能存在或者绝对不存在于这个key集合，用来减少无用的查询次数，从而加快查询的速度。