Redis 位图与布隆过滤器

位图以极致的内存效率存储海量布尔标记，布隆过滤器以极小内存判断元素是否存在，两者都是高性能大数据场景的利器。

位图核心命令回顾

SETBIT/GETBIT

Bash

# 设置位
SETBIT bitmap:user:signin 1000 1

# 获取位
GETBIT bitmap:user:signin 1000
# 返回: 1 或 0

BITCOUNT统计

Bash

# 统计值为1的位数量
BITCOUNT bitmap:user:signin

# 统计字节范围
BITCOUNT bitmap:user:signin 0 100

BITOP运算

Bash

# 位运算
BITOP AND result bitmap1 bitmap2
BITOP OR result bitmap1 bitmap2

位图应用场景详解

1. 用户签到系统

设计方案

Bash

- 用户ID作为offset
- 签到状态：1签到，0未签到
- 一年签到数据约0.5KB（365位）
- 1亿用户签到约50MB

实现

Bash

# 用户1000在2024年1月1日签到
SETBIT signin:2024:01 1000 1

# 检查签到状态
GETBIT signin:2024:01 1000

# 统计当日签到人数
BITCOUNT signin:2024:01

# 统计用户连续签到天数
BITOP AND result signin:2024:01 signin:2024:02 signin:2024:03
BITCOUNT result

用户个人签到记录

Bash

# 每个用户一个位图，日期为offset
SETBIT user:1000:signin 20240101 1

# 获取用户签到天数
BITCOUNT user:1000:signin

# 获取最近30天签到情况
BITCOUNT user:1000:signin {offset_start} {offset_end}

2. 用户活跃度统计

日活跃用户

Bash

# 记录日活跃用户（用户ID为offset）
SETBIT active:daily:2024:01:01 user_id 1

# 统计日活跃用户数
BITCOUNT active:daily:2024:01:01

# 统计周活跃用户（7天合并）
BITOP OR active:weekly:2024:01 active:daily:2024:01:01 active:daily:2024:01:02 ...
BITCOUNT active:weekly:2024:01

月活跃用户

Bash

# 30天合并
BITOP OR active:monthly:2024:01 active:daily:2024:01:* ...
BITCOUNT active:monthly:2024:01

3. 用户在线状态

实时在线

Bash

# 用户上线
SETBIT online:users user_id 1

# 用户下线
SETBIT online:users user_id 0

# 检查用户在线
GETBIT online:users user_id

# 统计在线人数
BITCOUNT online:users

4. 权限标记

多权限位图

Bash

# 用户权限位图（不同位表示不同权限）
# bit0: 读权限
# bit1: 写权限
# bit2: 删除权限
# bit3: 管理权限

SETBIT user:1000:perms 0 1  # 读权限
SETBIT user:1000:perms 1 1  # 写权限
SETBIT user:1000:perms 3 1  # 管理权限

# 检查权限
GETBIT user:1000:perms 1  # 检查写权限

布隆过滤器原理

布隆过滤器介绍

Python

布隆过滤器：
- 极高效的空间利用率
- 判断元素"可能存在"或"绝对不存在"
- 存在误判率（假阳性），但不会漏判（假阴性）
- 不能删除元素

原理

Python

1. 使用多个哈希函数
2. 每个哈希函数映射到位图的多个位置
3. 添加元素：所有哈希位置设为1
4. 查询元素：所有哈希位置都为1则"可能存在"
5. 任一位置为0则"绝对不存在"

误判率

lua

假阳性：元素未添加但查询返回"可能存在"
原因：其他元素的哈希位置覆盖了查询位置
假阴性：不存在，布隆过滤器不会漏判

Redis布隆过滤器实现

RedisBloom模块

Python

# RedisBloom是Redis的布隆过滤器模块
# 需要单独安装

# 安装后使用BF命令
BF.ADD myfilter item1
BF.EXISTS myfilter item1

手动实现布隆过滤器

基本实现

Python

import mmh3

