bloom

README

Bloom Filter

Space-efficient probabilistic set membership using Redis.

Overview

A Bloom filter is a space-efficient probabilistic data structure that can tell you:

• If an element is definitely not in a set
• If an element is possibly in a set

Installation

import "github.com/azghr/mesh/bloom"

Usage

// Create filter: name, expected items, false positive rate
bf := bloom.New(redisClient, "users", 100000, 0.01)

// Add items
bf.Add(ctx, "user:123")

// Check existence
exists, _ := bf.Exists(ctx, "user:123") // returns true

exists, _ := bf.Exists(ctx, "user:456") // returns false

API

New(client, name, expectedItems, falsePositive) *Filter

Creates a filter.

bf.Add(ctx, item) error

Adds an item.

bf.Exists(ctx, item) (bool, error)

Checks if item might exist.

bf.ExistsMany(ctx, items) (map[string]bool, error)

Checks multiple items.

bf.Reset(ctx) error

Clears the filter.

bf.Stats(ctx) (Stats, error)

Returns statistics.

Example

package main

import (
    "context"
    "log"

    "github.com/azghr/mesh/bloom"
    "github.com/redis/go-redis/v9"
)

func main() {
    client := redis.NewClient(&redis.Options{Addr: "localhost:6379"})
    bf := bloom.New(client, "cache-keys", 10000, 0.01)

    ctx := context.Background()

    // Add cache keys
    bf.AddMany(ctx, []string{"user:1", "user:2", "user:3"})

    // Check before querying database
    exists, _ := bf.Exists(ctx, "user:1")
    if exists {
        log.Println("Might be in cache")
    }
}

Documentation

Overview

Package bloom provides a Bloom filter implementation using Redis for storage.

A Bloom filter is a space-efficient probabilistic data structure that can tell you if an element is definitely not in a set or possibly in a set.

Features

• Redis-backed storage for distributed use
• Configurable expected items and false positive rate
• Add, Exists, and Reset operations
• Multiple independent filters

Usage

bf := bloom.New(redisClient, "my-filter", 10000, 0.01)
bf.Add(ctx, "item")
exists := bf.Exists(ctx, "item")

Index

• type Filter
  • func New(client *redis.Client, name string, expectedItems int, falsePositive float64) *Filter
  • func (f *Filter) Add(ctx context.Context, item string) error
  • func (f *Filter) AddMany(ctx context.Context, items []string) error
  • func (f *Filter) Count(ctx context.Context) (uint64, error)
  • func (f *Filter) Exists(ctx context.Context, item string) (bool, error)
  • func (f *Filter) ExistsMany(ctx context.Context, items []string) (map[string]bool, error)
  • func (f *Filter) Reset(ctx context.Context) error
  • func (f *Filter) Stats(ctx context.Context) (Stats, error)
• type Stats

Types

type Filter

type Filter struct {
	// contains filtered or unexported fields
}

Filter represents a Bloom filter

func New

func New(client *redis.Client, name string, expectedItems int, falsePositive float64) *Filter

New creates a new Bloom filter

expectedItems: number of items expected to be added
falsePositive: desired false positive rate (0.0 to 1.0)

Example:

bf := bloom.New(client, "users", 100000, 0.01)

func (*Filter) Add

func (f *Filter) Add(ctx context.Context, item string) error

Add adds an item to the filter

bf.Add(ctx, "user:123")

func (*Filter) AddMany

func (f *Filter) AddMany(ctx context.Context, items []string) error

AddMany adds multiple items to the filter

func (*Filter) Count

func (f *Filter) Count(ctx context.Context) (uint64, error)

Count returns the approximate number of items in the filter

func (*Filter) Exists

func (f *Filter) Exists(ctx context.Context, item string) (bool, error)

Exists checks if an item might be in the filter

Returns true if the item possibly exists, false if definitely not

func (*Filter) ExistsMany

func (f *Filter) ExistsMany(ctx context.Context, items []string) (map[string]bool, error)

ExistsMany checks multiple items

Returns a map of item to existence

func (*Filter) Reset

func (f *Filter) Reset(ctx context.Context) error

Reset clears all items from the filter

func (*Filter) Stats

func (f *Filter) Stats(ctx context.Context) (Stats, error)

Stats returns filter statistics

type Stats

type Stats struct {
	Name          string  `json:"name"`
	ExpectedItems int     `json:"expected_items"`
	FalsePositive float64 `json:"false_positive_rate"`
	NumBits       uint64  `json:"num_bits"`
	NumHashes     uint64  `json:"num_hashes"`
	ItemCount     uint64  `json:"item_count"`
}

Stats represents filter statistics