Redis BitMap与HyperLogLog实战：亿级UV统计、用户签到与布隆过滤器原理深度解析

引言：为什么需要概率数据结构

在高并发互联网系统中，我们经常面临海量数据的统计需求：日活用户数有多少？某篇文章的独立访客（UV）是多少？今天有多少用户完成了签到？用户是否已经看过这条推荐内容？这些问题看似简单，但当用户量达到亿级别时，传统的HashSet方案会消耗惊人的内存。Redis提供了BitMap、HyperLogLog以及通过Module支持的布隆过滤器，用极小的内存代价解决了这些大规模统计问题。本文将深入解析这三种概率/位图数据结构的底层原理，并给出完整的实战代码。

先来看一个直观的对比：统计1亿用户的UV，使用Redis SET存储用户ID大约需要1.5GB内存，使用HyperLogLog仅需12KB，误差约0.81%。使用BitMap存储1亿用户的签到状态仅需约12MB。这就是概率数据结构的威力——用可接受的精度损失换取数量级的内存节省。

BitMap数据结构原理与内存模型

BitMap的本质：字符串的位操作

Redis中的BitMap并不是一种独立的数据类型，而是基于String类型的位操作扩展。String类型在Redis中最大支持512MB，这意味着一个BitMap最多可以表示2^32（约42.9亿）个bit位。每一个bit位只有0和1两种状态，非常适合表示布尔型信息：签到/未签到、在线/离线、活跃/非活跃。

BitMap的底层存储就是普通的String。当你对某个key执行SETBIT操作时，Redis会确保对应的字符串长度足够，然后将指定位置的bit设置为0或1。字符串内部以字节为单位存储，每个字节包含8个bit位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 基本位操作示例

# 设置第7位（用户ID=7）为1，表示已签到

SETBIT user:sign:20260906 7 1

# 获取第7位的状态

GETBIT user:sign:20260906 7

# 返回: 1



# 统计所有为1的位数（今天有多少人签到）

BITCOUNT user:sign:20260906

# 返回: 1



# 对多个BitMap做位运算

BITOP AND result_key bitmap1 bitmap2  # 交集

BITOP OR  result_key bitmap1 bitmap2  # 并集

BITOP XOR result_key bitmap1 bitmap2  # 异或

内存占用计算

BitMap的内存占用取决于最大的bit偏移量，而非实际设置为1的位数。如果用户ID是稀疏的（例如最大ID为1亿但只有1万人活跃），BitMap仍然需要分配完整的1亿bit空间。这是BitMap与HyperLogLog的关键区别——BitMap适合密集的ID空间，HyperLogLog适合稀疏的大规模基数统计。

从表中可以看出，当用户ID连续且密集时，BitMap的内存效率远优于SET。但当ID范围远大于实际用户数时，HyperLogLog更具优势。

BitMap实战：用户签到系统设计

用户签到是一个典型的BitMap应用场景。假设系统有1000万用户，用户ID从1到10000000连续分配，我们需要记录每天每个用户的签到状态，并支持查询连续签到天数、当月签到天数等统计。

数据结构设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 按天存储签到记录

# Key格式: sign:{userId}:{yyyyMM}

# Value: BitMap，第day位表示该天是否签到



# 用户1001在2026年9月6日签到（本月第6天）

SETBIT sign:1001:202609 5 1



# 查询用户1001本月签到天数

BITCOUNT sign:1001:202609

# 返回: 1



# 查询用户1001在9月6日是否签到

GETBIT sign:1001:202609 5

# 返回: 1

Python实现：连续签到统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import redis

from datetime import datetime, timedelta



class SignInService:

    def __init__(self, host='localhost', port=6379):

        self.r = redis.Redis(host=host, port=port, decode_responses=True)

    

    def sign(self, user_id, date=None):

        if date is None:

            date = datetime.now()

        key = f"sign:{user_id}:{date.strftime('%Y%m')}"

        day_index = date.day - 1

        if self.r.getbit(key, day_index):

            return False

        self.r.setbit(key, day_index, 1)

        return True

    

    def get_month_sign_count(self, user_id, year, month):

        key = f"sign:{user_id}:{year}{month:02d}"

        return self.r.bitcount(key)

    

    def get_continuous_sign_days(self, user_id, date=None):

        if date is None:

            date = datetime.now()

        count = 0

        current = date

        while True:

            key = f"sign:{user_id}:{current.strftime('%Y%m')}"

            day_index = current.day - 1

            if self.r.getbit(key, day_index):

                count += 1

                current = current - timedelta(days=1)

            else:

                break

        return count

全局签到BitMap：一次BITCOUNT统计当日活跃

