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