设计一个分布式去重系统，用于处理海量日志数据（如PB级），要求支持高吞吐（每秒处理百万级数据条目）、低延迟（响应时间<100ms），并保证数据一致性。请描述系统架构、核心模块设计及关键技术点（如数据分片、哈希策略、缓存策略等），并说明如何处理数据倾斜问题。
湖北大数据集团算法工程师难度：中等
答案
1) 【一句话结论】
采用“一致性哈希分片+多级预检查（布隆+缓存+时间窗口）+分布式存储版本控制”架构，通过负载均衡、快速预检查降低延迟，结合版本控制保证数据一致性，支持PB级日志高吞吐去重。
2) 【原理/概念讲解】
（老师口吻，技术讲解）
- 数据分片：采用一致性哈希（CH）+虚拟节点，将日志按ID哈希值分配到不同节点，节点故障时数据自动迁移至其他节点（类比“把数据放进不同仓库，每个仓库负责一部分，节点故障时数据自动找新仓库”）。分片数量( S )与节点数( N )匹配（如( S=2N )），避免热点。节点数增加时，动态调整虚拟节点数量，保持负载均衡。
- 布隆过滤器：基于位数组+哈希函数实现概率去重，快速判断数据是否已存在（允许误报，降低后续检查压力）。误报率公式为 ( p = (1 - e^{-k/n})^m )（( k )为哈希函数数，( n )为位数组长度，( m )为元素数）。位数组长度( n )通过公式 ( n = -m \cdot \ln(p) / (\ln2)^2 ) 计算（如要求误报率1%，需根据业务数据量( m )调整参数，工程中通过测试优化( k )和( n )，确保误报率在可接受范围内）。
- 缓存策略：用分布式缓存（如Redis集群）存储已去重数据，结合LRU淘汰策略和TTL（如60秒），避免缓存雪崩。缓存键为日志ID，值可设为空或版本号，减少存储压力。
- 时间窗口：结合滑动时间窗口（如5分钟），限制周期性重复数据。窗口内重复数据会被去重，窗口外新数据重新计算。窗口大小根据日志生成频率（如每5分钟一次周期性事件）调整，避免过小导致正常重复被误判，或过大导致去重失效。
- 数据一致性：通过分布式存储（如HBase）+版本控制（时间戳序列），每个数据条目带版本号（如时间戳+序列号），确保数据不丢失且可追溯。即使节点故障，通过版本控制恢复数据，避免不一致。
3) 【对比与适用场景】
| 策略类型 | 定义 | 特性 | 使用场景 | 注意点 |
|---|---|---|---|---|
| 一致性哈希分片 | 节点故障时数据自动迁移 | 负载均衡，高可用 | 分布式系统，节点动态变化 | 需维护虚拟节点，避免数据倾斜 |
| 布隆过滤器 | 基于位数组的概率去重 | 极快，空间高效，允许误报 | 海量数据初步去重，降低后续压力 | 误报率需控制，误报导致漏检 |
| 缓存去重 | 分布式缓存存储已处理数据 | 响应快，但内存有限 | 低延迟场景，数据量适中 | 需防缓存雪崩，设置TTL/互斥锁 |
| 时间窗口去重 | 结合时间窗口限制重复 | 适用于周期性重复数据 | 日志中周期性事件（如每5分钟一次） | 窗口大小需合理，避免过宽导致去重失效 |
| 版本控制 | 分布式存储的版本号（时间戳） | 确保数据不丢失，可追溯 | 长期数据存储，保证一致性 | 需考虑存储成本，版本号管理 |
4) 【示例】
伪代码处理日志条目：
def process_log_entry(log_entry):
# 1. 数据分片：一致性哈希分配节点
shard_id = hash(log_entry.id) % num_shards
node = get_shard_node(shard_id)
# 2. 布隆过滤器检查（预检查）
bf = BloomFilter(node, log_entry.id)
if bf.contains(): # 误报则继续
return "已去重"
# 3. 缓存检查（分布式Redis）
cache_key = f"cache:{log_entry.id}"
if redis.get(cache_key):
return "已去重"
# 4. 时间窗口检查（滑动窗口，5分钟）
window = SlidingWindow(log_entry.timestamp, 5*60)
if window.contains(log_entry.id):
return "已去重"
# 5. 存储去重（HBase，带版本控制）
store_log_entry(log_entry, version=log_entry.timestamp)
# 6. 更新缓存和布隆过滤器
redis.setex(cache_key, 60, log_entry.id) # TTL 60秒
bf.add(log_entry.id)
return "去重成功"
5) 【面试口播版答案】
（约90秒，自然表达）
“面试官您好，针对海量日志的分布式去重系统，我设计的方案核心是构建一个‘分片+缓存+布隆+时间窗口’的架构，结合分布式存储的版本控制保证一致性。首先，数据分片采用一致性哈希+虚拟节点，将日志按ID哈希分配到不同节点，节点故障时数据自动迁移，实现负载均衡。处理流程中，先通过布隆过滤器快速判断是否已存在（允许误报，降低后续检查压力），接着检查分布式缓存（如Redis）是否命中，再结合滑动时间窗口（5分钟）限制周期性重复。对于确认的新数据，写入分布式存储（如HBase），并更新缓存和布隆过滤器。关键技术点包括：1. 一致性哈希分片确保节点故障时数据自动迁移；2. 布隆+缓存+时间窗口三重预检查，平衡速度与准确率；3. 滑动时间窗口处理周期性重复数据。数据一致性通过分布式存储的版本控制（时间戳序列）保证，即使节点故障也能恢复。处理数据倾斜问题，通过虚拟节点和负载均衡，结合动态扩容（比如监控分片负载率，超过阈值时增加分片数量或调整虚拟节点位置），确保每个分片负载均匀。”
6) 【追问清单】
- 问题1：如何处理数据倾斜？
回答要点：通过虚拟节点和负载均衡，结合动态扩容（如监控分片负载率，超过阈值时增加分片数量或调整虚拟节点位置），确保分片负载均匀。例如，当某个分片负载率超过80%时，自动增加该分片的虚拟节点数量，或重新分配数据。 - 问题2：布隆过滤器误报率如何控制？
回答要点：误报率公式为 ( p = (1 - e^{-k/n})^m )，通过位数组长度( n )和哈希函数数( k )控制。工程中，根据业务数据量( m )（如每秒百万条日志，一天约8.64亿条），计算( n )（如要求误报率1%，则( n \approx 28.5 )亿位，即约3.5亿字节），选择合适的( k )（如3-5个哈希函数），并通过测试调整参数，确保误报率在可接受范围内。 - 问题3：如何保证低延迟（<100ms）？
回答要点：缓存和布隆过滤器位于内存，检查时间极短（毫秒级）；时间窗口检查通过本地计算，避免网络延迟；分片节点本地处理，减少跨节点通信；批量写入分布式存储（如每100条日志批量写入），减少I/O延迟，整体流程在100ms内完成。
7) 【常见坑/雷区】
- 坑1：仅考虑内存缓存而忽略持久化，导致数据丢失，需明确缓存是临时，存储是持久化，通过版本控制保证一致性。
- 坑2：哈希策略导致分片不均（如简单哈希），应采用一致性哈希+虚拟节点，避免热点分片。
- 坑3：时间窗口设置不合理（如窗口过小导致正常重复被误判，或过大导致去重失效），需根据业务周期（如日志生成频率）调整窗口大小。
- 坑4：布隆过滤器误报率过高，未控制位数组长度，导致漏检率增加，应通过数学公式计算位数组长度，确保误报率在可接受范围内（如1%）。
- 坑5：未考虑分布式事务或版本控制，导致节点故障时数据不一致（如丢失或重复），需通过分布式存储的版本控制（时间戳序列）保证数据不丢失且可追溯。