32.10亿QQ如何去重?
大约 6 分钟
32.10亿QQ如何去重?
前言
最近在网上看到一个问题:10亿QQ号如何去重?
我觉得挺有意思的。
今天这篇文章跟大家一起分享一下常见的解决方案,希望对你会有所帮助。
访点击这里:100万QPS短链系统、复杂的微服务系统实战、商城系统实战、秒杀系统实战、代码生成工具实战、工作经验分享、技术选型、系统设计、性能优化、源码解读、高频面试题,这里什么都有
一、技术难点
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号去重的本质,是将问题拆解到每个计算单元都能高效处理的粒度。
为了帮助更多的粉丝朋友,找到个好工作,多拿几个offer。苏三最近建一些工作内推群,群里目前已经收集了很多内推岗位,大厂、中厂、小厂、外包都有。欢迎HR、开发、测试、运维和产品加入。
扫描下方微信,备注:网站+所在城市,即可拉你进工作内推群。