A Coder is a Poet

leveldb 利用 cache 来通过一个 key 快速地检索到 value 值，其在 include/leveldb/cache.h 中定义了 cache 应该实现的接口。leveldb 要求 cache 实现内部的同步，从而可以让外部的线程并发地访问。像前面介绍的运行时环境 Env 一样，外部的使用者可以根据接口自定义其 cache 的实现。同时，leveldb 也提供了默认的基于 LRU(Least-Recently-Used) 的 cache。

我们首先看一下 cache 的定义，其在类定义的时候声明了一个 Rep 结构，并在类中定义了一个指向 Rep 的指针 rep_：

class Cache {
private:
    struct Rep;
    Rep* rep_;
    ...
}

在后面的学习中我们可以看到，在 table_builder 的定义中，作者也采用了这种方式。可能有很多人不明白作者为什么采用这种方式来定义类成员。事实上，这正是 Scott Meyers 在 Effective C++ 条款 31 所提到的

今天我们来分析 leveldb 对于运行环境的封装。前面已经介绍过，leveldb 实际上就是一个基于文件存储的 KV 数据库。为了能够提供平台无关的文件系统操作方式，leveldb 的作者设计了统一的系统相关的文件操作接口。这些接口定义在头文件 include/leveldb/env.h 中。当需要移植 leveldb 到不同的系统上，或者利用不同平台的特性优化 leveldb 的性能时，用户可以自行实现 env.h 中的接口，也就是自行定义一套运行环境。

Env 中大部分的接口都与文件操作相关。根据文件 include/leveldb/env.h 中的说明，要自行定义一个 Env 大致需要实现以下几个类：

namespace leveldb {
    class FileLock;
    class Logger;
    class RandomAccessFile;
    class SequentialFile;
    class Slice;
    class WritableFile;
};

当然，leveldb 提供了其默认的 Env 实现，也就是 env_posix。 env_posix 适用于任何符合 posix 标准的文件系统上，在文件 utils/env_posix.cc 中定义。接下来我们就仔细分析下 env_posix 的实现。

最近花了两天时间看了下腾讯开源的 C++ 协程库 libco。libco 是微信后台大规模使用的 c/c++ 协程库，2013年至今稳定运行在微信后台的数万台机器上。其通过提供 socket 族函数的 hook，使得后台逻辑服务几乎不用修改逻辑代码就可以完成异步化改造。根据腾讯号称，libco 现在可以轻松达到单机千万并发。

有关 libco 的详细架构和实现我会在后续的博客中详细介绍，今天我们主要来关心一下 libco 介绍中所说的这个 高（chui）大（niu）上（bi）的实现细节，那就是通过 hook 系统的 socket 函数族来实现无需修改代码的异步化改造。简单来说，就是利用动态链接的原理来修改符号指向，从而达到『偷梁换柱』的编程效果。在介绍具体怎么做之前，我们需要回顾一下链接的知识。

不同于 redis 的内存管理方式（利用 jemalloc 或者 tcmalloc 做一层轻封装），LevelDB 根据自己的需求自行定制了一个简单的内存管理器 Arena，这个管理器将在后续 memtable 中被作为成员所使用。当每次向 memtable 中增加 Key/Value 时，memtable 将通过其 Arena 成员来为这些键值对分配空间。你暂时先不需要了解这个详细的过程，我们先讲一下这个简单的 Arena 实现原理。

Allocate 内存分配函数

根据代码来看，一个 Class Arena 拥有以下几个变量：

char* alloc_ptr_;                   // 指向当前 block 内还未使用的起始地址
size_t alloc_bytes_remaining_;      // 当前的 block 里还有多少字节可以使用
std::vector<char*> blocks_;         // 已经申请了的所有的内存块
port::AtomicPointer memory_usage_;  // 总的内存使用量统计

这里面出现了一个非常奇怪的变量类型 AtomicPointer，先不用管这个类型干什么的，现在就把它当做一个普通的 void* 指针就可以了 （有关 AtomicPointer 话题涉及到太多内容，先按下不表）。下图展示了 Arena 是怎么使用这几个变量的：

可以看到，Arena 每次都先从内存中申请一个 block(一般是 4KB，由参数 kBlockSize 定义)，然后将其放进 vector 中进行管理。当外部需要调用 Arena 申请内存时，Arena 都从当前这个 block 中，也就是图中的 block 3 中收集可用的内存返回给外部。其中 alloc_ptr 指向的位置就是未使用的内存开始的位置，从 block3 指针到 alloc_ptr 之间的都是已经使用过的内存。而当前块中还未被使用的内存数量即使用 alloc_bytes_remaining_ 来表示。

按照我们上一节的目录结构，我们就先从 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 是 google 的两位大神 Jeff Dean 和 Sanjay Ghemawat 开发的一个单机持久化 K/V 数据库。其基于 LSM(LOG Structured Merge Tree) 实现，将所有的 Key/Value 按照 Key 的词法序有序地储存在文件中，具有很高的随机/顺序写性能，非常适用于写多读少的环境。根据 LevelDB 的官网介绍，其具有特性如下：

1. Keys 和 Values 可以是任意的字节序列
2. 数据是按照 Key 排序的
3. 调用者可以提供一个定制的比较函数来决定 Keys 的排序方式。
4. 针对数据库的操作非常简单，i.e. Put, Get, Delete
5. 可以在一次原子的批处理中同时多次修改数据库
6. 用户可以创建 snapshot 保持对于数据视图的一致性
7. 这个数据结构提供前向和后向的迭代器 (iterator)
8. 数据可以自动经过 Snappy 算法压缩
9. 针对于操作系统文件的交互操作，LevelDB 提供给外部用户一个可以定制的虚拟的接口(Env)

这些特性初看起来可能很难理解，但是随着后续阅读的深入，可以很清楚地看到它们是如何一步一步反映到代码中的。当然，LevelDB 并不是一个通用的数据库，其同样具有一些使用场景的限制: