概述

• 从1、2讲，了解了逻辑意义上的数据库，以及如何写 SQL 来读写数据
• 接下来学习怎么样设计数据库管理系统 DBMS

课程大纲

• 关系数据库
• 存储
• 执行
• 并发控制
• 恢复
• 分布式数据库
• 杂项

基于磁盘的结构

• DBMS 假设主要的存储位置是在非易失性的磁盘
• 由 DBMS 的组件管理数据在易失性存储与非易失性存储之间的移动

存储的分层

访问时间

顺序存取 vs. 随机存取

• 非易失性存储上的随机访问往往比顺序访问要慢得多
• 用户的存取都是随机的，DBMS 希望把用户的随机存取最大化转换为顺序访问
  • 算法试图减少向随机页的写入，尽量让数据存储在连续的块（block）中
  • 一次分配多个页，即按区来分配。
    Allocating multiple pages at the same time is called an extent.

设计存储引擎的目标

• 允许 DBMS 管理容量超过可用内存容量的数据库
• 读/写磁盘是代价非常高昂的
• 随机对磁盘读写比顺序读写要慢得多，所以 DBMS 需要最大化顺序读写。

Disk-Oriented DBMS

• Disk
  • Database file：数据库以文件形式存在磁盘上
    • Diretory：文件开头，类似目录，把page映射为物理地址的作用
    • Page：
      • Header：数据头
      • Data
• Memory
  • Buffer pool：缓冲池，把需要用到的页缓冲到内存中，有限定大小

为什么不用 操作系统自带的 mmap

• DBMS 可以使用 mmap 来把文件的内容存储到程序的地址空间里，操作系统来负责把文件中的数据页移入、移出内存，所以 DBMS 不需要考虑。
  • mmap 可以提供一个虚拟内存，和实际硬盘是一样大的
  • 软件访问虚拟内存，假如软件请求 page 1，操作系统负责把文件中的 page1 加载到物理内存中，然后把虚拟内存链接到物理内存

• mmap 的问题

  • 假如物理内存都被填满了，而应用还需要请求新的页，那么淘汰掉哪一个页？
  • 如果多线程并发写， mmap 也有问题

• 操作系统也有针对这些问题提供方案

• DBMS 希望控制

  • 以正确的顺序把脏页刷到磁盘里
  • 特殊的预缓存情况，这样 执行器就不用等待特定的页加载到缓冲池中
  • 缓存替换策略
  • 进程、线程调度

数据库存储的两大关键问题

1. DBMS 如何在文件中存储数据库
2. DBMS 如何管理内存以及内存、磁盘间的数据移动

三个关键点

• File Storage
• Page Layout
• Tuple Layout

文件存储 File Storage

• DBMS 在磁盘上，用一个或多个文件，以特定的格式存储数据库
  • OS 不关心也不知道这些文件的内容
• 1980年代的 一些 DBMS 在原始存储（Raw Storage）上使用自定义的文件系统
  • 现在的一些商业 DBMS 还在这么干
  • 大多数新出来的 DBMS 不这么做了

存储管理器 Storage Managaer

• 存储管理器负责维护数据库的文件
• 把文件组织成页的集合
  • 跟踪数据读/写到页的过程
  • 跟踪可用的空间

页 Page

• 一个页就是一个固定大小的数据块

  • 页里可能存着元组、元数据、索引、日志记录...
  • 大多数系统对于页的使用都是固定的，比如存储索引的页不会用来存数据
  • 大多数系统需要页是自组织（self-contained）的，也就是说页的Header里标识了这个页的类型

• 每个页都有一个独特的标识符

  • DBMS 使用非直接的层来把page id 映射到物理位置

• 硬盘页

  • 最小能保证原子操作的单位

• 操作系统页（一般为 4kb）

  • 操作系统读写硬盘的最小单位

• 数据库页（512b ~ 16kb）

  • 数据库

堆文件 Database Heap

• 堆文件是一些无序的页，里面的元组也是无序存储的
  • 页需要有增删改查的功能
  • 必须支持对所有页的遍历
• 两种堆文件的组织形式
  • 链表 Linked List
  • 目录 Page Directory
• 需要元数据来跟踪，比如某一个页在磁盘的什么位置，哪一个页还有空闲空间

链表实现堆文件

• 第一个页是 Header，里面有两个链表，第一个链表，free page list，第二个链表 data page list

目录实现堆文件

• 维护一个目录，记录几号页在什么位置，记录每个页中的空闲 slot 数
• 需要保证目录页跟数据页的一致性

页布局

• 每一个页，都有一个头Header，里面记录了页内容的元信息

  • 页大小
  • 校验值 Checksum
  • DBMS Version
  • 事务可见性 Transaction Visibility
  • 压缩的信息 Compression Information

• 一些系统需要页是自解释（self-contained）的，也就是页需要告诉 DBMS 自己的类型

• 我们需要决定数据在页里怎么存储

  • 元组 Tuple-oriented
  • 日志 Log-oriented

简单的 Tuple 存储

• 记录已有 Tuple 页的数量，然后新插入的页，直接插入到已有页的末端
• 问题：
  • 假如删掉页2，出现碎片化，怎么维护？
  • 新插入页4到页2原来的位置，假如页4大小比页2占据的空间大，怎么办。而且这样可能会破坏顺序性

Slotted Pages

• 布局
  • Header
  • Slot Array
    • 存着Tuple的偏移量，第一个 slot 存着 第一个 tuple 的偏移量，第二个 slot 存着第二个 tuple 的偏移量
    • 假如 Tuple 3 被删掉，可以更改 slot[4] 的指针指向的地址
  • Tuples

Record ID

• DBMS 用来标识一个 tuple 的标识符
• 一般格式：page_id + offset/slot，几号页的第几个数据
• 应用不能依靠 record id 来查找数据

Tuple Layout

• 一个元组只是一些比特序列
• 由数据库来把这些byte序列转换为属性类型和值

Tuple Header

• Header
  • 每一个Tuple 都有一个 header，里面包含了元信息
    • 可见性信息（并发控制）
    • 为 NULL 值设置的 Bit Map，Header 中会有一些位来表示后面的数据是不是 NULL，一般有多少个数据，就用多少个位
• 不在 tuple 上存表结构相关信息

Tuple Data

• 按照列顺序来存数据

Denormalized Tuple Data

• SystemR 在 1970s 这么做了
• 一些 NoSQL DBMS 使用过这种思想