系列导航：面试索引 · 代码评审与 Agentic 研发

资深候选人的强答，应把算法正确性、资源成本、失败语义和验证办法连成一条链。 写出一个堆或画出消息队列，只完成了其中一段。沿优化、执行与存储追问资源预算；AI 方案须单列待验证假设。

所有容量数字均为面试题设或演算，未测得的数据不作性能承诺。个人案例保留【模板】。

一、先固定问题，再决定展示哪一层能力

1. 开场题：面对陌生问题，如何建立可检验的回答

强答要点：先固定输入、输出及错误条件，再给最低可行解；用一个约束排除明显不可行方案，然后选择一个关键路径深入。算法题需要循环不变量和复杂度前提，系统题需要成功确认点、持久化边界及超时后的行为。二者都应给出推翻自己方案的反例。

追问：面试官不提供规模怎么办？提出两组假设，例如内存可容纳与不可容纳，说明跨越哪条边界会改变算法；对方要求立即给方案怎么办？先声明一个最小假设并给主路径，再明确最可能推翻选型的条件。

差答：“先上分布式”“所有请求最终一致即可”“按经验用某产品”。

2. 数量题：每秒请求数与并发数如何约束架构

强答要点：“日增 10 TB、历史 1 PB、1000 并发、P99 小于 1 秒”不足以选型。在线分析处理（Online Analytical Processing，OLAP）要区分点查、固定报表和任意交互查询。每秒查询数（Queries Per Second，QPS）描述到达率，并发数描述在途数量；P99 是 99 分位延迟，不能直接当成平均延迟代入排队公式。

在稳定、统计口径一致的系统中，利特尔定律（Little’s Law）给出平均在途数 L = 到达率 λ × 平均停留时间 W。若到达率是 1000 次／秒，平均停留时间为 0.2 秒，则平均在途约 200；这不能推出 P99，也不能保证突发时只有 200 个请求。

按十进制单位演算，10 TB／日约为 116 MB／秒平均原始输入。如果题设再给 5 倍峰值，则峰值约 580 MB／秒；压缩、索引、复制和后台重写要分别计量。不要先乘一个没有依据的“数据库膨胀系数”，也不要把平均摄入吞吐当成峰值写入能力。

追问：CPU 利用率只有 40%，为什么 P99 很高？检查队列等待、单核串行路径、热点分片、远端读取与锁等待，不能只看整机均值；扩容两倍，吞吐能否翻倍？识别可并行部分与共享瓶颈，检查元数据、网络、热点及后台维护是否也增加容量。

差答：把“1000 并发”等同“1000 QPS”；用 P99 替代平均值；给每个组件分配同样的 P99 后相加。

二、通用算法题要展示可迁移的不变量

3. 二分与窗口：何时可以删除一半搜索空间

强答要点：二分查找（Binary Search）依赖单调判定，滑动窗口（Sliding Window）依赖扩展与收缩对合法性的可预测影响。先说明性质，再写模板；代码形状相似不意味着成立条件相同。

左边界采用半开区间 [lo, hi)，保持 lo 左侧都小于目标，hi 及右侧都不小于目标。终止时 lo = hi，返回的是插入位置，范围是 0 到 n。使用无符号长度时，空数组上不要先计算 n - 1。

 1#include <cstddef>
 2#include <span>
 3
 4std::size_t lower_bound_index(std::span<const int> a, int target) {
 5    std::size_t lo = 0;
 6    std::size_t hi = a.size();
 7    while (lo < hi) {
 8        const auto mid = lo + (hi - lo) / 2;
 9        if (a[mid] < target) {
10            lo = mid + 1;
11        } else {
12            hi = mid;
13        }
14    }
15    return lo;
16}

这个片段使用 C++20，只建立左边界语义；没有验证输入已排序，也没有承诺并发修改安全。现场测试至少覆盖空数组、全部相等、目标小于最小值和大于最大值。若题目要“是否存在”，还要检查返回位置小于 n 且元素等于目标。

对于正数数组的区间和约束，扩展右端不会使和下降，可以据此收缩左端。加入负数后该性质失效，应考虑前缀和、单调队列或其他结构。对乘积约束，还需要处理 0、负数和溢出；不能仅把“和”改成“乘积”。

追问：如何找最大可行资源配置？先证明可行性随参数单调，再把答案搜索转化为二分；存在离散跳变不影响单调性，但多峰目标不适用；窗口最大值为什么能线性完成？单调队列中，每个下标最多入队和出队一次，总操作次数为 O(n)，不是每个循环都只做常数工作。

