bloom

Documentation

Overview

Package bloom provides Bloom Filter implementations for ArcTable. Bloom filters provide fast negative membership tests. They are optional optimization hooks behind ArcTable implementations, not semantic state or part of the root-centric trust boundary.

Bloom Filter properties:

• False negative: If Test returns false, the item is definitely not in the set
• False positive: If Test returns true, the item might be in the set

Package bloom provides Bloom Filter implementations for ArcTable.

Package bloom provides a standard Bloom Filter implementation. This is a simple implementation using murmur3 hashing and bitset.

Index

• Constants
• type BloomCache
  • func NewBloomCache(kv kvstore.KVStore, maxSize int) *BloomCache
  • func NewBloomCacheWithConfig(kv kvstore.KVStore, maxSize int, defaultConfig *NamespaceConfig) *BloomCache
  • func (bc *BloomCache) Add(ctx context.Context, namespace string, paths []string) error
  • func (bc *BloomCache) Clear()
  • func (bc *BloomCache) CreateNamespace(ctx context.Context, namespace string, cfg *NamespaceConfig) error
  • func (bc *BloomCache) DefaultConfig() *NamespaceConfig
  • func (bc *BloomCache) DeleteNamespace(ctx context.Context, namespace string) error
  • func (bc *BloomCache) Get(ctx context.Context, namespace string) (*StandardBloom, error)
  • func (bc *BloomCache) GetNamespaceMeta(ctx context.Context, namespace string) (*NamespaceMeta, error)
  • func (bc *BloomCache) Invalidate(namespace string)
  • func (bc *BloomCache) MightContain(ctx context.Context, namespace string, path string) (bool, error)
  • func (bc *BloomCache) MightContainBatch(ctx context.Context, namespace string, paths []string) (map[string]bool, error)
  • func (bc *BloomCache) Size() int
  • func (bc *BloomCache) UpdateNamespaceMeta(ctx context.Context, namespace string, meta *NamespaceMeta) error
• type BloomFilter
• type NamespaceConfig
  • func DefaultNamespaceConfig() *NamespaceConfig
• type NamespaceMeta
• type StandardBloom
  • func NewStandardBloom(expectedItems int, falsePositiveRate float64) *StandardBloom
  • func NewStandardBloomFromData(k, m uint, bitsetBytes []byte) (*StandardBloom, error)
  • func (b *StandardBloom) Add(item []byte)
  • func (b *StandardBloom) Bitset() []byte
  • func (b *StandardBloom) Clear()
  • func (b *StandardBloom) EstimatedFalsePositiveRate() float64
  • func (b *StandardBloom) K() uint
  • func (b *StandardBloom) M() uint
  • func (b *StandardBloom) MarshalBinary() ([]byte, error)
  • func (b *StandardBloom) OptimalItemCount() uint64
  • func (b *StandardBloom) Size() uint64
  • func (b *StandardBloom) Test(item []byte) bool
  • func (b *StandardBloom) UnmarshalBinary(data []byte) error

Constants

const (
	DefaultExpectedItems     = 10000
	DefaultFalsePositiveRate = 0.01
)

Default bloom filter parameters.

Types

type BloomCache

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

BloomCache is an independent component that manages bloom filters for all namespaces. It provides LRU caching and persistence via KVStore.

func NewBloomCache

func NewBloomCache(kv kvstore.KVStore, maxSize int) *BloomCache

NewBloomCache creates a new BloomCache with the given KVStore and cache size.

func NewBloomCacheWithConfig

func NewBloomCacheWithConfig(kv kvstore.KVStore, maxSize int, defaultConfig *NamespaceConfig) *BloomCache

NewBloomCacheWithConfig creates a new BloomCache with custom default config.

func (*BloomCache) Add

func (bc *BloomCache) Add(ctx context.Context, namespace string, paths []string) error

Add adds paths to a namespace's bloom filter and persists it.

func (*BloomCache) Clear

func (bc *BloomCache) Clear()

Clear removes all entries from the cache.

func (*BloomCache) CreateNamespace

func (bc *BloomCache) CreateNamespace(ctx context.Context, namespace string, cfg *NamespaceConfig) error

CreateNamespace creates a new namespace with the given configuration. It persists the namespace metadata and initializes an empty bloom filter.

func (*BloomCache) DefaultConfig

func (bc *BloomCache) DefaultConfig() *NamespaceConfig

DefaultConfig returns the default namespace configuration.

func (*BloomCache) DeleteNamespace

func (bc *BloomCache) DeleteNamespace(ctx context.Context, namespace string) error

DeleteNamespace deletes a namespace and its bloom filter.

func (*BloomCache) Get

func (bc *BloomCache) Get(ctx context.Context, namespace string) (*StandardBloom, error)

Get retrieves the bloom filter for a namespace. It first checks the cache, then loads from KVStore if not found. If the namespace doesn't exist, it creates one with default config.

