哈希算法题目：设计一个基于哈希的分布式事件去重系统（支持时间窗口和滑动过期） 题目描述 设计一个分布式事件去重系统，用于处理高并发事件流（如用户点击、日志记录等）。要求： 去重功能 ：在指定时间窗口内（如5分钟），重复事件仅处理一次。 分布式支持 ：系统需在多台机器上运行，事件可能被任意节点接收。 滑动过期 ：事件去重的时间窗口需支持滑动过期（例如，若时间窗口为5分钟，则事件需在最后一次出现后保留5分钟再去重）。 高可用性 ：避免单点故障，保证数据一致性。 解题步骤 步骤1：明确去重逻辑与数据特征 事件唯一标识 ：每个事件需有唯一ID（如用户ID+动作类型+时间戳哈希）。 时间窗口 ：若时间窗口为5分钟，需记录事件首次出现的时间，并在此后的5分钟内忽略重复事件。 滑动过期 ：需动态更新事件的过期时间（如每次收到重复事件时重置过期时间）。 步骤2：选择哈希数据结构 本地哈希表+全局存储 ： 每个节点维护本地哈希表（ HashMap<EventId, Timestamp> ），记录事件最近一次到达时间。 全局共享存储（如Redis或分布式数据库）用于跨节点同步去重状态。 哈希函数 ：对事件ID计算哈希值，确定数据在分布式存储中的分片位置。 步骤3：设计分布式架构 事件接收节点 ： 接收事件后，先查询本地缓存（减少全局存储压力）。 若本地缓存命中且未过期，直接丢弃事件；否则查询全局存储。 全局存储设计 ： 使用 分布式哈希表（DHT） 或 键值数据库 （如Redis），键为事件ID的哈希值，值为过期时间。 通过一致性哈希分配数据分片，保证负载均衡和容错。 步骤4：实现滑动过期机制 全局存储操作 ： 写入 ：若事件不存在或已过期，则写入当前时间+时间窗口作为新过期时间。 更新 ：若事件未过期，更新过期时间为当前时间+时间窗口（滑动过期）。 懒惰清理 ：在查询时检查过期时间，自动清理过期事件，减少后台扫描开销。 步骤5：处理并发与一致性 原子操作 ：使用Redis的 SETNX （Set if Not Exist）或数据库的乐观锁，确保并发下仅一个节点能成功写入去重记录。 最终一致性 ：若本地缓存与全局存储短暂不一致，可接受少量重复（根据业务权衡）。 步骤6：优化性能 布隆过滤器预判 ：在查询全局存储前，先用布隆过滤器快速判断事件是否可能已存在，减少无效查询。 批量处理 ：对高吞吐场景，批量合并事件去重请求，降低网络开销。 举例说明 假设时间窗口为5分钟，事件ID为 user123_click ： 事件首次到达节点A： 本地缓存未命中，查询全局存储（Redis）未找到记录。 写入Redis： Key=hash(user123_click), Value=当前时间+5分钟 。 处理事件并更新本地缓存。 3分钟后同一事件到达节点B： 本地缓存未命中，查询Redis发现记录未过期。 更新Redis过期时间为 当前时间+5分钟 （滑动过期），丢弃事件。 若事件在8分钟后再次到达，Redis记录已过期，重新处理并更新记录。 关键挑战与解决方案 内存压力 ：通过TTL自动清理过期键，或使用时间窗口分片（如按小时划分存储）。 网络延迟 ：通过本地缓存降低全局存储访问频率，容忍毫秒级延迟。 分布式一致性 ：采用轻量级共识协议（如Raft）管理全局存储的元数据。 通过以上步骤，系统可在分布式环境下高效去重，并支持滑动过期机制。