go 2025年1月21日

Build Your Own Database From Scratch in Go 2nd

使用Go语言从零构建你自己的数据库(第二版)
go database
书籍封面

Build Your Own Database From Scratch in Go 2nd

作者：James Smith 出版日期：2024-06-11 出版社：build-your-own.org
本书详细讲解了如何从零开始构建一个具有事务处理能力的关系型数据库。教程循序渐进地介绍了构建数据库的核心概念和技术，包括持久化存储、B+树索引、崩溃恢复机制、事务并发控制以及SQL查询语言的解析与执行。 它通过构建一个简单的键值存储系统逐步扩展到关系型数据库，并强调了在每一步中理解基本原理的重要性，而不是死记硬背专业术语。 教程包含大量的代码示例，帮助读者理解每个步骤的实现细节。 最终目标是让读者通过约3000行代码掌握构建数据库的核心技术。

第 00 章：导论

  • 本章强调通过实践来掌握数据库的基本原理，而不是陷入复杂的术语。
  • 核心学习内容包括：
    • 原子性和持久性：确保数据更新要么全部成功，要么全部失败，并且更新后的数据能够可靠地保存。
    • 基于 B 树的键值存储：使用 B 树作为磁盘数据结构的基础。
    • 关系型数据库构建于键值存储之上：理解表和索引如何映射到低级别的 B 树。
    • 并发事务控制：管理多个并发事务。
  • 通过约 3000 行代码逐步构建一个数据库。
  • 数据库的核心原理并不复杂，每个人都可以尝试构建。
  • 本章提到了 SQLite 在智能手机上的广泛使用，并强调了数据库在崩溃时保护数据的重要性。

第 01 章：从文件到数据库

  • 本章讨论了直接使用文件存储数据时面临的问题，例如在更新过程中崩溃导致的数据损坏。
  • 原子重命名：通过将新文件重命名为旧文件的路径来实现原子替换，避免了在原位置更新数据。
    • 这种方法确保了在更新中断时，可以从旧文件恢复，并且并发读取不会读取到一半写入的数据。
    • 重命名操作在文件系统中是原子的，成本与数据大小无关。
    • 重命名对于并发读取是原子的，但对于断电不是原子的，需要额外的 fsync 操作。
  • 使用校验和进行原子日志更新：通过在每个日志条目中添加校验和，可以检测到日志条目的损坏，并确保日志更新的原子性。
  • 总结了数据库面临的挑战：
    • 避免在原位置更新。
    • 使用仅追加日志进行增量更新。
    • 使用 fsync 来保证数据持久化。
  • 提出了需要解决的问题：
    • 如何索引数据结构并更新它们。
    • 如何重用仅追加文件中的空间。
    • 如何将日志与索引数据结构结合。
    • 如何处理并发。

第 02 章：索引数据结构

  • 介绍了三种主要的 SQL 查询类型：
    • 扫描整个数据集（不使用索引）。
    • 点查询（通过特定键查询索引）。
    • 范围查询（通过范围查询索引，索引是排序的）。
  • LSM 树（Log-Structured Merge-Tree）：
    • 通过缓冲更新来减少写入放大，避免每次都重写整个数据集。
    • 多层结构，每一层都包含排序的数据。
    • 级别呈指数增长，通过合并大小相似的级别来减少写入放大。
    • 查询时需要合并来自每一层的结果。
    • 使用 Bloom 过滤器优化点查询，减少搜索的级别。
    • 删除的键用 tombstone 标记，并在合并过程中回收空间。
    • SSTable（Sorted String Table）、MemTable 和日志是 LSM 树的实现细节。

