<未完成>数据库系统的数据存储方式

发表于 更新于 分类于 阅读次数：

存储管理器: 数据存储模型

上一篇博客提到了数据库管理系统本身的抽象层次, 其中就有 Disk Manager 和 Buffer Pool Manager 作为数据库的存储管理器。

提到”数据库的数据存储方式”时, (尽管有些早)一半涉及到三个层次的存储方式: 文件的存储方式、页面内部的布局、元组的内部布局. 其中为什么需要文件的存储方式与元组的内部布局较好理解, 而数据库中页面的概念将会在下面说明, 为什么数据库需要实现自己的页面.

文件存储方式: Heap File

您可能需要阅读 CSAPP3e第六章(存储器层次结构) | Amiriox’s Storage 来对计算机存储器的层次结构的意义有一定的认识.

简单来说, 由于不同存储设备的访问速度不同, 在冯诺依曼体系的计算机不可避免地数据传输中会拖慢更快速的存储设备的效率, 所以按照存取效率进行排序, 利用时间/空间局部性, 将更快的存储器作为次快的存储器的缓存, 最大化利用存储器的存取效率.

很显然, 数据库的数据必须是可持久化的, 也就是最终要存在文件系统上, 而 CPU 对磁盘的访问通常较慢(尽管有 DMA), 最主要的原因是某个公司曾推出的可持久化的快速主存没能发展起来(大雾) 所以我们需要将主存作为磁盘的缓存, 利用磁盘加载到内存中的页面, 主要的数据操作在主存中进行, 最后将修改后的(脏页)写回磁盘. 这些页面交由执行引擎使用, 而与 Disk Manager 交互, 提供这个页面交换功能本身的组件叫 Buffer Pool Manager (BPM)

具体来说, 数据库的一个文件分为若干个固定大小的连续空间, 称为页, 这个文件称之为 Heap File, 也就是一堆无序的页面的集合; 同时还会有一页称为页目录 (Page Directory), 记录某个页在哪个 Heap File 上的哪个偏移量(位置).

当执行引擎指明我需要页号为 \(\text{page_id}\) 的页时, BPM 负责从磁盘中先提取 Page Directory 所在页, 解析其中的布局, 获取到一些元信息: \(\text{page_id}\) 这一页存在哪个文件里, 偏移量是多少; 然后通过文件和便宜量找到对应页, 加载到内存(单纯的复制). 当然, BPM 还要负责标记脏页/驱逐页面/写回等任务. (当然, 实现上肯定会分为不同组件, 单一职责)

为什么重造轮子?

以上这些东西听起来像是操作系统虚拟内存的功能, 甚至也有对应功能的实现: sys_mmap 系统调用, 映射磁盘页到内存, 标记脏页, 写回磁盘, 甚至还有 COW, 看上去非常”最佳实践”. 事实上也的确有很多数据库完全采用 mmap 系统调用来实现数据的, 但实际上 mmap 会导致许多问题: * 首先, 数据库的事务必须是原子性的(设想一个修改余额的操作进行了一半会怎么样?), 而操作系统诞生之初就是对一些功能的封装和抽象, 这意味着其资源管理是完全透明的(这意味着我们对其细节不可知), 具体来说, 它可能在任何时候 flush dirty page, 我们没法控制何时把脏页写回磁盘

  • 其次, 由于操作系统对页面资源的管理完全透明, 我们对页面是否在内存中并不了解, 每一次对页面的访问都可能导致一个 PAGE FAULT. 这往往是很耗时的, 操作系统会阻塞当前线程并从磁盘加载页面到主存

  • 由于 BPM 中可能存在驱逐等操作, 会改变磁盘页到内存帧上的映射, 在使用 mmap 时, 这些 page id to frame id 的映射是在页表中的(事实上, 有经验的开发者应该提到页表就开始敏感性能问题), 修改页表需要粒度较大的锁, 而且为了维护多核 CPU 的缓存一致性, 修改页表的 CPU 核心必须通过处理期间中断通知其他核心也及时更新 TLB, 造成 TLB Shootdown; 那么使用自己的 BPM 会怎么样呢? 所有的锁都是用户态的锁(POSIX 互斥锁的实现通常是 futex, 而实际上 futex 的特点就是在用户态执行大部分锁操作), 不涉及任何 TLB Shootdown, 性能很高

    所以手动实现一个 Buffer Pool Manager 是有意义的.

