2026-11-16 AI Agent 面试训练
今日学习主题:上限写在声明里,代价发生在窗口里。字段编号是线格式里的”身份额度”,CPU 配额是按 100ms 窗口发放的时间额度,KV 显存是并发的容量额度,任务 TTL 是句柄的存活额度,连接池是会话状态的存活窗口——所有”上限”都有一个发放粒度和一个计量口径,而平均值、接口声明、窗口大小这三个数字都不等于实际消耗。今天的五道题都在追问同一件事:这个上限是按什么窗口发放的,谁来计量,计量点在谁手里。
题目目录:
| 编号 | 题目 ID | 类型 | 一级类型 | 二级主题 | 题目名称 | 难度 | 一句话考察点 |
|---|---|---|---|---|---|---|---|
| B01 | Q-20261116-B01 | 非 Agent 基础 | 编程语言与运行时 | 序列化与数据校验:线格式演化与兼容性代数 | 删了一个字段又新建同号字段:为什么线上没有任何报错 | 基础题(中高) | 编号是身份、名字是别名;wire-safe 与 wire-compatible 的边界;未知字段保留的前提 |
| B02 | Q-20261116-B02 | Agent 基础 | AI 与大模型基础 | Attention、KV Cache 与上下文窗口的容量与成本边界 | 128K 上下文只能并发 6:KV Cache 才是并发的硬上限 | 基础题(中高) | KV 显存账;decode 访存受限;prefix 复用省 prefill 不省 decode |
| S01 | Q-20261116-S01 | Agent 场景 | 工具与互操作协议(兼属 AI Agent 核心) | MCP Tasks:持久句柄、轮询节奏、中途人工输入与协作式取消 | 8% 的工具调用跑不完 60 秒:把长任务从连接上摘下来 | 场景题(高) | 任务成为一等对象;幂等键与 taskId 绑定;取消是意图不是保证 |
| S02 | Q-20261116-S02 | 非 Agent 场景 | 数据库与存储(兼属分布式系统) | 连接池与连接复用:池化粒度对会话状态的影响 | 换成连接池中间件后,互斥锁同时被两个实例持有 | 场景题(高) | 会话状态的存活窗口被池化粒度改写;三层连接预算;状态外置 |
| L01 | Q-20261116-L01 | LeetCode | 栈与队列(贪心模拟) | 栈序列的可行性判定 | 946. 验证栈序列 | medium | 能弹就弹不损失可行性;交换论证;每个元素进出栈各一次 |
配置读取状态:成功读取 题库配置.md,版本 v9(last_maintained: 2026-11-16,本轮为 v9 生效后的第 1 次每日出题)。v9 相对 v8 为增量更新:在「AI 安全与治理」下新增”只读工具的副作用边界”与”目录限制与领域自带的间接引用机制”两项覆盖范围,并更新两个观察项状态;未新增、合并、降级、暂停任何一级类型,active 一级类型仍为 13 个。无暂停类型;「观察中的新技术」8 项均未标记「允许试学」,本轮不出题(其中 MCP Tasks 属于已启用的工具与互操作协议扩展体系,不是观察项,故 S01 可用)。
去重结果:索引窗口为 2026-08-16 至 2026-11-16(运行日前推 3 个日历月,含起止日期),窗口内最早条目为 2026-10-10,本轮无需剪除任何索引行。对比 题目索引.md 140 条记录与最近 30 天(2026-10-17 至 2026-11-16)题目:protobuf 线格式兼容、KV Cache 容量账、MCP Tasks 长任务改造、连接池会话状态、LeetCode 946 均无同题、同题号或换皮重复。需说明的三处邻近题目与区分点:① 2026-10-15 B02 是”序列化与数据校验的信任边界”(不可信输入、校验位置、多态反序列化风险),本题是”序列化格式自身的兼容性代数”(编号身份、wire type 跳读、未知字段、默认值语义),考点不重叠,且已超出 30 天窗口;② 2026-10-19 B02 与 2026-11-09 B02 都提到 KV Cache,但都停留在”Attention/窗口成本”与”量化位宽”层面,未做容量账与带宽账,本题是其结构层展开;③ 2026-10-28 S01 已用过 MCP Tasks 的能力协商与降级角度(扩展是否可用、如何回退),本题是单个长任务的生命周期、幂等与恢复角度,故障现象与结论均不同。
B01 · 删了一个字段又新建同号字段:为什么线上没有任何报错
题目 ID:Q-20261116-B01 | 分类:基础(非 Agent) | 一级类型:编程语言与运行时 | 二级主题:序列化与数据校验、线格式演化与兼容性代数
题目
订单事件以 protobuf 二进制写入 Kafka,同时把一份 ProtoJSON 副本落到对象存储供排障使用。某次重构中,有人删掉了 user_id(编号 3,int64),并在同一个提交里新建了 uid(编号 3,int64)。灰度两天后出现三件事:
- 旧版消费者把
uid解出来当user_id用,没有任何异常,但金额对账对不上; - 一个”反序列化后立即再序列化转发”的网关,把上游新加的
coupon_id字段抹掉了; - 排障时在 JSON 副本里能搜到字段名,在二进制文件里完全搜不到。
请回答:字段编号、字段名、wire type 三者在兼容性里各自承担什么角色?为什么”加字段”是 wire-safe 而”删字段后复用编号”是 wire-unsafe?“反序列化再序列化会丢字段”的机制与边界是什么?灰度期间应该怎么在 CI 里拦住这类回归?
先思考
- 二进制线格式里到底存不存字段名?如果不存在,接收端凭什么把这串字节映射到结构体的某个成员?
- 对一段老代码来说,一个”陌生的字段编号”是不是一定能被安全跳过?它靠什么信息决定跳几个字节?
- “未知字段会被保留”这句话,主语是谁——解析库,还是你的转发代码?哪些操作会让这个保证失效?
参考答案
结论:protobuf 二进制线格式里,字段的身份是编号,字段名只活在代码、JSON 与 TextFormat 里。因此兼容性等价于”接收端能否按编号正确解释这段字节,或安全地跳过它”。删字段却不 reserved 编号,等于把身份借给了新字段——它不会报错,只会静默给错值。
定义与机制:每个字段在线上的 key 是 (field_number << 3) | wire_type,wire_type 决定 payload 是 varint、64 位定长、长度前缀还是 32 位定长。所以”同号不同名”是两个名字指向同一个字段,“同名不同号”是两个完全无关的字段。官方对变更分三档:wire-safe(加字段、删字段但保留编号、给 enum 加值、把字段移入新建的 oneof)、wire-unsafe(改编号、把字段移入已有 oneof)、wire-compatible 但可能有损(int32↔int64、string↔bytes、fixed32↔sfixed32、singular↔repeated 的特定组合)。wire-compatible 只在你能控制所有读写端发布节奏时才可用;schema 对外发布时不应使用。官方的表述很直接:线格式”lean and doesn’t provide a way to detect fields encoded using one definition and decoded using another”——没有自校验能力。
适用边界:reserved 是唯一防线,且只能防未来的人,不能防已经发出去的旧二进制。reserved 编号范围是闭区间;reserved 名字只影响 protoc 与 TextFormat/JSON 解析,不影响二进制运行时。未知字段保留是 proto3 默认行为(与 proto2 一致),但有明确失效场景:转成 JSON 会丢、遍历所有字段逐字段拷贝到新 message 会丢。正确做法是二进制交换 + MergeFrom() / CopyFrom() 这类 message 级 API。
简洁示例:user_id(3, int64) 删除后新建 uid(3, int64),线上字节一模一样。旧读端毫不知情地把 uid 读成 user_id。这不是解析失败,是语义错位——比崩溃难查一个数量级,因为监控全绿、日志里字段名也对。
与相近概念的区别:与 JSON Schema / 业务校验的区别是分工不同。schema 校验回答”这个值合法吗”,编号回答”这串字节属于哪个字段”。前者拦不住编号复用(复用了值仍然合法),后者拦不住值越界(编号对、值超范围)。两层都要有,且位置不同:编号约束在编译期与 CI,值校验在运行时边界。
典型应用(通用工程):服务间 RPC、事件流与事件溯源、Kafka schema registry、数据湖落盘格式、以及任何需要跨版本共存的持久化契约。放到 Agent 系统里同样成立:工具返回结构的演化受同一套规则约束——模型侧 schema 是提示,消费侧解析才是契约,工具结果字段的编号复用会让 Agent 拿到”看起来合法”的错数据。
面试现场 1 分钟版:“二进制里没有字段名,只有编号和 wire type,所以编号就是字段的身份证,一旦发出就不能改、不能复用。加字段是安全的,老代码会把它当未知字段跳过并保留;删字段必须把编号和名字加入 reserved,否则后人复用编号,线上不会报错,只会读到错值,因为线格式本身没有能力发现’用一种定义编码、用另一种定义解码’。另一个坑是转发链路:转 JSON 或逐字段拷贝都会丢未知字段,所以中间层要用二进制加 message 级合并 API,不要手写字段映射。”
追问
追问:如果业务必须把一个已上线的 int32 金额字段扩展成 int64,怎么做最安全?
答:不要原地改类型。int32→int64 属于 wire-compatible 但有损:旧读端遇到超过 INT32_MAX 的值会截断高位,值本身合法、不报错。安全路径是新增编号字段(如 amount_v2)→ 双写并让读端”优先新字段、缺失回退旧字段”→ 用消费端版本观测数据确认没人再读旧编号 → 删除旧字段并把编号 reserved → 最后清理双写。判断”能否删旧字段”的依据是观测数据(谁还在读编号 3),不是发布时间表。
关键点
- 编号是身份、名字是别名:二进制里没有名字,改名的安全性取决于链路上是否有 JSON/TextFormat 或按名取值的下游。
reserved是唯一防线,且必须同时 reserve 编号与名字——前者防二进制复用,后者防 JSON/TextFormat 复用。- 未知字段保留有前提:二进制 + message 级拷贝;转 JSON、逐字段复制、TextFormat 回读都会丢。
- wire-safe ≠ 应用语义兼容:旧代码读到新字段只能看到默认值,而 implicit presence 的标量无法区分”显式设为默认值”与”根本没设置”。
- 兼容性有三档而不是两档:unsafe / safe / compatible-but-lossy,第三档才是最容易被误判的。
常见误区
- “改字段名不影响兼容”:二进制确实不影响,但名字在 JSON/TextFormat 里是线上数据,下游 BI、规则引擎、日志检索、甚至 prompt 里引用的字段名都按名字取值。改名等于悄悄破坏这些消费者,而它们不在你的兼容性测试范围内。
- “字段删掉就行,protoc 会报冲突”:protoc 只在编号已被
reserved时才报错。不 reserve 的话,复用编号是完全静默的——编译通过、测试通过、上线通过,只在脏数据里显形。 - “有 Schema Registry 就安全了”:registry 的检查强度取决于配置的兼容模式(BACKWARD / FORWARD / FULL),它检查的是”schema 之间的关系”,不检查”你是否真的把所有消费者都升级了”;而且 JSON 与二进制两条链路的兼容规则本身就不同,一套 registry 规则覆盖不了两条链路。
延伸学习
- Protocol Buffers 官方文档《proto3 Language Guide》→ “Updating A Message Type” 与 “Assigning Field Numbers”(wire-safe / wire-unsafe / wire-compatible 三档与
reserved规则,本轮已核验原文)。 - Protocol Buffers 官方《Encoding》页:varint、长度前缀与 wire type 的编码细节——理解了 key 的位布局,就理解了”为什么改编号等于换字段”。
B02 · 128K 上下文只能并发 6:KV Cache 才是并发的硬上限
题目 ID:Q-20261116-B02 | 分类:基础(Agent) | 一级类型:AI 与大模型基础 | 二级主题:Attention、KV Cache 与上下文窗口的容量与成本边界
题目
自建推理集群:8×H100 80GB,70B 模型 FP16,GQA 结构(8 个 KV head,head_dim 128,80 层),张量并行 8 路。上线后客户反馈:“上下文开到 128K 时并发只有 6,第 7 个请求的 TTFT 从 1.2 秒变成 18 秒,P99 到 25 秒。“运维的第一反应是”再加两台机器”。请回答:
- 这个模型每个 token 的 KV cache 占多少显存?128K 上下文下单个请求占多少?
- 为什么这里的并发上限是由显存而不是算力决定的?
- decode 阶段为什么是访存受限而不是计算受限?加副本、加 TP、开 prefix caching 分别解决哪一段?
- prefix caching 和厂商的 prompt caching 是同一件事吗?
先思考
- KV cache 的规模由哪几个维度相乘决定?哪些维度由模型结构固定,哪些由请求决定?
- decode 每生成一个 token 只做一次前向,但要读多少字节的权重和 KV?算术强度大概在什么量级?
- 如果缓存本身要占显存,那”缓存命中率”和”并发数”之间是什么关系?
参考答案
结论:本例 KV cache 约 320 KiB/token,128K 上下文单请求约 40 GiB,摊到 8 卡是每卡 5 GiB——显存直接决定并发;而 decode 每步要把全量权重与全部 KV 从 HBM 读一遍,算术强度极低,TPOT 由带宽而非 FLOPS 决定,所以”加算力”解决不了这个问题。
算账(定义与量化):每 token 每层 KV 字节 = 2(K 与 V)× kv_heads × head_dim × 元素字节 = 2 × 8 × 128 × 2 B = 4 KiB;乘 80 层 = 320 KiB/token。128K tokens → 40 GiB。再看显存:权重 140 GB ÷ 8 卡 = 17.5 GB/卡;80 GB 卡按 0.9 利用率留 72 GB,减权重 17.5 GB,再减激活与 CUDA graph 约 6 GB,剩约 48 GB 可给 KV;每请求每卡 40 ÷ 8 = 5 GiB → 理论上限约 9 路,实测 6 路。这 3 路的差额不是玄学:块内碎片(block 未用满)、按 max_tokens 预留、graph 内存池、以及预留水位——差额本身就是可优化空间,也是面试里区分”背过公式”和”调过服务”的地方。
为什么是显存不是算力:并发数 = 可用 KV 显存 ÷ 单请求 KV 占用。单请求 KV 与序列长度成正比,所以”上下文窗口 × 并发数”是一个乘法约束。模型能处理 128K 不等于能同时服务多个 128K——窗口是单请求能力上限,不是并发容量。
为什么 decode 是访存受限:prefill 一次处理整段 prompt,矩阵乘的算术强度高,算力受限,优化靠更好的 kernel 与 chunked prefill;decode 每步只生成一个 token,需要把 17.5 GB 权重(每卡)和全部 KV 从 HBM 读一遍才做一轮乘加,算术强度降到约 1 FLOP/byte 量级——H100 HBM 带宽约 3.35 TB/s,单卡每步下限就是毫秒级。batch 变大只能摊薄权重的读取,KV 读取随 batch 线性增长,所以吞吐提升有天花板,而首 token 延迟还要额外等 prefill。
结构层的位置(GQA 为什么关键):KV 头数从 64 降到 8,KV 直接降 8 倍。这是”架构层减 kv_heads”胜过”工程层抠显存”的原因——它改的是乘法因子,不是常数项。
prefix caching 的边界:它复用相同前缀的 KV 块,省的是 prefill 的计算和这段 KV 的重复分配;它不减少 decode 每步的 KV 读取,所以对 TPOT 没有帮助。而且缓存块自己占显存,与并发是零和的:命中率不够高时是负收益。官方 PagedAttention 论文的出发点是 KV 显存的分页管理与跨请求共享(“near-zero waste” 与 “flexible sharing”),prefix caching 是架在这套分页机制上的复用策略,不是另一套东西。
与 prompt caching 的区别:厂商 prompt caching(Anthropic / OpenAI 那一类)是商业层机制——按 token 计价折扣加 TTL,省的是账单,物理上是否复用 KV 由厂商决定;自建 prefix caching 省的是 GPU 时间与显存,收益要自己折算成钱。两者的共同前提是前缀完全一致,所以上下文布局的工程规则可以共用:稳定的放最前,易变的放最后。
在 Agent 系统中的典型应用:Agent 每一轮都把 system prompt、工具 schema、检索结果、历史消息拼在一起。如果工具结果插在中间,前缀每轮都变,prefix cache 命中率接近 0;正确布局是 system → tools schema → 稳定少样本 → 对话历史 → 本轮工具结果,并且多轮只追加不重写。KV 复用率应当和 token 成本、TTFT 一起进观测面板——它是”上下文工程是否真的省钱”的唯一硬指标。
追问
追问:P99 要求 30 秒内,应该提并发还是降 TPOT?
答:先分解 TTFT 与 TPOT,不要笼统谈”延迟”。本例 18 秒 TTFT 说明请求在排队(admission control 层面),不是解码慢——提 TPOT 优化毫无意义。处置顺序是:① 分池(长上下文请求单独池化,避免 128K 请求把短请求一起拖住);② 准入与上限(单池最大并发 + 排队超时快速失败,而不是无限排队);③ chunked prefill(避免一个 128K 的 prefill 阻塞整批);④ 降上下文(检索裁剪、历史摘要)把单请求 KV 打下来;⑤ 最后才是 TPOT 手段(KV 量化、更激进的 GQA、speculative decoding)。加机器只在①—④都做完仍是容量缺口时才有效。
关键点
- KV 显存 ≈ 2 × layers × kv_heads × head_dim × bytes × tokens,随 batch 与序列长度线性增长,是并发的分母。
- 上下文窗口是单请求上限,不是并发容量;两者相乘才是显存需求。
- prefill 算力受限、decode 带宽受限,优化手段不可互换。
- prefix cache 省 prefill 不省 decode,且与并发争显存,是零和博弈。
- 加副本解决吞吐、TP 解决放不下,两者都不改变”每 token 多少 KV”这个成本常数。
常见误区
- “窗口开到 128K,就能同时服务很多 128K 请求”:窗口是模型能力,并发是硬件容量。把能力当容量做容量规划,是这类事故最常见的起点。
- “加 GPU 就能提并发”:加副本提升的是总吞吐,但要配合会话亲和路由(同一会话落到同一副本才能复用 KV);加 TP 切分权重却引入 all-reduce 通信,单请求 KV 成本不变。盲加机器可能只是把排队从一个池挪到另一个池。
- “prefix cache 命中就等于省钱”:自建场景下它省的是 GPU 时间,而缓存占的显存直接减少并发。命中率 30% 的缓存可能让并发从 9 掉到 6、吞吐反而下降。必须先算”命中省下的 prefill 时间”与”被挤掉的并发损失”哪个大。
延伸学习
- Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023(arXiv:2309.06180)——KV cache 的动态增长、碎片与冗余复制如何限制 batch size,以及”近零浪费 + 跨请求共享”的设计目标(本轮已核验摘要原文)。
- vLLM 文档中 prefix caching / automatic prefix caching 相关章节(具体参数与默认值未核验,请以对应版本文档为准)——把”缓存块与并发零和”这件事落到配置项上。
S01 · 8% 的工具调用跑不完 60 秒:把长任务从连接上摘下来
题目 ID:Q-20261116-S01 | 分类:场景(Agent) | 一级类型:工具与互操作协议(兼属 AI Agent 核心) | 二级主题:MCP Tasks 的持久句柄、轮询节奏、中途人工输入与协作式取消
题目
业务背景:企业级 Agent 平台对外提供 300 个工具、40 个 MCP 服务,员工用它做发布、对账、合规扫描。
系统规模:30 万次/日工具调用,峰值 12 QPS;其中 8% 超过 60 秒(CI 构建 3–25 分钟、批量数据导出 2–10 分钟、合规扫描 5–40 分钟),合计约 2.4 万个长任务/日。另有 3% 的调用需要人工审批,审批平均 12 分钟。
当前架构与数据流:Agent 编排器 → API 网关(硬超时 60 秒,超时后客户端自动重试 2 次)→ MCP 服务(同步阻塞执行,执行完返回结果)。任务状态只存在请求的调用栈里。
目标:长调用不重复执行、可查进度、可中途接受人工确认、可被用户取消、客户端重启后可恢复。
限制条件:MCP Tasks 是扩展(Beta,目标 Core),不同客户端支持程度不同,必须与不支持扩展的旧客户端共存;不能给未声明支持的客户端返回任务;服务端创建任务速率上限 300/分钟;审计要求任务状态可追溯 30 天;部分副作用不可撤销(提交变更单、对外发邮件)。
故障现象:
- 网关 60 秒超时后客户端重试,同一次构建被执行 2–3 次,重复占用构建机、重复提交变更单;
- 需要审批的调用,审批意见回来时连接早已断开,结果丢失,用户只能重跑;
- 用户点”停止”后服务端仍在跑,40 分钟后照样写出了产物;
- 客户端偶发重启,进行中的任务再也查不到,只能人工翻日志。
需要取舍的问题:轮询与推送之间、TTL 长短之间、标准化协议与自建任务 API 之间各选一次,并说明判据。
先思考
- 这四个现象里,哪一个是”协议形态”问题(结构上不可能解决),哪几个是”实现没做对”?把两类分开,方案会清晰很多。
- 如果任务变成一个服务端对象,那”请求的身份”和”任务的身份”是同一个东西吗?重试时该复用哪一个?
- 用户点”停止”时,你能保证已经写出去的产物被撤回吗?如果不能,取消这个动作到底承诺了什么?
参考答案
结论:把”等待”从连接上摘下来——长调用立即返回一个已持久化的任务句柄,任务成为服务端一等对象,客户端从”等待者”降级为”观察者”;所有副作用按幂等键收敛到同一个 taskId;取消只是意图,不是保证,所以”可能已执行”的处置规则必须是只查不重发。
作答框架(3–5 分钟):一句话结论 → 四层归因(协议形态 / 请求身份 / 状态宿主 / 语义理解)→ 核心方案(任务对象 + 幂等键 + 状态机 + 观察者模型)→ 失败路径与默认态 → 指标与三层能力归属。
问题拆解:现象 1 是请求身份缺失——重试没有幂等键,超时变成乘法器;现象 2 与 4 是状态宿主错误——状态活在调用栈里,进程或连接一断就没了;现象 3 是语义误解——把 cancel 当成 kill,服务端没有协作式取消点;现象 4 的根因(现象 1、2、4 共同的上游)是协议形态:同步阻塞把”任务时长”绑死在”连接时长”上,任何长于网关超时的任务在协议上根本不存在,调参只是把断点推远。
核心方案(MCP Tasks 扩展):
- 能力协商:服务端在
server/discover的capabilities.extensions中声明io.modelcontextprotocol/tasks;客户端在每次请求_meta的clientCapabilities.extensions中声明同一扩展。服务端返回任务前必须确认客户端声明过——规范明确要求”never return a task to a client that did not declare support”,未声明者走同步路径。 - 创建:命中长任务时返回
resultType: "task"的CreateTaskResult,含taskId、初始状态、ttlMs、pollIntervalMs。规范的关键约束是”任务必须在响应发出前完成持久化创建”——这条决定了崩溃恢复的能力边界,也是”持久句柄”名副其实的唯一条件。 - 状态机:
working/input_required/completed/failed/cancelled,后三者为终态,进入后状态不再变化。 - 轮询:客户端按
pollIntervalMs调tasks/get,终态时completed带result、failed带error。服务端可选通过notifications/tasks(经subscriptions/listen)推送完整状态,轮询是默认路径。 - 中途输入:状态为
input_required时,tasks/get返回inputRequests,客户端通过tasks/update提交inputResponses;未知或已满足的键忽略(天然幂等)。 - 取消:
tasks/cancel由服务端确认,“尽可能”执行——取消是协作式的,任务仍可能以非cancelled的终态结束。
关键执行流程:
- Agent 发起
tools/call,携带客户端能力声明与平台生成的idempotency_key(租户 + 工具 + 参数指纹 + 会话/步骤)。 - 网关把幂等键写进任务创建请求,并对同一键做 single-flight。
- MCP 服务先落库任务记录(status=working、ttl、owner、幂等键唯一索引),再启动执行器,最后返回
CreateTaskResult——顺序不能反。 - 执行器持续写状态与
statusMessage;需要审批时置input_required并写inputRequests。 - 客户端按
pollIntervalMs轮询;平台把 MCP taskId 投影成自己的任务视图,前端只看平台 task_id。 - 审批回来 →
tasks/update;服务端校验 input 与操作指纹一致后继续。 - 到达终态:
completed/failed/cancelled。 - 审计与对账:任务表与副作用台账(外部单号、构建号)按 taskId 关联,保留 30 天——与 TTL 是两套存储。
技术选型与备选方案:
| 方案 | 优势 | 代价 | 判据 |
|---|---|---|---|
| A. MCP Tasks 扩展 | 标准化句柄、input_required 原生支持、跨客户端一致 | 生态支持不全(Beta,目标 Core) | 主路径 |
| B. 平台自建 task API + 同步 MCP | 完全可控、不依赖客户端能力 | 每个客户端都要改,未来要迁移 | 旧客户端兼容路径 |
| C. 事件推送(webhooks / events 一类) | 省轮询 | 未合并进规范,无规范文本可依赖 | 不作为依赖,仅作未来优化点 |
选型结论:对外以 A 为主,内部抽一层 task 门面(平台 task_id ↔ MCP taskId),旧客户端走 B;C 属于观察项,不能写进架构约束。
方案取舍:
- 轮询 vs 推送:轮询简单、GET 天然幂等、服务端无状态;代价是 QPS。按本例算:2.4 万长任务/日、平均 8 分钟 → 稳态约 133 个在跑;1 秒轮询约 133 QPS 额外请求,2s→5s 阶梯退避加抖动可压到 40 QPS 以内。有推送能力时只对长尾任务转推送。
- TTL 短 vs 长:TTL 短省存储但客户端恢复窗口小。TTL 是执行期句柄的寿命,审计是 30 天合规存储,两者混用会让”任务查不到”和”审计丢数据”同时发生。
- 可续跑 vs 一次性:续跑需要检查点与幂等执行器,只对可重入工具开启;不可撤销副作用工具宁可失败也不续跑。
失败路径、边界与恢复:
- 网关超时重试:幂等键在服务端唯一索引兜底,冲突时返回已有 taskId 而非报错。最常见的落地漏洞是重试时生成了新幂等键——键必须在调用发起前生成并随重试复用。
- 创建成功但响应丢失:客户端不知道 taskId,只能按幂等键查询,绝不能重发创建请求。
- 服务端崩溃:任务从持久化恢复为 working;执行器无检查点则置
failed(明确失败),不能假装成功,也不能默默重跑有副作用的步骤。 input_required超时:必须有显式默认态,且默认 fail-closed:超时置failed并写reason=approval_timeout。默认 proceed 等于让”提交变更单”这类不可撤销操作绕过审批。- 取消后仍完成:记录两个字段——
cancel_requested_at与最终终态;终态不是cancelled时写失败原因。已写出的产物只能补偿,不能撤回。 - TTL 到期被删:客户端拿到 not found,规则是”未知即查询不重发”;平台自己的任务视图独立于 MCP TTL 保留。
超时、重试、幂等:三层超时——单次 tasks/get 传输层 5s、轮询总时长等于业务 SLA(如 30 分钟)、任务 TTL 覆盖 SLA 加余量。重试只对读类(tasks/get)做指数退避加抖动;tasks/cancel 幂等可重试;创建类请求只靠幂等键重试。
安全、权限、成本与可靠性:taskId 必须不可猜测并带租户前缀,tasks/get/update/cancel 全部校验 (tenant, caller, task.owner)——持久句柄本身就是权限边界,这是 Tasks 带来的新攻击面(IDOR);input_required 的确认必须绑定操作指纹,防”确认 A 执行 B”的确认漂移;审计三元组 (taskId, actor, decision) 中 actor 来自 IdP,不来自模型。成本主要是轮询 QPS 与两套存储;可靠性靠”任务表为唯一事实源 + 执行器租约与心跳”避免双执行。
评测指标与观测:重复执行率(同一幂等键产生多个外部单号的比例,目标 0)、任务状态收敛率(超 TTL 仍 working 的比例)、input_required 平均等待与超时率、取消生效延迟中位数、not found 率、端到端完成率、P95 轮询开销。
三层能力归属:模型负责判断”这个调用可能很久”、把进度翻译成人话、判断是否需要人工确认——全是概率性的,不能当保证;Agent 编排负责 taskId 生命周期、把 input_required 转成人工任务、恢复与重试策略、给用户投影任务视图;确定性系统负责任务表、幂等键唯一索引、状态机、TTL、租约、审计——这些必须是代码,不是提示词。
追问
追问 1:客户端不支持 Tasks 扩展,体验怎么统一?
答:服务端先用 server/discover 探测能力,未声明则走同步路径,但平台侧仍创建自己的任务对象,只是把 MCP 调用放在平台执行器里异步跑,前端拿平台 task_id 轮询。用户看到的是同一套任务视图,差异被 task 门面吃掉。代价是旧路径的执行器在平台侧,需要自己的超时与取消;这正是”能力协商”要分两层的原因——协议层协商 MCP 能力,产品层协商平台能力。
追问 2:任务跑到一半服务端重启,已经发生的外部副作用怎么处理?
答:副作用台账加检查点。每个有副作用的步骤执行前先占位((task_id, step_id, 参数指纹) 唯一索引,状态 pending),执行后回填外部单号,状态变 committed。恢复时按 step_id 查台账:committed 则跳过,pending 则查询外部系统确认(构建号/变更单号)后决定跳过还是补偿,查不到就置 failed 交人工。核心规则是”可能已执行”只查不重发——重发的代价是不可撤销的重复副作用。
追问 3:2.4 万个长任务一起轮询,会不会把服务端打挂?
答:轮询是读放大,要三层处理。① 客户端侧:遵守 pollIntervalMs、阶梯退避加抖动(避免整点惊群);② 服务端侧:按 taskId 做 single-flight 请求合并、状态缓存(读己之写要求不高,秒级陈旧可接受)、按租户限流;③ 架构侧:对超长任务优先用 notifications/tasks 推送替代轮询,把”每任务 1 QPS”降成”每任务 1 条消息”。
关键点
- 任务必须在响应前持久化,否则”持久句柄”是假的,崩溃恢复无从谈起。
- 幂等键是请求身份,taskId 是任务身份,两者各自唯一索引,且在创建前生成、重试时复用。
- 取消是协作式意图,终态可能不是
cancelled,必须同时记录”请求取消的时间”与”实际终态”。 input_required必须有显式超时默认态,对不可撤销操作默认 fail-closed。- taskId 即权限边界:get / update / cancel 三个入口都要做归属校验,否则句柄泄漏等于越权。
常见误区
- “把网关超时从 60 秒调到 600 秒”:只是把断点推远。连接仍然脆弱、网关内存仍被占、客户端体验仍然卡死,而 40 分钟的扫描照样超时。长任务是协议形态问题,不是参数问题。
- “重试加个 retry 策略就行”:没有幂等键的重试是放大器——一次超时变成 2–3 次构建,而且重试越积极、重复越多。幂等键缺失时,正确的动作是”不重试而是查询”。
- “cancel 返回 200 就是停了”:协作式取消只表示”收到意图”。对已提交的变更单、已发出的邮件,正确假设是”可能已执行”,处置方式是查证与补偿,而不是重发或声称已撤回。
小型实践(30–60 分钟)
用 FastAPI + SQLite 实现一个约 200 行的任务服务:POST /tasks(带 Idempotency-Key,唯一索引)、GET /tasks/{id}、POST /tasks/{id}/input、POST /tasks/{id}/cancel,执行器是一个可被中断标志打断的线程。写 5 个 pytest 覆盖:① 同一幂等键两次 POST 返回同一 taskId;② 轮询到 completed 并取回 result;③ input_required → update → 继续到终态;④ cancel 后终态为 cancelled;⑤ 杀掉进程重启后按 taskId 仍能查到状态。第 5 个用例是本题的核心考点——它一条就把”持久化创建”这条规范要求验证掉了。
延伸学习
- MCP 官方 Tasks 扩展总览:
modelcontextprotocol.io/extensions/tasks/overview(能力协商、CreateTaskResult、五态生命周期、协作式取消的措辞,本轮已核验)。 github.com/modelcontextprotocol/ext-tasks(扩展规范正文与 schema;正文未逐条核验,以仓库当前版本为准)。
S02 · 换成连接池中间件后,互斥锁同时被两个实例持有
题目 ID:Q-20261116-S02 | 分类:场景(非 Agent) | 一级类型:数据库与存储(兼属分布式系统) | 二级主题:连接池与连接复用、池化粒度对会话状态的影响
题目
业务背景:电商订单中台,PostgreSQL 16 主库加两只读副本,600 个应用 Pod(Go 服务,40 个微服务,3 种语言混部)。
系统规模:峰值 1200 QPS 读、300 QPS 写,日订单 240 万。
原架构:每个 Pod 应用侧连接池上限 10,峰值 6000 个客户端连接直连主库,max_connections=800,高峰期频繁出现 too many clients already,P99 40 ms。
改造:引入 PgBouncer,pool_mode=transaction,default_pool_size=40,主库 max_connections 收到 400。切换后连接数降到 320,P99 12 ms。
故障现象(切换后一周内):
- 日终对账任务用
pg_advisory_lock做互斥,切换后两个实例同时在跑,重复入账 1.8 万条; - 某服务在连接建立时执行
SET statement_timeout = '5s',切换后长查询不再被中断,一个报表查询跑了 42 分钟并占住后端连接; - 导出任务用
DECLARE ... CURSOR WITH HOLD分页,切换后游标在事务结束后消失,导出返回空结果。
目标:保留连接复用的收益,同时恢复正确性,且不要求 40 个服务一次性改完。
限制条件:不能改 PG 大版本、不能重启主库、不能要求所有服务同步上线、改造期间业务不能停。
需要取舍的问题:把所有流量都塞进 transaction 模式,还是按服务分级用两种池化模式;把互斥改成数据库行锁,还是给这些服务单独一条直连路径。
先思考
- 这三个现象有没有共同的根因?如果只用一个词概括被改变的东西,那个词是什么?
pg_advisory_lock的”锁”到底绑在什么对象上——事务、连接,还是会话?连接被归还池之后,它还在吗?- 连接池的价值是”少建连接”,那它为什么会影响正确性?它改变的到底是资源数量,还是别的东西?
参考答案
结论:transaction pooling 把连接从”会话级资源”降级为”事务级资源”,于是任何跨事务存活的状态都失去了宿主:会话级锁、SET 出来的 GUC、WITH HOLD 游标、PRESERVE ROWS 临时表、SQL 级 PREPARE 全部失效。修复方向不是调参数,而是把跨事务状态从连接上搬到数据上,并对确实需要会话语义的少数路径保留 session 池作为例外。
作答框架(3–5 分钟):结论(粒度改变作用域)→ 逐条对照官方特性表归因 → 三层方案(状态外置 / 模式分级 / 连接预算)→ 迁移顺序与回滚 → 指标。
问题拆解(对照 PgBouncer 官方 “SQL feature map for pooling modes”):
| 特性 | session pooling | transaction pooling | 本次故障 |
|---|---|---|---|
| 会话级 advisory lock | Yes | Never | 现象 1 |
SET / RESET | Yes | Never | 现象 2 |
WITH HOLD 游标 | Yes | Never | 现象 3 |
PRESERVE/DELETE ROWS 临时表 | Yes | Never | 潜在 |
SQL 级 PREPARE/DEALLOCATE | Yes | Never | 潜在 |
| 协议级 prepared plans | Yes | Yes(需 max_prepared_statements 非 0) | 易混淆点 |
ON COMMIT DROP 临时表 | Yes | Yes | — |
一个词概括被改变的东西:作用域。连接不再是”我的会话”,而是一段”借来的事务窗口”。锁、参数、游标都活在这个窗口之外,所以全部失效。
核心方案(三层):
- 状态外置(把跨事务状态搬到数据上)
- 互斥:会话级 advisory lock → 行级 CAS(
UPDATE ... SET locked_until = now() + lease WHERE id = ? AND locked_until < now())或带唯一约束的租约表加 fencing token。 - 会话参数:
SET→ 连接启动参数(PgBouncer 保证一组固定启动参数一致,超出部分用track_extra_parameters)或ALTER ROLE ... SET,让参数成为角色属性而非语句副作用。 - 游标:
WITH HOLD→ keyset 分页(WHERE (updated_at, id) > (:last_updated_at, :last_id)),游标状态放客户端。 - 临时中间结果:
PRESERVE ROWS临时表 → 显式ON COMMIT DROP,或落 UNLOGGED 表并配清理任务。
- 互斥:会话级 advisory lock → 行级 CAS(
- 模式分级:绝大多数 OLTP 请求走 transaction 池;确有会话语义的(
LISTEN、长事务报表、会话锁密集)单独建 session 池的 database 条目,DSN 区分。混合模式是官方支持的常规用法,不是 hack——关键是把”为什么这个服务必须用 session 池”写进配置注释与到期复核项。 - 三层连接预算:应用池(每 Pod 10)× Pod 数 → PgBouncer 后端池(按后端核数估,本例 40)→ PG
max_connections(含 superuser reserved 与复制连接)。关系必须是”前面宽、后面窄”,这正是引入 pooler 的意义:客户端并发与数据库连接解耦。
关键执行流程:
- 先接入 PgBouncer 但不切主流量,用影子 DSN 跑只读流量,观察
SHOW POOLS(cl_active/sv_active/sv_idle/cl_waiting)与SHOW STATS。 - 静态扫描加运行期取证找会话状态用法:代码搜
advisory_lock|SET |CURSOR WITH HOLD|PREPARE,短期开log_statement=all采样,用pg_stat_activity看长事务与 idle in transaction。 - 按服务改造 → 单服务灰度切 transaction 模式 → 观察 24 小时(业务指标与连接指标一起看)。
- 无法外置的服务迁到 session 池,登记原因与复核日期。
- 全量切换后收紧
max_connections,把余量留给运维、复制与故障切换。
技术选型与备选:
| 方案 | 优势 | 代价 |
|---|---|---|
| PgBouncer(transaction) | 成熟、内存占用低(约 2 kB/连接)、支持在线重载与在线重启 | 会话语义受限,需改代码 |
| 应用侧池化直连 | 语义完整、无额外组件 | 6000 连接打满 PG,fork 成本与内存放大 |
| 云托管 multiplexing pooler | 免运维 | 语义同样受限且行为更不透明,故障时难定位 |
取舍结论:PgBouncer + 状态外置为主,session 池做例外,接受”两套池要运维”的成本。
失败路径与边界:
- 互斥从锁改成 CAS 后仍有并发窗口:CAS 只保证”谁先写成功”,业务层必须再加唯一约束兜底(如
(biz_date, account_id)唯一),否则 CAS 写错就是静默重复入账。 - 长事务占连接:transaction 模式下长事务仍占后端连接;PgBouncer 侧
server_idle_timeout/query_wait_timeout与服务端idle_in_transaction_session_timeout是两层不同防线,都要设。 - 残留状态:transaction 模式不在事务边界做会话重置,这既解释了
SET为何不生效,也解释了为什么”脏状态”不会串给别人(事务边界把它切断了)。这正是”失效”与”隔离”同时成立的原因。 LISTEN/NOTIFY:transaction 模式下LISTEN为 Never、NOTIFY技术上可用但语义残缺;需要LISTEN的服务必须走 session 池或独立常驻连接。- 回滚安全性:DSN 切回直连即可恢复。因为改造是”单向兼容”的(keyset 分页、CAS 互斥在直连下同样正确),回滚不会引入新故障——这一点应在改造设计时就有意保证。
性能与可用性分析:连接复用消掉 PG 的 fork 成本与每连接内存放大,P99 从 40 ms 降到 12 ms;代价是多一跳网络与一个新的单点。部署上每个节点一个 sidecar 或 DaemonSet,避免 PgBouncer 本身成为全局单点;cl_waiting 长时间大于 0 说明后端池太小,maxwait 上升说明排队已经在影响尾延迟。
验证指标:cl_waiting、avg_wait_time、后端连接数、事务时长分布、idle in transaction 数量、重复入账条数(业务指标,最硬的验证)、对账差异为 0 的连续天数。
追问
追问 1:为什么不直接把应用侧连接池调小,非要引入中间件?
答:调小可以降连接数,但会把每个 Pod 的并发卡在自己的池上,且池大小与副本数耦合——扩容时总连接数又涨回去。pooler 的价值是把”客户端并发”和”数据库连接”两个数字解耦:前面可以很宽(6000 个客户端连接很便宜,2 kB 一个),后面必须很窄(后端连接贵)。另外 pooler 提供统一的排队、超时与观测面,这是散落在 40 个服务里的连接池给不了的。
追问 2:transaction 模式下 prepared statement 到底能不能用?
答:要区分两种。协议级 prepared plans 在 transaction 模式下为 Yes,前提是 PgBouncer 侧 max_prepared_statements 设为非 0,由 PgBouncer 管理服务端的语句名——大多数驱动默认走这条路径,所以”切了 pooler 之后 prepared statement 还能用”。SQL 级 PREPARE / DEALLOCATE 为 Never,因为名字绑在会话上。判断依据不是”我用了 prepared statement”,而是”谁在管理这个名字”。
追问 3:业务确实需要会话级 advisory lock,只有改代码一条路吗?
答:两条路。一是把这些服务迁到 session 池,代价是连接数回升、且要单独运维一个池;二是改成行级锁/租约表加 fencing token,推荐后者——它把互斥的正确性从”连接是否存活”移到”数据状态”,本来就是更稳的模型,而且在主从切换、Pod 重启等场景下不会出现”锁跟着连接一起消失”的隐式失效。会话锁的正确性依赖一个不写在契约里的假设(连接不被回收),这类假设在引入任何中间件时都会破。
关键点
- 池化粒度决定会话状态的作用域:这是语义变更,必须按变更管理流程灰度,不能当性能优化直接全量。
- 官方特性表是判据,不是经验法则:advisory lock / SET / WITH HOLD / SQL PREPARE 在 transaction 模式一律 Never,协议级 prepared plans 是例外。
- 三层连接预算前宽后窄:应用池总和远大于后端池,后端池远小于
max_connections。 - 互斥的正确性应落在数据上,而不是连接上;CAS 之外还要有业务唯一约束兜底。
- 例外路径用 session 池,不要用调参掩盖:改
server_reset_query之类的参数不能让会话锁变正确。
常见误区
- “连接池只是性能优化,不影响正确性”:它改变的是状态作用域,属于语义变更。跳过灰度与业务对账,就会像本例一样”性能指标全面变好,同时开始重复入账”。
- “在每个事务开头重新 SET 一次就行”:能工作,但把参数变成每事务成本、容易漏、且掩盖了真正的问题(参数应该属于角色或连接,不属于某条语句)。
- “pooler 挂了切回直连就行”:直连会瞬间打出 6000 个连接打满
max_connections,把一次组件故障放大成数据库级故障。回滚路径必须先算容量、先限流。
小型实践(30–60 分钟)
本地 docker 起 PostgreSQL 加 PgBouncer(transaction 模式),写一个脚本验证四件事:① session 模式下两个连接用 pg_advisory_lock 互斥有效;② 切 transaction 模式后复现”两个客户端都拿到锁”;③ 改成 UPDATE ... WHERE locked_until < now() 的 CAS 后互斥恢复;④ 并发压测时用 SHOW POOLS 观察 cl_waiting 随并发上升。第 ② 步能在十分钟内让你对”作用域”这件事形成肌肉记忆。
延伸学习
- PgBouncer 官方《Features》页 → “SQL feature map for pooling modes”:逐项列出各特性在三种池化模式下的可用性(本轮已核验表格)。
- PgBouncer 官方《Config》文档:
pool_mode、default_pool_size、max_prepared_statements、server_reset_query的语义与默认值(参数细节未逐条核验,以所部署版本为准)。
L01 · LeetCode 946. 验证栈序列
题目 ID:Q-20261116-L01 | 分类:LeetCode | 数据结构与算法:栈与队列(贪心模拟)
题目
题目 ID:Q-20261116-L01
LeetCode:题号 946,中文名「验证栈序列」,英文名 Validate Stack Sequences,难度 Medium。
难度标注说明:官方页面本次抓取未渲染难度标签(连续多次出现同一现象),medium 为按 LeetCode 标准分类记录的结论,未直接核验。
官方链接:https://leetcode.com/problems/validate-stack-sequences/ (本轮已核验页面内容)
题目描述:给定两个整数数组 pushed 和 popped,二者的值互不相同,且 popped 是 pushed 的一个排列。判断是否存在一串 push 与 pop 操作,从一个初始为空的栈出发,先按 pushed 的顺序依次压入全部元素,并能在过程中按 popped 的顺序弹出全部元素。
输入:pushed: int[],popped: int[]
输出:bool——该弹出序列是否可能
约束:
1 <= pushed.length <= 10000 <= pushed[i] <= 1000pushed的所有元素互不相同popped.length == pushed.lengthpopped是pushed的一个排列
示例 1:
输入: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出: true解释: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1示例 2:
输入: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出: false解释: 1 不能在 2 之前被弹出。主要考察的数据结构与算法模式:栈 + 贪心模拟;“能匹配就立即匹配”的局部决策,配交换论证证明其不损失可行性。
先思考
- 如果
popped[0] = x,那么 x 之前的所有元素一定已经入栈了,而且它们必须等到 x 之后才能弹出。这说明在整个过程中,栈里元素的相对顺序被什么约束住了? - 模拟进行到任意时刻,“下一步能做的动作”有几种?除了”继续 push 下一个”和”pop 栈顶”,还有第三种可能吗?
- 如果此刻栈顶正好等于下一个待弹出的值,而你选择先 push 新元素,这个待弹出的值会被推到哪里去?它还有机会先出来吗?
参考答案
题号:946 | 中文名:验证栈序列 | 英文名:Validate Stack Sequences | 难度:Medium 官方链接:https://leetcode.com/problems/validate-stack-sequences/
解题思路(直观方案及其局限):最直接的想法是枚举所有 push/pop 交错顺序,检查能否产生 popped。push 与 pop 的交错方案数是卡特兰数量级,n=1000 时完全不可行;而且大量分支在很早就会出现矛盾,枚举做了大量无用功。
推荐方案的推导:注意到两个结构性事实。第一,push 的顺序是强制的——你只能按 pushed 的顺序压入,没有选择。第二,pop 也是被 popped 强制的——每一步”下一个该弹出的值”是固定的。所以真正存在自由度的只有”什么时候 pop”这一个决策,而且这个决策有一个贪心判据:
只要栈顶等于下一个待弹出值,就立即弹出,不需要犹豫。
理由是局部的、可验证的:假设此刻栈顶是 popped[j],而你决定先不弹、继续 push 后续元素。由于后续元素都会被压在它上面,popped[j] 只能等这些新元素全部弹完之后才能出来,也就是它会被延后到至少第 k 个新元素之后才可能弹出——这与”popped[j] 就是下一个待弹出值”矛盾。所以推迟弹出永远不可能更好,立即弹出不损失任何可行性。这就是交换论证:把”推迟的 pop”和”紧随其后的 push”交换次序,结果状态不变或更优。
于是算法是:遍历 pushed,每压入一个元素后,用 while 反复检查栈顶是否等于 popped[j],相等就弹出并令 j += 1(必须用 while 而不是 if,因为一次 push 可能触发连续多次弹出,如 [1,2,3] 弹 [3,2,1])。遍历结束后,若 j == len(popped) 则全部弹出成功,返回 true。
正确性说明:维护不变式——处理完 pushed 的前 i 个元素并执行完所有可执行的弹出后,栈中保存的是”已入栈但尚未到弹出时机”的元素,且 popped[0..j-1] 已按序弹出。① 必要性:若存在某个合法操作序列,则由上面的论证可知把其中”能弹而未弹”的动作提前不会破坏可行性,因此贪心序列也是合法的。② 充分性:若贪心结束时 j == n,则贪心过程本身就构造出了一个合法的 push/pop 序列,故 popped 可行。③ 若结束时 j < n,说明还有元素没弹出但 pushed 已耗尽,栈顶与 popped[j] 不匹配,而此后既不能 push 也不能 pop(pop 只能从栈顶取),故不可行。
复杂度:时间 O(n)——每个元素恰好入栈一次、出栈至多一次,while 的总执行次数受 n 约束;空间 O(n)——栈最多容纳 n 个元素。
Python 参考代码:
class Solution: def validateStackSequences(self, pushed: list[int], popped: list[int]) -> bool: stack: list[int] = [] j = 0 n = len(popped)
for x in pushed: stack.append(x) # 一次 push 可能触发连续多次弹出 while stack and j < n and stack[-1] == popped[j]: stack.pop() j += 1
return j == n关键边界情况:
n == 1:push 后立即匹配,返回 True;- 全部先 push 再逆序 pop(
pushed=[1..5],popped=[5..1]):合法,栈深度达到 n(峰值); popped == pushed:同样合法——每个元素 push 后立即 pop,栈深度始终为 1。这两种是”栈深度的两个极端”,都可行,不要误以为同序弹出不可能;- 中途栈空:
while条件必须先判stack非空,否则stack[-1]越界; j越界保护:j < n必须写在条件里,否则全部弹出后继续比较会索引越界;- 元素值可以为 0(约束下界是 0),不要用 0 当”空栈”哨兵。
测试用例:
| # | pushed | popped | 期望 | 说明 |
|---|---|---|---|---|
| 1 | [1,2,3,4,5] | [4,5,3,2,1] | True | 官方示例 1 |
| 2 | [1,2,3,4,5] | [4,3,5,1,2] | False | 官方示例 2 |
| 3 | [1] | [1] | True | 单元素下界 |
| 4 | [2,1,3] | [3,1,2] | True | 需要”弹到中途再 push” |
| 5 | [1,2,3] | [1,3,2] | True | 一次 push 后立即弹出,验证 while 的必要性 |
追问
追问:如果再加一个约束——栈的容量上限为 k,怎么改?
答:在每次 push 后(以及 push 前)检查 len(stack) > k,一旦超限立即返回 False。注意判定的位置:容量约束会改变可行性,因为某些”先攒着再弹”的方案被禁止了,而贪心的”能弹就弹”恰好是最省栈空间的策略——贪心解的峰值栈深度是所有合法方案中最小的,所以”贪心下都不超限”是”存在合法方案不超限”的充要条件。这一点是本题从”判定可行性”升级为”判定带资源约束的可行性”的关键,也是面试官最常用的加难方式。
关键点
- push 顺序与 pop 顺序都是强制的,唯一的自由度是”何时 pop”,这是贪心成立的前提。
- 能弹就弹不损失可行性,论证方式是交换论证(把推迟的 pop 与紧随的 push 交换)。
- 必须用
while而不是if:一次 push 可能解锁连续多次弹出。 - 循环条件要同时判空栈与
j < n,两个都是越界来源。 - 复杂度账:每个元素进出栈各一次,
while的总次数被 n 摊还,整体 O(n) 而非 O(n²)。
常见误区
- 用
if代替while:pushed=[1,2,3]、popped=[3,2,1]会判错——push 3 之后只弹一次就继续遍历,而pushed已耗尽,最终j=1 != 3返回 False。这是最高频的实现错误。 - 试图用”逆序对”或”位置关系”直接判定:栈序列可行性不是简单的偏序检查,
popped中任意两个元素的相对顺序都要结合它们在pushed中的位置判断,很容易漏掉跨段约束;模拟法把这层推理交给数据结构,成本只有 O(n)。 - “合法序列只能是某一种固定形态”:
popped == pushed(逐个进出,栈深恒为 1)与popped == reversed(pushed)(全进全出,栈深为 n)都是合法的。真正的约束只有一条——每个元素弹出时必须位于栈顶。用”是否逆序""是否同序”这类形态判断代替模拟,会在大量中间形态上判错。
延伸学习
- LeetCode 946 官方题解页(多种解法与图示;题解正文本轮未核验,仅核验题目页的描述、示例与约束)。
- 同族训练方向:括号匹配、字符串消除、嵌套调用的配对校验——它们共享”用栈维护未闭合结构 + 能匹配就匹配”的同一模式。
与 AI Agent 工程的关联(仅在自然关联处说明)
Agent 的嵌套工具调用(父调用未返回、子调用先完成)在协议层就是一个栈序列:子调用必须按”后进先出”的闭合顺序完成,而完成顺序又受编排器调度影响。判断”某组交错完成事件是否可能由一次合法的嵌套调用产生”,与本题是同一个判定问题——这是本题唯一自然的迁移点,其余场景不必强行联系。
延伸资料(当日重要主题)
- Protocol Buffers 官方文档《proto3 Language Guide》→ “Updating A Message Type”(protobuf.dev):wire-safe / wire-unsafe / wire-compatible 三档变更、字段编号不可复用、
reserved规则、未知字段保留与丢失场景。本轮已核验原文,B01 的判据全部来自此页。 - Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023(arXiv:2309.06180):KV cache 动态增长、碎片与冗余复制限制 batch size,分页化实现”近零浪费 + 跨请求共享”,同延迟下吞吐 2–4×。本轮已核验摘要原文。
- MCP 官方 Tasks 扩展总览(modelcontextprotocol.io/extensions/tasks/overview):能力协商、
CreateTaskResult、五态生命周期、“任务在响应前持久化创建”、协作式取消。本轮已核验;规范正文在github.com/modelcontextprotocol/ext-tasks,未逐条核验。 - PgBouncer 官方《Features》→ “SQL feature map for pooling modes”(pgbouncer.org):session / transaction / statement 三种模式对
SET、LISTEN、WITH HOLD游标、会话级 advisory lock、SQL 级PREPARE、协议级 prepared plans 的逐项支持情况。本轮已核验表格。 - Linux 内核文档《Control Group v2》CPU 章节与《CFS Bandwidth Control》(docs.kernel.org):
cpu.max的 quota/period 语义、cpu.stat的nr_periods/nr_throttled/throttled_usec、节流后”until the next period when the quota is replenished”的原文表述。列为资料备查——本主题已于 2026-10-14 出过题,本轮不再出,但它是理解”窗口式预算”的最好材料。
当日重点
- 上限都有发放窗口:字段编号按”线格式身份”发放,CPU 配额按 100ms 周期发放,KV 显存按”每 token”发放,任务句柄按 TTL 发放,连接池按事务边界发放。谈上限必须同时说清”按什么粒度发、谁来计量”。
- 平均值与声明都不是保证:平均 CPU 利用率看不见 100ms 窗口内的耗尽,
read-only声明不等于执行保证,“上下文窗口 128K”不等于并发容量,cancel返回 200 不等于已停止。判断一个系统时,先找它的计量口径,再判断这个口径能不能支撑你的决策。 - 状态必须有宿主:会话状态宿主是连接,任务状态宿主是持久化存储,KV 宿主是显存,字段身份宿主是编号。任何”把宿主换掉”的改造(引入 pooler、改协议形态、换推理引擎)都是语义变更,必须按变更管理走,而不是当性能优化。
- 静默错值比崩溃危险:编号复用、位宽截断、缺片聚合、重复入账——共同点是监控全绿、日志无异常、只有对账能发现。设计时应该主动问”这类错误会以什么形式暴露”,答不出来就说明缺少对账层。
- 三层能力归属要能当场说清:模型给的是概率性判断,编排层给的是流程与生命周期,确定性系统给的是状态机、幂等键与约束。把本该属于第三层的保证写进提示词,是所有 Agent 事故的共同起点。
运行信息
本次参考的历史资料:题目索引.md(140 条 / indexed_runs: 26 / last_updated: 2026-11-13)、题库配置.md(v9)、精选/README.md(4 条精选,未自动精选)、README.md 导航表、最近 30 天题目行(2026-10-17 至 2026-11-13)用于去重与轮换判断。未通读更早的训练正文。
配置读取状态:成功;实际生效版本 v9;无暂停类型;观察项 8 项均未标记「允许试学」,本轮未从中出题。
去重结果:最近 30 天(2026-10-17 至 2026-11-16)内无同题、换皮题或同 LeetCode 题号重复;三处邻近题目已在文件开头列明并给出区分点。滚动窗口 2026-08-16 至 2026-11-16 内最早条目为 2026-10-10,无需剪除任何索引行。
LeetCode 轮换说明:连续多轮已使用哈希集合、对撞双指针、堆 / Top-K、矩阵模拟、线性 DP、二叉树 BFS、单调队列、栈设计、原地数组、区间 DP、链表、Trie、差分、回溯、并查集、图论、二分。本轮按上轮建议选择”栈与队列应用型”,取 946 而非 232:232 是纯结构转换(设计题),946 需要贪心正确性论证,考察层次更高。946 在历史索引中未出现过。
L01 代码验证:官方两例加三个自建用例全部通过;另以 2000 组随机排列对拍(对照”枚举所有合法弹出序列”的独立实现,n ≤ 7),结果一致。
核验状态:LeetCode 946 题目页、protobuf proto3 指南、PagedAttention 摘要、MCP Tasks 总览、PgBouncer 特性表、cgroup v2 / CFS 带宽控制文档均为本轮实际抓取核验(难度标签未渲染、ext-tasks 规范正文未逐条核验、vLLM 前缀缓存文档与 PgBouncer 配置参数未逐条核验,已在正文对应位置标注)。
归档范围:仅本地 Obsidian 库,未做任何远端同步验证;不声称远端已同步。