Interview: Bloom Filter vs Cuckoo Filter for a One-Billion-User System
One billion usernames in 1.2 GB — Bloom or Cuckoo? Interviewers ask exactly this.
Interviewers often open with this one: how do you check whether a username already exists among one billion users? In the previous article we gave the cheapest answer, the Bloom filter. At a 1% false positive rate each element needs about 9.6 bits, so a table of one billion usernames fits in 1.2 GB of memory. Push the target down to 0.1% and each element climbs to 14.4 bits, about 1.8 GB, still within reach of a single machine.
So what is the Cuckoo filter for? Because lists get deleted. Usernames almost never disappear, but blacklists and device lists lose entries all the time, and the Bloom filter has no delete operation.
The database stays the source of truth. The filter is just a gate in front of it. Bloom or Cuckoo comes down to one question: will this set lose entries?
Understanding the Challenge
Checking a username against one billion existing users packs several problems into one path.
The set is too large to scan. On the registration hot path, a linear pass over one billion rows is out of the question.
This check runs right in front of the user. Every registration needs it, so does most login traffic, and it has to come back in single-digit milliseconds. Slower than that and the product starts to feel laggy.
Memory matters just as much. A hash set of one billion usernames, ten bytes each on average, runs to tens of gigabytes. You need a structure far smaller than the raw data to answer the membership question.
Usernames almost never disappear, but other lists do. Blacklists get unbanned, device lists expire, rate-limit lists get cleared. Once the filter cannot remove entries, the only option is a full rebuild.
Two users can race for the same username. The filter tells both “probably available”, and something downstream still has to guarantee that only one registration succeeds.
The Baseline: Database Design
No matter what filter sits in front, the database stays the source of truth. The schema from the previous article still works.
CREATE TABLE users (
user_id BIGINT PRIMARY KEY AUTO_INCREMENT,
username VARCHAR(255) UNIQUE NOT NULL,
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);
The unique index on username is not optional. It is the atomic gate that blocks duplicates when two requests race. A plain B-tree index handles point lookups fine, and the unique constraint doubles as the concurrency backstop.
The most direct way is to query the database once.
SELECT COUNT(*) FROM users WHERE username = 'desiredUsername';Or as a prepared statement.
boolean exists = jdbcTemplate.queryForObject(
"SELECT COUNT(*) FROM users WHERE username = ?",
Boolean.class, username);
Both work, and both cost too much on the hot path. At one billion rows, every check walks the index and fetches data, burning database CPU even when the answer is obvious. The database should only see the cases the filter cannot decide.
Step One: Put a Bloom Filter in Front
A Bloom filter answers one binary question: is this element in the set? It maps the element to k positions in a bit array with k hash functions. All k positions must be 1 for the answer to be “possibly present”. If any position is 0, the element is definitely not there.
That asymmetry is the point. It never produces false negatives, it can produce false positives, and the rate is tunable. With a bit array of size m and k hash functions, the false positive rate is about
(1 - e^(-kn/m))^kThe optimal number of hash functions is k = (m/n) * ln(2). At a 1% false positive rate, m/n lands around 9.6 bits and k is 7. At 0.1%, m/n is about 14.4 bits and k is about 10. Element length does not matter: one billion entries at 1% cost a fixed 1.2 GB, whether the usernames are 6 characters or 60.
A Minimal Java Implementation
import java.util.BitSet;
public class SimpleBloomFilter {
private final BitSet bits;
private final int size;
private final int hashCount;
public SimpleBloomFilter(int size, int hashCount) {
this.bits = new BitSet(size);
this.size = size;
this.hashCount = hashCount;
}
private int[] positions(String value) {
int[] pos = new int[hashCount];
int hash1 = value.hashCode();
int hash2 = (hash1 >>> 16) | (hash1 << 16);
for (int i = 0; i < hashCount; i++) {
pos[i] = Math.floorMod(hash1 + i * hash2, size);
}
return pos;
}
public void add(String value) {
for (int p : positions(value)) {
bits.set(p);
}
}
public boolean mightContain(String value) {
for (int p : positions(value)) {
if (!bits.get(p)) {
return false; // one bit is 0, definitely absent
}
}
return true; // all bits are 1, possibly present
}
}Don’t write this yourself in production. Guava’s BloomFilter handles sizing, hashing, and serialization.
BloomFilter<String> takenUsernames = BloomFilter.create(
Funnels.stringFunnel(StandardCharsets.UTF_8),
1_000_000_000L, // expected insertions
0.01); // target false positive rate
takenUsernames.put("alice");
boolean taken = takenUsernames.mightContain("alice");Redis exposes the same operations as commands.
BF.RESERVE usernames 0.01 1000000000
BF.ADD usernames alice
BF.EXISTS usernames aliceThe Problem Bloom Cannot Solve: Deletion
Bits are shared. Clearing the bits of one element drags down other elements with it. A standard Bloom filter supports insert and query, nothing else.
The usual patch is a counting Bloom filter: each position holds a counter instead of a single bit, and delete decrements the counter. The cost is memory, about four times the standard filter with 4-bit counters. Counters saturate at 15, so heavy delete traffic still produces errors. It is a patch, and the underlying design still has no native delete.
For username availability this does not matter: accounts are almost never deregistered, and the set only grows. Blacklists and device lists are different, deletion is a hard requirement.
Step Two: Cuckoo Filter When Deletion Matters
The Cuckoo filter comes from Fan et al.’s 2014 paper Cuckoo Filter: Practically Better Than Bloom, built to close exactly this gap.
Instead of a bit array, it stores a short fingerprint per element. Each element maps to two candidate buckets, and lookups only check those two. When both are full, the new fingerprint kicks out an old one, and the displaced fingerprint moves to its alternate bucket. The name comes from the cuckoo’s habit of pushing other eggs out of the nest.
Kicks push the load factor to about 95%, which keeps the filter compact. Fan et al. compared it directly with the alternatives: against counting Bloom filters it saves about half the space, against a non-deletable, space-optimized Bloom filter it costs 1.5 to 2 times more. The lower the target false positive rate, the smaller the gap. A USENIX ;login article gives a concrete pair of numbers: a Cuckoo filter with 12-bit fingerprints uses about 12.53 bits per element at a 0.19% false positive rate, while a Bloom filter uses 13 bits at 0.20%. At the one-billion scale the two filters sit in the same memory class, the real difference is deletion.
Fingerprint size follows a simple rule: for a target false positive rate r and bucket size b, take f >= log2(2b/r) bits. With 4-slot buckets and a 1% target, that means 10-bit fingerprints, about 10.5 bits per element including the load factor. Slightly above the Bloom filter’s 9.6 bits. When deletion is a hard requirement, that extra cost is worth paying.
A Simplified Java Implementation with Delete
public class SimpleCuckooFilter {
private static final int BUCKET_SIZE = 4; // fingerprints per bucket
private static final int MAX_KICKS = 500; // max kick attempts
private final long[][] buckets;
private final int numBuckets;
public SimpleCuckooFilter(int numBuckets) {
this.buckets = new long[numBuckets][BUCKET_SIZE];
this.numBuckets = numBuckets;
}
private long fingerprint(String value) {
return value.hashCode() & 0xFFFFL; // 16-bit fingerprint
}
private int index1(String value) {
return Math.floorMod(value.hashCode(), numBuckets);
}
private int index2(int i1, long fp) {
return Math.floorMod(i1 ^ Long.hashCode(fp), numBuckets);
}
private boolean insertInto(int index, long fp) {
for (int j = 0; j < BUCKET_SIZE; j++) {
if (buckets[index][j] == 0) {
buckets[index][j] = fp;
return true;
}
}
return false;
}
public boolean insert(String value) {
long fp = fingerprint(value);
int i1 = index1(value);
int i2 = index2(i1, fp);
if (insertInto(i1, fp) || insertInto(i2, fp)) {
return true;
}
int index = (Math.random() < 0.5) ? i1 : i2;
for (int k = 0; k < MAX_KICKS; k++) {
int slot = (int) (Math.random() * BUCKET_SIZE);
long kicked = buckets[index][slot];
buckets[index][slot] = fp;
fp = kicked;
index = index2(index, fp);
if (insertInto(index, fp)) {
return true;
}
}
return false; // too full, expand or rebuild
}
public boolean contains(String value) {
long fp = fingerprint(value);
int i1 = index1(value);
int i2 = index2(i1, fp);
for (int j = 0; j < BUCKET_SIZE; j++) {
if (buckets[i1][j] == fp || buckets[i2][j] == fp) {
return true;
}
}
return false;
}
public boolean delete(String value) {
long fp = fingerprint(value);
int i1 = index1(value);
int i2 = index2(i1, fp);
for (int j = 0; j < BUCKET_SIZE; j++) {
if (buckets[i1][j] == fp) {
buckets[i1][j] = 0;
return true;
}
}
for (int j = 0; j < BUCKET_SIZE; j++) {
if (buckets[i2][j] == fp) {
buckets[i2][j] = 0;
return true;
}
}
return false;
}
}
This is a teaching version: empty slots are marked with 0 and fingerprints are only 16 bits. A production implementation also has to handle fingerprint collisions, delete edge cases, and expansion. One warning: deleting a fingerprint that was never inserted, a false positive, removes someone else’s fingerprint and creates a false negative. Only delete what you actually added.
Redis provides the same operations, and delete is the one command Bloom cannot offer.
CF.RESERVE usernames 1000000000 BUCKETSIZE 4
CF.ADD usernames alice
CF.EXISTS usernames alice
CF.DEL usernames alice
Rewriting the Original Example: A Filter-First Service
The previous article cached query results with short TTLs. This version moves the filter in front of the database, which stays the source of truth.
@Service
public class UsernameAvailabilityService {
private final BloomFilter<String> takenUsernames = BloomFilter.create(
Funnels.stringFunnel(StandardCharsets.UTF_8),
1_000_000_000L,
0.01);
private final UserRepository userRepository;
public UsernameAvailabilityService(UserRepository userRepository) {
this.userRepository = userRepository;
}
public boolean isAvailable(String username) {
if (!takenUsernames.mightContain(username)) {
return true; // definitely absent, no database call
}
// filter says "possibly taken", verify against the source of truth
return !userRepository.existsByUsername(username);
}
@Transactional
public void register(String username) {
if (!isAvailable(username)) {
throw new UsernameTakenException(username);
}
try {
userRepository.insert(username); // unique index is the final gate
takenUsernames.put(username); // keep the filter warm
} catch (DuplicateKeyException e) {
throw new UsernameTakenException(username);
}
}
}
The flow matches the original architecture diagram: the filter absorbs the vast majority of requests, and the database only sees the “possibly taken” cases plus the final insert.
Lists that need deletion use the same pattern, just with a Cuckoo filter. The service below keeps a blacklist in memory and supports unbanning, something the Bloom version cannot do without a rebuild.
public class BlacklistService {
private final SimpleCuckooFilter blockedTokens = new SimpleCuckooFilter(1 << 20);
public boolean isBlocked(String token) {
return blockedTokens.contains(token);
}
public void block(String token) {
blockedTokens.insert(token);
}
public void unblock(String token) {
blockedTokens.delete(token);
}
}
Handling Concurrency
The filter answers the membership question, it is not a transaction. Two users can both see the same username as “available”, and the unique index turns the race into a single winner.
The cleanest approach is atomic check-and-insert: try the insert, let the database enforce the constraint, and translate DuplicateKeyException into a friendly error. The optimistic and pessimistic locking from the previous article still applies to rows with extra state. For the username itself, the unique index is simpler and faster than any application-level lock.
There is a second concurrency concern the previous article never had to face: not every Bloom filter implementation is thread-safe for concurrent writes. If the filter lives in application memory, writes need synchronization or a thread-safe variant. If it lives in Redis, commands execute atomically on the server, one more reason to take the Redis path.
Performance Considerations
You can shard the database by user id or username hash. The filter stays whole, it only answers existence, and 1.2 GB is small enough for every application node to keep a copy.
The Bloom filter has no delete, so a shrinking list eventually needs a rebuild. A rebuild is not a config change: you replay the current set, load the new filter, switch traffic, and watch the false positive rate for a while.
When insert still fails after the maximum number of kicks, the Cuckoo filter is full. Redis’s CF.RESERVE supports expansion parameters, and production implementations grow the table instead of failing the request.
The availability check must be synchronous. Downstream work like confirmation emails or analytics can go into a queue.
Which Filter Do You Pick
Answer one question first: will the list delete entries?
No, use a Bloom filter. At typical false positive rates it is simpler and smaller, with a mature ecosystem: Guava and Redis ship it, most databases do too. One-billion-username checks are its standard use case.
Yes, then look at how often and how much. If deletions are sparse and the list can be rebuilt, stay with Bloom plus periodic rebuilds. With frequent deletions at scale, the rebuild cost becomes unbearable, use the Cuckoo filter there.
DimensionBloom FilterCuckoo FilterBits per element, 1% FPR~9.6~10.5Bits per element, ~0.2% FPR~13~12.5DeletionnoyesInsert can failnoyes, needs expansionLoad factorn/a~95%Java ecosystemGuava, matureno Guava-level defaultRedis supportBF.* commandsCF.* commands
The Cuckoo filter costs more to implement and adds an insert-failure path. That cost is only justified when deletion is a real requirement. Blacklists and device lists qualify. Username availability, where accounts almost never disappear, does not.
References
Fan et al., Cuckoo Filter: Practically Better Than Bloom, ACM CoNEXT 2014
USENIX ;login article with the 12.53 vs 13 bits comparison, https://www.usenix.org/system/files/login/issues/1308_login_online.pdf
ScyllaDB glossary entry on Bloom filters, 9.6 bits per element at 1% FPR, https://www.scylladb.com/glossary/bloom-filter/
Redis Stack documentation for the CF.ADD command, https://redis-stack.io/commands/cf.add/
Guava BloomFilter API documentation, https://guava.dev/releases/31.0-jre/api/docs/com/google/common/hash/BloomFilter.html