Bird
Raised Fist0

Why Bloom Filters and What Exact Lookup Cannot Afford at Scale

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Why Bloom Filters and What Exact Lookup Cannot Afford at Scale
Understanding the necessity of Bloom Filters for scalable membership queries and the limitations of exact lookups at massive scale
mediumBloom Filters and Probabilistic Data StructuresFreq: medium
Prerequisites:HashingProbabilistic Data Structures
⚙️
Functional Requirements
  • Support membership queries to check if an element exists in a large dataset with minimal latency
  • Provide a probabilistic answer with zero false negatives and configurable false positive rate
  • Support high QPS reads (lookup queries) with sub-10ms latency at 99th percentile
  • Allow periodic updates/inserts to the membership data structure without downtime
  • Integrate with downstream systems to avoid expensive exact lookups when Bloom Filter returns negative
  • Expose metrics for false positive rate and filter saturation monitoring
📊
Non-Functional Requirements
  • System must handle 2 billion daily active users generating 40 membership queries per user per day
  • End-to-end lookup latency must be under 100ms P99
  • System availability must be 99.99% to support critical membership checks
  • Storage overhead for membership data structure must be under 10% of raw data size
  • False positive rate must be configurable and kept below 1%
❓
Clarifying Questions to Ask
  • What is the acceptable false positive rate for the Bloom Filter?
  • What is the expected size of the dataset for membership queries?
  • Are membership queries read-heavy or write-heavy?
  • What is the latency SLA for membership queries?
  • Is the membership data static or frequently updated?
  • What is the fallback mechanism when Bloom Filter returns positive?
Out of Scope
✗ Design of the exact data store for membership data (e.g., Cassandra schema)
✗ Handling of write-heavy workloads or bulk ingestion pipelines
✗ Security and encryption of membership data
✗ Complex query patterns beyond membership (e.g., range queries)
📌
Assumptions
  • 2 billion DAU
  • 40 membership queries per user per day
  • 100 bytes per membership record
  • Retention period of 30 days
⚡
QPS Calculation
write qps2B users × 40 queries/user/day / 86400 seconds ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qpsSame as write_qps since each query is a read: 925,926 reads/sec
💾
Storage Estimate
daily storage2B users × 40 queries × 100 bytes = 8 TB/day
retention storage8 TB/day × 30 days = 240 TB
with replication240 TB × 3 replicas = 720 TB total storage
🖥️
Server Estimate
bloom filter serversAssuming 1 Bloom Filter server handles 50K QPS with <10ms latency, need 925,926 / 50,000 ≈ 19 servers
storage nodesAssuming Cassandra nodes with 4 TB usable storage each, need 720 TB / 4 TB = 180 nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          | Client Request |
          +-------+--------+
                  |
                  v
          +-------+--------+
          |  API Gateway   |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Bloom Filter   |
          | Service (Redis)|
          +-------+--------+
           /             \
          /               \
         v                 v
  Negative Response   Positive Response
         |                 |
         |                 v
         |         +-------+--------+
         |         | Exact Lookup   |
         |         | (Cassandra)    |
         |         +-------+--------+
         |                 |
         |                 v
         |         +-------+--------+
         |         | Response to    |
         |         | API Gateway    |
         |         +-------+--------+
         |                 |
         +-----------------+
                  |
                  v
          +-------+--------+
          | Client Response|
          +----------------+
🧩
Components
API Gateway
Receives membership query requests and routes them to Bloom Filter service
Why thisNginx with Lua scripting for low-latency routing and rate limiting at 1M+ QPS
Why notAWS API Gateway has higher latency and cost at 1M QPS scale
Bloom Filter Service
Performs probabilistic membership checks with sub-millisecond latency
Why thisRedis with RedisBloom module supports efficient Bloom Filter operations and TTL management
Why notMemcached lacks native Bloom Filter support and TTL management
Exact Lookup Store
Stores full membership data for exact verification on Bloom Filter positives
Why thisApache Cassandra provides linear write scalability and tunable consistency for 3M+ writes/sec
Why notPostgreSQL cannot handle 3M writes/sec due to B-tree write amplification and manual sharding complexity
Monitoring & Metrics
Collects false positive rates, latency, and saturation metrics for Bloom Filter and exact lookup
Why thisPrometheus + Grafana provide real-time monitoring with alerting on SLA breaches
Why notCloudWatch has higher latency and less flexibility for custom metrics
Data Ingestion Pipeline
Feeds membership data updates into Bloom Filter and Cassandra asynchronously
Why thisApache Kafka supports high-throughput, ordered, durable event streaming for 3M+ writes/sec
Why notRabbitMQ does not scale linearly beyond 1M messages/sec and has higher latency
🔄
Data Flow
1
Client → API Gateway
Send membership query request
Client queries if element exists
2
API Gateway → Bloom Filter Service
Forward query to Bloom Filter
Bloom Filter returns probable membership
3
Bloom Filter Service → API Gateway
Return negative if Bloom Filter says no
No false negatives, so safe to reject
4
Bloom Filter Service → Exact Lookup Store
If Bloom Filter positive, query exact store
Confirm membership to avoid false positives
5
Exact Lookup Store → API Gateway
Return exact membership result
Final authoritative answer
6
API Gateway → Client
Send membership query response
Client receives final membership status

