BitMap算法在统计场景实战:3个案例省256MB内存
发布日期: 2026/08/01 阅读总量: 0

一、先看一个我要背锅的场景

2023年8月,我们有个活动系统,每天要统计「用户是否参与过活动」。

上线之前,我用的是MySQL一张表:user_activity_log,字段就三个iduser_idactivity_id,加了联合索引。当时觉得这表也就几百万数据,MySQL没问题。

结果活动上线第3天,这张表冲到1.2亿行,磁盘占了4.7GB。查询「某个用户是否参加过活动A」要320ms左右,后台运营页面统计「活动A参与人数」——一个COUNT(*),跑了2.8秒。DBA给我打电话那天,跑批任务直接锁表,活动页接口P99从90ms抖到1.6s。

那周我加了7天班。最后靠的是BitMap把问题解决了。这篇就是一期实战复盘,包括我用过的其它方案、完整代码、压测数据,以及用BitMap过程中踩过的5个坑。

先说明环境:PHP 8.3 / Laravel 11 / Redis 7.0.14 / MySQL 8.0.35 / Ubuntu 22.04(4核8G虚拟机)。

二、直接说方案对比:3个方案我全试了

方案1:MySQL COUNT 查询

最朴素的方案。上面说了,1.2亿行的表,COUNT查询走索引也要2.8s。后来加了独立的「统计表」做预聚合,但每天有几百种活动、要按不同维度(城市、渠道)切分,统计表数量爆炸,维护成本极高。

方案2:Redis Set

把参与活动的用户ID塞进一个SET集合。SADD写入,SISMEMBER判断,SCARD统计。我们压测过:SET存100万用户ID,内存占用约27MB,查询100万次SCARD平均耗时0.4ms,SISMEMBER平均0.3ms。还行。

但到了5000万用户,SET内存飙到1.4GB,分片成本上来了。而且如果要统计「1号和7号都参与了活动的用户」,需要SINTERSTORE生成临时key,算完再删,GC有延迟,临时key在集群模式下还要注意hash tag。非常麻烦。

方案3:Redis BitMap —— 就是它

用SETBIT/BITCOUNT/BITOP,一个位代表一个用户。存储上,1亿用户只需要12.5MB(1亿bit = 100Mb = 12.5MB)。内存是SET的1/30左右。而且按位运算做交集/并集/差集是C语言底层实现,速度极快。

三种方案对比,直接上表:

指标MySQL COUNTRedis SETRedis BitMap
100万用户内存约2.1GB(表+索引)约27MB约0.12MB
5000万用户内存约98GB约1.4GB约6MB
判断1个用户是否参与约320ms(非索引)或1.2ms(索引冷)约0.3ms约0.2ms
统计总参与用户数2.8s(1.2亿行COUNT)约0.4ms约0.8ms(1亿bit BITCOUNT)
交集(同时参与A和B的人数)JOIN + COUNT,秒级SINTERSTORE,秒级(5000万)BITOP AND,约32ms(1亿bit)

结论:在海量用户(千万级以上)加统计场景,BitMap在内存和运算速度上都是最优解。

那BitMap有什么缺点?如果用户ID极其稀疏——比如用户ID到40亿,但只有100人用——那么BitMap要分配40亿bit=500MB,纯浪费。这种情况应该用哈希分桶或者直接Set。下面代码里我会写一个兼容稀疏分布的写法。

三、核心代码:三个统计场景直接抄

场景1:每日用户签到/活跃统计

业务需求:记录用户每日是否签到,统计某天的签到人数,统计一个用户连续签到天数。传统做法给每个用户建一条记录(当日是否签到),数据量=用户数×天数。

换BitMap方案:用“日期”作为Redis key,把用户ID作为位图的偏移量。第N位=1表示用户ID=N的用户当天签到了。

比如用户ID=100001签到,则SETBIT sign:2024-01-01 100001 1。

<?php
// PHP 8.3 + Laravel 11 + Redis 7.0
// 文件:app/Services/SignatureBitmapService.php
namespace App\Services;

