MonadDb : Monad 定制的状态数据库

区块链节点需要数据库。每次 EVM 读取账户余额、加载合约代码或检查存储槽时，它都在从一个名为状态 trie 的数据结构中读取数据——一个 Merkle-Patricia Trie，它将键（账户地址、存储槽）映射到值（余额、nonce、字节码）。每次执行交易时，trie 都会更新，并计算出一个新的状态根哈希，该哈希以密码学方式提交到整个状态。

该数据库的性能直接决定了节点执行交易的速度。如果每次状态访问都需要通过多层间接寻址进行多次磁盘读取，那么执行速度就会受到存储延迟的瓶颈限制，而与 CPU 的速度无关。

MonadDb 是 Monad 定制的状态数据库。MonadDb 没有使用现成的键值存储，而是将 Merkle-Patricia Trie 实现为一流的磁盘数据结构，具有异步 I/O 和 SSD 感知的存储布局。本文解释了为什么这很重要以及它是如何工作的。

通用键值存储的问题

大多数以太坊客户端将状态 trie 存储在通用键值存储中，如 LevelDB、RocksDB 或 LMDB。这些都是成熟、经过充分测试的数据库，围绕着它们自己的内部数据结构构建：B 树 (LMDB) 或日志结构合并树 (LevelDB, RocksDB)。

通过使用 trie 节点哈希作为键，并使用序列化的节点数据作为值，trie 嵌入在 KV 存储中。要查找一个账户，客户端从根开始遍历 trie，并在每一层发出一个 KV 查找（例如，B 树遍历）以通过其哈希获取下一个节点。

这创建了一个数据结构分层问题：客户端正在遍历一个树（Merkle-Patricia Trie），该树存储在另一个树（B 树或 LSM 树）中。单个账户查找可能需要 6-8 个 trie 层级，并且每个层级都需要一个独立的 KV 查找，每次查找本身可能需要在 KV 存储的内部结构中进行多次磁盘读取。间接寻址会加剧。

除了读取路径外，写入也会受到影响。LSM 树在内存中缓冲写入，并定期将其压缩到磁盘，在此过程中会重写大量数据。这种写放大——即单个逻辑写入导致多次物理写入——是基于 LSM 树的存储的一个众所周知的成本，并且它与执行所需的读取竞争 SSD 带宽。

MonadDb：trie 就是数据库

MonadDb 通过直接将 Merkle-Patricia Trie 实现为磁盘数据结构来消除间接层。Trie 节点不是通过通用索引按哈希查找，而是通过直接物理指针定位。

trie 中的每个节点都为其每个子节点存储一个 chunk_offset 值，该值编码了子节点的精确磁盘位置。当从父节点遍历到子节点时，没有索引查找，没有哈希表探测，没有 B 树下降。父节点精确地知道子节点在磁盘上的位置，并且 I/O 子系统可以发出读取以精确读取这些字节。

本节解释了使这项工作生效的关键设计要素。

Trie 节点结构

查看代码：category/mpt/node.hpp MonadDb 使用了一个广义的 trie，它扩展了标准的以太坊 Merkle-Patricia Trie。节点最多可以有 16 个子节点（每个十六进制 nibble 一个），一个可选的键路径和一个可选的值。这些泛化允许单个节点扮演双重角色——例如，一个节点可以同时是一个扩展（具有路径）和一个分支（具有多个子节点），或者是一个具有叶子值的分支。

节点的磁盘表示形式按顺序打包以下数据：

1. 头部字段：一个 16 位子掩码（指示 16 个可能的子节点中的哪些存在），一个位打包字节（has-value 标志、路径 nibble 索引、中间哈希缓存大小）、值长度和一个版本号（此节点上次更新的区块号）。

2. 子偏移量数组：对于每个存在的子节点（如掩码所示），一个 8 字节的 chunk_offset 指向子节点的磁盘位置。

3. 压缩元数据：每个子节点的最小偏移量和最小版本，用于以每个子节点为根的子 trie。这些字段使压缩器能够确定哪些存储区域仅包含过期数据。

4. 子数据偏移量数组：每个子节点的 2 字节偏移量，指向子数据部分。这允许在不扫描的情况下定位任何子节点的数据。

5. 路径：此节点的 nibble 路径（可变长度），用于 trie 中的前缀压缩。

6. 值：面向用户的叶子数据（可变长度）——例如，账户的 nonce、余额和代码哈希的 RLP 编码。

7. 中间哈希缓存：对于既是一个子 trie 的叶子又是另一个子 trie 的根的节点（例如，以存储 trie 为根的账户节点），一个缓存的中间哈希。

8. 子数据：所有子节点的哈希数据，连接在一起。这是高效哈希计算的关键——见下文。

