Consensus and Coordination Algorithms Questions

Requirements & constraints:

• Allow low-latency reads from followers with bounded staleness.
• Provide an API that lets clients request fresher data when needed.
• Preserve monotonic reads and session guarantees for clients.

High-level design:

• Every write is assigned a monotonically increasing commit timestamp (use hybrid logical clocks or Lamport + physical time).
• Followers asynchronously replicate committed writes and expose read replicas.
• Clients maintain a session state containing last_seen_ts (highest commit_ts observed).

API semantics:

• GET(key, options) where options include:
  • max_staleness_ms (optional): acceptable age of data
  • min_commit_ts (optional): require data at least as fresh as this timestamp
  • consistency = {follower_read | leader_read} (default follower_read if staleness bound satisfied)
• Server response includes value, commit_ts, and source (follower/leader). If follower cannot satisfy min_commit_ts or max_staleness_ms, it returns TRY_LEADER or automatically forwards to leader.

Staleness bounds:

• Followers track last_applied_commit_ts per shard. For time-based bound, followers convert their last_applied_commit_ts to age using local clock vs commit_ts epoch and can accept reads where (now - commit_ts) <= max_staleness_ms.
• For version-based bound, followers ensure last_applied_commit_ts >= min_commit_ts.

Monotonic reads & session guarantees:

• Clients attach their session.last_seen_ts on each read (or server stores sessions). On a read, follower will only serve values with commit_ts >= session.last_seen_ts unless client explicitly requests weaker guarantee.
• After receiving a response with commit_ts R, client updates session.last_seen_ts = max(session.last_seen_ts, R).
• For writes, leader assigns commit_ts > session.last_seen_ts; clients can include session.last_seen_ts with write to ensure serialization after prior reads.

Ensuring correctness & freshness:

• Followers periodically apply replication and expose last_applied_commit_ts. To avoid serving too-stale data due to clock skew, use HLC to compare timestamps.
• If follower can't meet min_commit_ts, it rejects (TRY_LEADER) or proxies to leader which has the true latest commit_ts.
• To avoid stale follower serving after failover, use leader leases: leader increments epoch on election; followers refuse to serve follower_reads beyond lease window without confirming replication progress.

Operational notes and trade-offs:

• Pros: low-latency reads, explicit client control over freshness.
• Cons: complexity (HLC, session tracking), slightly higher tail latency if client asks for leader reads.
• Alternatives: synchronous cross-region replication for stronger freshness (higher write latency) or bounded staleness by fixed replica lag monitoring.

Example client flow:

1. Client reads with max_staleness_ms=50ms; follower checks last_applied_commit_ts and local time; if satisfied returns value+commit_ts; client updates last_seen_ts.
2. Later client issues a read requiring min_commit_ts = session.last_seen_ts+1 to ensure monotonicity; follower either serves (if applied) or returns TRY_LEADER.

This design gives clients explicit control of freshness, bounded staleness guarantees, and enforces monotonic reads via session timestamps while keeping read latency low when possible.

Requirements & constraints:

• Single coordinator at a time for scheduled jobs; low-latency election; tolerate network partitions; avoid duplicate job runs; fast failover; minimal operational complexity.

High-level options

1. Lease-based (TTL) via Zookeeper/etcd:

• Approach: one instance acquires a lease key with TTL; renew periodically. If lease expires, another can take leadership.
• Pros: simple, low overhead, widely supported, fast takeover when TTL short.
• Cons: choice of TTL vs risk window: too short → flaps on transient delays; too long → slow failover. Under partition, two nodes may think they hold lease if clock skew or network delays allow dual acquisition unless store offers linearizable TTL semantics.

2. Consensus algorithms (Raft/Paxos):

• Approach: a replicated state machine elects a leader via majority quorum. Leader change happens when majority detects failure.
• Pros: strong safety: at most one leader for any committed term; survives minority partitions; deterministic.
• Cons: higher latency, more complex, requires majority for progress — in split where a minority has network majority to job clients, those cannot progress.

Handling split-brain & safe failover (practical design)

