Storage 存储

• 这两节课的内容是disk manager
• 我们需要了解哪些API需要暴露给上层系统

这就意味着，每次我们执⾏查询时，所要访问的数据都不在内存中

我们的目标

我们所要试着在我们的数据库系统中达成的⽬标是给应⽤程序提供⼀种错觉，即我们能提供⾜够的内存将整个数据库存⼊内存中，就像一个虚拟内存

我们如何谨慎的最⼩化每次从磁盘读取内容或运行查询时所带来的影响。我们通过⼀系列不同的技巧来减轻这种问题带来的影响

为什么不用os&mmap？

本质上来讲，使用mmap意味着放弃了数据在上内存以及硬盘上来回移动的控制权

• OS还会停止我们的进程去读取数据，我们的DBMS会变得非常慢
• 另外，操作系统并不知道某些pages必须要在其他pages执⾏之前先从内存刷到磁盘中

——这是我们不想要的，操作系统并不知道我们要做什么

如果要使用mmap，需要做一些额外的事情来防⽌操作系统做⼀些错误的事情

MongoDB

这是⼀个⾮常著名的JSON数据库系统，最初使用mmap。为了让这个引擎能够正常⼯作，他们做了很多⽆⽤功来解决这个瓶颈，例如使用各种syscall：

• madvise
• mlock
• msync

最后没办法还是买了⼀个叫做WiredTiger的⾮mmap存储引擎

总之，数据库总是很确定地知道查询要做什么，它也知道⼯作负载是怎么样的，由自己主导读写是最佳选择…而不是把读写交给操作系统

磁盘-数据库表示

So，到头来，数据库其实就是磁盘上的⼀堆⽂件，某些系统将数据库存储为⼀个⽂件，例如SQLite；其他⼤部分系统会将这些东⻄分为多个⽂件来保存

与磁盘交互的方式

我们基于os的fs所提供的API来对⽂件进⾏读写

某些DBMS有自己的fs，不使用os接口，它们直接管理一个裸存储设备。例如Oracle，DB2和SQL server。

但现在你知道，你要⾃⼰去管理你⾃⼰的⽂件系统，这真的是个很⼤的坑，因为它⼤⼤降低了你东⻄的可移植性

某些⾼端数据库系统实际上在⽂件系统之上会有⼀个shim层，它允许数据库去做⼀些磁盘调度，尽量使得写入以顺序的方式进行、以及合并一些块写入，做统一的一次写入请求

现在我们所要构建的东⻄，本质上来讲，它被称为存储管理器/存储引擎，它是我们的数据库系统中的⼀个组件，它负责维护我们在磁盘上的数据库⽂件

DB Pages

⼀个page就是⼀个固定⼤⼩的数据块，能够保存任何东⻄，但大部分系统不会在一个page上混合存储不同的数据

有些数据库系统会要求你的page是self-contained的，所有本页的信息你都需要知道该如何去解释以及理解。但从系统的更⾼层⾯来讲，这并不是完全self-contained，我们依然需要页目录

这种情况下，如果你丢失了其他任何page，也不会影响什么，容灾能力很强

每个page都会被赋予⼀个唯⼀的内部标识符，DBMS会为我们⽣成这些page ID

indirection layer：相对位置

tuple相对于页的位置，页相对于文件的位置等等；这些indirection层避免了这些位置更新信息传播到系统的其他上层部分，上层只需要知道page id 和slot number等等

大小与硬件原子性

SSD或者机械硬盘会提供API读写，通常一个硬件页是4kb⼤⼩，这意味着存储设备只能保证每次写⼊4kb时是原⼦的

• 在这之上会有OS页
• 数据库系统都有不同的权衡，他们会选择不同的页大小

例如调整index page更大，数据page更小，这样可以减少索引的cache miss；但这样会增加维护写入操作原子性的成本

page 存储架构：Heap File Organization

有件事情要理解的是，在存储管理器最底层的级别中，我们不⽤关⼼我们的page中到底有什 么，我们就可以对这个page进⾏read或delete操作

heap⽂件是⼀个⽆序的page集合，尽管⼀个接⼀个地插⼊tuple，我并不能保证它们是按照我插⼊的顺序保存在磁盘上的

但我们需要读写page的API，以及遍历文件的API，为此我们需要一些额外的元数据跟踪我们有哪些page，哪些page中是空余空间

我们可以⽤不同的数据结构来表示它们：链表/页目录

heap file：链表

• header page：p2 free & p2 data

这是一个糟糕的想法，我可以进⾏循序扫描来查看每个page，直到我找到有空余空间的page为⽌

