You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@kvrocks.apache.org by "LiuQhahah (via GitHub)" <gi...@apache.org> on 2025/07/28 03:28:14 UTC
[D] Cuckoo Filter Design Proposal [kvrocks]
GitHub user LiuQhahah created a discussion: Cuckoo Filter Design Proposal
# 1. Introduction
In https://github.com/apache/kvrocks/issues/2534, we plan to support the cuckoo filter.
This document outlines the design for implementing a Cuckoo Filter in Kvrocks. The Cuckoo Filter is a high-performance, probabilistic data structure used for approximate set membership testing. It allows for fast checks to see if an item is in a set and, unlike Bloom Filters, supports item deletion.
# 2. Core Concepts
* Fingerprint: Instead of storing the items themselves, the Cuckoo Filter stores a "fingerprint" of the item, which is a small hash derived from the original item.
* Two Candidate Buckets: For any given item, it can be stored in one of two possible buckets. The locations of these buckets are determined by two hash functions.
* Cuckoo Hashing / Kicking: When a new item needs to be inserted and both of its candidate buckets are full, the filter will evict an existing item from one of the buckets to make space.
This evicted item is then re-inserted into its alternate location, which may cause a cascade of evictions. This process continues until all items find a home or a maximum number of evictions is reached.
# 3. Data Structure Design
To efficiently implement the Cuckoo Filter in Kvrocks, we will adopt a sharded (or chained) storage model. This model breaks down a large, logical Cuckoo Filter into smaller, manageable chunks, each stored as a separate key-value pair in RocksDB.
## 3.1. Metadata
The metadata stores the overall information and configuration for the Cuckoo Filter. Each Cuckoo Filter instance corresponds to a single metadata key-value pair in RocksDB.
* Key Format: __namespace__:cuckoo_filter:{user_key}
* Value Format: A serialized CuckooChainMetadata object. The structure of this object is detailed below.
### CuckooChainMetadata Structure
The metadata value is a tightly packed binary structure. The total size is typically 26 bytes, though this may vary slightly with memory alignment.
| Field Name | Data Type | Size (Bytes) | Description |
|---|---|---|---|
| n_filters | uint32_t | 4 | The number of filter shards in the chain. |
| capacity | uint64_t | 8 | The total theoretical capacity of the entire filter chain. |
| size | uint64_t | 8 | The current number of items stored in the filter chain. |
| max_iterations | uint32_t | 4 | The maximum number of kicks allowed during an insertion before giving up. |
| bucket_size | uint8_t | 1 | The number of fingerprints (slots) each bucket can hold (e.g., 2, 4). |
| expansion | uint8_t | 1 | The factor by which the filter's capacity grows during expansion (e.g., 2 for doubling). |
## 3.2. Filter Data
Each filter shard is stored as a separate key-value pair.
* Key Format: __cf__:{namespace_key}:{shard_index}
* __cf__: A fixed prefix to identify a filter data shard.
* {namespace_key}: The same namespace key used for the metadata.
* {shard_index}: The 0-based index of the shard in the chain.
* Value Format: The binary data of the filter shard.
* This data contains the actual fingerprints stored in the buckets.
* This is treated as an opaque blob by RocksDB, managed by the Cuckoo Filter logic.
Example:
For a my_filter that has been expanded once, the storage would look like this:
1. Metadata Key:
* Key: __namespace__:cuckoo_filter:my_filter
* Value: (Serialized metadata, e.g., {num_filters: 2, capacity: 3000, size: 1500, ...})
2. Data Key 0:
* Key: __cf__:__namespace__:cuckoo_filter:my_filter:0
* Value: (Binary data for the first shard, capacity 1000)
3. Data Key 1:
* Key: __cf__:__namespace__:cuckoo_filter:my_filter:1
* Value: (Binary data for the second shard, capacity 2000)
## 3.3. Storage Layout in RocksDB
The following diagram illustrates how a Cuckoo Filter with two shards is stored in RocksDB:
```
+-------------------------------------------------------------------------------------------------+
| RocksDB Storage |
+-------------------------------------------------------------------------------------------------+
| |
| +-----------------------------------------------------------------------------------------+ |
| | Metadata Entry | |
| | | |
| | Key: "__namespace__:cuckoo_filter:my_filter" | |
| | | |
| | Value: (Serialized JSON) | |
| | { | |
| | "n_filters": 2, | |
| | "capacity": 3000, | |
| | "size": 1500, | |
| | "max_iterations": 500, | |
| | "bucket_size": 2, | |
| | "expansion": 2 | |
| | } | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #0 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:0" | |
| | | |
| | Value: (Binary data for the first shard) | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #1 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:1" | |
| | | |
| | Value: (Binary data for the second shard) | |
| +-----------------------------------------------------------------------------------------+ |
| |
+-------------------------------------------------------------------------------------------------+
```
# 4. Operational Flow
## 4.1. Add Operation (CF.ADD)
1. Read Metadata: Read the metadata for the given user_key.
2. Locate Last Shard: Identify the last filter shard using num_filters - 1.
3. Read Shard Data: Read the data of the last shard from RocksDB.
4. Attempt Insert: Perform the insert operation in memory.
* Success: Update the size in the metadata and write the updated metadata and shard data back to RocksDB.
* Failure (Full): Trigger the expansion process.
## 4.2. Expansion
1. Update Metadata:
* Increment num_filters.
* Calculate the new total capacity based on the expansion_factor.
2. Create New Shard:
* Generate a new, empty filter data block.
* Atomically write the new metadata and the new filter shard to RocksDB.
3. Retry Insert: After expansion, re-attempt the insert operation, which will now target the newly created empty shard.
## 4.3. Exists Operation (CF.EXISTS)
1. Read Metadata: Read the metadata for the user_key.
2. Iterate Through Shards:
* Loop from shard_index = 0 to num_filters - 1.
* For each shard, read its data from RocksDB.
* Check if the item exists in the current shard.
* If the item is found in any shard, return True immediately.
3. Return Result: If the loop completes without finding the item, return False.
## 4.4. Delete Operation (CF.DELETE)
The delete operation is similar to the exists operation, requiring a search through the shards.
1. Read Metadata: Read the metadata for the user_key.
2. Iterate Through Shards:
* Loop from shard_index = 0 to num_filters - 1.
* For each shard, read its data and attempt to delete the item.
* If the item is successfully deleted, update the size in the metadata, write the updated metadata and shard data back to RocksDB, and return True.
3. Return Result: If the loop completes without deleting the item, return False.
# 5. Concurrency Safety
* Atomic Writes: All write operations (ADD, DELETE, EXPAND) must be atomic to ensure data consistency. This can be achieved using RocksDB's WriteBatch.
* Locking: To prevent race conditions, a lock should be acquired for the duration of the read-modify-write cycle, especially when updating metadata. This ensures that concurrent operations do not interfere with each other.
# Reference
1. https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
2. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
GitHub link: https://github.com/apache/kvrocks/discussions/3079
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LindaSummer (via GitHub)" <gi...@apache.org>.
GitHub user LindaSummer added a comment to the discussion: Cuckoo Filter Design Proposal
Hi @anupsingh3292 ,
@LiuQhahah planned in several months ago. But I'm not sure about his latest status. 😊
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15432813
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
Okay, thank you for your suggestion.
I will update the design document to ensure consistency in the description.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14135915
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
For example, in the first round, we have one filter with 16 buckets. e.g. `filter0 -> bucket0, ... bucket15`.
And after one rehashing, we can just extend it to a filter with 32 buckets, e.g. `filter0 -> bucket0 ..., bucket31`, since it is still relatively small and we don't need to store it in two keys.
In your design it seems no possible 🤔
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13919400
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice edited a comment on the discussion: Cuckoo Filter Design Proposal
> capacity | uint64_t | 8 | The number of buckets stored in each individual filter shard.
If we have sub-filters of different size, why the `capacity` is number of buckets in each sub-filters? size of which sub-filter?
I still feel that your proposal is ambiguous or vague in many places.
Also, could you use words consistently, e.g. select one of "sub-filter" and "filter shard", and use it through the whole proposal?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14135606
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
> Is it necessary to set the threshold to 3GB soon?
Usually blobDB is disabled. And in such case, I suggest that the max value size of a rocksdb should be less than 100KiB.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13941518
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "anupsingh3292 (via GitHub)" <gi...@apache.org>.
GitHub user anupsingh3292 added a comment to the discussion: Cuckoo Filter Design Proposal
@LiuQhahah Not really. I am a Python developer, and I want to utilize RocksDB in my personal project, and I have a very strong use case for the Cuckoo filter. So having this will be very useful.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15433329
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice edited a comment on the discussion: Cuckoo Filter Design Proposal
Let's create a new example of when the expansion factor is 2.
Here I want to avoid to use the word "filter".
For example, if in initial we have 100 buckets, in one rocksdb key, and when the rehashing is triggered, we should have 300 buckets.
And in this case, we have multiple choices.
1. remain just one rocksdb key, and put all 300 buckets into this key.
2. split them to two rocksdb keys, i.e. two rocksdb keys, and 150 buckets in each key
WDYT?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920657
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "git-hulk (via GitHub)" <gi...@apache.org>.
GitHub user git-hulk added a comment to the discussion: Cuckoo Filter Design Proposal
> After checking the code of Bloomfilter in kvrocks, I want to set the max value size to 128MiB, same as Bloomfilter in kvrocks.
I think we can reduce `128MiB` to `128KiB`(or a smaller value) to avoid the read/write amplification.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15501927
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LindaSummer (via GitHub)" <gi...@apache.org>.
GitHub user LindaSummer added a comment to the discussion: Cuckoo Filter Design Proposal
Hi @LiuQhahah ,
Sorry for the delayed reply on your proposal update. 😊
In the latest design, you point out that the read performance would be downgraded, and I think it should be the highest priority of this feature.
Could we mitigate it with some action, like merging and creating a brand new filter if we have too many filters?
Best Regards,
Edward
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14353344
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
It should be a big trouble if we don't have same-size filters. for example,
- we will have a more complicated indexing like 2:1:2:3:0... I really don't think it will work well.
- with more and more rehashing happen, the size of one rocksdb value will become larger and larger. (as you know, rocksdb key-values should be in a relatively small size. except in blob mode)
- we cannot control it in a more flexible way, e.g. we cannot adjust the size of filter in every rehashing.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13919372
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "anupsingh3292 (via GitHub)" <gi...@apache.org>.
GitHub user anupsingh3292 added a comment to the discussion: Cuckoo Filter Design Proposal
@LiuQhahah @LindaSummer , Do we have any plan for this? Any status?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15432683
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
This is an excellent and insightful suggestion.
In response to your suggestion, I have carefully considered it.
For those large-capacity cuckoo filters, if we take a one-to-one mapping between filters and the count of rehashing, the efficiency during subsequent query insertions and deletions will not be as high as when multiple rocksDB keys represent sub-filters.
This is a schematic diagram.
```
┌─────────────────────┬────────────────────────────────┬─────────────────────────────────────────────────────────────────────────────┐
│ RocksDB Key │ Value Description │ Details / Calculation │
├─────────────────────┼────────────────────────────────┼─────────────────────────────────────────────────────────────────────────────┤
│ "my_large_cuckoo" │ Serialized CuckooChainMetadata │ Contains: num_filters=3, num_buckets=2^19, expansion=2, bucket_size=2, etc. │
│ "my_large_cuckoo:0" │ Data block for Sub-filter 0 │ Size: 2^19 buckets * 2 bytes/bucket = 2^20 bytes (1 MiB) │
│ "my_large_cuckoo:1" │ Data block for Sub-filter 1 │ Size: (2^19 2^1) buckets 2 bytes/bucket = 2^21 bytes (2 MiB) │
│ "my_large_cuckoo:2" │ Data block for Sub-filter 2 │ Size: (2^19 2^2) buckets 2 bytes/bucket = 2^22 bytes (4 MiB) │
└─────────────────────┴────────────────────────────────┴─────────────────────────────────────────────────────────────────────────────┘
```
will convert into ->
```
┌───────────────────────┬────────────────────────────────┬──────────────────────────────────────────────────────────────┐
│ RocksDB Key │ Value Description │ Details / Calculation │
├───────────────────────┼────────────────────────────────┼──────────────────────────────────────────────────────────────┤
│ "my_large_cuckoo" │ Serialized CuckooChainMetadata │ Contains: num_filters=3, filter_chunks=[1, 2, 4], etc. │
│ │ │ │
│ "my_large_cuckoo:0" │ Data block for Sub-filter 0 │ Size: 1 MiB. (Not split as it doesn't exceed the threshold). │
│ │ │ │
│ "my_large_cuckoo:1:0" │ First half of Sub-filter 1 │ Size: 1 MiB. Contains buckets 0 to 2^19 - 1. │
│ "my_large_cuckoo:1:1" │ Second half of Sub-filter 1 │ Size: 1 MiB. Contains buckets 2^19 to 2^20 - 1. │
│ │ │ │
│ "my_large_cuckoo:2:0" │ First quarter of Sub-filter 2 │ Size: 1 MiB. Contains buckets 0 to 2^19 - 1. │
│ "my_large_cuckoo:2:1" │ Second quarter of Sub-filter 2 │ Size: 1 MiB. Contains buckets 2^19 to 2^20 - 1. │
│ "my_large_cuckoo:2:2" │ Third quarter of Sub-filter 2 │ Size: 1 MiB. Contains buckets 2^20 to (2^20 + 2^19) - 1. │
│ "my_large_cuckoo:2:3" │ Fourth quarter of Sub-filter 2 │ Size: 1 MiB. Contains buckets (2^20 + 2^19) to 2^21 - 1. │
└───────────────────────┴────────────────────────────────┴──────────────────────────────────────────────────────────────┘
```
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13918799
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
I updated the design document again.
1. The document supplemented the necessary reasons for using the cuckcoo filter chain (supporting multiple insertions of one key).
2. In order to fully utilize the compression feature of rocksdb, the design of rockskey was at the bucket level instead of the original sub-filter level
3. And the influence of cuckoo filter chain on the query has been listed.
Everyone is welcome to contribute their opinions and ideas. Thank @LindaSummer for his help to me.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14217764
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
> Hi @LiuQhahah , I just have one concern about the design. Would the performance significantly downgraded if we have too many sub filters with frequent adding?
You raise a valid concern about performance degradation with multiple sub-filters. Here's my analysis and proposed solution:
**The Challenge**
Yes, with the current implementation, query performance degrades linearly with the number of sub-filters. For example, with 20 sub-filters, an EXISTS query needs to check 40 buckets (2 per filter),
resulting in 40 separate RocksDB read operations.
**Proposed Solution: Leverage RocksDB's MultiGet**
The key optimization is to utilize RocksDB's native MultiGet API, which can dramatically improve query performance
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15558736
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
Hi @PragmaTwice
Regarding the CuckooFilter Proposal, could you provide some additional advice?
I want to implement CF in KVRocks as soon as possible.
Thanks,
Qiang
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14087939
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
> capacity | uint64_t | 8 | The number of buckets stored in each individual filter shard.
If we have sub-filters of different size, why the `capacity` is number of buckets in each sub-filters?
I still feel that your proposal is ambiguous or vague in many places.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14135606
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah edited a discussion: Cuckoo Filter Design Proposal
# 1. Introduction
In https://github.com/apache/kvrocks/issues/2534, we plan to support the cuckoo filter.
This document outlines the design for implementing a Cuckoo Filter in kvrocks. The Cuckoo Filter is a high-performance, probabilistic data structure used for approximate set membership testing. It allows for fast checks to see if an item is in a set and, unlike Bloom Filters, supports item deletion.
A key requirement for this implementation is to support the counting of duplicate items (via the CF.COUNT command). To robustly handle scenarios where a single item may be inserted many more times than the capacity of its two candidate buckets, we have chosen a sharded (or chained) expansion strategy. This approach ensures functional correctness and system stability under all conditions, accepting a trade-off in query performance degradation in favor of feature completeness and robust handling of high-frequency items.
# 2. Core Concepts
* Fingerprint: Instead of storing the items themselves, the Cuckoo Filter stores a "fingerprint" of the item, which is a small hash derived from the original item.
* Two Candidate Buckets: For any given item, it can be stored in one of two possible buckets within a given sub-filter. The locations of these buckets are determined by two hash functions.
* Kicking: When a new item needs to be inserted and both of its candidate buckets are full, the filter will evict an existing item from one of the buckets to make space.
This evicted item is then re-inserted into its alternate location, which may cause a cascade of evictions. This process continues until all items find a home or a maximum number of evictions is reached.
* Expansion (Chaining): If the kicking process fails to find a home for an item after a set number of attempts, the current sub-filter is considered full. An expansion is then triggered, which appends a new, larger sub-filter to the chain to accommodate more data. This design does not use global rehashing.
# 3. Data Structure Design
To efficiently implement the Cuckoo Filter in kvrocks, we will adopt a "Bucket as Key" storage model, combined with a sharded (or chained) expansion strategy. This model maps each bucket of each sub-filter to an individual key-value pair in RocksDB, ensuring high I/O performance and cache efficiency.
## 3.1. Metadata
The metadata stores the overall configuration for the Cuckoo Filter chain. Each Cuckoo Filter instance corresponds to a single metadata key-value pair in RocksDB.
* Key Format: namespace:cuckoo_filter:{user_key}
* Value Format: A serialized CuckooFilterMetadata object.
### CuckooFilterMetadata Structure
| Field Name | Data Type | Size (Bytes) | Description |
|---|---|---|---|
| n_filters | uint32_t | 4 | The number of sub-filters in the chain. |
| capacities | uint64_t[] | Variable | An array storing the bucket count for each sub-filter. capacities[i] is the number of buckets for the sub-filter at filter_index=i. |
| size | uint64_t | 8 | The total number of items stored in the entire filter chain. |
| max_iterations | uint16_t | 2 | The maximum number of kicks (evictions) allowed during an insertion before triggering an expansion.Default: 20 |
| bucket_size | uint8_t | 1 | The number of fingerprints (slots) each bucket can hold. Default: 2 |
| expansion | uint8_t | 1 | The growth factor for the capacity of a new sub-filter relative to the previous one. Default: 1 |
## 3.2. Bucket Data
Each bucket within each sub-filter is stored as a separate key-value pair. This granular approach is the key to performance.
* Key Format: cf:{namespace_key}:{filter_index}:{bucket_index}
* cf: A fixed prefix to identify Cuckoo Filter data.
* {namespace_key}: The same user key as used for the metadata.
* {filter_index}: The 0-based index of the sub-filter in the chain.
* {bucket_index}: The 0-based index of the bucket within that sub-filter.
* Value Format:
* A binary string containing the concatenated fingerprints for that bucket. This is a very small value (e.g., 4 bytes).
## 3.3. Storage Layout in RocksDB
The following diagram illustrates the storage layout for a Cuckoo Filter that has expanded once (n_filters = 2). It details both the Metadata entry and the structure of the individual "Bucket as Key" entries.
```
+-----------------------------------------------------------------------------------+
| RocksDB Storage (Bucket as Key + Chaining) |
+-----------------------------------------------------------------------------------+
| |
| +---------------------------------------------------------------------------+ |
| | Metadata Entry | |
| | Key: "namespace:cuckoo_filter:my_filter" | |
| | Value: (Serialized Data) | |
| | { | |
| | "n_filters": 2, | |
| | "capacities": [1024, 2048], // -> Filter 0 has 1024 buckets, | |
| | // Filter 1 has 2048 buckets. | |
| | "size": 1500, | |
| | "max_iterations": 20, | |
| | "bucket_size": 4, // -> Each bucket holds 4 fingerprints | |
| | "expansion": 2, | |
| | } | |
| +---------------------------------------------------------------------------+ |
| |
| +---------------------------------------------------------------------------+ |
| | Buckets for Filter #0 | |
| | | |
| | Key: "cf:...:my_filter:0:123" // Example bucket from Filter #0 | |
| | | |
| | Value: (4 bytes of binary data) | |
| | +----------+----------+----------+----------+ | |
| | | fpA | fpB | fpC | (empty) | | |
| | +----------+----------+----------+----------+ | |
| | | Slot 0 | Slot 1 | Slot 2 | Slot 3 | | |
| | (1 byte) (1 byte) (1 byte) (1 byte) | |
| | | |
| +---------------------------------------------------------------------------+ |
| |
| +---------------------------------------------------------------------------+ |
| | Buckets for Filter #1 | |
| | | |
| | Key: "cf:...:my_filter:1:456" // Example bucket from Filter #1 | |
| | | |
| | Value: (4 bytes of binary data) | |
| | +----------+----------+----------+----------+ | |
| | | fpX | fpY | fpX | fpZ | | |
| | +----------+----------+----------+----------+ | |
| | | Slot 0 | Slot 1 | Slot 2 | Slot 3 | | |
| | | |
| +---------------------------------------------------------------------------+ |
| |
+-----------------------------------------------------------------------------------+
```
# 4. Operational Flow
## 4.1. Add Operation (CF.ADD)
1. Read Metadata: Read the metadata for the given user_key to get n_filters and the capacities array.
2. Target Last Filter: Target the last sub-filter, which has an index of n_filters - 1.
3. Calculate Buckets: Based on the parameters of the last sub-filter (i.e., capacities[n_filters - 1]), calculate the two candidate bucket indices, i1 and i2, for the item.
4. Read Buckets: Use MultiGet to read the two corresponding bucket keys: ...:{n_filters-1}:{i1} and ...:{n_filters-1}:{i2}.
5. Attempt Insert: Try to place the item's fingerprint into an empty slot in either bucket. If successful, proceed to step 7.
6. Cuckoo Kicking: If both buckets are full, initiate the kicking process within the current sub-filter.
7. On Success: If the insertion is successful, increment the size in the metadata. Atomically write the updated metadata and all modified bucket data to RocksDB using a single WriteBatch.
8. On Failure: If the kicking process exceeds max_iterations, trigger the Expansion flow.
## 4.1.1. Internal Expansion Flow
1. Update Metadata: Calculate the capacity for the new sub-filter based on the expansion factor and append it to the capacities array.
2. Create New Filter: Write the updated metadata to a WriteBatch and commit it. This logically creates the new, empty sub-filter.
3. Retry Insert: Re-attempt the original ADD operation. It will now naturally target the newly created empty sub-filter and succeed.
## 4.3. Exists Operation (CF.EXISTS)
1. Read Metadata: Read the metadata to get n_filters and capacities.
2. Iterate Through Filters: Loop from filter_index = 0 to n_filters - 1.
3. Inside the loop, for each filter_index:
* Calculate the two candidate bucket indices (i1, i2) for the item based on the current sub-filter's capacity (capacities[filter_index]).
* Use MultiGet to read the two bucket keys: ...:{filter_index}:{i1} and ...:{filter_index}:{i2}.
* If the item's fingerprint is found in either bucket, return `True` immediately and terminate the operation.
4. Return Result: If the loop completes without finding the item, return False.
## 4.4. Count Operation (CF.COUNT)
This operation is the primary reason for choosing the chained expansion strategy, as it correctly handles high-frequency duplicate items.
1. Read Metadata: Read the metadata to get n_filters and capacities.
2. Initialize Counter: Set total_count = 0.
3. Iterate Through Filters:
* Loop from filter_index = 0 to n_filters - 1.
* Inside the loop, for each filter_index:
* Calculate the two candidate bucket indices (i1, i2) for the item based on the current sub-filter's capacity.
* Use MultiGet to read the two corresponding buckets.
* In memory, iterate through the contents of both buckets and add the number of matching fingerprints to total_count.
4. Return Result: After the loop completes, return the final total_count.
## 4.5. Delete Operation (CF.DELETE)
The delete operation is similar to EXISTS but only needs to find and remove the first occurrence of the item.
1. Read Metadata and Iterate Through Filters as in EXISTS.
2. In the loop, upon finding the first matching fingerprint in a bucket:
* Remove the fingerprint from the bucket's value data.
* Decrement the size in the metadata.
* Atomically write the modified bucket data and the updated metadata to a WriteBatch.
* Return `True` immediately, and terminate the operation.
3. Return Result: If the loop completes without finding the item, return False.
# 5. Disadvantages and Trade-offs
This design is a pragmatic compromise, and it's important to understand its inherent limitations.
* Query Performance Degradation: The most significant trade-off is that the performance of read operations (EXISTS, COUNT, DELETE) degrades linearly as the number of sub-filters (n_filters) increases. Each expansion adds another set of lookups to every query.
* Low Utilization of Older Sub-Filters: The "write-to-tail" strategy means that once a sub-filter triggers an expansion, it becomes "frozen." It will never receive new insertions, even if space is freed up by DELETE operations. This can lead to poor overall space utilization, as older sub-filters may become sparse over time while new ones are created.
* Hotspot-Driven Expansion: As identified, frequent insertion of a single, high-cardinality item can rapidly trigger multiple expansions. This creates numerous sub-filters that are largely dedicated to holding this single item, further exacerbating the space utilization problem. To mitigate this, it is highly recommended to use a larger `bucket_size` (e.g., 4 or ) instead of the default of 2 if this usage pattern is anticipated. A larger bucket size increases the capacity for duplicate items within a single sub-filter, delaying the need for expansion.
# 6. Concurrency Safety
* Atomic Writes: All write operations must be atomic to ensure data consistency. This is achieved by using RocksDB's WriteBatch.
* Locking: To prevent race conditions during a read-modify-write cycle, a lock should be acquired at the application level for the user key. This is especially critical during expansion to ensure that concurrent operations do not interfere with each other.
# 7. Reference
1. https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
2. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
GitHub link: https://github.com/apache/kvrocks/discussions/3079
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LindaSummer (via GitHub)" <gi...@apache.org>.
GitHub user LindaSummer added a comment to the discussion: Cuckoo Filter Design Proposal
Hi @LiuQhahah ,
I just have one concern about the design. Would the performance significantly downgraded if we have too many sub filters with frequent adding?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15497049
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice edited a comment on the discussion: Cuckoo Filter Design Proposal
> capacity | uint64_t | 8 | The number of buckets stored in each individual filter shard.
If we have sub-filters of different size, why the `capacity` is number of buckets in each sub-filters? size of which sub-filter?
I still feel that your proposal is ambiguous or vague in many places.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14135606
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
See if other people has advice. cc @git-hulk @mapleFU
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14088070
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah edited a discussion: Cuckoo Filter Design Proposal
# 1. Introduction
In https://github.com/apache/kvrocks/issues/2534, we plan to support the cuckoo filter.
This document outlines the design for implementing a Cuckoo Filter in Kvrocks. The Cuckoo Filter is a high-performance, probabilistic data structure used for approximate set membership testing. It allows for fast checks to see if an item is in a set and, unlike Bloom Filters, supports item deletion.
# 2. Core Concepts
* Fingerprint: Instead of storing the items themselves, the Cuckoo Filter stores a "fingerprint" of the item, which is a small hash derived from the original item.
* Two Candidate Buckets: For any given item, it can be stored in one of two possible buckets. The locations of these buckets are determined by two hash functions.
* Cuckoo Hashing / Kicking: When a new item needs to be inserted and both of its candidate buckets are full, the filter will evict an existing item from one of the buckets to make space.
This evicted item is then re-inserted into its alternate location, which may cause a cascade of evictions. This process continues until all items find a home or a maximum number of evictions is reached.
* Rehashing: If the kicking process fails to find a home for an item after a set number of attempts, the filter is considered full. An rehashing is then triggered,
increasing the total number of buckets and rehashing existing items to accommodate more data.
# 3. Data Structure Design
To efficiently implement the Cuckoo Filter in Kvrocks, we will adopt a sharded (or chained) storage model. This model breaks down a large, logical Cuckoo Filter into smaller, manageable chunks, each stored as a separate key-value pair in RocksDB.
## 3.1. Metadata
The metadata stores the overall information and configuration for the Cuckoo Filter. Each Cuckoo Filter instance corresponds to a single metadata key-value pair in RocksDB.
* Key Format: __namespace__:cuckoo_filter:{user_key}
* Value Format: A serialized CuckooChainMetadata object. The structure of this object is detailed below.
### CuckooChainMetadata Structure
The metadata value is a tightly packed binary structure. The total size is typically 26 bytes, though this may vary slightly with memory alignment.
| Field Name | Data Type | Size (Bytes) | Description |
|---|---|---|---|
| n_filters | uint32_t | 4 | The number of filter shards in the chain. |
| capacity | uint64_t | 8 | The number of buckets stored in each individual filter shard. |
| size | uint64_t | 8 | The current number of items stored in the filter chain. |
| max_iterations | uint32_t | 4 | The maximum number of kicks allowed during an insertion before rehashing. |
| bucket_size | uint8_t | 1 | The number of fingerprints (slots) each bucket can hold (e.g., 2, 4). |
| expansion | uint8_t | 1 | The factor by which the filter's capacity grows during expansion (e.g., 2 for doubling). |
## 3.2. Filter Data
To ensure high performance and scalability, a single logical sub-filter can be partitioned into multiple smaller chunks. This strategy avoids the performance pitfalls of storing values in RocksDB. Each chunk is stored as a separate key-value pair.
The binary data of the filter is stored in one or more data chunks. The key format is designed to uniquely identify each chunk within its logical sub-filter.
* Key Format: cf:{namespace_key}:{filter_index}:{chunk_index}
* cf: A fixed prefix to identify Cuckoo Filter data.
* {namespace_key}: The same key used for the metadata.
* {filter_index}: The 0-based index of the logical sub-filter in the chain.
* {chunk_index}: The 0-based index of the data chunk within that logical sub-filter.
* Value Format: The binary data of that specific chunk, containing the actual fingerprints. This is treated as an opaque blob by RocksDB.
Example
~~For a my_filter that has been expanded once, the storage would look like this:~~
1. ~~Metadata Key:~~
* ~~Key: __namespace__:cuckoo_filter:my_filter~~
* ~~Value: (Serialized metadata, e.g., {num_filters: 2, capacity: 3000, size: 1500, ...})~~
2. ~~Data Key 0:~~
* ~~Key: __cf__:__namespace__:cuckoo_filter:my_filter:0~~
* ~~Value: (Binary data for the first shard, capacity 1000)~~
3. ~~Data Key 1:~~
* ~~Key: __cf__:__namespace__:cuckoo_filter:my_filter:1~~
* ~~Value: (Binary data for the second shard, capacity 2000)~~
Consider a filter my_filter that has been expanded once. The first sub-filter is small and fits in one chunk, while the second, larger sub-filter is split into two chunks.
Metadata Key:
* Key: namespace:cuckoo_filter:my_filter
* Value: (Serialized metadata, e.g., {num_filters: 2, filter_chunks: [1, 2], max_chunk_size: 1048576, ...})
(Note: `filter_chunks: [1, 2]` indicates filter 0 has 1 chunk, and filter 1 has 2 chunks.)
Data Chunks for Filter 0:
* Key: cf:namespace:cuckoo_filter:my_filter:0:0
* Value: (Binary data for the first sub-filter)
Data Chunks for Filter 1:
* Key 1: cf:namespace:cuckoo_filter:my_filter:1:0
* Value: (Binary data for the first half of the second sub-filter)
* Key 2: cf:namespace:cuckoo_filter:my_filter:1:1
* Value: (Binary data for the second half of the second sub-filter)
## 3.3. Storage Layout in RocksDB
The following diagram illustrates how a Cuckoo Filter with two shards is stored in RocksDB:
```
+-------------------------------------------------------------------------------------------------+
| RocksDB Storage (Optimized Schema) |
+-------------------------------------------------------------------------------------------------+
| |
| +-----------------------------------------------------------------------------------------+ |
| | Metadata Entry | |
| | | |
| | Key: "__namespace__:cuckoo_filter:my_filter" | |
| | | |
| | Value: (Serialized JSON) | |
| | { | |
| | "n_filters": 2, | |
| | "filter_chunks": [1, 2], // -> Filter 0 has 1 chunk, Filter 1 has 2 chunks. | |
| | "max_chunk_size": 1048576, // -> Max size per chunk is 1MB. | |
| | "bucket_size": 2, | |
| | "expansion": 2, | |
| | ... | |
| | } | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Chunk for Filter #0 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:0:0" | |
| | // ^ ^ | |
| | // Filter Index | Chunk Index | |
| | | |
| | Value: (Binary data for the first filter, size <= 1MB) | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Chunk #0 for Filter #1 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:1:0" | |
| | | |
| | Value: (Binary data for the first half of the second filter, size <= 1MB) | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Chunk #1 for Filter #1 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:1:1" | |
| | | |
| | Value: (Binary data for the second half of the second filter, size <= 1MB) | |
| +-----------------------------------------------------------------------------------------+ |
| |
+-------------------------------------------------------------------------------------------------+
```
# 4. Operational Flow
## 4.1. Add Operation (CF.ADD)
1. Read Metadata: Read the metadata for the given user_key.
2. Calculate the two candidate bucket locations ((filter_idx1, bucket_in_filter1) and (filter_idx2, bucket_in_filter2)).
3. Read the data for the corresponding 1 or 2 shards from RocksDB
4. Attempt to insert the fingerprint into an empty slot in either bucket.
5. If both are full, begin the cuckoo kicking process, which may involve reading/writing to different shards as items are moved.
6. If insertion succeeds, increment size in metadata and atomically write the updated metadata and modified shard(s) back to RocksDB.
7. If kicking exceeds max_iterations, the insertion fails. Trigger the Reshading process.
## 4.2. Expansion
1. Update Metadata:
* Increment num_filters.
* Calculate the new total capacity based on the expansion_factor.
2. Create New Shard:
* Generate a new, empty filter data block.
* Atomically write the new metadata and the new filter shard to RocksDB.
3. Retry Insert: After resharding, re-attempt the insert operation, which will now target the newly created empty shard.
## 4.3. Exists Operation (CF.EXISTS)
1. Read Metadata: Read the metadata for the user_key.
2. Iterate Through Shards:
* Loop from shard_index = 0 to num_filters - 1.
* For each shard, read its data from RocksDB.
* Check if the item exists in the current shard.
* If the item is found in any shard, return True immediately.
3. Return Result: If the loop completes without finding the item, return False.
## 4.4. Delete Operation (CF.DELETE)
The delete operation is similar to the exists operation, requiring a search through the shards.
1. Read Metadata: Read the metadata for the user_key.
2. Iterate Through Shards:
* Loop from shard_index = 0 to num_filters - 1.
* For each shard, read its data and attempt to delete the item.
* If the item is successfully deleted, update the size in the metadata, write the updated metadata and shard data back to RocksDB, and return True.
3. Return Result: If the loop completes without deleting the item, return False.
# 5. Concurrency Safety
* Atomic Writes: All write operations (ADD, DELETE, EXPAND) must be atomic to ensure data consistency. This can be achieved using RocksDB's WriteBatch.
* Locking: To prevent race conditions, a lock should be acquired for the duration of the read-modify-write cycle, especially when updating metadata. This ensures that concurrent operations do not interfere with each other.
# Reference
1. https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
2. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
GitHub link: https://github.com/apache/kvrocks/discussions/3079
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice edited a comment on the discussion: Cuckoo Filter Design Proposal
> When continuously inserting items, if a new item is inserted and the cuckoofilter fails to find an empty bucket after 20 attempts of insertion, the expansion mechanism will be triggered, and filter 1 will be created. Since expansion is equal to 2, the capacity of filter 1 will become 2048.
> At this point, filter 0 > bucket0, bucket1, ..., bucket511 , filter 1 > bucket0, bucket1, ..., bucket1023.
OK. I think I've found the key conflict between our ideas.
First, if you want to migrate all buckets from filter0 to filter1, why do we need to keep filter0 in the storage?
Second, if the expansion factor is 2. From me, the total number of buckets should be 1024, NOT 1024 + 512. So my idea is to split these 1024 buckets to two filters. (or we can just put all 1024 buckets into filter0 and do not create filter1.)
So I don't see the benefits of have one filter of 512 buckets and another of 1024 buckets.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920530
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
Thank you for your proposal! Here are some comments after a brief review.
> n_filters | uint32_t | 4 | The number of filter shards in the chain.
> capacity | uint64_t | 8 | The total theoretical capacity of the entire filter chain.
I think we should also store the max number of buckets of each filter. i.e. how many buckets is stored in one filter?
Also IMHO `capacity` (if I understand correctly it is estimated number of max items to insert) is not so useful and worth to store, i.e. we can compute it immediately from other info.
> The maximum number of kicks allowed during an insertion before giving up.
Before "expansion" (BTW I prefer to use "rehashing" rather than "expansion")? Or before "giving up"?
> Data Key 1:
>
> Key: cf:namespace:cuckoo_filter:my_filter:1
> Value: (Binary data for the second shard, capacity 2000)
1. we don't need to create a rocksdb key-value if all buckets in it are empty.
2. we should have the same number of buckets for each "filter" here. e.g. if the first "filter" has 1000 buckets, the second should have same. If you want more 2000 buckets you should create 2 more "filter"s.
3. The bucket index can be computed via `filter_index * n_buckets_in_filter`.
> Locate Last Shard: Identify the last filter shard using num_filters - 1.
All filters should be useful. If we only care about the last filter, I think we should delete all other filters.
Here we should locate TWO filters (maybe one, if the two buckets are in the same filter) via its two buckets (located by its two hash values).
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13906830
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
Understood. I'll implement this function as soon as possible
Hi @PragmaTwice @LindaSummer
Do you have any other ideas about this design? I want to try to implement a version based on this design first.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15480362
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah edited a discussion: Cuckoo Filter Design Proposal
# 1. Introduction
In https://github.com/apache/kvrocks/issues/2534, we plan to support the cuckoo filter.
This document outlines the design for implementing a Cuckoo Filter in Kvrocks. The Cuckoo Filter is a high-performance, probabilistic data structure used for approximate set membership testing. It allows for fast checks to see if an item is in a set and, unlike Bloom Filters, supports item deletion.
# 2. Core Concepts
* Fingerprint: Instead of storing the items themselves, the Cuckoo Filter stores a "fingerprint" of the item, which is a small hash derived from the original item.
* Two Candidate Buckets: For any given item, it can be stored in one of two possible buckets. The locations of these buckets are determined by two hash functions.
* Cuckoo Hashing / Kicking: When a new item needs to be inserted and both of its candidate buckets are full, the filter will evict an existing item from one of the buckets to make space.
This evicted item is then re-inserted into its alternate location, which may cause a cascade of evictions. This process continues until all items find a home or a maximum number of evictions is reached.
* Rehashing: If the kicking process fails to find a home for an item after a set number of attempts, the filter is considered full. An rehashing is then triggered,
increasing the total number of buckets and rehashing existing items to accommodate more data.
# 3. Data Structure Design
To efficiently implement the Cuckoo Filter in Kvrocks, we will adopt a sharded (or chained) storage model. This model breaks down a large, logical Cuckoo Filter into smaller, manageable chunks, each stored as a separate key-value pair in RocksDB.
## 3.1. Metadata
The metadata stores the overall information and configuration for the Cuckoo Filter. Each Cuckoo Filter instance corresponds to a single metadata key-value pair in RocksDB.
* Key Format: __namespace__:cuckoo_filter:{user_key}
* Value Format: A serialized CuckooChainMetadata object. The structure of this object is detailed below.
### CuckooChainMetadata Structure
The metadata value is a tightly packed binary structure. The total size is typically 26 bytes, though this may vary slightly with memory alignment.
| Field Name | Data Type | Size (Bytes) | Description |
|---|---|---|---|
| n_filters | uint32_t | 4 | The number of filter shards in the chain. |
| capacity | uint64_t | 8 | The number of buckets stored in each individual filter shard. |
| size | uint64_t | 8 | The current number of items stored in the filter chain. |
| max_iterations | uint32_t | 4 | The maximum number of kicks allowed during an insertion before rehashing. |
| bucket_size | uint8_t | 1 | The number of fingerprints (slots) each bucket can hold (e.g., 2, 4). |
| expansion | uint8_t | 1 | The factor by which the filter's capacity grows during expansion (e.g., 2 for doubling). |
## 3.2. Filter Data
Each filter shard is stored as a separate key-value pair.
* Key Format: __cf__:{namespace_key}:{shard_index}
* __cf__: A fixed prefix to identify a filter data shard.
* {namespace_key}: The same namespace key used for the metadata.
* {shard_index}: The 0-based index of the shard in the chain.
* Value Format: The binary data of the filter shard.
* This data contains the actual fingerprints stored in the buckets.
* This is treated as an opaque blob by RocksDB, managed by the Cuckoo Filter logic.
Example:
For a my_filter that has been expanded once, the storage would look like this:
1. Metadata Key:
* Key: __namespace__:cuckoo_filter:my_filter
* Value: (Serialized metadata, e.g., {num_filters: 2, capacity: 3000, size: 1500, ...})
2. Data Key 0:
* Key: __cf__:__namespace__:cuckoo_filter:my_filter:0
* Value: (Binary data for the first shard, capacity 1000)
3. Data Key 1:
* Key: __cf__:__namespace__:cuckoo_filter:my_filter:1
* Value: (Binary data for the second shard, capacity 2000)
## 3.3. Storage Layout in RocksDB
The following diagram illustrates how a Cuckoo Filter with two shards is stored in RocksDB:
```
+-------------------------------------------------------------------------------------------------+
| RocksDB Storage |
+-------------------------------------------------------------------------------------------------+
| |
| +-----------------------------------------------------------------------------------------+ |
| | Metadata Entry | |
| | | |
| | Key: "__namespace__:cuckoo_filter:my_filter" | |
| | | |
| | Value: (Serialized JSON) | |
| | { | |
| | "n_filters": 2, | |
| | "capacity": 3000, | |
| | "size": 1500, | |
| | "max_iterations": 500, | |
| | "bucket_size": 2, | |
| | "expansion": 2 | |
| | } | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #0 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:0" | |
| | | |
| | Value: (Binary data for the first shard) | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #1 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_filter:1" | |
| | | |
| | Value: (Binary data for the second shard) | |
| +-----------------------------------------------------------------------------------------+ |
| |
+-------------------------------------------------------------------------------------------------+
```
# 4. Operational Flow
## 4.1. Add Operation (CF.ADD)
1. Read Metadata: Read the metadata for the given user_key.
2. Calculate the two candidate bucket locations ((filter_idx1, bucket_in_filter1) and (filter_idx2, bucket_in_filter2)).
3. Read the data for the corresponding 1 or 2 shards from RocksDB
4. Attempt to insert the fingerprint into an empty slot in either bucket.
5. If both are full, begin the cuckoo kicking process, which may involve reading/writing to different shards as items are moved.
6. If insertion succeeds, increment size in metadata and atomically write the updated metadata and modified shard(s) back to RocksDB.
7. If kicking exceeds max_iterations, the insertion fails. Trigger the Reshading process.
## 4.2. Expansion
1. Update Metadata:
* Increment num_filters.
* Calculate the new total capacity based on the expansion_factor.
2. Create New Shard:
* Generate a new, empty filter data block.
* Atomically write the new metadata and the new filter shard to RocksDB.
3. Retry Insert: After resharding, re-attempt the insert operation, which will now target the newly created empty shard.
## 4.3. Exists Operation (CF.EXISTS)
1. Read Metadata: Read the metadata for the user_key.
2. Iterate Through Shards:
* Loop from shard_index = 0 to num_filters - 1.
* For each shard, read its data from RocksDB.
* Check if the item exists in the current shard.
* If the item is found in any shard, return True immediately.
3. Return Result: If the loop completes without finding the item, return False.
## 4.4. Delete Operation (CF.DELETE)
The delete operation is similar to the exists operation, requiring a search through the shards.
1. Read Metadata: Read the metadata for the user_key.
2. Iterate Through Shards:
* Loop from shard_index = 0 to num_filters - 1.
* For each shard, read its data and attempt to delete the item.
* If the item is successfully deleted, update the size in the metadata, write the updated metadata and shard data back to RocksDB, and return True.
3. Return Result: If the loop completes without deleting the item, return False.
# 5. Concurrency Safety
* Atomic Writes: All write operations (ADD, DELETE, EXPAND) must be atomic to ensure data consistency. This can be achieved using RocksDB's WriteBatch.
* Locking: To prevent race conditions, a lock should be acquired for the duration of the read-modify-write cycle, especially when updating metadata. This ensures that concurrent operations do not interfere with each other.
# Reference
1. https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
2. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
GitHub link: https://github.com/apache/kvrocks/discussions/3079
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
>I think we should also store the max number of buckets of each filter. i.e. how many buckets is stored in one filter?
> Also IMHO capacity (if I understand correctly it is estimated number of max items to insert) is not so useful and worth to store, i.e. we can compute it immediately from other info.
I'm very sorry for misleading. Let me clarify again that "capacity" refers to the capacity of a single filter rather than the entire filter chain. I think using "capacity" to represent a single filter can solve the problem that you need to specify the capacity for each filter and do not need to set the capacity for the entire filter chain
> Before "expansion" (BTW I prefer to use "rehashing" rather than "expansion")? Or before "giving up"?
Thank you for your suggestion. I have updated "before giving up" to "before rehashing".
> we don't need to create a rocksdb key-value if all buckets in it are empty.
Yes, for empty filters, key-value pairs should not be inserted into rocks.
> Data Key 1:
> Key: cf:namespace:cuckoo_filter:my_filter:1
> Value: (Binary data for the second shard, capacity 2000)
"Data Key 1" refers to the filter after cf has undergone one reshading(expansion). At this point, the key of shard1 becomes cf:namespace:cuckoo_filter:my_filter:1, and the capacity in the Value is 2000. Data Key 1 and Data Key 0 refer to two different filters rather than the same filter.
> Locate Last Shard: Identify the last filter shard using num_filters - 1.
Thank you for pointing out the problem. The description of the add operation is inaccurate. The correct ADD operation is as follows. I have updated the document
1. Read Metadata: Read the metadata for the given user_key.
2. Calculate the two candidate bucket locations ((filter_idx1, bucket_in_filter1) and (filter_idx2, bucket_in_filter2)).
3. Read the data for the corresponding 1 or 2 shards from RocksDB
4. Attempt to insert the fingerprint into an empty slot in either bucket.
5. If both are full, begin the cuckoo kicking process, which may involve reading/writing to different shards as items are moved.
6. If insertion succeeds, increment size in metadata and atomically write the updated metadata and modified shard(s) back to RocksDB.
7. If kicking exceeds max_iterations, the insertion fails. Trigger the Reshading process.
If you still have any questions, please feel free to tell me. Thank you
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13909639
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
I still cannot get your idea.
If we want 1+2+4=7MB of storage to store buckets, why not to create 7 filters (1MB each)?
What is the meaning of "sub-filter"s and a more complicated indexing? Why not just filter0, filter1, filter2, ... filter6?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13919319
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
> For example, if in initial we have 100 buckets, in one rocksdb key, and when the rehashing is triggered, we should have 300 buckets.
> And in this case, we have multiple choices.
> remain just one rocksdb key, and put all 300 buckets into this key.
split them to two rocksdb keys, i.e. two rocksdb keys, and 150 buckets in each key
I was influenced by RedisBloom, which uses multiple sub-filters to form a cuckoofilter.
Personally, I find this approach quite clear.
For ADD operations, if multiple attempts fail to add an item, it triggers a resize, allowing the item to be inserted into a new sub-filter. During queries, you can simply iterate through the latest sub-filter one by one. Since cuckoofilter guarantees O(1) time complexity for finding the bucket index, it requires O(n) complexity to check if there are any free slots within the bucket. Since the bucket size ranges from 1 to 255, I believe the O(n) complexity is acceptable, ensuring that the ADD operation remains relatively fast. The same logic applies to DELETE and QUERY operations.
Below is a diagram of CF in RocksDB after three expansions with a capacity of 16, expansion=2, and bucket_size=2.
```
+-------------------------------------------------------------------------------------------------+
| RocksDB Storage |
+-------------------------------------------------------------------------------------------------+
| |
| +-----------------------------------------------------------------------------------------+ |
| | Metadata Entry | |
| | Key: "__namespace__:cuckoo_filter:my_cf" | |
| | Value: { "n_filters": 4, "base_capacity": 16, "expansion": 2, ... } | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #0 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_cf:0" | |
| | | |
| | Value: (Binary data, 32 bytes for 16 buckets) | |
| | +-----------------------------------------------------------------------------------+ |
| | | Bucket 0 | Bucket 1 | Bucket 2 | ... | Bucket 15 | | |
| | |-----------+-----------+-----------+ ... +-----------| | |
| | | S0 | S1 | S0 | S1 | S0 | S1 | ... | S0 | S1 | (S = Slot) | |
| | |-----------+-----------+-----------+ ... +-----------| | |
| | | fA | fB | fC | fD | fE | fF | ... | fX | fY | (f = Fingerprint, 1 byte) | |
| | +-------------------------------------------------------------------------------+ | |
| | | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #1 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_cf:1" | |
| | | |
| | Value: (Binary data, 64 bytes for 32 buckets) | |
| | +-----------------------------------------------------------------------------------+ |
| | | Bucket 0 | Bucket 1 | ... | Bucket 31 | | |
| | |-----------+-----------+ ... +-----------| | |
| | | S0 | S1 | S0 | S1 | ... | S0 | S1 | | |
| | +-----------------------------------------------------------------------------------+ |
| | | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #2 | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_cf:2" | |
| | | |
| | Value: (Binary data, 128 bytes for 64 buckets) | |
| | +-----------------------------------------------------------------------------------+ |
| | | ... (similar structure, but with 64 buckets) ... | |
| | +-----------------------------------------------------------------------------------+ |
| | | |
| +-----------------------------------------------------------------------------------------+ |
| |
| +-----------------------------------------------------------------------------------------+ |
| | Data Shard #3 (Empty) | |
| | | |
| | Key: "__cf__:__namespace__:cuckoo_filter:my_cf:3" | |
| | | |
| | Value: (Binary data, 256 bytes for 128 buckets, all bytes are 0x00) | |
| | +-----------------------------------------------------------------------------------+ |
| | | Bucket 0 | Bucket 1 | ... | Bucket 127| | |
| | |-----------+-----------+ ... +-----------| | |
| | | 00 | 00 | 00 | 00 | ... | 00 | 00 | (All slots are empty/zero) | |
| | +-----------------------------------------------------------------------------------+ |
| | | |
| +-----------------------------------------------------------------------------------------+ |
| |
+-------------------------------------------------------------------------------------------------+
```
In addition,
I have a question want to consult, https://github.com/facebook/rocksdb/wiki/RocksDB-FAQ recommends a maximum size of value is 3GB.
According to the current idea, after N expansions of cuckoofilter, the chunk method needs to be adopted to split a single subfilter into multiple key-value pairs of 3GB in size.
Is it necessary to set the threshold to 3GB soon?
When the capacity of the CF sub-filter is less than 3GB, a key-value representation of the sub-filter is used.
When the capacity of the sub-filter exceeds 3GB after expansion, multiple 3GB key-value pairs are used to represent the sub-filter.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13933205
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice edited a comment on the discussion: Cuckoo Filter Design Proposal
> When continuously inserting items, if a new item is inserted and the cuckoofilter fails to find an empty bucket after 20 attempts of insertion, the expansion mechanism will be triggered, and filter 1 will be created. Since expansion is equal to 2, the capacity of filter 1 will become 2048.
> At this point, filter 0 > bucket0, bucket1, ..., bucket511 , filter 1 > bucket0, bucket1, ..., bucket1023.
OK. I think I've found the key conflict between our ideas.
First, if you want to migrate all buckets from filter0 to filter1, why do we need to keep filter0 in the storage?
Second, if the expansion factor is 2. From me, the total number of buckets should be 1024, NOT 1024 + 512. So my idea is to split these 1024 buckets to two filters. (or we can just put all 1024 buckets into filter0 and do NOT create filter1.)
So I don't see the benefits of have one filter of 512 buckets and another of 1024 buckets.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920530
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
Got it.
After checking the code of Bloomfilter in kvrocks, I want to set the max value size to 128MiB, same as Bloomfilter in kvrocks.
https://github.com/apache/kvrocks/blob/4450da290fe0fdaf735e222a11e6ae199cb577e6/src/types/bloom_filter.h#L50
How do you think?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13981933
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
Hmm previously I thought that one cuckoo filter can work well by increasing numbers of buckets in this filter.
But after reading "Consistent Cuckoo Filter" (https://dekeguo.github.io/infocom_filter.pdf), I start to understand the performance benefits of having multiple CFs.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920797
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
> When continuously inserting items, if a new item is inserted and the cuckoofilter fails to find an empty bucket after 20 attempts of insertion, the expansion mechanism will be triggered, and filter 1 will be created. Since expansion is equal to 2, the capacity of filter 1 will become 2048.
> At this point, filter 0 > bucket0, bucket1, ..., bucket511 , filter 1 > bucket0, bucket1, ..., bucket1023.
OK. I think I've found the key conflict between our ideas.
First, if you want to migrate all buckets from filter0 to filter1, why do we need to keep filter0 in the storage?
Second, if the expansion factor is 2. From me, the total number of buckets should be 1024, NOT 1024 + 512. So my idea is to split these 1024 buckets to two filters. (or we can just put all 1024 buckets into filter0.)
So I don't see the benefits of have one filter of 512 buckets and another of 1024 buckets.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920530
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
> I still cannot get your idea.
> If we want 1+2+4=7MB of storage to store buckets, why not to create 7 filters (1MB each)?
Yes, if we want a 7MB filter, the cuckoofilter will create a `filter 0` with a capacity of 7MB. I understand that the issue discussed in is https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13918799 about the **expansion scenario**.
For example, when executing CF.RESERVE key capacity [BUCKETSIZE bucketsize] [MAXITERATIONS maxiterations] [EXPANSION expansion], setting capacity to 1000, bucketsize to 2, maxiterations to 20, and expansion to 2, `filter 0` will be created, and 512 buckets will be created.
When continuously inserting items, if a new item is inserted and the cuckoofilter fails to find an empty bucket after 20 attempts of insertion, the expansion mechanism will be triggered, and `filter 1` will be created. Since expansion is equal to 2, the capacity of `filter 1` will become 2048.
At this point, `filter 0 > bucket0, bucket1, ..., bucket511` , `filter 1 > bucket0, bucket1, ..., bucket1023`.
> What is the meaning of "sub-filter"s and a more complicated indexing? Why not just filter0, filter1, filter2, ... filter6?
Sub-filter this concept comes from the https://github.com/RedisBloom/RedisBloom/blob/master/src/cuckoo.h#L32C1-L37C1 . For the `"1 + 2 + 4 = 7 MB"` For the scenario (`expansion=2`), I expect to represent it using `filter0, filter1, filter2`, rather than `filter0, filter1, filter2,... filter6`, this is because `expansion=2` instead of `1`
> It should be a big trouble if we don't have same-size filters.
>we will have a more complicated indexing like 2:1:2:3:0... I really don't think it will work well.
> with more and more rehashing happen, the size of one rocksdb value will become larger and larger. (as you know, rocksdb key-values should be in a relatively small size. except in blob mode)
>we cannot control it in a more flexible way, e.g. we cannot adjust the size of filter in every rehashing.
I fully understand your concern.
Use `the same-size filter`. This is the case when the expansion is 1. For expansions of 2 or greater, in order to avoid the filter growing infinitely, we can use a threshold setting.
For a cuckoo filter with an expansion of 1, the space growth during expansion is not overly dramatic (merely a copy of the size of filter0). However, for expansions with a value of 2 or greater, the cuckoo filter expands exponentially.
We can set a threshold so that when cuckoofilter has been expanded N times and its capacity exceeds this threshold, we can use multiple keys to store `'filter N'` in RocksDB.
For instance, if the threshold is set to 1MB and the capacity of cuckoofilter reaches 2MB after the Nth expansion, we can use two RocksDB keys to store the expanded `"filter N"`? This is the current index, `cf:{namespace_key}:{filter_index}:{chunk_index}`, which has one more level than the original index, `{chunk_index}`.
This can ensure the maximum number of items stored in RocksDB.
> For example, in the first round, we have one filter with 16 buckets. e.g. filter0 -> bucket0, ... bucket15.
> And after one rehashing, we can just extend it to a filter with 32 buckets, e.g. filter0 -> bucket0 ..., bucket31, since it is still relatively small and we don't need to store it in two keys.
> In your design it seems no possible 🤔
Yes, it's obvious that for those small-capacity cuckoofilters, such as those with a capacity of only 1024 and an expansion of 2, resulting in 2048 after expansion, using two RocksDB keys to store the second filter seems very wasteful of resources.
**In summary**
For the case of expansion=1, after the expansion, the subsequent filter1->filterN remain of the same size as filter0
However, in cases where expansion is greater than 1, the cf expansion will show an exponential growth.
At this point, we can control the infinite growth of the filter by setting a threshold. Once the threshold is exceeded, the filterN will be split into multiple blocks and stored in rocksDB. At this point, the index will become 'cf:{namespace_key}:{filter_index}:{chunk_index}', and the insertion, deletion, and search will be conducted in RocksDB based on this index
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920092
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
Let's create a new example of when the expansion factor is 2.
Here I want to avoid to use the word "filter".
For example, if in initial we have 100 buckets, in one rocksdb key, and when the rehashing is triggered, we should have 300 buckets.
And in this case, we have multiple choices.
1. remain just one rocksdb key, and put all 300 buckets into this key.
2. split them to two rocksdb keys, i.e. two rocksdb keys, and 150 buckets in each key
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920657
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
> "Data Key 1" refers to the filter after cf has undergone one reshading(expansion).
I don't think it is a good idea of one-to-one mapping between filters and count of rehashing.
Before any rehashing, we can also have multiple filters.
And after one rehashing, we can increase numbers of filters from e.g. 2 to something like 4.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13916624
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice added a comment to the discussion: Cuckoo Filter Design Proposal
Ahh I check the doc of redis and I think 1024 + 512 is correct. Sorry for that.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-13920605
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "LiuQhahah (via GitHub)" <gi...@apache.org>.
GitHub user LiuQhahah added a comment to the discussion: Cuckoo Filter Design Proposal
> > After checking the code of Bloomfilter in kvrocks, I want to set the max value size to 128MiB, same as Bloomfilter in kvrocks.
>
> I think we can reduce `128MiB` to `128KiB`(or a smaller value) to avoid the read/write amplification.
The current implementation stores each bucket as an independent key-value pair, which eliminates the possibility of having a 128MB single key. The previous approach stored an entire filter (containing multiple buckets) in a single RocksDB key, which could result in 128MB in extreme cases. Therefore, the 128MB issue is no longer a concern.
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-15558763
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org
Re: [D] Cuckoo Filter Design Proposal [kvrocks]
Posted by "PragmaTwice (via GitHub)" <gi...@apache.org>.
GitHub user PragmaTwice edited a comment on the discussion: Cuckoo Filter Design Proposal
> capacity | uint64_t | 8 | The number of buckets stored in each individual filter shard.
If we have sub-filters of different size, why the `capacity` is number of buckets in each sub-filters? size of which sub-filter?
I still feel that your proposal is ambiguous or vague in many places.
Also, could you use consistent word, e.g. select one of "sub-filter" and "filter shard", and use it through the whole proposal?
GitHub link: https://github.com/apache/kvrocks/discussions/3079#discussioncomment-14135606
----
This is an automatically sent email for issues@kvrocks.apache.org.
To unsubscribe, please send an email to: issues-unsubscribe@kvrocks.apache.org