Counting Bloom Filter for rueidisprob package

[proost]

Summary

Adding Counting Bloom Filter to rueidisprob . Counting Bloom Filter is used to check whether data is in Redis or main storage and can sync with main storage.

Problem Definitions

Background

Bloom Filter is intended for solving cache penetration issue. Counting Bloom Filter can also solve cache penetration issue too. But Bloom Filter cannot remove items. So it is possible to inconsistency between bloom filter and main storage. For example, when items are hard-deleted from main storage or items are removed due to TTL. In these cases, we should handle it instead of resetting whole filter.

Features

1. add elements to coutning bloom filter.
2. check elements is in counting bloom filter or not
3. remove elements from counting bloom filter.
4. delete counting bloom filter.
5. returning how many elements are stored in coutning bloom filter.

Plan

API Design

// CountingBloomFilter based on Hashes.
// CountingBloomFilter uses 128-bit murmur3 hash function.
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.
	// NOTE: If keys are too many, it can block the Redis server for a long time.
	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

	// Count returns count of items in Counting Bloom Filter.
	Count(ctx context.Context) (uint, error)
}

Detailed Design

I use 2 data structures.

• String
  • Same as Standard Bloom Filter, using for number of inserted elements counter.
  • Key: {name}:c
    • name is a namespace for Counting Bloom Filter. And It is given by user when constructing Counting Bloom Filter.
    • using hash tag to enable Multi-keys operation using Lua script.
• Hashes
  • Using as a Bloom Filter. Each member is counter for each index which is hashed value from input key.
  • Key: {name}:bf
    • name is a namespace for Counting Bloom Filter. And It is given by user when constructing Counting Bloom Filter.
    • using hash tag to enable Multi-keys operation using Lua script.

AddMulti

1. Calculate indexes each key in client-side
2. Send indexes and other parameters with a Lua script.
3. Lua script do on the redis server
   1. Get counters of each key.
   2. if one of counters per key is zero, then this is new key. so increase counter of indexes by one each new key.
   3. increase number of new keys

RemoveMulti

1. Calculate indexes each key in client-side
2. Send indexes and other parameters with a Lua script.
3. Lua script do on the redis server
   1. Get counters of each key.
   2. if all of counters per key is bigger than zero, then this is existing key. so decrease counter of indexes by one all existing keys.
   3. decrease number of existing keys.

ExistsMulti

1. Calculate indexes each key in client-side
2. Send indexes and other parameters with a Lua script.
3. Lua script do on the redis server
   1. Get counters of each key.
   2. If all of counters per key is bigger than zero, then this is existing key.

Delete

1. Lua script do on the redis server
   1. remove hashes
   2. remove counter

Count

1. send GET command to counter

[rueian]

Thanks @proost, this looks great!

[proost]

Close due to #519

[zexicc]

Can anyone help me with a penetration test?

[proost]

@zexicc has any problem?