分布式一致性、并行与在线算法

• 线性一致性：操作有全局实时顺序，与真实时间一致
• 顺序一致性：只要求存在一个合法顺序，可重排
• Raft 单主多数派实现线性一致；多主复制通常只保证最终一致

线性一致性要求每个操作在"调用与返回之间"的某个时刻生效，所有操作存在一个与真实时间一致的全局顺序，任何客户端在任意时刻看到的都是该顺序的某个前缀——它是"最强"的一致性，等价于"单一系统 + 实时时钟"。顺序一致性只要求存在一个与程序顺序兼容的全局顺序（每个进程内操作保持程序顺序），允许该顺序与真实时间错位（如先返回后生效的窗口），客户端观测时只要最终能串出一个合法历史即可。Raft 通过"单领导者 + 多数派复制 + 日志顺序"实现线性一致性（配合 ReadIndex/Lease Read 可避免领导者读的线性化破坏），因为所有写操作经过同一领导者以同一顺序提交，读操作从领导者读到已提交日志。多主复制（multi-leader）中不同主节点接受写入、异步传播冲突，通常只保证最终一致性（即使配合冲突解决，也存在"两个客户端在不同时刻看到不同顺序"的窗口），要获得线性一致需额外协议（如严格串行化、全局时钟协调）。

本题考察一致性模型的"实时性"维度：线性一致性强在"与真实时间对齐"，顺序一致性弱在"允许时间错位"。回答时先给出两者的形式化定义与差异例子，再分别说明 Raft 单主与多主复制的保证，最后讲客户端观测方法（线性一致可用"响应顺序 + 时钟"验证，顺序一致用"串行化历史"验证）。

• LRU：时间局部性强、突发热点；LFU：长期稳定热点
• ARC：在 LRU/LFU 间自适应调节；W-TinyLFU：分段 LFU + 频率衰减
• trace 评估：重放访问序列、对比命中率与开销

LRU（最近最少使用）适合时间局部性强、热点短时集中的负载（Web 页面、CPU cache 的典型假设），实现 O(1)、对突发流量响应快，但周期性扫描（全量遍历）会把缓存"洗一遍"造成命中率骤降（缓存污染）。LFU（最少使用）适合热点长期稳定、访问频率分布极不均匀的负载（数据库索引页、CDN 大文件），但实现需维护频率结构、对"新晋热点"响应慢（旧高频项长期占位），且频率无限增长需衰减处理。ARC（自适应替换缓存）维护两个 LRU（最近一次区 + 频率区）并动态调节分配比例，自动适配"扫描型 vs 热点型"混合负载；W-TinyLFU（Caffeine 采用）用分段 LRU + 频率 Sketch（Count-Min）记录访问频率并做时间衰减（窗口采样），兼顾"突发热点"与"长期热点"，缓存污染免疫性好。评估方法：用真实访问 trace（时间戳 + key 序列）重放各策略，统计命中率/字节命中率，同时测开销（每次访问的复杂度与内存）；不同 trace 结论可能相反，需按负载特征（扫描比例、热点集中度、key 基数）分组报告。

本题考察"策略-负载匹配"：没有万能策略，只有对负载假设的匹配。回答时先讲三种经典策略的机制与适用场景，再讲 ARC/W-TinyLFU 的自适应机制，最后给 trace 评估方法论（重放 + 命中率 + 负载特征分组）。

• 次模函数（submodular）与贪心算法的 1-1/e 近似
• 在线匹配的贪心 1/2 竞争比与平衡算法 1-1/e
• VCG 拍卖的激励相容（诚实报价是占优策略）

Adwords 拍卖可建模为"在线二部图匹配/次模福利最大化"：每个广告主 i 有预算 b_i、对查询 q 的估值 w_iq，系统在线接收查询并分配广告主，目标是最大化总福利。当福利函数是次模（边际收益递减）时，经典结论：离线次模最大化中"贪心 + 随机化"的近似比为 1-1/e ≈ 0.632，该界来自次模函数的"每步贪心至少获得剩余最优收益的 1/e"论证（连续松弛 + Lovász 扩展的凹包技术）；在线版本（Adwords 的 MSVV 平衡算法）同样达到 1-1/e 竞争比（确定性界），这是该问题的紧界。VCG（Vickrey-Clarke-Groves）拍卖是"激励相容"的机制：每个参与者按其真实估值出价是占优策略（谎报不会更好），因为 VCG 的付费 = 他人福利的损失（外部性），使参与者外部性内部化；但 VCG 假设估值可分离（无预算约束），而 Adwords 有预算约束，预算约束下激励相容机制更难设计（需 Myerson 式机制或近似）。回答时要区分"福利最大化近似"（算法问题）与"激励相容"（机制设计问题）。

本题考察两个概念的层次：贪心 1-1/e 是算法界的近似保证，VCG 激励相容是机制设计界的性质。回答时先讲次模最大化的贪心论证与 1-1/e 界，再讲在线版本的平衡算法竞争比，最后讲 VCG 的占优策略与预算约束下的困难。

• 竞争比：在线代价 / 最优离线代价的上界
• 保守策略：确定性（最坏情形保证）vs 随机化（期望保证）
• ski rental（2-竞争）、list update（MTF 2-竞争）实例

在线算法在"输入逐步到达、不可预知未来"时决策，设计原则是"用保守的确定性策略保证最坏情形竞争比，或用随机化改善期望竞争比"：竞争比定义为在线算法代价与"事后最优离线算法（OPT）"代价之比的上界（确定性）或期望上界（随机化）。经典例子：ski rental 问题（滑雪板租/买），确定性最优策略是"租到第 B 天再买"（B 为买价），竞争比 2——因为 OPT 要么全程租（代价 ≤ 2·OPT）要么第一天买；随机化可将竞争比降到 e/(e-1) ≈ 1.58。list update 问题（维护线性表服务访问序列），Move-to-Front（MTF）策略达到 2-竞争（对任意访问序列），且 MTF 是"移动成本 1、访问成本 = 位置"模型下的最优在线策略族；离线 OPT 可用动态规划求解最优静态排列（"静态最优性"）。与离线算法的对照：离线算法能看完全部输入后优化（如最优排列、最优租买切换点），在线算法必须边看边决策，竞争比刻画"信息缺失的代价"。

本题考察在线算法的分析框架：竞争比 = 信息劣势的量化。回答时先定义竞争比，再以 ski rental 与 list update 两个经典例子演示确定性/随机化设计，最后与离线 OPT 对照说明意义。

• 收益评估：常数因子、n 的实际规模、最坏 vs 平均
• 改造方向：排序（离线）、哈希（点查）、平衡树（有序遍历）
• 不值得替换的情形：n 小、常数大、最坏罕见、可读性损失

算法替换的收益评估不能只看渐近阶：1) 实际规模 n——O(n²) 与 O(n log n) 的交叉点在 n 较小（如 n < 1000 且常数比差 10 倍）时 O(n²) 可能更快；2) 常数因子——哈希表 O(1) 平均但常数大、排序的 log 因子小，平衡树 log 因子带指针开销；3) 最坏 vs 平均——哈希退化、快排最坏 O(n²) 但平均极好，需按输入分布评估；4) 内存与实现成本——排序需额外数组、平衡树需节点内存与复杂实现。改造方向的判断：需要离线批量处理（求交集、去重、TopK）→ 排序 + 双指针/扫描；需要点查/去重 → 哈希；需要有序遍历/区间/前驱后继 → 平衡树；需要维护极值 → 堆。不值得替换的情形：n 恒小（常数支配）、最坏输入不会出现且平均已足够（可测）、改造后代码复杂度与维护成本上升且收益无实测支撑（"过早优化"）、一次性任务（总时间已可接受）。正确做法：先测基线（profiling），再按规模外推估算收益，最后以实测确认。

本题考察"渐近分析 + 工程判断"的结合：替换决策应基于规模、常数、分布与成本。回答时先给收益评估的多维框架，再按操作类型给出改造方向选择，最后列举不值得替换的典型情形与评估流程。

• 哈希：O(1) 点查/插入，无序、空间高、并发需锁/无锁
• 平衡树：O(log n) 有序操作，空间低、并发难（锁路径）
• 日志结构：顺序写快、读放大、空间放大，并发友好（追加）

三种结构构成"点查/有序/写优化"三个方向：哈希表提供 O(1) 平均点查与插入、O(n) 最坏退化风险，无序（无法范围查询），空间利用中等（负载因子），并发上桶锁/无锁方案成熟（如 ConcurrentHashMap）；平衡树（红黑树/B 树）提供 O(log n) 的有序遍历、区间查询、前驱后继，空间紧凑（B 树块友好），但并发更新需要路径锁/细粒度锁（B-link、无锁 B+ 树复杂度高），写放大相对日志结构高（原地更新 + 重平衡）；日志结构（LSM-tree、append-only 日志）写入只有顺序追加（写放大被 compaction 控制）、并发写天然无锁（追加点原子），但读需要多层查找（读放大）且空间放大（冗余版本），适合写多读少、写吞吐优先的负载。权衡矩阵：写密集 + 简单点查 → 日志结构；读密集 + 点查为主 → 哈希；读密集 + 范围查询 → B 树/平衡树；并发要求高 + 写多 → 日志结构/无锁哈希。实际系统常组合：LSM 写 + 布隆过滤器加速点查 + 内存哈希做热数据。

本题考察"三维权衡"的选型思维：时间（读写）、空间、并发三轴同时评估。回答时先给出三结构的特性矩阵，再按负载特征（读写比、查询类型、并发度）给出选型规则，最后讲工程组合方案。

• 竞争比定义：sup（在线/OPT）
• ski rental：确定性 2-竞争、随机化 e/(e-1)
• 在线二分：目标位置未知的对抗式二分，竞争比 O(log n) 或常数

竞争比分析入门分三步：1) 定义 OPT——对任意输入序列，最优离线算法（事后知道全部输入）的代价；2) 找到在线策略并构造最坏输入——分析在线代价与该输入下 OPT 代价的比值，取所有输入的上确界即竞争比；3) 下界论证——对任意在线算法构造对抗输入，证明任何算法竞争比 ≥ c。ski rental 示例：买价 B、租价 1/天，确定性策略"租满 B-1 天后买"的竞争比 2：若序列短于 B（OPT 全租），在线代价 ≤ 2·OPT；若序列长（OPT 第一天买），在线代价 = (B-1) + B ≈ 2B ≤ 2·OPT；随机化（按几何分布掷硬币决定买点）可达 e/(e-1) ≈ 1.58，且该界紧。在线二分/搜索：如"猜一个藏在 [1, n] 的整数，猜错给'大/小'反馈"，在反馈与历史保持一致的前提下，经典二分仍只需 O(log n) 次即可定位；若把代价建模为"比较次数"，并与"已知目标位置的离线 OPT（代价为 1）"相比，则任何确定性在线算法都需 Ω(log n) 次比较，竞争比为 O(log n) 量级（二分即可达到），而"租/买"类问题是常数竞争。入门建议：先掌握 ski rental 与 paging（缓存淘汰）两个模板，理解"下界 + 上界"的完整论证。

本题考察竞争比分析的完整套路：OPT 定义、上界（策略 + 最坏输入）、下界（对抗论证）。回答时以 ski rental 完整演示 2-竞争与 e/(e-1)，再介绍在线二分的建模与 log 竞争比，最后给学习路径。

