Fair Lock Queues from Sequential Nodes

A lock built from compare-and-swap is unfair by construction. Every waiter races for the same cell, the winner is whoever the service linearizes first, and a client that loses can lose repeatedly while others acquire and release in front of it. Under sustained contention that is not merely a fairness problem; it is a throughput problem, because every loser burns a read and a failed conditional write per attempt, and the service absorbs all of that work.

The queue alternative replaces the race with an ordered wait. Each client announces its arrival by creating a node, and the service assigns the node a sequence number at the instant of creation. The order of the numbers is the order of arrival as the service linearized it, so the queue is fair in a precise sense: the client that arrives first is served first, regardless of which one retries fastest or has the lowest network latency.

The ticket is the node name

The mechanism relies on the service’s ability to return a value it assigned rather than one the client supplied. A sequential create takes a prefix and returns a full name with a zero-padded counter appended. Ten clients creating under the same prefix produce names whose suffixes sort lexicographically in creation order, provided the counter is zero-padded to a fixed width: 0000000009 sorts before 0000000010, while an unpadded 9 sorts after 10. The zero-padding is not cosmetic; without it, string ordering diverges from numeric ordering as soon as the counter crosses a digit boundary.

A client determines its position by listing the children of the lock path and sorting them by name. If its own node is the lowest, it holds the lock. If not, it does not need to watch the lock path, because a notification from the path says only that something changed, and the client would have to list again to find out whether the change affected its position. Instead it watches the node immediately preceding its own. That predecessor’s deletion is the only event that can make the client the lowest node, so a notification from it is exactly the signal the client needs, and it is a signal that cannot be missed: the deletion happens once, and the watch is registered before the client checks its position, so a deletion between the check and the registration fires the watch and forces a re-check.

// Acquire creates a ticket, then waits on its predecessor only. The watch is
// registered before the existence check, so a deletion in between fires it
// rather than being missed.
func (l *Lock) Acquire(ctx context.Context) error {
	me, err := l.createSequential(l.path + "/lock-")
	if err != nil {
		return err
	}
	for {
		kids, err := l.list(l.path)
		if err != nil {
			return err
		}
		sort.Strings(kids)
		i := slices.Index(kids, me)
		if i < 0 {
			return errNodeGone // session expired; we no longer hold a ticket
		}
		if i == 0 {
			l.ticket = me
			return nil
		}
		prev := kids[i-1]
		w, err := l.watchExists(l.path + "/" + prev) // returns a channel
		if err != nil {
			return err
		}
		if stillExists, _ := l.exists(l.path + "/" + prev); !stillExists {
			continue // predecessor already gone; re-check position
		}
		select {
		case <-w:
		case <-ctx.Done():
			return ctx.Err()
		}
	}
}

Why the predecessor and not the lock node

Watching the whole lock path is the naive version, and it produces a herd. When the holder releases, its node is deleted, every waiter’s watch on the path fires, every waiter lists the children, and every waiter discovers that it is not first and re-registers. With n waiters, each release generates n notifications and n list operations, and the service’s work per acquisition grows linearly with the queue length. The predecessor scheme generates one notification per release, to exactly one waiter, and one list operation by that waiter. The total service work per acquisition is constant rather than proportional to the queue.

The herd also has a latency effect that is easy to miss. When all waiters wake at once, they all issue list requests at once, and the service’s response to each is delayed by the load the others create. The waiter that would have been next is not necessarily the first to complete its list, so the ordering of the queue is preserved by the node names but the speed at which the next holder discovers its turn depends on contention it did not create. The predecessor scheme removes that coupling: the next holder is woken by a single notification and is the only client making a request.

There is a cost to the predecessor scheme, and it is the case where the predecessor’s node vanishes without the client noticing. If the predecessor’s session expires, its node is deleted and the watch fires, so the client re-lists and finds a new predecessor. If the predecessor’s node is deleted and recreated, the watch fires on the deletion, and the re-list may see the recreated node with a higher sequence number, which places it after the client rather than before. The client’s position improves, which is correct, because the original arrival is gone.

Abandonment and the orphaned ticket

A client that creates a ticket and then fails before acquiring the lock leaves a node behind. If the node is ephemeral, its session’s expiry removes it and the queue advances. If the node is persistent, it blocks the queue forever, and every subsequent client waits behind a ticket whose owner no longer exists. This is the single strongest argument for making queue nodes ephemeral, and it is why the lock recipes for these services use ephemeral sequential nodes rather than persistent ones.

The expiry does not make abandonment free. A client whose session expires while it holds the lock loses the lock, and any work it was doing under the lock continues without protection. A client whose session expires while it is waiting loses its place and must re-create a ticket at the back of the queue. Neither is detectable by the client until it tries to use its node and finds it gone, so a client must verify its ticket still exists before treating itself as the holder, and the check-then-use gap must be covered by a lease or by a fencing token that the resource itself checks.

The queue also has to handle a holder that dies without releasing. The ephemeral node is deleted when the session expires, the successor’s watch fires, and the successor acquires. The interval between the holder’s death and the successor’s acquisition is the session timeout plus the notification latency, which is why session timeouts for lock holders are usually set much shorter than for ordinary membership, and why some designs use a separate short lease for the lock itself rather than relying on the session’s timeout.

Reentrancy, and why it is not free

A client that already holds the lock and wants to acquire it again must not create a second ticket, because the second ticket sorts after the first and the client would wait for itself to release. The client must recognize that it is the holder, by checking whether the lowest node is one it created in this session, and treat the acquisition as a reentrant increment of a local count. The service does not help with this; it sees two nodes and no identity linking them beyond the session.

The local count is per-process state and does not survive a restart, which is consistent with the lock not surviving either. It does mean that a client that holds a lock, forks, and has both processes use the inherited handle will produce two independent counts and two releases for one acquisition, and the second release will delete a node that is not there or, worse, delete the successor’s node if the client’s deletion is by name and the name is reused. Deletion by the exact ticket name, and by a conditional delete that checks the version, avoids the second failure.

What the queue does not guarantee

The queue guarantees order of acquisition among clients that successfully created tickets. It does not guarantee that the holder is alive, that it will release in bounded time, or that the protected resource is consistent when the next holder arrives. It also does not guarantee that a client’s ticket reflects its arrival at the resource; a client that creates a ticket and then stalls for a long time holds a position ahead of clients that arrived later and are ready to work, which is the classic convoy effect. A queue that wants to avoid convoys needs a notion of readiness, which the service does not provide and which the clients must implement by re-creating their ticket if they are not ready to proceed.

The queue’s fairness is also only as good as the service’s sequence assignment. If the service assigns numbers at a linearization point that is not the client’s send time, then “first” means first to reach the service, not first to try. Two clients on different network paths can have their attempts reordered, and the client that sent earlier can receive the later number. That is unavoidable and generally acceptable, because the alternative is trusting client clocks, which is worse. The ordering is total and agreed by all observers, which is what the protocol needs; whether it matches wall-clock arrival is not a property the service can offer.