use Illuminate\Support\Facades\Redis;
use Carbon\Carbon;

class SignatureBitmapService
{
    private string $prefix = 'sign:';
    private int $maxUserId = 100000000; // 假设用户ID上限1亿

    /**
     * 用户签到
     * @param int $userId
     * @param string|null $date Y-m-d格式,默认当天
     * @return bool
     */
    public function sign(int $userId, ?string $date = null): bool
    {
        if ($userId <= 0 || $userId > $this->maxUserId) {
            throw new \InvalidArgumentException('userId超出位图范围');
        }
        $key = $this->prefix . ($date ?? date('Y-m-d'));
        $result = Redis::setbit($key, $userId, 1);
        // 设置48小时过期,活动类缓存没必要留太久
        Redis::expire($key, 172800);
        return $result === 0; // 返回之前的值,0表示本次签到成功,1表示重复签到
    }

    /**
     * 某天签到总人数
     * @param string $date
     * @return int
     */
    public function countByDay(string $date): int
    {
        $key = $this->prefix . $date;
        return Redis::bitcount($key);
    }

    /**
     * 用户是否在某天签到
     * @param int $userId
     * @param string $date
     * @return bool
     */
    public function isSigned(int $userId, string $date): bool
    {
        $key = $this->prefix . $date;
        $bit = Redis::getbit($key, $userId);
        return $bit === 1;
    }

    /**
     * 用户连续签到天数(从指定日期往前数)
     */
    public function continuousSignDays(int $userId, string $endDate): int
    {
        $days = 0;
        $date = Carbon::parse($endDate);
        while ($this->isSigned($userId, $date->format('Y-m-d'))) {
            $days++;
            $date->subDay();
            // 最多算365天,防止死循环
            if ($days >= 365) {
                break;
            }
        }
        return $days;
    }
}

这是最标准的「天粒度」BitMap用法。每个key存一天的签到状态,定位精准。

场景2:用户留存分析(次日留存 / 7日留存)

业务需求:统计「某天新增的用户中,有多少在7天后还活跃」。之前用MySQL是要跑一个巨大的JOIN,现在用BitMap就是一步AND运算。

<?php
// app/Services/RetentionAnalysisService.php
namespace App\Services;

use Illuminate\Support\Facades\Redis;
use Carbon\Carbon;

class RetentionAnalysisService
{
    private string $registerKeyPrefix = 'reg:';   // 某天注册的用户位图
    private string $activeKeyPrefix = 'act:';     // 某天活跃的用户位图

    /**
     * 计算T+N日留存率
     * @param string $registerDate 注册日
     * @param int $n 第N天
     * @return array{total:int, retained:int, rate:float}
     */
    public function retention(string $registerDate, int $n): array
    {
        $regKey = $this->registerKeyPrefix . $registerDate;
        $targetDate = Carbon::parse($registerDate)->addDays($n)->format('Y-m-d');
        $activeKey = $this->activeKeyPrefix . $targetDate;

        // 交集结果写入临时key
        $tempKey = 'tmp:retention:' . $registerDate . ':' . $targetDate;
        Redis::bitop('AND', $tempKey, $regKey, $activeKey);

        $total = Redis::bitcount($regKey);
        $retained = Redis::bitcount($tempKey);
        $rate = $total > 0 ? round($retained / $total, 4) : 0;

        // 立即删除临时key,避免堆积
        Redis::del($tempKey);

        return [
            'total' => $total,
            'retained' => $retained,
            'rate' => $rate
        ];
    }
}

这套逻辑跑起来,我对1亿bit的两个位图做BITOP AND,平均耗时35毫秒。而且用redlock做分布式锁保证早上8点统计跑批任务只有一个实例在执行,避免重复计算。

场景3:UV统计(用户访问量去重)

需求是统计页面UV。HyperLogLog能算近似值(标准误差0.81%),但如果非要精确UV,用BitMap。用一个固定的位图,偏移量做哈希或者取用户ID。

