DDIA第三章

三. 存储与检索

• 日志结构的存储引擎
• 面向页面的存储引擎

驱动数据库的数据结构

索引：通过保存一些额外的元数据来作为路标帮助你找到想要的数据

• 额外的结构，添加与删除索引不影响数据的内容，而只会影响查询的性能
• 维护额外的结构会产生开销，维护索引减慢写入速度
• 提高读查询速度

散列索引

最简单的索引策略是：保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值在数据文件中的位置。写入新键值对时还需要更新散列映射。查找值时使用散列映射来查找数据文件中的偏移量来找到位置。

案例：Bitcask

• 适合每个键的值经常被更新的情况，例如键是url，值是url被点击的次数，这类工作负载有很多写操作，但没有太多不同的键，将所有键保存在内存中是可行的

如何避免最终用完硬盘空间？

• 将日志分为特定大小的段，当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的文件。可以对段进行压缩（conpaction：丢弃重复的键，只保留每个键的最近更新）
• 压缩可能会使段变得很小，可以在执行压缩的同时将多个段合并在一起。段不可以被修改，所以合并的段被写入一个新的文件。冻结段的合并和压缩可以在后台线程中完成，过程中使用旧段文件来正常提供读写请求，合并完成后转换为使用新段文件

合并需要考虑的问题

• 文件格式
• 删除记录
• 崩溃恢复
• 部分写入记录
• 并发控制

仅追加日志而不更新设计的好处

• 追加和分段合并都是顺序写入操作，通常比随机写入快得多
• 并发和崩溃恢复更简单，例如一个数据值在被更新的时候发生崩溃，不用担心文件里会同时包含新值或旧值的各自一部分（更新到一半）
• 合并旧段的处理也可以避免数据文件随时间的推移而碎片化的问题

散列索引的局限性

• 散列表必须能够放进内存。硬盘散列表表现很差，因为会产生大量的随机访问I/O，并且耗尽时扩充昂贵，同时需要很繁琐的逻辑去解决散列冲突
• 范围查询效率不高（很显然，因为键不是顺序的）

SSTables和LSM树

排序字符串表（Sorted String Table）

• 键值对的序列按键排序
• 每个键旨在每个合并的段文件中出现一次（压缩过程已经保证）

相比散列索引的优势

• 即使文件大于可用内存，合并段的操作仍然是简单而高效的，因为都是顺序排序的，合并类似于归并排序。多个段包含相同的键时，可以保留最近的段的值，并丢弃旧段中的值

• 不需要在内存中保存所有键的索引，内存中的索引可以变得更稀疏，找到一个表中不存在的键可以通过扫描这个键前后的两个键之间的区域来找到。
  

  假设你正在内存中寻找键 handiwork，但是你不知道这个键在段文件中的确切偏移量。然而，你知道 handbag 和 handsome 的偏移，而且由于排序特性，你知道 handiwork 必须出现在这两者之间。这意味着你可以跳到 handbag 的偏移位置并从那里扫描，直到你找到 handiwork（或没找到，如果该文件中没有该键）。

• 由于读请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为block，并在其写入硬盘之前对其进行压缩。稀疏内存索引中的每个条目都指向压缩块的开始处。除了节省硬盘空间之外，压缩还可以减少对I/O带宽的使用

构建和维护SSTables

• 新写入时，将其添加到内存中的平衡树数据结构，这个内存树有时被称为内存表
• 当内存表大于某个阈值时，将其作为SSTable文件写入硬盘，新的写入可以在一个新的内存表实例上继续进行
• 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找
• 后台时不时运行一个合并和压缩过程

问题：如果数据库崩溃，则最新的写入（在内存表中，但尚未写入硬盘）将丢失。

解决：硬盘上保留单独的日志，每个写入都会立即被追加到这个日志上，日志没有顺序，唯一的目的是在崩溃后恢复内存表。每当内存表写出到SSTable时，相应的日志都可以被丢弃

用SSTables制作LSM树

日志结构合并树（LSM树）：是基于更早之前的日志结构文件系统来构建的，基于这种合并和压缩排序文件原理的存储引擎通常被称为LSM存储引擎

在搜索查询中，由一个给定的2单词，找到提及单词的所有文档，这也是通过键值结构实现的：其中键是单词（term），值是所有包含该单词的文档的ID列表（postings list）。Lucene是一种全文搜索引擎，在Lucene中，从词语到记录列表的这种映射保存在类似于SSTable的有序文件中，并根据需要在后台合并

性能优化

• 查找数据库中不在的键时，LSM树算法可能会很慢（检查内存表和所有段），通常使用额外的布隆过滤器优化访问
• 使用不同策略来确定SSTables被压缩和合并的顺序和时间

