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
45 min · senior
senior

You are building a Bloom Filter service for a 50 million daily active user (DAU) startup. The system must support fast membership queries with a P99 latency under 200ms, handle encrypted data for privacy compliance, and allow configurable false positive rates per use case. The Bloom Filter will be used in multiple microservices for caching and deduplication. The system should be horizontally scalable and fault tolerant.

Constraints
  • P99 query latency < 200ms under 50M DAU load
  • Data must be encrypted at rest and in transit
  • False positive rate configurable between 0.1% and 1%
  • Support offline batch updates to Bloom Filters without downtime
  • Memory usage must be optimized to fit within 64GB RAM per node
📋
Guided Steps
1/5
Step 1
Choosing the Bit Array Storage
How would you store the Bloom Filter's bit array to meet latency and memory constraints?
💡 Hint
Consider in-memory data stores optimized for bit operations and large bit arrays.
Key Decision
Use Redis Bitmaps with Redis Cluster sharding - Redis supports efficient bit-level operations and scales horizontally with cluster mode to handle large bit arrays within 64GB RAM per node.
Interviewer Expectation
Mid: Names Redis Bitmaps for bit operations. Senior: Explains Redis Cluster sharding to horizontally scale bit arrays and avoid single-node memory bottlenecks.
⚠️Common Wrong Answer
Using a relational database to store bits as rows - causes high latency and excessive storage overhead, failing P99 latency and memory constraints.
Step 2
Selecting Hash Functions
Which hash functions would you use for the Bloom Filter and why?
💡 Hint
Look for fast, independent, and uniformly distributed hash functions suitable for high QPS.
Key Decision
Use MurmurHash3 combined with double hashing technique - MurmurHash3 is fast and non-cryptographic, and double hashing reduces the number of hash computations while maintaining independence.
Interviewer Expectation
Mid: Mentions MurmurHash3 for speed. Senior: Explains double hashing reduces CPU overhead and maintains uniform bit distribution critical for false positive rate guarantees.
⚠️Common Wrong Answer
Using cryptographic hashes like SHA-256 - too slow for 50M DAU and increases latency beyond 200ms P99.
Step 3
Configuring False Positive Rate
How do you design the system to support configurable false positive rates between 0.1% and 1%?
💡 Hint
Recall the relationship between bit array size, number of hash functions, and false positive rate.
Key Decision
Dynamically calculate bit array size and number of hash functions per filter using the formula m = -(n * ln p) / (ln 2)^2 and k = (m/n) * ln 2, where n is expected elements and p is false positive rate, then allocate Redis bitmaps accordingly.
Interviewer Expectation
Mid: Knows false positive rate depends on bit array size and hash count. Senior: Explains exact formula usage and how to provision Redis memory per filter to meet SLA.
⚠️Common Wrong Answer
Fixing bit array size and hash count statically - leads to either excessive memory use or unacceptable false positive rates.
Step 4
Handling Encryption Requirements
How would you ensure data encryption at rest and in transit for the Bloom Filter bit arrays and queries?
💡 Hint
Consider encryption capabilities of storage and network layers, and impact on latency.
Key Decision
Enable TLS for all Redis client-server communication and use Redis Enterprise with at-rest encryption enabled; encrypt Bloom Filter elements client-side before hashing to protect sensitive data.
Interviewer Expectation
Mid: Mentions TLS for in-transit encryption. Senior: Explains client-side element encryption before hashing to prevent leakage and Redis Enterprise at-rest encryption to meet compliance.
⚠️Common Wrong Answer
Relying only on network-level encryption - risks data exposure in memory or backups, violating compliance.
Step 5
Supporting Offline Batch Updates
How would you implement offline batch updates to Bloom Filters without downtime?
💡 Hint
Think about versioning filters and atomic switch-over strategies.
Key Decision
Maintain two Redis bitmaps per filter (active and standby); build new filter offline in standby bitmap, then atomically switch pointers in Redis using Lua scripts to minimize downtime.
Interviewer Expectation
Mid: Suggests rebuilding filter offline. Senior: Details atomic pointer swap via Redis Lua scripting to ensure zero downtime and consistent queries.
⚠️Common Wrong Answer
Rebuilding filter in-place causing query inconsistencies and downtime during updates.
🔌
API Design Challenge
Sketch 3 core API endpoints for the Bloom Filter service that support adding elements, querying membership, and updating filter parameters.
Hints
  • How does the client add an element to the Bloom Filter?
  • How does the client query if an element is possibly in the set?
  • How does the client update the false positive rate or reset the filter?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use Redis Bitmaps with cluster sharding for bit array storage to meet memory and latency constraints
  • Select MurmurHash3 with double hashing for fast, independent hash functions
  • Calculate bit array size and hash count dynamically based on false positive rate formulas
  • Implement TLS and at-rest encryption with client-side element encryption for data privacy
