Probabilistic Data Structures for Redis and Valkey in Java: Bloom, Cuckoo and Top-K

Some questions in a data-intensive Java application do not need an exact answer. Have I seen this username before? Is this URL already crawled? Which search terms are trending right now? Answer them exactly and you pay for a counter or a key per distinct item, and the memory grows with the size of the long tail rather than with the part you care about. A HashSet of fifty million usernames is not a data structure, it is a capacity-planning problem.

Probabilistic data structures trade exactness for a fixed, tiny memory footprint. A Bloom filter answers "have I seen this?" in a handful of bits per item instead of the item itself. A Cuckoo filter answers the same question and lets you delete. A Top-K sketch answers "which items show up most?" without a counter per item. All three live in the datastore rather than on your JVM heap, so several application instances share one filter, and Redisson exposes each one as an ordinary Java object.

This guide covers the four structures you are most likely to reach for, the sizing decision that determines whether a Bloom filter works or quietly degrades, and — the part that catches people migrating — exactly which of them exist on Valkey and which do not.

The First Decision: Module or No Module

Before any code, there is a fork that decides most of what follows. Redis and Valkey do not ship Bloom filters in the core server. They arrive through a module — RedisBloom on Redis, valkey-bloom on Valkey — and a managed instance may or may not have it loaded.

Redisson gives you two Bloom filter implementations because of this, and choosing the wrong one is the most common mistake in this corner of the API:

The rule is simple. If you control the server, or your provider loads the module, RBloomFilterNative is the better structure — the work happens server-side and the filter can grow. If you are on a managed instance that will not load modules, or you need one codebase to run against several deployments you do not control, RBloomFilter works everywhere with no module at all. That portability is the reason it exists, and it is worth more than it looks when a migration lands on you later.

RBloomFilter: The One That Runs Anywhere

RBloomFilter is implemented on ordinary bit operations, so it works against any Redis or Valkey deployment — cloud, on-premises, cluster, no modules required. You declare the expected number of insertions and the false-positive probability you will tolerate, and Redisson derives the bit array size and hash count from them.

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;

public class BloomFilterExample {

    public static void main(String[] args) {
        RedissonClient redisson = ... // Initialize your RedissonClient

        RBloomFilter<String> filter = redisson.getBloomFilter("crawled-urls");

        // Size it ONCE, before first use: expected insertions and error rate.
        // Returns false if the filter already exists - it does not resize.
        filter.tryInit(55_000_000L, 0.03);

        filter.add("https://example.com/page-1");

        // false means DEFINITELY absent. true means PROBABLY present.
        if (!filter.contains("https://example.com/page-2")) {
            crawl("https://example.com/page-2");
        }

        System.out.println("Approximate items:   " + filter.count());
        System.out.println("Bit array size:      " + filter.getSize());
        System.out.println("Hash iterations:     " + filter.getHashIterations());
        System.out.println("Configured for:      " + filter.getExpectedInsertions());
        System.out.println("Configured error:    " + filter.getFalseProbability());
    }
}

Two details in that block matter more than the rest. tryInit sizes the filter permanently. It returns false if the filter already exists, and it does not resize an existing one — a Bloom filter cannot be resized without rebuilding it from the source data, because the bit positions depend on the array length. Get the estimate wrong upward and you waste memory; get it wrong downward and the error rate climbs past what you asked for, silently. And the asymmetry of the answer is the whole contract: false is certain, true is probable. There are no false negatives, only false positives, which is why a Bloom filter is safe in front of a cache or a database and unsafe as the final word on anything.

Sizing It Before It Degrades

The cost per element depends only on the error rate you choose, not on the size of the items. That makes the arithmetic easy, and it makes the 2³²-bit ceiling on RBloomFilter concrete:

Read the last column as the point where RBloomFilter stops being an option, not as a target. Note also what the third column costs you: tightening the error rate from 3% to 0.01% multiplies the bits per element by 2.6 and the hash iterations — and therefore the work on every single read — by roughly 2.6 as well. A 0.01% filter is not a free upgrade over a 3% one.

Above a few hundred million elements you need either RBloomFilterNative, which is bounded by available memory rather than a fixed ceiling, or RClusteredBloomFilter in Redisson PRO, which raises the limit to 2⁶³ bits by partitioning the filter across a Redis or Valkey cluster rather than holding it in one slot. A single-slot 512 MiB value is also a resharding and replication problem in its own right, which is the practical reason large filters get partitioned well before they reach the theoretical cap.

RBloomFilterNative: Server-Side Bloom on Redis and Valkey

Where the module is available, RBloomFilterNative maps onto the server's own BF.* commands. The filter lives and executes entirely server-side, bulk operations become one round trip, and the structure can grow past the capacity you declared instead of degrading against a fixed array.