差答：背“左闭右开”但无法说出不变量；把任意区间约束套成双指针；把把返回“最后一个 ≤ 目标的位置”的函数叫作标准 upper_bound。

4. 堆与选择：Top K 的答案在哪里完成聚合

强答要点：题设是 1 TB 文本、1 GiB 内存，求精确词频前 10。前 K 项（Top K）先区分按数值选元素与按频次选键。前者可用选择算法；后者必须先完成同键计数。小顶堆只解决从完整计数结果中保留候选，不解决统计状态超内存。

精确离线方案可以先按完整词键做哈希分区，使同一个词只属于一个分区，再逐分区计数、选局部前 10，最后归并候选。哈希碰撞只让不同词进入同一分区，分区内仍比较完整键；不能用哈希值替代原词判等。

分区数由唯一键数、平均键长、装载因子、计数器和分配开销决定。一个 1 GB 原始文件不保证能放进 1 GiB 哈希表；超过预算时应递归分区或外排。单一高频词会使文件很大但状态很小，不能把文件大小倾斜与唯一键状态倾斜混为一谈。

同键已经归到唯一分区时，局部前 K 可覆盖全局前 K：一个键若在自己的分区严格落后于 K 个键，它也无法进入全局前 K。遇到频次相同，必须统一第二排序键；若要求“所有并列第 K 名”，候选数量可能超过 K。

任意按行切分则不成立。取 K = 1：分片 A 为 x:6、a:7，分片 B 为 x:6、b:7；各取局部第一只得到 a、b，但全局第一是 x:12。这个反例足以说明需要先做跨分片同键归并。

追问：只选数组前 K 个数呢？小堆 O(n log K)、原地快速选择期望 O(n)、排序 O(n log n)；需要有序输出时还要对候选排序；哈希分区遇到攻击性键分布怎么办？保留分区统计、限制单分区资源，换种子只能缓解某些碰撞，必要时回退外排；不能保证把同一个键拆散后仍直接取局部前 K。

差答：“固定切 1000 份即可”“先算每个机器的前 10 再合并”“用 HyperLogLog 找热点”。

5. 图与动态规划：状态压缩必须保持未来决策所需信息

强答要点：有向无环图（Directed Acyclic Graph，DAG）调度先维护未完成前驱数，只有前驱全部成功的任务才能进入就绪队列。拓扑排序（Topological Sort）只是依赖顺序，不负责并发额度、失败恢复和外部副作用。

按邻接表存图，入度法处理所有点边的时间为 O(V + E)。若处理点数少于 V，只能推出剩余子图存在环或被环阻塞；要给出环上具体节点，还需要进一步搜索，不能把所有剩余节点都标为环成员。

动态规划（Dynamic Programming，DP）则要先说明状态是否覆盖未来决策。0/1 背包一维数组按容量倒序更新，是为了让本轮读取仍来自上一轮物品状态；正序会让当前物品在同一轮被重复使用，变成另一个问题。

最长递增子序列（Longest Increasing Subsequence，LIS）的尾值数组保存各长度下的最小末尾，不必形成原数组的一条真实子序列。若要恢复路径，还需前驱及索引信息。能说清“压缩掉了什么”比复述转移公式更能证明理解。

追问：图很深，递归搜索有什么风险？调用栈可能随深度增长；用显式栈保留状态，同时仍需访问标记避免重复与环；查询优化器能直接用普通背包吗？连接重排涉及关系子集、物理属性和语义约束，状态要覆盖后续组合所需条件，不能只保留一个最便宜标量。

差答：把拓扑序当成完整调度系统；把“用了 DP”当成最优性证明；看到状态很大就任意丢弃维度。

6. LRU 与线程池：常数复杂度不等于有界服务时间

强答要点：哈希表定位加双向链表维护次序，查找与更新是期望 O(1)；哈希退化、内存分配、锁竞争不属于这个常数承诺。容量为 0 时直接拒绝存储，不能从空链表取尾节点。生产缓存通常按字节计费，并把过期与淘汰分开。

分片锁可以减少争用，却把全局严格 LRU 改成分片内近似策略。访问本身会修改链表，因此读多也可能争抢锁。是否值得维持严格次序，要比较命中收益与元数据写入成本。

线程池同样要先约束队列。无界任务队列只把过载延迟成内存耗尽；提交接口应返回接受或拒绝，携带截止时间，并定义关闭后的行为。任务异常必须捕获并传播到结果通道，不能任由异常穿出工作线程函数。

Redis 官方说明其 LRU 淘汰采用采样近似，并通过配置调整精度；这支持“策略存在实现成本”的论点，不支持“近似策略总比严格策略好”。见 Redis 淘汰策略。

