Redis 技术笔记

主题

第二十一章：布隆过滤器原理与应用 ​

Q65：布隆过滤器是什么？它的原理和工作过程是怎样的？ ​

答：

布隆过滤器（Bloom Filter）是一种概率型数据结构，用来快速判断「某个元素是否一定不在集合中」。它用极小的内存存储海量元素的存在性信息，但代价是存在一定的误判率（false positive）。

一、核心结论（背下来这三条） ​

  1. 判断「一定不存在」是准确的：如果布隆过滤器说「这个元素不存在」，那它一定不存在；
  2. 判断「可能存在」可能误判：如果布隆过滤器说「可能存在」，它可能其实并不存在（误判）；
  3. 不存在漏判（false negative）：真正存在的元素，永远不会被判断为不存在。

所以布隆过滤器的价值在于：用「极小内存 + 极小误判率」替你去挡住绝大部分「一定不存在」的查询，避免它们穿透到底层存储。

二、工作原理：位数组 + 多个哈希 ​

布隆过滤器底层是一个很长的位数组（bit array，初始全 0），加上 k 个独立的哈希函数。

插入元素：

text
插入元素 x：
  h1(x) = 位置 p1
  h2(x) = 位置 p2
  ...
  hk(x) = 位置 pk
  把位数组的第 p1、p2 ... pk 位 全部置为 1

查询元素是否存在：

text
查询元素 y：
  计算 h1(y)、h2(y) ... hk(y)
  ├─ 只要有一个位置是 0 → y 一定不存在
  └─ 所有位置都是 1 → y 可能存在（可能误判）

图解（8 位数组、3 个哈希函数示例）：

text
初始：  [0][0][0][0][0][0][0][0]

插入 "apple"：h1→2，h2→5，h3→7
        [0][0][1][0][0][1][0][1]
              ↑        ↑     ↑

插入 "banana"：h1→2，h2→4，h3→7
        [0][0][1][0][1][1][0][1]
              ↑     ↑  ↑     ↑

查询 "apple"：h1→2，h2→5，h3→7 → 全是 1 → 可能存在（确实存在 ✓）
查询 "cherry"：h1→1，h2→4，h3→6 → 位置 1 和 6 是 0 → 一定不存在 ✓
查询 "durian"：h1→2，h2→4，h3→7 → 全是 1，但 durian 没插入过 → 误判！

「durian」就是误判的例子：它的三个哈希位置（2、4、7）恰好都被其他元素（apple、banana）置 1 了，所以被误判为「可能存在」。

三、为什么可能误判 ​

因为位数组是共享的，多个元素写入时会把各自的位「或」到一起。某个位为 1，可能是被任意一个元素置 1 的，无法区分「到底是哪个元素置的」。当位数不足、元素太多、哈希函数太多时，位数组逐渐被填满，「所有位置恰好都是 1」的概率上升，误判率随之升高。

四、误判率由三个参数决定 ​

布隆过滤器有明确的参数权衡公式：

参数含义增大它，误判率怎么变
m（位数组长度）位数组的总位数m 越大，误判率越低（内存更多）
n（元素数量）预计要存入的元素个数n 越多，误判率越高（更拥挤）
k（哈希函数个数）哈希函数数量存在最优 k，不是越大越好

对给定的 n 和目标误判率 p，可以算出需要的 m 和最优 k：

text
m = -(n * ln p) / (ln 2)^2        # 需要的位数
k = (m / n) * ln 2                # 最优哈希函数个数

直观感受：约 100 万元素、1% 误判率，只约需 1MB 左右位数组，比直接用 Set 存 100 万元素（几十 MB 起）省得多。这正是它的价值。

五、一个重要限制：不支持删除 ​

标准布隆过滤器不能删除元素。因为你把一个元素删除前，如果把它对应的位清零，可能影响其他元素的判断（那一位也可能是别人置的）。需要删除能力时，要用「计数布隆过滤器（Counting Bloom Filter）」，把每个位从 bit 换成计数器。

Q66：布隆过滤器有哪些典型使用场景？用 Redis 怎么实现？ ​

答：

布隆过滤器最大价值是「挡掉一定不存在的查询」，典型用在查询前面加一道内存极省的过滤屏障，保护底层数据库/存储。

一、典型使用场景 ​

