# 4. 数据存储和检索


数据如何存储，如何检索

<!-- more -->

## 1. 存储引擎
上一节我们讨论了**数据模型和查询语言**，即应用开发人员向数据库执行数据格式并在之后如何查询的机制。接下来我们从数据的角度在此探讨同样的问题，即如何存储输入的数据，并在收到查询请求时，如何重新找到数据。

接下来我们将比较两个存储引擎家族: **日志结构**的存储引擎和**面向页**的存储引擎。

数据结构的核心是数据结构，为了高效的查询数据库中的数据，我们需要新的数据结构: 索引。索引背后的基本思想是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据。索引是基于原始数据派生而来的额外数据结构，它只会影响查询性能，维护额外的结构势必会引入开销，由于每次写数据时，需要更新索引，因此任何类型的索引都会降低写速度。

一个存储引擎通常需要解决以下问题:
1. 文件格式: 数据存储的方式，影响数据解析的效率，影响索引的选择，数据增删改查的方式
2. 数据分段: 数据和日志不可能只保存在一个文件中
3. 奔溃恢复
4. 部分写入的处理
5. 并发控制

## 2. 索引
### 2.1 哈希索引
内存中的 hash map 把每个键一一映射到数据文件中特定的字节偏移量。只要所有的 key 可以放入内存，只需要一次磁盘寻址，就可以查询到key 对应的 value 值。

哈希索引也有其局限性:
1. 哈希表必须全部放入内存
2. 哈希变满时，继续增长代价昂贵，并且哈希冲突时需要复杂的处理逻辑
3. 不支持区间查询。

使用 hash map 的典型存储引擎是 Bitcash(Riak 中的默认存储引擎，是一个 key-value 键值数据库)。Bitcash 是如何解决存储引擎的上述问题的呢？
1. 文件格式: 二进制格式，首先以字节为单位来记录字符串的长度，之后跟上原始字符串
2. 数据分段: 
    - 数据被分解成一定大小的段，多个数据段可以**按键合并压缩**(数据也是以key-value存储的)
    - 每个段都有自己的内存哈希表，查询时按照新旧程度顺序索引哈希表
3. 增删改查: 数据删除需要使用墓碑，以便在合并数据段时丢弃删除的记录
4. 奔溃恢复: 
    - 数据库重启 hash map 需要重建，此时需要扫描整个数据库文件
    - Bitcash 通过将 hash map 的快照存储在磁盘上，来加速索引的重建
5. 部分写入: 记录需要添加校验来发现部分写入的记录
6. 并发控制: 由于 Bitcash 采用追加写的方式，严格按照写入的先后顺序进行写入，并且数据是不可修改的，通常的实现是只有一个写线程。

通过实践证明追加写的设计非常合理，理由是:
1. 追加和分段主要是顺序写，通常比随机写快很多
2. 如果段文件是追加的和不可变的，并发和崩溃恢复要简单的多
3. 合并旧段可以避免随着时间推移数据文件出现碎片化的问题。

### 2.2 SSLTable 和 LVS-Tree
前面介绍采用追加写的数据分段中，key-value 是按照顺序写入的，后出现的值将覆盖之前的值。除此之外文件中 key-value 的顺序并不重要。而 SSLTable(排序字符串表)要求**每个键在每个段中只能出现一次，且 key-value 是顺序排序的**。

SSLTable 相比哈希索引的数据分段具有以下优点:
1. 合并段更加简单高效，即使文件大于内存，也可以使用类似归并排序的算法进行合并
2. 查询时，不需要再内存中保存所有键的索引，因为键是有序的，使用间隔的稀疏内存索引和二分查找就可以快速检索数据
3. 由于读请求往往需要扫描请求范围内的多个key-value，可以考虑将这些记录保存到一个块中并在写磁盘之前将其压缩，然后稀疏内存索引的每个条目指向压缩块的开头。

#### 构建和维护 SSLTable
SSLTables 构建的核心是如何让数据按键排序，有很多树结构支持按任意顺序插入并以排序后的顺序的读取。存储引擎的基本工作流程如下:
1. 写入时，将其添加至内存中的平衡树结构中(比如红黑树)，这个树又称为内存表
2. 当内存表大于一个阈值时，将其作为 SSLTable 写入磁盘文件
3. SSLTable 写入磁盘就可以创建新的内存表实例
4. 读请求，先从内存表读取，然后是磁盘段文件
5. 后台进程周期性执行段合并和压缩
6. 写入时，会同时写入内存表和追加至日志文件中，已进行崩溃恢复

以上正是 LevelDB  RocksDB key-value 键值数据库所使用的。类似的存储引擎还包括 Cassandra 和 HBase。

