磁盘数据库存储

1.简介

本文主要讨论的是基于磁盘数据库的存储，因此我们假设数据库中存在许多从磁盘到内存的移动。

对于磁盘来说，磁盘的特点为顺序I/O、块可寻址且为非易失设备。对于内存来说，内存的特点为随机I/O，字节可寻址且为易失设备。

2.缓存管理器与虚拟内存

很显然，由于磁盘更便宜、容量更大，因此大多数的数据都是存于磁盘之中的。但是冯诺依曼结构只允许我们在内存中进行数据运算，内存是无法装下所有数据的，因此DBMS需要提供类似操作系统的虚拟内存的抽象。

但我们不应该直接使用OS提供的虚拟内存或其他相关的API，原因是我们无法干预OS的底层。

比如若缓存池满了，我们需要选出一个牺牲页写回到磁盘中，此时的牺牲页选择策略可能不由我们控制（虽然OS提供了如madvise、mlock和msync等API，但总是不全面的）。

一个最常见的场景就是对于不同workload或者不同的语句下我们选择不同的策略，如顺序扫描的时候我们可以利用buffer bypass避免缓存管理器的页都被刷回磁盘中。

总的来说，操作系统提供的像是一辆大货车，拥有普适性。但是DBMS想要做到的是提供一辆跑车，没有普适性但是在特定场景下有更高的性能。

缓存管理器会在后文中详细介绍。

3.文件存储

数据库的数据落地到操作系统，本质就是特殊编码的一个或多个文件，由数据库的Storage manager负责跟踪并解码这些文件。

Storage manger负责将这些文件解释成page的集合，其中page类似于os的block，存储着tuple以及相关的元数据、也可以存储如索引等数据。

同时，Storage manger还负责跟踪tuple对应的实际文件位置，如对一个tuple进行更新的时候应该写入到哪个文件的哪个偏移量中。

4.Page，Page_id和Page Directory

Page就是固定大小的数据块，可以存储tuple或者是索引的相关数据。

每一个人Page都有一个独一无二的标识符page_id，如果数据库文件只有一个，那么该标识符可以是offset；如果有多个文件，可以是文件标识符+offset。大多数操作系统选择将文件路径和偏移量作为映射的key，映射到page_id中。

有了page_id，每一个tuple就可以根据page_id加tuple的offset形成一个tuple的独一无二标识符。

由于数据库是一个无序的数据集合，pages在底层也是无序的。此时，我们需要有方法由page_id找到page的物理位置。数据库常采用的方法是维护一些特殊的page，用于存储page的物理位置以及空余的空间（free space）。

5.Page的结构

每个Page的头部都有一些metadata，常见的有：

• Page大小
• Checksum
• DBMS版本
• 事务可见性：和MVCC相关。
• 自解释：即不需要额外信息就可以解释该页所含的数据。如记录tuple的结构，这样就可以根据tuple的头部加计算出来的固定偏移量找到需要的tuple内数据。

常见的存储模型有两种，行存储和列存储。行存储指的是在一个连续空间内记录一个完整的tuple，而列存储指的是将一个tuple的attributes分散存储。

其中常见的行存储又分为两种：

• Slotted Pages：即从页尾开始，在Page中存储一段段连续的tuple序列。可以根据固定的offset找到tuple。
• Log-Sructured：即不记录tuple的具体数据，而是记录对tuple的操作记录。

Slotted Pages的存储方式是同时具有较快的读和写速度，而Log-Structured则拥有更快的写速度，但是读速度则较慢。如果后者想要更快的读速度，则需要维护一些而外的元数据，比如最后一次写出现的时间。

列存储将tuple的attributes存储到不同页中。列存储的特点是结构紧凑，且主要用于OLAP即数据分析场景，该场景的特点是读取多、更新少。最重要的是，如果一个tuple包含成百上千个attribute，但是查询语句中只用到了其中的其中几十个甚至几个attribute，对比行存储就有更明显的效率优势。缺点是，读写都需要获取多个page，因此有更多的开销，只能用于特定场景。

6.Tuple的结构

Tuple就是Page中的序列，由DBMS解释。解释后的Tuple常常携带以下信息：

• Metadata
• 用于Concurrency Control的信息，如时间戳等。
• 表示空值的bitmap
• 不需要存schema（tuple结构）相关的信息
• Data：存储顺序常常和schema定义的相同。
• 标识符：常常是page_id+offset