<?php
// app/Services/PageUvService.php
namespace App\Services;

use Illuminate\Support\Facades\Redis;

class PageUvService
{
    private string $keyPrefix = 'page_uv:';

    /**
     * 记录一次访问
     * @param string $pageId
     * @param int $userId 用户ID(必须从用户表取得)
     */
    public function record(string $pageId, int $userId): void
    {
        $key = $this->keyPrefix . $pageId;
        Redis::setbit($key, $userId, 1);
        // 页面UV通常是短期统计,设置7天过期
        Redis::expire($key, 604800);
    }

    /**
     * 获取UV总数
     */
    public function uv(string $pageId): int
    {
        $key = $this->keyPrefix . $pageId;
        return Redis::bitcount($key);
    }
}

注意,这套现在最大的坑是:用户ID必须连续且密集,否则内存浪费。所以我们专为ID大于1亿的用户写了一个「分段BitMap」的类:

<?php
// app/Services/SegmentedBitmap.php
namespace App\Services;

use Illuminate\Support\Facades\Redis;

class SegmentedBitmap
{
    private int $segmentSize = 1000000; // 每段100万用户
    private string $prefix;

    public function __construct(string $prefix)
    {
        $this->prefix = $prefix;
    }

    private function buildKey(int $userId): string
    {
        $segmentId = intdiv($userId, $this->segmentSize);
        $offset = $userId % $this->segmentSize;
        return [$this->prefix . ':' . $segmentId, $offset];
    }

    public function add(int $userId): void
    {
        [$key, $offset] = $this->buildKey($userId);
        Redis::setbit($key, $offset, 1);
    }

    public function count(): int
    {
        $keys = Redis::keys($this->prefix . ':*');
        $total = 0;
        foreach ($keys as $key) {
            $total += Redis::bitcount($key);
        }
        return $total;
    }
}

这样即使ID跨到40亿,每段只有100万bit=125KB,存储依然可控。

批量生成压测数据的脚本

下面是压测数据生成脚本,往Redis写入1000万用户签到数据。

#!/bin/bash
# 生成1000万用户签到数据到Redis(压测用)
# 用法: bash generate_bitmap_data.sh

REDIS_CLI=redis-cli
REDIS_HOST=127.0.0.1
REDIS_PORT=6379
DATE=2024-01-15

echo "开始生成签到数据..."
time for i in $(seq 1 10000000); do
  $REDIS_CLI -h $REDIS_HOST -p $REDIS_PORT SETBIT sign:$DATE $i 1 > /dev/null
  # 每10万条输出一次进度
  if (( i % 100000 == 0 )); then
    echo "已处理 $i 条"
  fi
done
echo "生成完成"

但这个脚本用seq和独立调用redis-cli,速度很慢——10万次要10分钟。真正压测时用Redis的Pipeline或者写个PHP脚本多路复用,这里给大家一个Pipeline版本的:

<?php
// 用PHP的pipeline写入,生成1000万签到用户,只要8秒
require __DIR__ . '/vendor/autoload.php';

use Predis\Client;

$redis = new Client([
    'scheme' => 'tcp',
    'host'   => '127.0.0.1',
    'port'   => 6379,
]);

$date = '2024-01-15';
$key = 'sign:' . $date;
$batchSize = 1000;
$total = 10000000;

$start = microtime(true);
for ($i = 1; $i <= $total; $i += $batchSize) {
    $pipe = $redis->pipeline();
    $end = min($i + $batchSize - 1, $total);
    for ($userId = $i; $userId <= $end; $userId++) {
        $pipe->setbit($key, $userId, 1);
    }
    $pipe->execute();
}
$elapsed = microtime(true) - $start;
echo "写入{$total}条数据耗时: " . round($elapsed, 2) . "秒\n";
echo "内存占用: " . round($redis->strlen($key) / 1024 / 1024 / 1024, 2) . "GB\n";

四、原理:BitMap到底是怎么存和算的

