设计数据密集型应用（3）：Storage and Retrieval

第三章主要介绍可持久化的数据索引——主流的可持久化数据索引有下面几种：

1. Hash Index。
2. LSM-Tree。
3. B-Tree。
4. B+Tree。书中没有提到 B+Tree，可能是因为它和 B-Tree 比较像。考虑到 B+Tree 作为世界上最流行的关系数据库 MySQL 的官方存储引擎 InnoDB 的索引结构，本文还是决定拿出来学习一下。

Hash Index

Hash Index 是一种相对简单的索引结构。几乎每一种程序设计语言都有提供内存数据结构 hash map/table 的标准库，比如 C++ 中的 std::unordered_map、Python 中的 dictionary、Golang 中的 map。

简单的 Hash Index 可以在 hash map 的基础上实现将数据持久化：在内存中维护一个 hash map，保存 key -> <offset, size>，在磁盘上维护一个 append only 的文件用于持久化保存数据。

hash-index.png

简单粗糙的 C++ 代码实现如下：

#include <assert.h>
#include <fcntl.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

#include <string>
#include <unordered_map>
#include <vector>

class HashIndex {
 public:
  HashIndex(const std::string& data_fname)
      : data_fname_(data_fname), data_fd_(-1) {}

  int Init() {
    data_fd_ = open(data_fname_.c_str(), O_CREAT | O_RDWR | O_APPEND, 0666);
    if (data_fd_ < 0) {
      fprintf(stderr, "open %s error %s\n", data_fname_.c_str(),
              strerror(errno));
      return -1;
    }
    return 0;
  }

  int Get(const std::string& key, std::string* value) {
    auto itr = hash_.find(key);
    if (itr == hash_.end()) {
      return 1;
    }
    std::vector<char> buf(itr->second.size);
    ssize_t rsize =
        pread(data_fd_, &buf[0], itr->second.size, itr->second.offset);
    if (rsize != itr->second.size) {
      fprintf(stderr, "pread fd %d offset %lu size %u rsize %ld error %s\n",
              data_fd_, itr->second.offset, itr->second.size, rsize,
              strerror(errno));
      return -1;
    }
    std::string tmp_key;
    DecodeData(buf.data(), tmp_key, *value);
    if (tmp_key != key) {
      return -2;
    }
    return 0;
  }

  int Set(const std::string& key, const std::string& value) {
    std::string buf = EncodeData(key, value);
    off_t offset = lseek(data_fd_, 0, SEEK_CUR);
    if (offset < 0) {
      fprintf(stderr, "lseek fd %d error %s\n", data_fd_, strerror(errno));
      return -1;
    }
    auto wsize = write(data_fd_, buf.data(), buf.size());
    if (wsize != buf.size()) {
      fprintf(stderr, "write fd %d buf size %zu wsize %ld error %s\n", data_fd_,
              buf.size(), wsize, strerror(errno));
      return -1;
    }
    auto& value_info = hash_[key];
    value_info.offset = offset;
    value_info.size = buf.size();
    return 0;
  }

 private:
  uint32_t EncodeDataSize(uint32_t ksize, uint32_t vsize) {
    return sizeof(uint32_t) * 2 + ksize + vsize;
  }

  std::string EncodeData(const std::string& key, const std::string& value) {
    std::string result;
    uint32_t ksize = key.size();
    uint32_t vsize = value.size();
    result.reserve(EncodeDataSize(ksize, vsize));
    result.append((char*)&ksize, sizeof(ksize));
    result.append(key);
    result.append((char*)&vsize, sizeof(vsize));
    result.append(value);
    return result;
  }

  void DecodeData(const char* buf, std::string& key, std::string& value) {
    uint32_t ksize = *(const uint32_t*)buf;
    buf += sizeof(uint32_t);
    key = std::string(buf, ksize);
    buf += ksize;
    uint32_t vsize = *(const uint32_t*)buf;
    buf += sizeof(uint32_t);
    value = std::string(buf, vsize);
  }

  struct ValueInfo {
    uint64_t offset;
    uint32_t size;
  };

  std::unordered_map<std::string, ValueInfo> hash_;
  std::string data_fname_;
  int data_fd_;
};

int main() {
  HashIndex hash("/tmp/hash_index_test");
  int ret = hash.Init();
  assert(ret == 0);

  std::string v0;
  ret = hash.Get("hello", &v0);
  assert(ret == 1);
  
  ret = hash.Set("hello", "world");
  assert(ret == 0);

  ret = hash.Get("hello", &v0);
  assert(ret == 0);
  assert(v0 == "world");

  ret = hash.Set("hash", "HashTable");
  assert(ret == 0);
  ret = hash.Set("lsm", "LSMTree");
  assert(ret == 0);
  ret = hash.Set("b-", "B-Tree");
  assert(ret == 0);
  ret = hash.Set("b+", "B+Tree");
  assert(ret == 0);
  
  ret = hash.Get("hash", &v0);
  assert(ret == 0);
  assert(v0 == "HashTable");
  ret = hash.Get("lsm", &v0);
  assert(ret == 0);
  assert(v0 == "LSMTree");
  ret = hash.Get("b-", &v0);
  assert(ret == 0);
  assert(v0 == "B-Tree");
  ret = hash.Get("b+", &v0);
  assert(ret == 0);
  assert(v0 == "B+Tree");

  ret = hash.Set("hello", "WORLD");
  assert(ret == 0);
  ret = hash.Get("hello", &v0);
  assert(ret == 0);
  assert(v0 == "WORLD");

  return 0;
}

这个实现没有考虑太多方面的问题，比如：

1. 删除记录 。可以写入一条特殊的 delete flag 表示删除。
2. Crash recovery。进程重启后，如何重建索引？可以通过顺序扫描整个文件来重建索引。但是，当文件非常大的时候，重建索引的时间会很久。
3. 部分写失败。写文件不能保证是原子的，可能我们只写了一半就崩溃，重建索引的时候需要识别出来并剔除掉。
4. 并发控制。
5. 过期数据回收。等等。

想要知道这些问题如何解决，可以参考论文：Bitcask: A Log-Structured Hash Table for Fast Key/Value Data。

此外，Hash Index 还存在一些限制：

1. 整个 hash map 需要放在内存中，索引的大小受内存限制。
2. 不支持 range query（或者说 range query 的效率很低，一般需要通过全表扫描来实现）。

下面介绍的 LSM-Tree、B-Tree、B+Tree 的大小不会受到内存大小的限制，也能实现效率比较高的 range query，相对 Hash Indexe 会更加通用。

LSM-Tree

LSM-Tree 最早应该是出自论文 The Log-Structured Merge-Tree (LSM-Tree) ，其设计目标是提升写性能。

LSM-Tree 通过将随机写转化为顺序写来提高写性能（无论 HDD 还是 SSD，其顺序读写都要明显优于随机读写），而付出的代价就是读放大（每次查询可能需要 I/O）和写放大（compaction）。

lsm_arch.png

如上图所示：

1. LSM-Tree 的实现一般由内存中 MemTable + 外存（HDD/SSD）上的 WAL（Write Ahead Log） + 外存上的 SST（Sorted String Table）组成。Manifest 文件保存一些元数据。
2. 写操作很简单：1）写 WAL；2）写 MemTable。
3. 读操作就比较麻烦了：需要从新到旧读取 MemTable 或 SST，直到找到目标值。如果是范围查找，这个过程会更复杂一点，暂时不详细介绍了。
4. MemTable 在写满之后，会转换为 Immutable MemTable，然后被后台线程 dump 到外存上成为一个 SST 文件。这个过程也叫 Minor Compaction。
5. 随着外存上的数据/文件越来越多，为了尽可能保证数据的有序性和回收一些无效数据，外存上的 SST 之间会进行 compaction。这个过程叫 Major Compaction，也是 LSM-Tree 写放大的主要来源。

LSM-Tree 最近几年非常热门，比较知名的开源实现有：

• leveldb - https://github.com/google/leveldb
• rocksdb - https://github.com/facebook/rocksdb
• dgraph-io/badger - https://github.com/dgraph-io/badger
• cockroachdb/pebble - https://github.com/cockroachdb/pebble

B-Tree

1970 年的论文 Organization and maintenance of large ordered indices 提出了一种按页管理外存，便于随机访问的数据结构——B-Tree。

B-Tree 是众多平衡树中的一种，其设计思想是尽可能减少每次读写需要访问外存的次数。大部分 B-Tree 的操作（search、insert、delete）都只需要访问磁盘 O(h) 次。h 是 B-Tree 的高度。B-Tree 是一棵高扇出的扁平树。h 的值一般都比较小。

B-Tree 将数据划分成一个个固定大小的 page，一般是 4/8/16 KB，每次读写一个 page。一个 page 上保存的数据是有序的，方便快速查找。

B-Tree.png

一棵 m 阶的 B-Tree 的定义如下：

1. 根结点至少有 2 棵子树。
2. 每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1。
3. 所有内部结点（不包括根结点和叶子结点）的度数正好是关键字总数加 1，所以内部子树个数 k 满足：m/2 <= k <= m。
4. 所有的叶子结点都位于同一层。