追问：工作线程向同一线程池提交子任务并阻塞等待，会发生什么？全部工作线程都等待尚未执行的子任务时可能饥饿死锁，需异步依赖或执行策略调整；取消任务时如何释放资源？区分未开始、执行中和已完成状态；协作式取消需要算子检查点，不能假设删除队列元素就终止了执行。

差答：“get／put 都 O(1)，所以性能不会有问题”“析构时 join 就能优雅退出”“队列满了让调用者一直等”。

三、数据库算法要沿着内存、I/O 与语义展开

7. 哈希连接：线性复杂度有哪些隐藏条件

强答要点：构建侧 80 GB、内存 16 GB 且键倾斜，先指定连接类型和键语义，再决定构建侧。内连接通常优先考虑过滤后体积较小的一侧，但选择受连接方向、外连接输出规则和物理属性约束；不能只按原表行数选。

在哈希分布合适、探测代价可控的条件下，工作量可表示为期望 O(B + P + Z)，其中 B、P 是两侧行数，Z 是输出行数。多对多热点会使 Z 远大于输入，“哈希连接是 O(n)”不能隐藏输出成本。

超内存可以做分区哈希连接（Grace Hash Join）：两侧按相同规则分区，逐对装载处理；过大分区继续划分或回退。分区和读回增加临时写入与读取，外溢（Spill）需要磁盘配额、取消清理及错误传播，不是一个布尔开关。

热点键会使相同哈希分区持续超限，换更多分区也不会把同键自动分开。可识别热点单独处理，或者在保证配对覆盖且不重复的前提下分块。网络倾斜与输出爆炸要分别解决；结果本来就有数十亿行时，调度无法把它变成轻量查询。

追问：广播连接与分区连接如何选择？广播构建结构到每个接收端，网络总量及每节点内存随副本数增加；分区会重分布两侧，保留本地性可改变成本；NULL = NULL 是否匹配？普通 SQL 等值不匹配；空值安全等值连接另有语义。字符串还要固定排序规则及哈希与相等比较的一致性。

差答：“小表 build 大表 probe”“分区足够多就不会倾斜”“加 Bloom 就能解决连接成本”。

8. 外部排序：归并路数由内存和设备共同决定

强答要点：排序 1 TiB 输入、可用内存 8 GiB，先生成有序段，再多路归并。若 8 GiB 全部可用于输入排序且忽略元数据，初始约有 128 段；这是理想下界式估算。实际要扣除排序键展开、指针数组、压缩缓冲和执行框架预留。

设有 R 个段，归并扇入为 F，归并轮数约为向上取整的 log_F(R)。F 受每段输入缓冲、输出缓冲、文件句柄和并行任务限制；在共享磁盘或远端对象存储上，也受请求数量和带宽竞争约束。不能默认“开 128 个文件同时读”就是最快方案。

若每一轮都完整读写 N 字节、记录布局不变，生成段加 p 轮归并的读写量约为 2N(1 + p)。最终结果流向下游时可省最后一次物化写入；压缩、变长布局或提前终止会改变字节数。这是简化成本推导，不是设备耗时预测。

DuckDB 在 2025 年 9 月介绍了随 v1.4.0 发布的排序重设计，复用可外溢的页布局并重做执行路径。它说明工程优化会跨越内存管理与算子边界；不意味着经典归并成本模型失效。见 DuckDB 排序重设计。

追问：仅需要 ORDER BY ... LIMIT 100 呢？先考虑有界堆或局部候选，不能默认完整外排；大偏移分页和并列语义会增加所需候选；多路归并用堆还是败者树（Loser Tree）？二者都可做到每条记录 O(log F) 更新，比较器成本、分支与布局决定常数，按实际键类型验证。

差答：“归并排序 O(n log n)，所以选它”“内存用满即可”“临时空间永远等于输入两倍”。

9. Bloom 与 Cuckoo：允许假阳性，不能偷换集合语义

强答要点：先明确过滤器只做成员资格预判。标准 Bloom 在正确构建、查询且未错误清位时，可以判定“一定不存在”或“可能存在”；后者仍需精确存储确认。过滤器不返回原元素，也不能作为精确去重集合。

对 m 位、n 个插入元素、k 个近似独立均匀哈希，假阳性率近似为 (1 - exp(-kn/m))^k；最佳 k 近似为 (m/n) ln 2。给定目标误判率 p，每元素位数近似为 -ln(p)/(ln 2)^2。这些近似依赖模型，不覆盖恶意输入和错误并发实现。

若 n = 10 亿、p = 1%，约需 9.6 bit／元素，位数组约 1.2 GB，k 约为 7。这个预算不含构建临时结构和版本副本；如果每次请求都远端读取过滤器，预判的网络成本可能吞掉收益。

删除不能直接清 Bloom 的位，因为其他元素可能共享它。计数布隆过滤器（Counting Bloom Filter）用计数器支持受约束删除，但增加空间并需防溢出。不可变文件常可在重写时重建过滤器，未必需要可删除结构。

Cuckoo Filter 存储短指纹并检查候选桶，支持插入和删除，但接近容量时插入可能失败。删除要求有正确的成员管理，不能仅凭一次阳性就删除任意未插入键，否则可能误删碰撞指纹。见 CoNEXT 2014 论文。

追问：更新期间如何避免新键被误判为不存在？先发布覆盖新键的版本，或对未覆盖时间段旁路查询；“理论无假阴性”不能替代发布协议；如何决定是否启用过滤器？比较负查询比例 × 可省精确读取成本，与哈希、访问过滤器、构建和分发成本。

差答：“过滤器有误判，所以可能把真实数据漏掉”“Cuckoo 支持删除，因此任意阳性都可以删”“1% 假阳性等于整体准确率 99%”。

10. HyperLogLog：可合并的统计状态不等于可撤回的统计状态

强答要点：HyperLogLog（基数估计草图，HLL）把均匀哈希分桶，保存各桶观察到的秩，再通过估计器还原基数。它估计不同值数量，不回答“用户 x 是否存在”，也不提供用户频次。

经典分析给出相对标准误差约为 1.04/sqrt(m)，m 为寄存器数。若 m = 16384，约为 0.81%；这不是每一次估计都落在 ±0.81% 的硬保证。小基数修正、哈希宽度与实现细节还会影响实际误差。见 HLL 原始论文。

合并时对兼容状态逐寄存器取最大值。这里的兼容包括哈希函数、种子、精度及编码约定；不能把两个最终估计数相加当作并集，因为用户可能重复。数据库聚合接口应该传递可合并状态，而非只传递最终数字。

日窗口可以每天保存一份草图，查询 7 天时合并对应桶。窗口滑动不从总草图中“减去昨天”，而是重新合并仍有效的桶，或维护可重算的层级聚合。分钟级窗口可以按时间桶折中，边界精度与状态数量由业务选择。

普通 HLL 的最大值更新丢失了次大值和元素归属，因此不能直接撤回任意元素。这一点对物化视图（Materialized View，MV）与增量视图维护（Incremental View Maintenance，IVM）很关键：插入可合并不代表删除可逆。

追问：精确账单能否用 HLL？若合同要求逐用户精确结算，应使用精确集合或可核验明细；近似仪表盘与财务口径分离；所有分组都分配固定草图会怎样？总内存是分组数乘单组状态；高基数分组可能让小草图也失控，需要稀疏表示、限制或外部状态。

差答：“HLL 是一种稀疏／密集矩阵”“12 KB 是所有 HLL 的固定内存”“删除时减计数”。

11. 跳表、LSM 与 B+ 树：把成本归到前台和后台

强答要点：三者层级不同。跳表（Skip List）是有序查找结构，日志结构合并树（Log-Structured Merge-Tree，LSM Tree）组织多层有序状态及合并，B+ 树（B+ Tree）是多路平衡查找树，在数据库中通常采用页式布局。LSM 的内存表可以用跳表，不能把它们当作互斥产品。

随机层级跳表在通常独立随机假设下，查找和更新期望 O(log n)，最坏情况可退化。并发跳表还需要节点发布、删除和安全回收机制；有多层指针不等于天然无锁或安全。

B+ 树以页为单位提高扇出，内部节点通常保存分隔键和子页引用，叶子保存记录或记录定位信息。页容量要扣页头、槽目录及空隙；叶子记录宽度和内部键宽度不同，不能用同一容量直接推算所有层。

若内部有效扇出约 500、叶子平均容纳 200 条，100 万条需要约 5000 个叶子页，再约 10 个中间页和一个根页，形成三层。这个例子展示计算方法；缓存命中后，查找并不必然产生三次物理 I/O。

LSM 以顺序追加和批量合并改变写入路径，同时承担写放大、读放大和空间放大。后台合并（Compaction）必须有持续预算；写入突发超过可消化能力时，积压最终会反压前台。把随机写转顺序写，没有消除重写字节。

RocksDB 的官方概述说明了内存表、有序文件、写前日志及合并结构，可作为 LSM 实现例子；具体合并策略与参数需另行固定版本。见 RocksDB Overview。

追问：LSM 删除为何没有立即省空间？墓碑必须阻止旧值复活，安全清理需要覆盖相关旧版本且满足快照保留要求；B+ 树在固态盘上是否失去意义？扇出、缓存局部性、范围读取和更新协议仍有价值，设备变化改变成本权重，不自动淘汰结构。

差答：“B+ 树每层固定 1024 个节点”“红黑树有 20 层就要 20 次磁盘读取”“LSM 写入是 O(1)，后台免费”。

四、系统设计需要一个贯穿五道题的约束框架

12. 通用设计题：把成功确认点和状态所有权画出来

强答要点：沿请求标出接收、排队、执行、持久化、提交、返回六个时刻，并为每段状态指定所有者。组件图之外，至少补一张失败状态表；每个重试都要回答是否可能重复执行，每个缓存都要回答版本来自哪里。

预算覆盖接入、排队、执行与回传：线程数上限不约束全部在途对象，慢客户端也会延长缓冲占用。

追问：主节点失联是否立即失去主身份？不一定；需要协议任期、租约或隔离令牌约束有效操作，不能靠“它自己知道失联”保证安全；重试如何避免放大故障？设置总体截止时间、有限次数、退避与抖动，并只重试可重放操作；重试流量计入容量。

差答：“所有服务无状态”“消息队列保证恰好一次”“网络分区时兼顾全部一致与可用”。

13. 实时 OLAP：新鲜度必须和可见性一起定义

强答要点：先把目标约束到报表集合、数据新鲜度和资源配额。任意 SQL、任意扫描范围与固定秒级尾延迟，不能仅靠列存和并行承诺。对于不可控交互查询，应提供单独的资源池和超时语义。

可选择“持久输入日志 → 解析与幂等摄入 → 可查询列式分片 → 查询协调与执行”的主路径。控制面管理表、分片与版本；数据面处理扫描、连接、聚合和交换。存储是否与计算分离，取决于恢复目标、缓存命中与远端带宽。

变更数据捕获（Change Data Capture，CDC）要保留源位置、主键、更新顺序及删除语义。主键更新不能只做追加，否则聚合会重复计入旧值。跨源没有天然全局顺序时，要说明使用源内顺序、业务版本还是冲突规则。

成功确认至少区分“已持久接收”“已写入可查询状态”“所有目标报表已追上”。若产品只承诺第一种，客户端应能读取摄入位置与可见位置，不能从一个成功响应推断所有查询已包含新数据。

MV 用空间和维护成本换查询成本，IVM 则要求明确哪些表达式可增量维护。计数与求和可在保留足够状态时处理撤回，去重计数和连接更新可能持有大量状态；维表变更还可能使大量历史结果失效。先说明可维护子集，再讨论自动改写。

性能路径按实测瓶颈分解：扫描裁剪减少读取，列裁剪减少解码，运行时过滤减少探测，局部聚合减少交换。向量化执行（Vectorized Execution）降低逐行调度开销，但批次大小、变长数据和高选择性路径仍需测量。

DuckDB 2024 年的内存管理说明把流式执行、临时外溢及缓冲管理共同纳入资源控制。这是“多个算子共享预算”的公开工程例子，不是分布式 OLAP 的完整方案。见 Memory Management in DuckDB。

追问：源端重复发送会怎样？以源分区和位置或稳定业务标识去重，固定去重状态保留期；过期后重放需另有批次或重建协议；一个节点崩溃，如何确保查询不混读版本？协调器固定查询快照或可见版本，重试分片仍使用该版本；无法取得时明确失败或整体重跑。

差答：“Kafka 加 StarRocks 就完成设计”“向量化就是 SIMD”“建 MV 后所有查询都秒级”。

【模板】个人案例：填写一个允许披露的查询或 MV／IVM 问题：版本、业务目标、原始计划、本人负责边界、反例数据、方案比较、验证条件及尚未解决的限制。没有完整指标时保留定性结论，不补造提升倍数。

14. 分布式缓存：故障期间的源站预算先于命中率

强答要点：读请求 100 万／秒、源站最多 2 万／秒时，如果所有未命中都回源，稳定期至少需要 98% 命中率才能不超过源站预算；这只是平均条件。节点丢失与集中过期时，必须限制回源总量，并允许拒绝或返回被业务许可的旧数据。

先划分本地一级缓存与共享缓存，明确是否允许旧读。读路径做鉴权、缓存查找、同键请求合并及受限回源；写路径选定源站为真相来源，再通过版本化值、失效通知或变更流控制旧值窗口。

缓存旁路（Cache-Aside）有读写竞争：旧读在新写失效后才回填，会重新放入旧值。版本比较、回填条件和通知顺序需要共同设计；“先写数据库再删缓存”只描述动作，未消除竞态。

过期时间（Time To Live，TTL）加随机抖动可缓解集中到期，不能解决单热点。请求合并要有等待上限，持锁重建者死亡后要能恢复；允许旧读时可以先返回旧值再刷新，但授权、余额等场景未必允许。

一致性哈希（Consistent Hashing）减少成员变化时的键归属迁移，不自动解决热点请求。虚拟节点改善键分布及容量加权，某一个键的流量仍可能压垮归属节点。热点可以复制或本地缓存，但增加失效与版本协调成本。

追问：加一台节点到底迁移多少？在均匀、等权的理想模型下，新节点接收约总键数的 1／(节点数 + 1)，实际受权重、虚拟节点与分布影响；迁移字节和请求负载不一定同比；旧节点恢复后会不会返回旧数据？路由代际及迁移状态要控制读写责任，不能把节点存活视作数据已追平。

差答：“一致性哈希只影响相邻物理节点”“缓存命中率 99% 就稳定”“加锁避免所有击穿”。

15. 日志检索：摄入、可搜索和保留是三种不同承诺

强答要点：先问平均与高分位事件大小、峰值、字段结构、可搜索延迟、检索语法及删除要求。100 亿条／日约为平均 11.6 万条／秒；若每条按 1 KB 十进制原始大小估算，是约 10 TB／日，30 天约 300 TB，尚未计算压缩和索引。

输入先落可重放日志，解析后写入不可变检索段；段清单发布决定可搜索状态。按租户、时间和容量组织分区，保留期通过段或对象生命周期执行，不能仅把一条过期标记写进元数据就宣称物理数据已经删除。

倒排索引（Inverted Index）适合词项到文档的映射，列式字段适合过滤、聚合与读取；分词器、词位置与规范化决定全文、短语和大小写语义。请求标识应优先保留精确字段，不能把高熵标识任意分词后再声称可精确定位。

对任意子串、正则和大范围聚合，要说明能否利用索引，必要时拒绝或转异步。热门错误码可能命中大量文档，即使定位词项很快，读取与合并结果仍有成本。时间范围与结果上限应尽早收紧。

写入确认要区分日志持久化与检索可见；解析失败进入可观察的隔离通道，不能悄悄丢弃。若重放可能重复，采用稳定事件标识或明确“至少一次、查询侧去重”的语义，并核算去重状态成本。

追问：消费速度长期小于生产速度怎么办？算积压增长与日志保留耗尽时间，临时扩容、降低非关键索引或受控拒绝；缓冲不会解决长期能力不足；段合并为何影响 P99？合并和查询争抢 I/O、CPU 与缓存，需要独立预算；减少小段的收益必须扣掉重写成本。

差答：“按时间分表就行”“所有字段都建倒排”“全文检索延迟等于摄入延迟”。

16. 湖仓查询：一致的文件集合是计划执行的前提

强答要点：先固定表格式、读取快照、目录服务与引擎兼容版本，再谈缓存和调度。对象存储中“文件都存在”不等于它们属于同一次表提交；读取必须从表元数据确定一致文件集合。

Apache Iceberg 以快照及元数据描述表状态，提交通过元数据变更建立新状态；实现需要使用相应目录的原子提交机制。见 Iceberg 规范。本文设计范围固定在 v2／v3 能力，不把页面中更高格式版本的内容混入结论。

协调器在准入后固定快照，读取清单并裁剪文件，生成扫描任务；工作节点从对象存储读取并在本地缓存不可变数据块，交换中间结果并受内存预算控制。缓存键要覆盖对象身份、版本或内容标识及范围，防止路径重用带来的错读。

元数据可能成为主成本：大量小文件增加清单解析、任务调度与远端请求，即使压缩后数据很小也会慢。文件合并、分区设计与统计维护属于服务的一部分；后台重写与前台扫描需要分配不同预算。

结果缓存必须覆盖 SQL 参数、表快照、会话语义、权限上下文与相关函数行为。跨租户共享相同数据块可能可行，跨租户共享未经权限约束的查询结果则可能泄漏信息；两类缓存不能使用同一安全假设。

Iceberg 1.9.0 于 2025 年 4 月发布，发行记录包含为 v3 表写入删除向量（Deletion Vector）的支持。格式支持与每个查询引擎的读写支持是两层兼容性，不能仅升级目录就启用新格式。见 Iceberg 发行记录。

删除向量将指定数据文件中的行位置标为删除；读取仍需正确关联文件与删除状态。是否能减少删除文件开销，要按删除密度、更新模式及引擎实现测量；不能推导为“删除免费”或“任意更新都不需维护”。

