数据存储与检索

从最基本的层面看，数据库只需要做两件事：

• 向它插入数据时，它就保存数据
• 查询数据时，它就返回数据

本章主要从数据库的角度来探讨：

1. 如何存储输入的数据
2. 收到查询请求时，如何重新找到数据

作为一名普通的开发人员，我们不太可能从头实现一个自己的存储引擎，但是我们在做技术选型的时候，需要从众多的存储引擎中选一个最适合自己应用的，就需要对各种存储引擎底层机制有一个大概的了解。

我们将研究两个存储引擎家族：

• 日志结构的存储引擎
• 面向页的存储引擎（如 B-Tree）

数据库的核心：数据结构

一个简单的例子：

1
2
3
4
5
6
7
8
9

#!/bin/bash

de_set() {
    echo "$1,$2" >>database
}

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

我们实现了一个简单的 kv 存储的数据库，key 可以是任意值，value可以是一个 json，我们每次查找，都会获取key的最新值返回。

我们来看一下这样做的特点

1. 每次对数据进行追加，且旧值不会被覆盖，最后一次的值就是最新的值
2. 这种追加到文件末尾的方式通常足够高效，许多数据库内部也是使用日志（log），日志是一个仅支持追加式更新的数据文件，但是一个真正的数据库需要考虑的更多（并发控制、回收磁盘、控制日志文件大小）
3. 虽然写入的时候高效，但是如果日志文件产生了大量记录， do_get 性能会非常差，他只能进行 O(n) 扫描全表

那如何快速查找我们想要找的 key 的值呢，那就需要一个数据结构来索引它，最基本的想法就是存一些额外的数据，作为这些元数据的路标，帮助我们定位，但是引入额外的数据结构来维护索引，也是有开销的，每次写入数据不仅仅是简单的追加数据，还需要更新索引，因此任何类型的索引都会降低写入速度。

这里需要提一下存储引擎最终要的权衡设计：

1. 适量的索引可以提高查询速度
2. 每个索引都会减慢写入速度
3. 所以这里需要做一个权衡，通常来说，就是我们加索引不能随心所欲的乱加

哈希索引：

先从简单的哈希索引开始介绍，通常为 kv ，是其他更复杂的索引的基础构造模块。

KV大家已经很了解了，就理解成一个 map 就行。

假设我们现在需要设计一个kv的存储引擎，数据采用追加文件的做法，如果我们要给数据加索引，一个最直观的做法是：

map中的 key 值为键名，value 为字段在文件的偏移量。查找数据时，直接找到偏移量，就可以直接读取出文件。

这是一个可行的做法，且是 Bitcask 存储引擎的默认做法。用 hash_map 在内存中存 key，占用内存小，且 value 可以存一个比较大的值。但是缺点是，需要把所有的key存在内存中，要保证内存大小。

我们考虑一下优化方案，如果只追加到一个文件，如何避免磁盘空间被用尽呢？

一个好的方案是：

• 将日志分为一定大小的段
• 文件到达一定大小时就关闭它，后面的数据写入新的日志文件中
• 这些日志的段可以被压缩，在日志中丢弃重复的键
• 压缩会使段减少，如果压缩后非常小，可以将段之间进行合并

经过这样操作后，每个段都有自己的哈希表，将键映射到文件的偏移量。查找的时候，先检查新的段的 hash_map，不存在的话， 再找第二新的段，以此类推。

我们刚刚口糊了一个简单的kv存储引擎的实现方案，但是有些地方并不全面，我们还需要考虑：

• 文件格式：日志格式采用二进制格式会更省空间
• 删除记录：如果要删除键和关联的值，可以在数据文件中给这个数据打一个标记（称为墓碑）。在合并的时候，如果发现这段数据有墓碑标记，就丢弃这些数据
• 崩溃恢复：我们的数据都存在内存中，如果数据库突然崩溃，我们重启数据库的时候，只能重新读取日志文件重建一个哈希索引。但是如果日志文件特别大，那么就得扫描很长时间，则这个数据库很长时间才能启动起来。所以我们考虑给内存中存储的数据加快照，重启后直接读就行，快速重建
• 部分写入的记录：数据库可能随时崩溃，包括将记录追加到日志的过程中。我们需要给数据增加校验值，如果数据不对，就丢弃。
• 并发控制：文件的写入是有严格的先后顺序的，通常的实现是只有一个写线程，数据文件段是追加的，并且不可变，他们可以被其他多个线程读取。

