GitHub user nagisa-kunhah created a discussion: Proposal for Cuckoo Filter
# Cuckoo Filter Design Proposal for Apache Kvrocks ## 1. Introduction This proposal describes the design for adding RedisBloom-compatible Cuckoo Filter support to Apache Kvrocks. The related tracking issue is apache/kvrocks#3123. The first implementation work is being developed in apache/kvrocks#3481, starting with `CF.RESERVE` and `CF.ADD`. This proposal updates the earlier Cuckoo Filter discussion in apache/kvrocks#3079 and reflects the design changes made during review, especially the move from one RocksDB key per bucket to paged bucket storage. Cuckoo Filter is a probabilistic data structure for approximate set membership. It is similar to Bloom Filter in that it can return false positives, but it also supports deletion because each inserted item is represented by a small fingerprint stored in one of two candidate buckets. RedisBloom exposes Cuckoo Filter through commands such as `CF.RESERVE`, `CF.ADD`, `CF.ADDNX`, `CF.EXISTS`, `CF.MEXISTS`, `CF.COUNT`, `CF.DEL`, `CF.INFO`, `CF.INSERT`, `CF.INSERTNX`, `CF.SCANDUMP`, and `CF.LOADCHUNK`. Kvrocks already supports RedisBloom-style Bloom Filter commands. Adding Cuckoo Filter support improves RedisBloom compatibility and provides users with a probabilistic structure that can later support duplicate counting and deletion semantics. ## 2. Design Summary This proposal uses a chained Cuckoo Filter design. A logical Cuckoo Filter key stores compact metadata in the Metadata column family and stores bucket contents as paged subkeys in the PrimarySubkey column family. Each page contains multiple logical buckets to avoid the overhead of one RocksDB key per bucket. Expansion appends new sub-filters instead of rebuilding existing data. ## 3. Command Categories The RedisBloom-compatible Cuckoo Filter command set can be implemented in several groups. This grouping also gives us a natural way to split the work into reviewable PRs. 1. Creation and insertion commands These commands create a filter or add items to it. They are the foundation of the data layout because they define how metadata, pages, buckets, fingerprints, duplicate items, and expansion are written. - `CF.RESERVE key capacity [BUCKETSIZE bucket_size] [MAXITERATIONS max_iterations] [EXPANSION expansion]` - `CF.ADD key item` - `CF.ADDNX key item` - `CF.INSERT key [CAPACITY capacity] [NOCREATE] ITEMS item [item ...]` - `CF.INSERTNX key [CAPACITY capacity] [NOCREATE] ITEMS item [item ...]` 2. Membership and count commands These commands read the candidate buckets of one or more items. They need to search all sub-filters in the chain because an item may have been inserted before or after expansion. - `CF.EXISTS key item` - `CF.MEXISTS key item [item ...]` - `CF.COUNT key item` 3. Delete command This command removes one matching fingerprint occurrence from the filter. It depends on the same lookup path as `CF.EXISTS`, but also needs to update the page and metadata atomically. - `CF.DEL key item` 4. Information command This command exposes the logical filter state and is useful for users and tests to inspect capacity, size, number of filters, expansion, bucket size, and related metadata. - `CF.INFO key` 5. Dump and load commands These commands export and restore the internal Cuckoo Filter representation. They are important for RedisBloom compatibility and for workflows that need chunked serialization. - `CF.SCANDUMP key iterator` - `CF.LOADCHUNK key iterator data` ## 4. High-Level Design A logical Cuckoo Filter is represented by one Redis key. Internally, it is modeled as a chain of sub-filters: - `CuckooChain` represents the logical Redis key and owns high-level operations such as reserve, add, expansion, metadata validation, and write-batch commit. - `CuckooSubFilter` represents one sub-filter inside the chain. It implements normal insertion and kick-out insertion for one sub-filter. - `CuckooPageCache` maps logical buckets to persisted page values, reads the required pages, stages dirty page updates, and writes modified pages into the final RocksDB write batch. - `CuckooFilterHelper` provides stable algorithm-level helpers such as hashing, fingerprint generation, alternate-bucket calculation, capacity normalization, and bucket-count calculation. <img width="1122" height="1402" alt="Cuckoo Filter" src="https://github.com/user-attachments/assets/adea604e-a5d6-468a-b605-d7420e46a4c1"; /> The design uses chained expansion instead of in-place resizing. Resizing a Cuckoo Filter in place would change bucket indexes because bucket placement depends on the number of buckets, which would require rebuilding existing data. Instead, when the current chain cannot accept an item and scaling is enabled, Kvrocks appends a new sub-filter. Existing sub-filters remain valid and do not need to be rewritten. The main storage decision is to persist pages instead of individual buckets. The Cuckoo algorithm still works on logical bucket indexes, but RocksDB stores fewer, larger values. ## 5. Metadata Layout Each logical Cuckoo Filter key has one metadata entry in the Metadata column family. Conceptually: ```text Metadata column family: <namespace-prefixed user key> -> CuckooChainMetadata ``` The Redis type name is `MBbloomCF`, matching RedisBloom's Cuckoo Filter type name. `CuckooChainMetadata` extends the existing Kvrocks `Metadata` base class. The base metadata continues to provide common key-level fields such as type, expiration, version, and logical size. Cuckoo-specific fields are encoded after the base metadata. | Field | Type | Description | |---|---:|---| | `size` | `uint64_t` | Total number of successful insertions recorded in the logical Cuckoo Filter chain. This is inherited from base metadata. | | `expire` | `uint64_t` | Expiration timestamp inherited from base metadata. | | `version` | `uint64_t` | Metadata version inherited from base metadata. Page subkeys include this version so stale pages from older versions can be ignored. | | `n_filters` | `uint16_t` | Number of sub-filters in the chain. | | `expansion` | `uint16_t` | Growth factor used when appending a new sub-filter. `0` means non-scaling mode. Non-zero values are normalized to a power of two. | | `base_capacity` | `uint64_t` | Requested capacity of the first sub-filter. Later sub-filter capacity is derived from this value and `expansion`. | | `bucket_size` | `uint8_t` | Number of fingerprint slots per bucket. | | `max_iterations` | `uint16_t` | Maximum number of kick-out iterations before insertion is considered failed for a sub-filter. | | `num_deleted_items` | `uint64_t` | Reserved for delete/count maintenance in later commands. | | `page_size` | `uint32_t` | Target payload size for each persisted Cuckoo Filter page value. The current default is 2048 bytes. | `page_size` is an internal Kvrocks storage parameter. It is not exposed as a Redis command option. `CF.RESERVE` writes only metadata. It does not preallocate pages. Pages are created lazily when a bucket inside the page is first modified. Because a reserved but empty Cuckoo Filter has `size == 0`, `kRedisCuckooFilter` must be treated as an emptyable type in metadata logic. Otherwise, the key could be incorrectly treated as expired or removable simply because the logical size is zero. ## 6. Bucket and Page Storage Layout The earlier design stored each Cuckoo bucket as a separate RocksDB key. Review feedback pointed out that this would create too many tiny keys. For example, if a bucket contains only a few bytes, the RocksDB internal key, memtable, block index/filter, and compaction overhead can dominate the actual payload. The updated design groups multiple logical buckets into one persisted page value. Conceptually: ```text PrimarySubkey column family: InternalKey(<ns_key>, <filter_index, page_index>, version) -> page_data ``` The internal page subkey contains: - `filter_index`: the sub-filter index inside the chain. - `page_index`: the page index inside that sub-filter. The page value is a byte array. Each bucket occupies `bucket_size` bytes inside the page, and each byte stores one fingerprint slot: ```text page_data: bucket 0: [fp0, fp1, ...] bucket 1: [fp0, fp1, ...] ... ``` A fingerprint value of `0` means the slot is empty. Valid fingerprints are in the range `1..255`. The number of buckets per page is: ```text buckets_per_page = max(1, page_size / bucket_size) ``` The mapping from a logical bucket to a page is: ```text page_index = bucket_index / buckets_per_page offset = (bucket_index % buckets_per_page) * bucket_size ``` The last page of a sub-filter may be smaller than `page_size` because it only needs to contain the remaining buckets. When a page is missing from RocksDB, it is treated as an all-zero page of the expected size. When an existing page is present but has an unexpected size, the implementation treats it as corruption. <!-- TODO: Add diagram: one page containing many bucket byte ranges. --> This page-based layout reduces the number of RocksDB keys and improves storage efficiency compared with one-key-per-bucket storage, while preserving the logical Cuckoo Filter algorithm based on individual bucket indexes. ## 7. Hashing and Fingerprints The hashing model is part of the persistent data layout, so it must remain stable once Cuckoo Filter data has been written. The current implementation follows RedisBloom-style hashing: - The item hash uses `HllMurMurHash64A(data, length, 0)`. - The fingerprint is generated as `hash % 255 + 1`. - `0` is reserved as the empty-slot marker. - The first bucket uses `hash % num_buckets`. - The alternate hash uses `hash ^ (fingerprint * 0x5bd1e995)`. - The second bucket uses `alternate_hash % num_buckets`. For an item: ```text hash = MurmurHash64A(item, seed = 0) fingerprint = hash % 255 + 1 bucket1 = hash % num_buckets bucket2 = (hash ^ (fingerprint * 0x5bd1e995)) % num_buckets ``` During kick-out insertion, the implementation may no longer have the original full item hash for an evicted fingerprint. It computes the alternate bucket from the current bucket index and the fingerprint: ```text alternate_bucket = (current_bucket ^ (fingerprint * 0x5bd1e995)) % num_buckets ``` The bucket count is rounded to a power of two. With a power-of-two bucket count, using the bucket index in the alternate-bucket calculation preserves the required symmetry for moving a fingerprint between its two candidate buckets. ## 8. Capacity and Expansion The requested capacity is converted into a bucket count using a target load factor of `0.955`. ```text required_buckets = ceil(capacity / bucket_size / 0.955) num_buckets = next_power_of_two(required_buckets) ``` The power-of-two bucket count is required for correct alternate-bucket behavior and better distribution. The default parameters are aligned with RedisBloom compatibility: | Parameter | Default | |---|---:| | `capacity` for auto-created filters | `1024` | | `BUCKETSIZE` | `2` | | `MAXITERATIONS` | `20` | | `EXPANSION` | `1` | | `page_size` | `2048` bytes | `EXPANSION` behavior: - `EXPANSION 0` disables scaling. If the filter becomes full, insertion returns an error. - `EXPANSION 1` appends new sub-filters with the same capacity as the first sub-filter. - Non-zero values greater than one are normalized to the next power of two before being stored. - The maximum accepted `EXPANSION` value is `32768`. The capacity of sub-filter `i` is derived as: ```text filter_capacity(i) = base_capacity * expansion^i ``` For non-scaling filters, `n_filters` should remain `1`. ## 9. Atomicity, Expiration, and Versioning All writes that modify bucket/page data and metadata are committed through one RocksDB write batch. This is important because `metadata.size`, `metadata.n_filters`, and page contents must describe the same logical state. For example, after a successful `CF.ADD`, the modified page and the incremented metadata size should become visible together. Kvrocks metadata versioning is reused for Cuckoo Filter page subkeys. The page key includes the current metadata version, so stale pages from older versions can be ignored after key overwrite or deletion. This follows the same general pattern used by other complex data types in Kvrocks. Expiration is handled by the existing metadata layer. Cuckoo Filter-specific code should use `Database::GetMetadata`/type-aware metadata loading instead of raw metadata CF reads so expired keys and wrong-type cases are handled consistently. ## 10. Replication and Migration Replication uses Kvrocks' existing write-batch propagation mechanism. Cuckoo Filter writes include write-batch log data with the `kRedisCuckooFilter` type. The actual metadata and page updates are then replayed as part of the replicated write batch. For slot migration: - Raw key-value migration is supported because it copies the metadata and page subkeys directly. - Command-based migration is intentionally unsupported for now. Command-based migration is difficult because Cuckoo Filter pages contain only fingerprints, not original items. Kvrocks cannot reconstruct a semantically equivalent sequence of `CF.ADD` commands from the persisted data. The current behavior should explicitly return an unsupported error for `MBbloomCF` command migration and ask users to use raw key-value migration. ## 11. Disk Usage and Scan/Type Integration The new type is registered as `kRedisCuckooFilter` with Redis type name `MBbloomCF`. Integration points: - `TYPE key` should return `MBbloomCF`. - `SCAN ... TYPE MBbloomCF` should include Cuckoo Filter keys. - `DISK USAGE key` should account for the metadata entry and page subkeys. - Empty reserved Cuckoo Filters should be valid keys and should not be dropped only because `metadata.size == 0`. ## 12. Trade-Offs ### 12.1 Chained Sub-Filters Instead of Rehashing Appending sub-filters avoids rebuilding existing data and keeps expansion cheap. The trade-off is that future lookup, count, and delete commands may need to inspect candidate buckets in multiple sub-filters. For `CF.EXISTS`, this means checking the two candidate buckets in each sub-filter until a match is found or all sub-filters are exhausted. For `CF.COUNT`, this means scanning the two candidate buckets in each sub-filter and summing matching fingerprints. For `CF.DEL`, this means finding and removing one matching fingerprint occurrence across the chain. ### 12.2 Paged Buckets Instead of Bucket-Per-Key Paged bucket storage reduces RocksDB key overhead and improves space efficiency. The trade-off is write amplification at the page level: modifying one bucket rewrites the containing page value. This is acceptable because the page size is bounded and the alternative bucket-per-key design would create a large number of very small RocksDB entries. The default page size is currently 2048 bytes. This should be treated as an internal storage parameter, not a user-facing RedisBloom option. ## 13. References - Tracking issue: https://github.com/apache/kvrocks/issues/3123 - Current implementation PR: https://github.com/apache/kvrocks/pull/3481 - Earlier discussion: https://github.com/apache/kvrocks/discussions/3079 - Redis Cuckoo Filter documentation: https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/ - Cuckoo Filter paper: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf GitHub link: https://github.com/apache/kvrocks/discussions/3530 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected]
