帆软二面：堆与红黑树、联合索引与多租户调度平台设计

《面试题目》

1. 请先做个自我介绍。
2. TrID 透传组件解决什么问题？具体怎么实现？为什么改造 Callable/run，而不是包装线程池或用开源方案？
3. 流式输出对接解决什么问题？具体怎么做？500ms 防屏控是前台还是后台行为？是后台聚合吗？
4. 流式消息怎么保证必达？中间失败怎么处理？
5. 完全二叉树有什么特性？数组怎么存储？最大堆、最小堆怎么理解？
6. 已有一个小顶堆，插入新元素的过程是什么？
7. AVL 树的平衡条件是什么？插入后怎么调整？旋转有哪几种场景？
8. 红黑树有哪些特性？能保证什么平衡效果？已有 AVL，为什么还要红黑树？
9. 算法题：服务只在部分日期启动，日期数组升序不重复；一天包 5 元覆盖当天，三天包 11 元连续覆盖三个自然日，中间不需启动的日期也计费，求最小启动成本。状态怎么定义？转移公式是什么？目前只有两个套餐，是否不需要二维？从后往前推时后续状态是什么？
10. 联合索引 ABC 下，AB、AC、BA 查询分别怎么命中？C 能命中索引吗？AC 查询具体怎么走索引？
11. 同样基于 ABC 索引，查 A、C 和查 A、B 性能有差异吗？过程是什么？这里涉及几种索引？主键、非主键怎么区分？哪种查询需要回表？
12. Redis 集群下，值怎么分布到各节点？Lua 脚本用到多个 key，在 Redis 集群下会有问题吗？
13. Redis 分布式锁的原理是什么？怎么保证锁可重入？怎么保证锁是自己拿到的？客户端拿到锁后长时间卡顿会怎样？锁过期但任务没完成怎么办？
14. 设计多租户定时调度平台：约 10 万租户，3 个调度节点、50 个执行节点，表结构和调度流程怎么设计？
15. 需要几张表？任务定义表和结果表是一对一还是一对多？实例表有哪些字段？
16. 多调度节点扫描任务表，怎么保证只调度一次？幂等键放哪张表，还是用 Redis？如果 Redis 写成功但数据库提交失败怎么办？
17. 调度完成后，怎么让执行节点执行？执行节点也轮询任务表吗？延时高、并发大怎么办？能否按规则把大队列切成 50 个小队列？为什么不直接用 RPC 或 MQ？
18. 用 MQ 延时队列怎么做？为什么需要延迟？能否在任务表加「下次触发时间」字段避免冗余？
19. 执行节点拿到任务后，怎么保证不重复执行？业务自身怎么保证只执行一次？
20. 你有开源项目、个人博客或小工具吗？平时研究过开源框架或源码吗？

《参考解析》

堆的数组存储与插入：完全二叉树除最后一层外每层都满、最后一层靠左连续，因此可以用数组零空洞地存储：下标 i 的左孩子 2i+1、右孩子 2i+2、父节点 (i-1)/2。大顶堆要求父节点不小于孩子，小顶堆反之。小顶堆插入：先放到数组末尾，然后上浮——和父节点比较，比父节点小就交换，直到根或不再更小，复杂度 O(log n)。删除堆顶则是把末尾元素移到根再下沉。

AVL 与红黑树：AVL 要求任意节点左右子树高度差不超过 1，插入后如果失衡按四种情形旋转：LL（右旋）、RR（左旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。红黑树用颜色约束近似平衡（根黑、红节点不能相邻、从任一节点到叶子的黑节点数相同），最长路径不超过最短路径的两倍。红黑树存在的理由是更新代价更低：AVL 更严格平衡、查询略快，但插入删除的旋转次数更多；红黑树插入最多两次旋转、删除最多三次，写多的场景更划算。工程里几乎都是红黑树（TreeMap、HashMap 的树化、epoll 的内核结构）。

