Skip to content

memindex 统一定宽排序矩阵:[N,M]index 头 + N×M 行,O(1) listat/listlen、O(log N) 成员查找 #12

Description

@miaobyte

背景

memindex(,kind=index)承载目录成员名单。durable#18 已把它改成 offset 索引数组 [4B count][(count+1)×4B offset][names blob],listat/listlen 达到 O(1),但仍有两处不足:

  • 非 map 目录名单按插入序存、无序 → 成员存在性只能 O(N) 线扫;
  • redis 后端每次增删整块 GET+SET 重写。

durable#14 曾提议 redis 改原生 ZSET,但 ZSET 是后端专属结构,破坏「三后端同一 blob」契约,且 cmp_coord(整数坐标元组 row-major 序)无法干净编码进单一 f64 score。本 issue 用一个三后端通用、更简单的方案统一收口。

方案:定宽排序矩阵,几何塞进 kindexpr

memindex(kind=index)统一改为:

  • headkindexpr = [N,M]index,复用 XValueHead 的 [dims] 段承载几何——N=成员数,M=行宽(当前全体成员 UTF-8 字节最大长度)。
  • bodyN × M 字节。每行 = 成员名 UTF-8 + NUL 补齐到 M(UTF-8 永不含 0x00,NUL 补齐/终止安全)。
  • 排序:全表按 cmp_coord 排序。cmp_coord 三档天然覆盖三种容器——数组 [0][1]… / map 坐标段 → row-major 数值序(顺带修掉「按字节把 [10] 排到 [2] 前」的错误);object 字符串键 → 落字符串兜底档 = 字典序。无需按容器 kind 分派比较器

适用范围:index / object / stringkeymap 三种容器的 memindex(三者 memindex 均在 、kind=index;容器逻辑 shape 存在 p 值的头里,与 memindex 的 [N,M] 互不冲突)。

extindex = 矩阵 + 尾挂 ext_path(同一套,不割裂)

extindex(写时复制叠加层,运行时用作栈帧根)同样并入本矩阵:其本地 childs 是普通成员名,未来常是带自身 memindex 的容器、需要 listat / 有序能力,不降级为无序 hash。布局 = 矩阵 +1(+1 为 ext_path):

extindex body = [ ext_path 变长字节 ] + [ N×M 矩阵(childs,cmp_coord 有序) ]
head          = [N,M]extindex        # N=childs 数,M=childs 最大 UTF-8 宽
矩阵起点 off   = body_len − N*M        # body_len 在 head 唯一确定,无需额外长度字段
  • ext_path 置 body 头部(offset 0):帧生命周期内 ext_path 一次写定、childs 才 churn,头部固定 → 矩阵起点稳定、增删只重建尾部矩阵、ext_path 字节不被矩阵重建触碰(shm 可原地);亦延续「ext_path 为 0 号元素」的既有心智模型。ext_path 通常远长于 M(如 /lib/main·add/),故作变长段、不占 M 宽的行。
  • decode:ext_path = body[..off];childs = 尾部 N×M 矩阵行 body[off..](有序,listat/listlen/二分与普通 index 完全一致),off = body_len − N*M
  • list(expand_ext=true):本地矩阵 + base(ext_path 指向的 /lib/<func>/ 常规 index 矩阵)双侧有序归并、本地遮蔽 base、去重。
  • 栈帧局部 churn 增量 O(N) 重建可接受——帧局部数量小而有界(参数 nr + 返回 nw + 少量 ._litN),换来结构统一 + 全树有序能力。

复杂度

操作 复杂度 说明
listlen O(1) 读 head dims[0]=N不碰 body
listat(idx) O(1) body[idx*M .. idx*M+M] 去 NUL
成员存在 / 定位 O(log N) cmp_coord 二分
顺序遍历 O(N) 顺读
insert / del O(M·N) 整块重建

设计取舍(已定):

  • 丢弃 object 插入序,object 成员按名排序。
  • stringmap 键长由生成侧(agent prompt)约束在合理范围,接受定宽 padding。M 是本目录最大长度,坐标 / 定长数组目录 padding≈0;只有「一个超长键 + 一堆短键」才浪费,这类目录通常小。

redis 线传收益

  • listlen:GETRANGE 只取 head 前几字节。
  • listat(idx):GETRANGE 单行 M 字节,O(1) 线传,不拉整块。
  • 二分:每探一次 GETRANGE 一行,O(M·log N) 线传即可判存在性。

为什么不上树(取舍确认)

要同时做到「增量插入 O(log N) + 可位置无关序列化进 blob」,rank-augmented B-tree/skiplist、ART、succinct rank/select 等均需 blob 内分页 / 空闲空间管理或整块静态重建,复杂度高、逼近被明确排除的磁盘 B+ 树。目录「查多改少」前提下,本方案在 get / listat / 简单性 / 三后端一致性上全胜,代价仅 insert 的 O(n) 重建——取舍划算。

契约与分解

本 issue 为跨后端契约与总纲:shm / fs / durable(redis) 三后端必须实现同一 blob 布局与语义,listat / listlen / 顺序逐字节一致。存储侧 redis/shm 直接存该 blob,fs 于 get 时按 readdir 重建同格式 blob。

关联:supersedes array2d/kvspace-durable#18(offset 索引数组);取代 array2d/kvspace-durable#14 的 redis ZSET 方向(改用本统一 blob)。

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions