type
status
date
slug
summary
tags
category
icon
password
这是一个 磁盘空间管理器（disk space manager） 的文档注释，描述了其分页机制、元数据结构和虚拟页编号规则。以下是该注释的翻译与结构解析：
系统概述：Disk Space Manager
该管理器实现了 虚拟页地址映射（virtual page translation），使用两级页目录：
页结构：
- 每个 header page：
- 包含一个位图（bitmap），指示哪些数据页已被分配
- 管理 32K 个数据页
- master page：
- 包含每个 header page 的分配统计信息（用 16-bit 整数表示）
- 每个 master page 可追踪最多 2K 个 header pages（即：2K × 32K = 64M 数据页）
单个分区最大可管理：64M 个 data pages
缓存策略：
- master page 和 header pages 常驻内存
- 每次修改都会立即写回磁盘
- 内存开销小：128MB 分区仅需缓存 2 页（master + 一个 header）
该缓存机制独立于 buffer manager。
虚拟页编号（Virtual Page Numbers）
- 使用 64-bit 整数（Java long）表示
- 编号格式为：
其中：
partition_number是分区编号
n是该分区中第 n 个数据页（从 0 开始）
✅ 优点：易于调试，如：10000000006 表示分区 1 的第 6 页，而不是解析二进制组合出来的编号。
文件结构（每个分区对应一个 OS 文件）：
- 第 0 页：master page
- 第 1 页：第一个 header page
- 第 2～32769 页：该 header page 管理的 32K data pages
- 第 32770 页：第二个 header page
- 接下来的 32K 页：由第二个 header page 管理
- 依此类推...
总结重点：
概念 | 数值/结构 |
Header 管理页数 | 32K data pages |
Master 管理 header 数量 | 2K headers → 最多 64M data pages |
页编号格式 | partition × 10¹⁰ + page_in_partition |
缓存策略 | header/master 常驻内存，立即刷新磁盘 |
OS 文件结构 | 第 0 页 master，第 1 页起为 header 和数据页 |
为什么这么设计？
这个磁盘空间管理器的设计背后有几个非常清晰的工程动机，它解决的是如何高效地管理超大规模页空间的问题，并在性能、可扩展性、可调试性、与文件系统集成之间做了平衡。我们来拆解设计背后的 5 个核心原因：
1. 两级目录结构是为了高扩展性
问题：
直接用一张页表管理几百万甚至几千万个页，会导致：
- 巨大的元数据（位图或数组）
- 线性查找和更新变慢
- 难以持久化、分区
解法：
Master Page + Header Pages 二级结构
- 每个 header 管 32K data pages
- 每个 master 管 2K headers → 总共 64M 页
这种分层结构就像页表（Page Table）一样，有效降低了元数据的内存需求，也方便分段缓存。
2. 页编号设计便于调试与分区隔离
页编号格式：
好处：
- 简单一眼看懂是哪一个分区的哪一页（调试友好）
- 而不是复杂的 bit manipulation：例如
upper 32 bits = partition，难以肉眼解析
举个例子：10000000006就是分区 1 的第 6 页，看起来一目了然。
3. 主索引页和目录页常驻内存，性能更高
- 这两个页是页管理的“导航图”
- 常驻内存意味着：
- 分配页不需要反复读盘
- 查找页快速
- 修改立即刷新，保证一致性
只需缓存 2 页/分区，代价很小！
4. 目录信息结构化，方便页分配与释放
Header pages 使用 bitmap 来管理页分配：
- 哪些 data page 被使用？
- 哪些是空闲的？
- 可以快速找到可分配页
Master Page 存了每个 header 的使用统计，可以快速跳过全满的 header page，定位可能有空位的区域。
5. 与 OS 文件一一对应，简化实现和调试
- 每个 partition 对应一个文件（OS-level file）
- 页的布局按序号安排：第 0 页是 master，第 1 页是 header...
好处：
- 简单易查找
- 无需特殊映射结构
- 利于调试与故障恢复（能按编号定位）
总结一句话：
这个设计像是“多级页表 + 文件分区 + 可调试编号 + 局部缓存”的结合体，目标是在大规模数据页管理下，实现高效、清晰、可扩展的磁盘管理。
整体结构说明：Disk Space Manager 流程图
我们可以把这个流程拆成 4 个步骤，如下所示：
Step 1: 请求分配虚拟页（Virtual Page）
用户发起一个操作，比如：
这表示我们要在某个分区中分配一个新的 data page。
Step 2: 访问 Master Page
系统从磁盘或缓存中读取该分区的 Master Page（第 0 页），这里保存了：
- 该分区下每个 header page 管理的使用情况（空闲页数量）
目的：快速找到可能有空间的 header page
Step 3: 查找 Header Page
根据 Master Page 的信息，我们选中一个 尚有空闲页的 Header Page（比如第 1 页、第 32770 页等）
Header Page 中有一个 bitmap，它标记了：
- 哪些 data page 是空闲的（0）
- 哪些已经分配了（1）
Step 4: 分配 Data Page + 更新元数据
在这个 header page 下，我们找到第一个空位（比如 bitmap 中第 24 位是 0）：
- 将该位设置为 1（表示分配）
- 更新 Master Page 中该 header 的已用计数
- 返回对应的虚拟页号，例如：
假设
partition_id = 3，这是 header 的第 2 个页、第 24 个位置：总结：流程图逻辑串联起来就是——
为什么要设计 Partition？
在数据库系统中，磁盘空间管理器的目标是高效管理 海量页空间，如果整个数据库所有页都用一个统一的地址空间管理，会遇到几个问题：
单一大文件的问题：
- 元数据巨无霸（header bitmap 太大）
- 难以并发扩展和维护
- 跨表、跨事务资源难隔离
- 文件系统本身可能对单文件大小有限制
使用 Partition 的优点：
优点 | 描述 |
物理隔离 | 每个 partition 是一个独立文件，便于维护和备份 |
逻辑隔离 | 可以按表、索引、日志等类型分配不同 partition |
并行扩展 | 多个 partition 可并行访问，提高 I/O 吞吐 |
易于调试 | virtual_page_number 中包含 partition_id，定位直观 |
轻量索引 | 每个 partition 只需一个 master page 和 header 目录即可 |
每个 Partition 是什么？
每个 partition 就是一个 数据库文件（OS file），它的内部结构如下：
页编号 | 类型 | 内容 |
0 | Master Page | 记录各 header page 的使用统计 |
1 | Header Page 1 | 管理 data page 0～32K-1 的位图 |
2～32769 | Data Pages | 真正存放记录的数据页 |
32770 | Header Page 2 | 管理 data page 32K～64K-1 |
... | ... | 每 32K 页对应一个 header 页 |
虚拟页编号中的 Partition 是怎么用的？
系统定义虚拟页号格式为：
举个例子：
virtual_page_number = 20000001234
- 说明这是 第 2 个 partition 中的第
1234页
这个编号设计既能保证全局唯一，又容易拆解出分区信息。
总结一下 Partition 的设计哲学：
“Partition 是数据库页空间的物理与逻辑分片单位，提供了隔离性、可扩展性、并发性与易维护性。”
Partition 的分配策略
数据库系统在底层如何将逻辑对象（如表、索引、日志等）映射到具体的 partition（磁盘分区 / 文件），这一点直接影响系统的 可扩展性、并发性、数据隔离能力，属于 空间分配的核心设计策略。
1. 按用途（Usage-Based Partitioning）
每种用途一个 partition：
Partition ID | 用途（例子） |
0 | 系统元数据（catalog） |
1 | 表（user table） |
2 | 索引（B+ Tree） |
3 | 日志 / undo log |
4 | 临时表 / 工作区 |
优点：
- 物理隔离，不同类型数据独立管理
- 日志、临时页可以快速清空、分区独立销毁
- 容易设置缓存策略（例如：日志页高频写、表页高频读）
2. 按对象（Object-Based Partitioning）
每个对象（表/索引）一个 partition：
Partition ID | 对象类型 | 名称 |
10 | 表 | Users |
11 | 表 | Orders |
12 | 索引 | idx_date |
优点：
- 强隔离性：单个表可独立备份、回滚、压缩
- 容易按对象统计页数、增长趋势
- 更便于并发访问（页表不会成为瓶颈）
❗ 缺点：对象太多会导致 partition 数量过多，master/header 内存占用提升
3. 按空间大小或页数（Capacity-Based Partitioning）
分区达到阈值则开启新 partition：
比如：每个 partition 最多 100MB，当满了就新建一个
Partition ID | 状态 |
0 | 满 |
1 | 满 |
2 | 当前活跃分配区 |
优点：
- 动态扩展，不提前绑定逻辑对象
- 大型对象（如堆表）可跨多个 partition 分布
📍 常用于：Log-structured merge trees (LSM)、分片（sharding）等系统中
实际系统中的混合策略
现代数据库通常混合使用以上策略，例如：
- 系统页、日志页 → 固定用途的 partition
- 每个表/索引 → 单独分配 partition
- 表特别大时再用 paging 或动态扩展
🔧 如何选择策略？
目标 | 推荐策略 |
高并发隔离 | 按对象 |
简单实现、空间节省 | 按用途 |
可动态扩展 | 按容量 / 动态创建 |
容灾/备份友好 | 按对象 + 按用途结合 |
延伸应用：支持并行 IO
多个 partition → 多个文件 → 可以用 多个磁盘或线程并发读写
→ 带来显著吞吐量提升，尤其在 SSD 或分布式系统中效果明显
Partition Allocator 的设计模式
目标：在数据库内部如何 生成 / 分配 / 管理 partition ID 和对应文件
背景回顾
我们知道每个 partition 对应一个磁盘文件（如
partition_0001.db），并用一个整数 partition_id 唯一标识它。所有虚拟页号都是：所以 partition allocator 的职责是：
功能 | 描述 |
分配新 partition ID | 不冲突，不重复，可回收 |
持久化映射关系 | 记录 partition_id ↔ 文件路径 |
提供查找接口 | 能根据 virtual_page_number 快速定位分区文件 |
管理生命周期 | Drop 时释放 partition，避免泄漏 |
常见分配策略
① 自增分配（Monotonic Counter）
优点：简单实现、递增编号、调试方便
缺点：drop 后不能复用 ID，长期增长（但通常问题不大）
② 空洞复用（Gap Filling）
- 维护一个 空闲 ID 集合（free list）
- 优先复用已被 drop 的 partition_id
优点：节省编号空间
缺点：实现复杂些，需持久化
free_ids 状态③ 哈希分配（Hash-Based）
如果 partition 与某种逻辑对象强绑定，比如：
优点：可快速查找
缺点：不适合动态增长或管理生命周期（hash 冲突难处理）
文件名 & 路径策略（配合编号）
Partition ID | 文件路径示例 |
0 | data/part_0000.db |
42 | data/part_0042.db |
12345 | data/part_12345.db |
- 规则命名有助于调试、自动化、恢复
- 你还可以加用途前缀，比如
index_part_001.db、log_part_007.db
元数据持久化建议
为了让系统重启后还知道有哪些 partition，建议维护一个持久化的映射表：
这个文件可以叫做
partition_catalog.meta 或类似名字。🔧 接口设计建议（伪代码）
延伸功能
功能 | 实现点子 |
truncate/drop 表 | 删除对应 partition 文件 + 回收 ID |
压缩 partition ID 空间 | 重建 ID 映射表（需要全局迁移） |
版本控制 | 文件命名加 .v1, .v2 标记 |
总结
设计目标 | 推荐实现方式 |
简洁、调试方便 | 自增分配 + 显式命名 |
节省 ID 空间 | 空洞复用 + 持久化 free list |
快速恢复 | 映射表持久化 ( partition_catalog) |
易扩展 | 封装为模块，提供独立接口 |
partition num 如何分配？
这段 Java 代码是一个 分配新的 partition 的内部辅助方法
allocPartHelper，核心任务是：在磁盘上创建并初始化一个新分区，并将其注册到系统的 partition 管理结构中，同时配合事务和日志系统完成持久化记录。
方法签名
- 传入参数：
partNum是即将分配的新 partition 的编号（ID）
- 返回值：成功创建的 partition ID（即
partNum）
步骤解析
我们按顺序分段讲：
1. 获取全局管理器锁（managerLock）
说明：整个 DiskSpaceManager 是并发访问的，要先锁住它，避免多个线程同时改 partition 表。
2. 验证该 partition 不存在
说明：确保没有重复分配同一个 partition（防止覆盖已有文件或元数据冲突）
3. 创建 PartitionHandle 并注册
说明：
PartitionHandle是这个 partition 的运行时句柄（包含锁、路径、状态等）
- 注册到
partInfo映射中：Map<partNum, PartitionHandle>
4. 给这个 partition 单独加锁
注意：虽然你释放了全局锁 managerLock，但现在你已经锁住了具体这个 partition，防止别的线程操作它。
5. 日志记录：记录这个分区已被分配
说明：
- 如果当前有活跃事务（即不是 crash 恢复阶段），就要写一条 WAL 日志（Write-Ahead Logging）
- 日志内容是："Transaction X 分配了 partition Y"
这是数据库恢复机制的一部分！
6. 打开分区对应的文件/目录
实际上是去创建或打开 db/partitions/00042/ 这样的目录结构和初始文件（如 master page）
7. 成功返回分配的 partition ID
8. 释放 partition 的锁
保证锁释放在 finally 中，即使前面出异常也能释放
总结流程图式说明
为什么这样设计？
设计点 | 目的 |
两级锁（managerLock → partitionLock） | 控制粒度，避免死锁 / 粗粒度锁 |
日志记录 | 支持事务 + 崩溃恢复（WAL） |
PartitionHandle 抽象 | 解耦 partition 的状态与操作 |
延迟 open 操作 | 避免 manager 和 log manager 死锁 |
为什么要给这个 partition 单独加锁？
即这句代码：
是在对某一个 partition 的结构和资源加独立锁，即使我们已经在外层用了全局锁
managerLock。为什么还要多此一举？其实背后是非常精妙的并发控制设计。核心目标：细粒度并发控制，避免竞争与死锁
背景回顾：两种锁
锁名 | 作用范围 | 作用时机 |
managerLock | 全局 partition 注册表 | 用于管理 partInfo（如 put） |
partitionLock | 某个具体 partition 的内部 | 用于操作 partition 文件/状态 |
为什么要再加 partitionLock？
1. 允许并发创建多个 partition
如果你只用
managerLock，每次只能创建一个 partition，别的线程全阻塞（性能低）。而用这种设计：
- 短时间持有
managerLock：只用来注册PartitionHandle
- 然后立即释放
- 再用
partitionLock来保护真正的操作（如 open 文件）
多个线程可以并行地创建不同 partition，彼此互不干扰！
2. 保证 partition open 和初始化是原子的
open() 是涉及文件系统、页表、日志的复杂操作，可能失败或并发修改。如果没有
partitionLock，你可能遇到这种情况：- 线程 A 正在 open
- 线程 B 也来读或写这个 partition
- 会造成 状态不一致或文件损坏
加锁可以避免这种 race condition，确保 partition 的生命周期行为是原子的、串行的、安全的。
3. 支持未来对 partition 的并发访问
比如你以后实现：
你就可以让多个线程并发访问 不同的 partition，但一个 partition 依然是串行访问。
这是典型的 per-resource concurrency control 模式。
如果不加 partitionLock 会怎么样？
- 如果多个线程操作同一个 partition，可能会同时 open 两次、并发写文件，导致 crash 或数据损坏
- 在恢复过程中（涉及 WAL 日志和文件状态）也可能出错
- 未来实现多线程读写页时，无法实现正确并发
总结一句话：
partitionLock 的设计是为了实现对每个 partition 的“最小隔离单元”保护，它允许系统同时管理多个 partition，又能保证每个 partition 自身是线程安全的。
多线程 Partition 分配流程：锁依赖与调度表
步骤 | Thread A ( allocPartHelper(42)) | Thread B ( allocPartHelper(43)) | 说明 |
① | managerLock.lock() | 等待 managerLock | A 先抢到 manager 锁 |
② | validatePartitionUniqueness(42) | — | A 验证 partNum 唯一性 |
③ | PartitionHandle(42) 创建 + 注册 | — | 注册到 partInfo |
④ | partitionLock(42).lock() | — | 加细粒度锁 |
⑤ | managerLock.unlock() | managerLock.lock() 成功 | A 释放后，B 拿到 manager 锁 |
⑥ | — | validatePartitionUniqueness(43) | B 验证唯一性 |
⑦ | — | PartitionHandle(43) 创建 + 注册 | B 注册 |
⑧ | — | partitionLock(43).lock() | B 加自己的 partition 锁 |
⑨ | 写 WAL: logAllocPart(42) | 写 WAL: logAllocPart(43) | 各自记录日志（事务存在时） |
⑩ | pi.open("dbDir/42") | pi.open("dbDir/43") | 打开各自 partition 目录 |
⑪ | partitionLock(42).unlock() | partitionLock(43).unlock() | 释放锁，完成初始化 |
图解锁依赖（逻辑流程）：
并发安全性分析
点 | 说明 |
✅ 全局注册安全 | managerLock 确保不会同时注册两个 partition |
✅ 局部互斥 | partitionLock 保证每个 partition 的 open 是串行的 |
✅ 高并发 | 不同 partition 并发创建、独立加锁，无阻塞 |
✅ 无死锁 | 所有线程按相同顺序加锁：manager → partition，避免循环依赖 |