Bird
Raised Fist0

Bloom Filter Design - Bit Array, Hash Functions, False Positive Rate

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Bloom Filter Design - Bit Array, Hash Functions, False Positive Rate
Design a scalable Bloom Filter system with bit arrays and hash functions ensuring controlled false positive rates
mediumBloom Filters and Probabilistic Data StructuresFreq: medium
Prerequisites:HashingProbabilistic Data Structures
⚙️
Functional Requirements
  • Support insertions of elements into the Bloom Filter with multiple hash functions
  • Support membership queries with sub-100ms P99 latency
  • Allow configurable false positive rate (e.g., ≤1%) based on bit array size and hash count
  • Support periodic reset or aging of the Bloom Filter to handle stale data
  • Expose APIs for bulk insert and query operations
  • Support distributed deployment for high availability and scalability
📊
Non-Functional Requirements
  • Handle 2 billion membership queries per day (~23K QPS read)
  • Write throughput of up to 1 million insertions per second during peak
  • 99.99% availability SLA
  • P99 query latency under 100ms
  • False positive rate configurable and maintained under 1%
❓
Clarifying Questions to Ask
  • What is the expected element cardinality (number of unique elements) to be stored?
  • Is the Bloom Filter expected to be distributed or centralized?
  • What is the acceptable false positive rate threshold?
  • Should the Bloom Filter support deletions or only insertions?
  • What is the retention period or reset frequency for the Bloom Filter data?
  • Are there any constraints on memory or storage for the bit arrays?
Out of Scope
✗ Designing the underlying hash functions themselves (assume cryptographic or murmurhash variants)
✗ Handling false negatives (Bloom Filters inherently do not have false negatives)
✗ Data persistence beyond Bloom Filter bit arrays (no full data storage or retrieval)
✗ Complex user authentication or authorization mechanisms
📌
Assumptions
  • 2 billion membership queries per day (DAU)
  • 40 insertions per user per day
  • 100 bytes per element representation (for hashing input)
  • Retention period of 7 days for Bloom Filter data
⚡
QPS Calculation
write qps2B users × 40 inserts/day ÷ 86400 sec ≈ 925,926 inserts/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M inserts/sec
read qps2B queries/day ÷ 86400 sec ≈ 23,148 queries/sec
💾
Storage Estimate
bit array size per dayFor 1% false positive rate and 925K inserts/sec × 86400 sec ≈ 80B inserts/day, m ≈ 1.44 × n × ln(1/fp) ≈ 1.44 × 80B × ln(100) ≈ 1.44 × 80B × 4.605 ≈ 530B bits ≈ 66.25 GB/day
total storage 7 days66.25 GB × 7 ≈ 463.75 GB
with replicationAssuming 3 replicas for HA: 463.75 GB × 3 ≈ 1.39 TB
🖥️
Server Estimate
bit array storage nodesAssuming each node handles 100 GB storage, need ≈ 14 nodes (1.39 TB / 100 GB)
query processing nodesAssuming each node handles 5K QPS with <100ms latency, need ≈ 5 nodes (23K / 5K)
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client Apps   |
          +-------+--------+
                  | Queries/Insertions
                  v
          +-------+--------+
          |  API Gateway   |
          +-------+--------+
                  |
        +---------+----------+
        |                    |
 +------+-----+        +-----+-------+
 | Write Handler|        | Read Handler|
 +------+-----+        +-----+-------+
        |                    |
        v                    v
 +------+--------------------+-------+
 | Distributed Bit Array Storage (Redis Cluster with Bitmaps) |
 +--------------------------------+--------------------------+
                  |
          +-------+--------+
          |  Hash Function |
          +----------------+
🧩
Components
API Gateway
Entry point for client requests, routes insert and query requests
Why thisNginx with Lua or Envoy proxy supports high QPS routing with low latency and TLS termination
Why notAWS ALB lacks fine-grained routing and custom logic needed for hash-based routing
Write Handler
Processes insert requests, computes hash functions, sets bits in bit arrays
Why thisImplemented in Go for concurrency and low latency; integrates with Redis Cluster bitmaps for atomic bit set
Why notUsing relational DB for writes rejected due to poor write throughput and lack of bit-level operations
Read Handler
Processes membership queries by computing hashes and checking bits in bit arrays
Why thisGo service optimized for parallel bit checks with Redis MGETBIT commands for sub-100ms P99 latency
Why notMemcached rejected as it lacks bit-level operations and atomic multi-bit reads
Distributed Bit Array Storage
Stores the Bloom Filter bit arrays partitioned by hash ranges, supports atomic bit operations
Why thisRedis Cluster with bitmap commands supports efficient bit-level operations, TTL for aging, and horizontal scaling
Why notCassandra rejected due to higher read latency and lack of native bit operations
Hash Function Module
Computes k independent hash functions per element for bit positions
Why thisMurmurHash3 combined with double hashing technique provides fast, uniform distribution with low collision
Why notCryptographic hashes like SHA256 rejected due to higher CPU cost impacting latency
🔄
Data Flow
1
Client Apps → API Gateway
Send insert or query request with element identifier
Requests are load balanced and routed based on operation type
2
API Gateway → Write Handler
Route insert requests for processing
Write Handler computes hash functions for bit positions
3
Write Handler → Distributed Bit Array Storage
Set bits at computed positions atomically in Redis bitmaps
Uses Redis BITSET commands with pipelining for throughput
4
API Gateway → Read Handler
Route membership query requests
Read Handler computes hash functions for bit positions
5
Read Handler → Distributed Bit Array Storage
Check bits at computed positions using Redis BITGET commands
If all bits are set, respond 'possibly present'; else 'definitely not present'
6
Read Handler → Client Apps
Return membership query result
Ensures P99 latency under 100ms

