Proposal for Cuckoo Filter

[nagisa-kunhah]

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 #3123. The first implementation work is being developed in #3481, starting with CF.RESERVE and CF.ADD. This proposal updates the earlier Cuckoo Filter discussion in #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.

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. Cuckoo Filter on RocksDB

Kvrocks stores one logical Cuckoo Filter as one metadata entry and multiple page subkeys. The metadata describes the logical filter chain, while page subkeys store bucket slots. This follows Kvrocks' metadata/subkey model and avoids introducing a new RocksDB column family.

5.1 Logical Structure

A logical Cuckoo Filter contains one or more sub-filters. Each sub-filter contains logical buckets. Each bucket contains bucket_size one-byte fingerprint slots. Buckets are grouped into page values before being stored in RocksDB.

Logical Cuckoo Filter key
  -> CuckooChainMetadata
  -> Sub-filter 0
       -> Page 0
            -> Bucket 0: [slot 0, slot 1, ...]
            -> Bucket 1: [slot 0, slot 1, ...]
       -> Page 1
       -> ...
  -> Sub-filter 1
       -> Page 0
       -> ...

5.2 Metadata

In the examples below, ns_key represents Kvrocks' internal key after namespace handling.

Metadata column family:
              +------+--------+---------+------+-----------+-----------+---------------+-------------+----------------+-------------------+-----------+
              | type | expire | version | size | n_filters | expansion | base_capacity | bucket_size | max_iterations | num_deleted_items | page_size |
ns_key =>     +------+--------+---------+------+-----------+-----------+---------------+-------------+----------------+-------------------+-----------+
              | 1B   | 8B     | 8B      | 8B   | 2B        | 2B        | 8B            | 1B          | 2B             | 8B                | 4B        |
              +------+--------+---------+------+-----------+-----------+---------------+-------------+----------------+-------------------+-----------+

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.

5.3 Page Subkeys and Values

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.

PrimarySubkey column family:
                                             +------------------+------------------+-----+------------------+
                                             | bucket 0 slots   | bucket 1 slots   | ... | bucket N slots   |
InternalKey(ns_key, sub_key, version) =>     +------------------+------------------+-----+------------------+
                                             | bucket_size byte | bucket_size byte | ... | bucket_size byte |
                                             +------------------+------------------+-----+------------------+

sub_key is encoded separately:

sub_key:
+-----------------------+--------------------+
| filter_index (uint16) | page_index (uint32) |
+-----------------------+--------------------+

• filter_index: the sub-filter index inside the chain.
• page_index: the page index inside that sub-filter.
• page_data: a byte array containing multiple logical buckets.

The version is inherited from the metadata and encoded by InternalKey. It separates current page subkeys from stale page subkeys left by older versions of the same logical key.

A fingerprint value of 0 means the slot is empty. Valid fingerprints are in the range 1..255.

For example, if bucket_size = 2 and page_size = 2048, each page can store 1024 logical buckets. Updating one bucket rewrites the containing page value, but avoids creating one RocksDB key per bucket.

5.4 Bucket Location

The number of buckets per page is:

buckets_per_page = max(1, page_size / bucket_size)

The mapping from a logical bucket to a page is:

page_index = bucket_index / buckets_per_page
offset = (bucket_index % buckets_per_page) * bucket_size

6. 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:

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:

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.

7. Capacity and Expansion

The requested capacity is converted into a bucket count using a target load factor of 0.955.

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:

filter_capacity(i) = base_capacity * expansion^i

For non-scaling filters, n_filters should remain 1.

8. 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.

9. 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.

10. 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.

11. Trade-Offs

11.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.

11.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.

12. References

• Tracking issue: Tracking Issues: support Cuckoo Filter data structure and commands #3123
• Current implementation PR: feat(cf): add cf.add command #3481
• Earlier discussion: Cuckoo Filter Design Proposal #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

[jihuayu]

You did a great job, but I would like the content to include more data-structure-related material like this (https://kvrocks.apache.org/community/data-structure-on-rocksdb). That way, we can directly move it onto the page when we release.

[nagisa-kunhah]

You did a great job, but I would like the content to include more data-structure-related material like this (https://kvrocks.apache.org/community/data-structure-on-rocksdb). That way, we can directly move it onto the page when we release.

Ok, I added a new section, 5. Cuckoo Filter on RocksDB, following the style of the Kvrocks data-structure-on-RocksDB documentation. Does this better match what you expected? If the section is too detailed, or if there is still any important data-structure/storage-layout information missing, I would be happy to adjust it.