CMU-15445 Database Storage

15-445/645笔记。也参考李国良老师的《数据库管理系统》。之前参考这本书写过笔记,可以参考这里.

面向磁盘的数据库管理系统

这里重点关注面向磁盘的DBMS，其主要存储位置位于非易失的磁盘上。计算机结构中，CPU访问越快的存储，价格越高，按照访问速度分别为CPU Cache -> Memory -> Disk(SSD -> HDD)。其中Disk(磁盘)为非易失存储，其他为易失存储。现在也存在持久性内存(persistent memory)，当下不讨论这种硬件因为其仍然没有被广泛生产使用。

因为数据库存储在磁盘上，且系统无法直接操作磁盘上的数据。因此DBMS需要组件负责在非易失存储和易失存储之间移动数据，以及设计移动的方式。组件应该关注于隐藏延迟，因为透过内存直接从磁盘中取数据非常慢。

磁盘上的数据库文件以页面(Pages)为单位来组织，其中包括目录页面。操作页面需要将页面加载到内存中，从而需要缓存池(buffer pool)管理数据在内存和磁盘间的来回移动。查询执行引擎组件用于执行查询语句，其会向缓存池请求一个指定页面，缓存池负责将页面载入内存并给查询执行引擎一个指向该页面的指针。缓存池管理器需要保证查询执行引擎执行操作时页面指针有效。

DBMS vs OS

DBMS的一个设计目标是支持数据库超出可用内存的大小，因为磁盘读写开销很大，磁盘需要谨慎管理。从磁盘获取数据时不应该阻塞，而应该可以在等待时执行其他查询。这个设计目标类似于虚拟内存(virtual momory)，其中OS使用一个巨大的地址空间来从磁盘读取页面。

为了实现上述的DBMS的设计目标，可以使用mmap将文件映射到内存中。即由OS来负责数据在内存和磁盘间的来回移动。但是mmap有可能遇到页面错误(缺页)，导致进程阻塞。mmap不适用于DBMS的页面管理，原因在于：

• 事务安全，OS可能在任何时刻刷盘；
• I/O 停滞，DBMS不知道哪些页面在内存中，缺页时产生停滞；
• 错误处理，会遇到SIGBUS错误；
• 性能问题，OS数据结构竞争，TLB击落;

可以使用一部分OS接口：

• madvise, 告诉OS要读取指定的页面；
• mlock, 告诉OS指定页面不能被淘汰；
• msync, 告诉OS将指定页面刷到磁盘上。

DBMS更清楚数据和查询要怎么处理，包括：

• 脏页刷盘时机的正确顺序；
• 特定页面预取；
• 页面替换策略；
• 线程/进程调度；

由DBMS自行实现该设计目标可以是处理更合理和性能更优。

更具体的权衡和原因可以参考论文Are you Sure You Want to Use MMAP in Your Database Management System?，文中暗示了mmap是依托答辩.

文件系统

数据库存储有两个主要问题：

1. DBMS如何在磁盘文件上(以什么形式)表示数据库？（本文议程）
2. DBMS怎么管理其内存并将数据在磁盘间来回移动？

最简单的，DBMS将数据库作为文件存在磁盘中，有的数据库是层次结构文件，有的数据库是单个文件（比如SQLite）。

OS不了解数据库文件的结构和内容，由DBMS的存储管理(storage manager)组件管理数据库文件。其将文件组织成数据页面的集合，并跟踪已读取和写入页面的数据，以及这些页面中有多少空闲空间。

页面

DBMS中有三个页面概念： 硬件页面，OS页面和数据库页面。硬件设备保证了硬件页面的原子写入，但对于大于硬件页面的页面写入需要自行保证。

页面中包含不同数据（索引，或者数据项等），也存在混合各种数据的页面。

每个页面有一个唯一id。如果数据库是单个文件，可以通过查找文件+偏移量找到该数据页面。

DBMS通过链表或者页面目录找到指定页面：

• 链表：需要遍历；
• 页面目录：提供给定页面的地址。

数据库堆

页面内容

每个页面头部和数据两部分。头部主要包括页面大小，校验码等信息。对于面向行存的页面，数据一般有两种组织方式：

• Slotted Pages： 头部跟踪槽大小和偏移量（用于不定长的元组）；
• Log-Structured: 追加写入。

元组（数据项）布局

一个元组本质上是一个字节序列。DBMS的工作是将这些字节解释为属性类型和值。

元组中包括：

• 头部：包含该tuple元数据；
• 数据；
• 唯一标识符：数据库中的唯一标识符，一般表示为page_id+(offset/slot)