Bird
Raised Fist0

Why Bloom Filters and What Exact Lookup Cannot Afford at Scale

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

Receives client query for key presence

API Gateway accepts HTTP request with key lookup

Protocol:HTTP
BeforeClient has sent a key lookup request
AfterAPI Gateway forwards request to Bloom Filter Service
Bloom Filter Service

Checks Bloom Filter for key membership

Performs Redis GET to test if key might exist

Protocol:Redis GET
BeforeRequest just arrived at Bloom Filter Service
AfterBloom Filter indicates key is possibly present or definitely absent
Exact Lookup Store

Performs exact key lookup if Bloom Filter positive

Queries database for exact key data if Bloom Filter positive

Protocol:Database Query
BeforeBloom Filter indicated key might exist
AfterExact Lookup Store returns definitive presence or absence
Data Ingestion Pipeline

Processes new data to update Bloom Filter and Exact Store

Consumes Kafka stream to update both stores with fresh data

Protocol:Kafka Stream
BeforeNew data pending ingestion
AfterBloom Filter and Exact Lookup Store updated with latest keys
Monitoring & Metrics

Collects metrics on request latency and error rates

Aggregates telemetry from all components for health monitoring

Protocol:Internal Metrics
BeforeSystem processing requests without aggregated metrics
AfterMonitoring system updated with latest performance data
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────┐
│  API Gateway  │
└───────┬───────┘
        │ HTTP Request
        ▼
┌───────────────────────┐
│ Bloom Filter Service  │
└───────┬───────────────┘
        │ Redis GET (Bloom Filter check)
        ▼
┌───────────────────────┐
│  Exact Lookup Store   │
└───────┬───────────────┘
        │ Database Query (Expensive)
        ▼
┌───────────────────────┐
│ Data Ingestion Pipeline│
└───────┬───────────────┘
        │ Kafka Stream (Updates Bloom & Exact Store)
        ▼
┌───────────────────────┐
│ Monitoring & Metrics  │
└───────────────────────┘
Design Rationale

This architecture uses a Bloom Filter Service as a fast probabilistic pre-check to avoid expensive exact lookups in the Exact Lookup Store. When a client query arrives at the API Gateway, it is routed to the Bloom Filter Service, which uses a Redis GET to quickly determine if the key might exist. If the Bloom Filter returns negative, the system avoids querying the Exact Lookup Store, saving costly database operations at scale. If positive, the Exact Lookup Store performs a definitive query. The Data Ingestion Pipeline continuously updates both the Bloom Filter and Exact Store via Kafka streams to keep data fresh. Monitoring & Metrics collects telemetry from all components to track system health and performance. This design balances speed and accuracy, using Bloom Filters to reduce load on the exact store while ensuring correctness when needed.

Primary Focus

✓

Practice

(1/5)
1. In a Cache Aside pattern, at step 3 the application checks the cache and finds a miss. What happens next at step 4?
easy
A. The application queries the database, then updates the cache with the retrieved data
B. The cache automatically loads data from the database without application intervention
C. The application returns a null response to the user and retries later
D. The cache triggers a background refresh asynchronously and returns stale data

Solution

  1. Step 1: Understand Cache Aside flow

    On cache miss, application queries DB and updates cache explicitly.

  2. Step 2: Eliminate other options

    Cache Aside does not auto-load cache (A); it does not return null or stale data (C, D).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Application loads DB and updates cache on miss [check]
Hint: Cache Aside: app loads DB and updates cache on miss [check]
Common Mistakes:
2. In the DNS query flow, at step 3 the GeoDNS server receives a DNS request from a user in Europe. What does the GeoDNS server do at this step?
easy
A. Returns the IP address of the closest data center based on the user's IP location
B. Forwards the DNS request to the authoritative DNS server without modification
C. Caches the DNS response from the previous query regardless of location
D. Performs a health check on all data centers before responding

Solution

  1. Step 1: Understand GeoDNS behavior at step 3

    GeoDNS inspects the user's IP to determine geographic location and returns the IP of the nearest data center accordingly.

  2. Step 2: Rule out other options

    Forwarding without modification (B) ignores GeoDNS's purpose. Caching regardless of location (C) breaks geographic routing. Health checks (D) are done asynchronously, not per query.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    GeoDNS returns location-based IP at query time [check]
Hint: GeoDNS returns nearest IP based on client IP at query [check]
Common Mistakes:
3. In a multi-CDN request flow, at Step 4 the Global Traffic Manager receives a health check failure from CDN Provider A. What is the immediate action taken by the Global Traffic Manager at this step?
easy
A. It marks CDN Provider A as unhealthy and temporarily stops routing new requests to it
B. It sends a notification to the origin server to stop sending content to CDN Provider A
C. It immediately reroutes all new user requests to CDN Provider B without delay
D. It caches the last successful response from CDN Provider A to serve future requests

Solution

  1. Step 1: Understand Global Traffic Manager health check handling

    Upon receiving a health check failure, the manager marks the CDN as unhealthy to prevent routing new requests to it.

  2. Step 2: Eliminate other options

    Immediate rerouting (A) may cause abrupt traffic shifts without grace. Origin server notifications (C) are not part of traffic management. Caching responses (D) is unrelated to health check handling.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Health check failure -> mark CDN unhealthy, stop routing new requests [check]
Hint: Health check failure -> mark CDN unhealthy, pause routing [OK]
Common Mistakes:
4. You must design a membership filter for a system with extremely high insert rate and limited memory, but false positives must be kept below 1%. Which approach is best?
medium
A. Use multiple independent hash functions with a carefully sized bit array to balance false positive rate and memory
B. Use a single hash function with a large bit array to reduce false positives
C. Use a counting Bloom filter to allow deletions and reduce false positives
D. Use a standard hash set in memory for exact membership with no false positives

Solution

  1. Step 1: Analyze false positive rate constraints

    False positive rate depends on number of hash functions and bit array size; multiple hash functions reduce false positives effectively.

  2. Step 2: Evaluate memory and insert rate trade-offs

    Multiple hash functions with optimized bit array size balance memory use and false positive rate better than single hash or counting filters.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Multiple hashes + sized bit array minimize false positives under memory limits [check]
Hint: Multiple hashes + sized bit array minimize false positives [check]
Common Mistakes:
5. For a high-traffic API with strict memory limits and tolerance for bursty traffic, which rate limiting approach is best and why?
medium
A. Leaky bucket, because it enforces a steady output rate regardless of bursts
B. Sliding window counter, because it tracks exact request times for precise limits
C. Token bucket, because it smooths bursts and uses fixed memory for tokens
D. Fixed window counter, because it uses constant memory and handles bursts at window edges

Solution

  1. Step 1: Analyze memory constraints and burst tolerance

    Sliding window counters require storing timestamps, which grows with request volume, unsuitable for strict memory limits.

  2. Step 2: Fixed window counters use constant memory by counting requests per fixed interval, allowing bursts at window edges but fitting memory constraints

    Token and leaky buckets smooth bursts but require token state management and may not tolerate bursts as well.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Fixed window uses constant memory, tolerates bursts, fits strict memory limits [check]
Hint: Fixed window uses constant memory, sliding window stores timestamps [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