Go语言并发安全的BitMap位图统计亿级用户去重实战

title: “Go语言并发安全的BitMap位图统计亿级用户去重实战”date: 2026-06-08tags: [Go, Bitmap, 位图, 去重, 高并发, 大数据]categories: Go高并发编程Go语言并发安全的BitMap位图统计亿级用户去重实战导语在大数据和广告投放等场景中亿级用户去重是一个经典难题。如果用map[uint64]bool存储1亿个用户ID仅内存就需要约 800MB每个键值对约8字节而用Bitmap位图只需 1亿 / 8 12.5MB内存节省 64 倍。更妙的是位图支持极低成本的集合运算AND/OR/XOR是布隆过滤器、Roaring Bitmap、Redis Bitmap 的底层支撑。本文将用 Go 语言实现一个并发安全的 Bitmap覆盖基础位图、分段锁优化以及与 Redis Bitmap 的对接实战。一、核心技术知识点讲解1. Bitmap 基础原理Bitmap 用一个 bit 表示一个元素是否存在元素集合{0, 3, 7, 10} Bitmap16位 索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 位值 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 内存 [0b01001001, 0b00000010] byte[0] byte[1]容量计算N 位 Bitmap 可表示 0~N-1 的整数占用内存 ceil(N/8)字节1亿位 12.5 MB10亿位 125 MB2. 并发安全的 Bitmap 设计策略方案描述优点缺点全局 Mutex所有操作竞争一把锁实现简单高并发下性能差RWMutex读操作可并发读多写少时好写仍串行分段锁Sharded按 word 索引分片每片独立加锁并发度最高实现复杂atomic 位操作用atomic.Or8/And8操作单个 byte无锁极快只能操作单字节本文方案全局sync.RWMutex简单场景 分段锁高并发场景。3. Bitmap 的典型应用场景场景说明时间复杂度用户去重日活统计、UV 计算O(1)布隆过滤器底层用 k 个不同哈希函数映射到 k 个位O(k)签到系统365 位表示一年签到O(1)基数估计HyperLogLog寄存器用位图存储O(1)集合运算AND/OR/XOR 按 word 批量处理O(n/word)二、实战代码演示/项目案例总结1. 并发安全 Bitmap 基础实现packagemainimport(sync)// Bitmap 并发安全位图全局读写锁版本typeBitmapstruct{mu sync.RWMutex bits[]bytesizeuint64// 位容量}// NewBitmap 创建位图capacity最多可存储的元素值1funcNewBitmap(capacityuint64)*Bitmap{byteCount:(capacity7)/8// 向上取整returnBitmap{bits:make([]byte,byteCount),size:capacity,}}// Set 设置指定位为 1并发安全写锁func(bm*Bitmap)Set(bituint64){bm.mu.Lock()deferbm.mu.Unlock()ifbitbm.size{return// 静默忽略越界生产环境应返回 error}idx:bit/8offset:bit%8bm.bits[idx]|1offset}// SetN 批量设置减少锁竞争func(bm*Bitmap)SetN(bits[]uint64){bm.mu.Lock()deferbm.mu.Unlock()for_,bit:rangebits{ifbitbm.size{continue}idx:bit/8offset:bit%8bm.bits[idx]|1offset}}// Test 检查指定位是否为 1并发安全读锁func(bm*Bitmap)Test(bituint64)bool{bm.mu.RLock()deferbm.mu.RUnlock()ifbitbm.size{returnfalse}idx:bit/8offset:bit%8return(bm.bits[idx](1offset))!0}// Clear 清除指定位设为 0func(bm*Bitmap)Clear(bituint64){bm.mu.Lock()deferbm.mu.Unlock()ifbitbm.size{return}idx:bit/8offset:bit%8bm.bits[idx]^1offset// ^ 是 Go 的按位清除}// Count 统计置位数量population count / popcntfunc(bm*Bitmap)Count()uint64{bm.mu.RLock()deferbm.mu.RUnlock()varcountuint64for_,b:rangebm.bits{countuint64(popcnt(uint64(b)))// 单字节查表/计算}returncount}// popcnt Population Count查表法快varpc[256]byte// 预计算 0~255 的 1 的个数funcinit(){fori:rangepc{pc[i]pc[i/2]byte(i1)}}funcpopcnt(xuint64)int{// 对单字节returnint(pc[byte(x)])}// Bytes 返回底层字节切片用于持久化/网络传输func(bm*Bitmap)Bytes()[]byte{bm.mu.RLock()deferbm.mu.RUnlock()// 返回副本防止外部修改cp:make([]byte,len(bm.bits))copy(cp,bm.bits)returncp}// OR 按位或两个位图做并集func(bm*Bitmap)OR(other*Bitmap)*Bitmap{bm.mu.RLock()deferbm.mu.RUnlock()other.mu.RLock()deferother.mu.RUnlock()minLen:len(bm.bits)iflen(other.bits)minLen{minLenlen(other.bits)}result:NewBitmap(bm.size)fori:0;iminLen;i{result.bits[i]bm.bits[i]|other.bits[i]}// 若 other 更长复制剩余部分iflen(other.bits)minLen{copy(result.bits[minLen:],other.bits[minLen:])}returnresult}2. 使用math/bits加速Go 1.9importmath/bits// CountFast 使用 CPU 硬件指令 popcnt如果 CPU 支持func(bm*Bitmap)CountFast()uint64{bm.mu.RLock()deferbm.mu.RUnlock()varcountuint64for_,b:rangebm.bits{countuint64(bits.OnesCount8(b))}returncount}// CountBatch 按 8 字节uint64批量统计更快func(bm*Bitmap)CountBatch()uint64{bm.mu.RLock()deferbm.mu.RUnlock()varcountuint64// 按 uint648字节批量处理words:len(bm.bits)/8fori:0;iwords;i{offset:i*8// 将 8 字节组合为 uint64varwuint64forj:0;j8;j{w|uint64(bm.bits[offsetj])(j*8)}countuint64(bits.OnesCount64(w))}// 处理尾部不足 8 字节的部分fori:words*8;ilen(bm.bits);i{countuint64(bits.OnesCount8(bm.bits[i]))}returncount}3. 分段锁优化高并发场景constshardCount128// 分片数2的幂方便取模// ShardedBitmap 分段锁位图高并发优化typeShardedBitmapstruct{shards[shardCount]*bitmapShard sizeuint64}typebitmapShardstruct{mu sync.RWMutex bits[]byte}funcNewShardedBitmap(capacityuint64)*ShardedBitmap{sb:ShardedBitmap{size:capacity}bytesPerShard:((capacity7)/8)/shardCountfori:0;ishardCount;i{sb.shards[i]bitmapShard{bits:make([]byte,bytesPerShard1),// 1 防止边界溢出}}returnsb}func(sb*ShardedBitmap)getShard(bituint64)*bitmapShard{// 用 bit / 8 找到 byte 索引再对 shardCount 取模byteIdx:bit/8returnsb.shards[byteIdx%shardCount]}// Set 只锁对应的分片其他分片可并发func(sb*ShardedBitmap)Set(bituint64){ifbitsb.size{return}shard:sb.getShard(bit)shard.mu.Lock()defershard.mu.Unlock()idx:(bit/8)/shardCount// 分片内的 byte 索引offset:bit%8shard.bits[idx]|1offset}// Test 同理只持读锁在对应分片func(sb*ShardedBitmap)Test(bituint64)bool{ifbitsb.size{returnfalse}shard:sb.getShard(bit)shard.mu.RLock()defershard.mu.RUnlock()idx:(bit/8)/shardCount offset:bit%8return(shard.bits[idx](1offset))!0}4. 对接 Redis Bitmap生产级用法importgithub.com/redis/go-redis/v9// RedisBitmap 基于 Redis 的 Bitmap支持持久化、分布式typeRedisBitmapstruct{client*redis.Client keystring}funcNewRedisBitmap(client*redis.Client,keystring)*RedisBitmap{returnRedisBitmap{client:client,key:key}}// Set 使用 Redis SETBITfunc(rb*RedisBitmap)Set(ctx context.Context,bitint64)error{returnrb.client.SetBit(ctx,rb.key,bit,1).Err()}// Test 使用 Redis GETBITfunc(rb*RedisBitmap)Test(ctx context.Context,bitint64)(bool,error){result,err:rb.client.GetBit(ctx,rb.key,bit).Result()returnresult1,err}// Count 使用 Redis BITCOUNTfunc(rb*RedisBitmap)Count(ctx context.Context)(int64,error){returnrb.client.BitCount(ctx,rb.key,redis.BitCount{Start:0,End:-1,}).Result()}// CardinalityEstimation 使用 Redis HLLHyperLogLog更省内存// 若允许约 0.81% 的误差HLL 只需 ~12KB 即可统计亿级 UVfuncexampleHyperLogLog(ctx context.Context){client.PFAdd(ctx,uv:2026-06-08,user:1001,user:1002)count,_:client.PFCount(ctx,uv:2026-06-08)fmt.Printf(估算UV: %d\n,count)}三、开发痛点与报错避坑指南痛点1Bitmap 容量估算错误导致越界// ❌ 错误用用户 ID 最大值直接作为 capacity// 用户 ID 范围1000000 ~ 91000000最大 9100万bm:NewBitmap(91000000)// 实际上 capacity 应该是 910000001// 当设置 ID91000000 时91000000 91000000capacity被静默忽略// ✅ 正确capacity 取 maxID 1maxID:uint64(91000000)bm:NewBitmap(maxID1)最佳实践生产环境建议使用Roaring Bitmapgithub.com/Roaring/roaring它支持动态扩容无需预估算容量。痛点2bits.OnesCount64与手写循环的性能差异// ❌ 慢逐 bit 移位统计funccountSlow(bbyte)int{count:0fori:0;i8;i{if(b(1i))!0{count}}returncount}// ✅ 快使用 CPU popcnt 指令Go 的 math/bits 会自动使用硬件指令funccountFast(bbyte)int{returnbits.OnesCount8(b)// 编译为一条 CPU 指令如果 CPU 支持}// 性能差异~10x痛点3并发Set时的 “Read-Modify-Write” 竞争// ❌ 错误先 Test 再 SetTOCTOU 竞争if!bm.Test(bit){// 读// 另一个 goroutine 在这里插入了 bitbm.Set(bit)// 写实际应该 CAS}// ✅ 正确Set 操作是幂等的直接调用即可OR 操作天然幂等// 或者使用 atomic.Or8无锁但需要 *byte 指针importsync/atomicatomic.Or8(bm.bits[idx],1offset)// 无锁设置单 bit仅单字节安全痛点4Bitmap 持久化时的字节序问题// ❌ 错误直接把 []byte 写到文件不同机器大端/小端读取会出错data:bm.Bytes()os.WriteFile(bitmap.bin,data,0644)// ✅ 正确使用二进制协议如 protocol buffers或明确字节序// 或者Bitmap 的 []byte 是位→字节的映射本身不涉及数值字节序// 但要注意读取时必须按相同格式解析痛点51亿位以上 Bitmap 的内存碎片// ❌ 危险一次性分配超大 Bitmap可能分配失败bm:NewBitmap(10_0000_0000)// 10亿位 125MB可能触发 GC 压力// ✅ 改进使用 Roaring Bitmap压缩位图内存动态增长importgithub.com/Roaring/roaringrb:roaring.New()rb.Add(1,2,3,100000000)// 稀疏时极省内存四、全文总结技术进阶展望总结Bitmap 是海量数据去重的利器内存占用仅为map[int]bool的 1/64并发安全要点全局 RWMutex 适合读多写少分段锁适合高并发写入math/bits.OnesCount使用 CPU 硬件指令性能极高统计必备生产环境优先使用 Redis Bitmap 或 Roaring Bitmap支持持久化和动态扩容进阶展望Roaring Bitmap目前最快的压缩位图算法Spark、Elasticsearch、InfluxDB 均使用Go 实现github.com/Roaring/roaringConcurrent Roaring Bitmap支持并发修改的 Roaring Bitmap适合高并发分析场景Bitmap 索引数据库MySQL/PostgreSQL 的 Bitmap 索引原理可用于多条件组合查询优化SIMD 加速使用 AVX2/AVX-512 指令集批量处理位图Go 中可通过github.com/klauspost/cpuid检测 CPU 特性后选择优化路径内存占用对比1亿用户 ID 去重方案内存占用是否精确说明map[uint64]bool~800 MB✅ 精确不可接受普通 Bitmap12.5 MB✅ 精确推荐Roaring Bitmap稀疏1~12 MB✅ 精确最优HyperLogLog~12 KB❌ 误差~0.81%可接受误差时用五、参考文献Roaring Bitmap 官方论文.Consensus on Random: Consructing Small and Fast Bitmap Indexes. https://roaringbitmap.org/talk/roaring_bitmaps.pptx.pdfRedis BITMAP 官方文档. https://redis.io/commands/setbit/Gomath/bits包文档. https://pkg.go.dev/math/bitsApache Lucene - Roaring Bitmap 应用. https://lucene.apache.org/core/布隆过滤器原理. https://en.wikipedia.org/wiki/Bloom_filterHyperLogLog 算法论文. https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdfGo Roaring 实现. https://github.com/Roaring/roaringIntel Intrinsics Guide - POPCNT 指令. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html