追加写的方式是不是很浪费空间，为什么不采用不断更新原文件来实现呢？

1. 在旋转式磁盘上，顺序写比随机写入速度快得多
2. 如果段文件是追加的或不可改变的，那并发和数据恢复则要简单的多。不必担心重写值会发生崩溃的情况，留下一个新值和部分旧值混在一起的文件。

哈希表索引也有局限性：

• 哈希表需要存储在内存中，内存的大小有限。如果放入磁盘中维护哈希表是一件很困难的事.
• 区间查询效率不高，不能查某个区间范围所有键，只能逐个查找的方式查询键。

SSTables 和 LSM-Tree

我们改变上述文件格式：要求哈希表的 key-value 需要按照键的顺序排序。

这种格式被称为排序字符串表，也叫 SSTable，要求每个键在每个合并的段文件中只能出现一次（压缩过程中已经确保了）。SSTable有以下优点：

• 合并段更加简单高效，即使文件大于可用内存。方法类似于合并排序，并发读多个文件，比较每个文件的第一个键，拷贝到输出文件。这样就可以完成排序（相同的键出现在多个输入段时，保留新新值，删除旧值）
• 在文件中查找特定键时，不需要在内存中保存所有键索引，保存一些稀疏的范围索引即可。（假设我们要查 handiwork，我们不知道他的偏移量，但是我们知道 handbag 和 handsome 的偏移量，可以确定要查的字段一定位于两者之间，那我们就可以在一小段内顺序查找了）

如果所有的键和值都能保持固定的大小，我们可以考虑采用二分查找。

构建和维护 SSTables

数据的写入是随机的，我们首先要保证如何让数据按键排序。在磁盘上维护排序结构是可行的，不过，将其保存在内存中更加容易，那么现在的问题就转化成了一个数据结构问题，而内存排序有很多广为人知的数据结构，各种平衡树，比如：

• 红黑树（在 C++ STL 中 std::map 就是默认key有序，底层是用红黑树来实现）
• AVL树

他们插入、删除、更新数据时间复杂度都是 log 级别。

那这时我们的存储引擎基本流程如下：

1. 在内存中维护一棵平衡树
2. 当这棵树的大小超过某个阈值，将其作为 SSTable 文件落盘，继续维护一棵新的树
3. 后台进程周期性的执行压缩合并过程，合并多个段文件。

上述还存在一个问题，如果数据库崩溃（即写在了内存中但是还未落盘），最近的写入就会丢失，为了避免该问题，我们可以在磁盘上保留惨淡，这个日志不需要对键进行排序，唯一的作用就是在崩溃后恢复内存表，每当内存表写入 SSTable 后，则相应的日志可以丢弃。

从 SSTables 到 LSM-Tree

深入理解什么是LSM-Tree

以上算法的本质是 LevelDB 和 RocksDB 使用的，主要用于嵌入到其他应用程序的 KV 存储引擎库。

字节内部自研的 Abase 实质上就是基于 RocksDB 实现的

收到 Google Bigtable原版论文 Bigtable中文翻译 Bigtable中文 这篇论文启发，引入了 SSTable 这个术语。这个索引结构以日志合并树（Log-Structured Merge-Tree）来命名，基于合并和压缩排序文件原理的存储引擎通常都被称为 LSM 存储引擎。

Lucene 是Elasticsearch和 Solr等全文搜索系统所使用的索引引擎，它采用了类似的方法来保存其词典。全文索引比 kv索引复杂的多，但是基于一些类似的想法：给定搜索查询的某个单词，找到提及该单词的所有文档。主要使用 KV 实现，其中键是单词，值是所有包含该单词的文档的ID的列表。在 Lucene 中，从词条到 posting list 的映射关系保存在类 SSTable 的排序文件中，这些文件可以后台合并。

性能优化：

• 查找每个不存在的键时，LSM-tree 性能可能会很慢
  • 在确定键不存在之前，必须先检查内存表，然后一直回溯到最旧的段文件。
  • 为了优化这种情况，我们一般使用 布隆过滤器 （布隆过滤器可以用于检索一个元素是否在一个集合中，速度较快）
• 不同策略会影响甚至决定 SSTables 压缩和合并具体顺序的实际，最常见的方式是大小分级和层级压缩.
  • LevelDB 和 RocksDB 使用分层压缩
  • HBase 使用大小分级

LSM-Tree 的基本思想（保存在后台合并的一系列 SSTable）足够简单有效。技术数据集远远大于内存，仍然能够正常工作。由于数据按顺序存储，因此可以有效进行区间查询，由于磁盘是顺序写入的，所以 LSM-Tree 可以支持非常搞的吞吐量

B-Tree

B树我们应该都很熟悉了，在这里我们主要关注一下和之前日志结构索引的不同和一些特性即可。

关于具体数据结构的学习，可以看:https://segmentfault.com/a/1190000020416577

虽然日志结构索引正在逐渐受到更多的认可，但是它还不是最常见的索引类型。

BTree应该是我们最常见的索引结构了。时至今日，它仍然是几乎所有关系型数据库的标准索引实现。许多非关系型数据库也经常使用。

和 SSTable 思路差不多，BTree 保留按键排序的 kv 对，这样可以实现高效的 kv 查询和区间查询，但是相似的地方仅此而已，Btree 本质上具有非常不同的设计理念。

• 日志结构索引将数据库分解为大小可变的段，通常为几兆字节或者更大，并且按顺序写入
• BTree 将数据库分解成固定大小的块或页，传统大小为 4KB ，页是内部读写的最小单元，这种设计更接近底层硬件，因为磁盘也是按照固定大小的块排列
• 每个页面都可以使用地址或者位置进行标识，这样可以让一个页面引用另一个页面，类似于指针，它指向磁盘的地址，而不是内存。用这些页面引用来构造一个树，就是 B 树。

上面的例子可以看出，我们要查找 251 ，我们沿着根节点往下找，每个节点存储的都是一个范围的页的磁盘地址，只有叶子节点才存储具体的值。

在 B 树中，一个节点有几个儿子节点，这个数量称为 分支因子，在实际中分支因子取决于存储页面 引用和范围边界所需的空间总量，通常为几百个

如果需要对 B 树进行更新，搜索包含这个键的叶子页，更改页的值，并将页写回磁盘，如果要添加新键，就需要找到其范围内包含新键的页，并将其添加到页。如果此页中没有足够的空间，就把这个页分裂成两个页，并且其父页也需要包含分裂之后的新的键范围。

这个算法确保了树的平衡，具有n个键的 B-tree 总是具有 O(logn) 的深度，大多数数据库可以适合 3-4 层的 btree，因此不需要遍历非常深的页面层次即可找到所需的页（分支因子为500的4kb页的四级树存储高达 256TB）

使B-Tree可靠

B树写操作是新数据覆盖旧数据，它假设覆盖不会改变页的磁盘的存储位置。这与 LSM 形成鲜明对比，LSM-Tree 仅追加更新文件，不会修改文件。

在具体的实体磁盘执行这个操作， 首先要移动磁头，然后旋转盘面，然后用新数据覆盖旧数据。SSD的话更加复杂。所以很可能会出问题，为了能使数据库快速恢复，我们支持一个数据结构，叫：预写日志 WAL 。这是一个仅能追加的文件，在数据库崩溃时，可以将数据库恢复到最近一致的状态。

多个线程访问B树时，需要注意并发控制，通常使用锁存器保护树的数据结构正常完成。这方面，日志结构化的方式比较简单，因为他们在后台执行合并操作，不会干扰前台。

优化B-Tree

B-tree已经存在了很长时间，这里列举一些优化措施：

1. 一些数据库，比如 LMDB，不使用覆盖页和维护 WAL 来进行崩溃恢复，而是使用写时复制方案。修改的页被写入不同的位置。这种方案对并发控制也很有帮助。
2. 保存键的缩略信息，而不是完整的键，这样可以节省页空间。特别是树中间的页，只需要提供足够的信息来描述键的起止范围，这样就可以让更多的键压入到页中，从而减少层数。

这个变种有时候称为 B+ 树，然而优化是如此常见，以至于不能和其他 B-tree 变种区分开来。

