CMU15445 Lecture 3&4 Database Storage

本节讲述DBMS如何在磁盘文件中保存数据

回顾

在一个关系型数据库中，数据以表的形式呈现，每个表有多个列，每个列有一个唯一的名字，表的每一行表示一个单位的信息（one piece of information）

数据抽象

一个系统想要可用，它必须能够高效的取数据，因此在数据库中，数据库开发者用了一些复杂的数据结构去表示数据，由于用户并没有经过专业的训练，所以数据库开发者们，通过构建好几层抽象来达到隔离复杂度的目的，以此简化用户与系统的交互

物理层

最底层的抽象，用来描述数据实际上被存贮在哪里，比如磁盘中。物理层细致的描述了复杂的底层数据结构，比如表中的数据可以被描述为一块连续的内存字节。

逻辑层

更高的一层，其描述了什么数据被存储在数据库中，以及这些数据之间有什么联系，因此只需要一些相对简答的数据结构就可以。尽管实现逻辑层的这些简单数据结构可能需要复杂的物理层结构，但是逻辑层的用户不需要感知这些复杂度，这被叫做physical data independence,DBA们必须用逻辑层的抽象来决定将什么数据放入数据库中。比如说，每一条记录由类型定义所描述，记录类型之间的联系也被描述于逻辑层。可以说用SQL工作就是说工作在逻辑层。

视图层

最高层的抽象，其描述了数据库中的部分数据。如果数据库有大量繁杂的数据，那么即使是使用简单数据结构的逻辑层，也会非常复杂。很多用户只需要使用数据库系统中的一部分数据，视图层抽象的存在简化了用户与系统的交互。系统提供了很多视图对同一个数据库。比如说，电脑应用的用户（大学文职人员）能够看到学生的信息，并且看不到这些信息的数据类型，还只能看一部分数据，比如说他们不能够看到教授的工资。

数据模型的一大重要特点是它将底层实现的复杂性封装了。数据库系统允许应用开发者基于数据模型的抽象，去存取数据，数据库系统会将这些抽象操作转化为实际的底层操作。

存储

15-445将专注于基于磁盘的DBMS架构disk-oriented architecture，其假定数据存储在非易失磁盘(non-volatile disk)上。

  • 易失性设备
    • 易失意味着,如果你拔掉电源,那么数据就会丢失
    • 易失存储支持快速,字节寻址,随机访问,这意味着你可以跳到任一字节地址,去获取数据
    • 15-445中将易失存储称为memeory
  • 非易失性设备
    • 非易失性设备意味着断电后,数据不会丢失
    • 块寻址,这意味着为了去获取某个字节的数据,得把一整页装载进内存
    • 非易失性设备通常适合于连续访问(同时读连续几块数据)
    • 15-445中将非易失性设备称为disk,不会对HDD(Hard Disk Drive/spinning hard drives)与SSD(solid-state storage)做很大的区分

系统假定数据库存储在磁盘上,DBMS负责将数据在非易失性设备与易失性设备之间移动,因为系统不能够直接在磁盘上处理数据,15-445将专注于减少磁盘的延迟

基于磁盘的DBMS总览

数据库文件被组织成页,第一页是目录页,为了去处理数据,DBMS需要把数据从磁盘中放到内存,它通过在memory中建立一个buffer bool,DBMS有一个执行引擎(execution engine)用于执行查询操作

DBMS vs OS (为什么有了OS还需要DBMS?)

设计DBMS的目标是使得数据库可以使用超过内存大小的字节数,我们想要DBMS可以在等待磁盘数据的同时,处理其他的查询,这个目标于OS中的虚存类似
而实现虚存的一种手段是mmap
当mmp遇到页中断时,进程将会被阻塞:

  • 在DBMS,当你需要去写数据,你永远也不要去使用mmap
  • DBMS对于数据库数据与查询知道的更多,并且能够更好的控制数据库
  • OS并不可靠
    虽然可用通过madvise,mlock,msync等函数去优化OS的行为,但是DBMS任旧时更好的选择

文件存储

DBMS一般将数据库存储为文件在磁盘中,可以是层次文件,或则是一个文件(SQLite)
OS只当它们是普通文件，并不知道如何解读这些文件,但是DBMS知道如何去解析它们的内容

DBMS的storage manager负责管理数据库文件,它将文件表现一些存储页,它会记录跟踪什么数据被写入了页中,什么数据被读取过,以及页的空闲容量

数据库的页

页的定义

DBMS将database的多个文件存储在固定大小的被称作页(page)的数据块,页中可以包含不同的数据,比如tuple,index等,大多数系统不会讲这些不同类型的数据混在一页里,一些系统要求页是自包含的self-contained,也就是说页的所有数据(包括结构信息,比如第一列是id,第二列是num等等)

数据库页寻址

每一个页有一个唯一的标识符,如果一个数据库是一个单一文件,那么page id就是文件偏移

大多数DBMS有一个间接层(indirection layer),它可以讲page id映射成一个文件路径与一个偏移,当上层抽象获取到一个page id时,storage manager会将page number转为一个文件与文件偏移,

大多数DBMS使用固定大小的页,是为了避免用于支持可变大小的页的工程开销(engineering overhead)

保证数据库页与磁盘页一致

在DBMS中,有三种页的概念:

  • 硬件页(一般是4KB)
  • OS页(一般4KB)
  • 数据库页(1-16KB)
    存储设备可以保证写一个硬件页是原子的,所以如果数据库页大于硬件页,DBMS需要施加额外的手段去保证写数据库页是原子的

数据库堆(Database Heap)

定义

堆文件(heap file)组织是一种DBMS用来找到一个页在磁盘的位置的方法,heap file 是一个无序的page集合

heap file 分类

DBMS可以通过给定的page_id找到页,有两种组织管理heap file的page的方法,:

  • Linked List,page管理模块维护一个header page其中有两个指针,空闲链表指针与数据链表指针,每个页会维护跟踪它自己的空闲slot数量;但是Linked List有一个缺点,就是需要线性查找

  • Page Directory,page管理模块维护一个目录,该目录页还会跟踪每个页的空闲空间

页的布局

页头部

每个页的头部会存储页的内容的元数据:

  • 页的大小
  • 检验和(用于网络传输校验)
  • DBMS版本号
  • 事务可见性
  • 压缩信息

页的布局方案

一个猜想的方案是:每次都追加tuple,但是这样会有两个问题:删除tuple,会出现空缺;tuple中有可变长数据,如何处理
两种真正可行的方案:

  • slotted pages
    • 新增记录时：在 slot array 中新增一条记录，记录着改记录的入口地址。slot array 与 data 从 page 的两端向中间生长，二者相遇时，就认为这个 page 已经满了
    • 删除记录时：假设删除 tuple #3，可以将 slot array 中的第三条记录删除，并将 tuple #4 及其以后的数据都都向下移动，填补 tuple #3 的空位。而这些细节对于 page 的使用者来说是透明的
    • 处理定长和变长 tuple 数据都游刃有余
    • 目前大部分 DBMS 都采用这种结构的 pages。
  • Log-Structured
    • 只是存储记录的变化
      • Insert存储一整个tuple
      • Delete标记tuple为被删除
      • Update包含被修改的属性的变化值
    • 但是读一个记录,需要扫描log file,用来'recreate'tuple
    • 写很快,但读很慢
    • 对于只需要进行追加操作的存储很奏效,因为这种DBMS不需要回退以及跟新数据
    • 为了避免读的时间长,可以建立索引,也可以周期性的压缩log,压缩log会有写放大的问题它会写同样的数据一遍又一遍

tuple布局

实质

一个tuple实际上是一个字节序列.DBMS需要将这些字节序列按照属性的类型与值来解析

tuple 头部

  • DBMS的并发控制协议的可视信息,也就是记录'哪个事务创建,修改了该tuple',还有tuple 粒度的权限和并发控制
  • Bit Map for NULL value,也就是头部中又一些二进制位,对于tuple中的NULL做标记
  • 注意tuple头部不会存储table的schema,schema一般是存在system catalog中

tuple的数据

  • 数据一般是按你创建的表中的顺序存储的
  • 大多数DBMS不允许一个tuple的大小超过一个页

唯一标识符

  • 每一个在数据库中的tuple都有一个唯一标识符
  • 大多数情况下都是:page_id + (offset 或者 slot)
  • 这些tuple的唯一标识符对于应用程序而言是无意义的,应用程序处于视图层

非规范化tuple的数据

定义

物理上denormalize相关联的tuple,也就是pre-join,把它们存储在同一个页

  • 好处是,可以减少IO负载,读起来快
  • 坏处是,更新起来慢,更新操作更复杂,如果要更新一个tuple,DBMS需要给一个tuple更多的空间,该一个表的数据,写两个表的数据

数据表示

System Catalog

在文件中，一个 tuple 无非就是一串字节，而如何解读这些字节中隐含的数据类型和数据本身，就是 DBMS 的工作。DBMS 的 catalogs 保存着数据表的 schema 信息(包括数据类型与值的顺序)，有了这些信息，DBMS 就能够解读 tuple 数据

类型 实现
INTEGER/BIGINT/SMALLINT/TINYINT C/C++ Representation
FLOAT/REAL vs. NUMERIC/DECIMAL IEEE-754 Standard / Fixed-point Decimals
VARCHAR/VARBINARY/TEXT/BLOB Header with length, followed by data bytes, may also contain a checksum for the data
TIME/DATE/TIMESTAMP 32/64-bit integer of (micro) seconds since Unix epoch

FLOAT/REAL/DOUBLE vs. NUMERIC/DECIMAL

float, real, double 类型的数字按照 IEEE-754 标准存储，它们都是 fixed-precision，在 range 和 precision 上作了取舍，无法保证精确度要求很高的计算的正确性，如：

#include 

int main(int argc, char* argv[]) {
    float x = 0.1;
    float y = 0.2;
    printf("x+y = %.20f\n", x+y)
    printf("0.3 = %.20f\n", 0.3)
}

