数据库存储引擎

Bitcast

  • 日志型
  • 基于 hash 表
  1. 只支持追加 Bitcast 仅支持追加操作（Append-only），即所有的写操作只追加而不修改老的数据。
  2. 多版本文件
    • 每个文件有一定的大小限制，当文件增加到相应的大小时，就会产生一个新的文件，老的文件只读不写。
    • 在任意时刻，只有一个文件是可写的，用于数据追加，称为活跃数据文件（active data file）。而其他已经达到大小限制的文件，称为老数据文件（older data file）。
  3. 日志文件
    • Bitcast 数据文件中的数据是一条一条的 "操作", 所有的操作都会序列化到日志文件里 (包括删除).
    • 写入时首先将 Key-Value 记录追加到活跃数据文件的末尾，接着更新内存哈希表，因此，每个写操作总共需要进行一次顺序的磁盘写入和一次内存操作。
  4. 日志压缩
    • Bitcask 需要定期执行合并（Compaction）操作以实现垃圾回收。
    • 合并操作，即将所有老数据文件中的数据扫描一遍并生成新的数据文件，同一个 key 的多个操作以只保留最新一个的原则进行删除，每次合并后，新生成的数据文件就不再有冗余数据了。
  5. hash 索引
    • 哈希索引存储在内存中，如果不做额外的工作，服务器断电重启重建哈希表需要扫描一遍数据文件
    • 如果数据文件很大，这是一个非常耗时的过程。可以通过索引文件（hint file）来提高重建哈希表的速度。

LSM

核心思想

放弃部分读能力，换取写入的最大化能力

先可以将更新的数据驻留在内存中，等到积累足够多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘中。

LSM-tree 的主要思想是划分不同等级的树。

  • 以两级树为例，可以想象一份索引数据由两棵树组成，一棵树存在于内存，一棵树存在于磁盘。
  • 内存中的树可以不一定是 B 树，可以是其他的树，例如 AVL 树。因为数据大小是不同的，没必要牺牲 CPU 来达到最小的树高度，而存在于磁盘的树则是一棵 B 树。

写入过程

  • 在 LSM 树中，写入数据时首先会插入到内存的树中。

  • 当内存中的树的数据超过一定阈值时，会进行合并操作。合并操作会顺序遍历内存中的树的叶子节点，并与磁盘中的树的叶子节点进行合并

    • 当被合并的数据量达到磁盘的存储页的大小时，会将数据持久化到磁盘，同时更新父亲节点对叶子节点的指针。

  • LSM 树可以划分成很多层级的树

    • 第 0 层存储在内存，第 1 到 k 层存储在磁盘，每层的数据都是有序的。
    • 数据首先会插入到第 0 层，然后后台逐层合并。
    • 每一层的数据超过一定阈值时，往下一层合并。
    • 读取叶由于不知道数据在哪一层上，可能需要遍历所有的层。

Level DB

LevelDB 存储引擎主要包括：

  • 内存中的 MemTable 和不可变 MemTable（也称为 Frozen MemTable）
  • 磁盘上的几种主要文件：
    • 当前（Current）文件
    • 清单（Manifest）文件
    • 操作日志（Commit Log，也称为提交日志）文件
    • SSTable 文件

写入过程：

  • 当应用写入一条记录时，LevelDB 会首先将修改操作写入到操作日志文件，成功后再将修改操作应用到 MemTable，这样就完成了写入操作。
  • 当 MemTable 占用的内存达到一个上限值后，需要将内存的数据转储到外存文件中。
  • LevelDB 会将原先的 MemTable 冻结成为不可变 MemTable，并生成一个新 MemTable。新到来的数据被记入新的操作日志文件和新生成的 MemTable 中。
  • 不可变 MemTable 的内容是不可更改的，只能读取不能写入或者删除。LevelDB 后台线程会将不可变 MemTable 的数据排序后转储到磁盘，形成一个新的 SSTable 文件，这个操作称为 Compaction。
  • SSTable 文件是内存中的数据不断进行 Compaction 操作后形成的，且 SSTable 的所有文件是一种层级结构，第 0 层为 Level 0，第 1 层为 Level 1，以此类推。

SSTable: SSTable 是一个键是有序的，存储字符串形式键值对的文件。它是一个内部包含了任意长度、排好序的键值对集合的文件。SSTable 文件由两部分数据组成：索引和键值对数据。所有的 key 和 value 都是紧凑地存放在一起的，如果要读取某个键对应的值，需要通过索引中的 key:offset 来定位。SSTable 在序列化成文件之后，是不可变的，因为此时的 SSTable，就类似于一个数组一样，如果插入或者删除，需要移动一大片数据，开销比较大。

加快访问效率：

  • LSM 树写入效率很高，但读取可能需要访问较多的磁盘文件，效率较低。为了加快读取效率，工程实现上一般使用 Bloom Filter 来加快读取效率。它使用很小的存储空间换来较大的读取效率提升。

Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。

  • Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter 不适合那些“零错误”的应用场合。
  • 而在能容忍低错误率的应用场合下，Bloom Filter 通过极少的错误换取了存储空间的极大节省。

初始状态时，Bloom Filter 是一个包含 m 位的位数组，每一位都置为 0。为了表达 S={x1, x2,…,xn}这样一个 n 个元素的集合，Bloom Filter 使用 k 个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素 x，第 i 个哈希函数映射的位置 hi(x) 就会被置为 1（1≤i≤k）。注意，如果一个位置多次被置为 1，那么只有第一次会起作用，后面几次将没有任何效果。在判断 y 是否属于这个集合时，我们对 y 应用 k 次哈希函数，如果所有 hi(y) 的位置都是 1（1≤i≤k），那么我们就认为 y 是集合中的元素，否则就认为 y 不是集合中的元素。