Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Clock-Skew Resilient Distributed
Lease & Rate-Limiter Service.

Use a Raft-backed Lease Coordinator issuing monotonic fencing tokens with server-side monotonic TTLs, paired with local CLOCK_MONOTONIC token-bucket caches on API gateways.
Start the journey7 stages
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

Design a distributed leader-lease and API rate-limiting control plane serving 50K QPS across 3 availability zones where host NTP clocks can drift up to +/- 500 ms or step backward on VM migration, guaranteeing zero split-brain storage writes and zero rate-limiter freezes.

From patterns to decisions.

Use a Raft-backed Lease Coordinator issuing monotonic fencing tokens with server-side monotonic TTLs, paired with local `CLOCK_MONOTONIC` token-bucket caches on API gateways.

Full walkthrough · 7 stages
01
STAGE 01 · FAILURE MODELfoundation

Quantifying +/- 500 ms Clock Drift & Split-Brain Windows.

Assume 50,000 QPS across 3 AZs, 10-second leader leases, and worst-case +/- 500 ms host clock drift plus occasional -450 ms NTP steps.

Without fencing, a 1-second skew + 2-second GC pause allows two nodes to believe they hold the active lease simultaneously.

STAGE 01 · FAILURE MODEL

Drift & Split-Brain Budget

DriftIngress / BaselineSplit-Brain BudgetScale ConstraintValidation GateBottleneck SignalProduction OutcomeTarget SLAexposes

1.Stage Objective: Define the exact clock-skew failure scenarios and latency SLAs.

2.Level (Foundation): Assume 50,000 QPS across 3 AZs, 10-second leader leases, and worst-case +/- 500 ms host clock drift plus occasional -450 ms NTP steps.

3.Operational Invariant: Physical clock skew + GC pauses make wall-clock lease checks unsafe without consensus fencing.

Caption: Physical clock skew + GC pauses make wall-clock lease checks unsafe without consensus fencing.

02
STAGE 02 · LEASE COORDINATORfoundation

Single-Authority Raft Leases with Monotonic TTLs.

Clients acquire a 10s lease from the Raft group. The Raft leader records acquired_mono = monotonic_now() and renews/expires strictly against its own monotonic clock.

On Raft leader failover, the new leader waits one full max_lease_duration (10s) or enforces an explicit fencing_token increment before granting new leases.

STAGE 02 · LEASE COORDINATOR

Raft Monotonic Lease Engine

Raft MonotonicLease EngInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

1.Stage Objective: Eliminate cross-node clock comparison by evaluating lease expiry on the Raft leader's monotonic clock.

2.Level (Foundation): Clients acquire a 10s lease from the Raft group. The Raft leader records `acquired_mono = monotonic_now()` and renews/expires strictly again

3.Operational Invariant: Evaluating lease expiry on the Raft leader's monotonic clock removes cross-node skew.

Caption: Evaluating lease expiry on the Raft leader's monotonic clock removes cross-node skew.

03
STAGE 03 · FENCING TOKEN GATEintermediate

Atomic Compare-and-Set Fencing at the Storage Layer.

class FencedStorage:
    def __init__(self) -> None:
        self._max_token_by_resource: dict[str, int] = {}
        self._data: dict[str, bytes] = {}

    def write(self, resource_id: str, fencing_token: int, payload: bytes) -> None:
        if fencing_token <= 0:
            raise ValueError('fencing_token must be positive')
        current_max = self._max_token_by_resource.get(resource_id, 0)
        if fencing_token < current_max:
            raise PermissionError(
                f'Stale fencing token {fencing_token} < active {current_max}'
            )
        self._max_token_by_resource[resource_id] = fencing_token
        self._data[resource_id] = payload
STAGE 03 · FENCING TOKEN GATE

Storage Fencing Validation

Storage FencingValidatiValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

1.Stage Objective: Implement deterministic stale-leader rejection in the storage engine.

2.Level (Intermediate): class FencedStorage:

3.Operational Invariant: Rejecting any write with token < max_seen_token guarantees safety even under arbitrary clock jumps.

Caption: Rejecting any write with token < max_seen_token guarantees safety even under arbitrary clock jumps.

04
STAGE 04 · MONOTONIC RATE LIMITERintermediate

Clock-Skew-Safe Token Leasing at 50K QPS.

