字节抖音平台后端一面：大 key 热 key、令牌桶与 singleflight

《面试题目》

1. 自我介绍，并介绍在腾讯做的项目（面试重点在项目深挖，穿插八股与算法）。
2. Redis 的大 key 和热 key 怎么解决？
3. 令牌桶怎么实现？
4. 手写 singleflight 机制。
5. 二叉树层序遍历。

《参考解析》

大 key 与热 key：先能发现，再谈治理

这两个概念要分开答。大 key 指单个 key 的 value 过大（几十万成员的 Hash/List、几百 KB 的 String），危害是单次读写耗时长、占用大量网络带宽与内存，主从同步和集群迁移也会被它卡住。发现手段是 redis-cli --bigkeys、用 SCAN 采样统计元素个数与长度、或者从慢日志里找耗时尖峰。治理思路四条：拆——按业务维度把大 Hash 拆成多个小 key 或拆成多组 field；清——集合设置过期与定期清理，不要无限追加；换——特别大的 value 放对象存储，Redis 里只留索引；读——用 HSCAN/SSCAN 分批遍历，绝不在生产上跑 KEYS * 或全量 HGETALL。

热 key 是个别 key 的 QPS 极高，危害是单分片被打满（Cluster 下尤其明显，同一个 key 只落一个分片）。治理手段：本地缓存兜底（进程内缓存加短过期，配单飞防止击穿）、把 key 复制成多份（hotkey:1..N 随机读）把压力摊到多个分片、读写分离加从节点分摊读、前置限流与降级避免热点穿透到底层、客户端做热点统计上报或代理层采样。面试时把”怎么发现、怎么拆、怎么防击穿”三层说清就够，其中本地缓存加分布式锁（或单飞）这个组合是必答项。

令牌桶：允许突发，实现要保证原子性

令牌桶按固定速率往桶里放令牌，桶有容量上限，请求取到令牌才放行。它与漏桶的关键差别是允许突发：桶里攒下的令牌可以被短时间一次性取走，所以能扛住流量毛刺，同时用放令牌的速率约束长期平均速率。实现要点是”惰性补充”——不真的起定时器，而是每次请求按 (now - lastRefill) * rate 补令牌并封顶到桶容量，再判断余量是否够减。并发下”读-算-写”必须原子：单机用 CAS 或 synchronized，分布式场景用 Redis 加 Lua 脚本一次完成（Lua 在 Redis 内单线程执行，天然原子），或直接用成熟的 Redis 令牌桶实现。要注意用单调时钟、用 Redis 的 TIME 而不是各客户端本地时间（时钟漂移会让限流失效），key 的 TTL 要设好避免无用 key 堆积。常见追问是”桶容量与速率怎么定”：容量决定能容忍多大的突发，速率对应长期平均承载，两者要按下游真实容量定，而不是拍脑袋。

手写 singleflight：把同一 key 的并发请求合并成一次

singleflight 解决缓存击穿：某个 key 失效的瞬间大量并发请求同时打到后端，希望只有一个真正执行、其余共享结果。核心结构是 map[key]*call 加一把互斥锁，call 里放 sync.WaitGroup、结果 val、错误 err 以及”我是不是执行者”的标志。流程：加锁查 map，没有就创建 call、wg.Add(1)、放进 map、标记自己是执行者，然后解锁；执行者跑真正的业务，把结果写进 call 后 wg.Done()，最后加锁把 key 从 map 删除；跟随者拿到 call 后 wg.Wait()，再读 val/err 返回。

要能主动说出几个坑：① panic 会传染——执行者 panic 时跟随者可能永远等下去，需要 defer 加 recover 并把错误传给跟随者；② 长耗时请求会把所有跟随者一起卡住，需要 context 超时或取消，超时后让调用方自己降级；③ 共享的是同一份引用，返回可变对象要注意并发写；④ key 的粒度要选对（比如按”用户 + 商品”而不是整个接口），否则会串结果；⑤ 可扩展成返回 channel 的版本以支持 select 超时。标准库扩展 golang.org/x/sync/singleflight 就是这个模型，能手写出来并讨论上面这些边界，才算真的理解。

二叉树层序遍历：BFS 模板题

用队列做 BFS：根节点入队，循环里先记下当前层的元素个数 size，只处理这 size 个节点并顺手把它们的左右子节点入队，这样每轮结束正好得到一层，天然支持”按层返回”以及求最大宽度、层平均值这类变体。复杂度 O(n) 时间、O(width) 空间（最坏是满二叉树最后一层，约 n/2）。要主动提的边界是空树、只有根、以及极深的树——递归版 DFS 可能爆栈，BFS 不会。变体还有锯齿形遍历（按层反转或用双端队列）、右视图（每层取最后一个）、按层连 next 指针。实现时注意用切片加 head 索引当队列，别每次 pop(0)，那样会退化成 O(n²)。