1. 存储器

在 CMU 15-445 这门课中主要关注”disk-oriented” DBMS。我们假设数据库的主要存储位置在非易失性的硬盘上。

在这个存储器等级图中可以看出越靠近 CPU 的存储器，它的速度越快、容量越小、价格也越昂贵。
易失性设备:

• 易失性意味着当你断电后，存储器中的数据将会丢失。
• 易失性存储器支持快速的、按字节寻址的随机访问。这意味着程序可以跳到任何字节地址并从那里读取数据。
• 在这门课中，仪式性存储器特指“memory”也就是内存。

非易失性设备:

• 非易失性意味着不需要持续供电来保证数据不会丢失；即使断电，数据仍会持久化存在。
• 同时它是按块/页寻址的。这意味着为了从一个特定的 offset 中读取数据，程序首先需要加载包含指定数据的 4KB 页面到内存中。
• 在这门课中特指”disk”，并且不会区分 SSD 和 HDD。

现在也出现了一种新型的存储器叫做“non-volatile memory”，兼顾了内存的快速随机访问和硬盘的存储持久性。
因为系统假设数据库存储在硬盘上，那么数据库的组成部分应该负责如何在 non-volatile disk 和 volatile memory 之间移动数据，因为操作系统不能直接在硬盘上操作数据。
我们将关注于如何去“隐藏”硬盘的延迟，而不是关注于优化寄存器和 caches，因为从硬盘读取数据太慢了，首要的瓶颈就是硬盘的读取速度。

（上图中是假设 L1 cache 读取需要 0.5 秒，那么其他存储器读取分别需要多久？）

2. Disk-Oriented DBMS 概述

The database is all in disk。数据被组织成 pages 存在数据库文件中，并且第一个 page 是 directory page。为了能够使用数据，DBMS 需要将数据带到 memory 中。在数据库中，有一个组件是 buffer pool，它管理数据在 disk 和 memory 之间的移动。同时还有一个组件叫做“执行引擎(exeution engine)”，它会执行查询。执行引擎向缓冲池申请读取特定的页面，缓冲池会负责将 page 带到 memory 中并且给执行引擎一个指向 memory 中 page 的指针。同时，在执行引擎在 memory 中执行时，缓冲池会保证那个 page 一直在 memory 中。

3. DBMS vs. OS

数据库系统中的一个高级设计目标是使数据库能够支持大于 memory 剩余量的容量。由于向硬盘读\写的开销是巨大的，所以必须仔细地管理读写操作。我们不希望从硬盘中读取某些数据会导致所有的操作变慢，因为我们希望当数据库在等待从磁盘获取数据时，数据库可以执行其他的查询。
这个高级设计目标有点类似于 virtual memory（虚拟内存）。存在有一块巨大的地址空间和一块空间让 OS 从硬盘中读取 pages。
实现这个虚拟内存的一种方案是使用mmap在进程的地址空间中映射数据库文件的内容，同时这也将 page 在 memory 和 disk 中移动的管理权交给了 OS。不幸的是，这意味着如果mmap命中了缺页错误，那么进程将会被阻塞。

• 如果你需要写数据，在 DBMS 中不要使用mmap。
• DBMS 几乎总是想要自己控制，并且由于数据库更清楚哪个数据被获取以及哪个查询在进行。
  • 正确顺序地将脏数据刷盘
  • 特定地预先读取数据
  • Buffer 替换策略
  • 线程/进程调度
• Operating System is not your friend.

可能会使用到的操作系统调用：

• madvise: Tells the OS know when you are planning on reading certain pages.
• mlock: Tells the OS to not swap memory ranges out to disk.
• msync: Tells the OS to flush memory ranges out to disk.

为了正确和性能原因，我们不建议使用mmap在 DBMS 中。

4. File Storage

DBMS 以一个或多个文件的形式在硬盘中存储数据库。（操作系统不知道文件的内容）。
存储管理器负责维护数据库中的文件。
It organizes the file as a collection of pages。

• Tracks data read/written to pages.
• Tracks the available space.

5. Database Pages

一个 page 就是一块固定大小的数据块。

• 它可以包含 tuples、meta-data、indexes、log recordes…
• 大多数系统不会在 pages 中混合上面提到的类型。
• 一些系统要求 page 是 self-contained，这意味着所有读取页面所需的信息都包含在页面本身中。

每一个 page 都有独立的 id，DBMS 利用一个中间层将 page id 映射到物理位置上。

大多数 DBMS 会采用固定大小的页面。如果采用可变大小的页面，删除一个页面可能导致 DBMS 中出现一个无法放置新页面的空洞，因为新页面可能比旧页面大。
在 DBMS 中，存在三种不同概念的 page：

• Hardware page（通常是 4KB）
• OS page（4KB）
• Database page（1-16KB）

存储设备保证原子性地写一个 hardware page size 的数据。这也意味着，如果 Database page 大于 Hardware page，那么 DBMS 必须提供额外的方法来保证写安全。

6. Database Heap

在 DBMS 中存在多种方法来找到 DBMS 想要的数据在磁盘上的位置，而 heap file 就是其中一种方法。
heap file 就是 tuple 随机存储的页面的无序集合。
有两种方式来表示 heap file：Linked List 和 Page Directory。

Linked List

在文件的开始维护一个 header page，其中包含两个指针：

• HEAD of free page list
• HEAD of data page list

这也意味着查找某个页面的时间复杂度是 O(n).
每个页面自己维护 free slots 的数量。

Page Directory

DBMS 维护一个特殊的 page，它记录 data page 在 data file 中的位置，同时也维护各个 page 中空闲空间的数量。

7. Page Layout

每个 Page 都包含记录元数据的 header。元数据包括：

• page size
• checksum
• DBMS version
• Transaction visibility
• self-contained(some systems.)

主要有两种方法在 pages 中放置数据：slotted-pages 和 log structures

slotted-pages

大多数 DBMS 使用这种方式，

log structures

DBMS 不是在 page 中存储 tuples，而是存储 log record。

特点是“写快读慢”，因为读取的时候需要回放日志来创建 tuple。
同时为了避免读的太久，DBMS 可以通过索引在 log record 中跳到特定的位置：

8. Tuple Layout

tuple 本质上就是字节的序列。DBMS 负责将这些 bytes 解释成特定的属性和值。

Tuple Header

包含 tuple 的元数据：

• Visibility information for the DBMS’s concurrency control protocol (i.e., information about which transaction created/modified that tuple).
• BitMaps for NULL values
• 注意 DBMS 不要在这里存储关于 schema 的元数据

Tuple Data

tuple 的属性是按序存储的，方便读取。同时大多数 DBMS 不允许 tuple 的大小大于 page size。

Unique ID

每个在数据库中的 tuple 都被分配了唯一的 ID。
通常是： page_id + (offset or slot)
应用程序不能够用 ID 来表示任何东西。

Denormalized Tuple Data

如果两个表是关联的，那么有些 DBMS 会“pre join”它们，这两个表就会在同一个 page 当中。这种机制可以使读取更快（数据库只用读一次 page 而不是读两次 page），但它也会让写的开销变得更大。