• Amdahl 定律：加速比 ≤ 1/(s + (1-s)/p)，串行部分为瓶颈
• 并行归约：树形两两合并，步数 O(log n)、工作量 O(n)
• 前缀和：Blelloch 扫描（up-sweep + down-sweep），O(n) 工作量 O(log n) 步

Amdahl 定律给出加速比上界：若串行部分占比 s，p 核并行，加速比 ≤ 1/(s + (1-s)/p)，当 p→∞ 收敛到 1/s——串行部分是最终瓶颈，这解释了"95% 并行也只有 20 倍加速"。并行归约（求和/求极值）：把两两相加组织成平衡二叉树，每层并行处理，共 log n 层（步数 O(log n)），总工作量 O(n)；在 p 核上每层并行度受 p 限制，加速比接近 p（当 n ≫ p）但受 Amdahl（最后几层的串行归并）与同步开销限制。并行前缀和（scan）：Blelloch 算法分两个阶段——up-sweep（自底向上把子树和逐层合并，log n 步）与 down-sweep（自顶向下把前缀值分发，log n 步），总工作量 O(n)（每个元素参与常数次），步数 O(log n)；相比串行 O(n) 时间，p = n 核时加速比 ~ n/log n（对数开销），实际 p 有限时接近线性。分析要点：用"工作量（work）W"与"深度（depth）D"两个指标，加速比受 min(p, W/D) 限制，同时考虑负载均衡（元素分布不均时最慢线程决定时间）与同步/通信开销。

本题考察并行复杂度的双指标体系：工作量与深度，以及 Amdahl 对加速比的硬约束。回答时先讲 Amdahl 公式与含义，再分别给出归约与前缀和的树形算法、步数与工作量，最后讨论实际加速比的限制因素。

• 两阶段：内部排序生成有序段（run）+ 多路归并
• 败者树：k 路归并的 O(log k) 每输出、替代选择
• 趟数公式：⌈log_M(N/M)⌉ 随内存 M 增大而减少

外部排序处理超内存数据，分两阶段：第一阶段（run 生成），把数据分块读入内存排序后写回磁盘，形成若干个有序段（run），每段大小 ≈ 内存 M；第二阶段（归并），把所有 run 多路归并成一个有序序列。多路归并用"败者树"（loser tree）优化：它是一棵锦标赛树，内部节点记录"败者"（较大者），根是最小者，每次输出最小值后从对应叶子补充新元素并沿路径向上调整，每输出一个元素比较 O(log k) 次（k 为路数），比简单顺序比较的 O(k) 快，且不用像胜者树那样逐层重算；替代选择（replacement selection）还能让 run 平均长度为 2M。I/O 代价分析：设 N 为数据量、M 为内存、k 路归并，第一趟生成 N/M 个 run，此后每趟归并 k 路，趟数 = ⌈log_k(N/M)⌉，每趟读写全部数据一次（2N I/O），总 I/O ≈ (趟数+1)·2N。内存 M 增大时：单趟归并路数 k ≈ M 内能同时打开的文件数，M 翻倍 → 趟数减少约 1 趟，I/O 显著下降；极端情况 M ≥ N 时一趟归并即完成（等价于内存排序）。工程上还会用"多趟归并 + 缓冲预读"与"磁盘顺序 I/O"优化。

本题考察外存算法的 I/O 模型：趟数是核心指标。回答时先讲两阶段流程，再讲败者树机制与复杂度，最后推导趟数公式并分析内存大小的影响。

• 压缩：熵编码（gzip/zstd）、列压缩、字典
• 差分同步：rsync 式块哈希比对、delta 编码
• 批量 vs 流式：合并请求省首部开销 vs 低延迟，取舍在延迟与吞吐

带宽受限的设计围绕"传输内容的最小化"：1) 压缩——数据先压缩再传（zstd/gzip、数值列的 delta/varint 编码、字符串字典化），传输量降数倍至数十倍，代价是两端 CPU 与延迟；2) 差分同步——接收方已有旧版本时只传差异：rsync 用固定块哈希（弱哈希快速定位 + 强哈希校验）比对双方块，只传缺失/变化块；delta 编码（xdelta/bsdiff）对相似文件压缩差异；3) 增量传输——时间序列/日志只传新增部分，配合游标/水位线；4) 去重与缓存——内容寻址去重（相同数据块只传一次）。批量与流式的取舍：批量传输合并多个请求，摊薄首部/握手/打包开销，吞吐最优，但增加延迟（等批次积攒）与突发；流式传输低延迟、逐步可用，但每单位数据开销大（首部、ack）；取舍准则：延迟敏感（实时）用流式、吞吐敏感（同步/备份）用批量；混合方案（批量窗口 + 流式首包）常用。工程上配合拥塞控制与重传设计（QUIC/TCP 的选择性重传）在带宽受限下尤为重要。

本题考察"传输优化"的算法工具箱：压缩、差分、增量、去重四类手段，以及批量/流式在延迟-吞吐上的取舍。回答时逐项讲机制与收益，再给批量/流式的决策标准。

• 层次：线程/块/网格，共享内存为块内通信
• 归约：块内共享内存树形归约 + 块间原子/二次归约
• coalescing（连续线程访问连续地址）与 bank conflict（共享内存同 bank 冲突）

CUDA 编程模型分三层：线程（thread）组成块（block），块组成网格（grid）；块内线程用共享内存（shared memory）高速通信，块间通过全局内存 + 原子操作/多次 kernel 通信。并行归约实现：块内每个线程处理一段数据（strided 读取），在共享内存中做树形两两归约（每次迭代线程数减半、消除 warp 内分支），块内归约结果写回全局；块间再二次归约（原子加或第二个 kernel）。并行扫描同样用共享内存（Blelloch up/down-sweep）。性能模型的两个关键：1) 访存合并（coalescing）——全局内存访问以 32 字节/128 字节事务为单位，相邻线程访问相邻地址时合并成少数事务（带宽最优），跨步访问（stride）导致事务数爆炸（如按列访问行主序数组）；2) bank conflict——共享内存被分为 32 个 bank（每 bank 4 字节），同一 warp 内多线程同时访问同一 bank 的不同地址时串行化（冲突），设计时用填充（padding）或错位访问避免（如 stride 32 的经典冲突）。性能建模：估算每线程的访存事务数、共享内存冲突数、占用率（occupancy，块大小与寄存器/共享内存使用决定）与同步开销，用"理论峰值 vs 实测"定位瓶颈（memory-bound vs compute-bound）。

本题考察 GPU 并行实现的性能模型：层次结构 + 两个访存定律（coalescing、bank conflict）。回答时先讲三层模型与归约/扫描的组织，再重点讲 coalescing 与 bank conflict 的机制与规避，最后给性能分析流程。

• 确定性：租 B-1 天后买，分"短序列/长序列"两情形论证 ≤ 2
• 随机化：几何分布的随机买点，期望代价分析
• 下界：任意确定性算法 ≥ 2、任意随机化 ≥ e/(e-1)

ski rental：买价 B、租价 1/天。确定性策略"前 B-1 天租、第 B 天买"：若实际使用天数 T < B，OPT 全租代价 T，在线代价 T ≤ 2T；若 T ≥ B，OPT 第一天买代价 B，在线代价 (B-1) + B = 2B-1 < 2B = 2·OPT；故竞争比 2。下界：对任意确定性策略，对手选 T 为"策略第一次买的时刻"（买之前都租），则 T ≥ B 时在线 2B-1 vs OPT B，或 T 恰好 B-1 时在线 B-1 = OPT·(B-1)/(B-1)，综合论证任何确定性算法 ≥ 2-ε。随机化：算法按几何分布随机选择买点（每天以概率 1/B 决定"若今天买"），期望租期 B，期望在线代价 ≈ e/(e-1)·B（最优参数），上界 e/(e-1)；下界用 Yao 原理（构造输入分布，证明任何确定性算法在该分布上 ≥ e/(e-1)）给出。与 OPT 的对照：OPT 在知道 T 后选择"若 T ≥ B 买、否则租"，代价 = min(T, B)，在线算法的竞争比即"信息缺失"的代价上界，2 与 1.58 说明随机化能实质降低最坏情形代价。

本题考察竞争比推导的完整流程：策略构造 → 分情形上界 → 对抗下界（确定性用对手策略、随机化用 Yao）。回答时完整演示两个方向的论证，最后与 OPT 对照说明竞争比的语义。

• Power of Two Choices：随机取两个队列选短的，指数级改善最大负载
• JSQ：全局最短队列，最优但需全局状态（通信 O(n)）
• 权衡：抽样 k 个 vs 全局，负载均衡 vs 通信/一致性开销

Power of Two Choices（两选一）思想：每个任务随机采样两个队列，加入负载较轻者。理论结果：n 个队列、负载到达率 < 1 时，随机选择的最大负载为 O(log n/log log n)，而"两选一"把最大负载降到 O(log log n)——指数级改善，且这个"随机两选一"只需要 2 次采样，几乎不增加通信。原因：最短队列被选中的概率分布具有"指数集中"效应，负载高的队列被再次选中的概率随负载指数下降。JSQ（Join the Shortest Queue）选择全局最短队列，在理论上是最优的（负载均衡最均匀），但需要维护全局队列长度信息：集中式需要中心协调（单点、延迟），分布式需要广播/周期同步（每任务 O(n) 通信或过期信息），通信与一致性代价高。取舍：任务量大、队列多、状态变化快时用"抽样 k 个（k = 2 通常足够）"——用 2 次采样换取接近 JSQ 的均衡效果与 O(1) 通信；对负载差异大、需要严格均衡的场景才考虑 JSQ 的全局信息（或分层：先哈希分片再用两选一）。工程中（如任务调度、缓存分片、gRPC 连接池）普遍采用 P2C 变体（一致性哈希 + 两选一）。

本题考察"随机化 + 局部信息"逼近全局最优的经典结果：两选一的指数级改善。回答时先讲机制与负载分布结果，再讲 JSQ 的通信代价，最后给出"采样 vs 全局"的取舍原则与工程实践。

• MPI：进程级、分布式内存、消息传递（send/recv、collective）
• OpenMP：线程级、共享内存、编译指导（并行循环、归约）
• 混合模型：MPI 分节点 + OpenMP 节点内多核，减少消息数

MPI（消息传递接口）面向分布式内存：多进程各自有独立地址空间，通过显式消息传递通信（点对点 send/recv 与集合通信 broadcast/reduce/allreduce），编程模型是"进程 + 通信子（communicator）+ 秩（rank）"，可跨节点扩展，但通信开销显式且需手工管理数据分布。OpenMP 面向共享内存：单进程多线程，通过编译指导（#pragma omp parallel for、reduction、critical）自动并行化循环与归约，线程共享内存、无消息开销，但仅限单节点。分工原则：跨节点用 MPI（唯一选择）、节点内多核用 OpenMP（或线程库）。混合模型（MPI+OpenMP）：MPI 在节点间分配数据与任务（每个节点一个/几个 MPI 进程），OpenMP 在节点内并行化计算（每进程多线程）——收益：减少 MPI 消息数量与粒度（节点间通信聚合）、减少内存复制（线程共享数据）、提升单节点利用率；代价是两级并行度的调度复杂度与负载均衡问题（嵌套并行需控制线程数、避免 oversubscription）。典型应用：HPC 的稀疏迭代求解（MPI 分块 + OpenMP 稀疏矩阵向量乘）、大规模分子动力学。工程要点：进程数与线程数乘积 ≤ 核数、通信与计算重叠（非阻塞 MPI + 计算）、按数据局部性划分。