场景具体用法收益
防止缓存穿透判断 key 是否可能存在，不存在直接返回，不查 DB挡住恶意/无效 key 对 DB 的攻击
垃圾邮件 / 黑名单过滤判断邮箱/IP 是否在黑名单，不在则放行极小内存存大黑名单
爬虫 URL 去重判断 URL 是否抓过，抓过就跳过海量 URL 用极小内存去重
推荐系统过滤判断内容是否已推荐给用户，已推荐就跳过避免重复推荐
用户名 / 短链唯一性校验注册时判断用户名是否被占用快速预判，命中再回源精确校验
数据库存在性快速判断判断 id 是否可能存在，不存在直接拒绝减少无效查库

二、Redis 里的两种实现方式 ​

方式 1：RedisBloom 模块（推荐）

Redis 官方提供了 RedisBloom 模块（可用 Redis Stack 或单独加载），直接提供布隆过滤器命令：

bash
# 创建布隆过滤器，预计 100000 元素，误判率 0.01
BF.RESERVE user:exists 0.01 100000

# 添加元素
BF.ADD user:exists user:1001

# 判断是否存在（1 = 可能存在，0 = 一定不存在）
BF.EXISTS user:exists user:1001
# 批量判断
BF.MEXISTS user:exists user:1001 user:1002 user:9999

Python（用 redisbloom / redis-py 的扩展）：

python
# 需安装 redisbloom 客户端，或 Redis Stack 环境
redis_client.bf().create("user:exists", 0.01, 100000)
redis_client.bf().add("user:exists", "user:1001")
exists = redis_client.bf().exists("user:exists", "user:1001")

方式 2：用 Bitmap（SETBIT）手动实现

不用额外模块时，可以用 Redis 的 Bitmap 自己搭一个简化布隆过滤器：

python
import hashlib

def bloom_add(key: str, value: str, m: int, k: int):
    for i in range(k):
        h = int(hashlib.md5(f"{value}:{i}".encode()).hexdigest(), 16)
        offset = h % m
        redis_client.setbit(key, offset, 1)

def bloom_exists(key: str, value: str, m: int, k: int) -> bool:
    for i in range(k):
        h = int(hashlib.md5(f"{value}:{i}".encode()).hexdigest(), 16)
        offset = h % m
        if not redis_client.getbit(key, offset):
            return False   # 只要有一位是 0，就肯定不存在
    return True            # 全 1，可能存在

手动实现的哈希函数质量不如 RedisBloom 的（后者内部用了更优的哈希策略），但胜在「只用 Redis 自带命令，不依赖模块」。

三、用布隆过滤器防缓存穿透的完整流程 ​

缓存穿透是指「查询一个数据库里根本不存在的 key」，由于缓存里也没有，每次都会打到数据库。布隆过滤器在所有 key 写入时就同步标记，查询时先过滤：

text
写入流程：
  写入 DB 成功后 ──► BF.ADD 标记该 key「存在」

查询流程：
  请求 key ──► BF.EXISTS 判断
                ├─ 返回 0（一定不存在）→ 直接返回「不存在」，不打缓存不打 DB
                └─ 返回 1（可能存在）  → 正常走 缓存 → DB 流程
python
def query(key: str):
    # 先过布隆过滤器
    if not redis_client.bf().exists("bloom:keys", key):
        return None   # 一定不存在，直接返回，不再查缓存和 DB

    # 可能存在，正常走缓存 + DB
    cached = redis_client.get(f"cache:{key}")
    if cached:
        return cached
    data = query_db(key)
    redis_client.set(f"cache:{key}", data)
    return data

这样，攻击者用大量随机不存在的 key 打过来，绝大部分会在布隆过滤器这层被挡掉，不会穿透到数据库。

四、使用注意事项 ​

  1. 误判是存在的：布隆过滤器说「可能存在」不代表一定存在，命中后仍要回源精确查询（查缓存/DB）确认；
  2. 参数要提前算好：n（预计元素量）和 p（误判率）决定了 m 和 k，建过滤器前要合理预估，避免后期误判率飙升；
  3. 不支持的删除：标准布隆过滤器不能删，数据删改频繁的场景要注意；
  4. 扩容问题：元素量超预期后误判率会上升，可能需要重建或分层布隆过滤器；
  5. 判断结果只是「预筛」：不能拿布隆过滤器当「精确存在性」的唯一依据，重要场景必须回源确认。