1. 一般来说，页可以存放在磁盘的任何位置，没有要求相邻的页需要存放在相邻磁盘位置。但是随机放比较低效，所以，许多B-Tree实现尝试将树进行布局，以便相邻叶子页可以按顺序保存在磁盘上。但是随着树增长，保持这个顺序会变得越来越困难。相比之下 LSM-Tree 则完全没有这个问题。
2. 添加额外指针到树中。例如，每个叶子页面会向左和向右引用其他兄弟页，这样可以顺序扫描键，不用跳回到父页面
3. B-tree 的变种如分行树，借鉴了一些日志结构的想法来减少磁盘寻道。对比 B-Tree 和 LSM-Tree

其他索引

到目前为止，我们说的都是 KV 索引，对应于关系模型中的主键索引，主键唯一标识关系表中的一行，或者文档数据库的一个文档，或者图数据库的一个点。数据库的其他记录通过其主键来引用该行/文档/顶点，该索引用于解析此类引用。

二级索引很常见，在关系数据库中，可以使用 CREATE INDEX 命令来创建二级索引，很容易通过 KV 索引来构建，它的键不是唯一的，即可能有很多行具有相同键。这样可以通过两种方式解决：

1. 使索引每个值成为匹配行标识的列表
2. 增加一些行标识使每个键变得唯一

在索引中存值

我们已经有了主键索引，那么在额外假的索引中就不用直接存储元数据，只存储一个引用就可以，存储行的具体位置被称为堆文件。这样存在多个二级索引时，可以避免复制数据，实际数据只保存在一个位置.

在 MySQL InnoDB 引擎中，表的主键始终是聚集索引，二级索引引用主键位置。

多列索引

现在讨论的仍然是将一个键映射到一个值，如果我们的需求是同时查询表的多个列，如文档中的多个字段。

最常见的多列索引称为 级联索引，通过将几个字段连接组成一个键，进行排序

全文搜索和模糊索引

目前，我们讨论的都是有确切数据。还有一些其他索引，如:

1. 全文搜索引擎通常支持对一个单词的所有同义词进行查询，忽略语法上的变体
2. 其他模糊搜索则沿着文档和机器学习方向发展。

在内存中保存所有数据

现在内存价格逐渐便宜，数据集不那么大，用内存可以更好的服务。

比如我们常用的 redis ，这部分就不说了.

事务处理与分析处理

主要了解 OLTP 与 PLAP

事务指一个逻辑单元的一组读写操作

ACID，是指数据库管理系统（DBMS）在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。

数据处理大致可以分成两大类：

联机事务处理OLTP（on-line transaction processing）、联机分析处理OLAP（On-Line Analytical Processing）。

OLTP是传统的关系型数据库的主要应用，主要是基本的、日常的事务处理，例如银行交易。

OLAP是数据仓库系统的主要应用，支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果。

OLTP 系统强调数据库内存效率，强调内存各种指标的命令率，强调绑定变量，强调并发操作；

OLAP 系统则强调数据分析，强调SQL执行市场，强调磁盘I/O，强调分区等。

OLTP与OLAP之间的比较：

在我们实际应用中：

常见的 OLTP 数据库例如 MySQL，常见的 OLAP 系统，比如 Hive，clickHouse

列式存储

在大多数 OLTP 数据库中，存储以行的方式来进行布局：来自表的一行的所有值彼此相邻存储。文档数据库也类似。

那相对的，列式存储的想法也很简单：不要将一行中的所有值存在一起，而是将每列中的所有值存在一起。

在列式存储中比较著名的，有 ClickHouse.

什么是ClickHouse?

https://clickhouse.tech/docs/zh/ ClickHouse中文官网，讲的比较详细

ClickHouse是一个用于联机分析(OLAP)的列式数据库管理系统(DBMS)。在传统的行式数据库系统中，数据总是按照行来存储，同一行的数据总是被物理的存储在一起，常见的行式数据库有：MySQL、Postgres和MS SQL Server。

比如：

在列式存储数据库中，数据按照如下方式存储：

我们很容易看出两种存储方式的区别。不同的数据存储方式适用不同的业务场景，数据访问的场景包括：

• 进行了何种查询、多久查询一次以及各类查询的比例；
• 每种类型的查询(行、列和字节)读取多少数据；
• 读取数据和更新之间的关系；
• 使用的数据集大小以及如何使用本地的数据集；
• 是否使用事务,以及它们是如何进行隔离的；
• 数据的复制机制与数据的完整性要求；
• 每种类型的查询要求的延迟与吞吐量等等。

系统负载越高，依据使用场景进行定制化就越重要，并且定制将会变的越精细。没有一个系统能够同时适用所有不同的业务场景。如果系统适用于广泛的场景，在负载高的情况下，要兼顾所有的场景，那么将不得不做出选择。是要平衡还是要效率？

OLAP场景的关键特征

• 绝大多数是读请求

• 数据以相当大的批次(> 1000行)更新，而不是单行更新;或者根本没有更新。

• 已添加到数据库的数据不能修改。

• 对于读取，从数据库中提取相当多的行，但只提取列的一小部分。

• 宽表，即每个表包含着大量的列

• 查询相对较少(通常每台服务器每秒查询数百次或更少)

• 对于简单查询，允许延迟大约50毫秒

• 列中的数据相对较小：数字和短字符串(例如，每个URL 60个字节)

• 处理单个查询时需要高吞吐量(每台服务器每秒可达数十亿行)

• 事务不是必须的

• 对数据一致性要求低

• 每个查询有一个大表。除了他以外，其他的都很小。

• 查询结果明显小于源数据。换句话说，数据经过过滤或聚合，因此结果适合于单个服务器的RAM中

列式数据库更适合OLAP场景的原因

行式

列式

很容易看出其中的差别，我们考虑一下为什么会发生这种情况：

1. 针对分析类查询，通常只需要读取表的一小部分列。在列式数据库中你可以只读取你需要的数据。例如，如果只需要读取100列中的5列，这将帮助你最少减少20倍的I/O消耗。
2. 由于数据总是打包成批量读取的，所以压缩是非常容易的。同时数据按列分别存储这也更容易压缩。这进一步降低了I/O的体积。
3. 由于I/O的降低，这将帮助更多的数据被系统缓存。

由于执行一个查询需要处理大量的行，因此在整个向量上执行所有操作将比在每一行上执行所有操作更加高效。同时这将有助于实现一个几乎没有调用成本的查询引擎。如果你不这样做，使用任何一个机械硬盘，查询引擎都不可避免的停止CPU进行等待。所以，在数据按列存储并且按列执行是很有意义的。

有两种方法可以做到这一点：

1. 向量引擎：所有的操作都是为向量而不是为单个值编写的。这意味着多个操作之间的不再需要频繁的调用，并且调用的成本基本可以忽略不计。操作代码包含一个优化的内部循环。
2. 代码生成：生成一段代码，包含查询中的所有操作。

这是不应该在一个通用数据库中实现的，因为这在运行简单查询时是没有意义的。但是也有例外，例如，MemSQL使用代码生成来减少处理SQL查询的延迟(只是为了比较，分析型数据库通常需要优化的是吞吐而不是延迟)。

总结

概括来讲，存储引擎分为两大类:

• 针对事务处理( OLTP )优化的架构
• 针对分析型(OLAP)的优化架构。

它们典型的访问模式存在很大差异 :

• OLTP系统通常面向用 户，这意味着他们可能收到大量的请求。为了处理负载，应用程序通常在每个查询中只涉及少量的记录。应用程序基于某种键来请求记录 ，而存储引擎使用索引来查找所请求键的数据。磁盘寻道时间往往是瓶颈 。
• 由于不是直接面对最终用户 ，数据仓库和类似的分析型系统相对并不太广为人知，它们主要由业务分析师使用。 处理的查询请求数目远低于OLTP系统， 但每 个查询通常要求非常苛刻，需要在短时间 内扫描数百万条记录。 磁盘带宽(不是 寻道时间)通常是瓶颈，而面向列的存储对于这种工作负载成为日益流行的解决 方案。

在OLTP方面，由两个主要流派的存储引擎 :

• 日志结构流派，它只允许追加式更新文件和删除过时的文件，但不会修改 已写入的文件 。 BitCask、 SSTables、 LSM-tree、 LeveIDB、 Cassandra、 HBase、 Lucene 等属于此类。
• 原地更新流派，将磁盘视为可以覆盖的一组固定大小的页。 B-tree是这一哲学的最典型代表，它已用于所有主要的关系数据库，以及大量的非关系数据库。

日志结构的存储引擎是一个相对较新的方案。其关键思想是系统地将磁盘上随机访问写入转为顺序写入，由于硬盘驱动器和SSD的性能特性，可以实现更高的写入吞吐量。作为应用开发人员，掌握更多有关存储引擎内部的知识，可以更好地了解哪种工具最适合你的具体应用。

最后修改于 2021-07-09