为什么数据库不信任操作系统？从 Buffer Pool 说起 | CMU15-445 Lec6

回顾Lec3-5我们解决的问题How the DBMS represents the database in files on disk?我们从物理结构出发分析了页如何在磁盘内组织数据如何在页内组织如何表示一条记录tuple如何高效管理变长记录如何压缩以榨取更多价值这个lec我们将解决这个新的问题How the DBMS manages its memory and move data back-and-forth from disk解决这个问题的过程中我们将着眼于两个问题一个在lec3-5中提出的旧问题如何尽可能减少磁盘 I/O一个新的问题如何防止OS捣乱buffer pool服务于这两个目标lec3-5中我们只是管理了disk上的文件但是没有解决”如何高效的把数据从磁盘搬到内存“这个问题每次查询都从磁盘读太慢把所有数据都放内存内存不够大所以 Lec 6 要解决如何用有限的内存缓存热点数据最小化磁盘 I/O从DBMS的视角来看整个database看起来好像都在内存中尽管实际上database所占用的空间可能超过系统中可用的内存。然而DBMS不需要关心数据是怎么被取到内存中来的也不需要关心数据如何被管理因此我们需要从两个方向来优化空间与时间空间上尽可能让那些经常一起使用的页面在磁盘上尽可能靠近时间上控制页面什么时候被写入内存什么时候被写回磁盘以尽可能减少必须从磁盘读取数据而造成的停顿Buffer Pool ManagerBuffer Pool 是位于内存和磁盘之间的、以页面为单位的内存缓存。它本质上是数据库内部申请的一大片内存区域用来临时存储页面。Buffer Pool 的基础实现如图frame array是实际存储 page 的内存区域左边的pagetable存page id到frame id的映射与此同时我们需要有替换策略当frame array满的时候我们需要选择驱逐哪个frameDBMS 还维护一个 page directory页面目录它是从 page id 到数据库文件中页面物理位置的映射。Page directory 存储在磁盘上以保证持久化但通常会被缓存在内存中以降低页面访问延迟。功能上来讲DBMS需要这块buffer pool来完成很多工作具体来说包括Tuple Storage and Indexes元组存储和索引Sorting and Join Buffers排序和连接缓冲区Query and Dictionary Caches查询缓存和字典缓存Maintenance and Log Buffers维护缓冲区和日志缓冲区page table 与 page directorypage directory是从 page id 到物理数据库文件中页面位置的映射。所有修改都必须被记录到磁盘上这样 DBMS 在重启时才能找到它们。page table是从 page id 到缓冲池 frame中某个页面副本的映射。这是一个内存中的数据结构不需要存储在磁盘上。metadata缓冲池拥有的元数据存放在pagetable中主要包括dirty flag和pin counterdirty flag会在线程修改页面时被set。这向storage manager表明在该页面被驱逐之前必须先将它写回磁盘pin counter会跟踪当前正在访问该页面的线程数量无论是读还是写线程在访问页面之前必须先增加这个计数器使用完毕后减少计数器如果pin count 大于 0那么 storage manager 不允许把这个页面从内存中驱逐出去并发我们需要区分DBMS中的lock和latchlatch 保护的是DBMS 内部数据结构的物理一致性lock 保护的是数据库逻辑数据的事务隔离性latch就是我们OS里学到的保护临界区域的那种“锁”用来保护内存DBMS数据结构别被并发破坏掉是DBMS内部用的。而lock是在更宏观的角度用来保护DBMS本身事务的锁用来保护数据库的逻辑对象例如tuple, table, index record等很自然的当我们更新一条记录的时候两者都会用到首先为了事务隔离需要使用lock具体修改时为了安全修改内存的page需要使用latchOS与DBMS学习这个lec的时候总是有点混淆OS和DBMS各自负责的内容理了很久终于是理清楚了。首先DBMS做为运行在OS上的软件看起来DBMS做的事情就是把自己在管理的那些文件拉出来又围绕着这些文件做了一层新的文件系统和内存管理。为什么要这么做因为对于DBMS来说OS做的这些事情是“不可控的”这会让DBMS没有“安全感”。但是具体来说DBMS并不是完全接管OS的职能而是DBMS通过一些特定的方式“绕过”OS的一些机制但是底层仍然需要OS的系统调用来访问硬件为什么OS做事DBMS不放心因为OS提供的file system和memory management是通用的用以服务所有的应用程序但是DBMS有特殊的需求而OS不知道这些需求OS不知道哪些数据更重要在OS眼里他只知道这是一个文件一块内存一次读写请求无法根据数据库语义做优化OS 的页面替换策略不适合数据库OS经常用LRU类似的策略来管理page cache但是数据库经常会遇到顺序扫描例如SELECT * FROM huge_table;这回一次性读取几百万的page对于OS来说他会把这些page全读进内存把之前内存的热点数据都挤出去而这些进入内存的page又只用一次。对于DBMS来说它知道这些page只会用一次所以可以用其他特殊的策略OS不知道事务的存在DBMS有事务的概念而OS不知道如果OS的page cache觉得内存紧张把脏页刷回磁盘会破坏事务的原子性和持久性OS会引入不可控的延迟如果DBMS使用mmap把数据库文件映射到内存当其访问一个内存不存在的page时首先触发page fault然后OS阻塞进程在磁盘读取page唤醒进程。这个过程对于DBMS是黑盒的DBMS不知道这些事情而它希望可以主动控制自己什么时候读取哪些pageOS的文件系统不够灵活它是给通用程序用的但是DBMS需要固定大小的pagepage之间有逻辑关系自己能够按照某些方法快速定位某个page并且按照自己的方式组织page。如果完全依赖OS的文件系统DBMS就是去了上述的控制能力DBMS怎么绕过OSDBMS使用OS提供的最底层接口但是绕过OS的高层抽象文件系统缓存、虚拟内存自己来管理文件布局和内存绕过OS的page cacheDBMS使用O_DIRECT标志打开文件int fd open(database.db, O_RDWR | O_DIRECT);这样OS就不会缓存数据库文件的内容DBMS自己来管理buffer pool自己实现缓存逻辑自己管理内存分配绕过OS的虚拟内存不用mmap例如void* buffer_pool malloc(BUFFER_POOL_SIZE); //自己控制读哪个page read(fd, buffer_pool offset, PAGE_SIZE);DBMS就知道哪些page在内存里主动控制IO而且可以实现自己的替换策略自己管理文件布局详见上一篇Lec3-5的内容DBMS是在OS的文件系统之上又构建了自己的“文件系统”对OS来说这只是几个大文件而对DBMS来说这就是一个包含了page directory、heap file、BTree、log 的复杂结构DBMS没有绕过文件系统仍然使用open,read,write,但是在文件内容的组织上完全自主fsync problem我们先回顾一下磁盘的两个系统调用fwrite(): 写入操作系统的缓冲区这个调用会把数据复制到OS的page cache然后返回。数据没有到磁盘。只是从DBMS的内存到了OS的内存fsync(): 强制刷盘OS会把Page cache中的脏页真正写入磁盘磁盘控制器确认写入完成以后返回。这个时候数据才真的在磁盘上问题1DBMS调用fwrite会发生什么很明显数据只是被写入操作系统的 Page Cache并没有真正到达磁盘问题 2DBMS 调用 fsync会发生什么操作系统把 Page Cache 中的脏页真正写入磁盘并等待磁盘控制器确认写入完成后才返回问题 3如果 fsync 失败返回 EIO 错误会发生什么Linux中第一次fsync调用发生磁盘故障无法写入返回EIO错误但是Linux 把Page Cache中的脏页标记为干净。对于Linux来说他认为我是OS我只负责管理硬件。如果硬件出错了我告诉你错误EIO你应该自己决定怎么处理。如果你重试 fsync我假设你已经知道第一次失败了并且已经采取了适当的措施比如换一个磁盘。所以我把脏页标记为干净避免无限重试所以如果这个时候DBMS没有正确处理错误再次调用fsyncLinux检查Page cache发现所有页面都是干净的没有dirty page于是认为没有脏页需要刷盘fsync立即返回成功DBMS认为第二次fsync成功了数据已经在磁盘上了于是告诉客户端commit成功认为数据已经持久化。然而数据根本没有写到磁盘很多应用程序包括早期的数据库不知道这个行为天真的重试fsync导致数据丢失了。那么正确的处理方法应该是什么第一次失败就直接panic数据库立即停止服务防止数据损坏PostgreSQL就是这么做的重新打开文件这会让OS重新建立Page Cache清除之前的标记使用O_DIRECT写入时就会绕过Page CacheBuffer Replacement PoliciesLRU同OS的LRU需要维护每个页面上次被访问的时间戳CLOCK同OS的CLOCK每个页面拥有一个引用位被访问时置1需要替换页面时需要一个时钟指针开始扫描如果引用位为1则置0如果为0替换掉该页面LRU和CLOCK替换策略存在最大的问题就是前文提到的发生顺序扫描时快速读取大量页面缓冲池被填满拥有更早时间戳的页面被替换。这样的顺序扫描叫做sequential flooding顺序泛洪是指由于顺序扫描导致缓冲池内容被污染所以我们需要思考如果有一个页面在一段时间内被频繁访问即使最近没有被访问我们也不希望驱逐它LRU-K注意在课程Lec6中所讲解的算法是MYSQL对于LRU-2的一种近似实现并不是LRU-K算法。真正的LRU-K算法是在课程的project1-task1中要求我们去实现的这里我们先讲LRU-K算法K表示判断一个frame/page是否要换出的时候要看它“倒数第K次访问”的时间。LRU-1只看最近一次访问时间也就是普通 LRULRU-2看倒数第 2 次访问时间LRU-3看倒数第 3 次访问时间我们定义一个值backward k-distance 当前时间戳 - 第k次访问的时间戳我们来举一个例子假设k2当前时间是100某些frame的访问历史如下frame 1: [10] frame 2: [20, 80] frame 3: [30, 60, 90] frame 4: [5]只保留最近k次访问frame 1: [10] // 访问次数不足 2 frame 2: [20, 80] // 倒数第 2 次访问是 20 frame 3: [60, 90] // 倒数第 2 次访问是 60 frame 4: [5] // 访问次数不足 2计算backward k-distanceframe 1: backward 2-distance inf frame 2: backward 2-distance 100 - 20 80 frame 3: backward 2-distance 100 - 60 40 frame 4: backward 2-distance inf根据算法规则优先淘汰 backward k-distance 最大的如果访问不足k距离视为inf如果多个都是inf淘汰它们中“最早被访问”的那个这里就应该淘汰frame4他是最早被访问的inf这样的设计正好避免了遇到顺序泛洪时会把热点页面淘汰的问题。一般情况下k值为2MYSQL对于LRU-2的一种近似实现接下来我们再来讲课程中MYSQL的实现SQL 对 LRU-2 的一种近似实现是使用两个链表new list和old list并且只从 old list旧链表中驱逐页面每当一个页面被访问时如果它已经在 old list 中就把它放到 young queue年轻队列的开头否则就把它放到 old list 的开头。例子如下可以看到第一次访问page1的时候放入Old List队头第二次访问page1移至New list对头New list队尾的内容同步移动到Old list队头为什么说近似了LRU-2的思想因为访问不足2次的页面都会在old list里面优先被淘汰而访问次数≥2的页面在new list里会得到保护LocalizationDBMS 在每个查询的基础上选择要驱逐哪些页面。这最小化了每个查询对 buffer pool 的污染核心思想就是Per-query按查询替换不是全局决定替换哪些页面而是每个查询只能弄脏自己分配到的那部分 buffer pool。照样来一个例子这里有个buffer pool有10个frame其中100-105是热点数据有很多小查询频繁访问他们Buffer Pool (10 frames): Frame 0: Page 100 (用户索引) Frame 1: Page 101 (用户表热点数据) Frame 2: Page 102 (订单索引) Frame 3: Page 103 (产品目录) Frame 4: Page 104 (库存表) Frame 5: Page 105 (价格表) Frame 6: 空闲 Frame 7: 空闲 Frame 8: 空闲 Frame 9: 空闲而现在来了一个大查询执行一个全表扫描假设需要读取从200-1199共1000个页面但是这些页面又只会读一次读完就不需要了。那么对于Localization策略我们给这个大查询分配一个小的buffer pool我们把frame6-9给他Buffer Pool (10 frames): Frame 0: Page 100 (用户索引) Frame 1: Page 101 (用户表热点数据) Frame 2: Page 102 (订单索引) Frame 3: Page 103 (产品目录) Frame 4: Page 104 (库存表) Frame 5: Page 105 (价格表) Frame 6: Page 200 Frame 7: Page 201 Frame 8: Page 202 Frame 9: Page 203此时frame已满下一个page204进来的时候查询只能覆盖自己的这四个frameframe6变成Page 204一直循环直到最后Buffer Pool (10 frames): Frame 0: Page 100 (用户索引) Frame 1: Page 101 (用户表热点数据) Frame 2: Page 102 (订单索引) Frame 3: Page 103 (产品目录) Frame 4: Page 104 (库存表) Frame 5: Page 105 (价格表) Frame 6: Page 1196 Frame 7: Page 1197 Frame 8: Page 1198 Frame 9: Page 1199前面的热点数据完全不被影响。当查询结束之后frame6-9的内容就会被标记为可被替换Priority Hints让 DBMS 根据查询的上下文信息给页面打上重要性标签替换时优先驱逐不重要的页面。不同于 LocalizationPriority Hints 是给页面分等级。例如还是上面的情景我们把frame0-5的部分全部标上priority为High并且给那些小的查询的优先级全部标为high遇到顺序扫描的时候访问的页面全部标记为low加载新页面的时候有限替换 prioritylow的页面实现方式DBMS根据查询特征自动推断/用户指定/动态调整学习优化Buffer Pool的性能Multiple Buffer Pools单个Buffer pool会遇到一个情况当多个线程都在buffer pool的时候会产生锁竞争大量时间会浪费在等锁上因此我们可以创建多个独立的buffer pool。每个buffer pool都可以采用局部策略这些策略针对其内部存储的数据进行定制映射方式Object ID对象 IDHashing哈希Object ID的方法会扩展 record ID使其包含一个对象标识符。可以通过这些 object ID 维护从对象到特定缓冲池的映射另一种方法是 hashing。DBMS 对 page ID 进行哈希以选择要访问哪个缓冲池Pre-fetching预测未来访问例如我们进行大查询时如果如果访问了 Page N下一个大概率访问 Page N1因此当访问 Page N 时后台线程自动预取 Page N1, N2, N3Scan Sharing这允许多个查询附着到一个扫描表的单一游标如果一个查询开始扫描而此时已经存在另一个活跃扫描那么 DBMS 会把第二个查询的游标附着到已有游标上DBMS 会跟踪第二个查询是从哪里加入第一个查询的这样当它到达数据结构末尾时就可以完成扫描但是当需要按 I/O 付费时这种方式非常浪费且成本很高Buffer Pool Bypass即上文提到的使用O_DIRECT绕过OS的page cache这样可以避免双重缓存但是会让所有的IO都变成真实的磁盘操作一般适用于大小OLTP的数据库且内存足够大不依赖OS总结那么到这里我们已经解答了两个完整的问题How the DBMS represents the database in files on disk?How the DBMS manages its memory and move data back-and-forth from disk?到此为止我们已经基本解决了storage的问题后面的Lec7-10是storage的自然延申有了buffer pool我们如何用它高效的找到数据了所以到这里关于存储的内容就告一段落啦