RGA这个数据结构算法层面讲再多最后还是要回到一个现实问题跑通demo很容易扛住真实业务很难。我在前面几篇连载里把RGAReplicated Growable Array的基本操作、副本合并规则、一致性协议都过了一遍陆续有读者留言问性能到底怎么样多核机器上能不能并行编辑100万字的文档内存会不会爆炸这篇正好把性能、多核与内存三个话题放到一起聊拿我自己在工程里实际做的改造和压测数据来说话不整理论空谈。这篇的内容默认你已经知道RGA是啥如果不清楚建议先翻一下前几篇。大概300行就能实现的朴素RGA在1万字符规模下体验还不错可一旦把文档体积、协作者数量、操作频率拉上去立刻会撞上三个大坑链式扫描定位慢、墓碑无脑膨胀、对象分配爆炸。这三个坑分别对应标题里的性能、多核与内存下面一个一个拆开讲。1. RGA节点模型性能瓶颈藏在哪一头1.1 一次插入操作背后发生了什么先把朴素RGA的结构摆出来。每个元素一个节点节点里至少有三样东西内容值、一个全局唯一ID、一个指向下一个节点的引用。ID由“副本ID 单调递增序号”组成。插入的时候不是简单地把节点链到目标位置而是要在有序链表上进行ID排序。拿最常见的插入策略举例伪代码大致长这样void insert(int pos, String value) { Node prev locate(pos); // 跳过墓碑找可见位置 Node cur prev.next; Id newId new Id(localReplicaId, nextSeq()); while (cur ! null cur.id newId) { prev cur; cur cur.next; } prev.next new Node(value, newId, cur); }这段代码看着简单每一步都在烧性能。locate要无脑跳一遍链表还要过滤掉已删除的墓碑节点后面的while循环要和插入位置后方的节点逐一比较ID直到遇到一个ID比新节点小的节点才停下。也就是说一次插入在最坏情况下要把插入位置后面整段链都扫一遍这还没算上新节点的分配和随之而来的GC压力。我最初写这个版本时觉得问题不大结果拿真实编辑轨迹一测100万操作量的文档单次插入的p99直接飙到50ms以上。原因一目了然操作越多链表越长而新增节点又普遍往链尾附近堆插入一个新字符经常要扫后半段。1.2 复杂度推导为什么顺序扫描和墓碑累积是两大瓶颈朴素RGA的复杂度可以用两个公式说清楚。设可见节点数为V墓碑节点数为T链表总长度N V T。于是一次常规插入的定位复杂度是O(N)ID比较导致的扫描复杂度最坏也是O(N)一次读取第k个可见字符在最坏情况下要跳过连续k个墓碑复杂度O(T k)读取整个文档就是O(N)。问题在于T不是恒定的。协同编辑场景里删除操作产生的墓碑永远不会自动消失因为RGA需要靠墓碑来维持并发操作之间的排序关系。你越删T越大文档表面只有1万可见字符链表内部可能躺着3万甚至10万个墓碑节点。我在实际项目里见过一个极端案例一篇2万字的文章经过大量增删改后内部链表总节点数达到45万墓碑占比96%。这个放大效应还会波及其他模块。后面聊多核时会提到合并操作合并本质上也是扫描和重放墓碑越多合并一次消耗的时间越长后台合并线程的积压也就越快。1.3 三个瓶颈的优先级判断拿到一个慢的RGA实现先别急着改内存布局先判断当前到底是哪个瓶颈在主导。我一般按这个次序排查。第一个是定位和扫描。如果文档总节点数在100万以下性能大头几乎都在这。第二个是墓碑膨胀。如果编辑频繁、删除比例高墓碑放大效应很快会压过链式扫描。第三个是节点对象分配。这个在JVM和Go这类带GC的语言里尤其明显百万级节点对象的分配、引用、回收会拖垮整体吞吐。判断的办法很简单跑一个基准分别测“纯追加文档”和“大量增删文档”的插入延迟看差异。如果后者比前者慢了几倍先处理墓碑如果两者都慢先处理链式扫描如果两者都快但GC日志很难看再回头看对象模型。这三件事有先后依赖别跳着做否则容易白忙活。2. 多核并行一致性边界的工程设计2.1 CRDT为什么天然适合无锁合并多核环境下最容易踩的坑是“给整个数据结构加一把大锁锁住就完事”。加锁确实能保证一致性但多核的优势也被锁没了。RGA这类CRDT有一个稀缺特性副本合并操作是交换律、结合律、幂等的。你在A核上合并一段远端操作和你在B核上合并同一段操作只要操作集合相同最终状态一定一致与顺序无关。这个性质意味着合并操作在理论上可以无锁。不需要在合并过程中锁住整个数据结构去协调临界区因为任何一次合并都是“朝最终相同状态前进一步”即使两个线程同时合并不同副本的操作结果也一样。我说的无锁并不是说完全不用同步。数据结构的内部状态依然要保证跨线程的可见性该用的内存屏障、原子引用的发布机制还得用但不需要用互斥锁去保卫一个跨线程的复杂算法。这是一个本质差别锁保护的是“不许同时做”CRDT强调的是“同时做也没关系”。2.2 多线程提交的边界划分实际工程里我不会让所有线程都直接写同一个RGA。看着资源利用率高但ID分配、链表更新、缓存失效都会成为新瓶颈。我建议做三线程模型本地编辑线程处理用户操作更新主副本入站合并线程消费远端副本发来的操作日志合并进主副本快照线程定期生成只读快照供渲染端使用。编辑线程和入站合并线程之间用无锁队列传递操作批次快照线程读取的是由内存屏障保护的发布引用。这个模型最大的好处是隔离了速度差异本地编辑永远是低延迟通道远端合并允许稍高的延迟操作在无锁队列里排一会儿队编辑端完全感知不到用户只管自己打字。我在工程实践里还加了一条约束入站合并线程的优先级要低于编辑线程。这样即使远端操作大量涌入也不会抢走本地的编辑能力。掉几个远端操作几十毫秒没问题但用户键盘敲下去卡了几百毫秒那就是体验事故。2.3 批量提交把ID分配和共识压力降下来多核下还有一个容易忽视的点ID分配的原子操作竞争。每个新ID都要从副本的单调计数器里拿一个递增序号这个计数器通常是一个AtomicLong。高并发编辑下所有线程都去争抢这个原子变量CAS竞争会非常激烈吞吐量上不去。解决方法是批量预分配。本地编辑线程每次申请一批连续ID比如64个这一批内部的插入操作直接用“起始序号 偏移量”生成ID整个批次只需要一次原子操作。这个批次天然成为合并单元远端合并时可以对整个批次重放而不是逐条处理函数调用开销和索引定位开销都能摊薄。我实测过一个4写入线程的小型编辑器场景逐条分配AtomicLong的吞吐约每秒8万次插入改成批量预分配后每秒42万次翻了5倍多。合并线程也从每秒合并10万个操作提升到30万个因为操作日志的解析和按批次插入的比例大幅减少了。3. 内存问题从对象泥潭到连续布局3.1 JVM对象模型视角下的一字符一对象有多贵如果RGA节点是Java对象每个节点至少有这些固定开销对象头开启压缩指针后12字节未开启16字节、引用4字节、ID里的副本ID和序号至少8字节、内容引用4字节。就算节点里只存一个char加上堆对齐填充单个节点实际占用通常也在48字节左右。100万字符的文档光节点对象就是48MB上下这还不算墓碑、操作日志、ArrayList包装和GC的复制存活开销。如果编辑历史里还存着每次操作的备份内存轻松上百MB。在协同编辑器里这样的内存占用不可接受移动端更是直接崩。我的结论是能不用对象表达的位置单元尽量不用对象表达。把RGA的节点从“一个字符一个对象”改成“一块连续内存存多个字符”是性价比最高的内存改法。3.2 分块RGA把链式指针改成连续块分块RGA的核心思路叶子节点不再是一个字符而是一个固定容量的字符数组块块里连续存放若干可见字符块与块之间仍然用指针或索引连接。插入位置落在某个块内时如果块没满直接在块内移动元素块满了就分裂成两个块。块大小我建议取64到128字符。太小的话块内复制开销和块间指针数量都不划算太大会让分裂惩罚变大插入性能会抖动。用128字符的块100万字符的文档只有7800多个块而不是100万个节点内存省了至少一个数量级。这里要注意块内移动元素虽然也是O(块长)但块长是常数128单次插入的最坏复制开销是恒定的。真实负载里操作位置高度集中块内元素移动即使连续触发也不会导致复杂度退化。另外块间指针依然存在所以定位时仍需跨块移动但这时的跨块数量已经从百万级缩到千级。3.3 墓碑的代价与惰性压缩墓碑在内存上比可见节点更可恨因为它既不显示还占着块。我在分块版本里的处理方式是“可见率阈值触发压缩”当某个块内墓碑比例超过60%时把块里的可见字符重写到一个新块并替换掉原块。但墓碑压缩不能简单地把墓碑删掉否则并发下来的远端操作可能把ID区间撕开。工程做法是把被压缩区间里的墓碑信息编码成一条重写元数据记录哪些ID被删除、删除发生在什么顺序再把可见字符复制到新块。这样压缩后合并逻辑拿到的依然是相同的删除顺序信息不再需要扫描物理墓碑但CRDT的收敛语义不会受影响。压缩阈值也有讲究。60%触发的话压缩频率适中长期占据的内存比例能控制在30%以内如果把阈值调到90%内存能再省一点但压缩动作会频繁爆发CPU占用不稳。我建议默认60%同时提供一个可配置参数让重度编辑场景往里调。3.4 堆外内存与GC互动聊到JVM层面的内存堆外内存几乎是绕不开的话题。对于百万级节点的RGA堆内对象不仅占空间大还会让Minor GC复制存活对象耗时变长。把块的字符数据放到堆外比如DirectByteBufferGC完全不碰这些数据暂停时间会显著下降。但堆外不是银弹。堆外的分配和释放要自己管一旦泄漏就非常难排查数据在堆外和堆内之间搬运时还有拷贝开销。我的建议是只把最核心、生命周期最长的大块字符数据放堆外块对象本身的管理结构留在堆内。这样既降低了GC压力又把内存泄漏风险控制在一个明确的小范围内排查时思路也比较清楚。4. 基准测试与实测数据4.1 测试怎么设计才不算自嗨性能测试最大的坑是只用均匀随机操作测一遍就下结论这测不出真实编辑负载的特征。真实协同编辑里操作分布极度不均匀大部分插入集中在文档尾部删除操作相对少但会把墓碑堆成连续大段偶尔还有粘贴几千字的批量插入。我自己的测试是这样设计的先用概率模型生成一条模拟编辑轨迹70%插入、20%删除、10%合并插入位置用Zipf分布模拟“热点集中在光标附近”然后分别用朴素链式RGA、分块RGA、分块加墓碑压缩RGA三个版本回放同一条轨迹记录p50、p95、p99延迟每秒操作数堆内存占用和GC暂停。顺便说一句延迟分位数一定要画出来看别只盯平均值。平均值很容易被短暂峰值掩盖而协同编辑这种交互场景p99才是用户能感知的卡顿边界。4.2 四组对比实验数据我把上面三个版本加上“分块 批量子分配 堆外数据”的最优配置凑成四组。测试文档10万字符回放约50万次操作结果如下。版本平均插入耗时p99插入耗时峰值堆内存Full GC次数朴素链式1.2ms5.8ms214MB18分块12845us210us46MB6分块 墓碑压缩38us165us31MB3分块 批量 堆外29us118us24MB1这组数据我看过很多遍印象最深的是墓碑压缩的收益比预想的大。原本以为它只降内存没想到p99延迟也有明显提升原因是压缩减少了合并和扫描时跨过的墓碑节点数量顺带把定位和合并的耗时一起拉下来了。4.3 从数据看优化优先级回到最初的问题一个慢RGA先改什么从这组数据看改成连续块存储是收益天花板最高的一步内存直降75%左右延迟直降一个数量级。墓碑压缩是在此基础上的二次提效把长期内存控制在较低水位。批量分配和堆外数据属于锦上添花主要解决极端规模和GC压力对于10万字符级别的文档不做完全可用。多核并行那组测试也验证了批量提交的价值4线程并发编辑下ID从逐条分配改成64个一批吞吐从8万次/秒提升到42万次/秒一致性完全没受影响因为操作日志的批处理和重放路径是幂等的。5. 内存膨胀与泄漏排查专项5.1 谁在偷偷占着内存优化完内存布局内存依然可能悄悄膨胀尤其是多线程合并的代码里。我遇到过三个典型的隐性占用源。第一个是合并信道里的操作日志积压。远端副本每秒发来大量操作合并线程消费速度跟不上无锁队列里积压的操作对象会持续增长。这不是RGA本身的问题是消息队列的背压没做好。第二个是快照引用。快照线程把主副本当前状态发布给渲染端后如果渲染端持有引用不释放整棵块树都会留在堆里。并发场景下几个渲染端各持一版快照内存在视觉上就会像断崖一样下跌。第三个是墓碑的统计偏差。压缩阈值是“块内墓碑比例”但墓碑聚集在少数几个块里时阈值触发不了整体墓碑占比还是很高。这种局部聚集的压缩盲区需要靠全局统计兜底。5.2 排查工具链JVM环境我会用NMTNative Memory Tracking先看堆外内存启动参数加-XX:NativeMemoryTrackingdetail后面用jcmd工具查询。堆内部分用Eclipse MAT看堆转储里到底是哪些类占了空间重点看RGA节点和块数组的大小。非JVM语言的话valgrind或者heaptrack都能直接看到每个分配点的调用栈。还有一个实用技巧给RGA实现一个自检方法定期统计“总块数、可见字符、墓碑字符、合并队列长度”然后把指标打点上报。我后来就靠这个自检方法抓到了一例快照泄漏——指标曲线里“总块数”稳步上升而可见字符数早已稳定说明确实是快照引用链上挂了东西。5.3 监控指标设计最后聊一下我上线后一直在看的几个指标可见节点数、墓碑节点数、墓碑占比、每秒提交操作数、合并队列深度、GC暂停时间。墓碑占比和GC暂停时间高度相关合并队列深度和吞吐高度相关。不用把所有指标都做成看板我从经验里挑最重要的两个合并队列深度的分位数曲线和墓碑占比随时间的变化曲线。前者直接反映多核合并通道的健康度后者直接反映内存膨胀风险。只要这两个指标稳定RGA这块基本就不会出大乱子。最后补一句我自己的体会。性能、多核和内存这三件事单独拎出来每一件都有大堆文章可写组合到一起才是真正考验工程判断力的时候。我前几版踩过不少弯路有些方向看着高大上比如用堆外内存替换所有对象实际测下来性价比极低。踩过几次坑之后我的习惯变成任何优化都要先有测量数据支撑再动手改代码。这篇里的测试方法和指标你完全可以照着搭一套跑你自己的负载数据这会比直接抄我的任何配置都更靠谱。