按照我们上一节的目录结构，我们就先从 utils 目录开始入手分析。utils 目录中存放了很多 levelDB 所使用到的基础功能，例如：简单的内存管理系统 arena，编码方式 coding，提供给调用者的文件系统接口 env，布隆过滤器 bloomfiter 等等。在阅读源码的过程中，你可能会觉得这些是很不起眼或者是非常简单的话题，但是所有复杂的系统都是从基础堆叠起来的，因此，仔细地阅读基础模块是非常重要的。今天我们从编码 encoding 说起。
我们知道 levelDB 需要高效的将键值 Key 和 Value 存入到内存中，并序列化到磁盘上。为了节省空间，作者采用了几种简单灵活又不失效率的编码方式。
首先，定长的编码方式就是将 4 字节和 8 字节的数据按序写入到指定的位置。注意写入的时候会根据当前的机器是大端还是小端序做一个区分，代码如下非常好理解 (8字节的同理)：
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;
}
}
为了节省空间，levelDB 同时采用了变长的编码方式，这也是 levelDB 本身的功能所需求的。考虑一下，在 leveldb 的运行过程中，会涉及到大量的字符串序列化过程，而最简单的无压缩的字符串编码方式就是：len(str) + str 的格式，也就是先存下字符串的长度，然后在存下字符串的数据。在大部分情况下，字符串的长度都不会太长，也就是不会超过一个字节所能表示的整数的范围。如果我们将每个小整数都使用 4 个字节来进行存储，势必会浪费很多的空间（当同时存储上百万的 Key/Value 对时问题就出现了）。在这一点上 Redis 中的 ziplist 可能更能说明问题。如果有兴趣，可以去阅读以下 ziplist 是怎么做到针对字符串的压缩的。
LevelDB 使用了一种很简单的方案 varint 来节省小整数的存储。对于每一个字节，levelDB 使用其最高的 bit 位来表示当前的编码是否结束，而用低 7 bit 来存储实际的数据。如果最高位为1，表示当前的编码尚为结束，需要继续读下一字节的数据，否则当前的编码结束。简单来说，就是把平时的编码方式由 8 bit 制改为了 7 bit 制。因此在区间 [0-127] 内的整数都可以使用一个字节来表示。我们使用一个示意图来说明一下 (借鉴了这里)：
1. 对于比较大的数，如果存储的数据如下
1001 0001 1000 1001 0111 1100
^ ^ ^ A: 最高位是1，未结束，实际值是后七位 001 0001
| | | B: 最高位是1，未结束，实际值是后七位 000 1001
A B C C: 最高位是0，结束， 实际值是后七位 111 1100
因此，三个字节拼接应该是 C + B + A :
[1111100][000 1001][0010001] = 2032785
2. 对于 [0-127] 的整数，例如：
0001 0001
^ A: 第一字节，最高位为0，表示结束，实际值是 0010001
| 也就是 33
A
需要注意的是，在编码变长整数的时候是从最低字节开始的。也就是说，如果将数字 N 编码得到字节数组 char* K，那么 K[0] 存储的是 N 的最低 7 bit 的数据，这也就是为什么上面要 C+B+A 才会得到原始数据。知道了原理再来看代码就很好理解了:
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);
}
作者考虑到对于 8 字节的整数同样按照上面的每字节的处理方式太麻烦了，因此换了种写法。总体而言就是每次取出 v 中的 7 个 bit 然后判断是否需要在最低位加上 1，之后再拼接起来。
char* EncodeVarint64(char* dst, uint64_t v) {
static const int B = 128;
unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
while (v >= B) {
*(ptr++) = (v & (B-1)) | B;
v >>= 7;
}
*(ptr++) = static_cast<unsigned char>(v);
return reinterpret_cast<char*>(ptr);
}
上面只说明了编码的方式，针对解码的代码就不再一一细说了。需要注意的是，解码的过程其实可以分为一个 Fastpath 和一个 slowpath。Fastpath 的意思就是，如果取出的第一个字节 B 满足 B & 128 == 0，说明整数值位于 [0-127] 之间，因此可以直接解码得到 B & (128-1)。之所以提到这点，是因为我们在设计一个复杂的函数过程中，应该清楚地思考一下其流程是否能够分为 Fastpath 和 Slowpath，如果能够时时刻刻意识到这一点，生活中的很多问题都会有非常清晰的解决思路。