之所以称这样的存储方式下的文件为 “Heap File”, 因为其中的页只是无序地存在, 并通过 Page Directory 查询页的位置, 没有树形组织或者哈希等应用.

页面布局:

页面应该存储什么信息应当是显然的: 具体的关系表中的信息, 以及一些元数据, 视情况可能还有一些方便查询等操作的辅助数据结构.

把数据库中的行和列存到页面中有几种方式, 可以选择以行为单位存 \(r\) 个行, 也可以选择以列为单位存 \(c\) 个列

NSM/面向行存储

将元组作为基本单位存入页面文件, 即一个页面文件存储的是多个元组(行).

这样做的优点是插入删除等操作快, 但是缺点是读取某一属性(列)时需要加载整个元组, 导致从磁盘加载过多无用数据并且空间局部性很差; 另外也无法实现压缩(后文将提及, 大多数压缩策略是基于对同类数据的, 对同一属性元素压缩收益很大, 而 NSM 是元组连续, 而属性是混杂在一起的).

由于写友好而读不友好, 适用于多次写(而每次写入少量)少读的 OLTP (事务型数据库), 如 PostgreSQL 就是行存储.

DSM/分离式存储模型/面向列存储

适用于复杂 SQL 查询而写入操作较少的 OLAP (分析型数据库)

考虑到 NSM 的缺陷, 我们可以在一个页面文件中存储连续的列元素, 这样在查询某个属性时 (如 WHERE age >= 18) 就可以减少多余数据并保持良好的局部性.

也因此, 插入/删除操作变得较为复杂 (需要在多个页内进行协调)

PAX, 混合型存储

若干个完整的行存入同一页面中, 但页内的存储是按照列存

先将若干行为一组形成行组(row group), 然后将每个行组按列分为列块, 以列块为单位进行存储 (当然, 这样要记录大量的 metadata)

具体实现结构

以上主要介绍总体的存储策略, 而根据行存/列存方案选取不同, 具体的实现目前主要有以下几种:

Tuple-orientation Storage

在一个页面的开头一段区域存储 Page Header, 包括元组数目/schema/压缩方法(见下文)元信息;

紧接着的一段区域存储一个槽数组(Slot Array), 每个 slot 记录一个元组在这个页面的位置(通过偏移量);

由于 slot 的数量会随着新元组的插入变化, 所以元组本身的数据需要从 Heap File 文件末尾往前存储, 并且更新 slot 记录的偏移量.

这种方式的缺点也有很多:

  • 由于删除是直接删除元组所在位置的数据, 所以会出现一些空白位置; 同时 Slot 和 元组本身之间也有空白. 这些空白的区域浪费了很多存储空间
  • 为了操作一个元组, 需要读这整个页进来, 即使这个页(数据库的页往往有几十到几百 KB)可能有几百个元组是我们不需要的; 读入在不同页上的多个元组那就是更糟糕的情况了

由于只能存储元组, 所以是 NSM 方案的实现.

Log Structure Storage

通过 Log Structure Merge-Tree (LSM-Tree) 数据结构管理写入. LSM-Tree 包括 MemTable 和多级压缩的、不可变的 SSTable, 可能还包括摘要表.

