存储与索引

date

Oct 24, 2021

slug

DDIA-chapter3

status

Published

驱动数据库的数据结构

最简单的数据库

#!/bin/bash

db_set () {

echo "$1,$2" >> database

}

db_get () {

grep "^$1," database | sed -e "s/^$1,//" | tail -n 1

}

使用的时候

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'

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

$ db_get 42

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

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'

$ db_get 42{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database

123456,{"name":"London","attractions":["Big Ben","London Eye"]}

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

42,{"name":"San Francisco","attractions":["Exploratorium"]}

底层的存储：一个文本文件，每行包含一条逗号分隔的键值对，每次调用set函数就会追加记录，旧的记录不会被覆盖，所以查找最新值时候，需要找文件中键最后出现的位置。

优点：在极其简单的场景有很好的性能，因为在文件尾部追加写入很高效。

缺点：当数据库中有大量记录时，查找性能会很差，因为要从头到尾扫描。查找的开销是O(n)。

所以我们需要索引。

索引是附加结构，只影响查询性能，维护额外的结构会产生开销，特别在写入时，因为追加是最简单的写入操作。任何类型的索引通常都会减慢写入速度，因为每次写入数据都需要更新索引。

所以这里是一个trade off，数据库不会默认索引所有内容，需要DBA通过查询模式来手动选择索引，从而达到最大收益又不会引入超出必要的开销。

哈希索引

之前在各种编程语言中已经接触过哈希映射。既然我们已经有内存中数据结构hashmap，为什么不使用它来索引在磁盘上的数据呢？

假设我们的数据存储只是一个追加写入的文件，最简单的想法就是在内存中保存一个hashmap，每个键值映射到数据文件中的字节偏移量。（所有键必须能放入到可用内存中）

像这种方式适合每个键经常更新的情况。例如key可能是视频的url，value是它播放的次数（每次有人点击播放按钮时递增）。这种工作负载中，有很多写操作，但是没有太多不同的键，也就是说每个键都有很多写操作，并且将所有键保存在内存中是可行的。

追加写入文件如何避免用完磁盘空间呢？

将日志分为特定大小的段，当日志增长到特定尺寸时关闭当前段文件，开始写入一个新的段文件，然后对这些段进行压缩（compaction）。压缩是在日志中丢弃重复的键，保留键的最近更新。

可以同时进行压缩和分段合并，在进行过程中我们可以依旧用旧的段来正常提供读写操作。合并完成后，我们开始使用新的合并段然后可以删除掉旧的段文件。

真正投入实际应用时需要面临的一些问题：

文件格式，使用二进制格式会更快更简单（需要以字节单位对字符串进行编码）

删除记录，需要在文件中添加一个删除记录，在合并时放弃删除键的任何以前的值

崩溃恢复，如果数据库重新启动，内存散列映射会丢失，原则上可以重新从头到尾读取整个段文件然后进行恢复，如果段文件很大就不太好，Bitcask通过存储加速恢复磁盘上每个段的哈希映射的快照，可以更快地加载到内存中。

部分写入记录，数据库随时可能崩溃，包括记录附加到日志中途。Bitcask文件包含校验和，可以检测日志中的损坏部分。

并发控制，由于写是append模式，所以一般只有一个写入器线程，数据文件段是追加且不可变的所以可以被多个线程同时读取。为什么要用append追加而不是像文件一样覆盖呢？

- 追加和分段合并是顺序写入，比随机写入块，尤其是在磁盘上

- 如果段文件是附加或不可变的，并发和崩溃恢复就会很简单，不必担心覆盖值时发生崩溃从而出现既有新值又有旧值。

- 合并旧段可以避免数据文件随着时间推移而分散的问题

哈希表的局限性：

- 散列表必须能全部放进内存，原则上其实可以在磁盘上保留一个hashmap但是磁盘hashmap由于有很多随机访问I/O所以表现不好。

- 范围查询效率不高。

SSTables和LSM树

上述日志文件键值对的排序只和写入顺序有关，日志中稍后的值优先于较早的值，除此之外文件中的键值对的顺序并不重要。

我们做一个小小的变动：要求键值对按照key排序。

我们称这个格式为排序字符串表(Sorted String Table)，简称SSTable。我们要求每个键只在合并的段文件中出现一次。

SST的优势：

合并段简单高效，即使文件大于可用内存。过程就像归并排序中的归并。（如果几个输入段出现了相同的键就只保留最新的）

为了在文件中找到一个特定的key不需要保存所有键的索引，可以知道某个key如果存在就一定在key1和key2之间（其中key1<key<key2）。如果没找到就证明没有这个key。但是仍然需要一些索引告诉某些键的偏移量，不过可以很稀疏了。

然后就可以将记录分组到块中，对块进行压缩，稀疏索引指向块的开始处。

磁盘上有序结构有B树之类的，内存中的有序结构有比如红黑树和AVL树，这些数据结构可以任意顺序插入键并且按排序顺序读取他们。

此时我们的存储引擎工作流程：

写入时，将其添加到内存中的平衡树数据结构，有时称为内存表(memtable)

当内存表大于阈值，将其作为SST写入磁盘（因为已经在内存中排序了所以高效写入）当SST被写入磁盘时，数据库中新的数据写入可以写入到一个新的内存表实例

读取请求时先尝试在内存表中找到关键字，然后在最近的磁盘段，或者更久的磁盘段去找。

后台运行合并压缩过程的同时丢弃或覆盖旧的值

这个方案很好，只是会遇到一个问题，当系统崩溃时，最近内存表的写入会丢失，所以我们要在磁盘上保存一个append的日志用来恢复memtable，当memtable被成功写入sst时日志就可以丢弃了。

Log structure merge tree 日志结构合并树(LSM树)

LSMTree的缺点：

当查找数据库中不存在的key时，LSM树算法可能会很慢。（因为必须从Memtable一直找到最老的SST才能确定键不存在）为了优化这个访问，存储引擎通常用布隆过滤器

压缩合并的不同策略：

leveled compaction:关键范围被拆分成更小的SST，旧的数据被移动到单独的水平，使得压缩能都递增进行，减少磁盘空间

size-tiered compaction:新的和更小的SST被合并到更老的和更大的SST

有关LSM这里两种策略的对比可以看An In-depth Discussion on the LSM Compaction Mechanism这篇博客进行进一步了解。

LSMTree的优点：

即使数据集比可用内存大仍然能够继续工作

由于数据集按照排序存储所以可以高效执行范围查询

因为磁盘写入是连续的，所以LSMTree支持非常高的写入吞吐量

有关LSMTree中的KV分离存储内容可以看迟先生的这篇文章LSM 存储引擎中 KV 分离的实现

B树

B树将数据库分解成固定大小的块或者页面，一次只读取或写入一个页面。设计更接近底层硬件，因为磁盘也被安排在固定大小的块中。

每个页面用地址来标识，允许一个页面引用另一个页面（类似指针）。

有关B树的查找，添加，删除，本科数据库课程已经讲得很详细了，比如添加的时候如果页面中没有足够空间就分裂半满页面，删除的时候向兄弟借，(hhh如果想要回顾一下可以翻阅邹老师的PPT)

具有n个键的B树总是有O(logn)的深度。大多数数据库可以放入一个三到四层的B树（分支因子为500的4KB页面的四级树可以存储多达256TB）

B树可靠性：

为了防止比如页面分裂合并时出现崩溃，会导致一个损坏的索引（可能会有一个孤儿页面不是任何父项的子项），B树通常会有额外的数据结构，预写式日志（WAL，write-ahead-log）当数据库崩溃后用这个恢复一致性。

多线程访问，需要锁来保护，但是log-structure的方法在并发控制这里更易于实现，因为后台所有合并不会干扰传入的查询。

B树优化：

用写时复制，而不是覆盖页面并且用WAL进行崩溃恢复。修改的页面被写入不同的位置，树中父页面的新版本被创建指向新的位置。

不存储整个键，而是可以缩小键的大小。

B树尝试布局树，让叶子页面顺序出现在磁盘上。相比之下LSM树在合并时更容易使得顺序键在磁盘上彼此靠近。

树中加入额外的指针，每个叶子有对两个兄弟的引用，这样可以直接扫描

分形树借用日志结构的思想来减少磁盘寻道。

在数据库的生命周期中写入数据库导致对磁盘的多次写入——被称为写放大（write amplification）

其他索引

二级索引，通常对于有效执行连接至关重要。

可以在堆文件中存储行的元数据，每个索引引用到堆文件的一个位置。实际的数据保存在一个地方。在不更改键的情况下更新值，堆文件十分高效，只要新value不大于旧value，就可以覆盖记录，如果新value大，可能需要移到堆文件中有足够空间的位置，这猴子那个情况下所有索引都要更新指向新位置，或者在旧堆位置留下一个转发指针。

聚簇索引：在索引里存放行数据

非聚簇索引：仅在索引中存储对数据的引用

包含列的索引/覆盖索引：其存储表的一部分在索引内。

聚簇索引和覆盖索引可以加快读取速度，但是需要额外的存储空间，增加写入开销，需要额外的事务保证。

多列索引：

连接索引（concatenated index）它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）。比如按照字典序排序的花名册，可以很快查找相同姓氏的人们，或者名字中前几个字相同的人们，但是无法查询最后一个字相同的人们。

多维索引（multi-dimensional index）B树和LSM树不支持，可以利用空间填充曲线把二维转换成单个数字再用B树或者直接用R树

全文搜索和模糊索引（这些应该是信息检索里面的内容，比如编文档分类辑距离什么的）

在内存中存储一切

RAM变得便宜，数据集不那么大，且可以分布在多个机器，内存数据库发展起来了。

某些内存中的键值存储仅用于缓存，可以接受断电丢失数据，有一些需要达成持久性的，可以用电池供电的RAM将更改日志写入磁盘或者将定时快照写入磁盘来实现。

内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实（即使是基于磁盘的数据库也可能不需要读磁盘，因为操作系统会在内存中进行缓存），更快的真正原因是省去了将内存数据结构编码为磁盘数据结构的开销。

Redis由于将所有数据保存在内存中，没所以为各种数据结构（优先级队列和集合）提供了类似数据库的接口，实现起来方便。

内存数据库也可以支持比内存更大的数据集，比如可以用反缓存(anti-caching)方法将最近最少使用的数据从内存移到磁盘，需要访问的时候再重新加载，有点像OS里面的虚拟内存和交换空间吗，但是数据库可以更有效管理内存，因为可以粒度很小，而不一定是面向页面的。

事务处理还是分析？

交互式的应用程序的访问模式称为在线事务处理（OLTP, OnLine Transaction Processin）。查询通常由业务分析师编写，并提供给帮助公司管理层做出更好决策（商业智能）的报告。为了区分这种使用数据库的事务处理模式，它被称为在线分析处理（OLAP, OnLine Analytice Processing）。

公司在单独的数据库上进行分析，这个单独的数据库称为数据仓库（data warehouse）

数据仓库

星型和雪花型：分析的模式

星型模型：

模型中心是一个事实表，每一行代表在特定时间发生的时间，然后一些列是属性

事实表中其他列是对其他表（维度表）的外键引用，维度代表了时间发生的who,where,what,when,why,how。

其中比如尺寸可以进一步分为子尺寸，品牌和产品类型可能有单独的表格，dim表中每一行可能又能将某些列作为外键引用，而不是字符串，这个时候就变成了星型模型。

列存储

事实表中的列数很多，经常超过100列，我们分析查询可能只用到部分列，但是访问大量的行需要将行的全部列都加载，解析他们然后过滤掉不符合要求的条件，很慢很不划算。

列存储的思想很简单，将来自每一列的所有值存储在一起放在单独的文件，查询只需读取和解析查询中使用的那些列。

面向列的存储还很适合压缩来减少对磁盘吞吐量的需求。

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

比如查询

WHERE product_sk IN（30，68，69）

只需要加载product_sk=30，68，69三个位图并计算位图按位或

查询

WHERE product_sk = 31 AND store_sk = 3

只需加载product_sk = 31 和 store_sk = 3 的位图并按位与即可

一列中不同值的数量与行数相比较小，加入有n个不同值的列，可以转化成n个独立的位图，每个不同值的一个位图，每行一位，如果该行有该值，则该位为1，否则为0。

如果n很小，则这些位图可以每行存储一位。如果n很大，位图中有很多零，位图可以另外进行游程编码(Run-length encoding)，可以使列的编码十分紧凑。

内存带宽和向量处理

对于数据仓库查询来说，巨大的瓶颈是从磁盘获取数据到内存的带宽。还有主存储器到CPU缓存中的带宽，避免CPU指令处理流水线中的分支错误预测和泡沫。

面向列的存储布局也可以有效利用CPU周期。例如查询引擎可以将大量压缩的列数据存放在CPU的L1缓存中，然后在紧密循环中循环（没有函数调用），这样会快很多，而且位图的模式里面的按位与和按位或可以直接运行，这种技术称为矢量化处理。

列存储中的排序顺序

每个列单独排序是没有意义的，因为那样就不知道列中的哪些项属于同一行。我们重建一行必须要知道一列中的k行和另一列中的k行属于同一行。

所以要对一整行进行排序。而且还可以有多个排序关键字，可以加快查询速度，同时排序后列存储中相同的值会连续重复多次，有利于压缩。

第一个排序键的压缩效果最强，第二个和第三个排序键就混乱了，不会有长时间的重复值。

写入列存储

利用B树原地更新对于压缩的列是不可能的，因为想要在排序表中插入一行，就不得不重写所有列文件。

更好的解决方案：LSM树，内存中Memtable是面向行还是列不重要，积累了足够多的写入数据时，将与磁盘上的列文件进行合并，并批量写入新文件。

查询需要检查磁盘上的列数据和最近在内存中的写入，并将两者结合。查询优化器隐藏了用户这个区别，从分析师角度看，通过插入更新删除操作进行修改的数据会立即反映在后续的查询中。

聚合：数据立方体和物化视图

由于数据仓库查询总是执行聚集函数，所以可以缓存最频繁的计数。

创建这种缓存的一种方式是物化视图，物化视图是查询结果的实际副本，当底层数据发生变化时物化视图需要更新，这样的更新成本很高。

物化视图的特例称为数据立方体或者OLAP立方，是按照不同维度的聚合网络。

上面的例子就是对一个轴和另一轴上的产品都进行求和并且存在total里面。

优点是查询总和时会很快，因为已经预先计算了，还有比如想知道总销售额不用再扫描数万行了。

缺点是不具有灵活性，所以数据仓库尽可能保留原始数据，并且将聚合数据仅仅用在某些特定查询上。

小结

OLTP面向用户

OLAP面向数据分析师

OLAP方面有两大主流学派的存储引擎

log-structure：LSM树什么的，可以实现较高的写入吞吐量

update-in-place: B tree