专栏首页linjinhe的专栏设计数据密集型应用(3):Storage and Retrieval

设计数据密集型应用(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 最近几年非常热门,比较知名的开源实现有:

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 作为索引数据结构的开源实现主要有:

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 作为索引数据结构的数据库/存储引擎的有:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • WiscKey:LSM-Tree 写放大优化WiscKey 简介WiscKey 带来的好处WiscKey 面临的问题和挑战参考文档

    WiscKey 的提出,主要是为了优化 LSM-Tree 的写放大问题。此前已经有不少论文讨论过这个问题,如 LSM-trie 和 PebblesDB,但是大部...

    linjinhe
  • 现代 C++:一文读懂智能指针

    简单说,当我们独占资源的所有权的时候,可以使用 std::unique_ptr 对资源进行管理——离开 unique_ptr 对象的作用域时,会自动释放资源。这...

    linjinhe
  • 干货 | 携程国际BU的SEO重构实践

    熊聘,携程国际事业部公共研发团队Leader,目前主要负责国际化相关的基础组件和市场相关项目的研发。开源社区爱好者,喜欢阅读优秀的开源项目源码,对新技术有着深厚...

    携程技术
  • 【2019年8月版本】OCP 071认证考试最新版本的考试原题-第9题

    Which three statements are true about views in an Orade batabase?

    用户5892232
  • 你真的会正确使用断言吗?

    断言是作为一种调试工具被发明出来的,用来检查那些“代码写对了就肯定成立”的条件。例如我们要断言一个变量a必须要大于2,就可以这样写:

    simpleapples
  • 向李玉宝学习

      这几天,大家大多数都被“啥是佩奇”的广告刷屏了吧,后台一大堆人留言,问我怎么看待这个广告。。今天就姑且说说吧

    Dawnzhang
  • Python把汉字转换成拼音

    Python扩展库pypinyin支持汉字到拼音的转换,并且可以和分词扩展库配合使用。 >>> from pypinyin import lazy_pinyin...

    Python小屋屋主
  • 入坑系列之HAProxy负载均衡

    在大型系统设计中用代理在负载均衡是最常见的一种方式,而相对靠谱的解决方案中Nginx、HAProxy、LVS、F5在各大场中用得比较普遍,各有各的优势和使用场...

    欢醉
  • PHP代码审计笔记--任意文件上传

    基于安全方面的考虑,应增加用户上传文件的限制,比如检查文件类型、限制文件大小,限定文件路径,文件名重命名、白名单限制文件上传类型等。

    Bypass

扫码关注云+社区

领取腾讯云代金券