当前位置： 首页 > ai >正文

数据过滤器

ai 2025/7/5 23:00:07

目录

  • 数据签名算法
    • ✅ Hash（哈希）
      • xxHash
      • MurmurHash3
    • ✅ 加密（Encryption）
    • ✅ 签名（Signature）
  • 内存级别缓存
  • bitmap
    • github.com/RoaringBitmap/roaring
    • https://github.com/kelindar/bitmap
    • 实现一个简单的过滤器
  • bloom
    • github.com/bits-and-blooms/bloom
      • github.com/bits-and-blooms/bitset
      • AddString操作
    • redis 布隆过滤器组件
      • Redis vs Redis Stack vs RedisAI
      • docker部署redis-stack
      • redis命令行文档
        • BF.RESERVE
        • BF.ADD
        • BF.CARD
        • BF.EXISTS
        • BF.INFO
        • BF.INSERT
        • BF.MADD
        • BF.LOADCHUNK
        • BF.SCANDUMP

数据签名算法

通过数据签名，我们可以将奇形怪状的数据转换为长度固定的格式！

在这里插入图片描述

而数据处理常用到的一些概念有：

  • Hash（哈希）：一种将任意长度输入映射为固定长度输出的函数，通常用于快速查找、去重、数据校验等。
  • 加密（Encryption）：一种可以将明文转换为密文，并且在授权条件下可以还原的过程。
  • 签名（Signature）：基于加密 hash 的技术，用于确认数据未被篡改、且确实来自特定的发送者。

✅ Hash（哈希）

一种将任意长度输入映射为固定长度输出的函数，通常用于快速查找、去重、数据校验等。

  • 特点：

    • 输入相同，输出一定相同（确定性）
    • 输出固定长度（例如 64 位、128 位）
    • 小变化会导致结果剧烈变化（雪崩效应）
    • 无法反推出原始数据（不可逆）

  • 用途：

    • 快速过滤、去重（如 Bloom Filter）
    • 数据校验（如 CRC、MD5 校验码）
    • 分布式系统中做分片（Consistent Hash）

  • 示例算法：

    • 快速型：murmur3、xxhash、fnv
    • 安全型（带抗碰撞）：sha256、blake2b

常见哈希算法及对比：

算法类别长度速度抗碰撞性是否适合签名典型用途
FNV-1a快速哈希32/64快弱否哈希表、缓存
Murmur3快速哈希32/128很快中等否Go/Java系统内部、大量文本哈希
xxHash快速哈希64/128极快中等否日志去重、ETL 前处理
CRC32快速哈希32快很弱否网络校验、传输校验
MD5安全哈希128中弱否文件校验（逐渐淘汰）
SHA-1安全哈希160较慢较弱否SSL/TLS（已不再推荐）
SHA-256安全哈希256慢强是区块链、JWT、签名验证
Blake2b安全哈希256-512中强是替代 SHA 系列的现代安全哈希
SimHash指纹哈希64/128中可容忍差异否文本去重、搜索引擎
CityHash快速哈希64/128极快中等否Google 日志处理、搜索系统
MetroHash快速哈希64/128极快中等否高性能数据处理

用法场景：

场景建议算法原因
快速 bitmap 签名判重xxHash / Murmur3极快、输出稳定
数据签名校验（JWT 等）SHA-256 / Blake2安全性强
Redis 位图 key 签名xxHash / CRC32Redis key 要短、哈希速度优先
模糊文本去重 / 相似检测SimHash抽取文本特征，支持容忍差异
分布式缓存、哈希分片Murmur3 / JumpHash分布均匀性优

下面给出摘录出来的牛逼的工业级 Hash 算法（适合高性能/大规模系统）：

  1. 🔸 xxHash
    • 来自 Facebook 工程师，极致速度，低 CPU 消耗
    • 支持 SIMD 向量化指令集优化（xxh3 版本性能炸裂）
    • 应用：数据库、日志系统、数据去重

  1. 🔸 MurmurHash3

    • Google 出品，高速 + 均匀性好，常用于数据结构如 hashmap
    • Java 和 Go 等语言的标准库中经常使用
    • 应用：Kafka、Cassandra、HBase 内部都用过

  1. 🔸 Blake2b

    • 替代 SHA 系列的现代安全哈希，快且安全
    • 在密码学/区块链/签名中被广泛使用
    • 可配置输出长度，兼容性极好

  1. 🔸 CityHash / FarmHash / HighwayHash

    • Google 系列 hash：
      • CityHash：老一代搜索系统使用
      • FarmHash：跨平台优化 + 更好的碰撞特性
      • HighwayHash：使用 SIMD + 更强抗碰撞
    • 应用：日志处理、数据同步、高速缓存分片

xxHash

xxHash 是一种高性能、非加密型哈希算法，由 Yann Collet（@Cyan4973）在 2012 年开发。它的设计目标就是一个字：快！

它比 MD5、SHA 系列快数十倍，甚至比常见的 FNV、CRC32 等算法也快得多，且碰撞率仍保持在可接受范围内。

🔹 核心特点

特性说明
⚡ 极致速度单线程吞吐量可达 GB/s 级别，适合大数据场景
🧠 非加密、无安全性不能用于密码学，但非常适合判重、签名、hash table
🪶 轻量实现无需依赖复杂加密库，纯算法逻辑，易于移植
📦 多语言支持官方提供 C 实现，Go、Java、Python、Rust 等语言都有高质量移植版本
🔁 多种版本提供 xxh32, xxh64, xxh3_64, xxh3_128 等多种哈希输出长度选择

🔹 常见版本对比

版本位数特点推荐用途
xxh3232老版本，轻量级，但碰撞率稍高嵌入式系统，小数据量哈希
xxh6464主流版本，速度快，碰撞率低数据签名、日志判重、缓存 Key 等
xxh3_6464最新版本，极快，SIMD 优化大数据量、长字符串处理、性能优先场景
xxh3_128128支持 128 位哈希，抗碰撞性更好唯一标识符、高密度去重、大型数据索引场景

🔹 性能测试（vs 常见哈希）数据来源：官方 Benchmark

算法速度（GB/s）相对性能
xxh3_6445+ GB/s🚀🚀🚀🚀🚀
xxh6415 GB/s🚀🚀🚀
murmur34~5 GB/s🚀
sha10.7 GB/s🐌
md50.3 GB/s🐌

🔹 在工程中的应用场景

场景应用方式
Bitmap/Bloom 过滤使用 xxHash64 签名作为偏移位索引
消息去重用 xxHash 签名比对新消息是否已经存在
日志采样与聚合大量日志用 xxh3_64 做快速归类
分布式缓存 sharding基于 xxHash 将 Key 均匀分布在多个节点上
数据校验/传输比对xxh3_128 可作为轻量级文件或分块的指纹

🔹 Go 语言支持推荐

  • ✅ 推荐库：cespare/xxhash（Go 工程中的首选）
    • Go 原生实现，无需 CGO
    • 支持 Sum64(data []byte) 快速调用
  • ✅ 高性能替代：zeebo/xxh3
    • 实现 xxh3，更快更现代，适合处理大数据集

我们在go package搜索xxHash，

在这里插入图片描述

然后下载最高star的一个：go get github.com/cespare/xxhash/v2

给出使用案例：

package hashximport ("bufio""github.com/cespare/xxhash/v2""io""sync"
)var xxhashPool = sync.Pool{New: func() any {return xxhash.New()},
}func getXXHash() *xxhash.Digest {h := xxhashPool.Get().(*xxhash.Digest)h.Reset()return h
}func putXXHash(h *xxhash.Digest) {xxhashPool.Put(h)
}func XXHash(v []byte) uint64 {return xxhash.Sum64(v)
}func XXHashString(v string) uint64 {return xxhash.Sum64String(v)
}func XXHashStrings(v ...string) uint64 {h := getXXHash()defer putXXHash(h)for _, chunk := range v {_, _ = h.WriteString(chunk)}// go的return是3步走的// 1. returned = return 返回值变量复制// 2. defer() defer栈调用// 3. return returned 返回值return h.Sum64()
}func XXHashReader(reader io.Reader) uint64 {const bufSize = 4096bufReader := bufio.NewReaderSize(reader, bufSize)buffer := make([]byte, bufSize)h := getXXHash()defer putXXHash(h)for {n, err := bufReader.Read(buffer)if n > 0 {_, _ = h.Write(buffer[:n])}if err == io.EOF {break}if err != nil {panic(err)}}return h.Sum64()
}

给出单测/benchmark：

package hashximport ("bytes""strings""testing"
)func TestXXHashString(t *testing.T) {v := "hello world"h1 := XXHashString(v)h2 := XXHash([]byte(v))if h1 != h2 {t.Errorf("Hash mismatch: XXHashString=%d, XXHash=%d", h1, h2)}
}func TestXXHashStrings(t *testing.T) {parts := []string{"hello", " ", "world"}h1 := XXHashStrings(parts...)h2 := XXHashString(strings.Join(parts, ""))if h1 != h2 {t.Errorf("Hash mismatch: XXHashStrings=%d, XXHashString(joined)=%d", h1, h2)}
}func TestXXHashReader(t *testing.T) {data := "hello world from reader"buf := bytes.NewBufferString(data)h1 := XXHashReader(buf)h2 := XXHashString(data)if h1 != h2 {t.Errorf("Hash mismatch: XXHashReader=%d, XXHashString=%d", h1, h2)}
}func BenchmarkXXHashString(b *testing.B) {data := "hello world"for i := 0; i < b.N; i++ {_ = XXHashString(data)}
}func BenchmarkXXHashStrings(b *testing.B) {parts := []string{"hello", " ", "world", " from ", "cespare"}for i := 0; i < b.N; i++ {_ = XXHashStrings(parts...)}
}func BenchmarkXXHash(b *testing.B) {data := []byte("hello world from []byte")for i := 0; i < b.N; i++ {_ = XXHash(data)}
}func BenchmarkXXHashReader(b *testing.B) {data := []byte(strings.Repeat("benchmark", 100)) // ~1KBfor i := 0; i < b.N; i++ {reader := bytes.NewReader(data)_ = XXHashReader(reader)}
}func BenchmarkXXHashReaderBig(b *testing.B) {data := []byte(strings.Repeat("data-bucket-large-", 1024*1024)) // ~20MBb.ResetTimer()for i := 0; i < b.N; i++ {reader := bytes.NewReader(data)_ = XXHashReader(reader)}
}

结果：

