Bird
Raised Fist0

Bloom Filters in Real Systems - Cassandra, Redis, BigTable, Chrome

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/6
Client Application

Sends query for data existence

Client wants to check if a key exists without fetching full data

Protocol:WebSocket with Compression
BeforeClient has key to check, no query sent yet
AfterQuery sent compressed over WebSocket to network layer
Network Layer with Compression

Receives and decompresses query

Prepares query for Redis Cluster with Bloom Filter

Protocol:Internal Redis GET with Bloom Filter check
BeforeCompressed query received from client
AfterDecompressed query forwarded to Redis Cluster
Redis Cluster with Bloom Filter Module

Checks Bloom Filter for key existence

If Bloom Filter says 'no', reply false immediately

Protocol:Redis GET with Bloom Filter check
BeforeQuery received, Bloom Filter loaded in memory
AfterBloom Filter says 'maybe' → Redis GET forwarded to storage
Cassandra / BigTable Storage

Performs actual key lookup

Returns data if key exists or empty if not

Protocol:Storage read
BeforeStorage ready, query received from Redis Cluster
AfterData found or not found returned to Redis Cluster
Redis Cluster with Bloom Filter Module

Returns final existence result to client

Caches positive result, sends response back

Protocol:Redis GET response
BeforeReceived storage lookup result
AfterResult sent back through network layer to client
Bloom Filter Builder Job

Periodically updates Bloom Filters

Reads storage data and rebuilds filters in Redis

Protocol:Batch job with storage read and Redis write
BeforeBloom Filter may be stale
AfterBloom Filter updated with latest keys
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────┐
│   Client Application  │
└─────────────┬─────────┘
              │ WebSocket w/ Compression
              ▼
┌───────────────────────────────┐
│ Network Layer w/ Compression   │
└─────────────┬─────────────────┘
              │ Redis GET w/ Bloom Filter check
              ▼
┌─────────────────────────────────────────┐
│ Redis Cluster w/ Bloom Filter Module    │
│ - Checks Bloom Filter for key existence │
└─────────────┬───────────────────────────┘
              │ If bloom filter says 'maybe', Redis GET
              ▼
┌───────────────────────────────┐
│ Cassandra / BigTable Storage   │
│ - Stores actual data           │
└─────────────┬─────────────────┘
              │ Bloom Filter Builder Job updates filters
              ▼
┌───────────────────────────────┐
│ Bloom Filter Builder Job       │
│ - Builds and updates filters   │
└───────────────────────────────┘
Design Rationale

This architecture uses Bloom Filters in Redis to quickly check if a key might exist before querying the slower Cassandra or BigTable storage. The client sends a compressed query via WebSocket to the network layer, which decompresses and forwards it to Redis. Redis uses its Bloom Filter module to check key existence probabilistically. If the filter says 'no', Redis immediately returns false, avoiding expensive storage reads. If 'maybe', Redis queries the persistent storage. A background Bloom Filter Builder Job periodically updates the filters in Redis by scanning storage data, ensuring freshness. This design reduces storage load and latency by filtering out non-existent keys early.

Primary Focus

✓

Practice

(1/5)
1. A financial application requires that a transaction always leaves the database in a valid state according to business rules after commit. Which component primarily enforces this property?
easy
A. Consistency checks enforcing schema constraints after commit
B. Isolation level settings preventing dirty reads
C. Durability guarantees via write-ahead logging
D. Atomic commit protocol ensuring all-or-nothing transaction completion

Solution

  1. Step 1: Identify Consistency role

    Consistency ensures database state adheres to all defined rules and constraints after transaction commits.

  2. Step 2: Differentiate from other ACID properties

    Atomicity ensures all-or-nothing commit, Isolation controls concurrent access, Durability ensures persistence, but only Consistency enforces business rules.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Consistency enforces schema and business rules post-commit [check]
Hint: Consistency enforces valid state after commit [check]
Common Mistakes:
2. A video upload service must handle millions of concurrent uploads and ensure durability before transcoding. Which component best handles temporary storage and durability of raw uploads before processing?
easy
A. Use an in-memory cache like Redis to store raw uploads temporarily
B. Use a CDN edge cache to hold raw uploads before transcoding
C. Use a distributed object storage system like Amazon S3 for raw video storage
D. Store raw uploads directly in a relational database for strong consistency

Solution

  1. Step 1: Identify durability and scale needs for raw uploads

    Raw uploads require durable, scalable storage that can handle large binary files and high concurrency. Redis (Use an in-memory cache like Redis to store raw uploads temporarily) is in-memory and not durable for large files. Relational DBs (Store raw uploads directly in a relational database for strong consistency) are inefficient for large blobs and scale poorly. CDN edge caches (Use a CDN edge cache to hold raw uploads before transcoding) are for delivery, not upload storage.

  2. Step 2: Recognize object storage suitability

    Distributed object storage like S3 provides durability, scalability, and cost-effective storage for large files, making it ideal for raw uploads before transcoding.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Object storage ensures durable, scalable raw upload storage [check]
Hint: Object storage for durable large file uploads [check]
Common Mistakes:
3. In the failover incident trace, at Step 4 the Database Proxy receives a client query after the primary node crashed. What state does the proxy enter before forwarding the query?
easy
A. Marks the primary as unavailable and routes query to the new leader after election
B. Returns an error to the client without retrying
C. Queues the query indefinitely until the old primary recovers
D. Immediately forwards query to the old primary node, causing timeout

Solution

  1. Step 1: Trace Database Proxy behavior at Step 4

    Upon detecting primary failure, the proxy marks it unavailable and waits for leader election to complete before routing queries to the new leader.

  2. Step 2: Eliminate other options

    Forwarding immediately to old primary (A) causes timeouts; queuing indefinitely (C) stalls clients; returning errors without retry (B) reduces availability.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Proxy reroutes queries only after leader election [check]
Hint: Proxy reroutes only after leader election completes
Common Mistakes:
4. For a high-throughput system requiring SSL termination and HTTP header manipulation, which architecture is more appropriate and why?
medium
A. Use a Reverse Proxy for SSL termination and header manipulation because it operates at the HTTP layer with fine-grained control
B. Use an API Gateway for SSL termination and header manipulation because it is optimized for high throughput
C. Use a Load Balancer for SSL termination and header manipulation because it handles traffic efficiently
D. Use DNS load balancing to distribute SSL termination across multiple servers

Solution

  1. Step 1: Identify component capabilities

    Load Balancers typically operate at transport layer and may support SSL termination but lack detailed HTTP header manipulation; API Gateways add overhead and are less optimized for raw throughput; DNS load balancing does not handle SSL termination.

  2. Step 2: Match requirement to component

    Reverse Proxy operates at HTTP layer, supports SSL termination and header manipulation efficiently, suitable for high throughput.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Reverse Proxy = HTTP layer control + SSL termination [check]
Hint: Reverse Proxy = SSL termination + HTTP header control [check]
Common Mistakes:
5. In an asynchronous messaging system, what exactly breaks if the message queue component is removed?
medium
A. Senders block until recipients acknowledge, causing high latency
B. Messages are duplicated due to lack of deduplication in the queue
C. Messages are delivered immediately but with no ordering guarantees
D. The system silently drops messages without notifying senders

Solution

  1. Step 1: Understand queue's role in message deduplication and buffering

    Queues often provide deduplication and buffering to ensure exactly-once or at-least-once delivery.

  2. Step 2: Consequence of removing the queue

    Without the queue, messages may be duplicated due to lack of deduplication and buffering mechanisms.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Removing queue causes message duplication due to missing deduplication [check]
Hint: No queue means no deduplication, causing duplicates [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