哈希算法题目：设计一个基于哈希的分布式计数器系统（支持高并发和容错） 题目描述 设计一个分布式计数器系统，要求支持以下操作： increment(key, value) ：对指定 key 的计数器增加 value （ value 可为正或负）。 get(key) ：获取 key 的当前计数值。 系统需支持高并发操作，并保证在部分节点故障时数据不丢失。 解题步骤 步骤 1：分析核心挑战 高并发 ：多个客户端可能同时修改同一 key ，需保证原子性。 容错性 ：单点故障时数据不应丢失。 一致性 ：不同客户端读取同一 key 时应看到最新值（最终一致性或强一致性）。 步骤 2：选择哈希分片策略 使用 一致性哈希 将 key 分配到多个节点，避免节点增减时数据大规模迁移。 每个 key 根据哈希值（如 hash(key) % N ）映射到特定节点，同时为每个 key 创建多个副本（例如 3 副本）存储在不同节点，防止单点故障。 示例 ： 节点列表： [Node A, Node B, Node C] key="user_123" → 哈希值 h1 → 映射到 Node A ，副本存储在 Node B 和 Node C 。 步骤 3：设计增量操作（increment）的原子性 每个节点的计数器使用 原子操作 （如 CAS）或 分布式锁 （如 Redis 的原子命令）保证并发安全。 优化 ：将增量操作日志先写入 Write-Ahead Log（WAL），再更新内存计数器，确保崩溃后可恢复。 操作流程 ： 客户端发送 increment("user_123", 5) 。 根据一致性哈希找到主节点 Node A 和副本节点 Node B 、 Node C 。 主节点 Node A 执行： 写入 WAL： {key: "user_123", op: +5, timestamp: T1} 更新内存计数器： count = count + 5 主节点异步将操作同步到副本节点（若需强一致性，则同步阻塞等待副本确认）。 步骤 4：处理节点故障 副本机制 ：若主节点失效，系统自动将请求切换到副本节点（如 Node B ）。 数据恢复 ：新主节点上线后，通过 WAL 或副本同步数据。 冲突解决 ：若多个副本数据不一致，使用时间戳或版本号合并操作（如最后写入获胜）。 步骤 5：实现读取操作（get） 客户端向主节点或任意副本发送 get("user_123") 。 若需强一致性，只从主节点读取；若允许最终一致性，可从副本读取（可能返回旧值）。 步骤 6：优化性能 批处理 ：将短时间内的多个增量合并为一个操作，减少网络开销。 缓存热点 key ：对频繁访问的计数器使用本地缓存，定期同步到主节点。 总结 通过 一致性哈希分片 、 多副本冗余 、 WAL 日志 和 原子操作 ，实现了高并发、容错的分布式计数器。此设计平衡了一致性与性能，适用于电商库存计数、社交媒体点赞等场景。