• Use a linearizable backing store (etcd/consensus-backed) rather than ad-hoc DB; prefer Raft-backed systems (etcd) that provide atomic leases/leadership semantics.
• Combine lease with quorum check: leader holds a local lease and also writes heartbeats to a quorum of peers; on leadership handover require both lease expiration and inability to contact a quorum that confirms liveness.
• Use fencing tokens: whenever leader obtains lease, it increments a monotonically increasing token persisted in the store. Workers require the token to run jobs; older tokens are rejected. This prevents split-brain double-execution even if another node runs because it lacks current token.
• Clock strategy: avoid relying on synchronized clocks for safety; use store timestamps and TTL based on store's notion.
• Tune TTL and heartbeat: TTL = a few multiples of expected network RTT + processing jitter; implement exponential backoff to avoid thundering herds.
• Graceful handoff: leader, before releasing, attempts to transfer by writing next token and waiting acks; if impossible, allow failover after TTL/quorum rules.
• Observability & testing: simulate partitions, measure failover time, and add metrics/alerts for lease flaps and split-brain detection.

Recommendation

• Use a Raft-backed metastore (etcd/zookeeper) and implement leader leases with fencing tokens and quorum-aware checks. This gives practical simplicity of leases with the safety guarantees of consensus and a clear path to handle partitions and safe failover.

Requirements & assumptions:

• Goal: allow followers to serve local linearizable reads without contacting leader each time.
• Assume clocks have bounded drift: each node's clock rate differs by ≤ ρ (e.g., 100 ppm). Nodes can also optionally run a clock-sync protocol (NTP/PTP) to tighten bounds.
• Paxos/Raft-style single leader for writes; leader grants time-bounded leases to followers.

Design (lease-based linearizable reads):

