Meshanina --- 专用、WORM、内容寻址数据库

Meshanina 是一个非常奇特的键值数据库，具有三个假设

• 一旦写入，键值映射将永远不会被删除
• 某个函数 H 将每个值映射到每个键： H(v) = k。也就是说，相同的键永远不会被重新绑定到不同的值。

Meshanina 旨在用作 内容寻址 数据存储，其中键通常是值的哈希，删除操作不明确。它是一个纯日志结构的、内容寻址的数据库文件，我们在其中交错放置数据块和 64-ary HAMT 节点。当我们插入键时，我们只是插入大量数据，然后在刷新时确保元数据也被推出去。

在内存中，我们跟踪一串新节点，在它们被刷新出去之前。一切都是以“纯粹函数式”的方式管理的。

磁盘格式

• 4 KiB：保留区域
  • 从 10 个字节开始： meshanina2
  • 然后是额外的 16 个字节的随机、唯一的数据库特定 128 位分隔符
• 不定数量的 记录
  • （可能填充到某些漂亮的边界）
  • 16 个字节：保留区域中存储的魔法分隔符
  • 8 个字节：记录内容的 SipHash 1-3 校验和
  • 4 个字节：记录类型，小端序
    • 0x00000000：数据
    • 0x00000001：HAMT 内部节点
    • 0x00000002：HAMT 根节点
  • 4 个字节：记录长度
  • n 个字节：记录内容
    • 对于 HAMT 节点，这将是
      • 8 个字节：64 位小端序位图
      • n*8 个字节：64 位指针到绝对偏移量
    • 对于数据节点，这将是
      • 32 个字节：键
      • n 个字节：值

恢复

在打开数据库时，有一个恢复机制。我们从文件末尾开始向前搜索魔法分隔符的实例，然后尝试在每个实例处解码一个记录。当我们找到第一个 有效编码的 HAMT 根 时，我们停止。然后我们向前扫描，将此根之后每个有效的数据块重新插入到数据库中。

假设没有“间隙”在正确写入的块中——也就是说，如果一个记录被正确写入，那么它之前的每个记录也必须是正确的——这可以防御任意崩溃和电源中断。基本上，所有 Unix 文件系统都保证中断的文件追加不会干扰文件中的现有数据。

查找和插入

从最新的 HAMT 根节点开始，按照常规 HAMT 查找/插入，每次使用 256 位键值中的 6 位。