func (*BloomCache) GetNamespaceMeta

func (bc *BloomCache) GetNamespaceMeta(ctx context.Context, namespace string) (*NamespaceMeta, error)

GetNamespaceMeta retrieves namespace metadata from KVStore.

func (*BloomCache) Invalidate

func (bc *BloomCache) Invalidate(namespace string)

Invalidate removes a namespace's bloom filter from the cache.

func (*BloomCache) MightContain

func (bc *BloomCache) MightContain(ctx context.Context, namespace string, path string) (bool, error)

MightContain checks if a path might exist in a namespace using the bloom filter.

func (*BloomCache) MightContainBatch

func (bc *BloomCache) MightContainBatch(ctx context.Context, namespace string, paths []string) (map[string]bool, error)

MightContainBatch checks multiple paths at once using the bloom filter.

func (*BloomCache) Size

func (bc *BloomCache) Size() int

Size returns the current number of entries in the cache.

func (*BloomCache) UpdateNamespaceMeta

func (bc *BloomCache) UpdateNamespaceMeta(ctx context.Context, namespace string, meta *NamespaceMeta) error

UpdateNamespaceMeta updates the namespace metadata.

type BloomFilter

type BloomFilter interface {
	// Add adds an item to the bloom filter.
	Add(item []byte)

	// Test checks if an item might be in the set.
	// Returns false if definitely not in the set.
	// Returns true if might be in the set (could be false positive).
	Test(item []byte) bool

	// Clear resets the bloom filter.
	Clear()

	// Size returns the number of items added.
	Size() uint64

	// M returns the size of the bitset.
	M() uint

	// K returns the number of hash functions.
	K() uint

	// MarshalBinary serializes the bloom filter to bytes.
	encoding.BinaryMarshaler

	// UnmarshalBinary deserializes the bloom filter from bytes.
	encoding.BinaryUnmarshaler
}

BloomFilter is an interface for bloom filter operations.

type NamespaceConfig

type NamespaceConfig struct {
	ExpectedItems     int     `json:"expectedItems"`
	FalsePositiveRate float64 `json:"falsePositiveRate"`
}

NamespaceConfig holds bloom filter configuration for a namespace.

func DefaultNamespaceConfig

func DefaultNamespaceConfig() *NamespaceConfig

DefaultNamespaceConfig returns the default namespace configuration.

type NamespaceMeta

type NamespaceMeta struct {
	Config        NamespaceConfig `json:"config"`
	CreatedAt     time.Time       `json:"createdAt"`
	LastUpdatedAt time.Time       `json:"lastUpdatedAt,omitempty"`
}

NamespaceMeta holds metadata for a namespace.

type StandardBloom

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

StandardBloom is a standard Bloom Filter implementation.

func NewStandardBloom

func NewStandardBloom(expectedItems int, falsePositiveRate float64) *StandardBloom

NewStandardBloom creates a new StandardBloom filter. expectedItems: expected number of items to add falsePositiveRate: desired false positive rate (e.g., 0.01 for 1%)

func NewStandardBloomFromData

func NewStandardBloomFromData(k, m uint, bitsetBytes []byte) (*StandardBloom, error)

NewStandardBloomFromData creates a StandardBloom from serialized data.

func (*StandardBloom) Add

func (b *StandardBloom) Add(item []byte)

Add adds an item to the bloom filter.

func (*StandardBloom) Bitset

func (b *StandardBloom) Bitset() []byte

Bitset returns the serialized bitset.

func (*StandardBloom) Clear

func (b *StandardBloom) Clear()

Clear resets the bloom filter.

func (*StandardBloom) EstimatedFalsePositiveRate

func (b *StandardBloom) EstimatedFalsePositiveRate() float64

EstimatedFalsePositiveRate returns the estimated false positive rate based on current number of items.

func (*StandardBloom) K

func (b *StandardBloom) K() uint

K returns the number of hash functions.

func (*StandardBloom) M

func (b *StandardBloom) M() uint

M returns the size of the bitset.

func (*StandardBloom) MarshalBinary

func (b *StandardBloom) MarshalBinary() ([]byte, error)

MarshalBinary implements encoding.BinaryMarshaler. Format: [k:4][m:4][bitsetLen:4][bitset:...]

func (*StandardBloom) OptimalItemCount

func (b *StandardBloom) OptimalItemCount() uint64

OptimalItemCount returns the expected optimal number of items for this bloom filter.

func (*StandardBloom) Size

func (b *StandardBloom) Size() uint64

Size returns the number of items added.

func (*StandardBloom) Test

func (b *StandardBloom) Test(item []byte) bool

Test checks if an item might be in the set.

func (*StandardBloom) UnmarshalBinary

func (b *StandardBloom) UnmarshalBinary(data []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler.