纸上得来终觉浅，绝知此事要躬行

本项目基本就是重新敲一遍源码，加上一些注释和修改某些函数的实现方式，功能保持不变，目的就是学习大神们如何设计及编写出优秀的代码。

初试牛刀

据leveldb的设计可知，leveldb适合写操作多于读操作的应用场合，即写的效率高于读的效率，顺序读取的效率高于随机读取的效率。

编译源码，只需在包含makefile文件的目录下执行make命令即可，很顺利编译完成。
写一个程序(test.cc)使用该库，代码如下：

#include <include/leveldb/db.h>
#include <string.h>
#include <assert.h>
#include <iostream>
int main(){
    leveldb::DB* db;
    leveldb::Options options;
    options.create_if_missing = true;cy_test: test.o $(LIBOBJECTS) $(TESTHARNESS)
    leveldb::Status status = leveldb::DB::Open(options,"/tmp/test", &db);
    assert(status.ok());

    std::string key="vic";
    std::string value = "666";

    status = db->Put(leveldb::WriteOptions(), key,value);
    assert(status.ok());

    status = db->Get(leveldb::ReadOptions(), key, &value);
    assert(status.ok());
    std::cout << key <<"'s value is:" << value << std::endl;
    delete db;
    return 0;
}

编译该测试程序，我觉得最简单的方法就是修改原makefile文件，新增一个目标对象即可。例如，新增cy_test目标对象:

cy_test: test.o $(LIBOBJECTS) $(TESTHARNESS)
    $(CXX) $(LDFLAGS) test.o $(LIBOBJECTS) $(TESTHARNESS) -o $@ $(LIBS)

输入make cy_test后运行./cy_test得到结果：vic's value is:666

下面记录一些值得注意的地方

1. include/leveldb/slice.h data()和c_str()

作者在Slice中的构造函数上使用string的成员函数data()将string转换成char *：