Good to Have - 30%
  • Use dual bitmap versioning with atomic swaps for offline batch updates without downtime
  • Explain Redis Lua scripting for atomic pointer switching
  • Discuss horizontal scaling strategies for Redis cluster nodes
  • Include monitoring and alerting for false positive rate deviations
Bonus - 10%
  • Propose fallback mechanisms if Redis cluster nodes become unavailable
  • Suggest integration with Kubernetes for automated scaling
  • Describe metrics collection for Bloom Filter hit/miss rates
Anti-patterns to Avoid
Storing bits in relational databases causing high latency and memory overhead - relational DBs store bits inefficiently as rows, leading to slow queries and excessive storage, violating latency and memory constraints.
Using cryptographic hashes like SHA-256 leading to unacceptable CPU latency - cryptographic hashes are computationally expensive, causing query latency to exceed 200ms P99 under 50M DAU load.
Static bit array sizing ignoring false positive rate trade-offs causing memory waste or poor accuracy - fixed sizes either waste memory or fail to meet false positive rate SLAs.
Relying solely on network encryption without at-rest or client-side encryption risking data leaks - network encryption alone leaves data vulnerable in backups or memory, violating compliance.
Rebuilding Bloom Filters in-place causing query inconsistencies and downtime - in-place updates cause inconsistent query results and service interruptions.
Ignoring horizontal scaling leading to single-node bottlenecks and SLA violations - lack of sharding causes memory and CPU bottlenecks, failing latency SLAs.
✅
Model Answer
▼ Reveal

The Bloom Filter system uses Redis Bitmaps with cluster sharding to store bit arrays efficiently and scale horizontally. MurmurHash3 with double hashing provides fast, independent hash functions that maintain uniform bit distribution. The system dynamically calculates bit array size and hash count per filter based on configurable false positive rates using standard Bloom Filter formulas. TLS encrypts data in transit, Redis Enterprise provides at-rest encryption, and client-side element encryption protects sensitive data before hashing. Offline batch updates are supported via dual bitmap versioning with atomic pointer swaps implemented using Redis Lua scripts, ensuring zero downtime. Horizontal scaling of Redis cluster nodes supports 50M DAU query load with P99 latency under 200ms. Monitoring of false positive rates and memory usage triggers scaling or reconfiguration as needed.

Key Decisions
  • Use Redis Bitmaps with Redis Cluster sharding to meet memory and latency constraints for 50M DAU
  • Select MurmurHash3 combined with double hashing to optimize CPU usage and maintain uniform bit distribution
  • Dynamically compute bit array size (m) and number of hash functions (k) per filter using m = -(n * ln p) / (ln 2)^2 and k = (m/n) * ln 2 formulas
  • Enable TLS for all Redis client-server communication and use Redis Enterprise at-rest encryption
  • Encrypt Bloom Filter elements client-side before hashing to protect sensitive data
  • Implement dual bitmap versioning with atomic pointer swaps via Redis Lua scripts for zero-downtime offline updates
  • Horizontally scale Redis cluster nodes to handle 50M DAU query load with P99 latency under 200ms
  • Monitor false positive rates and memory usage per filter to trigger scaling or reconfiguration
  • Redis Bitmaps with Redis Cluster for scalable, memory-efficient bit array storage
  • MurmurHash3 with double hashing to optimize CPU usage and maintain uniform distribution
  • Dynamic calculation of bit array size and hash count using Bloom Filter mathematical formulas
  • TLS encryption for in-transit data and Redis Enterprise at-rest encryption for compliance
  • Client-side encryption of elements before hashing to protect sensitive data
  • Dual bitmap versioning with atomic Lua script swaps for zero-downtime offline updates
  • Horizontal scaling of Redis cluster nodes to handle 50M DAU query load under 200ms P99 latency
  • Monitoring false positive rates and memory usage per filter to trigger scaling or reconfiguration

Practice