上面的方案按用户维度存储签到，但如果我们想知道今天总共有多少用户签到了，需要额外维护一个全局BitMap。每天一个Key，用户ID作为bit偏移：

1
2
3
4
5
6
7
8
9
10
11
# 全局签到BitMap

SETBIT daily_sign:20260906 1001 1

SETBIT daily_sign:20260906 1002 1



# 统计今天签到总人数

BITCOUNT daily_sign:20260906

# 返回: 2



# 统计最近7天都有签到的用户（连续7天活跃）

BITOP AND active_7days daily_sign:20260831 daily_sign:20260901 daily_sign:20260902 daily_sign:20260903 daily_sign:20260904 daily_sign:20260905 daily_sign:20260906

BITCOUNT active_7days

BitMap实战：亿级用户活跃度统计

对于日活（DAU）、月活（MAU）这类指标，BitMap的位运算能力可以高效地计算交集、并集和差集。例如计算7天留存率，就是第1天和第7天都活跃的用户数除以第1天活跃的用户数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import redis

import calendar



class ActiveUserService:

    def __init__(self):

        self.r = redis.Redis(decode_responses=True)

    

    def mark_active(self, user_id, date_str):

        self.r.setbit(f"active:daily:{date_str}", user_id, 1)

    

    def get_dau(self, date_str):

        return self.r.bitcount(f"active:daily:{date_str}")

    

    def get_mau(self, year_month):

        year = int(year_month[:4])

        month = int(year_month[4:])

        days = calendar.monthrange(year, month)[1]

        keys = [f"active:daily:{year_month}{str(d).zfill(2)}" for d in range(1, days+1)]

        result_key = f"active:mau:{year_month}"

        self.r.bitop("OR", result_key, *keys)

        return self.r.bitcount(result_key)

    

    def get_retention_rate(self, day1, day2):

        key1 = f"active:daily:{day1}"

        key2 = f"active:daily:{day2}"

        self.r.bitop("AND", "temp:retention", key1, key2)

        retained = self.r.bitcount("temp:retention")

        total = self.r.bitcount(key1)

        self.r.delete("temp:retention")

        return retained / total if total > 0 else 0.0

HyperLogLog原理：基数估计算法深度解析

什么是基数估计

基数（Cardinality）是指一个集合中不重复元素的个数。精确计算基数需要存储所有元素（如SET），内存消耗与元素数量线性增长。基数估计算法通过概率数学方法，在固定内存下近似计算基数，误差可控但内存消耗与数据量无关。

HyperLogLog算法核心思想

HyperLogLog（HLL）基于一个观察：对随机数做哈希后，二进制表示中前导零的长度与基数存在对数关系。具体来说：

• 对每个元素计算哈希值，得到均匀分布的二进制串
• 取哈希值的前k位作为桶编号（Redis中k=14，宣16384个桶）
• 剩余位中第一个1出现的位置记为该桶的最大前导零长度+1
• 根据所有桶的最大前导零长度，用调和平均数估算基数

Redis的HyperLogLog固定使用12KB内存（16384个桶，每个6bit），无论统计1个元素还是1亿个元素，内存消耗恒定。标准误差约0.81%。

1
2
3
4
5
6
7
8
9
10
# HyperLogLog基本操作

PFADD page_uv:homepage user1 user2 user3

# 返回: 1



PFCOUNT page_uv:homepage

# 返回: 3



# 合并多个HLL

PFMERGE site_uv:total page_uv:homepage page_uv:article page_uv:about

PFCOUNT site_uv:total

Redis HLL的内存秘密

Redis的HyperLogLog使用稀疏存储和密集存储两种编码。当元素较少时（桶中多为0），使用稀疏编码节省内存，可能只占几十字节。当桶逐渐被填充后，自动转换为密集编码，固定占用约12KB（16384 * 6bit / 8 = 12288字节）。这种设计使得HLL在小数据量时也不会浪费内存。

1
2
3
4
5
6
7
8
9
10
11
12
# 观察HLL的内存变化

PFADD hll_test a

MEMORY USAGE hll_test

# 返回: 16（稀疏编码，非常小）



# 添加大量元素后

for i in $(seq 1 100000); do PFADD hll_test "user_$i"; done

MEMORY USAGE hll_test

# 返回: 12304（密集编码，约12KB）



PFCOUNT hll_test

# 返回: ~100025（误差0.03%）

HyperLogLog实战：UV统计系统实现

网站UV统计方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import redis

import hashlib

from datetime import datetime, timedelta