import org.redisson.api.RBloomFilterNative;
import org.redisson.api.RedissonClient;
import org.redisson.api.BloomFilterInfo;
import java.util.Arrays;
import java.util.Set;

public class BloomFilterNativeExample {

    public static void main(String[] args) {
        RedissonClient redisson = ... // Initialize your RedissonClient

        RBloomFilterNative<String> filter =
                redisson.getBloomFilterNative("username-blacklist");

        // 3% error rate, 55 million expected items
        filter.init(0.03, 55_000_000L);

        filter.add("user_spammer_1");

        // Bulk add and bulk test are each ONE round trip
        filter.add(Arrays.asList("user_bot_A", "user_bot_B"));
        Set<String> present = filter.exists(Arrays.asList("user_bot_A", "clean_user"));
        System.out.println("Present from batch: " + present);

        // BF.CARD - see the caveat below
        System.out.println("Unique items added: " + filter.count());

        BloomFilterInfo info = filter.getInfo();
        System.out.println("Capacity: " + info.getCapacity());
        System.out.println("Size (bytes): " + info.getSize());
    }
}

The bulk forms are the reason to prefer this variant when you have the choice. Checking two hundred candidate keys with exists(Collection) is a single command; the same check against RBloomFilter.contains in a loop is two hundred round trips, and at that point the network dominates whatever the structure saved you.

What Happens When You Exceed the Capacity You Declared

A native filter does not fail when it fills up — by default it scales, and understanding how is what separates a filter that ages well from one that quietly gets slower. When capacity is reached the server creates an additional sub-filter, and per the Redis documentation, "the size of the new sub-filter is the size of the last sub-filter multiplied by expansion." Every subsequent lookup must then consult every sub-filter. The documentation is blunt about the cost: "performance will begin to degrade after adding more items than this number… Performance degrades linearly with the number of sub-filters."

Redisson exposes both knobs through BloomFilterInitArgs:

import org.redisson.api.BloomFilterInitArgs;

filter.init(BloomFilterInitArgs.create()
        .errorRate(0.01)
        .capacity(1_000_000L)
        .expansionRate(4));      // each sub-filter 4x the last

Pick expansionRate by how well you know the workload. A high expansion rate means fewer, larger sub-filters — fewer to consult on every read, more memory committed up front. An expansion rate of 1 keeps memory tight when the capacity is genuinely known. The default is 2. The non-scaling option trades the degradation for an explicit failure: the filter "returns an error when capacity is reached," which is the right choice when you would rather be paged than silently slow.

None of this changes the advice to estimate properly at creation time. The reference is explicit that maintaining and querying sub-filters "requires additional memory… and consume further CPU time than an equivalent filter that had the right capacity at creation time." Scaling is a safety net, not a sizing strategy.

count() Is Not the Count You Think It Is

RBloomFilterNative.count() issues BF.CARD, and the definition repays a careful read. It returns the "number of items that were added to a Bloom filter and detected as unique (items that caused at least one bit to be set in at least one sub-filter)."

Two consequences follow. Adding the same item twice increments it once, so it is a cardinality estimate rather than a count of calls. And more subtly — an item that collides into a set of bits that are all already set is never counted at all. That is exactly the false-positive case, so BF.CARD undercounts by roughly the number of false positives the filter has produced. For dashboards and capacity alarms it is fine. For anything that has to reconcile, it is not a number to bill against.

Cuckoo Filters: Membership You Can Delete From

A Bloom filter has one structural limitation that no amount of tuning removes: you cannot delete from it. Bits are shared between items, so clearing the bits for one item may clear bits another item depends on, which would create false negatives and break the one guarantee the structure offers. The standard workaround is to rebuild the filter periodically from the source of truth, which is fine for a nightly job and useless for anything that has to forget an item now.

A Cuckoo filter stores a short fingerprint per item in one of two candidate buckets rather than setting shared bits, so a specific item can be located and removed. Redisson exposes it as RCuckooFilter:

import org.redisson.api.RCuckooFilter;
import org.redisson.api.RedissonClient;
import java.util.List;
import java.util.Set;

public class CuckooFilterExample {

    public static void main(String[] args) {
        RedissonClient redisson = ... // Initialize your RedissonClient

        RCuckooFilter<String> filter = redisson.getCuckooFilter("active-sessions");
        filter.init(100_000);

        filter.add("session-123");

        // addIfAbsent() is the deduplicating add: false means already present
        boolean wasNew = filter.addIfAbsent("session-456");

        Set<String> live = filter.exists(List.of("session-123", "session-999"));

        // The capability Bloom filters do not have
        boolean removed = filter.remove("session-123");
        System.out.println("Session 123 removed: " + removed);
    }
}

