leveldb学习-安装与编译测试

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
git clone --recurse-submodules https://github.com/google/leveldb.git

sudo apt-get install cmake

cd leveldb

cmake CMakeLists.txt

make

ubuntu下leveldb的安装与编译测试

1.源码下载

git clone –recurse-submodules https://github.com/google/leveldb.git

下载完成之后，在当前目录会有一个leveldb的文件夹。

2.编译安装

cd leveldb //进入leveldb目录
mkdir -p build && cd build
cmake -DCMAKE_BUILD_TYPE=Release .. && cmake –build .

1
cmake -DCMAKE_EXPORT_COMPILE_COMMANDS=1 -DCMAKE_BUILD_TYPE=Release .. &&cmake --build .

cmake生成用于sourcetrail的json文件

编译完成之后，leveldb/build/目录下生成了一个静态库libleveldb.a，将这个静态库复制到/usr/local/lib/, 并把leveldb相关的头文件复制到/usr/local/include/

sudo cp build/libleveldb.a /usr/local/lib/
sudo cp -r include/leveldb/ /usr/local/include/

至此就安装完成啦，下面开始测试

创建demo.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cassert>
#include <iostream>
#include <string>
#include <leveldb/db.h>
 
int main() 
{
  leveldb::DB* db;
  leveldb::Options options;
  options.create_if_missing = true;
  leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
  assert(status.ok());
 
  std::string key = "test_key";
  std::string value = "test_value";
  std::string get;
 
  leveldb::Status s = db->Put(leveldb::WriteOptions(), key, value);
  
  if (s.ok()) 
	s = db->Get(leveldb::ReadOptions(), key, &get);
  if (s.ok()) 
	std::cout << "key=" << key << "\nvalue=" << get  << std::endl;
  else 
	std::cout << "failed to find the key!" << std::endl;
 
  delete db;
 
  return 0;
}

用g++编译，测试，输出结果

1
g++ -o demo demo.cpp -pthread -lleveldb -std=c++11

然后输入./demo结果：

key=test_key
value=test_value

结果：

image-20201120140718303

skiplist跳表的数据结构

SkipList是一种用来代替平衡树的数据结构。
虽然在最坏的情况下SkipList的效率要低于平衡树，但是大多数情况下效率仍然非常高，其插入、删除、查找的时间复杂度都是O(log(N))。
除了高效外，其实现和维护非常简单也是一大优势。SkipList的使用还是比较广泛的，比如在LevelDB中的MemTable就是使用SkipList实现的。

​ skiplist是多层的有序链表

查找

以查找19为例

img

先从最上层的跳跃区间大的层开始查找。从头结点开始，首先和23进行比较，小于23，（此时查找指针在图中“1”位置处），查找指针到下一层继续查找。

然后和9进行判断，大于9，查找指针再往前走一步和23比较，小于23，（此时查找指针在图中“2”位置处） 此时这个值肯定在9结点和23结点之间。查找指针到下一层继续查找。

然后和13进行判断，大于13，查找指针再往前走一步和23比较，小于23，（此时查找指针在图中“3”位置处）此时这个值肯定在13结点和23结点之间。查找指针到下一层继续查找。此时，我们和19进行判断，找到了。

插入

包含以下几个操作：

1、查找到需要插入的位置

2、申请新的节点

3、调整指针

因为在找到插入点之后，新生成节点，新节点按概率出现在每层上，故需要保存所有层的后续指针，这里用一个临时数组保存所有层的插入点处的后续指针。

img

以上图为例，现在要插入15这个节点。
其过程和查找类似，唯一的问题是，前面的节点的指针是如何保留下来的？

我们可以看到插入结束后，13的level=0的指针指向了15，13的level=1的指针指向了15。
这就意味着，在插入的时候我们就需要保留13的level=0的指针和13的level=1的指针。

在SkipList中是这样做的，有一个update数组，这个数组的大小为maxLevel。
还是以上图为例，在15插入之前，update这个数组中就已经存储了当前每个level的指针。

  • update[0]：13 level=0
  • update[1]：13 level=1
  • update[2]：9 level=2
  • update[3]：null level=3

skiplist的删除

删除的逻辑和插入类似

1、查找到相应的节点

2、通过update数组来实现该节点的逻辑删除

3、回收该节点资源

sstable的读取过程

sstable的读取过程，简单总结就是四个字:按图索骥

各个索引在读取过程中发挥了很大的作用。首先是seek到文件末尾读取固定48个字节大小的footer，footer是定长的。最后有8个字节的magic校验

image-20201125153200335

然后解析出meta index block 以及index_block。

通过meta index block 解析出filter block

通过index block解析出data_block

查找时先通过filter block查找是否存在，然后通过data_block解析出对应的value.

compaction操作

backgroundcompaction函数的调用关系图

image-20201125205236672

整体流程

compactmemtable主要流程分为三部分：

  1. WriteLevel0Table(imm_, &edit, base)：imm_落盘成为新的 sst 文件，文件信息记录到 edit
  2. versions_->LogAndApply(&edit, &mutex_)：将本次文件更新信息versions_，当前的文件（包含新的 sst 文件）作为数据库的一个最新状态，后续读写都会基于该状态
  3. DeleteObsoleeteFiles：删除一些无用文件

通过Finalize函数计算compaction的level和score