本题考察并行编程模型的分工与混合：分布式 vs 共享内存的边界，以及两级的组合方式。回答时先讲两种模型的机制与适用域，再讲混合模型的收益与工程要点。

• 分离：Narwhal 负责交易广播（DAG 构建），Tusk 负责因果排序
• DAG 构建：每轮广播自己的块 + 引用前轮块，形成有向无环图
• 与 HotStuff（链式 BFT）对比：共识与传播解耦、吞吐与延迟

Narwhal & Tusk（Sui 的共识层）把"交易传播"与"共识排序"解耦：Narwhal 是一个高吞吐的 DAG 构建层——每个验证者每轮（round）打包交易形成块，块引用前一轮其他验证者的块（投票），块间形成 DAG，Narwhal 保证"块一旦提交到 DAG 就复制完整"（可靠广播）；Tusk 在 DAG 之上做排序：利用 DAG 的因果结构（投票关系）确定块的总序，只需少量轮次收集投票即可完成排序，无需传统 BFT 的"提案-预投票-投票-提交"消息流。为什么分离能提升吞吐：共识协议中"传播 + 排序"耦合时（HotStuff 的链式结构），每个提案都要完整传播并逐轮投票，传播延迟与共识延迟相互拖累；解耦后传播（Narwhal）可以全速并行进行（吞吐只受网络带宽限制），排序（Tusk）在已有 DAG 上做轻量确定，两者并行流水，吞吐可达数十万 TPS。与 HotStuff 对比：HotStuff 是链式 BFT（每个视图一个提案、三阶段投票，消息复杂度 O(n)，响应式 view change），吞吐受"每轮共识必须等传播完成"限制，延迟低（一轮可定序）但吞吐受网络往返约束；N&T 以稍高的延迟与 DAG 存储成本换取数量级更高的吞吐，且 DAG 天然支持异步性（不依赖同步假设的乐观路径）。

本题考察共识架构的"关注点分离"：传播与排序解耦的收益。回答时先讲 Narwhal 的 DAG 构建与 Tusk 的排序，再分析解耦提升吞吐的机制，最后与 HotStuff 对比吞吐-延迟的取舍。

• 在线定价：买家序贯到达，卖家即时报出价格（固定价或自适应）
• 无分布假设的竞争比：固定价格策略的 O(log n) 竞争
• 与 secretary problem：都属"最优停止/在线选择"，定价是"设定阈值"变体

在线定价问题：n 个买家按序到达，每人有一个私人估值 v_i，卖家在看到当前买家（或完全不知）时给出价格 p，买家若 v_i ≥ p 则成交；目标是最大化总收益，且不预知估值分布（对抗式）。无分布假设下的经典结果：固定单一价格策略达到 O(log n) 竞争比——关键是选对价格：把估值范围按 2 的幂分档（如 [1,2), [2,4), ...），统计各档"以该档价格为基准的收益"的估计，用"sampling + 保留价"或"consensus 价格"技术选择近似最优档；更精细的结果是 (1-ε) 最优收益的 O(log n) 竞争（对抗）与常数竞争（随机到达）。直觉：对未知分布的定价，本质是"估计最优单价的档位"，档位数量 O(log V)（V 为估值上界），选错档的代价可控。与 secretary problem 的联系：两者都属于"在线选择/最优停止"家族——secretary 是"选最好的候选人"（阈值 = 排名），在线定价是"选最优价格"（阈值 = 价格）；secretary 的经典结果是 e-竞争（1/e 概率选中最优），定价的类似结构是"先用样本估计分布再定价"（sample-then-price 的常数竞争）。区别：secretary 只看相对排名不看数值，定价需要数值阈值；定价还涉及多买家累计收益（不仅是选一个）。

本题考察在线收益最大化的建模：把"定价"转化为"选档位"。回答时先讲问题与无分布假设的结果，再讲 2 的幂分档与选档技术，最后与 secretary problem 对比同属在线阈值选择。

• ski rental：云资源购买/租赁决策、带宽扩容时机
• paging：缓存淘汰（LRU 的竞争比 2 思想）、内存换页
• secretary：招聘、数据分片选优、服务选择

三个在线问题的工程映射：1) ski rental（租/买时机）——云计算容量决策：业务流量不确定时"按需租用（按量付费）" vs "预留实例（包年包月）"，对应租/买，最优决策是"流量达到阈值才买"，竞争比思想指导预留与按量的混合策略；类似场景还有带宽扩容、许可证采购、GPU 集群的 spot/on-demand 选择；2) paging（页淘汰）——缓存系统的核心：LRU 是最优确定性在线页算法（k-竞争，k 为缓存大小），工程上所有缓存（Redis、CDN、CPU cache）都在做 paging 决策，竞争比框架解释"为什么 LRU 好但不够好"（需要自适应策略如 ARC）；3) secretary（择优时机）——"观察-决策"场景：招聘（面几个人后择优录用）、租房/买房（看几套后决定）、在线广告的流量分配（采样学习 vs 利用），以及数据流中"选最优代表"的变体（蓄水池抽样是其均匀版本）。共同点：这些问题的工程价值不是直接套算法，而是"竞争比思维"——面对不确定性时，用"样本 + 阈值 + 保守切换"设计系统策略，并在最坏情形与平均情形之间做显式权衡。

本题考察"理论问题 → 系统场景"的迁移能力：抽象问题在真实系统都有对应物。回答时逐个映射三个问题到具体系统与决策场景，最后总结"竞争比思维"的工程价值。

• 外存模型：I/O 复杂度（块传输次数）代替时间
• B 树：扇出大、树高小、块内顺序扫描
• LSM：顺序写 + 布隆过滤；PMem：持久化内存的字节寻址结构

内存受限（数据量超过内存）时，算法分析模型从 RAM 模型切换为外存模型（I/O 模型）：代价以"块传输次数"计量，一次随机访问 = 一次块读。设计原则是"减少随机访问、放大顺序访问"：1) B 树——大扇出（每节点 = 一个块，可存几百个键）使树高仅 3-4 层，查找路径 = 3-4 次随机读，块内顺序扫描做二分；B+ 树进一步把数据集中到叶子顺序链，范围查询按块顺序读；2) LSM-tree——写路径全部顺序追加（写放大但随机写变顺序写，SSD 友好），读用多层 + 布隆过滤器（每层一个布隆过滤器把"该层无此键"的读变成零 I/O），适合写多读多的日志型负载；3) 缓存友好的数据结构——B 树块的局部性、分块数组（blocked array）、cache-oblivious 布局（van Emde Boas 递归分块）让任意块大小下的访问都近似最优；4) PMem（持久内存）——字节可寻址、接近内存速度，可用"持久化的 B+ 树/哈希 + 崩溃一致性（undo/redo 日志、CLWB 刷写）"避免传统"内存结构 + 落盘转换"的双份开销。工程要点：按块组织、预取（prefetch）、合并小写（write coalescing）、顺序写优先。

本题考察外存算法设计的总原则：I/O 而非时间。回答时先讲外存模型，再按 B 树、LSM、缓存友好布局、PMem 四类结构讲机制与收益，最后给工程要点。

• 功耗模型：计算、内存、通信的能耗占比
• 近似/降采样：精度换能耗；离线压缩：减少传输量
• 端云权衡：本地计算能耗 vs 传输能耗 + 云端成本/延迟

功耗受限设备的算法设计围绕"能耗预算"展开：先建能耗模型——本地计算（CPU/GPU 能耗）、内存访问（比计算贵）、无线通信（单位数据能耗最高，LTE/5G 传输 1MB 的能耗相当于百万级 CPU 操作）。降耗手段：1) 近似计算——降低精度（float16/INT8 量化、迭代次数截断、采样估计）以减算力；2) 降采样——传感器数据降频、图像降分辨率，只处理关键帧；3) 离线压缩与聚合——数据在端上压缩/聚合（差分、抽稀、聚合成统计量）后再传输，减少通信能耗；4) 唤醒调度——降低采样频率与上报频率、批量上报、空闲休眠（低功耗 MCU 的 deep sleep）。端云卸载的权衡：本地计算的能耗 = 计算能耗，卸载的能耗 = 传输能耗 + 云端计算/网络成本；当本地计算量大（如视频分析、大模型推理）而传输小（如只传结果）时卸载更省电且更快；当数据量大、本地计算轻（传感器聚合）时本地处理更优；还需考虑延迟（实时性）、隐私、网络可用性（弱网）。决策可用"能耗-延迟-精度"三维权衡表：每类任务给定预算（如电池 10% 一天），用 profiling 实测各方案的能耗再选型。典型架构：边缘网关做聚合 + 近似推理，云端做精算，模型按"端上轻量 + 云上全量"分层。

本题考察"能耗作为第一公民"的算法设计：近似与压缩换取能耗，卸载与否取决于通信与计算的相对能耗。回答时先给能耗模型，再列四类降耗手段，最后给端云权衡的判据与决策流程。

• 增量聚合：可分解算子（sum/count/min/max/avg）的 O(1) 增量
• 不可分解聚合：去重计数、分位数需 Sketch/采样结构
• 增量索引：插入维护（B 树、哈希）vs 全量重建（MapReduce）

增量算法维护"随数据到达而变的聚合结果"：1) 增量统计——可分解（decomposable）聚合（SUM、COUNT、MIN、MAX、AVG、GROUP BY 的桶计数）只需保存部分和/桶统计，新数据到达时 O(1) 更新：sum += x、count++、min = min(min, x) 等，删除时反向操作；不可分解聚合（去重计数、中位数、分位数、TopK）需要流式结构：HyperLogLog（基数）、Count-Min Sketch（频次）、Reservoir Sampling（均匀样本）、TDigest/KLL（分位数），它们以近似换常数内存与 O(1) 更新；2) 增量索引——B 树/哈希/LSM 支持插入、删除的 O(log n)/摊还 O(1) 在线维护，倒排索引插入文档时更新词项列表；3) 增量与全量的对比：全量重算每次 O(n)（或 O(n log n)），m 次更新总代价 O(mn)；增量更新每次 O(1)/O(log n)，总代价 O(m + n)——当 m 大、n 大时数量级差异显著；但增量有累积误差与状态膨胀风险（Sketch 的近似误差、过期数据清理），全量重算无状态、结果精确、实现简单，适合低频批量场景。工程取舍：在线低延迟查询用增量，离线批处理/周期性校正用全量（lambda 架构的批层 + 速度层）。

本题考察"增量 vs 全量"的复杂度与一致性权衡：可分解算子增量 O(1)，不可分解用 Sketch。回答时先按算子分类讲增量机制，再对比复杂度与误差/状态风险，最后给架构取舍。

• 硬实时：最坏情形延迟上界（WCET），非平均
• 预计算：查找表、离线排序/索引、位图
• 低延迟结构：无锁、缓存友好、常数级算法

