Index(Hash/BTree/SkipList)——持久化机制与恢复协议
分册导航:index.md | [index-api.md](API 与工厂) | index-persistence.md | Index(Hash/BTree/SkipList)——Settings / API 详表 / 注入工厂 | Index(Hash/BTree/SkipList)——持久化机制与恢复协议
6. 持久化机制(两族对比)
两族均自建主存储(内置后台 dump worker + 帧恢复载入),区别在帧策略:
| 维度 | HashIndex | SortedIndex(BTree/SkipList) |
|---|---|---|
| 帧定位 | 帧走链——从 MinAddress 前向逐帧扫描选最新完整帧 | 固定锚点——首开预留 84B 锚点槽(MinAddress),dump 覆写 |
| 版本管理 | N 版轮替(PersistenceKeepVersions,ReclaimHead 回收最老帧) |
单帧覆写(帧长固定,无版本链需求) |
| 帧体内容 | 几何 32B + 桶区 size×128B + 溢出池 ofbCap×128B(fuzzy 逐槽原子读拷贝) | 几何 32B(root/head 指针 + 计数 + structSize)——节点本就写时持久化在引擎内 |
| 物化 | 整读体重建表+溢出池 → 重数实收(fuzzy 帧内混入条目以实收为准) | 设根 + 引擎读回根节点 → 计数(recountNeeded 时全树/全链实收) |
| dump 与写并发 | fuzzy 一致性(128bit 原子读拷贝,跳 Tentative 只收 Occupied;换代 stale-but-valid) | 操作闸全互斥(脏节点延迟写回——插入/分裂路径零引擎写,dump 时批量写回) |
| 后台触发 | BackgroundWorkerLoop(1s 轮询粒度,到点按策略判定) |
同左 |
| 帧格式 | 三段式 [头][体][尾]——头先行校验、体自定界、尾总验收 |
同左(codec 族私有) |
| 关闭 | PersistenceKind=None = 纯内存 + Ring 全量重放 |
同左 |
不配也安全——
PersistenceKind=None走全量重放 fail-safe(恢复核心三级回退兜底)。 帧格式(自校验三段式,对齐段表同款理由——写入的是外部存储就不完全相信):
- 头(先行校验,快速失败):magic/version/flags/kind + 体长——不符立即判无效,不读体。
- 体(自定界):结构内容由族自己的几何块推出边界。
- 尾(总验收):footerMagic + 水位 W + CRC64(覆盖头+体+尾前缀)——有效性最终裁决。
W =
IKeyResolver.GetFlushedWatermark()(已落盘水位——组合层契约:Insert 先于落盘、失败回滚, 已落盘必已入索引;在途 = 未落盘 = 崩溃即失)。调用CheckpointFrame前须先落盘真相源(如 Ring FlushUntil(Tail))。HashIndex fuzzy 一致性(FASTERKV 同构):逐槽 128bit 原子读拷贝(槽 =
LogicalAddress16B 原子单元,零撕裂)
- 跳 Tentative 只收 Occupied + 换代 stale-but-valid(dump 期间 GrowIndex 照常)。正确性靠组合一致性底座: dump 表覆盖 [?, W] 完整折叠;> W 混入条目靠重放 (W, End] 幂等收敛或恢复后 ring 裁决惰性失效。
SortedIndex 节点即数据教义**:节点写时持久化在自持引擎(节点变更即
WriteNodeContent记脏标记, dump 时批量写回引擎——插入/分裂路径零引擎写)。物化只需设根 + 引擎读回根节点,零逐节点流。BTreeIndex 脏节点延迟写回:
_dirtyNodes地址集(只存地址 16B/项——值快照版 240B×n 超 L3 污染点查,已销案); 写回从缓存取值——不变式:每次WriteNodeContent前节点必已入缓存(RefreshCache/根特例_cachedRoot), 读路径 miss = 从未变更 = 引擎内容最新,无需脏兜底。崩溃窗口(dump 前)由恢复重放 (W, End] 修复—— W = 上次 dump 水位,重放补齐全部变更,引擎旧链无害。SkipListIndex arena 驻留:变长非托管块(头 + 16B×实际层高;头尺寸 = 键 + 值指针区,随 TKey 定长布局—— 32B 头即 8B 键形态)——工作集从 288B/节点 压到均值 ~64B/节点 (100k 条 28.8MB→~6.5MB,L3 常驻);块只增不搬移 = 指针恒稳。addr→指针缓存(
LogicalAddressMap<nint>, 8B 值)——跳一跳 = 探测+指针直访,零结构拷贝。几何层分配 p=1/2 封顶MaxLevel,与插入时间/条目数解耦。
7. 恢复协议
7.1 三级回退(统一生命周期)
① hints(组合层最强知识)——重放窗口 [Begin, End)
② 主存储最新完整帧(载入物化 + 重放 (W, End])——Hash 帧走链 / Sorted 固定锚点
③ 建空结构 + Ring 全量重放兜底(W=Begin 走同一条 ScanAsync 路径)
每级失败自动降级到下一级——恢复不变量不变(索引 = 派生数据,重建数据面 = 真相源 record 流)。
7.2 锚点 W 协议
① Ring.Create → 恢复水位;锚点 W = ring.ReadOpaqueMeta()
(无锚点 / 损坏 / W 越过当前尾 → 回退 BeginAddress——宁可旧多重放)
② index.Initialize(hints) → hints.Begin = W, hints.End = ring.TailAddress
③ 主存储帧有效且 W∈[Begin,End] → 载帧物化 + 只重放 (W, End)
无帧 / 损坏 / W 越界 → 建空结构 + 全量重放 [Begin, End)
④ 每次 dump/重放后 ring.SetOpaqueMeta(W) 即可
7.3 重放核心
恢复核心拉 KeyResolver.ScanAsync(W, End) 流逐条处理:
- 普通记录 →
Insert(key, addr, LogicalAddress.Empty)(同 key 覆写——流序折叠 = 最新写胜出)。 - 墓碑记录 →
Delete(key)(已删 key 不复活;窗口内旧 put 先插后删收敛)。
Sorted 族锚点槽预留(
EnsureAnchorReserved):首开空引擎 = 第一个分配(MinAddress,节点分配自然在其后); 重开 = 旧锚点原位(MinAddress 恒为锚点——节点ReclaimTail不动 MinAddress)。Hash 族帧走链(
ScanFrames):从引擎 MinAddress 起,头(magic/version/kind)+ 帧长推导 + 尾 magic + CRC 总验收; 写中断的尾帧 CRC 不过即停——最新完整帧 = 最后一个通过验收的帧。账本同时重建(轮替用)。恢复全程经
LifecycleBase模板编排(RecoveryBase派生——只填恢复算法钩子, 底层生命周期骨架是压测背书的信任边界,结构层只填钩子)。详见meta.md(opaque 搭车)与storage-engine.md(引擎恢复)。