Lease Safety Margins Under Clock Drift

A lease is safe when no client can believe it holds a grant after the service has given that grant to someone else. The service and the client measure the interval with different clocks, so “after” is not a single instant. It is an interval whose width is set by the error between the two clocks, and the safety margin is the amount of extra time the service waits before reassigning. The basic grant-and-expiry mechanism is simple; the margin is where the difficulty concentrates. Getting that margin wrong is one of the few ways to build a coordination system that is unsafe in a way no test will reveal.

The two deadlines

Suppose the service grants a lease of duration D at server time t0. The server intends the grant to end at t0 + D. The client receives the grant at some later instant, reads its own clock as c0, and computes its deadline as c0 + D. The client’s clock differs from the server’s by an offset θ and by a drift that accumulates at a rate bounded by ρ on each side. Over an interval of length D, the client’s measured elapsed time can differ from the server’s by at most θ plus roughly 2ρD, plus the resolution of both clocks.

For safety, the client’s deadline must not be later than the server’s. If the client’s clock runs fast relative to the server’s, the client’s c0 + D corresponds to a server time earlier than t0 + D, which is safe: the client stops early. If the client’s clock runs slow, its deadline corresponds to a server time later than t0 + D, and there is an interval in which the client still believes it holds the grant after the server considers it ended. That interval is the danger, and its length is bounded by the offset error plus the accumulated drift.

The service’s margin is the fix. Rather than treating the grant as ended at t0 + D, the service refuses to grant the same resource to a new holder until t0 + D + M has elapsed on the server’s clock, where M exceeds the maximum by which a client’s deadline can lag the server’s. Within that margin, the only client that believes it holds the grant is the original holder, and the resource is idle. The cost is that recovery from a dead holder takes D + M rather than D.

Sizing the margin from the drift bound

The margin has three components, and each has a different source. The first is the initial offset between the clocks, which is bounded by whatever synchronization mechanism the deployment uses. A client that synchronizes with a network time protocol server over a wide-area path can have an offset of tens of milliseconds, and the uncertainty in that offset is what the protocol reports as its root dispersion. A client on the same host as the service, or a client that synchronizes over a local network, has an offset in the microseconds or less.

The second is the drift accumulated during the lease. A typical crystal oscillator has a frequency tolerance of some tens of parts per million, and the temperature and age of the crystal widen that. A bound of 100 parts per million is a conservative figure for commodity hardware; over a one-second lease it contributes 100 microseconds, and over a ten-second lease it contributes one millisecond. The contribution is linear in the lease duration, which is why long leases need proportionally larger margins.

The third is quantization. Timers fire at a granularity, and a service that checks expiry on a timer tick can be late by up to one tick. A client that reads its clock has a resolution, and a service that rounds the deadline down rather than up introduces an error of one unit. Both are small but both are systematic, and both must be added rather than assumed away.

Putting the components together, a margin of M = θ_max + 2ρD + q covers the worst case, where θ_max is the maximum absolute offset error, ρ is the drift-rate bound per clock, and q is the combined quantization. The factor of two on the drift accounts for the client and the server drifting in opposite directions. If the service’s clock is also subject to steps, from a time synchronization daemon correcting a large offset, the margin must additionally cover the largest step the daemon can apply, or the service must avoid stepping its clock while leases are outstanding. A step backwards is the dangerous direction: it makes the server’s elapsed-time measurement shorter than real time and can cause a reassignment before the holder’s deadline.

/* Server-side expiry check. The grant is reassignable only after the full
 * interval plus the margin, measured on a monotonic clock. */
struct grant { uint64_t granted_ns; uint64_t duration_ns; uint64_t margin_ns; };

static int reassignable(const struct grant *g, uint64_t now_ns)
{
    uint64_t end = g->granted_ns + g->duration_ns + g->margin_ns;
    if (end < g->granted_ns)          /* overflow: treat as never */
        return 0;
    return now_ns >= end;
}

