后端【免费下载链接】automergeA JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.项目地址https://gitcode.com/gh_mirrors/au/automerge点击查看免费下载Hexane 是 Automerge 底层的列式压缩存储引擎它以 Automerge 二进制文档格式存储有类型值的序列并支持在压缩字节上直接原地编辑插入、删除、拼接无需解压整列。本文以 Hexane 的 CHANGELOG.md 为骨架逐条拆解 1.0.0-alpha.2、0.2.1、0.2.0 三个版本里程碑中的破坏性变更、正确性修复与性能优化并结合 README.md、V1_MIGRATION.md 与核心源码说明这些变更背后的数据结构原理与迁移路径。读完本文你将掌握 Hexane v1 API 的全貌、2^63 值域契约的由来、B-tree 删除下溢处理的实现策略以及如何从 0.2 时代的光标 API 平滑迁移到 v1 列 API。Hexane 是什么可原地编辑的列式压缩库Hexane 的核心卖点体现在其 README 的一句话定位上Columnar compression you can edit in place可原地编辑的列式压缩。它把有类型值的序列存储在 Automerge 二进制规范定义的压缩列格式中并且与众不同地允许在压缩字节上直接执行变更操作插入、删除、拼接直接在压缩字节上进行复杂度为O(log n 受影响字节数)无需解压整列一百万个相同的值在磁盘上只占 3 字节仍然可以在任意位置以约一百纳秒完成插入它是 automerge 的存储引擎也适用于任何需要可编辑、压缩、有类型序列的场景。四种列类型速览类型能力适用场景ColumnT随机访问、拼接、迭代只需要一个可编辑的压缩序列PrefixColumnTO(log n)前缀和查询值是长度或计数需要偏移量定位DeltaColumnT增量编码、按值查找值大体上连续ID、计数器RawColumn未压缩的字节竞技场以字节区间寻址的变长 blob支持的取值类型包括u32、u64、i64、usize、NonZeroU32、String、Vecu8、bool以及每种类型的OptionT作为一等公民的空值存储。读取尽可能零拷贝ColumnString直接吐出str。数据管线从值到 B-treeREADME 用一个四级流水线概括了内部结构src/column.rs 的Slab与 B-tree 索引与之对应values ──RLE──▶ runs 7,7,7,8 → [run 3×7][run 1×8] runs ──────▶ segments one encoded run one segment segments ──────▶ slabs ≤ max_segments per slab (default 64) slabs ──────▶ B-tree per-slab aggregates: count, sum, min/max每一次变更都精确落在一个 slab 中大删除会波及相邻 slab通过 B-tree 以O(log S)找到目标 slab用基于 memcpy 的字节拼接只重写受影响的 run然后沿路径向上更新一个聚合值。slab 超出段预算时分裂与兄弟节点合并时保持平衡从而在任意编辑模式下维持树与 slab 的双重平衡。RLE 的线格式src/rle/mod.rs 顶部注释是理解压缩的关键Repeat run : signed_leb128( count 0 ) packed_value Literal run: signed_leb128( -n ) v0 v1 … v(n-1) Null run : signed_leb128( 0 ) unsigned_leb128( count )各操作的成本README 官方表格操作成本get(i)、iter_range(a..b)定位O(log S slab 内 run 数)insert/remove/spliceO(log S slab 内字节数)前缀和 / 按值查找O(log S slab 内 run 数)saveO(总字节数)合并边界 runloadO(总字节数)全量校验1.0.0-alpha.22026-07-07v1 API 全面接管CHANGELOG 的第一个里程碑是 1.0.0-alpha.2它同时包含最多的破坏性变更与最多的新增内容标志着 Hexane 从 0.2 时代的光标cursorAPI 正式切换到 v1 列 API。值得注意当前 Cargo.toml 中的版本已是1.0.0-alpha.5alpha.2 是这条演进线上的重要分水岭。破坏性变更一移除 0.2-era 光标 API0.2 时代的ColumnDataC、UIntCursor、DeltaCursor、BooleanCursor、Slab/SpanTree、Packable等类型被整体移除。这套 API 的典型问题在 V1_MIGRATION.md 中有明确解释v0 的ColumnDataC使用线性迭代器做前缀和查询advance_acc_by、shift_acc、get_acc_delta每次调用都是O(n)而 v1 的PrefixColumnT改用基于 slab 的 Fenwick 树BIT把前缀和查询降到O(log n)。破坏性变更二v1 API 提升到 crate roothexane::v1::Column成为hexane::Columnv1模块消失。从 src/lib.rs 的导出可以看到 v1 形态的最终面貌Column、PrefixColumn、DeltaColumn、RawColumn、Encoder/Decoder、DeltaEncoder/DeltaDecoder、LoadOpts、Run等全部直接挂载在 crate 根下。破坏性变更三PrefixedValue 与 PrefixSeek 新形态PrefixColumn/PrefixIter现在产出PrefixedValue.value、.prefix()、.total()替代原来的(prefix, value)元组PrefixSeek现在由{ pos, delta, pv }三个字段组成。从 src/prefix.rs 的源码看PrefixedValue把两种累加器视图固化成了不可混淆的命名prefix()排他本项之前的前缀和total()包含贯穿本项的前缀和。对单位宽度[1, 1, 1]第 1 项的prefix() 1、total() 2一个字节偏移列可以自然读作pv.prefix()..pv.total()——即该项的字节区间。PrefixSeek::delta则是自查找起点到该项之间、不含该项本身的前缀消耗量即[from, to)区间上的和。PrefixColumn的查询 API 也因此全面成型见 src/prefix.rslet pv lens.get(2).unwrap(); // a PrefixedValue assert_eq!(pv.value, 7); assert_eq!(pv.prefix(), 8); // bytes before record 2 assert_eq!(pv.total(), 15); // bytes through record 2 assert_eq!(lens.get_prefix(3), 15); // exclusive sum of 0..3 assert_eq!(lens.sum_range(1..3), 10); // 3 7 assert_eq!(lens.get_index_for_total(10), 2); // which record owns offset 10?其中get_index_for_totalsrc/prefix.rs 中get_index_for_prefix的saturating_sub(1)实现了哪个记录拥有偏移量 10这种逆向定位它依赖 B-tree 的find_slab_at_prefix加 slab 内的find_prefix_in_slab逐 run 累积整体O(log S slab 内 run 数)。这类逆向查询仅对单调递增的无符号前缀类型u32/u64/usize/u128开放被UnsignedPrefix标记 trait 在编译期把关——有符号前缀可能递减会导致逆向查找语义错误。破坏性变更四被移除与更名的方法PrefixColumn::{seek, get_delta, get_value, value_iter}被移除改用delta、values().get()、values().iter()prefix_delta更名为sum_range。也就是说v1 刻意收敛了既要前缀和、又要纯值的两套入口需要前缀上下文时走delta/ 迭代器方法只需要纯值时走values()子视图避免 API 冗余。破坏性变更五DeltaColumn::save_to_unless 与 with_max_segmentsDeltaColumn::save_to_unless改为接受T并比较实现后的值realized values——这与 v1 的统一稀疏文件技巧一致当每个值都等于哨兵值时什么都不写全默认列在保存文档中占零字节Column::with_max_segments以及load现在拒绝低于 2 的段预算。这是对空 slab 与单 slab 边界情形的一种防御性收紧确保 slab 分裂/合并逻辑始终在合法参数域内运行。新增内容remove_n、try_to_i64 与 golden 测试remove_n(index, n)所有列类型统一新增的批量删除入口。README 的快速上手展示了它与splice的关系——col.remove_n(2, 2)就是splice(index, n, [])的免类型体操版本越界时 panicDeltaValue::try_to_i64查询路径上的非 panic 转换。越域的find_by_value目标现在返回空迭代器而不是 panic——对应 README 的失败模式策略表查询一个列永远不可能包含的值 → 空结果未找到 才是诚实的答案Golden wire-format tests冻结与 v0 兼容的字节格式详见下文线格式冻结一节B-tree 删除下溢处理详见下文专门小节。正确性修复B-tree 删除下溢与结构性不变量检查CHANGELOG 的 Fixed 条目第一条是本次发布最重要的正确性修复修复了删除恰好覆盖内部节点 span 时发生的静默 B-tree 损坏修复了整叶删除触发的 O(N) 全量重建——在顺序删除场景下这会退化为二次复杂度新增的下溢处理覆盖三种情形空节点移除empty-node removal、根节点坍缩root collapse、叶兄弟合并leaf sibling mergingfuzzers 中加入了结构性不变量检查器structural invariant checker在每次模糊测试循环内重新验证所有缓存的 B-tree 聚合值。这一点与 README 的保障层描述互相印证property tests 与 fuzzers 为每种列类型提供参考模型结构性不变量检查器在 fuzz 循环内重验每个缓存的 B-tree 聚合值加上 validate-on-load 为 crate 中唯一的unsafe块背书。删除路径是 B-tree 最容易出问题的分支合并、借位、根坍缩交织在一起把不变量检查直接编入 fuzz 循环是比单元测试更强的保障手段——不变量一旦被破坏fuzz 会失败而不是静默通过。BoolEncoder 尾部元数据修复run 超过 127 的场景第二个修复针对BoolEncoder::into_slab在 run 长度超过 127 时的尾部元数据错误。布尔列是唯一不走 RLE 的编码src/lib.rs 中bool使用BoolEncoding其余类型均使用RleEncoding其位打包规则独立于普通 run 编码长 run 场景下尾部tail元数据一旦失真会破坏 slab 的最后一个段信息进而影响迭代续接与合并。这个修复说明即使是看似简单的布尔位打包在 slab 边界与 tail 记账上也有容易被长 run 触发的一致性陷阱。Delta 列的加载期校验与 2^63 值域契约第三个修复针对 Delta 列包含两方面加载期校验实现后的值u64/usize/i32的 delta 列现在在load时对实现后的值做校验包括对敌意输入hostile input引发的running-sum 溢出的检查文档化的 2^63 值域契约实现后的值必须落在 2^63 宽的区间内无符号类型要求 2^63。为什么是 2^63src/delta/mod.rs 的DeltaValuetrait 文档给出了精确的理由线上的 delta 是i64而删除一个元素会让它的两个邻居变成相邻所以列中任意一对值都可能在某次删除后需要把它们的差编码成单个 delta。如果值域跨度达到 2^63 或更大一次删除就可能产生装不进线格式的 delta。2^63 恰好是差值仍可表示的边界。由此形成三条一致的行为规则源码中to_i64与try_to_i64的分工场景行为写路径to_i64越域panic——这是写方自己数据的先决条件违规加载DeltaColumn::load遇越域/恶意数据返回Err(PackError)——不可信字节永远不该 panic查询try_to_i64/find_by_value越域目标空结果——未找到是诚实答案DeltaValuetrait 的MIN_I64/MAX_I64常量即为加载校验提供边界依据load会对照它们验证每个 slab 的实现值 min/max 聚合。注意 delta 列内部的实际存储类型是i64可空列则是Optioni64DeltaInner的to_opt/from_opt抽象让非空列的Option宽化开销在编译期被消除src/delta/mod.rs。性能优化专项memcpy 拼接、O(log S) slab_start 与编码器直通CHANGELOG 最后一条 Fixed 概括了本次发布的性能工作四项改动环环相扣memcpy-based slab spliceslab 内的字节拼接改为 memcpy 实现。src/column.rs 的splice_bytes用三个安全的 stdlib 调用Vec::resizecopy_withincopy_from_slice替代Vec::splice的逐元素ptr::write循环插入字节一次 memcpy 到位后缀移位一次memmove完成O(log S) 的slab_start定位 slab 起始位置从线性扫描改为经 B-tree/Fenwick 索引的二分提升find_slab_bit使用标准 BIT 二分提升O(log S)——这让Iter::nth的跨 slab 跳转src/column.rs和seek_to_value的 slab 二分搜索都能直接拿到 slab 起点无根聚合合并的索引下降index descents without root-aggregate merges在 B-tree 下降过程中避免不必要的根聚合合并减少每次定位的固定开销编码器到列的 slab 直通direct encoder-to-column slab handoff编码器产出的 slab 字节直接交给列结构省去中间往返。CHANGELOG 给出的量化结果是remap快 15–20%seek 类操作约快 2 倍。remap是 v1 为迁移新增的辅助能力V1_MIGRATION.md 中hexane::Column::remap(|T| T)——逐 run 重放每个值经f变换后重建列它的提速正来自第 4 项编码器直通RleEncoder::save_to_and_remap用RleDecoder走自己的缓冲重新发射到新编码器无需经Column往返。线格式冻结Golden wire-format tests 与 v0 兼容性CHANGELOG 的 Added 条目中包含一组Golden wire-format tests其意义在 README 的格式稳定性一节被明确点出字节格式就是automerge 文档格式因此它是冻结的。测试套件用 golden fixtures 钉住它——每种 codec 的字节级精确期望编码均对照原始参考实现采集。若某次改动触发这些测试那不是测试失败而是与每个现存文档的兼容性破坏。也就是说Hexane 的压缩列格式与 Automerge 文档格式是同一套字节格式任何线格式漂移都意味着既有文档不可读。golden fixtures 把这种兼容性承诺转化为可执行的回归防线与 README 中runcargo test -p hexane即可跑约 525 个测试含 fuzzers 与 golden fixtures的开发体验互相印证。特性开关与 0.2.x 演进回顾CHANGELOG 的 0.2.x 条目记录了两条重要的 API 演进理解它们有助于把握 v1 的设计动机。0.2.12026-03-25slow_path_assertions新增slow_path_assertions特性允许默认关闭慢路径断言。该特性至今保留在 Cargo.toml 中与wasm、deep_fuzz默认跳过、保持cargo test快速的深度 fuzz 测试、bijou64启用bijoux依赖提供可选的 Bijou64 线格式并列。完整的当前特性集特性作用wasm通过web-sys提供控制台日志slow_path_assertions慢路径断言默认关闭deep_fuzz深度/昂贵的 fuzz 测试默认跳过以保持测试速度bijou64可选的 Bijou64 varint 线格式依赖bijoux值得一提的还有 src/lib.rs 中的leb128与bijou两个别名模块use hexane::leb128::Column与use hexane::Column读取相同LEB128 是全 crate 默认但后者在导入处显式声明了线格式混用 codec 的代码可以同时导入两个模块并在使用处限定。0.2.02026-03-06encode_unless_empty 与光标 API 的收尾Added大量文档ColumnCursor::encode_unless_empty取代ColumnCursor::encode的force参数ColGroupIter::shift_acc再导出HasMinMax与RunIterFixedColumnCursor::splice正确处理 slab 边界附近的删除BreakingColumnCursor::encode不再接受布尔force参数泛型约束变为M: MaybePackablea, Self::Item, I: IntoIteratorItem M移除Encoder::finish改用into_column_data或save_toColGroupIter::nth改为按条目数推进按累加器数推进改用shift_accencode_unless_empty成为ColumnCursor的新必需方法。这组变更显示 v1 的稀疏文件哲学在 0.2 时代已经萌芽encode_unless_empty只在完全没有追加值时省略编码而 v1 的save_to_unless(default)把省略条件放宽为所有值都等于默认值——两者在可空列上重合空列即全 null但在非空列上语义发散。V1_MIGRATION.md 特别提醒非空列要匹配 v0 的线格式必须使用 v1 的encode_to不带_unless。从 0.2 迁移到 v1 的实战指引V1_MIGRATION.md 是一份仍在维护的迁移参考其核心决策树与 API 对照可直接落地类型选型需要前缀和使用需要——计数、按累加值定位、区间求和hexane::PrefixColumnT不需要——只要随机访问、迭代、拼接hexane::ColumnTPrefixColumn要求T: PrefixValue已为bool、u32、u64、i64、Optionu32、Optionu64、Optioni64、NonZeroU32等实现。注意实际实现的Prefix累加器类型src/prefix.rsu64 → u128、i64 → i128、u32 → u64、NonZeroU32 → u64、bool → usize——累加器通常比值类型宽一号以避免求和溢出。常用 API 对照// v0 → v1Column col.get(pos) → col.get(pos) // OptionT无 Cow col.iter_range(range) → col.iter_range(range) // 直接产 T col.splice::u64, _(pos, del, []) → col.remove_n(pos, del) // v0 → v1PrefixColumn col.get(pos) → col.values().get(pos) // 纯值走 values() 前缀和查询v0 需线性迭代→ col.get_prefix(pos) // O(log n) col.get_acc_delta(start, end) → col.sum_range(start..end) // O(log n) iter.shift_acc(n) → iter.advance_prefix(n) // 返回 PrefixSeek{pos, delta, pv} col.get_acc_delta(start, pos) → col.delta(start, pos) // 或 iter.delta_nth(pos - start)advance_prefix的边界契约是 Automerge 文本索引所依赖的单位宽度[1, 1, 1]下advance_prefix(0)落在第 0 项advance_prefix(1)落在第 1 项——累计和恰好等于n的项会被跳过而非返回。交叉验证脚手架模式迁移期间可以保留旧列做临时对照每个使用点同时算新旧两遍并assert_eq!所有 splice/insert/remove 同步更新旧列测试全绿后移除_old与全部断言。V1_MIGRATION 记录了 automerge 仓库内的迁移进度op set、change graph、bundle builder 中的各列类型与对应编码器其中key_str、mark_name、expand、insert、text、top、visible、timestamps、messages、extra_bytes_meta、value作为RawColumn等均已迁移完成而succ_count家族子列耦合、value_meta需要PrefixValue聚合钩子、MarkIndexColumn自成一体的自定义列等仍待处理——这些剩余工作恰好是 v1 能力边界的清单。开发与验证测试、基准与运行环境cargo test -p hexane # 约 525 个测试含 fuzzers 与 golden fixtures cargo bench -p hexane # divan 基准column_ops、load、remap 等运行环境以 Cargo.toml 为准edition 2021rust-version 1.90.0MSRV 1.90license MIT特性开关见上文表格[profile.release]开启debug truerelease 下保留调试信息便于栈回溯定位 fuzz 崩溃。benchmark 目录rust/hexane/benches/中的column_ops、load、remap等场景配合rust/hexane/proptest-regressions/tests.txt里的回归记录构成了性能与正确性的双保险。README 中关于性能的数字如百万全同值 3 字节、约百纳秒插入、稀疏列 sub-150ns 每次编辑均来自 divan 基准可用cargo bench在本机复现。结语Hexane 的 CHANGELOG 不仅是版本流水账更是一部列式压缩存储的设计笔记从 0.2 时代线性迭代器做前缀和的ColumnDataC到 v1 用 Fenwick 树把前缀和压到O(log S)从静默损坏的 B-tree 删除路径到带结构性不变量检查器的 fuzz 防线从force参数到语义清晰的save_to_unless从 v0 到 2^63 值域契约——每一次变更都以字节格式冻结为底线。对于想在 Automerge 生态内做存储层改造、或自行实现可编辑压缩列的开发者这份 CHANGELOG 连同 V1_MIGRATION.md 与 src/prefix.rs 等源码是最直接的演进地图与实现参照。赞分享后端【免费下载链接】automergeA JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.项目地址https://gitcode.com/gh_mirrors/au/automerge点击查看免费下载相关推荐PouchDB 3.0.3 补丁版本深度解析复制性能与正确性的取舍、慢复制调优与自动压缩正式化PouchDB 3.0.3 补丁版本深度解析复制性能与正确性的取舍、慢复制调优与自动压缩正式化 导读PouchDB 3.0.3 是紧随 3.0.0 性能大版数据库数据同步深度剖析PostgreSQL存储引擎从底层原理到性能优化深度剖析PostgreSQL存储引擎从底层原理到性能优化 你是否曾好奇PostgreSQL如何高效管理海量数据为何它能在高并发场景下保持数据一致性本文将带数据库关系型数据库Citus Columnar存储引擎列式存储与压缩技术深度剖析Citus Columnar存储引擎列式存储与压缩技术深度剖析 本文深入分析了Citus Columnar存储引擎的核心技术特点重点对比了列式存储与传统行式分布式数据库数据库关系型数据库上一篇Laravel Octane Dockerfile 常见问题解决方案下一篇Python测试与部署最佳实践Python Engineer Roadmap中的DevOps资源详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考