延迟受限场景（高频交易、实时控制、嵌入式）的约束是"最坏情形执行时间（WCET）有上界"，且常为硬性（超期即失败），算法设计围绕"把延迟压到确定的小常数"：1) 预计算——把昂贵计算离线完成：查找表（LUT，如三角函数表）、预排序数据 + 二分、预构建索引/位图、pow/exp 的查表近似，把运行时 O(f(n)) 变成 O(1) 查表；2) 近似——允许精度换时间：浮点近似、截断迭代（早期退出）、采样估计，但需给出误差界并保证"近似也满足正确性需求"；3) 低延迟数据结构——常数级与无锁：环形缓冲区（FIFO O(1) 无锁）、固定大小哈希（开放寻址、无 GC 的语言）、内存池（避免动态分配）、缓存友好的数组布局（AoS/SoA、对齐）、位操作算法（位图索引、popcount）；4) 延迟分配——把总预算（如 1ms）按流水阶段分解（网络 100μs、匹配 200μs、计算 500μs、输出 200μs），每阶段用预计算保证不超期；5) 确定性——避免 GC 停顿、锁竞争、动态分配与分支不可预测，用轮询代替事件、忙等代替休眠。与一般算法优化的差异：普通场景优化"平均"，实时场景保证"最坏"——用 profiling 实测最坏输入下的延迟分布（P99.999）而非均值。

本题考察实时系统的算法设计观：最坏延迟而非平均，预计算换运行时。回答时先讲 WCET 约束，再按预计算、近似、低延迟结构、延迟预算四类手段展开，最后强调确定性。

• Spot/抢占实例：低成本但随时回收；Serverless：按调用计费
• 状态外置：计算无状态化，状态放外部存储（Redis/对象存储）
• 容错重试：检查点 + 幂等重放，成本与延迟的权衡

成本受限场景用低价的弹性算力：Spot/Preemptible 实例（低价但可能被随时回收）、Serverless（按实际调用/时长计费、冷启动延迟）。应对节点回收的核心是"无状态计算 + 状态外置"：计算进程不保存本地状态，中间结果/进度存外部存储（Redis、对象存储、数据库），任务被回收后由其他节点从检查点继续——检查点（checkpoint）按可接受的恢复粒度定期保存，恢复成本 = 最后检查点到回收点的重算量。容错重试：任务记录幂等键（idempotency key），重试时幂等执行（结果去重、副作用一次性），配合指数退避与乱序容错（消息队列的重放语义）。成本与延迟的权衡：1) Spot 越便宜越容易被回收——用"Spot 池 + On-demand 兜底"混合，回收时切到按需；2) 检查点越频繁恢复越快（延迟低）但写检查点成本越高（成本高），按任务价值与失败概率调频率；3) Serverless 的冷启动延迟 vs 常驻实例的成本——低频任务用 Serverless、高频/低延迟用常驻；4) 批处理可容忍高延迟（成本优先：Spot + 大检查点间隔），交互任务要求低延迟（按需实例 + 小检查点间隔 + 预启动）。工程实践：任务队列 + 工作节点无状态 + 检查点表（进度、幂等键）+ 心跳与超时接管。

本题考察"弹性成本环境"的任务调度设计：无状态化与检查点重放。回答时先讲节点回收场景与状态外置原则，再讲检查点与幂等重试机制，最后给成本-延迟的权衡矩阵与工程实践。

• 窗口类型：滚动（tumbling）、滑动（sliding）、会话（session）
• 窗口语义：时间窗口 vs 计数窗口、乱序水位线
• 状态后端：RocksDB 外存状态 + WAL + checkpoint 实现 exactly-once

流处理窗口把无界流切分为有界批次：滚动窗口（tumbling）固定长度互不重叠（每 5 分钟一个窗口）；滑动窗口（sliding）固定长度 + 固定步长（每 5 分钟窗口、每 1 分钟滑动，窗口重叠，元素属多个窗口）；会话窗口（session）按"不活动间隔"切分（间隔超过超时值即结束会话），长度动态、适合用户行为序列（点击会话、登录会话）。窗口类型还有计数窗口（按元素数）与全局窗口，时间窗口需处理乱序：用水位线（watermark）决定窗口何时关闭（迟到数据丢弃或延迟触发）。状态后端：流算子（聚合、窗口、去重、连接）需要保存中间状态；当状态超过内存时用 RocksDB 状态后端——状态以 key-value 存外存（LSM 写优化），RocksDB 的 WAL（预写日志）保证写不丢；exactly-once 通过"状态快照（checkpoint）+ 两阶段提交"实现：周期性对状态做分布式快照（Barrier 对齐，Chandy-Lamport 式），把状态与输出事务绑定，故障时从最近快照恢复并重放，配合幂等输出/事务提交实现"恰好一次"语义（Flink 的 exactly-once 就是 checkpoint + 两阶段提交）。代价：RocksDB 外存状态读写放大与延迟高于内存状态，大状态场景下是吞吐瓶颈，需调优（块缓存、压缩、列族）。

本题考察流处理的两个核心机制：窗口划分（时间语义）与状态管理（容错语义）。回答时先讲三种窗口的划分规则与乱序处理，再讲 RocksDB 状态后端与 checkpoint 两阶段提交的 exactly-once 实现。

• JIT 预热、死代码消除、编译器优化对测量的干扰
• 统计方法：多次运行、剔除异常、置信区间
• 微基准误导：规模、输入分布、硬件状态与真实负载脱节

正确的基准测试要控制测量环境：1) 消除 JIT 影响——JMH（Java）通过预热（warmup，先跑数千次让 JIT 完成编译与内联）、黑盒（Blackhole）防止死代码消除（编译器把未使用结果优化掉）、避免常量折叠（用可变输入）；2) 消除测量噪声——多次运行（≥ 数十次）取分布而非单次、剔除首次与 GC 停顿、控制 CPU 频率（turbo boost 关/固定）、隔离核（CPU pinning）、防内存分页抖动；3) 统计报告——均值 + 置信区间 + 中位数（对异常值稳健），用 hyperfine/criterion（Rust）内置统计与回归检测；4) 控制变量——同一输入、同一规模、同一环境对比。微基准容易误导的原因：微基准测的是"孤立函数在理想输入下的延迟"，与真实负载脱节——真实系统的缓存命中率、分支预测、并发干扰、内存分配模式完全不同；小规模下常数主导（O(n²) 可能更快）、输入分布影响巨大（有序 vs 随机 vs 重复）、硬件状态（频率、缓存预热）不可控；因此"微基准快"不能推断"系统快"，需用宏观基准（真实 trace、端到端）验证，微基准只用于定位热点与比较相对差异。

本题考察基准测试的方法论：测量本身是门工程。回答时先讲 JIT/噪声/统计三类控制手段与工具特性，再分析微基准与真实负载脱节的原因，最后给"微基准定位 + 宏观验证"的建议。

• perf：采样（周期中断记录调用栈）与硬件计数器（cache miss、branch miss）
• FlameGraph：调用栈聚合的可视化，宽 = 占比
• 数据驱动 vs 直觉：先测后改、验证收益

性能剖析（profiling）用数据定位瓶颈：perf 是 Linux 性能工具——采样模式按固定周期中断当前线程并记录调用栈（on-CPU profile），统计各函数/调用栈的样本占比定位 CPU 热点；硬件计数器模式读取 PMU（性能监控单元）事件：L1/L2/LLC 缓存缺失率、分支预测失败率、指令数、IPC，判断瓶颈是计算密集还是访存密集（memory-bound）；perf record + perf report 或导出堆栈生成火焰图。火焰图（FlameGraph）把采样栈聚合成横向堆叠图：x 轴为采样占比（宽 = 开销大）、y 轴为调用深度，从上到下是调用链，能一眼看出"哪个调用路径最热"及其来源（上游谁调的），是定位热点的标准可视化。与直觉优化的差异：直觉优化（猜热点、凭经验改）常改错地方（90% 时间在一个没想到的函数）；数据驱动流程是"profile → 定位 top 热点 → 针对性优化（算法/结构/缓存）→ 重新 profile 验证收益"（每次改动用基线对比，防"优化了不热的地方"）。剖析还分 CPU 剖析（on-cpu）与阻塞剖析（off-cpu，等待 I/O/锁的时间，用延时跟踪如 offcpu 事件）；两者结合才能全面定位（瓶颈可能在等锁/等 I/O 而非 CPU）。

本题考察"先测后优"的方法论：剖析工具的使用与数据驱动决策。回答时先讲 perf 的采样与硬件计数器机制，再讲火焰图的读法，最后对比直觉优化并给出"测-改-验"闭环与 off-cpu 补充。

• 识别：profiling 找高频调用段（热路径）
• 优化手段：分支预测（热点分支前置）、内联、无锁、缓存布局
• 界限：先正确后优化、以实测为准、避免臆测

热路径优化针对"被高频执行的代码段"（如循环体、网络收包路径、日志格式化），原则是先识别后优化：用 profiling（采样/计数器）确认热点（≥ 20% 时间段的函数），针对热点做定向优化：1) 分支预测——把高频分支放最前（likely/unlikely 提示、if 顺序调整）、用查表/位运算替代分支（branchless）、避免可预测性差的分支；2) 内联——小函数内联减少调用开销（编译器 hot attribute、手动内联），但注意 I-cache 膨胀；3) 数据局部性——热数据按访问顺序布局（AoS/SoA）、热字段合并到同一缓存行；4) 减少分配与锁——对象池、无锁/细粒度锁；5) 循环优化——展开、向量化、循环内变量提升。与过早优化的界限：过早优化 = 在"没有性能证据"时猜测性地优化，浪费开发时间且可能恶化可读性/正确性；正确顺序是"先写出正确清晰的实现 → profiling 定位真实热点 → 只优化热点 → 每次优化用基准验证收益"。判断标准：是否有测量数据支撑（热点占比）、优化是否影响正确性/可维护性、收益是否可验证；对"知道会热"的段（如已被证明的热循环）可以提前设计，但必须尽快用测量确认。

本题考察"测量驱动优化"的纪律：热路径要识别、优化要对症、界限以证据为准。回答时先讲识别与四类优化手段，再讲过早优化的定义与正确流程，最后给判断标准。

• Amdahl：加速比 ≤ 1/(s + (1-s)/p)，需 s 极小
• 可扩展性：并行开销（同步/通信）随规模增长
• 图算法并行化：稀疏图的负载不均与同步开销

并行加速比的核心限制是 Amdahl 定律：加速比 ≤ 1/(s + (1-s)/p)，其中 s 为串行部分占比。含义：若 s = 10%，即使无限核加速比也不超过 10 倍——要获得高加速比，串行部分必须极小（s → 0），且当 p 增大时 (1-s)/p → 0，加速比趋于 1/s，核数的边际收益递减。并行效率（efficiency）= 加速比/p，随核数增多因通信与同步开销而下降（可扩展性分析：固定负载 vs 固定时间两种 scaling）。并行网络/图算法的效率挑战：1) 稀疏图（邻接表）的负载不均——按顶点/边划分时各分区的计算量差异大，需动态负载均衡（工作窃取）；2) 同步开销——BFS/最短路径的逐层同步（每层一次 barrier）、迭代算法的全局收敛检查（allreduce 判断是否继续）；3) 通信量——顶点状态交换（消息传递）与聚集，分布式图计算（Pregel 的 BSP 模型、GraphLab）中通信可能主导；4) 不规则访问——邻接表指针跳转破坏缓存与向量化。效率衡量：用"工作效率（work-efficient：总工作量与串行同阶）"与"深度（并行步数）"双指标（如并行 BFS 是 work-efficient O(m+n)、深度 O(D)），实际加速比受 1/(同步开销) 限制，稠密规则图比稀疏不规则图并行收益大。

本题考察并行算法的两个层面：Amdahl 的串行占比约束与图算法特有的负载/同步问题。回答时先讲 Amdahl 与效率定义，再讲图算法并行的三类障碍与双指标分析，最后给实践建议。

