第九章 海量数据处理场景（第201-208题）
本章说明：海量数据在有限内存下的去重、排序、统计、求交、TopK，核心是“分治 + 哈希 + 位图/布隆 + 外部排序 + 堆”的组合套路。
201. 风控要判断 14 亿存量 QQ 号是否在黑名单，内存只有 1G（布隆过滤器）
【考察内容】海量成员判断与概率数据结构
【题目】风控系统维护着一个 14 亿存量 QQ 号的“黑名单/已注册”集合（约 1 亿条在黑名单），要求每次登录毫秒级判断“这个 QQ 号在不在集合里”。内存预算只有 1G，不能上大缓存。请问用位图（Bitmap）和布隆过滤器（Bloom Filter）分别怎么做？各自代价是什么？
【参考答案】
位图（Bitmap）：要区分两种用法——①以 ID 直接做位下标（bit[QQ 号]=1）：14 亿个 bit ≈ 14 亿/8 ≈ 175MB，完全放得下 1G 内存，判断 O(1) 且无误差，但空间随 ID 上限线性增长，只适合 ID 连续/上限可控的场景；②哈希映射到固定位图（bit[hash（QQ 号）%m]=1）：空间可控，但不同 QQ 号映射到同一 bit 会碰撞、误判为存在，且只能回答“存在/不存在”、不能删除——所以哈希位图一般配“哈希分桶”或用于纯 ID 连续的场景；
布隆过滤器：用 k 个哈希函数映射到 m 位的位数组。判断“不在”是 100% 准确；判断“在”有误判率 p（可公式化：m = -n·ln(p)/(ln2)²，最优哈希函数个数 k = (m/n)·ln2）。误判率 1% 时，1 亿条黑名单约需 9.6 亿 bit（约 120MB，平均每元素约 9.6 bit）；误判率 5% 时约 6.2 亿 bit（约 78MB）；
工程组合：黑名单用布隆（误判“在黑名单”顶多多拦一次，成本低）；已注册判断用位图或布隆+DB 二次确认（布隆说“在”再去 DB 精确查）；
不能直接加载全量到内存时：哈希分桶到多台机器，每台只存一部分（分治）。
容量估算（再核对）： 1G 内存可选方案：① QQ 号直接位图：14e8 bit ≈ 175MB（只在「ID 恰好连续占满 1..14 亿」时成立：若按 10 位号段算，上限是 1e10，直接位图就是 1e10÷8 ≈ 1.25GB，已超 1G 预算——此时只能改哈希位图/布隆，或按号段分片只装热号段。答题要把 ID 域这个前提说死，175MB 和 1.25GB 是同一句「用位图」的两种结果）；② 布隆：p=1% 时 n=1e8 约 120MB（公式 m=-n ln p/(ln2)^2）；n=1.4e9 时 p=1% 约 1.7GB 超预算，需提高误判率或分桶到多机。误判只应导致“误拦”而非“误放”才适合黑名单。
失败与降级： 布隆误判上线后要用 DB 二次确认路径（说“在”再查库）；内存不足时哈希分桶，单桶机器故障则该桶降级查 DB（慢但正确）。批量构建失败可断点续跑；在线过滤服务要做多副本，防止单点导致风控全挂（可降级为“全部走 DB 限流查”）。
【原理溯源】
- 为什么布隆“说不在一定准，说在可能误判”？ 插入时 k 个哈希对应的位置全置 1。查询时若任一位为 0，则元素一定没插入过（假阴性不存在）。若 k 位全为 1，可能是本元素插入过，也可能是其他元素碰撞置的 1——所以“在”可能是假阳性。这个不对称性决定了它适合“过滤明显不存在”的场景。
- 空间公式从哪来？ 目标是在 n 个元素、m 位、k 个哈希下最小化误判率。最优 k=(m/n)ln2 时，p≈(0.6185)^(m/n)。工程上常用近似：每元素 10 bit 约 1% 误判，约 9 bit 约 1%（120MB/1亿）。误判率每降一个数量级，空间约增加 5 bit/元素——不是线性关系。
- 为什么标准布隆不能删除？ 删除时不能简单把对应位清 0——该位可能被其他元素共享，清 0 会造成假阴性（其他元素被误判为不存在）。计数布隆（CBF）用计数器代替 bit 可删，但空间放大数倍。多数场景用“定期重建”替代删除。
- 位图与布隆的本质区别是什么？ ID 直接位图：下标=ID，精确、空间随 ID 域线性，适合连续整数 ID。布隆：多哈希+概率，空间与元素数成正比（与 ID 域无关），有假阳性。选型看：ID 是否连续可控？能否接受误判？
- 为什么误判要配 DB 二次确认？ 布隆误判“在”只多一次 DB 查询（成本低）；若误判“不在”则漏放黑名单用户（成本高）。所以布隆说“不在”可直接放行，说“在”必须精确查证。这是概率结构+精确存储的经典分层。
【选型判断树】
海量成员存在性判断：
1. ID 是否连续整数且上限可控？
├─ 是 → 直接位图（14亿 bit≈175MB，精确）
└─ 否 → 继续
2. 能否接受假阳性？
├─ 能（黑名单多拦一次）→ 布隆
└─ 不能 → 布隆+DB/精确缓存二次确认，或精确分片 Set
3. 需要删除吗？
├─ 需要 → 计数布隆 / 定期重建 / 精确结构
└─ 不需要 → 标准布隆
4. 规模超单机内存？
└─ 哈希分片到多机，或分布式布隆（RedisBloom）判断口诀： 连续 ID 用位图；不确定就布隆；判“在”要复查；要删除就重建。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “海量存在性判断：精确位图 vs 概率布隆” |
| 0:30–1:30 | 位图 | ID 直接下标：14 亿连续→175MB；若是 10 位号段（上限 1e10）→1.25GB 超 1G 预算；精确；线性空间 |
| 1:30–2:30 | 布隆 | k 哈希置位；不对称误差；1%≈9.6bit/元素 |
| 2:30–3:30 | 工程组合 | 布隆粗筛 + DB 精确兜底 |
| 3:30–4:30 | 删除与扩展 | 标准布隆不可删；分片 |
| 4:30–5:00 | 收尾 | “用不对称误差换空间，用二次确认换正确性” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 14 亿 ID 直接位图 | ≈175MB | /8，精确；前提＝ID 连续占满 1..14 亿；按 10 位号段算是 1e10/8≈1.25GB，已超 1G 预算 |
| 布隆 1% 误判 | ≈9.6 bit/元素 | 1 亿条≈120MB |
| 布隆 0.1% 误判 | ≈14.4 bit/元素 | 误判率对数敏感 |
| 最优哈希个数 | k=(m/n)ln2 | 通常 5–10 |
| 二次确认 | 布隆说“在”才查 DB | 假阳性成本低 |
【追问链】（三层）
L1｜“布隆过滤器能删除吗？” → 标准布隆不能安全删除（清位会影响其他元素）。计数布隆可删但空间大；或定期用全量数据重建；或改用 Cuckoo Filter 等支持删除的概率结构。
L2｜“误判率设成 0 可以吗？” → 数学上布隆误判率随 m 增大趋近 0 但达不到 0。要“零误判”只能用精确结构（位图/Redis Set/DB）。工程上按业务容忍度选 1%–5%，再配二次确认。
L3｜“14 亿全量都要进布隆吗？黑名单只有 1 亿。” → 布隆容量按“要插入的元素数”算，即 1 亿黑名单，不是 14 亿全集。若要判断“是否已注册”且已注册也是 1 亿，则按 1 亿配。全集大小只影响“查询样本空间”，不影响布隆 m。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“用布隆过滤器省内存” |
| 80 分 | 讲清不对称误差、空间量级、与位图区别、DB 二次确认 |
| 95 分 | 能算 bit/元素；删除问题；分片扩展；按业务选精确 vs 概率 |
【关联题】
- 在线布隆： 第 207 题（同结构不同场景）
- 生产使用： 第 44 题（布隆误判与删除）
- 缓存穿透： 第 24 题（布隆防穿透）
- 时间窗口： 第 208 题
【自测】
- 布隆过滤器判断“不存在”和“存在”哪个可信？ 参考答案：“不存在”100% 可信（无假阴性）；“存在”可能误判（假阳性）。
- 1 亿个元素、期望 1% 误判率，大约需要多少内存？ 参考答案：约 9.6 bit/元素 × 1 亿 ≈ 9.6 亿 bit ≈ 120MB。
- 为什么标准布隆不支持删除？ 参考答案：bit 可能被多个元素共享，清 0 会造成其他元素假阴性。
202. 两个 500G 文件各存了海量 IP，内存只有 30G，求两个文件的交集（哈希分治）
【考察内容】海量数据分治求交
【题目】两个 500G 的文件里各存了一批 IP 地址（可能有重复），机器内存只有 30G，读不进内存。要求找出两个文件中都出现的 IP（去重后的交集）。请给出完整方案，说明为什么“直接 HashMap 全量加载”不可行。
【参考答案】
核心思想：哈希分治（分而治之）——同一个哈希函数 h，把文件 A 按 h(ip)%N 分到 N 个小文件 A0..A(N-1)，文件 B 同样分到 B0..B(N-1)。相同 IP 的哈希值相同，必然落到同编号的小文件对（Ai, Bi）里；
对每对小文件（Ai, Bi）：各自都能读进 30G 内存，用 Set/HashMap 统计 Ai 的 IP 集合，遍历 Bi 判断是否在 Ai 中，得到交集；
合并所有小文件对的交集即最终结果；N 的选择：保证单个小文件 < 内存可用量（如 500G/N < 5G，取 N=128/256 都行）；
若 IP 是 IPv4（32 位）：可进一步用位图——全部 2^32 个 bit = 512MiB（≈537MB 十进制），两次遍历直接按位求与，内存更省（可作加分项）；
扩展：去重后求交只需 Set；若还要计数交集元素的次数，则用 Map 计数。
容量估算： 500G 文件、内存 30G：17 桶（500/30）只是“单桶字节数 ≤ 物理内存”的下限，既没扣本题自己定的 1/3 安全水位（30G×1/3=10G → N ≥ 50），也没算 HashSet 装箱膨胀（下一条明说膨胀数倍至数十倍）；工程上取 128–256 桶（500/128≈4G/桶）才与【关键数字】一致。每桶再哈希读入 HashSet 求交。I/O：两文件各读一遍写桶+各桶再读，总读放大≈2–4 次×500G；SSD 上吞吐按 500MB/s 估，纯 I/O 小时级。IP 可用 uint32 紧凑存储省空间。
失败与降级： 单桶 OOM：加大桶数或对单桶二次哈希再分。磁盘临时空间要预留 ≥ 数据体积。作业失败按桶粒度重跑，不要整任务重来。结果可先写外部存储再校验数量级。
【原理溯源】
- 为什么“同哈希函数分桶”能保证不漏？ 相等元素哈希值相同，
h(x)%N必然相同，所以相同的 IP 一定进入同编号桶。交集只需在桶内求——全局交集=各桶交集的并。若两个文件用不同哈希，相同 IP 会落到不同桶，交集会被漏掉。 - 为什么 HashMap 全量加载不可行？ 500G 数据即使每 IP 只存 4 字节键，HashSet/HashMap 的对象头、指针、装箱开销会让内存膨胀数倍至数十倍。30G 内存放不下 500G 的键集合。分治把问题规模降到“单桶可入内存”。
- 桶数 N 怎么选？ 目标：单桶平均大小 < 可用内存的安全水位（如 30G 的 1/3=10G）。500G/128≈4G/桶，安全。还要考虑小文件数量带来的 IO 打开次数——N 过大（如 10 万）会有文件句柄与小文件惩罚。通常 128–1024。
- IPv4 位图为什么更优？ IPv4 只有 2^32 个可能值，一个 512MiB（≈537MB）位图即可表示全集。A 文件置位，B 文件查询/或第二次置位后按位 AND。精确、无哈希冲突、内存固定。IPv6（128 位）则不能直接全位图，仍需哈希分治。
- 数据倾斜怎么办？ 若哈希分布不均，某桶远大于其他桶，会内存爆。对策：更强的哈希（MurmurHash）、二次分桶、或按 IP 前缀预分（但前缀可能倾斜）。监控桶大小分布是工程必备。
【选型判断树】
海量求交：
1. 数据域大小？
├─ IPv4 全域 2^32 → 512MiB 位图，最简单
└─ 任意字符串/IP 对/大域 → 哈希分治
2. 分治参数
└─ N 使单桶 < 内存 1/3；同哈希函数
3. 桶内
├─ 只求交集 → Set
└─ 要计数 → Map
4. 规模悬殊
└─ 小文件建索引，大文件流式比对
5. 倾斜
└─ 二次分桶 / 换哈希判断口诀： 同哈希才能同桶；单桶必须进内存；IPv4 先想位图。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “内存不够就哈希分治，把问题切到可入内存的子问题” |
| 0:30–1:30 | 分治流程 | 同哈希分 N 桶；桶对求交；合并 |
| 1:30–2:30 | 正确性 | 相等元素必同桶；N 的选择依据 |
| 2:30–3:30 | IPv4 优化 | 512MiB 位图精确求交 |
| 3:30–4:30 | 工程细节 | 倾斜、大小悬殊、IO 遍数 |
| 4:30–5:00 | 收尾 | “分治是海量题的母题，哈希保证不漏” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 桶数 N | 128–1024 | 使单桶 < 内存 1/3 |
| IPv4 位图 | 512MiB（≈537MB） | 2^32 bit ÷ 8 |
| IO 遍数 | 约 2 遍（分写+桶内读） | 可接受 |
| 哈希函数 | MurmurHash/xxHash | 分布均匀、快 |
| 桶大小监控 | 最大桶 << 内存 | 防倾斜 |
【追问链】（三层）
L1｜“两个文件用不同的哈希函数会怎样？” → 相同 IP 落到不同桶编号，桶对求交会漏掉真实交集。必须用同一个哈希函数与同一个模数 N。
L2｜“一个文件 500G 一个文件 1G，还用对称分治吗？” → 可优化：只把小文件全量读入建 HashSet，大文件流式逐条查询。省一半 IO。若小文件也大，再对称分治。
L3｜“求交还要保留重复次数怎么办？” → 桶内用 Map<IP,count> 分别统计 A、B 的次数，交集元素取 min(countA,countB) 或按业务规则。内存仍是分治保证。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“分小文件处理” |
| 80 分 | 讲清同哈希分桶、桶对求交、N 的选择 |
| 95 分 | IPv4 位图优化；倾斜与大小悬殊；IO 分析 |
【关联题】
- TopK： 第 204 题（同样分治）
- 外部排序： 第 203 题
- 中位数： 第 205 题
- MapReduce： 第 206 题
【自测】
- 哈希分治为什么必须用同一个哈希函数？ 参考答案：保证相同元素落入同编号小文件，否则桶内求交会漏交。
- IPv4 求交有没有比哈希分治更省的方案？ 参考答案：有。IPv4 地址空间 2^32 个，一位一地址 → 2^32 bit = 512 MiB（= 536870912 B ≈ 537MB 十进制）位图即可，精确且内存固定。注意 512 是「MiB」口径，除以 1000 得约 537MB；别写成 512MB 再和同章按 1000 折算的数字混用。
- 桶数 N 选太小或太大各有什么问题？ 参考答案：太小则单桶仍超内存；太大则小文件过多，IO 与句柄开销大。
203. 1000 万条 URL 要全局去重并排序，内存只有 10M（外部排序/分治）
【考察内容】外部排序与多路归并
【题目】一批 1000 万条 URL（平均每条几十字节，总约几百 MB），需要“去重 + 按字典序排序”后输出。机器内存只有 10M。请设计完整方案，并说明内存充足（如 2G）时又该怎么做。
【参考答案】
内存不足（10M）场景——外部排序 + 去重：
- 第一步分治：把大文件按哈希（或读入顺序）切分成能装入内存的小块（每块 < 10M，如 5M），对每块在内存里排序并去重，写成有序小文件；
- 第二步多路归并：用 K 路归并（败者树/优先队列）把所有有序小文件合并成整体有序，合并时相同的 URL 只输出一次（去重）；
- 复杂度：IO 为主，一次排序写回 + 一次归并读回，约 2~3 遍 IO；
内存“看似充足”（2G）场景：先估再选——原始约 500MB，但 HashSet 装箱后常 2–3GB，2G 属临界；确认装箱后仍有余量才可以一次读入用 HashSet 去重 + 排序，否则仍走外排（见【原理溯源】与自测 3）；
变体优化：若允许一定误判，去重可用布隆先过滤明显重复（节省写盘），但精确去重最终仍要排序合并；
若 URL 有固定前缀结构，可用 Trie（前缀树）内存压缩存储，但 URL 长度不可控时收益有限。
容量估算（与题干「平均几十字节、总约几百 MB」同口径，按平均 50B 估）： 1000 万 × 50B ≈ 500MB 原始，内存 10M 必须外排/分治；若按平均 100B 上限估则约 1GB，结论不变。分桶：按哈希前缀分 256 桶，每桶 10^7/256 ≈ 3.9 万条，按 50B 约 2MB、按 100B 上限约 4MB，都可进 10M 内存去重排序，再多路归并。磁盘：至少 2×原始空间（输入+输出），即约 1GB 起。去重率未知时按最坏全唯一估。
失败与降级： 某桶过大（倾斜）：对该桶再二级哈希。外排中断：记录已完成桶号断点续跑。最终校验：抽样 + 总条数与桶内和一致。
【原理溯源】
- 为什么“分块排序+归并”能完成全局有序？ 排序的外排经典算法：内存放不下时，每次排好一块写盘，最后多路归并。因为每块内有序，归并时只需比较各块当前最小元素。局部有序+归并=全局有序，这是外部排序的基石。
- 去重为什么能在归并时顺带完成？ 归并指针移动时，若多个块的当前元素相同，只输出一个并跳过其余。因为各块已排序，相同元素必然相邻出现——无需额外去重结构。
- K 路归并为什么用败者树/堆？ 每次从 K 个块中取最小，朴素做法比较 K-1 次；堆是 O(logK)。败者树进一步优化常数。内存里只需放 K 个“当前元素”（每个块的头），所以 10M 内存可以开成百上千路。
- IO 遍数怎么算？ 读入分块（1 遍读）+ 写有序小文件（1 遍写）+ 归并读回（1 遍读）+ 最终写出（1 遍写）。约 2 读 2 写。可通过增大块、减少归并趟数优化。
- 为什么内存够时直接 HashSet+排序？ 1000 万 URL 若平均 50B，原始 500MB；HashSet 装箱后可能 2–3GB。2G 内存勉强或不够，要看实现。这就是为什么题目强调“内存只有 10M”——逼你用外排。面试要先估内存再选型。
【选型判断树】
去重+排序的内存决策：
1. 估算：n × 平均长度 × 装箱系数 vs 可用内存
├─ 放得下 → HashSet 去重 + 排序输出
└─ 放不下 → 外部排序
2. 外部排序
├─ 分块：每块 < 内存 1/2
├─ 块内：排序+去重，写有序小文件
└─ 归并：堆/败者树 K 路，归并时去重
3. 优化
├─ 布隆预过滤重复（可选）
└─ 前缀 Trie（结构稳定时）判断口诀： 先估内存；不够就分块内排；归并时去重；堆选最小。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “内存不够的去重排序 = 外部排序” |
| 0:30–1:30 | 两步法 | 分块排序写盘 → 多路归并 |
| 1:30–2:30 | 去重 | 归并时相同只输出一次 |
| 2:30–3:30 | 数据结构 | 堆/败者树 O(logK)；IO 遍数 |
| 3:30–4:30 | 对比内存够 | HashSet+排序；先估大小 |
| 4:30–5:00 | 收尾 | “局部有序+归并=全局有序” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 块大小 | 内存的 1/2~2/3 | 留排序临时空间 |
| 归并路数 K | 由内存/单元素大小定 | 堆顶数组 |
| IO 遍数 | 约 2 读 2 写 | 可多趟归并优化 |
| 1000 万×50B | ≈500MB 原始 | HashSet 可能 2GB+ |
| 败者树 | O(logK) 取最小 | 优于朴素比较 |
【追问链】（三层）
L1｜“归并的 IO 次数是多少？” → 典型：排序一遍读+写，归并一遍读+写，约 2 读 2 写。若小文件太多需多趟归并，IO 线性增加。增大块减少块数可减少趟数。
L2｜“1000 万条 URL 真的放不下 10M 吗？” → 平均 50 字节 × 1000 万 ≈ 500MB，远超 10M。即使只存哈希（8B）也要 80MB。所以必须外排。
L3｜“能不能用数据库排序去重？” → 生产可以（SELECT DISTINCT url ORDER BY url），但面试/笔试考察的是算法设计。工程上也要考虑数据库能否吃下 500MB 临时排序与索引。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“分小文件排序再合并” |
| 80 分 | 讲清两步外排、归并去重、堆结构、IO 遍数 |
| 95 分 | 先估内存；败者树；布隆/Trie 优化；与数据库方案对比 |
【关联题】
- 哈希分治： 第 202 题
- TopK： 第 204 题
- MapReduce： 第 206 题
- 爬虫 URL 去重： 第 137 题
【自测】
- 外部排序的两个主要阶段是什么？ 参考答案：① 分块读入内存排序后写成有序小文件；② 多路归并成全局有序，归并时去重。
- 为什么归并阶段用堆而不是每次比较 K 个数？ 参考答案：堆取最小为 O(logK)，优于 O(K)；内存只存 K 个当前元素。
- 内存 2G 时 1000 万 URL 能否全量加载？ 参考答案：原始约 500MB，但 HashSet 装箱可能膨胀到 2GB+，临界。需估算或仍外排。
204. 10TB 访问日志里统计访问次数最多的 100 个 IP（哈希分治 + TopK 堆）
【考察内容】分治 + HashMap 统计 + 堆 TopK
【题目】一台 Nginx 积累了 10TB 的访问日志，每行是一个请求的 IP。要求统计访问次数最多的 100 个 IP。单机内存有限（如 8G）。请设计完整方案，并说明如果 IP 统计完还要输出每个 IP 的次数该怎么处理。
【参考答案】
整体思路：哈希分治降规模 → 桶内统计 → 堆取 TopK → 归并；
第一步：扫描日志，按 h(ip)%N（如 N=1000，10TB/1000 ≈ 10GB 原文/桶）把每条记录写入对应小文件。相同 IP 一定落在同一个小文件；
第二步：对每个小文件，读入内存用 HashMap<IP, count> 统计次数——进内存的是桶内 distinct IP×(IP+count)，不是 10GB 原文：10GB 文本约 5e8 行，distinct 通常远小于行数，按 16B/条估到 GB 级；若该桶 distinct 仍撑不下 8G 就加大 N 或二次分桶；
第三步：对每个小文件统计结果，用大小为 100 的小顶堆（最小堆）维护当前 Top100（比堆顶大就替换）；遍历所有小文件的统计结果，最终堆里就是全局 Top100 IP 及次数；
复杂度：一趟哈希分写 + 一趟统计读 = 2 遍 IO；内存只放 HashMap 和堆；
变体：若小文件仍太大，可递归分桶；若 IP 是 IPv4，可先按 IP 前 16 位分 65536 个固定桶，每桶再统计（桶分布天然均匀，避免哈希分桶不均），或在大内存机器上用 2^32 计数数组（按计数宽度选 byte/short/int，空间 4GB 起）。
容量估算： 10TB 日志、Top100 IP：经典 MapReduce/哈希分治。每台内存装不下全量 IP 计数，按 IP 哈希分桶到 N 个 reducer，单机内存只要能装“单桶 distinct IP×计数结构”。若 distinct IP 千万级，单桶仍可能大，提高桶数。堆内存：Top100 用最小堆 100 个元素 O(K) 内存。I/O 带宽决定时长：10TB/（集群聚合 2GB/s）≈1.4 小时读一遍。
失败与降级： 数据倾斜热点 IP 导致单 reducer 慢：二次散列或对热点 IP 单独处理。作业失败从 checkpoint 桶继续。结果与离线数仓当日汇总交叉验证数量级。
【原理溯源】
- 为什么取 TopK 用小顶堆而不是大顶堆？ 维护“最大的 K 个”时，用大小为 K 的小顶堆：堆顶是当前第 K 大（最小的那个）。新元素比堆顶大，说明它能进 TopK，弹出堆顶、插入新值；比堆顶小则忽略。若用大顶堆，堆顶是最大值，无法高效知道“第 K 大”的门槛。
- 为什么不能先全局计数再取 Top100？ 全局计数需要一个装下所有不同 IP 的 Map。若不同 IP 达数十亿，8G 内存放不下。分治保证每个桶内 distinct IP 数可控。
- TopK 堆为什么是流式友好的？ 堆只需 O(K) 内存，可边扫描边维护，无需保存全量计数。这也是“精确计数分治 + 流式 TopK”组合的由来——计数分治处理规模，堆处理排序选择。
- 为什么按前 16 位分桶可能更好？ IPv4 前 16 位有 65536 种，直接分 65536 个文件，无需计算哈希，分布由地址分配决定（通常较均匀）。若日志源单一机房，前缀可能集中，需监控倾斜。哈希分桶更通用。
- 输出次数怎么处理？ 堆中元素本身带 count，Top100 可直接输出 IP+次数。若还要全量 IP 计数，则第二阶段的 HashMap 结果需落盘成 (IP,count) 文件，可再做外排（见 203 题）。
【选型判断树】
海量 TopK：
1. 先能不能全量计数？
├─ distinct 少、内存够 → Map 计数 + 排序/堆
└─ 放不下 → 哈希分治计数
2. 分治后
├─ 桶内 Map 计数
└─ 流式喂给大小为 K 的小顶堆
3. K 很大或要全量次数
└─ 桶结果落盘，再外排/归并
4. IPv4 特化
└─ 前 16 位分 65536 桶，或大内存计数数组判断口诀： 计数用分治，选择用小顶堆；堆顶是门槛，小了就丢。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “海量 TopK = 分治计数 + 堆选择” |
| 0:30–1:30 | 分治计数 | 同哈希分桶；桶内 HashMap |
| 1:30–2:30 | 小顶堆 | 为何是小顶堆；替换逻辑 |
| 2:30–3:30 | IO 与内存 | 2 遍 IO；O(K) 堆内存 |
| 3:30–4:30 | 变体 | IPv4 前缀分桶；全量次数输出 |
| 4:30–5:00 | 收尾 | “规模靠分治，排序靠堆” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 分桶数 N | 1000–10000 | 使桶内 distinct 可入内存 |
| TopK 堆 | 大小=K，小顶堆 | O(K) 内存 |
| 堆操作 | O(logK)/元素 | 流式友好 |
| IPv4 前缀桶 | 65536 | 前 16 位 |
| IO | 约 2 遍 | 分写+统计读 |
【追问链】（三层）
L1｜“Top100 用大顶堆还是小顶堆？” → 小顶堆。堆顶是当前 Top100 中最小的门槛值；新值比它大才替换。大顶堆堆顶是最大值，无法维护“第 100 大”。
L2｜“分桶后某桶还是超大怎么办？” → 说明分布倾斜或 N 太小。对策：二次分桶（递归哈希）、换更强哈希、或按数据特征换分桶键（前缀）。必须监控桶大小。
L3｜“有更优的 TopK 算法吗？” → 全量在内存时可用快速选择（partition）平均 O(n)。海量流式场景堆更合适（O(n logK)，但不需要随机访问与全量内存）。工程上还可用 Count-Min Sketch 等近似算法进一步降内存，接受近似误差。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“用 HashMap 统计再排序取前 100” |
| 80 分 | 讲清哈希分治、小顶堆替换、IO 遍数 |
| 95 分 | 为何小顶堆；倾斜处理；IPv4 特化；近似算法扩展 |
【关联题】
- 哈希分治： 第 202 题
- 外排： 第 203 题
- MapReduce： 第 206 题
- 热榜系统： 第 127 题
【自测】
- 取最大的 K 个数为什么用小顶堆？ 参考答案：堆顶是当前第 K 大（门槛），新值比堆顶大才替换，保证堆内始终是已见元素中最大的 K 个。
- 为什么不直接全局 HashMap 计数？ 参考答案：distinct IP 可能远超内存。哈希分治把计数规模降到单桶可入内存。
- TopK 堆的空间复杂度？ 参考答案：O(K)，与数据总量无关，流式友好。
205. 100 亿个整数（含重复）找中位数，内存只有 2G（分桶计数）
【考察内容】海量数据中位数/分位数的桶计数法
【题目】一个文件里有 100 亿个 int 整数（可能有重复），要求找出中位数（第 50 亿个小的数）。内存只有 2G，不能排序也不能全量加载。请设计方案。
【参考答案】
思路一：分桶统计（区间计数）——把整数范围按值域分桶（如按每 1000 万一个桶，int 全范围约 42 亿，每 1000 万一桶 ⇒ 约 420 个桶（想用 2 的幂就取 512 桶、每桶约 840 万，两者别混写））。第一遍扫描：统计每个桶内的元素个数（只需计数器数组，几十 KB）；累加桶计数找到中位数落在哪个桶，并得到中位数在该桶内的第几个位置 k；
第二遍扫描：只把目标桶范围内的数读入内存（该桶内元素数应远小于 2G），排序或再用“值域内二分”找到第 k 个数，即中位数；
思路二：值域二分（二分答案）——int 值域 [min, max]，每次猜中点 mid，扫描统计 ≤mid 的个数，判断中位数在左半还是右半，不断缩小区间。需要约 log2（42亿）≈32 次全量扫描（IO 多）；
对比：分桶统计只需 2~3 遍扫描，更优；桶要按实际数据分布切（先采样估计值域分布，避免某桶过大）；
补充：若整数范围已知且密集（如 0~1 亿），可直接用位图统计频次（每数一个计数），一趟完成。
容量估算： 100 亿 int：若 4B 原始约 40GB，内存 2G → 分桶计数。值域假设 32 位无符号约 43 亿区间，这里分 1000 桶（每桶约 430 万；与思路一的 420/512 桶是同一方法的不同粒度——桶越多，第二遍要载入内存的候选越少），每桶计数用 4B×桶内可能值或位图。中位数位置=5e9，累计桶计数找到目标桶，桶内再精确定位。一次扫描内存只需桶计数数组（1000×8B 级）+ 可选桶内压缩位图。I/O 一遍为主。
失败与降级： 值域未知/极端长尾：先扫描求 min/max 再分桶，或改多轮。计数溢出用 64 位。作业失败重扫成本高，可先抽样估计桶边界。
【原理溯源】
- 为什么中位数不能“排序取中间”？ 100 亿 int 原始 40GB，排序需要外排多趟 IO。分桶法把“全序”问题降为“定位区间+区间内精确”，通常只需 2 遍扫描——用值域上的粗定位换取 IO 的大幅下降。
- 为什么第一遍只需计数器数组？ 我们不需要知道每个具体值，只需知道“落在每个值域区间有多少个数”。计数器数组大小=桶数，与 n 无关。累加前缀和即可判断中位数落在哪一桶。
- 为什么第二遍只扫目标桶？ 中位数已锁定在某一值域区间。第二遍只关心落在该区间的数（其他直接跳过），内存压力=该桶元素数×4B。桶切得均匀时，期望元素数≈n/桶数，100 亿 ÷ 512 ≈ 2 千万（1e10/512=1.95e7），×4B ≈ 78MB，可入 2G。
- 值域二分为什么 IO 多？ 每次猜 mid 都要全量扫描统计 ≤mid 的个数，约 log2（值域）≈32 次。若每次扫描 40GB，IO 恐怖。适合作为“内存更紧、能接受多次扫描”的备选，或与分桶结合（桶内二分）。
- 为什么桶不能机械均分？ 若数据集中在 [-1000,1000]，均分到 42 亿范围会导致某桶极挤、其他桶空。先采样估计分布，按分位数切桶或动态二分，保证桶内均匀。
【选型判断树】
海量整数分位数：
1. 值域是否小且密集？
├─ 是 → 计数数组/位图一趟统计
└─ 否 → 分桶
2. 分桶
├─ 采样估分布 → 切成均匀桶
├─ 第一遍：桶计数 + 前缀和定位
└─ 第二遍：只收目标桶，桶内精确
3. 桶内仍大
└─ 桶内继续分桶或值域二分
4. 备选
└─ 纯值域二分：约 32 遍扫描判断口诀： 两遍扫描：计数定位，桶内精确；先采样防倾斜。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “中位数=第 K 小，用分桶把全序降为区间定位” |
| 0:30–1:30 | 第一遍 | 值域分桶计数，前缀和找桶 |
| 1:30–2:30 | 第二遍 | 只收目标桶，排序/二分 |
| 2:30–3:30 | 对比值域二分 | 32 遍 vs 2 遍 |
| 3:30–4:30 | 分布与密集 | 采样；计数数组特例 |
| 4:30–5:00 | 收尾 | “定位粗、精确细，IO 最省” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| int 值域 | 约 ±21 亿 | 2^32 |
| 桶数 | 256–1024 | 使目标桶可入内存 |
| 扫描遍数 | 2 遍 | 计数+目标桶 |
| 值域二分次数 | ≈32 | log2（42亿） |
| 100 亿 int 原始 | ≈40GB | 不能全载 |
【追问链】（三层）
L1｜“找众数（出现超过一半）怎么办？” → 摩尔投票法：O(n) 时间 O(1) 空间，无需分桶。若求出现次数最多的 TopK 众数，则回到哈希分治计数+堆（204 题）。
L2｜“目标桶还是放不下 2G 怎么办？” → ① 增加桶数使更细；② 桶内再分桶递归；③ 桶内值域二分。关键是单层内存超限就再切一层。
L3｜“外排取中位数不行吗？” → 可行，正确但 IO 更多（排序多趟）。分桶是针对“只需一个顺序统计量”的优化——不需要全序，只需定位。面试要能对比两者 IO。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“分段统计” |
| 80 分 | 讲清两遍分桶、前缀和定位、桶内精确 |
| 95 分 | 对比值域二分 IO；采样防倾斜；密集域计数数组；与众数算法区分 |
【关联题】
- 分治： 第 202 题
- TopK： 第 204 题
- 外排： 第 203 题
- MapReduce： 第 206 题
【自测】
- 分桶法求中位数需要几遍扫描？各做什么？ 参考答案：两遍。第一遍桶计数+前缀和定位；第二遍只收目标桶内精确求第 k 小。
- 为什么值域二分 IO 更多？ 参考答案：每次猜中点都要全量扫描统计，约 log2（值域）≈32 次。
- 数据分布极不均匀时怎么切桶？ 参考答案：先采样估计分布，按分位数或递归二分切桶，避免单桶过大。
206. 海量文本文件要统计单词出现次数 Top 100（MapReduce 思想）
【考察内容】MapReduce 编程模型与海量统计
【题目】一批总大小 TB 级的英文文本文件，需要统计所有单词的出现次数，并输出出现次数最多的 100 个词。要求方案能跑在普通机器集群（或单机多进程）上。请给出类 MapReduce 的完整方案，并说明每个阶段做什么、数据怎么流转。
【参考答案】
Map 阶段（分片并行）：把大文件切分成小分片（如每片 64MB），每个 worker 读一个分片，分词并输出 (word, 1) 键值对；可按 h(word)%N 将键值对分区写入对应中间文件（保证相同单词进同一分区）；
Shuffle/分区阶段：相同单词的 (word, 1) 汇聚到同一分区（同一次 reduce 的输入）；
Reduce 阶段（聚合）：每个 reducer 处理一个分区，把相同单词的计数累加（HashMap 聚合），输出 (word, count)；
若单词总量仍大：对输出再做一轮“分区聚合”，或直接输出全量 (word, count) 结果文件；
取 Top100：对每个分区的统计结果，各用大小为 100 的小顶堆取局部 Top100，再对局部结果合并取全局 Top100；
单机多进程版：用多线程/进程分别处理分片，结果文件按单词哈希分桶合并，思路一致。
容量估算： 单词 Top100：Mapper 本地 combiner 预聚合可大幅减 shuffle。Reducer 按词哈希分片，单机内存=单分片 distinct 词×平均 key 长度。若 distinct 千万级，分片数 64–256。Shuffle 量≈总词次×(词长+计数)×(1-合并率)。Top100 各分片局部 Top 再全局合并，网络只传很小。
失败与降级： 长尾热词导致单 reducer 热点：combiner + 二次散列。脏数据/编码不一致先清洗。失败任务按分片重试；结果与抽样日志统计对账。
【原理溯源】
- 为什么 MapReduce 能把 TB 级统计跑起来？ 核心是把计算移到数据旁+按 key 分区聚合。Map 并行处理分片（无共享状态），Shuffle 保证相同 key 到同一 reducer，Reduce 再做局部聚合。水平扩展简单：加机器加分片即可。
- Shuffle 为什么是正确性关键？ 若相同 word 落到不同 reducer，会输出多个半截计数，无法得到全局次数。
h(word)%N保证同 word 同分区——与 202 题“同哈希必同桶”是同一原理。 - 为什么要局部 Top100 再合并？ 全量 (word,count) 可能很大。每个 reducer 先用小顶堆丢掉非 Top100，网络与最终合并量大幅下降。因为全局 Top100 一定包含在各分区 Top100 的并集里（反证：若某词是全局第 k 却不在其分区 Top100，则分区内已有 100 个更大的，全局它进不了前 100）。
- MapReduce 与 204 题 TopK 的关系？ 204 是单机分治版：分桶=Map+Shuffle，桶内计数+堆=Reduce+局部 TopK。MapReduce 是分布式框架化同一思想。面试应能把两者串起来讲。
- 数据倾斜怎么处理？ 若某单词（如“the”）特别多，对应 reducer 会成瓶颈。对策：combiner 在 Map 端预聚合、热点 key 加盐再二次聚合、或自定义分区器打散。首字母分区会倾斜，哈希分区较均匀。
【选型判断树】
海量词频 TopK：
1. 单机内存够 distinct 吗？
├─ 够 → Map 计数 + 堆
└─ 不够/多机 → MapReduce
2. MapReduce 阶段
├─ Map：分词发射 (w,1)，本地 combiner 预聚合
├─ Shuffle：h(w)%R 分区
└─ Reduce：聚合 count，局部 Top100 堆
3. 最终
└─ 合并各 reducer 局部 Top100
4. 倾斜
└─ combiner / 热点加盐二次聚合判断口诀： Map 发射，Shuffle 按 key 聚，Reduce 计数，局部 TopK 再归并。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “MapReduce 把海量统计拆成并行 Map + 按 key Reduce” |
| 0:30–1:30 | Map | 分片、分词、(w,1)、combiner |
| 1:30–2:30 | Shuffle | 同 word 同分区；正确性 |
| 2:30–3:30 | Reduce | 聚合；输出 (w,count) |
| 3:30–4:30 | Top100 | 局部堆+全局合并；为何正确 |
| 4:30–5:00 | 收尾 | “与单机哈希分治同一思想，只是分布式化” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 分片大小 | 64–256MB | 兼顾并行与开销 |
| 分区数 R | 按集群 reducer 数 | 通常几十到几百 |
| Combiner | Map 端预聚合 | 大幅减 Shuffle 量 |
| 局部 TopK | 每 reducer 堆大小 100 | 合并安全 |
| 英文 distinct | 常见数十万～百万级 | 可能单机放得下 |
【追问链】（三层）
L1｜“Combiner 是什么？为什么能用？” → Map 端的本地 Reduce，先把同一分片内相同词聚合再输出，减少 Shuffle 网络量。因为词频聚合满足结合律交换律，结果不变。
L2｜“reducer 结果还是太大怎么办？” → 再做一轮 MapReduce（二次聚合）；或 reduce 输出时继续分区压缩；Top100 场景其实局部堆已把结果压到很小。
L3｜“单词按首字母分桶行不行？” → 会倾斜（以 t、a 开头的常用词极多）。应用哈希分区。若必须按业务键分区，需热点检测与加盐二次聚合。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“分文件统计再合并” |
| 80 分 | 讲清 Map/Shuffle/Reduce、同 key 分区、TopK 堆 |
| 95 分 | 局部 Top100 正确性证明；combiner；倾斜；与单机分治打通 |
【关联题】
- 哈希分治： 第 202 题
- TopK： 第 204 题
- 外排： 第 203 题
- 日志系统： 第 140 题
【自测】
- MapReduce 中 Shuffle 的作用是什么？ 参考答案：按 key 哈希分区，保证相同单词进入同一 reducer，聚合正确。
- 为什么可以先算各分区 Top100 再合并？ 参考答案：全局 Top100 一定出现在各分区 Top100 的并集里，否则与分区计数矛盾。
- Combiner 有什么好处？ 参考答案：Map 端预聚合，减少 Shuffle 网络传输量，结果不变（满足结合律）。
207. 注册时要在 1 亿存量手机号里毫秒级判断“是否已注册”（在线布隆过滤）
【考察内容】在线布隆过滤器与精确兜底的分层架构
【题目】注册流程要求：用户输入手机号后，系统要毫秒级判断该号是否已注册（避免重复注册）。存量已注册手机号 1 亿条，存 MySQL（几十 G），Redis 放不下全量。怎么做“在线快速查重”？布隆过滤器误判“已注册”会有什么影响、怎么兜底？
【参考答案】
方案：布隆过滤器前置 + MySQL 精确兜底——内存/Redis 里放一个针对 1 亿已注册手机号的布隆过滤器（误判率 1% 约需 120MB，5% 约需 78MB）；判断“不在”→ 100% 确定未注册，直接放行；判断“在”→ 有误判可能，去 MySQL 精确查；
误判“已注册”的影响：把未注册手机号误拦为“已注册”，用户无法注册——所以不能直接拒绝，必须 MySQL 二次确认；若布隆说“在”而 DB 查无，则放行注册；
更新一致性：新注册成功就向布隆写入该手机号（add 一次；布隆只增不删，手机号注销后不再重新注册的业务可接受，若允许注销后重注册则需定期重建或改用计数布隆）；
规模再大（几十亿）：布隆 + 一致性哈希分片（每台机器管一部分哈希区间）；或用 Redis 精确 set 分片（成本高）；
兜底：布隆可做成“多级”（内存布隆 + Redis 布隆），DB 永远做最终精确源。
容量估算： 1 亿手机号判断是否已注册、毫秒级：布隆在线过滤 p=0.1%–1%。n=1e8，p=1% → m≈9.6e8 bit≈120MB；p=0.1% → ≈180MB。Redis bitmap/bitfield 可承载，QPS 可达数万–十万级。注册写路径：先布隆+DB 唯一索引双保险；布隆只能挡明显不存在的查询压力，真正唯一靠 DB。
失败与降级： Redis 不可用：本地已加载布隆分片缓存兜底；降级为 DB 查（必须限流）。重建布隆用全量手机号导出，期间“可能误判为已存在”会让少数正常注册失败——需人工/重试通道。监控误判率与 Redis 内存。
【原理溯源】
- 为什么不能直接查 MySQL？ 1 亿行手机号即使有索引，高并发下 DB QPS 与 RT 都不理想，且拖库风险大。布隆用约 120MB 内存挡住绝大部分“未注册”请求（它们不必打 DB），只把“可能已注册”的流量放到 DB——用概率结构把 DB 压力降一个数量级。
- 为什么误判方向决定了业务处理？ 布隆假阳性=把未注册误判为已注册。若直接返回“已注册”，用户无法注册且投诉。所以流程必须是：布隆说“不在”→ 放行；说“在”→ 查 DB 确认。概率结构的“是”必须被精确源确认。
- 为什么与 201 题同一结构不同侧重？ 201 是离线风控判断，误判多拦一次成本低；207 是在线注册体验，误判会直接伤害用户，因此对二次确认的实时性要求更高（DB 必须毫秒级响应）。场景决定误判代价，代价决定是否要精确兜底。
- 新注册如何同步？ 注册成功事务提交后，异步或同步向布隆 add。注意：若布隆写失败，会出现“已注册但布隆不知道”→ 下次仍会打 DB，只影响性能不影响正确性（DB 是源）。反向（布隆有、DB 无）只可能来自误判或删除场景。
- 注销重注册怎么支持？ 标准布隆不能删。方案：① 业务不允许重注册则无需删；② 计数布隆；③ 定期全量重建；④ 删除手机号先记“墓碑”精确集合，查询时先查墓碑再查布隆。
【选型判断树】
在线存在性查重：
1. 精确集合能进内存/Redis 吗？
├─ 能（百万级）→ Redis Set/本地缓存
└─ 不能（亿级）→ 布隆
2. 误判"已注册"能否直接拒绝？
├─ 不能（用户受损）→ 布隆粗筛 + DB 精确兜底
└─ 能（黑名单）→ 可直接拦（201 题场景）
3. 更新
└─ 新增同步 add；删除→重建/计数/墓碑
4. 扩展
└─ 一致性哈希分片布隆；多级布隆判断口诀： 亿级用布隆；假阳性必须 DB 确认；DB 是唯一精确源。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “在线查重：布隆挡流量，DB 保正确” |
| 0:30–1:30 | 空间与流程 | 1 亿/1%≈120MB；不在→放行，在→查库 |
| 1:30–2:30 | 误判影响 | 不能直接拒；必须二次确认 |
| 2:30–3:30 | 一致性 | 新增 add；删除难题 |
| 3:30–4:30 | 扩展 | 分片布隆；多级 |
| 4:30–5:00 | 收尾 | “概率做前置，关系库做终审” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 1 亿/1% 布隆 | ≈120MB | 9.6 bit/元素 |
| 1 亿/5% 布隆 | ≈78MB | 误判换空间 |
| 判断延迟 | 内存布隆 μs 级 | 毫秒级要求轻松满足 |
| DB 兜底 | 仅布隆判“在”时 | 命中率低 |
| 布隆 TTL/重建 | 可周期重建 | 支持删除类变更 |
【追问链】（三层）
L1｜“布隆误判率怎么设？” → 按业务容忍度与内存预算权衡：注册查重 1%–5% 常见。误判率低则内存大；高则 DB 兜底流量增多。用 p=1% 起步，观察 DB 查重 QPS 再调。
L2｜“手机号注销后能否重用？” → 标准布隆不支持删。若业务允许重注册：计数布隆、定期重建、或精确墓碑集合+布隆组合。若不允许重注册，则无需删除。
L3｜“直接把 1 亿手机号放 Redis Set 行不行？” → 理论可行但内存数十 GB，成本高。布隆以约 1% 误判换 100 倍空间压缩。若预算充足且要精确，Redis 集群分片 Set 也可——要讲清成本取舍。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“用布隆过滤器” |
| 80 分 | 讲清粗筛+DB 兜底、误判不能直接拒、空间量级 |
| 95 分 | 更新/删除一致性；与黑名单场景对比；分片与多级；成本取舍 |
【关联题】
- 离线布隆： 第 201 题
- 生产布隆： 第 44 题
- 缓存穿透： 第 24 题
- 时间窗口： 第 208 题
【自测】
- 布隆判“已注册”后为什么不能直接拒绝用户？ 参考答案：可能是假阳性，会误伤未注册用户。必须 MySQL 精确确认。
- 为什么布隆说“未注册”可以直接放行？ 参考答案：布隆无假阴性，“不在”100% 准确。
- 1 亿手机号、1% 误判率大约多少内存？ 参考答案：约 120MB。
208. 如何快速定位“5 分钟内重复登录”的账号（时间窗口 + 位图/布隆）
【考察内容】时间窗口与海量实时去重的工程结合
【题目】安全团队怀疑有批量撞库：同一 QQ 号在 5 分钟内登录超过 1 次即异常。登录日志每秒几十万条，账号总量 14 亿。要求实时检测“5 分钟窗口内重复登录的 QQ 号”并告警。怎么设计？（提示：考虑位图/布隆的时间窗口维护与清理）
【参考答案】
方案 A：滑动窗口 + Redis 计数——key=QQ 号，value=最近一次登录时间戳（或 5 分钟内登录次数）；每次登录 SET 并判断：若已有 key 且时间在 5 分钟内 → 命中重复，告警；key 设置 5 分钟过期（TTL 自动清理）。内存：14 亿账号若全量常驻，按每个 key 60–90B 的结构开销算是 ≈90–130GB（不是「几十 G」），量级差 3–4 倍；本方案能落地的唯一前提是「只保留 5 分钟窗口内的活跃 key」：5e5 事件/s×300s＝1.5 亿 key×约 90B≈13.5GB——答题要把这个前提和这两个数一起说出来；进一步可加“只保留 5 分钟内有登录的活跃 key”；
方案 B（常见错法，作答时拿来当对比）：切两个 5 分钟位图桶，当前桶与上一桶做位与（AND），非空即判重复——这个方案不成立：① 两次登录落在同一个桶时置的是同一位，与上一桶 AND 恒为 0，而「5 分钟内重复」多数恰恰落在同桶 → 漏报；② 落在相邻两桶的两次实际可相隔近 10 分钟 → 误报成 5 分钟内重复；③ 固定桶不是滑动窗口，「天然滑动」是方案 C 的轮转结构才被成立的性质。正解见方案 C：先查位再置位，且桶数要按窗口长度切够。
方案 C：多桶布隆/位图轮转——按窗口长度切成 N 个桶（5 分钟窗口就切 5 个“每分钟桶”），当前桶写入，检测时对最近 N 个桶逐桶查询/做或运算，命中即疑似重复；分钟切换时写入新桶、丢弃最旧的桶，天然滑动。注意：两个桶只覆盖约 2 分钟，覆盖不了 5 分钟窗口，必须按窗口长度切够 N 个。误判率可接受（宁可多报不可漏报）；
方案 D：流式计算（Flink）——按 QQ 号开 5 分钟滚动窗口，窗口内 count>1 输出告警，适合跨多机海量流；
告警联动：命中后查全量登录记录确认是否异地/IP 异常，再决定是否拦截（布隆/位图只做第一层粗筛）。
容量估算： “5 分钟内重复登录”：滑动窗口计数或位图。每用户 5 分钟桶：用 Redis key
login:{uid}:{minute}或 bitmap 5 bit。存储：活跃用户数×窗口内键。QPS 按题干给定的量算，不要写成「远低于读接口」：题干是「登录日志每秒几十万条」，要处理的是日志事件流而不是登录请求，两者差 1–2 个数量级；单 Redis 实例自述约 10 万 ops/s，5e5 事件/s 就必须 ≥5 个分片实例（还要给查询留余量），或者走 Flink＋本地状态。精确定义：同一账号/IP/设备维度；窗口精度 1 分钟足够多数风控。离线可用小时级数仓 + 在线 Redis 组合。失败与降级： Redis 丢窗口会导致漏判/误判：风控评分降级为更宽规则或暂存本地。误伤正常用户要有申诉/二次验证通道。规则上线前用历史日志回放评估误报率。
【原理溯源】
- 为什么 TTL 天然实现滑动窗口？ Redis key 设 5 分钟 TTL，只保留“最近 5 分钟活跃”的账号。每次登录：若 key 存在且未过期 → 窗口内重复；若不存在 → 首次。过期即离开窗口，无需显式清理。这是用存储过期模拟时间窗口的最简工程手法。
- 为什么位图时间桶必须切够 N 个？ 5 分钟窗口若只保留“当前分钟桶+上一分钟桶”，只覆盖约 2 分钟，会漏掉 2–5 分钟前的登录。正确做法是 5 个分钟桶轮转：新分钟来时丢弃最旧桶。漏桶=漏报，这是本题最大陷阱。
- 为什么粗筛后仍要精确确认？ 位图/布隆有碰撞/误判，可能把不同 QQ 号判为重复。告警系统应：粗筛命中 → 查登录流水（精确 IP/设备/时间）→ 确认再处置。避免误封正常用户。概率结构只做第一层，业务决策必须精确。
- Flink 适合什么规模？ 单 Redis 实例简单命令约 10 万级 ops/s，要到几十万需按账号分片或多实例；进程内位图/单机多核才谈得上数十万。若跨地域多数据中心、或还要做更复杂的会话分析，用 Flink keyed window 更合适：天然支持乱序、迟到、精确一次语义。代价是集群运维成本。
- 为什么说“宁可多报不可漏报”？ 安全检测场景假阳性成本是“多查一次日志”，假阴性成本是“放过撞库”。所以可接受布隆/哈希位图的误判。这与注册查重（假阳性伤害用户）方向相反——同一结构，业务代价决定误判取舍。
【选型判断树】
时间窗口重复检测：
1. 流量与部署
├─ 单机/单 Redis 可扛 → 方案 A TTL 计数
└─ 要极省内存/可误判 → 方案 C 多桶位图轮转
2. 桶轮转关键
└─ 桶数必须覆盖整个窗口（5 分钟→5 个 1 分钟桶）
3. 跨机海量流
└─ Flink keyed window
4. 处置
└─ 粗筛命中 → 流水精确确认 → 告警/拦截判断口诀： TTL 即滑动窗；桶数=窗口粒度；粗筛后必精查。
【口述骨架】（5 分钟）
| 时间 | 任务 | 内容 |
|---|---|---|
| 0:00–0:30 | 定性 | “时间窗口去重：TTL 计数或位图桶轮转” |
| 0:30–1:30 | 方案 A | Redis key+TTL；只存活跃 |
| 1:30–2:30 | 方案 A/C | 位图/布隆做粗筛；B（两个固定桶做 AND）是错法，只当反面对比——同桶漏报、相邻桶误报，且桶数必须覆盖整个窗口 |
| 2:30–3:30 | 陷阱 | 只留两桶会漏报 |
| 3:30–4:30 | 分层 | 粗筛+流水精查；Flink 规模化 |
| 4:30–5:00 | 收尾 | “窗口维护是核心，误判方向看业务” |
【关键数字】
| 参数 | 经验值 | 说明 |
|---|---|---|
| 窗口长度 | 5 分钟 | 桶数按粒度切够 |
| Redis TTL | = 窗口长 | 自动滑出 |
| 桶粒度 | 1 分钟×5 | 勿只用 2 桶 |
| 登录日志事件 | 数十万/秒（题干口径） | 单实例约 10 万 ops/s 扛不住，需 ≥5 分片实例或走 Flink＋本地状态 |
| 活跃账号 | 远小于 14 亿 | 实际内存可控 |
【追问链】（三层）
L1｜“TTL 方案跨机器怎么同步？” → Redis 本身是共享存储，多实例写同一 key 天然同步。单机位图方案需按 QQ 号哈希分片到多台，每台只处理自己分片的账号。
L2｜“误报怎么处理？” → 粗筛结构只输出“疑似”。告警后查登录流水（IP、设备、UA、时间）精确确认；可叠加信誉分与阈值（如同 IP 多号）。避免直接按布隆结果封号。
L3｜“位图能不能删除旧登录记录？” → 标准位图按时间桶整体丢弃，不按单条删除。若需要“移除某次误报登录”，应改用精确结构（Redis 记录）或重建该桶。时间桶设计本身就是用“整体过期”换简单性。
【评分标准】
| 档位 | 答案特征 |
|---|---|
| 60 分 | 知道“用缓存记录最近登录时间” |
| 80 分 | 讲清 TTL 滑动窗口、时间桶位图、桶数覆盖窗口 |
| 95 分 | 漏桶陷阱；粗筛+精查分层；与注册查重误判方向对比；Flink 规模化 |
【关联题】
- 布隆基础： 第 201 题、第 207 题
- 在线判重： 第 207 题
- 风控： 第 147 题、第 4 题（防刷）
- 流式窗口： 第 206 题 MapReduce 对照
【自测】
- 为什么 Redis TTL 能实现滑动窗口？ 参考答案：key 过期即离开窗口，只需保留窗口内活跃数据，无需显式清理。
- 时间桶位图只保留 2 个桶有什么问题？ 参考答案：覆盖不了完整 5 分钟窗口，会漏报。必须切够 N 个桶覆盖窗口长度。
- 为什么安全检测允许布隆/位图误判而注册查重不行？ 参考答案：安全检测假阳性只是多查一次，假阴性才是风险；注册误判会伤害用户。业务代价决定误判取舍。
后端主库第 1–208 题（第 1–200 题为八类高频技术场景题，第 201–208 题为海量数据处理补充题）+ 国企金融专题第 209–228 题。