1、2、3 主要是规定了 B-Tree 的结点分裂（split）与合并（merge）的基本规则。

4 保证了树结构是平衡的。

一个 page 中能存放的关键字 key 越多，B-Tree 的扇出（m 的值）就越大，这棵树就会越扁平。

二叉树扇出固定为 2，5 层最多可以存储 31 个 key-value。

B-Tree 假设 page 为 8KB，key 16 B, value 64 B，扇出可以接近 100。假设扇出为 100，5 层的 B-Tree 最多可以存储超过 100 亿个 key-value。

使用 B-Tree 作为索引数据结构的开源实现主要有：

• PostgreSQL - https://www.postgresql.org/
• MongoDB 的 wiredtiger 存储引擎 - https://github.com/wiredtiger/wiredtiger
• SQLite - https://www.sqlite.org/index.html

B+Tree

B+Tree.png

B+Tree 是 B-Tree 的变种。B+Tree 与 B-Tree 的最大区别在于：B-Tree 可以在非叶结点中存储数据，而 B+Tree 的所有数据都存储在叶子节点中，非叶子结点只存储 key 不存储 value。

这一点的区别让 B+Tree 的扇出大大高于 B-Tree。理论上，同等情况下 B+Tree 的高度要比 B-Tree 矮。

另外，B+Tree 通过在叶子结点增加相互连接的指针，可以很方便地执行范围查询和遍历，提高区间访问的性能。

一般情况下，在范围查询（range query）的场景下，B+Tree 的性能要优于 B-Tree；在点查询（point query）的场景下，B+Tree 每次查询都需要固定从根节点访问到叶子结点，而 B-Tree 可能在树中间就能查到结果。

使用 B+Tree 作为索引数据结构的数据库/存储引擎的有：

• MySQL 的 InnoDB 存储引擎 - https://www.mysql.com/
• BerkeleyDB - https://github.com/berkeleydb/libdb

LSM-Tree vs B-Tree/B+Tree

1. 写性能和写放大。 LSM-Tree 只有顺序写，B-Tree/B+Tree 会有随机写。正常情况下，LSM-Tree 的写性能优于 B-Tree/B+Tree。 LSM-Tree 的后台 compaction 会引入大量写放大。B-Tree/B+Tree 每次写入至少是一个 page，也存在写放大的问题，同时各种 B-Tree/B+Tree 的实现还会引入 double write 等问题，进一步加剧写放大。B-Tree/B+Tree 的写放大倍数和具体业务场景有关，在 Facebook 的场景下[7]，B+Tree（InnoDB）的写放大比 LSM-Tree（RocksDB）严重。
2. 读性能和读放大。 点查询。LSM-Tree 需要从上往下一层一层查询，一般需要多次 I/O。B-Tree/B+Tree，特别是 B+Tree，一般叶子结点以上部分是常驻内存中的，一次查询至多需要一次 I/O。 范围查询。LSM-Tree 的范围查询其实相当于在每一层都执行一次范围查询，性能其实是比较差的。一般情况下，范围查询的性能 B-Tree/B+Tree 要优于 LSM-Tree。
3. 空间放大。 LSM-Tree 存在过期未清理的数据，会占有一些空间。B-Tree/B+Tree 每个 page 是固定大小的，每个 page 可能存在一些碎片空间，同样会浪费一些空间。没有具体的场景，很难说谁浪费的多。 但是，实践中 LSM-Tree（RocksDB） 的压缩效果明显优于 B-Tree/B+Tree（InnoDB）[7]。所以，空间占用这一块，LSM-Tree 要优于 B-Tree/B+Tree。
4. 稳定性。 Compaction 带来的负载抖动是 LSM-Tree 的一个令人头疼的问题——Compaction 太快，会和正常请求争抢资源；Compaction 太慢，会容易导致 write stall。 相比之下，B-Tree/B+Tree 的写入操作虽然可能带来分裂、合并的连锁反应，但是影响范围被控制得很有限，不容易造成负载抖动。理论上，B-Tree/B+Tree 的表现应该是要比 LSM-Tree 稳定的。

参考文档

1. Designing Data-Intensive Applications - Storage and Retrieval
2. Bitcask - https://en.wikipedia.org/wiki/Bitcask
3. LSM-Tree - https://en.wikipedia.org/wiki/Log-structured_merge-tree
4. B-Tree - https://en.wikipedia.org/wiki/B-tree
5. B+Tree - https://en.wikipedia.org/wiki/B+_tree
6. B-Tree Visualization - https://www.cs.usfca.edu/~galles/visualization/BTree.html
7. MyRocks Introduction