# How to Use Bloom Filter for Key Filtering to Reduce Cache Miss Stampede in CoCache

> Employ CoCache and Guava's Bloom Filter to efficiently filter non-existent keys, preventing backend overload and cache miss stampedes.

- Repository: [Ahoo Wang/cocache](https://github.com/ahoo-wang/cocache)
- Tags: how-to-guide
- Published: 2026-02-23

---

**Use CoCache's `KeyFilter` interface backed by Guava's `BloomFilter` via `BloomKeyFilter` to short-circuit lookups for non-existent keys, preventing backend overload from cache-miss stampedes.**

CoCache (ahoo-wang/cocache) provides a built-in **key-filter** mechanism that acts as a lightweight gatekeeper before expensive cache or database lookups. By implementing a Bloom filter for key filtering, you can eliminate unnecessary backend traffic caused by concurrent requests for keys that definitively do not exist in your system.

## Understanding the Key Filter Interface

The core abstraction resides in [`me/ahoo/cache/KeyFilter.kt`](https://github.com/ahoo-wang/cocache/blob/main/me/ahoo/cache/KeyFilter.kt), which defines a simple contract for existence checks:

```kotlin
interface KeyFilter<K> {
    fun notExist(key: K): Boolean
}

```

When `notExist()` returns `true`, the cache implementation immediately returns a missing-guard value without querying the distributed cache (L1) or the underlying data source. This check occurs in [`DefaultCoherentCache.kt`](https://github.com/ahoo-wang/cocache/blob/main/DefaultCoherentCache.kt) within the `getL2Cache` method, ensuring the filter acts as the first line of defense against cache-miss stampedes.

## Implementing Bloom Filter for Key Filtering

The concrete implementation `BloomKeyFilter` in [`me/ahoo/cache/filter/BloomKeyFilter.kt`](https://github.com/ahoo-wang/cocache/blob/main/me/ahoo/cache/filter/BloomKeyFilter.kt) wraps Guava's `BloomFilter<String>` to provide probabilistic key existence testing.

### Creating the Guava Bloom Filter

First, instantiate a Guava Bloom filter with your expected insert count and acceptable false-positive probability:

```kotlin
import com.google.common.hash.BloomFilter
import java.nio.charset.Charset

// Expected 10,000 keys with 1% false-positive rate
val bloom = BloomFilter.create<String>(
    { from, into -> into.putString(from, Charset.defaultCharset()) },
    10_000,
    0.01
)

// Populate with known existing keys
bloom.put("user:123")
bloom.put("order:987")

```

### Wrapping with BloomKeyFilter

Wrap the Guava filter in CoCache's `BloomKeyFilter` implementation:

```kotlin
import me.ahoo.cache.filter.BloomKeyFilter

val keyFilter = BloomKeyFilter(bloom)

```

### Configuring CoherentCacheConfiguration

Inject the filter into your cache configuration via [`CoherentCacheConfiguration.kt`](https://github.com/ahoo-wang/cocache/blob/main/CoherentCacheConfiguration.kt):

```kotlin
import me.ahoo.cache.consistency.CoherentCacheConfiguration
import me.ahoo.cache.consistency.DefaultCoherentCache

val config = CoherentCacheConfiguration<String, MyValue>(
    cacheName = "myCache",
    clientId = "instance-1",
    keyConverter = KeyConverter.default(),
    distributedCache = myDistributedCache,
    clientSideCache = myClientSideCache,
    cacheSource = CacheSource.noOp(),
    keyFilter = BloomKeyFilter(bloom)  // Stampede prevention
)

val coherentCache = DefaultCoherentCache(config, myCacheEvictedEventBus)

```

Now, any call to `coherentCache.getCache("non-existent-key")` will be intercepted by the Bloom filter. If the key is definitively not present, the system returns `DefaultCacheValue.missingGuard` immediately, bypassing the distributed cache and database entirely.

## How DefaultCoherentCache Prevents Stampede

The stampede protection logic lives in [`DefaultCoherentCache.kt`](https://github.com/ahoo-wang/cocache/blob/main/DefaultCoherentCache.kt). When retrieving a value, the cache executes the following flow:

1. **Check L2 (client-side) cache** - if miss, proceed
2. **Query Bloom filter** - calls `keyFilter.notExist(cacheKey)`
3. **Short-circuit if absent** - if `true`, returns missing guard instantly
4. **Proceed to L1/L0** - if `false` (possible existence), queries distributed cache or data source

This mechanism ensures that a flood of requests for the same non-existent key—perhaps from a cache invalidation event or malicious traffic—never reaches your backend infrastructure. The Bloom filter acts as a probabilistic set that fits in memory, offering O(1) lookup times regardless of your data set size.

## Spring Boot Auto-Configuration

If you use the CoCache Spring Boot starter, wire the Bloom filter through dependency injection:

```kotlin
@Configuration
class CacheConfig {
    @Bean
    fun bloomFilter(): BloomFilter<String> = BloomFilter.create(
        { s, into -> into.putString(s, Charset.defaultCharset()) },
        20_000,
        0.005
    )

    @Bean
    fun bloomKeyFilter(bloom: BloomFilter<String>): BloomKeyFilter = 
        BloomKeyFilter(bloom)
}

```

The starter automatically detects any bean implementing `KeyFilter` and assigns it to `CoherentCacheConfiguration` via the `coCache.keyFilter` property path, eliminating manual configuration boilerplate.

## Summary

- **BloomKeyFilter** implements the `KeyFilter` interface to wrap Guava's probabilistic data structure
- **Configuration injection** occurs through `CoherentCacheConfiguration` where the filter is wired before cache instantiation
- **Stampede prevention** happens in `DefaultCoherentCache.getL2Cache`, which returns missing guards immediately when `notExist()` returns true
- **Memory efficiency** allows billions of keys to be represented in hundreds of megabytes with tunable false-positive rates
- **Spring Boot integration** enables zero-code configuration through bean autowiring

## Frequently Asked Questions

### What is a cache-miss stampede and how does a Bloom filter prevent it?

A cache-miss stampede occurs when a popular key expires or does not exist, causing hundreds of concurrent requests to simultaneously hit your database or upstream service. By placing a Bloom filter in front of your cache layer, requests for keys that definitively do not exist are rejected at the application layer in constant time, preventing backend overload.

### How do I tune the false-positive rate for my Bloom filter?

The false-positive rate is set during `BloomFilter.create()` via the third parameter (e.g., `0.01` for 1%). Lower rates require more memory. According to the implementation in [`BloomKeyFilter.kt`](https://github.com/ahoo-wang/cocache/blob/main/BloomKeyFilter.kt), a false positive only means an unnecessary cache lookup—not incorrect data—so moderate rates (0.5-1%) typically provide the best balance between memory usage and backend protection.

### Can I use a different key-filter implementation instead of BloomKeyFilter?

Yes. The `KeyFilter` interface in [`me/ahoo/cache/KeyFilter.kt`](https://github.com/ahoo-wang/cocache/blob/main/me/ahoo/cache/KeyFilter.kt) is designed for extension. You can implement custom filters using Cuckoo filters, Redis Set lookups, or static hash sets. Simply implement `notExist(key: K): Boolean` and inject your implementation into `CoherentCacheConfiguration` following the same pattern shown in [`BloomKeyFilterTest.kt`](https://github.com/ahoo-wang/cocache/blob/main/BloomKeyFilterTest.kt).

### How do I update the Bloom filter when new keys are added to the database?

The `BloomKeyFilter` wraps a mutable Guava `BloomFilter`, so you can call `put()` on the underlying instance when writing new keys. For distributed consistency across cache instances, consider implementing a write-through pattern that updates the filter before or after database commits, or rebuild the filter periodically from your database snapshot if eventual consistency is acceptable.