• Leader issues a lease to a follower: (follower-id, lease-start, lease-duration, leader-term, signature). lease-start is leader's local timestamp when granting; signature prevents forgery.
• Follower can serve reads locally if its local clock t_local satisfies: t_local ∈ [lease_start - ε, lease_start + lease_duration - ε'] where ε accounts for clock skew bounds and message latency. Conservative choice: require follower's local clock < lease_start + lease_duration - max_clock_skew.
• Leader increments a monotonic term/epoch with each new leader; leases include term to invalidate old leases after leader changes.

Handling clock skew:

• Use bound ρ to compute safe margins. If leader timestamped lease_start = T_L, follower with clock T_F treats lease valid only until T_F < T_L + lease_duration - Δ where Δ = 2 * max_clock_skew + max_msg_delay. Alternatively, run periodic clock sync to reduce Δ.
• On ambiguous boundary, follower rejects local reads and forwards to leader.

Lease renewal:

• Follower tracks lease expiry and attempts renewal early (e.g., at 50% expiry) by sending renewal request to leader. Leader renews if still leader and term unchanged; renewal extends lease_start to leader's current time.
• Leader only grants/extends leases while it knows it's leader (based on its election timeout and majority heartbeats).

Leader transfer:

• To transfer leadership, current leader:
  1. stops granting new leases and waits for outstanding leases to expire (or immediately invalidates by bumping term).
  2. Initiates a safe handoff: increments term, writes a no-op entry to the log, and replicates it to majority. New leader starts granting leases only after committing its leadership entry.
• Alternatively, new leader can request explicit revocation signatures from old leader; committing new term ensures prior leases are invalidated by term mismatch.

Correctness reasoning:

• Linearizability preserved because a local-read served under a valid lease is guaranteed that no other leader could have committed conflicting writes in that lease interval (leader held exclusive authority). Term/version in lease plus conservative skew margins ensure no overlap with concurrent leaders.

Trade-offs:

• Larger leases reduce leader load but increase window for stale leader problems; smaller leases increase renewal overhead.
• Reliance on clock drift bounds vs. stronger clock sync: tighter sync reduces safety margins and improves availability.
• Simpler alternative: leader-coordinated reads (quorum read/lease read index) has higher latency.

Edge cases:

• Network partitions: followers won't serve reads if lease expired or uncertain.
• Clock jumps: detect large jumps and invalidate leases locally until reconciled.

Two-phase commit (2PC) is a blocking, coordinator-driven protocol to get distributed participants to agree to commit or abort a transaction.

• Phase 1 (Prepare): Coordinator asks all participants “Can you commit?” Each participant does local checks, writes a prepared/lock record, and replies YES or NO.
• Phase 2 (Commit/Abort): If all YES, coordinator sends COMMIT; otherwise it sends ABORT. Participants on COMMIT make changes durable and release locks; on ABORT they roll back.

Key properties and pitfalls:

• Atomicity across participants when coordinator and participants are correct.
• Blocking: if coordinator crashes after participants vote YES, participants wait on locks until coordinator recovery.
• No builtin fault-tolerant agreement: 2PC assumes a coordinator; it doesn’t tolerate coordinator loss without external recovery.

Contrast with distributed consensus (Paxos/Raft):

• Consensus solves agreement on a value in a fault-tolerant way (leader election, replicated log). It tolerates minority failures and provides liveness under leader availability.
• Using consensus for commits (e.g., replicate the transaction record in a Raft log) removes the single-point-of-failure blocking behavior and enables progress if a leader can be elected.
• Consensus has higher implementation and runtime cost (more messaging, log replication, complexity).

When 2PC is sufficient:

• Small number of services with reliable networks, short-held locks, and strong coordinator availability (e.g., within a single datacenter or for low-concurrency operations).
• When simplicity and low latency matter and occasional blocking is acceptable.

When prefer consensus or other approaches:

• Use consensus (or a replicated transaction coordinator) when you need fault-tolerant, non-blocking progress across failures and strong durability — at cost of complexity and latency.
• Prefer compensating transactions / eventual consistency (sagas) when operations span heterogeneous services that can’t participate in 2PC, when high availability and scalability matter, or when business logic allows eventual reconciliation. Sagas avoid global locks by ordering local commits and providing compensations on failures.

Rule of thumb:

• If you need strict ACID across services and can tolerate operational overhead and potential blocking, 2PC (or better, a replicated coordinator) can work.
• If you need availability and failure-tolerance at scale, use consensus-based coordination or design with compensating transactions and idempotent, retryable operations.

Requirements:

• 10k concurrent clients, low-latency exclusive locks on logical resources (keys), availability under node failures, safety (no two holders), reasonable fairness, avoid stale locks/deadlocks.

High-level architecture:

• Clients talk to a distributed lock service composed of either a consensus-backed key-value store (etcd/Consul) or a small fleet of lock servers behind a load balancer with leader election for state replication.
• Each lock is a lease record: {resource_id, owner_id, lease_id, expire_ts, version}.

Lock acquisition & renewal:

• Fast path (consensus-backed): client issues a conditional Put (compare-and-swap) to create lease if key absent or expired. The KV store ensures linearizability.
• Lease model: client obtains lease for TTL T and must renew before expire via refresh RPC (extend via CAS with current lease_id).
• If renew fails, client must stop using resource.

TTLs & stale lock avoidance:

• TTLs sized to expected operation latency + jitter (e.g., 2x p99). Clients extend proactively at 1/2 TTL.
• Use monotonic lease_id/version to prevent ABA; only matching lease_id can renew or release.
• For long operations, allow explicit checkpointing or lock handoff: holder writes state and issues a Transfer operation using CAS.

Failure detection:

• Rely on lease expiry for liveness. For quicker reclamation, use health heartbeats plus quorum-based consensus to avoid false positives.
• For centralized server approach, run the server replicated with leader election (RAFT) so leader failure detection is via election timeouts.

Fairness:

• Implement FIFO wait-queue per resource: if acquisition fails, client enqueues a request (append-only list) and server grants to head. With consensus store, maintain queue as a list under same key using CAS operations.
• Avoid starvation with bounded backoff and priority aging.

Deadlock avoidance:

• Avoid multi-lock blocking by:
  • Encouraging single resource locks where possible.
  • If multiple locks required, enforce global ordering (canonical resource ordering) or use two-phase locking with try-lock + rollback (try all without blocking; if any fails, release acquired and retry with backoff).
  • Provide deadlock detection by building a wait-for graph periodically (expensive) and aborting victims.

Trade-offs — consensus-based store (etcd) vs centralized lock server:

• Consensus (etcd):
  • Pros: Strong consistency, automatic leader election/replication, simpler client logic (CAS/leases), high durability.
  • Cons: Higher write latency (quorum), heavier operational complexity for large write rates; scaling many resources requires sharding or many keys (but etcd handles tens of thousands fine).
• Centralized lock server:
  • Pros: Lower latency for single leader, more flexibility for custom optimizations (in-memory queues, batching).
  • Cons: More complex replication for correctness; single leader is performance and availability bottleneck; you must implement safety (durable writes, leader failover) yourself.

Recommendations:

• For correctness and operational simplicity: use a consensus-backed lease/TTL mechanism (etcd) with per-resource FIFO queues and client-side proactive renewals. For extreme low-latency or specialized semantics, implement a replicated lock service using RAFT with careful attention to leader load, sharding hot keys, and strict lease/version checks.