levelDB之Varint

发表于 更新于

前言

Leveldb 作为一个 kv 数据库，使用的 lsm-tree，一句话解释 lsm-tree 就是将数据按照字符排序。首先将数据写入内存，然后将数据刷入磁盘，定时合并文件。在每个文件头部记录下当前最小最大的 key，然后使用 bloom 记录是否存在 key，查询的时候根据二分查找等方式进行数据查找。
数据是紧凑的写在内存或磁盘上的，所以每条数据都会记录当前值的长度和具体的值形如：[key_length][key][value_length][value]，如 key 为 key_123,value 为 value_123,记录方式就是[7][key_123][9][value_123]。一个 32 位整型的空间一般是 4 个字节，Leveldb 就是觉得这个 4 个字节实在是太多了，如上文，当前的 key 是 7，其实只需要一个字节就可以表示，所以在这个上面 Leveldb 使用了 Varint。具体在leveldb/util/coding.cc和leveldb/util/coding.h中实现，本文就是对其中的实现做一个简单的介绍和分析。

具体实现

Leveldb 中上文提到的两个源码文件中，包含了两种，一种是 Varint 和 Fixed，包含了 32 位和 64 位，也就是 32 位整型和 64 位整型 的值。核心都是使用 char 数组来表示 32 位整型和 64 位整型。

编码具体实现

下面是编码方法列表

1
2
3
4
5
char* EncodeVarint32(char* dst, uint32_t value);
char* EncodeVarint64(char* dst, uint64_t value);
// 在coding.h 文件中直接实现的内联函数
inline void EncodeFixed32(char* dst, uint32_t value);
inline void EncodeFixed64(char* dst, uint64_t value);

为了将 32 位整型或者 64 位整型 使用 char 数据记录，肯定需要对 int 的 4 位字节分别存储，也就是每次移动 8 位，为了标识当前字节处于整个字节的位置，还需要预留一个标识符，所以每一个 char 最多有 7 位标识一个 int，2 的 7 次方，也就是一个 char 最多标识 128 的数据。也就是说如果超过了 2 的 28 次方，可能需要额外的字节来标识。也就是说 int 值最多需要 5 个字节来表示。对应的 64 位整型类型则需要使用 64/7 +1 也就是 10 个字节来标识。

32 位整型

下面的代码核心其实就是分为 5 个字节如何存储，每一个 if 就是一个多出一个字节。

*(ptr++) = v;的写法结果：

  1. 从 ptr 指向的地址获取一个指向的值。
  2. 将变量 v 的值赋给该地址处。
  3. 将 ptr 的值增加 1，使其指向下一个地址。

代码如下：

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);// 将当前指针变成uint8_t类型的指针
  static const int B = 128; // 2的 七次方，确1000 0000
  if (v < (1 << 7)) {
    *(ptr++) = v; // 如果当前的值小于2^7，则直接将值写入指针，最大标识0111 1111 即127
  } else if (v < (1 << 14)) {
    *(ptr++) = v | B; // 如果值大于2^7，小于2^14，则首先小后七位写入第一个字节，也就是说是小端存储，此时该字节首位是1，因为B 1000 0000  使用或的关系只是将后七位和原值相等，首位赋值1
    *(ptr++) = v >> 7; // 将剩下的值写入，此时首位为0
  } else if (v < (1 << 21)) { // 大于2^14小于2^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); // 将值转换会原来的位置
}

举例说明下面的各个字节标识：

原始值 32 位二进制 转换后
1 00000000 00000000 00000000 00000001 00000001
129 00000000 00000000 00000000 10000001 10000001 00000001
65537 00000000 00000001 00000000 00000001 10000001 10000000 00000100

上面分别为 1，2^7+1 ，2^16+1,也就是分别需要 1 字节，2 字节和 3 字节的数据存储。所以 varint32 的值有以下特征：

  • 小端存储
  • 如果当前 char 的最高位是 1 ，则说明当前的值没有结束，一直到最高位为 0 的 char
64 位整形

64 位和 32 位基本上没有区别：

1
2
3
4
5
6
7
8
9
10
char* EncodeVarint64(char* dst, uint64_t v) {
  static const int B = 128;
  uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
  while (v >= B) {
    *(ptr++) = v | B;
    v >>= 7;
  }
  *(ptr++) = static_cast<uint8_t>(v);
  return reinterpret_cast<char*>(ptr);
}

实现上只是使用循环的方式，其他的都是一样的。这里就不赘述了。

解码具体实现

相对编码，解码里面提供了较为多方法，包含了和类外一个 LevelDB 比较重要的对象 Slice 的交互，这里先不看这个 Slice 的交互，只看解码的部分。

下面是我觉得两个比较核心的方法：

1
2
3
4
5
6
7
// Pointer-based variants of GetVarint...  These either store a value
// in *v and return a pointer just past the parsed value, or return
// nullptr on error.  These routines only look at bytes in the range
// [p..limit-1]
// 传入的待解码char开始指针p,待解码char结束指针，最后值写入的指针v。看方法参数可以看到，一般情况下都是在某个char* 类型的数据上进行顺序读取来获取数据，也就是p 和limit 应该是属于一个char* 的不同位置的指针，他的返回值是指向当前值结尾指针的下一个指针。如果出错，则返回nullptr
const char* GetVarint32Ptr(const char* p, const char* limit, uint32_t* v);
const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* v);

在实现上分为两种情况：

  1. 当前的值小于 128，即传入的 p 的第一个字节为 0，也就是上文编码中说的，如果首位为 0 ，则说明后续都没有数据了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    inline const char* GetVarint32Ptr(const char* p, const char* limit,
                                      uint32_t* value) {
      if (p < limit) { //确保p是在limit 前面的
        uint32_t result = *(reinterpret_cast<const uint8_t*>(p));
        if ((result & 128) == 0) { // p的第一个字节为0，说明当前值7位就可以标识，字节返回。
          *value = result;
          return p + 1; // 返回当前解码后值的后一个字节
        }
      }
      return GetVarint32PtrFallback(p, limit, value);
    }

如果超过 7 位，则进入到 GetVarint32PtrFallback 方法中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const char* GetVarint32PtrFallback(const char* p, const char* limit,
                                   uint32_t* value) {
  uint32_t result = 0;
    // 最多执行5次
  for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
    uint32_t byte = *(reinterpret_cast<const uint8_t*>(p));
    p++; // 移动p的指针
    if (byte & 128) { // 如果当前char的首位是1，说明后续还有值
      // More bytes are present
        // 取当前值的后7位，并且移动shift
      result |= ((byte & 127) << shift);
    } else {
        // 当前已经到尾部字节，将值写入即可
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
    // 出现如limit>p这种情况，字节返回nullptr
  return nullptr;
}

64 位的解码基本上和 32 位一样，只是移动次数变成了 10 次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
  uint64_t result = 0;
  for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
    uint64_t byte = *(reinterpret_cast<const uint8_t*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return nullptr;
}

总结

leveldb 针对 32 位和 64 位的整形进行了优化，能够节约空间。个人觉得这么做的主要目的是因为我们的 key 或者 value 的值长度一般不会很大，很少人会使用 2^32 个字节来作为 key 存储。所以这么做积少成多，确实能够节约不少的空间。使用 0,1 判断是否到数据尾部，确实很秀。