哈希算法题目：设计一个基于哈希的分布式实时监控系统（支持滑动窗口统计和异常检测）

题目描述
设计一个分布式实时监控系统，用于收集来自多个服务器的指标数据（如CPU使用率）。系统需要支持以下功能：

1. 添加指标数据：接收（服务器ID, 指标值, 时间戳）。
2. 滑动窗口统计：查询任意服务器在最近时间窗口（如5分钟）内的指标统计值（如平均值、最大值）。
3. 异常检测：基于滑动窗口内的历史数据，动态检测当前指标是否异常（如超过平均值的2倍标准差）。

要求实现高吞吐量的数据写入和低延迟的查询，使用哈希算法优化数据分片和快速访问。

解题过程

步骤1：系统架构设计

• 使用分布式哈希表（DHT）分片数据：根据服务器ID的哈希值将数据分配到不同节点。
• 每个节点负责存储特定范围内的服务器数据，实现负载均衡。
• 数据模型：每个服务器的指标按时间序列存储，使用滑动窗口链表或环形缓冲区。

关键细节：

• 哈希函数选择：一致性哈希（Consistent Hashing）避免节点增减导致的数据大规模迁移。
• 时间窗口管理：为每个服务器维护一个固定长度的队列，队列长度由窗口大小和数据粒度决定（如每10秒一个数据点，5分钟窗口需30个点）。

步骤2：数据添加逻辑

1. 接收数据（server_id, value, timestamp）。
2. 计算 server_id 的哈希值（如MD5后取模），确定负责的节点。
3. 在该节点的哈希表中，以 server_id 为键，存储一个时间序列队列。
4. 将新数据插入队列尾部，并淘汰早于窗口的数据（如时间戳 < 当前时间 - 5分钟）。

示例代码逻辑：

class MonitorNode:
    def __init__(self, window_size=300):  # 5分钟=300秒
        self.data_map = {}  # server_id -> deque(maxlen=窗口容量)
    
    def add_metric(self, server_id, value, timestamp):
        if server_id not in self.data_map:
            self.data_map[server_id] = deque(maxlen=30)  # 假设每10秒一点，容量30
        # 清理过期数据（可选，deque满时自动淘汰最旧数据）
        self.data_map[server_id].append((timestamp, value))

步骤3：滑动窗口统计实现

• 查询时，根据 server_id 定位到对应节点的队列。
• 遍历队列，筛选出时间窗口内的数据点（timestamp ≥ 当前时间 - 窗口大小）。
• 计算统计值（平均值、最大值等）。

示例代码：

def get_stats(self, server_id, current_time, window=300):
    if server_id not in self.data_map:
        return None
    points = [v for t, v in self.data_map[server_id] 
              if t >= current_time - window]
    if not points:
        return None
    avg = sum(points) / len(points)
    max_val = max(points)
    return {"avg": avg, "max": max_val}

步骤4：异常检测算法

• 基于滑动窗口数据计算均值和标准差。
• 若当前值超过均值 ± k倍标准差（如k=2），标记为异常。
• 动态更新：每次添加新数据时重新计算统计量，避免全量遍历。

优化：维护窗口内数据的累加和、平方和，实现O(1)计算均值和标准差：

# 在添加数据时维护
sum_val = 0
sum_sq = 0
count = 0

# 添加新点v时：
sum_val += v
sum_sq += v * v
count += 1

# 移除旧点v_old时（当队列满自动淘汰）：
sum_val -= v_old
sum_sq -= v_old * v_old
count -= 1

# 计算标准差：
mean = sum_val / count
std = sqrt((sum_sq / count) - mean * mean)

步骤5：分布式扩展与一致性哈希

• 使用一致性哈希环分配节点，减少节点变更时的数据迁移。
• 为每个节点分配虚拟副本，平衡负载。
• 查询时，先哈希 server_id 确定节点，再转发请求。

总结
本题通过哈希分片实现数据分布式存储，结合时间序列队列支持滑动窗口统计。关键点在于：

1. 哈希路由快速定位数据节点。
2. 队列结构自动维护时间窗口。
3. 增量计算优化统计性能。
4. 一致性哈希提升系统可扩展性。