企业官网建设流程全解析

04 · 瀑布图背后：异步操作链是怎么重建的？（两个算法讲透）

阅读时长：约 35 分钟
前置知识：第 3 篇（配对成操作）。本篇解决"父子嵌套关系怎么找出来"。
本篇目标：把 Chrome DevTools Performance 那种瀑布图的地基代码，一行行讲透。你会学到两个计算机经典算法的真实应用：最近包含扫描和扫描线（sweep-line）依赖发现。

目录

1. 我们要解决的问题：操作谁包含谁？
2. 概念：什么叫"时间包含"？打个比方
3. 建树：最近包含扫描（重点）
4. 为什么只返回根节点？
5. 找依赖：扫描线 + 顺序相邻
6. 瓶颈检测：P95 一刀切
7. 数据流向全景
8. 总结 + 下篇预告

1. 我们要解决的问题：操作谁包含谁？

配对之后，我们有一堆操作。每个操作有开始时间（startTime）和结束时间（endTime）。

假设有 4 个操作（单位 ms）：

A: 请求进入，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(startX<=startY&&endX>=endY){// 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(leti=0;i<spans.length;i++){// 从 i 的前一个开始，往回一个个看for(letj=i-1;j>=0;j--){// 谁能在时间上"完全包住"我？if(spans[j].startTime<=spans[i].startTime&&spans[j].endTime>=spans[i].endTime){spans[i].parentId=spans[j].id;// 认父spans[j].children.push(spans[i]);// 父也登记我这个儿子spans[i].depth=spans[j].depth+1;// 我的深度 = 父亲深度 + 1break;// 找到最近的父，就停！}}}

3.4 关键问题：为什么是"往回扫"而不是"从最开头扫"？

这是整个算法设计的精妙之处。

打个比方：想象你在一个电影院找"谁坐在我前面直接挡着我"。你不会去问第一排的人（太远了），你会看紧挨着你的前排——那个人最可能挡到你。

在时间线上：“最可能的父节点，是开始时间比我早、结束时比我晚、并且离我最近的那个”。

所以算法从 i-1 开始往回扫，第一次命中（找到能包住我的）就立刻break。这样：

• 找到的是"最近的"父节点（正确性关键）
• 找到就停（效率关键，省掉大量无效比较）

为什么必须是"最近的"而不是"任意一个能包住的"？

打个比方：你站在一排套娃最外层的 A 里面，又站在中间层 B 里面。往回扫时，你第一个遇到的能包住你的应该是内部的 B（因为 B 离你近），而不是外层的 A。"最近包含"保证了你直接挂在正确的中间层下面，而不是跳过一层直接挂到最外层。

3.5 手动跑一遍（走数据）

假设排序后的操作（时间 ms）：

spans[0]: A 0–300 spans[1]: B 10–90 spans[2]: C 100–200 spans[3]: D 210–290

• i=1 (B)：往回看 j=0 (A)。A 开始 0 ≤ 10，A 结束 300 ≥ 90 → 包含！B 认 A 为父。break。
• i=2 ©：往回看 j=1 (B)。B 开始 10 ≤ 100，但 B 结束 90 ≥ 200？否！B 不包含 C。继续 j=0 (A)。A 开始 0≤100，A 结束 300≥200 → 包含！C 认 A 为父。
• i=3 (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,depth+1),]);}

• marginLeft: depth * 16→缩进随深度增加，每层 16px
• width: endTime - startTime→横条宽度= 耗时
• 递归 children + depth+1 → 画子节点

这样一来，"深度（嵌套层级）"和"宽度（耗时）"两个维度就出来了——横着是时间，竖着/缩进是层级，这就是瀑布图。

5. 找依赖：扫描线 + 顺序相邻

buildWaterfall给出的是"结构"，而"依赖关系"（比如"查询 A 在等连接建立"）由buildDependencies用扫描线算法补足。它做两件事。

5.1 第一遍：父–子依赖（栈式扫描）

constactive=[];// 一个栈，装着"当前还开着"的操作for(constopofsorted){constopEnd=op.end?.timestamp??Infinity;// 弹出所有"已经结束"的容器（它们结束时间早于当前操作开始）while(active.length>0&&active[active.length-1].endTime<op.start.timestamp){active.pop();}// 栈顶就是当前操作的直接父if(active.length>0){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(leti=1;i<sorted.length;i++){constprevEnd=sorted[i-1].end?.timestamp??sorted[i-1].start.timestamp;constgap=sorted[i].start.timestamp-prevEnd;if(gap>=0&&gap<=5){// 间隙小于等于 5mslinks.push({source:sorted[i-1].operationId,target:sorted[i].operationId,type:'sequential',// 顺序依赖});}}

关键：只判断排序后的相邻对——如果两个操作隔着一堆其他操作，就不算顺序依赖。这让检测保持局部、避免误报。

5.4 三种依赖总结

6. 瓶颈检测：P95 一刀切

6.1 代码

exportfunctionfindBottlenecks(spans:TraceSpan[],thresholdPercentile=95):TraceSpan[]{constdurations=spans.map(s=>s.duration).sort((a,b)=>a-b);constthreshold=durations.length?durations[Math.ceil((thresholdPercentile/100)*durations.length)-1]:0;returnspans.filter(s=>s.duration>=threshold&&s.duration>0);}

6.2 它在干什么

1. 把所有操作耗时排序，算出 P95 值作为阈值。
2. 把达到或超过这个阈值的操作标为"瓶颈"。

6.3 为什么"自己跟自己比"？

阈值不依赖任何外部基准（不是什么"必须 <500ms 才合格"），而是基于当前数据自己算出 P95。

打个比方：一场赛跑，不规定"必须 10 秒内算合格"，而是取前 5% 完成的人当"跑得快的人"。这样无论赛道多长多短（数据集多快多慢），总能挑出"相对最慢的那几个"。

好处：任何数据集都能用，不用预设阈值；坏处：它给的是"相对慢"而不是"绝对超标"。两者各有用途，NodeVerdict 在这里选了相对快照。

7. 数据流向全景

把第 1-4 篇串起来，一条完整的可视化数据流：

8. 总结 + 下篇预告

8.1 本篇干货清单

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 解析让大文件不占爆内存。

本篇附赠：动手练习

1. 手算下面 3 个操作的时间包含关系，判断谁是父：
   • X: 0–500，Y: 100–200，Z: 10–600
2. 思考：两个操作时间区间完全重叠（都有 0–100）却互相不包含，会发生什么？（答案：谁都不包含谁，都可能是根）
3. 如果我从 j=0（最开头）往回扫而不是从这个 break，结果会一样吗？（答案：会认到最外层那个父，而不是最近的父——嵌套层级就错了）