## Design Leader Election Using Redis Leases You have **N stateless service instances** all running the same code. At any instant, **exactly one** instance must act as the **leader** and perform a *singleton task* (e.g. driving a cron/scheduler, being the sole writer to a partition, running the single consumer of a queue). Every other instance is a follower/standby, ready to take over. Design a **lease-based leader election** mechanism using **Redis** as the coordination dependency. A single primary Redis endpoint is acceptable for this exercise. You may use any Redis features (`SET NX PX`, Lua scripts, Pub/Sub, etc.). Your design must address: - **Leader election** — at most one leader at any time. - **Failover** — if the leader crashes or becomes unhealthy, a new leader is elected within a bounded time. - **Lease / heartbeat** — leadership is time-bounded and continuously renewed while the leader is healthy. - **Correctness** — how you avoid or mitigate split brain, a leader "sticking" after a crash, clock-skew assumptions, and network hiccups / GC (stop-the-world) pauses. - **Operations** — what metrics and logs you would add, and what the system does when Redis is unavailable. Deliverables: a precise algorithm/protocol description, the Redis data model (keys, values, TTLs), and the edge-case behavior. ```hint Where to start Model leadership as a **lock with a TTL** (a *lease*): `SET key value NX PX T`. `NX` gives you mutual exclusion; the `PX` TTL gives you automatic failover when the holder stops renewing. The hard part is not acquiring — it's renewing and releasing *safely*. ``` ```hint The renewal trap A blind `PEXPIRE` on renewal is a bug: by the time you renew, you may have *already* lost the lease (it expired during a pause and someone else acquired it), and you'd be extending **their** lock. Make renew and release **compare-and-act atomically** — embed a unique owner id in the value and check it. What Redis primitive lets you run "check value, then act" as one indivisible operation? ``` ```hint The case a lease alone can't cover Even an ownership-checked lease has a gap: a leader can pass its "am I leader?" check, then suffer a long GC pause, lose its lease, watch a new leader get elected, and *then* wake up and complete a stale write. Think about pushing enforcement **down to the protected resource** — a monotonically increasing token the resource uses to reject writes from a superseded leader. ``` ```hint Clock skew Decide whose clock you actually depend on. If expiry is judged by **Redis's own clock** and instances only use **local monotonic timers** to decide *when* to renew, you need no cross-instance clock synchronization — and a skewed local clock affects responsiveness, not safety. Be honest about the one residual clock assumption that remains. ``` ### Constraints & Assumptions - **N** stateless instances (think tens, e.g. $N \le 50$); each runs the identical election loop. - Single primary Redis endpoint. Redis is **not** a CP consensus system — be explicit about where that bounds the safety guarantee. - The coordination load is tiny: a few small keys and a low rate of renew/acquire operations. Throughput is *not* the scaling concern; **failover latency and safety** are. - Network partitions, packet loss, and process (GC/STW) pauses are all in scope. - It is always acceptable to have **zero** leaders briefly; it is **never** acceptable to have **two** leaders doing conflicting work. Safety dominates liveness. - No synchronized wall clocks across instances may be assumed. ### Clarifying Questions to Ask - What does the singleton task actually *do* — does it write to an external resource (DB, object store, queue) that could enforce a fencing token, or is it pure in-memory work where idempotency is the only lever? - What is the failover SLO — how many seconds of "no leader" is tolerable after a hard crash? (This directly sets the TTL.) - How catastrophic is a brief two-leader window — is the work *idempotent*, or would a duplicate/stale action corrupt data? - Is the Redis endpoint truly single-primary, or is there a replica with async failover I must reason about? - Do followers need near-instant promotion (Pub/Sub handover) or is TTL-bounded failover sufficient? ### What a Strong Answer Covers - **The core mechanism**: one Redis key as a TTL'd lock, `SET NX PX`, with mutual exclusion and auto-failover both falling out of `NX` + TTL. - **A safe renewal/release protocol**: ownership-checked, atomic compare-and-renew / compare-and-delete (Lua), and a clear three-way distinction between renew succeeding, renew *losing* ownership, and renew *erroring* (couldn't reach Redis) — and why those must be handled differently. - **Fencing tokens**: a monotonic epoch enforced at the resource, and a clear statement of why a timeout-based lease *alone* cannot guarantee at most one *effective* leader (the GC-pause / async-failover windows). - **TTL sizing reasoning**: the $R \ll T$ relationship, the failover-vs-stability tradeoff, and how it bounds failover time. - **Clock-skew honesty**: which clock the design actually depends on, why no cross-instance sync is needed, and the residual single-node Redis-clock risk. - **Failure-mode table**: precise behavior for crash, partition, GC pause, Redis-down, replica failover, clock jump, and thundering herd — failing *closed* (everyone becomes a follower) when Redis is unreachable. - **Observability**: leader gauge, the three-way renew outcome counters, time-to-elect, flap rate, downstream fencing rejections, and the corresponding alerts. - **The honest caveat**: Redis isn't CP; for safety-critical singletons the same protocol over etcd/ZooKeeper is the right backing store, and with Redis fixed, fencing + idempotency bound the blast radius. ### Follow-up Questions - The leader does `GET`/check, then a long GC pause, then performs its write. Walk through exactly how a fencing token prevents data corruption — and what happens if the protected resource *cannot* fence. - The Redis primary fails over to an async replica that hadn't yet replicated the lock. Two instances now believe they're leader. What breaks, and what (if anything) saves you? - How would **Redlock** (acquiring across $N$ independent Redis masters with a majority quorum) change the safety story, and why is it still not a substitute for fencing? - You observe leadership changing dozens of times per minute (flapping). What are the likely causes, and which knobs do you turn?