Bird
Raised Fist0

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

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/8
API Gateway

Receives client request to add element

Parses request and routes to Write Handler

Protocol:HTTP
BeforeClient request with element data arrives at API Gateway
AfterWrite Handler receives element add request
Write Handler

Requests hash computations for element

Sends element data to Hash Function Module

Protocol:RPC
BeforeWrite Handler has element data but no hash values
AfterHash Function Module receives element for hashing
Hash Function Module

Computes k hash values for element

Returns hash indices to Write Handler

Protocol:RPC
BeforeHash Function Module has element data, no hashes computed
AfterWrite Handler receives k hash indices
Write Handler

Sends bit set requests to Distributed Bit Array Storage

Sets bits at computed hash indices

Protocol:RPC
BeforeWrite Handler has hash indices, bits not set yet
AfterDistributed Bit Array Storage updates bits at indices
API Gateway

Receives client request to check element membership

Routes request to Read Handler

Protocol:HTTP
BeforeClient sends membership check request to API Gateway
AfterRead Handler receives membership check request
Read Handler

Requests hash computations for element

Sends element data to Hash Function Module

Protocol:RPC
BeforeRead Handler has element data but no hash values
AfterHash Function Module receives element for hashing
Hash Function Module

Computes k hash values for element

Returns hash indices to Read Handler

Protocol:RPC
BeforeHash Function Module has element data, no hashes computed
AfterRead Handler receives k hash indices
Read Handler

Queries bits at hash indices from Distributed Bit Array Storage

Checks if all bits are set for membership

Protocol:RPC
BeforeRead Handler has hash indices, bits not checked yet
AfterRead Handler determines membership result
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────┐
│  API Gateway  │
└───────┬───────┘
        │ HTTP Request (Add/Check)
        ▼
┌───────────────┐
│ Write Handler │
└───────┬───────┘
        │ RPC Call (hash requests)
        ▼
┌───────────────────────┐
│ Hash Function Module   │
│ (computes k hashes)   │
└───────┬───────────────┘
        │ RPC Call (bit set/get)
        ▼
┌───────────────────────────────┐
│ Distributed Bit Array Storage  │
│ (bit array shards, durable)   │
└───────┬───────────────────────┘
        │ RPC Response (bit status)
        ▲
        │
┌───────┴───────┐
│ Read Handler  │
└───────┬───────┘
        │ HTTP Response (membership)
        ▼
┌───────────────┐
│  API Gateway  │
└───────────────┘
Design Rationale

This Bloom Filter design uses an API Gateway as the entry point for client requests, routing add and check operations to dedicated Write and Read Handlers. Both handlers delegate hash computations to a centralized Hash Function Module, which returns multiple hash indices per element. The Write Handler sets bits at these indices in the Distributed Bit Array Storage, a durable, sharded bit array store. The Read Handler queries the same storage to verify if all bits are set, indicating probable membership. This vertical flow ensures separation of concerns: API Gateway handles routing, Handlers manage request logic, the Hash Module centralizes hash computations for consistency, and the distributed storage maintains the bit array state. The design balances scalability and accuracy, with the false positive rate controlled by the number of hash functions and bit array size.

Primary Focus

✓

Practice

(1/5)
1. A Pastebin-like service must store millions of short text snippets with automatic expiration after a configurable TTL. Which storage component best handles this requirement efficiently?
easy
A. Use a relational database with periodic batch jobs to delete expired snippets
B. Use a distributed file system to store snippets as files and run a daily cleanup script
C. Use a NoSQL document store without TTL and rely on application logic to filter expired snippets
D. Use a key-value store like Redis with built-in TTL support for automatic expiration

Solution

  1. Step 1: Identify storage with native TTL support

    Redis supports automatic expiration of keys with TTL, avoiding manual cleanup overhead.

  2. Step 2: Evaluate alternatives

    Relational DB with batch jobs (A) adds latency and complexity; file systems (C) lack efficient expiration; NoSQL without TTL (D) requires expensive filtering.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Redis TTL automates expiration, reducing operational complexity [check]
Hint: Use storage with native TTL for automatic expiration [check]
Common Mistakes:
2. For a high-traffic e-commerce site needing to invalidate product pages immediately after price updates, which cache invalidation strategy is best and why?
medium
A. Use surrogate keys to invalidate all related product pages atomically
B. Use client-side cache control headers to force revalidation
C. Use short TTL to ensure freshness but accept higher cache misses
D. Use long TTL with manual purge to minimize cache misses

Solution

  1. Step 1: Identify need for immediate, atomic invalidation

    Price updates require instant invalidation of all related pages to avoid stale data.

  2. Step 2: Evaluate strategies

    Long TTL with manual purge delays invalidation; short TTL causes high cache misses; client-side headers don't guarantee server cache invalidation; surrogate keys enable atomic invalidation of related content.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Surrogate keys enable atomic, immediate invalidation of related cache [check]
Hint: Surrogate keys invalidate related content atomically [check]
Common Mistakes:
3. For a global social media platform with highly skewed user activity, which sharding strategy best balances load while minimizing cross-shard queries?
medium
A. Directory-based sharding to assign hot users to dedicated shards dynamically
B. Hash-based sharding to evenly distribute users regardless of activity
C. Range-based sharding to group users by geographic region
D. Random sharding to avoid hotspots by unpredictable distribution

Solution

  1. Step 1: Analyze skew and query patterns

    Skewed activity causes hotspots; static range or hash sharding can't adapt dynamically.

  2. Step 2: Evaluate strategies

    Directory-based sharding allows dynamic assignment of hot users to dedicated shards, balancing load and reducing cross-shard queries.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Directory-based sharding supports dynamic load balancing [check]
Hint: Directory sharding adapts dynamically to hotspots [check]
Common Mistakes:
4. For a system requiring per-user rate limits with minimal latency, which architecture is better and why?
medium
A. Service-layer counters with no database persistence for simplicity
B. Centralized database counters updated synchronously on every request for accuracy
C. Client-side counters with server verification on every request for trustworthiness
D. Distributed in-memory counters at the API Gateway with periodic async database sync for scalability

Solution

  1. Step 1: Compare latency and scalability

    Synchronous DB updates cause high latency and DB bottlenecks; client-side counters are untrustworthy; service-layer without persistence risks data loss.

  2. Step 2: Evaluate distributed in-memory counters

    API Gateway counters provide low latency and scalability; async DB sync ensures eventual consistency and durability.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Distributed in-memory counters balance latency and scalability [check]
Hint: Async DB sync + in-memory counters = low latency + scalability [check]
Common Mistakes:
5. At 10x scale, which component in a Redis-based centralized rate limiter is most likely to fail first and why?
hard
A. Network bandwidth, because of increased data transfer between servers
B. API servers, because they cannot handle increased request volume
C. Redis server, due to single-threaded command processing becoming a bottleneck
D. Client applications, due to increased latency causing timeouts

Solution

  1. Step 1: Identify Redis command processing model

    Redis processes commands single-threaded, limiting throughput regardless of hardware.

  2. Step 2: Analyze scaling impact

    At 10x scale, Redis becomes the bottleneck as it cannot process atomic increments fast enough.

  3. Step 3: Evaluate other components

    API servers can be scaled horizontally; network and clients are less likely to fail first.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Redis single-threaded processing limits throughput at high scale [check]
Hint: Redis single-threaded limits throughput 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