cpu: AMD Ryzen 7 6800H with Radeon Graphics         
BenchmarkXXHashString
BenchmarkXXHashString-16       	138831620	         8.547 ns/op
BenchmarkXXHashStrings
BenchmarkXXHashStrings-16      	 7997679	       149.7 ns/op
BenchmarkXXHash
BenchmarkXXHash-16             	157724559	         7.504 ns/op
BenchmarkXXHashReader
BenchmarkXXHashReader-16       	  688735	      1757 ns/op
BenchmarkXXHashReaderBig
BenchmarkXXHashReaderBig-16    	     592	   1991434 ns/op

MurmurHash3

MurmurHash3 是一款非加密、快速、高质量的哈希函数，常用于：

  • 哈希表（如 Redis dict/hash map）
  • Bloom Filter、HyperLogLog 等 probabilistic data structures
  • 分布式系统中的哈希分片

它由 Austin Appleby 开发（Google 出身），属于 非加密哈希算法（即不适用于安全相关领域，但非常快）。

非加密哈希算法（Non-cryptographic Hash Function），指的是那些只关注性能和散列分布质量，而不关注安全性的哈希算法。

// 非加密哈希（murmur3/xxhash）
xxhash.Sum64([]byte("hello world")) // 8ns 左右
murmur3.Sum64([]byte("hello world"))// 加密哈希（SHA256）
sha256.Sum256([]byte("hello world")) // 500~1000ns

其次是安全性：

targetHash := uint32(0xDEADBEEF)
for i := 0; ; i++ {if murmur3.Sum32([]byte(strconv.Itoa(i))) == targetHash {fmt.Println("Found input:", i)break}
}

这在加密哈希（SHA256）上是不可想象的，因为它需要千万年，但 murmur3 里几分钟可能就撞出来了。

✨ 特点

特性描述
非加密哈希无法用于加密或签名，但速度非常快
雪崩效应良好输入略变则输出完全不同，避免碰撞
多平台一致性保证不同语言/平台上结果一致
支持 32bit 和 128bit常用的有 MurmurHash3_x86_32 和 MurmurHash3_x64_128

Go 官方库没有内建 MurmurHash，但有很多优秀的第三方库可用：spaaace/murmur3

Star 数：2.1k+ 质量非常高，广泛用于生产环境。支持 Sum32, Sum64, Sum128，且无依赖、易于使用。

go get github.com/spaolacci/murmur3

给出使用案例：

package hashximport "github.com/spaolacci/murmur3"func MurmurHash32(v []byte) uint32 {return murmur3.Sum32(v)
}func MurmurHashString32(v string) uint32 {return MurmurHash32([]byte(v))
}func MurmurHash64(v []byte) uint64 {return murmur3.Sum64(v)
}func MurmurHashString64(v string) uint64 {return MurmurHash64([]byte(v))
}func MurmurHash128(v []byte) (uint64, uint64) {return murmur3.Sum128(v)
}func MurmurHashString128(v string) (uint64, uint64) {return MurmurHash128([]byte(v))
}

给出单测/benchmark：

package hashximport "testing"func TestMurmurHash(t *testing.T) {data := []byte("hello world")if MurmurHash32(data) == 0 {t.Error("MurmurHash32 returned zero")}if MurmurHashString32("hello world") == 0 {t.Error("MurmurHashString32 returned zero")}if MurmurHash64(data) == 0 {t.Error("MurmurHash64 returned zero")}if MurmurHashString64("hello world") == 0 {t.Error("MurmurHashString64 returned zero")}h1, h2 := MurmurHash128(data)if h1 == 0 && h2 == 0 {t.Error("MurmurHash128 returned zero pair")}h3, h4 := MurmurHashString128("hello world")if h3 == 0 && h4 == 0 {t.Error("MurmurHashString128 returned zero pair")}
}var testBytes = []byte("the quick brown fox jumps over the lazy dog")
var testStr = "the quick brown fox jumps over the lazy dog"func BenchmarkMurmurHash32(b *testing.B) {for i := 0; i < b.N; i++ {MurmurHash32(testBytes)}
}func BenchmarkMurmurHashString32(b *testing.B) {for i := 0; i < b.N; i++ {MurmurHashString32(testStr)}
}func BenchmarkMurmurHash64(b *testing.B) {for i := 0; i < b.N; i++ {MurmurHash64(testBytes)}
}func BenchmarkMurmurHashString64(b *testing.B) {for i := 0; i < b.N; i++ {MurmurHashString64(testStr)}
}func BenchmarkMurmurHash128(b *testing.B) {for i := 0; i < b.N; i++ {MurmurHash128(testBytes)}
}func BenchmarkMurmurHashString128(b *testing.B) {for i := 0; i < b.N; i++ {MurmurHashString128(testStr)}
}

结果：

cpu: AMD Ryzen 7 6800H with Radeon Graphics         
BenchmarkMurmurHash32
BenchmarkMurmurHash32-16           	100000000	        10.93 ns/op
BenchmarkMurmurHashString32
BenchmarkMurmurHashString32-16     	100000000	        10.69 ns/op
BenchmarkMurmurHash64
BenchmarkMurmurHash64-16           	91395146	        12.77 ns/op
BenchmarkMurmurHashString64
BenchmarkMurmurHashString64-16     	29730547	        39.35 ns/op
BenchmarkMurmurHash128
BenchmarkMurmurHash128-16          	85256336	        13.11 ns/op
BenchmarkMurmurHashString128
BenchmarkMurmurHashString128-16    	31526098	        39.32 ns/op

🆚 与 xxHash 对比：

特性MurmurHash3xxHash
速度快（但比 xxHash 略慢）极快（近乎 C 语言极限）
质量高，抗碰撞强高，适用于非安全场景
加密性❌ 无❌ 无
流式支持✅ 有✅ 有
Go 实现质量高（spaolacci）高（cespare）
最佳用途Bloom, 去重逻辑日志、KV、哈希表等高频场景

✅ 加密（Encryption）

一种可以将明文转换为密文，并且在授权条件下可以还原的过程。

  • 特点：

    • 可逆，解密后可以还原出原文
    • 通常需要密钥
    • 可对称（一个密钥）或非对称（公钥加密，私钥解密）

  • 用途：

    • 数据传输加密（HTTPS）
    • 文件加密、数据库加密
    • 身份认证和安全通信

  • 典型算法：

    • 对称加密：AES、DES
    • 非对称加密：RSA、ECC

✅ 签名（Signature）

基于加密 hash 的技术，用于确认数据未被篡改、且确实来自特定的发送者。

  • 特点：

    • 不一定能还原数据，但能校验“谁发的”和“内容是否被改”
    • 通常使用私钥签名、对应公钥验证（非对称加密）

  • 用途：

    • 数字身份认证（如 JWT）
    • 代码签名、软件发布认证
    • 区块链中的交易签名

  • 过程概述：

    签名者用私钥对 Hash(data) 进行签名 → 接收方用公钥验证签名

内存级别缓存

在 Go 语言中，内存级别的缓存有很多优秀的库和工具，这些库可以帮助开发者高效地管理内存数据缓存，特别适用于高性能的应用。下面是一些非常牛逼的内存缓存库，它们在性能、易用性和功能上都有出色的表现。

🏆 1. dgraph-io/ristretto - 高性能的内存缓存

  • 简介：ristretto 是一个高性能的 Go 内存缓存库，它非常注重性能优化，支持多核并发，采用了现代的缓存淘汰策略（例如 LRU 和加权计数）。

  • 特点：

    • 高效的内存使用。
    • 支持并发操作，能够充分利用多核 CPU。
    • 支持加权缓存，适用于需要自定义缓存策略的场景。
    • 性能非常好，适合高并发应用。

  • 适用场景：当你需要非常高效且低延迟的内存缓存，并且对内存使用有严格要求时，ristretto 是一个非常好的选择。

    package mainimport ("fmt""log""github.com/dgraph-io/ristretto/v2"
)func main() {// Create a new cachecache, err := ristretto.NewCache(&ristretto.Config{NumCounters: 1e7, // Number of keys to track frequency of (10 million).MaxCost:     1 << 30, // Maximum cost of cache (1 GB).BufferItems: 64, // Number of items to buffer when adding to the cache.})if err != nil {log.Fatal(err)}// Set a value in the cachecache.Set("key", "value", 1)// Get a value from the cachevalue, found := cache.Get("key")if found {fmt.Println(value)} else {fmt.Println("Key not found")}
}

🏅 2. golang/groupcache - 内存级缓存与分布式缓存

  • 简介：groupcache 是一个由 Google 开发的缓存库，它最初用于分布式缓存，但也可以作为一个非常高效的内存缓存使用。它支持缓存一致性哈希和内存优化，适合于高并发、高性能场景。

  • 特点：

    • 高效的内存缓存。
    • 支持分布式缓存和一致性哈希。
    • 能够自动处理缓存的填充和更新，避免缓存穿透。

  • 适用场景：适合需要高并发和内存级缓存的场景，特别是当你有分布式缓存需求时，groupcache 非常合适。

    package mainimport ("fmt""log""github.com/golang/groupcache"
)var cache *groupcache.Groupfunc main() {cache = groupcache.NewGroup("example", 64<<20, groupcache.GetterFunc(func(ctx groupcache.Context, key string, dest groupcache.Sink) error {dest.SetString("This is a cached value: " + key)return nil}))var result stringerr := cache.Get(nil, "key1", &result)if err != nil {log.Fatal(err)}fmt.Println(result)
}

🥇 3. patrickmn/go-cache - 简单的内存缓存

  • 简介：go-cache 是一个简单易用的内存缓存库，支持设置缓存过期时间，并且支持自动清理过期缓存。适合用于简单的缓存需求。

  • 特点：

    • 极其简单易用，适合轻量级应用。
    • 支持自动过期和缓存清理功能。
    • 线程安全，支持并发读写。

  • 适用场景：适用于中小型项目，短生命周期缓存和非分布式的场景。

    package mainimport ("fmt""time""github.com/patrickmn/go-cache"
)func main() {c := cache.New(5*time.Minute, 10*time.Minute)c.Set("foo", "bar", cache.DefaultExpiration)value, found := c.Get("foo")if found {fmt.Println(value)} else {fmt.Println("Key not found")}
}

bitmap

Bitmap（位图） 是一种非常高效的数据结构，用于表示集合中的元素是否存在。它本质上是一个位数组，每个位（bit）对应集合中的一个元素，并且每个元素可以是存在（1）还是不存在（0）。由于其使用的是位级存储，因此可以非常节省空间，特别适用于需要判断大规模数据是否存在的场景。

