浅谈数据库存储结构

本文是公司内部的一次分享。

本文讨论的内容主要是数据库的存储结构，对很多同学来说内容比较基础。本文的目的旨在通过一个合适的角度理解各类存储结构形成的原因。

引子

存储结构

我们知道，存储引擎是数据库最重要的部分之一，其负责数据在磁盘和内存上的存储、检索和管理，并向上层提供细粒度的数据操作接口。

而存储引擎最重要的就是存储的结构。内存、缓存、读写流程的设计都是建立在存储结构的基础上的，由此存储结构和存储引擎的特性和性能方面关系十分密切。相对于浩如烟海的数据库和存储引擎，可用的存储结构却没几个。

B树作为一个非常适合磁盘的存储结构，自关系型数据库兴起后一直占据着存储领域的主流。但近些年随着分布式技术的兴起和固态硬盘以及多核CPU的发展，另一种存储结构LSM树越来越火热。

本文，我们从最基础的存储需求出发，来跟大家讨论一下这两类主流存储结构的共性和特性，试着去找出存储结构发展的趋势，并介绍一下它们各自为了迎合这种趋势又发展出了哪些变种与优化。

磁盘

一般我们数据库的数据，最终要持久化到磁盘。而存储到磁盘，是通过操作系统的文件系统来实现，即我们可以简单认为数据库的数据存储形态是文件。所以在存储结构的设计上，就需要遵从磁盘、文件及文件系统的特性。

我们在内存中，有多种高效的数据结构：数组、链表、二叉搜索树、红黑树、跳表等。但这些结构都不适合用于磁盘上的存储结构。原因：

• 磁盘的IO速度远低于内存IO，磁盘随机IO又远低于顺序IO。所以对磁盘的操作更倾向于一次性读取一片连续区域，哪怕读取后再进行内存操作。
• 存储结构要支持并发。并发往往是加锁控制，存储结构的存储单元越小，锁粒度越小，并发度越高。

常见的内存数据结构往往不能同时满足以上两点，即不能直接用于磁盘上的存储结构。

KV

数据库对用户暴露的视图有表格、文档等，但在存储时往往转化为KV存储。所以我们后文讨论存储结构，也以KV形式介绍。

最简单的存储需求

我们由一个最简单的存储需求出发，即直接使用shell操作文件来实现一个数据库。

#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

这个数据库实现了基于字符串的KV存储。只支持set/get，不支持delete。（当然可以考虑通过set空value实现delete操作）

1. set：在文件末尾追加一个 KV 对。
2. get：匹配所有 Key，返回最后（也即最新）一条 KV 对中的 Value。

$ db_set 'Tom' 'London' 
$ db_set 'Alice' 'New York'
$ db_set 'Liming' 'Beijing'
$ db_get 'Alice'
New York

以上操作形成的文件内容：

Tom,London
Alice,New York
Liming,Beijing

基于这个数据库其实可以实现简单的存储需求。

这个数据库有个优点：写很快（文件追加）；同时有很多问题：

1. 读很慢。要逐行遍历整个文件。
2. 修改操作也是文件追加写，文件会一直膨胀下去。

我们从下面这个问题，来引出后续内容。

基于文件的存储如何修改数据？

为了讨论这个问题，我们介绍两大流派：in-place update和out-of-place update。两者的代表分别是B树和LSM树。

in-place update——B族树

如果需要执行：

$ db_set 'Alice' 'Washington'

想直接在文件上做原地修改，为了保证数据库数据正确性，则需要做大量数据拷贝。修改操作的时间复杂度太高，无法接受。

暂时无法在飞书文档外展示此内容

其实到这里，原来的shell版本数据库已经无法完成以上这个操作了。我们依然用db_set命令只是为了方便介绍。下同。

为了解决以上问题，我们引出分页管理。

分页管理

将文件分成固定大小的页，假设Page大小为16KB。则文件的增长、修改均以页为粒度来操作。

同样执行以下命令

$ db_set 'Alice' 'Washington'

假设Page x容纳不了修改后的内容，则在文件末尾申请新的Page写入。

此时只需要修改2个页，32KB大小的数据，避免了整个文件的拷贝。

举一反三

分页管理的思想其实很常见，比如：

1. 操作系统的虚拟内存管理
2. JVM的G1、ZGC算法基于region的内存管理
3. HBase bucket cache 缓存池实现

虽然以上场景目的不尽相同，但方法上有共通之处。

到此我们解决了数据修改的问题，但查询依旧很慢。自然想到：构建索引，以空间换时间。