日期套餐的最小成本（DP）：状态定义成「处理到第 i 个日期时，当前这张三天票的剩余覆盖天数」。从后往前推更好写：f(i, r) 表示第 i 天开始、已有 r 天剩余覆盖时的最小花费——若 r>0 则今天免费，转到 f(i+1, r-1)；否则买一天票（5 + f(i+1,0)）或三天票（11 + f(i+1,2)）。因为只有两种套餐，状态只有 0/1/2 三档，一维即可，不需要二维。注意「中间不需要启动的日期也计费」意味着三天票的覆盖是自然日连续的，所以剩余天数要按自然日递减，与日期数组是否跳天无关——这正是这题的主要陷阱。可以用记忆化或滚动数组，时间 O(n)。

联合索引 (A,B,C) 的命中：最左前缀原则。AB、BA、A、A B C 都能用上索引（优化器会自动调整等值条件的顺序，所以 BA 等价于 AB）；AC 只能用到 A 这一段，C 用不上索引定位（5.6 之后可以用索引条件下推 ICP 在存储引擎层过滤 C，减少回表次数，但仍是范围过滤而不是精确定位）；单独的 C 完全用不上。AB 与 AC 的性能差异在于：AB 能把两个条件都下推到索引定位，回表行数少；AC 只能定位到 A 的范围，回表行数多。回表指的是二级索引的叶子节点只存主键值，需要再按主键去聚簇索引取整行；如果查询的列都在索引里（覆盖索引）就不需要回表。

Redis 集群与 Lua：Cluster 用 16384 个槽做分片，CRC16(key) mod 16384 决定槽位。多 key 的 Lua 脚本要求所有 key 在同一个槽，否则报 CROSSSLOT；解法是hash tag——把 key 写成 {user:1}:a、{user:1}:b，花括号内的部分参与哈希，保证落在同槽。这是用法约束而不是 Redis 的能力缺陷。

分布式锁的完整链条：加锁用 SET key value NX PX ttl，value 是唯一标识；解锁用 Lua「比对 value 再删」防止误删；可重入靠 value 里带线程标识 + 计数（或用 Hash 存 owner -> count）；续期用看门狗（后台定时把 TTL 续上）应对长任务；锁过期但任务没跑完的根因是TTL 与业务时长不匹配，兜底是 fencing token——每次加锁生成单调递增的 token，写数据时带上 token，存储层拒绝比已见 token 更小的写入，从根上防止旧持有者的写入生效。

多租户调度平台设计：表分四类——job_definition（租户、cron、任务参数、状态）、job_instance（每次触发的实例：定义 id、计划触发时间、状态机、重试次数、执行节点、幂等键）、job_result（实例 id、开始/结束时间、退出码、日志地址，一对一或一对多取决于是否分步）、job_lock（调度幂等）。调度流程：调度节点按时间轮扫描「下次触发时间 <= now」的定义，为每个定义生成实例并写入 job_instance（唯一索引是 (definition_id, plan_time)），插入成功的那一个节点获得调度权——这就是「多调度节点只调度一次」的做法，比依赖 Redis 更可靠，因为在同一事务里。

Redis 与数据库双写不一致：如果先用 Redis 抢占再写库，Redis 成功而事务回滚会导致任务丢失。所以幂等键必须落在与业务同一个事务的存储里；Redis 只作为加速层，允许失效后回源。这是「唯一真相源」原则。

执行节点怎么拿到任务：轮询数据库在大规模下会带来延迟和空转压力。更好的方案是分片拉取 + 长轮询/通知：把执行节点按一致性哈希分成 50 个逻辑分片，每个节点只拉自己分片的任务；用 MQ（或 Redis Stream）做「有新任务」的通知，节点收到通知再批量拉一批，既降延迟又控并发。直接用 RPC 推送的问题是调度节点要知道谁空闲、要做负载均衡与故障转移；MQ 的问题是引入额外组件且消息与数据库状态可能不一致。工程上常选「数据库为准 + MQ 通知」的组合。

保证不重复执行：三层防线——调度层幂等（唯一索引）、分发层幂等（消息带实例 id，消费侧去重）、业务层幂等（业务自己用唯一键保证「只生效一次」）。最后一层最重要，因为前两层都可能因为重试而重复投递。