Bitmap 的应用场景

  1. 集合去重：可以使用位图来表示一个非常大的集合，通过设置对应位置的位来判断是否存在某个元素。
  2. 成员判断：利用位图快速判断某个元素是否在集合中，适用于大量的判定任务。
  3. 大规模数据统计：例如，判断某个用户是否访问过某个页面、某个事件是否发生过等，适用于日志分析和行为追踪。
  4. Bloom Filter：位图是布隆过滤器（Bloom Filter）这种数据结构的基础。

Bitmap 的工作原理非常简单：

  • 每个元素通过哈希函数映射到位图中的某个位置。
  • 如果要将元素插入到集合中，就将对应位置的位设置为1（表示该元素存在）。
  • 如果要检查某个元素是否存在，就检查它对应的位置是否为1。

优点与缺点

优点：

  • 节省内存：Bitmap 可以使用少量内存表示大量的数据，尤其是当数据的范围非常大时，位图依然能保持较小的内存开销。
  • 高效查询：查询某个元素是否存在的操作时间复杂度为O(1)，非常高效。
  • 并发友好：对于并发访问和修改，位图可以高效处理。

缺点：

  • 空间浪费：如果集合中的元素分布稀疏，位图会浪费大量的内存。
  • 无法删除元素：传统的位图结构不能支持删除操作，因为一旦某个位被设置为1，就无法重置为0（会产生误判）。
  • 需要预估空间大小：需要知道最大值范围，才能预先确定位图的大小。

使用位图的高级场景：

  1. 去重：通过位图可以避免重复计算。例如，在处理大量用户访问日志时，使用位图可以快速统计有多少个用户访问过某个页面。
  2. 大规模唯一用户统计：通过位图统计唯一用户的数量，可以快速判断某个用户是否已经在某个活动中注册，避免重复。
  3. HyperLogLog：位图也被用于 HyperLogLog 算法，它是一种高效的基数估计算法，能够估算集合中不重复元素的数量。

在 Go 语言中，有多种高效的位图（Bitmap）实现，适用于不同的场景，如高性能数据处理、内存优化和并发访问等。以下是一些值得关注的优秀位图库：

1. github.com/kelindar/bitmap

  • 简介：这是一个高性能的位图实现，专为密集型小到中型数据集设计。
  • 特点：
    • 使用 []uint64 切片作为底层存储，避免堆分配，提升性能。
    • 通过汇编实现 SIMD 矢量化，进一步加速位操作。
    • 支持布尔代数运算，如 AND、OR、XOR 等。
    • 提供高效的位计数和搜索功能，如 Count()、Min()、Max() 等。
  • 适用场景：适用于需要高性能位操作的场景，如实时数据处理和内存存储。

2. github.com/boljen/go-bitmap

  • 简介：这是一个线程安全的位图库，支持并发访问。
  • 特点：
    • 提供了多种位图类型，如普通位图、并发位图和线程安全位图。
    • 支持原子操作，确保在并发环境下的安全性。
    • 提供了丰富的位操作接口，如 Set()、Get()、Len() 等。
  • 适用场景：适用于需要在多线程环境中安全操作位图的场景。

3. github.com/RoaringBitmap/roaring

  • 简介：这是一个基于 Roaring 位图算法的实现，提供压缩的位图表示。
  • 特点：
    • 支持高效的位图压缩，节省内存空间。
    • 提供了与 Java 和 C/C++ 版本的二进制兼容性。
    • 支持高效的位操作，如 Union()、Intersect()、Difference() 等。
  • 适用场景：适用于需要处理大规模数据集并节省内存的场景。

4. github.com/zentures/bitmap

  • 简介：这是一个实现了增强型字对齐混合（EWAH）位图压缩算法的库。
  • 特点：
    • 提供了位图压缩功能，减少内存占用。
    • 支持多种位图压缩算法的实现。
    • 提供了与其他语言版本的兼容性。
  • 适用场景：适用于需要压缩位图以节省内存的场景。

选择建议

  • 高性能且无堆分配：推荐使用 kelindar/bitmap。
  • 线程安全和并发支持：推荐使用 boljen/go-bitmap。
  • 大规模数据集和内存压缩：推荐使用 RoaringBitmap/roaring 或 zentures/bitmap。

github.com/RoaringBitmap/roaring

github.com/RoaringBitmap/roaring 是 Go 语言中实现 Roaring 位图（Roaring Bitmap）的高效库。​Roaring 位图是一种压缩的位图数据结构，适用于表示和操作大规模整数集合，特别是在内存和性能方面具有优势。

Roaring 位图采用分段存储策略，将整数集合划分为多个段，每个段使用不同的容器类型（如 ArrayContainer、BitmapContainer、RunContainer）存储数据。​这种设计使得在内存和性能之间取得良好的平衡。

在这里插入图片描述
RoaringBitmap 的一个显著优势是无需预先定义大小，它会根据添加的元素自动扩容。​其底层采用分段存储策略，将整数集合划分为多个段（每个段表示 2^16 个整数），每个段使用不同的容器类型（如 ArrayContainer、BitmapContainer、RunContainer）存储数据。​这种设计使得在内存和性能之间取得良好的平衡。​

当添加的元素超出当前范围时，RoaringBitmap 会自动创建新的容器来存储这些元素，无需手动扩容。​因此，您可以放心地添加任意范围的整数，RoaringBitmap 会自动处理存储和扩容。

对于内存体积使用，RoaringBitmap 提供了 GetSizeInBytes() 方法，用于估算当前位图的内存占用。​通过定期调用此方法，可以监控内存使用情况，并在达到预设阈值时采取相应措施，例如清理数据或触发垃圾回收。

size := bitmap.GetSizeInBytes()
if size > yourThreshold {// 执行清理或其他操作
}

其次，从 Go 1.19 开始，标准库引入了 runtime/debug.SetMemoryLimit() 函数，允许开发者设置程序的最大内存使用限制。​当程序的内存使用接近该限制时，Go 的垃圾回收器将更频繁地运行，以控制内存占用。

import "runtime/debug"func init() {// 设置最大内存限制为 1GBdebug.SetMemoryLimit(1 << 30)
}

安装：go get github.com/RoaringBitmap/roaring/v2

使用方法：

package bitmapximport ("github.com/RoaringBitmap/roaring/v2/roaring64""sync"
)type RoaringBitMap64 struct {m *sync.RWMutexb *roaring64.Bitmap
}func NewRoaringBitMap64() *RoaringBitMap64 {return &RoaringBitMap64{m: new(sync.RWMutex),b: roaring64.New(),}
}

这是一种最粗糙直接的使用方式，其他解决思路是分片而降低锁的粒度：

type ShardedBitmap struct {shards []struct {mu sync.RWMutexbm *roaring.Bitmap}shardCount int
}func NewShardedBitmap(shardCount int) *ShardedBitmap {shards := make([]struct {mu sync.RWMutexbm *roaring.Bitmap}, shardCount)for i := range shards {shards[i].bm = roaring.New()}return &ShardedBitmap{shards:     shards,shardCount: shardCount,}
}func (s *ShardedBitmap) getShard(value uint32) int {return int(value) % s.shardCount
}func (s *ShardedBitmap) Add(value uint32) {shard := s.getShard(value)s.shards[shard].mu.Lock()defer s.shards[shard].mu.Unlock()s.shards[shard].bm.Add(value)
}func (s *ShardedBitmap) Contains(value uint32) bool {shard := s.getShard(value)s.shards[shard].mu.RLock()defer s.shards[shard].mu.RUnlock()return s.shards[shard].bm.Contains(value)
}

其次，虽然 github.com/RoaringBitmap/roaring 本身不是线程安全的，但可以使用其他线程安全的封装库，如 github.com/orcaman/concurrent-map，将 RoaringBitmap 封装在一个线程安全的 map 中，以实现并发访问。

import ("github.com/RoaringBitmap/roaring/v2/roaring64"cmap "github.com/orcaman/concurrent-map/v2"
)type RoaringBitMap64 struct {shards cmap.ConcurrentMap[string, *roaring64.Bitmap]
}func NewRoaringBitMap64() *RoaringBitMap64 {return &RoaringBitMap64{shards: cmap.New[*roaring64.Bitmap](),}
}func (cb *ConcurrentBitmap) Add(key string, value uint32) {item, ok := cb.shards.Get(key)if !ok {rb := roaring.New()rb.Add(value)cb.shards.Set(key, rb)} else {rb := item.(*roaring.Bitmap)rb.Add(value)}
}func (cb *ConcurrentBitmap) Contains(key string, value uint32) bool {item, ok := cb.shards.Get(key)if !ok {return false}rb := item.(*roaring.Bitmap)return rb.Contains(value)
}

https://github.com/kelindar/bitmap

kelindar/bitmap 是一个高性能的 Go 语言位图（bitset）库，专为处理密集型小到中等规模的数据集合而设计。该库通过以下技术手段实现了卓越的性能：

  • 零堆分配：所有关键方法都避免了堆内存分配，减少了 GC 压力。
  • SIMD 向量化：利用汇编实现的 SIMD 指令，加速布尔运算和位计数等操作。
  • 循环展开：通过展开循环，提高了迭代和过滤操作的效率。
  • 布尔代数支持：支持与（AND）、或（OR）、异或（XOR）、非（NOT）等布尔运算，适用于构建复杂的位图索引。
  • 快速位计数与搜索：提供高效的位计数（如 Count()）和搜索（如 Min()、Max()）功能。

这些特性使得 kelindar/bitmap 特别适用于需要高性能位图操作的场景，如数据库索引、实时数据处理、内存存储管理等。

以下是一个基本的使用示例，展示了如何创建位图、设置位、检查位是否存在以及执行布尔运算：

package mainimport ("fmt""github.com/kelindar/bitmap"
)func main() {// 创建一个新的位图var bm = bitmap.Bitmap// 设置位bm.Set(10)bm.Set(20)bm.Set(30)// 检查某个位是否存在fmt.Println("Contains 20:", bm.Contains(20)) // 输出: truefmt.Println("Contains 25:", bm.Contains(25)) // 输出: false// 位图计数fmt.Println("Count:", bm.Count()) // 输出: 3// 创建另一个位图other := bitmap.New()other.Set(20)other.Set(40)// 执行布尔运算bm.And(other) // 交集fmt.Println("After AND operation, Count:", bm.Count()) // 输出: 1
}