Q67：布隆过滤器、HyperLogLog、Count-Min Sketch 这些「概率结构」有什么区别？各自用在什么场景？ ​

答：

这三者都是 Redis Stack 提供的「概率数据结构」，核心思想都是用极小内存，换取一个有界的误差，但解决的具体问题完全不同。

一、解决的问题与结构对比 ​

结构解决的问题能做什么有误差的是哪部分
布隆过滤器（Bloom）判断「元素是否存在」是否存在（有/无）可能把「不存在」误判为「存在」
HyperLogLog统计「不同元素的数量」去重计数（UV）计数结果有约 0.81% 标准误差
Count-Min Sketch统计「元素出现频次」频次估算（热门词、访问次数）频次可能高估，不会低估
Top-K找「最常出现的元素」热点 Top N近似 Top N
Cuckoo Filter类似布隆，但支持删除存在性 + 删除同布隆，但有删除能力
t-digest统计「分位数 / 百分位」P50、P90、P99 延迟分位数近似

二、各结构详解 ​

1. 布隆过滤器：判断存在性

  • 回答的问题：这个元素在不在集合里？
  • 特点：极小内存、可能误判「存在」、不会漏判「不存在」、不支持删除；
  • 场景：防缓存穿透、黑名单、URL 去重、用户名唯一性预检。

2. HyperLogLog：去重计数

  • 回答的问题：集合里去重后有多少个不同元素？
  • 特点：固定约 12KB 内存就能估算上亿的去重数，误差约 0.81%，但不能列出具体是哪些元素；
  • 场景：UV（独立访客数）、独立 IP 数、去重点击量。
bash
PFADD uv:page 1.2.3.4 5.6.7.8
PFCOUNT uv:page        # 去重后的数量（近似）

3. Count-Min Sketch：频次估算

  • 回答的问题：某个元素出现了多少次？
  • 特点：内存固定，频次只会高估不会低估，适合「热度」类需求；
  • 场景：热门搜索词统计、内容热度、访问频次 Top 计算。
bash
CMS.INITBYPROB topk:freq 0.001 0.01
CMS.INCRBY topk:freq itemA 1
CMS.QUERY topk:freq itemA   # 返回估算频次（近似）

4. Top-K：热点 Top N

  • 回答的问题：出现频率最高的 N 个元素是谁？
  • 特点：用极小内存维护近似的 Top N，实时更新；
  • 场景：热搜榜、热门商品、实时热点话题。
bash
TOPK.RESERVE topk:hot 10
TOPK.ADD topk:hot itemA itemB itemC
TOPK.LIST topk:hot     # 返回近似 Top N

三、一句话区分 ​

结构一句话
布隆过滤器判断「在不在」—— 有没有这个元素
HyperLogLog统计「有多少个」—— 去重后的数量
Count-Min Sketch统计「出现几次」—— 元素频次
Top-K找「谁最热」—— 频次最高的元素

四、选型决策 ​

text
要判断元素是否存在 / 做过滤 ──► 布隆过滤器（Cuckoo Filter 如需删除）
要统计去重数量（UV） ──► HyperLogLog
要统计元素频次 / 热度 ──► Count-Min Sketch
要找频次最高的 Top N ──► Top-K
要统计延迟分位数 P99 ──► t-digest

五、共同注意点 ​

  1. 都是「近似」的：结果有误差，不能用于「必须 100% 精确」的场景（如金额、库存）；
  2. 都要预先估算容量：多数概率结构需要根据预期数据量初始化参数；
  3. 属于 Redis Stack：这些命令需要 RedisBloom / Redis Stack，普通开源 Redis 需要额外加载模块或用对应数据结构模拟；
  4. 价值在「省内存」：当数据量巨大、精确结构（Set/Hash）内存吃不消时，才体现它们的优势。

小结 ​

  • 布隆过滤器用「位数组 + 多个哈希」以极小内存判断存在性：一定不存在是准的，可能存在会误判，不支持删除；
  • 典型场景：防缓存穿透、黑名单、URL 去重、唯一性预检；
  • Redis 实现：RedisBloom 的 BF.RESERVE/ADD/EXISTS，或 Bitmap 手动模拟；
  • 概率结构分工：布隆过滤器管「在不在」，HyperLogLog 管「有几个」，CMS 管「几次」，Top-K 管「谁最热」，本质都是用省内存换有界误差。