后端【免费下载链接】loroMake your JSON data collaborative and version-controlled with CRDTs项目地址https://gitcode.com/gh_mirrors/lo/loro点击查看免费下载导读本文围绕 LoroCRDT 数据协同引擎对 MovableList可移动列表中非法Move/Set操作的导入校验展开。在收到来自其他对端外部输入的更新时指向未知元素、其他列表元素、超出操作因果历史范围或在浅快照文档上指向浅根之前已删除元素的Move/Set现在会返回DecodeError并使整个导入原子回滚文档保持原状且可继续使用而对已删除元素的移动/设置则按并发操作的语义被接受。读完本文你将掌握 Loro 在导入路径上分层校验恶意/损坏操作的设计思路、底层实现源码位置与调用链以及 Rust 与 JS/WASM 两侧的测试验证方式。背景不合法操作如何让文档崩溃MovableList 的Move { from, to, elem_id }与Set { elem_id, value }操作由其他对端产生属于不可信的外部输入。在引入校验之前若干畸形操作会在持有文档锁的状态下触发unwrap()panicMovableListState::apply_diff_and_convert中的pos.unwrap()/value_id.unwrap()MovableListHistoryCache::last_pos中的idlp_to_id(..).unwrap()MovableListDiffCalculator::calculate_diff中的last_value(..).unwrap()越界列表 delta 的convert_index(..).unwrap()diff tracker 的 B 树在巨型位置上越界由于 panic 发生在LoroMutex锁内会毒化poison锁展开unwind过程中析构函数再次触碰被毒化的锁时进程直接中止。在 WASM 环境下panic 表现为不可恢复的 trapRuntimeError: unreachable。相关设计与讨论详见 context/movable-list-op-validation.md。一、被拒绝Err无意义的操作Loro 将无意义的操作分成三类分别在解码期、导入期与状态校验期拦截。1. 任何真实序列都无法到达的位置解码期拦截InnerListOp::check_positionscrates/loro-internal/src/container/list/list_op.rs在二进制outdated_encode_reordered::decode_op与 JSONjson_schema::decode_op操作解码时即运行。它会拒绝任何达到或超过UNKNOWN_SPAN_LEN - 1的位置。UNKNOWN_SPAN_LEN u32::MAX / 4约 1,073,741,823是 diff tracker 为未重放历史准备的占位 span 长度crates/loro-internal/src/container/richtext/tracker.rs。此前位置超过该值会在validate_diff有机会运行之前就在 tracker 内部 panic。该检查不需要历史数据因此覆盖所有导入路径包括分离detached导入。更重要的是它是一个硬性文档级限制而非仅导入检查decode_op同样是文档解析自己存储的 change block 与 snapshot block 的入口block_encode.rs因此 ≥ 1,073,741,822 的序列位置在那里也会被拒绝。这符合设计意图快照与更新块同样是外部输入约 10.7 亿项≥1GB 文本的序列任何对端都无法 diff 或导入此前 tracker 会先 panic为自有块跳过检查需要把信任标志贯穿块解码全程得不偿失。2. 未知元素或超出因果历史的元素导入期拦截OpLog::validate_movable_list_elem_refs_in_import_scopecrates/loro-internal/src/oplog.rs逐一检查每个Move/Setelem_id必须是同一容器内、位于该操作因果历史中的Insert操作否则返回LoroError::DecodeError。实现要点元素引用由OpLog::insert_new_change记录进打开的ImportRollback因此覆盖直接导入的变更、导入解锁的 pending 变更以及import_batch的每一个 blob校验器只读记录列表不会重新从 change store 读导入范围。OpLog::resolve_movable_list_elemcrates/loro-internal/src/oplog.rs通过一次ChangeStore::get_change_by_lamport_lte查找定位元素该查找同时扫描已解析块与仅 KV 的块因此 miss 意味着该 lamport 不在已存历史中。元素解析结果不依赖具体操作因此每个elem_id只解析一次并缓存moves/sets 会反复命中同一元素避免每操作克隆/插入版本向量对比AppDag::get_vv改用ensure_vv_for读取缓存的开头版本。因果性检查is_visible_movable_list_elemcrates/loro-internal/src/oplog.rs同一 DAG 节点中更早的操作来自同一对端节点起始版本已覆盖其他对端的因果部分仅当elem_id.lamport op_lamport或元素非本容器插入时判定不可见。浅快照文档上 miss 时回退到浅根状态ContainerHistoryCache::shallow_root_has_movable_list_elem根之后的操作只能看到根处仍存活的根前元素。调用点有三处crates/loro-internal/src/loro.rs 附近的import_changes_and_apply_delta_to_state_if_needed附加attached分支启用rollback_enabled时分离detached分支preflight 请求作用域且无批处理作用域打开时自行打开以及BatchImportGuard::finish——在收尾 checkout 前对整个批次校验一次失败即整批回滚见 context/import-batch-atomicity.md。3. 逃过导入的越界from/to状态校验期拦截MovableListState::validate_diff在操作索引空间计入已删除项对列表 delta 做边界检查与ListState::validate_diff一致该检查需要状态因此分离导入无法运行它见已知缺口它检查的是合成后的 delta因此被同一导入中后续操作抵消的越界 move如move to: 9后跟delete pos: 9会被接受——所有路径对其结果一致文本有等价检查RichtextState::validate_diff在实体索引空间边界检查文本 delta此前超过文本末尾的 insert/delete/mark 会在insert_elem_at_entity_index中持锁 panicloro-dev/loro#1160。为什么每个此类导入都需要回滚作用域ImportChangesPreflight与PendingChanges::has_state_apply_rollback_ops会为 List、MovableList、Text、Tree 操作设置needs_state_apply_rollbackoplog::state_apply_can_reject。没有该作用域的导入若被validate_diff拒绝其 diff 会 panic因此validate_diff可能失败的容器类型必须列入其中作用域开销极小每次导入仅若干小克隆与日志条目单操作 Text 导入约 0.3 µs20k 次导入 ~44→50 msloro-dev/loro#1160大导入无可测量变慢。preflight 会检查每一个新变更的操作包括 deps 尚不在 DAG 中的变更其 deps 可能是同一导入中更早的变更会在导入过程中解锁它们。此前它会在查看操作前跳过这类变更使[C1: 仅 Map 变更, C2: 依赖 C1 的伪造操作]同时跳过回滚作用域与校验跨容器 move 被静默接受、把同一元素放进两个列表见测试cross_container_move_is_not_applied_to_two_lists。二、被接受CRDT 语义对已删除元素的 move/set因果上位于其元素删除之后的Move/Set无法来自公开 API但它仍然被接受含义与对已删除元素的并发move/set 相同move 创造了新位置元素以最后的值复活set 改变了一个无人能见的值。原因有二对伪造者无新增价值伪造者可声明删除之前的 deps通过合法并发 move 获得同样效果一致性拒绝代价不可承受checkout 模式重放checkout、import_batch的收尾重挂、并发导入、detached →attach需要知道元素在操作版本处是否存活这要求从列表项到覆盖其删除的索引若只有线性路径拒绝import与import_batch对同一字节流的结果会不一致。唯一无法直接应用该语义的路径是前向快速路径DiffMode::Linear/ImportGreaterUpdates那里 movable-list diff 只携带操作触及的字段其余由DocState中的元素补全。检测与回退MovableListState::references_absent_elem/DocState::needs_checkout_diff检测 delta 是否移动/设置了状态中缺失的元素recalc_in_checkout_mode_if_neededcrates/loro-internal/src/loro.rs用DiffCalculator::new(true)Persist恒为 Checkout 模式重算该导入的 diff等价于完整重放诚实的导入永远不会触发它validate_diff仍会对这类 delta 返回Err作为兜底。三、测试验证Rust 与 JS/WASM 双端Rust 端crates/loro/tests/movable_list_invalid_ops.rs 构造伪造 JSON 更新并通过import_json_updates导入断言拒绝后文档不变且可用Snapshot::assert_unchanged校验深值与 oplog 版本向量assert_usable验证仍可本地编辑、仍可与其他对端正常同步每条导入路径结果一致assert_same_result_on_every_import_path在普通导入、二进制更新、import_batch、快照加载导入、detached 导入 attach之间交叉验证并与一次性全量重放的文档对比深值与版本向量覆盖的非法样例未知元素L990、无操作的 peer、指向删除操作而非元素的 lamportL30、跨容器元素L40、因果历史之外的元素L31、越界from/to、巨型位置u32::MAX/4及以上包括 List/Text 的巨型 insert/delete、同一导入内依赖forged_after_map_change单/双 peer 两种变体合法场景对已删除元素 move/set 与并发删除移动的复活语义concurrent_delete_and_move_resurrects_moved_element、浅快照上仍存活元素的 move/set、快照加载文档上旧元素的导入、反向删除len: -1仍被接受。另见 crates/loro-internal/src/tests/import_atomicity.rs 的二进制与import_batch用例、crates/loro-internal/src/oplog/change_store.rs 的ChangeStore回滚与 KV 查找测试。JS/WASM 端crates/loro-wasm/tests/movable_list_invalid_ops.test.ts 验证 WASM 行为错误必须可读/Decode error/且绝不出现unreachabletrap文档 JSON 与 oplog 版本不变且仍可编辑同步。同时覆盖伪造操作依赖同一导入内变更、巨型位置、对已删除元素的 move 应用、快照加载文档导入旧元素以及getChangeAtLamport在快照加载后能找到存储在 KV 块中的变更该用例直接暴露了下文的 change-store 缺陷。四、本次工作暴露的 ChangeStore 陷阱decode_block_range错读一个版本 varintencode_block写出的 postcardEncodedBlock无版本前缀但decode_block_range仍按带版本前缀读取导致每个字段错位一位。历史3d2d9d9c2024-09refactor: optimize block encoder移除了块的version字段及其编码器与完整解码器却遗漏了decode_block_range。所有loro-crdt1.0.0*版本都包含该提交因此任何 1.x 构建都从未写过带版本前缀的块修复不会导致存量数据不可读。其后果包括非 0 counter 开头的块被跳过0P块把 lamport 长度当成了 lamport 起点仅 KV 块上的 lamport 查找错误快照加载后的get_change_with_lamport_lte/ JSgetChangeAtLamport在 main 上同样损坏元素校验器也受影响。既有测试未发现是因为它们先解析了每个块。回滚不得把旧块留在下一次插入之前insert_change_inner会把变更合并进其前一个缓存块。失败序列一次导入创建对端最新块而未加载更旧块作用域内的一次读取如校验器的 lamport 查找缓存了更旧的 KV 块回滚移除最新块下一次同变更插入便以 counter should be continuous panic。因此ChangeStore::rollback_import会驱逐回滚触及的每个对端已 flush 的块按需从 KV 重载。此外该查找解析时注册的容器链接会被 arena 回滚丢弃回滚因此会丢弃自导入开始以来解析块的变更见 context/arena-parent-links.md 的 import rollback 小节。廉价回滚记录ChangeStoreRollback为每个导入追加过的未 flush 的 scope 前块保存一个BlockShape变更数、末变更的操作数与最后一个操作。回滚截断回该形状即可因为导入只追加。flush 的块无需记录其 KV 副本即 scope 前版本。此前的记录是整个块的Arc使 scope 下每次导入的下一次追加都要复制块的变更小 movable-list 导入慢约 40%而 List/Tree 导入在 main 上已为此付出代价现在快约 45%。五、已知缺口未在本次修复中解决from未指向其元素的Move被接受tracker 会移除from处的任意列表项导致另一元素消失。结果在所有路径一致但不匹配任何诚实操作。显式分离的文档导入仅被状态校验拒绝的操作越界列表插入、越界 movable-list move在attach()/checkout_to_latest上会 panic它们返回()并expectcheckout。影响所有容器类型且早于本次变更。FastSnapshot内的 oplog 未逐操作校验那需解码每个块伪造快照仍可能在后续 checkout 触达 diff 计算器的 unwraps。伪造变更若作为 pending 停放解锁它的后续导入会失败并被回滚与列表越界错误行为一致。总结Loro 对 MovableList 非法Move/Set的导入防御是分层设计解码期用check_positions拒绝不可达的巨型位置覆盖所有路径含 detached 导入导入期用validate_movable_list_elem_refs_in_import_scope校验元素引用覆盖整批导入与批量回滚状态校验期用MovableListState::validate_diff检查合成 delta 的越界索引。三类检查共同把此前会毒化锁并导致进程中止/WASM trap 的输入转化为可读的DecodeError与文档原状回滚而对已删除元素的 move/set 按并发 CRDT 语义接受保证了所有导入路径含快速路径回退到 checkout 模式重算的结果一致性。伴随修复还校正了 change-store 的块解码与回滚记录并由 Rust 与 TS 双端测试锁定行为为其他容器的外部输入校验提供了可复用的参考范式。赞分享后端【免费下载链接】loroMake your JSON data collaborative and version-controlled with CRDTs项目地址https://gitcode.com/gh_mirrors/lo/loro点击查看免费下载相关推荐Type Challenges 进阶实现 GetRequired\T\从对象类型中提取所有必需属性Type Challenges 进阶实现 GetRequired\T\ 从对象类型中提取所有必需属性 导读 GetRequiredT 是 type ch后端从崩溃到回滚Miniforge版本管理的完整安全操作指南从崩溃到回滚Miniforge版本管理的完整安全操作指南 引言 在软件开发和数据科学工作中环境配置和版本管理是至关重要的环节。Miniforge作为一个轻量开发工具包管理器HsMod终极指南55个功能全面改造你的炉石传说游戏体验HsMod终极指南55个功能全面改造你的炉石传说游戏体验 HsMod是一款基于BepInEx插件框架的开源炉石传说模改工具它通过55实用功能实现游戏体验的游戏开发上一篇Clay跨平台构建CMake工具链文件编写指南下一篇crypto-js模块测试案例分析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考