Design streaming difference at scale

Q: Design streaming difference at scale

This question evaluates system design and streaming-data engineering competencies, covering membership-check strategies, caching and storage tiers, probabilistic data structures (Bloom filters), normalization and update propagation, fault tolerance, and scalability; it belongs to the System Design domain and tests practical application of distributed architecture patterns alongside conceptual understanding of trade-offs. It is commonly asked to assess an engineer's ability to architect a near-real-time anti-join between a high-throughput event stream and a very large reference set while reasoning about latency, throughput, correctness, state management, and cost-performance trade-offs without implementation details.

Q: How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty System Design question, commonly asked during Onsite rounds at Palo Alto Networks.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Palo Alto Networks during technical interviews.

Question

Design a Near Real-Time Anti-Join: Stream vs. Large Reference List

You are given:

list1: an unbounded, high-throughput event stream of keys (e.g., user IDs, IPs, URLs).
list2: a very large, frequently updated reference set of keys that may not fit in memory on a single machine.

Goal: Emit, with near real-time latency, the events from list1 whose keys are NOT present in list2.

Provide a detailed system design that includes:

1) Architecture

Ingestion: how events and list2 changes enter the system.
Processing: how the anti-join is performed at scale.
Storage: what stores act as source of truth and caches.

2) Membership Checking Strategies

Describe how you would perform membership checks for list2 using:

(a) An in-memory set (when feasible, and how to shard).
(b) A distributed cache (e.g., Redis) with pipelining/batching.
(c) An external database/NoSQL store as the authoritative source.

Explain how you would combine these layers (e.g., L1/L2/L3 lookups) for latency and cost.

3) Bloom Filter Usage

When and why to add a Bloom filter in front of the cache/DB.
How to size it (false-positive rate, memory, number of hashes) and place it (per-partition/global).
How to mitigate false positives (exact fallback, counters vs. rebuilds) and handle deletes.

4) Normalization Consistency

The canonicalization rules (e.g., case folding, trimming, Unicode normalization, formatting, hashing).
How to enforce consistent normalization across producers/consumers and stores.

5) Updates to list2

How list2 is maintained (snapshot + CDC, periodic rebuilds, or streaming updates).
Ordering/consistency between list1 events and list2 updates to avoid correctness gaps.
Handling adds and deletes, cache invalidation, and Bloom filter maintenance.

6) Back-Pressure and Flow Control

How the system reacts when downstream is slow (e.g., bounded queues, asynchronous I/O, scaling).

7) Fault Tolerance and Correctness

Delivery semantics (at-least/at-most/exactly-once) and idempotency strategy.
Recovery for processor, cache, and database failures.

8) Scalability

Partitioning/sharding strategy and state distribution.
Vertical vs. horizontal scaling, hot-key mitigation.

9) SLOs and Cost Trade-offs

Target throughput/latency (e.g., p95/p99) and how you would size hardware.
Memory/compute/network trade-offs for in-memory sets, Bloom filters, Redis, and databases.

Your answer should include a step-by-step data flow, small numeric examples (e.g., Bloom filter sizing), key formulas, and guardrails to validate correctness and performance.