Hexane v1 迁移指南：从 v0 `ColumnData＜C＞` 迁移到 `PrefixColumn＜T＞` / `Column＜T＞`-迪斯科星球

后端

【免费下载链接】automerge

A 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

点击查看免费下载

注意（1.0.0-alpha.2）：本文档描述的 0.2 时代ColumnData<C>API（下文统称"v0"）已被移除，v1 API 现位于 crate 根部（不再有v1::前缀）。本指南作为面向仍基于 0.2 编写代码的移植参考继续保留。详见 CHANGELOG。

Automerge Hexane 列式存储迁移实战：从 v0`ColumnData<C>`到 v1`PrefixColumn<T>`/`Column<T>`

Hexane 是 Automerge 项目底层的列式压缩存储引擎，直接以 Automerge 二进制文档格式的列格式存储类型化序列，并支持原地编辑（插入、删除、splice 直接作用于压缩字节）。本文以 rust/hexane/V1_MIGRATION.md 为核心，系统讲解如何把基于 v0ColumnData<C>游标 API 的代码迁移到 v1 的PrefixColumn<T>与Column<T>：从类型声明、构建、splice、前缀和查询、迭代器 seek，到编码器与内存列存储两大迁移战线，全部给出可复制的对照代码、API 映射表与 automerge 仓库内的真实迁移案例。读完你可以独立完成一次从 v0 到 v1 的完整迁移，并理解背后的 Fenwick 树（BIT）索引原理与"交叉验证脚手架"迁移方法。

为什么迁移：从 O(n) 线性迭代到 O(log n) 树索引

v0 的ColumnData<C>对前缀和查询（advance_acc_by、shift_acc、get_acc_delta）使用线性迭代器，每次调用都是 O(n)。当列中数据量大时，这些"按累计值 seek"的操作会成为性能瓶颈。

v1 的两类列解决了这个问题：

PrefixColumn<T>：基于 slab 的 Fenwick 树（树状数组，BIT）实现前缀和索引，get_prefix、get_index_for_total、sum_range均为 O(log n)；
Column<T>：当你只需要值（不需要前缀和）时，提供 O(log n) 的随机访问，且没有 BIT 的额外开销。

在 rust/hexane/src/prefix.rs 中可以看到 BIT 节点的实现：PrefixSlabWeight同时携带len（条目数）和prefix（前缀和）两个分量，一棵 Fenwick 树同时支持 O(log S) 的位置查询与 O(log S) 的前缀和查询。README 中给出的整体复杂度表格印证了这一设计：

（复杂度表摘自 rust/hexane/README.md。）slab 拆分/合并机制保证树与 slab 在任意编辑模式下保持平衡——每次变更只落在一个 slab 内（大删除波及邻居），通过 B 树 O(log S) 定位 slab，仅重写受影响 run 的字节，回程路径上更新一个聚合值。

选择正确的 v1 类型

迁移的第一步是判断每个列到底需不需要前缀和语义：

判断依据很直接：当列的值是长度或数量时，累计值本身就是最关心的数字——它能把"第 2 条记录"翻译成"第 8..15 字节"。这正是 automerge 文本索引（text列存字符宽度、top列存行首标记）使用PrefixColumn的原因。而像visible这种只做布尔标志读取、从不求和的列，用Column<bool>即可，避免 BIT 的维护开销。

类型声明迁移

最典型的迁移样例是 automerge 的Indexes结构体（文本索引三件套）：

// Before text: ColumnData<UIntCursor>, // Option<u64> with prefix sums top: ColumnData<BooleanCursor>, // bool with prefix sums visible: ColumnData<BooleanCursor>, // bool, no prefix sums needed // After text: hexane::PrefixColumn<Option<u32>>, // prefix sums over Option<u32> top: hexane::PrefixColumn<bool>, // prefix sums over bool visible: hexane::Column<bool>, // values only

注意两个细节：

值类型从Option<u64>收窄为Option<u32>（字符宽度用 32 位足够，线格式更省）；
是否加Prefix前缀完全取决于"是否需要前缀和"，与值的类型无关——bool也可以有前缀和（此时前缀类型是u32）。