// =>
// x+y = 0.30000001192092895508
// 0.3 = 0.29999999999999998890

如果希望允许数据精确到任意精度（arbitrary precision），则可以使用 numeric/decimal 类型类存储，它们就像 VARCHAR 一般，长度不定，以 Postgres 的 NUMERIC 为例，它的实际数据结构如下所示:

typedef unsigned char NumericDigit;
typedef struct {
    int ndigits;           // # of Digits
    int weight;            // Weight of 1st Digit
    int scale;             // Scale Factor
    int sign;              // Positive/Negative/NaN
    NumericDigit * digits; // Digit Storage
} numeric;

Large Values

大部分 DBMSs 不允许一个 tuple 中的数据超过一个 page 大小，如果想要存储这样的 large values，DBMS 通常会使用 overflow/TOAST page：

external file


DBMS无法保证external file被外部操作修改,以及无法保证事务间的隔离

OLAP&OLTP

数据库的应用场景大体可以用两个维度来描述：操作复杂度和读写分布，如下图所示：

坐标轴左下角是 OLTP（On-line Transaction Processing），OLTP 场景包含简单的读写语句，且每个语句都只操作数据库中的一小部分数据，举例如下：

SELECT P.*, R.*
  FROM pages AS P
 INNER JOIN revisions AS R
    ON P.latest = R.revID
 WHERE P.pageID = ?;
 
UPDATE useracct
   SET lastLogin = NOW(),
       hostname = ?
 WHERE userID = ?
 
 INSERT INTO revisions
 VALUES (?,?...,?)

在坐标轴右上角是 OLAP（On-line Analytical Processing），OLAP 主要处理复杂的，需要检索大量数据并聚合的操作，举例如下：

SELECT COUNT(U.lastLogin)
       EXTRACT (month FROM U.lastLogin) AS month
  FROM useracct AS U
 WHERE U.hostname LIKE '%.gov'
 GROUP BY EXTRACT(month FROM U.lastLogin);

通常 OLAP 操作的就是 OLTP 应用搜集的数据

Data Storage Models

Relational Data Model 将数据的 attributes 组合成 tuple，将结构相似的 tuple 组合成 relation，但它并没有指定这些 relation 中的 tuple，以及 tuple 的 attributes 的存储方式。一个 tuple 的所有 attributes 并不需要都存储在同一个 page 中，它们的实际存储方式可以根据数据库应用场景优化，如 OLTP 和 OLAP。

目前常见的 Data Storage Models 包括：

  • 行存储：N-ary Storage Model (NSM)
  • 列存储：Decomposition Storage Model (DSM)

NSM

NSM 将一个 tuple 的所有 attributes 在 page 中连续地存储，这种存储方式非常适合 OLTP 场景，如下图所示：
DBMS 针对一些常用 attributes 建立 Index，如例子中的 userID，一个查询语句通过 Index 找到相应的 tuples，返回查询结果，流程如下：
但对于一个典型的 OLAP 查询，如下图所示：

尽管整个查询只涉及到 tuple 的 hostname 与 lastLogin 两个 attributes，但查询过程中仍然需要读取 tuple 的所有 attributes。

总结一下，NSM 的优缺点如下：

  • Advantages
    • 高效插入、更新、删除，涉及表中小部分 tuples
    • 有利于需要整个 tuple （所有 attributes）的查询
  • Disadvantages
    • 不利于需要检索表内大部分 tuples，或者只需要一小部分 attributes 的查询

DSM

DSM 将所有 tuples 的单个 attribute 连续地存储在一个 page 中，这种存储方式特别适用于 OLAP 场景，如下图所示：

这时候，就可以优雅地处理 OLAP 查询浪费 I/O 的问题：

由于 DSM 把 attributes 分开存储，也引入了新的问题，比如：
如何跟踪每个 tuple 的不同 attributes？可能的解决方案有：

  • Fixed-length Offsets：每个 attribute 都是定长的，直接靠 offset 来跟踪（常用）
  • Embedded Tuple Ids：在每个 attribute 前面都加上 tupleID

    DSM的优缺点:
  • Advantages
    • 减少 I/O 操作
    • 更好的查询处理和数据压缩支持
  • Disadvantages
    • 涉及少量 tuples、多数 attributes 的查询低效

参考

note3
note4

公开课数据库CMU15445

相关

mysql数据库死锁的产生原因及解决办法

【数据库】快速安装 SQL Server Express

关于SQL递归查询在不同数据库中的实现方法

GraphX 在图数据库 Nebula Graph 的图计算实践

主流开源分布式图数据库 Benchmark

图数据库 Nebula Graph 的安装部署

图数据库 Nebula Graph 是什么

Windows安装SQL Server数据库

SQL Server 维护计划实现数据库备份（Step by Step）(转)

mysql查出来的时间跟数据库相差13/14小时

Gin中记录Gorm数据库表生成-查询使用

如何用时序数据库 CTSDB 与 TARS 结合，解决海量监控数据难题

标签