SSLTable 最初以 LSM-Tree 命名，基于**合并和压缩排序文件**原理的存储引擎通常被称为 LSM 存储引擎。

#### 性能优化
查找数据库不存在的键时，LSM-Tree 算法可能很慢，因为要从内存表追溯到最旧的段文件。为了优化这种访问，存储引擎通常使用**布隆过滤器**。

不同的策略会影响 SSLTable 压缩和合并的具体顺序和时机。常见的两种方式是: **大小分级和分层压缩**:
1. 大小分级: 较新和较小的 SSLTable 被连续合并到较旧和较大的 SSLTable
2. 分层压缩: 键的范围分裂成多个更小的 SSLTable，旧数据被移动到单独的纷呈，这样压缩可以逐步进行并节省磁盘空间

#### SSLTable 总结
对于使用 SSLTable的存储殷勤:
1. 即使数据集远远地大于可用内存，仍然能正常工作
2. 由于数据集按排序存储，因此可以有效执行区间查询
3. 由于磁盘顺序写入，SSLTable 可以支持非常高的写入吞吐量。

### 2.3 B-trees
和 SSLTable 一样，B-tree 保留了按键顺序的 key-value，可以实现高效的 key-value 查找和区间查询。但相似仅此而已，B-tree 有着非常不同的设计理念:
1. B-tree 将数据库分解成固定大小的页，通常为 4KB，也是内存读写的最小单元，这种设计更接近底层硬件，因为磁盘也是固定大小的块
2. 每个页都有地址或位置标识，可以让一个页引用另一个页，这样所有的页将构造成一个树状页集合
3. 更新现有键的值，首先搜索包含该键的叶子页，然后更新，并将整个页写回磁盘
3. 插入时类似，找到其范围包含新键的页，添加至该页，然后写入整个页，如果也没有足够的空间就会分裂
4. 插入算法会自动保证树的平衡，具有 n 个键的 B-tree 具有 Ologn 的深度，大多数数据库都只有 3-4层的 B-tree

#### B-tree 的可靠性
B-tree 底层的基本写操作是使用新数据覆盖磁盘的旧页，在也分裂时，需要写多个页，并更新父页内对子页的引用。这是比较危险的，因为如果数据库在完成部分页写入后发生奔溃，会导致索引破坏。

为了从奔溃中恢复，数据库中的 B-tree 实现需要支持磁盘上的额外数据结构: 预写日志(write-ahead log, WAL)，也称为重做日志。这是一个仅追加写的文件，每个 B-tree 的修改必须先更新 WAL 然后在修改树本身的页。

原地更新页的另一个复杂因素是，多线程并发访问控制，否则线程可能会看到树处于不一致的状态。通常使用锁存器(轻量级的锁)保护树的结构来完成。这方面，日志结构化的方法(LVS-tree)显得更简单，因为它们在后台执行合并，不干扰前端的查询。

### 2.4 B-tree 与LSM-tree 对比
根据经验，LSM-tree 通常写入更快，B-tree 读取更快，具体也依据实际使用场景不同。

LSM-tree 的优点:
1. 顺序写，具有较低的写放大，支持更高的写入吞吐量
2. 支持更好的压缩，通常更小。相反 B-tree 存在碎片导致占据更大的空间

LSM-tree 的缺点:
1. 压缩过程中，有时会干扰正在进行的读写操作，及时存储引擎尝试增量执行压缩，不影响并发访问，但是磁盘并发资源有限，执行昂贵的压缩时，很容易发生读写等待，相反 B-tree 的响应延迟则更具确定性
2. 如果写入吞吐量很高可能会发生压缩无法匹配数据写入速率的情况，此时数据段将不断增多，读取速率也会降低

B-tree 的优点:
1. 每个键都唯一对应于索引中的某个位置，而日志结构的存储引擎可能在不同的段中具有相同键的多个副本
2. 如果希望提供强大的事务语义，B-tree 更具吸引力。在许多关系型数据库中，事务隔离是通过键范围上的锁实现的，在B-tree 索引中这些锁直接定义在树中

### 2.5 其他索引
#### 聚簇非聚簇索引
1. 聚簇索引: 就是记录直接保存在索引中
2. 非聚簇索引:
    - 索引值保存的是数据的引用，实际数据存放在堆文件中
    - 每个索引只引用堆文件中数据的位置信息，可以避免数据重复
    - 当更新值而不是更新键时，堆文件非常高效，只要新值不大于旧值就可以原地更新
    - 如果更新的新值比旧值大，就需要移动数据同时更新所有索引中数据的指向
    - 从索引到堆文件的额外跳转对于读取是很大的性能损失