class UVService:

    def __init__(self):

        self.r = redis.Redis(decode_responses=True)

    

    def _hash_user(self, user_id):

        return hashlib.md5(user_id.encode()).hexdigest()[:16]

    

    def record_page_view(self, page, user_id):

        today = datetime.now().strftime('%Y%m%d')

        key = f"uv:page:{page}:{today}"

        self.r.pfadd(key, self._hash_user(user_id))

        self.r.expire(key, 86400 * 30)

    

    def get_page_uv(self, page, date_str=None):

        if date_str is None:

            date_str = datetime.now().strftime('%Y%m%d')

        return self.r.pfcount(f"uv:page:{page}:{date_str}")

    

    def get_page_uv_range(self, page, days=7):

        keys = []

        for i in range(days):

            date_str = (datetime.now() - timedelta(days=i)).strftime('%Y%m%d')

            keys.append(f"uv:page:{page}:{date_str}")

        merge_key = f"uv:page:{page}:range:{days}d"

        self.r.pfmerge(merge_key, *keys)

        self.r.expire(merge_key, 3600)

        return self.r.pfcount(merge_key)

    

    def get_site_total_uv(self, date_str=None):

        if date_str is None:

            date_str = datetime.now().strftime('%Y%m%d')

        pattern = f"uv:page:*:{date_str}"

        keys = list(self.r.scan_iter(pattern))

        if not keys:

            return 0

        merge_key = f"uv:site:{date_str}"

        self.r.pfmerge(merge_key, *keys)

        self.r.expire(merge_key, 86400)

        return self.r.pfcount(merge_key)

HLL误差实测与边界场景

在生产环境中使用HLL前，需要了解其误差范围和适用场景。以下是实测数据：

注意：HLL不适合需要精确值的场景，如财务统计、库存计数等。它最适合容忍约1%误差的大规模去重统计，如UV、DAU、独立设备数等。

布隆过滤器：原理、RedisBloom模块与生产应用

布隆过滤器原理

布隆过滤器（Bloom Filter）是一种概率数据结构，用于判断元素是否在集合中。它的特点是：可能有假阳性（说在但实际不在），但绝无假阴性（说不在就一定不在）。这个特性使它非常适合用作缓存前置过滤——当布隆过滤器说不存在时，可以直接跳过缓存和数据库查询，避免缓存穿透。

布隆过滤器的原理：

• 使用一个长度为m的bit数组和k个哈希函数
• 插入元素时，用k个哈希函数计算k个位置，全部置为1
• 查询元素时，用k个哈希函数计算k个位置，如果全部为1则可能存在，如果任意一个为0则一定不存在
• 假阳性率取决于bit数组长度m、哈希函数数量k和已插入元素数量n

RedisBloom模块安装与使用

RedisBloom是Redis的官方Module，提供了布隆过滤器、布谷鸟过滤器（Cuckoo Filter）、Count-Min Sketch等概率数据结构。从Redis 4.0开始支持Module，可以通过–loadmodule参数加载。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# RedisBloom基本命令

# 创建布隆过滤器，指定预期元素数量和假阳性率

BF.RESERVE user_filter 0.001 1000000

# 参数：key名称, 错误率0.1%, 预期容量100万



# 添加元素

BF.ADD user_filter "user:10001"

# 返回: 1



# 批量添加

BF.MADD user_filter "user:10002" "user:10003" "user:10004"



# 检查元素是否存在

BF.EXISTS user_filter "user:10001"

# 返回: 1（可能存在）



BF.EXISTS user_filter "user:99999"

# 返回: 0（一定不存在）



# 批量检查

BF.MEXISTS user_filter "user:10001" "user:99999"

# 返回: 1 0

布隆过滤器实战：解决缓存穿透

缓存穿透是指大量请求查询数据库中不存在的数据，每次请求都穿透缓存直达数据库，可能导致数据库崩溃。布隆过滤器可以在缓存层之前做一道拦截：将所有合法ID加入布隆过滤器，请求到来时先查布隆过滤器，不存在则直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import redis



class CachePenetrationGuard:

    def __init__(self):

        self.r = redis.Redis(decode_responses=True)

        self.filter_key = "bf:user_ids"

    

    def init_filter(self, user_ids, error_rate=0.001, capacity=1000000):

        self.r.execute_command('BF.RESERVE', self.filter_key, error_rate, capacity)

        pipe = self.r.pipeline()

        for uid in user_ids:

            pipe.execute_command('BF.ADD', self.filter_key, str(uid))

        pipe.execute()

    

    def add_user(self, user_id):

        self.r.execute_command('BF.ADD', self.filter_key, str(user_id))

    

    def get_user(self, user_id):

        user_key = f"user:{user_id}"

        exists = self.r.execute_command('BF.EXISTS', self.filter_key, str(user_id))

        if not exists:

            return None

        cached = self.r.hgetall(user_key)

        if cached:

            return cached

        # 第3层：数据库查询

        # db_user = db.query("SELECT * FROM users WHERE id = %s", user_id)

        # if db_user:

        #     self.r.hmset(user_key, db_user)

        #     self.r.expire(user_key, 3600)

        # return db_user

        pass

