@jepemo

CRDTs and Coordination Avoidance: Uniqueness, Allocation, and Coordination Requirements

Learning / Distributed Systems / CRDTs and Coordination Avoidance / 012

LESSON

CRDTs and Coordination Avoidance

012 30 min intermediate

CRDTs and Coordination Avoidance: Uniqueness, Allocation, and Coordination Requirements

Core Insight

Imagine a multi-region product where users create public workspace slugs. Madrid accepts atlas for one team while Dublin, temporarily partitioned from Madrid, accepts atlas for another team. Both regions did a local check. Both saw no existing atlas. Both accepted the request.

When the replicas merge, a CRDT can preserve both facts perfectly:

slug "atlas" was claimed by team A
slug "atlas" was claimed by team B

That is convergence, but it is not the product promise. The product promised that a slug names exactly one workspace. A deterministic conflict resolver can pick a winner, but that changes the promise to "your accepted slug might be revoked later." That may be acceptable for some products. It is not the same as preserving uniqueness.

The key move is to stop asking "which CRDT makes usernames unique?" and ask "who is allowed to allocate this part of the namespace?" Uniqueness is usually protected by coordination, by partitioning the namespace, or by changing the identifier so independent replicas cannot choose the same value.

The Naive Unique Set

A tempting design stores slug claims in a mergeable map:

claims[slug] = owner

On a single machine, the rule feels simple:

if claims["atlas"] is empty:
  claims["atlas"] = team_a

In a multi-region system, "empty" is only a local observation unless the system has coordinated with the authority for that slug.

During a partition:

Madrid local state:
  claims["atlas"] = empty
  accept claims["atlas"] = team_a

Dublin local state:
  claims["atlas"] = empty
  accept claims["atlas"] = team_b

If the map merges by keeping all observed assignments, the merged state is honest:

claims["atlas"] = {team_a, team_b}

The data type did not lose information. The invariant failed.

If the map merges with last-writer-wins, the merged state may look tidy:

claims["atlas"] = team_b

But the system has hidden the conflict by discarding team A's accepted claim. That may be a repair policy, but it is not a uniqueness guarantee at accept time. It is compensation after a broken promise.

Why Uniqueness Needs A Boundary

The invariant is:

For every slug:
  at most one active owner exists.

Two independently valid states can violate that invariant after merge:

state A:
  atlas -> team_a

state B:
  atlas -> team_b

merge:
  atlas -> {team_a, team_b}

This is the same invariant-confluence test from the previous lessons. Each state was reachable and locally valid. Their merge is not valid. That means a coordination-free design cannot preserve this exact global uniqueness rule if any replica can claim any slug at any time.

The problem depends on absence. To accept atlas, a replica wants to know that no other active owner exists. In an asynchronous system, a delayed message can always contain the missing owner. Without a boundary, "I have not seen one" is not the same as "none exists."

A boundary can be a leader, a quorum, a partitioned namespace, a reservation service, a lease, or an allocation table. The form can vary. The purpose is the same: make one place responsible for deciding whether a particular value is still free.

Allocation Makes The Decision Local

Allocation means a prior decision assigns authority over a piece of the namespace.

For generated IDs, allocation can be built into the ID:

Madrid generates: madrid-000001
Dublin generates: dublin-000001
Lisbon generates: lisbon-000001

Those identifiers are unique because each region owns a disjoint prefix. No replica needs to ask whether Dublin has already generated madrid-000001, because Dublin is not allowed to generate that prefix.

For human-readable names, allocation is harder. Users want atlas, not madrid-atlas. The system can still partition authority:

authority_for(slug) = hash(slug) % 3

atlas  -> Dublin
delta  -> Lisbon
vector -> Madrid

Now Madrid can accept vector locally if Madrid owns that slug shard and its local authority state says the slug is unused. If a Madrid user asks for atlas, Madrid must route the request to Dublin or wait until Dublin is reachable.

The important shift is this:

without allocation:
  every replica may accept the same name

with allocation:
  exactly one authority may accept a given name

The operation can be local only when the request reaches the authority that owns that value. Allocation avoids global coordination on every claim, but it does not make every region able to accept every name while disconnected.

The trade-off is clear: allocation buys fast local decisions for the owning authority, and it costs routing, hot-spot management, authority migration, and a visible slow path when the authority is unavailable.

Worked Example: Workspace Slugs

Suppose a product runs in three regions:

Madrid
Dublin
Lisbon

The product promise is:

Every workspace slug resolves to exactly one workspace.

The team chooses this authority rule:

authority_for(slug):
  hash(slug) chooses exactly one home region

A user in Madrid creates vector. The hash says Madrid owns vector.

request:
  create slug "vector" for team A

Madrid is authority:
  local check: "vector" is free
  accept
  replicate claim asynchronously

This is coordination avoidance. The common path is local because the request landed on the authority for that value.

Now a user in Madrid creates atlas. The hash says Dublin owns atlas.

request:
  create slug "atlas" for team B

Madrid is not authority:
  route to Dublin

If Dublin is reachable, Dublin checks and accepts or rejects. If Dublin is partitioned away, Madrid cannot safely accept atlas while preserving global uniqueness. It can show a pending state, suggest available slugs owned by Madrid, or ask the user to retry later.

That user-visible behavior is not a minor implementation detail. It is the product expression of the invariant.

Comparing Identifier Choices

Different identifiers create different coordination requirements.

Generated internal object ID:
  Usually local if IDs include enough disjointness or randomness.

Human-chosen global username:
  Coordination required unless authority over the name is partitioned.

Username scoped inside a tenant:
  Coordination can be limited to the tenant's authority.

Invite code from a preallocated batch:
  Local while the replica still has unused codes from its batch.

Display name with no uniqueness promise:
  Mergeable without uniqueness coordination.

This is why many systems separate internal identity from user-facing names.

account_id = globally unique generated ID
username   = user-facing claim with coordination rules
display    = non-unique label

The internal ID can be created offline. The username may need a reservation path. The display name can usually be a normal mergeable field.

The design gets easier when each field has a precise promise.

Failure Modes

Practice

Design the allocation path for a global username feature.

regions:
  Madrid
  Dublin
  Lisbon

promise:
  a username belongs to at most one active account

latency goal:
  most users should get an answer in under 200 ms

Answer these questions:

1. What is the authority rule for a username?
2. What happens when the user's nearest region is not the authority?
3. What happens during a partition from the authority?
4. Which fields can still be updated with CRDTs while username reservation waits?
5. What user-visible states do you expose for a pending username claim?

The small win is recognizing that "unique username" is not one storage problem. It is an authority boundary plus a product promise.

Connections

Resources

Key Takeaways

PREVIOUS CRDTs and Coordination Avoidance: Escrow, Bounded Counters, and Rights Transfer NEXT CRDTs and Coordination Avoidance: Composing CRDTs into Domain Models

← Back to CRDTs and Coordination Avoidance

← Back to Distributed Systems

← Back to Learning Hub