Why CA is impossible: Claiming CA means "consistent and available even during partition" — but by definition a partition means nodes can't communicate. A consistent system that can't communicate must return an error (unavailable). A CA system requires a network with zero partitions — only possible on a single machine.

CP behavior during partition: etcd elects a new leader via Raft and refuses reads/writes from nodes that can't communicate with a quorum. This guarantees linearizability but means partial unavailability.

AP behavior during partition: Cassandra accepts writes on any replica. When the partition heals, last-write-wins (LWW) based on timestamp reconciles conflicts. The client may read stale data during the partition.

PACELC (the real model): Even without partition, there's a trade-off: lower latency or higher consistency. Spanner prioritizes consistency (2PC + TrueTime), adding ~10ms latency. DynamoDB eventual reads save latency vs consistent reads that always hit the leader.

Raft election basics: Nodes start as Followers. If no heartbeat from leader within election timeout (150–300ms), a Follower becomes Candidate and requests votes. A node votes for at most one candidate per term. A candidate that receives majority becomes Leader and begins sending heartbeats.

Fencing tokens: Every leader gets a monotonically increasing token (etcd: lease + revision). Clients include the token in every request. Storage layer rejects requests with stale tokens — prevents a zombie leader from making writes after losing its lease.

ZooKeeper approach: Clients create ephemeral sequential znodes (lock/node_0000001). The node that creates the lowest-numbered znode is the leader. Nodes watch the znode just below theirs — this avoids herd effect (all nodes waking on each deletion).

etcd approach: Use a lease (TTL-bound key). Leader heartbeats to refresh the lease. If leader crashes, lease expires and a new election starts. etcd guarantees linearizable reads via Raft log.

Linearizability (strong): Every operation appears to take effect instantaneously at some point between its invocation and response. Cost: requires coordination (2PC, Raft commit) → higher latency. Used for: financial transactions, inventory deductions, leader election. etcd, CockroachDB, Spanner.

Sequential consistency: Operations appear in order across all processes, but not necessarily in real-time order. Less strict than linearizability. Java volatile gives sequential consistency within a single machine.

Causal consistency: Operations causally related are seen in order by all nodes. Concurrent operations may be seen in different orders. Vector clocks or hybrid logical clocks (HLC) track causality. Used in: comment threading ("replies appear after the comment they reply to"), shopping carts. MongoDB session consistency is causal.

Eventual consistency: Weakest guarantee. Guarantees convergence but not order or timing. DNS updates propagate eventually — you may query a stale IP for minutes. Great for: view counts, likes, recommendations. Cassandra ONE, DynamoDB default.

Lag sources:
1. Write amplification: Primary writes 100K rows/s; replica replays them serially. Mitigate with max_worker_processes and parallel WAL apply (Postgres 14+ parallel logical replication).
2. Long-running queries on replica: A 30-minute analytics query on the replica can cause lag because WAL apply waits for conflicting queries. Set max_standby_streaming_delay = 0 to cancel blocking queries.
3. Network: WAL segments are up to 16MB. High-latency links between AZs cause lag spikes. Monitor pg_stat_replication.sent_lsn - replay_lsn.

Detection: SELECT * FROM pg_stat_replication shows write_lag, flush_lag, replay_lag for each standby. Alert if replay_lag > threshold. Application-level: embed write timestamp in response, replicas report how far behind they are.

Mitigation patterns:
1. Read-your-writes: After write, read from primary for 30s. Or attach write LSN to session and replica checks pg_last_wal_replay_lsn() >= session_lsn.
2. Semi-sync replication: Primary waits for ≥1 replica to flush WAL before acknowledging write (MySQL semi-sync, Postgres synchronous_standby_names).
3. Route by staleness tolerance: User-facing reads → primary. Reporting/analytics → replica.

Write fanout (push model): On post, asynchronously write to every follower's timeline cache (Redis sorted set, score = timestamp). Feed read is O(1) — just ZRANGE. Problem: Kylie Jenner posts → 300M Redis writes. Not feasible.

Read fanout (pull model): On feed read, query followed accounts, fetch their recent posts, merge-sort. Fast for celebrities, terrible for users following 10K accounts — expensive N-way merge at read time.