LSM树的基本思想：保存一系列在后台合并的SSTables

• 即使数据集比可用内存大得多也会继续正常工作
• 键按顺序存储，可以高效地执行范围查询
• 硬盘写入是连续的，所以LSM树可以支持非常高的写入吞吐量

B树

将数据库分解成固定大小的块（block）或分页（page），传统上大小为4KB，并且一次只能读取或写入一个页面。

每个页面都可以使用地址或位置来标识，这允许一个页面引用另外一个页面——类似于指针，但在硬盘中。

图：查询

一个页会被指定为B树的根，在索引中查找一个键时从这里开始。页面包含键和对子页的引用，引用两侧的键表示子页管理的范围

一个页中对子页的引用的数量称为分支因子（branching factor）

图：通过分割页来生成B树

B树的基本底层写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置

如果数据库在系列操作进行到一半时崩溃，那么最终将导致一个损坏的索引。为了使数据库能处理异常崩溃的场景，B树通常会带有一个额外的硬盘数据结构：预写式日志（WAL，也称作重做日志，即redo log）。这是一个仅追加的文件，每个B树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在奔溃后恢复时，这个日志被用来使B树恢复到一致的状态

如果多个线程要同时访问B树：通常通过使用锁存器（latches 轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰新接收到的查询，并且能够时不时地将段文件切换为新的（该切换是原子操作）

B树的优化

• 写时复制
• 可以通过不存储整个键，而是缩短其大小来节省页面空间，允许页面中包含更多的键，允许树有更高的分支因子
• 通常，页面可以放在磁盘上的任何位置，如果某个查询需要按顺序扫描大部分的键范围，那么这种布局可能会效率低下。许多B树的实现在布局树时会精良使叶子页面按顺序出现在硬盘上，但是随着树的增长，要维持这个顺序是很困难的
• 在树种添加额外的指针
• B树的变体分形树

比较B树和LSM树

通常来说LSM的写入速度更快，而B树的读取速度更快

写入时，LSM树中的MemTable的追加写入速度要比B树的维护快得多。

• B树的写入不是一个纯粹的内存操作，因为从根节点到数据页的路径中，有任何页不在缓存里，数据库都会触发磁盘IO来读取，所以写入场景下，B树的维护就慢了
• LSM写入的追加发生在内存中

拓展阅读：分布式数据库存储透析：B-TREE和LSM-TREE的性能差别

LSM的优点

• 较低的写放大（每笔数据导致对硬盘的多次写入）
• 顺序写入紧凑的SSTable文件而不是必须覆写树中的几个页面
• LSM树可以被压缩的更好，通常能产生更小的文件
• 较低的写入方法率和减少的碎片对固态硬盘更有利，更紧凑地表示数据允许在可用的 I/O 带宽内处理更多的读取和写入请求

LSM树的缺点

• 压缩过程有时会干扰正在进行的读写操作。虽然增量压缩对于并发访问的影响较小，但会发生某个请求需要等待硬盘先完成昂贵的压缩操作的情况，可能会导致在更高百分位的相应时间相当长
• 硬盘的有限写入贷款需要在初始写入（记录日志和刷新内存表到硬盘）和后台运行的要锁线程之间共享。高写入吞吐量时，有可能导致压缩跟不上写入速率。硬盘上未合并的段不断增加，直到硬盘空间用完，读取速度也会减慢。需要自己监控来检测这种情况
• B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得B树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接附加到树上

其它索引结构

次级索引主要的不同是键不是唯一的，即可能有许多行有相同的键

将值存储在索引中

索引中的键可能有两种情况

1. 实际的行
2. 对存储在别处的行的引用，行存储的地方被称为堆文件，并且存储的数据没有特定的顺序

堆文件方法避免了多个次级索引时对数据的复制，在不更改键的情况下更新值时，堆文件方法可以非常高效

• 新值的字节数不大于旧值：直接覆盖该记录
• 大于旧值：可能需要移到堆中有足够空间的新位置，在这种情况下，要么所有涉及的索引都需要更新以指向新堆位置，要么在旧堆位置留下一个转发指针

聚集索引：被索引的行直接存储在索引中

在聚集索引和非聚集索引之间的这种被称为覆盖索引，其在索引内存储表的一部分列。这允许通过单独使用索引来处理一些查询（这种情况下，可以说索引覆盖了查询）

多列索引

最常见的多列索引被称为连接索引（concatenated index） ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）

多维索引

例如对于查询矩形地图区域内的所有餐馆，这需要一个二维范围查询，一个标准的B树或LSM树不能高效的处理这种查询，它可以返回一个纬度范围内的所有餐馆（但经度可能是任意值），或者返回在同一个经度范围内的所有餐馆（但纬度可能是北极和南极之间的任意地方），但不能同时满足两个条件

