一、技术难点
1.1 数据规模分析
- 原始数据：10亿×8字节 = 8GB
- HashSet去重：至少16GB内存（Java对象开销）
- 理想方案：<1GB内存
1.2 核心挑战
二、单机解决方案：位图法
2.1 算法原理
利用位数组表示数字存在性：
public class BitMap { private final byte[] bits; public BitMap(int maxNum) { this.bits = new byte[(maxNum >> 3) + 1]; // 每byte存储8个数字 } public void add(int num) { int arrayIndex = num >> 3; // num/8 int position = num & 0x07; // num%8 bits[arrayIndex] |= 1 << position; } public boolean contains(int num) { int arrayIndex = num >> 3; int position = num & 0x07; return (bits[arrayIndex] & (1 << position)) != 0; } }2.2 QQ号范围优化
QQ号范围：10000（5位） - 9999999999（10位）
位图内存计算：
(10^10 - 10^4) / 8 / 1024/1024 ≈ 1.16GB优化方案：
// 偏移量优化：存储(qq - 10000) public void add(long qq) { long num = qq - 10000; int arrayIndex = (int)(num >> 3); int position = (int)(num & 7); bits[arrayIndex] |= 1 << position; }三、进阶方案：布隆过滤器
3.1 应对内存限制
3.2 参数设计与实现
public class BloomFilter { private final BitSet bitset; private final int size; private final int[] seeds; public BloomFilter(int size, int hashCount) { this.bitset = new BitSet(size); this.size = size; this.seeds = new int[hashCount]; for (int i = 0; i < hashCount; i++) { seeds[i] = i * 31; } } public void add(String qq) { for (int seed : seeds) { int hash = hash(qq, seed); bitset.set(Math.abs(hash % size), true); } } public boolean contains(String qq) { for (int seed : seeds) { int hash = hash(qq, seed); if (!bitset.get(Math.abs(hash % size))) { return false; } } return true; } private int hash(String value, int seed) { // MurmurHash 实现 int result = 0; for (char c : value.toCharArray()) { result = seed * result + c; } return result; } }3.3 内存优化效果
| 方案 | 内存消耗 | 误差率 |
|---|---|---|
| 原始存储 | 8 GB | 0% |
| 位图法 | 1.16 GB | 0% |
| 布隆过滤器(0.1%) | 171 MB | 0.001 |
四、磁盘方案：外部排序与多路归并
4.1 处理流程
4.2 关键代码实现
// 外部排序 public void externalSort(String input, String output) throws IOException { List<File> chunks = splitAndSort(input, 100_000_000); // 每个文件1千万 mergeFiles(chunks, output); } // 多路归并 void mergeFiles(List<File> files, String output) { PriorityQueue<MergeEntry> queue = new PriorityQueue<>(); List<BufferedReader> readers = new ArrayList<>(); // 初始化堆 for (File file : files) { BufferedReader reader = new BufferedReader(new FileReader(file)); readers.add(reader); String line = reader.readLine(); if (line != null) { queue.add(new MergeEntry(line, reader)); } } try (BufferedWriter writer = new BufferedWriter(new FileWriter(output))) { long last = -1; while (!queue.isEmpty()) { MergeEntry entry = queue.poll(); long qq = Long.parseLong(entry.value); // 去重：只写入不重复的QQ号 if (qq != last) { writer.write(entry.value); writer.newLine(); last = qq; } // 读取下一行 String next = entry.reader.readLine(); if (next != null) { queue.add(new MergeEntry(next, entry.reader)); } } } finally { readers.forEach(r -> { try { r.close(); } catch (IOException e) {}}); } } class MergeEntry implements Comparable<MergeEntry> { String value; BufferedReader reader; public MergeEntry(String value, BufferedReader reader) { this.value = value; this.reader = reader; } @Override public int compareTo(MergeEntry o) { return this.value.compareTo(o.value); } }五、分布式解决方案
5.1 分片策略设计
5.2 Spark实现方案
val qqRDD = spark.read.textFile("hdfs://qq_data/*.txt") .map(_.toLong) .repartition(1000) // 分为1000个分区 // 每个分区内部去重 val distinctRDD = qqRDD.mapPartitions { iter => val bitmap = new RoaringBitmap() iter.foreach(qq => bitmap.add(qq.toInt)) bitmap.iterator.asScala.map(_.toLong) } // 全局去重（可选） val globalDistinct = distinctRDD.distinct() globalDistinct.saveAsTextFile("hdfs://result/")5.3 内存优化：RoaringBitmap
存储优势对比：
普通位图：10^10 / 8 / 1024/1024 ≈ 1.16 GB RoaringBitmap：稀疏数据下可压缩至100-300 MB六、生产级架构：Lambda架构
6.1 系统架构图
6.2 各层技术选型
| 架构层 | 技术栈 | 处理目标 |
|---|---|---|
| 批处理层 | Spark + HDFS | 全量数据去重 |
| 速度层 | Flink + Redis | 实时增量去重 |
| 服务层 | Spring Boot + HBase | 统一查询接口 |
6.3 实时去重实现
public class QQDeduplication { private static final String REDIS_KEY = "qq_set"; public boolean isDuplicate(String qq) { try (Jedis jedis = jedisPool.getResource()) { // 使用HyperLogLog进行基数估计 if (jedis.pfcount(REDIS_KEY) > 1_000_000_000L) { return true; // 已超过10亿，直接返回重复 } return jedis.sadd(REDIS_KEY, qq) == 0; } } }七、终极方案：分层位图索引
7.1 架构设计
7.2 存储计算
QQ号范围：10000 - 9999999999（约100亿）
分层设计：
- 第一层分片：100个区间（每区间1亿）
- 第二层分片：100个子区间（每区间100万）
- 第三层存储：RoaringBitmap（每分区1.2MB）
总内存需求：
100 × 100 × 1.2MB = 12GB（分布式存储可行）7.3 Java实现
public class LayeredBitmap { private final RoaringBitmap[][][] bitmaps; private static final int L1 = 100; // 一级分片 private static final int L2 = 100; // 二级分片 public LayeredBitmap() { bitmaps = new RoaringBitmap[L1][L2][]; } public void add(long qq) { int l1Index = (int)((qq - 10000) / 100_000_000); long remainder = (qq - 10000) % 100_000_000; int l2Index = (int)(remainder / 1_000_000); int value = (int)(remainder % 1_000_000); if (bitmaps[l1Index][l2Index] == null) { bitmaps[l1Index][l2Index] = new RoaringBitmap(); } bitmaps[l1Index][l2Index].add(value); } public boolean contains(long qq) { // 类似add的分片计算 RoaringBitmap bitmap = bitmaps[l1Index][l2Index]; return bitmap != null && bitmap.contains(value); } }八、方案对比与选型建议
| 方案 | 适用场景 | 内存/存储 | 时间复杂度 | 精度 |
|---|---|---|---|---|
| 单机位图 | <1亿数据 | O(n) | O(1) | 100% |
| 布隆过滤器 | 百亿级容忍误差 | O(1) | O(k) | <99.9% |
| 外部排序 | 单机磁盘处理 | 磁盘空间 | O(n log n) | 100% |
| Spark分布式 | 海量数据批量处理 | 集群存储 | O(n) | 100% |
| Redis实时去重 | 增量数据实时处理 | O(n) | O(1) | 100% |
| 分层位图索引 | 超大规模精准去重 | O(n)压缩存储 | O(1) | 100% |
九、实战经验与避坑指南
9.1 数据倾斜解决方案
问题场景：部分QQ号段过于集中（如100000-199999）
解决策略：
// 动态分片函数 int getShardId(long qq, int shardCount) { String str = String.valueOf(qq); // 取后6位作为分片依据 int suffix = Integer.parseInt(str.substring(Math.max(0, str.length() - 6))); return suffix % shardCount; }9.2 去重精度保障
9.3 成本优化建议
- 冷热分离：热数据用内存位图，冷数据存磁盘
- 压缩存储：使用RoaringBitmap替代普通位图
- 分级存储：
- 最近3个月数据：内存存储
- 历史数据：HBase+压缩
总结
- 分治思想：10亿问题拆解为1000个100万问题
- 空间换时间：位图法用存储空间换取O(1)时间复杂度
- 概率智慧：布隆过滤器用可控误差换取千倍空间压缩
- 分层设计：亿级→百万级→万级分层处理
- 动静分离：批处理处理历史数据，实时处理增量数据
10亿QQ号去重的本质，是将问题拆解到每个计算单元都能高效处理的粒度。
