LevelDB源码解析(3) 变长编码
背景
LevelDB在内存中存储key、value时，最后是以单值形式存储到一个跳跃表中的，跳跃表我们在上一篇文章LevelDB源码解析之SkipList(跳跃表）聊过了。这里主要想谈一下，LevelDB是如何把key、value编码到一个单值里面的，顺带分析一下为什么要这样做。
思考题
如何把一对key、value编码到一个单值中呢？很自然的一个想法是用冒号做分割，存储成key:value这种格式。但是如果key或者value里面有冒号怎么办？总不能规定不允许使用冒号吧？所以使用特殊符号做区分是不够通用的。
一种常见的方法是用size-value的方式。比如先用4字节存储key的size，然后再存储key，再存储value的size和value。这种方式避免了使用特殊符号分割的局限性，通用性是OK的。缺点是多了两个size域，额外占用8个字节的存储。如果key和value都是比较小的，那么size域产生的存储开销就很可观了。假设key和value也都是4个字节，总共8个字节。size域的8个字节就使用了一半的存储空间了。
既然key和value这么小，我能不能只用2个字节存储size呢？如果key和value的大小能够限制在2^18大小，这样是可以的。但是如果有的key或者value超过这个大小就无法存储了。
总结一下，其实矛盾点就在于使用固定大小的size域，要么浪费空间，要么无法适配更大的key和size。这里就要引入我们今天的主题，size变长编码了。
LevelDB的变长编码
LevelDB的解决方案是把size域每个字节的bit0设置为标记位，bit1~bit7存储size的值。如果bit0为0，表示size域到当前字节结束。下一个字节就是数据域了，如果bite0为1，表示下一个字节还是size域。
比如：
- size=7，size域只有一个字节，二进制编码为 00000111，变长编码为00000111。bit0为0，表示当前字节是size域最后一个字节。
- size=300，size域有两个字节，二进制编码为 0000010 0101100，这里为了方便理解，二进制bit按照7个bit为一组进行了拆分，变长编码其实只需要给每个7元bit组的前面加一个标记bit即可，最终变长编码为：10000010 00101100。第1个字节的bit0为1，表示size域还没有结束，第2个字节的bit0为0，表示当前字节是size域最后一个字节。
- size=300000，size域有三个字节，二进制编码为 0010010 0100111 1100000，变长编码为 10010010 10100111 01100000。
- 以此类推，实际上可以支持任意大小的size，不过一般2^32的size基本能满足所有需求了。
因为实际使用kv时，大部分的key和value的size都是比较小的，变长编码只需要一个字节或者两个字节基本就能满足需求。这样相对于4个字节的固定编码，节省了至少一半的存储空间。
如果了解大端序和小端序的话，会发现上面的变长编码使用的是大端序，即高位放在了低地址位。大端序在解码和编码时，要比小端序麻烦一些，性能也要差一些，所以实现的时候推荐使用小端序，LevelDB使用的就是小端序实现.
LevelDB的实现代码
//编码入口
char* EncodeVarint32(char* dst, uint32_t v)
{
uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
static const int B = 128; //B = 1000 0000
if( v < (1 << 7))
{
//v小于2^7，直接写入size域（因为v < 2^7,所以bit0标记位一定为0）
*(ptr++) = v;
}else if( v < (1 << 14))
{
//v 小于 2^14
//v的低7位，前面加上值为1的标记比特，8个bit写入size域
*(ptr++) = v | B;
//v右移7位后的低8位直接写入size域，因为v<2^14,所以此时低8位的bit0一定是0
*(ptr++) = v >> 7;
}else if( v < (1 << 21))
{
//v的低7位，前面加上值为1的标记比特，8个bit写入size域
*(ptr++) = v | B;
//v右移7位后的低7位前面加上值为1的标记位，共8bit写入size域
*(ptr++) = (v >> 7) | B;
//v右移14位后的低8位直接写入size域
*(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);
}
//解码入口
inline const char* GetVarint32Ptr(const char* p, const char* limit, uint32_t* value)
{
if( p < limit )
{
uint32_t result = *(reinterpret_cast<const uint8_t*>(p));
//如果result & 1000 0000为0，说明第一个字节的标记位为0，即size域只有一个字节，直接返回结果
if((result & 128) == 0 )
{
*value = result;
return p + 1;
}
}
//size域不只一个字节，返回变长编码
return GetVarint32PtrFallback(p, limit, value);
}
//解析变长编码的逻辑很简单，每次取一个字节，取bit1-bit7计算size，如果bit0为0，就结束。
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 uint8_t*>(p));
p++;
//byte & 1000 0000
if( byte & 128 )
{
//与运算结果为1说明size域还没结束，取bit1-bit7写入result对应的bit位
result |= ((byte & 127) << shift);
}else
{
//与运算结果为0说明当前字节是size域最后一个字节，取bit0-bit7写入result
//因为bit0为0，所以不需要先和127求与了
result |= (byte << shift);
*value = result;
return reinterpret_cast<const char*>(p);
}
}
return nullptr;
}
代码添加了一些注释，比较容易看懂了，这里就不细说了。解码代码中一个优化性能的方式可以留意一下。GetVarint32PtrFallback实际上可以完成完整的解码，但是当size域只有一个字节时，作者直接在GetVarint32Ptr中进行了解码。细心的读者应该已经发现这个函数是一个内联函数。而GetVarint32PtrFallback只是一个普通函数。这里相当于为size域只有一个字节的这种场景进行了性能优化，把多字节的场景放到普通函数中去解码。这样一个字节时调用的是只有几行代码的内联函数，多个字节时调用的是代码较多的普通函数。兼顾了性能和内存占用。