编者注：本文为历史博文归档；涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。

MapDB 特性

MapDB 是一个内嵌式纯 Java 数据库，提供了并发的 HashMap、TreeMap、Queue 等数据结构，支持基于堆外内存（Off-heap）或磁盘存储数据。用户可以通过配置选择不同的机制来优化性能，例如配置多种 Cache 以减少反序列化开销、提升读取性能；或开启异步写引擎，利用后台线程进行序列化和存储更新，从而提高插入性能并降低响应时间（RT）。

此外，MapDB 还具有以下显著特点：

  • 事务支持：支持 ACID 事务与 MVCC 隔离级别。
  • 轻量级：代码精简，仅包含一个 JAR 包，无其他依赖，体积约 200 KB。
  • 高度模块化：用户可轻松扩展并添加新特性。

MapDB 架构

从下方的类图可以看出 MapDB 的整体脉络。它采用分层设计，遵循面向接口编程的原则：上层仅依赖下层的接口，具体实现可灵活替换。

  • 顶层（API 层）：面向用户的接口，即各种数据结构接口。
  • 中间层（Engine 层）：存储引擎核心模块，提供简单的 Key-Value 接口。管理对象为记录（Record），通过记录 ID（recid）进行操作，用户不能直接使用。
  • 底层（Volume 层）：对原始存储媒介的抽象。MapDB 提供堆内、堆外、磁盘等多种存储媒介实现。

这样的分层设计使得 MapDB 模块清晰，每一层都可以通过实现接口轻松扩展。

MapDB 实现原理

以 BTreeMap (Map) + StoreDirect (Engine) + FileChannelVol (Volume) 为例，我们来分析 MapDB 的存储实现。

核心存储结构

BTreeMap 是 B+ 树的一个实现，非叶子节点存储 Key，叶子节点存储实际的 Value。

B+ 树的核心操作流程如下：从根节点开始，通过 Key 找到对应的叶子节点，将节点读出，然后对节点中的 Value 进行增删改查操作。当单节点元素个数达到某个阈值后，进行节点分裂或者合并。

在 BTreeMap 的实现中，每个节点作为一条记录在 Engine 中维护。引擎对外提供根据 recid 访问记录的接口，例如读接口 Engine.get(long recid, Serializer<A> serializer)。BTreeMap 只需要维护根节点的 recid 就可以访问到整棵树。

记录管理 (StoreDirect)

StoreDirect 通过维护一个索引 Volume和一个物理 Volume来实现基于 recid 的记录管理。

  • 索引 Volume：用来维护索引项序列（每个索引项为 8 字节 long）。
  • 物理 Volume：用来存储实际数据。

每个索引项维护一个物理指针，信息包括记录所在的物理 Volume 的偏移量和记录大小。通过公式 recid * 8 + IO_USER_START 可以找到索引项，再通过索引项就可以找到记录所在物理 Volume 的位置和大小，从而实现通过 recid 访问记录的功能。

存储结构示意：

  • 索引 Volume：每个 slot 为 8 字节的 long。
  • 物理 Volume：每个格子为一个物理页，大小为 16 × N Bytes（最大为 64 KB）。

空间分配机制

索引 Volume 还有一个功能是维护空闲的索引项列表和空闲的物理页列表（均为 FIFO 列表），这些空闲列表被称为 Long stack，维护在索引 Volume 的第 15 到 4111 的 slot 中。

  • 空闲索引项：当某个 recid 被删除，其对应的索引项就成了空闲索引项，被加到空闲索引项列表里。由于每个索引项的大小是固定的，只需要一个列表就可以维护所有的空闲项，索引 Volume 第 15 个 slot 用来维护该列表。
  • 空闲物理页：对应的物理 Volume 空间被释放后，加入空闲的物理页列表。每个物理页最小为 16 Bytes，最大为 64 KB（必须是 16 的倍数），不同的记录使用不同大小的物理页。因为每个记录删除之后所释放的物理页大小可能都不一样，所以需要第 16 到 4111 个 slot 来维护不同尺寸（共 4096 种）的物理页空闲列表，每个 slot 指向对应尺寸的物理空闲页列表。

记录写入流程：

  1. 查找空闲索引列表拿到 recid。如果空闲索引列表不为空，则复用该 recid 的索引项；否则在索引 Volume append 新的索引项，返回新的 recid。
  2. 拿到索引项之后，申请物理页空间。根据记录的大小找到对应的空闲物理页列表，如果有则复用，否则在物理 Volume append 得到新的物理页。
  3. 更新索引项，然后写入数据。

物理页的分配方式类似伙伴系统算法 (Buddy System)，可以减少外部碎片，充分利用空间。当一条记录大于 64 KB 的时候，需要通过链接法，链接多个物理页来存储记录。

扩展性与事务

在这个例子里我们使用的是 FileChannelVol，所以索引 Volume 和物理 Volume 都是存储在文件中的，这是一个基于磁盘的 B+ 树实现。如果我们把 FileChannelVol 替换为 MemoryVol，并启用 useDirectBuffer，那么就是一个堆外的 BTreeMap。

MapDB 在 Engine 模块中还使用了装饰者模式，为引擎添加更多的特性：

  • HashTable：为引擎添加 Hash 缓存。
  • AsyncWriteEngine：添加异步写特性。如果使用堆外存储或者磁盘存储，启用异步写可以减小 RT，提高性能。

对事务的支持则是通过 StoreWAL 来实现，它继承 StoreDirect，通过增加预写日志（Write Ahead Log）的特性来实现事务。

MapDB 提供了丰富的功能，并且具有很强的扩展性，需要用到内嵌数据库或者堆外内存的场景，可以优先考虑。

说明：本文基于 MapDB 早期版本（如 1.x）分析，文中提及的包大小（200KB）及部分架构细节可能随版本迭代有所变化。生产环境使用请参考 MapDB 官方最新文档。