Designing a Correct Distributed Lease Service: Tenure on Raft

Most distributed outages blamed on “capacity” are really coordination failures in disguise. The hard question is not whether the system can do more work; it is whether every participant can still agree on who is allowed to act, for how long, and with what authority when clocks drift, leaders fail, and delayed messages reappear. Tenure is interesting in that context because it frames lease ownership as an explicitly replicated correctness boundary rather than as an incidental feature in a larger storage system, and the public codebase and design docs make that framing concrete rather than purely rhetorical (Gray & Cheriton, 1989; Ongaro & Ousterhout, 2014).

That is the reason to treat a distributed lease service as infrastructure in its own right. Once multiple workers, schedulers, controllers, or reconcilers can attempt the same action, correctness depends on making ownership explicit and making ambiguity expensive. Throughput matters, but throughput without coordination discipline just lets a system violate invariants faster.

Distributed Systems Fail Because of Coordination, Not Just Throughput

Plenty of systems can survive high request rates. Far fewer survive contradictory decisions made under partial failure. The dangerous cases are familiar: two controllers both believe they are primary, a scheduler retries after a timeout and races its own first attempt, or an old actor resumes after a pause and writes state long after its authority should have ended. None of those failures are solved by adding queue depth or CPU. They are solved by explicit coordination semantics and a replicated state machine that gives the system one defensible answer at a time (Schneider, 1990; Gilbert & Lynch, 2002).

The Core Primitive: “Who Is Allowed to Act Right Now?”

The right abstraction is not “distributed mutex” in the casual sense. It is time-bounded authority. A lease says that a named owner may act on a resource until an expiry chosen by the service. That is stronger than optimistic hope and narrower than general transaction processing. It is a deliberate answer to coordination problems where temporary exclusive authority is enough to serialize dangerous work such as leadership, scheduling, shard movement, failover orchestration, or singleton task execution (Gray & Cheriton, 1989).

That framing matters because it keeps the system honest. The service is not trying to solve every consistency problem. It is trying to solve the ownership problem precisely enough that other components can build on top of it.

Why Leases Instead of Locks

Traditional locks are often described as if ownership persists until explicit release. In a single process, that is fine. In a distributed system, it is a trap. Processes pause, packets disappear, leaders crash, and clients die while still “holding” something. A lease is explicit about the real world: ownership is temporary unless renewed. That boundedness gives the system a recovery path after client loss and prevents abandoned ownership from becoming permanent. Gray and Cheriton made the case decades ago: leases trade perpetual lock state for time-bounded authority that can be reclaimed safely when communication is imperfect (Gray & Cheriton, 1989).

Leases also force a sharper question about time. If ownership ends automatically, whose clock decides? If the answer is “each client decides for itself,” the service has already lost its correctness boundary. Lease semantics only become defensible when the system has a single authority for time evaluation during grant and renewal.

Why Tenure Exists as a Purpose-Built Lease Service Rather Than a General-Purpose KV Store

A general-purpose key-value store can often be made to approximate lease semantics, but that does not mean leases are its first-class contract. A purpose-built lease service can put the whole interface around ownership, renewal, release, expiry, and fencing tokens instead of treating them as conventions layered on top of arbitrary reads and writes. That narrower scope matters operationally because the hard part is not storing bytes. The hard part is ensuring that every state transition preserves single-owner meaning under failover and partial failure.

This is the architectural lens I am using for Tenure here. The important point is not hidden implementation detail; it is that Tenure is best understood as a lease-specific replicated state machine, not as a generic storage substrate with some helper APIs attached.

Why Scala Matters Here

That same design goal is also why Scala is a meaningful implementation choice rather than a cosmetic one. A lease service is mostly coordination logic: explicit states, guarded transitions, asynchronous replication steps, and failure handling that cannot afford ambiguous local mutation. Scala fits that shape well because it makes immutable modeling natural, keeps algebraic state representations practical, and gives the implementation a clearer way to express “these are the only valid lease states and transitions” instead of spreading that logic across ad hoc mutable objects.

That does not mean the language somehow proves distributed correctness on its own. Raft, fencing, quorum rules, and expiry semantics still do the real systems work. But Scala helps keep the local program honest. It is a strong fit for a correctness-first coordination service because immutability reduces accidental state drift, typed state modeling makes illegal transitions harder to smuggle in, and JVM-based asynchronous composition gives concurrency structure without forcing thread management to become the primary design surface (Scala, 2025). In a system like Tenure, that combination matters: the implementation language should make concurrency and correctness boundaries easier to express, not easier to blur.

sealed trait LeaseState
case object Free extends LeaseState

final case class Held(
  owner: OwnerId,
  expiry: Instant,
  token: Long
) extends LeaseState

def renew(
  current: LeaseState,
  requester: OwnerId,
  now: Instant,
  ttl: FiniteDuration
): Either[LeaseError, Held] =
  current match {
    case held: Held
        if held.owner == requester &&
           now.isBefore(held.expiry) =>
      Right(held.copy(expiry = now.plusMillis(ttl.toMillis)))

    case held: Held if now.isBefore(held.expiry) =>
      Left(LeaseOwnedByAnotherRequester)

    case _ =>
      Left(LeaseExpired)
  }

final class LeaseRecord {
  OwnerId owner;
  Instant expiry;
  long token;
  boolean free;

  void renew(OwnerId requester, Instant now, Duration ttl) {
    if (!free && owner.equals(requester) && now.isBefore(expiry)) {
      expiry = now.plus(ttl);
      return;
    }
    throw new LeaseException();
  }
}

If you want to compare that framing to the project itself, the public Tenure repository is worth reading alongside this post, especially its README, architecture spec, API contract, and request-flow diagrams. Those materials explicitly emphasize time-bounded ownership, leader-mediated expiration decisions, fencing tokens, and a replicated state-machine model, which is exactly the slice this post is focused on.

