Bird
Raised Fist0

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

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Bloom Filters in Real Systems - Cassandra, Redis, BigTable, Chrome
Design and integration of Bloom filters in large-scale distributed storage and caching systems
mediumBloom Filters and Probabilistic Data StructuresFreq: medium
Prerequisites:Caching BasicsKey-Value StoresProbabilistic Data StructuresDistributed Systems Fundamentals
⚙️
Functional Requirements
  • Support probabilistic membership queries to quickly check if a key exists in storage without disk access
  • Integrate Bloom filters with distributed key-value stores like Cassandra and BigTable to reduce unnecessary disk reads
  • Provide configurable false positive rates to balance memory usage and query accuracy
  • Support incremental updates to Bloom filters as new keys are inserted or deleted
  • Expose Bloom filter query APIs for caching layers like Redis to optimize cache misses
  • Enable efficient serialization and deserialization of Bloom filters for distributed replication
📊
Non-Functional Requirements
  • Handle at least 2 billion daily active users generating 40 key lookups per user per day
  • Achieve 99.99% availability for membership queries with P99 latency under 10ms
  • Support false positive rates below 1% to minimize unnecessary disk reads
  • Bloom filter memory overhead must not exceed 5% of total storage size
  • System must scale linearly with data growth up to 100PB of stored keys
❓
Clarifying Questions to Ask
  • What is the expected key distribution and update frequency in the system?
  • Are Bloom filters used per partition, per SSTable, or globally?
  • What is the acceptable false positive rate and how does it impact memory?
  • How frequently are Bloom filters rebuilt or updated incrementally?
  • Is deletion support required or are keys only appended?
  • What are the latency requirements for membership queries in the critical path?
Out of Scope
✗ Design of the underlying key-value store or database (e.g., Cassandra internals)
✗ Detailed cryptographic security of Bloom filter data
✗ Full-text search or complex query support beyond membership tests
✗ Client-side caching or browser-specific optimizations beyond Chrome's use case
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user performs 40 key lookups per day
  • Average key size is 100 bytes
  • Retention period of 30 days for stored keys
⚡
QPS Calculation
write qps2B users × 40 writes/user/day ÷ 86400 sec/day ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qpsAssuming 2× reads per write: 925,926 × 2 ≈ 1.85M reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention storage8 TB/day × 30 days = 240 TB
with replication240 TB × 3 replicas = 720 TB total storage
🖥️
Server Estimate
cassandra nodesAssuming 1 TB usable per node, 720 nodes needed for storage
redis nodesAssuming 64 GB RAM per Redis node, 5% Bloom filter memory overhead on 240 TB = 12 TB RAM needed, ≈ 188 Redis nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |   Client App   |
          +-------+--------+
                  |
                  v
          +-------+--------+
          |  Redis Cluster |
          | (Bloom Filters)|
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Cassandra /    |
          | BigTable Store |
          +-------+--------+
                  |
                  v
          +-------+--------+
          |  Bloom Filter  |
          |  Builder Job   |
          +----------------+
🧩
Components
Redis Cluster with Bloom Filter Module
Serve fast in-memory Bloom filter membership queries to reduce backend reads
Why thisRedisBloom module supports native Bloom filters with sub-millisecond lookups and TTL for stale data expiration
Why notMemcached lacks native probabilistic data structures and TTL support, requiring manual eviction and higher latency
Cassandra / BigTable Storage
Persistent distributed key-value store holding actual data and SSTables indexed by Bloom filters
Why thisCassandra and BigTable provide scalable, partitioned storage with SSTable files that integrate Bloom filters per file to avoid disk reads
Why notRelational databases like PostgreSQL do not scale linearly at 2.78M writes/sec and have higher disk I/O overhead
Bloom Filter Builder Job
Periodically generate or update Bloom filters from SSTables or key partitions asynchronously
Why thisBatch jobs using Apache Spark or Hadoop efficiently process large SSTables to build accurate Bloom filters offline
Why notReal-time Bloom filter updates on write path would increase write latency and complexity
Client Application
Issue membership queries to Redis Bloom filters before querying Cassandra/BigTable
Why thisClient-side filtering reduces unnecessary backend calls, improving latency and reducing load
Why notDirect queries to storage cause high disk I/O and increased latency
Network Layer with Compression
Compress Bloom filter data during transfer between builder jobs, Redis, and storage nodes
Why thisUsing Snappy or LZ4 compression reduces bandwidth usage for large Bloom filter bitmaps
Why notUncompressed transfers increase network costs and latency at scale
🔄
Data Flow
1
Client App → Redis Cluster
Query Bloom filter for key membership
Fast in-memory check to avoid unnecessary backend reads
2
Redis Cluster → Client App
Return membership result (possible or definitely not present)
False positives possible; false negatives impossible
3
Client App → Cassandra / BigTable
If Bloom filter indicates possible presence, query actual data
Disk read only if Bloom filter positive
4
Bloom Filter Builder Job → Redis Cluster
Update Bloom filters asynchronously with new keys from SSTables
Batch updates reduce write path latency
5
Bloom Filter Builder Job → Cassandra / BigTable
Scan SSTables to generate Bloom filters per partition or file
Offline processing to maintain accuracy

