海量存储系列之八、九、十

编者注：本文为历史博文归档，主要探讨存储引擎的核心数据结构原理。涉及 JDK、框架与工具链版本请以当前官方文档为准。文中部分引用外链图片可能失效，阅读时请注意时效性。

为什么磁盘存储常用 B+ 树？

首先来回答一个问题：为什么在磁盘中要使用 B+ 树 来进行文件存储呢？

核心原因在于 树的高度。磁盘本身是一个「顺序读写快，随机读写慢」的系统，如果想高效地从磁盘中找到数据，势必需要满足一个最重要的条件：减少寻道次数。

我们以 平衡二叉树 为例进行对比，就会发现问题所在了。

先上个图：

这是个平衡树，可以看到基本上一个元素下只有两个子叶节点。

抽象地来看，树想要达成有效查找，势必需要维持如下一种结构：

树的子叶节点中，左子树一定小于等于当前节点，而当前节点的右子树则一定大于当前节点。只有这样，才能够维持全局有序，才能够进行查询。

这也就决定了只有取得某一个子叶节点后，才能够根据这个节点知道它的子树的具体值情况。这点非常之重要，因为二叉平衡树只有两个子叶节点，所以如果想找到某个数据，它必须重复更多次「拿到一个节点的两个子节点，判断大小，再从其中一个子节点取出它的两个子节点，判断大小」这一过程。

这个过程重复的次数，就是树的高度。那么既然每个子树只有两个节点，那么 N 个数据的树的高度也就很容易可以算出了。

平衡二叉树这种结构的好处是，没有空间浪费，不会存在空余的空间；但坏处是需要取出多个节点，且无法预测下一个节点的位置。这种取出的操作，在内存内进行的时候，速度很快，但如果到磁盘，那么就意味着大量随机寻道，磁盘性能基本就被拖累了。

而 B 树，因为其构建过程中引入了有序数组，从而有效地降低了树的高度。一次取出一个连续的数组，这个操作在磁盘上比取出与数组相同数量的离散数据，要「便宜」得多。因此磁盘上基本都是 B 树结构。

不过，B 树结构也不是完美的。与二叉树相比，它会耗费更多的空间。在最恶劣的情况下，要有几乎是元数据两倍的格子才能装得下整个数据集（当树的所有节点都进行了分裂后）。

以上，我们就对二叉树和 B 树进行了简要的分析。当然里面还有非常多的知识我这里没有提到，我希望这个系列能够成为让大家入门的材料，如果感兴趣可以知道从哪里着手即可。如果您通过我的文章发现对这些原来枯燥的数据结构有了兴趣，那么我的目标就达到了 : )

B 树在磁盘结构中的问题

在这章中，我们还将对 B 树的问题进行一下剖析，然后给出几个解决的方向。

其实 TokuDB 的网站上有个非常不错的对 B 树问题的说明，我在这里引用一下，将他们的图作为说明 B 树问题的图谱吧，因为真的非常清晰。

文档链接：http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf

B 树在插入的时候，如果是最后一个 node，那么速度非常快，因为是顺序写。

但如果有更新、插入、删除等综合写入，最后因为需要循环利用磁盘块，所以会出现较多的随机 I/O，大量时间消耗在磁盘寻道时间上。

如果是一个运行时间很长的 B 树，那么几乎所有的请求，都是随机 I/O。因为磁盘块本身已经不再连续，很难保证可以顺序读取。

以上就是 B 树在磁盘结构中最大的问题了。

解决方案与 LSM Tree 的兴起

那么如何能够解决这个问题呢？目前主流的思路有以下几种：

  1. 放弃部分读性能，使用更加面向顺序写的树的结构来提升写性能。
    这个类别里面，从数据结构来说，就我所知并比较流行的是两类：

    • 一类是 COLA（Cache-Oblivious Lookahead Array），代表应用自然是 TokuDB。
    • 一类是 LSM Tree（Log-Structured Merge Tree）或 SSTable，代表的数据集是 Cassandra、HBase、BDB Java Edition、LevelDB 等。
  2. 使用 SSD，让寻道成为往事。

我们在这个系列里，主要还是讲 LSM Tree 吧，因为这个概念几乎要「一桶浆糊」了。几乎所有的 NoSQL 都在使用，然后利用这个宣称自己比 MySQL 的 InnoDB 快多少多少倍。我对此表示比较无语，因为 NoSQL 本身似乎应该是以省去解析和事务锁的方式来提升效能，怎么最后却改了底层数据结构，然后宣称这是 NoSQL 比 MySQL 快的原因呢？

