[CMU15445] 06 - Buffer Pools

传统数据库的数据组织通常由磁盘和内存两部分构成，所有的数据都存在磁盘上，当用户使用特定的SQL查询数据时，Execution Engine会将需要哪些页告诉Buffer Pool，然后Buffer Pool会将这些页读进来进行操作, 数据库使用一些机制来管理内存中的数据

image.png

Buffer Pool Manager

Buffer Pool在内存中就是一大块内存的数组，数组的每一项叫做一个frame，可以存储磁盘的一个page

image.png

除了在内存中存储数据意外，还需要存储一些metadata来让数据库知道这些page的一些信息，我们使用一个叫做Page Table的结构来保存这些metadata，Page Table里面存储了内存中一个frame中存储的是磁盘的第几个page，还存储其他信息，例如Dirty Flag(表示数据被读入内存后有没有被修改过)，Pin Counter(当有查询需要对该页进行读写时，就要把他钉住，这会阻止系统将该页换出内存)。

page table vs page directorty

page table用于管理内存中的页，而page directory是用于管理磁盘上的所有页

当一个查询需要最内存中某一页进行修改了，为了避免其他线程同时修改该页，会给这一个页加上一个latch(不是lock)

latch vs lock

latch和lock的区别在于，在数据库中，lock是指在一个事务中，为了保护数据，给一个数据库，表或者单条记录加锁，是一个high-level的概念，lock可能会由于资源竞争而导致死锁。而latch指的是一种low-level的锁，是数据库为了保护它内部的数据结构而使用的原语，latch是不会造成死锁的问题的

image.png

Buffer Pool Optimization

这节介绍了一些优化Buffer Pool的方式

• Mutiple Buffer Pools：使用多个Buffer Pool，可以为一个数据库设置一个Buffer Pool，可以为某一种特定的页类型设置一个Buffer Pool，这样做可以为每一个Buffer Pool使用不同的策略，做到细粒度的优化，同时还可以减少锁竞争

• Pre-Fetching：在某些特定的查询，例如顺序查询中，当在处理一个page时，可以提前读入下面的page，从而减少IO的停顿

image.png

• Scan Sharing：当queryA在查询时，queryB可以将自己的cursor附着到queryA的cursor上，等到A结束后，再单独去获取没有扫描到的数据

  
  
  image.png

• Buffer Pool Bypass

对于一些查询，例如顺序查询，很多page都是读一次就再也不用了，此时将他们存到Buffer Pool中就会浪费资源并且污染原来的Buffer Pool，所以对于一些顺序或者join的操作，可以使用单独的temporary Buffer Pool，将数据读到内存用完之后就直接扔掉

OS Page Cache

大多数数组库在读取数据时都会绕过OS的Page Cache，使用O_DIRECT的方式直接从文件读取，一个例外是Postgresql

image.png

Buffer Replacement Policies

• LRU: 为每一个frame存储一个时间戳，每次访问更新时间戳，当需要替换时淘汰最久没有被访问的frame
• Clock：LRU需要存储和频繁更新时间戳，开销太大，Clock是对LRU的近似，使用一个ref位，当frame被访问时，ref=1，当需要淘汰时，则扫描队列，对于ref=1的frame，将red=0，对于red=0的frame，将它替换出去

image.png

上述两种方法会有一个叫做Sequential Flooding的问题，也就是当查询循环引用页时，你刚刚放进来的页反而是最久才会被下次访问到的页，此时两种方法的性能会很差，通常使用LRU-K的方法来优化这种情况