Practice

(1/5)
1. A social media platform needs to store user posts with high write throughput and ensure efficient retrieval by user and timestamp. Which component best handles this workload?
easy
A. A wide-column store like Cassandra with partition keys on user ID
B. A relational database with normalized tables and joins
C. A document store like MongoDB with embedded user posts
D. An in-memory cache like Redis without persistence

Solution

  1. Step 1: Identify write throughput and query pattern

    The system requires high write throughput and efficient retrieval by user and timestamp, which suits wide-column stores that partition data by user ID.

  2. Step 2: Evaluate options against constraints

    Relational DBs struggle with high write throughput and joins; document stores lack efficient range queries by timestamp; Redis lacks durability and is not ideal for large persistent datasets.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Wide-column store partitions by user ID -> high write throughput and efficient user queries [check]
Hint: Partition by user ID for high write and read throughput [check]
Common Mistakes:
2. In a system using Kafka for write-ahead logging to ensure strong consistency, what exactly breaks if Kafka becomes unavailable during a write operation?
medium
A. The system falls back to eventual consistency, causing stale reads temporarily
B. The client's write blocks indefinitely until Kafka recovers, preventing data loss
C. The write is accepted locally but lost permanently if the server crashes before Kafka recovers
D. The system switches to causal consistency mode automatically to maintain availability

Solution

  1. Step 1: Trace failure impact on write path

    Without Kafka, writes accepted locally but not durably logged can be lost if the server crashes before Kafka recovers.

  2. Step 2: Eliminate other options

    The system falls back to eventual consistency, causing stale reads temporarily is incorrect because fallback to eventual consistency is not automatic; The client's write blocks indefinitely until Kafka recovers, preventing data loss is wrong because writes may not block indefinitely; The system switches to causal consistency mode automatically to maintain availability is false as consistency mode does not switch automatically.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Writes accepted locally but lost if server crashes before Kafka recovers [check]
Hint: Without Kafka, local writes risk loss if server crashes [check]
Common Mistakes:
3. For a globally distributed key-value store requiring low write latency and strong consistency, which replication approach is best and why?
medium
A. Single-leader replication with leader in primary region only
B. Asynchronous replication with conflict resolution on reads
C. Synchronous replication with majority quorum writes to all regions
D. Synchronous replication with local quorum writes per region and global reconciliation

Solution

  1. Step 1: Evaluate latency and consistency trade-offs

    Global synchronous quorum to all regions (A) causes high latency; asynchronous (B) sacrifices strong consistency.

  2. Step 2: Consider local quorum with global reconciliation

    Local quorum writes reduce latency while global reconciliation maintains strong consistency.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Local quorum + global reconciliation balances latency and consistency [check]
Hint: Local quorum writes reduce latency, global reconciliation ensures consistency [check]
Common Mistakes:
4. For real-time message delivery to mobile clients with intermittent connectivity, which architecture best balances latency and resource usage?
medium
A. Use gRPC streaming connections from server to mobile clients
B. Use WebSocket connections with heartbeat and fallback to push notifications
C. Use long polling HTTP requests from clients to server
D. Use MQTT protocol with persistent sessions for mobile clients

Solution

  1. Step 1: Evaluate WebSocket vs gRPC streaming for mobile clients

    gRPC streaming is efficient but poorly supported on many mobile platforms; WebSocket is widely supported with heartbeat to detect disconnects.

  2. Step 2: Consider fallback mechanisms

    WebSocket with push notification fallback handles intermittent connectivity better than long polling or MQTT, which have higher overhead or complexity.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    WebSocket + push fallback balances latency and mobile constraints [check]
Hint: WebSocket + push fallback handles mobile connectivity best [check]
Common Mistakes:
5. At 10x traffic scale, which component in a load balanced web service is most likely to fail first, and why?
hard
A. The DNS server, due to increased domain resolution requests
B. The load balancer, because it maintains stateful TCP connections and cannot shard easily
C. The backend servers, because they cannot horizontally scale beyond a fixed number
D. The database, due to increased query volume and connection limits

Solution

  1. Step 1: Analyze component scaling characteristics

    Backend servers (The backend servers, because they cannot horizontally scale beyond a fixed number) typically scale horizontally. DNS servers (The DNS server, due to increased domain resolution requests) are highly distributed and cacheable. Load balancers (The load balancer, because it maintains stateful TCP connections and cannot shard easily) can be scaled with multiple instances and sharding.

  2. Step 2: Identify database bottleneck

    Databases (The database, due to increased query volume and connection limits) often face connection limits and query volume bottlenecks first at large scale, requiring sharding or caching to scale further.

  3. Step 3: Confirm failure mechanism

    Without proper scaling, the database becomes the first component to fail under 10x load due to resource exhaustion.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Database connection limits cause first failure at 10x scale [check]
Hint: Database connection limits break first 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