kelindar/bitmap 适用于多种需要高效位图操作的场景，包括但不限于：

  • 数据库索引：在列式存储中，使用位图索引可以快速过滤和查询数据。
  • 实时数据处理：在实时数据处理系统中，位图可以用于高效的数据过滤和聚合。
  • 内存存储管理：在内存存储系统中，位图可以用于管理数据的可用性和占用情况。
  • 数据分析：在数据分析中，位图可以用于快速的数据集操作和统计。

对于容量控制，kelindar/bitmap 使用 []uint64 作为底层存储结构，初始时并不分配固定大小的内存。当设置的位超出当前容量时，库会自动扩展底层切片的容量，以容纳新的位。

在这里插入图片描述
扩展策略采用指数增长方式，确保在需要时快速扩展，同时避免频繁的内存分配。

实现一个简单的过滤器

前面我们提到xxHash 和 MurmurHash3 是高性能的非加密哈希函数，这类hash函数的设计特点就是：

  • 设计目的：非加密哈希函数（如 xxHash 和 MurmurHash3）主要用于提高数据处理速度，适用于哈希表、布隆过滤器等数据结构。
  • 抗碰撞性：这些函数不具备强抗碰撞性，攻击者可以通过构造特定输入，导致哈希冲突，从而可能引发性能问题或安全漏洞。
  • 哈希长度：较短的哈希长度（如 32 位或 64 位）增加了碰撞的可能性。

为了避免数据计算得到相同位，就需要多次哈希，生成多个位置，比如index1,index2，当取值的时候这两个位置同时为1才证明该值真的存在！

在这里插入图片描述

首先来看下双重哈希（Double Hashing）：双重哈希是一种在哈希表中解决冲突的方法，它使用两个不同的哈希函数来计算元素的哈希值，从而生成多个探查序列（Kirsch 和 Mitzenmacher 提出了一种优化方法，只需使用两个哈希函数 h1(x) 和 h2(x)）。​具体地，对于一个元素 x，使用两个哈希函数 h1(x) 和 h2(x)，生成第 i 个哈希值：

gi(x) = h1(x) +ih2(x) mod p,

这种方法可以有效地减少哈希冲突，提高哈希表的性能。

package mainimport ("hash/fnv""math"
)type BloomFilter struct {bitset []boolsize   uintk      uint
}func NewBloomFilter(n uint, p float64) *BloomFilter {m := uint(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))k := uint(math.Round((float64(m) / float64(n)) * math.Ln2))return &BloomFilter{bitset: make([]bool, m),size:   m,k:      k,}
}func (bf *BloomFilter) Add(item string) {h1 := fnv.New64a()h1.Write([]byte(item))hash1 := h1.Sum64()h2 := fnv.New64()h2.Write([]byte(item))hash2 := h2.Sum64()for i := uint(0); i < bf.k; i++ {combinedHash := (hash1 + uint64(i)*hash2) % uint64(bf.size)bf.bitset[combinedHash] = true}
}func (bf *BloomFilter) Contains(item string) bool {h1 := fnv.New64a()h1.Write([]byte(item))hash1 := h1.Sum64()h2 := fnv.New64()h2.Write([]byte(item))hash2 := h2.Sum64()for i := uint(0); i < bf.k; i++ {combinedHash := (hash1 + uint64(i)*hash2) % uint64(bf.size)if !bf.bitset[combinedHash] {return false}}return true
}

​FNV（Fowler–Noll–Vo）是一种非加密型哈希算法，由 Glenn Fowler、Landon Curt Noll 和 Phong Vo 于 1991 年提出。​该算法设计简洁、计算速度快，特别适用于对大量数据进行快速哈希处理，同时保持较低的冲突率。​FNV 哈希函数在处理相似字符串（如 URL、文件名、IP 地址等）时表现出良好的分散性，因此被广泛应用于哈希表、数据去重、布隆过滤器等场景中。

bloom

1970 年，布顿·霍华德·布隆（Burton Howard Bloom）为了在拼写检查器中检查一个英语单词是否在字典里，创建了布隆过滤器这一高效的数据结构。它的核心由一个包含 ( m ) 位的位数组和 ( k ) 个哈希函数组成，基本操作如下：

  • 初始化：
    开始时，布隆过滤器是一个包含 ( m ) 位的数组，每一位都设置为 0。

  • 添加元素：
    将某个元素添加到布隆过滤器中时，首先使用 ( k ) 个哈希函数对该元素进行哈希处理，生成 ( k ) 个数组位置索引。随后，将这些位置上的位都设置为 1。

  • 查询元素：
    要检查一个元素是否在布隆过滤器中，同样使用 ( k ) 个哈希函数对其进行哈希处理，得到 ( k ) 个索引。如果这些索引对应的位置全部为 1，则元素可能存在于集合中；如果有任意一位为 0，则元素一定不在集合中。

从上述过程可以看出，无论集合中已有多少元素，添加或查询一个元素的时间都是固定的 ( O(k) )，这意味着操作效率非常高。与其他表示集合的数据结构（如哈希表、平衡二叉树、跳表等）相比，布隆过滤器不仅查找速度快，而且空间效率也非常高。它不需要存储元素本身，从而节省了大量空间。

不过，布隆过滤器也存在缺点。由于多个元素可能被映射到相同的位置，布隆过滤器的查询结果存在误判的可能。假设某个 key 并不在集合中，但其哈希结果与其他已存在元素的哈希结果发生了重叠，那么布隆过滤器就会错误地判断该 key 存在于集合中。这种现象被称为假阳性（False Positive）。

当一个元素实际上并不在集合中，而布隆过滤器却判断其存在的概率，即为假阳性率（false positive rate）。直观来说，在哈希函数数量 ( k ) 固定的前提下，位数组大小 ( m ) 越大，发生哈希碰撞的概率越小，假阳性率也就越低。

因为有概率存在这样的 key，它们内容不同，但多次 Hash 后的 Hash 值都相同，所以对于 BloomFilter 判断不存在的 key ，则是 100% 不存在的，反证法，如果这个 key 存在，那它每次 Hash 后对应的 Hash 值位置肯定是 1，而不会是 0。布隆过滤器判断存在不一定真的存在。

这里先简单推导一下布隆过滤器误差率计算，假设布隆过滤器使用的位数组大小为 m m m，哈希函数的数量为 k k k，并且已经向过滤器中添加了 n n n 个元素。由于我们使用的哈希函数是理想的、均匀随机的，因此可以假设它们以相等的概率选取数组中的位置。

当插入一个元素时，某个位被某个哈希函数设置为 1 1 1 的概率为：

1 m \frac{1}{m} m1​

那么，某个位未被该哈希函数设置为 1 1 1 的概率为：

1 − 1 m 1 - \frac{1}{m} 1−m1​

由于总共有 k k k 个相互独立的哈希函数，某个位未被任何一个哈希函数设置为 1 1 1 的概率为：

( 1 − 1 m ) k \left(1 - \frac{1}{m} \right)^k (1−m1​)k

此时，我们引入自然对数 e e e 的一个极限恒等式：

lim ⁡ m → ∞ ( 1 − 1 m ) m = 1 e \lim_{m \to \infty} \left(1 - \frac{1}{m} \right)^m = \frac{1}{e} m→∞lim​(1−m1​)m=e1​

所以当 m m m 较大时，可以近似地表示为：

( 1 − 1 m ) k ≈ e − k / m \left(1 - \frac{1}{m} \right)^k \approx e^{-k/m} (1−m1​)k≈e−k/m

接下来考虑向布隆过滤器中插入了 n n n 个元素，那么某个位始终未被设置为 1 1 1 的概率为：

( 1 − 1 m ) k n ≈ e − k n / m \left(1 - \frac{1}{m} \right)^{kn} \approx e^{-kn/m} (1−m1​)kn≈e−kn/m

于是，某个位最终被设置为 1 1 1 的概率是：

1 − ( 1 − 1 m ) k n ≈ 1 − e − k n / m 1 - \left(1 - \frac{1}{m} \right)^{kn} \approx 1 - e^{-kn/m} 1−(1−m1​)kn≈1−e−kn/m

那么，假设某个元素不在集合中，但其哈希得到的 k k k 个位置全部为 1 1 1，也就是说发生假阳性的概率为：

( 1 − e − k n / m ) k \left(1 - e^{-kn/m} \right)^k (1−e−kn/m)k

通过上面的推导可以看出，布隆过滤器的假阳性率与以下三个参数密切相关：

  • 哈希函数的数量 k k k
  • 位数组的大小 m m m
  • 插入的元素数量 n n n

其中， n n n 通常由应用场景决定，表示预期将要插入布隆过滤器的元素总数。这一值一般由外部系统或需求推导得出，因此不易调整。

增大 m m m 可以有效降低假阳性率，但也会增加内存占用。在存储资源受限的场景下， m m m 不可能无限制地增大。此外，扩大 m m m 带来的收益是线性递减的，所以需要权衡性能与成本之间的平衡。

相比之下，调整 k k k 对误判率的影响更为显著，因为它直接影响了位数组中有多少位会被设置为 1，从而改变了哈希碰撞的概率。

综合考虑，在实际应用中：

  • n n n 由使用场景决定，无法调整；
  • m m m 受限于系统资源，调整空间有限；
  • k k k 则成为一个直接可控的优化手段。

那么问题就转化为：在已知 n n n 和 m m m 的情况下，如何选择一个最优的 k k k，以最小化假阳性率？这个问题可以通过数学分析优化求解，虽然过程较为复杂，但结论是明确的。最优哈希函数数量 k k k 为：

k = m n ln ⁡ 2 k = \frac{m}{n} \ln 2 k=nm​ln2

这个公式可以用来在设计布隆过滤器时，合理选取哈希函数的数量，达到误判率最低的效果。

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。

在这里插入图片描述

在 Go 语言中，布隆过滤器（Bloom Filter）是一个高效的概率型数据结构，广泛应用于缓存系统、去重操作、黑名单检测等场景。​以下是Go 社区中广泛使用的布隆过滤器

  1. github.com/bits-and-blooms/bloom/v3

    • 简介：这是 Go 语言中最常用的布隆过滤器库之一，适用于需要高性能和空间效率的场景。

    • 特点：

      • 提供标准的布隆过滤器实现。
      • 被多个知名系统使用，如 Milvus 和 beego。
      • 支持自定义哈希函数和位数组大小。

    • 适用场景：适用于缓存系统、去重操作等需要高性能布隆过滤器的场景。