第 03 章：B 树和崩溃恢复

  • B 树：
    • 是一种高度平衡的 n 叉树，所有叶子节点的高度相同。
    • 每个节点可以有 2、3 或 4 个子节点的 2-3-4 树是 B 树的一个例子。
    • 可以通过排序数组来理解 B 树。
    • 只有叶子节点包含值，内部节点包含键，指示子树的键范围。
  • 维护 B+ 树的三个不变量：
    • 所有叶子节点的高度相同。
    • 节点大小受限于一个常量。
    • 节点不为空。
  • 通过拆分节点来增长 B 树：当插入导致节点超出大小限制时，将节点拆分为更小的节点，并可能导致父节点也需要拆分，最终导致树的高度增加。
  • 通过合并节点来缩小 B 树：删除可能导致空节点，此时需要将空节点与其兄弟节点合并，合并操作也可能传播到根节点，导致树的高度降低。
  • Copy-on-write B 树：
    • 为了安全地更新 B 树，先复制节点，并在副本上进行修改，更新父节点指向新节点，复制操作传播到根节点，形成新的树根。
    • 原树保持不变，可以从旧的根访问。
    • 这种方法被称为 copy-on-write 数据结构，也称为不可变或持久性。
    • 解决了如何找到树根的问题，并使用空闲列表来复用旧版本的节点。
    • 优点包括免费获得快照隔离，以及轻松的崩溃恢复。
    • 适用于多读单写并发模型。
  • In-place 更新的双写技术：
    • 通过保存更新节点的副本，fsync 保存的副本，进行原位置更新，并再次 fsync 更新，实现崩溃恢复。
    • 在崩溃后，使用保存的副本来恢复数据结构。
    • 双写使更新具有幂等性，允许 DB 重试更新。
  • 崩溃恢复的原则：确保在任何时候都有足够的信息来恢复到旧状态或新状态。

第 04 章：B+ 树节点和插入

  • B+ 树节点的设计：所有 B+ 树节点大小相同，以便使用空闲列表。
    • 节点包含固定大小的头部，包括节点类型和键的数量。
    • 内部节点包含指向子节点的指针列表。
    • 节点包含键值对列表和指向键值对的偏移列表，用于二分查找。
    • 简化了实现，仅关注基本原理。
  • 数据结构与 IO 解耦：使用回调来抽象空间分配和释放，在数据结构和 DB 的其余部分之间建立边界。
  • 节点格式：
    • 头部：节点类型 (2B) 和键的数量 (2B)。
    • 子节点指针：nkeys * 8B。
    • 键值对偏移量：nkeys * 2B。
    • 键值对：klen (2B) | vlen (2B) | key | val。
  • 节点更新：在叶子节点插入键值对时，使用 nodeLookupLE 找到插入位置，然后将所有内容复制到包含新键的新节点中。
  • 节点拆分：
    • 当节点过大时，将其拆分为 2 或 3 个节点。
    • nodeSplit2 将节点拆分为两个。
    • nodeSplit3 将节点拆分为最多三个。
  • B+ 树插入：从根节点开始进行键查找，直到到达叶子节点，然后执行插入操作，可能会导致节点拆分。
    • treeInsert 函数递归地插入键值对。
    • nodeInsert 函数处理内部节点的插入。

第 05 章：B+ 树删除和测试

  • 高层接口：
    • Insert 函数用于插入新键或更新现有键。
    • Delete 函数用于删除键，并返回键是否存在。
  • 维护根节点：
    • 如果树为空，则创建根节点。
    • 如果根节点拆分，则添加新的根节点。
  • 哨兵值：在创建第一个根时插入一个空键，以消除边缘情况。
  • 合并条件：删除可能导致空节点，此时可以将空节点与兄弟节点合并。
    • shouldMerge 函数判断是否应该与兄弟节点合并。
  • 测试 B+ 树：
    • 使用内存模拟页面的方式来测试 B+ 树。
    • C 结构体包含一个 BTree，一个引用数据 ref 和一个内存页面的映射 pages。
    • 使用 C.pages 来验证指针并读取页面。
    • 验证结构是否有效（键是否排序，节点大小是否在限制内）和数据是否与引用匹配。

第 06 章：仅追加键值存储

  • 基于文件的键值存储：
    • 使用 copy-on-write B+ 树，并使用文件作为持久化存储。
    • 文件是仅追加的，空间重用将在下一章节讨论。
    • 忽略并发，假设在一个进程内进行顺序访问。
    • 实现了处理磁盘页面的三个 B+ 树回调。
  • 两阶段更新：
    • 先写入新节点，fsync 来保证顺序。
    • 然后原子地更新根指针，再次 fsync 来使一切持久化。
  • 使用日志的持久性：
    • 双写方案也需要两个 fsync 阶段。
    • 双写类似于日志，只需要一个 fsync 进行更新。
  • 内存数据的并发：
    • 可以使用互斥锁或原子 CPU 指令实现内存数据的原子性。
    • 内存数据的可见性需要内存屏障，类似于 fsync。
  • 文件布局：
    • 数据库是一个文件，分为多个页面。
    • 第一页是元页面，包含指向最新根节点的指针和辅助数据。
    • 新节点以日志形式追加，文件的页面数量存储在元页面中。
  • 目录上的 fsync：在创建新文件后，需要在父目录上执行 fsync。
  • mmap、页面缓存和 IO：mmap 允许像内存缓冲区一样读写文件，磁盘 IO 是隐式和自动的。
  • 管理磁盘页面：使用 mmap 实现页面管理回调。
  • 元页面：元页面包含魔术字节、根指针和页面使用数量，并使用 saveMeta 和 loadMeta 函数来保存和加载。
    • 使用 pwrite 原子地更新元页面。
  • 错误处理：
    • IO 错误后，可以回滚到旧的树根。
    • 需要处理临时写入错误。