PrefixColumn要求T: PrefixValue。已实现的类型包括：bool、u32、u64、i64、Option<u32>、Option<u64>、Option<i64>、NonZeroU32等。PrefixValue的前缀累加类型通常比值类型宽一级以避免溢出，见 rust/hexane/src/prefix.rs：

值类型	`Prefix`（累加类型）
`u64`	`u128`
`i64`	`i128`
`bool`	`u32`
`Option<u64>`	`u128`
`Option<i64>`	`i128`

PrefixValue还要求实现accumulate与accumulate_run两个方法；slab_sum/partial_sum提供默认实现（直接解码 run 计算，O(segments) 而非 O(items)）。

构建列：FromIterator

PrefixColumn和Column都实现了FromIterator，因此.collect()可以直接工作：

// Before let text: ColumnData<UIntCursor> = widths.iter() .map(|w| if visible { Some(*w) } else { None }) .collect(); // After let text: PrefixColumn<Option<u32>> = widths.iter() .map(|w| if visible { Some(*w as u32) } else { None }) .collect();

如果数据本来就是有序到达的（构建 change、解析文件等流式场景），还可以跳过 Column 直接走流式编码器Encoder/DeltaEncoder，见 rust/hexane/README.md。

Splice 操作迁移

v1 对"删除"提供了更明确的语义方法remove_n（所有列类型都有，见 CHANGELOG）：

// Before (delete) col.splice::<u64, _>(pos, del, []); // After (delete) col.remove_n(pos, del); // 参数与 splice(pos, del, []) 相同 // Before (insert/replace) col.splice(pos, 1, [Some(value)]); // After —— 相同调用，只需匹配新的元素类型 col.splice(pos, 1, [Some(value as u32)]);

v1 的splice在内部把每个值视为 1 个条目（map(|v| (v, 1))），批量插入均匀数据时建议用splice_runs走 run 感知的快速路径（rust/hexane/src/prefix.rs）。

API 迁移参考：逐方法对照

获取单个值

// v0 let val = col.get(pos); // → Option<Option<Cow<'_, T>>> // v1 PrefixColumn let val = col.values().get(pos); // → Option<T> (owned，无 Cow) // v1 Column let val = col.get(pos); // → Option<T>

v1 消除了Cow包装：Copy类型直接返回 owned 值，String/Vec<u8>这类引用类型返回&str/&[u8]（零拷贝读取，见 rust/hexane/README.md）。PrefixColumn自身的get返回带前缀上下文的PrefixedValue；不需要前缀时通过values()拿到底层Column的普通值读取。

迭代区间内的值

// v0 let iter = col.iter_range(range); // yields Option<Cow<'_, T>> // v1 PrefixColumn let iter = col.values().iter_range(range); // yields T // v1 Column let iter = col.iter_range(range); // yields T

位置前缀和（0..pos 之和）

// v0 —— 无直接调用，必须迭代 // v1 let sum = col.get_prefix(pos); // O(log n), returns T::Prefix

get_prefix是排他前缀和（0..index的和）；配套的get_total(index)是包含前缀和（等于get_prefix(index + 1)），实现见 rust/hexane/src/prefix.rs。

区间前缀和增量

// v0 let (delta, item) = col.get_acc_delta(start, end); let index = delta.as_usize(); let visible = item.is_some(); // v1 let index = col.sum_range(start..end) as usize; // O(log n), 同 slab 快速路径 let visible = col.values().get(end).is_some();

sum_range在内部通过迭代器两次advance_to（起点、终点）一次遍历算出区间和（rust/hexane/src/prefix.rs）；同 slab 内的计算走 BIT 的快速路径。

按累计值 seek ——`advance_prefix`

v0 的shift_acc(n)把"前进 n 个单位"和"告诉我落点在哪"合二为一。v1 的等价物是PrefixIter上的advance_prefix(n)：

// v0 let mut iter = col.iter_range(range).with_acc(); let start_acc = iter.acc(); let tx = iter.shift_acc(n)?; let pos = tx.pos; let consumed = (tx.acc - start_acc).as_usize(); // v1 let mut iter = col.iter_range(range); let tx = iter.advance_prefix(n)?; let pos = tx.pos; let consumed = tx.delta as usize; // 迭代器现在位于 pos+1，可以继续 iter.next() 等

