Linear drain for long-lived stream queues
长期流队列的线性排空
Long-lived stream queues can accumulate thousands of frames while their consumers are busy. Removing each frame with `Array.prototype.shift()` moves the remaining array range on the observed V8 path, so draining `N` queued frames performs quadratic reference movement and delays unrelated work on the same event loop. [Issue #3270](https://github.com/deepseek-harness/deepseek-harness/issues/3270) records the production
English
Problem
Long-lived stream queues can accumulate thousands of frames while their consumers are busy. Removing each frame with Array.prototype.shift() moves the remaining array range on the observed V8 path, so draining N queued frames performs quadratic reference movement and delays unrelated work on the same event loop. Issue #3270 records the production sample that identified ArrayShift, MoveRange, and memmove as the dominant stack.
The affected streams have different wake-up, failure, cancellation, and disposal behavior. Their shared requirement is storage that preserves FIFO order without making those lifecycle decisions.
Decision
@deepseek-ai/dsh-deque owns one zero-dependency circular array for Host and browser consumers. pushBack(), pushFront(), and popFront() change indices instead of moving the live range. A removal clears its slot immediately. The backing array doubles when full and halves when a non-empty deque reaches one quarter of capacity, so growth and compaction copy work remains amortized constant time and vacant storage stays bounded over interleaved queue use.
The package has no singleton state, symbols, or class identity shared between consumers. Each consumer constructs and confines its own deque, so duplicate npm copies preserve runtime behavior and the published dependency policy treats Deque as a safe Host export. The Client bundle purity rule also treats the package as an inline-safe library. The Gateway browser artifact carries its deque implementation without introducing a module-table entry or a Cordis service.
The Host Remote event source, each connected Client Remote event queue, the browser Remote stream inbox, each Session history follower, each Session control stream, and each Workspace follower store frames in this deque. Their owning classes retain all wake-up, failure, cancellation, buffered-drain, and disposal behavior. Session history uses front insertion to place constructor-seed events before live events received during its opening observation.
Queue capacity, frame coalescing, overload rejection, and global agent admission remain consumer or application policy. The deque does not infer any of them from storage pressure.
Verification
The deque unit suite covers FIFO order, front insertion, array-boundary wrapping, geometric growth, quarter-full compaction after interleaved enqueue and dequeue, clearing, reuse, and undefined entries. Focused coverage reports 100% statements, branches, functions, and lines for packages/util/deque/src/index.ts.
The API Remote, Gateway, Session control/history, and Workspace follow suites exercise the migrated lifecycle behavior. They retain their package-owned ordering, failure, cancellation, and disposal assertions.
The command pnpm exec tsx packages/util/deque/benchmarks/drain.ts ran on Node v26.0.0, arm64 macOS 26.4. Five samples per size produced these median deque drain times; enqueue time is outside the measurement:
| Entries | Median drain | Nanoseconds per entry |
|---|---|---|
| 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 |
The checked-in benchmark makes the measurement reproducible, but CI does not enforce a wall-clock threshold. Deterministic unit coverage owns the algorithm and compaction paths; the benchmark demonstrates approximately linear drain work on the recorded runtime.
Alternatives considered
Array head removal. Keeping shift() preserves the smallest source diff but repeats the production failure mode and provides no amortized constant-time guarantee.
A monotonic head cursor with occasional slicing. This can provide amortized constant-time FIFO removal, but Session history also needs front insertion before concurrently buffered entries. A circular deque provides both operations through one storage rule without a special history prefix buffer.
A linked deque. Linked nodes make every end operation constant time and release removed nodes immediately, but each frame also allocates a node and pointer fields. The circular array keeps contiguous storage and amortizes the less frequent copies.
An external deque dependency. The required API is small, and the retention rule includes immediate slot clearing plus a specific shrink condition that the regression suite must exercise. A local zero-dependency utility keeps that storage lifecycle inspectable in both compiler faces; an external collection would still require the same integration and retention verification.
Consequences
Draining a backlog performs linear deque work instead of quadratic array-range movement. Removed frame references become collectible before backing-storage compaction, and a stream that remains active does not retain every historical slot.
The repository owns a small generic collection implementation and its compatibility surface. Changes to its indexing, growth, or shrink rules require focused ordering and compaction coverage because every migrated stream shares the result.
Unbounded producers can still exhaust memory or delay consumers through the volume of legitimate per-frame work. Capacity and admission policy remain separate decisions rather than hidden behavior in a generic collection.
中文
问题
当消费方忙碌时，长期存在的流队列可能积累数千个帧。在观测到的 V8 路径上，使用 Array.prototype.shift() 移除每个帧会移动剩余数组区间，因此排空 N 个排队帧会执行二次方级别的引用移动，并延迟同一事件循环上的无关工作。Issue #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 策略仍是独立决策，而不是通用集合中的隐藏行为。