• Raft：单领导者 + 日志复制 + 多数派提交实现线性一致
• 读优化：ReadIndex/Lease Read 保线性一致
• CAP：网络分区下一致性 vs 可用性的选择

Raft 通过"单领导者 + 多数派复制"实现线性一致写：客户端把写请求发给领导者，领导者写入本地日志并复制到多数派（quorum）后才提交并返回——因为任何两个多数派集合必有交集，已提交日志不可能被新领导者覆盖（选举约束：候选人必须包含已提交日志），从而所有已提交写有全局一致顺序。线性一致读的关键是"读到最新已提交状态"：直接读领导者本地状态可能读到旧值（领导者可能已失联/被分区，其日志已落后），因此需要 ReadIndex（读前向多数派确认自己仍是领导者并拿到最新提交索引，再本地读）或 Lease Read（租期内假定领导者不变，免去每次确认）——它们保证"读发生在某次写提交之后"的实时顺序。CAP 的工程含义：网络分区（P）不可避免，此时必须在一致性（C：分区两侧不能同时响应）与可用性（A：任何一侧都响应）之间取舍——CP 系统（ZooKeeper、etcd/Raft）分区时拒绝少数侧写入保证一致；AP 系统（Cassandra、Dynamo）分区时两侧都可写、用最终一致/冲突解决收敛；"CA"在分布式下不存在。工程含义：按业务需求选型——强一致需求（金融、锁、协调）用 CP；高可用 + 可最终一致（社交 feed、购物车）用 AP；并用一致性级别参数（如 Cassandra 的 quorum/one）按操作粒度调整。

本题考察分布式一致性的落地：Raft 的读写路径与 CAP 的工程选择。回答时先讲写线性一致（多数派 + 选举约束）与读线性一致（ReadIndex/Lease），再讲 CAP 的取舍逻辑与系统分类，最后给工程选型。

• Avalanche：随机子采样投票（每次问 k 个节点）+ 偏好更新
• 收敛：偏好多数时被翻转概率指数下降，高概率收敛
• 与 PBFT：无领导者、概率性安全 vs 确定性安全、拜占庭假设

Avalanche 共识是"无领导者 + 随机抽样投票"的概率性共识：每个节点维护对候选事务的偏好，重复执行"随机选取 k 个节点（子采样）询问其偏好，若多数偏好某候选则更新自己偏好（计数超过 α 阈值）"，经过足够多轮，正确候选的偏好占比像"Polya 瓮"一样滚雪球增长，错误候选被翻转的概率指数下降，最终全网以高概率收敛到同一偏好。收敛的直觉：初始任意分布下，正确偏好占比 > 1/2 的轮次会使支持者增加，随机化使"支持率向占优方集中"，偏差越大翻转概率越小，形成正反馈；安全性是概率性的（允许极小概率出错），活性（liveness）在高概率下保证。与 PBFT 的差异：1) 通信模型——PBFT 是确定性 BFT：固定验证者集合、视图 + 三阶段（pre-prepare/prepare/commit）消息、需要 n ≥ 3f+1 节点（f 为拜占庭数），安全性确定性保证（不可推翻的提交）；Avalanche 是"随机化 + 概率安全"，无需视图与固定领导者，吞吐随参与度可扩展；2) 假设——PBFT 需要同步/部分同步假设与身份认证（签名），Avalanche 基于采样统计（假设拜占庭比例 < 1/3 时收敛），对"女巫攻击"依赖质押/身份（权益证明）；3) 适用性——PBFT 用于许可链/联盟链（确定性、低延迟），Avalanche 用于开放网络（大规模、高吞吐、最终确认概率化，如雪崩协议族 Avalanche/Snowball/Slush）。

本题考察两类共识范式的对比：确定性 BFT 与概率性抽样共识。回答时先讲子采样投票机制与收敛直觉，再对比 PBFT 的消息流程、拜占庭假设、安全性与适用场景。

• DPoS：持币人投票选出少量见证人出块，吞吐高
• PoH（Proof of History）：可验证延迟函数（VDF）生成时间戳序列
• 安全假设：DPoS 依赖少数可信出块者，PoH 依赖 VDF 的单向延迟

DPoS（Delegated Proof of Stake，如 EOS）通过"委托投票"压缩共识参与者：持币人投票选出少量（如 21 个）见证人/超级节点轮流出块，出块权确定性轮转、无需挖矿竞争，区块确认快、吞吐高（EOS 数千 TPS）；安全假设是"见证人集合诚实"——若多数见证人被贿赂/合谋则可能审查或重组，因此依赖代币质押（作恶被 slash）与投票的民主性；它牺牲了"任何节点可出块"的开放性与去中心化程度换取效率。PoH（Solana）：用可验证延迟函数生成一串"可验证的时间戳"（对前一哈希反复执行 VDF 得到序列，每个输出带序号，验证者可快速验证但无法并行加速生成），节点以 PoH 序列作为全局时钟协调出块顺序，避免传统共识的消息往返（无需等广播确认即可排序），配合流水线（TPU/GPU 并行处理）实现高吞吐（数万 TPS）；安全假设是 VDF 的单向性（生成慢验证快，攻击者无法伪造时间顺序）与网络带宽（PoH 依赖节点间同步序列，实际以乐观并发 + 验证者的快速确认保证），其安全性模型更接近"高效确认 + 概率安全"而非经典 BFT 的确定性。两者对比：DPoS 用"少节点 + 委托"降共识开销，PoH 用"可验证时钟 + 流水线"降排序开销，都牺牲部分去中心化/确定性换取吞吐。

本题考察共识效率优化的两条路线：减少参与者（DPoS）与减少通信/排序开销（PoH）。回答时分别讲机制、吞吐来源与安全假设，最后对比两者的取舍。

• 惰性执行：操作构建 DAG，compute() 触发执行
• 调度：任务图分层、依赖拓扑、多进程/线程/分布式调度器
• 与 Spark：行级 vs 分区级粒度、Python 原生 vs JVM 批处理

Dask 把 Python 计算表示为惰性任务图：用户调用 dask 集合（array/dataframe/delayed）的操作时不立即执行，而是构建一个有向无环图（DAG）——节点是函数调用（任务），边是数据依赖；调用 compute() 时，调度器按依赖拓扑把任务分发给工作进程（多进程/线程/分布式 scheduler），并行执行并缓存中间结果。调度特点：任务粒度是"函数级"（每个 Python 函数调用一个任务），支持细粒度依赖（比阶段式更灵活），数据在任务间以序列化后的对象传递；分布式调度器（distributed）提供动态负载均衡、工作窃取与容错重试。与 Spark 的差异：1) 粒度——Dask 任务粒度细（函数调用级），Spark 以"分区（partition）级"为调度单元（宽窄依赖划分 stage，stage 内任务并行），调度开销 Dask 更细但 Python 函数调用开销大；2) 语言与生态——Dask 直接操作 Python 对象（NumPy/Pandas 兼容 API），Spark 是 JVM 的 RDD/DataFrame 批处理引擎（PySpark 通过桥接），Spark 的 SQL/流/ML 生态更全、优化器（Catalyst）更强；3) 执行模型——Spark 是"阶段 + shuffle"的批式模型（宽依赖触发 shuffle），Dask 是"任意 DAG + 动态调度"（更灵活但 shuffle 优化弱）；4) 适用性——Dask 适合 Python 生态内的中型分布式计算（单机多核/小集群），Spark 适合大规模数据工程（数 TB 级、SQL 分析、生产化）。

本题考察两类"数据流引擎"的差异：惰性 DAG 的 Python 原生实现 vs JVM 批处理引擎。回答时先讲 Dask 的构建-调度流程，再对比 Spark 在粒度、优化器、执行模型与生态上的差异。

• Flink：事件级流处理，Barrier 对齐的分布式快照（checkpoint）
• exactly-once：状态快照 + 两阶段提交/幂等输出
• 与 Spark Streaming：微批（小批次）vs 逐事件、延迟与吞吐差异

Flink 是逐事件（event-at-a-time）流处理引擎：每个事件独立被算子处理（无需等批次），通过 checkpoint 实现容错与一致性。checkpoint 机制（Chandy-Lamport 分布式快照）：周期性地在数据流中注入 Barrier 标记，算子收到 Barrier 后把本地状态做快照（异步写外部存储），Barrier 按算子拓扑对齐（align）保证快照一致性（每算子快照对应同一逻辑时刻）；故障时从最近快照恢复状态并重放日志。exactly-once 的落地：状态恢复 + 输出一致性用两阶段提交（sink 参与 checkpoint，预提交-提交协议，如 Kafka sink）或幂等写入/事务输出，保证每条数据对状态与外部系统的影响恰好一次（配合可重放源与幂等 sink）。与 Spark Streaming 的差异：1) 处理模型——Spark Streaming（结构化流）是"微批"：把到达数据按时间切成小批次（默认秒级），用批处理引擎（Spark SQL）逐批执行，延迟 = 批次间隔（秒级），吞吐高（批处理优化成熟）；Flink 逐事件处理，延迟毫秒级，事件时间语义（水位线）原生；2) 一致性——微批天然"批内一致"、批间靠 checkpoint（Spark 的 offset 管理 + 幂等输出）达到 exactly-once；Flink 的 barrier 快照提供流式 exactly-once；3) 适用性——Flink 适合低延迟、事件时间、复杂窗口/CEP（复杂事件处理）；Spark Structured Streaming 适合与批处理共享生态（同一引擎跑批+流）、秒级延迟可接受的场景；两者都支持 exactly-once，差异在延迟与 API/生态。

本题考察流引擎的两大机制：Flink 的快照一致性（Barrier + 两阶段提交）与微批模型（Spark）的对比。回答时先讲 Barrier 对齐快照与 exactly-once 实现，再对比微批的延迟/吞吐/语义差异。

• 思想：用可接受的精度/风险换数量级资源节省
• 手段：近似（Sketch、量化）、采样（估计）、离线预处理（索引/缓存）
• 典型例子：流式频次（Count-Min）、基数（HLL）、学习型索引、缓存

节俭计算（frugal computing）的核心是"以可控的精度/概率换取数量级资源节省"：不做精确计算，而用三种杠杆——1) 近似：用有界误差的数据结构替代精确结构，如 Count-Min Sketch（频次估计，O(1) 空间 vs 精确计数 O(n)）、HyperLogLog（基数估计，KB 级空间估数亿基数）、Bloom Filter（集合成员判断，假阳性换 90%+ 空间）、量化压缩（float32→int8 降 4 倍内存）；2) 采样：用随机样本估计总体，如蓄水池抽样（流上均匀样本）、随机投影（LSH 降维）、A/B 测试的样本量控制，误差随样本量 √ 级下降（n=10000 样本误差 ~1%），换时间/内存数量级节省；3) 离线预处理：把计算移到低峰期/离线完成——预计算索引（学习型索引、ANN 建图）、缓存热点结果（LRU）、物化视图/预聚合（数据立方体），在线查询变成查表。典型例子：大数据频次统计（近似 TopK）、网站 UV 统计（HLL）、拼写检查的字典过滤（Bloom）、推荐召回（ANN + 近似）、数仓的预聚合。适用边界：精度要求高、最坏情形重要、数据量小或一次性任务时不划算；工程上用"误差上界 + 概率保证"量化收益（如"99% 置信度误差 < 1%"），并按业务可接受度选型。

本题考察"精度-资源"的交换思维：三杠杆的机制与数量级收益。回答时按近似、采样、离线预处理三类给出结构与收益，再举典型例子，最后给适用边界与量化方法。