class Slice {
 public:
  ...
  // Create a slice that refers to the contents of "s"
  Slice(const std::string& s) : data_(s.data()), size_(s.size()) { }
  ...

c++98标准中关于data()有这样一段话：

Accessing the value at data()+size() produces undefined behavior: There are no guarantees that a null character terminates the character sequence pointed by the value returned by this function.

通俗点说，data()转换后的字符数组结尾不保证有终结符'\0'，标准只是没有要求一定要有'\0'，不代表一定没有'\0'，不同的编译器可能得的结果不同，准确地说，这里的不同的编译器其实是指不同的C++ STL版本。

不过，这一问题在C++11标准中得到了解决，data()转换后的字符数组以'\0'结尾，同c_str()一样，原文描述如下：

Returns a pointer to an array that contains a null-terminated sequence of characters (i.e., a C-string) representing the current value of the string object. This array includes the same sequence of characters that make up the value of the string object plus an additional terminating null-character ('\0') at the end.

2. include/leveldb/options.h

在options.h文件中，作用通过声明的方式来使用其他文件中对应的类，如下所示：

#include <stddef.h>
namespace leveldb {
    class FilterPolicy;
    class Cache;

我修改如下，显示地引入头文件，注释了类的声明。

#include <stddef.h>
#include "filter_policy.h"
namespace leveldb {
    // class FilterPolicy;
    class Cache;

上述的做法本质是相同的，通过宏指令#include显示地把需要的头文件包含进来，这些头文件会在预处理阶段被编译器替换成相应的代码。

若不使用#include，只需显示地给出需要用到的类声明即可。那么，预处理阶段没有找到类的实现代码，但它不会报错，它默认认为这该类在其他文件中给出了定义，此处会增加标记告诉编译器此符号未定义，需要在链接阶段找到它的定义，从哪找？从参与链接目标文件中取找，怎么找？遍历目标文件的符号表(Linux中目标文件的格式是ELF，符号表是ELF文件中的一个entry)。

挖坑:整理一下编译器的工作过程->链接的过程->ELF文件的格式(2种，可链接可执行的和可执行的)->ELF格式为何要这样设计?(联系虚存的中各种area，方便加载到虚存中)->虚拟内存相关知识。)

最终编译出的库是完全一样的，我觉得各有千秋：

#include的方法缩短编译时间，避免了链接阶段的遍历；
而通过声明的方式是减少了编程人员的工作，避免了头文件重复引用的问题。

3. include/leveldb/status.h util/status.cc

在 status.h中，有一些成员函数，如：

// Return error status of an appropriate type.
  static Status NotFound(const Slice& msg, const Slice& msg2 = Slice()) {
    return Status(kNotFound, msg, msg2);
  }

调用了自定义的有参构造函数，该构造函数的定义如下：

...
Status(Code code, const Slice& msg, const Slice& msg2) {
  assert(code != kOk);
  const uint32_t len1 = msg.size();
  const uint32_t len2 = msg2.size();
  const uint32_t size = len1 + (len2 ? (2 + len2) : 0);
  char* result = new char[size + 5];
  memcpy(result, &size, sizeof(size));
  result[4] = static_cast<char>(code);
  memcpy(result + 5, msg.data(), len1);
  if (len2) {
    result[5 + len1] = ':';
    result[6 + len1] = ' ';
    memcpy(result + 7 + len1, msg2.data(), len2);
  }
  state_ = result;
}
...

在msg是用户自定义的错误描述字符串，用法如下：

...
return Status::NotFound("in-memory file skipped past end");
...

看到这里，有一点不太明白: 既然msg是自定义的错误描述信息，那么msg2的存在意义是什么呢？

4. include/leveldb/comparator.h util/comparator.cc

对key排序时使用的比较方法。默认为升序。

5. include/leveldb/write_batch.h db/write_batch.cc

对若干数目 key 的 write 操作(put/delete)封装成 WriteBatch

6. util/coding.h util/coding.cc

为了节省空间，原作者设计了一种变长编码方式来表示整型：varint。越小的数字所用的字节数越少。

Varint编码

一般int需要3-byte来表示一个整数，varint使用的变长编码的方式和utf-8编码的方法本质上是一样的，下面表示的一个3字节的utf8编码： ''' 1110xxxx 10xxxxxx 10xxxxxx ``` 第一字节中的从最高位开始，有连续几个1就表示该字符有几个字节，后面的每一字节都以`10`开头。

同样的道理，在varint变长编码中，如果每个字节的最高为1，表示后续的字节也是该数字的一部分；如果该位位0，则结束。

// 变长编码
//
// 每个数字用1到5个字节来编码，每个字节中的最高bit为标识位，
// 剩下的7位用于表示数据
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)) {             // iff v < 128 then encode with 1-byte
    *(ptr++) = v;
  } else if (v < (1<<14)) {     // iff 128 <= v < 2^14 then ... 2-byte
    *(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 {                      // encode with with 5-byte
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = (v>>14) | B;
    *(ptr++) = (v>>21) | B;
    *(ptr++) = v>>28;
  }
  return reinterpret_cast<char*>(ptr);
}
void PutVarint32(std::string* dst, uint32_t v) {
  char buf[5];

varint解码

inline const char* GetVarint32Ptr(const char* p,
                                  const char* limit,
                                  uint32_t* value) {
  if (p < limit) {
    // 非const转换成const
    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) {    // 最高位位1，还有后续字节
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return NULL;
}

6.SkipList

当我们插入的记录一条记录时，会先写log日志，然后将数据插入到memtable中，从名字也可以看出，memtable是在内存中的，当数据量到达一定量后再写到硬盘中，用sstable数据结构来组织数据的。

memtable是利用有名的SkipList来组织数据的，它是由William Pugh在论文：Skip lists: a probabilistic alternative to balanced trees中提出。下面的gif很形象的展示了skiplist的结构和查询/插入的过程，每个节点的level是随机生成的，动图中的coin flip展示了这一过程。一图胜千言。图片摘自[wiki] (https://en.wikipedia.org/wiki/Skip_list)

关于它的分析，网上有很多的类似博文，可以参考segmentfault中的这篇

snipercy/leveldb