VLStore 是一个面向论文研究的可验证日志存储原型。项目关注 append-heavy 日志数据上的高吞吐写入、低开销查询和可验证范围查询，核心思路是把日志式写入、learned index 和 Merkle authenticated data structure 结合起来。
当前代码库不是生产级数据库，而是用于验证设计假设、复现实验结果和继续演化算法的研究系统。本文档以当前源码为准，描述已经实现的系统边界、核心模块、查询证明流程和后续开发基线。
VLStore 试图回答的问题包括：
- 如何在日志型工作负载中同时获得顺序写性能和可验证查询能力。
- 如何用 learned index 减少磁盘查询时的索引空间和随机 I/O。
- 如何为范围查询生成可验证证明，并用组件摘要重构全局 digest。
- 如何在内存组件、immutable 组件和磁盘组件之间维护一致的认证状态。
- 如何评估 fanout、epsilon、value size、数据规模、查询选择率等参数对性能和空间的影响。
系统入口是 VLStore，位于 vlstore.go。它维护一个活跃内存表、一组等待刷盘的 immutable memtable、一组磁盘表、组件元数据和页缓存。
Insert
-> active MBTree
-> threshold reached
-> immutable MBTree
-> background flush
-> MerkleLearnedTable on disk
Search / SearchWithProof
-> active MBTree
-> immutable MBTree(s)
-> disk MerkleLearnedTable(s)
-> merge results and verify component digests
当前实现更准确地说是 LSM-like append/flush 架构：内存表满后会生成新的磁盘组件，但尚未实现完整的多层 compaction。早期文档中提到的 run/LevelRun 和 level merge 已经不再是当前主线代码。
.
├── vlstore.go # 顶层存储引擎 API、组件管理、查询证明整合
├── util/
│ ├── config.go # 系统参数
│ ├── type.go # Key、Value、H256、KeyValue
│ ├── hash.go # SHA256 / BLAKE3 哈希接口
│ └── model.go # PGM-style 分段线性模型
├── memtable/
│ ├── mbtree.go # 当前使用的顺序写优化 Merkle B+Tree
│ └── base_mbtree.go # baseline 标准 Merkle B+Tree
├── disktable/
│ ├── mlt.go # MerkleLearnedTable 构建、查询、证明
│ ├── key_pager.go # key -> value position 分页存储
│ ├── value_log.go # append-only value log
│ ├── model_pager.go # learned index 模型分页存储
│ ├── mht_pager.go # MHT 分页构建与证明
│ ├── cache_manager.go # key/model/MHT 页缓存
│ └── mht_pager_subtree.go # 实验性 subtree MHT 页布局
└── draw/ # 论文实验图表
VLStore 是系统的顶层对象，主要字段包括：
configs: 全局参数，包括树 fanout、MHT fanout、PGM epsilon、存储目录、内存表阈值等。memTable: 当前活跃内存表。immutableMemTableVec: 已冻结、等待后台刷盘的内存表。flushImmutableMemTableChan: 通知后台 flush worker 的 channel。diskTableVec: 已刷盘的磁盘组件列表，新的组件插入到列表前部。componentMetaMap: 每个组件的MinKey、MaxKey和Digest。cacheManager: 磁盘 key page、model page、MHT page 的 LRU 缓存。
每个组件都有一条元数据：
type ComponentMeta struct {
MinKey util.Key
MaxKey util.Key
Digest util.H256
}范围查询会先用组件的 key range 判断是否需要访问该组件。若查询范围与组件无交集，证明中只返回该组件 digest；若有交集，则生成该组件内部的 range proof。
memtable.MBTree 是当前默认内存表。它是一个针对顺序写优化的 Merkle B+Tree：
- 新写入先进入临时 leaf
tmp。 tmp达到TreeFanout后一次性提交成真实 leaf。- 新 leaf 通过
last指针追加到树最右侧。 - 每个 leaf 维护 key-value hash，内部节点维护 child hash。
- 支持单点查询、范围查询、range proof 生成和 digest 重构。
这个实现适合日志型、递增 key 或基本有序 key 的负载。对于大量乱序写入，应使用或扩展 BaseMBTree 的标准 B+Tree 插入逻辑。
内存表刷盘后会生成一个 disktable.MerkleLearnedTable。每个磁盘组件由四类文件组成：
k_<componentID>.dat key page: key -> value-log position
v_<componentID>.dat value log: append-only value bytes
m_<componentID>.dat model page: learned index models
h_<componentID>.dat MHT page: Merkle hash tree nodes
key_pager.go 将 KeyPos 按 4KB page 存储：
type KeyPos struct {
Key util.Key
Pos *ChunkPosition
}其中 ChunkPosition 指向 value log 中的 block number、chunk offset 和 chunk size。
value_log.go 实现 append-only value log：
- block 大小为 32KB。
- 每个 value 被写成一个或多个 chunk。
- chunk header 包含 checksum、length 和 chunk type。
- 支持单条
Read和批量ReadBatch。
model_pager.go 使用 util.ModelGenerator 生成 PGM-style 分段线性模型。模型以 key 预测其在 key array 中的位置：
predicted_position = slope * (key - start) + intercept
Epsilon 控制预测误差上界。查询时先由模型预测位置，再读取 [pred - epsilon, pred + epsilon] 附近的 key page 进行精确查找。
当模型页不止一页时，系统会递归构建上层模型，使顶层模型页可以定位下层模型页。
mht_pager.go 将 key-value hash 构造成 MHT，并按 page 写入。磁盘范围证明由两部分组成：
- 非叶子层证明：从 MHT page 中读取范围路径外的 sibling hashes。
- 叶子层证明：读取边界附近 key/value，计算范围外 sibling leaf hashes。
MHT fanout 由 Configs.Fanout 控制。
- 调用
VLStore.Insert(key, value)。 - KV 写入 active
MBTree。 - 更新 active component 的
MinKey、MaxKey和Digest。 - 若
memTable.KeyNum() >= BaseStateNum：- 当前 memtable 变为 immutable memtable。
- 创建新的 active memtable 和 component id。
- 将旧 memtable 发送给后台 flush worker。
- flush worker 调用
ConstructRunByInMemoryTree构造磁盘组件。 - flush 完成后：
- 用磁盘 MHT root 更新组件 digest。
- 从 immutable 队列移除该 memtable。
- 将新磁盘表插入
diskTableVec。
当前 flush 是异步的，因此性能实验中经常会在写入后等待一段时间，以确保磁盘组件构造完成。
VLStore.Search(key) 按以下顺序查找：
- active memtable。
- immutable memtable 列表。
- disk table 列表。
查询前会用 ComponentMeta.MinKey/MaxKey 做快速过滤。磁盘查询使用 learned index 预测 key 位置，再读取有限范围的 key page，最后从 value log 读取 value。
VLStore.SearchWithProof(startKey, endKey) 会为所有组件构造一个 VLStoreProof：
- 若组件 key range 与查询范围无交集，证明中只记录该组件 digest。
- 若组件 key range 与查询范围有交集：
- memtable 生成
memtable.RangeProof。 - disk table 生成
disktable.TableProof。
- memtable 生成
VerifyAndCollectResult 会：
- 并行重构每个 memtable 和 disk table 的 digest。
- 按组件顺序拼接 digest，重构全局 root。
- 与查询前获得的
rootHash比较。 - 合并所有组件返回的 KV。
- 按 key 排序并过滤到
[startKey, endKey]。
全局 digest 的计算方式是：
Root = BLAKE3(concat(component_digest_1, component_digest_2, ...))
util.Configs 当前定义如下：
type Configs struct {
TreeFanout int // MBTree fanout
Fanout int // MHT fanout
Epsilon int // learned index prediction error bound
DirName string // storage directory
BaseStateNum int // active memtable flush threshold
SizeRatio int // reserved for future LSM level design
}构造示例：
configs := util.NewConfigs(
8, // TreeFanout
2, // MHT Fanout
86, // Epsilon
"data_dir", // DirName
64000, // BaseStateNum
)
store := vlstore.NewVLStore(configs)运行全部测试：
go test ./...只运行较小的功能测试时，建议指定测试名。部分测试是论文实验或性能评估，会写入大量数据并运行较久。
go test ./memtable -run TestRangeSearch
go test ./disktable -run TestProveAndVerify
go test . -run TestVLStoreVerifyQuery当前测试覆盖了：
- MBTree 顺序写入、查询、范围查询、证明。
- BaseMBTree baseline 行为和性能。
- PGM 模型生成、预测和序列化。
- key page、model page、MHT page、value log 的序列化和读写。
- MerkleLearnedTable 的构造、查询和证明验证。
- VLStore 端到端写入、查询、范围证明、空间占用和吞吐实验。
这些限制是后续开发和论文实现整理时需要优先确认的边界：
- 尚未实现完整的持久化恢复。
Load和getMeta仍是未完成状态，组件列表和componentMetaMap不能可靠从磁盘恢复。 - 尚未实现真正的多层 LSM compaction。当前磁盘组件是 flush 产生的 run 列表。
- 当前默认
MBTree针对顺序写优化，乱序 key 的正确性和性能不应直接假设。 - 顶层并发控制还不完整。
Insert、flush worker 和查询路径之间仍可能存在数据竞争。 SearchWithProof和磁盘证明路径中有调试打印，会影响性能测量和库化使用。- 错误处理仍偏研究原型风格，部分路径使用
panic。 mht_pager_subtree.go是新的 subtree MHT 实验实现，目前尚未接入主磁盘表查询路径。
为了把 VLStore 作为稳定研究基线继续推进，建议按以下顺序整理：
- 明确工作负载假设：顺序日志 key、乱序日志 key、是否允许重复 key。
- 完成持久化元数据格式：component id counter、组件顺序、key range、digest、文件名映射。
- 补齐并发控制：active memtable swap、immutable 队列、disk table 列表和 component meta 的一致性。
- 修复查询边界行为：不存在 key、空范围、跨组件重复 key、flush 中查询。
- 将 debug 输出改为可关闭的 benchmark instrumentation。
- 明确是否需要实现 LSM compaction，并定义 compaction 后的 digest 和 proof 语义。
- 比较当前 fanout MHT 与 subtree MHT 的证明大小、I/O 次数和构造成本。
- 把论文实验脚本、数据预处理、图表生成流程固定下来，减少手工步骤。
VLStore 当前最适合作为以下方向的研究原型：
- 可验证日志存储。
- 可验证范围查询。
- learned index 在认证存储中的应用。
- Merkle proof 生成与验证开销分析。
- append-heavy 数据集上的存储、查询、空间放大实验。
如果目标是生产系统，还需要补齐崩溃恢复、并发事务语义、删除/更新语义、compaction、资源回收和长期运行稳定性。