# Agent Note: 长期流队列的线性排空

Status: implemented
Archived: 2026-09-04

[English](2026-08-28-linear-stream-queue-drain.md) | 中文

## 问题

当消费方忙碌时，长期存在的流队列可能积累数千个帧。在观测到的 V8 路径上，使用 `Array.prototype.shift()` 移除每个帧会移动剩余数组区间，因此排空 `N` 个排队帧会执行二次方级别的引用移动，并延迟同一事件循环上的无关工作。[Issue #3270](https://github.com/deepseek-harness/deepseek-harness/issues/3270) 记录了把 `ArrayShift`、`MoveRange` 和 `memmove` 识别为主要堆栈的生产采样。

受影响的流具有不同的唤醒、失败、取消和 disposal 行为。它们的共同要求是保持 FIFO 顺序、同时不替它们作出这些生命周期决策的存储。

## 决策

`@deepseek-ai/dsh-deque` 为 Host 和浏览器消费方拥有一个零依赖环形数组。`pushBack()`、`pushFront()` 和 `popFront()` 改变索引，而不移动存活区间。移除会立即清空对应槽位。后备数组在满载时翻倍，在非空双端队列达到四分之一容量时减半，因此扩容和压缩的复制工作保持摊销常数时间，且交错队列使用期间的空闲存储保持有界。

该包没有消费方之间共享的 singleton 状态、符号或类身份。每个消费方都会构造并独占自己的双端队列，因此 npm 中存在重复包副本不会改变运行时行为，发布依赖策略也会把 `Deque` 视为安全的 Host 导出。Client bundle purity 规则同样把该包视为可内联库。Gateway 浏览器产物携带其双端队列实现，而不引入 module-table 条目或 Cordis 服务。

Host Remote 事件源、每个已连接 Client 的 Remote 事件队列、浏览器 Remote 流 inbox、每个会话历史 follower、每个会话控制流和每个 Workspace follower 都在此双端队列中存储帧。它们的所属类保留全部唤醒、失败、取消、缓冲排空和 disposal 行为。会话历史使用前插，把构造器种子事件放在打开观察期间收到的 live 事件之前。

队列容量、帧合并、过载拒绝和全局 agent admission 仍是消费方或应用策略。双端队列不会根据存储压力推断其中任何策略。

## 验证

双端队列单元测试覆盖 FIFO 顺序、前插、数组边界环绕、几何扩容、交错入队和出队后的四分之一满压缩、清空、复用与 `undefined` 条目。聚焦覆盖率报告显示 `packages/util/deque/src/index.ts` 的语句、分支、函数和行均为 100%。

API Remote、Gateway、会话控制/历史和 Workspace follow 测试覆盖迁移后的生命周期行为。它们保留所属包对顺序、失败、取消和 disposal 的断言。

命令 `pnpm exec tsx packages/util/deque/benchmarks/drain.ts` 在 Node v26.0.0、arm64 macOS 26.4 上运行。每个规模采样五次，得到以下双端队列排空时间中位数；测量不包含入队时间：

| 条目数 | 排空中位数 | 每条目纳秒数 |
|---:|---:|---:|
| 250,000 | 1.705 ms | 6.818 ns |
| 500,000 | 2.541 ms | 5.082 ns |
| 1,000,000 | 4.668 ms | 4.668 ns |
| 2,000,000 | 9.656 ms | 4.828 ns |

检入的 benchmark 使该测量可复现，但 CI 不强制墙钟时间阈值。确定性单元覆盖率负责算法和压缩路径；benchmark 在所记录运行时上证明排空工作近似线性。

## 考虑过的替代方案

**数组头部移除。** 保留 `shift()` 能得到最小源码差异，但会重复生产故障模式，也不提供摊销常数时间保证。

**单调头游标配合偶尔切片。** 这可以提供摊销常数时间的 FIFO 移除，但会话历史还需要在并发缓冲条目之前执行前插。环形双端队列通过一项存储规则同时提供两种操作，不需要特殊的历史前缀缓冲区。

**链式双端队列。** 链式节点让每个端点操作都保持常数时间，并立即释放已移除节点，但每个帧还会分配一个节点和指针字段。环形数组保持连续存储，并摊销频率较低的复制。

**外部双端队列依赖。** 所需 API 很小，保留规则包括立即清空槽位以及回归测试必须覆盖的特定缩容条件。本地零依赖工具让两个编译 face 都能检查该存储生命周期；外部集合仍需相同的集成和保留验证。

## 后果

排空 backlog 会执行线性双端队列工作，而不是二次方级别的数组区间移动。已移除帧的引用在后备存储压缩前即可回收，持续活动的流也不会保留每个历史槽位。

仓库拥有一项小型通用集合实现及其兼容性接口。对其索引、扩容或缩容规则的修改需要聚焦的顺序和压缩覆盖，因为每个已迁移流都会共享结果。

无界生产者仍可能通过合法逐帧工作的数量耗尽内存或延迟消费方。容量和 admission 策略仍是独立决策，而不是通用集合中的隐藏行为。