Turnkey 压缩 TVC 可验证状态的内存索引
来源标题：Merkle log defragmentation: exploiting our key space to compress an index
Turnkey 通过利用 merkle log 中页号与位置的对应关系，将 TVC Verifiable State 的内存索引从原本 8 TB 卷需超 100 GB 内存大幅压缩，且随写入趋于顺序化持续缩小。该索引支撑基于 QMDB 分支的交互式 merkle 证明协议，使节点可近乎即时地从另一节点派生。
以下正文由 AI 翻译自 Hacker News 最新（原文版权归原站所有），可能存在偏差，重要内容请以原文为准。
关于本文： 了解 Turnkey 如何将 TVC Verifiable State 背后的内存索引从 QMDB 的 merkle log 压缩为一种 bucket 编码，并且这种编码会随着写入变为顺序写而不断缩小。 读者对象： 从事可验证存储、merkle 数据库、TEE 和存储引擎的工程师。
我们来聊聊碎片整理。不是硬盘那种碎片整理，而是对 merkle log 进行碎片整理，让内存索引大幅缩小。
在 TVC Verifiable State 中——这是为运行在 Turnkey Verifiable Cloud（TVC）上的应用提供的持久化存储——一个 8 TB 的卷可能仅仅为了索引其数据和证明就需要超过 100 GB 的内存。通过利用页号与其在 merkle log 中位置之间的关系，我们找到了一种压缩该索引的方法，并且随着系统运行还能持续缩小。
本文介绍这个索引，以及我们如何把它缩小到足以常驻内存，同时仍能近乎即时地从一个节点派生出另一个节点。
TVC Verifiable State 在一个自定义的、高度优化的交互式 merkle 证明协议之上运行一个虚拟用户态块设备，该协议基于 Commonware 优秀的 QMDB 库的一个分支构建。
TVC Verifiable State 在内核看到每一次读写之前，都会在可信执行环境（TEE）内对其进行验证。对于一个 8 TB 的卷，仅上游 QMDB 的内存索引就需要大约 60 GB。
QMDB 是一个 merkle log。从根本上说，它是一个操作日志，其中每个操作都是 merkle log 中的一个位置。操作日志由 merkle 树的上层提交，并且每个操作都会存储它所对应的键。
QMDB 中有一个外部索引，将每个键映射到操作日志中当前持有它的位置。该索引不被 merkle 树提交。
在有序变体中——这是唯一能在 TEE 和零知识（ZK）系统内正确且可靠使用的变体——我们还会在操作日志中存储下一个键。所以这基本上就是一个在操作日志中提交的映射，从每个键映射到数据库中当前的 next key。
这让你能够使用外部索引获取某个键当前存储在 merkle log 中的位置，并从中获取其下一个键的位置。next-key 查找对于排除证明之类的操作是必要的，也对于从一棵 merkle 根到另一棵 merkle 根的状态转换进行无状态验证是必要的，这就是为什么在 ZK 和 TEE 中需要它。
在当前版本的 QMDB 中，还有一个位图，用于跟踪操作日志中每个位置是否仍然活跃。这些位图被嫁接到 merkle 树的另一层中。
真正不幸的是，QMDB 的外部索引始终位于热路径上。如果它存储在磁盘上，你的 merkle 树会慢得离谱。
所以上游的解决方案是将索引存储在内存中，对于有序变体来说，就是一个普通的 Rust std BTreeMap。上游还将活跃位图和嫁接树的顶部保留在内存中，而证明所需的 merkle 节点只是对位置进行算术运算，因此可以一次性全部读取。
这意味着 QMDB 实际上并不进行依赖读取。一次 get 就是一次内存查找，然后一次日志读取。
将索引保留在内存中很好，但它有一个问题，即活跃键的加载时间是 O(n)。节点启动时必须通过重放日志来重建索引和位图。
我们需要让节点能够快速生成，所以这不是一个选项。我希望能够近乎即时地从一个节点派生出另一个节点，而不是等待它重放日志。
我们尝试过从检查点惰性加载索引。但惰性加载还不够。每当所需的那部分索引不在内存中时，你又会回到热路径上访问存储。
现实中你希望这个索引始终在内存中，这意味着它必须很小。
那么让我们讨论一下这个索引的大小。大小由数据库中任意时刻活跃键的数量决定。这没问题，但它是会增长的。
假设你正在编写一个具有 4 KB 页的可验证块设备。一个 8 TB 的卷大约有 20 亿页，一旦它填满，每一页都是一个活跃键。仅键到位置的 BTreeMap 就已经大约 60 GB 了。
不用说，它真的很大，这对于节点的快速启动时间来说并不理想，而且运行 QMDB 的内存需求也非常大。
而且这甚至还不是为了让 QMDB 实例真正快速而需要在 RAM 中存储的全部内容。你还需要知道从哪里获取每个块的内容以及从哪里获取相关的证明记录，以便快速生成 merkle 证明。把这些也放进同一个 BTreeMap，你就超过 100 GB 了。
在 TVC Verifiable State 中，我们幸运地拥有一个受限的键空间。我们的键空间完全由从页号到 4 KB 块的映射组成。它实际上是 u64 到 u64，页号到操作号。
为了解决这个问题，我利用了键空间。
我们利用三个数字之间的自然对齐。
我们的 W 对象——实际包含数据的预写日志对象——具有单调递增的编号。操作日志同样是一个单调递增的 u64。而页号在操作日志中并不是单调递增的。
所以我们看着这些说，好吧，其中几个是一起增长的。有一个不是。但在理想情况下它是的，因为当你进行顺序写入时，操作号和页号实际上确实是一起单调增长的。
所以这给你留下了一个非常可利用的性质，即如果你在键空间中编码这种关系，并尝试增强这种关系，你就可以在内存中拥有一个更小的索引。
（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）
正文由 探How 从来源站点 RSS 同步，内容未经改写；遇到排版缺失或需要图片、视频时请以原文为准。