本期主要介绍数据库内存和磁盘之间的交互

DISK-ORIENTED DBMS

在DBMS中，执行引擎和磁盘中间有一个Buffer Pool作为缓冲，执行引擎想要读取数据时，首先去看Buffer Pool中有没有，如果没有，则从磁盘中把对应的Page加载到内存 buffer pool中，然后把这个内存中的Page的指针返回给执行引擎。

Buffer Pool Manager

Buffer Pool Organization

内存区域被组织为一个固定Page大小的数组，数组的每个单元被称为frame。每当DBMS需要读取page时，就会把Page放到这个frames中。

dirty pages（脏页）是指在缓冲池中已经被修改但尚未写回到磁盘的数据页。

脏页的存在是因为DBMS使用了缓冲池来提高数据库的性能。通过将数据加载到内存中进行操作，可以避免频繁的磁盘访问，从而提高数据的读取和写入效率。然而，为了保证数据的一致性和持久性，脏页需要定期写回到磁盘上的对应数据文件中。

Buffer Pool Meta-data

Page table(页表)会跟踪当前在内存中的每个Page。通常是用一个固定大小的Hash Table来记录，并用latches来保证线程安全。

页表通常是一个索引结构，它记录了数据页在缓冲池中的位置、状态和其他相关信息。每个数据页在页表中都有一个对应的条目。通过使用页表，DBMS可以有效地管理缓冲池中的数据页。它可以快速查找和定位特定的数据页，跟踪数据页的状态和访问模式，并支持缓冲池的替换和管理策略。

每个Page的一些元数据信息包括：

1. Dirty Flag, 标识Page是否被修改过，内存和磁盘中的数据不一致
2. 固定计数器，用于跟踪Page在缓冲池中被固定的状态的计数器。
3. 访问跟踪信息, 用于记录和跟踪数据页在缓冲池中的访问情况

Locks VS Latches

Locks和Latches的区别：

1. 并发级别：Latches通常用于数据库内部数据结构的并发控制，如缓冲池、索引等。它们是数据库引擎内部的同步机制，用于保护共享资源。而Locks通常用于控制事务对数据库对象（如表、行）的访问，并提供事务的隔离性和一致性。
2. 轻量级 vs. 重量级：Latches是相对轻量级的同步机制，通常由数据库内核直接管理。它们是基于硬件或操作系统提供的原语实现的，速度较快，但功能较简单。而Locks通常是数据库引擎的高级抽象，提供更复杂的功能，如并发事务隔离、锁级别等。Locks的实现通常包括更丰富的语义和管理机制。
3. 锁粒度：Latches通常用于对数据结构的较小粒度的保护，如页或缓冲区。它们的作用是提供对这些数据结构的原子性访问。而Locks可以用于更大粒度的数据对象，如表、行或事务级别的锁。
4. 锁模型：Latches通常是基于互斥（Mutex）的模型，即同一时间只允许一个线程持有latch。多个线程可以同时获取共享latch，但独占latch只允许一个线程获取。而Locks可以基于不同的模型，如共享锁（Shared Lock）和独占锁（Exclusive Lock），支持更复杂的并发控制策略。

需要注意的是，latches和locks在数据库系统中扮演不同的角色。Latches是数据库引擎内部用于管理共享资源的同步机制，而Locks是用于控制事务对数据库对象的访问和维护数据的一致性。它们相互补充，共同实现数据库的并发控制和事务管理。

Page Table VS Page Directory

Page Table和Page Directory的区别

1. Page Table: 页表是一种数据结构，用于将Page id映射到缓冲池中Page对应的frame。这是一种内存中的数据结构，不必保存在磁盘中。
2. Page Directory(页目录): 页目录是用来映射Page id和数据文件在物理磁盘中的位置。因此，对页⽬录做出的所有改变都必须持久化到磁盘。

Buffer Pool Optimizations

Multiple Buffer Pools

Multiple Buffer Pools 是一种数据库管理系统（DBMS）中用于提高性能和优化内存管理的技术。它允许将数据库缓冲区划分为多个独立的缓冲池，每个缓冲池可以有不同的配置和策略。

Multiple Buffer Pools有以下关键特点和优势：

1. 隔离和优化：通过将缓冲区划分为多个独立的缓冲池，可以实现数据的逻辑隔离和优化。不同类型的数据可以分配到不同的缓冲池，并为每个缓冲池设置独立的缓存策略。这样可以根据数据的访问模式和重要性，针对性地优化缓冲池的管理和性能。
2. 优化内存利用率：多个缓冲池可以根据具体需求和资源限制分配不同的内存大小。对于不同类型的数据，可以为其分配适当的缓冲池大小，以达到最佳的性能和内存利用率。例如，可以为频繁访问的热数据分配更大的缓冲池，而为冷数据分配较小的缓冲池。
3. 避免争用：多个缓冲池可以减少并发访问时的争用。不同的缓冲池可以由不同的线程或事务独立管理，减少了对共享缓冲区的争用。这可以提高并发性能，并降低锁竞争。
4. 高级别的策略控制：每个缓冲池可以有独立的缓冲策略和调度算法。根据数据的特性和访问模式，可以为每个缓冲池设置不同的替换算法、预读取策略、写回策略等。这样可以更精确地控制缓冲池的行为和性能。

有以下两种方法来进行分区：