追问：查询进行时快照被过期清理怎么办？保留期必须覆盖在途查询或有引用保护；仅固定快照编号而文件已删，仍会失败；计算节点随时可回收，外溢文件放哪里？选择失败后重跑或持久中间结果；临时本地盘便宜，但不能同时承诺不重算恢复。

差答：“对象存储强一致，所以多文件表更新天然原子”“数据不变所以结果缓存永远有效”“升级文件格式会自动让所有引擎支持删除向量”。

17. LLM 服务平台：先算每个请求占用多少状态

强答要点：先按模型版本、输入输出长度分布、到达模式和交互目标分组。检索增强生成（Retrieval-Augmented Generation，RAG）会引入检索及上下文装配，智能体可能反复请求模型；一次业务请求不等于一次模型推理。

首词元延迟（Time To First Token，TTFT）、词元间延迟（Inter-Token Latency，ITL）及端到端完成时间要分别定义，并固定客户端或服务端测量边界；请求内平均的每输出词元时间（Time Per Output Token，TPOT）不能替代逐词元 ITL 的尾延迟。指标实现可参见 vLLM v0.10.2 Production Metrics。有效吞吐（Goodput）应只统计满足服务目标的工作量，并固定是请求数还是词元数；增加总吞吐但让大部分交互超时，不能视作达标。

入口做鉴权、模型路由、长度限制和租户配额；调度器做准入与批处理；执行节点负责预填充（Prefill）和逐步解码（Decode）；平台管理模型版本、权重分发、健康、指标与扩缩容。先用同节点执行建立基线，再决定是否分离两阶段。

1每个词元的 KV 字节 ≈ 2 × 层数 × KV 头数 × 每头维度 × 每元素字节数
2请求 KV 字节 ≈ 上式 × 当前缓存词元数

公式按各层同形的常规 KV 估算；MLA、滑动窗口、量化元数据、分页空隙及 KV 头分片／复制需另算。

假设 32 层、8 个 KV 头、每头 128 维、每元素 2 字节，逻辑缓存约为 128 KiB／词元。8192 个词元约需 1 GiB，一个实例的可并发请求数因而可能先受显存约束，而不是先受连接数约束。这是架构演算，不对应某个指定模型的实测。

追问：请求排队时是否预留全部最大输出缓存？全量预留更保守，动态分配提高利用率但增加运行中抢占风险；需要明确输出上限和不足时策略；长请求是否应该独立队列？隔离可保护短请求，但可能降低总体利用率；按长度分组、优先级及公平性共同评估，不能只按请求条数限额。

差答：“加一个自动扩容器即可”“QPS 相同所以负载相同”“KV 缓存就是普通结果缓存”。

18. 推理调度追问：分块、分离与缓存路由分别解决什么

强答要点：这些机制控制不同成本。分块预填充（Chunked Prefill）把长输入分成可调度块；两阶段分离控制资源干扰；前缀缓存复用已经计算的状态；CUDA Graph（CUDA 执行图）减少重复执行时的主机调度开销。先定位等待来自哪里，再比较方案。

Sarathi-Serve 在 2024 年提出结合分块预填充的调度，研究吞吐与延迟的权衡。论文支持“长预填充与解码混排需要调度控制”，不支持任意块大小都最优。见 Sarathi-Serve。

DistServe 在 2024 年研究预填充与解码分离，按两阶段延迟目标及通信条件配置资源。它支持“隔离干扰可能提升达标服务能力”，不是“分离总是更快”。见 DistServe。

若一次请求需转移前节估算的 1 GiB 缓存，假设该请求独占有效吞吐为 25 GiB／秒的传输路径，且实际转移量恰为 1 GiB，单纯传输时间约为 40 毫秒，尚未计排队、协议与争用。分离节省的干扰成本必须超过传输和调度新增成本；同机高速互连与跨机网络不能共用结论。

vLLM v0.10.2 的自动前缀缓存文档按块组织复用状态，并说明哈希键还包含前驱信息和附加身份信息；其 V1 引擎可通过可选的请求级 cache_salt 限制复用范围，V0 不支持该机制；该选项不自动识别租户；服务端应按信任域控制盐值，不能把客户端任意提供的盐当作授权凭据。见 Automatic Prefix Caching。

vLLM v0.15.1 的 CUDA Graph 文档区分完整图与分段图等模式，涉及后端兼容和运行形状选择。见 CUDA Graphs 设计。应按捕获形状、填充浪费、显存与回退路径验证，不把“打开执行图”当作消除所有开销。