毕竟 MySQL 又不是不能挂接 LSM Tree 的引擎。

好吧，牢骚我不多说，毕竟还是要感谢 NoSQL 运动，让数据库团队都重新审视了一下数据库这个产品本身。

LSM Tree 的核心思想

那么下面，我们就来介绍一下 LSM Tree 的核心思想吧。

首先来分析一下为什么 B+ 树会慢。

从原理来说，B+ 树在查询过程中应该是不会慢的，但如果数据插入比较无序的时候，比如先插入 5，然后 10000，然后 3，然后 800 这样跨度很大的数据的时候，就需要先「找到这个数据应该被插入的位置」，然后插入数据。这个查找到位置的过程，如果非常离散，那么就意味着每次查找的时候，它的子叶节点都不在内存中，这时候就必须使用磁盘寻道时间来进行查找了。更新基本与插入是相同的。

那么，LSM Tree 采取了什么样的方式来优化这个问题呢？

简单来说，就是 放弃磁盘读性能来换取写的顺序性。

乍一看，似乎会认为读应该是大部分系统最应该保证的特性，所以用读换写似乎不是个好买卖。但别急，听我分析之：

  1. 内存的速度远超磁盘，1000 倍以上。而读取的性能提升，主要还是依靠内存命中率而非磁盘读的次数。
  2. 写入不占用磁盘的 I/O，读取就能获取更长时间的磁盘 I/O 使用权，从而也可以提升读取效率。

因此，虽然 SSTable 降低了读的性能，但如果数据的读取命中率有保障的前提下，因为读取能够获得更多的磁盘 I/O 机会，因此读取性能基本没有降低，甚至还会有提升。而写入的性能则会获得较大幅度的提升，基本上是 5~10 倍左右。

下面来看一下细节。

其实从本质来说，K-V 存储要解决的问题就是这么一个：尽可能快地写入，以及尽可能快地读取。

让我从写入最快的极端开始说起，阐述一下 K-V 存储的核心组件之一——「树」吧。

我们假设要写入一个 1000 个节点的 key 是随机数的数据。

对磁盘来说，最快的写入方式一定是顺序地将每一次写入都直接写入到磁盘中即可。但这样带来的问题是，我没办法查询，因为每次查询一个值都需要遍历整个数据才能找到，这个读性能就太悲剧了。

那么如果我想获取磁盘读性能最高，应该怎么做呢？把数据全部排序就行了，B 树就是这样的结构。

那么，B 树的写太烂了，我需要提升写，可以放弃部分磁盘读性能，怎么办呢？

简单，那就弄很多个小的有序结构。比如每 m 个数据，在内存里排序一次；下面 100 个数据，再排序一次……这样依次做下去，我就可以获得 N/m 个有序的小的有序结构。

在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。

很容易可以看出，这样的模式，读取的时间复杂度是 (N/m)*log2N。读取效率是会下降的。

这就是最本来意义上的 LSM Tree 的思路。

LSM Tree 的优化方式

那么这样做，性能还是比较慢的，于是需要再做些事情来提升，怎么做才好呢？于是引入了以下的几个东西来改进它：

  1. Bloom Filter
    就是个带随机概率的 Bitmap，可以快速地告诉你，某一个小的有序结构里有没有指定的那个数据。于是我就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
  2. 小树合并为大树
    也就是大家经常看到的 Compact 的过程。因为小树它性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用 log2N 的方式找到，不需要再进行 (N/m)*log2N 的查询了。

这就是 LSM Tree 的核心思路和优化方式。

局限性与展望

不过，LSM Tree 也有个隐含的条件，就是它实现数据库的 insert 语义时性能不会很高。原因是，insert 的含义是：事务中，先查找该插入的数据，如果存在，则抛出异常，如果不存在则写入。这个「查找」的过程，会拖慢整个写入。

这样，我们就又介绍了一种 K-V 写入的模型啦。在下一次，我们将再去看看另外一种使用了类似思路，但方法完全不同的 B 树优化方式——COLA 树系。敬请期待 ~

说明：本文主要阐述存储引擎设计的经典理论与历史演进，文中提到的性能倍数（如 5~10 倍）为特定场景下的估算值，实际效果取决于硬件环境与数据分布。关于 TokuDB、LevelDB 等具体产品的最新特性，请参考其官方文档。