面经策

有一张表里面有三个字段，分别是（id，开始时间，结束时间），表中数据量为 5000W，如何统计流量最大的时候有多少条数据？ ​

  • 标签：场景题

🏛 业务架构师 ​

拿到这个需求我第一件事不是写 SQL，而是问清业务目的：这是给带宽容量规划做一次性分析，还是要常态化实时监控？两者方案和成本完全不同。

如果是一次性/离线分析（大多数场景）

5000W 数据在现代大数据平台上根本不算大，一条 Hive/Spark SQL 就能出结果，思路是经典的扫描线：

  • 把每条记录拆成两个事件：(开始时间, +1)、(结束时间, -1)
  • 按时间排序，做前缀和，前缀和的最大值就是最大同时在线/最大流量
sql
SELECT max(cnt) FROM (
  SELECT sum(type) OVER (ORDER BY ts) AS cnt
  FROM (
    SELECT start_time AS ts, 1 AS type FROM t
    UNION ALL
    SELECT end_time AS ts, -1 AS type FROM t
  ) e
) s;

时间复杂度 O(N log N)，交给分布式计算几分钟跑完。

如果要常态化实时监控

说明业务已经到了需要按分钟级观测资源峰值的水位（比如带宽计费、license 并发数），那应该走流式方案：Flink 窗口内维护增减事件，实时输出峰值曲线，并配告警。

我会主动提醒的成本权衡：如果业务方只是偶尔看一次，上一套实时计算集群是典型的过度设计，离线 T+1 加个定时任务就够了。数据方案跟着业务决策频率走，而不是跟着数据量走。

🏗 系统架构师 ​

这是典型的最大重叠区间问题：任意时刻的最大并发数。我不会去逐秒扫描表，而是把每条记录拆成两个事件点。

算法核心 把 5000W 行拆成 (start_time, +1) 和 (end_time, -1) 共 1 亿个事件，按时间排序后做前缀和，前缀和的历史最大值就是答案，复杂度 O(n log n)。

容量估算（决定单机还是分布式） 1 亿个事件，每条按 (long 时间戳, int ±1) 共 12 字节，原始数据约 1.2GB，排序索引翻倍也在 5GB 以内——64G 内存的机器单机就能做，不需要上大数据平台。这是架构师先算再动手的习惯：很多"大数据问题"算完存储就变成单机问题。

执行方案分档

  • 数据在 MySQL：不要 SELECT * 拖库，按 start/end 两列各建覆盖索引，游标分批拉出（每批 10 万），流式生成事件写外部排序临时文件，或直接 ORDER BY 分段归并。
  • 有数仓/Spark：一条 SQL 即可：
sql
SELECT max(cnt) FROM (
  SELECT sum(delta) OVER (ORDER BY ts) AS cnt
  FROM (
    SELECT start_time AS ts, 1 AS delta FROM t
    UNION ALL
    SELECT end_time AS ts, -1 AS delta FROM t
  ) e
) s;
  • 如果要求实时统计最大在线数，那就是 Flink 开窗 + 状态聚合的流式方案，成本完全不同，我会先和业务确认是离线一次性还是持续输出。

💻 全栈开发专家 ​

这是经典的「区间最大重叠」问题，我实际做过类似的带宽统计。思路是把每条记录拆成两个事件：开始时间 +1、结束时间 -1，然后按时间排序做前缀和，前缀和的最大值就是峰值。

单表 5000W，直接让 MySQL 干

sql
SELECT t, SUM(delta) OVER (ORDER BY t) AS cur, MAX(SUM(delta) OVER (ORDER BY t))
FROM (
  SELECT start_time AS t, 1 AS delta FROM records
  UNION ALL
  SELECT end_time AS t, -1 AS delta FROM records
) e;

窗口函数一亿行排序对 MySQL 压力大，我会加 EXPLAIN 确认是否走临时表落盘，必要时调 tmp_table_size、sort_buffer。

工程上我更推荐两种落法

  • 程序流式处理：SELECT start_time, 1 FROM t UNION ALL SELECT end_time, -1 FROM t ORDER BY 1 用游标流式读（fetchSize=Integer.MIN_VALUE），Java 里单变量累加求峰值，内存 O(1)，只是排序仍压在 DB。
  • 外部排序：把时间事件导出成文件，分块排序后多路归并（小顶堆），完全不碰生产库，适合从库资源紧张时。

常见坑

  • 开始/结束时间相同的点，-1 要排在 +1 前面还是后面要先和业务对齐（闭区间还是半开区间），不然峰值差 1。
  • 时间精度不齐（秒 vs 毫秒）要先归一化。
  • 如果只要峰值不要求时刻，还可以按小时/分钟聚合成桶，用小表统计，牺牲一点精度换速度。

这个题本质考的是扫描线思想 + 大数据量下「计算下推还是拉出来算」的取舍。