基于哈希的分布式实时热点检测系统（支持滑动窗口和Top K热点追踪）

题目描述

设计一个分布式实时热点检测系统，能够持续接收来自多个数据源的事件流（例如用户点击、搜索关键词、商品访问等），并实时统计在最近一段时间内（滑动窗口）出现频率最高的前K个元素（热点）。
系统需要满足以下要求：

1. 实时性：能够低延迟地处理高频率输入的事件流。
2. 滑动窗口：只统计最近固定时间长度内的事件（例如最近5分钟）。
3. Top K查询：能够快速返回当前窗口内频率最高的K个元素及其频次。
4. 分布式扩展：支持横向扩展以应对海量数据和高并发请求。

解题思路

1. 核心挑战

   • 事件流是连续的，且时间窗口不断滑动，需要高效地淘汰过期事件。
   • 频率统计需要支持快速更新和查询，同时维护Top K的顺序。
   • 分布式场景下，数据分片和聚合需要保证性能与一致性。

2. 设计思路

   • 使用滑动窗口哈希表记录每个元素在窗口内的频次。
   • 结合最小堆或计数排序+哈希来维护Top K。
   • 分布式环境下采用分片+聚合策略，每个分片独立处理部分事件，定期合并结果。

步骤详解

步骤1：数据结构设计（单机版）

1. 滑动窗口表示
   将窗口划分为多个时间桶（如每秒一个桶），每个桶存储该时间段内事件的频次哈希表。

   • 示例：窗口长度 = 5分钟，桶粒度 = 1秒 → 300个桶。
   • 每个桶的结构：{ 元素: 频次 }。

2. 全局频率哈希表
   维护窗口内所有元素的累计频次，通过累加有效桶中的数据得到。

   • 结构：global_count[element] = total_frequency_in_window。

3. Top K 维护
   使用最小堆（大小为K）存储当前频率最高的K个元素，键为频次。

   • 每当元素的频次更新时，尝试更新堆：
     • 如果元素已在堆中，更新其频次并调整堆。
     • 否则，如果频次 > 堆顶元素频次，替换堆顶并调整。

4. 过期数据处理

   • 维护一个时间戳队列，记录每个事件到达的时间。
   • 定期检查队列头部事件是否超出窗口，如果是：
     • 从对应桶的哈希表中减少该事件的计数。
     • 更新全局哈希表（减去过期计数）。
     • 如果该事件在堆中，需要重新计算Top K（可懒惰更新）。

步骤2：单机版流程示例

假设窗口=5分钟，K=3，事件流为：
(t=0, "A"), (t=1, "B"), (t=2, "A"), (t=3, "C"), (t=4, "B"), (t=5, "A")

1. 初始化：桶数组大小=300（每桶1秒），当前时间指针指向最新桶。
2. 插入事件"A"（t=0）：
   • 桶0的哈希表：{"A":1}
   • 全局哈希表：{"A":1}
   • 最小堆：[("A",1)]
3. 插入事件"B"（t=1）：
   • 桶1：{"B":1}
   • 全局：{"A":1, "B":1}
   • 堆：[("A",1), ("B",1)]
4. 插入事件"A"（t=2）：
   • 桶2：{"A":1}
   • 全局：{"A":2, "B":1}
   • 堆更新为：[("A",2), ("B",1)]
5. 当t=301秒时（窗口滑动）：
   • 桶0过期，移除{"A":1}，全局中"A"减1 → {"A":1, "B":1}
   • 重新计算Top K：堆调整为[("A",1), ("B",1)]

步骤3：分布式扩展

1. 数据分片

   • 使用一致性哈希将事件按元素ID哈希值分配到不同节点。
   • 每个节点独立维护自己的滑动窗口和Top K。

2. 定期聚合

   • 每个节点定期（如每秒）将本地Top K结果（元素+频次）发送到聚合器。
   • 聚合器合并所有节点的Top K列表，重新计算全局Top K。
   • 优化：节点可以只发送频次超过阈值的元素，减少网络开销。

3. 容错与一致性

   • 每个节点采用WAL（Write-Ahead Logging）持久化事件流，故障恢复时重放日志。
   • 聚合结果可以缓存在Redis等内存数据库中，供客户端查询。

步骤4：系统架构图

事件流 → 负载均衡器 → 分片节点1 → 滑动窗口哈希表 + Top K堆
                     → 分片节点2 → 滑动窗口哈希表 + Top K堆
                     → 分片节点N → 滑动窗口哈希表 + Top K堆
                          ↓
                    定期聚合器 → 全局Top K计算 → 结果缓存 → 查询接口

总结

• 核心：滑动窗口哈希表 + 最小堆维护Top K。
• 分布式关键：分片统计 + 定期聚合，平衡实时性与一致性。
• 优化方向：
  • 使用跳表或分层计数代替最小堆，加速频次更新。
  • 采用近似算法（如Count-Min Sketch）节省内存，但会损失精度。
  • 窗口滑动时批量淘汰过期桶，减少计算开销。