Raft-Based System Model

For a lease service, Raft is attractive because it gives a comprehensible path to a linearizable write leader backed by replicated log agreement. A client proposal becomes durable system state only after the leader appends it, replicates it to a quorum, and applies it in log order. That is exactly the shape a lease service wants: one write authority at a time, ordered state transitions, and an unambiguous rule for what counts as committed ownership (Ongaro & Ousterhout, 2014; Lamport, 2001).

Tenure: Lease Service Architecture (Raft-Based)

That model narrows ambiguity. Followers are not independent authorities; they are replicas that participate in commitment. Clients may talk to an API endpoint anywhere, but lease-changing commands must resolve to the leader path if the system wants one linearizable answer.

Lease Acquire — Linearizable Write Path

Lease State Machine

A lease service becomes intelligible when its state machine is narrow. There is some representation of free, some representation of held, and a small number of legal transitions. Complexity comes from the guards around those transitions: whether the caller is the current owner, whether the lease has expired according to service authority, and whether the transition should advance the fencing token.

Lease State Transitions

Time Model and Why Leader-Based Time Authority Matters

Leases force the system to mix consensus with time. Consensus orders state transitions, but expiry depends on a time calculation. The least dangerous model is to make the leader’s evaluation time authoritative for grant and renewal, then replicate the resulting expiry as part of committed state. That does not make clocks perfect. It makes the system’s decision process singular. Without that singularity, each client or follower can reinterpret lease validity independently, which is exactly how contradictory ownership appears.

Leader-Based Time Authority

This is also why lease design should stay modest about what time can prove. Spanner shows one disciplined answer to time uncertainty: expose bounds and incorporate them into the correctness model rather than pretending uncertainty is absent (Corbett et al., 2012). A lease service without globally synchronized clocks should make the simpler move: choose one authority for expiry decisions and make downstream consumers rely on fencing, not just on wall-clock optimism.

Fencing Tokens and Downstream Safety

Expiry is necessary, but it is not sufficient. A client can continue acting after its lease expired if it was partitioned, paused, or merely delayed. That is the classic zombie writer problem. The standard answer is a monotonically increasing fencing token issued on successful acquisition or handoff. Downstream systems must reject operations carrying an older token than the one they have already accepted. This turns lease history into an order, not just a timer.

Safe Lease Handoff

Preventing Zombie Writes

Failure Modes

A lease service is only as credible as its behavior under failure. This is where many hand-wavy designs collapse. Every interesting failure mode is really a question about whether the system can preserve ownership meaning when observation becomes incomplete.

Leader Failover and Lease Safety

If the old leader granted something that was not committed to a quorum, the new leader must behave as if that grant never became authoritative. That is harsh, but it is correct. Raft’s value here is that it gives a precise answer to what survives failover: committed state, not local memory (Ongaro & Ousterhout, 2014).

Partition Handling

That same discipline explains expiry and reacquire behavior. If a client disappears and later returns, the system should not care about the client’s narrative. It should care only whether the lease remained valid in replicated state and whether a later owner has already taken over. Delayed or stale clients are ordinary conditions, not special exceptions.

Closing on Ambiguity and Ownership

The real job of a distributed lease service is not to make mutual exclusion feel convenient. It is to make ownership ambiguity difficult to express. Raft helps by giving the system one ordered place where lease-changing decisions become authoritative. Leader-based time authority helps by ensuring expiry is computed from a single defensible perspective. Fencing tokens help by carrying that ordering into downstream state changes where stale actors would otherwise remain dangerous.

That is why Tenure is worth examining as a dedicated lease system. The value is not that it stores a bit saying “locked.” The value is that it treats temporary exclusive authority as replicated state with explicit failure behavior. If you want to inspect the current project directly, start with the Tenure codebase on GitHub and then follow the architecture and API documents from there. The architectural point is narrow and important: in distributed systems, ownership must be something the system can prove, not something a client merely believes.

What to Read Next

For the broader context around this kind of correctness work, see Distributed Systems Engineering: Correctness, Coordination, Reliability.

If you want the simpler entry points into the same cluster, start with Distributed Systems Interview Guide and What Is a Distributed Lock? (With Examples). Then continue with Fencing Tokens Explained and Distributed Lock Failure Modes in Production to connect lease theory to stale-writer incident handling. For the adjacent consensus comparison, continue with Raft vs Paxos vs EPaxos: A Practical Guide.

References

• Corbett, J. C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J. J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., Hsieh, W., Kanthak, S., Kogan, E., Li, H., Lloyd, A., Melnik, S., Mwaura, D., Nagle, D., Quinlan, S., Rao, R., Rolig, L., Saito, Y., Szymaniak, M., Taylor, C., Wang, R., & Woodford, D. (2012). Spanner: Google’s globally distributed database. In OSDI 2012. https://research.google/pubs/pub39966/
• Gilbert, S., & Lynch, N. (2002). Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News. https://cs-www.cs.yale.edu/homes/aspnes/pinewiki/attachments/DistributedSystems/brewers.pdf
• Gray, C., & Cheriton, D. (1989). Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. In SOSP 1989. https://dl.acm.org/doi/10.1145/74850.74870
• Lamport, L. (2001). Paxos made simple. SIGACT News. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
• Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm (Raft). USENIX ATC. https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
• Scala. (2025). Futures and Promises. https://docs.scala-lang.org/overviews/core/futures.html
• Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys. https://www.cs.cornell.edu/fbs/publications/smsurvey.pdf
• Robertson, R. (2026). Tenure [Software repository]. GitHub. https://github.com/richrobertson/tenure