Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Dynamic Network Connectivity &
Fraud Ring Detector with Union-Find.

Partition link events into an idempotent WAL feeding stateful DSU engine shards with periodic RocksDB snapshots and bounded-window edge expiry.
Start the journey7 stages
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

Design a real-time fraud-ring detection and dynamic network connectivity service ingesting 100K account-link events/sec (shared device_id, IP, payment_card) across 200M accounts, supporting < 5 ms p99 `sameRing(accountA, accountB)` queries, component size alerts when a ring exceeds 50 accounts, and crash recovery without losing merged state.

From patterns to decisions.

Partition link events into an idempotent WAL feeding stateful DSU engine shards with periodic RocksDB snapshots and bounded-window edge expiry.

Full walkthrough · 7 stages
01
STAGE 01 · SCALE & MEMORY MATHfoundation

Sizing 200M-Node DSU State & Latency Budgets.

Assume 200M active accounts mapped to dense int32 internal IDs via an ID-interning RocksDB/hash table.

  • DSU Array: 200M * 4 bytes (negative-size parent[]) = 800 MB RAM.
  • ID Interning Map: 200M * ~24 bytes = ~4.8 GB RAM.
  • Throughput: 100K union()/sec and 250K find()/sec easily run on 1–4 CPU cores in C++/Rust/Go at ~100 ns per operation.
STAGE 01 · SCALE & MEMORY MATH

Memory & Throughput Sizing

MemoryIngress / BaselineThroughput SizingScale ConstraintValidation GateBottleneck SignalProduction OutcomeTarget SLAexposes

1.Stage Objective: Calculate exact RAM requirements for 200M nodes and justify single-shard vs. partitioned topologies.

2.Level (Foundation): Assume 200M active accounts mapped to dense `int32` internal IDs via an ID-interning RocksDB/hash table.

3.Operational Invariant: Compact int32 negative-size DSU fits 200M accounts in ~800 MB RAM, leaving headroom for replicas.

Caption: Compact int32 negative-size DSU fits 200M accounts in ~800 MB RAM, leaving headroom for replicas.

02
STAGE 02 · INGESTION & SUPER-NODE GUARDfoundation

Preventing False-Positive Collapses on Shared IPs & Hubs.

A naive union(account, ip) merges every user on an airport Wi-Fi or CGNAT IP into one mega-component. Before emitting a union edge for an attribute (IP, device, card), enforce a degree cap (e.g., max 20 accounts per IP per 24h) using a Redis/HyperLogLog or Count-Min Sketch gate.

Attributes exceeding the threshold are quarantined as super_node signals rather than hard DSU edges.

STAGE 02 · INGESTION & SUPER-NODE GUARD

Super-Node Quarantine Gate

Super-NodeQuarantine GaInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

1.Stage Objective: Block high-cardinality shared attributes from merging unrelated users into a single giant component.

2.Level (Foundation): A naive `union(account, ip)` merges every user on an airport Wi-Fi or CGNAT IP into one mega-component. Before emitting a union edge for an

3.Operational Invariant: Filtering high-degree public IPs before DSU ingestion prevents catastrophic component collapse.

Caption: Filtering high-degree public IPs before DSU ingestion prevents catastrophic component collapse.

03
STAGE 03 · CORE DSU ENGINEintermediate

Thread-Safe Sharded Engine with Threshold Alerting.

On every union(a, b) that merges two distinct components whose combined size crosses ALERT_THRESHOLD = 50, emit an asynchronous alert event to the Risk Sink.

class FraudRingDSU:
    def __init__(self, capacity: int, alert_threshold: int = 50) -> None:
        self.parent = [-1] * capacity
        self.alert_threshold = alert_threshold

    def find(self, x: int) -> int:
        if not (0 <= x < len(self.parent)):
            raise ValueError('Invalid account ID')
        root = x
        while self.parent[root] >= 0:
            root = self.parent[root]
        while x != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union_and_check(self, a: int, b: int) -> tuple[bool, int]:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False, -self.parent[ra]
        if self.parent[ra] > self.parent[rb]:
            ra, rb = rb, ra
        prev_a, prev_b = -self.parent[ra], -self.parent[rb]
        self.parent[ra] += self.parent[rb]
        self.parent[rb] = ra
        new_size = -self.parent[ra]
        crossed = (prev_a < self.alert_threshold and prev_b < self.alert_threshold and new_size >= self.alert_threshold)
        return crossed, new_size
STAGE 03 · CORE DSU ENGINE

Threshold-Aware Union Engine

Threshold-AwareUnion EnValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

1.Stage Objective: Implement deterministic union-by-size with threshold callbacks and bounded input validation.

2.Level (Intermediate): On every `union(a, b)` that merges two distinct components whose combined size crosses `ALERT_THRESHOLD = 50`, emit an asynchronous alert ev