advance_prefix返回PrefixSeek { pos, delta, pv }，其中：

pos—— 落点所在条目位置；
delta——[from, to)区间内消费的前缀量（不含该条目本身）；
pv—— 该条目作为PrefixedValue：.value、.prefix()（排他）、.total()（包含）。

边界契约（automerge 文本索引依赖此语义）：单位宽度[1, 1, 1]时，advance_prefix(0)落在条目 0，advance_prefix(1)落在条目1——越过条目 0 的 1 个单位意味着"越过"它；累计值恰好等于n的条目会被跳过而非返回（rust/hexane/src/prefix.rs）。实现上它通过get_index_for_total在 B 树上做一次 O(log S) 逆查询定位 slab，再在 slab 内做 ceiling 除法定位 run。

定位到已知位置 ——`advance_to`/`delta_nth`

v0 的get_acc_delta(start, pos)返回某位置处的增量与值。v1 的等价物是PrefixIter上的advance_to/delta_nth：

// v0 let (delta, item) = col.get_acc_delta(start, pos); let visible = item.is_some(); let index = delta.as_usize(); // v1 let tx = col.delta(obj_range.start, pos).unwrap(); let visible = tx.pv.value.is_some(); let index = tx.delta as usize; // （或者，在已有的 PrefixIter 上用 iter.delta_nth(pos - start)）

`PrefixColumn`上的便捷方法

一次性查找、之后不再需要迭代器时，用delta方法（内部创建临时迭代器）：

// Value + prefix context at a position, in one shot let tx = col.delta(start, pos)?; let value = tx.pv.value; let consumed = tx.delta; // [start, pos) 上的和

delta(from, to)要求to >= from（反向区间会 panic，属于调用方错误，见 rust/hexane/src/prefix.rs）。已经持有区间或需要继续迭代时，直接使用迭代器方法（advance_prefix/delta_nth/advance_to），避免重复创建迭代器的开销。

交叉验证脚手架模式：迁移期保平安

迁移过程中，把旧列暂时留在结构体里做对照验证，是文档推荐的稳妥做法：

// In the struct text: hexane::PrefixColumn<Option<u32>>, text_old: ColumnData<UIntCursor>, // 临时保留，验证完成后删除 // At every usage site let new_result = col.sum_range(start..end) as usize; let (old_delta, _) = col_old.get_acc_delta(start, end); assert_eq!(new_result, old_delta.as_usize(), "v1 vs v0 mismatch"); // Keep text_old in sync at every splice/insert/remove

要点：

每个使用点都做一次assert_eq!双写对照；
每次 splice/insert/remove 都要同步维护_old列；
测试全部通过后移除_old字段与所有断言。

automerge 仓库内已完成的迁移（脚手架均已移除）：

insert：ColumnData<BooleanCursor>→hexane::PrefixColumn<bool>（完成，脚手架已移除）
top：ColumnData<BooleanCursor>→hexane::PrefixColumn<bool>（完成，脚手架已移除）
visible：ColumnData<BooleanCursor>→hexane::Column<bool>（完成）
text：ColumnData<UIntCursor>→hexane::PrefixColumn<Option<u32>>（进行中，脚手架仍活跃）

在当前仓库 rust/automerge/src/op_set2/columns.rs 中可以确认：text、top、visible已是 hexane 类型，text为PrefixColumn<Option<u32>>、top为PrefixColumn<bool>、visible为Column<bool>，与迁移目标完全一致。

API 摘要与迁移映射

所有 seek 类方法统一返回PrefixSeek { pos, delta, pv }：

delta—— 从 seek 起点到该条目之前（不含）的排他累计和；
pv—— 条目本身作为PrefixedValue（.value、.prefix()、.total()）。

迭代器方法（推荐 —— 已持有区间时使用）

| 方法 | 说明 | |-|-| |iter.advance_prefix(n)| 越过n个前缀单位，返回落点条目 | |iter.advance_to(pos)| 跳转到位置pos，返回条目 + 前缀增量 |