——我们可能需要进行大量的遍历链表的无用操作

heap file：页目录

• 文件header：维护了page id和它们所处位置的映射关系，可以有其其他额外的元数据例如该页剩余空间

原子性问题：删除一个满的page后，我们想更新header但系统崩溃了——这时候就会出现问题，硬件无法保证对两个硬件page操作的原子性。

我们需要保证容灾能力与操作的原子性。这是我们之后要讨论的内容

Page Layout

两种数据表示策略：tuple oriented/log structured

header

header中可能存储一堆信息，例如：

tuple oriented：问题很多

idea：固定大小的page根据偏移量插入就行——但会产生碎片，可以在这个空余位置插入，但需要扫描

且如果不是固定长度的，这个空余可能没有足够的空间保存下一个tuple；所以每次删除可能需要移动其他tuple

slotted page：最常用

• 除了其他元数据，header中存放一个Slot Array，将⼀个特定的slot映射到page上的某个偏移量上，从而找到某个tuple

我们现在就可以将这个page内的tuple移动到我们想要的任何地⽅

• ⼀条记录的位置是由page id+slot number/offset来⼀起确定的
• 在插入tuple时，我们只需要复制tuple并更新slot array

e.g. Postgres & SQL server & Oracle 的实现

通过将系统内部这些东⻄暴露出来，使得管理员能够理解正在发⽣什么

不同的DBMS用不同的方式定位一个tuple，但思路都是一样的，例如Postgres的CTID：

这里101 tuple存放在page 0，offset 1处

关系模型对于我们插⼊tuple的顺序并不在意，Postgres会将我们插⼊的数据放到最后，而不是空缺处

SQL server中并没有ctid，而是一个内置函数：

将slot1处的tuple删除再插入一条数据，它显示这个：

它会自动让page变得紧凑，进行page压缩

Oracle中有个叫rowid的东⻄

你可以破译他：

删除再插入显示slot插入到3，与Postgres相同

log-structured：最大化顺序访问

存储这些如何创建tuple以及修改tuple的相关信息，而非tuple本身。我们只需要不断在文件后面追加log就行

这样最大化了顺序访问，提高了访问页的速度

假设我要去更新10个tuple，但它们在不同的page上，那我就必须在这个10个page上来写⼊并更新这些tuple；但如果我使⽤的是这种log-structured组织，那我将这10条更新语句写在单个page上，我⼀次就能搞定全部了

最大的缺陷：读取，你需要读取上游日记找到某条tuple是在哪里插入的

有⼏种⽅式可以提⾼这种⽅式的速度：

• 索引
• 压缩日志：遍历日志，只留一条需要的

Tuple Layout

从⾼级层⾯来讲，⼀个tuple就是⼀个字节序列，就是⼀个字节数组——这就取决于DBMS如何去解释它的意思，以及弄清楚它的类型

header：不存schema

我们通过⼀个header来跟踪⼀些不同的东⻄，例如 NULL；但不跟踪数据类型之类的东西——不同的tuple天差地别

字段排列与字对齐

大部分DBMS将不同字段按建表顺序排列，而内存型DBMS例如Redis会尝试重排字段，提高缓存命中率

不同表的 tuple 保存在同⼀个page中？

⼤部分的系统都不会这么做，因为这样会需要大量的元数据，产生数据 冗余，且更新时需要更新多张表，及其耗费时间

数据库设计规范 normalization 与 denormalization

数据库规范基本上来讲就是，关于我们如何将数据库拆分到不同的表中；而denormalization基本上是唯一一种在一个page内存储来自不同表的tuple的情形

一个有外键的表经常需要它引用的表Join，我们可以在物理上进行 pre-join

字段表示

例如INTEGER，BIGINT，SMALLINT，TINYINT，FLOAT/REAL这些固定⻓度的东⻄，和C/C++一样使用 IEEE 754 standard

可变长度类型，例如varchar，varbinary，text以及blob

• header保存长度，后面跟着数据，但没有一个NULL终止符

Dates and Timestamps，在不同的数据库中，它们的实现可以千差万别

• 大多数系统会保存1970年1⽉1⽇起的秒/毫秒/微妙，进而处理时间；本质上来讲，这些数据库系统保存的依然是完整的时间戳
• 某些系统会直接将它们以Date的形式进⾏保存，这样我们所保存的就是⼀个很⼩的值

定点数

定点数：numeric/decimal

可变精度的数字操作很高效，CPU通常只需要一条指令就可以加减；而涉及到定点数时，则需要更多的指令，会变得更慢