NVIDIA 在 2026 年 3 月发布的 Dynamo 1.0 官方技术文章把多节点推理、KV 感知路由和缓存管理放在平台层讨论，并支持对接 vLLM 等执行引擎。这里仅引用功能与架构定位，不引用其特定硬件上的营销性能倍数。见 Dynamo 1.0 官方技术博客。

追问：如何做可信比较？固定模型和精度、硬件与拓扑、输入输出长度分布、到达模型、缓存冷热和软件版本，同时报告达标率及成本；连续批处理（Continuous Batching）为何不等于无限加大批次？大批次可能增加调度等待和词元间延迟，显存压力还会触发抢占与重算。

差答：“数据库流水线可以直接套到模型推理”“解码一定只受带宽限制”“执行图支持所有动态路径”。

【模板】迁移叙事：填写一个已做过的数据库资源控制案例，再列出能迁移的预算、反压和版本原则；AI 推理部分分别注明已经实现、仅做源码阅读或准备验证的范围。不得把阅读 DistServe 或调试样例说成运营过大规模推理平台。

五、评估标准要落在可观察证据上

下面的练习量表检查证据，不是任何公司的录用标准。正确性缺口须单独修复，不能用其他维度总分抵消。

20. 验证题：怎样设计能推翻方案的实验

强答要点：先分开正确性、资源与性能假设。用小规模精确基线验证语义，用可控分布观察资源增长，再在固定环境验证吞吐与尾延迟。任何一个维度失败，都应能定位到具体假设，而不是只得到“综合跑分下降”。

算法验证包括空输入、极值、相同键、倾斜与最坏排列；系统验证再增加超时、重复、乱序、部分提交、节点失效和恢复。近似算法需要在多次试验中观察误差分布，单个样本准确不能证明估计器稳定。

性能实验保留数据生成方式、分布、热身、缓存状态、输入输出大小及并发背景。固定并发闭环压测会在服务变慢时自动降低到达率，可能掩盖排队失控；要验证过载，应另设独立到达率及明确拒绝策略。

追问：平均值变好而 P99 变坏怎么办？按长度、租户、查询类和缓存状态分组，判断收益是否由一类请求占用另一类资源换来；新方案只在热缓存下更好怎么办？报告适用条件，测预热成本与故障后恢复时间；不要隐去冷态结果。

差答：“跑一遍基准”“流量回放没有报错”“CPU 降了所以成本降了”。

【模板】决策记录：在【版本／时间】、【可披露负载】下，我负责【明确边界】。原方案在【观测】上不满足【目标】，我比较【方案 A／B】，依据【不变量与预算】选择【方案】；由【本人／协作者】完成【验证】，结果是【真实数据或定性结论】，仍不适用于【限制】。

新增来源与证据边界

1. Cuckoo Filter: Practically Better Than Bloom，CoNEXT 2014：指纹、候选桶、插入删除及容量条件，不支持任意阳性删除。
2. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm，2007：经典估计误差与合并基础，不提供任意撤回能力。
3. RocksDB Overview，官方 Wiki：LSM 实现的内存表、文件与合并概览，不作为固定版本源码调用链。
4. Redis Key Eviction，官方文档：采样式 LRU 与淘汰策略，不承诺适用于任意工作负载。
5. Redis HyperLogLog，官方文档：Redis 的操作与实现参数，不泛化为所有 HLL 的常数。
6. Memory Management in DuckDB，2024-07-09：流式处理、外溢与缓冲预算的工程关联。
7. Redesigning DuckDB’s Sort, Again，2025-09-24：v1.4.0 排序布局与执行设计，本文不复述其基准倍数。
8. Apache Iceberg Specification，官方规范：快照、元数据与删除表示，本文限定 v2／v3 范围。
9. Apache Iceberg Releases，官方发行记录：1.9.0 的发布时间及 v3 删除向量写入支持。
10. DistServe，2024：预填充／解码分离的资源及延迟问题，不提供跨硬件通用性能承诺。
11. Sarathi-Serve，2024：分块预填充与调度取舍，本文不把论文结果当作本人的实验。
12. vLLM v0.10.2 Automatic Prefix Caching，官方文档：块哈希、附加身份及缓存隔离设计。
13. vLLM v0.15.1 CUDA Graphs，官方文档：执行图模式、适用条件及后端约束。
14. How NVIDIA Dynamo 1.0 Powers Multi-Node Inference at Production Scale，2026-03-16：平台层路由与缓存管理的官方架构说明，不作为独立性能复现证据。

准备结束的判断条件是：换掉输入分布、压缩内存预算、打断一次提交，你仍能说明结果是否正确、谁承担额外成本、怎样发现假设不成立。若某个主题目前只能讲正常路径，就缩小承诺范围并补验证；不要用更多组件名填满尚未证明的部分。