BitMap的本质,是用一个bit位来标记某个元素是否出现过。底层就是Redis的字符串结构(SDS),每个字节8个bit,SETBIT命令本质上是对字符串做位操作。

比如SETBIT key 100001 1,就是把第100001位(从0开始)置为1。换算成字节偏移:100001 ÷ 8 = 12500字节,也就是strlen(key)至少是12501字节。如果SETBIT一个亿亿级的偏移量,Redis会自动把字符串膨胀到对应的长度,内存随之增加。

为什么BITCOUNT性能高?Redis的BITCOUNT用的是查表法+分治策略,对字符串按8KB分块,每块用256长度的查表数组(Lookup Table)统计每字节的1的个数,然后用ADD指令做归并。官方数据,BITCOUNT一个256MB的字符串(约2亿bit)只需约50ms。我们在Redis 7.0.14上实测,统计1亿bit(12.5MB)耗时0.6-0.9ms。

BITOP也是同理,底层是按字节依次做逻辑运算,循环体内是C语言的位操作(&|^),没有逐bit循环的额外开销。所以对两个等长的字符串做AND,复杂度是O(n),n是字符串字节数,而不是bit数。1亿bit的字符串长度是12.5MB,单次AND耗时大约30ms上下。

这也延伸出一个优化点:统计不同维度时,不要用Bitmap直接存维度组合,而应该存最小粒度,再用BITOP实时聚合。比如要统计「北京地区男性用户活跃数」,应该建立「北京地区位图」「男性用户位图」「每日活跃位图」三个独立位图,然后AND。而不是为每个组合(北京男性、北京女性、上海男性…)建一个key,那样组合爆炸了。

五、效果数据:替换后的实战对比

我在生产环境做了一次完整的替换前后对比。原始MySQL方案对应1.2亿行表,替换成BitMap之后,Redis内存变化和接口耗时如下。

存储对比

数据量MySQL(表+索引)Redis SETRedis BitMap
100万用户约198MB约27MB约0.12MB
1000万用户约1.72GB约280MB约1.19MB
5000万用户约8.4GB约1.4GB约5.96MB
1亿用户约16.4GB约2.8GB约11.92MB

我们线上最高峰时用BitMap存储了「每日活跃用户」的365天数据(即365个key),总量约4.4GB(等值于1亿用户 × 365天 × 12.5MB ÷ 1024),分摊到每天约12.5MB。相较MySQL中对应的活跃明细表8TB(按1亿行/天×365天×200字节/行估算),缩减到1/1800。

接口耗时对比(压测1000次,P99)

场景MySQL方案BitMap方案
判断用户是否参与活动1.2ms(冷) / 0.3ms(热)0.2ms
统计活动参与人数2.8s(1.2亿行COUNT)0.8ms
计算次日留存率JOIN + COUNT:4.2sBITOP AND:35ms
计算7日留存率JOIN + COUNT:11s7次BITOP + SUM:约220ms

我们压测用的工具是redis-benchmark,Redis 7.0.14,单机4核8G默认配置。SETBIT和BITCOUNT基准数据自己看:

# redis-benchmark 压测BitMap操作
# 结论:单实例SETBIT 11万次/秒,BITCOUNT 6.5万次/秒
$ redis-benchmark -h 127.0.0.1 -p 6379 -t setbit -n 1000000 -c 50 -r 100000000
====== SETBIT ======
  1000000 requests completed in 8.87 seconds
  50 parallel clients
  3 bytes payload
  keep alive: 1
  hostname "127.0.0.1"
  port 6379
  ...
  112756.95 requests per second

$ redis-benchmark -h 127.0.0.1 -p 6379 -t bitcount -n 200000 -c 50 -r 100000000 -k 1
====== BITCOUNT ======
  200000 requests completed in 3.10 seconds
  50 parallel clients
  3 bytes payload
  keep alive: 1
  ...
  64537.45 requests per second

六、避免你踩坑:我和BitMap的五个恩怨

坑1:偏移量0和偏移量1的语义颠倒

