今日头条后端暑期实习二面:RocketMQ 延迟消息架构与两降序数组第 k 大
- 轮次
- 二面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 自我介绍,以及个人情况和一些经历问题。
- 讲讲你在 WXG 参与了什么?架构是怎么样的?一共有哪些微服务?
- 简历追问。
- 在 AI Coding 上有什么实践吗?
- 实验室这边还有任务吗?这段时间在学什么、开发什么?
- 讲讲 Redis 的 String 底层实现?长字符串发生变化时怎么调整?
- ZSet 底层实现?
- InnoDB 的索引底层实现?InnoDB 的索引类型有哪些?
- RabbitMQ 和 Kafka 有什么区别?功能上有什么区别?
- 设计 RocketMQ 延迟消息的架构和实现方案?(帖主答的是定时任务加载可投递的消息)
- 如果延迟队列里有很多消息,定时任务消费速度慢导致消息拥塞,怎么解决?(连续追问)
- 给两个降序数组,怎么找到第 k 大的数?双指针或堆的复杂度是多少?有没有 O(log n) 的做法?
- 算法:用 O(log n) 找两个降序数组的第 k 大元素。
《参考解析》
Redis String 的底层与扩容:String 用 SDS(简单动态字符串)实现,结构里有 len、alloc、flags 和字节数组,因此取长度是 O(1)、二进制安全、不会因为内容里有 \0 被截断。追加内容时若剩余空间不足会扩容:新长度小于 1MB 时按两倍扩,超过 1MB 时每次多扩 1MB,并预留一部分空闲空间以减少频繁分配。注意 Redis 3.2 之后 SDS 按长度分了 sdshdr5/8/16/32/64 几种头,短字符串用更小的头省内存。
ZSet 底层:元素少且值短时用 listpack(旧版本是 ziplist),超过阈值(默认 128 个元素、单元素 64 字节)转为 skiplist 加哈希表。跳表负责按 score 排序与范围查询,哈希表负责 O(1) 按成员取 score。跳表相比平衡树实现更简单、范围查询天然有序,代价是空间换层数。
InnoDB 索引:底层是 B+ 树,非叶子节点只存键、叶子节点存数据并用双向链表串联,因此范围扫描高效、树高通常 3 到 4 层。聚簇索引按主键组织,叶子节点就是整行数据;二级索引叶子节点存主键值,查询非索引列要回表。类型上分主键(聚簇)、唯一、普通、前缀、联合、全文索引;按数据结构还有自适应哈希索引,由 InnoDB 自己根据访问模式建立。
RabbitMQ 与 Kafka 的差异:RabbitMQ 是传统消息队列,以 broker 为中心做路由,支持复杂 exchange(direct、topic、fanout、headers)、消息确认、优先级、延迟队列,单条消息延迟低,适合业务解耦与任务分发;Kafka 是分区日志,消息按 partition 追加、消费者按 offset 拉取,吞吐高、支持回溯与多消费者独立消费,适合日志、埋点、流处理。取舍点是「要灵活路由与低延迟选 RabbitMQ,要高吞吐与可重放选 Kafka」。
RocketMQ 延迟消息架构:原生 RocketMQ 4.x 只支持固定延迟级别,做法是把延迟消息先写入 SCHEDULE_TOPIC_XXXX 下对应延迟级别的队列,由定时服务扫描到期后转投真实 topic。5.0 引入定时消息,用时间轮(timer wheel)按投递时间分槽,到点触发投递,支持任意时间精度。设计时要讲清三件事:延迟消息的存储与索引(按投递时间排序)、到期扫描的触发机制、以及转投时的幂等与重复投递处理。
定时任务扫描慢导致积压的解法:先定位瓶颈是「扫描范围太大」还是「单次投递太慢」。方向包括:按时间分片,把到期时间落在不同 slot 的消息分给不同扫描线程,避免全表扫;用时间轮或延迟队列替代轮询,把「查」变成「到点触发」;批量拉取并批量转投,减少网络往返;扫描进度用位点持久化,避免每次从头扫;消息量极大时按业务维度拆 topic 或多实例分片消费。回答时补一句「延迟消息的语义是至少一次,消费端必须幂等」,这是这类设计的必答项。
两个降序数组的第 k 大,O(log n):设两个数组降序,要找合并后第 k 大,等价于在第 k 大的左侧取 i 个来自 A、j = k - i 个来自 B,满足 A[i-1] >= B[j] 且 B[j-1] >= A[i](边界用哨兵处理)。在 i 的取值区间 [max(0, k - len(B)), min(k, len(A))] 上二分,根据比较结果收缩,复杂度 O(log(min(len(A), len(B))))。若数组是升序,则改找第 k 小,思路对称。双指针是 O(k),用大小为 2 的堆逐个弹出也是 O(k),面试里要能说出三者复杂度差异再动手写二分,避免写完才被问「能不能更快」。