Kyle's Notebook

《DDIA》阅读笔记(三):数据存储与检索

Word count: 6.6kReading time: 22 min
2020/12/13

《DDIA》阅读笔记(三):数据存储与检索

本章结构如下:

  • 数据存储与检索
    • 数据结构
      • 哈希索引
        • 追加写入
        • 偏移量
        • 分段压缩
        • 文件格式
        • 删除记录
        • 崩溃恢复
        • 部分写入
        • 并发控制
        • 局限性
          • 哈希表必须全部放入内存
          • 区间访问效率不高
      • LSM-Tree
        • 构建和维护 SSTables
          • 处理写请求
          • 处理读请求
          • 合并和压缩
          • 崩溃恢复
        • LSM 存储引擎
        • 性能优化
          • 布隆过滤器
          • 压缩合并策略
        • 优势与劣势
          • 写放大
          • 写入较快
          • 读取较慢
          • 更好的压缩
          • 写入带宽开销
      • B-trees
        • 分页设计
          • 查找
          • 更新
          • 插入
        • 可靠性
          • 预写日志
          • 并发控制
        • 性能优化
          • 写时复制
          • 键略缩信息
          • 相邻布局
          • 添加额外指针
          • 分形树
        • 优势与劣势
          • 读取较快
          • 写入较慢
          • 并发控制
      • 其他索引结构
        • 在索引中存储值
          • 堆文件
          • 聚簇索引
        • 多列索引
          • 级联索引、多维索引
          • 全文搜索和模糊索引
      • 在内存中保存所有内容
        • 应用实例
        • 反缓存架构
    • 事务处理与分析处理
      • 事务处理系统(OLTP)
        • 日志结构
        • 原地更新
      • 分析系统(OLAP)
      • 数据仓库
      • 星型与雪花型分析模式
    • 列式存储
      • 列压缩
        • 列与列簇
        • 矢量化处理
      • 排序操作
      • 写操作
      • 聚合:数据立方体与物化视图

数据结构

即额外的、用于辅助查找的元数据。每次写入数据都需要同步更新,因此会降低写速度,需要在 加速查询避免降低写入速度 之间权衡。

对于 OLTP 系统,主流的存储引擎:

  • 日志结构:只允许追加式更新文件和删除过时文件,不修改己写入的文件。比如 BitCask、SSTables、LSM-tree、LevelDB、Cassandra、HBase、Lucene 等。关键思想是系统地将随机写入转为顺序写入,由于硬盘驱动器和 SSD 的性能特性,可以实现更高的写入吞吐量。

  • 原地更新:以 B-Tree 为代表,将磁盘视为可覆盖的一组固定大小的页,用于主要的关系数据库和大量的非关系数据库。

Hash

Riak 的默认存储引擎 Bitcask。

基本操作

写入:通常以单线程按顺序追加到日志中。

  • 追加和分段合并是顺序写,通常比随机写入快(特别是机械磁盘)。

  • 段文件追加或不可变,并发控制和崩溃恢复更简单。

  • 合并旧段可避免数据文件碎片化。

读取:数据段是追加且不可变,可被多线程读取,但区间访问效率较低。

删除:在文件中为键值追加墓碑标记,在合并段时发现标记则丢弃该键所有值。

偏移量

假设采用追加式文件存储数据,索引策略为保存内存中的哈希表:

  • 键映射到文件中特定的字节偏移量,以便找到值的位置。一次磁盘寻址即可将值加载到内存,再结合缓存则无需磁盘 I/O。

  • 在文件中追加新键值对时,要更新 hash map 反映刚写入的数据偏移量(插入新的或更新已有键的值)。

适用于键值频繁更新、但没有太多不同的 key(内存有限)的场景。

压缩合并

格式:文件以二进制格式写入,更快更简单;以字节为单位记录字符串长度,后续跟上无需转义的原始字符串。

压缩:为节省磁盘空间,把日志分解成等大的段,文件达到一定大小即关闭、开启新段。再可对段进行压缩,丢弃日志中重复的键,只保留最近更新。

合并:后台线程在压缩时将多个段合并写入新文件,此时用旧段文件处理读写请求。合并完成后将读取请求切到新段上再删除旧段。

崩溃恢复

由于数据库重启内存 hash map 会丢失,Bitcask 将段 hash map 快照存储在磁盘,更快地加载到内存中,而无需从头到尾扫描整个文件、重新记录偏移量。以此加快恢复速度,再通过校验值发现损坏部分并丢弃。

LSM-Tree

按顺序追加以提高吞吐量、基于合并和压缩排序文件的存储引擎。

SSTable:键值对按键排序为字符串表,通过压缩保证键在每个合并的段文件中只出现一次。

  • 合并段更简单高效:并发读取多个输入段文件,比较每个文件的第一个键,按顺序把最小的键取出到文件,即产生新的按键排序的合并段文件。当多个段包含相同的键时,保留最新段的值并丢弃旧段中的值。
  • 在文件中查找特定的键时,无需在内存中保存所有键的索引,只需要一个可稀疏的内存索引来记录键的偏移。

应用实例:

  • LevelDB 和 RocksDB,嵌入应用程序的键值存储引擎库。类似的存储引擎还被用于 Cassandra 和 HBase。

  • Elasticsearch 和 Solr 的全文索引存储引擎 Lucene。

SSTables

采用树结构维护索引:

  • 处理写:

    • 将数据添加到内存的平衡树(即内存表)中。

    • 通过树维护按键排序的键值对,当内存表大于某阈值(数 MB)则将其写入 SSTable 文件。

    • 在写磁盘同时可处理对新内存表的写入。

  • 处理读:先在内存表查找键值,然后在最新的磁盘段文件,再在次新的磁盘段文件,以此类推。

  • 合并和压缩:后台进程周期性执行段合并与压缩,并丢弃已被覆盖或删除的值。

  • 崩溃恢复:由于数据库崩溃时在内存表但尚未写入磁盘的数据会丢失。可在磁盘上保留日志,每次写入时追加到该日志(无需排序),用于崩溃后恢复内存表。每当将内存表写入 SSTable 时,日志即可丢弃。

性能优化:

  • 布隆过滤器:查找不存在的键可能很慢:先检查内存表,再回溯访问到最旧的段文件,将涉及多次磁盘读。引入布隆过滤器可快速判断集合中存在/不存在的键,节省磁盘 I/O。

  • 压缩合并策略:压缩和合并的顺序和时机。

  • 大小分级:连续将较新和较小的 SSTables 合并到较旧和较大的 SSTables(比如 HBase 和 Cassandra)。

  • 分层压缩:键的范围分裂成更小的 SSTables,旧数据被移动到单独的层级,可逐步压缩并节省磁盘空间(比如 Cassandra)。

B-Tree

B-tree 保留按键排序的键值对,可实现高效的键值查询和区间查询。

几乎所有关系数据库中的标准索引实现,许多非关系型数据库也经常使用。

分页设计

SSTable 和哈希索引将数据库分解为大小可变的段(数 MB或更大),而 B-tree:

  • 将数据库分解成固定大小的块或页(传统 4KB,有时更大)作为内部读写的最小单元,设计上更接近底层硬件,比如磁盘也是按固定大小的块排列。

  • 页面包含多个连续区间内的键和对子页的引用(可用地址标识,类似指针指向磁盘地址),相邻引用之间的键指示这些范围的边界,以某一页作为根,构成树形结构。

  • 页所包含的子页引用数量称为 分支因子,取决于存储页面引用和范围边界所需的空间总量(通常几百个)。

  • 树的维护算法要确保树保持平衡,具有 n 个键的树总是具有 O(logn) 的深度,大多数数据库可以适合 3~4 层的 B-tree,不需要遍历太深的层次即可找到所需的页。

查找操作:从根页开始遍历,由于每个孩子负责一个区间内的键、相邻孩子指示区间边界,沿着孩子及其进一步分解的子区间查找,最终到达包含单个键的页(叶子),该页包含每个内联键的值或包含可以找到值的页的引用。