对于插入/删除/更新等写入操作, 分为以下几个阶段

  1. 整理日志为一个键值对. 如操作 PUT(table_id.row_id.age, 18) 会变成一个 \((K, V)\) 的键值对, 其中键 \(K\) 为表 table_id 和 row_id 的组合, 还有一个用于表明操作顺序的全局计数器 seq_num, 值 \(V\) 为整个元组的新值, 如 ['Alice', 18, 337845818] (当然实际可能是通过序列化等方式实现的, 这里不深入具体实现)
  2. 写入内存中的 MemTable 数据结构, 具体的实现可以是多样的, 功能是将元素 \((K, V)\) 按 Key 排序. (比如跳表, 后面我们会说 Skip List 是优秀的内存数据结构)
  3. 当 MemTable 中的元素满了或到达一定阈值时, 将其中已有序的键值对进行 Flush 操作, 首先按照 seq_num 对冗余的记录只保留最新的记录\(^{[1]}\), 然后写入到磁盘上的 SSTable 文件上. SSTable 中的键值对同样是有序的, 便于进行二分查找; 并且 SSTable 是不可变的文件, 一旦生成除非销毁(压缩后), 不会被修改. 此外还要注意, 对于同一个 SSTable 内部是不存在冗余记录的, 因为一个 SSTable 是一个 MemTable 一次 Flush 的产物, 而 Flush 时会去重.
  4. 上面这些由 MemTable 生成的 SSTable 文件是第一级 SSTable, 当第一级 SSTable 数量较多时, 可以把第一级多个 SSTable 合并成一个更大的第二级 SSTable. 具体来说, 例如存在一个较早的 (table1.row3, ['Alice', 18]) 和一个较新的 (table1.row3, <tombstone>) (其中墓碑标记 tombstone 表示已被删除), 则可以直接清除这两条键值对. 这里的早晚的规则是: 更低一级的 SSTable 来自上层 SSTable 的压缩, 所以越低的 SSTable 越早; 同一级的 SSTable 按照生成顺序即可辨别记录新旧.

对于查询操作:

  1. 我们会设置内存中的摘要表, 对每一级 SSTable 设置过滤器来判断这一层是否存在我们需要的键 (过滤器以后的文章中会提及), 还会记录每个 SSTable 的最大/最小键, 用来支持范围查询操作.
  2. 除此之外, 就只能对每个符合查询条件的 SSTable 进行二分查找了.

$[1]: $ 之所以在 MemTable 中保留冗余项还要记录 seq_num, 是因为原地更新需要对元素项加锁, 并发效率不好.

Index-organization Storage

使用平衡树(考虑到并发和缓存性能等, 通常是 B+ Tree)组织索引, 而 B+ Tree 的每个叶子节点存储的键值对是实际的数据, 其中值为标记着元组物理位置 Record ID.

B+ Tree 是较为重要的数据结构, 在后面 <TODO: 数据库系统设计中的数据结构> 有详细介绍.

Record ID (aka. Tuple ID)

上面的实现过程中能发现我们有时会需要唯一标识一个元组, 比如 Log Structure Storage 的 row_id,

具体来说, 数据库会为每一个元组分配一个 Record ID, 用来标记这个元组唯一的物理位置.

  • 对于 NSM 的行存方式: 一般是一个 \((\text{File ID, Page ID, Slot})\) 的三元组(的加工); SQLite 的策略是一个自增的 rowid, 以这个 rowid 为 Key 在 B+ Tree 建立的索引中查找叶子节点的页面 (关于索引和 B+ Tree 见本博客后面的文章)
  • 对于 DSM 或 PAX 的方式: 存储一个列位置 (Fixed-length Offsets), 这个行的所有元素在所有页面的列中是对齐的

压缩策略:

上文也提及了, 对于元组这样不同类数据是不太好压缩的, 所以主要存在对一列内容的压缩上(比如 temperature 列的温度可能相邻两者差距不大, 有些 isValid 列可能会出现连续的 0 或 1).

<TODO: 具体的压缩策略>

此外还可以通过传统压缩算法对若干元组组成的块进行压缩, 并以 mod log 来辅助进行延迟更新.

处理其他元组内部值的问题:

<TODO: >