本系列为 CMU 15-445 Fall 2022 Database Systems 数据库系统 [卡内基梅隆] 课程重点知识点摘录,附加个人拙见,同样借助CMU 15-445课程内容来完成MIT 6.830 lab内容。
上节中提到,DBMS 的磁盘管理模块主要解决两个问题:
本节将讨论第二个问题。管理数据在内存与磁盘之间的移动又分为两个方面:空间控制(Spatial Control)和时间控制(Temporal Control)
Spatial Control
Temporal Control
整个 big picture 如下图所示:
本节的提纲如下:
DBMS 启动时会从 OS 申请一片内存区域,即 Buffer Pool,并将这块区域划分成大小相同的 pages,为了与 disk pages 区别,通常称为 frames,当 DBMS 请求一个 disk page 时,它首先需要被复制到 Buffer Pool 的一个 frame 中,如下图所示:
同时 DBMS 会维护一个 page table,负责记录每个 page 在内存中的位置,以及是否被写过(Dirty Flag),是否被引用或引用计数(Pin/Reference Counter)等元信息,如下图所示:
当 page table 中的某 page 被引用时,会记录引用数(pin/reference),表示该 page 正在被使用,空间不够时不应该被移除;当被请求的 page 不在 page table 中时,DBMS 会先申请一个 latch(lock 的别名),表示该 entry 被占用,然后从 disk 中读取相关 page 到 buffer pool,释放 latch。以上两种过程如下图所示:
Locks:
Latches:
总体而言,Locks和Latch在数据库管理系统中扮演着不同的角色。Locks用于提供更细粒度的并发控制和隔离,用于事务对数据库对象的独占访问。而Latch则用于保护内部数据结构的一致性,提供基本的互斥访问。
page directory:
page table:
为了减少并发控制的开销以及利用数据访问的局部性,DBMS 可能在不同维度上维护多个 Buffer Pools:
DBMS 可以通过查询计划来预取 pages,如:
Scan Sharing 技术主要用在多个查询存在数据共用的情况。当两个查询 A, B 先后发生,B 发现自己有一部分数据与 A 共用,于是先共用 A 的 cursor,等 A 扫完后,再扫描自己还需要的其它数据。
当遇到大数据量的 Sequential Scan 时,如果将所需 pages 顺序存入 Buffer Pool,将造成后者的污染,因为这些 pages 通常只使用一次,而它们的进入将导致一些可能在未来更需要的 pages 被移除。因此一些 DBMS 做了相应的优化,在这种查询出现时,为它单独分配一块局部内存,将其对 Buffer Pool 的影响隔离。
大部分 disk operations 都是通过系统调用完成,通常系统会维护自身的数据缓存,这会导致一份数据分别在操作系统和 DMBS 中被缓存两次。大多数 DBMS 都会使用 (O_DIRECT) 来告诉 OS 不要缓存这些数据,除了 Postgres。
当 Buffer Pool 空间不足时,读入新的 pages 必然需要 DBMS 从已经在 Buffer Pool 中的 pages 选择一些移除,这个选择就由 Buffer Replacement Policies 负责完成。它的主要目标是:
维护每个 page 上一次被访问的时间戳,每次移除时间戳最早的 page。
Clock 是 LRU 的近似策略,它不需要每个 page 上次被访问的时间戳,而是为每个 page 保存一个 reference bit :
二者都容易被 sequential flooding 现象影响,从而导致最近被访问的 page 实际上却是最不可能需要的 page。为了解决这个问题,又提出了 LRU-K 策略。
sequential flooding:
LRU-K 保存每个 page 的最后 K 次访问时间戳,利用这些时间戳来估计它们下次被访问的时间,通常 K 取 1 就能获得很好的效果。
DBMS 针对每个查询做出移除 pages 的限制,使得这种影响被控制在较小的范围内,类似 API 的 rate limit。
PostgreSQL(通常称为Postgres)维护着一个小的环形缓冲区,该缓冲区是每个查询私有的:
有时候 DBMS 知道每个 page 在查询执行过程中的上下文信息,因此它可以根据这些信息判断一个 page 是否重要。
移除一个 dirty page 的成本要高于移除一般 page,因为前者需要写 disk,后者可以直接 drop,因此 DBMS 在移除 page 的时候也需要考虑到这部分的影响。除了直接在 Replacement Policies 中考虑,有的 DBMS 使用 Background Writing 的方式来处理。它们定期扫描 page table,发现 dirty page 就写入 disk,在 Replacement 发生时就无需考虑脏数据带来的问题。
Allocation Policies 指 DBMS 如何为不同的查询分配内存,可以分为 Global Policies 和 Local Policies。前者指同时考虑所有查询来分配内存,后者指为单个查询分配内存时不考虑其它查询的情况。
除了存储 tuples 和 indexes,DBMS 还需要 Memory Pools 来存储其它数据,如:
Maintenance Buffers(维护缓冲区)是PostgreSQL中的一个概念,用于处理后台写入和维护操作:
数据库管理系统(DBMS)可以比操作系统更好地管理内存资源。
利用查询计划的语义可以做出更好的决策,包括页面驱逐、内存分配和预取操作。