CMU15445-lecture3
第三课：数据库存储（Part 1）
1 存储
我们将专注于以磁盘为导向的DBMS架构，假设数据库的主要存储位置在非易失性磁盘上。
在存储层次的顶部，你拥有离CPU最近的设备。这是最快的存储设备，但也是最小和最昂贵的。离CPU越远，存储设备越大但速度越慢。这些设备的每GB价格也越便宜。
易失性设备：
- 易失性意味着如果你将设备断电，那么数据将丢失。
- 易失性存储支持快速的随机访问，并且具有以字节为寻址单位的位置。这意味着程序可以跳转到任何字节地址并获取那里的数据。
- 对于我们的目的，我们将始终将这种存储类型称为“内存”。
非易失性设备
- 非易失性意味着存储设备不需要持续供电才能保留其存储的位。
- 它也是块/页可寻址的。这意味着为了在特定偏移处读取一个值，程序首先必须将包含程序想要读取的值的4KB页面加载到内存中。
- 非易失性存储在顺序访问方面传统上更好（同时读取多个连续数据块）。
- 我们将其称为“磁盘”。我们不会在固态存储（SSD）和旋转硬盘（HDD）之间进行（重大）区分。
还有一种相对较新的存储设备正在变得越来越受欢迎，被称为非易失性内存。这些设备旨在兼具DRAM的速度和磁盘的持久性，可谓兼具两者之优势。我们在这门课程中不涉及这些设备，并且目前尚未广泛使用于生产中。可能最著名的例子是Optane；不幸的是，英特尔在2022年夏天停止生产该产品。请注意，您可能会在之前的参考资料中看到将非易失性内存称为“非挥发性内存”的说法。
你可能会看到关于NVMe SSD的参考资料，其中NVMe代表非易失性内存扩展。这些NVMe SSD与持久内存模块不是同一种硬件。相反，它们是通过改进的硬件接口连接的典型闪存驱动器。这种改进的硬件接口允许更快的传输速度，利用了NAND闪存性能的改进。
由于我们的DBMS架构假设数据库存储在磁盘上，DBMS的组件负责确定如何在非易失性磁盘和易失性内存之间传输数据，因为系统不能直接在磁盘上操作数据。
我们将重点放在隐藏磁盘延迟上，而不是寄存器和缓存的优化，因为从磁盘获取数据非常慢。如果从L1缓存引用中读取数据需要1秒钟的时间，而从SSD读取数据需要4.4小时，从HDD读取数据需要3.3周的时间。
2 基于磁盘的DBMS概述
数据库全部存储在磁盘上，数据库文件中的数据被组织成页，第一页是目录页。为了对数据进行操作，数据库管理系统需要将数据加载到内存中。它通过拥有一个缓冲池来管理磁盘和内存之间的数据传输。DBMS还拥有一个执行引擎来执行查询。执行引擎会向缓冲池请求特定的页，缓冲池会负责将该页加载到内存中并向执行引擎提供该页在内存中的指针。缓冲池管理器将确保在执行引擎在内存中操作该部分时，该页存在。
3 DBMS vs OS
DBMS的一个高级设计目标是支持超过可用内存的数据库。由于读写磁盘是昂贵的，必须仔细管理磁盘使用。我们不希望从磁盘获取数据时出现大的停顿，从而导致其他事务减缓。我们希望DBMS能够在等待从磁盘获取数据时处理其他查询。
这个高级设计目标类似于虚拟内存，其中有一个大的地址空间和一个能够从磁盘上载入页面的操作系统位置。
实现虚拟内存的一种方法是使用mmap将文件的内容映射到进程的地址空间中，这使得操作系统负责在磁盘和内存之间移动页面。然而，不幸的是，如果mmap遇到也错误，进程将被阻塞。
- 如果你需要写入，就不应该在你的数据库管理系统中使用mmap。
- 数据库管理系统（几乎）总是希望自己控制事物，并且在这方面做得更好，因为它对所访问的数据和正在处理的查询有更多了解。
- 操作系统不是你的朋友。
可以通过以下方式使用操作系统：
- madvise：告诉操作系统你计划何时读取某些页面。
- mlock：告诉操作系统不要把内存范围交换到磁盘。
- msync：告诉操作系统将内存范围刷新到磁盘。
出于正确性和性能的原因，我们不建议在DBMS中使用mmap。
尽管系统可能具备类似操作系统提供的功能，但是将这些过程由DBMS自己实现可以给它带来更好的控制和性能。
4 文件存储
在最基本的形式中，数据库管理系统将数据库存储为磁盘上的文件。有些可能使用文件层次结构，而另一些可能使用单个文件（例如，SQLite）。
操作系统对这些文件的内容一无所知。只有数据库管理系统知道如何解读这些内容，因为它们是以特定于数据库管理系统的方式进行编码的。
DBMS 的存储管理器负责管理数据库的文件。它将文件表示为一个page的集合。它还跟踪哪些数据已被读取和写入页面以及这些页面中有多少可用空间。
5 数据库页
DBMS将数据库组织在一个或多个文件中，这些文件包含了称为页的固定大小的数据块。页可以包含不同类型的数据（元组、索引等）。大多数系统不会在页内混合使用这些类型。某些系统要求每个页都是自包含的，意味着读取每个页所需的所有信息都在页本身上。
每个页面都被赋予了一个唯一的标识符。如果数据库是一个单独的文件，那么页面ID可以直接是文件的偏移量。大多数数据库管理系统都有一个间接层，它将页面ID映射到文件路径和偏移量上。系统的上层将请求一个特定的页面编号。然后，存储管理器将把该页面编号转换成文件和偏移量以找到该页面。
大多数数据库管理系统使用固定大小的页面，以避免支持可变大小页面所需的工程开销。例如，对于可变大小的页面，删除一个页面可能会在数据库管理系统无法轻松填充新页面的文件中创建一个空洞。数据库管理系统中有三个页面的概念：
- 硬件页面（通常为4 KB）。
- 操作系统页面（4 KB）。
- 数据库页面（1-16 KB）。
存储设备保证以硬件页面大小的原子写入。如果硬件页面是4 KB，并且系统尝试将4 KB写入磁盘，要么全部写入4 KB，要么全部不写入。这意味着如果我们的数据库页面大于硬件页面，数据库管理系统将必须采取额外措施确保数据被安全地写出，因为在系统崩溃时，程序可能正在写入数据库页面的一部分到磁盘。
6 数据库堆
有几种方法可以找到DBMS希望在磁盘上找到的页面位置，堆文件组织就是其中一种方法。堆文件是一个无序的页面集合，其中元组以随机顺序存储。DBMS可以通过使用页面链表或页面目录来根据页面ID在磁盘上定位一个页面。
- 页面链表：头页面保存了指向空闲页列表和数据页列表的指针。然而，如果DBMS正在寻找特定的页面，它必须在数据页列表上进行顺序扫描，直到找到所需的页面为止。
- 页面目录：DBMS维护特殊页面，跟踪数据页面的位置以及每个页面上的空闲空间量。
7 页面布局
每个页面都包含一个头，记录页面内容的元数据信息：
- 页面大小
- 校验数
- DBMS版本
- 事务可见度
- 自包含性。（一些系统如Oracle需要这个特性。）
一种针对数据布局的稻草人方法是跟踪DBMS存储的元组数量，并在每次添加新元组时将其追加到末尾。然而，当元组被删除或者元组具有可变长度的属性时，问题就会出现。
有两种主要的数据布局方法：（1）使用插槽页面和（2）日志结构。
插槽页面：页面将插槽映射到偏移量上。
- 是目前在DBMS中最常用的方法。
- 页眉保存了已使用插槽的数量、最后一个已使用插槽的起始位置的偏移量以及插槽数组，用于跟踪每个元组的起始位置。
- 要添加一个元组，插槽数组将从开始位置增长到结束位置，元组的数据将从结束位置增长到开始位置。当插槽数组和元组数据相遇时，页面被视为已满。
日志结构：在下一节讲述。
8 元组布局
元组实质上是一系列字节的序列。DBMS的工作是将这些字节解释为属性类型和值。
元组头：包含关于元组的元数据。
- DBMS并发控制协议的可见性信息（即，哪个事物创建/修改了该元组的信息）。
- NULL值的位图
- 注意，DBMS不需要在这里存储有关数据库模式的元数据。
元组数据：属性的实际数据
- 属性通常按照创建表时指定的顺序存储。
- 大多数DBMS不允许元组的大小超过一个页面的大小。
唯一标识符：
- 数据库中的每个元组都被分配一个唯一标识符。
- 最常见的是页面Id+（偏移量或插槽）
- 应用程序不能依赖这些ID标识任何含义。
无规范化的元组数据：如果两个表相关，则DBMS可以“预连接”它们，使两个表位于同一页上。这样可以提高读取速度，因为DBMS只需加载一页而不是两个单独的页面。但是这样会增加更新的成本，因为DBMS需要更多的空间来存储每个元组。