前言

决定开坑leveldb的学习，还是借助up主的博客学习，轻松一点，借鉴的是硬核课堂的文档。

LevelDB是一款写性能十分优秀的可持久化的KV存储引擎，其实现原理是依据LSM-Tree（Log Structed-Merge Tree），由Google开源。

设计思路

对于普通机械磁盘，由于写操作需要磁盘旋转和磁道寻址，顺序写的性能要比随机写的性能好很多。比如对于15000转的SAS盘，4K写IO，顺序写在200MB/s左右，而随机写性能可能只有1MB/s左右，LevelDB的设计正是利用了磁盘的这个特性。

LevelDB是依据LSM-Tree的原理实现的，写性能极高。

LSM原理介绍

LSM-tree 是专门为KV存储系统设计的，Key-Value类型的存储系统最主要的两个功能：

put(key,value)：写入一个Key-Value ;

get(key)：给定一个 key 查找 value。

从名字上来看，LSM树由两部分组成，分别为Log Structed 和Merge Tree。

“Log Structed”是日志结构的意思，而我们常说的日志就是软件系统输出的执行信息，其特点就是不断追加的写入日志文件中，不需要更改，只需要在后边追加就好了。很多数据库在写操作前的日志也是追加型的，因此说到日志结构，基本就是指“追加，Append-Only”。而“Merge Tree”，就是“合并树”的意思，就是把多个树合成一个大树。所以LSM-Tree就是数据以Append-Only方式写入文件，成为一颗小树，然后通过合并形成更大的树。

实现思路

将索引树结构拆成一大C0一小C1两棵树，较小的一棵树常驻内存，较大的一棵树持久化到硬盘，他们共同维护一个有序的key空间，如下图所示：

LSM-tree 的组成部分，是一个多层结构，由C0，C1，…，Ck树，由小到大。首先是内存的 C0 层，保存了最近所有写入的 （k，v），这个内存结构是有序的，并且可以随时原地更新，同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上，每一层都是一个在 key 上有序的结构。

• 写入操作

  put(k,v)会先追加到WAL日志树中，也就是真正写入之前先记录到日志中，防止丢失数据，接下来加到C0这棵内存树，当C0的数据打到一定大小会触发C0和C1层合并，类似于归并排序。当C1层达到一定大小，继续和下层Ck合并，合并之后旧文件都可以删除，留下新文件。

  由于key-value的写入可能重复，新版本需要覆盖旧版本，比如先写a=10,再写a=20，20就是新版本。

  如果a=10的老数据已经到Ck层了，C0层来了个a=20，此时不会去管底层的文件有没有老版本10，清理是在合并的时候清理。

• 读操作

  由于最新的数据在C0层，最旧的数据在Ck层，查询也是先查C0层，依次查到Ck层，由于一次查询需要多次查找操作，因此读操作会稍微慢一点，因此说LSM适合写多读少的操作。

字节序

字节序是处理器架构的特性

• 低序字节存储在起始地址叫小端
• 高序字节存储在起始地址叫大端

测试字节序的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

using namespace std;

int main() {
    union {
        short s;
        char c[sizeof(short)];
    } un;
    un.s = 0x0102;
    if (sizeof(short) == 2) {
        if (un.c[0] == 1 && un.c[1] == 2) {
            cout << "大端" << endl;
        } else if (un.c[1] == 1 && un.c[0] == 2) {
            cout << "小端" << endl;
        } else {
            cout << "unknown" << endl;
        }
    } else {
        cout << "sizeof(short)=" << sizeof(short) << endl;
    }
    return 0;
}

slice

slice是leveldb中自定义的字符串处理类，主要是因为标准库中的string，

• 默认语意为拷贝，会损失性能(在可预期的条件下，指针传递即可)
• 标准库不支持remove_prefix和starts_with等函数，不太方便

remove_prefix 函数接受一个 size_t 类型的参数 n，表示要移除的字节数。函数首先检查 n 是否小于等于 Slice 对象的长度，如果不是，程序会终止运行。然后，函数将 data_ 指针向后移动 n 个字节，同时将 size_ 减去 n。

需要注意的是，remove_prefix 函数并不会改变原始数据，它只是改变了 Slice 对象的 data_ 指针和 size_。因此，remove_prefix 函数的时间复杂度是 O(1)，不会随着 n 的增大而增大。

总的来说，remove_prefix 函数是一个简单而高效的函数，它可以方便地移除 Slice 对象表示的字节序列的前 n 个字节

status

用于记录leveldb中状态信息，保存错误码和对应的字符串错误信息(不过不支持自定义)。其基本组成

代码为拼接过程：

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

 private:
  enum Code {
    kOk = 0,
    kNotFound = 1,
    kCorruption = 2,
    kNotSupported = 3,
    kInvalidArgument = 4,
    kIOError = 5
  };