willf/bloom 是原始的仓库，由开发者 Will Fitzgerald 维护（willf 是他的 GitHub 用户名缩写）。

后来项目迁移到了新的组织 bits-and-blooms 下，并启用了 Go 模块（Module）支持，版本号为 v3），因此新路径为 github.com/bits-and-blooms/bloom/v3。

github.com/bits-and-blooms/bloom

github.com/bits-and-blooms/bloom/v3 是 Go 语言中广泛使用的布隆过滤器（Bloom Filter）实现，旨在提供高效的空间使用和快速的查询性能。布隆过滤器是一种概率型数据结构，广泛用于去重、黑名单检测、缓存系统等场景。

特点：

  • 高效性：该库实现了经典的布隆过滤器，并且为高性能做了优化。
  • 简洁易用：支持简单的 API，易于集成和使用。
  • 空间效率：它能够以较低的内存开销存储大量数据，适用于内存敏感的应用场景。
  • 支持自定义哈希函数：用户可以根据需求选择不同的哈希函数，以提升性能或满足特定需求。

安装：

go get github.com/bits-and-blooms/bloom/v3

使用案例：

创建一个简单的布隆过滤器

package mainimport ("fmt""github.com/bits-and-blooms/bloom/v3"
)func main() {// 创建一个布隆过滤器，预计插入 100 个元素，误判率为 0.1%filter := bloom.NewWithEstimates(100, 0.001)// 向过滤器中添加元素filter.Add([]byte("apple"))filter.Add([]byte("banana"))filter.Add([]byte("cherry"))// 检查元素是否存在fmt.Println("apple:", filter.Test([]byte("apple")))   // truefmt.Println("banana:", filter.Test([]byte("banana"))) // truefmt.Println("cherry:", filter.Test([]byte("cherry"))) // truefmt.Println("grape:", filter.Test([]byte("grape")))   // false
}

布隆过滤器的持久化

可以将布隆过滤器的状态保存到文件中，并在需要时加载，以节省内存和避免重新计算。

package mainimport ("fmt""github.com/bits-and-blooms/bloom/v3""os"
)func main() {// 创建布隆过滤器并添加元素filter := bloom.NewWithEstimates(100, 0.001)filter.Add([]byte("apple"))filter.Add([]byte("banana"))// 保存到文件file, err := os.Create("bloomfilter.dat")if err != nil {fmt.Println("Error creating file:", err)return}defer file.Close()// 将布隆过滤器保存到文件err = filter.WriteTo(file)if err != nil {fmt.Println("Error writing filter to file:", err)return}// 从文件中读取file, err = os.Open("bloomfilter.dat")if err != nil {fmt.Println("Error opening file:", err)return}defer file.Close()// 读取文件并恢复布隆过滤器loadedFilter, err := bloom.ReadFrom(file)if err != nil {fmt.Println("Error reading filter from file:", err)return}// 检查恢复后的过滤器fmt.Println("apple:", loadedFilter.Test([]byte("apple")))   // truefmt.Println("banana:", loadedFilter.Test([]byte("banana"))) // truefmt.Println("cherry:", loadedFilter.Test([]byte("cherry"))) // false
}

总结:

github.com/bits-and-blooms/bloom/v3 提供了一个高效且易于使用的布隆过滤器实现。它在缓存系统、去重操作、黑名单检测等场景中得到了广泛应用。如果你需要一个简单且高效的布隆过滤器实现，这个库是一个很好的选择。

它的主要特点包括：

  • 高效的空间利用
  • 支持自定义哈希函数
  • 提供了计数功能（用于计数布隆过滤器）
  • 支持持久化存储

这边给出一个布隆过滤器的可视化看板：https://gallery.selfboot.cn/zh/algorithms/bloomfilter

在这里插入图片描述

github.com/bits-and-blooms/bitset

我们可以注意到，github.com/bits-and-blooms/bloom/v3底层采用的是：github.com/bits-and-blooms/bitset！

github.com/bits-and-blooms/bitset 是一个用 Go 语言实现的高效位集（BitSet）库，旨在提供非负整数与布尔值之间的映射。与传统的 map[uint]bool 相比，它在内存使用和性能上具有显著优势，特别适用于需要高效位操作的场景，如布隆过滤器、权限管理、签到系统等。

这里的map[uint]bool指的是，我们简单使用一个map去判断一个值是否存在，实际上任何bitset的实现都比map高效！

🔧 核心特性

  • 高效存储：使用位图（bitmap）结构，节省内存空间，例如，存储 20 亿个数字仅需约 0.233GB，而 map 或切片可能占用数十GB。
  • 丰富操作：支持设置（Set）、清除（Clear）、翻转（Flip）、测试（Test）等基本操作
  • 集合运算：支持并集（Union）、交集（Intersection）、差集（Difference）等集合操作
  • 链式调用：方法返回指针，支持链式调用
  • 自动扩展：位集大小可动态调整，适应不同需求

🚀 安装方法

go get github.com/bits-and-blooms/bitset

🧪 使用示例

package mainimport ("fmt""math/rand""github.com/bits-and-blooms/bitset"
)func main() {fmt.Printf("Hello from BitSet!\n")var b bitset.BitSet// play some Go Fishfor i := 0; i < 100; i++ {card1 := uint(rand.Intn(52))card2 := uint(rand.Intn(52))b.Set(card1)if b.Test(card2) {fmt.Println("Go Fish!")}b.Clear(card1)}// Chainingb.Set(10).Set(11)for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {fmt.Println("The following bit is set:", i)}if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {fmt.Println("Intersection works.")} else {fmt.Println("Intersection doesn't work???")}
}

一个使用了 N 位的 bitset 至少会占用 N/8 字节的内存。bitset 中的位数至少会等于你访问过的最大位索引加一。因此，在使用 bitset 的时候，有可能因为内存不足而导致程序崩溃。

如果你需要管理大量的位数据，可以考虑使用压缩 bitset，比如 Roaring bitmap 及其在 Go 中的实现。

Roaring 库支持在压缩的 Roaring bitmap 和常规 bitset 实例之间来回转换，例如：

mybitset := roaringbitmap.ToBitSet()
newroaringbitmap := roaring.FromBitSet(mybitset)

AddString操作

我们都知道bloom通过k个hash来确保误报率，那么他究竟是如何做的呢？我们可以查看AddString源码：

// Add data to the Bloom Filter. Returns the filter (allows chaining)
func (f *BloomFilter) Add(data []byte) *BloomFilter {h := baseHashes(data)for i := uint(0); i < f.k; i++ {f.b.Set(f.location(h, i))}return f
}

其中baseHashes使用murmur哈希生成四个64位的hash：

func baseHashes(data []byte) [4]uint64 {var d digest128 // murmur hashinghash1, hash2, hash3, hash4 := d.sum256(data)return [4]uint64{hash1, hash2, hash3, hash4,}
}

然后利用多重hash技术生成K个hash：

func location(h [4]uint64, i uint) uint64 {ii := uint64(i)return h[ii%2] + ii*h[2+(((ii+(ii%2))%4)/2)]
}// 分解为
func location(h [4]uint64, i uint) uint64 {ii := uint64(i)part1 := h[ii%2]          // 交替选择 h[0] 或 h[1]part2 := h[2 + (((ii + (ii%2))%4)/2)]return part1 + ii * part2
}// location returns the ith hashed location using the four base hash values
func (f *BloomFilter) location(h [4]uint64, i uint) uint {return uint(location(h, i) % uint64(f.m)) // 映射到位数组范围内
}

这是一个非常巧妙的双重哈希（Double Hashing）实现，用于在布隆过滤器中用 2个基础哈希值 生成 k个哈希位置。这种技术通过数学组合的方式，将少量哈希函数扩展为多个，大幅减少了计算开销。

基础哈希：通过 baseHashes 生成 4个基础哈希值 h[0], h[1], h[2], h[3]（实际可能由 2 次 MurmurHash-128 计算得到）。双重哈希公式：利用线性组合公式生成多个哈希位置：

  location_i = h[i%2] + i * h[2 + ((i + i%2)/2)%2]

其中 i 是第 i 个哈希位置（从 0 到 k-1）。假设 i 从 0 开始递增，观察哈希值的组合规律：

ii%2h[…] 第一部分第二部分系数h[…] 第二部分
00h[0]0h[2 + (0/2)%2] = h[2]
11h[1]1h[2 + (1/2)%2] = h[3]
20h[0]2h[2 + (2/2)%2] = h[2]
31h[1]3h[3]
40h[0]4h[2]

  • 第一部分 h[i%2]：在 h[0] 和 h[1] 之间交替取值。

  • 第二部分 h[2 + ...]：在 h[2] 和 h[3] 之间交替取值。

  • 组合方式：location_i = 基础偏移量 + i * 步长，类似双重哈希。

传统的双重哈希公式为：

hash_i = hash1 + i * hash2

此代码的变种是：

hash_i = hash_a + i * hash_b

其中 hash_a 和 hash_b 分别从两组基础哈希值中交替选取，增加了随机性。

性能优势

  • 计算量减少：仅需 2 次 MurmurHash-128 计算（生成 4 个 64 位值），即可派生出任意多个哈希位置。

  • 对比传统方法：传统布隆过滤器需要 k 次独立哈希计算，此方法将复杂度降为 O(1) + O(k) 次简单算术运算。

  • 理想条件：若 h[0], h[1] 和 h[2], h[3] 完全独立且均匀分布，此方法与传统 k 次独立哈希的误判率一致。

  • 实际风险：若基础哈希值之间存在相关性，可能导致位冲突率上升。MurmurHash 的高质量保证了低相关性。

工程实践建议

  • 验证哈希质量：通过统计测试（如卡方检验）验证生成的哈希值分布均匀性。
  • 动态调整 k：根据误判率公式 k = (m/n) * ln2 调整哈希次数，其中 m 是位数，n 是元素数量。
  • 位数组压缩：使用位操作（如 & (f.m - 1)）代替取模运算，当 f.m 是 2 的幂时效率更高。

最后将其设置到bitSet中：

