nwave-ai/nw-sd-patterns

Core Distributed Systems Patterns

Load Balancing

Problem: single server can't handle all traffic.

Approaches: Round Robin (simple, ignores load) | Weighted Round Robin (accounts for capacity) | Least Connections (fewest active) | IP Hash (session affinity) | Layer 4/transport (IP/port, fast) | Layer 7/application (HTTP-aware, smarter)

Placement: client-to-web | web-to-app | app-to-database

Trade-offs: LB itself is SPOF -- use active-passive pair | session affinity complicates horizontal scaling -- prefer stateless servers | health checks critical

Caching

Problem: repeated DB reads are slow.

Strategies: Cache-aside/lazy loading (app checks cache, fills on miss -- most common) | Write-through (write cache+DB simultaneously) | Write-behind (cache only, async to DB) | Read-through (cache fronts DB transparently)

Cache-aside pattern: Read: cache.get(key) -> hit? return : db.read -> cache.set -> return | Write: db.write -> cache.delete(key)

Eviction: LRU (most common) | LFU (skewed access) | TTL (time-based)

Problems: thundering herd (many misses simultaneously -- use locking/coalescing) | cache penetration (non-existent keys -- Bloom filter or cache null) | cache avalanche (mass expiration -- jittered TTLs) | size cache based on working set, not total data

Database Replication

Master-Slave: all writes to master, reads to replicas | replication lag = eventual consistency | master fails: promote replica

Multi-Master: writes to any node, conflict resolution required | better write availability, much more complex | suitable for multi-region

Trade-offs: sync replication = consistency but higher write latency | async = lower latency but data loss risk on failure

Database Sharding

Problem: single DB can't handle write volume or data size.

Strategies: Hash-based (hash(key) % N -- even but resharding painful) | Range-based (ranges, can have hotspots) | Directory-based (lookup table, flexible but SPOF)

Partition key: must distribute data AND queries evenly | must be in most queries | common: user_id, tenant_id, region

Challenges: resharding (consistent hashing helps) | celebrity/hotspot problem | cross-shard joins (expensive -- denormalize) | referential integrity (enforce in app) | schema changes across all shards

Consistent Hashing

Problem: traditional hash(key) % N remaps almost all keys when N changes.

How: hash output space as ring (0 to 2^32-1) | servers at positions on ring | keys walk clockwise to first server | adding/removing server affects only adjacent keys

Virtual nodes: each physical server gets 100-200 positions | ensures even distribution | handles heterogeneous capacities

Used in: DynamoDB, Cassandra, Discord, Akamai CDN

Message Queues

Problem: tight coupling; spikes overwhelm downstream.

Properties: decoupling | buffering (absorbs spikes) | async processing | guaranteed delivery

Patterns: Point-to-point (one consumer per message) | Pub/Sub (all subscribers get message) | Dead letter queue (failed messages for debugging)

When: email/notification sending | image/video processing | analytics ingestion | cross-service communication | any op where user doesn't need immediate result

Technologies: Kafka (high throughput, log-based, event streaming) | RabbitMQ (flexible routing, task queues) | SQS (managed, AWS) | Redis Streams (lightweight)

Rate Limiting

Problem: protect services from abuse and cascading overload.

| Algorithm | Mechanism | Pros | Cons | |-----------|-----------|------|------| | Token Bucket | tokens refill at fixed rate | allows bursts, simple | memory per user | | Leaking Bucket | queue with fixed processing rate | smooth output | no burst flexibility | | Fixed Window | count per time window | simple | burst at edges | | Sliding Window Log | track each request timestamp | precise | memory-intensive | | Sliding Window Counter | hybrid fixed + weighted | good balance | approximate |

Token Bucket is industry standard (AWS, Stripe, GitHub). Implementation: API gateway or per-service | Redis counters with TTL | return 429 with Retry-After and X-RateLimit headers

CDN

Problem: static content from origin adds latency for distant users.

How: assets cached at edge servers worldwide | DNS routes to nearest edge | cache miss fetches from origin

Push vs Pull: Push (upload to CDN, infrequent changes) | Pull (CDN fetches on first request, simpler)

Invalidation: URL versioning (preferred) | CDN API purge | TTL expiration

Bloom Filters

Problem: quickly check "is X in set?" without storing full set.

How: bit array + k hash functions | insert sets k bits | query checks k bits | false positives possible, false negatives impossible

Used for: cache penetration prevention | duplicate URL detection (crawlers) | spam filtering

Config: 10 bits per element ~ 1% false positive rate | cannot delete (use Counting Bloom Filter)

Unique ID Generation

| Approach | Sortable | Size | Coordination | Throughput | |----------|----------|------|-------------|------------| | UUID v4 | No | 128b | None | Unlimited | | DB auto-inc | Yes | 64b | High | Limited | | Ticket server | Yes | 64b | Medium | Limited | | Snowflake | Yes | 64b | Minimal | Very high |

Snowflake: [1 unused | 41 timestamp | 5 datacenter | 5 machine | 12 sequence] -- ~4M IDs/sec/DC | clock sync via NTP is Achilles heel

Fan-out Strategies

Fan-out on write (push): post immediately written to all followers' feeds | read is instant | expensive for celebrities

Fan-out on read (pull): feed computed at read time | write is fast | read is slow

Hybrid (production): push for normal users | pull for celebrities (>10K followers)

Real-time Communication

Long Polling: server holds request open until data or timeout | simple, resource-intensive

WebSocket: full-duplex persistent | low latency | stateful (complicates LB -- need sticky sessions)

SSE: server pushes over HTTP | unidirectional | auto-reconnect | simpler for notification/feed

Geohashing and Spatial Indexing

Geohash: encodes lat/lon to string, nearby share prefix | precision by length (4=39km, 6=1.2km, 8=38m) | boundary problem: query target + 8 neighbors

Quadtree: recursive subdivision into 4 quadrants | adaptive to density | in-memory, 200M items ~1.7GB

Geohash vs Quadtree: geohash simpler (string prefix), DB-friendly | quadtree adaptive to density, in-memory only

Data Replication Strategies

Single-leader: one primary writes, replicas read | simple but SPOF

Multi-leader: multiple write nodes, conflict resolution | better for multi-DC

Leaderless (Dynamo): any node reads/writes | quorum W+R>N | W=1,R=N fast writes | W=N,R=1 fast reads | W=R=N/2+1 balanced | anti-entropy + read repair

Conflict Resolution

LWW: timestamp-based, simple but lossy | Vector clocks: detect conflicts, app resolves | CRDTs: auto-merge data types | Application-level: present to user (like Git)

CAP Theorem

CP (consistency): reject writes during partition | HBase, MongoDB, Redis Cluster | financial transactions

AP (availability): accept writes, resolve later | Cassandra, DynamoDB, CouchDB | social feeds, shopping carts

Real question: "what happens during network partition?" | most systems need availability for reads, consistency for certain writes | tunable consistency (Cassandra) gives flexibility

Write-Ahead Log (WAL)

Before applying mutation, write to append-only log | acknowledge to client | periodically apply to data structure | on crash: replay from last checkpoint. Used in PostgreSQL, MySQL, Cassandra, Kafka.

Gossip Protocol

Each node maintains member list with heartbeat counters | periodically exchanges state with random peer | propagates in O(log N) rounds. Used for membership, failure detection, config propagation.

Trie (Prefix Tree)

Each node = character, root-to-leaf = string | optimizations: compress single-child chains, cache top results at each node, shard by first character. Used in: search autocomplete, spell checking, IP routing.