15445

发表于 更新于 分类于 阅读次数：

15445 是 一门 数据库管理系统的设计与实现 的课程。

课程大纲：

  • Relational Databases
  • Storage
  • Execution
  • Concurrency Control
  • Recovery
  • Distributed Databases
  • Potpourri

关系模型关系代数

存储1

面向磁盘的数据库，所有数据都存储在磁盘中。

mmap 不要用在数据库存储中。

如何将数据存储在磁盘上 ？

需要暴露那些 API ？

  1. 如何表示磁盘上文件中的数据 ？

  2. 如果管理内存和磁盘之间的数据移动。（buffer pools）

第一个问题

1
2
3
File Storage
Page Layout
Tuple Layout

首先 如何将 数据库组织在 一系列 page 中。

然后 如何将 这些 page 保存在文件中

然后 这些 page 中的 tuple 是什么样的

1
2
3
Storage Manager 负责维护磁盘上的文件。
这些文件为 page 的 集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
database PAGES

一个 page 是一个固定大小的数据块
page 可以包含 tuples，meta-data，indexes，log records。任何东西。

有的数据库要求 page 元数据和数据保存在一起，这样即使丢了一个page 也不会影响其他page(oracle)
indirection 层 运行将 page id 映射到文件中的某一个位置。
page directory 记录page 在哪里


hardware page（4k） 执行原子写入存储设备的最底层的东西. 对磁盘进行 write和flush操作，
										存储设备只能保证每次写入4kb时是原子的
OS page （4k）
database page （512b - 16 K）

对磁盘进行 write 和 flush 只能保证 4kb 是原子的。
1
2
3
4
5
6
page storage architecture
不同数据库管理 page 文件使用不同的方式

HEAP FILE
Sequential/Sorted FILE
hashing File

HEAP FILE 无序的

1
2
3
4
5
6
7
8
9
10
11
12
13
提供操作page 的函数
create
get
write
delete
  
迭代page   
iterating
  
元数据表示 page 是否有空间，有那些 page
  
两种方式表示 heap file
  链表（没人用）、page目录

该如何表示page 存储架构?

最常⻅的方式是使用Heap File Organization.

数据库中的 heap 文件是一个无序的 page 集合。

用 page 目录来表示page 对应的位置。

更新数据和 page 目录的时候，有可能会崩溃，需要确保重建数据库的时候，能准确无误。

每个 page 的 header里面有 page 大小，checksum，数据库版本之类的东西。

当新版本发布时候，可以判断根据不同版本来解析page。

在一个page中，我们可以通过两种不同的方式来表示数据

面向 tuple 的方式 和 log-structured 的策略

page header 后面有个 slot 数组 ，表明 tuple 数据。

page header 里面记录有条 tuple （没人这么干）

一个page 里都是相同 格式的 tuple。如果有碎片，需要 vaccum 进行整理碎片

tuple id 一般由 page id 加 slot 组成。

会有元数据记录 tuple 的组成。为了读取。

1
2
3
4
5
6
7
8
9
10
11
12
create table r(id int primary key, val varchar(6));
insert into r values(101,'aaa'),(102,'bbb'),(103,'ccc');
select r.ctid, r.* from r;

-- protgres ctid 表示了数据的位置。

delete from r where id = 102;

insert into r values(104, 'ddd'); 会在后面追加。

--  pg 的 vacuum 会整理page。

存储2

lsm tree 型数据库

优势，速度快。追加

劣势，查找慢。(压缩，建索引 提高查找速度)

1
2
3
Data Representation
System Catalogs
Storage Models

数据类型，decimal。大多数情况下，page的大小是固定的。

如果一个 page 放不下数据的话。使用 overflow page。 通过一个指针，指向存数据的位置。

postgres 中叫做 TOAST。 还有一种是放在 外部文件中。

区分 olap 和 oltp

buffer pool Manager

如何将磁盘中的数据库文件 或者 page 放到内存中

什么时候将 page 读入内存，什么时候写出到磁盘。

malloc 一块内存，分成固定大小的 chunk，叫做 frame。

page table 用来跟踪内存(pool)中有哪些 page。必须是线程安全的.

通过page table 和 page id 就可以定位到 内存中 的 特定page

每个 page 都需要 额外的 元数据 来表示 page 发生的变化。page修改前， 需要写日志。

1
2
Dirty Flag   (page 是否被修改)
Pin/Reference Counter  (引用该 page 的线程数，这样就不想写到磁盘中)
1
2
3
4
Locks:
	保护数据库中的逻辑内容，
Latches:
	保护内部数据或者线程

page catalog 记录page 在数据库的文件的什么位置。需要持久化。

page table 记录 buffer pool （内存）中 page 的位置，不需要持久化。

buffer pool optimizations

1
2
3
4
Multiple Buffers Pools
Pre-Fetching
Scan Sharing
Buffer Pool Bypass

多种策略：

每个表一个 buffer pool。例如一个 buffer pool 处理索引，一个处理表。这样可以减少冲突。

预取，提前把可能要读的数据放到内存中。

查询共享，跟结果缓存不一样，结果缓存要求查询必须一样。两个查询要扫描相同的数据。

不使用 操作系统的 缓存，一般使用 direct_io。posgtresql 是唯一一个依赖操作系统缓存的。

fwrite 不是真正的写到磁盘，只有调用 sync 才会写。

替换策略

LRU 算法 LRU 的变体clock；

不跟踪时间戳，跟踪每个 page 的标志位。(在检查过后，这个page 是否被访问过。)

环形 buffer，然后有个指针可以转，来检查标志位是 1还是 0。

如果标志位是 0.那么自从上次检查过后，page没有被访问过。可以移除。

优化 ：

  1. LRU-K，访问达到 k 次的才会被移除。

  2. 多个buff er池

  3. priority hints(优先级提示)

如何处理 dirty pages ？

page 上有一个 dirty bit 标志是否有 query 对他进行了修改。

其他内存池：

1
2
3
4
5
sorting + join
query caches
maintenance buffers
log buffers
dictionary buffers

project 1s

hash table

  • hash functions
  • Static Hashing Schemes
  • Dynamic Hashing Schemes

hash functions

1
2
3
4
5
6
CRC-64 (1975)
MurmurHash (2008)
Google CityHash (2011)
FaceBook XXHash (2012)   ---- 最好
Google FarmHash (2014)