README
¶
rueidisprob
A Probabilistic Data Structures without Redis Stack.
Features
Bloom Filter
It is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed.
Example:
package main
import (
"context"
"fmt"
"github.com/redis/rueidis"
"github.com/redis/rueidis/rueidisprob"
)
func main() {
client, err := rueidis.NewClient(rueidis.ClientOption{
InitAddress: []string{"localhost:6379"},
})
if err != nil {
panic(err)
}
bf, err := rueidisprob.NewBloomFilter(client, "bloom_filter", 1000, 0.01)
err = bf.Add(context.Background(), "hello")
if err != nil {
panic(err)
}
err = bf.Add(context.Background(), "world")
if err != nil {
panic(err)
}
exists, err := bf.Exists(context.Background(), "hello")
if err != nil {
panic(err)
}
fmt.Println(exists) // true
exists, err = bf.Exists(context.Background(), "world")
if err != nil {
panic(err)
}
fmt.Println(exists) // true
}
Counting Bloom Filter
It is a variation of the standard Bloom filter that adds a counting mechanism to each element. This allows for the filter to count the number of times an element has been added to the filter. And it allows for the removal of elements from the filter.
Example:
package main
import (
"context"
"fmt"
"github.com/redis/rueidis"
"github.com/redis/rueidis/rueidisprob"
)
func main() {
client, err := rueidis.NewClient(rueidis.ClientOption{
InitAddress: []string{"localhost:6379"},
})
if err != nil {
panic(err)
}
cbf, err := rueidisprob.NewCountingBloomFilter(client, "counting_bloom_filter", 1000, 0.01)
err = cbf.Add(context.Background(), "hello")
if err != nil {
panic(err)
}
err = cbf.Add(context.Background(), "world")
if err != nil {
panic(err)
}
exists, err := cbf.Exists(context.Background(), "hello")
if err != nil {
panic(err)
}
fmt.Println(exists) // true
exists, err = cbf.Exists(context.Background(), "world")
if err != nil {
panic(err)
}
fmt.Println(exists) // true
count, err := cbf.Count(context.Background())
if err != nil {
panic(err)
}
fmt.Println(count) // 2
err = cbf.Remove(context.Background(), "hello")
if err != nil {
panic(err)
}
exists, err = cbf.Exists(context.Background(), "hello")
if err != nil {
panic(err)
}
fmt.Println(exists) // false
count, err = cbf.Count(context.Background())
if err != nil {
panic(err)
}
fmt.Println(count) // 1
}
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
View Source
var ( ErrEmptyName = errors.New("name cannot be empty") ErrFalsePositiveRateLessThanEqualZero = errors.New("false positive rate cannot be less than or equal to zero") ErrFalsePositiveRateGreaterThanOne = errors.New("false positive rate cannot be greater than 1") ErrBitsSizeZero = errors.New("bits size cannot be zero") ErrBitsSizeTooLarge = errors.New("bits size is too large") )
View Source
var ( ErrEmptyCountingBloomFilterName = errors.New("name cannot be empty") ErrCountingBloomFilterFalsePositiveRateLessThanEqualZero = errors.New("false positive rate cannot be less than or equal to zero") ErrCountingBloomFilterFalsePositiveRateGreaterThanOne = errors.New("false positive rate cannot be greater than 1") ErrCountingBloomFilterBitsSizeZero = errors.New("bits size cannot be zero") )
Functions ¶
This section is empty.
Types ¶
type BloomFilter ¶
type BloomFilter interface {
// Add adds an item to the Bloom filter.
Add(ctx context.Context, key string) error
// AddMulti adds one or more items to the Bloom filter.
// NOTE: If keys are too many, it can block the Redis server for a long time.
AddMulti(ctx context.Context, keys []string) error
// Exists checks if an item is in the Bloom filter.
Exists(ctx context.Context, key string) (bool, error)
// ExistsMulti checks if one or more items are in the Bloom filter.
// Returns a slice of bool values where each bool indicates whether the corresponding key was found.
ExistsMulti(ctx context.Context, keys []string) ([]bool, error)
// Reset resets the Bloom filter.
Reset(ctx context.Context) error
// Delete deletes the Bloom filter.
Delete(ctx context.Context) error
// Count returns count of items in Bloom filter.
Count(ctx context.Context) (uint64, error)
}
BloomFilter based on Redis Bitmaps. BloomFilter uses 128-bit murmur3 hash function.
func NewBloomFilter ¶
func NewBloomFilter( client rueidis.Client, name string, expectedNumberOfItems uint, falsePositiveRate float64, ) (BloomFilter, error)
NewBloomFilter creates a new Bloom filter. NOTE: 'name:c' is used as a counter key in the Redis to keep track of the number of items in the Bloom filter for Count method.
type CountingBloomFilter ¶ added in v1.0.34
type CountingBloomFilter interface {
// Add adds an item to the Counting Bloom Filter.
Add(ctx context.Context, key string) error
// AddMulti adds one or more items to the Counting Bloom Filter.
// NOTE: If keys are too many, it can block the Redis server for a long time.
AddMulti(ctx context.Context, keys []string) error
// Exists checks if an item is in the Counting Bloom Filter.
Exists(ctx context.Context, key string) (bool, error)
// ExistsMulti checks if one or more items are in the Counting Bloom Filter.
// Returns a slice of bool values where each bool indicates
// whether the corresponding key was found.
ExistsMulti(ctx context.Context, keys []string) ([]bool, error)
// Remove removes an item from the Counting Bloom Filter.
Remove(ctx context.Context, key string) error
// RemoveMulti removes one or more items from the Counting Bloom Filter.
// NOTE: If keys are too many, it can block the Redis server for a long time.
RemoveMulti(ctx context.Context, keys []string) error
// Delete deletes the Counting Bloom Filter.
Delete(ctx context.Context) error
// ItemMinCount returns the minimum count of item in the Counting Bloom Filter.
// If the item is not in the Counting Bloom Filter, it returns a zero value.
// Minimum count is not always accurate because of the hash collisions.
ItemMinCount(ctx context.Context, key string) (uint64, error)
// ItemMinCountMulti returns the minimum count of items in the Counting Bloom Filter.
// If the item is not in the Counting Bloom Filter, it returns a zero value.
// Minimum count is not always accurate because of the hash collisions.
ItemMinCountMulti(ctx context.Context, keys []string) ([]uint64, error)
// Count returns count of items in Counting Bloom Filter.
Count(ctx context.Context) (uint64, error)
}
CountingBloomFilter based on Hashes. CountingBloomFilter uses 128-bit murmur3 hash function.
func NewCountingBloomFilter ¶ added in v1.0.34
func NewCountingBloomFilter( client rueidis.Client, name string, expectedNumberOfItems uint, falsePositiveRate float64, ) (CountingBloomFilter, error)
NewCountingBloomFilter creates a new Counting Bloom Filter. NOTE: 'name:cbf:c' is used as a counter key in the Redis and 'name:cbf' is used as a filter key in the Redis to keep track of the number of items in the Counting Bloom Filter for Count method.
Source Files
Click to show internal directories.
Click to hide internal directories.