设计数据密集型应用3 —— 数据存储与读取

序言

上一篇我们介绍了数据模型和查询语言相关的原理，本篇我们介绍实际的数据库引擎，数据存储和读取的实现方式。当实际工作中遇到数据库选型和性能调优的问题时，掌握这些知识至关重要。

不同类型的存储引擎，会针对不同类型的负载做优化。事务处理(online transaction processing, OLTP)的场景与数据分析(online analytic processing, OLAP)的场景，对应的存储引擎设计方案差距巨大。

我们来看看主流数据库中使用最多的两种数据引擎:日志结构的存储引擎(Log Structured Merge Tree，LSM-Tree)与页结构的存储引擎(B-Tree)

从0到1设计数据库

我们来实现一个最简单的数据库:

#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

通过两个简单的shell函数，就实现了一个可以存储键-值对的极简版数据库。db_set()向database文件中插入数据，db_get()读取相应key的最近一条记录。

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}']

$ db_get 42

{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

db_set()采用的是追加写的方式，每次将数据追加到数据库的末尾。如果对同一个key进行了多次更新操作，旧版本的数据不会被覆盖掉，所以db_get()使用了tail -n 1来获取最新版本的记录。

追加写的性能非常好。现实中的很多数据库，底层使用了和db_set()类似的日志文件，通过追加写的方式更新数据。当然实际的数据库有更多的设计问题需要考虑，比如为了防止日志文件体积无限增长，要对数据进行压缩并清理旧版本数据记录，为了防止多个客户端在同时写入时产生脏数据，要做好并发控制。

然而db_get()的性能就很差了，每次查询都需要扫描整个database文件，为了提高查询的效率，我们需要引入一个新的数据结构:索引(index)。

索引的基本思想，是维护一份额外的元数据，来加速查询，类似图书的目录，帮助我们更快地定位到相关内容。

虽然提高了查询性能，但是索引不是免费的午餐 ———— 它增加了数据写入的成本，写入操作不仅要写原始数据，还需要对索引进行更新。

索引是数据库存储引擎设计中一个重要的权衡。数据库通常不会为所有的内容创建索引，而是需要应用开发者来指定对哪部分数据创建哪种类型的索引。

哈希索引

让我们从最简单的场景开始，假设我们的数据是以key-value形式存储的(现实场景中这是普遍情况)， 插入数据的时候，以追加写的方式，写入单个文件。

对这类数据最简单的索引方式，是创建一个HashMap索引，索引的key就是数据的key，索引的value取数据在文件中的偏移量:

只要索引的体积不是特别大，能够装载进内存，那么查询速度就会很快 ———— 根据传入的key值，从索引中读到偏移量，然后到文件中相应的位置读取数据。由于采用了追加写的方式，写操作的速度也非常快。

追加写的问题在于，如果数据源源不断地被写入，磁盘终将被耗尽。为了解决这个问题，一个好的方式从单个日志文件存储的方式切分为按分段(segment)存储的方式，单个分段限制存储体积的上限，当达到这个上限时，就创建一个新的分段，后续追加的数据写入到这个新的分段中。

为了减少数据存储所需空间，可以对分段进行压缩(compaction)，删除掉同一个key的过期版本。并且由于分段被压缩之后体积通常会大大减小，我们还可以把多个压缩后的小分段，合并成一个新的分段。由于数据写入之后不再被修改，压缩操作可以在一个后台线程中安全地执行。

压缩操作示意图:

分段存储之后，可以为每个分段建立hash索引。查询数据的时候，首先将最新的一个分段对应的hash索引加载进内存，读出偏移量并获取相应的数据值。如果未找到所需数据，则继续查找下一个次新的分段，依次类推完成整个查询操作。

采用追加写日志的方式，同一个key可能会写入多个版本的记录，初看上去比直接更新key值，更加浪费存储空间，但是追加写有一些重要的优势:

• 追加写操作比随机写具有更好的性能，尤其是数据存储在机械硬盘的场景，避免了磁头寻址的开销。
• 数据一旦写入，就不能再被修改，这种不可变属性(Immutable)能够更好地适应并发和容灾的场景。在随机写的情形，可能会发生数据更新到一半，系统出现了故障，导致脏数据的产生。
• 对于分段的压缩与合并，可以避免数据文件碎片化的问题。

目前的方案也存在一些缺陷:

• 哈希索引必须能够被装载进内存。如果数据包含的key很多，导致索引超出了内存容量的限制，那么查询速率就会很慢。
• 范围查询效率很差。如果需要查询kitty0000到kitty9999范围内的数据，可能需要扫描整个哈希索引。

SSTable与LSM-Tree

为了优化上文中哈希索引方案的缺陷，我们实现分段文件时，引入两个额外的约束:

• 在每个分段文件中，key-value键值对按key排序
• 每个分段文件中，执行完压缩操作之后，单个key在该文件中只出现一次

满足这两个约束的分段文件，被称作SSTable(Sorted String Table), 相比于之前的hash索引方案，有以下几个优势:

• 为了查找某个key，我们不再需要在内存中存储所有key的索引，现在只需要稀疏地存储某些key即可。为了找到某个key，我们可以根据稀疏的has索引确定一个大致范围，然后通过二分搜索定位到想要查找的key。

比如下图的例子，为了查找key handiwork, 我们首先查到handbag 和 handsome 对应的偏移量，然后在这个范围内通过二分查找，即可快速查出handiwork

• 范围查询也变得更加高效。基于查询范围的上界和下界，根据稀疏的hash索引，可以很快确定偏移量范围，然后批量读取数据块。

• 分段文件的合并(merge)操作也变得更加高效。因为各个分段文件是有序的，可以通过高效的归并排序，完成多个分段文件的合并。

构造和维护SSTable

如何构造SSTable呢?我们采用的是追加写的方式，如何让生成的SSTable满足按key排序的约束呢？

计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。

整理磁盘中的数据使其重新变得有序成本是很高的，我们可以引入一个间接的中间层，让数据先写入内存，在内存中维护一个有序的数据结构，比如红黑树或者AVL树，然后将内存中的有序数据依次写入磁盘生成SSTable。

具体的存储引擎实现方式为:

• 写操作首先将数据写入内存，在内存中维护一颗有序的平衡树，这颗树也被称作memtable。
• 当memtable的数据量超过一定阈值时，将memtable整体写出到磁盘，生成一个新的SSTable，由于memtable中的key是有序的，所以SSTable中的数据也保持有序。
• 读请求，首先在memtable中查找相应的key，未找到的话，再依次查找各个SSTable。
• 后台间歇性地对SSTable进行合并和压缩，清理过期数据。

现在还剩一个问题需要解决，当系统发生crash时，内存中的memtable数据会丢失。为了避免这个问题，我们可以先把数据追加写入一个临时的日志文件，如果系统crash，可以从这个日志文件重建memtable，当memtable被写出磁盘生成SSTable之后，临时的日志文件可以被删除。

这样的存储引擎实现方案被称作Log-Structured Merge-Tree(LSM-Tree)，其架构如下图所示:

LSM-Tree实际工程实现的时候，还有很多技术细节需要考虑，比如当所需查找key不存在时，需要扫描memtable以及所有的SSTable，才能确定key确实存在，性能比较差。为了解决这个问题，存储引擎常常维护一个额外的布隆过滤器(Bloom filter)，通过位数组来快速判断出一个key不存在。

B-Tree

基于日志结构的索引存储方式正变得日渐流行，但是实际上用得最多的索引存储方式是B树，几乎所有的关系型数据库都是用B树作为索引存储结构。

和memtable类似，B树也将key-value数据按顺序存储，但是B树在底层不是按分段文件存储，而是按页面(page)存储，每个页面通常大小为4k，这么设计是为了适配磁盘按固定大小区块的数据存储方式，每次读写以页面为单位，性能较好。

每个页面中包含多个节点，每个节点包含指向子页面的指针，各个节点按数据大小排序。页面中的相邻两个节点，标识了一个数据区间 ———— 所指向的子页面的数据，其范围处于这两个节点数据数据之间。

指向子页面的指针，将父子页面串联起来，构成了最终的B树，其结构如下图所示:

以查找键值为251的节点为例，首先在根页面节点定位到200~300的范围，根据子页面的指针寻址到相应的子页面，接着在子页面中定位到250~270的范围，再寻址到相应的子页面，最终查到251节点对应的值。

单个页面包含的子页面指针数量，称作B树的分支因子(branching factor)，上图中的分支因子是6。实际的应用系统中，分支因子通常在数百至数千之间，B树的高度只需要3到4层，就足以存储所有的数据。在查询数据的时候，通常只需要3到4次的寻址操作，可以迅速完成。

B树的可靠性

为了保证B树的可靠性，在系统crash时也不丢失数据，和LSM-Tree类似，在数据写入B树之前，首先会先写入到磁盘上的一个日志文件中，这个日志文件被称作write-ahead log(WAL, 也被称作redo log), 采用追加写入的方式。在crash发生时，读取WAL恢复数据。

为了保证并发写入时候的数据一致性，引入了latches(一种轻量级的锁)，在后台将写入操作合并，并通过原子性的swap操作，用新的页面数据替换到旧的页面。

比较B-Tree和LSM-Tree

由于底层实现机制的不同，LSM-Tree的写操作是顺序地追加写日志文件，B-Tree是随机的页面粒度写，所以LSM-Tree的写操作通常更快一些。LST-Tree的读操作需要扫描MemTable和SSTable,而B-Tree的读操作通常指需要几次寻址操作，所以B-Tree的读操作通常更快一些。这个是经验法则，实际场景中还是要以实际的性能测试数据为准。

事务处理与数据分析

早期的业务数据处理，典型的场景是在一个事务中，向关系型数据库存入数据，然后其他应用通过索引查出数据库中的少量行，再进行后续处理。这种数据处理模式被称为在线事务处理(online transaction processing, OLTP)。

除了事务处理之外，还有一种非常不同的数据分析的场景: 一次分析查询通常需要扫描很多行记录，每行记录中取出少部分列，然后做一些聚合统计分析，典型的场景例如:

• 统计所有门店的一月份总营收
• 统计上个季度销量最好的水果品类

这种场景被称作在线数据分析(online analytic processing, OLAP)

在数据总量不大(千万量级以内)时，传统关系型数据库可以同时满足OLTP和OLAP的需求，但是在大数据时代，当需要分析的数据量规模较大时，传统的关系型数据库在OLAP场景就难以满足性能要求，于是业界采用了一种新的数据库来解决OLAP场景的问题 —— 数据仓库(Data Warehouse)

数据仓库

数据仓库从OLTP数据库中提取(Extract)数据，转换(Transform)成适合分析场景的数据结构，然后加载(Load)到自己的存储中，供后续的数据分析场景使用。整个流程被称作Extract-Transform-Load(ETL)，如下图所示:

数据仓库的一大优势在于，将后台大规模分析请求和前台OLTP数据库的高频读写请求隔离开，可以针对分析请求的场景，对底层的数据引擎进行优化。

数据模型

上一篇中我们提到，OLTP数据库支持多种数据模型，比如二维行列模型、文档模型、图模型。OLAP数据库支持的数据模型比较标准化，其支持的数据模型被称作星型模型(star schema)，也被称作维度建模(dimensional modeling)。

以一个零售场景举例，其数据模型如下图所示:

在星型模型中，处于居中地位的是事实表(fact table)， 如上图中的销售明细表fact_sales，事实表包含了实际发生的每一个具体的事件信息，所以通常包含很多行和很多列。

事实表中可以参与统计计算的列，被称作属性(attribute)，比如fact_sales表中的discount_price列，可以用来计算营收。
其他的一些列包含了指向外部表的外键，这些外部表被称作维度表(dimension table)，比如dim_product，包含了事件的维度信息。

事实表处于居中地位，维度表作为外部支撑，构成了星型模型。

实际场景中，维度表可能会比较复杂，会被进一步分解成子维度表，此时的数据模型被称作雪花模型(snowflake schema)，是星型模型的一个变种。

基于列的存储

维度表数据量不大，数据查询的挑战主要在于事实表。

尽管事实表通常很宽，包含数百乃至上千列，实际查询的时候，几乎不会需要扫描出许多列数据。以下面的典型SQL为例，扫描了大量的行，但是只需要获取3列数据:

SELECT
    dim_date.weekday, dim_product.category,
    SUM(fact_sales.quantity) AS quantity_sold 
FROM fact_sales
    JOIN dim_date ON fact_sales.date_key =  dim_date.date_key
    JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk 
WHERE
    dim_date.year = 2013 AND
    dim_product.category IN ('Fresh fruit', 'Candy') GROUP BY
    dim_date.weekday, dim_product.category;

在大部分OLTP数据库，数据是按行存储的:把属于同一行的数据存储在一起。如果是用OLTP数据库来处理上述SQL，需要加载所有相关的行，然后过滤出相关的列，加载了大量的不必要数据，可能需要很长的时间才能返回结果。

所以在OLAP的场景，通常是采用按列存储的方式:把属于一列数据存储在一起，不同列分散存储，一次分析查询只需要读取少数相关的列，极大提升了查询效率。

列数据压缩

同一列中虽然存储了大量的数据，但是其取值范围通常是有限的，许多值在同一列中重复出现。为了进一步减少磁盘存储的数据量，我们可以在按列存储的时候，对数据进行压缩。下图演示了一种基于位数组的压缩方式:

• 对于在列中出现的数值，找到对应的位数组，将相应的位的值设置为1
• 对于位数组进行压缩编码，存储压缩后的值

写入数据仓库

采用列数存储并进行压缩之后，读取数据进行分析变得更加简单高效，但是相应地，写入成本变得更高。

如果我们采用了B-Tree作为底层存储，那么向压缩的列中写入一行数据，意味着几乎需要重写所有数据，这样的操作开销成本是无法接受的。

幸好我们之前已经了一个更适合的解决方案 ———— LSM-Tree。所有的写操作首先写入内存，生成Memtable，在Memtable的体积达到阈值时生成SStable，通过这种方式保证了写入操作的高吞吐。

物化视图与Data Cube

传统的OLTP数据库，提供了视图(view)的功能，视图提供了一个虚拟的查询的视角，可以看成SQL执行的快捷方式。由于OLTP场景下数据更新很频繁，所以视图不会直接存储查询结果。

在OLAP场景，由于数据更新通常不频繁，可以将实际查询的结果缓存起来，命中缓存的查询可以迅速返回结果，这样的缓存被称作物化视图(Materialized View)。

Data Cube 是视图的一种特殊形式，存储了按多个维度聚合的查询结果。下图是一个按2个维度聚合的Data Cube示例，实际使用场景中可能按更多的维度聚合。

总结

本章我们深入学习了数据库引擎的底层实现，主要介绍了两种主流的实现方式，

• 一种是B-Tree方式，将磁盘看作一系列可覆写的页，在索引的辅助下，对这些页进行随机读写。
• 一种是LSM-Tree方式，追加写入日志，底层不断对日志文件做合并和压缩。

我们也学习了两种主要的数据库场景。

• 一种是面向前台用户，大量的读写请求，每次只读写一小部分数据的OLTP场景。OLTP场景通常基于某些key执行查询请求，底层的存储引擎使用索引快速找到相应的数据，性能的瓶颈在于磁盘的查找时间。基于B-Tree的存储的引擎能很好地适应这种场景。
• 另一种是海量数据分析的OLAP场景，每次请求常常要扫描数百万乃至上亿行数据，针对某些维度做聚合统计分析。在这种场景下，索引对性能的影响已经不大，更重要的是对数据进行压缩编码以减少需要扫描的数据量，性能的瓶颈通常在磁盘的带宽。基于LSM-Tree的存储引擎在OLAP场景正变得愈发流行。