Implement a correctness-safe Bloom filter lookup with Amazon ElastiCache for Valkey and Amazon Aurora PostgreSQL

This article demonstrates how to build a correctness-safe three-tier membership lookup system combining Bloom filters, exact-match caching, and Aurora PostgreSQL to achieve sub-millisecond latency while eliminating false positives.

• Bloom filter (Tier 1) acts as a fast-negative gate, rejecting non-members in microseconds with no downstream I/O
• Exact-match cache (Tier 2) serves confirmed hits in sub-millisecond time using ElastiCache for Valkey
• Aurora PostgreSQL (Tier 3) provides the authoritative source of truth with point queries by primary key
• Composite keys encode scoped relationships (e.g., card:token:merchant:ID) enabling single-filter queries without per-scope proliferation
• Bucketed filters distribute across Valkey cluster shards for horizontal scaling with 200 manageable objects instead of millions
• Consistency model uses write-path ordering, recent-writes safety net, and periodic rebuilds to prevent false negatives
• For 95% negative-query workloads at 1% FPR, Bloom filter absorbs 94% of traffic and reduces database load by ~99%
• P50 latency stays below 1ms; P99 in low single-digit milliseconds

The pattern enables high-throughput membership checks with zero false positives by composing fast in-memory tiers with a durable database source of truth, dramatically reducing database load and latency.