Status::Status(Code code, const Slice& msg, const Slice& msg2) {
  assert(code != kOk);
  const uint32_t len1 = static_cast<uint32_t>(msg.size());
  const uint32_t len2 = static_cast<uint32_t>(msg2.size());
  const uint32_t size = len1 + (len2 ? (2 + len2) : 0);
  char* result = new char[size + 5];
  std::memcpy(result, &size, sizeof(size));
  result[4] = static_cast<char>(code);
  std::memcpy(result + 5, msg.data(), len);
  if (len2) {
    result[5 + len1] = ':';
    result[6 + len1] = ' ';
    std::memcpy(result + 7 + len1, msg2.data(), len2);
  }
  state_ = result;
}

编码

leveldb中分为定长和变长编码，其中变长编码目的是为了减少空间占用。其基本思想是：每一个Byte最高位bit用0/1表示该整数是否结束，用剩余7bit表示实际的数值，在protobuf中被广泛使用。

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

char* EncodeVarint32(char* dst, uint32_t v) {
  // Operate on characters as unsigneds
  uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
  static const int B = 128;
  if (v < (1 << 7)) {
    *(ptr++) = v;
  } else if (v < (1 << 14)) {
    *(ptr++) = v | B;
    *(ptr++) = v >> 7;
  } else if (v < (1 << 21)) {
    *(ptr++) = v | B;
    *(ptr++) = (v >> 7) | B;
    *(ptr++) = v >> 14;
  } else if (v < (1 << 28)) {
    *(ptr++) = v | B;
    *(ptr++) = (v >> 7) | B;
    *(ptr++) = (v >> 14) | B;
    *(ptr++) = v >> 21;
  } else {
    *(ptr++) = v | B;
    *(ptr++) = (v >> 7) | B;
    *(ptr++) = (v >> 14) | B;
    *(ptr++) = (v >> 21) | B;
    *(ptr++) = v >> 28;
  }
  return reinterpret_cast<char*>(ptr);
}

低位在低地址，然后，根据v的大小选择不同的编码方式。如果v小于128（即7位），则直接将v存储在ptr指向的位置，并将ptr指针向后移动一个字节。如果v大于等于128，则需要使用多个字节进行编码。具体的编码方式是，将v的低7位存储在ptr指向的位置，并将ptr指针向后移动一个字节。然后，将v的下一个7位存储在ptr指向的位置，并将ptr指针向后移动一个字节。依此类推，直到将v的所有字节都编码完毕。

skiplist

是一种可以代替平衡树的数据结构，可以看做是并联的有序链表。跳跃表通过概率保证平衡

跳表（Skip List）是一种用于有序链表的数据结构，它允许快速地进行搜索、插入和删除操作。跳表通过在原始链表上增加多层索引来加速搜索操作，从而提高了链表的查询效率。

跳表的基本思想是在原始链表的基础上增加多层索引，每一层索引都是原始链表的一个子集，且每一层索引的元素都是前一层索引的元素的子集。最底层索引就是原始链表本身。每一层索引中的元素都包含一个指向下一层索引中相同元素的指针。

通过这种方式，跳表可以在进行搜索操作时，通过从最高层索引开始，逐层向下查找，直到找到目标元素或者找到一个比目标元素大的元素为止。这样，跳表的搜索操作的时间复杂度可以达到O(log n)，其中n是链表中的元素个数。

跳表的插入和删除操作也比较高效。在插入操作中，跳表会根据一定的概率随机选择插入到哪一层索引中，从而保持索引的平衡性。在删除操作中，跳表会根据需要更新索引，以保持索引的正确性。

总的来说，跳表是一种高效的数据结构，它在有序链表的基础上增加了多层索引，从而提高了搜索、插入和删除操作的效率。跳表的实现相对简单，且具有较好的性能，因此在实际应用中被广泛使用。

插入

布隆过滤器

在平常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。

最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是浪费存储空间。那有没有更优化的数据结构呢？

简介

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是由一个很长的bit数组和一系列哈希函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中。

布隆过滤器还拥有k个哈希函数，当一个元素加入布隆过滤器时，会使用k个哈希函数对其进行k次计算,得到k个哈希值，并且根据得到的哈希值，在维数组中把对应下标的值置位1。

在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。

即错误率越低，位数组越长，控件占用较大错误率越低，无偏hash函数越多，计算耗时较长

增加元素

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1

通过k个无偏hash函数计算得到k个hash值依次取模数组长度，得到数组索引将计算得到的数组索引下标位置数据修改为1

例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1.

查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：

通过k个无偏hash函数计算得到k个hash值依次取模数组长度，得到数组索引判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

关于误判，其实非常好理解，hash函数在怎么好，也无法完全避免hash冲突，也就是说可能会存在多个元素计算的hash值是相同的，那么它们取模数组长度后的到的数组索引也是相同的，这就是误判的原因。例如李子捌和李子柒的hash值取模后得到的数组索引都是1，但其实这里只有李子捌，如果此时判断李子柒在不在这里，误判就出现啦！因此布隆过滤器最大的缺点误判只要知道其判断元素是否存在的原理就很容易明白了

使用场景

1. 黑名单校验
2. 快速去重
3. 爬虫URL校验
4. leveldb/rocksdb快速判断数据是否已经block中，避免频繁访问磁盘
5. 解决缓存穿透问题