// the wordSize of a bit set
const wordSize = uint(64)
// log2WordSize is lg(wordSize)
const log2WordSize = uint(6)func (b *BitSet) Set(i uint) *BitSet {if i >= b.length { // if we need more bits, make 'emb.extendSet(i)}b.set[i>>log2WordSize] |= 1 << wordsIndex(i)return b
}// wordsIndex calculates the index of words in a `uint64`
func wordsIndex(i uint) uint {return i & (wordSize - 1)
}

BitSet​​ 通过 []uint64 数组（即 b.set）管理位集合。​​每个 uint64 元素可以存储 ​​64 个位​​（0 或 1）。

b.set = [0x00000000, 0x00000000, 0x00000000] // 3个 uint64，共 3 * 64=192 个位
位索引范围所属的数组元素
0 ~ 63A (b.set[0])
64 ~ 127B (b.set[1])
128~191C (b.set[2])
wordIndex := i >> log2WordSize  // 等价于 i / 64bitIndex := i & (wordSize - 1)  // 等价于 i % 64

假设你要操作第 i 个位（例如 i=100），如何找到它在数组中的位置​​：

  1. 步骤1​​：确定它属于数组中的第几个 uint64 元素：wordIndex = i / 64（即 i 除以 64）（位运算（右移）比除法快得多），若 i = 100 → 100 / 64 = 1 → 属于数组的第 1 个元素（即 b.set[1]）。
  2. 步骤2​​：确定它在该 uint64 元素内的第几个位：bitIndex = i % 64（即 i 对 64 取余），若 i = 100 → 100 % 64 = 36 → 操作 b.set[1] 的第 36 位。

我们最终找到了i的位置，那么接下来就是将他置为1：

b.set[i>>log2WordSize] |= 1 << wordsIndex(i)、
// 第 36 位被置 1。
b.set[1] = b.set[1] | 0x0000001000000000 // 结果：0x0000001000000000

redis 布隆过滤器组件

上文提到的github.com/bits-and-blooms/bloom是基于内存的bloom过滤器，我们的程序如果是分布式的那必定要用分布式的布隆过滤器进行全局过滤。

就像之前我们使用进程缓存+全局缓存一样使用进程bloom+全局bloom！

RedisBloom 是 Redis 官方提供的模块，支持 Bloom 过滤器、Cuckoo 过滤器、Count‑Min Sketch 和 Top‑K 等多种概率型数据结构，能够在内存中以恒定空间和极低误判率快速处理大规模数据查询。

RedisBloom 提供如 BF.RESERVE、BF.ADD、BF.EXISTS、BF.MADD、BF.MEXISTS 等丰富命令，并支持动态扩容（scaling）、持久化和集群部署。（布隆过滤器Cmd）

在这里插入图片描述
这里我们简单用docker搭建redis环境。

Redis vs Redis Stack vs RedisAI

突然发现Redis又整出一堆幺蛾子，出现了Redis Stack，Redis Ai等套餐。简单介绍下这几个套餐分别是什么意思。

Redis 被广泛认为是一种高效的内存数据存储，常用于缓存、会话管理和实时分析。然而，随着其发展，Redis 逐渐衍生出多个专化版本以满足不同场景需求。​​Redis Stack​​ 和 ​​RedisAI​​ 便是两个在核心功能基础上扩展的创新项目。尽管它们同源，但三者定位不同且不可互换。

1. Redis（核心数据库）

  • 定位：Redis 是一个开源的内存数据结构存储，核心功能是高性能的键值数据库。

  • 功能：

    • 支持字符串（String）、列表（List）、哈希（Hash）、集合（Set）、有序集合（ZSet）等基础数据结构。

    • 用于缓存、消息队列、实时数据分析等场景。

    • 提供持久化、主从复制、事务等特性。

  • 特点：轻量级、高性能，但功能相对基础，适合传统键值存储需求。

2. Redis Stack

  • 定位：Redis Stack 是 Redis 的扩展版本，集成了多个高级模块和工具，提供“一站式”解决方案。

  • 核心组件：

    • RediSearch：全文搜索引擎（支持复杂查询、聚合、分词等）。

    • RedisJSON：直接存储和操作 JSON 格式数据。

    • RedisTimeSeries：时间序列数据处理（支持降采样、聚合等）。

    • RedisBloom：概率数据结构（布隆过滤器、HyperLogLog 等）。

    • RedisGraph：图数据库（基于属性图模型）。

    • RedisAI（已更名为 RedisML）：机器学习模型部署与推理。

  • 特点：

    • 开箱即用，无需单独安装模块。

    • 针对现代应用场景（如搜索、JSON 文档、时序数据、图数据等）优化。

    • 适合需要扩展功能的场景（如电商搜索、实时监控、社交网络关系分析等）。

3. Redis AI（RedisML）

  • 定位：Redis 生态中与机器学习（AI/ML）相关的模块，用于模型部署和实时推理。

  • 功能：

    • 模型存储：将训练好的模型（如 TensorFlow、PyTorch、ONNX 格式）直接存储在 Redis 中。

    • 实时推理：通过 Redis 命令直接调用模型进行预测（低延迟）。

    • 数据与模型结合：与 Redis 的实时数据结合，适用于推荐系统、实时异常检测等场景。

    • 名称变更：早期称为 RedisAI，后整合到 Redis Stack 中并更名为 RedisML（Machine Learning）。

  • 特点：

    • 无需额外部署 ML 服务，直接在数据库层完成推理。

    • 适合需要实时 AI 集成的应用（如个性化推荐、欺诈检测）。

产品定位核心功能适用场景
Redis基础内存数据库键值存储、数据结构操作缓存、消息队列、简单数据存储
Redis StackRedis 的扩展版本（All-in-One）集成搜索、JSON、时序、图、ML 等模块复杂应用（搜索、文档存储、实时分析）
Redis AI/MLRedis 的机器学习模块（属于 Stack）模型部署与实时推理实时 AI 推理（推荐、异常检测）

• 仅需基础功能：使用 Redis。

• 需要搜索、JSON 等高级功能：选择 Redis Stack（已包含 RedisML/RedisAI）。

• 需部署机器学习模型：直接通过 Redis Stack 中的 RedisML 模块实现。

• Redis Stack Server 是官方推荐的部署方式，整合了所有模块，简化了配置。

• Redis 公司近年来在扩展生态（如云服务 Redis Enterprise、矢量数据库能力等），但 Redis Stack 是开源且免费的核心增强版。

docker部署redis-stack

上文提到redis-stack是redis的增强版，且自带bloom，那我们就部署他了，有些文档可能写道需要下载：redislabs/rebloom:2.2.2镜像，但在docker hub，官方已经标记其为弃用模式了，并且推荐安装redis-satck：

在这里插入图片描述
我们可以看到，官方给出了bloom的配置方法：

在这里插入图片描述
在终端中执行以下命令下载官方镜像：docker pull redis/redis-stack:latest

启动 Redis Stack 容器​：

$ docker pull redis/redis-stack:latest
$ mkdir -p /opt/docker/redis-stack/data
$ docker run \
-p 自定义Redis端口:6379 \
-p 自定义RedisInsight端口:8001 \
-e REDIS_ARGS="--requirepass 自定义密码" \
-v /opt/docker/redis-stack/data:/data:rw \
--name redis-stack-6-2-4-v2 \
-d redis/redis-stack:latest#备注：1)6379为Redis端口,请自定义映射端口2)8001为RedisInsight可视化页面端口,请自定义映射端口3)requirepass为自定义密码,其他模块的参数参考 步骤3说明 ,使用 -e 传入容器,参数具体内容查看Redis官网具体模块的配置说明4)redis-stack.conf为配置文件,此处不持久化到本地了,没什么必要,参考 步骤4说明5)进入容器的命令：docker exec -it redis-stack-6-2-4-v2 /bin/bash6) 按需使用的参数，非必须,一般使用 -m 限制下内存就够用了,如 -m 512m1>容器内存限制相关-----------------------------------------------------------------------------选项                  描述-m,–memory           内存限制，格式是数字加单位，单位可以为 b,k,m,g。最小为 4M–memory-swap         内存+交换分区大小总限制。格式同上。必须必-m设置的大–memory-reservation  内存的软性限制。格式同上–oom-kill-disable    是否阻止 OOM killer 杀死容器，默认没设置–oom-score-adj       容器被 OOM killer 杀死的优先级，范围是[-1000, 1000]，默认为 0–memory-swappiness   用于设置容器的虚拟内存控制行为。值为 0~100 之间的整数–kernel-memory       核心内存限制。格式同上，最小为 4M-----------------------------------------------------------------------------2>容器CPU限制相关,一般使用 -m 限制下就够用了,如 -m 512m-----------------------------------------------------------------------------选项                  描述–cpuset-cpus=""      允许使用的 CPU 集，值可以为 0-3,0,1-c,–cpu-shares=0     CPU 共享权值（相对权重）cpu-period=0         限制 CPU CFS 的周期，范围从 100ms~1s，即[1000, 1000000]–cpu-quota=0         限制 CPU CFS 配额，必须不小于1ms，即 >= 1000–cpuset-mems=""      允许在上执行的内存节点（MEMs），只对 NUMA 系统有效说明：其中–cpuset-cpus用于设置容器可以使用的 vCPU 核。-c,–cpu-shares用于设置多个容器竞争 CPU 时，各个容器相对能分配到的 CPU 时间比例。–cpu-period和–cpu-quata用于绝对设置容器能使用 CPU 时间。-----------------------------------------------------------------------------

最后通过：docker ps验证是否启动：

在这里插入图片描述
redis-stack.conf配置文件无太多东西,无需映射到本地,以下为具体redis相关的配置内容,路径为容器内路径：

/etc/redis-stack.confport 6379
daemonize no
loadmodule /opt/redis-stack/lib/redisearch.so
loadmodule /opt/redis-stack/lib/redisgraph.so
loadmodule /opt/redis-stack/lib/redistimeseries.so
loadmodule /opt/redis-stack/lib/rejson.so
loadmodule /opt/redis-stack/lib/redisbloom.so--------------------------------------------------------
/opt/redis-stack/etc/redis-stack-service.confport 6379
daemonize no
loadmodule /opt/redis-stack/lib/redisearch.so
loadmodule /opt/redis-stack/lib/redisgraph.so
loadmodule /opt/redis-stack/lib/redistimeseries.so
loadmodule /opt/redis-stack/lib/rejson.so
loadmodule /opt/redis-stack/lib/redisbloom.so
--------------------------------------------------------
/opt/redis-stack/etc/redis-stack.confport 6379
daemonize yes

/opt/redis-stack/etc/redis-stack.conf为最终生效配置会覆盖其他配置，所以daemonize为yes。

最后我们打开8001端口就可以看到redis 提供的web管理界面：

在这里插入图片描述
然后去github：https://github.com/redis-windows/redis-windows下载一个windows版本的redis-cli去连接，可以看到redis已经存储了一个String类型：

在这里插入图片描述
在这里插入图片描述
然后我们测试一下redis bloom：

在这里插入图片描述
在这里插入图片描述
golang 客户端我们使用github.com/redis/go-redis/v9，使用go get github.com/redis/go-redis/v9 安装好后，我们写一个简单的main去验证：

func main() {client := redis.NewClient(&redis.Options{Addr:     "10.128.145.159:6379",Password: "123456",DB:       0,})// Pongcmd := client.Ping(context.Background())fmt.Println(cmd.Result())// trueb := client.BFExists(context.Background(), "myfilter", "helloworl")fmt.Println(b.Result())
}

这样，我们的redis分布式bloom就搭建好了，对于一个大量数据过滤的项目，就可以采用两级bloom去过滤去重。

redis命令行文档

官方的redis命令行文档在：https://redis.io/docs/latest/commands/?group=bf

可以看到，redis支持的功能越来越多：

在这里插入图片描述
这里我们着重介绍布隆过滤器的命令！

BF.RESERVE

创建一个空的布隆过滤器（Bloom Filter），并为其指定初始容量（capacity）和误判率（error_rate）。

  • ​​默认行为​​：当过滤器达到容量上限时，会自动扩展（创建新的子过滤器）。新子过滤器的容量是前一个子过滤器容量乘以扩展因子（expansion）。
  • 推荐做法​​：尽量预先估算总容量并一次性分配，因为动态扩展会增加内存和 CPU 开销（每个子过滤器需额外存储位和哈希函数）。
BF.RESERVE key error_rate capacity [EXPANSION expansion] [NONSCALING]

必需参数

  • key 要创建的布隆过滤器的键名。
  • error_rate 期望的误判概率，取值范围为 0 到 1。例如： 0.001 表示允许 0.1% 的误判率（即 1000 次查询中允许 1 次误判）。
  • capacity 计划添加到过滤器中的预期条目数量。 若允许扩展，超过此容量后性能会逐步下降（性能下降幅度与子过滤器数量成线性关系）。

可选参数

  • NONSCALING 禁止过滤器自动扩展。当容量达到上限时，过滤器会报错。 非扩展模式比扩展模式稍节省内存。
  • EXPANSION expansion 当容量达到上限时，新子过滤器的容量是前一个子过滤器容量乘以 expansion（正整数）。
    • 若不确定总条目数，建议设置 expansion ≥ 2 以减少子过滤器数量。
    • 若已知总条目数，可设置 expansion = 1 以节省内存。
    • 默认值：2

底层原理​

  1. 最优哈希函数数量
    哈希函数数量 = ⌈ − ln ⁡ ( error_rate ) ln ⁡ 2 ⌉ \text{哈希函数数量} = \left\lceil \frac{-\ln(\text{error\_rate})}{\ln 2} \right\rceil 哈希函数数量=⌈ln2−ln(error_rate)​⌉

  2. 每个条目所需比特数
    比特数/条目 = − ln ⁡ ( error_rate ) ( ln ⁡ 2 ) 2 \text{比特数/条目} = \frac{-\ln(\text{error\_rate})}{(\ln 2)^2} 比特数/条目=(ln2)2−ln(error_rate)​

  3. 总比特数
    总比特数 = capacity × 比特数/条目 \text{总比特数} = \text{capacity} \times \text{比特数/条目} 总比特数=capacity×比特数/条目

常见误判率配置示例

误判率哈希函数数量每个条目所需比特数
1%79.585
0.1%1014.378
0.01%1419.170

返回值

  • 成功：返回简单字符串 OK。
  • 失败：返回错误信息（如参数无效、键已存在等）。

示例

-- 创建容量为 1000、误判率 1% 的布隆过滤器
127.0.0.1:6379> BF.RESERVE bf 0.01 1000
OK-- 重复创建同名过滤器会报错
127.0.0.1:6379> BF.RESERVE bf 0.01 1000
(error) ERR item exists-- 创建允许扩展的过滤器（扩展因子为 2）
127.0.0.1:6379> BF.RESERVE bf_exp 0.01 1000 EXPANSION 2
OK-- 创建禁止扩展的过滤器
127.0.0.1:6379> BF.RESERVE bf_non 0.01 1000 NONSCALING
OK
BF.ADD
BF.ADD key item

向布隆过滤器（Bloom Filter）中添加一个元素。

  • 如果 key 不存在，Redis 会自动创建一个新的布隆过滤器，使用默认参数：

    • 误判率（error_rate）：默认 0.01（1%）

    • 初始容量（capacity）：默认 100

    • 扩展因子（expansion）：默认 2

  • 建议预先通过 BF.RESERVE 明确配置过滤器的参数以优化性能。

必需参数

  • key 目标布隆过滤器的键名。若不存在则自动创建。

  • item 要添加的元素（字符串类型）。

返回值

  • 成功添加新元素：返回整数 1。
  • 元素可能已存在（可能存在误判）：返回整数 0。
  • 错误（参数无效、键类型错误、过滤器已满等）：返回空数组 []。

示例

-- 添加新元素 "item1"
127.0.0.1:6379> BF.ADD bf item1
(integer) 1-- 重复添加同一元素（可能返回误判结果）
127.0.0.1:6379> BF.ADD bf item1
(integer) 0
BF.CARD
BF.CARD key

功能描述 返回布隆过滤器（Bloom Filter）的基数，即被检测为唯一且成功添加到过滤器中的元素数量。

  • 基数计算规则：统计所有导致至少一个子过滤器中至少一个位（bit）被设置的元素。
  • 版本支持：自 RedisBloom 2.4.4 版本起可用。

必需参数

  • key 目标布隆过滤器的键名。

返回值

  • 存在 key：返回已添加的唯一元素数量（等同于 BF.INFO key ITEMS）。
  • 不存在 key：返回整数 0。
  • 错误（参数无效、键类型错误等）：返回空数组 []。

示例

-- 添加元素 "item_foo"
127.0.0.1:6379> BF.ADD bf1 item_foo
(integer) 1-- 查询基数（返回 1）
127.0.0.1:6379> BF.CARD bf1
(integer) 1-- 查询不存在的过滤器（返回 0）
127.0.0.1:6379> BF.CARD bf_new
(integer) 0

注意事项

  1. 与 BF.INFO 的关系：
    BF.CARD key 的返回值等同于 BF.INFO key ITEMS，但 BF.CARD 的语法更简洁。

  2. 非唯一性统计：
    布隆过滤器无法保证绝对唯一性，返回的基数是基于位操作的概率性统计值。

  3. 应用场景：
    适用于估算唯一元素数量（如独立访客计数），但需容忍一定误差（由误判率决定）。

BF.EXISTS
BF.EXISTS key item

功能描述 检查指定元素是否可能存在于布隆过滤器（Bloom Filter）中。

  • 特性：

    • 若返回 1，表示元素可能已存在（存在误判概率，由 error_rate 决定）。

    • 若返回 0，表示元素一定不存在或过滤器键 key 不存在。

  • 此命令为单元素检查版本，批量检查请使用 BF.MEXISTS：BF.MEXISTS key item [item …]

redis> BF.MADD bf item1 item2
1) (integer) 1
2) (integer) 1
redis> BF.MEXISTS bf item1 item2 item3
1) (integer) 1
2) (integer) 1
3) (integer) 0