索引

索引数据通常也需要持久化，即也需要以文件形式存储到磁盘上。我们当然可以同样以页的形式存储索引数据。

可以先粗暴地将页分为：索引页，数据页。

我们介绍两种索引的主要组织形式：堆组织表、索引组织表。

堆组织表

• 数据文件：维持我们以上介绍的形式。分页管理，按页增长和修改。

• 索引：以有序多叉搜索树形式组织

  • 将索引内容排序，才能方便地做检索。比如在页内做二分查找。
  • 索引同样是以页存储，页大小有限，则存储的数据有限。单个索引页无法存储所有数据页的位置，自然想到以树的形式分层增长。

此时，已经演化出B树的结构。数据库只要优先加载根索引页，就可以按需加载到所有数据，实现数据的快速增删改。

索引组织表

• 将数据页作为索引树的叶子节点，与索引文件合并存储在一起。
• 数据页内部排序。

B树变种

B+树

• 叶子节点中，增加指向兄弟节点的指针，加速跨页的范围查询。

B*树

• 增加了非叶子节点到其兄弟节点的指针

• 提升空间利用率：

• B树/B+树：节点满时，一分为二。最低空间利用率1/2

• B*树：节点满时，先将部分数据搬迁到下一个兄弟节点，两个节点都满了，再由两个节点分裂成2个。最低空间利用率2/3

B-Link树

SMO操作

全称Structure Modification Operation，也就是结构修改操作。在B树结构中，向一个页中增加数据或删除数据，可能会造成页的分裂或合并，影响关联节点或其父节点。并且，这种影响可能还会向上传递，甚至有可能造成根节点的分裂或合并。

所以如果我们想要保证出现SMO操作时读写的安全的话，就需要对有可能受SMO操作影响的节点加锁。

B树/B+树的加锁操作是自上向下加锁，而B-Link树可以自下向上加锁，减少锁冲突。

• 在B*树基础上，每个节点都增加一个high key值，记录当前节点的最大key

分裂过程：

1. 先把老节点的数据拷贝到新节点
2. 然后建立同一层节点间的连接关系
3. 最后再建立从父节点指向新节点的连接关系

B-Link树可以先不锁父节点，如果查找过程中，根据子节点high key判断要查找的数据是否已经分裂到兄弟节点，再根据兄弟节点指针，仍能找到正确结果。

COW B树

对页的每次修改，都复制一个新页，所以父页中存储的指针也要修改，父页也复制一遍，级联复制到根节点。

BoltDB就是采用这样的极简设计。Go语言编写，源码非常简练，可用于学习。

这其实这已经有些out-of-place update的设计了。

小结

1. 我们由修改操作的实现，引出分页管理形式
2. 再由数据检索效率，引出以B树实现的两种主要组织形式
3. 然后简单对比下两种索引组织形式：

	堆组织表	索引组织表
写性能	相对强	相对弱	堆组织表的数据页顺序写入
读性能	相对弱	相对强	索引组织表读取过程少一次磁盘寻址
代表数据库	Oracle、PostgreSQL	MySQL InnoDB

这里性能强弱的对比，仅从理论上以数据文件组织的形式来讨论，不代表数据库的真实性能强弱。

索引的存储形式对存储引擎的性能影响更大，而两种索引都是以B树形式组织，所以并不认为性能上有本质差别。

1. 而后介绍B树的主要变种，主要在增大并发能力方向不断进化。

Out-of-place update——LSM树

让我们重新回到最初shell版本数据库，走另一条发展路线。

这条路上，基本的思路是：仍然顺序写入文件，要如何构建索引。

内存索引

我们仍然让所有数据顺序追加到文件上。为了加快查询，我们在内存中构建一个哈希索引：

1. Key是KV对的Key
2. Value是KV对在文件中的起始偏移量

虽然很简单，但这正是Bitcask的基本设计。它能够实现非常高的数据读写性能。

1. 写：文件追加写
2. 读：一次内存查询，一次磁盘seek

但也有些问题：

1. 要求key集合很小，可以全部放入内存哈希表中。
2. 文件一直追加写，单个文件持续膨胀。在文件到达一定尺寸后，就新建一个文件，将原文件变为只读。同时为了回收delete和重复key多次写入的造成的空间浪费，将只读文件进行压实（ compact ） ，将旧文件进行重写，以进行垃圾回收。

哈希索引不支持范围查询。如果有此需求，可以考虑将内存中的索引结构替换为跳表或红黑树。