B Tree

插入操作:要添加新键,则需要找到其范围包含新键的页,并将其添加到该页。如果页中没有足够的可用空间来容纳新键则将其分裂为两个半满的页,并且父页也需要更新以包含分裂之后的新的键范围。

B Tree 分裂

更新操作:搜索包含目标键的叶子页,更改该页的值并将页写回到磁盘(对该页的任何引用仍然有效)。

LSM-Tree 与 B-Tree 对比

LSM-Tree B-Tree
写入吞吐量 写放大较低,其顺序写入紧凑的 SSTable 文件,不必重写树中的多个页。而且顺序写比随机写快得多。 写入时需要写预写日志和树的页(可能还会分裂)。即使该页中只有几个字节更改,也必须承受写整个页的开销。
一些存储引擎甚至覆盖相同的页两次,以避免在故障时出现部分更新的页。
读取效率 较慢,必须在不同的压缩阶段检查多个数据结构。
且当段数量过多,读时扫描量大,读取效率更低。
快。
压缩支持 顺序写入且定期重写 SSTables 消除碎片,能更好地支持压缩,磁盘文件比 B-tree 小很多(尤其使用分层压缩时存储开销更小)。 面向页存储,当页被分裂或某行内容不适合现有页时,出现碎片会导致某些磁盘空间无法使用。
响应延迟 压缩有时会干扰读写。即使增量压缩不影响并发访问,磁盘并发资源有限,压缩容易导致读写等待、提高响应时间。 响应延迟更具确定性。
磁盘带宽 磁盘写入带宽有限,需要被初始写入(记录并刷写磁盘)和后台压缩线程共享。数据量越大、被挤占的磁盘带宽越多。
压缩需要根据写入吞吐量配置。如果压缩无法匹配写入速率,未合并段不断增加、直到磁盘空间不足(同时影响读)。
写入效率不受限制,需要额外的监控处理这种情况。
副本数量 可能在不同的段中具有相同键的多个副本。 每个键都唯一对应于索引中的某个位置。
事务隔离 不支持 通过键范围上的锁支持。
范围查询 效率较低 支持

写放大:在数据库内一次数据库写入请求导致的多次磁盘写的情况称为写放大。

对于固态硬盘而言。由于擦写覆盖次数有限,需要关注写放大指标。固态硬盘固件内部使用日志结构化算法,将随机写转换为底层存储芯片上的顺序写,存储引擎写入模式的影响不明显。但如果能以更紧凑的方式表示数据,即可在有限的 I/O 带宽中支持更多的读写请求。

其他索引结构

以上是键值索引(类似主键索引),用于标识关系模型的行(文档模型的文档、图模型的顶点),其他记录可通过主键引用。

二级索引(非聚簇索引,需二次查找)用于高效地进行联结操作,可以容易地基于键值索引来构建。在于可能有许多行(文档,顶点)具有相同键,可使用两种方式解决:

  • 使索引中的每个值成为匹配行标识符的列表(像全文索引中的 posting list)。

  • 追加行标识符使键变得唯一。

B-Tree 和 日志结构索引都可以用作二级索索引。

在索引中存储值

索引中的键是查询搜索的对象,而值则可以:实际行(文档,顶点)或对其他地方存储的行的引用。

  • 堆文件:对其他地方存储的行的引用(行的具体位置),不以特定的顺序存储,可以是追加或记录删除行,以便用新数据覆盖。

    • 当存在多个二级索引时可以避免复制数据:每个索引只引用堆文件中的位置信息,实际数据仍保存在一个位置。

    • 当更新值时只要新值字节数不大于旧值,就可以直接覆盖,否则可能需要移动数据以得到足够大的空间。

    • 所有索引都需要更新,以指向新的堆位置,或在旧堆位置保留一个间接指针。

  • 聚簇索引:从索引到堆文件的额外跳转在读取时有较大性能损失,因此可将索引行直接存储在索引中,被称为聚簇索引。聚簇索引 在索引中直接保存行数据,非聚簇索引 仅存储索引中数据的引用,一种折中设计称为 覆盖索引 或 包含列的索引,在索引中保存表的列值,可支持只通过索引即可响应的简单查询(被称索引覆盖了查询,可避免回表)。

