CigaCase
0%

CMU15-445 2022Fall Lecture 3.4.5

发表于 分类于

Lecture 3,4,5: Database Storage & Storage Model

本章主要介绍了数据库的存储方式以及几种常见的存储模型

Disk_Oriented DBMS

  • 数据库保存在磁盘上，按照页（page）作为单元进行划分，第一页为目录页，如果想要对数据库进行操作，则首先需要将数据库中的page调度到内存中
    • 通过一个保存在内存中的缓冲池（buffer pool）来管理数据在磁盘和内存之间的移动
    • DBMS有一个负责查询的执行引擎，缓冲池将page带入内存，并且给执行引擎返回一个指向该page的指针，以确保在执行引擎在对该page进行操作的时候，此page的确存在于该位置

DBMS vs OS

DBMS的一个高级设计目标就是：创造一个容量远大于内存的数据库，与此同时并不希望过于频繁地访问数据库，因为访问磁盘的代价很大
这就类似于操作系统中的虚拟内存，保证磁盘中的地址空间能够映射到内存中
提起磁盘和内存之间数据的迁移，很容易想起mmap，的确曾经有很多DBMS选择使用mmap来执行，然而实际上是会造成一些问题的

  1. DBMS并不知道哪些page在内存中，而mmap在遇到page fault时会阻塞进程
  2. OS可以在任何时刻写回脏页，然而OS并不知道哪些page需要在其他page之前写回磁盘，这会造成并发控制方面出现问题
    尽管有办法解决这方面的问题，但是从性能和安全性两方面考虑，并不建议由操作系统来完成这一任务
    因此根据Andy所言，由DBMS自己来实现数据的控制是一个更好的选择

DataBase Storage

File Storage

DBMS使用自己独有的编码形式将数据库作为单个文件或者多层次文件保存在磁盘中，OS对此一无所知
DBMS的存储管理器负责管理数据库的文件，它会将这些文件作为一个page的集合，并且追踪哪些数据被读写、这些page有多少可用空间

DataBase Page

DBMS将数据库文件中固定大小的数据块称为页（page），可以参考OS中的虚拟内存，页面可以包含不同的数据结构（tuple、indexes、log等）
在大多数DBMS中，一个page会被要求只能存储一种类型的数据

例如page1只能存储tuple，page2只能存储日志
所以，每个page都会被赋予⼀个唯⼀的内部标识符，系统会生成属于page的ID。之后，就会有一个indirection层。indirection层允许将⼀个page ID映射到某个物理位置，即某个文件中的某个位置（类似于一个字典映射，其实就是记录⼀个相对位置，方便文件整体移动后，只要知道整体文件的初始位置，我依然可以通过该相对位置（即page ID）找到某个文件某个位置的数据所对应的page）。这样的话，就可以支持磁盘的压缩或者使用另一块磁盘而不改变page ID。

DataBase Heap

关于page之间是如何进行存储的——
堆文件组织是是一个无序的页面集合，是从磁盘上查找我们想要的page地址的一种方法
DBMS可以通过使用页面的链接列表或页面目录在磁盘上找到一个给定的页面ID：

  1. Linked List：
    是一种顺序存储（顺序存储并不意味着有序），这是一种很容易想到的存储方式，然而弊端也是显然的：链表的查询时间复杂度为O（n），效率远不及hash
  2. Page Directory：
    可以类比书的目录，每次查询只需要从page directory中获取目标page的偏移量即可，然而弊端在于：必须时刻保证目录与实际page信息的同步。如果往某个page中写入数据，此时page满了，但系统也崩溃了，那么目录中的信息是相对滞后的，在重启系统之后需要有对应策略来重新扫描以维护信息的一致性；如果数据量很大，在极端条件下可能始终无法统一

Page Layout

