leveldb学习记录-编码

发表于 2021-09-29 更新于 2020-12-26 分类于 leveldb 阅读次数：

计算机硬件有两种数据存储的方式：大端字节序和小端字节序

举例来说，数值0x2211使用两个字节储存：高位字节是0x22，低位字节是0x11。

大端字节序：高位字节在前，低位字节在后，这是人类读写数值的方法。

小端字节序：低位字节在前，高位字节在后，即以0x1122形式储存。

编码分为变长的VarInt和固定大小的FixedInt两种，每种分32位和64位。

变长编码

为了节省空间，设计了一种varint变长编码方式来表示整型，越小的数字所占用的字节数越少。不采用变长编码，存放一个int类型的1，一般情况下需要4个字节，采用变长编码后，仅需要1个字节就可以保存。leveldb的变长编码也是采用小端序

Varint 中的每个 byte 的最高位 bit 是标识位有特殊的含义。如果该位为 1，表示后续的 byte 也是该数字的一部分，
如果该位为 0，则结束。其他的 7 个 bit 都用来表示数字。

编码过程和解码过程举例：

编码过程：

假设一个待表示的数为1000，二进制表示为==111== 1101000

字节1：取最右边的7bit，1101000，高位补0凑成一个字节：0110 1000

字节2：剩下的是==111==,同样高位补0，0000 0111

字节1最高bit位标识为1，表示后续的byte也是该数字的一部分。

字节2最高bit位标识为0。

故最终的编码结果为：

1110 1000 0000 0==111==

解码过程：

读取第一个字节，发现其最高bit位为1，表示还有后续，与下一字节一同表示同一个数值。将最高bit位变为0后，第一个字节：0110 1000

下一个字节：0000 0==111==

按照小端序，字节交换后位置结果是：==111== 1101000 =》十进制为1000

leveldb中的实现

【编码】

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;//0x80，用来设置一个字节的最高位
  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);
}


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);
}

【解码】

bool GetVarint32(Slice* input, uint32_t* value) {
  const char* p = input->data();
  const char* limit = p + input->size();
  //encode后的值存储到value，返回剩余的字符串
  const char* q = GetVarint32Ptr(p, limit, value);
  if (q == nullptr) {
    return false;
  } else {
    //修改input，存储剩余的字符串
    *input = Slice(q, limit - q);
    return true;
  }
}

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));
    //对小整数的优化，只有原整数<128，编码后的result才满足result&128 == 0
    if ((result & 128) == 0) {//与128相与为0表示待解码的result<=127，所以长度就是一个字节直接赋值给*Value即可。
      *value = result;
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p, limit, value);
}

const char* GetVarint32PtrFallback(const char* p, const char* limit,
                                   uint32_t* value) {
    //对于超过一个字节的长度编码，解码的过程就是按小端顺序，每7位取出，然后移位来组装最后的实际长度，组装结束的表示就是MSB位为0
  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++;
    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封装了一个Put函数，便于用户调用

void PutVarint32(std::string* dst, uint32_t v) {
  char buf[5];
  char* ptr = EncodeVarint32(buf, v);
  //写入encode后的值(大小为ptr - buf)
  dst->append(buf, ptr - buf);//将编码结果保存在dst中
}

这里申请的buffer缓冲区大小为5个字节，因为变长编码的范围，对于32位（Varint32）整形数经变长编码后占用15个Byte，小的数字用1个字节，大的数字0xffff ffff用5个字节。
对于64为（Varint64）整形数经变长编码后占用110个Byte，小的数字用1个字节，大的数字用10个字节。

PutLengthPrefixedSlice函数

void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
  //首先写入encode后的value大小
  PutVarint32(dst, value.size());
  //其次写入data数据
  dst->append(value.data(), value.size());
}

对于一个数据，调用PutLengthPrefixedSlice函数，将他的长度和数值放入dst中。

GetLengthPrefixedSlice函数

bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
  uint32_t len;
  //从input先解析出字符串长度
  if (GetVarint32(input, &len) &&
      input->size() >= len) {
    //再从input解析出字符串，记录到result
    *result = Slice(input->data(), len);
    //调整input跳过已经解析的字符串
    input->remove_prefix(len);
    return true;
  } else {
    return false;
  }
}

将编码后的string中的字符串长度移除，得到原始的字符串。

还有一同名的重载函数

const char* GetLengthPrefixedSlice(const char* p, const char* limit,Slice* result) 
{
 //对内存buffer按照varint解码，解码后的整数存储到value
// 内存buffer从p开始，最大不超过limit
// 返回已经解析的buffer的下一个字节，即p + len(varint编码)
  uint32_t len;
  p = GetVarint32Ptr(p, limit, &len);
  if (p == nullptr) return nullptr;
  if (p + len > limit) return nullptr;
  *result = Slice(p, len);
  return p + len;
}

Honor's Blog