CMU15-445 Database Storage

Image.png

(图片来自CMU15-445课件)

概述

volatile，random Access，字节寻址

non-volatile,sequential Access，块寻址能力，即使只是需要64bit的数据，也必须去获取存储该数据的整个块（4KB）。

面向磁盘型数据库管理系统： 数据库的主要存储位置在磁盘。意味着每次执行查询，所要访问的数据都不在内存中。涉及到I/O。

storage hierarchy：

读一本书：

L1-> 书在桌上

L2-> 输在隔壁房间

L3-> 书在图书馆

基于从磁盘读写数据受到磁盘读写速度的影响，主要关注点在如何谨慎地最小化从磁盘读写数据的影响。

设计DBMS的目标是：

在数据库系统中达成的目标是给应用程序一种错觉，我们能提供足够大的内存将整个数据库都存入内存。

即即使存储的数据超过了可用的内存量，也不必每次停下来进行数据的读写。

Disk -Oriented DBMS:

IMG_20210925_193029_edit_439710923499569.jpg

既然会涉及到从磁盘读取数据，为什么不考虑使用OS去进行控制？

• OS：本质上是从磁盘上获取文件，告知操作系统，将文件页面映射到需求进程的地址空间中，然后 就可以对这些内存地址进行读写。
• 如果使用操作系统，dbms就丧失了对文件从磁盘到内存移动的控制权。（是否是如果在读写数据的步骤中发生了错误，导致数据的丢失或其他错误，数据库无法得到相应的消息？）
• 同时，使用OS的话，在磁盘读取数据到内存中，发生缺页中断，进程本身会进行等待，则导致此时数据库也进行等待。因此考虑到降低停顿的时间，也得放弃使用OS来进行数据从磁盘到内存的读取。

！！！OS不是你的朋友

database storage层要解决的问题：

*

* 问题一：DBMS如何在磁盘上表示数据库？

* 问题二：DBMS如何管理它的内存以及磁盘上数据的存取？

问题一：DBMS如何在磁盘上表示数据库？

DBMS在磁盘存储数据库的形式就是文件（os的文件系统中的文件），因此可以利用OS提供的API进行文件的读取。

第一个出现的组件：存储引擎（维护磁盘上的DB文件）。

shim层：

存储引擎会将所有的文件组织成page集合。本质上，一个page就是一个固定大小的数据块。一些DBS会要求page是self-contained，即每个page的所有信息，其自身都知道该如何去解释和理解。

每个page都会被赋予一个唯一的内部标识符。

indirection层：

一些DBMS有一个indirection layer，该层允许我们将一个page ID映射到某个集合中一个文件的某个位置（记录的是一个相对位置，方便文件整体移动后，能够快速定位该page），磁盘移动或更换都不会改变page ID。

DBMS中三个page概念：

• HardWare Page：usually 4KB，原子的，即每次write或flush，存储设备只保证每次写入4KB时时原子的。
• OS Page：4KB，可以从存储设备中去除数据放入内存。
• Database Page：512B-16KB

不同的数据库用不同的方式管理磁盘上文件中的pages，是一个trade-off。

Heap File Organization（最常见的）：

• 在storag manager的底层，并不关心page中有什么，Database中的heap文件是一个无序的page集合，并且tuple的存储顺序也是随机的。
• 会提供堆page进行读写和访问的API
• 也会额外使用一些元数据（meta-data）来跟踪有哪些page以及哪些page是空余的。
• heap file的表示：
  • linked list：Header page holds pointers to to a list of free pages and a list of data pages. 但是找数据的话，必须循序扫描
  • Page directory：专门维护一个page用于直接跟踪data page在file中的位置

page laye

每个page在头部会包含一些关于该page某些信息的meta-data，包括：

page size、checksum、DBMS version、Transaction Visibility、Compression Information、Some systems require pages to be self-contained (e.g oracle).

存储data的方式：

• slotted-pages

1-tupleStorage.jpg

2-tupleStorage.jpg

• log-structured:
  • 不将所有的tuple都存放在page中，而是去存储如何创建的以及修改的信息，就如同日志记录一样。