3.Operational Invariant: Negative-size union detects exact ring-size threshold crossings in O(alpha(N)) without extra lookups.

Caption: Negative-size union detects exact ring-size threshold crossings in O(alpha(N)) without extra lookups.

04
STAGE 04 · CRASH RECOVERYintermediate

Idempotent WAL Replay & Non-Blocking Snapshots.

Because union(a, b) is commutative and associative, replaying duplicate WAL records after a crash is naturally idempotent! Every 60 seconds, fork/copy-on-write snapshot the parent[] array + Kafka offset to object storage (S3/GCS).

On restart, mmap the latest 800 MB snapshot in < 1 second and replay only the tail WAL from the recorded offset.

STAGE 04 · CRASH RECOVERY

Snapshot + WAL Recovery

Snapshot + WALRecoveryHot PathCore EnginePartition / IndexGuard & VerifyLatency / RAM BoundProduction OutcomeScaled Statebounds

1.Stage Objective: Recover 200M-node in-memory DSU state in seconds after a process crash.

2.Level (Intermediate): Because `union(a, b)` is commutative and associative, replaying duplicate WAL records after a crash is naturally idempotent! Every 60 second

3.Operational Invariant: Commutative union semantics allow fast snapshot mmap + tail WAL replay with zero data loss.

Caption: Commutative union semantics allow fast snapshot mmap + tail WAL replay with zero data loss.

05
STAGE 05 · HANDLING EDGE EXPIRYadvanced

Rolling Epoch DSU for 30-Day Sliding Windows.

Instead of deleting edges online, maintain daily or weekly DSU epochs (or a background shadow-rebuild job over the trailing 30-day edge log). At midnight UTC, promote the freshly built 30-day DSU snapshot atomically via pointer swap.

Queries read the active immutable-horizon snapshot + live delta ring buffer.

STAGE 05 · HANDLING EDGE EXPIRY

Rolling Epoch Rebuild

Rolling EpochRebuildFault TriggerCore EngineIsolation BoundaryGuard & VerifyFallback / QuarantineProduction OutcomeProtected Pathisolates

1.Stage Objective: Expire stale device/IP links without implementing complex dynamic link-cut trees.

2.Level (Advanced): Instead of deleting edges online, maintain daily or weekly DSU epochs (or a background shadow-rebuild job over the trailing 30-day edge log)

3.Operational Invariant: Periodic background rebuilds over a 30-day edge window cleanly expire stale links.

Caption: Periodic background rebuilds over a 30-day edge window cleanly expire stale links.

06
STAGE 06 · READ SCALINGadvanced

Read Replicas & Cross-Shard Federation.

Replicate the Kafka edge stream to N stateless-recovery read replicas. Each replica maintains an identical in-memory DSU and serves sameRing(A, B) locally in < 1 ms.

If graph size outgrows single-node RAM, shard by region/tenant or run a two-tier architecture: local shard DSU + global cross-shard boundary-edge DSU.

STAGE 06 · READ SCALING

Replicated Read-Query Topology

ReplicatedRead-Query ToCheckpoint / LogCore EngineReplay / SyncGuard & VerifyConsistency GateProduction OutcomeRecovered Stateverifies

1.Stage Objective: Scale `sameRing(A, B)` to 250K+ QPS with < 5 ms p99 latency.

2.Level (Advanced): Replicate the Kafka edge stream to N stateless-recovery read replicas. Each replica maintains an identical in-memory DSU and serves `sameRin

3.Operational Invariant: Streaming WAL replication to read replicas scales connectivity queries linearly.

Caption: Streaming WAL replication to read replicas scales connectivity queries linearly.

07
STAGE 07 · OBSERVABILITY & FAILURE MODESadvanced

Monitoring Giant-Component Drift & Replication Lag.

Track max_component_size, p99_find_hops, super_node_quarantine_rate, and wal_consumer_lag_ms. If max_component_size spikes suddenly (e.g., > 100K accounts), trigger an automatic circuit breaker that pauses ingestion from the offending attribute source and rolls back to the previous 60-second snapshot.

STAGE 07 · OBSERVABILITY & FAILURE MODES

Circuit Breaker & Snapshot Rollback

Circuit BreakerTelemetry SignalSnapshot RollbackSLO ThresholdValidation GateCircuit BreakerProduction OutcomeSafe Degradationtrips

1.Stage Objective: Detect silent graph collapse and stale read replicas before fraud checks degrade.

2.Level (Advanced): Track `max_component_size`, `p99_find_hops`, `super_node_quarantine_rate`, and `wal_consumer_lag_ms`. If `max_component_size` spikes suddenl

3.Operational Invariant: Monitoring max component size catches super-node collapses and triggers automatic snapshot rollback.

Caption: Monitoring max component size catches super-node collapses and triggers automatic snapshot rollback.

Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why is replaying an edge stream from a Kafka offset after a crash safe for DSU state recovery?

Recommended Learning Flow