(1/5)
1. In an Active-Passive failover system, at step 3 the passive node receives a heartbeat timeout from the active node. What is the passive node's immediate state transition?
easy
A. Passive node continues waiting for active node recovery
B. Passive node promotes itself to active and starts accepting traffic
C. Passive node sends a failback request to active node
D. Passive node shuts down to avoid split-brain

Solution

  1. Step 1: Understand heartbeat role

    Heartbeat timeout signals active node failure, triggering failover.

  2. Step 2: Passive node failover action

    Passive node must promote itself to active to maintain availability and accept traffic.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Heartbeat timeout -> passive promotes to active [check]
Hint: Heartbeat lost -> passive promotes active [check]
Common Mistakes:
2. A global CDN operator needs to prevent a misconfiguration from propagating incorrect BGP routes that could cause widespread internet outages. Which component is primarily responsible for detecting and containing such route leaks?
easy
A. Using a centralized DNS firewall to block suspicious IP prefixes
B. Implementing BGP route filters and prefix limits on edge routers
C. Relying on client-side validation of IP addresses before routing
D. Deploying a distributed cache to store valid routing tables

Solution

  1. Step 1: Identify BGP route filtering role

    BGP route filters and prefix limits on edge routers prevent invalid or excessive route announcements, containing route leaks.

  2. Step 2: Eliminate other options

    DNS firewalls (A) do not control BGP routing; client-side validation (C) is ineffective for routing control; distributed caches (D) do not enforce routing policies.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    BGP route filters contain route leaks at the network edge [check]
Hint: Edge routers enforce BGP filters to block bad routes [check]
Common Mistakes:
3. In a distributed counter system using sharded CRDTs, at Step 4 the Aggregator node merges shard states received from replicas. What is the Aggregator's state immediately after merging two shards with counts 100 and 150?
easy
A. The Aggregator state is the average of the two counts: 125, to smooth spikes
B. The Aggregator state is the maximum of the two counts: 150, to avoid double counting
C. The Aggregator state is the sum: 250, reflecting all increments
D. The Aggregator state resets to zero after merging to avoid stale data

Solution

  1. Step 1: Understand CRDT merge semantics for counters

    Sharded counters merge by summing counts from each shard to reflect total increments without double counting.

  2. Step 2: Apply merge to counts 100 and 150

    Sum is 250, representing combined increments from both shards.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    CRDT counters merge by summing shard values [check]
Hint: CRDT counters merge by summing shard counts [check]
Common Mistakes:
4. You must design a load balancer for a global web app that requires session stickiness and fault tolerance. Which approach is best?
medium
A. Use IP Hash to ensure session stickiness but risk uneven load distribution
B. Use Round Robin to evenly distribute requests without session affinity
C. Use Least Connections with a centralized session store for stickiness
D. Use Weighted Round Robin with weights adjusted dynamically per server health

Solution

  1. Step 1: Identify session stickiness requirement

    Session stickiness requires requests from the same client to reach the same server to maintain session state.

  2. Step 2: Evaluate options for stickiness and fault tolerance

    Round Robin ignores stickiness; Least Connections needs external session store adding complexity; Weighted Round Robin adjusts load but not stickiness. IP Hash provides stickiness by hashing client IP.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    IP Hash ensures session stickiness but may cause uneven load distribution [check]
Hint: IP Hash ensures stickiness but risks uneven load distribution [check]
Common Mistakes:
5. At 10x scale, which component in a Redis Cluster using consistent hashing is most likely to become the first bottleneck, and why?
hard
A. The client-side slot cache, because it grows linearly with cluster size and increases latency
B. The network bandwidth between nodes, due to increased replication traffic
C. The cluster management node, because it handles all slot reassignments centrally
D. The individual Redis nodes, because maintaining many virtual nodes increases CPU overhead

Solution

  1. Step 1: Identify cluster management role

    Cluster management node coordinates slot assignments and node membership changes.

  2. Step 2: Analyze scaling impact

    At 10x scale, centralized management node becomes bottleneck due to coordination overhead (The cluster management node, because it handles all slot reassignments centrally).

  3. Step 3: Eliminate other options

    Network bandwidth (A) and Redis nodes (D) scale better; client slot cache (C) is local and does not cause cluster-wide bottleneck.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Centralized cluster manager -> coordination bottleneck at large scale [check]
Hint: Central cluster manager bottlenecks slot coordination at scale [OK]
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