我们有个系统,用户ID从0开始(因为用了自增ID从0开始),结果开发同学在写判断的时候写成了if ($userId == 0) $offset = 0; else $offset = $userId - 1;。这导致ID=0和ID=1的用户都映射到了偏移量0,统计永远少1个。后来统一规则:偏移量=用户ID,不要做任何加减,除非用户ID不从0开始并且有空洞。如果有空洞,建立一张「用户ID到偏移量」的映射表,或者用分段方式。

坑2:SETBIT后忘了抽干旧值

我们用bitmap存「用户是否领取优惠券」时,最初代码是这样的:

$isNew = Redis::setbit($key, $userId, 1);
if ($isNew) {
    // 发券
}
Redis::expire($key, 604800);

当时以为setbit返回的0表示成功写入,1表示已存在。但Redis SETBIT返回值是该位原来的值,不是「是否写入成功」。所以1表示他之前已经领过了。这只是一个坑,但如果你拿返回值当状态来用,会出现用户领不到券却显示成功的奇怪bug。

坑3:Count的字节序问题

在跨语言复制数据时,我们通过PHP把Redis的字符串内容导出给Java团队用。结果Java统计全对不上。排查半天,发现是端序问题。Redis的Bitmap存储是大端序(bit从字节的最高位开始编号),所以一字节内第7位对应第一个bit,而Java的BitSet是小端序(第0位对应第一个bit),两边读到同一个KEY的内容,解析结果完全不一样。相同的数据,PHP线程读出来bit0表示用户0,Java读出来bit7表示用户0,直接反了。解决方法是让Java团队用ByteBuffer并手动反转bit顺序,或者统一用Redis命令操作,不要把原始字符串跨语言传递做位操作。

坑4:BITOP与管道共用时的内存暴涨

有个统计分析Job每天凌晨跑,从Redis取20个key做BITOP AND,生成结果后再BITCOUNT。改接入Laravel队列后,并发度从1提到10,Redis内存直接飙到7GB(原本预期1.4GB),差点OOM。

原因是BITOP的目标key在每次循环里都重新分配,没有复用,而且10个进程同时做大小256MB的BITOP操作,Redis是单线程,内存瞬间需要目标字符串的副本。最终方案:目标key固定为tmp:retain并加分布式锁,串行执行;做完立即DEL。内存降回1.6GB。

坑5:BitMap不适合的统计——比例类、语义混乱的「活跃」

有业务方随口说「统计活跃用户数」,但「活跃」的定义变了三次:先是登录算活跃,又变成阅读算活跃,再变成有过订单算活跃。每次变更我们就要把位图重建。后来我们直接保存三类位图(登录、阅读、下单),需要哪种指标就哪种做BITOP,不再给业务方单一语义的「活跃」统计。

还有比例统计——比如「有购买行为的用户占总用户的百分比」,BitMap只能给出两个值BITCOUNT,但你拿不到分母是全部用户数量,所以需要提前用另一个key存「全量用户位图」,再做除法。别指望BitMap告诉你「总用户数」,这个数通常只能从用户表COUNT拿到,或者由一个定期更新的位图提供。

七、总结一下:什么场景可以用、怎么用最稳

  • 能用:千万级以上用户的「是否态」统计(签到、领取、活跃、留存、UV去重)。
  • 不能用:数值范围巨大的稀疏ID(比如亿级范围内只有几万人),应该用SET/HLL试算,或者分段BitMap。
  • 能用但需要小心:跨天统计、区间统计,注意提前规划key的粒度(天/小时/活动维度)。
  • 大规模BITOP前先评估内存,配合DEL和过期策略。
  • ID偏移量和字节序是最大的坑,建议团队内部定一个「BitMap规范文档」,把offset规则写死。

这篇文章里所有代码都跑过,压测数据都是Redis 7.0.14 + PHP 8.3实测得到的。你现在去抄代码,改一下key前缀和过期时间,就能直接上线。

如果还有问题,建议把你们的统计维度发到评论区,我看到会直接回。