统计 5000 万时间区间的最大并发量

日期：2026-07-11
标签：#面试 #八股 #后端 #系统设计 #场景题

一句话答案

将每条记录拆成“开始 +1、结束 -1”的事件，按时间排序后做前缀和，前缀和最大值就是同时存在的最大记录数。

面试口语版

这是典型扫描线问题。每条区间生成两个事件：开始时间加一，结束时间减一，按时间排序后顺序累加，最大累计值就是峰值。如果定义区间是 [start,end)，相同时间应先处理结束再处理开始；如果结束时刻也算在线，则反过来。5000 万行会产生一亿个事件，不能轻易全部放内存，可以让数据库分组聚合后排序，或者用离线计算框架做外部排序；若时间精度只到秒或分钟，也可以按时间桶聚合增量。

SQL 思路

SELECT ts, SUM(delta) AS delta
FROM (
  SELECT start_time AS ts, COUNT(*) AS delta FROM records GROUP BY start_time
  UNION ALL
  SELECT end_time AS ts, -COUNT(*) AS delta FROM records GROUP BY end_time
) e
GROUP BY ts
ORDER BY ts;

应用层对结果按顺序求前缀和及最大值。支持窗口函数的数据库也可继续使用 SUM(delta) OVER (ORDER BY ts)。

关键细节

必须先问清区间边界语义、时间精度、统计全量还是某一天。
为开始和结束时间建立索引只能改善读取，核心成本仍是聚合和排序。
数据量大时使用分区、外部排序、MapReduce/Spark，或预先维护时间桶增量表。
不要用每个时间点执行一次 start <= t AND end > t，复杂度过高。

面试官追问

相同时间的开始和结束谁先处理？
内存放不下一亿事件怎么办？
如何实时维护峰值？
时间跨度极大但事件稀疏怎么办？

面试官追问参考答案

1. 相同时间的开始和结束谁先处理？

取决于区间语义。若区间是 [start,end)，结束时刻已不活跃，相同时间应先处理 -1 再处理 +1；若是闭区间 [start,end]，结束时刻仍计入，则先处理开始。面试时必须先明确业务定义。

2. 内存放不下一亿事件怎么办？

先在数据库或分布式计算中按时间聚合相同事件，显著减少记录数，再做外部排序和流式前缀和。也可以将事件按时间范围分区，分别排序并携带前一分区的累计值；Spark/MapReduce 本质也是分区、排序和归并。

3. 如何实时维护峰值？

若按分钟等固定粒度统计，可将开始时刻桶 +1、结束时刻桶 -1 写入流处理系统，再按事件时间窗口维护前缀和与历史最大值。迟到和修正事件需要水位线、可撤回聚合或定期离线重算，峰值结果应带统计截止时间。

4. 时间跨度极大但事件稀疏怎么办？

不要为每个时间点建立数组，只保存实际发生变化的时间点，使用有序 Map、排序事件文件或压缩时间坐标。复杂度取决于事件数量而非时间跨度。