CMU15445数据库系统笔记.18221501

news/2024/10/5 11:17:54

本篇文章是CMU 15445数据库系统的学习笔记，持续更新...
[课程视频 Fall 2021] | [课程主页]

LEC03. 数据库存储结构（上）

分层设计概述

设计任何大型系统时的一个常用手段是分层，数据库系统也可以被分成若干层，每一层处理自己的事情，向上提供简单的API隐藏细节。

举个例子，比如最底层的磁盘管理器负责处理如何划分、组织磁盘页，而由于磁盘上的数据只有在内存中才能被CPU处理，所以再上一层的Buffer Pool管理器便负责在需要时将这些页从磁盘fetch到内存中并保持一段时间。它可能做了很多工作，比如当fetch一个新页，但内存不够需要踢出一个旧页时，如何做出正确且最好的选择。而对于上层来说，它只跟Buffer Pool管理器提供的API交流，它们甚至可以认为我们有一个无限大的内存，数据全部存在内存中（是不是有点像操作系统课程中学过的虚拟内存）。

虽然数据库底层的DiskManager只负责划分和组织磁盘页，但LEC03的内容不止于此，涉及到：

将页面在文件中布局的方式（如何通过页号找到页面，如何管理空闲空间）

将tuple在物理页中布局的方式

将数据在tuple中布局的方式

顶层视角

下面我们来从磁盘管理器和Buffer Pool管理器的顶层视角来看一下它们是如何工作的

首先我们注意到，页一定是需要通过某些方式编址的，这个地址就叫页号
其次，我们要有一个页号到物理页位置的映射，一般来说会在一个公知的磁盘页上保存这些映射，这个磁盘页就叫页目录
外界通过页号来访问Buffer Pool管理器，Buffer Pool管理器会查看当前该页是否被加载到内存中，是否过期等，如果需要的话，就访问磁盘把对应的页fetch出来
fetch任何页之前，肯定要先fetch页目录，页目录基本是要pin在Buffer Pool中的

如何在文件中组织页面

在本节中讨论如何在文件中组织数据库页面，涉及页面的新增、获取、写入和删除操作，并且我们的组织方式必须支持所有页面的遍历（考虑全表扫描场景）。我们需要有一些元数据来跟踪我们有哪些页面以及哪些页面具有空闲空间。

常见的组织方式有三种：

堆文件组织
顺序文件组织
Hash文件组织

这里主要介绍堆文件组织

堆文件是一个页面的无序集合，有两种方式实现堆文件：

链表
页目录

堆文件：链表实现

使用一个公知位置的page作为header page，其中只存储两个指针，这两个指针构成两个链表，一个是具有空闲空间的页面组成的列表，一个是已经完全满了的页面组成的列表。

当向一个页面写入时，我们需要遍历Free PageList，找到第一个能够满足我们写入请求的页面。

在寻找一个页面时，我们没有任何元数据，所以也只能遍历寻找。

堆文件：页目录实现

使用一个公知位置的page作为页目录，它维护指定页号的页面在文件中的位置。

页目录同样保存了每一个页面具有多大空间的元数据。

DBMS必须确保在页发生变化时，页目录同步更新。在使用链表时，页面的元数据是在页内部保存的，只要页能原子写入就不存在元数据和页实际情况不符的时候，但页目录必须处理这种情况。

这里只介绍了高层次的思路，但没有讨论细节。实际上很多东西可以讨论，比如一个页面做页目录如果不够了咋办？如何能减少物理页的数量（提高页大小）？如何组织页目录让它对CPU缓存友好？

页结构

页头

页面有一个头部来描述页面的一些元数据，比如页面大小、checksum、用于兼容版本升级的version号、事务可见性信息、压缩信息等等。一些高级的数据库系统要求页面是自包含（self-contained）的，以提供更强的容灾，此时可能还要在头中存储一切自包含信息（比如表的schema）。

数据

数据库系统可能有很多不同种类的页，比如有的会存数据、有的存索引、有的存日志......我们这里只讨论存储数据的数据页。实际上在很多系统中虽然有很多种页面，但它们都被像数据页一样的方式处理，即将要存储的内容也作为tuple。

一个简单的存储tuple的方式就是保存页内的元组数量，然后只是一个接一个的存储：

这种方式有几个问题：

若每个tuple长度不一致（变长列），删除tuple时可能产生碎片
如果你将tuple在页内的绝对偏移返回给上层用于定位，那你就不能进行碎片清理
如果你将tuple的与位置无关的编号返回给上层，则查找时需要在页内对所有tuple进行遍历

一种更常见的，被商用数据库使用的方式是槽页：

在页面顶部存储一些固定长度的槽
tuple则被存在页面底部
一旦有了一个tuple，就会有一个槽指向它
返回给上层的是槽号，这让我们可以随意的对页面进行碎片清理，只需要更新槽中指针就行，槽对上层屏蔽了这些动作（就像页目录向上层屏蔽了页的物理位置）

数据库系统的上层使用 pageid + slot/offset 作为元组的唯一记录id（record identifier）。具体场景：查询名字叫andy的教授，我们会查name列的索引，索引中包含对应记录的(pageid, slot)，可以拿它去表文件中找。
PostgreSQL中的CTID、Sqlite和Oracle中的ROWID都是这样做的，InnoDB的索引组织表好像使用了完全不同的方案，这种场景下需要两次索引查询。

LEC04. 数据库存储结构（下）

日志文件组织

顺序的向页面中追加每一个数据库操作

这种组织方式的写入很快，因为都是顺序IO，但在读取时则需要通过向上扫描日志来重建我们需要的元组。比如有如下日志：

INSERT id=1, col1=a, col2=b
// a lots of log entries
UPDATE id=1, col1=z

我们必须从最后一个UPDATE读到最前面才知道id=1的这条记录的所有字段内容。

加速读取：

建立索引，以可以直接找到对应id的一批记录（但顺序写入的优势就降低了）
定期压缩，日志文件组织随着时间推移肯定会有很多无用的内容，需要定期压缩以减少向上扫描时的浪费

使用日志文件组织的数据库：HBASE、cassandra、levelDB、RocksDB

固定精度数字带来的问题

由于浮点数的精度问题，数据库系统不得不为用户实现固定精度的小数——NUMRIC、DECIMAL。

用户可以指定固定精度小数的整数位数和小数位数，但由于CPU中并没有一个像浮点数那样的电路来执行固定精度小数之间的计算，所以这些计算都是在应用层用大量代码来完成的，它的性能肯定不如浮点类型。

溢出页

一般数据库不会允许一个元组或者说一个元组中的列大于整个页面的，数据库一般会在列个数和列长度之间做出限制。

但若还是存在一个元组或一个列可能超过一个页大小的情况（BLOB、TEXT），对应的内容就会被存在溢出页中，而元组中的列则保存一个到溢出页的指针。

一个值可能占用多个溢出页，溢出页之间可以组织成一个链表或以什么其它方式组织。

InnoDB的压缩行模式中貌似对于VARCHAR等数据，超过一定长度就会存到溢出页中，这样有好处也有坏处。好处就是一个数据页容纳的数据量更多了，坏处就是每次取这个溢出列的值都是一次随机IO。

一些DBMS允许你将非常大的值存储在外部文件中，而不是页面内，比如Oracle的BFILE类型。

System Catalogs

System Catalogs保存数据库中的一些元数据信息，包含：

表、列、索引、视图的元数据
用户、权限的元数据
内部统计数据

大多数系统会将这些元数据信息包装成和数据表一样的关系、元组形式供用户使用，如MySQL的information_schema（这好象是一个ANSI标准），同时有特殊的代码来驱动这些特殊的库表。

数据库工作负载

数据库可能用于处理不同的工作负载，这对如何构造实际的存储系统有巨大的影响，数据库领域常见的工作负载如下：

在线事务处理（OLTP）：每次只读/更新少量数据的快速操作，重点在于处理大量这样事务的并发。
在线分析处理（OLAP）：读取大量数据并计算聚合的复杂查询
混合事务分析处理（HTAP）：OLTP + OLAP在一个数据库实例中

常见的公司的做法是：

部署OLTP数据桶 + OLAP数据仓
所有事务在OLTP侧发生，通过ETL（提取、转换、加载）过程被周期性推送到OLAP数据仓（比如一天一次）
OLAP进行分析计算，得出一些分析结果
如果需要的话，也有可能将分析结果推送回OLTP侧

面向行的NSM（OLTP）

N-ARY存储模型（NSM）是指DBMS在一个页面中连续地存储一个单一元组的所有属性，非常适用于OLTP这种只对独立实体操作且重写入的工作负载。

考虑下面的查询：

SELECT * FROM t_user
WHERE username = 'xxx';

这是OLTP应用的常见查询，DBMS首先通过在username列上的索引找到对应记录所在的页面（也许是pageid, slot），然后只再需要一次读取就可以一次性读取该数据的全部内容了，因为所有属性都被连续的存在了一起。

考虑下面的查询：

SELECT COUNT(U.lastLogin),EXTRACT(month FROM U.lastLogin) as month
FROM t_user AS U
WHERE U.hostname LIKE '%.gov'
GROUP BY EXTRACT(month FROM U.lastLogin)

该查询找出所有hostname以.gov结尾的用户，将它们根据最后登录的月份分组，最终导出每一个月份有多少官方人员最后一次登录的统计。

在类似这样的统计查询中，用户通常只关心某些列而不是全部列，如果使用NSM，一个页面中大部分数据可能是你不关心的，这样一次IO读取的收益就很低了。

NSM优势：

插入、更新以及删除都很快，数据都在一个地方，找到了写就完事了
很适合OLTP这种大部分查询需要返回整个元组的

劣势：

不适合扫描表中大量数据
不适合只读取元组的子属性集

面向列的DSM（OLAP）

分解存储模型（DSM）是指DBMS将元组的所有单一属性连续地存储在一个页面中，适合OLAP这种写入少且需要在表的子属性集上做大量扫描的工作负载。

再次考虑刚刚的查询：

SELECT COUNT(U.lastLogin),EXTRACT(month FROM U.lastLogin) as month
FROM t_user AS U
WHERE U.hostname LIKE '%.gov'
GROUP BY EXTRACT(month FROM U.lastLogin)

这次，DBMS只需要找到保存hostname和lastLogin列的页面，读到的都是它所需要读的数据。

将列单独存储的额外代价是：必须有一个策略识别每一列的每一个值来自于哪个原始行，否则，像上面的SQL，你利用hostname列过滤出了最终需要统计的用户，但你怎么知道过滤出的是哪些用户？如何和lastLogin列关联？