class BloomFilter:
    def __init__(self, redis, key, capacity, error_rate=0.01):
        self.redis = redis
        self.key = key
        # 计算需要的位数和哈希函数数量
        self.size = self._calculate_size(capacity, error_rate)
        self.hash_count = self._calculate_hash_count(self.size, capacity)

    def add(self, item):
        for seed in range(self.hash_count):
            # 多个哈希函数计算位置
            position = mmh3.hash(str(item), seed) % self.size
            self.redis.setbit(self.key, position, 1)

    def might_contain(self, item):
        for seed in range(self.hash_count):
            position = mmh3.hash(str(item), seed) % self.size
            if self.redis.getbit(self.key, position) == 0:
                return False  # 绝对不存在
        return True  # 可能存在

参数计算

Python

def _calculate_size(self, n, p):
    # 位数 m = -n*ln(p) / (ln(2)^2)
    import math
    m = -n * math.log(p) / (math.log(2) ** 2)
    return int(m)

def _calculate_hash_count(self, m, n):
    # 哈希函数数量 k = m/n * ln(2)
    import math
    k = m / n * math.log(2)
    return int(k)

Lua脚本实现

Python

-- 布隆过滤器添加元素
local key = KEYS[1]
local size = tonumber(ARGV[1])
local hash_count = tonumber(ARGV[2])
local item = ARGV[3]

for i = 0, hash_count - 1 do
    local hash = redis.call('INCR', key .. ':seed') - 1
    local position = tonumber(item) + hash * 31 % size
    redis.call('SETBIT', key, position, 1)
end

return 1

布隆过滤器应用场景

1. 缓存穿透防护

text

# 预热布隆过滤器
def warmup_bloom_filter():
    # 加载所有存在的key到布隆过滤器
    all_keys = db.query_all_keys()
    for key in all_keys:
        bloom_filter.add(key)

# 查询前检查
def get_data(key):
    # 布隆过滤器判断
    if not bloom_filter.might_contain(key):
        return None  # 绝对不存在，直接返回

    # 可能存在，继续查询
    data = redis.get(key)
    if data:
        return data

    data = db.query(key)
    if data:
        redis.set(key, data)
    else:
        # 误判，实际不存在
        redis.set(key, "NULL", ex=60)

    return data

2. URL爬虫去重

text

# 爬虫已访问URL布隆过滤器
def is_visited(url):
    if bloom_filter.might_contain(url):
        return True  # 可能已访问，跳过
    bloom_filter.add(url)
    return False  # 未访问，继续爬取

3. 邮箱/用户名检查

text

# 已注册邮箱布隆过滤器
def check_email_registered(email):
    if bloom_filter.might_contain(email):
        # 可能已注册，需要精确查询数据库
        return db.query_email(email)
    return False  # 绝对未注册

4. 推荐系统去重

text

# 用户已推荐内容布隆过滤器
def should_recommend(user_id, content_id):
    key = f"bloom:recommended:{user_id}"
    if bloom_filter.might_contain(content_id):
        return False  # 已推荐过
    bloom_filter.add(content_id)
    return True  # 未推荐，可以推荐

位图与布隆过滤器对比

特性	位图	布隆过滤器
存储内容	精确标记	多哈希位置
查询结果	精确	可能误判
内存效率	极高	更高
删除支持	支持	不支持
适用场景	精确标记	去重、预判

内存效率对比

存储1亿数据

方式	内存占用	特点
Set存储ID	~200MB+	精确
位图标记	~12.5MB	精确
布隆过滤器(1%误判)	~120MB	可能误判

布隆过滤器在相同误判率下比位图节省内存，但存在误判。

注意事项

位图使用注意

text

- 用户ID必须密集，稀疏ID浪费内存
- 大偏移量会扩展字符串，分配内存
- 位操作是原子性的

布隆过滤器注意

text

- 不能删除元素（影响其他元素的哈希位置）
- 存在误判率，需要接受
- 需要合理设置容量和误判率
- 容量固定，超出会提高误判率

要点总结

位图极省内存，1亿用户标记约12.5MB
用户签到、活跃统计、在线状态、权限标记适合位图
BITCOUNT统计1的位数，BITOP支持AND/OR运算
布隆过滤器判断"可能存在"或"绝对不存在"
布隆过滤器有误判（假阳性），无漏判（假阴性）
缓存穿透防护：布隆过滤器预判，不存在直接返回
爬虫去重、邮箱检查、推荐去重适合布隆过滤器
布隆过滤器不能删除元素，容量超出会提高误判率
位图要求ID密集，稀疏ID浪费内存

📝 发现内容有误？点击此处直接编辑