• RDMA：网卡直接读写远端内存（InfiniBand/RoCE），绕过内核与 CPU
• GPU Direct：GPU 显存 ↔ 网卡直接 DMA（绕过主机内存与 CPU 拷贝）
• NCCL：集合通信库用 GPU Direct RDMA 提升 allreduce 带宽，需硬件支持

GPU Direct RDMA（GDR）让 GPU 显存与远端 GPU 显存之间直接传输，路径为"GPU 显存 → PCIe → 网卡 → 网络"，完全绕过主机内存（CPU 内存）与 CPU 参与：普通路径（GPU→CPU 内存→网卡）需要两次 DMA 与 CPU 拷贝，GDR 直接把 GPU 显存映射给网卡（GPUDirect 的 peer memory 机制），消除主机内存中转与 CPU 干预，降低延迟并提升带宽。RDMA 本身（InfiniBand/RoCEv2）提供内核旁路（用户态直接发报文）与零拷贝（网卡硬件读写内存），是低延迟高带宽的传输基础。在分布式训练中，NCCL（NVIDIA 集合通信库）实现 allreduce/allgather 等操作：启用 GDR 后，梯度在 GPU 显存间直接聚合（ring allreduce 的每步传输都是 GPU↔GPU 直连），bandwidth 显著提升（相比 PCIe 中转可提升数倍，接近网卡线速），延迟降低；NCCL 还利用 NVLink 做节点内互连，形成"节点内 NVLink + 节点间 RDMA"的分层通信。部署条件：1) 硬件——支持 GDR 的网卡（Mellanox InfiniBand/RoCE）、PCIe peer-to-peer 支持（P2P）、GPU 与网卡同 PCIe 拓扑（减少跨 PCIe 交换机）；2) 软件——驱动开启（GPUDirect 支持、nv_peer_mem 内核模块）、NCCL 环境变量（NCCL_P2P/NCCL_IB_GDA）、IOMMU 配置（直通或关）；3) 拓扑感知——按 PCIe 拓扑优化分组（NCCL topo 文件），否则跨 NUMA/PCIe 域时收益下降；4) 风险——P2P 与虚拟化（VM）兼容性、稳定性与驱动版本敏感。

本题考察高性能网络栈的"路径缩短"思想：GPU 直接与网卡 DMA。回答时先讲 GDR 的传输路径与 RDMA 机制，再讲 NCCL 中的收益（allreduce 带宽），最后列部署条件与风险。

• MapReduce 三阶段：map → shuffle（分区+排序）→ reduce
• shuffle：按 key 哈希分区 + 排序（相同 key 归并到同一 reduce），是"分组"的实现
• Combiner：map 端本地聚合（如求和）减少跨网络传输

MapReduce 的执行模型：map 阶段把输入拆成 (key, value) 中间对；shuffle 阶段把中间结果按 key 分区（哈希/范围分区）并排序，使"同一 key 的所有 value 被送到同一个 reduce 任务且有序"；reduce 阶段按 key 分组处理。shuffle 是关键步骤的原因：它实现了"按 key 分组"（分布式分组的核心，等价于 SQL 的 GROUP BY 与 join 的按键汇聚），分区决定负载均衡（key 倾斜需分区器优化）、排序保证 reduce 收到有序流（可合并、可提前终止，如 join 的 sort-merge），且 shuffle 的网络传输量通常是作业的主要开销（I/O 与带宽瓶颈），其效率决定整体性能。Combiner 是"map 端的 mini-reduce"：在 map 任务内先对本地 (key, value) 做聚合（如求和/计数/去重），把多个 (k, v) 合并成 (k, 聚合值) 再进 shuffle——减少网络传输的中间数据量与 reduce 的输入量（如 100 万条词频 → 本地合并后几万条），显著降低 shuffle 带宽与 reduce 负载；约束：Combiner 函数必须满足"结合律且可交换"（结果与合并顺序无关，如 sum/max/count 可以，平均值不行），否则会改变结果。工程要点：分区器（partitioner）保证 key 均匀分布、合并器（combiner）减少传输、压缩中间数据。

本题考察 MapReduce 的架构要点：shuffle 是分组与负载均衡的枢纽，Combiner 是传输优化。回答时先讲三阶段与 shuffle 的分区排序机制，再讲 Combiner 的预聚合流程与约束（可结合可交换），最后给工程优化点。

• PBFT：三阶段（pre-prepare/prepare/commit）+ 视图切换 O(n³)
• HotStuff：链式三阶段 + 门限签名 + 线性视图切换（O(n)）
• 两者都假设 n ≥ 3f+1、部分同步

PBFT（Practical Byzantine Fault Tolerance）是经典确定性 BFT：正常路径三阶段（pre-prepare → prepare → commit，每阶段全网广播 2f+1 确认），视图切换（换主）时需各节点互相交换视图消息并收集证书，消息复杂度 O(n³)；每次共识需多轮广播，吞吐受限。HotStuff（LibraBFT 基础）的改进：1) 链式三阶段——把 pre-prepare/prepare/commit 变成链上的三轮投票（每轮提案引用前轮投票证书，形成链），每个提案只要一轮 prepare + 一轮 commit 即可，正常路径消息复杂度 O(n)；2) 门限签名——把 2f+1 个签名聚合为一个门限签名（阈值签名/聚合签名），证书（QC）从"O(n) 个签名"变为"一个聚合签名"，广播的消息体大幅缩小；3) 线性视图切换——切换视图时新主只需广播一条包含最新 QC 的消息（其他节点用 QC 验证），无需 PBFT 的 O(n³) 全交换，视图切换复杂度 O(n)。BFT 假设的异同：相同——都假设拜占庭节点数 f < n/3（n ≥ 3f+1）、网络部分同步（最终同步），保证安全性（不可能同时破坏 safety 与 liveness 的经典下界）；不同——PBFT 的视图切换在"主节点故障"时触发且参与节点都需活跃（同步假设严格），HotStuff 用"响应式"（reactive）方式：新主从 QC 恢复，无需节点间互相证明，配合门限签名使协议更简单、可流水线化（连续提案不断链）。工程上 HotStuff 适合状态机复制的高吞吐场景（Libra/Diem），PBFT 适合小规模联盟链。

本题考察 BFT 协议的演进：从 O(n³) 消息到 O(n)。回答时先讲 PBFT 的三阶段与视图切换代价，再讲 HotStuff 的链式投票、门限签名与线性视图切换三个改进，最后对比 BFT 假设的相同与差异。

• Paxos：无固定领导者的多阶段协商（prepare/accept），可并行多提案
• Raft：强领导者 + 任期 + 日志复制 + 多数派提交
• 多数派读写：quorum 交集保证线性一致，读优化（ReadIndex/Lease）

Paxos 与 Raft 都解决"状态机复制/共识"，多数派（quorum）读写的本质相同：任何两个多数派有交集，提交日志不可能被覆盖，故写操作（提交）与读操作（读最新提交）可满足线性一致。工程差异在设计与可实现性：Paxos 是"无固定领导者"的多阶段协议（prepare/accept 两轮，可多个提案并发协商），它把共识抽象为"值选择"原语，理论优雅但工程复杂——多提案活锁、领导权轮换、日志的间隙（gap）管理、状态机如何组装 Paxos 均未规定，实现易错（著名的"Paxos 难实现"）；Multi-Paxos 用选出的领导者减少 prepare 轮次，但仍需处理领导者重选与日志补洞。Raft 的简化：1) 强领导者——所有写经当前领导者（任期 term + 选举超时随机化保证唯一领导者），无需并发提案协商；2) 日志复制（append entries）——领导者把日志按序复制到多数派即提交，跟随者只追加，日志严格有序无间隙（领导人补齐）；3) 选举约束——候选人日志必须"更完整"（比较最后日志任期与索引）才可能当选，保证已提交日志不丢失，避免 Paxos 的复杂证明；4) 明确的角色状态机（leader/candidate/follower）与任期机制使实现可测试。多数派读写的落地：写走领导者 + 多数派提交；读为线性一致需 ReadIndex（确认领导者 + 最新提交索引）或 Lease Read（租期免确认）；读多数派（quorum read）也可直接保证线性一致但代价高，故工程常用领导者 + 索引确认。

本题考察共识协议的设计取舍：Raft 用工程简化换取可实现性。回答时先讲两者的多数派交集本质，再讲 Paxos 的复杂点与 Raft 的强领导者/日志复制/选举约束三个简化，最后讲读的线性一致实现。

• Ray 核心抽象：task（无状态函数调用）+ actor（有状态对象）
• 弹性调度：对象存储（分布式共享内存）+ 动态资源（GPU/CPU 需求）
• 与 Dask/Spark：细粒度、动态任务图 vs 阶段批式、对象语义差异

Ray 是为"Python 细粒度分布式计算"设计的系统，两个核心抽象：task——远程函数调用（@ray.remote 装饰的函数），每次调用是一个任务，返回 ObjectRef（分布式对象引用）；actor——有状态的远程对象（类实例驻留在某节点，方法调用即远程执行），用于维护状态与 GPU 等资源。调度机制：任务/actor 声明资源需求（CPU/GPU/内存数），Ray 的 GCS（全局控制存储）维护集群资源状态，调度器按资源可用性与数据局部性分配（优先调度到输入 ObjectRef 所在节点），对象存储在节点间共享内存（Plasma）中传输数据（零拷贝反序列化）；动态弹性：节点可随时加入/退出，资源实时更新，配合自动缩放（autoscaler）按负载增删节点。与 Dask/Spark 的差异：1) 粒度——Ray 的任务粒度是"函数调用级"且任务图动态（运行时可 spawn 新任务），Dask 也是惰性任务图但偏向集合 API（array/dataframe）与批式调度，Spark 是"阶段 + 分区"的批式模型（宽依赖划分阶段），细粒度与动态性 Ray 最强；2) 数据语义——Ray 的对象是"引用传递 + 分布式内存"（可变对象语义、零拷贝），Spark 的 RDD/DataFrame 是"不可变分区集合 + shuffle"，Dask 介于两者；3) 适用——Ray 适合强化学习、超参数搜索、在线服务（Serve）与需要细粒度状态/动态调度的应用，Spark 适合大规模离线批处理与 SQL，Dask 适合 Python 数据科学生态内的并行。

本题考察三种 Python/分布式计算框架的定位：task/actor 模型 vs 集合/阶段模型。回答时先讲 Ray 的 task/actor 与弹性调度机制，再对比 Dask/Spark 在粒度、数据语义与适用场景的差异。

• Count-Min：频率估计，误差 ε·N 上界，空间 O(1/ε log 1/δ)
• HLL：基数估计，相对误差 ~1.04/√m，空间 O(log log N)
• Misra-Gries：频繁项（保证出现 εN 次以上的项必被找到），空间 O(1/ε)