The Deletion Rule That Corrupts the Filter

The deletion that makes Cuckoo filters attractive comes with a rule that is easy to violate and expensive when you do. The Redis documentation states it as plainly as documentation ever states anything: "Never use this command to delete an item unless you are certain you've added the item to the filter. Deleting an item you didn't previously add may corrupt the filter and cause false negatives."

The mechanism is worth understanding, because it explains why this is unfixable rather than merely discouraged. The filter stores fingerprints, not items, and fingerprints collide. Deleting an item you never inserted will happily find a matching fingerprint belonging to some other item and remove that instead. The filter now reports false for something genuinely present — and a false negative destroys the only guarantee a membership filter makes. Nothing detects it, and nothing repairs it short of a rebuild.

In practice this means a Cuckoo filter is safe when deletions are driven by an authoritative event — a session that your own code created and is now ending, a record you know you indexed — and unsafe when driven by user input or an external feed. Note also that deletion removes one occurrence: "if the item was added multiple times, it will still be present."

Top-K: Which Items Show Up Most

Membership is one question; frequency is another. Which search terms are trending? Which API clients account for most of the traffic? Which products are selling? Keeping an exact counter per distinct item in a HashMap<String, Long> fails for the same reason a HashSet did — the map grows with the number of distinct keys, not with the twenty you actually want, and sorting it on every read adds cost.

A Top-K sketch tracks the k most frequent items in fixed memory using the HeavyKeeper algorithm, regardless of how many distinct items pass through it. Redisson exposes it as RTopK:

import org.redisson.api.RTopK;
import org.redisson.api.RedissonClient;
import java.util.List;
import java.util.Map;

RTopK<String> trending = redisson.getTopK("trending:searches");
trending.init(20);                       // track the top 20

// add() returns the item pushed out of the leaderboard, or null
String evicted = trending.add("postgres");

// Weight an event by its cost rather than counting it once
trending.incrementBy("postgres", 5);

boolean isLeader = trending.contains("postgres");

List<String> leaders = trending.list();
Map<String, Long> withCounts = trending.listWithCount();

Prefer listWithCount() over the older per-item count(), which is deprecated as of Redis Bloom 2.4.0 because its estimate can be inaccurate; listWithCount() returns the leaderboard and its approximate counts in a single call. When you need finer control over the accuracy-versus-memory trade-off, init(TopKInitArgs) exposes the underlying sketch — width (counters per array, default 8), depth (number of arrays, default 7) and decay (the probability a counter is decremented on collision, default 0.9):

import org.redisson.api.TopKInitArgs;

trending.init(TopKInitArgs.topK(50)
        .width(2000)
        .depth(7)
        .decay(0.925));

What "Approximate" Means in Practice

The structure hashes each item into a small grid of counters and, when different items collide, decays the existing count probabilistically. Items with large counts are very unlikely to be decayed away, so genuine heavy hitters are protected while rare items fade — that selective forgetting is precisely what buys the bounded memory.

Two consequences shape what you can build on it. The counts are estimates, which makes them right for ranking, leaderboards and dashboards and wrong for billing or quota enforcement. And items sitting at the boundary of the top k may be reported in or out from one read to the next — the clear leaders are stable, the marginal ones are not. If you need exact counts or a precise ordering, an RScoredSortedSet is the honest tool; if the distinct-item count is small enough that a counter each is cheap, a plain counter is simpler than any sketch.

What Runs on Valkey and What Does Not

This is where teams get surprised, and it is the single most useful thing to check before you write code you intend to run on both. Redis's RedisBloom module implements five command families. Valkey's valkey-bloom module implements one.

There is one further divergence inside the Bloom family itself, and it is easy to miss because everything else lines up. Redis dumps and restores a filter through the BF.SCANDUMP / BF.LOADCHUNK pair, which is what Redisson's scanDump() and loadChunk() map onto. Valkey has neither. It offers BF.LOAD, which restores a filter in a single operation, and no chunked dump at all. Ordinary add, exists, count and getInfo code ports without change; a backup or migration routine built on scanDump() does not.

The practical consequence for anyone migrating from Redis to Valkey: RBloomFilter and RHyperLogLog move without thinking about it, RBloomFilterNative moves provided valkey-bloom is loaded and you are not dumping filters, and RCuckooFilter, RTopK and RTDigest do not move at all. Nothing in the Java type system distinguishes the two targets, so the failure arrives at runtime as an unknown command. Pin the server in your integration tests — it is the only check that actually runs. For the wider picture, see Valkey vs Redis.

Choosing Between Them