多列索引

以上索引只将一个键映射到一个值,如果需要同时查询表的多个列,则需要多列索引。

常用于一次查询多列,比如地理空间数据的经度和纬度,要求同时满足在某个经度和纬度范围内的数据。

级联索引:通过将一列追加到另一列,将几个字段组合成一个键(索引的定义指定字段连接的顺序)。

1
2
3
4
SELECT * 
FROM restaurants
WHERE latitude > 51.4946 AND latitude < 51.5079
AND longitude > -0.1162 AND longitude < -0.1004;

多维索引:使用空格填充曲线将二维位置转换为单个数字,再使用常规的 B-tree 索引。

全文搜索和模糊索引

为了处理文档或查询中的拼写错误,搜索引擎(如 Lucene)可在某个编辑距离内搜索文本。

Lucene 对词典使用类似 SSTable 的结构,由内存索引告知查询要找到键需要排序文件中的哪个偏移量。

在 LevelDB 中内存中的索引是一些键的稀疏集合,Lucene 在内存中的索引是键字符序列的有限状态自动机(类似字典树),可以转换成 Levenshtein 自动机,支持在给定编辑距离中高效地搜索单词。

保存所有内容

以上数据结构都是为了适应磁盘限制,与内存相比磁盘更难以处理、容量更大、成本更低。要获得良好的读写性能需要精心地安排磁盘上的数据布局。

当数据集不太大,则可以完全保留在内存,或分布式的多台机器上。

  • 只要内存足够,基于磁盘的存储引擎也可以永远不从磁盘读取:操作系统将最近使用的磁盘块缓存在内存中。内存数据库可避免使用写磁盘的格式对内存数据结构编码的开销,效率更高。

  • 除了提升性能,内存数据库还提供了基于磁盘索引难以实现的数据模型(比如 Redis 的多种数据结构)。

应用实例

一些键值存储(如 Memcached)用于缓存,可容忍数据丢失。

如果需要实现持久性,可用特殊硬件将变更记录或快照写入磁盘,便于故障恢复(Redis 和 Couchbase 通过异步写入提供较弱的持久性,RAMCloud 则是对内存和磁盘上的数据使用日志结构),也便于通过外部工具来执行备份、检查和分析。

关系型内存数据库 VoltDB、MemSQL、Oracle TimesTen 移除了磁盘管理的开销以获得极大的性能提升。

反缓存架构

内存数据库架构可扩展,以支持远大于可用内存的数据集,不会导致以磁盘为中心架构的开销。

  • 当没有足够的内存时,将最近最少使用的数据写到磁盘,再次被访问时再将其加载到内存。

  • 与操作系统对虚拟内存和交换文件的操作类似,但数据库可以在记录级别(而不是整个内存页)的粒度工作,因而比操作系统更有效地管理内存。这种方法需要将索引放入内存(参考 Bitcask)。

事务处理与分析处理

数据系统分为两大类:

属性 事务处理系统(OLTP) 分析系统(OLAP)
读特征 基于键,每次查询返回少量的记录 对大量记录进行汇总
写特征 随机访问,低延迟写入用户的输入 事件流或批量导入(ETL)
使用场景 终端用户,通过网络应用程序 内部分析师,为决策提供支持
数据表征 最新的数据状态(当前时间点) 随着时间而变化的所有事件历史
数据规模 GB 到 TB TB 到 PB

事务处理系统(OLTP)

基于某种键查询记录,而存储引擎使用索引来查找所请求键的数据,磁盘寻道时间往往是瓶颈。

不建议在 OLTP 数据库上直接运行临时分析查询,需要扫描大量数据集,可能会损害并发执行事务的性能。

日志结构

以追加式更新文件和删除过时文件,不会修改己写入的文件。系统地将磁盘上随机访问写入转为顺序写入,由于硬盘驱动器和SSD的性能特性,可以实现更高的写入吞吐量。

