实现一个基于哈希的分布式实时排行榜系统（支持分数更新和Top K查询）

题目描述
设计一个分布式实时排行榜系统，支持以下操作：

1. add_score(user_id, score)：为用户添加分数（可正可负，支持多次累加）
2. get_top_k(k)：返回当前分数最高的K个用户（分数相同时按最新更新排序）
3. 系统需支持高并发读写和水平扩展

关键难点

1. 分数频繁更新时如何高效维护全局排名
2. 分布式环境下如何保证数据一致性
3. Top K查询需要低延迟响应

解题步骤

第一步：设计数据分布策略

1. 使用一致性哈希将用户数据分散到多个节点
   • 将用户ID作为哈希键，映射到虚拟环上的节点
   • 每个节点负责环上连续的一段哈希区间
2. 数据分片规则：
   • 每个用户的数据（包括当前分数、最后更新时间）存储在其对应的节点上
   • 例如：user_id=1001 通过哈希函数得到 hash(1001)=0x8A3F，定位到节点N3

第二步：设计分数存储结构
每个节点内部维护两个数据结构：

1. 哈希表（快速更新）：

   user_map = {  
       user_id: {  
           'score': 当前总分,  
           'timestamp': 最后更新时间戳  
       }  
   }  
   

2. 平衡二叉树（快速查询Top K）：
   • 使用红黑树或跳表存储（分数, 时间戳, user_id）元组
   • 排序规则：先按分数降序，分数相同按时间戳降序（最新更新排前面）
   • 例如：(95, 1645600000, "user123") 比 (95, 1645590000, "user456") 排名更高

第三步：实现分数更新逻辑

1. 客户端调用 add_score(user_id, delta)：
   • 根据 user_id 哈希定位到对应节点
   • 节点执行原子操作：

     old_data = user_map.get(user_id, {'score':0, 'timestamp':0})  
     new_score = old_data['score'] + delta  
     new_timestamp = current_time()  
     
     # 更新哈希表  
     user_map[user_id] = {  
         'score': new_score,  
         'timestamp': new_timestamp  
     }  
     
     # 更新平衡二叉树：先删除旧记录，再插入新记录  
     tree.remove((old_data['score'], old_data['timestamp'], user_id))  
     tree.insert((new_score, new_timestamp, user_id))  
     

第四步：实现分布式Top K查询

1. 客户端调用 get_top_k(k)：
   • 向所有节点广播查询请求
   • 每个节点返回本地平衡二叉树中的前K个记录
   • 聚合节点使用胜者树（Tournament Tree）合并结果：
     • 初始状态：每个节点的Top 1记录进入胜者树
     • 每次取出胜者（当前最大分数记录），再从该节点补充下一个记录
     • 重复直到取满K个记录或数据耗尽
   • 合并示例：

     节点1返回: [(100, t1, u1), (90, t3, u3)]  
     节点2返回: [(95, t2, u2), (85, t4, u4)]  
     合并过程：  
       第一轮：比较(100,u1)和(95,u2) → 选择u1  
       第二轮：从节点1取(90,u3)，比较(90,u3)和(95,u2) → 选择u2  
       第三轮：从节点2取(85,u4)，比较(90,u3)和(85,u4) → 选择u3  
     最终Top3: [u1, u2, u3]  
     

第五步：优化性能与容错

1. 写优化：
   • 批量更新：累计一段时间内的分数变化再写入二叉树
   • 异步复制：主节点更新后异步同步到副本节点
2. 读优化：
   • 缓存Top K结果（设置短时间过期）
   • 使用布隆过滤器快速跳过低分节点
3. 容错机制：
   • 为每个分片设置副本节点
   • 通过版本号解决更新冲突（向量时钟算法）

总结
该设计通过组合一致性哈希、平衡二叉树和胜者树，实现了：

• 高效更新：哈希表O(1)访问 + 二叉树O(log n)排序维护
• 快速查询：分布式合并排序将复杂度控制在O(k log m)（m为节点数）
• 可扩展性：增加节点时只需重新分配部分数据