必需参数

  • key 目标布隆过滤器的键名。 若 key 不存在，直接返回 0。
  • item 待检查的元素（字符串类型）。

返回值

  • 可能存在：返回整数 1（高概率存在，但有误判可能）。
  • 确定不存在或键不存在：返回整数 0。
  • 错误（参数无效、键类型错误等）：返回空数组 []。

示例

-- 添加元素 "item1"  
127.0.0.1:6379> BF.ADD bf item1
(integer) 1-- 检查已存在的元素（返回1）  
127.0.0.1:6379> BF.EXISTS bf item1
(integer) 1-- 检查不存在的元素（返回0）  
127.0.0.1:6379> BF.EXISTS bf item2
(integer) 0
BF.INFO
BF.INFO key [CAPACITY | SIZE | FILTERS | ITEMS | EXPANSION]

功能描述 返回布隆过滤器（Bloom Filter）的详细信息，包括容量、内存占用、子过滤器数量等。

  • 默认行为：若未指定可选参数，返回所有字段信息。
  • 指定字段：可单独查询特定属性（如容量、内存大小等）。

必需参数

  • key 目标布隆过滤器的键名。

可选参数

  • CAPACITY 返回过滤器的初始容量（即触发自动扩展前的最大条目数，包含已添加条目）。

  • SIZE 返回过滤器占用的内存大小（单位：字节）。

  • FILTERS 返回子过滤器的数量（自动扩展时会产生多个子过滤器）。

  • ITEMS 返回已添加的唯一元素数量（等同于 BF.CARD key）。

  • EXPANSION 返回扩展因子（当容量不足时，新子过滤器的容量增长倍数）。

返回值
未指定可选参数时

  • 成功：返回包含所有字段的数组（字段名和对应值交替出现）。

  • 失败（键不存在、类型错误等）：返回空数组 []。

指定可选参数时

  • 成功：直接返回对应字段的整数值。

  • 失败：返回空数组 []。

示例

-- 添加元素并查询全部信息
127.0.0.1:6379> BF.ADD bf1 observation1
(integer) 1127.0.0.1:6379> BF.INFO bf11) Capacity           -- 初始容量2) (integer) 1003) Size               -- 内存大小（字节）4) (integer) 2405) Number of filters  -- 子过滤器数量6) (integer) 17) Number of items inserted  -- 已添加唯一元素数8) (integer) 19) Expansion rate     -- 扩展因子
10) (integer) 2-- 单独查询容量
127.0.0.1:6379> BF.INFO bf1 CAPACITY
1) (integer) 100

关键字段解释

字段名含义
Capacity初始容量（自动扩展前的最大条目数）。
Size占用的内存总大小（单位：字节）。
Number of filters子过滤器数量（自动扩展时增加）。
Number of items inserted已添加的唯一元素数量（可能存在重复添加但未触发位变化的条目）。
Expansion rate扩展因子（新子过滤器的容量增长倍数，默认 2）。
BF.INSERT
BF.INSERT key [CAPACITY capacity] [ERROR error] [EXPANSION expansion] [NOCREATE] [NONSCALING] ITEMS item [item ...]

