存储引擎简述(Todo)

Posted on | Edited on | In

本文将对存储引擎的常用实现方式做个大概的介绍，目的首要是尝试去“理清”各个数据库系统在选择底层数据结构时的各种考量和优劣势，同时，也是为了更好的对各种“层出不穷”的数据库和缓存系统作一个“由底至上”的了解。

Why存储引擎

在计算机科学领域中，数据的存储和查询是经久不衰的话题。而这里又有两种主要的类型:

  • 目标是作为缓存的系统，如常用的Redis等
  • 目标是作为数据库的系统，如常用的关系型数据库MySQL,非关系型MongoDB等等

不同的业务场景需要解决的最核心的问题自然不一样，内存型的可能是查询速度和可用性等等，而数据库
系统则相对统一一些：

  • 数据的可靠性
    既然是作为数据库系统，那么自然需要对存储到库里的系统做充分的持久性保证。无论说是在调用保存
    之后还是数据库系统本身崩掉，都应该足够可靠的保存数据
  • 查询/更新的性能
    除了存储，查询和更新自然是最核心、最重量级的功能。

毫无疑问的是，对于数据库来说，数据最终总会“持久化”到磁盘上(也就是所谓的非易失性存储器)。
常见的磁盘有机械硬盘, 固态硬盘
对于机械硬盘来说，是有机械臂在磁盘的碟片上选择来读取数据，而固态硬盘则要快的多。但是，他们都有
一个核心特点：随机的读和写比顺序的要慢不少。

那么，当我们需要在磁盘上高频率的存储大量数据，同时也可能高频率的查询数据时， 数据库的持久化机制
就显得特别重要：

  • 数据是随机写还是顺序写？
  • 随机写后怎么读取，顺序写了怎么读取？
  • 在存储过程中磁盘坏了怎么处理？
  • …

这一系列问题需要解决的都是一个点：数据在磁盘上的存储方式。同时，还需要平衡查询和更新中间某些数据时
的性能。当前，主要有如下的几种结构来组织存储在磁盘上的数据:

  • Hash
    文件被已不断增加的方式保存在磁盘上，同时，在内存里“维护”一个key-offset的映射关系，每当对数据进行更新的时候都同时更新这个offset。
  • B+树
    数据被有序的存储在磁盘上，逻辑上构成一颗B+树。毫无疑问，更新和写入都是随机IO
  • B树
    数据被有序的存储在磁盘上，逻辑上构成一颗B树。毫无疑问，更新和写入都是随机IO
  • LSM结构
    数据已append-only的方式在文件上进行只增加不减少的形式存储，然后后台异步的整理文件再保存为新的文件

下面分别作介绍：

Hash

Hash结构也就是通常所说的key-value的映射关系，在很多编程语言里也叫directory。它的特点很明显：
查找数据的平均时间复杂度为O(1)

而具体在一个数据库系统里（一般是指key-value类型）里，则主要用于构建查找数据的基本结构，主要特点如下：

  • 文件已append-only的形式追加都某个文件上
  • 内存里维护一个key-offset的映射关系

由于在内存里保存了所有的key的文件偏移指针，所以查询数据只需要一次随机IO即可（如果已经在文件系统缓存里，则不需要磁盘IO），同时，写入也是顺序性的，所以提供了很好的性能。但同时，有如下几个缺陷：

  • 内存必须能保存下所有的key
    如果所有key的集合超过内存大小，则不得不把这个hash结构保存到磁盘上，但是对于一个磁盘上的hash结构很难保证有良好的性能-会要求很多的随机IO。
  • 范围查找很难实现（平衡时间和空间复杂度的情况下）

存储引擎Bitcask就是使用的该模型，它非常适合于key更新非常频繁的场景，比如说某些视频的访问量统计-用视频的url作为key,某个数字作为value，每当有用户观看视频的时候都会更新该数据 - 也就是说，有很多的更新需求，但是总的key的集合并不大。

ps: 上面只说道了对文件进行新增操作，但是对于一直更新一个文件最终会产生一个超大的文件并且文件前面的内容可能说并无作用，所以可以引入一个merge/compaction过程：
文件写入到很多固定大小的小文件中，后台异步的把这些小文件的归档为一个文件（即按照先后顺序读取文件，在内存里对文件的内容进行分析，比如说对于同一个key的多次更改则取最后一次，然后再生成新的文件，期间对文件的查找先使用旧文件，直到compaction完成后读取新生成的文件）。
当然，实际实现上可能还需要考虑以下问题：

  • 文件格式
    使用csv还是自定义的二进制格式
  • 删除操作如何记录
    可以对删除操作定义一个特殊的标记，就和新增以及更新一样的记录。
  • 崩溃恢复
    内存里的hash映射将丢失，需要重新读取所有的数据文件来构建这个hash
  • 文件安全性
    比如持久化一半系统崩溃
  • 并发控制

LSM结构

在上面的hash结构里，我们看到对于数据的组织方式是：key-value对被顺序的写入到文件中，对于相同的key，文件后面的value覆盖前面的value。在整个文件中，完全不关心key-value对的顺序。

B树

B树是一种平衡多路查找树，它有如下几个特点：

  • 每个节点可以有多个子树
  • 节点数据也是左小右大,满足查找树的特点
  • B 树每个中间节点有 k-1 个关键字（可以理解为数据）和 k 个子树（ **k 介于阶数 M 和 M/2 之间，M/2 向上取整）
  • B 树的所有叶子节点都在同一层，并且叶子节点只有关键字，指向孩子的指针为 null

对于存储引擎来讲，B树的一个核心点就是它的所有中间节点都有数据。它的查找逻辑：

  1. 从根节点开始，如果查找的数据比跟小，就去左字树查找，否则去右子树
  2. 和字树的多个关键字进行比较，知道找到它所处的范围，然后去该范围对应的字树查找
  3. 循环直到找到叶子节点为止

上面是算法层面的逻辑，当数据被以B树的结构存储在磁盘上时，又具体是如何查找的呢？

由于

B+树