第 07 章：空闲列表：回收和重用

  • 内存管理技术：讨论了手动和自动内存管理，以及如何重用未使用的对象。
  • 空闲列表：存储未使用的页面列表，以便重用。
  • 嵌入式链表：最简单的方案是在对象内部嵌入链表指针，但与 copy-on-write 冲突。
  • 空闲列表磁盘布局：每个节点都包含指向下一个节点的指针，项目追加到尾节点，并从头节点消费。
  • 更新空闲列表节点：列表节点的更新是在原位置进行的，但在页面内部是追加的，不需要额外的崩溃恢复。
  • 空闲列表接口：FreeList 结构体包含页面管理回调和元数据。
    • PopHead 函数从列表头部获取一个项目。
    • PushTail 函数将项目添加到尾部。
  • 空闲列表数据结构：
    • 使用 headSeq 和 tailSeq 作为单调递增的索引。
    • SetMaxSeq 函数设置 maxSeq，以防止消耗新添加的项目。
  • 从空闲列表消费：flPop 函数从头部删除一个项目，并移动到下一个节点。
  • 推送到空闲列表：PushTail 函数将项目追加到尾部节点，如果尾部节点满了，则添加新的空尾部节点。
  • 带空闲列表的 KV：
    • 页面管理现在可以使用空闲列表。
    • pageAlloc 函数优先使用空闲列表，再追加页面。
    • pageWrite 函数返回一个可写的页面副本。
    • pageRead 函数优先从待更新映射中读取，再从文件中读取.
  • 更新元页面：元页面现在包括空闲列表指针，和树根一起原子更新。

第 08 章：键值存储上的表

  • 将行编码为 KV：
    • 在关系型数据库中，数据被建模为二维表，由行和列组成。
    • 定义了 Record 结构体来表示表行。
    • 定义了 TableDef 结构体来表示表模式。
  • 内部表：
    • 使用预定义的内部表来存储表模式。
    • TDEF_TABLE 表存储表定义。
    • TDEF_META 表存储自动递增的计数器。
  • 获取、更新、插入、删除、创建：
    • 提供了读取和写入单行的接口。
    • DB 结构体是 KV 的包装器。
    • 使用 decodeValues 函数将值解码为列。
    • 使用 checkRecord 函数重新排序记录并检查缺少的列。
    • 使用 encodeKey 函数对 KV 的键进行编码。
    • 使用 getTableDef 函数获取表模式。
    • dbGet 函数从内部表读取表定义。
  • 插入或更新行：
    • INSERT、UPDATE 和 UPSERT 语句在处理现有行方面有所不同。
    • 使用 MODE_UPSERT、MODE_UPDATE_ONLY 和 MODE_INSERT_ONLY 标志来区分。
    • dbUpdate 函数处理行的插入和更新。
  • 创建表：
    • 创建表的过程包括检查重复名称，读取和更新表前缀计数器，并将模式插入到 @table。
  • 迭代器接口：
    • 使用 SeekLE 函数查找小于或等于输入键的最接近位置。
    • 使用 BIter 结构体表示 B+ 树的位置，使用 Deref 函数获取当前 KV 对，使用 Valid 函数判断是否有效，使用 Prev 和 Next 函数向后和向前移动。