#### 多列索引和多维度索引
1. 多列索引: 由多列数据组成的索引
2. 多维度索引: **一次查询多列的方法**，比如地理空间查询，标准的 B-tree 和 LSM-tree 都无法高效的完成此类查询

多维度索引的一种选择是将多维转换为一维然后使用 B-tree 索引。更常见的是使用专门的空间索引，比如 PostGIS 使用 Post供热SQL 的广义搜索树。另一种多维索引技术是 **HyperDex**


#### 全文索引和模糊索引
前面介绍的索引都是**查询确切的数据**，而全文索引或者模糊索引支持对一个单词的所有同义词进行查询，并忽略单词语法上的变体，即一种模糊查询。

#### 在内存中保存所有内容
目前讨论的所有数据结构都是为了适应**磁盘限制**。与内存相比，磁盘更难处理，需要精心安排磁盘上的数据布局。这些都是值得的，因为磁盘可以进行数据持久化并且每 GB 容量成本更低。

随着内存的更便宜更大，内存数据库也随之出现和发展。一些内存 key-value 数据库主要用于缓存，数据丢失是可接受到。但是其他内存数据库通过一些技术，比如: 用特殊的硬件(电池供电内存)，将更改记录磁盘，定期快照至磁盘、复制内存到其他机器等方式实现持久化。尽管写入磁盘，但是磁盘仅仅用于持久化目的，读取完全靠内存服务。

内存数据库有:
1. VoltDB/MemSQL/Oracle TimesTen：具有关系模型的内存数据
2. RAMCloud: 开源的具有持久性的内存 key-value 数据库，对内存和磁盘上的数据使用日志结构
3. Redis/Couchbase: 通过异步写入磁盘提供较弱的持久性。

**与直觉相反，内存数据库的性能欧式并不是因为它们不需要从磁盘读取。如果有足够的内存，即便是基于磁盘的存储引擎，也可能不需要从磁盘读取，因为操作系统将最近使用的磁盘块缓存在内存中。相反内存数据库可以更快是因为它们避免使用写磁盘的格式对内存数据结构编码的开销。**

内存数据库另一个有意思地方是提供了基于磁盘索引难以实现的数据结构，典型的是 Redis。内存数据库使用所谓的**反缓存方法**，在内存不够用时将最近最少使用的数据写到磁盘，可以支持比内存更大的数据集。

将来非易失性存储得到广泛普及后，存储引擎将会进一步更新。

## 3. 列式存储
### 3.1 事务处理和分析处理
数据库的使用有另种典型的应用场景:
1. 事务处理: OLTP(online transaction processing)
    - 应用程序使用索引中的某些键查找少量记录，根据用户输入插入或者更新记录。因为这些应用程序是交互的，所以访问模式被称为**在线事务处理**
    - 事务，主要指组成一个逻辑单元的一组读写操作
2. 分析处理: OLAP(online ayalytic processing)
    - 分析查询需要扫描大量记录，每个记录只读取少数激烈，并计算汇总统计信息，而不是返还原始数据给用户
    - 为了区分**使用数据库与事务处理**的模式，称之为在线分析处理 

|属性|OLTP|OLAP|
|:---|:---|:---|
|主要读特征|基于键，每次返回少量的记录|对大量记录进行汇总|
|主要写特征|随机访问，低延迟写入用户输入|批量导入(ETL)或事件流|
|典型使用场景|终端用户，通过网络应用程序|内部分析师，为决策提供支持|
|数据表征|最终的数据状态(当前时间点)|随时间而变化的所有事件历史|
|数据规模|GB到TB|TB到PB|
|请求数|大量用户请求，使用索引查找数据，磁盘寻道是瓶颈|请求数量少，扫描行数多，磁盘带宽是瓶颈|

**当查询需要在大量行中顺序扫描是，索引的关联性就会显著降低，相反最重要的是非常紧凑的编码数据，以尽量减少磁盘读取的数据量**.

### 3.2 数据仓库
单独的用于数据分析的数据库，被称为数据仓库。企业可能有十几种不同的交易数据，数据仓库包含公司所有 OLTP 系统的只读副本。将数据导入数据仓库的过程称为**提取-转换-加载**(Extract-Transform-Load, ETL)。

OLAP 通常要扫描大量数据，代价昂贵，使用单独的数据仓库可以避免对 OLTP 业务产生影响，保证其高可用和并发执行事务的性能。于此同时单独的数据仓库可以针对分析访问模式进行优化，这就是我们接下来要说的**列式存储**，它可以实现我们前面所说的紧凑的编码数据的目的。

