Skip to content

memindex 定宽排序矩阵:fs + redis 后端实现(参考实现,主 issue kvspace#12) #19

Description

@miaobyte

主 issue(契约与总纲):array2d/kvspace#12

durable(fs + redis)实现 memindex 定宽排序矩阵。durable 为三后端参考实现,先在此验证格式与语义,再供 kvspace-c 对齐。

格式(见 kvspace#12)

memindex(kind=index):kindexpr=[N,M]index + body N×M(每行 UTF-8 + NUL 补齐到 M),全表 cmp_coord 排序。

改动点

  • xvalue_index.rs:encode/decode 由 offset 索引数组改为 [N,M] 矩阵——几何写入 head dims(不再进 body 头),body 纯 N×M;提供 matrix_count(=head N)/matrix_at(body,M,idx)(O(1) 单行)原语。
  • backend.rs(redis 存储侧):add_child / remove_child / set() 批量合并块按 cmp_coord 有序重建矩阵并重算 M;list_len 走 head N、list_at 走单行;get/get_dir 从矩阵 decode 成员名单;redis 用 GETRANGE 优化 listlen(读 head)/ listat(读单行),避免整块 GET。
  • fs/kvspace.rs:fs 于 get(p·) / dir_value 时按 readdir + cmp_coord 排序重建同格式矩阵 blob(fs 本就外部索引、不常驻存 blob);__order__ 插入序文件对 index/object 可移除(改按名排序)。
  • extindex 并入同一矩阵:xvalue_index.rsencode_ext_index_raw/decode_ext_index_raw 改为 [N,M]extindex head + body 头部变长 ext_path + 尾部 N×M 矩阵(childs,cmp_coord 有序);off=body_len−N*Mext_path=body[..off]、childs 矩阵=body[off..];listat/listlen/二分与普通 index 共用同一原语;list(expand_ext=true) 本地矩阵与 base(ext_path 指向的 /lib/ index)双侧有序归并、本地遮蔽去重。栈帧 churn 增量重建 O(N) 可接受(帧局部小而有界),ext_path 头部固定不被矩阵重建触碰。

验证

  • durable cargo test
  • kvlang tutorial fs + redis 全回归逐字节一致;
  • listat/listlen 与 shm 侧(kvspace-c)blob 逐字节对齐。

supersedes #18(offset 索引数组);取代 #14 的 redis ZSET 方向。

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