第 09 章：范围查询

  • 范围查询：介绍了 Scan 接口，用于执行范围查询。
  • 顺序保留编码：为了支持范围查询，序列化的键必须按照它们的数据类型进行比较。
    • 将无符号整数编码为大端整数。
    • 将有符号整数转换为无符号整数并翻转符号位。
    • 使用转义字符来编码字符串，并在末尾添加分隔符。
    • 通过逐列比较来处理多列比较。
  • 范围查询：Scanner 结构体是 B+ 树迭代器的包装器。
    • dbScan 函数选择合适的索引，然后执行查询。
  • 将缺失的列编码为无穷大：使用 "\xff" 作为 +∞，使用 "" 作为 -∞。
    • 通过添加列类型代码作为标签，来支持前缀列上的范围查询。
    • 使用 encodeKeyPartial 函数为输入范围进行编码。

第 10 章：二级索引

  • 二级索引：通过在更新时删除旧的索引键并插入新的索引键来维护二级索引。
  • 多键更新的原子性：多个键涉及的更新会丢失原子性，需要回滚到之前的状态。
  • 事务接口：
    • 添加 Begin、Commit 和 Abort 接口来允许原子执行一组操作。
    • 使用 copy-on-write 来实现原子性，commit 和 rollback 都只是更新根指针。
  • 替代方案：使用日志来实现原子性，在日志 fsync 后，DB 可以将成功返回给客户端。

第 11 章：原子事务

  • 将树操作移动到事务：将树操作与事务关联，并将它们移动到 KVTX。
  • 事务表操作：为基于表的接口添加包装类型 DBTX。
  • 可选择的优化：
    • 减少多键更新时的复制.
    • 压缩公共前缀。

第 12 章：并发控制

  • 并发级别：
    • 讨论了并发客户端的事务操作，区分了只读事务和读写事务。
    • 介绍了读者-写者锁（RWLock）。
    • 介绍了读取-复制-更新（RCU）。
    • 介绍了乐观并发控制和悲观并发控制。
  • 快照隔离：使用 copy-on-write，事务操作在 B+ 树的快照上。
    • KVTX 结构体包含一个只读快照和本地更新。
    • Get 函数首先从 KVTX.pending 中读取，然后从 KVTX.snapshot 中读取。
    • CombinedIter 结构体用于合并两个树的范围查询。
  • 空闲列表中的版本号：
    • 为每个版本分配一个单调递增的版本号。
    • 空闲列表永远不会给出比最旧事务更新的页面。
  • 处理写入冲突：
    • 将所有读取添加到 KVTX.reads。
    • 将每个成功提交添加到 KV.history。
    • 使用 detectConflicts 函数检测冲突。
    • 序列化内部数据结构。

第 13 章：SQL 解析器

  • 语法、解析器和解释器：
    • 查询语言是解析为树结构用于进一步处理的字符串。
    • 示例：SELECT 语句和表达式的树表示。
    • 通过访问树节点来评估表达式.
    • 介绍了 INDEX BY 和 FILTER 子句。
    • 使用 QLNode 结构体表示表达式树节点.
  • 递归下降：
    • 每个语句都被划分为更小的部分，包括表达式节点 QLNode.
    • QLSelect、QLUpdate 和 QLDelete 结构体表示不同类型的语句。
    • 顶级解析器函数 pStmt 确定语句的类型，然后将其分派给具体的函数。
    • pKeyword 函数匹配和消耗输入中的关键字。
    • 将输入分成越来越小的部分，直到结束为一个操作符、名称或文字值。
    • 使用递归将中缀操作符转换为二叉树。
    • pExprOr 是解析表达式的最高级函数，调用 pExprAnd 等低优先级函数。

第 14 章：查询语言

  • 表达式评估：使用 QLEvalContex 结构体评估表达式。
    • qlEval 函数评估表达式树。
  • 范围查询：
    • QLScan 结构体表示一个范围查询。
    • qlScanInit 函数初始化扫描器，将 QLNode 转换为 Record 和 CMP_??。
    • 根据 Key1 和 Key2 的类型来设置比较操作符。
  • 重新审视无穷大编码：使用空元组来处理仅使用前缀的查询。
    • 使用 covered 函数来判断索引是否覆盖。
  • 结果迭代器：
    • RecordIter 接口定义了迭代器的通用接口。
    • qlSelectIter 结构体用于在 SELECT 中计算表达式。
    • qlScanIter 结构体处理过滤。
  • 结论和下一步：总结了实现的多个接口，以及下一步的计划。
    • 创建一个网络协议，让 DB 在不同的进程或机器上运行。
    • 创建一门编程语言并编译为机器代码。
社交媒体
Github
友链
鸟窝
鸟窝 © 2025 All Rights Reserved.