三种 Sketch 解决不同问题：1) Count-Min Sketch——频率估计（统计流中每个元素的出现次数）：用 d 个哈希函数 + d×w 计数器矩阵，插入时对 d 个桶计数，查询取 d 个桶的最小值；误差上界：以概率 1-δ，估计误差 ≤ ε·N（N 为流总长度），空间 O((1/ε)·log(1/δ))（d = log(1/δ)、w = 2/ε），时间 O(d) 每元素；是"频率估计"的标准结构（偏向高估）。2) HyperLogLog——基数估计（流中有多少不同元素）：用哈希值的前缀零个数估计基数，m 个寄存器时相对误差 ~1.04/√m，空间 O(m)（m = 16384 寄存器约 12KB 可估数十亿基数，即空间 O(log log N) 量级）；适合 UV、去重计数。3) Misra-Gries（多数投票家族）——频繁项检测：维护 k-1 个候选及其计数，新元素命中候选则计数 +1，否则所有计数 -1（计数归零的候选移除）；保证"出现次数 > N/(k) 的元素必在候选中"（找频繁项），空间 O(k)（取 k = 1/ε 时找出现 εN 次以上的项），一次扫描、无概率误差（确定性）。选型矩阵：需求"每元素频率估计"用 Count-Min；"不同元素个数"用 HLL；"找出高频项/多数元素"用 Misra-Gries（或 HeavyKeeper/Count-Min 变体配合 TopK）；组合使用（HLL 估基数 + Count-Min 估频率 + 布隆过滤成员）可构建流式统计工具箱。

本题考察流式近似结构的"问题-结构"匹配：每个 Sketch 回答一类问题。回答时逐一讲机制、误差/空间边界与确定/概率性，最后给选型矩阵与组合建议。

• RDD 血统：记录父 RDD 与转换函数（谱系图）
• 恢复：从源头重放转换重算丢失分区（懒惰、无副本开销）
• 取舍：长血统重算代价高 → checkpoint 截断血统

Spark 的 RDD（弹性分布式数据集）容错基于血统（lineage）：每个 RDD 记录"如何从父 RDD 转换而来"（依赖关系 + 转换函数），形成谱系 DAG。分区丢失（节点故障）时，从最近的可用父分区出发重放转换重新计算丢失分区，无需存储数据副本——优点：存储零开销（只有元数据与函数引用）、重算只涉及丢失分区的依赖路径、天然支持"任意阶段恢复"；代价是重算时间：长血统（几十次转换）或高成本转换（shuffle、join、训练迭代）重算代价高。检查点（checkpoint）的取舍：checkpoint 把中间 RDD 的物化结果持久化到可靠存储（HDFS/对象存储），截断血统——恢复时直接从检查点读取而非重算；代价是写入 I/O 开销（物化成本）与存储空间。取舍规则：血统短、转换便宜（过滤、映射）→ 用血统重算（默认，零额外开销）；血统长或转换昂贵（shuffle、迭代算法如 PageRank/ML 迭代）→ 在关键节点 checkpoint（典型：迭代中的每 N 次迭代 checkpoint 一次，避免"全链重算"）；Spark Streaming 的每个批次也周期性 checkpoint 状态。工程注意：checkpoint 会改变 RDD 血缘（截断），需在"预计重算代价 > checkpoint 代价"时使用；配合持久化级别（MEMORY_ONLY/DISK）在内存与磁盘间权衡。

本题考察"计算 vs 存储"的容错权衡：血统用重算免副本，checkpoint 用存储截断血统。回答时先讲血统机制与重算流程，再讲 checkpoint 的物化与截断，最后给取舍规则与工程注意。

• TLA+ 规范：状态变量 + Init + Next（非确定性动作）
• 安全性不变量：不变量声明 + TLC 模型检查穷举状态
• 状态爆炸：节点数/消息/值域的组合爆炸，需对称约减与抽象

TLA+ 用"状态机 + 时序逻辑"描述分布式协议：规范 = 状态变量集合（如日志、投票、任期）+ Init（初始状态）+ Next（所有合法状态转移，用非确定性选择模拟并发与拜占庭行为）；安全性（safety）用不变量表达（如"多数派提交的日志不相冲突"、"不会出现两个不同值都提交"、"领导者单调"），活性（liveness）用时序公式（如"最终会提交"）。验证流程：用 TLC 模型检查器对有限实例穷举搜索——从 Init 出发按 Next 枚举所有可达状态，检查每个状态是否满足不变量，违反时输出反例轨迹（具体操作序列）定位协议 bug；Raft/Paxos 的著名验证（Lamport 的 Paxos 规范、Raft 的 TLA+ 规范）就是用这种方式发现边界 bug（如日志覆盖、选举安全）。状态爆炸：模型检查的可达状态数随"节点数 × 消息数 × 值域 × 序列深度"指数增长——如 5 节点、2 值、消息乱序的 Paxos 可达数百万状态；爆炸时用抽象与约减：对称性约减（节点/值互换视为同态）、数据抽象（把值域抽象为少数代表值）、协议分层（先验证抽象层再细化）、随机化 TLC（深度优先 + 随机选择）在无法穷举时找反例。经验法则：单参数模型（固定节点数 n ≤ 5、固定消息上限）在百万级状态内可验证；参数增大（n = 7+、无限消息）即爆炸，需抽象或改用定理证明（TLAPS）。

本题考察形式化验证分布式协议的实操：建模 → 不变量 → 模型检查 → 爆炸处理。回答时先讲 TLA+ 的状态机规范与不变量，再讲 TLC 验证流程与反例价值，最后讲状态爆炸的原因与约减技术。

• Tendermint：两轮投票（预投票/预提交）+ 锁定期（lock）
• 安全性：锁定期防止已锁定提案被覆盖，两轮投票保证多数派一致
• 与 PBFT：视图切换（换 proposer）只广播锁与投票信息，复杂度低

Tendermint 是权益证明的 BFT 共识（Cosmos 使用）：每个高度（round）由轮值 proposer 提出区块，经历两轮投票——pre-vote（预投票，2/3+ 赞成后进入）与 pre-commit（预提交，2/3+ 赞成后锁定并提交），任一时刻节点可因超时发起换轮（轮次递增、新 proposer）。锁定期机制：节点一旦 pre-commit 某个区块就"锁定"它，在后续轮次中只对锁定的区块投 pre-vote（除非看到更高轮次的证明），并广播自己的锁信息；锁 + 两轮投票保证安全性：因为任何两轮投票的 2/3 集合必有交集，一个区块若被 pre-commit（2/3 预提交），后续轮次中不可能有另一区块获得 2/3 的 pre-commit（锁定的节点不会投新提案，除非新提案有"解锁证明"——即更高轮次中 2/3 预投票了它，而那是旧提案尚未提交的合法场景），从而避免"双提交"（安全性）；活性通过超时换轮保证（liveness）。与 PBFT 的简化：PBFT 正常路径三阶段（pre-prepare/prepare/commit）+ 复杂视图切换（节点交换视图消息、收集 2f+1 证明，O(n²) 消息）；Tendermint 的换轮只需广播"锁与投票信息"（新 proposer 据此提案），无需全视图交换，消息复杂度更低（每轮 O(n)），且协议更简单、可流水线化；两者都要求拜占庭 < 1/3、部分同步，但 Tendermint 把"视图切换"融入轮次机制（超时自动换轮）而非独立协议。

本题考察 Tendermint 安全性的核心论证：锁定 + 两轮投票 + 轮次超时。回答时先讲两轮投票流程与锁定机制，再论证"为何不会双提交"，最后对比 PBFT 的视图切换简化。

• 批处理：全量离线分析、ETL、数据仓库（延迟容忍）
• 流处理：实时事件、窗口聚合、告警（低延迟）
• 图计算：BSP 迭代（PageRank、最短路径、社区发现）

三类框架对应三类负载特征：1) 批处理（MapReduce/Spark）——数据全量、结果延迟容忍（分钟-小时级）：离线 ETL、数仓分析、报表、机器学习特征批量构建；特点：吞吐优先（压缩、列存、shuffle 优化）、一次性/周期执行、容错靠重算/检查点；Spark 的批 + SQL 生态最强。2) 流处理（Flink/Kafka Streams）——持续到达的事件流、延迟敏感（毫秒-秒级）：实时监控告警、实时聚合（窗口）、事件驱动应用、CDC 同步；特点：逐事件/微批处理、水位线与事件时间、exactly-once、状态管理；需要"实时性"时选流，能容忍秒级延迟且要批流一体时选 Spark Structured Streaming。3) 迭代图计算（Pregel/Giraph/GraphX）——图结构数据的迭代算法：PageRank、单源最短路径、连通分量、社区发现、推荐（图上迭代）；特点：BSP（整体同步并行）模型——每轮所有顶点并行处理消息，同步后进入下一轮，直到收敛；适合"每步依赖上一步全局结果"的迭代；图规模大且算法是迭代传播型时用 Pregel 类系统（比 MapReduce 逐轮重读高效），数据小/单机可用内存图算法。选型矩阵：按"延迟要求（批 vs 流）× 计算形态（表 vs 图）"选：表数据 + 容忍延迟 → Spark/MapReduce；表数据 + 实时 → Flink；图数据 + 迭代 → Pregel 类（或图数据库）；混合场景用批流一体（Flink 批流、Spark 批 + Structured Streaming）。

本题考察框架-负载匹配：延迟与计算形态两个维度。回答时按三类框架讲机制与典型负载，最后给二维选型矩阵与混合场景建议。

• 分治：划分（partition）+ 递归/归并（merge）
• 外排序：分块排序 + 多路归并；两阶段聚合：map 端局部 + reduce 端合并
• 减少 shuffle：分区器、局部聚合（combiner）、倾斜处理

分治是大数据处理的通用骨架：把大规模问题拆成可并行的小块（划分），各自处理后合并（归并）。三个典型应用：1) 外排序——数据超内存时"分块内部排序生成有序段 + k 路归并"，与内存排序的 O(n log n) 时间、I/O 趟数 ⌈log_k(N/M)⌉ 的划分-归并结构完全一致，只是"块"由内存决定；2) 分布式聚合（两阶段归并）——map 阶段每个分片本地聚合（combiner：局部求和/计数），shuffle 按 key 分区后 reduce 阶段合并各分区结果——正是"分治：每块算局部答案，再合并全局答案"；对可分解聚合（sum/count/min/max）局部聚合无损，对不可分解（去重/中位数）需"两阶段 + 近似/采样"；3) MapReduce 的契合——map 是划分后的独立计算（可并行、无依赖），reduce 是归并（按 key 合并），shuffle 是"按 key 划分到归并者"的枢纽，天然分治。减少 shuffle 的关键：1) 分区器——按 key 哈希/范围均匀分区，避免数据倾斜（热点 key 单独分区或加盐）；2) map 端局部聚合（combiner）——把同 key 的中间结果先合并再传输，网络量降一个数量级；3) 倾斜处理——热点 key 打散（加随机后缀再二次聚合）、动态分区、skew join（广播小表）；4) 压缩中间数据。分治原则贯穿：先划分均衡、再局部计算、后高效归并，每步都是"减少跨节点数据量"。

本题考察分治在大数据系统的贯穿性：划分-归并结构与 shuffle 优化。回答时先讲三个应用的划分-归并骨架，再重点讲减少 shuffle 的四类手段（分区、combiner、倾斜、压缩）。

• 缓存局部性：时间/空间局部性，数据布局与访问顺序
• SIMD：数据级并行（一次处理多元素），带宽利用
• cache-oblivious：与缓存大小无关的递归分块布局（van Emde Boas）

