Multi-Region and Geo-Distributed Systems Questions

Clarify requirements & constraints

• Multi-region stateful service (strong consistency required), must detect network partitions, avoid split‑brain, perform automated recovery with zero/controlled data corruption, minimal failover time, run on AWS (examples: Route53, ELB, EBS, DynamoDB, SQS).

High-level architecture

• Regions run replicas (leader + N followers). Use distributed consensus for metadata (e.g., Raft quorum via etcd or Consul) colocated or in a dedicated control-plane cluster per global group.
• Persistent store: single-writer primary with async/sync replication depending on RPO/RTO.

Core components

• Health checks: local (process, disk, storage latency), transport (TCP/HTTP), and cross-region heartbeats via a quorum service. Push metrics to CloudWatch and alerting.
• Leader election & fencing: use a central lock service (etcd/Consul/Cloud Spanner/leader-lock in DynamoDB with conditional writes) that issues monotonically increasing fencing tokens on AcquireLock.
• Safe write fencing: every write from a leader includes fencing token; followers reject writes with stale tokens.
• Split-brain detection: compare quorum of heartbeats + lease expirations + majority visibility.

Algorithmic steps

1. Leader acquires lock L with token T (atomic conditional write). Persist T to local durable log.
2. Leader serves writes; each write metadata includes token T.
3. Followers accept replication only if their local last_token == T or token is uninitialized; otherwise reject.
4. Health loop: nodes send heartbeats to quorum every H ms. If leader misses M heartbeats from majority, quorum considers leader dead.
5. On partition, isolated leader will not be able to renew lock (lock TTL). If leader cannot renew before TTL, lock becomes acquirable.
6. New leader candidate attempts AcquireLock -> receives token T2 > T. Only node with T2 can accept writes. Nodes with older token must refuse leadership until they accept T2 and reconcile.
7. Stale-leader detection: when a node with T tries to write after losing quorum, quorum rejects renew; clients receive 409/412 and use read-repair from majority.
8. Recovery: new leader performs safe catch-up: read highest committed log index from majority, perform leader-driven reconciliation (merge non-conflicting entries, abort/transform conflicting writes), then advance committed index and start accepting writes.
9. Data corruption prevention: writes are conditional on token and log index; any incoming write with token != current lock_token is rejected.

Implementation details (AWS examples)

• Use DynamoDB conditional PutItem for lock with attribute Version (fencing token) + TTL.
• Use Regional ALBs + Route53 health-check-based failover for traffic; clients prefer leader via service discovery (Route53 weighted + Consul DNS).
• Use EBS snapshots / S3 for backups; enable cross-region replication for logs.

Trade-offs & edge cases

• TTLs vs network latency: choose TTL >> typical RTT but small enough for failover.
• Split brain if two regions think they have quorum: centralize lock in a global control-plane (Cloud Spanner or a strong-consistency DB) to avoid dual leaders.
• Reconciliation complexity: prefer deterministic conflict resolution or abort-on-conflict for safety.

Monitoring & automation

• Automated runbooks: revoke lock, force fencing token increment, perform snapshot-based restore if divergence detected.
• Metrics: lock‑holder, token, last-commit-index, heartbeat latency, rejected-writes count.

This design ensures deterministic leader fencing, safe writes tied to tokens, explicit stale-leader detection via lock TTL and majority heartbeats, and controlled recovery without data corruption.

Clarify constraints

• RTO (max downtime) and RPO (max data loss) determine choices: RTO < 5 min → active-active or warm-standby with fast orchestration; RPO = 0 → synchronous cross-region replication (rare at scale) or planned regional paxos/CRDTs. I’ll assume RTO ≤ 15m, RPO ≤ 1min for examples.

Detection

• Multi-layer health checks:
  • Platform: CloudWatch / Azure Monitor / GCP Operations synthetic HTTP checks and regional ALB/Load Balancer target health.
  • Control-plane: metrics on API Gateway, message backlog, DB replication lag.
  • Heartbeat aggregator: central controller (Lambda/Function + SNS) that requires N-of-M signals; trigger only when majority of checks fail for > threshold (avoid flaps).

Orchestration

• Use serverless state machine (AWS Step Functions / Azure Durable Functions):

  1. Confirm outage via cross-checks and run sanity probes.
  2. Quarantine primary (mark unhealthy to avoid split-brain).
  3. Promote data replicas.
  4. Reconfigure services and networking.
  5. Update DNS and edge routing.
  6. Run validation tests; if fail, auto-rollback.

• Runbooks and IaC templates (CloudFormation/Terraform) invoked by state machine; actions executed via IAM-assumed playbooks (SSM, APIs).

Data promotion