列便捷方法（一次性查询）

| 方法 | 说明 | |-|-| |col.delta(from, to)| seek 到to；delta携带[from, to)上的和 |

迁移映射表

注意prefix_delta在 v1 中已更名为sum_range（见 CHANGELOG）。

编码器迁移状态（automerge 侧）

`XYZCursor::encode_unless_empty`的语义陷阱

这是迁移中最容易踩的坑：

v0 的encode_unless_empty只在完全没有追加任何值时才省略编码（即迭代器为空且编码器状态为空）；
v1 的save_to_unless(default)只要所有值都等于 default 就省略。

对可空列两者恰好一致（"空列"即"全 null"），但对不可空列两者会分叉——不可空列请使用 v1 的encode_to（不带_unless），以保持与 v0 线格式一致。v1 的save_to_unless检查条件是self.slabs.is_empty() && self.state.is_single_run_of(value)，见 rust/hexane/src/encoder.rs。

已迁移列（v0 脚手架已移除 —— v1 为唯一事实来源）

剩余 v0 编码器与迁移阻塞点

| 文件 | 列 | 编码器 | 阻塞点 | |-|-|-|-| |op_set2/change.rs|value|RawCursor::encode_unless_empty|Raw 编码—— v1 的Column<Vec<u8>>使用 RLE，产生不同的线格式 | |change_graph.rs|timestamps、messages、extra_bytes_meta|ColumnData<*>::save_to_unless_empty| 这些是活跃的 v0 列而非流式编码器，见"列存储迁移"一节 | |storage/bundle/builder.rs::BundleOpWriter|value|Encoder<'a, RawCursor>| Raw |

需要完成的工作类别

Raw 编码：v1 需要一个RawEncoder（无压缩的字节拼接）。影响change.rs与bundle/builder.rs中的value列，以及 change_graph 中本就是原始Vec<u8>拷贝的extra_bytes_raw。

除此之外，其余所有流式编码器类别（RLE、Bool、UInt、Delta）已全部迁移完成。

迁移期间新增的可复用辅助工具