Hybrid approach (Twitter's actual model):
1. Users with <1M followers → write fanout (push on post)
2. Celebrities (>1M followers) → read fanout (pull their timeline when user opens feed)
3. On feed read: load pre-built timeline from cache + pull from celebrities + merge

Storage: Redis sorted set per user: timeline:{user_id} with score=epoch, value=tweet_id. Keep last 800 tweets (beyond that, cold storage). Tweet content stored separately in a tweet service — timeline only stores IDs.

Replication for feed reads: Timeline reads don't need strong consistency — serve from read replicas. Write to primary when building timelines. ~50ms stale lag is acceptable for a social feed.

Leftmost prefix rule: Index on (user_id, created_at, status) helps: WHERE user_id=5, WHERE user_id=5 AND created_at>X, WHERE user_id=5 AND created_at=X AND status='active'. Does NOT help: WHERE created_at>X (no user_id prefix), WHERE status='active' (not leftmost).

When indexes are skipped:
1. Function on indexed column: WHERE LOWER(email)='x' — create expression index instead: CREATE INDEX ON users(LOWER(email))
2. Leading wildcard: WHERE name LIKE '%smith' — can't use B-tree, use full-text search
3. Implicit cast: WHERE user_id='123' when user_id is INTEGER — cast changes the type, function applied
4. Low selectivity: Boolean column index on a table where 90% of rows have status='active' — planner chooses sequential scan
5. OR conditions: WHERE a=1 OR b=2 — each index can serve one arm; use UNION ALL instead

Covering index: Index includes all columns needed by the query — no heap fetch required. CREATE INDEX ON orders(user_id) INCLUDE (total, created_at). Query SELECT total,created_at FROM orders WHERE user_id=5 is satisfied entirely from the index page.

LSM-Tree write path: Write → MemTable (in-memory sorted tree) → WAL (durability). When MemTable fills, flush to SSTable (immutable sorted file on disk). Background compaction merges and garbage-collects SSTables.

LSM-Tree read path: Check MemTable → L0 SSTables → L1 → L2 (each level has larger, compacted SSTables). Bloom filter per SSTable: probabilistically skip SSTables that don't contain the key. Without bloom filters, worst-case reads check every level.

Write amplification: B-Tree: random writes = many page updates, write amplification ~10x. LSM: sequential writes, compaction causes write amplification ~30x for L1 (10x for each merge level). But LSM writes are sequential — faster on HDDs and more NVMe friendly.

B-Tree wins for: Mixed OLTP (reads and writes), complex queries, range scans, relational workloads. PostgreSQL, MySQL InnoDB.

LSM wins for: Write-heavy (IoT, time-series, audit logs), high write throughput, SSD-optimized workloads. RocksDB, Cassandra, LevelDB, InfluxDB.

Geohash approach: Encode (lat, lng) into a string (e.g., "9q8yy"). Nearby locations share a common prefix. Store driver locations with a Geohash index. Query: search all geohash prefixes covering the 5km radius. Fast B-tree range scan on a string column. Caveats: grid cells at Geohash boundaries are adjacent but don't share a prefix — must check 8 surrounding cells.

PostGIS + GIST index: Store location as GEOGRAPHY(POINT). Create CREATE INDEX ON drivers USING GIST(location). Query: SELECT * FROM drivers WHERE ST_DWithin(location, 'POINT(-122 37)', 5000). GIST index supports circle queries natively. Best accuracy, but requires PostGIS extension.

Redis GEO commands: GEOADD drivers:available lng lat driver_id, GEORADIUS drivers:available -122 37 5 km. Internally uses Geohash stored in a sorted set. O(N+log(N)) with N nearby results. Fast for real-time driver tracking — update location on every GPS ping.

Driver location update design: Drivers send GPS every 5s. Write to Redis (real-time tracking) + async write to Postgres (historical). Matching service reads from Redis. Billing/analytics read from Postgres replicas.

Dirty Read: Txn A reads uncommitted data from Txn B. If B rolls back, A read data that never existed. Prevented at Read Committed+.

Non-repeatable Read: Txn A reads row twice; B commits update in between; A gets different values. Prevented at Repeatable Read+.

Phantom Read: Txn A runs a range query twice; B inserts a new row that matches; A gets different set. Prevented at Serializable. (Postgres Repeatable Read prevents phantoms too — an implementation detail above the SQL standard.)

Write Skew (MVCC-specific): Two transactions both read an overlapping set and make decisions based on it. Classic example: two doctors both see "1 on-call doctor" and both decide to go off-call — now 0 on-call. Prevented only by Serializable (SSI in Postgres).

Postgres defaults: Read Committed (default). Each statement sees a new snapshot. Safe from dirty reads, but prone to non-repeatable reads. For financial transactions: use Repeatable Read or Serializable. Postgres uses SSI (Serializable Snapshot Isolation) — optimistic, detects conflicts at commit time with minimal locking.

Dead tuple lifecycle: UPDATE creates a new row version. The old version's xmax is set to the updating transaction's xid. It becomes a dead tuple once that xid is committed and no active snapshot needs it. VACUUM marks dead tuples as free space, reclaimed for future inserts.

Table bloat: Without VACUUM, dead tuples accumulate. A table that is 100GB logically may be 400GB on disk after many updates. Queries read more pages than necessary — performance degrades. Fix: VACUUM FULL rewrites the table (takes exclusive lock, slow) or pg_squeeze / pg_repack (online).

Transaction ID wraparound: Postgres xid is 32-bit — wraps at ~2.1 billion. When a table's oldest xmin approaches the current xid by 200M (autovacuum_freeze_max_age), Postgres must freeze those tuples (set xmin to FrozenTransactionId=2 — always visible). If it fails to do this, Postgres refuses new connections with: "database is not accepting connections: database age exceeds autovacuum_freeze_max_age." Recovery: enter single-user mode, run VACUUM FREEZE.

autovacuum tuning: autovacuum_vacuum_scale_factor=0.2 (trigger at 20% dead tuples). For high-write tables: lower to 0.01 or use cost-based throttling. Monitor: SELECT relname, n_dead_tup, n_live_tup FROM pg_stat_user_tables ORDER BY n_dead_tup DESC.

Pessimistic locking approach:
BEGIN;
SELECT balance FROM accounts WHERE id=1 FOR UPDATE;
SELECT balance FROM accounts WHERE id=2 FOR UPDATE;
-- check balance >= amount
UPDATE accounts SET balance = balance - amount WHERE id=1;
UPDATE accounts SET balance = balance + amount WHERE id=2;
INSERT INTO transfers (from, to, amount) VALUES (1, 2, 100);
COMMIT;

Critical: Always lock accounts in a consistent order (lower ID first) to prevent deadlocks. FOR UPDATE acquires row-level lock; concurrent transfers to the same accounts wait, not race.

Optimistic locking approach (for low contention):
Add a version column. Read version + balance. Update with WHERE id=1 AND version=read_version. If 0 rows affected → conflict → retry. No locks held between read and write — better throughput when conflicts are rare.

Idempotency key: Client includes idempotency_key (UUID). Store (idempotency_key, result) with a UNIQUE constraint. If the same key is submitted twice (retry after network failure), return the cached result instead of applying a duplicate transfer.

Event sourcing for audit: Never update balances in-place. Append a ledger entry for every transaction. Balance = SUM of all ledger entries. Immutable, auditable, trivially reversible.

Job queue schema:
CREATE TABLE jobs (id BIGSERIAL PRIMARY KEY, status TEXT DEFAULT 'pending', payload JSONB, attempts INT DEFAULT 0, run_at TIMESTAMPTZ DEFAULT NOW(), created_at TIMESTAMPTZ DEFAULT NOW());
CREATE INDEX ON jobs(status, run_at) WHERE status IN ('pending','failed');

Worker claim logic:
BEGIN;
SELECT id, payload FROM jobs
WHERE status = 'pending' AND run_at <= NOW()
ORDER BY run_at
LIMIT 1
FOR UPDATE SKIP LOCKED;
UPDATE jobs SET status='running', attempts=attempts+1 WHERE id=<claimed_id>;
COMMIT;

The SKIP LOCKED ensures each worker atomically claims a unique job. Without SKIP LOCKED, all workers would queue on the first row's lock.

At-least-once delivery: If a worker crashes mid-job, the row stays as 'running'. A reaper job periodically: UPDATE jobs SET status='pending', run_at=NOW()+interval'5m' WHERE status='running' AND updated_at < NOW()-interval'10m' — this re-queues stuck jobs.

Versus Kafka/SQS: Postgres-as-queue works excellently up to ~1000 jobs/s. Beyond that, use a dedicated message broker. Advantages: transactional (enqueue inside business logic txn, no dual-write), no extra infrastructure, easy visibility into queue state.

Acquire: SET lock:resource <token> NX PX 30000 — atomic, returns OK if acquired or nil if held.

Release (Lua CAS):
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else return 0 end
The token check + delete is atomic. Without this, two scenarios break: (a) lock expires, B acquires, A releases B's lock; (b) A finishes, releases, B acquires, A crashes and re-tries release.

Failure modes:
1. GC pause: Process A holds lock, GC pauses for 35s, TTL=30s expires, B acquires lock, GC resumes — A and B both believe they hold the lock. Fix: fencing tokens (a monotonic counter included in every request, storage rejects older tokens).
2. Redis failover: A acquires lock on primary. Primary crashes before replicating to replica. Replica becomes primary — lock is gone. B acquires the same lock. Fix: Redlock algorithm (acquire on 3+ Redis masters, need majority).
3. Clock skew: Redlock relies on TTL being honored consistently across machines. NTP skew can cause early expiry on one node.

When Redis locks are fine: For "advisory" locks where occasional failures are acceptable (preventing duplicate sends, rate limiting). Not for critical mutual exclusion (use Postgres FOR UPDATE or ZooKeeper/etcd ephemeral nodes).

Read path:
L1 (in-process) → L2 (Redis cluster) → L3 (DB replica) — miss at each level populates the level above it (read-through or cache-aside).

Cache key design: product:{product_id}:v{version} or product:{product_id} with TTL. If using version in key: cache is auto-busted on publish — old keys expire naturally. Allows instant invalidation by incrementing version in Redis (atomic, O(1)) without scanning all product keys.

Write invalidation strategies:
1. TTL expiry: Simple, eventual. Cache may serve 5min stale data. Acceptable for many products.
2. Cache-aside invalidation: On product update → DELETE cache key → next read populates fresh. Risk: stampede on hot products (use mutex or stale-while-revalidate).
3. Write-through: Update DB + cache in same transaction. Ensures no stale reads. Doubles write latency.
4. CDC + async invalidation: Debezium captures DB changes → Kafka → cache invalidation workers. Decoupled, scales independently. Sub-second invalidation.

TTL jitter: All 100M products added at launch — without jitter, all expire simultaneously. TTL = base_ttl + random(0, 0.1 * base_ttl). Spreads expiry over time.

Hot key mitigation: Top 100 products by traffic get a longer TTL and proactive refresh (background job refreshes before expiry). Or local L1 with 1s TTL on each app server absorbs spikes.

LRU: Evict the item not accessed for the longest time. Works well for temporal locality (recent data is more likely to be accessed). Weakness: a large sequential scan pollutes the cache with items that won't be accessed again (cache pollution). Redis implements approximate LRU: sample 5 random keys, evict the oldest — saves memory overhead of a true LRU linked list.

LFU: Evict the item accessed the fewest times overall. Better for stable hot sets (a product that was hot last month but not last week would be protected by LFU). Redis allkeys-lfu uses a logarithmic frequency counter (decay over time). Best for: CDN edge caches, recommendation results, stable popular content.

ARC (used in ZFS, some CDNs): Maintains two LRU lists — recently used (T1) and frequently used (T2) — plus ghost entries to adapt the balance. Outperforms both LRU and LFU on mixed workloads without tuning.

Redis eviction policies: noeviction (returns error on OOM), allkeys-lru, volatile-lru (only TTL keys), allkeys-lfu, volatile-lfu, allkeys-random, volatile-ttl (evict soonest-expiring).

Recommendation: General cache → allkeys-lru. Stable hot content → allkeys-lfu. Mixed → use ARC at the CDN level, LRU at Redis level.

Token Bucket in Redis:
Lua script for atomicity:
local tokens = tonumber(redis.call("get", key) or capacity)
local now = tonumber(ARGV[1])
local last = tonumber(redis.call("get", key..":ts") or now)
tokens = math.min(capacity, tokens + (now-last) * rate)
if tokens >= 1 then
redis.call("set", key, tokens-1)
redis.call("set", key..":ts", now)
return 1 -- allowed
else return 0 end

Sliding Window Counter in Redis:
Sorted set with timestamp as score:
MULTI
ZREMRANGEBYSCORE key 0 (now-window_ms)
ZCARD key
ZADD key now request_id
EXPIRE key window_seconds
EXEC
Count in the sorted set = requests in the last window_ms. If count < limit → allow.

Trade-offs:
Token Bucket: allows bursts (100 req/s limit, user sends 100 at t=0, then waits 1s) — feels natural. Good for APIs. Memory O(1) per user.
Sliding Window: no burst. Strictly N requests per window. Slightly higher memory (O(N) per user). Better for abuse detection.
Fixed Window: simple but boundary attack — 100 req at 11:59:59pm + 100 req at 12:00:00am = 200 requests in 2 seconds, both technically within limits.

Distributed rate limiting: Each app server has local counter + sync to Redis every 100ms. Trade-off: occasional over-counting (up to 100ms window * N servers) for lower Redis latency.

At-most-once (producer): acks=0 — producer doesn't wait for broker ack. Highest throughput, data loss on broker failure. Used for: metrics, logs where loss is acceptable.

At-least-once (producer): acks=all + retries=MAX_INT + enable.idempotence=false. Broker confirms all in-sync replicas wrote. If ack is lost in transit, producer retries → duplicate. Consumer must be idempotent (check if already processed). Used for: most event pipelines.

Exactly-once (producer + consumer): enable.idempotence=true gives idempotent producer (sequence number per partition, broker deduplicates). Transactional API (initTransactions / beginTransaction / commitTransaction) wraps consume+produce in an atomic unit — offsets committed only if the entire batch commits. Used for: financial calculations, inventory updates.

Consumer offset commits: auto.commit.enable=true commits every 5s — at-least-once (may reprocess on crash). Manual commit after processing: call commitSync() after handling each batch. Enable.idempotence on consumer side: use a DB unique constraint or Redis SET NX on message_id before processing.

Topic design: One topic per business entity/event type: orders.placed, orders.payment-processed, orders.fulfilled, orders.cancelled. Partition by order_id — ensures all events for an order arrive in order to one consumer.

Outbox pattern (dual-write problem): The problem: writing to DB and Kafka in a single transaction is impossible. If you write DB then Kafka crashes → inconsistency. Solution: write to an outbox table in the same DB transaction. A CDC process (Debezium) tails the WAL and publishes outbox records to Kafka. Atomicity guaranteed by the DB transaction; Kafka publish is a separate async step.

Schema registry: Use Confluent Schema Registry with Avro/Protobuf. Producers register schemas; consumers fail-safe against schema evolution. Critical for a multi-team event bus — prevents schema drift breaking consumers silently.

Consumer group isolation: payment-service, inventory-service, notification-service each have their own consumer group. Each gets every event independently. One service being slow doesn't affect others — it just falls behind (monitor consumer lag).

Dead letter queue (DLQ): If a consumer fails processing after N retries, route to an orders.dlq topic. Monitor DLQ; don't silently drop. Replay from DLQ after fixing the bug.

Kafka: Log-based — messages are retained and replayable. Consumers track their own offset. Fan-out to N consumer groups with no extra cost. Throughput: 1M+ msgs/s. Use for: event sourcing, analytics pipelines, CDC, microservice event bus, audit logging. Operational complexity: requires ZooKeeper/KRaft, partition management, schema registry.

RabbitMQ: Message broker — delete-on-ack model. Rich routing: fanout exchange (broadcast), direct (routing key), topic (pattern matching), headers. Messages are consumed once and deleted. Priority queues, TTL, dead-letter exchanges. Use for: task queues, RPC over messaging, complex routing, low-volume high-flexibility needs.

SQS: Managed AWS service. FIFO queues or standard (at-least-once, best-effort ordering). Visibility timeout prevents double-processing without locking. Dead-letter queues built-in. Max 14-day retention. No replay. Use for: serverless architectures, AWS-native systems, simple decoupling, Lambda triggers. SQS + SNS = pub-sub fan-out.

Decision framework: Need replay/audit? → Kafka. Complex routing rules? → RabbitMQ. AWS-managed, no ops burden? → SQS/SNS. High throughput streaming? → Kafka. Simple job queue? → RabbitMQ or SQS.

L4 load balancers (e.g., AWS NLB, HAProxy TCP mode): Establish one TCP connection to backend per client connection (full proxy) or use DSR (Direct Server Return) where response bypasses the LB. Low latency (~microseconds added), can handle millions of connections/s. Used for: database proxies, game servers, any non-HTTP protocol, ultra-low latency scenarios.

L7 load balancers (e.g., AWS ALB, Nginx, Envoy): Terminate the client TLS/TCP connection, read the full HTTP request, then make a routing decision and open a new connection to the backend. Can do: path-based routing (/api → backend, /static → CDN), host-based routing (api.example.com → API cluster), header injection (X-Forwarded-For), WebSocket upgrades, HTTP/2 multiplexing, sticky sessions via cookies. Added latency: 1–5ms for TLS + HTTP parsing.

Sticky sessions: L7 LB sets a cookie on first response. Subsequent requests from the same client include the cookie → same backend. Required for stateful apps that store session in memory. Better: eliminate stickiness by storing session in Redis.

AWS architecture: NLB (L4) in front of ALB (L7) for maximum flexibility. NLB gets a static IP (required for whitelisting), passes through to ALB which does HTTP routing.

DNS-based global routing (Route 53): Latency-based routing: returns the IP of the region with lowest latency to the client. Geolocation routing: EU clients → EU region (data residency compliance). Health checks: if us-east-1 health check fails, Route 53 removes it from DNS and routes to eu-west-1. TTL: set low (60s) for fast failover, but DNS caching by ISPs can still cause 5–15min propagation delay.

Anycast: Cloudflare and AWS Global Accelerator advertise the same IP prefix from all PoPs globally. BGP routing automatically sends clients to the nearest PoP. No DNS TTL delay — failover happens at BGP convergence time (~30s). Better for real-time apps where DNS TTL delay is unacceptable.

Active-active vs active-passive: Active-active: both regions serve live traffic. Write conflicts require conflict resolution (last-write-wins, CRDTs, or sticky writes to one region). Active-passive: primary region serves all traffic; passive is warm standby. RTO (Recovery Time Objective) ~minutes. Lower complexity.

Data replication: Stateless services are easy — just add replicas. Databases: async replication with possibility of data loss on failover, or synchronous replication with latency penalty (Spanner, CockroachDB, Aurora Global).

1. Local caches: Browser DNS cache (chrome://net-internals/#dns), OS hosts file (/etc/hosts), OS resolver cache (nscd/systemd-resolved). TTL-bounded.

2. Recursive resolver query: OS sends query to configured DNS resolver (DHCP-assigned or 8.8.8.8). Resolver checks its cache. If miss, begins iterative resolution.

3. Root nameserver: 13 logical root server clusters (A–M), distributed globally via anycast. Returns NS records for .com TLD server. Response cached; root servers are rarely queried.

4. TLD nameserver: .com TLD operated by Verisign. Returns NS records for example.com's authoritative nameserver. TTL: 2 days (changes rarely).

5. Authoritative nameserver: Returns A record (IPv4) or AAAA (IPv6) for example.com. This is what you configure in Route 53 / Cloudflare DNS. TTL: 300s (5min) is common. Lowered to 60s before migrations.

6. TCP + TLS: 3-way handshake (1 RTT) + TLS 1.3 handshake (1 RTT with 0-RTT for repeat connections). HTTP/2 multiplexes multiple requests over one connection. QUIC/HTTP3 eliminates TCP handshake overhead entirely.

CDN interception: If Cloudflare is the authoritative NS, it returns a CDN edge IP. Request goes to nearest PoP, served from edge cache. Origin is only contacted on cache miss.

ABR streaming (HLS / DASH): Video encoded at multiple quality levels (360p, 720p, 1080p, 4K). Split into 2–6 second segments. Client player downloads a manifest (.m3u8 or .mpd) listing segment URLs. Player monitors download speed and buffer health, switching quality levels seamlessly. Each segment is independently cacheable at CDN edge.

CDN caching for video: Segments (small, fixed-size) → high cache hit ratio. Manifest file (.m3u8) → short TTL (30s) since live streams update it constantly. Signed URLs for auth: CDN validates HMAC signature so you don't need to call origin for auth on every segment request.

Multi-CDN: Use 2–3 CDN providers (Cloudflare, Fastly, Akamai). Route users to fastest CDN based on real-time QoE data. Fallback: if CDN A has elevated error rate → shift traffic to CDN B. Tested by Netflix (OpenConnect) and YouTube.

Origin shield: CDN PoPs closer to edge may not cache long-tail content. Origin shield = a single regional CDN node that consolidates cache-miss requests to origin. Reduces origin load from N PoP misses to 1 shield miss per segment.

Live streaming: Ultra-low latency (<3s): CMAF Low-Latency HLS or WebRTC. Standard live (3–8s): HLS/DASH with short segment duration. Broadcast-quality (8–30s): larger segments for better compression.

Offset pagination problem: SELECT * FROM posts ORDER BY created_at LIMIT 20 OFFSET 10000 forces the DB to read and discard 10,000 rows. Each page gets slower. Also: if a row is inserted/deleted between page 1 and page 2 requests, you get duplicates or skipped items.

Cursor-based (keyset) pagination:
-- First page
SELECT * FROM posts ORDER BY created_at DESC LIMIT 20;
-- Returns: last item has created_at='2024-01-15 10:30:00'
-- Next page cursor = base64('2024-01-15 10:30:00')
SELECT * FROM posts
WHERE created_at < '2024-01-15 10:30:00'
ORDER BY created_at DESC LIMIT 20;
Index seek directly to cursor position — O(log N) regardless of page depth. Stable: inserts/deletes don't cause skips or duplicates.

Cursor collision (non-unique sort key): If two items have the same created_at, cursor is ambiguous. Fix: composite cursor (created_at, id) → stable, unique ordering. WHERE (created_at, id) < (cursor_ts, cursor_id).

API design: Return { data: [...], cursor: "opaque_base64", has_more: true }. Cursor is opaque to client — implementation can change without breaking clients. GraphQL Relay spec: edges + pageInfo { endCursor, hasNextPage }.

Breaking changes (require new version): Removing fields, renaming fields, changing field types, changing HTTP methods, changing auth scheme, removing endpoints, changing error codes.

Non-breaking changes (safe to deploy): Adding new optional request parameters, adding new response fields (clients should ignore unknown fields), new endpoints, new enum values (if client handles gracefully), looser validation.

Versioning strategies:
1. URL path: /v1/users, /v2/users. Simple, explicit, excellent CDN cacheability. Most popular for public APIs (Twitter, Stripe, Twilio).
2. Header versioning: API-Version: 2024-01-01 (Stripe's date-based approach). Clean URLs; version is a request concern not a resource concern. Harder to test in browser.
3. Query param: /users?version=2. Convenient for quick tests; messy for complex APIs.

Sunset policy: When deprecating v1: (a) add Sunset: Sat, 31 Dec 2024 and Deprecation: Mon, 01 Jan 2024 headers on every v1 response, (b) email registered API key owners, (c) log which clients still use v1, (d) enforce sunset date. Stripe runs versions for years — very generous sunset windows for public APIs.

Client implementation: Generate UUID before sending. Retry the exact same request (same body + same key) on timeout or 5xx. Never generate a new key for a retry — that creates a new operation.

Server implementation:
BEGIN;
-- Atomic check-and-insert
INSERT INTO idempotency_keys (key, status, response)
VALUES ('uuid-123', 'processing', NULL)
ON CONFLICT (key) DO UPDATE
SET lock_acquired = true
RETURNING status, response;
-- If status='completed' → return cached response
-- If status='processing' → wait or return 409
-- Execute payment logic...
UPDATE idempotency_keys SET status='completed', response=... WHERE key='uuid-123';
COMMIT;

Concurrent retry handling: Two retries arrive simultaneously. First gets the row lock (SELECT FOR UPDATE on idempotency_keys). Second sees 'processing' and returns 409 or waits. When first completes, second re-reads and returns cached response.

TTL: Keep idempotency keys for 24 hours (Stripe) or 7 days. After expiry, the key is invalid — client must generate a new one. Store in Redis with TTL for fast lookups + periodic sync to DB for durability.

Response reproducibility: The same idempotency key must always return the exact same response — including error responses. If payment failed with "insufficient funds" on the first attempt, retry must return the same error, not re-attempt.

Sidecar proxy pattern: Envoy (or Linkerd's linkerd-proxy) runs as a sidecar container in the same pod. All inbound and outbound traffic is transparently intercepted. Services talk to localhost; the sidecar handles everything else.

What a service mesh provides:
1. mTLS (mutual TLS): Every service-to-service call is encrypted and mutually authenticated. No more trusting "because it's inside the cluster." Istio does this with SPIFFE/SPIRE certificate issuance.
2. Retries + circuit breaking: Configured in YAML, not code. Consistent policy across all services.
3. Observability: Automatic distributed traces (Jaeger/Zipkin integration), golden signals (latency, traffic, errors, saturation) for every service pair without code changes.
4. Traffic management: Canary deployments (route 5% of traffic to v2), A/B testing, fault injection for chaos engineering.

Drawbacks: Sidecar adds ~2ms latency per hop. Operational complexity of Istio is significant. Alternative: Cilium eBPF-based mesh (no sidecar, kernel-level, lower overhead).

When NOT to use: <5 services, single team, small scale. The overhead isn't worth it. Start with a good HTTP client library (Resilience4j, go-kit) for retry/circuit breaking.

Bounded contexts (DDD): Identify domain boundaries where concepts have consistent meaning. "Order" means different things to the payment team (a charge to process) vs the warehouse team (a pick list) vs the customer team (a status to track). These are natural service boundaries.

Strangler Fig pattern: Build new functionality as services. Add a routing layer (API gateway) in front of the monolith. Gradually migrate monolith endpoints to services behind the same gateway. The monolith "strangles" over time — new code goes to services, old code stays until migrated. Zero-risk incremental migration.

Database decomposition: Most painful part. Options:
1. Shared DB (anti-pattern) → two services sharing a DB schema — creates coupling.
2. Database-per-service → each service owns its schema. Joins go away; replaced by API calls or events. Enables polyglot persistence (use the right DB for each service).
3. Shared DB with schema isolation → same Postgres instance but different schemas — a stepping stone toward full separation.

Anti-patterns to avoid: Distributed monolith (services that are tightly coupled and must deploy together). Nano-services (too granular — network overhead dominates). Services that share databases (schema coupling).

Architecture: Postgres (source of truth) → CDC/Debezium → Kafka → Elasticsearch indexing workers → ES cluster → Search API → clients.

ES cluster sizing (100M docs): ~1KB per doc average = 100GB source data. ES index size ~3–5x source (inverted index overhead, stored fields, doc values) = 300–500GB. With 3 replicas: ~1TB. Shard size recommendation: 20–50GB per shard → 20–50 primary shards. Too many small shards → overhead per shard (heap, segment merges). Too few large shards → uneven distribution, slow reindex.

Mapping design:
- title: text with standard analyzer + keyword for exact sort/facet
- description: text with english analyzer (stemming: "running" → "run")
- price: float (range queries, sorting)
- category: keyword (facets, filtering)
- embedding: dense_vector(dims=1536) for semantic search

Hybrid search (keyword + semantic): BM25 for exact keyword relevance + vector similarity (cosine) for semantic meaning. Combine with Reciprocal Rank Fusion (RRF) or weighted combination. ES 8.x has native hybrid search with kNN + BM25.

Zero-downtime reindex: Create new index with updated mapping → reindex documents → atomic alias swap (POST _aliases: remove old, add new) → delete old index. Never reindex in place.

Embedding generation: Pass text through a model (OpenAI text-embedding-3-small, sentence-transformers, Cohere) → 768–3072 dimension float vector. Each document gets an embedding at index time. Query also gets an embedding at query time.

Approximate Nearest Neighbor (ANN) algorithms: Exact kNN (brute force cosine similarity over all vectors) is O(N×D) — too slow for 100M docs. ANN algorithms trade recall for speed:
- HNSW (Hierarchical Navigable Small World): Graph-based, O(log N) query, excellent recall. Used by: pgvector, Pinecone, Weaviate, ES 8.x. Memory-intensive: 1536-dim float32 = 6KB/vector → 600GB for 100M vectors.
- FAISS (Facebook AI Similarity Search): IVF (inverted file index) + PQ (product quantization) compresses vectors 4–32x. Lower memory, slight recall loss. Good for massive scale.

When BM25 wins: "GET invoice INV-2024-001" — exact match, structured lookup. Part numbers, SKUs, specific names — users know exactly what they want.

When vector wins: "comfortable shoes for standing all day" — semantic intent, no exact keywords. Recommendations ("similar to this product"). Multimodal ("search by image").

Good SLIs: Measure what users care about — not internal metrics. Bad: CPU < 80%. Good: request latency p99 < 500ms at the load balancer level. Best SLI categories (Google's four golden signals): Latency (how slow), Traffic (how much load), Errors (how many failures), Saturation (how full — queue depth, DB connections).

Setting SLOs:
1. Start with historical data — what's your p99 latency actually been? Set SLO slightly below your current best performance.
2. Ask: what does the user experience? For payments, 99.99% availability. For recommendations, 99.5% is fine (degrading to no recommendations is acceptable).
3. Consider dependency SLOs. Your SLO cannot exceed your dependencies' SLOs. If your DB is 99.9%, your service SLO must be ≤ 99.9% (in practice, lower due to your own failures).

Error budget usage: 99.9% SLO = 43.8 min budget/month. Spend budget on: incidents, planned maintenance, risky feature deploys. When budget is low (<20% remaining): pause risky changes, focus reliability work. When budget is ample: move fast, ship features. This creates a data-driven conversation between reliability and velocity.

Multi-window burn rate alerts: Google SRE recommendation: alert when burn rate is high over both short (1h) and long (6h) windows simultaneously. Avoids false positives from brief spikes. A 14x burn rate over 1h means you'll exhaust the monthly budget in 2 days.

Trace context propagation (W3C traceparent header):
traceparent: 00-{trace_id}-{span_id}-01
trace_id: 128-bit, unique per request (e.g., user clicks "checkout"). span_id: 64-bit, unique per operation within the trace. Each service: extracts parent span from incoming headers, creates a child span, injects its own span ID before calling downstream services.

Span attributes: http.method, http.status_code, db.statement, peer.service, error=true, user.id. Rich attributes enable powerful queries: "all traces where db.statement contained a slow query AND error=true."

Sampling: At 10K req/s, tracing 100% creates enormous data volume. Strategies:
1. Head sampling: decide at trace entry point (1% of requests). Simple, but misses rare slow requests.
2. Tail sampling: collect all spans, make sampling decision after trace completes (keep 100% of errors + slow traces, 1% of fast successful ones). Requires a trace buffer (Tempo's tail sampler, Honeycomb's Refinery).

OpenTelemetry standard: Vendor-neutral: instrument once, export to any backend (Jaeger, Zipkin, Honeycomb, Datadog, Grafana Tempo). SDK available in Go, Java, Python, JS, Rust. Auto-instrumentation: zero-code spans for HTTP, gRPC, DB drivers via agent injection.

Prometheus internals: Time-series DB (TSDB) on local disk. 2-hour in-memory block, flushed to immutable on-disk block. Blocks compacted over time. Retention: 15 days default. WAL for durability. Query engine: PromQL (functional, vector-oriented).

Scale challenges: Single Prometheus: max ~5M active series, ~1M samples/s. Beyond that: Cortex, Thanos, or VictoriaMetrics for horizontal scaling.

Thanos architecture:
1. Sidecar runs next to each Prometheus, uploads blocks to object storage (S3) every 2h.
2. Store Gateway serves queries against S3 blocks.
3. Querier fan-outs to multiple Prometheus + Store Gateways, deduplicates replicated series.
4. Compactor merges and downsamples old blocks (5m resolution after 2 weeks).
Result: unlimited retention, global query view across Prometheus instances.

Cardinality explosion: Each unique label combination = one time-series. http_requests_total{user_id="12345"} — if user_id has 10M values, this single metric creates 10M series. This is a "high cardinality" metric and will OOM Prometheus. Fix: use trace attributes for high-cardinality data; metrics for aggregate dimensions only.

Phase 1 (PREPARE): Coordinator sends PREPARE to all participants. Each acquires locks and writes a redo log, then responds YES/NO.

Phase 2 (COMMIT or ROLLBACK): If all YES → COMMIT. Any NO → ROLLBACK. Participants apply and release locks.

Failure modes:
1. Coordinator crashes after PREPARE, before COMMIT: Participants hold locks indefinitely — must block waiting for coordinator to recover. This is the "in-doubt transaction" problem.
2. Participant crashes after ack, before commit: Coordinator waits for timeout, then rolls back. Participant must re-sync on recovery.

When to use 2PC: Same-organization, low-latency networks (e.g., two Postgres shards in the same AZ). Never across microservices owned by different teams — coordinator coupling is too tight.

Saga advantages: Each service uses only local transactions. No coordinator. Service failures trigger compensation events. Pairs perfectly with event-driven architecture. Used by Stripe, Uber, Netflix.

Saga disadvantages: No isolation between saga steps — concurrent sagas may interleave. Intermediate states are visible. Must design idempotent compensating transactions.

The dual-write failure scenarios:
1. DB write succeeds → process crashes → Kafka publish never happens → downstream services miss the event
2. Kafka publish succeeds → DB write fails (timeout, constraint) → event fired for a transaction that was rolled back

Outbox Pattern:
1. Within the same DB transaction: INSERT into business table + INSERT into outbox table (event_type, payload, status='pending')
2. A separate publisher process (CDC relay or polling) reads pending outbox rows and publishes to Kafka
3. On successful Kafka ack: mark outbox row as published (or delete it)

CDC approach (preferred): Use Debezium to tail the outbox table's WAL. No polling — microsecond latency after commit. Debezium publishes one Kafka message per row change. The outbox table never needs explicit status updates — deletion is the signal.

Idempotency: Outbox gives at-least-once delivery (publisher may crash between Kafka ack and DB update). Consumers must be idempotent: check a unique event_id before processing. Store processed event_ids in a dedup table with TTL.

Why orchestration over choreography for payments: Choreography (services react to events) becomes a distributed state machine that's hard to visualize, debug, and audit. An explicit orchestrator (a service or workflow engine) owns the saga state, retries, timeouts, and compensations — a single source of truth for payment status.

Payment saga steps:
1. ReserveInventory → compensation: ReleaseInventory
2. AuthorizeCard (pre-auth) → compensation: VoidAuthorization
3. DeductInventory → compensation: RestockInventory
4. CaptureCharge → compensation: RefundCharge (expensive!)
5. FulfillOrder → compensation: CancelFulfillment

Idempotency keys: Every step receives an idempotency_key = payment_id + step_name. If a step is retried (network timeout after success), the downstream service returns the cached result instead of double-charging.

Timeout handling: Each step has a deadline. If no response in 30s → orchestrator marks step as UNKNOWN → retries with same idempotency key → if 3 retries fail → compensation saga begins from the last confirmed step.

State persistence: Saga state stored in a JSONB column (saga_id, current_step, status, compensation_log). Updated atomically with each step. On orchestrator restart, resume from last known state.

CRUD model: accounts table has a balance column. UPDATE accounts SET balance=balance-100 WHERE id=5. Previous state is gone. No history without a separate audit log.

Event sourcing model: events table: {account_id, type:'DEBIT', amount:100, timestamp, version}. Current balance = SUM over event stream. Full history retained. Append-only — no updates or deletes.

Projections (Read Models): Replaying every event for every read is slow. Event sourcing pairs with CQRS: a separate read model (denormalized Postgres table, Redis, Elasticsearch) is updated by an event processor. Read model may lag by milliseconds.

Snapshots: For long-lived aggregates, store a periodic snapshot of current state + the event version at snapshot time. On load: load snapshot, replay only events after snapshot version. Prevents O(N) replay.

When to use: Financial ledgers (required audit trail), e-commerce orders (need to reconstruct order state at any point), collaborative tools (Figma, Google Docs — operations as events enable conflict-free merge), compliance-heavy domains.

Downsides: Schema evolution is hard (event format v1 must be migratable to v2), query patterns are limited (cannot directly query "all accounts with balance > 1000" without a projection), eventual consistency of read models needs careful design.

Connection layer: Stateless HTTP + WebSocket gateway servers. Each server holds 10K–50K connections in memory. A connection service writes to Redis: user:{id}:server = server_id with a 30s TTL (heartbeat refreshes). On disconnect, key expires.

Message flow (1-to-1):
1. User A (on Server 1) sends message to User B
2. Server 1 looks up Redis: B is on Server 3
3. Server 1 publishes to Redis channel server:3
4. Server 3 receives pub/sub event, pushes to B's WebSocket
5. Message written to Cassandra asynchronously (partition key: conversation_id, sort key: timestamp)

Group messages (fan-out): A group has 1000 members. One message → 1000 deliveries. At 100K messages/s in a large group: use a fan-out service. Option A: write once to DB, online members pull via long-poll (WhatsApp model). Option B: fan-out to all online members' servers via pub/sub (Slack model). Option A scales better; Option B is lower latency.

Message storage: Cassandra: partition by conversation_id, cluster by created_at DESC. Allows efficient "latest 50 messages" query. Retention: keep 90 days in hot storage, archive to S3 Parquet for compliance.

Offline delivery: If user is offline (no entry in Redis), write message to inbox table. On reconnect, drain inbox. Also trigger push notification (APNS/FCM) via a notification service.

Online status:
SETEX presence:{user_id} 60 "online" — client sends heartbeat every 30s. TTL=60s means 2 missed heartbeats = offline. Query: GET presence:{user_id}. For bulk friend status: MGET presence:u1 presence:u2 ...

Status fan-out: When user A comes online, their status change must be pushed to all of A's contacts who are currently online. Naive: query all friends (potentially 5000), look up their servers, send presence update to each. Optimized: clients subscribe to presence channel for friends they care about; server pushes deltas only.

Typing indicators: "User is typing" debounced every 2s. Server receives → broadcasts to conversation participants → TTL 5s (if no new typing event in 5s, display disappears). Never persisted — entirely ephemeral Redis pub/sub.

Scale concern: 100M users × 30s heartbeat = ~3.3M heartbeat writes/s to Redis. This is fine for a Redis cluster (sharded by user_id). The expensive part is fan-out: publishing presence changes to all connected friends. Batch updates: aggregate presence changes over 1s windows and bulk-push diffs.

Naive approach (fails): Last write wins — if A inserts "hello" at position 5 and B deletes character at position 5 concurrently, naive merge loses data or corrupts the document.

Operational Transformation (OT): Each edit is an operation (INSERT char at pos, DELETE char at pos). Operations are transformed against concurrent operations before being applied. If A inserts at pos 5 and B inserts at pos 3, A's operation is transformed: insert at pos 6 (accounting for B's insert). Requires a server to sequence and transform operations — can't be fully P2P.

CRDTs: Mathematical data structures designed to merge without conflicts. Each character gets a globally unique ID and a position derived from its neighbors (not integer offset). Insertions and deletions commute — apply in any order, same result. No server coordination needed, P2P friendly. Used in: Figma, Automerge, Yjs framework (used by VS Code, Jupyter).

Architecture for Google Docs-scale:
1. All clients connect via WebSocket to a document session server
2. Operations buffered locally, sent to server
3. Server applies OT, assigns a global sequence number, broadcasts to all participants
4. Clients apply received operations, transform against pending local ops
5. Document state checkpointed every N operations to S3; operations stored in append-only log

Presence in docs: Cursor positions broadcast via WebSocket every 100ms. Not persisted — ephemeral.

Upload flow:
1. Client splits file into 4MB chunks, computes SHA256 of each chunk
2. Client sends chunk hashes to metadata API: "which of these do I need to upload?"
3. API checks chunk store — returns list of hashes not yet uploaded (deduplication)
4. Client uploads only missing chunks to S3 via presigned URLs
5. Client calls CompleteUpload(file_id, [chunk_hashes]) — metadata DB records file as version N

Deduplication benefit: If 100 users upload the same file, only 1 copy is stored. Even within a file, duplicate chunks (e.g., large files with repeated sections) are stored once. Dropbox reported 90%+ deduplication rate on early servers.

Sync: Each device has a sync cursor (last-seen change_id). On reconnect, client queries: "give me all changes since change_id=X" → receive delta of modified files → pull only changed chunks.

Conflict resolution: If two devices edit the same file while offline, both generate version N+1. On sync, server detects version conflict. Strategy: create a "conflicted copy" (Dropbox's approach — no data loss) or merge (requires CRDT for structured data). For binary files (photos, PDFs), always create a conflicted copy.

Presigned URLs: Metadata server issues S3 presigned URLs with 15-minute expiry for each chunk upload. Client uploads directly to S3 — metadata server is never in the data path. Reduces infrastructure cost dramatically (no bandwidth billing on app servers).

Upload pipeline:
1. Creator uploads to a resumable upload endpoint (multipart to S3)
2. S3 event triggers a transcoding job (published to SQS/Kafka)
3. Transcoding workers (GPU or AWS MediaConvert) produce: 4 resolution variants × 3 codecs × N segments
4. Segments stored in S3, manifest files generated per quality level
5. Video metadata (duration, thumbnails, chapters) stored in PostgreSQL

Adaptive Bitrate (ABR): HLS playlist has a master manifest listing all quality levels. Player buffers 30s of video. If download speed drops → switch to lower quality at next segment boundary. If speed improves → switch up. Seamless to user (no rebuffering on quality switch).

CDN strategy: Segments are static files → perfect for CDN caching. Long-tail videos (watched rarely) are cached at origin. Popular videos (top 0.1%) are cached at all 200 CDN PoPs globally. YouTube serves 1B+ hours/day — without CDN edge caching, origin bandwidth would be economically infeasible.

DRM (Digital Rights Management): Encrypted segments keyed with content-specific AES keys. Key server (KMS) issues decryption keys only to authenticated players. Widevine (Google) for Chrome/Android, FairPlay (Apple) for Safari/iOS, PlayReady (Microsoft) for Windows.

Thumbnail generation: Extract frames at N-second intervals during transcoding. Generate animated previews (hover thumbnails). Stored as WebP/AVIF for compression. Served from CDN.

Erasure coding: An object is split into k data chunks + m parity chunks. Any k out of k+m chunks can reconstruct the full object. S3 uses a variant where chunks are stored across multiple AZs — loss of an entire AZ still allows reconstruction. More storage-efficient than 3× replication (typical overhead: 1.4× vs 3×) while providing stronger durability.

Intra-AZ redundancy: Within each AZ, chunks are stored on multiple physical drives across multiple racks. A single disk failure or rack power failure doesn't lose any chunk.

Continuous scrubbing: S3 continuously reads and checksums stored data. Silent bit-rot (bit flips due to cosmic rays, aging drives) is detected within seconds and repaired from redundant chunks before the corruption spreads.

S3 vs EBS vs EFS:
S3 = object store (key-value, eventually-strong, infinite scale, high latency ~50ms)
EBS = block store (attached to one EC2 instance, POSIX-like, low latency ~1ms)
EFS = distributed file system (multi-AZ, NFS-compatible, can attach to many EC2, ~5ms)
Instance Store = ephemeral NVMe on the EC2 host (fastest, no durability — data lost on stop)

Strong consistency (added Dec 2020): S3 now provides read-after-write consistency for all operations. Previously, new objects were eventually consistent — there was a window where a GET after a PUT could return 404. This is no longer the case.

LSM-Tree + Bloom Filter: When reading key K, you must check: MemTable → L0 SSTables → L1 → L2 ... Each level may have N SSTables, each needing a disk seek. Bloom filter per SSTable: if filter says NO, skip the SSTable entirely — O(1) instead of O(log N) disk reads. Cassandra reports 90% of reads served without disk I/O for keys in cache thanks to Bloom filters.

Cassandra Bloom filter tuning: bloom_filter_fp_chance = 0.1 (10% FPR). Lower FPR = more memory. bloom_filter_fp_chance = 0.01 (1% FPR) uses ~10× more memory per SSTable. Tune based on read/write ratio — read-heavy workloads benefit from lower FPR.

Chrome Safe Browsing: Downloading 2M+ malicious URLs on every browser would be infeasible. Instead: a Bloom filter of ~300MB covers all known bad URLs with <1% FPR. On URL check: if filter says "possibly malicious" → real-time check against Google's API. If "definitely not" → skip check. 99% of URL checks handled locally.

Cache penetration prevention: Load all valid user IDs into a Bloom filter at startup. Requests for non-existent user IDs (common in scraping/DDoS attacks) are rejected by the filter before hitting cache or DB. Zero false negatives = valid users always pass through.

Intuition: Hash each element to a uniformly random binary string. The probability of seeing k leading zeros is (1/2)^k. If the maximum leading zeros observed is k, the estimate of distinct elements is ~2^k. HLL uses many hash sub-streams and harmonic mean to reduce variance.

Redis HyperLogLog: PFADD daily_visitors user_id, PFCOUNT daily_visitors. Returns approximate distinct count. Memory: 12KB per HLL regardless of cardinality. Compare to keeping a set: 1M distinct user IDs × 8 bytes = 8MB. HLL is 99.8% smaller with <1% error.

Merge: HLLs can be merged: PFMERGE total daily:mon daily:tue daily:wed — union cardinality estimated without re-scanning source data. Useful for "unique users over 7 days" type queries.

Use cases: Daily active users, unique IPs per endpoint (for rate limiting alerting), unique search queries per day, unique items viewed per user session.

Count-Min Sketch: Estimates frequency of items in a stream. 2D array of counters, k hash functions. Query: min count across all hash functions. Used for: top-K frequent items, approximate frequency counting in Kafka streams, detecting trending topics. Overestimates never, underestimates never — gives upper bound on count.

MinHash / LSH: Estimate Jaccard similarity between sets without comparing full sets. Used in: near-duplicate detection, plagiarism detection, recommendation systems (find users with similar listening history).

Why single-table: DynamoDB charges per-request and per-stored-byte. Multiple tables means multiple round-trips for related data. Single-table lets you collocate related items under the same partition key, enabling efficient queries that would require JOINs in SQL.

Pattern — Generic keys: Use overloaded PK/SK (partition_key, sort_key) with type-prefixed values:
PK=USER#123, SK=PROFILE → user profile
PK=USER#123, SK=ORDER#456 → order by user
PK=ORDER#456, SK=ORDER#456 → order details
PK=ORDER#456, SK=ITEM#789 → order line item
One query: PK=USER#123, SK begins_with ORDER# → all orders for user.

GSI (Global Secondary Index): Reverse lookups. If you need "all orders by status", create a GSI with PK=status, SK=created_at. Query GSI instead of scan. Up to 20 GSIs per table.

Access pattern first: Start by listing every query your app needs. Design PK/SK/GSI combinations to serve each query in a single request. If an access pattern requires a Scan — rethink the schema.

When to avoid DynamoDB: Ad-hoc queries unknown at design time, complex reporting and analytics, heavy JOINs, strong ACID transactions across many items, team unfamiliar with NoSQL modeling. In those cases: PostgreSQL + read replicas scales to 100K+ reads/s before you need DynamoDB.

Why TSDB beats Postgres for metrics:
1. Compression: Time-series data has high temporal correlation — values close in time are similar. Delta encoding (store difference instead of full value) achieves 5-20× compression vs raw floats. InfluxDB's Gorilla compression (Facebook's TSDB paper) compresses doubles to ~1.4 bytes average.
2. Ingestion throughput: Prometheus scrapes millions of metrics/s. A relational DB with row-per-point can't keep up with index updates. TSDBs use append-only segment files, batched writes, in-memory buffers.
3. Retention policies: Keep raw 1s data for 7 days → downsample to 1min for 90 days → downsample to 1hr for 2 years. TSDBs automate this (continuous queries, retention policies). In Postgres you'd write custom jobs.
4. Time-window queries: SELECT mean(cpu_usage) FROM metrics WHERE time > now()-1h GROUP BY time(5m) — TSDBs optimize these natively.

Prometheus + Thanos for scale: Prometheus is single-node (2B samples/shard practical limit). For multi-region scale: Thanos adds a sidecar that uploads Prometheus blocks to S3 + a query layer that merges results from multiple Prometheus instances. Free unlimited historical range.

When PostgreSQL + TimescaleDB is enough: Under 1M data points/day, need SQL JOINs with business data (e.g., metrics + user accounts), team already expert in PostgreSQL. TimescaleDB's hypertables give automatic time-partitioning, continuous aggregation, and compression within Postgres.

The SQL problem for graphs: "Find all friends of friends of user 123 who have purchased in the last 7 days." In SQL: 3 recursive JOINs on a users table. At 1M users with avg 200 friends each: join explodes exponentially. Postgres can handle 2–3 hops with CTEs but performance degrades rapidly beyond 3 hops.

Graph DB fraud detection:
Nodes: Account, Device, IP, Phone, Email, Card
Edges: USED_DEVICE, USED_IP, LINKED_PHONE, LINKED_EMAIL, CHARGED_CARD

Query: "Is this new account connected to any known fraudulent account within 2 hops via shared device or IP?"
MATCH (newAccount)-[:USED_DEVICE|USED_IP*1..2]-(fraudAccount {is_fraud:true})
RETURN COUNT(fraudAccount) > 0

This traversal visits only relevant subgraphs — not the full graph. At 100M accounts: milliseconds.

Real-world graph fraud signals:
1. Shared device between 50+ accounts → device farming
2. IP shared between new accounts created in burst → account factory
3. Phone number linked to known fraudulent accounts → phone resale
4. Ring structure: A → B → C → D → A (money laundering cycle)

Graph DB vs Postgres for graphs: Postgres with recursive CTEs handles simple graphs (social networks up to ~5M nodes, 3-hop queries). Beyond that, or for complex pattern matching, use a purpose-built graph DB.

Redis Sorted Set operations:
ZADD leaderboard:global 9500 user:123 — O(log N)
ZRANK leaderboard:global user:123 — O(log N), returns 0-indexed rank
ZREVRANGE leaderboard:global 0 99 — O(log N + 100), top 100
ZINCRBY leaderboard:global 50 user:123 — O(log N), atomic increment

Ranking window complexity: "Rank among my friends" — maintain a separate ZSET per user of their social graph + scores. Update on each score change: ZINCRBY friend_leaderboard:{user_id} delta friend_id for all friends. Fan-out on write. Or: on read, ZUNIONSTORE a temp set from all friend score ZSETs — fan-out on read, but single lookup at display time.

Handling 100M players: Redis ZSET performance is excellent up to ~10M members. Beyond that: shard by user_id bucket (ZSET per shard), maintain a global top-1000 in a separate ZSET (reconciled periodically). For the "exact global rank" of any user: probabilistic rank estimation + exact rank only for top 10K.

Persistence: Redis is in-memory. Persist to Postgres asynchronously: Redis acts as the write buffer and read cache. Background job drains Redis scores to Postgres every 60s. On Redis failure: reload from Postgres snapshot + replay score events from Kafka.

Windowed leaderboards (daily/weekly): Use EXPIREAT on the ZSET key — the key for "today's leaderboard" expires at midnight UTC. No manual cleanup needed. Or: key = leaderboard:{date} rotated daily.