The use of a monotonic clock in that check is not incidental. A wall clock can be stepped by an administrator or by a synchronization daemon, and a grant that was issued before a backwards step can appear to have been issued in the future. Monotonic clocks do not step, though their rate can still be adjusted, which is why the drift term remains even when the clock is monotonic.

Why the client must not extend its own deadline

A client that renews a lease is granted a new deadline, and it is tempting to treat the renewal as extending the original. That is only safe if the renewal is acknowledged before the original deadline, because the new grant starts at the server’s renewal instant, not at the client’s request instant. A client that sends a renewal at its deadline minus one millisecond and receives the response after the deadline has, from the server’s point of view, been granted a new lease that begins after the old one ended. Whether that is a continuation or a new grant depends on the service’s policy, and the client must not assume continuation unless the response says so.

The safe client protocol is to treat each grant as independent: a renewal returns a new deadline, the client adopts it, and the old deadline is forgotten. The client’s own safety rule remains that it must stop at the deadline it currently holds, not at the deadline it hopes to receive. A client that continues working while a renewal is in flight, past its current deadline, is exactly the stale holder the margin is designed to contain, and the margin will contain it only if the client’s deadline is no later than the server’s.

There is a corresponding rule for the service: it must not accept a renewal for a grant that has already been reassigned. If the grant has lapsed and the resource has a new holder, a late renewal must fail, not silently resurrect the old grant. A service that accepts late renewals defeats the margin entirely, because the old holder can extend its belief indefinitely while the new holder is writing.

The interaction with session timeouts

Coordination services often implement leases as sessions, and the session timeout plays the role of D. The service’s expiry of a session is the reassignment point for everything the session owns, and the margin is the difference between the client’s timeout and the server’s. Session expiry is therefore a lease expiry wearing a different name, with the same obligation on the client to stop at its own deadline rather than at the moment it learns of the loss. If both sides use the same numeric timeout with no margin, the client and the server can disagree about the moment of expiry by the clock offset, and the client can act for that offset after the server has cleaned up.

The common implementation avoids the problem by making the client’s timeout shorter than the server’s, or by having the server treat the session as expired only after the client’s declared timeout plus a grace period. Both encode the same asymmetry. The grace period must be at least the offset bound, and it should be visible in the service’s configuration rather than buried in a constant, because it is the parameter that determines how long a crashed client’s state persists and therefore how quickly the system recovers.

The session timeout also has a lower bound set by the renewal cost. A client that renews at one third of the timeout can lose two renewals before expiry, which tolerates a brief network problem; a timeout short enough that a single lost renewal expires the session produces false expiries under ordinary jitter, and each false expiry costs a rebuild of the client’s state. The lower bound is therefore a function of the network’s latency distribution, and the upper bound is a function of how long the system can tolerate a dead holder’s state persisting. The gap between them is the design space, and it is often narrower than expected.

Detecting that the margin is wrong

A margin that is too small produces a safety violation, and safety violations are usually silent: two clients write, one write is lost or overwritten, and no error is reported. A margin that is too large produces slow recovery, which is visible but often attributed to the failure rather than the margin. Neither is easy to diagnose from the outside.

What can be measured is the distribution of clock offsets, which the synchronization protocol itself reports, and the distribution of renewal latencies, which the client can record. Comparing the maximum observed offset against the configured margin tells whether the margin is adequate for the observed conditions; comparing the renewal latency distribution against the timeout tells whether the timeout is long enough to avoid false expiries. Both measurements are of the system’s own behaviour, not of the application, and both are cheap to collect.

The harder case is a clock that steps. A margin computed for drift does not cover a step, and a service that does not exclude steps from its lease clock will eventually violate safety on a host whose clock is corrected by a large amount. The mitigation is to use a monotonic clock for lease accounting, to bound the maximum step the synchronization daemon can apply, or to invalidate outstanding grants when a step is detected. The last is the most conservative and the most disruptive, and it is the one that makes the safety argument complete.