04 · 瀑布图背后异步操作链是怎么重建的两个算法讲透阅读时长约 35 分钟前置知识第 3 篇配对成操作。本篇解决父子嵌套关系怎么找出来。本篇目标把 Chrome DevTools Performance 那种瀑布图的地基代码一行行讲透。你会学到两个计算机经典算法的真实应用最近包含扫描和扫描线sweep-line依赖发现。目录我们要解决的问题操作谁包含谁概念什么叫时间包含打个比方建树最近包含扫描重点为什么只返回根节点找依赖扫描线 顺序相邻瓶颈检测P95 一刀切数据流向全景总结 下篇预告1. 我们要解决的问题操作谁包含谁配对之后我们有一堆操作。每个操作有开始时间startTime和结束时间endTime。假设有 4 个操作单位 msA: 请求进入0 ~ 300 大到能装下下面三个 B: MySQL 查询10 ~ 90 C: Redis 读取100 ~ 200 D: Kafka 发送210 ~ 290一个关键事实B、C、D 全都发生在 A 的时间范围内。于是很自然地你会想A 是一个父操作B/C/D 是 A 的子操作。这就是瀑布图的嵌套语义┌─ A 请求 (0–300) ────────────────────────────┐ │ ├─ B 查询 (10–90) │ │ ├─ C 读取 (100–200) │ │ └─ D 发送 (210–290) │ └────────────────────────────────────────────┘问题来了计算机怎么判断A 包含了 B答案看时间区间是否包含。A 的开始 ≤ B 的开始且 A 的结束 ≥ B 的结束 → A 包含 B。2. 概念什么叫时间包含打个比方打个比方想象一条高速公路录像每个操作是一辆车在高速上行驶的一段路程A 车从 0 公里开到 300 公里全程B 车在 10 到 90 公里这段行驶C 车在 100 到 200 公里段行驶很明显B、C、D 的行驶区间都落在 A 的区间之内。A 是包住它们的更长的车程。“时间包含就是车程包含”。判断规则极其简单如果 X 的开始 ≤ Y 的开始且 X 的结束 ≥ Y 的结束那么 X 包含 Y。写成代码if(startXstartYendXendY){// X 是 Y 的潜在父节点}这个朴素的规则是全篇的灵魂。堆砌在它上面的是怎么高效找到最近的那个父节点。3. 建树最近包含扫描重点3.1 代码在哪里全在src/shared/engine/trace-aggregator.ts的buildWaterfall函数里。我们来拆。3.2 第一步把所有操作按开始时间排序spans.sort((a,b)a.startTime-b.startTime);打个比方录像本来录的是乱序的片段我们先按这辆车从几公里出发排好队。这样每辆车后面跟着的必然是在它之后出发的车。3.3 第二步对每个操作往回找最近包含它的人这是核心算法。代码for(leti0;ispans.length;i){// 从 i 的前一个开始往回一个个看for(letji-1;j0;j--){// 谁能在时间上完全包住我if(spans[j].startTimespans[i].startTimespans[j].endTimespans[i].endTime){spans[i].parentIdspans[j].id;// 认父spans[j].children.push(spans[i]);// 父也登记我这个儿子spans[i].depthspans[j].depth1;// 我的深度 父亲深度 1break;// 找到最近的父就停}}}3.4 关键问题为什么是往回扫而不是从最开头扫这是整个算法设计的精妙之处。打个比方想象你在一个电影院找谁坐在我前面直接挡着我。你不会去问第一排的人太远了你会看紧挨着你的前排——那个人最可能挡到你。在时间线上“最可能的父节点是开始时间比我早、结束时比我晚、并且离我最近的那个”。所以算法从 i-1 开始往回扫第一次命中找到能包住我的就立刻break。这样找到的是最近的父节点正确性关键找到就停效率关键省掉大量无效比较为什么必须是最近的而不是任意一个能包住的打个比方你站在一排套娃最外层的 A 里面又站在中间层 B 里面。往回扫时你第一个遇到的能包住你的应该是内部的 B因为 B 离你近而不是外层的 A。最近包含保证了你直接挂在正确的中间层下面而不是跳过一层直接挂到最外层。3.5 手动跑一遍走数据假设排序后的操作时间 msspans[0]: A 0–300 spans[1]: B 10–90 spans[2]: C 100–200 spans[3]: D 210–290i1 (B)往回看 j0 (A)。A 开始 0 ≤ 10A 结束 300 ≥ 90 → 包含B 认 A 为父。break。i2 ©往回看 j1 (B)。B 开始 10 ≤ 100但 B 结束 90 ≥ 200否B 不包含 C。继续 j0 (A)。A 开始 0≤100A 结束 300≥200 → 包含C 认 A 为父。i3 (D)同理跳过 B、C认 A 为父。最终结构A (depth 0) ├─ B (depth 1) ├─ C (depth 1) └─ D (depth 1)看到关键了C 想认 B 当爸但 B 结束得太早包不住 C于是继续往上找到 A。这一个往回扫 break就把嵌套关系精确还原了。3.6 复杂度分析进阶最坏情况是 O(n²)——如果所有操作互相都包含极端嵌套每个都要往回扫很多个。但实际操作往往层数浅break会早停实际性能可接受。在 40 万事件的大文件场景下这件事已经被挪进 Worker 处理第 5 篇主线程不受影响。4. 为什么只返回根节点4.1 代码returnspans.filter(s!s.parentId);4.2 意思把没有父节点的操作根节点返回子节点已经嵌套在它们的children数组里了。打个比方你整理一个文件夹树只想显示最顶层的文件夹因为子文件夹已经装在了顶层文件夹里面。为什么不返回全部因为 UI 渲染时用递归遍历遇到一个根就能顺着 children 找到它所有的子孙。返回根就够画出整棵树了还避免重复渲染。4.3 UI 怎么画渲染函数递归每个节点functionrenderSpans(roots,depth){returnroots.flatMap(s[div style{{marginLeft:depth*16,width:s.endTime-s.startTime}}{s.label}/div,...renderSpans(s.children,depth1),]);}marginLeft: depth * 16→缩进随深度增加每层 16pxwidth: endTime - startTime→横条宽度 耗时递归 children depth1 → 画子节点这样一来深度嵌套层级和宽度耗时两个维度就出来了——横着是时间竖着/缩进是层级这就是瀑布图。5. 找依赖扫描线 顺序相邻buildWaterfall给出的是结构而依赖关系比如查询 A 在等连接建立由buildDependencies用扫描线算法补足。它做两件事。5.1 第一遍父–子依赖栈式扫描constactive[];// 一个栈装着当前还开着的操作for(constopofsorted){constopEndop.end?.timestamp??Infinity;// 弹出所有已经结束的容器它们结束时间早于当前操作开始while(active.length0active[active.length-1].endTimeop.start.timestamp){active.pop();}// 栈顶就是当前操作的直接父if(active.length0){links.push({source:active[active.length-1].op.operationId,target:op.operationId,type:parent-child,});}active.push({op,endTime:opEnd});}5.2 打个比方扫描线 图书馆的书被借出/归还的令牌把操作想象成你往一个柱子上套橡皮圈每个操作是一个橡皮圈横跨它的[开始, 结束]。扫描线算法的做法从时间 0 到无穷一个滚动指针从左到右扫。用一个栈记录当前还挂在柱子上的橡皮圈一个新操作要开始先看看当前栈顶最新挂上的是不是还开着。如果栈顶已经关了结束时间 当前开始就把它弹掉它不再包含任何后续操作。此时栈顶永远是最内层、还开着的操作正好就是当前操作的父。这就是扫描线维护一个活动中的祖先栈一趟扫描 O(n) 找出所有父子依赖。5.3 第二遍顺序相邻前后紧挨就是依赖有时候两个操作互不包含不是父子但几乎无缝衔接间隔 0-5ms。这暗示前者是后者的前置步骤。for(leti1;isorted.length;i){constprevEndsorted[i-1].end?.timestamp??sorted[i-1].start.timestamp;constgapsorted[i].start.timestamp-prevEnd;if(gap0gap5){// 间隙小于等于 5mslinks.push({source:sorted[i-1].operationId,target:sorted[i].operationId,type:sequential,// 顺序依赖});}}关键只判断排序后的相邻对——如果两个操作隔着一堆其他操作就不算顺序依赖。这让检测保持局部、避免误报。5.4 三种依赖总结类型判定打个比方parent-child时间上包含父文件夹装子文件夹sequential相邻 间隙 ≤5ms前一步做完下一步立刻开始async由 asyncStart/asyncEnd 配对推导等待外部 I/O6. 瓶颈检测P95 一刀切6.1 代码exportfunctionfindBottlenecks(spans:TraceSpan[],thresholdPercentile95):TraceSpan[]{constdurationsspans.map(ss.duration).sort((a,b)a-b);constthresholddurations.length?durations[Math.ceil((thresholdPercentile/100)*durations.length)-1]:0;returnspans.filter(ss.durationthresholds.duration0);}6.2 它在干什么把所有操作耗时排序算出 P95 值作为阈值。把达到或超过这个阈值的操作标为瓶颈。6.3 为什么自己跟自己比阈值不依赖任何外部基准不是什么必须 500ms 才合格而是基于当前数据自己算出 P95。打个比方一场赛跑不规定必须 10 秒内算合格而是取前 5% 完成的人当跑得快的人。这样无论赛道多长多短数据集多快多慢总能挑出相对最慢的那几个。好处任何数据集都能用不用预设阈值坏处它给的是相对慢而不是绝对超标。两者各有用途NodeVerdict 在这里选了相对快照。7. 数据流向全景把第 1-4 篇串起来一条完整的可视化数据流渲染错误:Mermaid 渲染失败: Parse error on line 2: ...R A[TracingEvent[]] -- B[第3篇流水线8. 总结 下篇预告8.1 本篇干货清单算法解决什么打个比方复杂度最近包含扫描谁是父 → 建树电影院找前排挡视线的人O(n²) 带剪枝扫描线栈父–子依赖图书馆橡皮圈栈O(n)相邻探测顺序依赖前脚走后脚到O(n log n) 排序主导P95 阈值瓶颈标注赛跑取前 5%O(n log n)8.2 配餐数据examples/tracing-cross-lib.json— 跨 5 库的复杂异步链Express → Auth → Redis → MySQL → Kafka最适合看嵌套瀑布examples/tracing-multi-lib.json— pg KafkaJS Express 跨库8.3 下篇预告逻辑上我们能画出瀑布图了。但当数据大到 40 万条、64MB 时浏览器主线程会卡死。下篇进入性能工程Web Worker 把重计算挪出主线程增量 JSON 解析让大文件不占爆内存。本篇附赠动手练习手算下面 3 个操作的时间包含关系判断谁是父X: 0–500Y: 100–200Z: 10–600思考两个操作时间区间完全重叠都有 0–100却互相不包含会发生什么答案谁都不包含谁都可能是根如果我从 j0最开头往回扫而不是从这个 break结果会一样吗答案会认到最外层那个父而不是最近的父——嵌套层级就错了