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.
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-sizeparent[]) = 800 MB RAM. - ID Interning Map:
200M * ~24 bytes= ~4.8 GB RAM. - Throughput: 100K
union()/sec and 250Kfind()/sec easily run on 1–4 CPU cores in C++/Rust/Go at ~100 ns per operation.
Memory & Throughput Sizing
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.
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.
Super-Node Quarantine Gate
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.
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_sizeThreshold-Aware Union Engine
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.
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.
Snapshot + WAL Recovery
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.
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.
Rolling Epoch Rebuild
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.
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.
Replicated Read-Query Topology
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.
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.
Circuit Breaker & Snapshot Rollback
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: Make the trade-off yourself.
Why is replaying an edge stream from a Kafka offset after a crash safe for DSU state recovery?