rueidisbloom extension proposal

[proost]

Summary

Adding rueidisbloom package that supports Bloom Filter with rueidis.

---

Motivation

Recently, I experienced the cache penetration issue. I mitigated the issue caching empty object instead of missing value. But using null object pattern has two problems.

1. First missing request always goes through primary db.
2. If total count of missing data is big, there is big waste of memory.

So if redis stores bloom filter about all data and sync with primary db, user pre-filters requests which will be sent to primary db.

If using RedisBloom, the issue is solved. but someone like me who can’t use Redis Stack, can’t solve issue easily. if rueidisbloom supports bloom filter, users like me solve cache penetration issue with low effort.

---

Goals

1. add elements to bloom filter
2. check elements is in bloom filter or not
3. set TTL to bloom filter.
4. reset bloom filter.

Non-Goals

1. pre-populate bloom filter

---

Plan

// BloomFilter is a Bloom filter.
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.
	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 delete the Bloom filter.
	Delete(ctx context.Context) error
	
	// Count returns count of items in Bloom filter. 
	Count(ctx context.Context) (uint, error)
}

type bloomfilter struct {
	client rueidis.Client

	// name is the name of the Bloom filter.
	// It is used as a key in the Redis.
	name string

	// hashIterations is the number of hash functions to use.
	hashIterations uint
}

// NewBloomFilter creates a new Bloom filter.
func NewBloomFilter(
	client rueidis.Client,
	name string,
	expectedNumberOfItems uint,
	falsePositiveRate float64,
) (*Client, error) {
   ...
}

I will use 128bits hashes and use murmurhash3 algorithm. Mostly I will refer codes here to make hashes.

Bitmaps is used for Internal data structure

[rueian]

Hi @proost,

Your intention is good. But there are a couple of things we need to consider:

1. The name rueidisbloom may mislead other users to think it is backed by RedisBloom.
2. In your use case, you may also need to support Delete/Remove methods to keep the filter in sync with your database.
3. You may also need to resize the filter when it is close to full, otherwise it will always return false positive results eventually.

[proost]

1. how about rueidisbloomfilter?
2. Well, i will implement standard bloom filter. standard bloom filter did not supports Delete/Remove operation. In those case, we need "d-left hashing bloom filter" or "counting bloom filter". but these idea need count each index so that more complicated data structure is required. bitmaps can't handle it.
3. How about add Rename method to BloomFilterClient? So periodically changing old bloom filter to new one can be possible.

[rueian]

1. rueidisbloomfilter is still similar to rueidisbloom but is more specific to the bloom filter. I'd like to keep some space for further development. How about rueidissketch or rueidisprob?
2. Ok. Just leave some flexibility for further development. Eventually, someone will need the Delete/Remove operation.
3. Rename alone looks weird. I think, first of all, users need a way to know whether the filter is full or not, and then they can decide what to do next.

[proost]

@rueian

1. rueidisprob is better name to me.
2. Yes. I agree that someone will need Delete/Remove operation. But supporting Deleted/Remove operation to standard bloom filter is complicated.
3. Ok. how about adding EstimatedInsertedItemCount method? using BITCOUNT command can support how many items are inserted.

[rueian]

Would it be better to have a concrete count like what BF.CARD does? We can store it to another key.

[proost]

Getting bigger than i expected. if package name is rueidisprob, how about adding each data structure one by one?

this time adds standard bloom filter and then counting bloomf filter. if someone needs something else, at that time implments count-min sketch, hyperloglog, etc.

[rueian]

Thanks! I still think a counter would be better in terms of accuracy.

Another question is related to the proposed API:

	// 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.
	// Returns a slice of strings containing the keys that were not added.
	AddMulti(ctx context.Context, keys []string) ([]string, error)

The return signatures of these two methods look inconsistent. Why does AddMulti return keys that were not added but Add doesn't? On the other hand, why keys not being added should be returned? What is the use case?

	// Expire sets an expiration time for the Bloom filter.
	Expire(ctx context.Context, expirationTime time.Time) error

How to use this Expire method? It seems that users need to call this periodically to extend the expiration time. I am afraid this is quite inconvenient.

[proost]

1. Add is single operation. that means if happening error means given key is not added. I think it is clear. AddMulti is batch operation. so that some operation can success but others can fail. In this case, we should return what keys are failed to be inserted. user can clearly knows failed keys.

2. I missed. we should support delete operation when user want to change new bloom filter

[proost]

Oh, I figure out what you intend. We don't need to return failed keys. but there is always trade off. if inserted indexes are huge, then possibly block redis quite longer.

[rueian]

I was asking for clarification because when I first saw the return signature ([]string, error), I thought that was reporting keys that were already in the filter before calling the AddMulti, but then I saw the Add method only returns an error which made me felt these two signatures were inconstant.

However, if you were considering unexpected partial failures such as networking issues, timeouts, etc, I believe the best solution is making it atomic with a LUA script. Or at least returning an error slice, similar to what DoMulti does.

Yes, doing this with a long list of keys can block redis for a long time, but users can split the list by themself.

[proost]

I see. Because i considered long list of keys, I proposed to endure partial failure. If user handle this, then just returning error makes sense.

[proost]

Close due to #493

I will send a Counting Bloom Filter design soon