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 槽 × 16BLogicalAddress)、表+溢出池同代原子对InternalHashTable、 条带写锁(64 条——Insert/Delete 按 hash 低位分条带)+ 溢出链条带锁(16 条)。 槽稳定读协议:16BLogicalAddress普通读可能撕裂——双读比对一致才接受,不一致走 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路径——降级全量重建不是第二条路。