功能描述 向布隆过滤器中批量添加元素，并支持动态创建过滤器或指定参数。

  • 核心行为：

    • 若 key 不存在，则自动创建一个新过滤器（可指定参数 CAPACITY、ERROR 等）。

    • 若 key 已存在，则直接添加元素到现有过滤器。

  • 本质：此命令是 BF.RESERVE（创建过滤器）和 BF.MADD（批量添加）的语法糖。

必需参数

  • key 目标布隆过滤器的键名。若不存在则自动创建。

  • ITEMS item ... 待添加的一个或多个元素（字符串类型）。

可选参数

  • NOCREATE 禁止自动创建过滤器。若 key 不存在，直接返回错误。 互斥限制：不可与 CAPACITY 或 ERROR 同时使用。

  • CAPACITY capacity 指定新过滤器的初始容量（仅当 key 不存在时生效）。 默认值：若未指定且需自动创建，使用模块级默认容量（通常为 100）。

  • ERROR error 指定新过滤器的误判率（仅当 key 不存在时生效）。 默认值：若未指定且需自动创建，使用模块级默认误判率（通常为 0.01，即 1%）。

  • NONSCALING 禁止过滤器自动扩展。当容量达到上限时，返回错误（仅对新创建的过滤器生效）。

  • EXPANSION expansion 指定新过滤器的扩展因子（仅当 key 不存在时生效）。 默认值：2。

返回值 返回一个数组，每个元素表示对应元素的添加状态：

  • 成功添加：1（元素可能实际为新插入）。
  • 元素可能已存在：0（可能存在误判）。
  • 错误（如过滤器已满、参数无效、NOCREATE 但键不存在等）：返回空数组 []。

示例

-- 自动创建过滤器并添加三个元素（使用默认参数）
127.0.0.1:6379> BF.INSERT filter ITEMS foo bar baz
1) (integer) 1  -- foo 成功添加
2) (integer) 1  -- bar 成功添加
3) (integer) 1  -- baz 成功添加-- 指定容量为 10000 并添加元素（若过滤器不存在则创建）
127.0.0.1:6379> BF.INSERT filter CAPACITY 10000 ITEMS hello
1) (integer) 1  -- hello 成功添加-- 强制不自动创建过滤器（若不存在则报错）
127.0.0.1:6379> BF.INSERT filter NOCREATE ITEMS foo bar
(error) ERR not found  -- 若 filter 不存在，返回错误
BF.MADD
BF.MADD key item [item ...]

功能描述 向布隆过滤器（Bloom Filter）中批量添加一个或多个元素。

  • 自动创建过滤器：若 key 不存在，会自动创建一个新过滤器，使用默认参数：

    • 误判率（error_rate）：默认 0.01（1%）

    • 初始容量（capacity）：默认 100

    • 扩展因子（expansion）：默认 2

  • 与 BF.INSERT 的区别：此命令不能指定过滤器的误判率、容量等参数，仅用于快速批量添加元素。

必需参数

  • key 目标布隆过滤器的键名。若不存在则自动创建。

  • item ... 一个或多个待添加的元素（字符串类型）。

返回值 返回一个数组，每个元素表示对应元素的添加状态：

  • 成功添加：1（元素可能实际为新插入）。
  • 元素可能已存在：0（可能存在误判）。
  • 错误（如过滤器已满、参数无效等）：返回空数组 []。

示例

-- 批量添加三个元素（包含重复项）
127.0.0.1:6379> BF.MADD bf item1 item2 item2
1) (integer) 1  -- item1 成功添加
2) (integer) 1  -- item2 成功添加（首次添加）
3) (integer) 0  -- item2 重复添加（可能误判）

注意事项

  1. 默认参数限制： 自动创建的过滤器使用默认参数，可能不适用于大规模场景，建议通过 BF.RESERVE 预先配置。

  2. 误判机制： 返回 0 表示元素可能已存在，实际需结合业务逻辑判断是否需要去重。

  3. 性能影响： 批量操作的时间复杂度为 O(k * n)，误判率越低（k 越大），耗时显著增加。

BF.LOADCHUNK
BF.LOADCHUNK key iterator data

功能描述 从 BF.SCANDUMP 命令生成的备份数据块中恢复布隆过滤器（Bloom Filter）。

  • 核心用途：用于增量恢复通过 BF.SCANDUMP 导出的过滤器数据。

  • 注意事项：

    • 此命令会覆盖目标键 key 中现有的布隆过滤器数据。

    • 恢复过程中需确保过滤器未被修改（否则可能导致数据不一致）。

必需参数

  • key 要恢复的布隆过滤器的键名（目标键）。

  • iterator 数据块关联的迭代器编号（由 BF.SCANDUMP 命令返回）。

  • data 要恢复的数据块内容（由 BF.SCANDUMP 命令返回）。

返回值

  • 成功恢复：返回简单字符串 OK。

  • 失败（参数无效、键类型错误、数据损坏等）：返回空数组 []。

工作原理

  1. 数据分块导出：BF.SCANDUMP 会将过滤器数据分割为多个块（类似 DUMP 但支持增量导出）。
  2. 顺序恢复：使用 BF.LOADCHUNK 按迭代器顺序依次恢复每个数据块，直到收到迭代器 0（表示恢复完成）。

应用场景

  • 增量备份与恢复：适用于大型布隆过滤器的持久化存储和迁移。

  • 容灾恢复：当过滤器数据损坏时，从备份块中逐步恢复。

BF.SCANDUMP
BF.SCANDUMP key iterator

功能描述 以增量方式导出布隆过滤器（Bloom Filter）的数据块，适用于无法通过 DUMP/RESTORE 处理的大型过滤器。

  • 首次调用：需设置 iterator=0，后续调用使用返回的迭代器值。

  • 结束标志：当返回 (0, NULL) 时表示导出完成。

  • 用途：与 BF.LOADCHUNK 配合实现过滤器的增量备份与恢复。

必需参数

  • key 目标布隆过滤器的键名。

  • iterator 迭代器编号：

    • 首次调用：设为 0。

    • 后续调用：使用前一次返回的迭代器值。

返回值

  • 成功：返回数组 [迭代器值, 数据块]。 迭代器为 0：表示导出完成。

  • 失败（键不存在、类型错误等）：返回空数组 []。

示例
步骤1：创建并填充过滤器

-- 创建容量为10、误判率10%的过滤器
127.0.0.1:6379> BF.RESERVE bf 0.1 10
OK-- 添加元素 "item1"
127.0.0.1:6379> BF.ADD bf item1
(integer) 1

步骤2：增量导出数据块

-- 首次调用（迭代器初始化为0）
127.0.0.1:6379> BF.SCANDUMP bf 0
1) (integer) 1                -- 下一个迭代器值
2) "\x01\x00\x00\x00..."      -- 数据块1（二进制格式）-- 使用迭代器1继续导出
127.0.0.1:6379> BF.SCANDUMP bf 1
1) (integer) 9                -- 下一个迭代器值
2) "\x01\b\x00\x80..."        -- 数据块2-- 使用迭代器9继续导出（返回0表示完成）
127.0.0.1:6379> BF.SCANDUMP bf 9
1) (integer) 0                -- 迭代器归零
2) ""                          -- 无数据

步骤3：删除并恢复过滤器

-- 删除原过滤器
127.0.0.1:6379> DEL bf
(integer) 1-- 按顺序恢复数据块
127.0.0.1:6379> BF.LOADCHUNK bf 1 "\x01\x00\x00\x00..."
OK
127.0.0.1:6379> BF.LOADCHUNK bf 9 "\x01\b\x00\x80..."
OK-- 验证恢复结果
127.0.0.1:6379> BF.EXISTS bf item1
(integer) 1

Python 代码示例 数据导出与恢复流程

# 导出数据块
chunks = []
iter = 0
while True:# 调用 BF.SCANDUMP 获取数据块iter, data = conn.execute_command("BF.SCANDUMP", "bf_key", iter)if iter == 0:breakchunks.append((iter, data))# 恢复数据块
for iter, data in chunks:conn.execute_command("BF.LOADCHUNK", "bf_key", iter, data)

注意事项

  1. 顺序恢复：必须按 BF.SCANDUMP 返回的迭代器顺序调用 BF.LOADCHUNK。
  2. 数据完整性：恢复过程中禁止修改目标过滤器，否则可能导致数据损坏。
  3. 二进制数据：导出的数据块为二进制格式，需原样传输和存储。
http://www.xdnf.cn/news/2128.html

相关文章：

  • 阿里云域名智能解析至国内外AWS的合规化部署指南
  • Windows11系统中GIT下载
  • 系统架构设计中的DSSA方法：理论、实践与行业深度应用
  • 【SwitchyOmega安装教程】
  • 【Token系列】01 | Token不是词：GPT如何切分语言的最小单元
  • 思科路由器重分发（RIP动态路由+静态路由）
  • 强化学习：高级策略梯度理论与优化方法
  • react的fiber 用法
  • 6.1腾讯技术岗2025面试趋势前瞻：大模型、云原生与安全隐私新动向
  • 重定向和语言级缓冲区【Linux操作系统】
  • 用python写一个相机选型的简易程序
  • RTMP 协议解析 1
  • Linux0.11内存管理：相关代码
  • 从零实现 registry.k8s.io/pause:3.8 镜像的导出与导入
  • 山东大学软件学院项目实训-基于大模型的模拟面试系统-网页图片显示问题
  • 基于开源技术体系的品牌赛道力重构：AI智能名片与S2B2C商城小程序源码驱动的品类创新机制研究
  • 月之暗面开源 Kimi-Audio-7B-Instruct，同时支持语音识别和语音生成
  • 推荐三款GitHub上高星开源的音乐搜索平台
  • 华为OD机试真题——素数之积RSA加密算法（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现
  • JDK 17 与 Spring Cloud Gateway 新特性实践指南
  • Flask + ajax上传文件（三）--图片上传与OCR识别
  • DataStreamAPI实践原理——计算模型
  • 上位机知识篇---时钟分频
  • [mysql]数据类型精讲下
  • 【Linux网络】HTTP协议全解析 - 从请求响应到方法与Header
  • SpringBoot UserAgentUtils获取用户浏览器 操作系统设备统计 信息统计 日志入库
  • 从基础到实战的量化交易全流程学习：1.1 量化交易本质与行业生态
  • C++---类和对象(二)
  • VO包装类和实体类分别是什么？区别是什么？
  • C++学习笔记（四十）——STL之归约算法