9. 内存中的子指针：当一个节点加载到内存中时，会附加空间用于指向已经在内存中的子节点的 shared_ptr 引用。这些指针不会持久化到磁盘。

内联子数据：避免读取哈希

一个中心设计选择是将每个子节点的哈希数据内联存储在父节点中。在标准实现中，计算节点的 merkle 哈希需要读取其所有子节点以检索其哈希。在 MonadDb 中，这些哈希已经嵌入在父节点的磁盘表示形式中。

这意味着，当 trie 更新并且需要沿着从修改后的叶子到根的路径重新计算哈希时，该路径上的每个节点都已经包含其所有子节点所需的哈希数据——它只需要重新读取单个已更改的子节点。哈希重新计算所需的磁盘读取次数与修改的深度成正比，而不是与分支因子成正比。

chunk_offset：64 位中的位置 + 大小

查看代码：category/async/config.hpp trie 中的每个子指针都是一个 64 位 chunk_offset，打包为位字段：

MonadDb 使用 15 个备用位来编码子节点的磁盘大小，表示为带有移位的页数：

这意味着单个 64 位值告诉 MonadDb 节点的位置和要读取的字节数。当 I/O 子系统收到子节点的读取请求时，它可以发出精确大小的读取，而无需进行初步 I/O 来确定节点的大小。编码是近似的（它会向上取整），因此读取可能会获取稍微多于必要的字节，但绝不会更少。

使用 io_uring 进行异步 I/O

查看代码：category/async/io.hpp 并行事务执行意味着多个事务正在并发执行，每个事务都可能读取状态 trie 的不同部分。如果磁盘读取阻塞调用线程，则并行性受到线程数的限制，并且大多数线程将其时间花费在等待 I/O 上，而不是执行有用的工作。

MonadDb 使用 Linux 的 io_uring 接口进行完全异步的磁盘 I/O。当 trie 遍历到达一个不在内存中的节点时，它会向 io_uring 提交队列提交一个读取请求，并屈服控制（通过轻量级的 Boost Fiber 协程），以便可以进行其他工作。当内核完成读取时，会从 io_uring 完成队列中获取完成，并恢复等待的纤程。

这允许数百或数千个并发状态读取同时处于活动状态，所有这些读取都通过少量 OS 线程进行多路复用。并发读取的数量是可配置的（对于读写数据库默认为 1024，对于只读数据库默认为 600），提供背压以避免压垮存储设备。

读取缓冲区分两层管理：

• 短读取（最多 4 KB）：从预先分配的固定大小缓冲区池中提取，避免每次读取都分配内存。

• 长读取（超过 4 KB）：使用直接 I/O 所需的对齐方式动态分配。

存储布局：块和区域

查看代码：category/async/storage_pool.hpp MonadDb 将其存储划分为 256 MB 的块，灵感来自 NVMe zoned namespace (ZNS) 存储。即使在传统的 SSD 上运行，MonadDb 也会模拟分区存储语义，将原始块设备或文件划分为两种类型的块：

• 传统块 (cnv)：用于需要随机访问的元数据，例如根偏移量环形缓冲区和数据库元数据。通常这些块的数量很少（默认值：每个设备 3 个）。

• 顺序块 (seq)：用于 trie 节点数据。这些块被视为仅追加：新节点按顺序写入到当前块的末尾，一旦块已满，写入将移动到下一个块。一旦不再需要旧块中的数据，就可以批量回收旧块。

顺序写入模式具有显着的 SSD 性能优势。SSD 在内部将 NAND 闪存组织成大型擦除块。对任意位置的随机写入会产生碎片，迫使 SSD 的垃圾收集器在可以回收部分使用的擦除块之前，先将活动数据复制出擦除块——这个过程会消耗带宽并不可预测地增加延迟。通过顺序写入并一次性回收整个块，MonadDb 避免了这种内部碎片。回收块后，MonadDb 会发出 TRIM 命令，允许 SSD 有效地回收底层闪存块。

在支持 NVMe 分区命名空间的设备上，顺序块直接映射到设备的仅追加区域，完全绕过 SSD 的内部块设备模拟层。这可以将读取延迟从典型的 ~70 微秒降低到 15-30 微秒，因为从顺序区域的读取直接转到 NAND 闪存，而无需通过 SSD 的闪存转换层。

文件系统旁路

MonadDb 可以直接在原始块设备上运行，完全绕过文件系统。这消除了文件系统开销，包括块分配、目录元数据管理和日志记录。MonadDb 通过块系统管理自己的块分配，该块系统比通用文件系统更简单、更可预测，因为访问模式是预先知道的。

持久性 Trie：无锁版本控制

查看代码：category/mpt/db.hpp MonadDb 使用持久性（在函数式编程意义上） trie 结构。当一个区块更新某些账户时，MonadDb 不会就地修改现有节点。相反，它会创建修改后的节点的新版本，并将它们写入磁盘上的新位置。旧节点保持完好，并且可以在其原始位置读取。