One pattern deserves a note because it is where most of these end up in production. Putting a Bloom filter in front of a datastore turns a lookup for a key that does not exist into a local false instead of a cache miss that reaches the database — the standard defence against a flood of requests for nonexistent keys. It works precisely because the answer you rely on is the negative one, which is the answer a Bloom filter gives with certainty. The same asymmetry makes these structures a poor fit for idempotency keys, where a false positive means silently dropping work that was never done; use an atomic claim on a real key for that.

Frequently Asked Questions

Does Redis Have a Built-In Bloom Filter?

Not in the core server. BF.* commands arrive with the RedisBloom module on Redis, or valkey-bloom on Valkey 8.0 and above. Redisson works around this with two implementations: RBloomFilterNative uses the module commands, while RBloomFilter is built on core bit operations and runs on any deployment with nothing loaded. If you are unsure what a managed instance has, RBloomFilter is the safe default.

What Is the Difference Between RBloomFilter and RBloomFilterNative?

RBloomFilter needs no module, is capped at 2³² bits, and cannot grow past the capacity given to tryInit. RBloomFilterNative requires RedisBloom or valkey-bloom, executes server-side, does bulk adds and tests in one round trip, and scales by chaining sub-filters when it exceeds the capacity given to init. Choose on module availability first, then on scale.

How Do I Size a Redis Bloom Filter?

Cost per element depends only on the false-positive rate: roughly 7.3 bits at 3%, 9.6 at 1%, 14.4 at 0.1%. Multiply by the number of items you expect at the filter's end of life, not today's number, because a Bloom filter cannot be resized — the bit positions depend on the array length, so changing it means rebuilding from source. Tightening the error rate also raises the hash-iteration count, which is work on every read, so 0.01% is not a free upgrade over 3%.

What Happens When a Bloom Filter Exceeds Its Capacity?

With RBloomFilter, nothing visible — the bit array is fixed, so the observed false-positive rate simply climbs past what you configured. With RBloomFilterNative the server adds a sub-filter sized by the expansion rate, and every later lookup consults every sub-filter; the Redis documentation notes that "performance degrades linearly with the number of sub-filters." The non-scaling option returns an error at capacity instead, which is preferable when you would rather fail loudly than degrade quietly.

Can You Delete From a Bloom Filter?

No. Bits are shared between items, so clearing one item's bits can clear bits another depends on, producing false negatives and breaking the structure's only guarantee. Use RCuckooFilter when you need deletion, or rebuild the Bloom filter periodically from the source of truth. Note the Cuckoo rule: never delete an item you are not certain you added, because a fingerprint collision will remove some other item's entry and corrupt the filter.

Which Probabilistic Structures Work on Valkey?

RBloomFilter and RHyperLogLog work everywhere with no module. RBloomFilterNative works with valkey-bloom on Valkey 8.0+, except for scanDump() and loadChunk() — Valkey has BF.LOAD rather than BF.SCANDUMP/BF.LOADCHUNK. RCuckooFilter, RTopK and RTDigest have no Valkey equivalent at all, because valkey-bloom implements only the BF.* family.

Does Redisson Support Count-Min Sketch?

The probabilistic-structures reference documents six structures — Bloom, Bloom native, Cuckoo, HyperLogLog, Top-K and t-digest — and Count-Min Sketch is not among them. In most cases RTopK is what you actually wanted: Count-Min Sketch estimates the frequency of an item you name, while Top-K maintains the leaderboard of heaviest items itself. For exact per-item counts, use a sorted set or an atomic counter.

Why Does count() Return Fewer Items Than I Added?

Because BF.CARD counts "items that were added… and detected as unique (items that caused at least one bit to be set)." Re-adding the same item does not increment it, and an item whose bits were all already set — the false-positive case — is never counted. The shortfall is therefore roughly the number of false positives the filter has produced. Treat it as a cardinality estimate, not an audit trail.

Next Steps

Probabilistic structures are the right answer whenever the exact answer costs more than it is worth and a bounded error is acceptable — which covers far more of a production system than most teams assume. The decision order that keeps you out of trouble is: check module availability, size for end-of-life rather than today, and confirm the structure exists on every server you intend to run against.

From here, Redis Data Structures in Java maps the rest of the type system onto its Java objects, and Redis Use Cases puts these patterns in context alongside caching, locking and queues. Distributed Rate Limiting covers the counting problem these sketches deliberately approximate, and Redis-based Time Series covers the windowed variant. The probabilistic structures reference carries the async, reactive and RxJava3 forms of everything above. And if you need a Bloom filter past 2³² bits, RClusteredBloomFilter in Redisson PRO partitions it across the cluster — try it for free.

Similar articles

• Redis Data Structures in Java
• T-Digest for Redis on Java
• How to Use Redis (or Valkey) in Java
• A Redis-based Java Time Series Collection
• Vector Sets in Valkey and Redis