Leases and Time to Live

Distributed systems constantly hand out things that should not last forever: a cached copy of data, a login session, the right to process a job, the role of leader. If such a grant never ends, a crash or a forgotten cleanup leaves it in place indefinitely. Two simple ideas solve this by attaching a clock: a time to live (TTL) makes data expire, and a lease makes a permission expire. This topic explains both, with caching and databases as the main examples. It builds on Caching.

Time to live

A TTL is a lifetime attached to a piece of data. When it runs out, the data is treated as gone. Typical uses:

• Cache entries, so a stale value disappears after a known time even if an invalidation was missed.
• Sessions and tokens, so an abandoned login stops working on its own.
• Temporary records in a database, such as one-time codes, rate-limit counters or old event data.

Choosing a TTL

The TTL is a trade-off between freshness and load:

• Short TTL: data is fresher, but more requests miss and go to the database.
• Long TTL: fewer misses, but a stale value can survive longer.

Choose it from how stale the data is allowed to be: seconds for a stock count, minutes for a profile, hours or days for something that rarely changes. Where correctness matters, do not rely on the TTL alone; invalidate on write and use the TTL as the safety net.

Add jitter

If many keys are cached at the same moment with the same TTL, they all expire at the same moment, and all their requests hit the database together. Adding a small random amount to each TTL, for example 60 seconds plus up to 10 seconds, spreads the expiries out and avoids the spike.

Expiry is not instant

Stores remove expired data in different ways, and it matters:

• Redis never returns an expired key. Its documentation explains that keys "are expired in two ways: a passive way and an active way": an expired key is removed when someone accesses it, and a background process also samples and removes expired keys.
• DynamoDB TTL is a clean-up tool, not a precise timer: it "automatically deletes expired items within a few days of their expiration time, without consuming write throughput". Until then, queries can still return expired items, so applications must filter them out by checking the expiry time themselves.

The rule: use database TTL to stop old data piling up, not to enforce a deadline exactly.

Leases

A lease is a permission with an expiry time: "you may do X until time T". If the holder needs more time, it renews the lease before it expires. If the holder crashes, the lease simply runs out and someone else can take over. Nothing has to detect the crash.

Leases in a cache

In the Caching topic, two problems were left open: the stale set, where a slow reader writes an old value into the cache after it was invalidated, and the thundering herd, where many requests miss the same popular key at once and all query the database. Facebook's memcache uses leases to solve both.

• On a miss, the cache gives the client a lease: "a 64-bit token bound to the specific key the client originally requested".
• To fill the cache, the client must present that token. If the key was deleted in the meantime, the token is no longer valid and the old value is refused. This removes the stale-set race.
• For popular keys, the cache hands out a token "only once every 10 seconds per key". Other clients that miss are told to wait briefly, and by the time they retry, the first client has usually filled the value. Only one request goes to the database instead of thousands.

The measured effect, from the paper: for keys prone to this problem, "Without leases, all of the cache misses resulted in a peak database query rate of 17K/s. With leases, the peak database query rate was 1.3K/s."

Example: keeping product prices correct

A shop caches product details, including the price, so product pages load quickly. An admin then lowers a price from 500 to 450. Without care, shoppers can keep seeing 500 long after the change, and the cart can disagree with the product page.

1. t1: Shopper A's request misses the cache. The cache issues lease 7 for the product key, and A starts reading the price, 500, from the database.
2. t2: Before A finishes, the admin saves the new price, 450, in the database. The application then deletes the product's cache key. The delete also cancels lease 7.
3. t3: Shopper A, slower, tries to store 500 in the cache with lease 7. The cache refuses, because lease 7 is no longer valid. The old price never reaches the cache.
4. t4: Shopper B's request misses, gets a new lease, reads 450 from the database and caches it. From now on everyone sees 450.

Without the lease, step 3 would succeed and the cache would serve the old price to everyone until its TTL ran out. Three rules complete the picture:

• Delete the key whenever the price changes, after the database update has committed.
• Keep a TTL as well, so that even a missed delete corrects itself within a known time.
• Never charge from the cache. At checkout, read the price from the database. The cache may show a price; only the database decides what is charged.

TTL works everywhere; leases need support

The two tools differ in where you can use them:

• TTL is universal. Redis (EXPIRE, or SET with an expiry), Memcached (an expiry time on every set), CDNs and browsers (the Cache-Control: max-age header), and databases such as DynamoDB and Cassandra (per-item TTL) all support it. Nothing extra has to be built.
• Leases need support from the cache itself. The cache must hand out a token on a miss, remember it, cancel it on delete and check it on every fill. Facebook added this mechanism to its own memcache; standard deployments of Redis and Memcached do not issue cache leases out of the box.
• Where leases are not available, emulate them. Use a compare-and-set operation (store only if the value has not changed since it was read; Memcached offers this as cas), or store a version number with each value and refuse to overwrite a newer version with an older one.

So the practical rule: put a TTL on every cache entry, because it works everywhere and bounds how long any mistake can last. Add leases, or one of their emulations, only for data where a stale value is costly, such as prices, stock levels or permissions.

Leases as locks

Leases are also how distributed systems hand out exclusive roles: which worker processes a job, which server is the leader, who may write a file.

A plain lock held by a crashed worker blocks everyone forever. A lease frees itself. Two rules make leases safe:

• Renew early, stop if you cannot. The holder renews well before expiry, and if a renewal fails, it stops working at once, because someone else may soon hold the lease.
• Guard against late writes. A holder can be paused (a long garbage collection, a stalled machine) and wake up after its lease has passed to someone else, still believing it holds it. The fix is a fencing token: every new lease gets a higher number, every write carries it, and storage rejects writes with a lower number than one it has already seen.

Clocks

Leases and TTLs depend on time, and different machines' clocks never agree exactly. Keep lease periods well above any expected clock difference, measure expiry with the local clock's elapsed time rather than comparing timestamps from different machines, and leave a margin: the holder should consider its lease over a little before the issuer does.

A real system: Facebook's memcache

The figures above all come from Scaling Memcache at Facebook (NSDI 2013). The paper introduced leases "to address two problems: stale sets and thundering herds", describes the 64-bit tokens and the once-per-10-seconds rule, and reports the drop in peak database queries from 17,000 to 1,300 per second for susceptible keys. Since databases are provisioned for peak load, the paper notes, that reduction is a significant efficiency gain.

How to use this in an interview

• Give every cache entry a TTL with jitter, and say what staleness the TTL allows.
• For a hot key, mention the thundering herd and how a lease or a single refill request prevents it.
• For any exclusive role (a job, a leader, a lock), use a lease with renewal, not a plain lock, and mention fencing tokens if correctness depends on it.

Implementing it in your project

• TTL on every cache key. In Redis, SET product:42 "..." EX 600 stores a value for 600 seconds; add a few random seconds per key as jitter. In Spring, configure a TTL per cache name.
• A simple lock lease in Redis. SET lock:job42 <unique-id> NX PX 30000 takes the lock only if nobody holds it, and it expires on its own after 30 seconds. Release it only if the value is still your own unique ID (checked and deleted together in a small Lua script), so you never release a lease that expired and passed to someone else. Renew it before it runs out if the work takes longer.
• Emulating cache leases. Where the cache has no leases, store a version number with each cached value and refuse to overwrite a newer version, or use Memcached's cas (check-and-set) so a fill succeeds only if the key has not changed since it was read.
• Prices and stock: delete the key on every change, keep a short TTL, and read from the database at checkout.

---

Sources and credibility

Everything above is written from scratch; the quotes come from the sources below, attributed where used.

Primary (highest confidence)

• Scaling Memcache at Facebook, Nishtala et al., USENIX NSDI 2013, section 3.2.1. Source of the lease design, the 10-second rule and the 17K/s to 1.3K/s measurement.
• EXPIRE, Redis documentation. Source of the passive and active expiry description.
• Time to Live (TTL), Amazon DynamoDB developer guide. Source of the "within a few days" deletion behaviour.

Method

• TTL jitter, lease renewal, fencing tokens and the clock guidance are standard distributed-systems practice; the explanations are our own.

On copyright: the diagrams on this page were drawn for this article, and the explanations are original. Quoted phrases are short and attributed.