API gateways lease token batches (e.g., 500 tokens for 1s) from Redis using server-side PEXPIRE (time.monotonic() on Redis), and refill local in-memory buckets strictly with time.monotonic().

Even if a gateway host's UTC clock jumps -5 seconds, local monotonic() advances smoothly.

STAGE 04 · MONOTONIC RATE LIMITER

Gateway Token-Batch Leasing

Gateway Token-BatchLeasHot PathCore EnginePartition / IndexGuard & VerifyLatency / RAM BoundProduction OutcomeScaled Statebounds

1.Stage Objective: Keep API gateway rate limiters fast and immune to NTP backward jumps.

2.Level (Intermediate): API gateways lease token batches (e.g., 500 tokens for 1s) from Redis using server-side `PEXPIRE` (`time.monotonic()` on Redis), and refill

3.Operational Invariant: Local monotonic buckets + Redis server-side PEXPIRE sustain 50K QPS with zero NTP stalls.

Caption: Local monotonic buckets + Redis server-side PEXPIRE sustain 50K QPS with zero NTP stalls.

05
STAGE 05 · RENEWAL SAFETY MARGINadvanced

Sizing Heartbeat Renewal vs. Bounded Clock Drift.

Renew 10s leases at T/3 (every 3.3s) using monotonic() elapsed time, and self-fence (step down immediately) if a renewal RPC fails or takes > T - 2 * max_drift_margin.

STAGE 05 · RENEWAL SAFETY MARGIN

Self-Fencing Renewal Window

Self-FencingRenewal WinFault TriggerCore EngineIsolation BoundaryGuard & VerifyFallback / QuarantineProduction OutcomeProtected Pathisolates

1.Stage Objective: Prevent premature lease loss during minor clock-rate drift or network jitter.

2.Level (Advanced): Renew 10s leases at `T/3` (every 3.3s) using `monotonic()` elapsed time, and self-fence (step down immediately) if a renewal RPC fails or ta

3.Operational Invariant: Renewing at T/3 and stepping down before expiry bounds overlap even under network stalls.

Caption: Renewing at T/3 and stepping down before expiry bounds overlap even under network stalls.

06
STAGE 06 · AUDIT ORDERINGadvanced

Hybrid Logical Clocks (HLC) for Cross-AZ Event Logs.

Attach an HLC (physical_ms, logical_counter) to every lease grant and fenced write. When a node receives a message with msg_hlc >= local_hlc, it advances local_hlc causally, ensuring audit logs sort deterministically.

STAGE 06 · AUDIT ORDERING

HLC Causal Audit Ordering

HLC Causal AuditOrderinCheckpoint / LogCore EngineReplay / SyncGuard & VerifyConsistency GateProduction OutcomeRecovered Stateverifies

1.Stage Objective: Order audit events causally across 3 AZs despite +/- 500 ms physical skew.

2.Level (Advanced): Attach an HLC `(physical_ms, logical_counter)` to every lease grant and fenced write. When a node receives a message with `msg_hlc >= local_

3.Operational Invariant: Hybrid Logical Clocks preserve causal event ordering across AZs despite physical clock skew.

Caption: Hybrid Logical Clocks preserve causal event ordering across AZs despite physical clock skew.

07
STAGE 07 · CHAOS & TELEMETRYadvanced

Testing with `libfaketime` & Monitoring Fencing Rejections.

Run chaos tests injecting -500 ms and +5 s clock jumps via libfaketime / chronyc. Alert on stale_fencing_token_rejections_total, raft_lease_stepdowns_total, and host_ntp_offset_ms > 50.

STAGE 07 · CHAOS & TELEMETRY

Chaos Clock-Jump Verification

Chaos Clock-JumpVerificTelemetry SignalCore EngineSLO ThresholdGuard & VerifyCircuit BreakerProduction OutcomeSafe Degradationtrips

1.Stage Objective: Verify clock-skew resilience in CI and alert on real-world NTP anomalies.

2.Level (Advanced): Run chaos tests injecting `-500 ms` and `+5 s` clock jumps via `libfaketime` / `chronyc`. Alert on `stale_fencing_token_rejections_total`, `

3.Operational Invariant: Automated clock-jump chaos tests and fencing-rejection metrics validate production safety.

Caption: Automated clock-jump chaos tests and fencing-rejection metrics validate production safety.

Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does the storage layer still need a `fencing_token` check even if the Raft coordinator uses a monotonic clock?

Recommended Learning Flow