腾讯 TEG 云架平二面：MPSC 队列与限流器设计

《面试题目》

1. 你 C++ 熟吗？
2. 设计一个多生产者单消费者（MPSC）的任务队列，你会怎么设计？
3. 队列是有限长度的吗？队列塞满了，生产者这边应该怎么处理？
4. 追问：生产者线程当前这次插入操作失败了，是挂起还是继续往后处理别的事情？
5. 前面是用锁保证线程安全的，有没有方法可以做到无锁？
6. 有一个比较大的 QQ 号数据集（取值范围先限定为 32 位整型），要找出其中只出现过一次的 QQ 号，怎么找？
7. 你这个外排大概是什么样的处理过程？
8. 外排代价比较大，有没有不用排序、开销更小的办法？
9. 设计一个限流器：接入服务器要限制每个 key 每秒访问次数上限（如每秒 100 次），超过直接拒绝，怎么处理？
10. 只是计数的话，每秒这个时间窗口怎么体现出来？
11. 面试官指出每秒 reset 存在的问题：前一秒最后 100ms 来了 99 次没超限，reset 后下一秒前 10ms 又来 10 次——实际不到 1 秒却处理了超过 100 次，跨窗口突发打破了限制，怎么解决？
12. 追问：以 5 秒为一个时间窗口，来了一个请求，你怎么判断当前这个请求能不能放过？
13. 每个 key 都维护计数和 key 本身，key 量大、高并发时内存开销大，怎么减少内存开销？
14. 手写代码：原地归并排序，重点是要在原地处理。

《参考解析》

有界 MPSC 队列怎么设计（有锁版）：标准结构是环形缓冲 + 两个索引——生产者只改 head、消费者只改 tail，加一把互斥锁（或生产者侧一把、消费者侧一把）配合条件变量做等待唤醒。有界还是无界直接决定背压策略，有界队列满了通常三选一：阻塞等待（调用方线程挂起，靠条件变量被唤醒，适合后台任务）、立刻返回失败让生产者去做别的事（适合接入层，不能拖住网络线程）、丢弃最旧/最新的任务（只适合可丢的监控类数据）。面试官追问”这次插入失败是挂起还是继续做别的”，考察的就是你知不知道在哪个线程里阻塞——如果在网络 IO 线程里阻塞，整条连接都会被拖死。

无锁 MPSC 怎么做：单消费者是实现无锁的最大便宜——tail 只被消费者线程改，所以消费侧根本不用 CAS。生产者侧用一次原子 fetch_add(1) 预约槽位（比 CAS 循环更公平、几乎无饥饿），拿到序号后写入数据，再把该槽位的”已发布”序号用 release 语义写出去；消费者用 acquire 语义读序号，只处理已发布的连续槽位。这就是 Dmitry Vyukov 的 bounded MPMC 队列思路，注意三个坑：槽位序号要用”轮次 + 下标”防止生产者的预约与消费者的读取发生覆盖（ABA）、head 和 tail 要按 cache line 对齐（alignas(64) 或 padding）避免伪共享、内存序写错会在弱一致性的 ARM 上偶发丢数据。

32 位整数里找只出现一次的 QQ 号：位图法最直接——开两个位图，bit1 记录”出现过”、bit2 记录”出现过两次及以上”：第一次见置 bit1，第二次见置 bit2，最后 bit1 & ~bit2 就是答案。代价是 2^32 bit = 512MB/张，两张 1GB，内存不够就按高位分片（分成 4 片、每片 256MB、扫 4 遍原数据），仍然不够就对 id 做 hash 分桶写外存再逐个桶处理。外排的流程是：读入一块内存排序成有序 run 写临时文件，再做 k 路归并。想免掉排序，可以退到近似或分片计数（每个 id 用 2~4 bit 计数器，达到饱和值就不再涨），或者干脆用 hash 分片把单次处理的数据量压到能全放内存。

限流器：固定窗口的漏洞与替代方案：每秒 reset 的固定窗口问题是边界突发——窗口交界处实际 1 秒内可能放过接近 2 倍配额。四种常见解法：① 滑动窗口日志，用 Redis ZSET 存请求时间戳，每次 ZREMRANGEBYSCORE 清掉窗口外的再 ZCARD 判断，精确但内存最贵；② 滑动窗口计数，同时保留当前窗口和上一窗口的计数，按 prev × (1 - 已过时间/窗口长度) 加权估算，5 秒窗口的请求判断就是 cur + prev × 剩余比例 >= 阈值 ? 拒绝 : 放过，成本低、精度够用；③ 令牌桶，按 (now - last) / rate 补令牌，允许一定突发；④ 漏桶，把流量整形成恒定速率。生产上大多是 Redis + Lua 保证”取时间、算权重、加计数、比较”这一整套原子执行。

key 多了内存怎么省：单个 key 的限流信息如果用 Redis 的独立键存，每个键的元数据开销（dict entry、过期字典）比计数本身还大。可用的手段：把同一维度的计数塞进 Redis Hash 分片（用 {bucket}:field 结构，配 HINCRBY + 对 field 设过期或用惰性清理），能省掉大量 key 元数据；只给活跃 key 分配结构，冷 key 直接判 0 不落存储；用近似结构代替精确计数（count-min sketch、布隆类结构），以少量误判换数量级的内存；本地内存做分片计数、按秒批量汇总到 Redis，把 QPS 高但 key 分散的场景下沉到无锁 map；最后是位数压缩（计数封顶到阈值即可，不需要 4 字节整数）。

手写原地归并排序：核心是 rotate（三次翻转实现块交换）加上二分定位。merge(a, mid, b) 的做法：设 len1 = mid - a、len2 = b - mid，若 len1 == 0 || len2 == 0 返回；若 len1 > len2，取右半的中点 j = mid + len2/2，在左半区间里二分找出第一个大于 arr[j] 的位置 i，然后 rotate(i, mid, j)，此时 arr[j] 落到了最终位置 i + (j - mid)，再递归处理左右两段；len1 <= len2 时对称地取左半中点去右半二分。时间复杂度从 O(n log n) 退化到 O(n log²n)（每层都多一次二分与翻转），空间 O(1)，是纯原地归并的标准答案。如果允许 O(√n) 辅助空间，可以用分块 + 内部缓冲的 block merge sort，把复杂度压回接近 O(n log n)；工程实现里也有 SymMerge 这类更复杂但更快的变体。

这场的复盘：作者提到从八月起几乎所有面试都在问实习和项目，这场反而全是”复古”的并发与设计题，反问后确认面试官所在部门就是做存储的。面试官主动指出候选人方案的漏洞并追问替代方案，是典型的”看思维过程不看答案”的面法：设计题要先说清约束（有界/无界、能不能丢、在哪个线程阻塞），再给方案和代价。