LSMT（Log-structured merge-tree）

接下来，我们通过解决一个个问题，一步步牵出LSMT的全貌。

SSTables 和 MemTable

我们首先解决内存索引的第一个问题：索引数据完全放内存，key集合过大，内存放不下怎么办？则必须考虑让索引数据也存磁盘。

我们加一条限制，保证不可变的只读文件按key有序，我们称这种格式为：SSTable（Sorted String Table）。

此时：不需要在内存中保存所有数据的索引。仅需要记录下每个文件界限，以区间表示：[startKey, endKey]。查找某个Key时，去所有包含该Key的区间对应的文件中做二分查找即可。

但数据是乱序接收的，文件是有序存储的，那么就需要在内存中暂时积攒数据，排序后顺序写入磁盘，形成不可变文件——SSTable。内存中的结构称为MemTable，可以为红黑树、跳表等有序数据结构。

所有的写入操作（delete被视为特殊的put），都优先写入MemTable。在MemTable在写够一定大小之后，会切换一个新的MemTable继续接收新的写入，旧的MemTable落盘形成SSTable。

MemTable存储在内存中，但对需要数据持久化的数据库来说，内存毕竟是不可靠的。

WAL（Write-ahead LOG）

如果出现宕机，内存中MemTable的数据则会丢失。解决方法也很经典：WAL。

请求数据先顺序追加写入WAL，落盘后再写入MemTable。即使出现宕机，也可以通过回放WAL恢复数据。

Compaction

以上的存储结构基本实现了数据的高效写入，但数据读取还有些问题：随着数据的持续写入，SSTable会越来越多，导致查询越来越慢。

解决方法在前文也提到过：压实（Compaction）。即按需对SSTable做合并，清理掉已经删除和重复key写入的数据。

Compaction执行过程，即有序文件的归并外排，顺序读，顺序写。

LSM树优化

LSM树也有些弊端，最明显的便是读写放大问题：

• 写入的数据会随着多次compaction执行，被重复读写多次
• 读操作需要在多个SSTables中查找，对结果做merge

Compaction 优化

最常见的便是优化compaction执行策略，避免无意义的文件读写。

Leveling和Tiering两种策略，都是将SSTable按文件大小分层：

Leveling

• 除level 0外，同level的SSTable范围没有交集
• 除level 0外，查询时每层最多只查1个SSTable
• compaction时，将跨层且有交集的SSTable做合并

Tiering

• 将同层SSTable合并进入下一层

LevelDB、RocksDB采用的是Leveling策略；Cassadra采用的是Tiering策略；HBase没有做严格的分层，但也更接近Tiering策略。

Compaction Offload

• 将后台Compaction行为从数据节点中剥离出来，避免compaction与正常读写请求竞争 IO 和 CPU等资源。

键值分离：WiscKey

WiscKey 的核心思想是将数据中的 Key 和 Value 分离，只在 LSM树 中有序存储 Key，而将 Value 存放在单独的 vLog 中。显著降低了写放大。

1. 当 LSM-Tree 进行 compaction 时，只会对 Key 进行排序和重写
2. vLog取代了LSM树的WAL，减少了value的一次写入

WiscKey 的设计很大一部分还建立在 SSD 的普及上，相比 HDD，SSD 有一些变化：

1. SSD 的随机 IO 和顺序 IO 的性能差距并不像 HDD 那么大，所以LSM树为了避免随机 IO 而采用了大量的顺序 IO，反而可能会造成了带宽浪费
2. SSD 拥有内部并行性，但LSM树并没有利用到该特性
3. SSD 会因为大量的重复写入而产生硬件损耗，LSM树的高写入放大率会降低设备的寿命

小结

我们从另一个角度，即数据异地更新，逐步牵出LSM树的基本实现。

LSM树自1996年提出后，随着多核CPU和固态硬盘的发展，逐渐成为越来越多数据库存储引擎的实现方案。但银弹并不存在，LSM树也有其弊端：写放大问题。

我们围绕读写放大问题，又介绍了compaction的几类优化，以及创新性的键值分离的实践。

总结

• 我们介绍了数据库中存储结构的重要性，以及存储结构设计的考虑因素
• 从一个最简单的文件数据库出发，分两条实现路线介绍了B族树和LSM树的设计要点，及其变种和优化。

参考

• 《数据密集型应用》
• B+树、B-Link树、LSM树，解读一下常用的存储结构
• WiscKey: Separating Keys from Values in SSD-Conscious Storage
• Compaction management in distributed key-value datastores