Table of Contents

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 原子读拷贝(槽 = LogicalAddress 16B 原子单元,零撕裂)

  • 跳 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(引擎恢复)。