两个选择

• 使用空间填充曲线，将二维位置转化为单个数字，然后使用B树
• 使用特殊的空间索引，例如R树

全文搜索和模糊索引

搜索类似的键

内存中的存储

RAM变得更便宜

内存中的数据持久化可以通过特殊的硬件（电池供电的RAM）来实现，或者将日志或定时快照写入硬盘，或者将内存中的状态复制到其它机器上来实现

内存数据库的性能优势不在于他们不需要从硬盘中读取，而在于省去了将内存数据结构编码为硬盘数据结构的开销

内存数据库提供了难以用基于硬盘的索引实现的数据模型，例如Redis为各种数据结构提供了类似数据库的接口

内存数据库可以通过类似于缓存与硬盘交换的方式扩展到支持比可用内存更大的数据集 （反缓存 anti-caching）

事务处理还是分析？

事务处理只是意味着允许客户端进行低延迟的读取和写入，而不是只能定期运行的批处理作业

在线事务处理（OLTP，OnLine Transaction Processing） ，交互式的访问模式，例如：应用程序通常使用索引通过某个键找少量记录。根据用户的输入来插入或更新记录。

在线分析处理（OLAP, OnLine Analytic Processing） ，常，分析查询需要扫描大量记录，每个记录只读取几列，并计算汇总统计信息（如计数、总和或平均值），而不是将原始数据返回给用户。

• 一月份每个商店的总收入是多少？
• 最近的推广活动中多卖了多少香蕉？

比较

属性	OLTP	OLAP
主要读取模式	查询少量记录，按键读取	在大批量数据上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL）或者事件流
主要用户	终端用户，通过WEB应用	内部数据分析师，用于决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推理的历史事件
数据集尺寸	GB~TB	TB~PB

逐渐转向在单独的数据库上运行分析——数据仓库（data warehouse）

数据仓库

分析查询通常开销巨大，如果在OLTP上运行会影响执行事务的性能

数据仓库可以针对类的访问模式进行优化

数据仓库包含公司各种OLTP系统中所有的只读数据副本，从OLTP数据库中提取数据，导入 （ETL，抽取 转换 加载） 数据仓库中

表面上，一个数据仓库和一个关系型OLTP数据库看起来很相似，因为它们都有一个SQL查询接口，然后系统内部针对非常不同的查询模式进行了优化

分析的模式

在分析性业务中，数据模型的多样性少得多，许多数据仓库都以相当公式化的方式使用，被称为星型模式（也称为维度建模）

星型模式的名字来源于这样一个事实，即当我们对表之间的关系进行可视化时，事实表在中间，被维度表包围；与这些表的连接就像星星的光芒

这个模版的变体被称为雪花模式，其中维度被进一步分解为子维度。雪花模式比星型模式更规范化，但是星型模式通常是首选，因为分析师使用它更简单

在典型的数据仓库中，表格通常非常宽：事实表通常有100列以上，有时甚至有数百列。维度表也可以非常宽，因为它们包括了所有可能与分析相关的元数据

列式存储

事实表通常有万亿行和数PB的数据，如何高效的存储事实表示一个具有挑战性的问题

尽管事实表通常超过100列，但典型的数据仓库查询一次只会访问其中4个或5个列，SELECT *的查询很少用于分析

在大多数OLTP数据库中，存储都是以面向行的方式进行布局的：表格的一行中的所有值都相邻存储。如果采用面向行的方式来对OLAP进行布局，查询时需要将所有行从硬盘加载到内存中再解析它们，过滤掉那些不符合要求的属性，这可能需要很长时间

列式存储：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起，如果每个列式存储在一个单独的文件中，查询时只需要读取和解析查询中使用的那些列

• 列式存储布局依赖于每个列文件包含相同顺序的行，因此如果你需要重新组装完整的行，你可以从每个单独的列文件中获取特定行，并将他们放在一起形成表的特定行

列压缩

列储存通常很适合压缩

在数据仓库中特别有效的一种技术是位图编码

通常情况下，一列中的不同值的数量与行数相比要小得多，将一个有n个不同值的列转换为n个独立的位图，每个不同值对应一个位图，每行对应一个比特定，如果该行是该值则该位位1，否则为0

如果n非常大，大部分位图中将会有很多的零（稀疏的），可以进行游程编码（run-length encoding），如上图所示

例1：

WHERE product_sk IN（30，68，69）

只需要加载 product_sk = 30、product_sk = 68 和 product_sk = 69 这三个位图，并计算三个位图的按位或（OR）就可以有效的完成，结果中为1的行即为满足条件的查询结果

例2：

WHERE product_sk = 31 AND store_sk = 3

加载 product_sk = 31 和 store_sk = 3 的位图，并计算按位与（AND）。这是因为列按照相同的顺序包含行，因此一列的位图中的第 k 位和另一列的位图中的第 k 位对应相同的行

区分列族和列式

• 列族可能是面向行的，例如Bigtable

内存带宽和矢量化处理

数据仓库查询瓶颈

• 从硬盘获取数据到内存的贷款
• 如果有效利用内存到CPU缓存的带宽，以及在现代CPU上使用单指令多数据（SIMD）指令来加速运算

矢量化处理：查询引擎可以将一整块压缩好的列数据放进 CPU 的 L1 缓存中，然后在紧密的循环（即没有函数调用）中遍历。相比于每条记录的处理都需要大量函数调用和条件判断的代码，CPU 执行这样一个循环要快得多。列压缩允许列中的更多行被同时放进容量有限的 L1 缓存。前面描述的按位 “与” 和 “或” 运算符可以被设计为直接在这样的压缩列数据块上操作。这种技术被称为矢量化处理（vectorized processing）

列式存储中的排序顺序

查询以最常用来作为范围目标的列来进行排序，可以少扫描很多行

数据的排序需要对一整行进行统一操作即使它们的存储方式是按列的。因为对每列分别执行排序是没有意义的，因为这样就没法知道不同列中的哪些项属于同一行

排序的另一个好处是它可以帮助压缩列。如果主排序没有太多个不同的值，那么在排序之后，将会得到一个相同的值连续重复多次的序列。一个简单的游程编码可以将该列压缩到几KB

第一个排序键的压缩效果最强。第二个和第三个排序键会更混乱，因此长的连续重复值会更少，对后面列做排序的效果没有对前几列做好

几种不同的排序顺序

因为数据需要做备份，因此可以用不同的方式来存储冗余数据，以便在处理查询时，调用最适合查询模式的版本

写入列式存储

列式存储，压缩和排序都有助于更快进行读取的查询，然而使得写入更加困难，如果你想在排序表中间加入一行，你可能不得不重写所有的列文件

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

查询操作需要检查硬盘上的列数据和内存中的最近写入，并将两者的结果合并起来。但是查询优化器对用户隐藏了这个细节

聚合

物化聚合（Materialized Aggregates）：将一些查询使用最频繁的计数或总和缓存起来

物化视图（Materialized View）：类似于视图，但是物化视图是查询结果的实际副本，会被写入硬盘，而虚拟视图只是编写查询的一个捷径。

• 从虚拟视图读取时，SQL引擎会将其展开到视图的底层查询中，然后再处理展开的查询
• 当底层数据发生变化时，物化视图需要更新，因为它是数据的非规范化副本。数据库可以自动完成该操作，但是这样的更新使得写入成本更高，所以OLTP数据库中不经常使用物化视图
• 数据仓库中读取更为繁重，物化视图更有意义

物化视图的常见特例称为数据立方或OLAP立方，它是按不同维度分组的聚合网格

如图：一个轴线上是日期，另一个轴线上是产品，每个单元格包含具有该日期-产品组合所有事实属性的聚合

一搬来说，事实往往有两个以上的维度。要想象一个五维超立方体是什么样子是很困难的，但是原理是一样的

• 物化数据立方体的优点是可以让某些查询变得非常快，因为它们已经被有效地预先计算了

• 数据立方的缺点是不具有查询原始数据的灵活性。例如，没有办法计算有多少比例的销售来自成本超过 100 美元的项目，因为价格不是其中的一个维度。因此，多数数据仓库视图保留尽可能多的原始数据，并将聚合数据仅用作某些查询的性能提升手段

总结

事务处理（OLTP） ：通常面向最终用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序在每个查询中通常只访问少量的记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。硬盘查找时间往往是这里的瓶颈。

在线分析（OLAP） ：数据仓库和类似的分析系统会少见一些，因为它们主要由业务分析人员使用，而不是最终用户。它们的查询量要比 OLTP 系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。硬盘带宽（而不是查找时间）往往是瓶颈，列式存储是针对这种工作负载的日益流行的解决方案。

OLTP两派主流的存储引擎：

• 日志结构学派：只允许追加到文件和删除过时的文件，但不会更新已经写入的文件。Bitcask、SSTables、LSM 树、LevelDB、Cassandra、HBase、Lucene 等都属于这个类别。
• 就地更新学派：将硬盘视为一组可以覆写的固定大小的页面。 B 树是这种理念的典范，用在所有主要的关系数据库和许多非关系型数据库中。

日志结构的存储引擎是相对较新的技术，通过系统性地将随机访问写入转换为硬盘上的顺序写入，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高的写入吞吐量