Why Locks Across Independent Services Do Not Compose

An organization that runs two clusters, two regions, or two generations of infrastructure usually ends up with two coordination services. Each is internally correct, each offers linearizable locks, and each is operated by a team that can explain why its own service is safe. The trouble starts when a resource is protected by a lock in one service and also by a lock in the other, or when a client acquires in one and assumes the other will respect it.

Two orders, no relation

A lock service’s guarantee is an order over the operations it serves, an order that only exists because every grant goes through one linearizable serialization point. Within one service, “A acquired before B” is a fact the service can establish. Across two services, there is no fact of the matter. Service 1 can grant the lock at what it considers instant 100 while service 2 grants the same lock at what it considers instant 100, and neither instant is comparable to the other. Both clients believe they hold the lock, and both are correct relative to their own service.

The failure is not that one of the services is buggy. It is that mutual exclusion requires a total order over the grants, and two independent services provide two partial orders with no intersection. A client cannot repair this by reading both services and comparing, because the comparison needs a common clock or a common sequence, and neither exists. It cannot repair it by taking a lock in both, because acquiring in service 1 and then service 2 does not prevent another client from acquiring in service 2 and then service 1, which is the classic deadlock of two locks taken in opposite orders, now distributed across two systems with no common timeout to break the cycle.

The standard name for the situation is that the two lock services are not in the same failure domain and not in the same consistency domain. The first is operational: an outage of one does not affect the other, which is why the second one exists. The second is semantic: an operation in one has no defined relationship to an operation in the other, which is why the combination cannot be used as a single lock.

What a client-side protocol can and cannot do

The tempting protocol is to acquire in both services and consider the lock held only when both succeed. That gives exclusion within each service, so no two clients can both succeed in service 1, and no two can both succeed in service 2. It does not give exclusion overall, because client A can hold service 1 and client B can hold service 2, and each is waiting for the other’s lock. The resource is protected by neither client exclusively; it is protected by the intersection of two waits, which is empty.

A protocol that avoids the deadlock by ordering the acquisitions, always service 1 then service 2, does prevent the two-client cycle. It does not prevent the case where service 1 is unavailable and service 2 is not: a client holding service 2 waits forever for service 1, and the resource is idle. It also does not prevent the case where service 1 grants to A and service 2 grants to B before either client has both, because the ordering of the acquisitions does not constrain the services’ independent grants. The client-side ordering only orders the client’s own requests, not the services’ decisions.

The only client-side protocol that gives real exclusion is one where the two services are not independent: one of them is authoritative and the other is a cache or a replica that defers to it. That is a change to the services, not to the client. If service 2’s grants are conditional on a token issued by service 1, then service 2 is not an independent lock service; it is a subordinate. The composition works because the ordering is imported from the authoritative service, not because the client is clever.

The token that crosses the boundary

The mechanism that makes two services composable is the same one that makes a lock and a resource composable: a monotonic token from a single source of order, checked by every participant. If service 1 issues the token and service 2 refuses to grant a lock whose token is not the highest it has seen, then service 2’s grants are ordered by service 1’s grants, and the combination is a single lock with a single order. Service 2 is then not independent; it depends on service 1 for its ordering, and an outage of service 1 stops service 2 from granting.

That dependency is exactly what the second service was built to avoid. The trade is unavoidable: either the two services share an order, in which case they share a failure domain for the ordering, or they do not, in which case they cannot provide a single lock. There is no third option in which two independent orders combine into one. This is the same argument as fencing tokens at the resource, lifted from the lock-resource boundary to the lock-lock boundary.

The practical consequence is that multi-region locking is either built on a single consensus group that spans the regions, with the latency and availability cost that implies, or it is not locking at all. Systems that claim to offer multi-region locks without a cross-region consensus usually mean that locks are local to a region and that conflicts across regions are resolved by something else, such as a last-writer-wins rule or an application-level reconciliation. Those are legitimate designs, but they are not mutual exclusion, and calling them locks invites the assumption that they provide it.

Partition tolerance and the impossibility

The deeper reason is a familiar one. A lock service that remains available in every partition would have to grant the lock on both sides of a partition, which violates exclusion. So any lock service must give up availability on the minority side, which means the service’s availability is bounded by its quorum. Two services in two regions, each with its own quorum, each remain available in their own region during a partition between the regions, and each can grant the same lock. The partition is exactly the scenario in which the two grants are most likely, because it is the scenario in which the two services cannot see each other.

Adding a third service does not help. Three independent quorums give three independent orders, and the number of pairwise incomparable grants grows with the number of services. The only structure that composes is a single order, whether that order is implemented by one consensus group, by a hierarchy where one group’s decisions constrain another’s, or by a token that every participant checks. Everything else is a set of locks that happen to be spelled the same way.

The case that arises from staggered migration

The failure mode that matters is rarely a carefully constructed two-service protocol. It is an accidental one: a resource protected by a lock in service 1 for one class of clients and by a lock in service 2 for another class, because the two classes were built at different times. A batch job takes the lock in the old service; an online service takes the lock in the new one; both write to the same table. Neither client knows the other exists, and the exclusion each relies on is real within its own service and absent across them.

The symptom is intermittent corruption that correlates with the two workloads overlapping, and the diagnosis is hard because each service’s logs show a correctly held lock. The fix is to migrate one class of clients to the other service, or to introduce a single authoritative lock that both classes use, or to partition the resource so that the two classes never write the same rows. The last is often the cheapest and the least satisfying, because it solves the problem by removing the shared resource rather than by coordinating access to it.

A related case is a lock that is held across a service migration. A client acquires in service 1, the migration moves the resource to service 2, and the client’s lock is now in a service that no longer protects anything. The client’s writes are unguarded, and the new service’s clients are unaware. Migration procedures that move a resource must either drain the old lock holders first or transfer the lock state with the resource, and transferring lock state between services is exactly the composition problem in its most concrete form.

The design rule

The rule that follows is narrow and useful: a resource must be protected by exactly one lock service, and every writer to the resource must use that service. If a second service must exist for availability or locality, it must derive its grants from the first, or the resource must be partitioned so that each service protects a disjoint part. A resource protected by two independent lock services is not doubly protected; it is unprotected, with two sets of clients each believing otherwise.

The rule is easy to state and hard to enforce, because the second service is usually introduced for a good reason and the overlap is usually discovered later. Enforcement is a matter of inventory: knowing which resources are protected by which service, and treating a resource with two protecting services as a defect rather than a redundancy. That inventory is the unglamorous part of coordination, and it is the part that determines whether the guarantees hold in the cases that matter.