数据仓库的数据模型最常见的是关系型，因为 SQL 通常适合分析查询。表面上数据仓库和关系型 OLTP 数据库看起来很相似，因为他们都具有 SQL 查询接口，但是系统内部差异很大，针对不同的查询模式进行了各自的优化。

开源的数据仓库包括: Apache Hive、Spark SQL、Cloudera Impala、FaceBook Presto、Apache Tajo、Apache Drill

### 3.3 分析业务的数据模型
分析业务的数据模型非常少，许多数据仓库都实用了星型模式，又称维度建模，包括:
1. 事实表: 模式的中心
    - 每一行表示在特定时间发生的事件
    - 每一列是属性，与维度表关联的外键
2. 维度表: 维度表记录了时间的对象、什么、地点、时间、方法以及原因
3. 日期和时间通常使用维度表示，这样可以对日期时间进行分组对比分析

### 3.4 列式存储
星型模式中的数据仓库中，事实表通常**列数非常多**，因为要记录所有事件**占据的存储非常大**，对其高效的存储和查询是一个挑战。虽然事实表列数非常多，但典型的查询往往值访问其中4、5列。

大多数 OLTP 数据库中，存储以**面向行的方式布局**: 来自表的一行的所有值彼此相邻存储。即便只需要一行中的个别列，但是仍然需要将过滤出的行的所有列从磁盘加载到内存并解析它们，最后丢弃不需要的列。

面向列存储则，不需要将一行中的所有值存储在一起，而是**将每列中的所有值存储在一起**，查询时只需要读取和解析需要的列，从而节省大量的工作。面向列存储依赖一组文件，每个文件以相同顺序保存着数据行。

![列式存储](/images/db/db_columns.jpg)

面向列的存储还非常适合压缩。通常列中的不同值的数量要远小于行数，我们可以使用**位图编码**进行压缩，具体的做法是:
1. 假如一列有 n 个不同值，每个值有独立的一行位图，一个位对应一行
2. 如果行具有该值，该位为 1
3. 如果 n 很大，大多数位图将会有很多零，此时位图可以进行游程编码

说起来比较复杂我们看下面的图示

![位图编码](/images/db/bits_save.png)

位图索引非常适合下面这样的查询:

```
WHERE product_sk IN（30，68，69）
WHERE product_sk = 31 AND store_sk = 3
```

只要加载相应的位图行，执行按位与计算即可。对于不同类型，还有各种其他的压缩算法。

注意: Cassandra 和 HBase 有一个列族的概念，他们继承自 Google Bigtable，但是它们每个列族中，都将一行中的所有列与行主键一起存储，并且不使用列压缩。因此，Bigtable模型仍然主要是面向行的。

处理数据存储，OLAP 数据库还有其他问题需要考虑:
1. 从磁盘获取数据到内存的带宽
2. 如何高效的将内存带宽用于CPU缓存

而列式存储除了有效降低数据量外，还有利于高效利用 CPU 周期。

### 3.5 列存储中的排序
列存储中每列独自排序是没有意义的，因为那样我们就不会知道列中的哪些项属于同一行。我们可以基于常见查询的知识，将列存储中的数据，按照常见查询的键进行排序后存储。这样一方面可以加快常见查询查询速度，另一方面可以增加**排序键的压缩效果**。

第一个排序键的压缩效果最强。第二和第三个排序键的压缩情况会变得更加复杂，因为通常不会有太多相邻的重复值。排序优先级进一步下降的列基本上会呈现接近随机的顺序。

不同的查询受益于不同的排序顺序，那么为什么不以多种不同的方式存储相同的数据呢？无论如何，数据需要复制到多台机器来保证数据不丢失。因此存储**不同方式排序的**冗余数据，正是商业数据仓库 Vertica 使用的方式。

### 3.6 列存储的写操作
面向列的存储，压缩和排序都有助于更快地读取这些查询。然而，他们有写更加困难的缺点。

使用B树的更新就地方法对于压缩的列是不可能的。如果你想在排序表的中间插入一行，你很可能不得不重写所有的列文件。由于行由列中的位置标识，因此插入必须始终更新所有列。

幸运的是，本章前面已经看到了一个很好的解决方案：LSM树。所有的写操作首先进入一个内存中的存储，在这里它们被添加到一个已排序的结构中，并准备写入磁盘。内存中的存储是面向行还是列的，这并不重要。当已经积累了足够的写入数据时，它们将与磁盘上的列文件合并，并批量写入新文件。这基本上是Vertica所做的。

查询需要检查磁盘上的列数据和最近在内存中的写入，并将两者结合起来。但是，查询优化器隐藏了用户的这个区别。