Table of Contents

Index(Hash/BTree/SkipList)——Settings / API 详表 / 注入工厂

分册导航:index.md | [index-api.md](API 与工厂) | index-persistence.md | Index(Hash/BTree/SkipList)——Settings / API 详表 / 注入工厂 | Index(Hash/BTree/SkipList)——持久化机制与恢复协议

2. Settings 全参数

2.1 三 Settings 对比

参数 所属 Hash 默认 BTree 默认 SkipList 默认 说明
PersistenceKind 基类 Builtin Builtin Builtin None=纯内存+重放;Builtin=自建主存储
PersistencePolicy.Interval 基类 30s 30s 30s 后台 dump 时间间隔(自上次 dump 起)
PersistencePolicy.EntryDeltaThreshold 基类 10_000 10_000 10_000 条目增量水位阈值(任一命中触发 dump)
PersistenceKeepVersions 基类 2 2 2 版本保留数(N 版轮替,对齐 Mirror/Metadata 家族)
HashTableCapacity Hash 专属 1<<14 — — 哈希表初始桶数(2 的幂,超 0.7 自动翻倍增长)
OverflowPoolCapacity Hash 专属 1<<12 — — 初始溢出池桶数(增长换代新池=新表/2,下限 1024)
NodeSize BTree 专属 — 256 — 节点大小(实际取 max(结构体大小, 256, 本值))
MinFillPercent BTree 专属 — 50 — 最小填充率(节点合并触发阈值——百分比)
MaxLevel SkipList 专属 — — 16 塔最大层数(head 哨兵按满层建;几何层分配 p=1/2 封顶)
HighLevelCacheThreshold SkipList 专属 — — 8 高层缓存阈值(≥此值全量内存缓存——塔高层稀疏,代价低)
MaxRetryCount SkipList 专属 — — 3 CAS 插入最大重试次数(塔链竞争失败重试上限)
SafeReclaimDelayMs SkipList 专属 — — 1000 物理回收延迟(ms——等 epoch 退出后回收被删节点)
NodeCacheInitialCapacity Sorted 基类 — 1024 1024 节点缓存初始槽位(非上限,按数据量增长至索引量级)

2.2 构造形态

三 Settings 均接受 StorageEngineOptions 直构(对齐 BlittableRingSettings/EntryLogSettings 双 ctor 形态):

var ringSettings    = new BlittableRingSettings(new StorageEngineOptions("kv-ring", 64L << 20));
var hashSettings    = new HashIndexSettings(new StorageEngineOptions("kv-hash", 64L << 20));
var btreeSettings   = new BTreeIndexSettings(new StorageEngineOptions("kv-btree", 64L << 20));
var skipListSettings = new SkipListIndexSettings(new StorageEngineOptions("kv-skiplist", 64L << 20));

基类(ProbingIndexSettings/SortedIndexSettings)收持久化机制配置(Kind/Policy/KeepVersions), 子类只填格式布局参数(对齐 LogBase/RingBase/MirrorBase:机制容器在基类,子类只实现 codec)。 segment 增长上限固定 1G(AlignmentConst.Alignment1G)。


4. API 详表

4.1 IIndex<TKey> 五成员最小协议

成员 签名 返回 / 语义
Find LogicalAddress Find(TKey key) 命中 = value 逻辑地址;Empty = 不存在
Insert LogicalAddress Insert(TKey key, LogicalAddress valueAddress, LogicalAddress beginAddress) 同 key 覆写 value 不增计数;返回插入后地址
Delete bool Delete(TKey key) true = 真删到;false = 不存在
EntryCount long EntryCount { get; } 条目数(写者维护——O(1))
IndexSize long IndexSize { get; } 索引内存占用估算(字节)

beginAddress 参数:探测下限地址(重放路径约定)——槽内旧条目地址小于它视为陈旧,可覆写落位。 Sorted 族插入不消费此参数(保留接口对称)。

4.2 两族共有扩展 API

成员 签名 语义
BeginAddress LogicalAddress BeginAddress { get; } 探测/结构起始地址(引擎 MinAddress)
EnterScope IndexScope EnterScope() 读保护 scope(ref struct——创建即 Resume epoch,Dispose 即 Suspend)
IndexScope.Find LogicalAddress Find(TKey key) scope 内单查(走 FindNoEpoch——省逐次 epoch 进出 ~10ns/op)
FindBatch void FindBatch(ReadOnlySpan<TKey> keys, Span<LogicalAddress> results) 批量点查(同一轮 epoch 内完成——零逐查 Resume/Suspend 开销)
EnterEpoch / ExitEpoch void EnterEpoch() / void ExitEpoch() epoch 读保护协议(IEpochProtected——Session 读 scope 聚合入口转发)
CheckpointFrame bool CheckpointFrame() 显式帧落盘(公开检查点触发口——语义同内部 TryDump)
MainStorageAppliedLastRecovery bool { get; } 诊断位:上次恢复是否走了主存储载入路径(false = 全量重放 fail-safe)

4.3 HashIndex 专属 API

成员 签名 语义
GrowIndex void GrowIndex() 扩容(装载超 0.7 由 Insert 自动触发——函数式换代表,均摊 O(1)/插)
DiagDumpBucketRaw internal string DiagDumpBucketRaw(TKey key) 诊断:dump 某 key 所在桶全部原始槽位(排障用)
DiagScanKeyAllSlots internal string[] DiagScanKeyAllSlots(TKey key) 诊断:全表扫描收集某 key 的全部实体(幽灵实体定位——O(全表))

HashIndex 内核:128B HashBucket(8 槽 × 16B LogicalAddress)、表+溢出池同代原子对 InternalHashTable、 条带写锁(64 条——Insert/Delete 按 hash 低位分条带)+ 溢出链条带锁(16 条)。 槽稳定读协议:16B LogicalAddress 普通读可能撕裂——双读比对一致才接受,不一致走 CAS 环读兜底。

4.4 SortedIndex 专属 API

成员 签名 语义
CreateScanCursor IIndexScanCursor<TKey> CreateScanCursor(ReadDirection direction) 有序遍历游标(仅 Forward——叶链/层 0 链单向,Backward 显式抛 NotSupportedException)
TryGetMax bool TryGetMax(out TKey key, out LogicalAddress value) 键序最大条目(Latest 语义——时序/版本链"最新点查"),O(log n)
TryGetFloor bool TryGetFloor(TKey key, out TKey floorKey, out LogicalAddress value) 键序 ≤ key 的最大条目(floor/前驱语义——Prometheus @ 采样/前驱点查),O(log n)
TruncatePrefix long TruncatePrefix(TKey boundExclusive) 键序前缀批量删(删除全部 key < bound 的条目——retention trim 专用,批量 O(覆盖区))

BTreeIndex 内核:160B BTreeNode(9 槽定长 (TKey, LogicalAddress) + Next 叶链指针 + 叶/根标志位)。 SkipListIndex 内核:arena 驻留变长节点(32B 头 + 16B×实际层高),addr→指针缓存(零结构拷贝下降)。 操作闸(MonitorScope):全部公开操作(读/写/游标单步/后台 dump)经内部操作闸互斥—— 单操作粒度全互斥,结构自保证任意并发组合安全。粒度 = 单操作(游标 = 单步推进),长扫描经逐步持闸与写者交错。

4.5 IIndexScanCursor<TKey> 游标

成员 签名 语义
CurrentKey TKey CurrentKey { get; } 当前条目的 key(从 RecordStore 读回真 key,非占位符)
CurrentValue LogicalAddress CurrentValue { get; } 当前条目的 value 逻辑地址(指向 record)
SeekLowerBound bool SeekLowerBound(TKey key) 定位到首个 key ≥ key 的条目(lower_bound;可在迭代前或迭代中调用)
MoveNext bool MoveNext() 推进到下一条目(操作闸单步粒度——与写者交错;首次调用定位起点)
MoveNextAsync ValueTask<bool> MoveNextAsync(CancellationToken ct) 异步推进(同步委托 MoveNext——无真异步 IO)
Dispose / DisposeAsync void Dispose() / ValueTask DisposeAsync() 释放游标(幂等——游标不持有页资源,仅置标记)

范围查询 [from, to) = SeekLowerBound(from) + 逐条 MoveNext 推进至 key ≥ to 停(无需从头跳过被略键)。 BTree 游标:最左叶定位 + 叶链 Next 前向推进 + 跨空叶(删除不重平衡可留 Count=0 的叶)。 SkipList 游标:层 0 链前向推进 + lower_bound 塔链定位。


5. 自定义注入工厂

注入点 接口 必填 用途
KeyResolver IKeyResolver<TKey> Hash 必填 / Sorted 可选 判等闭环核心——Hash tag 命中后回读 Ring 拿 key 比对;两族恢复拉流重放
KeyComparer IKeyComparer<TKey> 可选(默认 KeyComparer<TKey> 全字段判等) 哈希/比较路由;Hash 点查 latest 版本语义可注入版本无关比较器
Codec IProbingIndexCodec / ISortedIndexCodec 族私有(子类内置单例) 主存储帧格式(magic/version/kind/字段布局/CRC 偏移)——禁跨族共用
PersistenceKind ProbingIndexPersistenceKind / SortedIndexPersistenceKind 默认 Builtin None=纯内存+重放;Builtin=自建主存储
PersistencePolicy ProbingIndexPersistencePolicy / SortedIndexPersistencePolicy 默认 30s / 10k 条目 后台 dump 触发策略(时间间隔 / 条目增量水位阈值,任一命中)
RecoveryHints ProbingIndexRecoveryHints / SortedIndexRecoveryHints 经 Initialize(hints) 注入 重放窗口 [Begin, End)——组合层锚点 W
Epoch LightEpoch 可选(null=索引自建并持有) 读保护(IEpochProtected——Session 读 scope 聚合入口)
ITransactionParticipant 显式实现(六件套) 内置 2PC:Prepare / ConfirmCommitted / OnCommitted / Abort

IKeyResolver 闭环:TryGetKey(addr, out key) 按 address 回读真 key(Hash 判等);GetFlushedWatermark() 返回已落盘水位 W(主存储 dump footer 锚点——组合层契约:Insert 先于落盘、失败回滚,已落盘必已入索引); ScanAsync(begin, end, ct) 异步迭代器流式回源(冷区真异步 IO 不阻塞,墓碑感知)。

ISortedIndexCodec / IProbingIndexCodec 契约律(对齐 ILogCodec):基类只管机制(帧走链/CRC 总验收/体长定界), 格式知识(magic/version/kind/字段布局)全在实现侧——接口只传机制需要的原始值,不暴露任何具体格式类型。

ITransactionParticipant 六件套(显式实现):Prepare(seq) / PrepareAsync(seq, ct) / ConfirmCommitted(seq) / OnCommitted(seq, callback) / Abort(seq) / AbortAsync(seq, ct)。 协调器 = Transactions/TransactionLog(写独立 commit record 文件驱动);上层编排归 Session(session.md)。

5.1 RecoveryHints 注入

// 组合层职责:恢复 Ring 后从 opaque 取锚点 W,连同 Ring 尾注入 index 恢复窗口
var opaque = ring.ReadOpaqueMeta();                              // opaque 容器(ReadOnlySpan——同步栈内消费)
//   W 由组合层自行编解码(如 8B LogicalAddress 编码在容器内);IsEmpty = 无锚点/损坏
var begin  = DecodeW(opaque, ring.BeginAddress);                 // 无锚点 → W = BeginAddress(宁可旧多重放)
var end    = ring.TailAddress;                                   // Ring 尾(半开区间不含)
var hints  = new ProbingIndexRecoveryHints(begin, end);          // [Begin, End) 重放窗口
hash.Initialize(hints);                                         // 注入恢复窗口
await hash.WaitForReadyAsync(ct);                                // 等恢复完成(载帧物化或重放)

// 每次 dump/重放后更新锚点:CheckpointFrame 落帧 → W 编码进 opaque(随 meta 写原子落盘)
hash.CheckpointFrame();                                          // 显式帧落盘(W = ring 已落盘水位)
ring.SetOpaqueMeta(EncodeW(watermark));                          // 更新 opaque 锚点 W(ReadOnlySpan<byte>)

HasReplayWindow = End > Begin 才重放(默认 default hints = Empty/Empty = 不重放,空结构首开)。 W = Begin 走同一条 ScanAsync 路径——降级全量重建不是第二条路。