布谷鸟过滤器：支持删除的替代方案

标准布隆过滤器不支持删除操作——因为多个元素可能共享同一个bit位，删除一个元素会影响其他元素。布谷鸟过滤器（Cuckoo Filter）解决了这个问题，它支持删除且空间效率更高。RedisBloom模块同样提供了布谷鸟过滤器：

1
2
3
4
5
6
7
8
9
10
# 布谷鸟过滤器

CF.RESERVE user_cf 1000000

CF.ADD user_cf "user:10001"

CF.EXISTS user_cf "user:10001"

# 返回: 1



# 布谷鸟过滤器支持删除

CF.DELETE user_cf "user:10001"

CF.EXISTS user_cf "user:10001"

# 返回: 0

性能对比与生产选型建议

三种方案的性能基准

以下是我们在生产环境中实测的性能数据（Redis 7.2，单节点，16核32GB）：

选型决策树

• 需要精确的存在性判断且元素密集 → BitMap（用户签到、活跃度标记）
• 需要去重计数（UV/DAU），可接受约1%误差 → HyperLogLog（UV统计、独立设备数）
• 需要前置过滤防止缓存穿透 → Bloom Filter（商品ID过滤、用户ID过滤）
• 需要删除操作 → Cuckoo Filter（动态变化的集合）
• 需要精确计数且数据量小 → SET（数据量小于10万时SET完全可用）

生产环境最佳实践

1. BitMap的BITCOUNT优化：对大BitMap使用START和END参数分批统计，避免阻塞：

1
2
3
4
5
6
7
# 分批统计1亿bit的BitMap

total = 0

for i in range(12):

    start = i * 8388608

    end = (i + 1) * 8388608 - 1

    total += r.bitcount("active:daily:20260906", start, end, "BIT")

print(f"总活跃用户: {total}")

2. HyperLogLog的Key设计：避免一个Key存储过多数据，按时间维度拆分，用PFMERGE合并。这样可以灵活计算任意时间范围的UV：

1
2
3
4
5
6
7
# 按小时维度存储UV，更灵活

PFADD uv:homepage:2026090614 user1 user2

PFADD uv:homepage:2026090615 user3 user4



# 合并全天UV

PFMERGE uv:homepage:20260906 uv:homepage:2026090614 uv:homepage:2026090615

PFCOUNT uv:homepage:20260906

3. 布隆过滤器的容量规划：创建时必须指定预期容量，超出后假阳性率急剧上升。建议设置为实际容量的1.5-2倍，并定期重建：

1
2
3
4
5
6
7
# 假设实际用户100万，设置容量200万

BF.RESERVE user_filter 0.001 2000000



# 监控布隆过滤器状态

BF.INFO user_filter

# 返回包含：Capacity, Size, FilterNum, InsertedNum, ExpansionNum等

# 当 InsertedNum 接近 Capacity 时需要扩容或重建

4. 数据预热与异步更新：布隆过滤器和BitMap的初始化应该异步进行，避免阻塞业务：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import threading



def warm_up_bloom_filter():

    def _init():

        r = redis.Redis()

        offset = 0

        batch_size = 50000

        while True:

            ids = db.execute(f"SELECT id FROM users ORDER BY id LIMIT {batch_size} OFFSET {offset}")

            if not ids:

                break

            pipe = r.pipeline()

            for row in ids:

                pipe.execute_command('BF.ADD', 'bf:user_ids', str(row['id']))

            pipe.execute()

            offset += batch_size

        print("布隆过滤器预热完成")

    

    thread = threading.Thread(target=_init, daemon=True)

    thread.start()

    return thread

总结

Redis的BitMap、HyperLogLog和布隆过滤器分别解决了大规模数据场景下的不同问题：BitMap以位为单位高效存储布尔状态，适合用户签到和活跃度统计；HyperLogLog以固定12KB内存估算任意规模的基数，是UV统计的不二之选；布隆过滤器用极小的内存代价提供存在性判断，是防止缓存穿透的利器。三者各有适用场景，理解它们的原理、误差特征和性能边界，才能在架构设计中做出正确的选型。在生产环境中，还需要注意大BitMap的位运算阻塞问题、HLL的合并性能、布隆过滤器的容量规划等实际工程细节，才能真正发挥这些数据结构的优势。