Practice

(1/5)
1. A critical database cluster must failover automatically without data loss or downtime during a primary node crash. Which component is responsible for orchestrating this failover in a distributed SQL database system?
easy
A. Consensus protocol (e.g., Raft) managing leader election and log replication
B. Load balancer redirecting traffic based on health checks
C. Client-side retry logic to reconnect to a new primary node
D. Backup scheduler triggering periodic snapshots for recovery

Solution

  1. Step 1: Identify failover orchestration component

    The consensus protocol like Raft manages leader election and ensures log replication consistency, enabling automatic failover without data loss.

  2. Step 2: Eliminate other options

    Client-side retries (A) handle reconnection but don't orchestrate failover; load balancers (B) redirect traffic but don't manage state; backups (D) aid recovery but not live failover.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Consensus protocol controls leader election and failover [check]
Hint: Consensus protocols manage failover, not clients or load balancers
Common Mistakes:
2. In a system generating KSUIDs, at step 4 the ID generator component appends a random payload after the timestamp. What is the state of the generated ID at this step?
easy
A. The ID is a UUIDv4 embedded inside the KSUID format
B. The ID is fully deterministic and only contains the timestamp
C. The ID contains a timestamp prefix followed by a cryptographically secure random payload
D. The ID is a sequential number incremented per node

Solution

  1. Step 1: Understand KSUID structure at step 4

    KSUIDs combine a 4-byte timestamp prefix with a 16-byte random payload to ensure uniqueness and sortability.

  2. Step 2: Eliminate incorrect states

    Deterministic timestamp only (A) lacks uniqueness; UUIDv4 (C) is unrelated; sequential number (D) is not part of KSUID design.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    KSUID = timestamp + random payload for uniqueness and sortability [check]
Hint: KSUID = timestamp prefix + random payload [check]
Common Mistakes:
3. You need to implement a live news feed with many clients receiving frequent updates but no client-to-server messages. Which technology is best considering scalability and simplicity?
medium
A. Use WebSockets to maintain persistent connections for all clients to push updates.
B. Use Server-Sent Events to push unidirectional updates efficiently with automatic reconnection.
C. Use Long Polling to simulate server push by clients repeatedly requesting updates.
D. Use HTTP/2 server push to send updates without client requests.

Solution

  1. Step 1: Analyze communication pattern

    Live news feed requires unidirectional server-to-client updates with many clients and no client messages.

  2. Step 2: Evaluate technology trade-offs

    Server-Sent Events efficiently support unidirectional streaming with automatic reconnection and lower overhead than WebSockets. WebSockets add complexity and resource usage for no client-to-server messages. Long Polling is less efficient due to repeated HTTP requests. HTTP/2 server push is not widely supported for this use case.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Server-Sent Events optimize unidirectional streaming with scalability [check]
Hint: Unidirectional + many clients -> Server-Sent Events [check]
Common Mistakes:
4. At 10x scale, which component in a WebRTC video calling system is most likely to become the bottleneck first, and why?
hard
A. Media Servers, because transcoding CPU load grows linearly with concurrent calls
B. Signaling Servers, because they maintain stateful WebSocket connections and cannot easily shard sessions
C. STUN/TURN Servers, because NAT traversal requests increase exponentially with users
D. Client devices, because battery and CPU limits prevent scaling user concurrency

Solution

  1. Step 1: Analyze component scalability at 10x load

    Media Servers scale with CPU but can be horizontally scaled; STUN/TURN scale well with stateless UDP; clients are outside system control.

  2. Step 2: Identify Signaling Server bottleneck

    Signaling Servers hold stateful WebSocket connections per user, making sharding and scaling challenging.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Stateful WebSocket connections limit Signaling Server horizontal scaling [check]
Hint: Stateful WebSocket limits Signaling Server scaling first [check]
Common Mistakes:
5. At 10x scale of global traffic, which component in the BGP-based routing infrastructure is most likely to fail first, and why?
hard
A. Edge routers, because their CPU cannot handle the increased packet forwarding rate
B. Route reflectors, because they become overwhelmed maintaining full routing tables and propagating updates
C. Network monitoring systems, because data volume exceeds processing capacity causing delayed alerts
D. Client devices, because they cannot process rapid route changes at scale

Solution

  1. Step 1: Identify bottleneck at scale

    Edge routers handle packet forwarding at line rate; at 10x traffic, their CPU and forwarding ASICs are stressed first.

  2. Step 2: Evaluate other components

    Route reflectors (A) scale better with hierarchical design; monitoring systems (C) can be scaled horizontally; client devices (D) are downstream and less critical for routing stability.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Edge routers' CPU overload causes first failure at 10x traffic [check]
Hint: Edge routers hit CPU limits first at massive 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