关于page中的信息是如何存放的——
每一个page都有一个页头（header）来存放该page的，譬如页面大小、DBMS版本号之类的相关信息，这些信息被称为元数据（meta data）
一般来说数据在page中有2种常见的存储方式：tuple-oriented和log-structured

  1. tuple storage
    一种朴素的思想就是将tuple以数组的方式存放，同时header记录page的信息，但这是一个strawman idea：因为当我们删除其中的一个tuple时，会产生内部碎片，导致文件的不连续；如果tuple的长度是不定长的话，这个问题会更加显著。同时tuple的查找也只能够顺序遍历，所以并不推荐
  2. slotted storage
    page中除了header以外还有两种数据结构，一种是slot，一种是tuple
    其中slot从header之后顺序存储，每个slot都保存了对应的tuple在该page中的偏移量；而tuple本身是从page的末尾开始从后往前循序存储。虽然必然会出现一定的内部碎片，然而这是为了处理变长tuple不得不做出的牺牲，当然有些数据库支持对于内部碎片的再整理
    对于slotted storage，一个tuple的查询需要其所在的page_id和slot_id
  3. log-structured storage
    slotted storage依然有很多问题没有能够解决：例如删除tuple的时候会留下空隙、必须从磁盘中读取整个page来获取其中的一个tuple、随机读取的效率很低
    由此诞生了log-structured storage，这是一种只允许创建新数据而不允许覆盖已有数据的存储方式，DBMS中只会存放日志记录
    • 将数据库如何被修改的记录存储到文件中（放入和删除）。每条日志包含tuples的唯一标识符
    • 要读取一条记录，DBMS会从最新的到最旧的逆向扫描日志文件，并 “重新创建 “这个 tuple。
    • 写的快，读的可能慢。磁盘写入是连续的，现有的页面是不可改变的，这导致了随机磁盘I/O的减少。
    • 在append-only的存储上工作得很好，因为DBMS不能回溯并更新数据。
    • 为了避免长时间的读取，DBMS可以有索引来允许它跳到日志中的特定位置。它还可以定期地压缩日志。（如果它有一个tuple，然后对其进行了更新，它可以将其压缩到只插入更新的tuple）
    • 由于不再需要时间信息，数据库可以将日志压缩到一个按id排序的表中。这些被称为分类字符串表（SSTables），它们可以使tuple搜索非常快。
    • 紧凑化的问题是，DBMS最终会出现写入放大的情况。（它一次又一次地重写相同的数据）

Tuple Layout

关于tuple的具体结构——
其实通过sql的创建table的句式就可以观察出来，tuple本质上是一个字节的序列，DBMS的工作就是将字节的序列翻译成不同的属性和值

  • Tuple Header：包含了tuple的元数据
    • DBMS的并发控制协议的可见性信息。关于哪个事务创建/修改了该元组
    • NULL值的位图
  • Tuple Data：数据的实际属性
    • 属性通常按照你创建表时指定的顺序存储
    • 大多数DBMS不允许一个tuple超过一个页面的大小
  • Unique Identifier
    • 数据库中的每个tuple都被分配一个唯一的标识符
    • 一般是：page_id + （offset or slow）

Storage Model

数据库并没有规定应该按照哪一种模型来保存数据，然而在实际操作中，storage model的影响是很大的

OLTP（On-line Transaction Processing）

意思是从外界拿到数据后，只会将其放入数据库中进行简单的查询或者更新，一个具体的例子就是网购的购物车，将购物车中的东西删除、或者新增东西到购物车里，tuple的改变是很小的

OLAP（On-line Analytical Processing）

从数据库中的到数据后不会修改原有的数据，而是希望能够从数据中挖掘出更加深入的信息，例如数据挖掘、数据分析之类的工作，某种意义上OLAP是只读的，并且join的操作很多

以上两种不同的数据库使用方式就导致诞生了各种数据的存储模型：

  1. N-ary Storage Model（NSM）
    简单来说就是一个tuple会保存表中的所有属性，例如（姓名，性别，生日，年龄）作为一个tuple
    这是一种典型的row storage，并且利好OLTP：因为内容都是顺序排列的，存储粒度足够小，我们可以只关心自己想要的数据
    但是对于OLAP而言，NSM是灾难性的，显然我们的查询会涉及到很多我们并不想要的数据
  2. Decomposition Storage Model（DSM）
    这是一种典型的列存储模型，他将每一个tuple按照属性进行拆分存储，例如姓名作为一个tuple，性别作为第二个tuple……
    对于列存储而言，每次查询可以只读取某几个属性的值，这对于OLAP是有利的