Skip to content

decision request: O(n²) per-turn recommend screening in acp-kernel starves the event loop on long sessions (#5304) #5337

Closed

Description

@ranxianglei

来源: #5304 (#5304) 分析「长会话 Web GUI 冻结在 v0.1.209 上确认复现」时发现

一句话说清

长会话(数千~上万条消息)的每个回合,kernel 的 processTurn 内部都会跑一段无条件执行的推荐筛查(recommend screening),对整段入站历史做二次方复杂度的同步扫描:2.3 万条核心消息量级下单次调用实测 ~17 秒。扫描期间 Node 主线程被占死,bili 进程上的 Web GUI 与同端口其他请求全部冻结——这正是 #5304 / #4528 报告的症状,且 #4528 的修复(#4544,已包含在报告者的 v0.1.209 里)只在阶段之间让出事件循环,拆不开这一个内核调用内部的大块。

机制(根因链)

  1. kernel/src/compress.ts:1192 的 recommendNode 没有 enabled 门控(对比同文件 crush/filter 节点都有)——每个回合、任何会话都执行,与上下文压力无关。
  2. 它把可压缩区间合并成推荐单元(mergeRangesToThreshold,单元数 U ∝ 历史长度),再经 screenRecommendedUnits(kernel/src/recommend.ts:646)对每个单元调用 projectUnit(kernel/src/unit-projection.ts:92)。projectUnit 是 [Bug] recommend/apply 对同一区间的 turn-integrity 判定永久不一致:acp_status 反复推荐的区间被 apply 侧整段拒绝(0.1.196,Range would split N turn(s) at the protected-zone boundary) #3236 定下的「能否折叠」唯一判定定义,判定标准本身不能弱化——问题不在判定,在实现复杂度。
  3. projectUnit 内部对全历史做线性 .find() 扫描(没有 id→index 索引):
    • filterProtectedToolMessages(unit-projection.ts:521)两个循环逐 id messages.find(m => m.id === id)(:559、:574);
    • mediaExcluded 过滤同样逐 id .find()(:210-213);
    • 保护区截断检查 droppedIds.includes(half) 嵌在 .some() 里(:272-277)。
      总工作量 Σ|unit|·n ≈ O(n²)。
  4. 每个单元还重复做全历史重扫:collectFailedCompressCallIds / collectLatestProtected / collectAgedCompressCallIds(unit-projection.ts:533/536/544)、computeIntegrityWithdrawals → computeTurnGroups(turn-integrity.ts:138/:30);computeProtectedRefs 每回合调两次(compress.ts:1195/:1230)。

证据(合成语料实测,形状对齐报告者:OpenAI-wire、reasoning+tool_calls 密集、单 bili 进程)

核心消息数 单次 processTurn
3,964 ~0.3 s
6,773 ~0.9 s
11,526 ~3.2 s
23,521(~42 MiB) ~16.8 s

n 翻倍 → 时间 ×4,O(n²) 成立。 V8 采样 profile(单次 23,521 消息运行)top JS 函数全部落在该家族:filterProtectedToolMessages 12.4%、computeIntegrityWithdrawals 7.4%、computeTurnGroups 3.9%、projectUnit 3.9%;builtin 侧 LoadIC_Megamorphic 27.6% / StringEqual 12.4% / Set/Map 查找各 ~8.7%——典型的反复建 Set + 字符串成员扫描。

对照:#5304 报告者四个会话(2,345 → 13,836 条)的冻结随规模超线性增长、重启无效——同一签名。绝对值差异(报告者峰值 local=7,093 ms vs 本语料 16.8 s)来自语料内容密度不同,量级与增长律一致。

宿主侧(processTurn 之外的全部 prepare 阶段:parse、wire 转换、nudge 决策、出站重建等)在同一 42 MiB 输入上合计 <0.5 s——瓶颈完全在这一内核调用内。

为什么宿主侧解不了

  • 这是一个同步的单一 kernel 调用,[PR] fix(#4528): yield to the event loop during long turns; warn on slow sessions #4544 的 boundary yield 够不到其内部;要让出事件循环就得把 processTurn 改异步 = 架构级改动(选项 C)。
  • 关掉/绕过 recommend 路径 = 关掉压缩触发(核心承诺),不可接受。
  • 入站历史由宿主客户端(dsh desktop 每回合全量重发)决定,bili 不能裁剪(wire fidelity)。

⇒ 修复必须在 kernel/ 内,按 Kernel Boundary 需 owner 批准后才实施。

选项

A(推荐)— 算法级 O(n) 修复,判定行为零变化

  • 每次筛查通道构建一次 id→index Map(projectUnit 增加可选输入,缺省时内部构建,apply/report 两条现有调用路径不受影响);
  • 替换三处逐 id .find() 与 droppedIds.includes;
  • 把每单元重复的全历史重扫(failed-compress ids / latest-protected / aged-compress ids / turn groups / computeProtectedRefs×2)提升为每回合一次计算的共享输入,传入 screenRecommendedUnits;
  • 复杂度 O(n²)→O(n);2.3 万消息预计从秒级降到低百毫秒级;
  • 成本:一个 kernel PR(kernel-change 声明 + kernel/package.json 版本 bump + kernel 单测 + bili 集成两层测试)+ 回归钉(大 N 筛查耗时上界测试;既有投影一致性套件必须原样绿)。

B — 跨回合记忆化(#4528 fix ②):按内容 hash 缓存每条消息的派生数据并随会话持久化。更彻底,但跨 host+kernel、动持久化格式面,设计面大得多。
C — worker_threads(#4528 fix ③):pipeline 移线程池,架构级,代价最大。
D — 宿主侧缓解:不可行(见上)。

结构化八问

  1. 是什么问题:长会话每回合多秒级的同步扫描占死主线程,Web GUI/同进程请求冻结(可用性体验缺陷,数据无损)。
  2. 什么原因导致的:recommend 节点无条件每回合运行,且其单元筛查(projectUnit)用逐 id 线性 .find() + 每单元全历史重扫实现,总复杂度 O(n²)(见机制链)。
  3. 影响范围与严重程度(按选项):
    • 现状(不修):任何入站历史到数千条消息的车道(dsh desktop 已确认 4 个会话;opencode/pi/codex 同样长历史时同风险)每回合秒级冻结;p1 体验毁灭级「特定条件下有问题」= 长会话 + 压缩未覆盖大部分历史。
    • A:仅改变 kernel recommend 路径的性能特性,判定输出字节不变;风险集中在重构自身(由既有测试兜底)。
    • B:新增持久化缓存面,影响会话文件布局与迁移;C:动并发模型,波及所有 pipeline 路径,回归面最大。
  4. 怎么修复的(推荐 A):纯算法优化——索引化 + 共享输入提升,不改任何判定语义;B/C 的收益也包含 A,A 是前置。
  5. 是否有回归问题(按选项):A — 投影语义不变,id 是账本唯一主键不存在映射歧义;风险 = 重构引入行为漂移,由 kernel 单测 + bili 集成 + 新增耗时上界钉 + tests/golden/wire-contract/kernel.json 黄金钉共同兜底。B — 缓存失效错误会直接导致错误折叠决策,风险高于 A。C — 线程安全/状态传递,最高。
  6. 是否破坏缓存:A 不动任何缓存/重试/增量游标/去重键;B 自身就是新缓存层,需配套失效设计。
  7. 是否改了设计方向:A 不改架构/边界/数据流(单模块内算法优化);B 增加持久化维度;C 增加并发维度。
  8. 是否引入了新的配置:A 无新 env/config/默认值;B/C 可能需要 knob。

请拍板

是否批准选项 A 的 kernel 变更?批准后我开 kernel PR 引用本 issue + #5304(B/C 留待 A 落地后按残余耗时再评估,不并行开工)。

Activity

  1. ranxianglei commented on Oct 31, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    (ai: vllm-qwen/qwen3.8-27b)

    查重:不重复

    与 #5304(用户报告)、#4528(原始 event-loop starvation,已关闭)相关但机制不同——本 issue 是 #5304 分析中独立定位出的 kernel 内 O(n²) 根因 + 决策请求。#4528 的修复(#4544 boundary yield)只解决阶段间让出,够不到 processTurn 内部;本 issue 针对的是 processTurn 内部 recommend screening 的算法复杂度。

    代码验证(已逐行确认)

    所有机制链声称的代码模式均已在当前 master 上核实存在:

    声称 验证结果
    recommendNode 无 enabled 门控 ✅ compress.ts:1192 — 直接 run(io, ctx),对比 crush 节点 :1130 有 ctx.config.crush?.enabled === true 门控
    computeProtectedRefs 每回合调两次 ✅ compress.ts:1195 和 :1230 各一次
    mediaExcluded 逐 id .find() ✅ unit-projection.ts:210-213 — input.messages.find((m) => m.id === id) 在 .filter() 内
    filterProtectedToolMessages 两个循环逐 id .find() ✅ unit-projection.ts:559 和 :574 — 各一次 messages.find((m) => m.id === id)
    每单元重复全历史重扫 ✅ :533/:536/:544 — collectFailedCompressCallIds / collectLatestProtected / collectAgedCompressCallIds 每次调用都遍历全 messages
    screenRecommendedUnits 对每个单元调 projectUnit ✅ recommend.ts:646-666 — units.filter(unit => projectUnit({...}))

    O(n²) 判定成立:单元数 U ∝ n(历史长度),每单元 O(n) 扫描 → 总 O(U×n) = O(n²)。

    结构化八问

    1. 是什么问题:长会话(数千~上万条消息)每回合 kernel processTurn 内的 recommend screening 做 O(n²) 同步扫描,占死 Node 主线程数秒到十几秒,Web GUI 与同端口全部请求冻结。数据无损但体验毁灭。

    2. 什么原因导致的:recommendNode 无条件每回合执行(无 enabled 门控),其核心 projectUnit 对全历史用逐 id 线性 .find() 而非索引查找,且每单元重复构建 Set/重扫全历史(failed-compress ids、latest-protected、aged-compress ids、turn groups)。总复杂度 = 单元数 × 每单元线性扫描 = O(n²)。

    3. 影响范围与严重程度(按选项):

      • 现状(不修):任何入站历史 >3K 条消息的车道每回合秒级冻结。dsh desktop 已确认 4 个会话受影响(2,345→13,836 条);opencode/pi/codex 长历史时同风险。p1——特定条件下体验毁灭级(长会话 + 大部分历史未被压缩覆盖)。
      • A:仅改变 kernel recommend 路径的性能特性,判定输出字节不变。风险集中在重构自身引入行为漂移,由既有测试+新耗时上界钉兜底。
      • B:新增持久化缓存面,影响会话文件布局与迁移策略。缓存失效错误会直接导致错误折叠决策,风险高于 A。
      • C:动并发模型(worker_threads),波及所有 pipeline 路径,线程安全/状态传递复杂度最高,回归面最大。
    4. 怎么修复的(推荐 A):纯算法优化,不改任何判定语义——①每次筛查通道构建一次 id→index Map(projectUnit 增加可选输入参数,缺省时内部构建);②替换三处逐 id .find() 与 droppedIds.includes;③把每单元重复的全历史重扫提升为每回合一次计算的共享输入传入 screenRecommendedUnits。预期 2.3 万消息从 ~17s 降到低百毫秒级。B/C 的收益包含 A,A 是前置且独立闭环。

    5. 是否有回归风险(按选项):

      • A:投影语义不变(id 是账本唯一主键,Map 索引不存在映射歧义);tests/golden/wire-contract/kernel.json 黄金钉 + 既有投影一致性套件必须原样绿;新增大 N 筛查耗时上界回归钉。高危模式逐项过:无 fail-fast 变吞错、无阈值/时序漂移、无输出格式变化。
      • B:缓存键设计错误 → 错误折叠决策(比现状更糟);持久化迁移失败 → 会话不可读。
      • C:pipeline 状态跨线程传递 → 竞态;worker 启动开销在短会话反而更慢。
    6. 是否破坏缓存:A 不动任何缓存/重试/增量游标/去重键。B 自身就是新缓存层需配套失效设计。C 不涉及。

    7. 是否改了设计方向:A 不改架构/边界/数据流(单模块内算法优化,接口向后兼容)。B 增加持久化维度。C 增加并发维度。

    8. 是否引入了新的配置:A 无新 env/config/默认值。B/C 可能需要 knob。

    选项对比

    A (算法 O(n)) B (跨回合记忆化) C (worker_threads)
    预期效果 17s → <200ms 进一步降低(稳态近零) 同 A 量级 + 不阻塞主线程
    改动范围 kernel/src/unit-projection.ts + recommend.ts + compress.ts(小改) host + kernel + 持久化格式 全 pipeline 路径
    行为变更 零(字节等价) 低(缓存失效策略) 中(时序/并发语义)
    回归面 小(单模块,既有测试兜底) 中(持久化迁移) 大(并发模型)
    实施成本 1 个 kernel PR 多 PR + 设计文档 架构级重构
    是否 A 的前置 — 否(独立但收益含 A) 否(独立但收益含 A)

    我的建议

    批准选项 A。理由:

    • 问题已完全定位且有量化证据(合成语料实测 + V8 profile top 函数全落在该家族);
    • A 是零行为变更的纯性能修复,风险最低、收益最直接(秒级→百毫秒级);
    • B/C 的收益包含 A,A 落地后若残余耗时仍显著再评估不迟;
    • 符合 Kernel Boundary 流程:kernel-change 声明 + owner 批准 + 版本 bump + 两层测试 + 回归钉。

    等待你拍板。批准后我开 kernel PR 引用本 issue + #5304。


    标签:bug, scope/kernel, p1(长会话每回合秒级冻结 = 体验毁灭级可用性缺陷;修复点在 kernel recommend 路径算法)

  2. added 3 commits that reference this issue on Oct 31, 2026
  3. added a commit that references this issue on Oct 31, 2026
  4. ranxianglei commented on Oct 31, 2026

    @ranxianglei
    OwnerAuthor

    已由 PR #5361 修复合入 master(merge 2026-10-31T15:30:37Z):每轮压缩筛查的 O(n) 全史推导提升为每轮一次共享,长会话每回合卡死从二次方降为线性;合成语料 N=20000 实测 9028ms → 572ms(约 16×)。判定输出逐字节不变(等价性测试钉住),内核全套 1510 测试绿。选项 B/C(记忆化/worker_threads)仍是未来可选项,不构成本单关闭条件。

  5. added a commit that references this issue on Nov 1, 2026
  6. added a commit that references this issue on Nov 5, 2026
  7. added a commit that references this issue on Nov 6, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions