Conditional Writes: Building a Lock Out of Single-Key Compare-and-Set

One atomic operation is enough to start

An object store offers no transactions and no locks, but it does offer a write whose outcome depends on the current state of the key. The mechanism is the HTTP precondition, evaluated by the service at the moment of the write rather than by the client beforehand. Two forms matter: a condition that the key must not already exist, and a condition that the key’s current entity tag or generation must equal a value the client supplies.

The first form is the create-if-absent primitive. A client sends a PUT with a header asserting that no object currently exists at that key; if another writer got there first, the service returns a failure, either 412 Precondition Failed or a 409 in the S3 conditional-write form, and stores nothing. Exactly one of a set of concurrent writers succeeds, regardless of how many are racing and regardless of network reordering, because the check and the write are one operation inside the store.

The second form is compare-and-swap. The client reads the key, notes its entity tag, computes a new value, and writes with a precondition that the tag still matches. If any other writer changed the object in between, the tag has changed and the write fails. That is the classic optimistic concurrency loop: read, compute, attempt, and on failure re-read and retry. The loop terminates only if contention is bounded, and under sustained contention it livelocks, which is why the retry needs a backoff and why the pattern is suited to coordination records rather than to hot data.

Neither primitive existed on all services at the same time. S3 gained general conditional writes later than the others and, in its first form, supported only the create-if-absent condition on PUT, with entity-tag preconditions on GET and DELETE; the ability to condition a PUT on an entity tag arrived afterwards. Any design that depends on compare-and-swap should establish which of the two forms the target service actually supports, because the create-if-absent form is sufficient for a lock but not for updating a counter.

A lease is a key with an expiry encoded in its value

The standard construction for mutual exclusion on top of create-if-absent is a lease object. A writer that wants the lock attempts to create the key with a body naming itself and a deadline. On success it holds the lock until the deadline; on failure it reads the existing lease, compares the deadline to the current time, and if the lease has expired it attempts to take over.

Taking over an expired lease is where the subtlety lives. A naive takeover, which reads the expired lease and then writes a new one, races with another writer doing the same thing, and both can believe they won. The correct form is a conditional write against the entity tag of the expired lease: read it, and write the replacement only if the tag is unchanged. Exactly one takeover succeeds; the other re-reads and finds a fresh, unexpired lease.

Expiry does not, by itself, revoke the previous holder. A holder whose lease expired because it was paused, or because its clock disagreed with the service’s, may still be executing. The lease is therefore an optimisation that bounds the frequency of conflicting work, not a guarantee that conflicting work cannot happen. Every design that uses one must make the protected operation idempotent or verify ownership at the point of effect. The classic treatment of this problem, including the need for fencing tokens that the protected resource checks, is Chubby’s, and it applies unchanged to an object-store lease.

A minimal version of the takeover loop, using the entity tag as the compare value:

import time

class LeaseStore:
    """Wraps a store exposing get(key) -> (body, etag) and
    put_if_match(key, body, etag) -> new_etag or None."""

    def __init__(self, store, key, ttl):
        self.store, self.key, self.ttl = store, key, ttl

    def acquire(self, owner):
        deadline = time.time() + self.ttl
        body = f"{owner} {deadline:.3f}"
        # Create-if-absent: succeeds only for the first writer.
        if self.store.put_if_absent(self.key, body):
            return deadline
        old, etag = self.store.get(self.key)
        _, expiry = old.split()
        if float(expiry) > time.time():
            return None                      # held by someone else
        # Expired: replace only if nobody else replaced it first.
        if self.store.put_if_match(self.key, body, etag):
            return deadline
        return None                          # lost the takeover race

The two failure returns are not the same condition: the first means the lease is live, the second means another writer took it during the race. A caller that retries should distinguish them, since only the second is worth an immediate retry.

Publication: making a multi-object write look like one

The other use of the primitive is to make a set of object writes appear to commit together. The pattern is a pointer object. Data objects are written under keys that include a generation number or a random suffix, so no reader is looking at them; when all are present, a single small object is written whose body names the generation. Readers read the pointer first and then the objects it names. The commit is the pointer write, and it is atomic because it is a single-key write.

That much is ordinary. The part that requires a conditional write is preventing two writers from publishing different generations at once, and preventing a publisher from overwriting a pointer that a newer publisher already advanced. Both are handled by conditioning the pointer write on the entity tag read at the start, or by conditioning it on absence when the pointer is expected not to exist yet. A writer that loses the race must discard its generation rather than retry blindly, because the other writer’s generation is already the committed one and its objects may already be the ones readers are using.

This is the mechanism behind table formats that commit to object storage, and its consequences, namely snapshot isolation across readers, the need to garbage-collect superseded generations, and the difference between a pointer and a manifest list, are worked through in atomic commit over object stores.

What conditional writes cannot do

The primitive is per key, so any invariant spanning two keys has no atomic expression. A counter that must not exceed a limit is expressible because a counter is one key: read, compare, write with the tag. A pair of counters that must sum to a constant is not, unless they are packed into one object, and packing them means every update rewrites the whole object, which reintroduces the contention the design was trying to avoid.

There is no wait primitive. A failed precondition returns immediately, so any caller that wants to block until a lock is free must poll, and polling costs requests. The polling interval is a trade between the latency of acquisition and the request rate, and the request rate is subject to the per-prefix limits described in request rate limits and key prefix partitioning. A lease that is polled every 100 ms by a hundred workers is a thousand requests per second aimed at one key, which is not a workload the partition holding that key was sized for.

Finally, conditional writes interact with versioning in a way worth stating. In a versioned bucket, a create-if-absent condition applies to the absence of a current version, so a key whose current version is a delete marker counts as absent for the purpose of the condition, a subtlety that can let a writer “create” a key that has history. The state machine that produces this behaviour is described in versioning and delete markers. A lock key in a versioned bucket should be treated as a lock key whose history is irrelevant, and its entity tag, not its version list, is the value to condition on.

The honest summary is that an object store supplies one atomic operation, conditional replacement of a single key, and that this is enough to build locks and commit pointers, which are the two coordination structures most systems actually need. Everything else, including anything that resembles a transaction across keys, has to be reduced to one of those two or moved to a service that offers a real transaction.