Practice

(1/5)
1. In an Elasticsearch query flow, at Step 4 the Coordinating Node receives partial results from all shards. What does the Coordinating Node do at this step before returning the final response?
easy
A. It merges and sorts the partial results from shards to produce a unified response
B. It forwards the query to the Master Node for final aggregation
C. It writes the query results to a temporary index for caching
D. It directly queries the replica shards again to verify consistency

Solution

  1. Step 1: Understand Coordinating Node role at Step 4

    The Coordinating Node collects partial results from primary and replica shards and merges them.

  2. Step 2: Eliminate incorrect actions

    Master Node does not aggregate query results; caching is handled elsewhere; querying replicas again is unnecessary for consistency at this stage.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Coordinating Node merges and sorts shard results [check]
Hint: Coordinating Node merges shard results before response [check]
Common Mistakes:
2. For a system with frequent feature toggles and multiple teams deploying daily, which approach best balances deployment speed and risk mitigation?
medium
A. Rely solely on Canary deployments without feature flags
B. Use Blue-Green deployment exclusively for all releases
C. Combine Feature Flags for gradual feature exposure with Canary deployments for version rollout
D. Use Rolling deployments with manual rollback procedures

Solution

  1. Step 1: Identify constraints

    Frequent deployments and multiple teams require fast, low-risk releases.

  2. Step 2: Evaluate options

    Blue-Green alone is heavy for frequent deploys; Canary alone lacks feature granularity; Rolling with manual rollback is slow and risky.

  3. Step 3: Combine Feature Flags and Canary

    Feature Flags enable gradual feature exposure; Canary controls version rollout risk.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Feature Flags + Canary balance speed and risk for frequent deploys [check]
Hint: Feature Flags + Canary = fast, safe multi-team deploys [OK]
Common Mistakes:
3. For a video calling system targeting mobile clients with intermittent connectivity, which architecture best balances latency and reliability for media delivery?
medium
A. Use a multipoint control unit (MCU) media server that mixes all streams into one
B. Use a fully peer-to-peer WebRTC connection with no media server relay
C. Use a selective forwarding unit (SFU) media server to relay streams only when needed
D. Use HTTP Live Streaming (HLS) for media delivery to ensure reliability

Solution

  1. Step 1: Evaluate architectures for mobile intermittent connectivity

    Pure peer-to-peer (A) suffers from connectivity issues; MCU (C) adds latency and CPU overhead; HLS (D) is high latency and not real-time.

  2. Step 2: SFU (B) relays streams selectively, reducing latency and handling network variability well.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    SFU balances latency and reliability for mobile intermittent networks [check]
Hint: SFU relays selectively, best for mobile intermittent connectivity [check]
Common Mistakes:
4. For a system requiring minimal key remapping and uniform load distribution when nodes are frequently added or removed, which approach is best?
medium
A. Use rendezvous hashing without virtual nodes
B. Use modulo hashing with a fixed number of partitions per node
C. Use a centralized directory that reassigns keys on every node change
D. Use consistent hashing with virtual nodes and assign multiple tokens per physical node

Solution

  1. Step 1: Evaluate modulo hashing with fixed partitions

    Modulo hashing causes large remapping on node changes, poor for frequent changes.

  2. Step 2: Compare consistent hashing with virtual nodes

    Virtual nodes spread load evenly and reduce remapping, ideal for frequent node changes.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Virtual nodes in consistent hashing balance load and minimize remapping [check]
Hint: Virtual nodes smooth load and reduce remapping on node changes [check]
Common Mistakes:
5. At 10x scale of concurrent users, which component in a typeahead autocomplete system using Elasticsearch and Trie is most likely to become the bottleneck first, and why?
hard
A. The Trie servers, because in-memory Tries are stateful and cannot be easily sharded or distributed across nodes
B. The client-side UI, because rendering large autocomplete result sets slows down user experience
C. The prefix hash map, because storing all prefixes for billions of entries exceeds memory limits quickly
D. The Elasticsearch cluster, because fuzzy queries require heavy CPU and memory, causing query latency spikes

Solution

  1. Step 1: Analyze statefulness and scalability

    Trie servers hold large in-memory state and are difficult to shard due to pointer-based node structures, limiting horizontal scaling.

  2. Step 2: Compare other components

    Elasticsearch scales horizontally with shards; prefix hash map can be partitioned or replaced; client UI is less likely the first bottleneck at backend scale.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Trie statefulness limits sharding -> bottleneck at scale [check]
Hint: Trie stateful, hard to shard -> first bottleneck at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard