MIT6.830 Lab1：从零构建SimpleDB存储引擎核心模块

1. 初识SimpleDB存储引擎第一次接触数据库存储引擎的实现时我完全被各种专业术语搞晕了。Tuple、Catalog、BufferPool这些概念听起来高大上但其实它们就像是我们日常生活中常见的物品。想象一下SimpleDB就是一个大型文件柜系统而我们要做的就是亲手打造这个文件柜的核心部件。MIT6.830的Lab1实验提供了一个绝佳的实践机会。这个实验要求我们用Java实现SimpleDB存储引擎的四个核心模块Tuple元组、Catalog目录、BufferPool缓冲池和HeapFile堆文件。对于数据库初学者来说这就像是从零开始搭建一个微型数据库系统能够帮助我们深入理解数据存储和访问的基本原理。我刚开始做这个实验时最大的困惑是不知道这些模块之间如何协作。后来发现它们的关系其实很直观Tuple是数据的基本单位Catalog负责管理表信息BufferPool作为内存缓存HeapFile则处理磁盘存储。这种分层设计在真实数据库系统中也很常见比如MySQL的InnoDB引擎就有类似的架构。2. Tuple模块实现详解2.1 理解Tuple的核心概念Tuple本质上就是数据库表中的一行记录。在SimpleDB中每个Tuple由多个Field对象组成每个Field对应表中的一个字段值。这就像Excel表格中的一行数据包含多个单元格的值。实现Tuple类时需要重点关注三个核心属性TupleDesc描述元组的结构类似表结构定义RecordId记录在磁盘上的物理位置Field列表存储实际字段值的集合public class Tuple implements Serializable { private TupleDesc td; // 元组结构描述 private RecordId rid; // 磁盘位置标识 private CopyOnWriteArrayListField fields; // 字段值集合 // 构造方法 public Tuple(TupleDesc td) { this.td td; this.fields new CopyOnWriteArrayList(); } // 其他方法... }2.2 TupleDesc的设计实现TupleDesc定义了元组的结构相当于表的Schema。它包含一组TDItem对象每个TDItem描述一个字段的类型和名称。这里我采用了CopyOnWriteArrayList来保证线程安全因为数据库系统通常需要处理并发访问。public class TupleDesc implements Serializable { CopyOnWriteArrayListTDItem tdItems; public static class TDItem implements Serializable { public final Type fieldType; // 字段类型 public final String fieldName; // 字段名 public TDItem(Type t, String n) { this.fieldName n; this.fieldType t; } } // 合并两个TupleDesc public static TupleDesc merge(TupleDesc td1, TupleDesc td2) { TupleDesc result new TupleDesc(); if (td1 ! null) result.tdItems.addAll(td1.tdItems); if (td2 ! null) result.tdItems.addAll(td2.tdItems); return result; } }2.3 踩坑经验分享在实现Tuple的equals方法时我最初只比较了RecordId结果导致测试用例失败。后来意识到需要同时比较TupleDesc和所有Field值才算完整。这个教训让我明白数据库系统中数据一致性的检查必须非常严格。另一个容易出错的地方是Tuple的序列化。SimpleDB需要将Tuple转换为字节数组存储到磁盘因此toString()方法的格式必须完全符合要求字段间要用制表符分隔。我在这里调试了好几次才通过所有测试用例。3. Catalog模块设计与实现3.1 Catalog的核心职责Catalog相当于数据库的目录管理着所有表的信息。每次访问表时都需要先查询Catalog获取表的元数据。在SimpleDB中Catalog主要维护两个映射关系表ID到表信息的映射表名到表ID的映射我使用ConcurrentHashMap来实现这些映射确保多线程环境下的安全性public class Catalog { private ConcurrentHashMapInteger,Table tableIdMap; private ConcurrentHashMapString,Integer tableNameMap; public Catalog() { tableIdMap new ConcurrentHashMap(); tableNameMap new ConcurrentHashMap(); } public void addTable(DbFile file, String name) { int tableId file.getId(); tableIdMap.put(tableId, new Table(file, name)); tableNameMap.put(name, tableId); } }3.2 Table类的辅助设计为了更好地组织表信息我创建了一个辅助类Table封装了DbFile、表名和主键字段Data // 使用Lombok简化getter/setter public class Table { private DbFile file; // 对应的数据文件 private String name; // 表名 private String pkeyField; // 主键字段名 public Table(DbFile file, String name) { this(file, name, ); } }3.3 加载Schema的注意事项Catalog还需要支持从文件加载Schema。这个过程需要解析文本文件创建对应的表和TupleDesc。我在这里遇到的一个坑是字段类型的处理 - 必须严格区分INT_TYPE和STRING_TYPE否则后续操作会出错。public void loadSchema(String catalogFile) { try (BufferedReader br new BufferedReader(new FileReader(catalogFile))) { String line; while ((line br.readLine()) ! null) { // 解析表定义 String name line.substring(0, line.indexOf(()).trim(); String fields line.substring(line.indexOf(()1, line.indexOf())).trim(); // 处理每个字段 String[] els fields.split(,); ListString names new ArrayList(); ListType types new ArrayList(); for (String e : els) { String[] parts e.trim().split( ); names.add(parts[0].trim()); types.add(parts[1].trim().equalsIgnoreCase(int) ? Type.INT_TYPE : Type.STRING_TYPE); } // 创建表并加入Catalog TupleDesc td new TupleDesc(types.toArray(new Type[0]), names.toArray(new String[0])); HeapFile hf new HeapFile(new File(name.dat), td); addTable(hf, name); } } catch (IOException e) { e.printStackTrace(); } }4. BufferPool缓存管理实现4.1 BufferPool的核心作用BufferPool是数据库性能的关键组件它缓存从磁盘读取的页减少IO操作。在SimpleDB中BufferPool使用固定大小的页缓存默认50页当缓存满时需要实现页面替换策略。Lab1中我们只需要实现基础功能重点是getPage()方法public class BufferPool { private final int numPages; private final MapPageId, Page bufferPool new ConcurrentHashMap(); public Page getPage(TransactionId tid, PageId pid, Permissions perm) throws DbException { if (!bufferPool.containsKey(pid)) { // 从磁盘加载页面 DbFile file Database.getCatalog().getDatabaseFile(pid.getTableId()); Page page file.readPage(pid); // 如果缓存已满需要处理页面替换 if (bufferPool.size() numPages) { throw new DbException(Buffer pool full - need eviction policy); } bufferPool.put(pid, page); } return bufferPool.get(pid); } }4.2 页面大小与内存管理SimpleDB默认页大小是4KB这与现代数据库系统的页大小如MySQL的16KB有所不同。页大小直接影响IO效率较大的页可以减少IO次数但会增加内存占用。我在测试时发现BufferPool的页面管理必须非常精确。例如计算偏移量时一个字节的错误就会导致读取到完全错误的数据。因此所有与页大小相关的计算都需要反复检查public static final int DEFAULT_PAGE_SIZE 4096; // 4KB private static int pageSize DEFAULT_PAGE_SIZE; public static int getPageSize() { return pageSize; }4.3 后续实验的扩展点虽然Lab1不要求实现页面替换策略但我在代码中预留了evictPage()方法为后续实现LRU等算法做准备。这也是数据库系统优化的关键点之一 - 好的缓存算法可以显著提升性能。5. HeapFile存储结构实现5.1 HeapFile的整体架构HeapFile是SimpleDB中最基础的存储结构它直接将元组存储在磁盘文件中没有排序或索引。每个HeapFile由多个HeapPage组成每个HeapPage包含固定数量的元组槽位(slot)。实现HeapFile时需要重点关注计算页数和偏移量实现页面的随机读写提供元组迭代器功能public class HeapFile implements DbFile { private final File f; // 数据文件 private final TupleDesc td; // 表结构 public Page readPage(PageId pid) { int offset pid.getPageNumber() * BufferPool.getPageSize(); byte[] data new byte[BufferPool.getPageSize()]; try (RandomAccessFile raf new RandomAccessFile(f, r)) { raf.seek(offset); raf.readFully(data); return new HeapPage((HeapPageId)pid, data); } catch (IOException e) { throw new IllegalArgumentException(Page read error); } } }5.2 HeapPage的位图设计HeapPage使用位图来跟踪哪些槽位被占用。每个元组对应位图中的一位1表示占用0表示空闲。这种设计非常节省空间但计算起来需要格外小心public class HeapPage implements Page { private final byte[] header; // 位图头 private final Tuple[] tuples; // 元组数组 private final int numSlots; // 总槽位数 // 计算总元组数 private int getNumTuples() { return (BufferPool.getPageSize() * 8) / (td.getSize() * 8 1); } // 检查槽位是否被占用 public boolean isSlotUsed(int i) { int headerByte i / 8; int bitPos i % 8; return (header[headerByte] (1 bitPos)) ! 0; } }5.3 文件迭代器的实现HeapFile需要提供遍历所有元组的能力我通过实现DbFileIterator来完成这个功能。这个迭代器需要跨页工作当当前页的元组遍历完后自动跳到下一页private class HeapFileIterator implements DbFileIterator { private int pageNo 0; private IteratorTuple tupleIterator; public boolean hasNext() throws DbException { if (tupleIterator null) return false; if (tupleIterator.hasNext()) return true; while (pageNo numPages()-1) { pageNo; tupleIterator getTupleIterator(pageNo); if (tupleIterator.hasNext()) return true; } return false; } private IteratorTuple getTupleIterator(int pgNo) throws DbException { HeapPageId pid new HeapPageId(getId(), pgNo); HeapPage page (HeapPage)Database.getBufferPool() .getPage(null, pid, Permissions.READ_ONLY); return page.iterator(); } }6. 操作符与查询执行6.1 SeqScan操作符实现SeqScan是最基础的表扫描操作符它通过迭代HeapFile中的所有元组来实现全表扫描。实现时需要特别注意TupleDesc的处理 - 需要将表别名与字段名组合起来public class SeqScan implements OpIterator { private DbFileIterator iterator; private String tableAlias; public TupleDesc getTupleDesc() { TupleDesc orig Database.getCatalog().getTupleDesc(tableId); Type[] types new Type[orig.numFields()]; String[] names new String[orig.numFields()]; for (int i 0; i orig.numFields(); i) { types[i] orig.getFieldType(i); names[i] tableAlias . orig.getFieldName(i); } return new TupleDesc(types, names); } }6.2 简单查询的执行流程通过组合这些组件我们可以执行一个完整的查询。以下是一个简单查询的执行示例// 1. 创建表Schema Type[] types {Type.INT_TYPE, Type.STRING_TYPE}; String[] names {id, name}; TupleDesc td new TupleDesc(types, names); // 2. 创建表文件并加入Catalog HeapFile table new HeapFile(new File(mytable.dat), td); Database.getCatalog().addTable(table, mytable); // 3. 执行查询 TransactionId tid new TransactionId(); SeqScan scan new SeqScan(tid, table.getId()); scan.open(); while (scan.hasNext()) { Tuple t scan.next(); System.out.println(t); } scan.close();6.3 调试技巧分享在实现这些操作符时我总结出几个有用的调试技巧使用toString()方法打印关键对象的状态为每个测试用例单独创建临时文件避免测试间干扰逐步验证每个组件的输出不要试图一次通过所有测试特别注意边界条件如空表、单行表等特殊情况7. 实验总结与进阶思考完成Lab1后我对数据库存储引擎有了更深入的理解。从最底层的Tuple存储到BufferPool的缓存管理再到操作符的执行流程每个组件都有其独特的设计考量。这个实验最让我印象深刻的是数据库系统的分层设计思想。每一层只需要关注自己的职责通过清晰的接口与其他层交互。例如BufferPool不需要知道页面的具体格式只需要按PageId存取HeapFile不需要关心事务处理只需要提供页面读写能力。对于想进一步深入的同学我建议尝试实现更复杂的页面替换算法如LRU添加基本的索引支持如哈希索引优化HeapFile的存储布局提高空间利用率实现简单的WAL(Write-Ahead Logging)机制这些扩展练习可以帮助你更好地理解现代数据库系统的实现原理。