Documentation ¶
Overview ¶
cuckoofilter redis扩展[RedisBloom](https://github.com/RedisBloom/RedisBloom)帮助模块,用于处理布隆过滤器
cuckoofilter redis扩展[RedisBloom](https://github.com/RedisBloom/RedisBloom)帮助模块,用于处理布隆过滤器
Index ¶
- Variables
- func AddItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string, ...) (*redisbloomhelper.BoolValPlacehold, error)
- func AddWithRefreshTTL() optparams.Option[AddOpts]
- func AddWithRefreshTTLAtFirstTime() optparams.Option[AddOpts]
- func AddWithTTL(t time.Duration) optparams.Option[AddOpts]
- func AddWithTTLAtFirstTime(t time.Duration) optparams.Option[AddOpts]
- func AddWithoutNX() optparams.Option[AddOpts]
- func CountItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string) *redisbloomhelper.Int64ValPlacehold
- func DelItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string) *redisbloomhelper.BoolValPlacehold
- func ExistsItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string) *redisbloomhelper.BoolValPlacehold
- func InsertPipe(pipe redis.Pipeliner, ctx context.Context, key string, items []string, ...) (*redisbloomhelper.BoolMapPlacehold, error)
- func InsertWithCapacity(capacity int64) optparams.Option[InsertOpts]
- func InsertWithExpansion(expansion int64) optparams.Option[InsertOpts]
- func InsertWithNoCreate() optparams.Option[InsertOpts]
- func InsertWithRefreshTTL() optparams.Option[InsertOpts]
- func InsertWithRefreshTTLAtFirstTime() optparams.Option[InsertOpts]
- func InsertWithTTL(t time.Duration) optparams.Option[InsertOpts]
- func InsertWithTTLAtFirstTime(t time.Duration) optparams.Option[InsertOpts]
- func InsertWithoutNX() optparams.Option[InsertOpts]
- func MAddItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, items []string, ...) (*redisbloomhelper.BoolMapPlacehold, error)
- func MExistsItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, items ...string) (*redisbloomhelper.BoolMapPlacehold, error)
- func ReservePipe(pipe redis.Pipeliner, ctx context.Context, key string, capacity int64, ...) *redis.Cmd
- func ReserveWithBucketSize(bucketsize int64) optparams.Option[ReserveOpts]
- func ReserveWithExpansion(expansion int64) optparams.Option[ReserveOpts]
- func ReserveWithMaxIterations(maxiterations int64) optparams.Option[ReserveOpts]
- func ReserveWithRefreshTTL() optparams.Option[ReserveOpts]
- func ReserveWithTTL(t time.Duration) optparams.Option[ReserveOpts]
- func WithAutoRefreshInterval(autoRefreshInterval string) optparams.Option[Options]
- func WithKey(key string) optparams.Option[Options]
- func WithMaxTTL(maxTTL time.Duration) optparams.Option[Options]
- func WithMiddlewaretype(typename string) optparams.Option[Options]
- func WithNamespace(ns ...string) optparams.Option[Options]
- func WithSpecifiedKey(key string) optparams.Option[Options]
- func WithTaskCron(taskCron *cron.Cron) optparams.Option[Options]
- type AddOpts
- type Cuckoofilter
- func (c *Cuckoofilter) AddItem(ctx context.Context, item string, opts ...optparams.Option[AddOpts]) (bool, error)
- func (c *Cuckoofilter) Clean(ctx context.Context) error
- func (c *Cuckoofilter) CountItem(ctx context.Context, item string) (int64, error)
- func (c *Cuckoofilter) DelItem(ctx context.Context, item string) (bool, error)
- func (c *Cuckoofilter) ExistsItem(ctx context.Context, item string) (bool, error)
- func (c *Cuckoofilter) Info(ctx context.Context) (*CuckoofilterInfo, error)
- func (c *Cuckoofilter) Insert(ctx context.Context, items []string, opts ...optparams.Option[InsertOpts]) (map[string]bool, error)
- func (c *Cuckoofilter) MAddItem(ctx context.Context, items []string, opts ...optparams.Option[AddOpts]) (map[string]bool, error)
- func (c *Cuckoofilter) MExistsItem(ctx context.Context, items ...string) (map[string]bool, error)
- func (c *Cuckoofilter) Reserve(ctx context.Context, capacity int64, opts ...optparams.Option[ReserveOpts]) error
- type CuckoofilterInfo
- type InfoPlacehold
- type InsertOpts
- type Options
- type ReserveOpts
Constants ¶
This section is empty.
Variables ¶
var Defaultopt = Options{ Middlewaretype: "redis-ext-cuckoofilter", MiddlewareOpts: []optparams.Option[middlewarehelper.Options]{}, }
Functions ¶
func AddItemPipe ¶
func AddItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string, opts ...optparams.Option[AddOpts]) (*redisbloomhelper.BoolValPlacehold, error)
AddItemPipe cuckoofilter中设置物品, 注意如果不设置NX则会重复向表中插入数据,返回全部为false,尽量带nx插入 @params key string 使用的key @params item string 要插入的物品 @params opts ...optparams.Option[AddOpts] 设置add行为的附加参数 @returns bool 设置的物品是否已经存在,true表示已经存在,不会插入
func AddWithRefreshTTL ¶
AddWithhRefreshTTL 设置总是刷新,pipeline中无效
func AddWithRefreshTTLAtFirstTime ¶
AddWithRefreshTTLAtFirstTime 设置第一次创建key时使用MaxTTL设置过期,pipeline中无效
func AddWithTTL ¶
AddWithTTL 设置总是使用指定的ttl刷新key
func AddWithTTLAtFirstTime ¶
AddWithTTLAtFirstTime 设置第一次创建key时使用指定的ttl设置过期,pipeline中无效
func AddWithoutNX ¶
AddWithoutNX 设置cuckoofilter中只存在不存在都会添加
func CountItemPipe ¶
func CountItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string) *redisbloomhelper.Int64ValPlacehold
CountItemPipe cuckoofilter中检查item存在的个数 @params key string 使用的key @params item string @return int64 计数item的个数,如果报错则返回0
func DelItemPipe ¶
func DelItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string) *redisbloomhelper.BoolValPlacehold
DelItemPipe cuckoofilter中检查item存在的个数 @params key string 使用的key @params item string @return bool item是否删除成功,true为删除成功,false表示不存在item无法删除
func ExistsItemPipe ¶
func ExistsItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, item string) *redisbloomhelper.BoolValPlacehold
ExistsItemPipe cuckoofilter中检查是否已经存在 @params key string 使用的key @params item string 待检查的物品 @return bool 物品是否已经存在
func InsertPipe ¶
func InsertPipe(pipe redis.Pipeliner, ctx context.Context, key string, items []string, opts ...optparams.Option[InsertOpts]) (*redisbloomhelper.BoolMapPlacehold, error)
InsertPipe 向一个cuckoofilter中插入数据,如果不存在则创建 @params key string 使用的key @params items []string 待插入物品 @params opts ...optparams.Option[InsertOpts] 可选设置项
func InsertWithCapacity ¶
func InsertWithCapacity(capacity int64) optparams.Option[InsertOpts]
InsertWithCapacity 容量,预估物品的数量.当过滤器已经存在时用于创建过滤器.容量越大检索效率越低,但如果超出容量则会默认使用子过滤器扩容,这对检索效率的影响更大.当`NOCREATE`存在时这个设置将失效
func InsertWithExpansion ¶
func InsertWithExpansion(expansion int64) optparams.Option[InsertOpts]
InsertWithExpansion 当达到容量时进行扩容. 使用范围: bloomfilter bloomfilter会创建一个额外的子过滤器,新子过滤器的大小是最后一个子过滤器的大小乘以扩展设置的值. 如果要存储在过滤器中的元素数量未知我们建议您使用`2`或更多的扩展来减少子过滤器的数量; 否则我们建议您使用1的扩展来减少内存消耗.默认扩展值为 2 cuckoofilter则会扩容到2^n
func InsertWithNoCreate ¶
func InsertWithNoCreate() optparams.Option[InsertOpts]
InsertWithNoCreate 如果过滤器不存在则不创建它.这可以用于过滤器创建和过滤器添加之间需要严格分离的地方.`NOCREATE`的优先级高于`CAPACITY`和`ERROR`
func InsertWithRefreshTTL ¶
func InsertWithRefreshTTL() optparams.Option[InsertOpts]
InsertWithhRefreshTTL 设置总是刷新
func InsertWithRefreshTTLAtFirstTime ¶
func InsertWithRefreshTTLAtFirstTime() optparams.Option[InsertOpts]
InsertWithRefreshTTLAtFirstTime 设置第一次创建key时使用MaxTTL设置过期
func InsertWithTTL ¶
func InsertWithTTL(t time.Duration) optparams.Option[InsertOpts]
InsertWithTTL 设置总是使用指定的ttl刷新key
func InsertWithTTLAtFirstTime ¶
func InsertWithTTLAtFirstTime(t time.Duration) optparams.Option[InsertOpts]
InsertWithTTLAtFirstTime 设置第一次创建key时使用指定的ttl设置过期
func InsertWithoutNX ¶
func InsertWithoutNX() optparams.Option[InsertOpts]
InsertWithoutNX 设置cuckoofilter中无论存在不存在物品都进行插入
func MAddItemPipe ¶
func MAddItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, items []string, opts ...optparams.Option[AddOpts]) (*redisbloomhelper.BoolMapPlacehold, error)
MAddItemPipe cuckoofilter中设置多个物品,使用的是INSERT或者INSERTNX命令 注意如果不设置NX则会重复向表中插入数据,返回全部为false,尽量带nx插入 @params key string 使用的key @params item []string 要插入的物品 @params opts ...optparams.Option[AddOpts] 设置add行为的附加参数 @returns map[string]bool 设置的物品是否在设置前已经存在,true表示已经存在,并未插入
func MExistsItemPipe ¶
func MExistsItemPipe(pipe redis.Pipeliner, ctx context.Context, key string, items ...string) (*redisbloomhelper.BoolMapPlacehold, error)
MExistsItemPipe cuckoofilter中检查复数物品是否已经存在 @params key string 使用的key @params item ...string 待检查的物品 @return map[string]bool 检查的物品是否已经存在
func ReservePipe ¶
func ReservePipe(pipe redis.Pipeliner, ctx context.Context, key string, capacity int64, opts ...optparams.Option[ReserveOpts]) *redis.Cmd
ReservePipe 创建一个cuckoofilter,如果有设置maxttl,则会同时为其设置一个过期 @params key string 使用的key @params capacity int64 容量,预估物品的数量,容量越大检索效率越低,但如果超出容量则会默认使用子过滤器扩容,这对检索效率的影响更大 @params opts ...optparams.Option[ReserveOpts] 可选设置项
func ReserveWithBucketSize ¶
func ReserveWithBucketSize(bucketsize int64) optparams.Option[ReserveOpts]
ReserveWithBucketsize 每个存储桶中的项目数.较高的桶大小值会提高填充率,但也会导致更高的错误率和稍慢的性能.
func ReserveWithExpansion ¶
func ReserveWithExpansion(expansion int64) optparams.Option[ReserveOpts]
ReserveWithExpansion 当达到容量时进行扩容. bloomfilter会创建一个额外的子过滤器,新子过滤器的大小是最后一个子过滤器的大小乘以扩展设置的值. 如果要存储在过滤器中的元素数量未知我们建议您使用`2`或更多的扩展来减少子过滤器的数量; 否则我们建议您使用1的扩展来减少内存消耗.默认扩展值为 2 cuckoofilter则会扩容到2^n
func ReserveWithMaxIterations ¶
func ReserveWithMaxIterations(maxiterations int64) optparams.Option[ReserveOpts]
ReserveWithMaxIterations 在声明过滤器已满并创建附加过滤器之前尝试在存储桶之间交换项目的次数.较低的值对性能更好,较高的值对过滤器填充率更好.
func ReserveWithRefreshTTL ¶
func ReserveWithRefreshTTL() optparams.Option[ReserveOpts]
ReserveWithhRefreshTTL 设置使用maxttl设置key的过期,pipeline无效
func ReserveWithTTL ¶
func ReserveWithTTL(t time.Duration) optparams.Option[ReserveOpts]
ReserveWithTTL 设置使用指定的ttl设置key的过期
func WithAutoRefreshInterval ¶
WithAutoRefreshInterval 设置自动刷新过期时间的设置
func WithMaxTTL ¶
WithMaxTTL 设置token消减间隔时长,单位s
func WithMiddlewaretype ¶
WithMiddlewaretype 设置中间件类型
func WithNamespace ¶
WithNamespace 中间件通用设置,指定锁的命名空间
func WithSpecifiedKey ¶
WithSpecifiedKey 中间件通用设置,指定使用的键,注意设置key后namespace将失效
func WithTaskCron ¶
WithTaskCron 设置定时器
Types ¶
type AddOpts ¶
type AddOpts struct { NX bool RefreshOpts []optparams.Option[middlewarehelper.RefreshOpt] }
AddOpt filter添加元素物品的参数
type Cuckoofilter ¶
type Cuckoofilter struct { *middlewarehelper.MiddleWareAbc // contains filtered or unexported fields }
CuckooFilter 布谷鸟过滤器对象 [布谷鸟过滤器](https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) 常用于去重场景,其原理来自[cuckoo hash](https://en.wikipedia.org/wiki/Cuckoo_hashing)这种算法.这种算法的特点可以总结为`鸠占鹊巢`. 最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希,得到桶中的两个位置,此时 1. 如果两个位置都为为空则将key随机存入其中一个位置 2. 如果只有一个位置为空则存入为空的位置 3. 如果都不为空,则随机踢出一个元素踢出的元素再重新计算哈希找到相应的位置 当然假如存在绝对的空间不足那老是踢出也不是办法,所以一般会设置一个踢出阈值(`MaxIteration`),如果在某次插入行为过程中连续踢出超过阈值则进行扩容
布谷鸟过滤器的布谷鸟哈希表的基本单位称为条目(entry),每个条目存储一个指纹(fingerprint),指纹指的是使用一个哈希函数生成的n位比特位,n的具体大小由所能接受的误判率来设置,通常都比较小. 哈希表通常由1个桶数组组成
- 其中一个桶可以有多个条目,单个桶中的的条目数即为`BucketSize`.`BucketSize`的大小会对搜索效存储效率都有影响. +`BucketSize`越小则假阳性率越大,表的利用率也就越低.默认的`BucketSize`为2,可以有84%的负载因子α当设置为3时可以到95%,设置为4是可以到98%
- BucketSize`越大就需要越长的指纹才能保持相同的假阳性率(即b越大f越大).使用较大的桶时每次查找都会检查更多的条目,从而有更大的概率产生指纹冲突.
- 一个桶数组中包含桶的个数即为`NumberOfBuckets`,我们如果可以预估到总量的话可以使用如下公式进行设置 2^(n-1)< capacity < NumberOfBuckets*BucketSize = 2^n 在初始化时我们可以指定capacity和BucketSize,NumberOfBuckets则是用上面的关系自动分配的
布谷鸟过滤器一般采用2个桶数组,同时采取了两个并不独立的哈希函数(即下面的hash和𝑓𝑖𝑛𝑔𝑒𝑟𝑝𝑟𝑖𝑛𝑡)计算一个物品的索引和指纹:
i_1=ℎ𝑎𝑠ℎ(𝑥) 𝑓=𝑓𝑖𝑛𝑔𝑒𝑟𝑝𝑟𝑖𝑛𝑡(𝑥) i_2=i_1 xor ℎ𝑎𝑠ℎ(𝑓)
i_1和i_2 即计算出来哈希表中两个桶所在的索引,这样我们可以得到一个坐标即(i_1,i_2)和一个数据的指纹(f),插入时则使用上面布谷鸟哈希方法插入;查询则是通过这个坐标取出两个桶中的数据匹配是否存在指纹. 如果要删除一个已经存在的物品也是一样,确定好坐标和指纹后在桶中找出匹配的条目清空即可.不过也要注意删除未被添加的物品可能会引起被添加的物品被删除,因此需要谨慎使用
布谷过滤器在错误率要求小于3%的场景下空间性能优于布隆过滤器(实际应用场景下常常满足),而且支持动态删除物品. 而且布谷鸟过滤器按照普通设计只有两个桶,相比于布隆过滤器的多个Hash函数多次访存在数据量很大不能全部装载在内存中的情况下往往可以提供更好的访问效率. 布谷过滤器也有其相应的缺点: 1. 当装填因子较高的时候容易出现循环的问题--即插入失败的情况. 2. 就是访问空间地址不连续,通常可以认为是随机的,这个问题在布隆过滤器中也是一样.这样严重破坏了程序局部性,对于Cache流水线来说非常不利.
func New ¶
func New(cli redis.UniversalClient, opts ...optparams.Option[Options]) (*Cuckoofilter, error)
New 创建一个新的令牌桶对象 @params cli redis.UniversalClient @params opts ...optparams.Option[Options] 设置对象的可选参数
func (*Cuckoofilter) AddItem ¶
func (c *Cuckoofilter) AddItem(ctx context.Context, item string, opts ...optparams.Option[AddOpts]) (bool, error)
AddItem cuckoofilter中设置物品, 注意如果不设置NX则会重复向表中插入数据,返回全部为false,尽量带nx插入 @params item string 要插入的物品 @params opts ...optparams.Option[AddOpts] 设置add行为的附加参数 @returns bool 设置的物品是否已经存在,true表示已经存在,不会插入
func (*Cuckoofilter) Clean ¶
func (c *Cuckoofilter) Clean(ctx context.Context) error
Clean 清除cuckoofilter的key
func (*Cuckoofilter) CountItem ¶
CountItem cuckoofilter中检查item存在的个数 @params item string @return int64 计数item的个数,如果报错则返回0
func (*Cuckoofilter) DelItem ¶
DelItem cuckoofilter中检查item存在的个数 @params item string @return bool item是否删除成功,true为删除成功,false表示不存在item无法删除
func (*Cuckoofilter) ExistsItem ¶
ExistsItem cuckoofilter中检查是否已经存在 @params item string 待检查的物品 @return bool 物品是否已经存在
func (*Cuckoofilter) Info ¶
func (c *Cuckoofilter) Info(ctx context.Context) (*CuckoofilterInfo, error)
Info 查看指定cuckoofilter的状态
func (*Cuckoofilter) Insert ¶
func (c *Cuckoofilter) Insert(ctx context.Context, items []string, opts ...optparams.Option[InsertOpts]) (map[string]bool, error)
Insert 向一个cuckoofilter中插入数据,如果不存在则创建 @params items []string 待插入物品 @params opts ...optparams.Option[InsertOpts] 可选设置项
func (*Cuckoofilter) MAddItem ¶
func (c *Cuckoofilter) MAddItem(ctx context.Context, items []string, opts ...optparams.Option[AddOpts]) (map[string]bool, error)
MAddItem cuckoofilter中设置多个物品,使用的是INSERT或者INSERTNX命令 注意如果不设置NX则会重复向表中插入数据,返回全部为false,尽量带nx插入 @params item []string 要插入的物品 @params opts ...optparams.Option[AddOpts] 设置add行为的附加参数 @returns map[string]bool 设置的物品是否在设置前已经存在,true表示已经存在,并未插入
func (*Cuckoofilter) MExistsItem ¶
MExistsItem cuckoofilter中检查复数物品是否已经存在 @params item ...string 待检查的物品 @return map[string]bool 检查的物品是否已经存在
func (*Cuckoofilter) Reserve ¶
func (c *Cuckoofilter) Reserve(ctx context.Context, capacity int64, opts ...optparams.Option[ReserveOpts]) error
Reserve 创建一个cuckoofilter,如果有设置maxttl,则会同时为其设置一个过期 @params capacity int64 容量,预估物品的数量,容量越大检索效率越低,但如果超出容量则会默认使用子过滤器扩容,这对检索效率的影响更大 @params opts ...optparams.Option[ReserveOpts] 可选设置项
type CuckoofilterInfo ¶
type CuckoofilterInfo struct { Size int64 `json:"Size"` NumberOfBuckets int64 `json:"NumberOfBuckets"` NumberOfFilter int64 `json:"NumberOfFilter"` NumberOfItemsInserted int64 `json:"NumberOfItemsInserted"` NumberOfItemsDeleted int64 `json:"NumberOfItemsDeleted"` BucketSize int64 `json:"BucketSize"` ExpansionRate int64 `json:"ExpansionRate"` MaxIteration int64 `json:"MaxIteration"` }
CuckoofilterInfo cuckoofilter状态信息
type InfoPlacehold ¶
type InfoPlacehold struct { Ck string Cmd *redis.Cmd }
func InfoPipe ¶
func InfoPipe(pipe redis.Pipeliner, ctx context.Context, key string) *InfoPlacehold
InfoPipe 查看指定cuckoofilter的状态 @params key string 使用的key
func (*InfoPlacehold) Result ¶
func (r *InfoPlacehold) Result() (*CuckoofilterInfo, error)
type InsertOpts ¶
type InsertOpts struct { NoCreate bool Capacity int64 Expansion int64 NX bool RefreshOpts []optparams.Option[middlewarehelper.RefreshOpt] }
type Options ¶
type Options struct { Middlewaretype string MiddlewareOpts []optparams.Option[middlewarehelper.Options] //初始化Middleware的配置 }
Options broker的配置
type ReserveOpts ¶
type ReserveOpts struct { Expansion int64 BucketSize int64 MaxIterations int64 RefreshOpts []optparams.Option[middlewarehelper.RefreshOpt] }