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

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, which defines a simple contract for existence checks:

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

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:

import me.ahoo.cache.filter.BloomKeyFilter

val keyFilter = BloomKeyFilter(bloom)

Configuring CoherentCacheConfiguration

Inject the filter into your cache configuration via CoherentCacheConfiguration.kt:

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

@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, 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 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.

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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}