2024-07-07发表2024-07-20更新学习笔记16 分钟读完 (大约2443个字)

《Designing Data Intensive Applications》读书笔记 - 存储和索引

首先讨论传统关系性数据库使用的存储引擎，分为两类：日志结构存储引擎和页面结构存储引擎。

数据结构

Hash 索引

首先从最简单的 key-value 数据库开始，只有两个函数的脚本:

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

数据写入以追加的方式添加到文件结尾，数据读取从文件结尾开始匹配目标 key，修改数据也是以追加一条新记录的形式，删除数据需要一个特殊的 tombstone 标志。
数据的检索存在问题，每次都需要扫描所有数据，时间复杂度为 O(n)。很容易想到，在内存中保存一份索引，记录 key 对应的文件记录偏移。

现在的一个问题是如何避免磁盘写满，一个方案是将记录文件进行分片，当文件达到一定大小时就开始写入新文件。在写入新的分片文件时，旧的分片文件可以进行压缩，合并。
查找过程，需要先查找新分片的索引，再查找次新分片的索引。

这个实现看上去太过简单，实际上非常可行。数据的写入非常高效，因为磁盘顺序写没有寻道时间, Bitcask 就是这种实现方式。适用于每个值频繁更新的情况，比如视频播放计数。

一些实现细节

文件格式 CSV 并不是最合适的格式。更快更简单的二进制格式：首先编码字符串长度，然后是字符串本身。
删除记录 追加一个特殊的删除记录，标记为删除（tombstone）合并分片的时候，丢弃给定 key tombstone 之前的记录。
故障恢复 数据库重启时，内存中的哈希表会丢失，通过文件重新建立索引太过耗时，Bitcask 存储哈希表的快照，直接从快照中恢复。
部分写记录 写入过程中崩溃，校验和
并发控制 一般实现是只有一个写线程，读线程可以并发。文件分片不会改变，所以支持多线程并发读

优点
只追加的日志看起来浪费，好处是：

追加和分片合并是顺序写，磁盘顺序写比随机写快很多。
并发和故障恢复更简单，不需要考虑并发写入的问题。
合并旧分片可以避免文件碎片化，提高读取性能。

局限

索引需要能够整个存入内存，理论上可以放在上磁盘上，操作系统可以交换磁盘，实际上效率也非常低（随机访问时交换频率很高）
范围查找效率依然很低。

SSTable 和 LSM-Tree

接下来做些小的改变，保持键值对有序，按 key 排序，我们将这个格式称为 SSTable（Sorted String Table）。
咋看上去这可能会破坏我们的顺序写，不过可以带来几个好处：

文件进行分片，合并压缩过程非常高效，归并排序的合并过程，时间复杂度是 O(n)
哈希文件不需要保持所有的 key，现在可以维护一个稀疏索引。
范围查询时，整块读取，可以减少磁盘带宽的使用

初始有序文件的创建
在写入文件之前，可以将记录保存在内存中，使用红黑树维护顺序，超过一定大小之后写入文件。为了应对故障，同时需要维护一个 WAL 日志文件

未命中查询
LSM-tree 在查找不存在的 key 时性能比较慢，一个办法是 Bloom Filter，这样可以快速判断 key 是否存在。

B-Trees

B-Tree 可以说是广泛使用的一种索引结构，和 LSM-Tree 唯一的相同之处就是保持记录在文件中有序。最突出的不同是，每个 key 在文件中只有一个记录，修改是直接操作磁盘。
管理文件是以页或块（对应操作系统中的页）为单元，将索引结构以树的形式组织。

优化

不去覆写页和维护 WAL，而是写入一个新的页，然后更新父节点的引用
不存储整个 key, 只保存缩写，只需要用来确定 key 的范围即可，这样子一个页内可以存放更多的key, 整个树的高度更低
一般来说，页可以在磁盘的任意位置，很多 B 树的实现让叶子节点在磁盘上连续。但是，随着树的增长，这个顺序很难维持
额外的指针，叶子节点之间的指针，可以加速范围查询
B 树变种 fractal trees 借鉴了 LSM-tree 的思想减少磁盘寻道

比较
根据经验，LSM-Tree 写入速度更快，B-Tree 读取速度更快

LSM-Tree 优点：

顺序写磁盘，磁盘吞吐量高
更好的压缩，避免磁盘碎片化

LSM-Tree 缺点：

压缩操作可能会影响正在进行的读和写，磁盘带宽必须和压缩写共享
不合理的配置，如果压缩合并跟不上写入的速度，可能导致磁盘耗尽

B-Tree 优点：

一个 key 只在一个地方，容易实现并发控制

B-Tree 缺点：

块大小固定，磁盘碎片化
至少写入两次磁盘，写放大比 LSM-Tree 显著

其它索引结构

聚簇索引存储值和索引在一起，不需要再次查找 MySQL 主键索引就是聚簇索引，二级索引引用主键
多列索引，比如按经纬度查询
全文搜索，模糊索引
所有内容在内存

事务处理或分析

数据库除了用于 OLTP 也越来越多的用于 OLAP 一般来说，数据分析需要扫描很多记录，同时只关心少数几列，往往会进行聚合计算。

数据仓库

单独的数据库运行分析查询，不会影响 OLTP 操作。数据是从 OLTP 数据提取，转化为分析友好的模式，清洗加载到数据仓库（ETL）。使用单独的数据库最大的好处是可以为分析访问模式优化数据仓库。

区别
数据仓库的数据模型通常是关系性，因为 SQL 非常适于分析查询。表面上看数据仓库和关系性 OLTP 数据库比较相似，但是系统内部非常不同，因为各自为不同的查询模式优化。

星形模式
不像事务处理会有多样的数据模型，分析处理模型较为一致，star schema.
模式中心称为 fact-table 每行通常是一个单独的事件，比如网页浏览或者点击，包含其它纬度的数据说明何人何事何时何地以及为何。星形模式是因为 fact-table 在中心和其它纬度的表相关联，形状像星形。

列式存储

通常 fact-table 非常大量的数据，经常超过 100 多列，查询时一般只会涉及到 4-5 列。为了支持高效查询，通常选择列式存储。

压缩列
每列的数据经常重复，可以非常高效的进行压缩，基于列中数据，可以选择不同的压缩方式。一种相当有效方式是：位图编码
例如，销售记录可能有上亿行，而商品只有 n 种，我们就可以选择将其转换为 n 万个不同的位图。如果 n 很小 (200) , 每行可以用 1 个位表示，如果 n 很大（比较稀疏），可以使用游程编码方法（run-length encoded）
位图索引非常适合常见的查询，比如下面的查询只需要进行对应的位操作即可。
WHERE product_sk = 31 AND store_sk = 3:
WHERE product_sk IN (30, 68, 69):

列式存储可以更高效的利用 CPU 周期，列压缩允许更多的行放入 CPU 一级缓存。

排序
不同的查询受益于不同的排序，存储冗余数据以不同的排序方式

写入
就地更新的方式对于压缩的列不大可能，不过可以借鉴 LSM-Tree 的思路，所有的写先存入内存，等到足够多时再写入磁盘。查询时合并两个结果。

物化视图（materialized view ）
多个查询使用相同的聚合，直接缓存起来更为高效。数据变更时，视图需要重新更新（OLAP 很少更新）
data cubes 比如，产生销售数据，聚合数据按时间和产品，之后方便查询。

总结

数据存储和索引是数据库的核心，不同的查询模式需要不同的存储和索引方式。OLTP 和 OLAP 有不同的查询模式，需要不同的存储方式。

#DataBase