跳转至

1.1 文件管理模块概述

引言

这个模块属于是数据库的底层设施，甚至不算数据库的一部分，它的全名叫《页式文件管理系统》，是一个管理文件及其缓存的系统。在课改前的大作业中是没有算进需要实现的几个模块之一的，但助教商讨认为，了解本模块对于理解数据库的上层实现有重要意义，因此我们依然提供了往年祖传的实现（后文简称“参考实现”，可从文档的《附件》章节中下载），但也进行了详细讲解，以便有需要的同学按照教程自行实现。

需求

首先需要理解我们为什么需要数据库，为什么需要一个专用的文件管理系统。

1. 大文件

数据库被设计用来存储大量数据（通常是高于计算机内存的）并进行增删查改等操作，我们在操作时内存通常只能取数据库文件的一小部分进行局部操作。

尽管我们不必将一个数据库存在一个文件中，也即我们可以通过将不同表拆分成不同文件、将数据和索引拆分成不同文件等手段来减小文件的大小，但一般至少一张表的数据会存入同一个文件中，我们仍然可能因为一张表有上G条记录而出现超过内存大小的文件。

2. 页式管理

因此我们需要一种策略将数据库的文件拆分成更小的单元，将文件操作体现在这些单元之上。因此，首先我们需要一个页式文件系统，将文件以页为单位进行拆分——页的大小不必是一样的，但是简单起见我们实现的是固定页大小的。本文档中还会提到页的概念，如无特别解释均指代页式文件系统的“页”，它的大小或许恰好与操作系统的页相同（比如都是4KB）， 或许不同，需要注意区分。

3. 缓存引入

完成页式文件系统后，我们需要考虑操作的成本问题：

  • 一方面，我们不能在每次读写时都去文件中获取一页，IO 时间会有较高成本，我们希望通过更多的 CPU 计算来减少 IO 频次，提高数据库引擎性能，在文件较小时，针对这一问题有一种经典的减少 IO 操作法（维护一些 meta 信息时仍然可以参考这种手段）：启动程序时（或者第一次读写时）将文件内容全部读入内存，操作完毕后在结束程序时（或者其他合适的时机，但保证频率应该较低）将文件内容写回文件。

  • 但在另一方面，即便页式处理后，由于无法看见文件的全貌，我们一定会因为内存不足而需要交换内存和文件的页，因此不能像处理小文件那样借助内存将 IO 完全降低为一次读一次写。

综上所述，我们需要合理使用内存作为文件系统的缓存，如果你了解 CPU 的缓存策略会发现它们有极高的相似之处。我们需要事先在内存中预留好若干页的空间，并为每个页准备一些额外属性，例如 dirty 标记、对应的文件页位置等，我们将在后面的章节讲述缓存替换算法。

系统总览

综合上述需求，我们不直接使用操作系统提供的文件系统，而是要透过以页式文件系统为基础的上层数据库管理系统，主要有两方面原因：

  1. 文件太大，不能进行全量操作，需要页式分散
  2. 页面太散，不能直接构造应用层的系统，需要上层数据库提供 schema 和复杂的管理

本章的页式文件系统作为一个桥梁，将操作系统的文件系统碎片化，为后文数据库执行计划的操作提供了物理载体，因此理解它对于理解我们最终要实现的数据库系统的特性及功能有重要意义。

相关组件

我们需要这样一些组件来完成上述的文件管理：

  • 一个完成文件 IO 的管理器，它会处理文件创建、打开、删除，完成一页数据的读、写（对应参考实现的 FileManager）
    • 一个容器来存储已经打开过的文件，并暴露一个 ID 或者对象供上层使用（对应参考实现的 FileManager::fm）
    • 相关 IO 接口调用，包括二进制文件打开（及创建）、关闭、偏移到指定位置并读写指定大小（对应参考实现的 open、close、lseek、read、write 等）
  • 一个为数据页提供缓存的缓存管理器，它对外提供指定文件读写，内部根据实际情况操作缓存数据（对应参考实现的 BufPageManager）
    • 一个大数组（内存块）来存放大量页（对应参考实现的 BufPageManager::addr，注意它配合 BufPageManager::allocMem 使用了二维动态数组，但这对性能可能并不友好）
    • 上述内存块的元信息，记录对应的文件、页号、dirty 标记等，判断是否命中缓存及对应数据的位置（对应参考实现的 BufPageManager::hash 和 BufPageManager::dirty）
    • 一个缓存替换算法，未命中缓存时决定将新的缓存页放在哪（对应参考实现的 BufPageManager::replace 配合 BufPageManager::last）

本章剩下几节将给出完成这些组件的文档。

Authors: Congyuan Rao