• Preferred designs by RPO:
  • RPO ≈ 0: use managed global DB (Aurora Global/Cloud Spanner) with fast region primary switch; promotion via single-step managed API (low lag).
  • RPO ≈ seconds/min: asynchronous replica with minimal replication lag; promotion sequence:
    • Ensure replica apply queue drained.
    • Promote replica to writable (RDS promote-read-replica / gcloud sql promote replica).
    • Run consistency snapshot/checksum for key tables.
  • For object stores: promote cross-region replicated S3 buckets (replication status check) or use global namespace.

DNS & traffic shift

• Use health-aware DNS with low TTL in Route 53 / Traffic Manager and weighted or failover policies.
• Orchestrate in two phases:
  1. Control-plane switch: update service discovery / config (SSM Parameter Store, Consul).
  2. DNS change: change Route53 alias/weighted weights to point to new ALB/GCLB; set low TTL (30s) and use regional Anycast / CDN fronting to reduce client impact.
• For fast cutover, combine DNS with global load-balancer failover (Cloud CDN + Global LB) to shift in seconds.

Validation checks

• Automated smoke tests (login, writes, reads, core flows) executed by Step Function post-switch.
• Replication health and data integrity checks (row counts, checksums).
• Performance baseline checks (latency, error-rate thresholds).
• Canary traffic routing before full cutover.

Rollback

• Predefined rollback window and steps:
  • If validation fails, Step Function triggers reverse actions: demote promoted DB if possible or redirect traffic back, restore configuration from snapshots/IaC.
  • Preserve write-forwarding logs / change log to reconcile during rollback.
  • If primary recovers later, perform controlled failback with data reconciliation (dump + apply / logical replication) to avoid data loss.

Security & audit

• All actions logged to CloudTrail / Audit logs; approval gates for manual override; IAM roles with least privilege.

How RTO/RPO drive choices

• Lower RTO → more automation, warm/warm-active, global LB and low TTL, pre-provisioned infra.
• Lower RPO → synchronous or near-synchronous replication, more cost (latency/tradeoff).
• Trade-offs: cost vs latency vs complexity; choose the smallest architecture meeting RTO/RPO.

Example stack (AWS): CloudWatch alarms → Lambda aggregator → Step Functions → SSM/CloudFormation + RDS/Aurora promotion APIs → Route53 failover + Global Accelerator → Lambda smoke tests → SNS alerts/rollback.

Approach — brief
Implement an LWW-register that stores (value, timestamp, node_id). assign updates when timestamp greater or equal with node_id tie-break. merge chooses element with larger timestamp or, on tie, larger node_id (deterministic). Provide value() to read current value.

Code

class LWWRegister:
    def __init__(self):
        # store tuple: (timestamp:int, node_id:str, value: any)
        self._entry = None

    def assign(self, node_id: str, value, timestamp: int):
        """Assign a value with a timestamp and node id."""
        if self._entry is None:
            self._entry = (timestamp, node_id, value)
            return
        ts, nid, val = self._entry
        # replace if newer, or same timestamp but node_id greater
        if timestamp > ts or (timestamp == ts and node_id > nid):
            self._entry = (timestamp, node_id, value)

    def merge(self, other: 'LWWRegister'):
        """Merge another LWWRegister into this one deterministically."""
        if not isinstance(other, LWWRegister):
            raise TypeError("merge expects LWWRegister")
        if other._entry is None:
            return
        if self._entry is None:
            self._entry = other._entry
            return
        ts1, nid1, val1 = self._entry
        ts2, nid2, val2 = other._entry
        if ts2 > ts1 or (ts2 == ts1 and nid2 > nid1):
            self._entry = (ts2, nid2, val2)

    def value(self):
        """Return current value or None if empty."""
        return None if self._entry is None else self._entry[2]

Complexity & edge cases

• assign/merge/value all O(1) time and space.
• Handles tie-break deterministically via lexicographic node_id.
• Assumes monotonic integer timestamps per node not required; merge resolves conflicts.
• In cloud infra, use this for metadata convergence (e.g., instance tags) across regions; ensure node_id uniqueness (e.g., region+instance-id).

Clarify requirements & constraints

• RTO < 5 min, RPO < 1 min for user sessions, global low-latency reads/writes, active-active across regions. Assume cloud provider (e.g., AWS/GCP/Azure) managed services are acceptable.

High-level architecture

• Global traffic: provider GSLB (AWS Route53 latency/geo + health checks + weighted failover) + Anycast front door (CloudFront / Cloud CDN / Azure Front Door / GCP Cloud Load Balancing) to terminate TLS at edge.
• Regional stacks: identical app fleets behind autoscaling regional ALBs/PLBs, regional caches (Redis / Memcached) with cross-region replication, regional application APIs.

Session management

• Prefer stateless sessions:
  • JWT or opaque token stored in signed secure cookie; token contains minimal claims and refresh strategy.
  • Session state stored in globally-replicated store only when needed (see below).