1. Object Id: 给每条记录都嵌入一个object标识符，用来映射制定的缓存池
2. Hash: 通过对Page id取hash值来选择使用哪一个缓存池

Pre-Fetching

Pre-Fetching用于提前将数据加载到缓冲区中，以减少对磁盘的访问延迟和提高查询性能。它通过预先获取可能需要的数据块，提前将其存储在内存缓冲区中，以便在需要时能够快速访问。

Scan Sharing

Scan Sharing用于在数据库查询中共享扫描操作，以减少重复的数据访问和提高查询性能。比如SQL1准备去读取表A，但此时SQL2已经在读取表A了，那么DBMS就会把SQL1的游标attach到SQL2的游标上去。

Scan Sharing的优势包括：

1. 减少数据读取：通过共享扫描操作，可以避免重复读取相同的数据块，减少了磁盘I/O操作和数据传输的成本。
2. 提高查询性能：共享扫描可以减少扫描操作的次数，从而加快查询的执行速度。
3. 资源节约：通过减少扫描操作，可以减少系统资源的使用，提高系统的整体效率和吞吐量。

Contionous Scan Sharing

Contionous Scan Sharing是一种比较极端的想法，DBMS会持续重复的去扫描数据文件到内存中。现实中也很少有数据库采用这种优化方法。

Buffer Pool ByPass

缓冲池绕过用于在某些情况下绕过数据库的缓冲池，直接访问磁盘上的数据，以提高查询性能。这种技术通常应用于特定类型的查询或操作，其中数据集的大小超过了缓冲池的容量或查询需要直接访问磁盘上的新数据。

Buffer Replacement Policies

当缓冲池已经满了，此时有新的Page需要从磁盘中加载到缓冲池时，DBMS需要释放一个frame的空间，他就需要决定到底淘汰哪一个Page。整个淘汰策略需要考虑到正确性，准确性以及速度等。

Least-Recently Used

LRU会将最近最少使用的Page驱逐出缓冲池。

当每个Page被访问时，都会维护一个对应的时间戳。当DBMS需要淘汰Page时，就会选择一个最老的时间戳。

LRU List将所有Page通过链表的形式串联在一起，表头是最新访问的，每当Page被访问时，就会往前移动，然后淘汰时就会驱逐表尾的Page.

Clock

Clock方式类似于LRU，但是不需要每个Page都维护一个独立的时间戳。

每个Page都有一个引用bit, 每当被访问时，就会设置为1。所有的Page以圆圈的形式组织起来，然后会按顺时针去check每个Page的bit是否为1，如果是，则设置为0，否则就会驱逐出去。

LRU-K

LRU-K是一种改进的缓存替换策略。它是对传统的LRU策略的扩展。他关注的是每个Page最后K次被访问的历史，然后计算出相邻引用之间的间隔。

比如K为2，则关注的是倒数第一次和倒数第二次访问之间的时间差，根据这个时间差DBMS就可以估算出下次这个Page会被访问的时间。并淘汰预期间隔时间最长的Page。

Mysql Approximate LRU-K

在Mysql中也有类似LRU-K的实现方式

他有一个LRU链表，链表中有两个指针，分别指向Young List和Old List。新的Page加载到缓存池中时总是插入到Old List的头节点， 如果在Old List中的Page被再次访问，则会被插入到Young List的头节点。

Localization

Localization就是指DBMS会根据每个查询的基础来决定驱逐哪个Page。 这样可以最大限度的减少来自于每个查询对缓冲池的污染。比如Postgres就给每个查询都维护了一个私有的小型唤醒缓冲池。

Priority Hints

还有一种比较好的策略：Priority Hints(优先级提示)。

开发人员可以向查询优化器提供关于查询重要性和优先级的信息，以便系统能够更准确地选择执行计划。例如，对于一些重要的查询，可以使用高优先级提示，使优化器更注重性能和效率。而对于一些次要的查询，可以使用低优先级提示，使优化器更注重资源利用和系统的整体平衡。

以下图为例，有很多索引相关的Page, 当我们插入了连续递增的id， 然后想进行扫描查询，虽然执行的路径可能不一样，但一定会经过index-page0，因此可以向DBMS提示这个Page的优先级很高，可以放入缓冲池中。

Dirty Pages

当DBMS从缓冲池中淘汰一个Page时，如果这个Page没有被修改过，不是dirty的，那么可以直接驱逐他。但如果是脏页，被修改过，则需要把这个Page更新到磁盘进行持久化

BackGround Writing

BackGround Writing指的就是DBMS会在后台定期的遍历page table然后把脏页写入磁盘，当脏页安全的写入到磁盘后，DBMS就会驱逐这个Page或者把取消这个Page的dirty flag标识符。

Disk I/O Scheduling

DBMS会维护一个内部的队列来跟踪来自整个系统的Page读写请求，并会基于图中的一些因素来计算优先级。

我们大多数磁盘操作都是通过操作系统的API，除非DBMS告诉他不要。

操作系统会维护一个自身的文件系统缓存(Page Cache)。大概流程就是DBMS想去读一个Page，缓存中没有，然后就从磁盘中读取放到OS的Page Cache中, 然后再从Page Cache中拷贝到用户空间中。这个流程就会出现一次多余的复制。因此大多数DBMS会使用直接I/O来跳过操作系统的缓存来减少多余的复制。