nagisa-kunhah commented on PR #3481: URL: https://github.com/apache/kvrocks/pull/3481#issuecomment-4390189366
@jihuayu Hi, thank you for the review. I have summarized the design and implementation details below to explain the layering, responsibilities, and key storage decisions. # 1 Design Overview The design follows Kvrocks' existing layered architecture. Conceptually, the change can be divided into four layers: 1. Command layer 2. Type layer 3. Metadata/storage encoding layer 4. RocksDB persistence layer ## 1.1 Command layer The command layer introduces RedisBloom-compatible Cuckoo Filter commands, such as `CF.RESERVE`, `CF.ADD`, `CF.EXISTS`, and `CF.MEXISTS`. Following the existing architecture, each command is implemented as a `Commander` subclass and registered through the existing command registration mechanism. ## 1.2 Type layer The type layer introduces the new `CuckooChain` abstraction to represent each logical Cuckoo Filter. The reason for using a chain abstraction is that Cuckoo Filters are not easy to resize in place: the bucket positions depend on the current bucket count, so resizing a filter would require rebuilding existing data. Instead, the design appends new sub-filters when expansion is needed. This model is inspired by RedisBloom's scalable Cuckoo Filter design. `CuckooChain` implements the high-level operations for a logical Cuckoo Filter, including `RESERVE`, `ADD`, `EXISTS`, `MEXISTS`, and related key-level behavior. To keep the type layer separated from the algorithm details, `CuckooFilter` is introduced as an internal helper. It provides Cuckoo Filter-specific calculations used by `CuckooChain`, while `CuckooChain` remains responsible for the Redis/Kvrocks-facing behavior. ## 1.3 Metadata/storage encoding layer At the metadata/storage encoding layer, the implementation adds `CuckooChainMetadata` to store the state and parameters for each logical Cuckoo Filter. This metadata extends the existing Kvrocks metadata model, so common key-level fields such as type, size, expiration, and version are still handled consistently with other data types. The Cuckoo-specific fields describe the filter chain, including the number of sub-filters, base capacity, bucket size, expansion factor, and insertion iteration limit. This keeps the logical filter state compact while leaving the actual bucket contents in subkeys. ## 1.4 RocksDB persistence layer At the persistence layer, the implementation reuses Kvrocks' existing metadata/subkey model. The logical key metadata is stored as metadata, and individual buckets are stored as internal subkeys. This follows the same general pattern used by other complex Redis data structures in Kvrocks. The metadata entry and bucket entries are written through RocksDB write batches when they need to be updated together. This keeps the logical filter state and the modified bucket data consistent without introducing a separate persistence path for Cuckoo Filter. # 2 Logical Structure A logical Cuckoo Filter is associated with one user key. Internally, it is represented as a chain of sub-filters rather than a single resizable filter. The relationship between the main concepts is: <img width="1536" height="1024" alt="cuckoo_filter_logical_structure" src="https://github.com/user-attachments/assets/a58904fb-4528-47c6-822f-670ba21f84eb"; /> - The logical filter is the user-visible Cuckoo Filter associated with a Redis key. - A sub-filter is one filter segment in the chain. Expansion appends new sub-filters to the chain. - Each sub-filter contains `num_buckets` buckets, and `num_buckets` is rounded to a power of two. - A bucket belongs to one sub-filter and contains a fixed number of slots. - A slot stores one fingerprint. A zero value means the slot is empty. - A fingerprint is a compact representation derived from the item hash. # 3 Implementation Details ## 3.1 Data Layout ### 3.1.1 Metadata Each logical Cuckoo Filter key has one `CuckooChainMetadata` entry. The metadata describes the filter-level state and configuration, while the actual bucket data is stored separately. The metadata is stored in the `metadata` column family. The RocksDB key is the namespace-prefixed logical Redis key, represented as `ns_key` in the implementation. Conceptually: ```text metadata CF: <ns_key> -> CuckooChainMetadata ``` The metadata contains the following fields: | Field Name | Data Type | Size (Bytes) | Description | |---|---|---:|---| | `size` | `uint64_t` | 8 | The total number of items recorded in the entire filter chain. This field is inherited from the base `Metadata`. | | `expire` | `uint64_t` | 8 | The expiration timestamp of the logical key. This field is inherited from the base `Metadata`. | | `version` | `uint64_t` | 8 | The metadata version used to separate current subkeys from stale subkeys. This field is inherited from the base `Metadata`. | | `n_filters` | `uint16_t` | 2 | The number of sub-filters in the chain. | | `expansion` | `uint16_t` | 2 | The growth factor used when a new sub-filter is appended. | | `base_capacity` | `uint64_t` | 8 | The capacity of the first sub-filter. The capacity of later sub-filters is derived from this value and `expansion`. | | `bucket_size` | `uint8_t` | 1 | The number of fingerprint slots each bucket can hold. | | `max_iterations` | `uint16_t` | 2 | The maximum number of relocation attempts during insertion. | | `num_deleted_items` | `uint64_t` | 8 | The number of deleted items recorded by the filter. | This metadata belongs to the logical Cuckoo Filter as a whole. It is not stored per bucket or per sub-filter. ### 3.1.2 Bucket Storage The bucket data is stored as internal subkeys under the logical Cuckoo Filter key. Each bucket is identified by both a `filter_index` and a `bucket_index`. The bucket subkey is constructed from: - `filter_index`: identifies which sub-filter in the chain the bucket belongs to. - `bucket_index`: identifies the bucket inside that sub-filter. The bucket value is a fixed-size byte array whose length is `bucket_size`. Each byte stores one fingerprint. A value of `0` represents an empty slot, while valid fingerprints are stored as non-zero values. Conceptually, the bucket layout is: ```text PrimarySubkey CF: <bucket_key> -> bucket_data bucket_key = InternalKey(<ns_key>, <encoded filter_index and bucket_index>, version) ``` Here, `filter_index` and `bucket_index` are encoded into the bucket subkey as binary fields, not as a numeric sum. This layout keeps the logical filter metadata separate from the bucket contents, while still reusing Kvrocks' existing internal subkey model. ## 3.2 Hashing Model ### 3.2.1 Item Hash Each item is first converted into a 64-bit hash using `HllMurMurHash64A` with seed `0`. This is the actual function name used in the codebase. It follows Redis' MurmurHash64A-style hash implementation and keeps the hashing model close to RedisBloom's Cuckoo Filter design. The item hash is the base value used to derive both the fingerprint and the candidate bucket positions. Since these values determine where the item is stored and looked up, the hash function is part of the persistent data layout and should remain stable once data has been written. ### 3.2.2 Fingerprint The fingerprint is generated from the item hash as `hash % 255 + 1`, producing an 8-bit non-zero value in the range `1..255`; `0` is reserved as the empty-slot marker. ### 3.2.3 Candidate Buckets For each sub-filter, an item has two candidate buckets. The first bucket is derived directly from the item hash: ```text bucket1 = hash % num_buckets ``` The second bucket is derived from both the hash and the fingerprint: ```text delta = fingerprint * 0x5bd1e995 bucket2 = (hash ^ delta) % num_buckets ``` The constant `0x5bd1e995` follows RedisBloom's Cuckoo Filter implementation and is used as the mixing constant for deriving the alternate bucket. During kick-out insertion, the original item hash of an evicted fingerprint is no longer available. Instead, the implementation uses the current bucket index and the fingerprint to compute the alternate bucket: ```text alternate_bucket = (current_bucket ^ delta) % num_buckets ``` This is valid because `num_buckets` is always rounded to a power of two. When `num_buckets = 2^k`, modulo is equivalent to keeping the lower `k` bits, so: ```text (hash ^ delta) % num_buckets == ((hash % num_buckets) ^ delta) % num_buckets ``` This lets the kick-out path move a fingerprint between its two candidate buckets using only the current bucket index and the fingerprint. ## 3.3 Current Write Path ### 3.3.1 CF.RESERVE `CF.RESERVE` creates the logical Cuckoo Filter key and initializes its metadata. It validates the requested capacity and configuration parameters, checks that the key does not already exist, and then creates a `CuckooChainMetadata` entry with the initial filter configuration. The initial metadata records the base capacity, bucket size, maximum insertion iterations, expansion factor, and initializes `n_filters` to `1`. The initial number of buckets is derived from the requested capacity and bucket size. The calculation uses a target load factor of `0.955`, which reserves extra slots instead of assuming that all slots can be filled successfully. The result is then rounded to a power of two. The implementation does not preallocate all buckets during reserve. Buckets are created lazily when they are first written. This keeps `CF.RESERVE` lightweight and avoids writing empty bucket data for sparse filters. ### 3.3.2 CF.ADD `CF.ADD` inserts an item into an existing logical Cuckoo Filter. It first loads and decodes the `CuckooChainMetadata`, then computes the item hash and fingerprint. For each sub-filter in the chain, the implementation derives the two candidate buckets for the item. It reads these buckets, treats missing buckets as empty buckets, and tries to place the fingerprint into any available slot in either bucket. For insertion, sub-filters are checked from the first one to the latest one, in `filter_index` order from `0` to `n_filters - 1`. This prioritizes reusing available slots in earlier sub-filters before placing data into newer sub-filters, which keeps the chain more compact and avoids expanding the effective write target too aggressively. **This is different from RedisBloom, which checks sub-filters from the latest one back to the first one.** If a free slot is found, the updated bucket data and the updated metadata are written in the same write batch. This keeps the bucket content and the logical filter state updated atomically. If no free slot is available in the candidate buckets, the implementation falls back to kick-out insertion on the latest sub-filter. The kick-out path relocates existing fingerprints between their candidate buckets and writes all modified buckets together when the insertion succeeds. ### 3.3.3 Expansion Expansion is triggered when insertion cannot find a free slot and kick-out insertion also fails. Instead of resizing an existing sub-filter in place, the implementation appends a new sub-filter to the chain. The new sub-filter is represented by increasing `n_filters` in `CuckooChainMetadata`. Its capacity is derived from `base_capacity`, `expansion`, and the new `filter_index`. The existing buckets are not rebuilt or moved during expansion. This avoids rewriting existing filter data. After expansion, the insertion is retried against the newly added sub-filter. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