• If sticky is required for legacy stateful apps:
  • Use short-lived sticky cookies at regional load balancer + replicate authoritative session store for failover.
  • Make stickiness fallback tolerant: on regional failure, app accepts stateless token or rehydrates session from replicated store.

Database replication & conflict resolution

• Use a globally-distributed, strongly-consistent option if application needs cross-region transactional consistency (e.g., Google Spanner, Cosmos DB with multi-master + strong consistency, or CockroachDB).
  • These meet RPO <1min and provide low-conflict semantics.
• For relational workloads on AWS:
  • Use Amazon Aurora Global DB (single-writer regional primary + fast secondary reads) OR implement multi-write with conflict resolution via:
    • Sharded single-writer per shard (route writes by shard key),
    • Multi-master with application-level conflict resolution (CRDTs for mergeable data, last-writer-wins with vector clocks for tolerable conflicts).
• For session store:
  • Use a global data plane: Redis Enterprise Active-Active (CRDT-based) or DynamoDB global tables with conditional writes to ensure <1 min replication and deterministic reconciliation.
• Design for idempotency and causal ordering: assign request IDs, client monotonic counters, or vector clocks to avoid duplicated effects.

DNS & traffic policies

• Low TTL (e.g., 30–60s) for DNS records used in failover, combined with health checks and Route53 or vendor policy to shift weights automatically.
• Use weighted routing to gradually shift traffic; use health-check-driven failover for full cutover.
• Anycast + global load balancer ensures new flows land in healthy regions quickly; DNS handles coarse steering.

Monitoring, SLOs, automation

• SLOs: session creation latency, replication lag (<30s target), error rates.
• Telemetry: DB replication lag, edge & regional health, traffic steering actions.
• Automated runbooks: IaC playbooks that can reconfigure weights, promote read-replicas, or rollback.

Failover / fallback testing

• Regular DR drills and Chaos Engineering:
  • Simulate full-region outage (cut network interfaces or withdraw weight), measure RTO against 5-min target.
  • Simulate DB write-region loss: test promotion (for single-writer) or conflict resolution (for multi-master).
  • Validate DNS TTL propagation times and client reconnection behavior.
  • Test session continuity: create sessions, fail region, verify sessions are honored or recovered within RPO target.
• Runbook & automation validation: automated promotion scripts, smoke tests, and rollback steps executed during drills.

Trade-offs

• Strong consistency (Spanner/Cosmos) simplifies correctness but costs more/latency higher for cross-region writes.
• CRDT/multi-master reduces write latency but increases complexity in conflict resolution.

This design uses global load balancing + Anycast for fast traffic steering, stateless-first session strategy with globally replicated session store, a managed global DB (or deterministic sharding/multi-master with CRDTs), low-TTL DNS and automated failover playbooks — all validated via scheduled chaos drills to ensure RTO < 5 min and RPO < 1 min.

Situation & goal
Minimize player-perceived latency and cross-region jitter for an 8-region real-time multiplayer game; support UDP traffic with session affinity.

Comparison (short)

• DNS-based routing
  • Pros: simple, low cost.
  • Cons: DNS caching causes stale mappings; coarse control; client may resolve to suboptimal region during failover — bad for tight latency/jitter.
• Anycast (BGP)
  • Pros: single IP, routes to nearest POP quickly; low connection-establishment latency.
  • Cons: unpredictable backend selection; packet path may change across BGP reconvergence — can cause cross-region jitter; needs global backbone to steer traffic to region.
• Cloud global load balancer / Global Accelerator
  • Pros: provider-managed front-door, health checks, deterministic steering to nearest healthy region, supports UDP (e.g., AWS Global Accelerator, GCP Traffic Director + proxy), rapid failover, observability.
  • Cons: cost, vendor lock-in.

Recommendation
Use a cloud global-load-balancer front door (Global Accelerator or equivalent) combined with regional game servers:

• Deploy edge accelerators / Anycast ingress managed by cloud provider (gives single static IPs + UDP support).
• LB steers UDP flows to the optimal region based on latency/health and can failover quickly.
• Keep regional authoritative game servers; use region-aware matchmaking to group players by latency.

Affinity for UDP

• Terminate UDP at the provider edge (accelerator), then forward to region over stable, low-latency backbone (preserves path).
• Use 5-tuple hashing (src IP, src port, dst IP, dst port, protocol) at the edge to ensure stickiness for the life of a match.
• For NATed clients, supplement with application-level session tokens: client includes session ID in packets; edge persists mapping (token -> backend) if 5-tuple changes.
• Implement periodic keepalives and short session timeouts (e.g., 30–60s) to release state.
• On failover, ensure accelerated state sync or redirect with quick rebind: edge returns “migrate to region X” with minimal RTT.

Operational notes

• Monitor latency/jitter metrics per region and per POP, tune steering policy.
• Use active health checks, and run chaos tests for region failover.
• Prefer provider solutions supporting UDP and real-time steering (AWS Global Accelerator or equivalent).