设计一个基于哈希的分布式实时聊天系统（支持消息排序和去重）

题目描述：
设计一个分布式实时聊天系统，需要支持以下功能：

1. 用户发送消息到聊天室
2. 按时间顺序显示消息
3. 防止重复消息（消息去重）
4. 支持高并发访问
5. 系统需要具备可扩展性

解题过程：

第一步：分析系统需求

• 消息需要全局有序，但分布式环境下时间同步是个挑战
• 需要防止用户重复发送相同消息（网络重传或恶意行为）
• 系统要支持大量并发用户和消息
• 数据需要分布式存储

第二步：设计消息ID生成方案
使用雪花算法变种生成唯一消息ID：

• 64位长整型：时间戳(41位) + 机器ID(10位) + 序列号(12位) + 随机盐(1位)
• 时间戳保证基本时序，序列号解决同一毫秒内的排序
• 随机盐位用于哈希分桶，避免热点问题

第三步：消息去重设计
使用布隆过滤器 + Redis集合的二级去重：

class MessageDeduplicator:
    def __init__(self):
        self.bloom_filter = BloomFilter(capacity=1000000, error_rate=0.01)
        self.redis_client = RedisCluster()
        self.local_cache = LRUCache(10000)
    
    def is_duplicate(self, message_hash):
        # 第一级：本地缓存快速判断
        if message_hash in self.local_cache:
            return True
            
        # 第二级：布隆过滤器判断（可能有假阳性）
        if not self.bloom_filter.check(message_hash):
            self.bloom_filter.add(message_hash)
            return False
            
        # 第三级：Redis精确判断
        if self.redis_client.sadd("message_set", message_hash):
            self.local_cache.set(message_hash, True)
            return False
        return True

第四步：消息存储架构
采用分片存储策略：

class MessageStorage:
    def __init__(self, shard_count=10):
        self.shards = [MessageShard(i) for i in range(shard_count)]
        
    def get_shard(self, message_id):
        # 基于消息ID哈希分片
        hash_value = hash(message_id) 
        return self.shards[hash_value % len(self.shards)]
    
    def store_message(self, message):
        shard = self.get_shard(message.id)
        return shard.store(message)

第五步：消息排序实现
使用跳表(SkipList)维护消息顺序：

class MessageTimeline:
    def __init__(self):
        self.skip_list = SkipList()
        self.message_map = {}  # 消息ID到消息的映射
        
    def add_message(self, message):
        if message.id in self.message_map:
            return False  # 去重
            
        self.skip_list.insert(message.id, message.timestamp)
        self.message_map[message.id] = message
        return True
        
    def get_messages(self, start_time, end_time, limit=100):
        # 使用跳表快速定位时间范围内的消息
        message_ids = self.skip_list.range_query(start_time, end_time, limit)
        return [self.message_map[msg_id] for msg_id in message_ids]

第六步：分布式会话管理
使用一致性哈希管理用户连接：

class SessionManager:
    def __init__(self, node_count=5):
        self.consistent_hash = ConsistentHash()
        self.nodes = [SessionNode(i) for i in range(node_count)]
        
    def route_message(self, user_id, message):
        node_index = self.consistent_hash.get_node(user_id)
        return self.nodes[node_index].handle_message(user_id, message)

第七步：完整系统整合
将各个组件整合：

1. 客户端发送消息时生成唯一哈希（内容+时间戳+用户ID）
2. 通过去重器检查是否重复
3. 分配全局唯一消息ID
4. 存储到对应分片
5. 更新时间线索引
6. 广播给在线用户

这个设计通过多级哈希结构实现了高效的消息去重、分片存储和时间排序，能够支持大规模的实时聊天场景。