
开发者用 Zig 语言实现 CMU 数据库课程缓冲池
来源标题:Building a buffer pool in Zig, following Andy Pavlo's CMU 15-445/645
一位开发者宣布启动为期约一年的系列项目,跟随 Andy Pavlo 的 CMU 15-445/645 课程用 Zig 语言动手实现数据库组件。首篇文章讲解数据库如何在页内存储行、页与磁盘的读写,以及缓冲池如何将热页保留在内存中,并完成相应 Zig 实现。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
分享 我关注CMU数据库组的课程已经有一段时间了,但从未真正投入进去——做练习、读论文等等,所以我决定开始一个系列来深入了解数据库系统。这次会不一样,我向自己(也向你们)承诺,要认真过一遍课程和章节,真正动手做出东西来。我只是个打工人,可能没法按自己希望的频率来更新,但这大概会是一个为期一年的系列。
Andy Pavlo是数据库领域的GOAT,他是CMU数据库组的老师。他们把一切都免费放在网上——讲座、幻灯片、讲义、项目。当我发现这一点时,我惊呆了。零成本就能获得这么好的内容,至今仍让我觉得不可思议。
最重要的材料是《Database System Concepts》这本书,如果你想更深入地探索这些主题,一定要读它。另外,如果你有任何建议,或者发现我犯了错误,请在评论区告诉我。
在这篇文章中,我们将回答三个问题:数据库如何在一页(page)内存储一行(row),这一页如何写入磁盘再读回来,以及缓冲池(buffer pool)如何把热页保留在内存中。然后我们将用Zig把这一切构建出来。
本文与#04: Memory Management课程相关。
A Paging Experiment with the Multics System 第13.2-13.5章(每当你看到没有书籍引用的章节,请假定它来自《Database System Concepts》一书)
它是一个固定大小的字节块;通常是4 KB,不过8 KB或16 KB也很常见,数据库总是读写整页,从不读写单独的行,因为磁盘寻道远比访问内存慢得多。还有一个技术限制:磁盘总是按块读取,从不按单个字节读取。
L1缓存是1ns,主内存访问是100ns,SSD随机读取:16,000ns,单次机械硬盘寻道:2,000,000ns。这个网页是很好的可视化方式。
最朴素的布局是一团字节:行一行接一行地拼接在一起。
[ row 0 ][ row 1 ][ row 2 ][ row 3 ]
如果这能行得通,生活就简单了,但它行不通。行的长度各不相同,所以我们无法确定第x行从哪里开始,每次需要某一行时都得扫描整个文件。我们至少需要一个头部(header)、一种更容易定位页内槽位(slot)的方法,以及一种随时跟踪页上还剩多少空间的方式。
解决办法是加一层间接寻址:在页的前部放一个小型的槽位目录,行数据从页尾反方向向后生长。
+---------------------------------------------------------------+ | header | slot 0 | slot 1 | ... | free space | record data ... | +---------------------------------------------------------------+ 0 8 lower -> <- upper end
头部是8字节:
偏移 字段 含义 0 slot_count 槽位数量,包括已删除的 2 lower 槽位目录的末端 / 空闲空间的起点 4 upper 记录数据的起点 / 空闲空间的终点 6 - 保留
每个槽位是4字节:
pub const Slot = struct { offset: u16, // 行在页内的起始位置 length: u16, // 它占用了多少字节 };
它们相向生长,空闲空间就是中间剩下的部分:upper - lower。
Waterloo Bridge, London, at Sunset by Claude Monet
为什么用槽位而不是直接移动行 因为槽位是稳定的标识符。一行的身份是(page_id, slot_id),而不是它的字节偏移量。
当你删除第0行时,你把它对应的槽位标记为已删除(length = 0),并把字节留在原地。O(1)复杂度,而且其他所有行都保持自己的身份。
当你最终回收空间时,你对页进行压缩(compact):把存活的行复制到页尾方向,更新指向它们的槽位。行移动了。槽位编号没变。槽位目录本身永远不会缩小;已删除的槽位会作为墓碑保留下来,这样所有更高编号的槽位都保持在原来的索引位置,我们不想反复分配再释放堆内存,那是很昂贵的操作。
我打算使用的页大小是8192字节。关于页布局以及页大小与磁盘I/O权衡的文章有好几篇,如果你感兴趣,我推荐Graefe的这篇论文。
让我们往一个空页里写入"hello",然后写入"world",看看实际的字节。PAGE_SIZE是8192;u16字段采用小端序。
偏移 字节 含义 0x0000 01 00 slot_count = 1 0x0002 0C 00 lower = 12 0x0004 FB 1F upper = 8187 0x0008 FB 1F 05 00 slot 0: offset 8187, length 5 0x1FFB 68 65 6C 6C 6F "hello"
写入"world"之后
偏移 字节 含义 0x0000 02 00 slot_count = 2 0x0002 10 00 lower = 16 0x0004 F6 1F upper = 8182 0x0008 FB 1F 05 00 slot 0: offset 8187, length 5 0x000C F6 1F 05 00 slot 1: offset 8182, length 5 0x1FF6 77 6F 72 6C 64 "world" 0x1FFB 68 65 6C 6C 6F "hello"
把小端的FB 1F读出来:0x1FFB = 8187。槽位0表示"第0行是从8187开始的5个字节"。槽位1表示"第1行是从8182开始的5个字节"。
注意"world"所在的地址比"hello"更低,尽管它是更新的行。行是从页尾向下分配的——还记得槽位页布局吧——所以第二次插入落在第一次插入的正下方。槽位顺序和物理顺序不必一致。
还有一个细节。当我们插入一行时,我们需要为行本身和它的槽位都留出空间:
const needed = record.len + SLOT_SIZE; // 5 + 4 = 9 if (hi - lo < needed) return error.PageFull;
那4个字节是目录项。头部不计入needed,因为它位于lower之下,已经算过了。
Postgres完全不需要这么做,因为它使用MVCC,从不原地更新行,情况要复杂一些,所以我们这里不展开所有细节。大概会有另一篇文章来讨论这个。Postgres是我最熟悉的数据库系统,所以你会看到我时不时提到它。
简单的情况是缩小或等大小替换,我们只需原地覆盖字节,更新槽位的length字段,就完成了。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。