cuckoofilter

package
v2.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 27, 2022 License: MIT Imports: 10 Imported by: 0

Documentation

Overview

cuckoofilter redis扩展[RedisBloom](https://github.com/RedisBloom/RedisBloom)帮助模块,用于处理布隆过滤器

cuckoofilter redis扩展[RedisBloom](https://github.com/RedisBloom/RedisBloom)帮助模块,用于处理布隆过滤器

Index

Constants

This section is empty.

Variables

View Source 
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 

func AddWithRefreshTTL() optparams.Option[AddOpts]

AddWithhRefreshTTL 设置总是刷新,pipeline中无效

func AddWithRefreshTTLAtFirstTime 

func AddWithRefreshTTLAtFirstTime() optparams.Option[AddOpts]

AddWithRefreshTTLAtFirstTime 设置第一次创建key时使用MaxTTL设置过期,pipeline中无效

func AddWithTTL 

func AddWithTTL(t time.Duration) optparams.Option[AddOpts]

AddWithTTL 设置总是使用指定的ttl刷新key

func AddWithTTLAtFirstTime 

func AddWithTTLAtFirstTime(t time.Duration) optparams.Option[AddOpts]

AddWithTTLAtFirstTime 设置第一次创建key时使用指定的ttl设置过期,pipeline中无效

func AddWithoutNX 

func AddWithoutNX() optparams.Option[AddOpts]

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 

func WithAutoRefreshInterval(autoRefreshInterval string) optparams.Option[Options]

WithAutoRefreshInterval 设置自动刷新过期时间的设置

func WithKey 

func WithKey(key string) optparams.Option[Options]

WithKey 中间件通用设置,指定使用的键,注意设置后namespace依然有效

func WithMaxTTL 

func WithMaxTTL(maxTTL time.Duration) optparams.Option[Options]

WithMaxTTL 设置token消减间隔时长,单位s

func WithMiddlewaretype 

func WithMiddlewaretype(typename string) optparams.Option[Options]

WithMiddlewaretype 设置中间件类型

func WithNamespace 

func WithNamespace(ns ...string) optparams.Option[Options]

WithNamespace 中间件通用设置,指定锁的命名空间

func WithSpecifiedKey 

func WithSpecifiedKey(key string) optparams.Option[Options]

WithSpecifiedKey 中间件通用设置,指定使用的键,注意设置key后namespace将失效

func WithTaskCron 

func WithTaskCron(taskCron *cron.Cron) optparams.Option[Options]

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 

func (c *Cuckoofilter) CountItem(ctx context.Context, item string) (int64, error)

CountItem cuckoofilter中检查item存在的个数 @params item string @return int64 计数item的个数,如果报错则返回0

func (*Cuckoofilter) DelItem 

func (c *Cuckoofilter) DelItem(ctx context.Context, item string) (bool, error)

DelItem cuckoofilter中检查item存在的个数 @params item string @return bool item是否删除成功,true为删除成功,false表示不存在item无法删除

func (*Cuckoofilter) ExistsItem 

func (c *Cuckoofilter) ExistsItem(ctx context.Context, item string) (bool, error)

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 

func (c *Cuckoofilter) MExistsItem(ctx context.Context, items ...string) (map[string]bool, error)

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]
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.