后端【免费下载链接】loroMake your JSON data collaborative and version-controlled with CRDTs项目地址https://gitcode.com/gh_mirrors/lo/loro点击查看免费下载导读本文基于 context/loro-js-performance.md2026-09-30 对照代码核验整理系统讲解 loro.js——Loro 项目中的纯 TypeScript CRDT 运行时——的性能架构。核心目标是让loro-js/src/runtime中各个数据结构的渐进复杂度asymptotic behavior对齐 Rust 原生实现同时接受一个更大的 JavaScript 常数因子。读完本文你将理解 Text/List/MovableList 的顺序统计树treap、删除与样式区间索引、快照懒加载与历史覆盖层history overlay等核心机制掌握其复杂度保证、基准测试运行方式以及当前仍存的常数因子与内存差距。背景纯 TS 运行时的性能定位loro.js 的纯 TypeScript 运行时位于loro-js/src/runtime。它的性能目标不是与 Rust 在绝对时间上打平而是继承 Rust 运行时的渐进复杂度操作代价随数据规模的增长方式与 Rust 一致允许付出更大的 JavaScript 常数因子。文档中反复出现的 expected O(log n)、O(output size) 等表述正是这套架构对外承诺的复杂度契约。后续小节将逐一展开这套契约的具体载体顺序统计 treap、删除索引、有序排名索引、富文本样式锚点与样式区间索引、版本切换、事件增量、快照懒加载与单容器补齐等。顺序统计索引SequenceIndex treap节点结构与 32 元素物理跨度loro-js/src/runtime/sequence-index.ts是 Text / List / MovableList 共用的顺序统计 treapSequenceIndex也是整个性能架构的地基。其核心设计要点如下一个节点最多容纳 32 个相邻 Unicode 标量或列表项源码常量MAX_SEQUENCE_SPAN 32。标量节点保持轻量多元素跨度span则维护局部可见性与编码前缀索引。O(1) 尾部追加与有界插入成本在节点右边界追加时只需 O(1) 更新跨度在跨度内部插入最多移动 32 个位置。子树缓存多维度度量每个子树缓存物理长度、可见 Unicode 长度、UTF-16 长度、UTF-8 长度并增量维护操作 ID 与历史插入/删除计数器区间索引。惰性 增量的 MovableList lamport 索引lamport 首次查询时才构建之后增量维护。分层计数器存储顺序操作计数器用稠密数组远距离计数器用稀疏区间索引随机删除的目标 ID 用排序的 1024 计数器分页paged index。O(log n) 转换族位置、ID、游标、编码单位的互转均为预期 O(log n)物化输出仍为 O(输出大小)。从源码可以看到节点字段的实态ownCount、ownVisibleCount、ownVisibleUtf16、ownVisibleUtf8、visibleOffsets、visibleUtf16Prefix、firstVisibleId、idRunCount等均由 tree 节点持有sequence-index.ts。内联位置免去每标量一个 WeakMap 定位对象元素通过模块级 SymbolSEQUENCE_NODE、SEQUENCE_OFFSET见 sequence-index.ts记住自己所在节点与有界跨度内偏移避免为每个标量单独分配一个 WeakMap 定位对象。这对 B4 这种 18 万标量级的场景直接减少了对象数与内存足迹。可见 ID 连续段缓存子树额外缓存其可见 ID 是否构成一段连续 run。因此以下操作从按字符扫降为按段扫把可见区间转换为 delete/style ID runs把 ID run 映射回 UTF-16 事件区间从历史因果视图获取 ID runs。对连续文本其成本为预期 O(log n 返回的 runs 数) 而非 O(字符数)。删除索引SequenceDeletionIndex 与惰性子树隐藏loro-js/src/runtime/sequence-deletion-index.ts用互不相交的 target/delete ID 区间存放连续 ID 跨度删除的因果元数据。核心技巧惰性可见性标志一个物理上连续的子树可以用一个懒标志 缓存度量更新整棵隐藏而不用触碰其后代。小碎片跨度走操作 ID 定位索引只重算被触碰的 32 元素跨度一次且只重算这些跨度祖先路径的并集避免为每个小删除扫描一棵碎片化的 B4 树。单元素删除有更小的标量快路径其操作计数器稠密存储随机顺序的 target ID 放入分页索引从而省去每个 B4 删除一个平衡树节点。标量删除计数器索引只保留给孤立删除和一对多删除。源码印证SequenceDeletionIndex内部按 peer 维护TargetSegment与OperationRun两棵OrderedIndexsequence-deletion-index.tsadd时按 target 区间切分边界并追加映射。有序排名索引OrderedIndexloro-js/src/runtime/ordered-index.ts是 Map 键与 Tree 子节点共用的有序排名索引OrderedIndex插入 / 删除 / 排名查找均为预期 O(log n)有序迭代为 O(n)内部是带 parent 指针的随机优先级 treap节点大小在插入 / 删除时通过 split/merge 维护ordered-index.ts。删除索引与文本样式索引内部都以OrderedIndex承载 segment因此它承担了区间切分 排名查找的底层职责。富文本样式零宽锚点与 TextStyleIndex零宽样式锚点富文本样式锚点是 Text 序列中的零宽元素与 Rust 侧模型一致详见 context/loro-js-richtext-anchors.md。每个子树额外计数不含 UTF-16 宽度的元素源码节点字段ownZeroWidth、ownVisibleZeroWidth见 sequence-index.ts因此 Unicode 位置与实体位置的互转只需 O(log n)无锚点的序列仍走旧的快路径。文档中反复强调该模型的代价与收益它使 Rust 或 loro.js 历史无论是否带样式的 replay 能与快照状态对齐解决了此前 loro.js 不计锚点导致 Rust 创建的花式文本 replay 不一致的问题loro-dev/loro#1137。其零宽计数器是 treap 节点的四个额外字段即使无锚点文本也会在每次更新时维护因此普通文本编辑付出恒定成本详见 Benchmarks 一节的数据。TextStyleIndex按操作 ID 区间存样式历史loro-js/src/runtime/text-style-index.ts把样式历史存放在互不相交的操作 ID 区间StyleSegment与标量 Text 元素分离一个样式覆盖其两个锚点之间的元素因此应用一次样式的成本为预期 O(log n 区间内 ID runs 数)检查或撤销一个样式区间为预期 O(log style-runs 受影响 style-runs)全范围 mark 与其订阅 checkout 事件不再逐字符写入或检查Delta 与快照输出复用 run 局部样式解析器工作量保持与返回的文本和样式 runs 线性相关。源码中add会在目标区间首尾#ensureBoundary切分再逐段插入元数据text-style-index.tshistoryAt/membershipAt提供按 ID 的样式历史查询。文档级簿记与版本操作LoroDoc 的每 peer 数组LoroDoc维护每 peer 的变更数组、end 计数器、操作计数、当前 frontiers、排序历史缓存以及每变更的依赖版本缓存。由此最新版本 / frontier 查找为 O(peer/frontier 数)按 ID 查变更为 O(log 该 peer 的变更数)版本区间与显式 ID 跨度利用每 peer 数组直接定位第一个重叠变更尾部导出或前向 checkout 的开销与被选变更数成正比而非全部保留历史增量导入只应用新集成的记录。版本切换retreat 与 comparable-versionRetreat回退与可比版本转换只切换受影响的序列元素、Map 键、Tree 节点、计数器、文本样式条目以及 MovableList 的位置与元素Map / Tree 的 winner 查找使用每 subject/每 peer 数组 二分搜索MovableListloro-js/src/runtime/movable-list.ts详见 context/loro-js-movable-list.md维护一个 FugueSequenceIndex其 0/1 度量标记用户可见位置因此 用户索引 ↔ 操作索引 ↔ 位置 查找均为 O(log n)一次版本切换只切换被切换操作创建/删除的位置再按候选 newest-first 重新选取每个被触碰元素的胜出位置与值成本为 O((受影响操作 被跳过候选) · log n)等价于 Rust 的last_pos扫描无需重放与已应用操作并发的导入操作通过 tracker 版本每位置的 delta 度量解析索引该 tracker 在操作版本间增量移动等价于 Rust 的Tracker::checkout而不是每个操作构建一个因果视图——由pnpm --dir loro-js bench:movable-list度量。连续插入/删除的转换连续 Text/List 的插入与删除转换在两个方向都复用物理 ID runs 与可逆的惰性子树可见性无事件订阅者时隐藏或显示一个完整 run 为预期 O(log n 被触碰物理 runs)有订阅者时恢复操作仍为 O(输出大小)因为事件必须包含恢复的文本/列表值。事件快照无订阅者则完全跳过文档没有事件订阅者时完全跳过事件快照。有订阅者时本地事务、增量导入、前向 checkout 在顺序统计 piece treap 上组合 Text/List 增量——小编辑不会复制整个序列。Map、Counter、Tree 事件同样只保留生成最终事件所需的、事务相对意义上的键、值或节点。事务、导入日志与合并挂起事务增量维护累计操作长度与因果版本绝不在提交时通过重放所有挂起操作来恢复二者。导入日志记录每个导入变更的少量 undo 闭包以便失败回滚导入到空文档时跳过日志只有状态改变后失败才付出一次历史重放见 context/import-batch-atomicity.md。合并相邻变更只把新操作与键表条目追加到保留记录上操作长度、peer end、frontier 集合、操作索引、订阅者更新切片都增量更新因此一串可合并提交不会反复复制或缩减完整历史。同一事务内的连续 List/MovableList 插入还共享单一操作值数组。分配与紧凑性TextRunBuffer 与 compact()普通 Text/List 元素只在操作需要时才分配删除、值与移动元数据Text 样式元数据活在区间索引里。多标量 Text 插入把字符串与 UTF-16 边界一次性存入TextRunBuffer见loro-js/src/runtime/containers.ts内部保存整段#text与#utf16Ends边界数组。物理跨度只保留 buffer 区间因此切分 piece 不复制文本、也不物化 ID 列标量视图只在 API 主动索取时创建。单标量编辑仍走较小的对象路径因为 B4 轨迹全部由单标量插入构成为每次编辑构造临时打包跨度得不偿失。LoroText.compact()是显式、安全的重建入口containers.ts把高度碎片化的标量存储重建为相邻的 32 元素跨度且不改变 CRDT 历史重建函数会跳过含锚点的元素。文本迭代方面迭代回调返回false时直接在索引内停止toString、slice、iter消费连续的可见存储区间并一次读取整个 text-buffer 区间而不是为每个字符分配标量视图与 substring区间谓词也能在索引内提前停止因此Text.unmark不必先把被检查区间物化再应用 mark。可选的行索引按需构建的 sidecarText 行元数据是可选的。第一次lineCount、lineStart、lineAt或getLine查询会构建稀疏的 per-buffer 与 per-node 换行偏移及子树合计切分共享 buffer 偏移而不复制节点合计放在 sidecarSEQUENCE_LINE_BREAK_METRICSWeakMap见 sequence-index.ts未开启行 API 的文档不会撑大热路径 treap 节点形状后续编辑维护索引行/位置查找预期 O(log n)行分隔符为 LFgetLine对 CRLF 输入去掉前置 CR位置保持 UTF-16 偏移。源码中enableLineBreaks()会替换度量函数并recomputeSubtreeMetricssequence-index.tslineCount返回visibleLineBreaks 1空文本为一行。Fugue 增量 origin 索引与并发插入Text / List 的 Fugue 插入只在需要给并发/未来区间排序时才使用增量originLeft直子索引连续 ID 保持单子边隐式SequenceIndex查找下一个因果包含元素时可跳过整个未来 ID run普通本地编辑走较小的未索引路径MovableList 位置保持扫描MovableListState, useOriginIndex falseorigin 索引会把兄弟子树 其后一个并非其子孙的并发位置错误排序。兄弟子树是连续的因此两个直子之间的空隙属于较早的子最后一个子之后的区间还可能包含 origin 在originLeft左侧的并发元素Rust 的扫描在它们之前停止。该索引因此先检查区间最后一个元素是否从originLeft衍生否则二分搜索边界。衍生测试沿 origin-left 链接走但通过 per-peer 排序的显式非连续元素计数器跳过每个隐式 run成本为 O(显式链接数 · log n)等价于 Rust 的基于跨度的扫描而不是在长并发 run 中逐标量探测loro-dev/loro#1139。文档给出 2026 年 9 月 28 日的实测对比Node 22B4 轨迹作兄弟子树时二分搜索 7.3 ms 对 11.1 ms而深层显式链接链两个位置交替输入、64k 元素上 60.6 ms 对 15.5 ms每次 O(log n) 探测都要走链接链。现实轨迹更偏向二分搜索。热 origin 索引下512k 字符连续输入后导入一个并发字符耗时 0.28–0.31 msmain 分支为 0.29–0.30 ms但其会错排其他情形逐标量走法为 9.7–10.7 mstext-concurrent-insert-after-long-run从 64k 到 512k 字符保持在 0.18–0.30 ms。导入删除的解析与回退保障导入的 Text 删除按操作在其因果视图中的位置解析等价于 Rust 的 trackerLoroText._deleteTargets通过visibleIdRuns或缓存的因果视图成本 O(log n runs)。记录的start_id只是回退方案因为 Rust 的 WASM 构建对星形文本astral text可能记录偏离其 UTF-16 长度的start_id。本地删除跳过该查找。版本切换路径有多层安全网按 ID 去重SequenceElementSet打包的 Text 跨度每次查找返回新包装两个并发删除同一字符时曾导致重复删除失败回滚补齐completion抛错则重装快照状态并保持容器已水合checkout 抛错则恢复之前的版本与状态#transitionTo在 try 内准备diff在自身或回移抛错时以完整重建恢复当前状态转换前检查#canTransitionRecords检查每个序列仍持有被跨越插入操作命名的元素。它按容器收集 runs每容器调用一次containsIdRuns见 sequence-index.ts读取 ID 而不构建元素视图O(元素数 runs log runs)。此前每操作一次调用使 checkout 达到 O(操作数 × 元素数)8k 文本中 2k 分散插入在 main 上耗时 698 ms现在 4.2 mstext-scattered-edits-checkout1k→8k 从 13→698 ms 降到 1.0→4.2 ms2026-09-29 测。快照路径SSTable、懒状态与历史覆盖层编码层的流式化快照 SSTable 在能减小体积时选择可互操作的 LZ4 块。DeltaRLE 状态列以流式编解码而非分配百万项 BigInt 中间值LZ4 解码直接写入类型化存储。懒水合与覆盖层导入初始 latest-state 快照时会立即校验每个状态条目与 frontier 块但保留当前状态为自有的已编码 SSTable根容器在导入时水合被引用的后代容器按需、一个 SSTable 块一个块地解码未触碰块在快照导出时直接复制脏容器条目本地重写已编码历史是只读基底之后本地或导入的变更使用小型物化覆盖层overlay。由此本地编辑、完整 update 导出、latest 快照导出、当前读取、版本、frontiers、操作计数都不会构建完整历史 DAG。而历史查询、checkout、部分区间导出等需要任意依赖遍历的 API仍会在 staging 文档上一次性构建并校验全部历史索引后才安装。导入订阅者保留急切状态水合因为其导入事件必须描述每个变更容器。快照序列的补齐completionText/List/MovableList 从快照水合后无论 eager、lazy 还是 shallow root没有墓碑、删除索引也没有快照操作的样式/值/移动历史。LoroDoc.#snapshotSequences记录每个此类容器及其快照版本。补齐发生在两类时机导入前#prepareSnapshotImport补齐被导入记录与快照版本并发触碰的容器该记录的因果视图可能需要快照丢弃的墓碑loro-dev/loro#1163checkout / checkoutToLatest / diff / detached 快照导出#encodeLatestState前#prepareSnapshotTransition只看转换触碰的容器——懒编码的容器直接水合未触碰的懒容器仍持有其最新状态即当前版本状态转换跨越快照操作时从该容器自己的操作重建#completeSnapshotSequenceshallow 文档中从其 shallow root 条目出发。快照之后应用的操作照常索引Map/Tree/Counter 状态无需重建每容器记录索引每个历史修订构建一次连续续写的文本插入合并为一个跨度重放coalescedTextInsert见 document.ts。不相关容器从不重放懒 SSTable 保留因此快照导出复制每个未触碰条目、只重写被触碰者。删除转换仍被拒绝除非删除索引记录过该删除例如 detached 状态下导入的删除。补齐的可比性与 unreplayable 容器补齐会把 Text/List 的重放与快照状态可见 ID 加值比较。锚点模型loro-dev/loro#1137使带样式文本也可重放此前 loro.js 不计锚点Rust 创建的花式文本重放会不一致。现在重放仅在快照状态与其自身历史冲突时才不同loro.js 0.2 写的快照见 loro-js/README.md 的 Upgrading from 0.2或保留区间缺口描述的 shallow 快照见 context/loro-js-rust-differential.md。冲突时重放被丢弃容器变为unreplayable保留快照状态、只编码一次、永不给重放。触碰它的转换无操作运行后再单独移动#planSnapshotStates若已安装状态已含全部前向操作记为appliedText 按 ID 与样式版本切换O(delta)与无历史状态相同否则例如 detached 时导入的更新从快照状态加目标包含的后继操作重建#rebuildFromSnapshotStateO(容器大小 其操作数)。事件来自转换的记录或跨越样式操作时取整个容器值其区间来自位置。该模型保证了什么最新状态、导入与导出等于快照状态加后继操作按 loro.js 的应用方式与快照并发的后继操作在补齐后的容器上运行。更早的版本是近似的快照状态无法恢复其之前被删除的文本。Round-3 评审的随机 Rust 历史中旧版本与revertTo与 Rust 的分歧多于 main437 对 317 个检查版本、287 对 151 次 revert而 main 在 90 个种子中有 57 个在 checkout 往返后损坏最新状态、本 PR 无损坏。锚点模型消除这两种成本。main 上还有两个缺口detached 导入更新后活文档上的 shallow 导出可能改变其最新状态纯文本亦然loro-dev/loro#1136 修复纯文本情形中途抛错的 shallow 导出把活文档留在根或中间状态因为#encodeShallowSnapshot无恢复地重建。补齐成本第一次与快照并发的导入付出一次该容器历史的重放——这正是从 updates 加载的文档在加载时付出的工作。2026-09-30 实测每 peer 2000 次随机 Text 编辑快照后并发导入 675 msmain 上完整历史 update 导入后为 667 msmain 的快照路径只花 235 ms因为它跳过了墓碑loro-dev/loro#1163。8000 项 MovableList 加每 peer 8000 次 move/set 时快照路径 92 msupdate 导入后 60 msmain 为 35/96 ms其快照路径跳过历史并偏离 Rust。Text 并发导入仍超线性与 main 一致因为每操作都要算因果视图causalView。完整重建与 shallow 历史#rebuildFromHistory非增量回退路径shallow 导出、forkAt以同样方式重建 unreplayable 容器。它不再先检查快照水合的带样式 Text#checkSnapshotSequences已在 loro-dev/loro#1137 移除——那个额外重放本是为了补偿锚点偏移 Rust 位置如今锚点模型已计入。因此带样式与纯文本行为一致未被转换补齐的水合容器取自身历史重放0.2 快照即 Rust 的读数只有 shallow 导出的根状态用重放因为快照状态晚于根。forkAt仅在版本包含该状态版本的 fork 中保留快照状态更早的 fork 没有撤销该状态中后继操作所需的操作故保留自身历史重放并与自身操作保持一致。测试覆盖见 loro-js/tests/snapshot-checkout.test.ts随机 checkout、detach、importRust rich-text 历史rich-text-history.json对照纯导入文档外加 fork、Rust MovableList movesmovable-moves.json与标记字符被删除的 Rust 文本deleted-mark.json。关键实测数字文档记录首个 checkout导入 262,144 操作的单一 peer Text 快照后约 57 ms早期整文档重放约 148 msApple M5 Pro 5 轮交替中位数65,536 操作为 25 对 43 ms订阅者无可测增量早期 262k 为 192 ms。之后 checkout 稳定在 0.1–0.4 ms。含 32,768 个 child Map 的文档回退一个 Map 无需重放57–61 ms 对 152 ms峰值 RSS 同为 234 MiB此前 284 MiB。合并插入还让 B4 轨迹一次 update 导入快约 30%约 195 对 275 ms。计数合并B4 留下 182,315 个标量对象打包进 13,613 个 TS treap 节点更新导出合并后从 1,153,540 缩到 274,574 字节文本状态合并连续文本使快照从 309,780 缩到 206,553 字节。首个 checkout 成本从每操作一次检查698 ms 8k 分散插入降到每容器一次4.2 ms。shallow 历史首回浅文档中 32,768 child Map 的 Map/Tree 回退低于 1 ms1,024 Maps 起保持平坦loro-js 与 Rust 写入的快照皆然之后每次约 0.02–0.03 ms对应 Rust 每 Map checkout 索引种子的 loro-dev/loro#1120、#1124。事件与订阅者路径的性能数据64k Text 中一次订阅的单字符编辑约 0.35 ms此前事件生成复制整个 Text 时为 34.6 ms含 64k 订阅中插的事务总约 294 ms随操作数近似线性。有无订阅者下回退/恢复一个单变更尾部含单字符 mark、MovableList set/move 后缀、单变更diff在 1k–64k 保留变更间稳定在 0.05–0.69 ms四元素 MovableList 在并发 move 分支间直切低于 0.4 ms订阅路径低于 0.6 ms混合 move/insert/delete 的分支切换低于 0.5 ms。删除连续 64k Text ID 跨度约 0.5–0.8 ms含订阅路径最新孤立 run 的标量参考路径约 101 ms1k–64k 基本平坦因为删除覆盖单一物理 ID run。订阅的前向 checkout 组合全范围删除与 mark1k 字符 0.41 ms、8k 0.16 mswarm 后。历史 mark 位置直接转因果 ID runs事件生成前减去被移除 ID runs紧凑删除事件不再引发逐字符中间扫描。无订阅者时连续 64k 插入回退/恢复约 0.19/0.14 ms连续 64k 删除回退/重放约 0.4–3.2/0.13 ms只发删除的订阅转换低于 0.4 ms恢复 64k 值约 70–76 ms正比于事件负载。100 提交探测中不相关容器订阅者 1k/8k/64k 下每受影响容器 0.018/0.011/0.009 ms——派发不扫描无关监听器。detached 64k Text 上首块后停止iter约 0.25 ms完整toString约 1.5–1.6 ms双数组路径 2.2 ms中间 32k 切片约 0.42 msrange-array 路径 1.27 ms。历史序列视图在下降前把整棵物理 ID 子树计为完全包含/排除64k 冷视图排除全 run / 仅最终元素 / 三分之一后缀约 0.31 / 0.34 / 0.11 ms1k–8k 暖矩阵全排除约 0.01–0.06 ms。最近 8 个因果版本缓存已算视图1,000 次交替缓存查询在 64k 内低于 0.7 ms。1k–64k 保留变更下只导出/导入/checkout 最后变更 warm 后低于 0.7 ms单操作跨度导出低于 0.3 ms。样式与锚点的代价明细对一段连续 64k Text 应用 mark孤立重复探测约 0.37–0.74 ms全范围 mark 回退/恢复约 0.11/0.10 ms订阅恢复约 0.41 ms——随 ID/style runs 与输出格式区间扩展而非 64k 字符。锚点在序列中后2026-09-28Node 22loaded 机器 best of 764k 全范围 mark 0.07–0.08 ms其回退/恢复 0.06–0.07 ms订阅恢复 0.06 ms粗体范围内输入 1,000 字符 3.1–3.3 ms此前 1.7–2.1 ms——每次插入都要与两个物理邻居的样式成员关系求交。反复 mark 同一区间会嵌套锚点第 n 次 mark 的区间包含前 n-1 个起始锚点为独立 ID runs因此应用与跨版本移动为 O(n)与 Rust 一致其StyleRangeMap在该处每锚点一段。text-repeated-mark-tail-{retreat,restore}因此随规模增长1k/2k/4k/8k 下 0.5/1.1/2.2/6.9 ms此前 0.16–0.29 msRust WASM 回退 1k/4k/16k 此类 mark 需 7.1/19/362 ms构建 16k 历史 loro.js 402 s、Rust 542 s。其余bench:complexity项 1k–8k 均平坦。零宽计数器是 treap 节点新增的四个字段8,000 订阅中插 15.4–15.8 ms 对 14.3–14.4 mstext-subscribed-batch、history-commit、history-update-batch-import在 8k 时慢 12–20%2026-09-29Node 22。无条目因它们随规模增长。把零宽计数移入仅锚点序列分配的 sidecar像换行合计那样可消除该成本。从快照读 Rust 写的带样式 Text16k 字符、200 marks、2k 后继编辑并 checkout 中间版本首次 24.7–25.0 ms、回最新 4.1–4.3 ms、fork 11.8–12.2 msmain 为 35.9–37.2 / 3.1–3.3 / 29.8–30.5 ms 但文本错误它把文本标为 unreplayable 并切换其快照状态。评审loro-dev/loro#1137Node 26load 25–40复测64k 粗体范围内输入 1,000 字符 2.9–4.4 msmain 1.9 ms8k 重复 mark 尾回退/恢复 8.0–8.1 / 11.6–13.2 msmain 0.4–0.6 ms。评审修复后复测Node 221k/2k/4k/8k 回退 0.51–0.71 / 1.18–1.27 / 2.25–2.80 / 6.11–8.25 ms、恢复 0.47–0.53 / 1.16–1.35 / 2.08–2.57 / 5.89–7.75 msmain 0.08–0.43 ms64k 全范围 mark 应用 0.11–0.17 ms、回退 0.22–0.35 ms、恢复 0.11–0.14 ms。基准测试命令与典型结果所有基准脚本位于 loro-js/benchmarks以node --expose-gc运行见 loro-js/package.json 的 scripts。脚本会完全预热所请求的最大前缀并在强制 GC 前释放前一样本。完整 B4 轨迹pnpm --dir loro-js bench:b4 -- 259778 7在 Apple M5 Pro Node 26.4.0 上完整 259,778 动作 B4 轨迹三样本中位数 353.5 ms样本 351.8–354.9 ms最终 104,852 个 UTF-16 code units进程报告 107.1 MB 已用 JS heap 与 322.1 MB RSS。原数组实现估计需 30–50 分钟20k 至完整轨迹的前缀测量近似线性扩展。同机 Rust Criterion 基准点估计 47.711 ms即 TypeScript 绝对时间慢约 7.4 倍。同次运行还测得快照导出 162.4 ms、更新导出 129.3 ms、快照导入 161.5 ms、更新导入 328.1 ms。文本存储 / 读取 / 行查找 / 显式压缩pnpm --dir loro-js bench:text-buffer -- 131072 50000 7同机 Node 22.23.1 对origin/main的 A/B2026-07-22 文本基准批量 131,072 标量插入 21.8 ms 对 33.2 mstoString0.40 对 6.34 ms中间一半slice0.22 对 3.67 msiter2.00 对 8.05 ms批量文档保留堆从 22.9 MB 降到 10.7 MB。独立交替标量探测 31.0 对 30.8 ms0.8% 差异噪声内。可选行索引构建约 16.0 ms、保留约 1.46 MB1,000 次中间行查找约 0.71 ms 对 103.8 ms重复扁平字符串扫描。显式压缩 50,000 个最大碎片化的中间插入约 20.6 ms物理节点从 50,000 减到 1,563。六对交替运行顺序的全新进程 B4origin/main234.4 ms带文本改动 234.8 ms0.2% 差异噪声内。主 ESM bundle 从 461.87 kB / 88.41 kB gzip 增至 485.79 kB / 92.11 kB gzip。复杂度缩放矩阵pnpm --dir loro-js bench:complexity -- 1000,2000,4000,8000覆盖点/排名查找、穿越删除空隙的游标查找、缓存因果视图、map/root/tree 路径查找、不相关容器订阅者派发、单变更序列与样式版本切换、单变更历史导入/导出/checkout/diff、并发 MovableList 分支切换、1,000 次容器 ID 查找——均验证不随不相关保留状态增长。输出型 APItoJSON、toString、getAllChanges、快照、全版本转换保持与返回/编码数据成正比。真实快照内存工作流pnpm --dir loro-js bench:snapshot-memory -- /path/to/document.snapshot对 11,387,982 字节测试文档423,797 操作、115,147 容器Node 26.4.0 报告加载输入后 70.92 MiB RSS、快照导出后进程峰值 160.70 MiB——增量峰值 89.78 MiB已用 JS heap 峰值 8.58 MiB。快照导入约 0.90 s、本地提交约 1.9 ms、完整更新导出约 6.6 ms、快照导出约 57 msApple M5 Pro。懒状态与历史覆盖层整合前同一工作流导入后立即保留约 703 MiB heap、首次本地编辑后超 860 MiB、快照导出期间达约 1.66 GB RSS。普通完全物化快照路径的 A/B 保持中性三轮 warmup 后两轮 15 样本 B4 快照导出父版本中位数 110.5/107.0 ms懒快照 107.7/107.7 ms两版本都产出相同的 309,780 字节快照。crdt-benchmarks 端到端对比zxch3n/crdt-benchmarks适配器提供与已发布 Loro WASM 适配器的端到端对比本地 loro.js 构建B4 从修复前的 180 秒移除首个拷贝路径后 141.5 秒降到增量维护合并变更长度后的 2.846 秒WASM 适配器为 4.733 秒。B3.5 288 对 303 msB3.3 快照 240,032 字节WASM 约 242 KB此前未压缩 TS 快照 7.95 MB。60k 项 List 更新 231,840 字节、120k 字符 Text 更新 120,095 字节均与 WASM 输出大小一致。C1.1 仍需 6.988 对 1.728 秒其余量差距在剩余常数因子与内存差距一节说明而非视为渐进回归。MovableList 专项pnpm --dir loro-js bench:movable-list度量并发导入的 tracker 版本增量解析见版本切换一节。剩余常数因子与内存差距文档结论已审计的公开路径相对 Rust 运行时没有已知的时间复杂度差距。前向、回退与可比版本 checkout 只应用版本增量连续插入/删除/样式转换使用 ID runs 与惰性子树可见性紧凑的订阅转换不展开这些 runs返回/编码/解码/发出 n 个值的操作保持 O(n)与 Rust 一致。剩余差异是表示方式与 JavaScript 常数因子标量快路径的对象保留多标量 Text 操作共享字符串/ID 跨度但 B4 把 182,315 个标量作为独立操作插入其标量快路径在显式compact()前仍每标量保留一个对象。有界物理节点把 B4 的 treap 节点数砍掉约 13.4 倍内联位置还免去每标量一个位置对象与 WeakMap 条目。直接标量→打包跨度突变路径被实测后否决Fugue 排序会立刻读 ID 与 origin临时打包视图拖慢 B4 多于节省。收窄剩余 Rust 内存差距需要 Fugue 中的原始列访问或调用方选定静默点做压缩而不是无条件打包每次编辑。订阅恢复正比于输出订阅者对大型插入/删除的恢复必须把恢复的文本/列表值放进事件故正比于发出的输出无订阅者时隐藏与显示转换走可逆懒可见性层正比于受影响的 ID runs。快照水合容器的首次补齐latest 快照水合的状态没有墓碑或 MovableList 候选历史。首次以并发方式触碰该容器、或指名其缺失的 MovableList 元素的导入只从自身历史重建该容器#prepareSnapshotImport首次触碰水合 MovableList 的版本转换同理。后续导入与转换恢复增量。MovableList move/set 的导入校验每操作 O(log changes)目标元素在水合状态内时保持延迟快照历史延迟见 context/loro-js-movable-list.md 的 Validation。C1.1 的百万操作并发文本轨迹本地编辑阶段约为 WASM 适配器的 4 倍解析 6.5 MB 快照 3.62 秒对 43 ms。流式 DeltaRLE、类型化 LZ4 解码与延迟历史集成已消除已知超线性与临时分配失败收窄剩余差距需要更紧凑的解码操作/frontier 表示而非又一次公开 API 复杂度改动。旧容器父边绑定没有 parent-edge 绑定的旧或手工构造容器会扫描 parent 一次并缓存恢复的绑定常规容器路径查找直接用索引绑定。最后文档提醒改动这些结构时保持 loro-js/tests/indexes.test.ts 的随机索引不变量覆盖以及 loro-js/tests/rust-interop.test.ts 的 Rust/TypeScript fixture 覆盖随机化 Rust 差分套件loro-js/tests/differential见 context/loro-js-movable-list.md对照 Rust 实现的 WASM 构建检查收敛、事件与编码互换。另外当元素的删除标志、tree 父/位置或 map 可见性变化时必须经由其所属索引的辅助方法变更——直接突变会让子树或有序键缓存失效。小结loro.js 的性能架构可以概括为一句话用有界物理跨度、惰性可见性与增量区间索引把一切按字符/按整文档的工作降为按 run / 按子树 / 按受影响容器。无论是顺序统计 treap 的 32 元素跨度与内联位置、删除与样式区间的分段索引、可选行索引与零宽锚点 sidecar、Fugue 增量 origin 索引还是快照懒水合 历史覆盖层 单容器补齐其目标始终一致——继承 Rust 的渐进复杂度让规模增长时的性能曲线与原生实现同形。若需进一步深挖 MovableList 的 Fugue 模型、富文本锚点语义或导入原子性可继续阅读仓库中 context/loro-js-movable-list.md、context/loro-js-richtext-anchors.md、context/import-batch-atomicity.md 与 context/loro-js-rust-differential.md 等配套文档。赞分享后端【免费下载链接】loroMake your JSON data collaborative and version-controlled with CRDTs项目地址https://gitcode.com/gh_mirrors/lo/loro点击查看免费下载相关推荐RSuite Button 组件入门从默认按钮创建到源码级解析RSuite Button 组件入门从默认按钮创建到源码级解析 RSuite 的 Button 是组件库中最基础的交互元素用于触发用户操作。本文以官方文档中后端RTranslator 离线翻译断网也能实时互译RTranslator 离线翻译断网也能实时互译 RTranslator 离线翻译是一款跑在 Android 手机本地的实时翻译 App。翻译用 Meta 的人工智能AI 应用本地部署语音NLP移动开发Hello 算法时间复杂度实战用 PythonTutor 逐行可视化 O(1) 到 O(n!) 七大类渐近复杂度Hello 算法时间复杂度实战用 PythonTutor 逐行可视化 O 1 到 O n! 七大类渐近复杂度 导读 本文以《Hello 算法》日语仓库中的 P教程文档示例工程教育上一篇Gumbo纯 C99 实现的 HTML5 解析库——安装、核心 API 与解析树实战指南下一篇OpenResume错误恢复机制用户操作回滚与状态重置创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
后端【免费下载链接】loroMake your JSON data collaborative and version-controlled with CRDTs项目地址https://gitcode.com/gh_mirrors/lo/loro点击查看免费下载导读本文基于 context/loro-js-performance.md2026-09-30 对照代码核验整理系统讲解 loro.js——Loro 项目中的纯 TypeScript CRDT 运行时——的性能架构。核心目标是让loro-js/src/runtime中各个数据结构的渐进复杂度asymptotic behavior对齐 Rust 原生实现同时接受一个更大的 JavaScript 常数因子。读完本文你将理解 Text/List/MovableList 的顺序统计树treap、删除与样式区间索引、快照懒加载与历史覆盖层history overlay等核心机制掌握其复杂度保证、基准测试运行方式以及当前仍存的常数因子与内存差距。背景纯 TS 运行时的性能定位loro.js 的纯 TypeScript 运行时位于loro-js/src/runtime。它的性能目标不是与 Rust 在绝对时间上打平而是继承 Rust 运行时的渐进复杂度操作代价随数据规模的增长方式与 Rust 一致允许付出更大的 JavaScript 常数因子。文档中反复出现的 expected O(log n)、O(output size) 等表述正是这套架构对外承诺的复杂度契约。后续小节将逐一展开这套契约的具体载体顺序统计 treap、删除索引、有序排名索引、富文本样式锚点与样式区间索引、版本切换、事件增量、快照懒加载与单容器补齐等。顺序统计索引SequenceIndex treap节点结构与 32 元素物理跨度loro-js/src/runtime/sequence-index.ts是 Text / List / MovableList 共用的顺序统计 treapSequenceIndex也是整个性能架构的地基。其核心设计要点如下一个节点最多容纳 32 个相邻 Unicode 标量或列表项源码常量MAX_SEQUENCE_SPAN 32。标量节点保持轻量多元素跨度span则维护局部可见性与编码前缀索引。O(1) 尾部追加与有界插入成本在节点右边界追加时只需 O(1) 更新跨度在跨度内部插入最多移动 32 个位置。子树缓存多维度度量每个子树缓存物理长度、可见 Unicode 长度、UTF-16 长度、UTF-8 长度并增量维护操作 ID 与历史插入/删除计数器区间索引。惰性 增量的 MovableList lamport 索引lamport 首次查询时才构建之后增量维护。分层计数器存储顺序操作计数器用稠密数组远距离计数器用稀疏区间索引随机删除的目标 ID 用排序的 1024 计数器分页paged index。O(log n) 转换族位置、ID、游标、编码单位的互转均为预期 O(log n)物化输出仍为 O(输出大小)。从源码可以看到节点字段的实态ownCount、ownVisibleCount、ownVisibleUtf16、ownVisibleUtf8、visibleOffsets、visibleUtf16Prefix、firstVisibleId、idRunCount等均由 tree 节点持有sequence-index.ts。内联位置免去每标量一个 WeakMap 定位对象元素通过模块级 SymbolSEQUENCE_NODE、SEQUENCE_OFFSET见 sequence-index.ts记住自己所在节点与有界跨度内偏移避免为每个标量单独分配一个 WeakMap 定位对象。这对 B4 这种 18 万标量级的场景直接减少了对象数与内存足迹。可见 ID 连续段缓存子树额外缓存其可见 ID 是否构成一段连续 run。因此以下操作从按字符扫降为按段扫把可见区间转换为 delete/style ID runs把 ID run 映射回 UTF-16 事件区间从历史因果视图获取 ID runs。对连续文本其成本为预期 O(log n 返回的 runs 数) 而非 O(字符数)。删除索引SequenceDeletionIndex 与惰性子树隐藏loro-js/src/runtime/sequence-deletion-index.ts用互不相交的 target/delete ID 区间存放连续 ID 跨度删除的因果元数据。核心技巧惰性可见性标志一个物理上连续的子树可以用一个懒标志 缓存度量更新整棵隐藏而不用触碰其后代。小碎片跨度走操作 ID 定位索引只重算被触碰的 32 元素跨度一次且只重算这些跨度祖先路径的并集避免为每个小删除扫描一棵碎片化的 B4 树。单元素删除有更小的标量快路径其操作计数器稠密存储随机顺序的 target ID 放入分页索引从而省去每个 B4 删除一个平衡树节点。标量删除计数器索引只保留给孤立删除和一对多删除。源码印证SequenceDeletionIndex内部按 peer 维护TargetSegment与OperationRun两棵OrderedIndexsequence-deletion-index.tsadd时按 target 区间切分边界并追加映射。有序排名索引OrderedIndexloro-js/src/runtime/ordered-index.ts是 Map 键与 Tree 子节点共用的有序排名索引OrderedIndex插入 / 删除 / 排名查找均为预期 O(log n)有序迭代为 O(n)内部是带 parent 指针的随机优先级 treap节点大小在插入 / 删除时通过 split/merge 维护ordered-index.ts。删除索引与文本样式索引内部都以OrderedIndex承载 segment因此它承担了区间切分 排名查找的底层职责。富文本样式零宽锚点与 TextStyleIndex零宽样式锚点富文本样式锚点是 Text 序列中的零宽元素与 Rust 侧模型一致详见 context/loro-js-richtext-anchors.md。每个子树额外计数不含 UTF-16 宽度的元素源码节点字段ownZeroWidth、ownVisibleZeroWidth见 sequence-index.ts因此 Unicode 位置与实体位置的互转只需 O(log n)无锚点的序列仍走旧的快路径。文档中反复强调该模型的代价与收益它使 Rust 或 loro.js 历史无论是否带样式的 replay 能与快照状态对齐解决了此前 loro.js 不计锚点导致 Rust 创建的花式文本 replay 不一致的问题loro-dev/loro#1137。其零宽计数器是 treap 节点的四个额外字段即使无锚点文本也会在每次更新时维护因此普通文本编辑付出恒定成本详见 Benchmarks 一节的数据。TextStyleIndex按操作 ID 区间存样式历史loro-js/src/runtime/text-style-index.ts把样式历史存放在互不相交的操作 ID 区间StyleSegment与标量 Text 元素分离一个样式覆盖其两个锚点之间的元素因此应用一次样式的成本为预期 O(log n 区间内 ID runs 数)检查或撤销一个样式区间为预期 O(log style-runs 受影响 style-runs)全范围 mark 与其订阅 checkout 事件不再逐字符写入或检查Delta 与快照输出复用 run 局部样式解析器工作量保持与返回的文本和样式 runs 线性相关。源码中add会在目标区间首尾#ensureBoundary切分再逐段插入元数据text-style-index.tshistoryAt/membershipAt提供按 ID 的样式历史查询。文档级簿记与版本操作LoroDoc 的每 peer 数组LoroDoc维护每 peer 的变更数组、end 计数器、操作计数、当前 frontiers、排序历史缓存以及每变更的依赖版本缓存。由此最新版本 / frontier 查找为 O(peer/frontier 数)按 ID 查变更为 O(log 该 peer 的变更数)版本区间与显式 ID 跨度利用每 peer 数组直接定位第一个重叠变更尾部导出或前向 checkout 的开销与被选变更数成正比而非全部保留历史增量导入只应用新集成的记录。版本切换retreat 与 comparable-versionRetreat回退与可比版本转换只切换受影响的序列元素、Map 键、Tree 节点、计数器、文本样式条目以及 MovableList 的位置与元素Map / Tree 的 winner 查找使用每 subject/每 peer 数组 二分搜索MovableListloro-js/src/runtime/movable-list.ts详见 context/loro-js-movable-list.md维护一个 FugueSequenceIndex其 0/1 度量标记用户可见位置因此 用户索引 ↔ 操作索引 ↔ 位置 查找均为 O(log n)一次版本切换只切换被切换操作创建/删除的位置再按候选 newest-first 重新选取每个被触碰元素的胜出位置与值成本为 O((受影响操作 被跳过候选) · log n)等价于 Rust 的last_pos扫描无需重放与已应用操作并发的导入操作通过 tracker 版本每位置的 delta 度量解析索引该 tracker 在操作版本间增量移动等价于 Rust 的Tracker::checkout而不是每个操作构建一个因果视图——由pnpm --dir loro-js bench:movable-list度量。连续插入/删除的转换连续 Text/List 的插入与删除转换在两个方向都复用物理 ID runs 与可逆的惰性子树可见性无事件订阅者时隐藏或显示一个完整 run 为预期 O(log n 被触碰物理 runs)有订阅者时恢复操作仍为 O(输出大小)因为事件必须包含恢复的文本/列表值。事件快照无订阅者则完全跳过文档没有事件订阅者时完全跳过事件快照。有订阅者时本地事务、增量导入、前向 checkout 在顺序统计 piece treap 上组合 Text/List 增量——小编辑不会复制整个序列。Map、Counter、Tree 事件同样只保留生成最终事件所需的、事务相对意义上的键、值或节点。事务、导入日志与合并挂起事务增量维护累计操作长度与因果版本绝不在提交时通过重放所有挂起操作来恢复二者。导入日志记录每个导入变更的少量 undo 闭包以便失败回滚导入到空文档时跳过日志只有状态改变后失败才付出一次历史重放见 context/import-batch-atomicity.md。合并相邻变更只把新操作与键表条目追加到保留记录上操作长度、peer end、frontier 集合、操作索引、订阅者更新切片都增量更新因此一串可合并提交不会反复复制或缩减完整历史。同一事务内的连续 List/MovableList 插入还共享单一操作值数组。分配与紧凑性TextRunBuffer 与 compact()普通 Text/List 元素只在操作需要时才分配删除、值与移动元数据Text 样式元数据活在区间索引里。多标量 Text 插入把字符串与 UTF-16 边界一次性存入TextRunBuffer见loro-js/src/runtime/containers.ts内部保存整段#text与#utf16Ends边界数组。物理跨度只保留 buffer 区间因此切分 piece 不复制文本、也不物化 ID 列标量视图只在 API 主动索取时创建。单标量编辑仍走较小的对象路径因为 B4 轨迹全部由单标量插入构成为每次编辑构造临时打包跨度得不偿失。LoroText.compact()是显式、安全的重建入口containers.ts把高度碎片化的标量存储重建为相邻的 32 元素跨度且不改变 CRDT 历史重建函数会跳过含锚点的元素。文本迭代方面迭代回调返回false时直接在索引内停止toString、slice、iter消费连续的可见存储区间并一次读取整个 text-buffer 区间而不是为每个字符分配标量视图与 substring区间谓词也能在索引内提前停止因此Text.unmark不必先把被检查区间物化再应用 mark。可选的行索引按需构建的 sidecarText 行元数据是可选的。第一次lineCount、lineStart、lineAt或getLine查询会构建稀疏的 per-buffer 与 per-node 换行偏移及子树合计切分共享 buffer 偏移而不复制节点合计放在 sidecarSEQUENCE_LINE_BREAK_METRICSWeakMap见 sequence-index.ts未开启行 API 的文档不会撑大热路径 treap 节点形状后续编辑维护索引行/位置查找预期 O(log n)行分隔符为 LFgetLine对 CRLF 输入去掉前置 CR位置保持 UTF-16 偏移。源码中enableLineBreaks()会替换度量函数并recomputeSubtreeMetricssequence-index.tslineCount返回visibleLineBreaks 1空文本为一行。Fugue 增量 origin 索引与并发插入Text / List 的 Fugue 插入只在需要给并发/未来区间排序时才使用增量originLeft直子索引连续 ID 保持单子边隐式SequenceIndex查找下一个因果包含元素时可跳过整个未来 ID run普通本地编辑走较小的未索引路径MovableList 位置保持扫描MovableListState, useOriginIndex falseorigin 索引会把兄弟子树 其后一个并非其子孙的并发位置错误排序。兄弟子树是连续的因此两个直子之间的空隙属于较早的子最后一个子之后的区间还可能包含 origin 在originLeft左侧的并发元素Rust 的扫描在它们之前停止。该索引因此先检查区间最后一个元素是否从originLeft衍生否则二分搜索边界。衍生测试沿 origin-left 链接走但通过 per-peer 排序的显式非连续元素计数器跳过每个隐式 run成本为 O(显式链接数 · log n)等价于 Rust 的基于跨度的扫描而不是在长并发 run 中逐标量探测loro-dev/loro#1139。文档给出 2026 年 9 月 28 日的实测对比Node 22B4 轨迹作兄弟子树时二分搜索 7.3 ms 对 11.1 ms而深层显式链接链两个位置交替输入、64k 元素上 60.6 ms 对 15.5 ms每次 O(log n) 探测都要走链接链。现实轨迹更偏向二分搜索。热 origin 索引下512k 字符连续输入后导入一个并发字符耗时 0.28–0.31 msmain 分支为 0.29–0.30 ms但其会错排其他情形逐标量走法为 9.7–10.7 mstext-concurrent-insert-after-long-run从 64k 到 512k 字符保持在 0.18–0.30 ms。导入删除的解析与回退保障导入的 Text 删除按操作在其因果视图中的位置解析等价于 Rust 的 trackerLoroText._deleteTargets通过visibleIdRuns或缓存的因果视图成本 O(log n runs)。记录的start_id只是回退方案因为 Rust 的 WASM 构建对星形文本astral text可能记录偏离其 UTF-16 长度的start_id。本地删除跳过该查找。版本切换路径有多层安全网按 ID 去重SequenceElementSet打包的 Text 跨度每次查找返回新包装两个并发删除同一字符时曾导致重复删除失败回滚补齐completion抛错则重装快照状态并保持容器已水合checkout 抛错则恢复之前的版本与状态#transitionTo在 try 内准备diff在自身或回移抛错时以完整重建恢复当前状态转换前检查#canTransitionRecords检查每个序列仍持有被跨越插入操作命名的元素。它按容器收集 runs每容器调用一次containsIdRuns见 sequence-index.ts读取 ID 而不构建元素视图O(元素数 runs log runs)。此前每操作一次调用使 checkout 达到 O(操作数 × 元素数)8k 文本中 2k 分散插入在 main 上耗时 698 ms现在 4.2 mstext-scattered-edits-checkout1k→8k 从 13→698 ms 降到 1.0→4.2 ms2026-09-29 测。快照路径SSTable、懒状态与历史覆盖层编码层的流式化快照 SSTable 在能减小体积时选择可互操作的 LZ4 块。DeltaRLE 状态列以流式编解码而非分配百万项 BigInt 中间值LZ4 解码直接写入类型化存储。懒水合与覆盖层导入初始 latest-state 快照时会立即校验每个状态条目与 frontier 块但保留当前状态为自有的已编码 SSTable根容器在导入时水合被引用的后代容器按需、一个 SSTable 块一个块地解码未触碰块在快照导出时直接复制脏容器条目本地重写已编码历史是只读基底之后本地或导入的变更使用小型物化覆盖层overlay。由此本地编辑、完整 update 导出、latest 快照导出、当前读取、版本、frontiers、操作计数都不会构建完整历史 DAG。而历史查询、checkout、部分区间导出等需要任意依赖遍历的 API仍会在 staging 文档上一次性构建并校验全部历史索引后才安装。导入订阅者保留急切状态水合因为其导入事件必须描述每个变更容器。快照序列的补齐completionText/List/MovableList 从快照水合后无论 eager、lazy 还是 shallow root没有墓碑、删除索引也没有快照操作的样式/值/移动历史。LoroDoc.#snapshotSequences记录每个此类容器及其快照版本。补齐发生在两类时机导入前#prepareSnapshotImport补齐被导入记录与快照版本并发触碰的容器该记录的因果视图可能需要快照丢弃的墓碑loro-dev/loro#1163checkout / checkoutToLatest / diff / detached 快照导出#encodeLatestState前#prepareSnapshotTransition只看转换触碰的容器——懒编码的容器直接水合未触碰的懒容器仍持有其最新状态即当前版本状态转换跨越快照操作时从该容器自己的操作重建#completeSnapshotSequenceshallow 文档中从其 shallow root 条目出发。快照之后应用的操作照常索引Map/Tree/Counter 状态无需重建每容器记录索引每个历史修订构建一次连续续写的文本插入合并为一个跨度重放coalescedTextInsert见 document.ts。不相关容器从不重放懒 SSTable 保留因此快照导出复制每个未触碰条目、只重写被触碰者。删除转换仍被拒绝除非删除索引记录过该删除例如 detached 状态下导入的删除。补齐的可比性与 unreplayable 容器补齐会把 Text/List 的重放与快照状态可见 ID 加值比较。锚点模型loro-dev/loro#1137使带样式文本也可重放此前 loro.js 不计锚点Rust 创建的花式文本重放会不一致。现在重放仅在快照状态与其自身历史冲突时才不同loro.js 0.2 写的快照见 loro-js/README.md 的 Upgrading from 0.2或保留区间缺口描述的 shallow 快照见 context/loro-js-rust-differential.md。冲突时重放被丢弃容器变为unreplayable保留快照状态、只编码一次、永不给重放。触碰它的转换无操作运行后再单独移动#planSnapshotStates若已安装状态已含全部前向操作记为appliedText 按 ID 与样式版本切换O(delta)与无历史状态相同否则例如 detached 时导入的更新从快照状态加目标包含的后继操作重建#rebuildFromSnapshotStateO(容器大小 其操作数)。事件来自转换的记录或跨越样式操作时取整个容器值其区间来自位置。该模型保证了什么最新状态、导入与导出等于快照状态加后继操作按 loro.js 的应用方式与快照并发的后继操作在补齐后的容器上运行。更早的版本是近似的快照状态无法恢复其之前被删除的文本。Round-3 评审的随机 Rust 历史中旧版本与revertTo与 Rust 的分歧多于 main437 对 317 个检查版本、287 对 151 次 revert而 main 在 90 个种子中有 57 个在 checkout 往返后损坏最新状态、本 PR 无损坏。锚点模型消除这两种成本。main 上还有两个缺口detached 导入更新后活文档上的 shallow 导出可能改变其最新状态纯文本亦然loro-dev/loro#1136 修复纯文本情形中途抛错的 shallow 导出把活文档留在根或中间状态因为#encodeShallowSnapshot无恢复地重建。补齐成本第一次与快照并发的导入付出一次该容器历史的重放——这正是从 updates 加载的文档在加载时付出的工作。2026-09-30 实测每 peer 2000 次随机 Text 编辑快照后并发导入 675 msmain 上完整历史 update 导入后为 667 msmain 的快照路径只花 235 ms因为它跳过了墓碑loro-dev/loro#1163。8000 项 MovableList 加每 peer 8000 次 move/set 时快照路径 92 msupdate 导入后 60 msmain 为 35/96 ms其快照路径跳过历史并偏离 Rust。Text 并发导入仍超线性与 main 一致因为每操作都要算因果视图causalView。完整重建与 shallow 历史#rebuildFromHistory非增量回退路径shallow 导出、forkAt以同样方式重建 unreplayable 容器。它不再先检查快照水合的带样式 Text#checkSnapshotSequences已在 loro-dev/loro#1137 移除——那个额外重放本是为了补偿锚点偏移 Rust 位置如今锚点模型已计入。因此带样式与纯文本行为一致未被转换补齐的水合容器取自身历史重放0.2 快照即 Rust 的读数只有 shallow 导出的根状态用重放因为快照状态晚于根。forkAt仅在版本包含该状态版本的 fork 中保留快照状态更早的 fork 没有撤销该状态中后继操作所需的操作故保留自身历史重放并与自身操作保持一致。测试覆盖见 loro-js/tests/snapshot-checkout.test.ts随机 checkout、detach、importRust rich-text 历史rich-text-history.json对照纯导入文档外加 fork、Rust MovableList movesmovable-moves.json与标记字符被删除的 Rust 文本deleted-mark.json。关键实测数字文档记录首个 checkout导入 262,144 操作的单一 peer Text 快照后约 57 ms早期整文档重放约 148 msApple M5 Pro 5 轮交替中位数65,536 操作为 25 对 43 ms订阅者无可测增量早期 262k 为 192 ms。之后 checkout 稳定在 0.1–0.4 ms。含 32,768 个 child Map 的文档回退一个 Map 无需重放57–61 ms 对 152 ms峰值 RSS 同为 234 MiB此前 284 MiB。合并插入还让 B4 轨迹一次 update 导入快约 30%约 195 对 275 ms。计数合并B4 留下 182,315 个标量对象打包进 13,613 个 TS treap 节点更新导出合并后从 1,153,540 缩到 274,574 字节文本状态合并连续文本使快照从 309,780 缩到 206,553 字节。首个 checkout 成本从每操作一次检查698 ms 8k 分散插入降到每容器一次4.2 ms。shallow 历史首回浅文档中 32,768 child Map 的 Map/Tree 回退低于 1 ms1,024 Maps 起保持平坦loro-js 与 Rust 写入的快照皆然之后每次约 0.02–0.03 ms对应 Rust 每 Map checkout 索引种子的 loro-dev/loro#1120、#1124。事件与订阅者路径的性能数据64k Text 中一次订阅的单字符编辑约 0.35 ms此前事件生成复制整个 Text 时为 34.6 ms含 64k 订阅中插的事务总约 294 ms随操作数近似线性。有无订阅者下回退/恢复一个单变更尾部含单字符 mark、MovableList set/move 后缀、单变更diff在 1k–64k 保留变更间稳定在 0.05–0.69 ms四元素 MovableList 在并发 move 分支间直切低于 0.4 ms订阅路径低于 0.6 ms混合 move/insert/delete 的分支切换低于 0.5 ms。删除连续 64k Text ID 跨度约 0.5–0.8 ms含订阅路径最新孤立 run 的标量参考路径约 101 ms1k–64k 基本平坦因为删除覆盖单一物理 ID run。订阅的前向 checkout 组合全范围删除与 mark1k 字符 0.41 ms、8k 0.16 mswarm 后。历史 mark 位置直接转因果 ID runs事件生成前减去被移除 ID runs紧凑删除事件不再引发逐字符中间扫描。无订阅者时连续 64k 插入回退/恢复约 0.19/0.14 ms连续 64k 删除回退/重放约 0.4–3.2/0.13 ms只发删除的订阅转换低于 0.4 ms恢复 64k 值约 70–76 ms正比于事件负载。100 提交探测中不相关容器订阅者 1k/8k/64k 下每受影响容器 0.018/0.011/0.009 ms——派发不扫描无关监听器。detached 64k Text 上首块后停止iter约 0.25 ms完整toString约 1.5–1.6 ms双数组路径 2.2 ms中间 32k 切片约 0.42 msrange-array 路径 1.27 ms。历史序列视图在下降前把整棵物理 ID 子树计为完全包含/排除64k 冷视图排除全 run / 仅最终元素 / 三分之一后缀约 0.31 / 0.34 / 0.11 ms1k–8k 暖矩阵全排除约 0.01–0.06 ms。最近 8 个因果版本缓存已算视图1,000 次交替缓存查询在 64k 内低于 0.7 ms。1k–64k 保留变更下只导出/导入/checkout 最后变更 warm 后低于 0.7 ms单操作跨度导出低于 0.3 ms。样式与锚点的代价明细对一段连续 64k Text 应用 mark孤立重复探测约 0.37–0.74 ms全范围 mark 回退/恢复约 0.11/0.10 ms订阅恢复约 0.41 ms——随 ID/style runs 与输出格式区间扩展而非 64k 字符。锚点在序列中后2026-09-28Node 22loaded 机器 best of 764k 全范围 mark 0.07–0.08 ms其回退/恢复 0.06–0.07 ms订阅恢复 0.06 ms粗体范围内输入 1,000 字符 3.1–3.3 ms此前 1.7–2.1 ms——每次插入都要与两个物理邻居的样式成员关系求交。反复 mark 同一区间会嵌套锚点第 n 次 mark 的区间包含前 n-1 个起始锚点为独立 ID runs因此应用与跨版本移动为 O(n)与 Rust 一致其StyleRangeMap在该处每锚点一段。text-repeated-mark-tail-{retreat,restore}因此随规模增长1k/2k/4k/8k 下 0.5/1.1/2.2/6.9 ms此前 0.16–0.29 msRust WASM 回退 1k/4k/16k 此类 mark 需 7.1/19/362 ms构建 16k 历史 loro.js 402 s、Rust 542 s。其余bench:complexity项 1k–8k 均平坦。零宽计数器是 treap 节点新增的四个字段8,000 订阅中插 15.4–15.8 ms 对 14.3–14.4 mstext-subscribed-batch、history-commit、history-update-batch-import在 8k 时慢 12–20%2026-09-29Node 22。无条目因它们随规模增长。把零宽计数移入仅锚点序列分配的 sidecar像换行合计那样可消除该成本。从快照读 Rust 写的带样式 Text16k 字符、200 marks、2k 后继编辑并 checkout 中间版本首次 24.7–25.0 ms、回最新 4.1–4.3 ms、fork 11.8–12.2 msmain 为 35.9–37.2 / 3.1–3.3 / 29.8–30.5 ms 但文本错误它把文本标为 unreplayable 并切换其快照状态。评审loro-dev/loro#1137Node 26load 25–40复测64k 粗体范围内输入 1,000 字符 2.9–4.4 msmain 1.9 ms8k 重复 mark 尾回退/恢复 8.0–8.1 / 11.6–13.2 msmain 0.4–0.6 ms。评审修复后复测Node 221k/2k/4k/8k 回退 0.51–0.71 / 1.18–1.27 / 2.25–2.80 / 6.11–8.25 ms、恢复 0.47–0.53 / 1.16–1.35 / 2.08–2.57 / 5.89–7.75 msmain 0.08–0.43 ms64k 全范围 mark 应用 0.11–0.17 ms、回退 0.22–0.35 ms、恢复 0.11–0.14 ms。基准测试命令与典型结果所有基准脚本位于 loro-js/benchmarks以node --expose-gc运行见 loro-js/package.json 的 scripts。脚本会完全预热所请求的最大前缀并在强制 GC 前释放前一样本。完整 B4 轨迹pnpm --dir loro-js bench:b4 -- 259778 7在 Apple M5 Pro Node 26.4.0 上完整 259,778 动作 B4 轨迹三样本中位数 353.5 ms样本 351.8–354.9 ms最终 104,852 个 UTF-16 code units进程报告 107.1 MB 已用 JS heap 与 322.1 MB RSS。原数组实现估计需 30–50 分钟20k 至完整轨迹的前缀测量近似线性扩展。同机 Rust Criterion 基准点估计 47.711 ms即 TypeScript 绝对时间慢约 7.4 倍。同次运行还测得快照导出 162.4 ms、更新导出 129.3 ms、快照导入 161.5 ms、更新导入 328.1 ms。文本存储 / 读取 / 行查找 / 显式压缩pnpm --dir loro-js bench:text-buffer -- 131072 50000 7同机 Node 22.23.1 对origin/main的 A/B2026-07-22 文本基准批量 131,072 标量插入 21.8 ms 对 33.2 mstoString0.40 对 6.34 ms中间一半slice0.22 对 3.67 msiter2.00 对 8.05 ms批量文档保留堆从 22.9 MB 降到 10.7 MB。独立交替标量探测 31.0 对 30.8 ms0.8% 差异噪声内。可选行索引构建约 16.0 ms、保留约 1.46 MB1,000 次中间行查找约 0.71 ms 对 103.8 ms重复扁平字符串扫描。显式压缩 50,000 个最大碎片化的中间插入约 20.6 ms物理节点从 50,000 减到 1,563。六对交替运行顺序的全新进程 B4origin/main234.4 ms带文本改动 234.8 ms0.2% 差异噪声内。主 ESM bundle 从 461.87 kB / 88.41 kB gzip 增至 485.79 kB / 92.11 kB gzip。复杂度缩放矩阵pnpm --dir loro-js bench:complexity -- 1000,2000,4000,8000覆盖点/排名查找、穿越删除空隙的游标查找、缓存因果视图、map/root/tree 路径查找、不相关容器订阅者派发、单变更序列与样式版本切换、单变更历史导入/导出/checkout/diff、并发 MovableList 分支切换、1,000 次容器 ID 查找——均验证不随不相关保留状态增长。输出型 APItoJSON、toString、getAllChanges、快照、全版本转换保持与返回/编码数据成正比。真实快照内存工作流pnpm --dir loro-js bench:snapshot-memory -- /path/to/document.snapshot对 11,387,982 字节测试文档423,797 操作、115,147 容器Node 26.4.0 报告加载输入后 70.92 MiB RSS、快照导出后进程峰值 160.70 MiB——增量峰值 89.78 MiB已用 JS heap 峰值 8.58 MiB。快照导入约 0.90 s、本地提交约 1.9 ms、完整更新导出约 6.6 ms、快照导出约 57 msApple M5 Pro。懒状态与历史覆盖层整合前同一工作流导入后立即保留约 703 MiB heap、首次本地编辑后超 860 MiB、快照导出期间达约 1.66 GB RSS。普通完全物化快照路径的 A/B 保持中性三轮 warmup 后两轮 15 样本 B4 快照导出父版本中位数 110.5/107.0 ms懒快照 107.7/107.7 ms两版本都产出相同的 309,780 字节快照。crdt-benchmarks 端到端对比zxch3n/crdt-benchmarks适配器提供与已发布 Loro WASM 适配器的端到端对比本地 loro.js 构建B4 从修复前的 180 秒移除首个拷贝路径后 141.5 秒降到增量维护合并变更长度后的 2.846 秒WASM 适配器为 4.733 秒。B3.5 288 对 303 msB3.3 快照 240,032 字节WASM 约 242 KB此前未压缩 TS 快照 7.95 MB。60k 项 List 更新 231,840 字节、120k 字符 Text 更新 120,095 字节均与 WASM 输出大小一致。C1.1 仍需 6.988 对 1.728 秒其余量差距在剩余常数因子与内存差距一节说明而非视为渐进回归。MovableList 专项pnpm --dir loro-js bench:movable-list度量并发导入的 tracker 版本增量解析见版本切换一节。剩余常数因子与内存差距文档结论已审计的公开路径相对 Rust 运行时没有已知的时间复杂度差距。前向、回退与可比版本 checkout 只应用版本增量连续插入/删除/样式转换使用 ID runs 与惰性子树可见性紧凑的订阅转换不展开这些 runs返回/编码/解码/发出 n 个值的操作保持 O(n)与 Rust 一致。剩余差异是表示方式与 JavaScript 常数因子标量快路径的对象保留多标量 Text 操作共享字符串/ID 跨度但 B4 把 182,315 个标量作为独立操作插入其标量快路径在显式compact()前仍每标量保留一个对象。有界物理节点把 B4 的 treap 节点数砍掉约 13.4 倍内联位置还免去每标量一个位置对象与 WeakMap 条目。直接标量→打包跨度突变路径被实测后否决Fugue 排序会立刻读 ID 与 origin临时打包视图拖慢 B4 多于节省。收窄剩余 Rust 内存差距需要 Fugue 中的原始列访问或调用方选定静默点做压缩而不是无条件打包每次编辑。订阅恢复正比于输出订阅者对大型插入/删除的恢复必须把恢复的文本/列表值放进事件故正比于发出的输出无订阅者时隐藏与显示转换走可逆懒可见性层正比于受影响的 ID runs。快照水合容器的首次补齐latest 快照水合的状态没有墓碑或 MovableList 候选历史。首次以并发方式触碰该容器、或指名其缺失的 MovableList 元素的导入只从自身历史重建该容器#prepareSnapshotImport首次触碰水合 MovableList 的版本转换同理。后续导入与转换恢复增量。MovableList move/set 的导入校验每操作 O(log changes)目标元素在水合状态内时保持延迟快照历史延迟见 context/loro-js-movable-list.md 的 Validation。C1.1 的百万操作并发文本轨迹本地编辑阶段约为 WASM 适配器的 4 倍解析 6.5 MB 快照 3.62 秒对 43 ms。流式 DeltaRLE、类型化 LZ4 解码与延迟历史集成已消除已知超线性与临时分配失败收窄剩余差距需要更紧凑的解码操作/frontier 表示而非又一次公开 API 复杂度改动。旧容器父边绑定没有 parent-edge 绑定的旧或手工构造容器会扫描 parent 一次并缓存恢复的绑定常规容器路径查找直接用索引绑定。最后文档提醒改动这些结构时保持 loro-js/tests/indexes.test.ts 的随机索引不变量覆盖以及 loro-js/tests/rust-interop.test.ts 的 Rust/TypeScript fixture 覆盖随机化 Rust 差分套件loro-js/tests/differential见 context/loro-js-movable-list.md对照 Rust 实现的 WASM 构建检查收敛、事件与编码互换。另外当元素的删除标志、tree 父/位置或 map 可见性变化时必须经由其所属索引的辅助方法变更——直接突变会让子树或有序键缓存失效。小结loro.js 的性能架构可以概括为一句话用有界物理跨度、惰性可见性与增量区间索引把一切按字符/按整文档的工作降为按 run / 按子树 / 按受影响容器。无论是顺序统计 treap 的 32 元素跨度与内联位置、删除与样式区间的分段索引、可选行索引与零宽锚点 sidecar、Fugue 增量 origin 索引还是快照懒水合 历史覆盖层 单容器补齐其目标始终一致——继承 Rust 的渐进复杂度让规模增长时的性能曲线与原生实现同形。若需进一步深挖 MovableList 的 Fugue 模型、富文本锚点语义或导入原子性可继续阅读仓库中 context/loro-js-movable-list.md、context/loro-js-richtext-anchors.md、context/import-batch-atomicity.md 与 context/loro-js-rust-differential.md 等配套文档。赞分享后端【免费下载链接】loroMake your JSON data collaborative and version-controlled with CRDTs项目地址https://gitcode.com/gh_mirrors/lo/loro点击查看免费下载相关推荐RSuite Button 组件入门从默认按钮创建到源码级解析RSuite Button 组件入门从默认按钮创建到源码级解析 RSuite 的 Button 是组件库中最基础的交互元素用于触发用户操作。本文以官方文档中后端RTranslator 离线翻译断网也能实时互译RTranslator 离线翻译断网也能实时互译 RTranslator 离线翻译是一款跑在 Android 手机本地的实时翻译 App。翻译用 Meta 的人工智能AI 应用本地部署语音NLP移动开发Hello 算法时间复杂度实战用 PythonTutor 逐行可视化 O(1) 到 O(n!) 七大类渐近复杂度Hello 算法时间复杂度实战用 PythonTutor 逐行可视化 O 1 到 O n! 七大类渐近复杂度 导读 本文以《Hello 算法》日语仓库中的 P教程文档示例工程教育上一篇Gumbo纯 C99 实现的 HTML5 解析库——安装、核心 API 与解析树实战指南下一篇OpenResume错误恢复机制用户操作回滚与状态重置创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