常数优化分三个层次：1) 缓存局部性——优化内存访问模式：空间局部性（访问连续内存，用数组替代链表、结构体数组 AoS/SoA 选择、块状遍历）、时间局部性（重用热数据，循环融合/分块 tiling），目标是让热数据留在 L1/L2；2) SIMD 向量化——数据级并行：用 SSE/AVX 一次处理 4-16 个元素（循环向量化、手动 intrinsics），针对"计算密集 + 数据规整"的循环（过滤、聚合、矩阵乘），配合内存对齐（avx 需 32 字节对齐）与避免 gather/scatter（随机访问不向量化）；3) cache-oblivious 布局——设计"对任意缓存大小都友好"的递归分块：van Emde Boas 布局把矩阵/数组按 √ 大小递归分块存储，使任何层次缓存的访问都近似最优（cache-oblivious matrix multiplication、二分搜索的递归布局），无需知道具体缓存参数。用 profiling 定位瓶颈：先测"访存 vs 计算"类别——perf 的 cache-misses（LLC 缺失率）、IPC（每周期指令数）、bandwidth（内存带宽利用率）、branch-misses：若 cache-misses 高 → 优化布局/分块；若 IPC 低但计算密集 → 向量化/减少依赖链；若带宽饱和 → 压缩/减少数据移动；若 branch-misses 高 → 分支重排/分支消除；每项优化后用"优化前 vs 后"的同一基准对比确认收益（防负优化）。

本题考察常数优化的层次体系与数据驱动：三类优化的作用域与 profiling 的归因方法。回答时逐层讲机制与适用，最后给"指标 → 措施"的定位流程。

• COW：修改时才复制，未修改部分共享（写多读少时收益）
• Path Copying：沿路径复制 + 子树共享（持久化结构的标准）
• CRDT 合并开销：操作日志修剪、版本合并的复杂度控制

写时复制（COW）与路径复制（Path Copying）的本质相同：不可变（或逻辑不可变）结构通过"共享未变部分 + 只复制修改路径"减少复制。COW 是惰性版本：修改前先复制共享对象（如进程 fork、容器镜像分层），未修改的页面/层完全共享，只有写时才复制——收益在"读多写少、共享多"时最大（复制代价摊到实际修改量）；Path Copying 是持久化数据结构的主动版本：每次修改沿根到目标节点复制路径（O(log n) 新节点），未涉及子树保持引用共享——收益：多版本共享同一主体，更新代价 O(log n) 而非 O(n)，且旧版本可持久化访问、天然线程安全。两者共同点："共享不可变结构"消除了深拷贝：修改只产生"增量"，复制量正比于改动规模而非数据总量。CRDT 的合并开销控制：CRDT（如协同编辑的文档结构）在合并副本状态/操作日志时，若直接合并全部历史，开销随版本数线性增长；控制手段：1) 操作日志修剪（GC）——把已合并到快照的操作删除，只保留"未传播"部分；2) 状态合并的增量计算——只合并双方差异（版本向量定位差异区间）；3) 墓碑/孤儿清理——删除操作留下的墓碑（tombstone）定期压缩；4) 分层合并——按分片/块粒度合并（只合并变化的块），避免整文档合并；5) 快照 + 增量同步——定期快照替换长日志。目标是把合并成本从 O(历史总量) 降到 O(差异量)。

本题考察两类"共享减少复制"机制的收益模型与 CRDT 的合并成本工程。回答时先讲 COW 与 Path Copying 的共享-复制机制与收益条件，再讲 CRDT 合并开销的来源与五类控制手段。

• Fork-Join：分治递归 + 任务窃取，限制于分治串行部分与任务粒度
• MapReduce：数据并行 + shuffle，限制于 shuffle 通信与数据倾斜
• CUDA：线程并行 + 同步，限制于访存/同步/占用率

三种并行化模式：1) Fork-Join（分治并行，如 Java ForkJoinPool、OpenMP 任务）——递归拆分子问题、并行执行、合并结果；加速比限制：分治的串行部分（合并阶段、基线条件）受 Amdahl 约束、任务粒度（拆太细则调度/创建开销超过收益，需要"阈值后串行"）、任务窃取的负载均衡（尾部任务不均）；2) MapReduce（数据并行）——数据划分后独立 map、shuffle 归并、reduce；加速比限制：shuffle 的通信量（网络是主要开销）、数据倾斜（热点 key 使单个 reduce 成为瓶颈）、reduce 的串行合并部分、任务的启动/调度开销（小文件/小任务时开销主导）；3) CUDA（线程并行）——成千上万线程分层执行；加速比限制：访存带宽（memory-bound 时计算核闲置）、同步开销（块间同步只能靠 kernel 边界）、占用率（occupancy：寄存器/共享内存限制活跃线程数，低占用率无法掩盖延迟）、分支发散（warp 内分支串行化）、Amdahl 的串行部分（host 端、kernel 间依赖）。共同限制：Amdahl 定律（任何模式都受串行部分占比约束）与"并行开销"（通信、同步、调度、负载不均）随规模增长；提升加速比的三板斧：增大并行度（划分更细）、减少串行部分（合并/同步外置）、减少并行开销（局部性、批量通信、负载均衡）。分析框架：加速比 = 1/(s + (1-s)/p + 开销系数)，用 profiling 定位是"串行占比"还是"并行开销"主导。

本题考察并行模式的统一分析：不同模式有各自的并行开销来源，但都受 Amdahl 与开销约束。回答时逐模式讲机制与限制因素，最后给共同框架与提升手段。

• 资源约束：KB-MB 内存、mW 功耗、有限算力
• 流式/在线：单遍处理 + O(1) 内存（Sketch、采样、滑动窗口）
• 近似与离线预处理：精度换资源、查表/压缩模型

嵌入式/移动端（MCU、传感器节点、手机端侧）的资源受限设计把"内存、功耗、算力"作为第一约束，算法选择原则是"单遍、O(1) 内存、低计算量"：1) 流式算法——数据持续到达且不能全存，用单遍 + 常数内存结构：滑动窗口统计（环形缓冲）、蓄水池抽样（均匀样本，无需预知 n）、Count-Min/HLL 等 Sketch（频次/基数近似）、Misra-Gries（频繁项）——这些结构内存 O(1/k)（k 为参数）且每元素 O(1) 时间，适合传感器数据流、日志流；2) 在线算法——无需预知未来，边到边决策：LRU/自适应缓存（存储有限）、指数移动平均（EMA）平滑、阈值触发（超阈值才处理/上报），配合竞争比思想（如 ski rental 的"何时持久化/何时上报"）；3) 近似与降精度——定点数代替浮点（MCU 无 FPU 时提速数十倍）、INT8 量化模型（端侧推理）、截断迭代（早期停止）、查表（三角函数/对数预计算）、多项式近似（泰勒/极小极大），误差可控且资源降数量级；4) 离线预处理——把重计算离线完成：模型压缩/蒸馏（端侧部署）、数据模板/字典预置（减少运行时计算）、周期批处理（低峰期聚合，在线只做查表）；5) 系统层面——低功耗调度（占空比：周期醒来处理再休眠）、DMA 批量处理、掉电保存关键状态（闪存/备份寄存器）。设计流程：先定预算（内存上限、功耗预算、精度要求），再按"数据规模 vs 内存"选流式/采样，用误差上界证明可用性，最后实测功耗与精度验证。

本题考察受限环境的设计思维：把资源当输入、算法当输出。回答时按流式/在线/近似/离线预处理四类手段讲机制与适用，最后给"预算驱动 + 实测验证"的设计流程。

• 贪婪：子模/覆盖类问题，集合覆盖 ln n 近似
• LP 舍入：整数规划的松弛与舍入，顶点覆盖 2 近似
• 局部搜索：邻域迭代，k-median 常数近似（LP/局部搜索 3-5）

近似算法按"问题结构"选型：1) 贪婪（greedy）——适用于"覆盖/子模"类问题（集合覆盖、最大覆盖、子模最大化）：每次选择"边际收益最大"的元素；集合覆盖的最优贪婪近似比为 ln n（每步至少覆盖剩余未覆盖的 1/opt 部分，总覆盖率指数逼近），且该界是紧的（除非 P=NP）；最大覆盖/子模最大化（无预算约束）的贪婪近似比 1-1/e；实现简单、快，适合大规模实例。2) LP 舍入（LP rounding）——适用于"可写成整数规划的约束优化"：先解 LP 松弛（多项式时间），再把分数解舍入为整数解；顶点覆盖的经典做法：把"每条边至少一端被选"写成 LP，取"分数 ≥ 1/2 的顶点"得 2 近似（每条边至少一端分数 ≥ 1/2，故选集是可行覆盖且 ≤ 2×LP 最优 ≤ 2×OPT）；其他例子：集合覆盖的 LP 舍入 ln n 近似、带度约束的树。3) 局部搜索（local search）——适用于"组合优化 + 邻域结构明确"：从初始解迭代改进（交换/替换邻域直到局部最优）；k-median（选 k 个中心最小化距离和）的局部搜索（交换一个中心）达到常数近似（3 + ε 或 5），LP 舍入也能到 5-6 近似；其他：最大割的局部搜索 1/2、旅行商的 2-近似（MST 加倍）。选型准则：覆盖/子模 → 贪婪（1-1/e 或 ln n）；约束可 LP 化且结构规整 → LP 舍入（常数近似 + 可证明）；邻域直观、实例大 → 局部搜索（工程快 + 常数近似）；最后用"近似比 × 实现复杂度 × 实例规模"综合决策，必要时用元启发式（模拟退火）做工程兜底。

本题考察近似算法的"问题-算法"映射：三个算法族分别对应覆盖/子模、约束优化、邻域优化。回答时逐一讲机制、近似比与适用问题，最后给选型准则与工程考量。

• 蓄水池抽样：未知长度流上的等概率采样（k 个样本，O(1) 内存）
• 加权采样：按权重概率选择（A-Res/指数跳跃法）
• 误差：标准误 ∝ 1/√n，置信区间随样本量收敛

蓄水池抽样（Reservoir Sampling）解决"未知长度的流中均匀抽取 k 个样本"：维护大小为 k 的水池，第 i 个元素以 k/i 概率替换池中随机一个元素——正确性：每个元素最终留在池中的概率均为 k/n（可归纳证明），内存 O(k)、单遍、无需预知 n；实现要点：随机数生成器的质量（伪随机退化会破坏均匀性）、替换时均匀选取下标。加权采样：每个元素按权重 w_i 被选中的概率 ∝ w_i：A-Res（Algorithm A-Res）维护带"key = u^(1/w)"的堆（key 最大的 k 个被选，u 为 (0,1) 均匀随机数）；指数跳跃法（Efraimidis-Spirakis 的 A-ExpJ）按几何分布跳过非选中元素，均摊 O(1) 每元素；权重归一化与浮点精度（u=0 时 key 退化）是常见坑。流式采样变体：滑动窗口采样（只从最近 W 个中采，用指数直方图/链式删除）、分层采样（按类别配额）、放回 vs 不放回。采样误差：简单随机样本的估计误差随样本量 n 以 1/√n 收敛——标准误 SE = σ/√n（σ 为总体标准差），n 从 100 到 10000（100 倍）误差缩小 10 倍；误差界用中心极限定理给置信区间（95% 区间 ≈ 估计值 ± 1.96·SE），对比例估计用 p(1-p)/n 计算 SE；误差与总体规模 N 几乎无关（抽样比 n/N 只在 n 接近 N 时经有限总体校正影响），因此"10 万人的民意调查抽 1000 人就够"是统计直觉。工程注意：样本独立同分布（无偏）、随机数种子可复现、按层加权时用加权标准误。

本题考察采样算法的实现与统计基础：蓄水池的替换证明、加权的 key 堆、误差的 √n 收敛。回答时先讲两种采样实现与正确性，再讲滑动/分层变体，最后给误差公式与工程注意。