这意味着状态 trie 的多个版本共存于磁盘上，每个版本都可以通过其根偏移量访问。传统块中的环形缓冲区存储每个区块号的根偏移量，允许通过区块号查找任何历史版本（在保留窗口内）。

持久性模型具有重要的并发优势。访问特定区块号状态的读取器通过 trie 的不可变快照跟踪指针——它们永远不会观察到部分写入的更新，并且它们不需要任何锁或与写入器的协调。这正是区块链节点所需要的，在区块链节点中，执行引擎正在写入新状态，而 RPC 服务器和共识层正在并发读取各种最新区块高度的状态。

版本跟踪

每个 trie 节点都记录了上次更新的区块号（在版本字段中)。对于叶子节点，这是上次修改值的区块。对于内部节点，该版本至少与子 trie 中任何叶子的最大版本一样大。

这种按节点版本控制支持高效的历史记录过期。压缩器可以检查子 trie 的最小版本，以确定其任何数据是否在保留窗口内，并跳过已知仅包含当前数据的整个子 trie。

压缩

随着新区块生成新的节点版本，旧版本会在磁盘上累积。MonadDb 通过压缩来回收空间：它遍历活动 trie，将可访问的节点转发复制到新的顺序块，并回收旧块。

块被组织成两个链接列表——一个快速列表和一个慢速列表——它们支持分层存储。热数据（最近写入或经常访问的节点）位于快速列表块中，而冷数据会迁移到慢速列表. 完全压缩的块移动到空闲列表以供重用。

压缩过程与正常更新内联运行，受到限制以避免干扰执行吞吐量。数据库根据可用磁盘空间动态调整其历史记录保留长度。

崩溃安全

查看代码：category/mpt/detail/db_metadata.hpp MonadDb 维护其数据库元数据的两个副本，存储在传统块中。更新在两个副本之间交替进行，因此如果在元数据写入期间进程崩溃，则至少一个副本保持有效。启动时，MonadDb 会读取两个副本并使用一致的副本。

具有基于 Nibble 分区的统一 Trie

查看代码：monad-triedb README MonadDb 将所有区块链数据——账户状态、合约代码、交易收据、区块头和二级索引——存储在一个统一的 trie 中。数据类型由前导 nibble 前缀分隔：

收据、交易和区块头按区块号进行版本控制，因此相同的键结构根据查询的版本（区块号）检索不同的数据。

二级索引（交易哈希和区块哈希）支持标准的以太坊 RPC 查找，例如 eth_getTransactionByHash——给定一个交易哈希，索引返回区块号和交易索引，然后可以使用它们来获取完整的交易数据。

这种统一的方法意味着只有一个存储引擎可以优化，只有一个压缩过程，只有一个缓存层，而不是用于不同数据类型的单独系统。

缓存

查看代码：category/mpt/node_cache.hpp , category/core/lru/lru_cache.hpp MonadDb 维护了一个最近访问的 trie 节点的内存 LRU 缓存，按其虚拟块偏移量进行键控。缓存受内存限制（对于只读数据库，默认为 50 MB），而不是受条目计数限制，并且它跟踪每个缓存节点的实际大小。

平均节点大小约为 104 字节，50 MB 的缓存可容纳大约 500,000 个节点。由于 trie 的上层比叶子访问的频率高得多，因此缓存自然会保留热内部节点，并为典型工作负载提供高命中率。

在 Rust 方面，共识层和 RPC 层添加了额外的缓存。每个区块缓存都会保留最近最终确定的区块的账户数据和区块头，并且 RPC 服务器会预加载最新区块的交易和收据，以在不命中 trie 的情况下处理常见查询。

整合

查看代码：monad-triedb/src/lib.rs MonadDb 的核心（trie、I/O 层和存储池）是在 C++ 中作为执行引擎的一部分实现的。用 Rust 编写的共识客户端和 RPC 服务器通过 C FFI 边界访问数据库。

FFI 接口公开了一小组操作：同步读取、带有回调的异步读取、前缀遍历和范围查询。在 Rust 方面，一个专用的轮询线程驱动 io_uring 完成循环，将 C++ 回调转换为 Rust 通道消息。这使异步 I/O 机制包含在 C++ 层中，同时为 Rust 代码提供了一个用于并发状态访问的干净接口。

Rust 方面相对于 trie 是只读的。状态写入完全发生在 C++ 执行引擎中，该引擎在执行区块时写入新的节点版本。Rust 共识层查询数据库以检查最终确定的状态、读取验证器集和服务 RPC 请求，但它永远不会直接修改 trie。这种分离确保只有一个写入器和多个读取器，这与持久性 trie 的并发模型自然对齐。

• 原文链接： x.com/keonehd/status/202...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～