Lecture #06: Memory Management

CMU15-445
,

refer to Note

refer to Slide

1. Introduction

如何存储：

  • 我们的 pages 要存储在 disk 上的什么样的地方

快速操作：

  • 对于 DBMS 来说，在进行操作数据之前需要将所有的的数据从 Disk 先转移到 Memory 中才可以进行操作。
    image

image

2. Locks vs. Latches

image

3. Buffer Pool

Memory 中存储的是一个个固定大小的 pages。

其中的每一个记录称之为 frame

当我们需要一个 page 的时候，我们会立刻复制一个 frame。

Dirty pages 不会立刻写回。(Write-Back Cache)

image

Buffer Pool Meta-data

image

page table 是用来跟踪哪些 pages 在 memory 中。

通常还有一些信息也会被保存在 page table 中

  • Dirty Flag

  • Pin/Reference Counter

Dirty Flag 用来表示这个页是否被写过。

Pin/Reference Counter 是用来固定 frame 来确保该页面不会被放回到 disk 中。

page directory 是一个将 page id 映射到 page location 的一个映射。所有信息必须存放在 disk 上，以便 DBMS 可以找到。

page table 是一个将 page id 映射到 buffer pool 中的帧上的映射。这是一个 in-memory 的数据结构不需要存储在 disk 上。

Memory Allocation Policies

Allocation Policies

全局策略

  • 为所有的操作负责，确保全局最优

局部策略

  • 仅仅考虑当前的查询的效率而不考虑其对全局的影响

4. Buffer Pool Optimizations

Multiple Buffer Pools

通常 DBMS 不总是仅仅有一个 buffer pool

DBMS 维护多个 buffer pool 是为了多种目的 (i.e per-database buffer pool, per-page type buffer pool)。然后每个缓冲池可以针对每个存储在其中的数量进行定制本地策略。

主要有两种方式访问不同的buffer Pool

  1. Object id
    通过 Object Id 来识别不同的 buffer pool

  2. Hashing
    通过 hash page id 来识别不同的 buffer pool

Pre-fetching

DBMS 可以基于查询提前交换页面，特别适用于

  • 顺序查询

  • 索引查询


查询到 page1 的时候 buffer pool 就将接下来需要解析的加载到 buffer pool中


同样是可以提前加载

Scan Sharing(Synchornized Scans)

通常发生在多次查询同一个东西的时候。

如果第一个查询一张表，不久之后第二个也在查询同一张表，那么最终的情况会第二个查询会和第一个查询进行同步查询。在第一个查询结束后，第二个查询会补查漏掉的数据。

在 Q1 查询到了一半的时候 Q2 也执行了同样的查询

scan sharing_1

由于 Q1 已经查询了一段距离，在 Buffer pool 中重新载入 page0 是非常浪费的。那么我们可以和 Q1 一起查询。

scan sharing_2

在一起查询结束之后我们再去查询 Q2 剩下来的 page0-page2

如果启用这种策略进行查询到的话，那么最终的结果可能是不同的。因为我们的查询是无序的。对于一个顺序十分重要且确定的结构中，一般不会采用这种方式进行查询。

scan sharing_3

Buffer Pool Bypass

对于一些操作可能不会存储在 buffer pool 中，这样可以减少开销。

5. OS Page Cache

OS Page Cache

在 DBMS 中通常不会直接采用 OS 的的文件管理。

  • 减少 pages 的多次拷贝

  • 减少 page 的退出策略

  • 加强对 I/O 的控制

6. Buffer Replacement Policies

Buffer Replacement Policies

当 DBMS 需要将 buffer pool 里的 frame 给清除了，需要决定就近是哪个页退出。

所以 Buffer Replacement Policies 就是关于清除 frame 的算法。

它的主要目标是

  • 正确

  • 一致

  • 速度

  • 元数据的开销

Least Recently Used (LRU)

LRU

维护一个时间表来记录哪个 page 是最后被访问的，在需要置换 frame 的时候，将最后被访问的页面给置换出去。

CLOCK

CLOCK

clock 算法是 LRU 的一种近似的产物。它的好处是不再需要一张时间表来记录各个 pages 了，而采用 bit 的形式记录。

Clock 是，将所有的页面以某种顺序进行记录，并且该顺序是首位相连的。初始时，将所有的页都标记为 0 ，在某个页访问的时候，将该页的 bit 标记为一。在寻找需要置换的页面时，也将顺序的找下去，如遇到 page 的 bit 为 1 那么就将该 bit 置为 0 ， 如果该页的的 bit 为 0 ，那么则将该页置换下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
page_id clock_page() {

	static page_id ref =  0;
	
	for ( ; ; ref ++ ) {
		if(ref >= BUFFER_POOL_SIZE) ref = 0;
		
		if (bit[ref]) 
			bit[ref] = 0;
		else 
			return ref;
			
	}
	return -1;
}

Alternatives

不管是 LRU 还是 CLOCK 都对 sequential flooding 操作影响较深。

  • 一种顺序查询所有页的操作

  • 这种操作仅仅执行一次，并且不会再次进行访问

这就会导致一种结果，Buffer pool 里面存储的数据不会是接下来需要用到的数据。

为了减少这种情况的发生我们通常会采用 LRU-K 来进行置换。

LRU-K

追踪每个页面的最近 K 次访问。DBMS 根据这个记录来确定访问优先级。

Dirty Page

Dirty Page

对于非 Dirty Page 而言，只需要将 page 丢掉即可，而 Dirty Page 则需要写回到 disk 上以保持持久性。

为了避免这一现象，有一种策略是通过周期性扫描 buffer pool 中的 dirty pages 并将其写回 disk 中，这样就可以较为安全的移除 dirty pin flag 。

7. Other Memory Pools

Other Buffer Pools

Tasks

https://15445.courses.cs.cmu.edu/fall2022/project1/