100亿订单号如何去重
100亿订单号如何去重
面试官您好，关于 100 亿订单号去重这个问题，我会从需求分析→方案演进→最优解落地→核心代码→技术难点五个层面来回答，同时兼顾性能、成本和可靠性 👇
📌 第一步：先明确核心约束
- 数据量：100 亿条订单号（假设每条 64 位 = 8 字节，纯数据量≈80GB）
- 核心需求：快速判断一个订单号是否已存在（存在即重复）
- 性能要求：单次查询延迟 < 10ms，支持 10 万 + QPS 高并发写入查询
- 业务约束：订单号一旦生成永不修改，最终一致性要求高，绝对不允许漏判重复
🚀 第二步：方案演进（从简单到复杂）
| 方案 | 核心原理 | 100 亿数据内存占用 | 查询性能 | 适用场景 | 致命缺点 |
|---|---|---|---|---|---|
| HashSet | Java 原生哈希表 | >800GB（对象头 + 指针开销） | O(1) | 百万级以下 | 内存爆炸💥 |
| MySQL 唯一索引 | 数据库唯一约束 | 磁盘存储 | 100ms+ | 千万级以下 | 磁盘 IO 瓶颈，无法支撑高并发 |
| Redis Set | 内存哈希集合 | ≈160GB（Redis 编码优化） | O(1) | 亿级以下 | 成本高，160G 云 Redis≈2 万 / 月 |
| 布隆过滤器 | 概率型数据结构 | ≈11.5GB（误判率 0.01%） | O (k)（k 为哈希函数个数） | 百亿级及以上 | 存在极小误判率 |
💎 第三步：最终最优解（布隆过滤器 + 兜底校验）
核心架构图
关键参数计算 🧮
对于 100 亿数据，误判率 p=0.01%：
- 所需位数组大小：
m ≈ -n * ln(p) / (ln2)^2 ≈ 100亿 * 9.21 ≈ 921亿位 ≈ 11.5GB - 最优哈希函数个数：
k ≈ m/n * ln2 ≈ 7个
🔥 第四步：核心代码与技术亮点实现
1. RedisBloom 分布式布隆过滤器（生产级首选）
技术亮点：基于 Redis 官方模块，支持集群部署、持久化、动态扩容，避免 Guava 本地布隆过滤器的分布式一致性问题
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;
import javax.annotation.Resource;
@Component
public class RedisBloomOrderDeduplicator {
private static final String BLOOM_FILTER_KEY = "order:id:bloom";
private static final long EXPECTED_INSERTIONS = 10_000_000_000L;
private static final double FPP = 0.0001; // 0.01%误判率
@Resource
private RedissonClient redissonClient;
@Resource
private OrderRepository orderRepository;
private RBloomFilter<Long> bloomFilter;
@PostConstruct
public void init() {
// 获取或创建布隆过滤器，仅第一次创建时生效
bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_KEY);
bloomFilter.tryInit(EXPECTED_INSERTIONS, FPP);
}
/**
* 去重判断核心方法
* @return true: 重复, false: 不重复
*/
public boolean isDuplicate(Long orderId) {
// 1. 先查布隆过滤器（纯内存操作，微秒级）
if (!bloomFilter.contains(orderId)) {
// 2. 布隆过滤器说不存在，一定不存在，直接写入
bloomFilter.add(orderId);
return false;
}
// 3. 布隆过滤器说存在，才查数据库兜底（只有0.01%的请求会走到这一步）
return orderRepository.existsById(orderId);
}
/**
* 批量添加历史订单号（冷启动用）
* 技术亮点：使用Redis管道批量操作，性能提升100倍以上
*/
public void batchAdd(List<Long> orderIds) {
bloomFilter.add(orderIds); // Redisson内部已封装管道批量操作
}
}2. 分片布隆过滤器优化（解决单实例大内存问题）
技术亮点：按订单号前缀分片，每个分片一个独立布隆过滤器，将 11.5GB 大内存拆分为 10 个 1.15GB 小实例，解决 Redis 大 key 问题和单实例内存瓶颈
@Component
public class ShardedBloomOrderDeduplicator {
private static final int SHARD_COUNT = 10; // 分为10个分片
private final List<RBloomFilter<Long>> shards = new ArrayList<>(SHARD_COUNT);
@PostConstruct
public void init() {
for (int i = 0; i < SHARD_COUNT; i++) {
RBloomFilter<Long> shard = redissonClient.getBloomFilter("order:id:bloom:shard:" + i);
shard.tryInit(EXPECTED_INSERTIONS / SHARD_COUNT, FPP);
shards.add(shard);
}
}
private RBloomFilter<Long> getShard(Long orderId) {
// 按订单号最后一位分片，保证均匀分布
int shardIndex = (int) (orderId % SHARD_COUNT);
return shards.get(shardIndex);
}
public boolean isDuplicate(Long orderId) {
RBloomFilter<Long> shard = getShard(orderId);
if (!shard.contains(orderId)) {
shard.add(orderId);
return false;
}
return orderRepository.existsById(orderId);
}
}3. 历史数据冷启动批量加载优化
技术亮点：多线程分页查询 + Redis 管道批量写入，将 100 亿数据加载时间从数天缩短至数小时
@Component
public class BloomFilterInitializer {
private static final int PAGE_SIZE = 10000; // 每次查询1万条
private static final int THREAD_COUNT = 20; // 20个线程并行加载
@Resource
private ShardedBloomOrderDeduplicator deduplicator;
@Resource
private OrderRepository orderRepository;
@Resource
private ThreadPoolTaskExecutor taskExecutor;
public void initAllHistoryOrders() {
// 1. 获取订单号最小值和最大值，避免全表扫描
Long minId = orderRepository.findMinId();
Long maxId = orderRepository.findMaxId();
long totalPages = (maxId - minId) / PAGE_SIZE + 1;
// 2. 多线程并行加载
CountDownLatch latch = new CountDownLatch((int) totalPages);
for (long page = 0; page < totalPages; page++) {
long startId = minId + page * PAGE_SIZE;
long endId = Math.min(startId + PAGE_SIZE - 1, maxId);
taskExecutor.execute(() -> {
try {
List<Long> orderIds = orderRepository.findIdsBetween(startId, endId);
if (!orderIds.isEmpty()) {
deduplicator.batchAdd(orderIds);
}
} finally {
latch.countDown();
}
});
}
// 3. 等待所有线程完成
latch.await();
log.info("布隆过滤器历史数据加载完成，共加载{}条订单", maxId - minId + 1);
}
}⚠️ 第五步：核心技术难点与解决方案
| 技术难点 | 产生影响 | 解决方案 | 技术亮点 |
|---|---|---|---|
| 历史数据冷启动慢 | 系统启动时间长达数天，无法快速上线 | 1. 按 ID 范围分页查询 2. 多线程并行加载 3. Redis 管道批量写入 4. 提前预生成布隆过滤器文件 | 加载速度提升 100 倍以上，100 亿数据可在 4 小时内完成加载 |
| 布隆过滤器扩容难 | 容量满后误判率急剧上升，无法继续写入 | 1. 双写切换扩容：创建新的更大布隆过滤器，同时写入新旧两个 2. 分片扩容：新增分片节点，重新分配哈希槽 3. 滚动扩容：逐个分片迁移数据，不影响业务 | 全程无停机，业务无感知，扩容期间性能无明显下降 |
| 分布式一致性问题 | 多实例本地布隆过滤器数据不一致，导致漏判 | 1. 统一使用 RedisBloom 分布式布隆过滤器 2. 采用最终一致性模型，数据库唯一索引兜底 3. 定期全量校验布隆过滤器与数据库数据 | 保证绝对不出现漏判重复，最终一致性 |
| 误判率控制 | 误判率过高会导致大量请求穿透到数据库 | 1. 精确计算布隆过滤器参数 2. 监控实际误判率，超过阈值及时扩容 3. 采用分层布隆过滤器：热数据用低误判率，冷数据用高误判率 | 实际误判率稳定在 0.01% 以下，数据库压力降低 99.99% |
| Redis 大 key 问题 | 11.5GB 大 key 导致 Redis 集群迁移、备份失败 | 1. 按订单号前缀分片，拆分为多个小布隆过滤器 2. 每个分片大小控制在 2GB 以内 3. 冷热分离：热数据放内存，冷数据放磁盘 | 解决 Redis 大 key 所有问题，集群稳定性大幅提升 |
| 高并发下的性能问题 | 高并发写入时布隆过滤器成为瓶颈 | 1. 本地缓存热点布隆过滤器分片 2. 读写分离：读本地缓存，写 Redis 3. 批量异步写入 Redis | 支持 100 万 + QPS，延迟稳定在 1ms 以内 |
⚡ 第六步：生产环境进阶优化
- 冷热分离：近 3 个月热数据放本地 Guava 布隆过滤器，冷数据放 Redis 布隆过滤器
- 监控告警：监控布隆过滤器的填充率、误判率、查询延迟和 Redis 内存使用率
- 容灾备份：定期备份 Redis 布隆过滤器数据，故障时可快速恢复
- 压测验证：上线前进行全链路压测，验证 100 亿数据量下的性能和稳定性
🎯 面试官追问回答要点
问：布隆过滤器误判了怎么办？
答：不会影响业务正确性，因为还有数据库唯一索引兜底。误判只会导致极少量请求多查一次数据库，0.01% 的误判率对系统性能几乎无影响。
问：订单号达到 100 亿后布隆过滤器满了怎么办？
答：提前规划扩容，当填充率达到 70% 时，启动双写切换扩容流程，创建一个 2 倍容量的新布隆过滤器，同时写入新旧两个，待新过滤器数据同步完成后，切换读流量到新过滤器。
问：为什么不用 Roaring Bitmap？
答：Roaring Bitmap 适合连续整数去重，而订单号通常是雪花算法生成的分布式 ID，分布稀疏。100 亿稀疏 ID 的 Roaring Bitmap 内存占用会达到 50GB 以上，远大于布隆过滤器的 11.5GB。
真实面试模拟
真实面试模拟
面试官 😊：
同学你好，咱们放松聊。先来个场景设计题：有100亿个订单号，需要做去重，你会怎么设计？ 可以把思路逐步说清楚。
候选人 🤔：
好的面试官。我先确认一下前提：订单号通常是 Long 型，8字节，100亿条原始数据大约 80GB，单机内存肯定放不下，所以直接用 HashSet 这条路直接堵死了。
我能先问几个问题帮我细化场景吗？
面试官 👍：
当然，你问。
候选人 📋：
- 第一，订单号是什么生成规则？是连续的纯数字，还是像雪花算法那种随机 Long？
- 第二，业务允许极小概率的误判吗，还是必须 100% 精确？
- 第三，是离线的一次性去重（比如 T+1 报表），还是实时流需要立刻去重？
面试官 🧑💻：
好，假设订单号是雪花算法生成的 Long，分布很随机；精确性要求是必须精准，不能有漏网；然后咱们分别聊聊 离线批量 和 实时流 两种场景。
候选人 ✨：
明白了。针对随机 Long 且必须精确，我脑中立刻拆成两套打法。我先说 离线批量去重。
🔹 场景一：离线批量精确去重
候选人 💡：
核心思想是“分而治之”。单机装不下 80GB，那就把相同订单号哈希到同一台机器或同一个文件，再局部去重。
具体步骤：
- 哈希分片：对每个订单号
hash(id) % N，均匀写入 N 个小文件（比如 N=1000）。同一个订单号必然落在同一个文件，且每个文件大约80GB/1000 ≈ 80MB，完全能读进内存。 - 单文件精确去重：依次把每个文件加载到内存
HashSet去重，或直接排序去重，得到纯净结果。 - 汇总输出：每个文件去重后直接输出，因为是分片隔离的，不存在跨文件重复。
面试官 👏：
清晰。那如果变成 实时流 呢？每秒几十万订单进来，还要精确去重，你怎么做？
🔹 场景二：实时流精确去重
候选人 ⚡：
实时就必须用 外部存储 + 快速判断 的架构了。我会用 布隆过滤器 + 分布式KV存储 的组合拳，核心是“布隆做高速闸门，KV 做精确审判”。
面试官 🧐：
展开说说？
候选人 🔧：
- 布隆过滤器 先驻内存，用极小内存判断“绝对没出现过”。如果布隆说“没有”，那一定没有，直接放行，然后写入布隆和下游。
- 如果布隆说“可能存在”，这里就存在误判，所以必须去 HBase / RocksDB 这种持久化KV里查一次。确实存在就丢弃，不存在就插入，完成精确去重。
相当于布隆拦截了99.9%的查询，只有极少数会穿透到磁盘。
实时订单号 ──> [布隆过滤器] ──(可能存在)──> [HBase/RocksDB精确查重]
│ 绝对没有 │
↓ ↓
直接放行+写入布隆 存在→丢弃
不存在→插入并放行面试官 📊：
你这布隆过滤器内存占用和误判率怎么权衡？100亿数据量下具体要多大？
候选人 📏：
如果允许误判率 0.01%，公式是 -n*ln(p) / (ln2)^2。100亿，p=0.0001，算出来大约需要 18GB 内存来存布隆的位数组。这个大小在一台高配机器上完全可以接受，甚至能用 Redis 集群的 Bitmap 分摊。误判率带来的穿透查询占比极小，对 HBase 压力可忽略。
面试官 💬：
那如果我不想依赖外部KV，或者要求极低延迟，有没有更“内存化”的精确方案？
候选人 🔍：
那就看订单号有没有局部连续性。如果雪花算法的 Long 有一部分是时间戳，可以考虑 RoaringBitmap 这种压缩位图，它能压缩连续区间，内存占用远低于传统位图。但若完全随机，RoaringBitmap 压缩收益有限，还是得靠“布隆+KV”或分片状态存储。
像 Flink 的 KeyedState 结合 RocksDB 后端，每个订单号状态精确保留，同时利用 TTL 自动过期旧数据，也是不错的实时精确方案。
📊 最后总结对比
候选人 🙌：
我把几种方案整理成一张表：
| 方案 | 精确度 | 内存/资源 | 延迟 | 适用场景 |
|---|---|---|---|---|
| 哈希分片+文件排序去重 | 100% | 分片文件，内存占用低 | 高（分钟级） | 离线 T+1 批处理 |
| 布隆过滤器 + HBase 兜底 | 100%（有布隆误判则穿透） | 布隆 ≈18GB，+HBase 集群 | 低（毫秒级） | 实时高吞吐 |
| Flink State(RocksDB) | 100% | 分布式状态后端 | 低 | 有状态流处理 |
| 单机 Bitmap | 100% | 连续ID ~2.5GB | 极低 | 稠密订单号 |
面试官 💻：
方案讲得不错，那能不能现场写一段核心代码？比如布隆过滤器 + Redis 的判重逻辑，或者分片去重的关键片段。用你擅长的语言就行。
候选人 ⌨️：
好的，我用 Java 写一下布隆过滤器预判 + Redis 精确去重的核心逻辑，并加上 Lua 脚本保证原子性，这是有技术亮点的地方。
// 布隆过滤器（基于Guava）
BloomFilter<String> bloomFilter = BloomFilter.create(
Funnels.stringFunnel(Charset.forName("UTF-8")),
10_000_000_000L, // 预期插入量：100亿
0.0001 // 误判率 0.01%
);
// Redis Lua 脚本：原子性判断并插入
String luaScript =
"local exists = redis.call('GET', KEYS[1]) " +
"if exists then " +
" return 0 " + // 已存在，重复
"else " +
" redis.call('SET', KEYS[1], '1', 'EX', ARGV[1]) " +
" return 1 " + // 不存在，插入成功
"end";
// 去重主流程
public boolean isDuplicate(String orderId) {
// 第一步：布隆过滤器快速拦截
if (!bloomFilter.mightContain(orderId)) {
// 绝对不存在，直接插入布隆并放行
bloomFilter.put(orderId);
return false;
}
// 第二步：布隆返回“可能存在”，穿透到Redis精确查询
try (Jedis jedis = jedisPool.getResource()) {
// 用 Lua 保证 GET + SET 原子，避免并发重复插入
long result = (long) jedis.eval(luaScript,
Collections.singletonList(orderId),
Collections.singletonList("604800") // TTL 7天
);
if (result == 1) {
// 确实不重复，同步更新布隆过滤器
bloomFilter.put(orderId);
return false;
}
return true; // 重复
}
}技术亮点说明 🔍：
- 布隆 + Redis 双层架构：布隆拦住 99.99% 请求，Redis 扛住最后的精确校验。
- Lua 原子化：
GET + SET在 Redis 单线程中一气呵成，避免高并发下两个请求同时判断为“不存在”而都插入。 - TTL 自动过期：订单去重通常有时效（如7天），Redis 键自动过期，控制内存。
面试官 🧐：
那如果是离线分片去重，用 MapReduce 或 Spark 实现，核心代码怎么写？
候选人 ⚡：
我用 Spark 的 shuffle 去重，它天然就是 hash 分片 + 局部去重的理想模型，一行核心代码就能搞定：
// Spark 精确去重：利用 distinct 算子，底层基于 reduceByKey 做 shuffle
Dataset<String> orders = spark.read().textFile("hdfs://input/orders");
Dataset<String> uniqueOrders = orders.distinct();
uniqueOrders.write().text("hdfs://output/unique_orders");原理：distinct() 会触发 shuffle，以订单号作为 key 进行 reduceByKey，相同订单号必然进入同一个 partition，然后每个 partition 内部直接去重。这就是我们之前说的“分片 + 局部去重”的分布式实现，代码极简但背后是成熟的 shuffle 引擎。
如果要更精细控制，可以手动 hash 分区：
Dataset<String> unique = orders
.map((MapFunction<String, Tuple2<String, Void>>) s -> new Tuple2<>(s, null),
Encoders.tuple(Encoders.STRING(), Encoders.kryo(Void.class)))
.groupByKey(orders.sparkSession().sparkContext().defaultParallelism()) // hash 分片
.mapGroups((MapGroupsFunction<String, Tuple2<String, Void>, String>) (key, it) -> key,
Encoders.STRING());技术亮点：充分利用 Spark 的分布式 shuffle 能力，无需手动切文件，天然解决数据倾斜时可以通过加盐、二次聚合等优化。
面试官 🤔：
很好。那接下来咱们聊聊技术难点。在这个 100 亿订单去重的实现中，你觉得会遇到哪些棘手问题，又怎么解决？
候选人 📝：
我梳理了四个核心难点及解决方案，看这个表格 👇
| 技术难点 | 问题描述 | 解决方案 |
|---|---|---|
| 数据倾斜 | 离线分片时某些订单号（如热点商户）hash 后集中，导致个别分片过大，任务长尾甚至 OOM | 1. 二次聚合：先加随机前缀打散，局部去重再去前缀； 2. 自定义分区器，按数据量动态调节； 3. 用自适应执行，如 Spark AQE 自动处理倾斜分区 |
| 布隆过滤器不可扩容 | 一旦创建位数组大小固定，数据量超出预期会误判率飙升 | 1. 创建时预估足够容量，留 20%~30% 余量； 2. 多层布隆：历史数据用稳定层，增量用新层，查询时多层判断； 3. 可扩展布隆过滤器（Scalable Bloom Filter）自动追加新布隆 |
| Redis 内存压力与击穿 | 100 亿订单若长期存 Redis，内存爆炸；高并发下热点 key 击穿 | 1. TTL 严格设置（如7天），保证数据过期清理； 2. 热点 key 本地缓存（Caffeine） + 布隆挡大部分； 3. Redis 集群分片，单 key 分散； 4. 持久化兜底：Redis 仅作热数据，全量在 HBase，冷热分离 |
| 状态一致性 | 实时流处理中，Checkpoint 失败或重启可能导致部分订单漏判或重复插入 | 1. Flink 的 两阶段提交 + Checkpoint 保证 exactly-once； 2. 状态后端使用 RocksDB，增量 checkpoint 快速持久化； 3. 幂等设计：即便重放，Lua 原子插入也能保证最终一致 |
面试官 📊：
还有一个实际工程问题：布隆过滤器本身是内存结构，如果服务重启，内存里的布隆数据就丢了，你怎么处理？
候选人 🔄：
确实，这是个常见坑。有几种方案：
- 定期快照持久化：定期把布隆的 BitSet 序列化到本地磁盘或 HDFS，重启时加载。Guava 的布隆支持
writeTo/readFrom。 - Redis 托管布隆：直接用 RedisBloom 模块，布隆数据存在 Redis 里，服务无状态，重启不丢。
- 冷启动预热：从 HBase 等持久化层回放近期（如7天）订单号重建布隆，虽然耗时但保证完全一致。
一般生产环境选 RedisBloom 或 内存 + 定期快照 就够了。
面试官 😄：
非常全面了，从代码到难点都有实战经验的味道。今天就到这里，感谢你的精彩分享！
候选人 🙏：
谢谢面试官，我也从交流中学到很多！