RocksDB源码学习一

发表于

编码

第一章先来看一下Rocksdb的编码情况，具体的实现在：util/coding.cc, util/coding.h, util/coding_lean.h。Rocksdb的编码实现与leveldb基本一致的，由于需要将Key、Value等数据按序写入到内存中，并最终flush到磁盘上，因此需要一个高效的编解码实现。这里的编解码很多会用在key size、value size的整型编码上面。

Rocksdb的整型编码方式很简单，主要支持两种方案：定长编码和变长编码。

  • 定长编码：定长编码的实现比较简单，比如可以直接将4字节/8字节的整型直接按序写入到指定的位置；
  • 变长编码：节省空间，如果用定长编码的方式，实际上对于小数来说，很多位其实是没必要存储。结合ASCII码的特点，所有字符ASCII码的最高位都是0，可以利用最高位去做一些特别的标记；

实现

字节端序

关于编码，首先需要了解计算机在存储字节时分为大端字节序和小端字节序两种，Rocksdb是用小端序存储（低位放在较小的地址处，高位放在较大的地址处）的，因此需要提供根据不同平台对内存存储模型进行转换的选项。

在port/port.h文件内包含了一些平台相关的的头文件：

1
2
3
4
5
#if defined(ROCKSDB_PLATFORM_POSIX)
#include "port/port_posix.h"
#elif defined(OS_WIN)
#include "port/win/port_win.h"
#endif

以port_posix.h为例，这里包含了posix平台关于大小端的定义：

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
#undef PLATFORM_IS_LITTLE_ENDIAN
#if defined(OS_MACOSX)
  #include <machine/endian.h>
  #if defined(__DARWIN_LITTLE_ENDIAN) && defined(__DARWIN_BYTE_ORDER)
    #define PLATFORM_IS_LITTLE_ENDIAN \
        (__DARWIN_BYTE_ORDER == __DARWIN_LITTLE_ENDIAN)
  #endif
#elif defined(OS_SOLARIS)
  #include <sys/isa_defs.h>
  #ifdef _LITTLE_ENDIAN
    #define PLATFORM_IS_LITTLE_ENDIAN true
  #else
    #define PLATFORM_IS_LITTLE_ENDIAN false
  #endif
  #include <alloca.h>
#elif defined(OS_AIX)
  #include <sys/types.h>
  #include <arpa/nameser_compat.h>
  #define PLATFORM_IS_LITTLE_ENDIAN (BYTE_ORDER == LITTLE_ENDIAN)
  #include <alloca.h>
#elif defined(OS_FREEBSD) || defined(OS_OPENBSD) || defined(OS_NETBSD) || \
    defined(OS_DRAGONFLYBSD) || defined(OS_ANDROID)
  #include <sys/endian.h>
  #include <sys/types.h>
  #define PLATFORM_IS_LITTLE_ENDIAN (_BYTE_ORDER == _LITTLE_ENDIAN)
#else
  #include <endian.h>
#endif

constexpr bool kLittleEndian = PLATFORM_IS_LITTLE_ENDIAN;
#undef PLATFORM_IS_LITTLE_ENDIAN

定长编码

定长编码比较简单，首先判断大小端序，对于小端，value本身就是按小端排放的，可以直接拷贝；对于大端，则是将value的最低位放置在内存的最低地址端。

1
2
3
4
5
6
7
8
9
10
inline void EncodeFixed32(char* buf, uint32_t value) {
  if (port::kLittleEndian) {
    memcpy(buf, &value, sizeof(value));
  } else {
    buf[0] = value & 0xff;
    buf[1] = (value >> 8) & 0xff;
    buf[2] = (value >> 16) & 0xff;
    buf[3] = (value >> 24) & 0xff;
  }
}

解码也一样，Rocksdb提供了三种整型编解码：uint16_t,uint32_t,uint64_t。解码时，gcc会优化里面的memcpy的操作，变成inline copy loops，提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline uint32_t DecodeFixed32(const char* ptr) {
  if (port::kLittleEndian) {
    // Load the raw bytes
    uint32_t result;
    memcpy(&result, ptr, sizeof(result));  // gcc optimizes this to a plain load
    return result;
  } else {
    return ((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0]))) |
            (static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) << 8) |
            (static_cast<uint32_t>(static_cast<unsigned char>(ptr[2])) << 16) |
            (static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) << 24));
  }
}

变长编码

前面提到的，为了节省空间，Rocksdb使用变长的编码方式varint。Rocksdb使用最高位来表示编码是否结束，而低7bit则存储实际的数据。根据统计来说，小整型出现的概率更高，这样就能节省更多的空间，比如0-127的整数都可以只用一个字节来表示，而uint32较大的数字则需要5个字节。

1
2
3
4
5
6
7
0001 0001 ====>> 表示33
^                           A: 最高位为0，表示结束；
A
=======================================================
1000 0011 0110 1111 ====>> 表示1007
^         ^                 A: 最高位为1，表示未结束，实际值是000 0011；
A         B                 B: 最高位为0，表示结束，实际值是110 1111；

具体的编码以uint32_t为例，将uint32_t编码成变长字符：

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
  unsigned char* ptr = reinterpret_cast<unsigned char*>(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);
}

uint64_t的变长编码实现，作者用了循环来编码，每7bit一组，并在最低位判断是否需要置位1。因此对于64位整型，最多需要10个字节：

1
2
3
4
5
6
7
8
9
10
inline char* EncodeVarint64(char* dst, uint64_t v) {
  static const unsigned int B = 128;
  unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
  while (v >= B) {
    *(ptr++) = (v & (B - 1)) | B; // leveldb的实现是v | B; 不明白区别在哪
    v >>= 7;
  }
  *(ptr++) = static_cast<unsigned char>(v);
  return reinterpret_cast<char*>(ptr);
}

解码的实现也有一些优化，主要是利用内联函数提高效率，当数字小于等于127时，直接返回结果：

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
inline const char* GetVarint32Ptr(const char* p,
                                  const char* limit,
                                  uint32_t* value) {
  if (p < limit) {
    uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
    if ((result & 128) == 0) {
      *value = result;
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p, limit, value);
}

const char* GetVarint32PtrFallback(const char* p, const char* limit,
                                   uint32_t* value) {
  uint32_t result = 0;
  for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
    uint32_t byte = *(reinterpret_cast<const unsigned char*>(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;
}

总结

编解码这里还是比较简单和高效的，比较有意思的是实现了一个variant编码，源码值得一看。