README
¶
bloom
简介
bloom 包实现了高效的布隆过滤器（Bloom Filter），用于大规模集合的成员判定，具备极高的空间效率和可配置的误判率。支持分组、可插拔存储（内存/自定义）、多哈希函数、并发安全，适用于缓存预判、黑名单、唯一性校验等场景。
主要特性
- 支持标准布隆过滤器接口（添加、判定、分组操作）
- 支持自定义存储后端（内存、可扩展为 Redis 等）
- 支持分组隔离，适合多租户/多集合场景
- 支持误判率、元素数量等参数灵活配置
- 并发安全，适合高并发环境
- 采用 murmur3 哈希算法，分布均匀
- 完善的错误处理与日志能力
- 完整单元测试覆盖
设计理念
bloom 包遵循"高效、灵活、易用"的设计理念，核心接口与实现分离，支持多种存储后端。通过 Option 模式灵活配置，支持分组、日志、参数自定义。默认实现为高性能内存存储，便于本地高并发场景。
安装
前置条件
- Go 版本要求：Go 1.18+
- 依赖要求：
- github.com/spaolacci/murmur3
- github.com/spf13/cast
- github.com/stretchr/testify（仅测试）
- github.com/golang/mock/gomock（仅测试）
安装命令
go get -u github.com/fsyyft-go/kit/container/bloom
快速开始
基础用法
package main
import (
"context"
"fmt"
"github.com/fsyyft-go/kit/container/bloom"
)
func main() {
// 创建布隆过滤器，预计 10000 元素，误判率 0.01
bf, _, err := bloom.NewBloom(
bloom.WithName("my-bloom"),
bloom.WithExpectedElements(10000),
bloom.WithFalsePositiveRate(0.01),
)
if err != nil {
panic(err)
}
ctx := context.Background()
// 添加元素
_ = bf.Put(ctx, "foo")
// 判定元素
exists, _ := bf.Contain(ctx, "foo")
fmt.Println("foo 是否可能存在：", exists)
}
分组用法
// 支持分组隔离
_ = bf.GroupPut(ctx, "group1", "bar")
exists, _ := bf.GroupContain(ctx, "group1", "bar")
自定义存储
// 使用内存存储，指定内存块大小（字节）
store := bloom.NewMemoryStore(1024*1024) // 1MB
bf, _, _ := bloom.NewBloom(
bloom.WithStore(store),
bloom.WithExpectedElements(1000),
)
详细指南
核心概念
- 布隆过滤器：空间效率极高的概率型集合判定结构，适合大数据量场景。
- 误判率：可配置，越低则空间需求越大。
- 分组：同一过滤器可隔离多个逻辑集合。
- 存储后端：可插拔，默认内存实现。
- 多哈希函数：自动根据参数计算最优数量。
常见用例
- 缓存穿透预判
- 黑名单/白名单判定
- 唯一性校验
- 分布式唯一性预过滤（可扩展 Redis 存储）
最佳实践
- 合理设置元素数量和误判率，避免空间浪费或误判过高
- 对于分布式场景可自定义 Store 实现
- 并发场景下直接使用，无需额外加锁
- 始终检查返回的 error
API 文档
主要类型
// Bloom 布隆过滤器接口
type Bloom interface {
Contain(ctx context.Context, value string) (bool, error)
Put(ctx context.Context, value string) error
GroupContain(ctx context.Context, group, value string) (bool, error)
GroupPut(ctx context.Context, group, value string) error
}
// Store 存储后端接口
type Store interface {
Exist(ctx context.Context, key string, hash []uint64) (bool, error)
Add(ctx context.Context, key string, hash []uint64) error
}
// Option 配置项类型
type Option func(*bloom)
// NewBloom 创建布隆过滤器
func NewBloom(opts ...Option) (Bloom, func(), error)
// NewMemoryStore 创建内存存储
func NewMemoryStore(size int) Store
关键函数
NewBloom：创建布隆过滤器，支持 Option 配置Put/Contain：添加/判定元素GroupPut/GroupContain：分组添加/判定NewMemoryStore：创建内存存储
配置选项
WithName(name string)：设置过滤器名称WithStore(store Store)：自定义存储后端WithExpectedElements(n uint64)：预计元素数量WithFalsePositiveRate(p float64)：误判率WithLogger(logger log.Logger)：自定义日志
错误处理
- 名称为空、重复、误判率参数非法等会返回详细错误
- 存储层错误会原样返回
- 建议所有操作均检查 error
性能指标
- 内存存储百万级元素判定/添加操作均为 O(k)，k 为哈希函数数，单次操作微秒级
- 误判率与空间、哈希函数数量成反比
测试覆盖率
- 单元测试覆盖所有接口、边界、异常场景
- 使用 gomock+testify，覆盖率 100%
调试指南
- 检查参数设置是否合理（元素量、误判率）
- 内存存储建议根据实际场景调整 size
- 分组键名冲突可通过 WithName 区分
相关文档
贡献指南
欢迎提交 Issue、PR 或建议，详见 贡献指南。
许可证
本项目采用 MIT License 许可证。详见 LICENSE。
Documentation
¶
Overview ¶
Package bloom 提供可分组的 Bloom Filter 及其存储抽象。
Bloom Filter 只提供 Put 和 Contain 一类追加式操作：Contain 返回 false 时表示元素一定不存在， 返回 true 时表示元素可能存在且存在误判，不支持删除后再精确恢复“不存在”语义。 本包通过 Bloom name 与 group 派生独立 key，隔离不同位图命名空间。默认内存存储按 key 分区并使用 RWMutex 保护并发访问，但会忽略传入的 ctx；Redis 存储会透传 ctx，将派生 key 转换为 Redis key，并通过 Lua 脚本批量执行位图读写。
Index ¶
- Variables
- func NewMemoryStore(size int) *memoryStore
- func NewRedisStore(redis kitredis.Redis) (*redisStore, error)
- type Bloom
- type MockBloom
- func (m *MockBloom) Contain(ctx context.Context, value string) (bool, error)
- func (m *MockBloom) EXPECT() *MockBloomMockRecorder
- func (m *MockBloom) GroupContain(ctx context.Context, group, value string) (bool, error)
- func (m *MockBloom) GroupPut(ctx context.Context, group, value string) error
- func (m *MockBloom) Put(ctx context.Context, value string) error
- type MockBloomMockRecorder
- func (mr *MockBloomMockRecorder) Contain(ctx, value interface{}) *gomock.Call
- func (mr *MockBloomMockRecorder) GroupContain(ctx, group, value interface{}) *gomock.Call
- func (mr *MockBloomMockRecorder) GroupPut(ctx, group, value interface{}) *gomock.Call
- func (mr *MockBloomMockRecorder) Put(ctx, value interface{}) *gomock.Call
- type MockStore
- type MockStoreMockRecorder
- type Option
- type Store
Constants ¶
This section is empty.
Variables ¶
View Source
var ( // ErrBloomNameEmpty 表示布隆过滤器名称为空或仅包含空白字符。 ErrBloomNameEmpty = errors.New("bloom: bloom name can't be empty") // ErrBloomNameRepeated 表示 bloomNames 注册表中已经存在相同的布隆过滤器名称。 ErrBloomNameRepeated = errors.New("bloom: bloom name can't repeated") // ErrBloomFalseProbabilityThanOne 表示期望误判率大于 1。 ErrBloomFalseProbabilityThanOne = errors.New("bloom: bloom false probability can't than 1") // ErrBloomFalseProbabilityNegative 表示期望误判率小于 0。 ErrBloomFalseProbabilityNegative = errors.New("bloom: bloom false probability can't be negative") )
View Source
var (
ErrResultTypeNotArray = errors.New("result type is not array")
)
ErrResultTypeNotArray 表示 Redis Lua 查询脚本返回结果不是数组。
redisStore.Exist 期望批量 getbit 脚本返回 []any；当 Redis 客户端返回其它类型时会返回该错误。
Functions ¶
func NewMemoryStore ¶
func NewMemoryStore(size int) *memoryStore
NewMemoryStore 创建一个新的内存 Store 实例。
参数：
- size: 每个 key 的内存块大小，单位为 byte；小于或等于 0 时使用 defaultBlockSize。
返回：
- *memoryStore: 初始化完成的内存 Store；不同 key 的位图相互隔离，并发访问由内部锁保护。
func NewRedisStore ¶
NewRedisStore 创建一个基于 Redis 的布隆过滤器 Store 实例。
NewRedisStore 会在 context.Background() 下预加载批量 setbit 和 getbit Lua 脚本。返回的 Store 不负责关闭 Redis 客户端，客户端生命周期由调用方管理。
参数：
- redis: Redis 客户端实例，用于预加载脚本并执行后续位图读写。
返回：
- *redisStore: Redis 存储实现的实例指针。
- error: set 或 get 脚本预加载失败时返回底层 Redis 错误。
Types ¶
type Bloom ¶
type Bloom interface {
// Contain 判断元素是否可能存在于当前 Bloom 名称对应的位图中。
//
// 参数：
// - ctx: 调用上下文，会传递给底层 Store；是否生效由具体 Store 实现决定。
// - value: 待判断的元素值，按原始字符串内容参与 hash 计算。
//
// 返回：
// - bool: 元素存在性判断结果：
// - false: 元素一定不存在。
// - true: 元素可能存在，调用方需要接受布隆过滤器的误判可能。
// - error: 底层 Store 查询失败时返回错误。
Contain(ctx context.Context, value string) (bool, error)
// Put 将元素添加到当前 Bloom 名称对应的位图中。
//
// 参数：
// - ctx: 调用上下文，会传递给底层 Store；是否生效由具体 Store 实现决定。
// - value: 待添加的元素值，按原始字符串内容参与 hash 计算。
//
// 返回：
// - error: 底层 Store 写入失败时返回错误。
Put(ctx context.Context, value string) error
// GroupContain 判断元素是否可能存在于指定分组对应的位图中。
//
// 参数：
// - ctx: 调用上下文，会传递给底层 Store；是否生效由具体 Store 实现决定。
// - group: 分组名称，会按 "name:group" 与 Bloom 名称拼接成最终 Store key；调用方应避免
// name 或 group 中的冒号导致 key 冲突。
// - value: 待判断的元素值，按原始字符串内容参与 hash 计算。
//
// 返回：
// - bool: 元素在分组中的存在性判断结果：
// - false: 元素在该分组中一定不存在。
// - true: 元素在该分组中可能存在，调用方需要接受布隆过滤器的误判可能。
// - error: 底层 Store 查询失败时返回错误。
GroupContain(ctx context.Context, group string, value string) (bool, error)
// GroupPut 将元素添加到指定分组对应的位图中。
//
// 参数：
// - ctx: 调用上下文，会传递给底层 Store；是否生效由具体 Store 实现决定。
// - group: 分组名称，会按 "name:group" 与 Bloom 名称拼接成最终 Store key；调用方应避免
// name 或 group 中的冒号导致 key 冲突。
// - value: 待添加的元素值，按原始字符串内容参与 hash 计算。
//
// 返回：
// - error: 底层 Store 写入失败时返回错误。
GroupPut(ctx context.Context, group string, value string) error
}
Bloom 定义可追加写入的布隆过滤器接口。
Bloom 以字符串值为输入，通过底层 Store 保存多重 hash 对应的位图位置。Contain 或 GroupContain 返回 false 时表示元素一定不存在，返回 true 时表示元素可能存在且可能包含误判。
type MockBloom ¶
type MockBloom struct {
// contains filtered or unexported fields
}
MockBloom 是 Bloom 接口的 mock 实现。 用于在测试中模拟布隆过滤器的行为。
func NewMockBloom ¶
func NewMockBloom(ctrl *gomock.Controller) *MockBloom
NewMockBloom 创建一个新的 MockBloom 实例。
参数：
- ctrl：gomock 控制器实例，用于管理 mock 对象
返回值：
- *MockBloom：新创建的 mock 实例
func (*MockBloom) Contain ¶
Contain 模拟了 Bloom 接口的 Contain 方法。 用于判断指定元素是否可能存在于布隆过滤器中。
参数：
- ctx：上下文对象，用于控制请求的生命周期
- value：要判断是否存在的元素值
返回值：
- bool：元素是否可能存在于布隆过滤器中
- error：操作过程中发生的错误
func (*MockBloom) EXPECT ¶
func (m *MockBloom) EXPECT() *MockBloomMockRecorder
EXPECT 返回一个对象，允许调用者指示预期的使用。
返回值：
- *MockBloomMockRecorder：用于设置期望的调用记录器
func (*MockBloom) GroupContain ¶
GroupContain 模拟了 Bloom 接口的 GroupContain 方法。 用于判断指定分组中是否可能包含指定元素。
参数：
- ctx：上下文对象，用于控制请求的生命周期
- group：分组名称，用于区分不同的数据集合
- value：要判断是否存在的元素值
返回值：
- bool：元素是否可能存在于指定分组中
- error：操作过程中发生的错误
type MockBloomMockRecorder ¶
type MockBloomMockRecorder struct {
// contains filtered or unexported fields
}
MockBloomMockRecorder 是 MockBloom 的调用记录器。 用于记录和验证对 MockBloom 的方法调用。
func (*MockBloomMockRecorder) Contain ¶
func (mr *MockBloomMockRecorder) Contain(ctx, value interface{}) *gomock.Call
Contain 指示对 Contain 方法的预期调用。
参数：
- ctx：上下文对象
- value：要判断的元素值
返回值：
- *gomock.Call：用于设置期望的调用
func (*MockBloomMockRecorder) GroupContain ¶
func (mr *MockBloomMockRecorder) GroupContain(ctx, group, value interface{}) *gomock.Call
GroupContain 指示对 GroupContain 方法的预期调用。
参数：
- ctx：上下文对象
- group：分组名称
- value：要判断的元素值
返回值：
- *gomock.Call：用于设置期望的调用
func (*MockBloomMockRecorder) GroupPut ¶
func (mr *MockBloomMockRecorder) GroupPut(ctx, group, value interface{}) *gomock.Call
GroupPut 指示对 GroupPut 方法的预期调用。
参数：
- ctx：上下文对象
- group：分组名称
- value：要添加的元素值
返回值：
- *gomock.Call：用于设置期望的调用
func (*MockBloomMockRecorder) Put ¶
func (mr *MockBloomMockRecorder) Put(ctx, value interface{}) *gomock.Call
Put 指示对 Put 方法的预期调用。
参数：
- ctx：上下文对象
- value：要添加的元素值
返回值：
- *gomock.Call：用于设置期望的调用
type MockStore ¶
type MockStore struct {
// contains filtered or unexported fields
}
MockStore 是 Store 接口的 mock 实现。 用于在测试中模拟布隆过滤器底层数据存储的行为。
func NewMockStore ¶
func NewMockStore(ctrl *gomock.Controller) *MockStore
NewMockStore 创建一个新的 MockStore 实例。
参数：
- ctrl：gomock 控制器实例，用于管理 mock 对象
返回值：
- *MockStore：新创建的 mock 实例
func (*MockStore) Add ¶
Add 模拟了 Store 接口的 Add 方法。 用于将一组 hash 值添加到指定 key 对应的存储中。
参数：
- ctx：上下文对象，用于控制请求的生命周期
- key：存储键名
- hash：要添加的哈希值列表
返回值：
- error：添加过程中发生的错误
func (*MockStore) EXPECT ¶
func (m *MockStore) EXPECT() *MockStoreMockRecorder
EXPECT 返回一个对象，允许调用者指示预期的使用。
返回值：
- *MockStoreMockRecorder：用于设置期望的调用记录器
type MockStoreMockRecorder ¶
type MockStoreMockRecorder struct {
// contains filtered or unexported fields
}
MockStoreMockRecorder 是 MockStore 的调用记录器。 用于记录和验证对 MockStore 的方法调用。
func (*MockStoreMockRecorder) Add ¶
func (mr *MockStoreMockRecorder) Add(ctx, key, hash interface{}) *gomock.Call
Add 指示对 Add 方法的预期调用。
参数：
- ctx：上下文对象
- key：存储键名
- hash：要添加的哈希值列表
返回值：
- *gomock.Call：用于设置期望的调用
func (*MockStoreMockRecorder) Exist ¶
func (mr *MockStoreMockRecorder) Exist(ctx, key, hash interface{}) *gomock.Call
Exist 指示对 Exist 方法的预期调用。
参数：
- ctx：上下文对象
- key：存储键名
- hash：要判断的哈希值列表
返回值：
- *gomock.Call：用于设置期望的调用
type Option ¶
type Option func(*bloom)
Option 定义 NewBloom 的配置修改函数。
参数：
- *bloom: 待修改的布隆过滤器配置实例，由 NewBloom 在初始化阶段传入。
func WithExpectedElements ¶
WithExpectedElements 设置布隆过滤器预计要存储的元素数量。
参数：
- n: 预计元素数量，用于 NewBloom 计算位数组大小和 hash 次数；调用方应传入正数，当前实现不单独校验 0。
返回：
- Option: 应用于 NewBloom 的预计元素数配置项。
func WithFalsePositiveRate ¶
WithFalsePositiveRate 设置布隆过滤器的期望误判率。
参数：
- p: 期望误判率；NewBloom 会拒绝小于 0 或大于 1 的值。
返回：
- Option: 应用于 NewBloom 的误判率配置项。
func WithLogger ¶
WithLogger 设置布隆过滤器持有的日志记录器。
参数：
- logger: 日志记录器实例；当前核心读写路径不主动写日志，但会保存在实例配置中。
返回：
- Option: 应用于 NewBloom 的日志配置项。
func WithName ¶
WithName 设置布隆过滤器名称。
参数：
- name: 布隆过滤器名称；NewBloom 会拒绝空白名称，并使用该名称作为默认位图命名空间 key。
返回：
- Option: 应用于 NewBloom 的名称配置项。
type Store ¶
type Store interface {
// Exist 判断指定 key 对应的所有 hash 值是否都已存在。
//
// 参数：
// - ctx: 调用上下文，是否生效由具体 Store 实现决定。
// - key: 位图命名空间标识；不同 key 之间互不影响。
// - hash: 要判断的哈希值列表；为空时按全称判断语义表示没有缺失位。
//
// 返回：
// - bool: 所有哈希值是否都已存在：
// - false: 至少有一个哈希值不存在。
// - true: 所有哈希值都存在，或 hash 为空且实现未返回错误。
// - error: 查询过程中发生的错误。
Exist(ctx context.Context, key string, hash []uint64) (bool, error)
// Add 将一组 hash 值添加到指定 key 对应的存储中。
//
// 参数：
// - ctx: 调用上下文，是否生效由具体 Store 实现决定。
// - key: 位图命名空间标识；不同 key 之间互不影响。
// - hash: 要添加的哈希值列表；为空时不设置任何位。
//
// 返回：
// - error: 添加过程中发生的错误。
Add(ctx context.Context, key string, hash []uint64) error
}
Store 定义布隆过滤器底层位图存储接口。
key 标识一个位图命名空间；只有最终 Store key 不同时，对应位图才彼此隔离。 分组操作使用 "name:group" 直接拼接 Store key，不转义或校验分隔符；name 或 group 含有冒号时可能与其它 name/group 组合产生相同 Store key。 ctx 是否生效由具体实现决定，例如内存实现会忽略它，Redis 实现会将其传递给底层命令。
Source Files
Click to show internal directories.
Click to hide internal directories.