hexane::Column::remap(|T| T)—— 遍历 run 并通过f重新发射每个值，替换整列。要求T: ColumnValueRef。实现位于 rust/hexane/src/column.rs。
hexane::RleEncoder::save_to_and_remap(out, |T| T)/save_to_unless_and_remap(out, unless, |T| T)—— 与save_to/save_to_unless类似，但保存时直接应用f，无需经过Column往返：用RleDecoder直接遍历编码器自身的缓冲区并重发射进新编码器。实现见 rust/hexane/src/encoder.rs。
hexane::RleEncoder::append_owned(T)—— 有主值的简写，与append(T::Get<'a>)互补；让持有Option<String>或String的调用点无需包装成append_n_owned(v, 1)即可追加。
hexane::DeltaEncoder<'a, T: DeltaValue>—— 流式增量编码器，镜像RleEncoder的接口（append、append_n、extend、save、save_to、静态encode/encode_to）。与 v0DeltaCursor及 v1DeltaColumn::from_values字节兼容。支持全部DeltaValue类型：u32、u64、i32、i64、usize及其Option<_>变体。

列存储迁移状态（automerge 侧）

与上面的编码器迁移相互独立：automerge 在内存中为 op set、change graph 及若干索引保留了活跃的ColumnData<*>列，这些列通过 v0 列 API（splice、iter、get等）读写。

已迁移列（`hexane::Column`/`hexane::PrefixColumn`）

在 rust/automerge/src/op_set2/columns.rs 中可以验证这些字段的当前状态。

剩余 v0`ColumnData<*>`列与迁移阻塞点

需要完成的工作类别

平凡 RLE 迁移（id_actor、obj_actor、obj_ctr、key_actor、action、inc、num_ops、messages）：与已完成的text/top/visible迁移同一模式 —— 改字段类型 + 更新所有调用方使用 v1 的迭代器/get/splice API。
succ_count及其伙伴（succ_count、succ_actor、succ_ctr）：子列耦合意味着这三列必须一起迁移。succ_count使用前缀和语义 → 变为PrefixColumn<u32>（类似text）；子列由它的前缀和定位。
Acc 权重列（value_meta）：v0 的MetaCursor提供agg(item) = item.length()供列累加。extra_bytes_meta已通过PrefixValue for ValueMeta { to_prefix(v) = v.length() as u128 }解决 —— 同样的实现可套用于value_meta。
Delta 列（id_ctr、key_ctr、succ_ctr、timestamps）：需要流式DeltaEncoder与DeltaColumn上匹配ColumnData<DeltaCursor>的 splice/iter API。这是 v1 工作中最大的一块。
MarkIndexColumn：独立自定义列，逻辑自成一体，迁移本身就是一个小项目。

迁移完成后的验证

单元与模糊测试：cargo test -p hexane（约 525 个测试，含模糊测试与 golden fixtures，见 rust/hexane/README.md）；
性能基准：cargo bench -p hexane（divan 基准：column_ops、load、remap 等）；
格式稳定性：hexane 的字节格式就是Automerge 文档格式，被 golden fixtures 以字节精确的期望编码钉死（对照原始参考实现捕获）。如果某个改动触发了这些测试，那不是测试失败，而是与每一个现存文档的兼容性断裂（rust/hexane/README.md）。

因此，在迁移value这类 Raw 编码列之前，务必确认RawEncoder的线格式与原RawCursor逐字节一致——这是迁移中唯一的"格式级"阻塞点，其余类别（RLE、Bool、UInt、Delta）均已打通并得到 golden 测试的保护。

后端

【免费下载链接】automerge

A 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

点击查看免费下载

企业官网建设流程全解析

【免费下载链接】automerge

Automerge Hexane 列式存储迁移实战：从 v0ColumnData<C>到 v1PrefixColumn<T>/Column<T>

为什么迁移：从 O(n) 线性迭代到 O(log n) 树索引

选择正确的 v1 类型

类型声明迁移

构建列：FromIterator

Splice 操作迁移

API 迁移参考：逐方法对照

获取单个值

迭代区间内的值

位置前缀和（0..pos 之和）

区间前缀和增量

按累计值 seek ——advance_prefix

定位到已知位置 ——advance_to/delta_nth

PrefixColumn上的便捷方法

交叉验证脚手架模式：迁移期保平安

API 摘要与迁移映射

迭代器方法（推荐 —— 已持有区间时使用）

列便捷方法（一次性查询）

迁移映射表

编码器迁移状态（automerge 侧）

XYZCursor::encode_unless_empty的语义陷阱

已迁移列（v0 脚手架已移除 —— v1 为唯一事实来源）

剩余 v0 编码器与迁移阻塞点

需要完成的工作类别

迁移期间新增的可复用辅助工具

列存储迁移状态（automerge 侧）

已迁移列（hexane::Column/hexane::PrefixColumn）

剩余 v0ColumnData<*>列与迁移阻塞点

需要完成的工作类别

迁移完成后的验证

【免费下载链接】automerge

相关推荐

Next.js-Auth0 从 V0 到 V1 迁移指南

Great Expectations 从 V0 迁移到 V1 完全指南

如何快速部署Qwen通义千问：企业级AI大模型完整实践指南

热门文章

文章分类

标签云

相关文章

Agora Flat 开源教室客户端构建指南：从特性解析到 Electron / Web 双端编译打包实战

Rockstar 语言类型转换与变更操作完全指南：split / join / cast / turn 的源码级实战

H3C与华为交换机配置命令对比：VLAN、链路聚合与OSPF实战指南

需要专业的网站建设服务？

Automerge Hexane 列式存储迁移实战：从 v0`ColumnData<C>`到 v1`PrefixColumn<T>`/`Column<T>`

按累计值 seek ——`advance_prefix`

定位到已知位置 ——`advance_to`/`delta_nth`

`PrefixColumn`上的便捷方法

`XYZCursor::encode_unless_empty`的语义陷阱

已迁移列（`hexane::Column`/`hexane::PrefixColumn`）

剩余 v0`ColumnData<*>`列与迁移阻塞点