BitCask 、SSTables、LSM-tree、LevelDB、Cassandra、HBase、Lucene 等属于此类。

原地更新

B-Tree 是最典型代表,将磁盘视为可覆盖的一组固定大小的页,用于所有主要的关系数据库,以及大量的非关系数据库。

分析系统(OLAP)

处理的查询请求数目远低于 OLTP 系统, 但每个查询通常要求非常苛刻,需要在短时间内扫描数百万条记录。磁盘带宽(非寻道时间)通常是瓶颈,而面向列的存储对于这种工作负载成为日益流行的解决方案。

数据仓库

存储 OLTP 系统的只读副本:对于 OLTP 数据库,从周期性数据转储或连续更新流中提取数据,转换为分析友好的模式、执行必要的清理,再加载到数据仓库中(ETL)。

OLTP 与数据仓库

关系型 OLTP 与数据仓库都具备 SQL 接口,但针对不同的查询模式各自进行优化、专注于支持事务处理或分析工作负载,一般不能同时支持两者。

星型与雪花型模式

参考:https://yipwinghong.github.io/2020/02/15/DataWarehouse_design-basic/

星型模式中心是事实表,每一行表示在特定时间发送的事件(如用户下单,或页面上的一次点击)。

  • 如果捕获小粒度、单独的事件,则对之后的分析具有最大灵活性,但表会非常庞大。

  • 事实表列为属性,可引用维度表的外键:通常表示事件的对象、事件本身、地点、时间、方法、原因。

雪花型模式是对星型模式的规范化,维度进一步细分为子空间,比如订单的商品的品牌和类别可以有单独的表格、而不是直接存储在商品表中。

在典型的数据仓库中,事实表、维度表(分析相关的元数据)通常非常宽。

列式存储

事实表一般非常大,适合用列式存储实现高效存储和查询。

  • 事实表可宽达过百列,而典型分析查询往往只访问其中几列,如使用面向行的方式存储(一行的所有值彼此相邻存储)则要把大量的数据加载到内存解析,再过滤出不符合条件的行。

  • 当查询需要在大量行中顺序扫描时,索引的关联性就会显著降低。最重要的是非常紧凑地编码数据、以尽量减少磁盘读取的数据量。面向列的存储将每列中的所有值存储在一起。如果每个列存储在一个单独的文件中,查询只需要读取和解析在该查询中使用的列。

列压缩

压缩数据可进一步降低对磁盘吞吐量的要求:同一列中重复的值可以压缩。取决于列中具体数据模式,可采用不同的压缩技术,比如位图编码:如列中不同值的数量小于行数,使用 n 个不同值的列,并将其转换为 n 个位图。位图对应每个不同的值,一个位对应一行(该行是列值是否为 x)。如果行具有该值则该位为 1 , 否则为 0。在访问时只需要加载位图、执行按为与/或操作即可。

位图编码压缩

列与列簇

Cassandra 和 HBase 都有列簇的概念,在列簇中将一行中的所有列与行主键一起保存,不使用列压缩。因此 Bigtable 模型仍然主要是面向行。

矢量化处理

对于需要扫描数百万行的数据仓库查询,将数据从磁盘加载到内存的带宽是一大瓶颈,还要关心如何高效地将内存带宽用于 CPU 缓存。

矢量化处理:除了减少从磁盘加载的数据量,面向列的存储布局也有利于高效利用 CPU 周期。查询引擎将一大块压缩列数据放入 CPU 的 L1 缓存中,以紧凑循环(没有函数调用)进行迭代。对于被处理的记录,CPU 能比基于很多函数调用和条件判断的代码更快地执行循环。列压缩使列中更多的行可加载到 L1 缓存。如先前描述的按位 AND 和 OR 的运算符,可被设计成直接对列压缩数据块的操作。

排序操作

在列存储中行的存储顺序并不太重要。可按插入顺序保存,插入新行时追加到列文件;或强制按某个顺序(像 SSTable)、将其用作索引机制。

  • 单独对列排序没有意义,无法知道列中的某一项属于哪一行(知道某列中的第 k 项和另一列的第 k 项一定属于同一行,可以重建一行)。

  • 即使数据是按列存储的,也需要排序整行。比如以时间范围查询,可设置时间字段为第一个排序键,优化器只扫描某段时间内的行,比扫描所有行快得多(当第一列排序出现相同值时,可以指定第二列继续进行排序)。

  • 排序可以 帮助进一步压缩列,如果主排序列上没有很多不同的值,在排序之后将出现一个很长的序列,其中相同的值在一行中重复多次。

  • 不同的查询可以在不同的排序方式中获益,因此可以 以不同方式排序存储多份冗余数据,在处理查询时选择最适合特定的排序版本(同时也提高可靠性)。

  • 面向列的存储具有多个排序顺序,类似在面向行的存储中具有多个二级索引。区别在于面向行的存储将每一行都保存在一个位置(堆文件和聚簇索引),而二级索引只包含指向匹配行的指针。对千列存储, 通常没有任何指向别处数据的指针, 只有包含值的列。

写操作

写入操作比较困难。

  • 不能使用的原地更新(B-Tree),如果在排序表的中间插入一行,可能不得不重写所有的列文件。

  • 可类似 LSM-Tree:首先写入内存, 将其添加到已排序的结构中,再准备写入磁盘(无关行存或列存)。累积足够的写入,内存数据将与磁盘上的列文件合并,批量写入新文件。

  • 执行查询时需检查磁盘上的列和内存中最近的写入,并结合这两者。

聚合:数据立方体与物化视图

物化聚合:数据仓库查询涉及的聚合函数(COUNT、SUM、AVG、MIN 等),可利用物化视图创建缓存:

  • 作为查询结果的实际副本,并被写到磁盘,而虚拟视图只是用于编写查询的快捷方式。从虚拟视图中读取时,SQL 引擎将其动态地扩展到视图的底层查询,然后处理扩展查询。

  • 当底层数据发生变化时, 物化视图也需要随之更新(影响写入性能,因此 OLTP 数据库不常使用)。

数据立方体:由不同维度分组的聚合网格,对于已被预先计算出来的查询非常快(只需要直接查看对应维度的总和, 而不需要扫描数百万行);但缺乏像查询原始数据那样的灵活性,数据仓库需保留尽可能多的原始数据,仅当数据立方体可对特定查询显著提升性能时,才会采用多维数据聚合。

数据立方体

CATALOG
  1. 1. 《DDIA》阅读笔记(三):数据存储与检索
    1. 1.1. 数据结构
      1. 1.1.1. Hash
        1. 1.1.1.1. 基本操作
        2. 1.1.1.2. 偏移量
        3. 1.1.1.3. 压缩合并
        4. 1.1.1.4. 崩溃恢复
      2. 1.1.2. LSM-Tree
        1. 1.1.2.1. SSTables
      3. 1.1.3. B-Tree
        1. 1.1.3.1. 分页设计
        2. 1.1.3.2. LSM-Tree 与 B-Tree 对比
      4. 1.1.4. 其他索引结构
        1. 1.1.4.1. 在索引中存储值
        2. 1.1.4.2. 多列索引
        3. 1.1.4.3. 全文搜索和模糊索引
      5. 1.1.5. 保存所有内容
        1. 1.1.5.1. 应用实例
        2. 1.1.5.2. 反缓存架构
    2. 1.2. 事务处理与分析处理
      1. 1.2.1. 事务处理系统(OLTP)
        1. 1.2.1.1. 日志结构
        2. 1.2.1.2. 原地更新
      2. 1.2.2. 分析系统(OLAP)
        1. 1.2.2.1. 数据仓库
        2. 1.2.2.2. 星型与雪花型模式
    3. 1.3. 列式存储
      1. 1.3.1. 列压缩
        1. 1.3.1.1. 列与列簇
        2. 1.3.1.2. 矢量化处理
      2. 1.3.2. 排序操作
      3. 1.3.3. 写操作
      4. 1.3.4. 聚合:数据立方体与物化视图