我们倾向于使用可变精度的数字，但这里会有舍入误差，硬件没法精确表示浮点数

对于定点数，处理的基本思路是，将它作为varchar存储，然后带一堆元数据，表示例如精度范围、四舍五入信息、小数点等等

PostgreSQL：定点数的实现

它需要通过⼀系列switch条件才能完成，⽐如说，要判断它的正负，是不是0，或者两个数字是否相等——所以会慢很多

我们并没有SQL server和Oracle的源码，但其实实现也差不多

大型二进制对象 BLOB 存储

如果我们所要保存的东⻄没办法保存在⼀个单个page下的话…

策略1：overflow page/TOAST，末尾放一个类似于CTID一样的指针定位到数据的后半部分

不同DBMS使用该策略的时机不同。在PostgreSQL中，如果我们要试着保存的值的⼤⼩⼤于2kb，他就会使用这个策略

这种策略需要额外的手段以进行容灾恢复

例如，在PostgreSQL中，⼤部分时候，这些overflow page是只读或者⼏乎都⽤来读，很少往 上⾯写东⻄

策略2：外部存储，将数据存储到外部存储中，DB中只存一个指向数据位置的指针/路径

实际上你⽆法修改该⽂件中的内容，你可以读取数据，但你⽆法操作数据

如果有⼈现在在数据库系统之外对该⽂件进⾏修改，那么当我们任何时候从我们的数据库中读取 该⽂件的时候，我们就能看到其中的变化

很多策略只在DB中存储缩略图，这样更快。将⼀⼤堆视频⽂件保存在⾼端的企业磁盘上，这种做法可能就是在浪费你们的钱。So，你们可以将这些⽂件chuck（块），保存在HDFS或者使⽤更便宜的⽹络存储服务AWS的s3 上⾯

system catalog：表的元数据

它是关于数据库相关信息的元数据，它⾥⾯存放了表名，索引等等；当然也有其他⼀些东⻄，例如，⽤户权限，安全相关

很多数据库系统都会将它们的所有数据库的Catalog⽤另⼀张表来保存

⼤部分数据库系统会通过STANDARD INFORMATION_SCHEMA API把catalog暴露出来

对于MySQL，这个元数据的表也存放在一个目录下，它无法阻止其他人修改这个目录，这可能对我们的正确性造成一定的威胁

存储模型

在我们的数据库系统中，我们所关⼼的workload有两类：

对于机器学习和流式处理来说，它们所要关⼼的可能不⽌这两种，但对于我们来说，⽬前关⼼ 这两种就⾜够了

OLTP & OLAP

联机事务处理 OLTP

构建⼀个新应⽤程序时就会遇到它。我们从外⾯的世界拿到新数据后，将它们放⼊我们的数据库系统

• 它的特点是你只会反复地去读写⼀⼩部分数据

联机分析处理 OLAP

当你们已经从OLTP应⽤程序中收集到⼀⼤堆数据时，现在，你们想去分析它，并从中推断出新的信息

它们会去读取⼤量的数据，进行大量的Join

还有⼀种新的workload，它被称为混合事务分析处理HTAP，即在拿到数据时就尝试分析

行存储 / 列存储

• why 行存储？

N-ary storage model 也被称为行存储模型.

我们的目的是访问单个实体，例如某个tuple，对这种情形来说行存储非常快速

常见于OLTP

• why 列存储？

而如果我们想访问所有tuple中的某个字段，如果使用行存储，一整个页中只有一小部分是有效的数据，这会耗费大量的时间。更好的方式是把某列的值连续地保存在一起

• 同时我们需要一些手段把值和tuple对应
• 列存储使我们可以更加方便地进行空间压缩，因为对于列存储，同一个page中的值都是类似的，有大量重复的值存在
• 缺点也很明显，读取一个tuple很困难
• 常见于OLAP。

他的问题是，有没有很好的理由来将两者混合在⼀起。实际上在构建我们的数据库系统时（知秋注：这个课上cmu所开发的这个数据库），确实将它们 两个混合在了⼀起

后⾯，我们将这种想法抛弃，并从头开始，因为它是个糟糕的想法。它在⼯程上消耗太多时间了

有些系统会向我们提供这两种。例如，在MySQL中，我们在创建表时可以告诉它⽤⾏存储，创 建另⼀张表时告诉它使⽤列存储。本质上来讲，它们有两种独⽴的存储管理器，以及两种独⽴的执⾏引擎来对它们进⾏处理。So，这种系统被称为混合存储系统，或者说混合数据库系统

对于内存型数据库，我认为我们在列存储上能够⾜够快的执⾏事务处理