@jepemo

CRDTs and Coordination Avoidance: Maps, Nested CRDTs, and Schema Evolution

Learning / Distributed Systems / CRDTs and Coordination Avoidance / 009

LESSON

CRDTs and Coordination Avoidance

009 30 min intermediate

CRDTs and Coordination Avoidance: Maps, Nested CRDTs, and Schema Evolution

Core Insight

Consider a replicated task object used by a team that works from browsers, phones, and regional services:

task:
  title
  labels
  comment_count
  comments
  last_opened_at

The tempting implementation is to store the whole object as one JSON blob and resolve conflicts with last-writer-wins. That converges, but it can lose unrelated work. If Ana changes the title in Madrid while Bruno adds a label in Dublin, choosing one whole-object value discards the other field even though the edits did not logically conflict.

A map CRDT changes the unit of merge. The map still looks like an object at the API, but each key is backed by its own CRDT policy. title can be a multi-value register, labels can be an observed-remove set, comment_count can be a counter, and last_opened_at can be a last-writer-wins register. The map merge aligns keys and delegates each field to the right merge rule.

The non-obvious part is that nested structure does not remove design choices. It multiplies them. Deleting a field, updating a child, renaming a key, or changing a field type all become merge semantics. The trade-off is expressive local updates versus more metadata, sharper schema discipline, and a stronger need to define what each field means under concurrency.

A Map Is Not A Blob

A map CRDT is a mapping from keys to CRDT values:

key -> CRDT value

title          -> multi-value register
labels         -> observed-remove set
comment_count  -> PN-counter
last_opened_at -> LWW register

When two replicas merge, the outer map does not choose one object over the other. It walks the keys and merges the values stored under those keys:

Replica A:
  title = "Fix login redirect"
  labels = {frontend}

Replica B:
  title = "Fix login redirect"
  labels = {frontend, auth}

merge:
  title.merge(title)
  labels.merge(labels)

This is why maps are useful. They let an application keep an object-shaped model without pretending that every field has the same conflict policy.

The empty value for a field is often called bottom. Bottom means "no information yet," not "an explicit user value." For an absent counter, bottom is zero components. For an absent set, bottom is no live add dots and no relevant causal context. For an absent register, bottom is no write.

That distinction matters during schema evolution. A new field should usually start at bottom. If old replicas do not know the field, they should not create a competing default write merely by reading or rewriting the object.

Nested CRDTs

Nested CRDTs are CRDTs stored inside other CRDTs. A task can contain a map of comments, where each comment is itself a map:

task:
  comments:
    c1:
      body       -> multi-value register
      reactions  -> PN-counter map
      resolved   -> LWW register or domain-specific register

The merge path follows the structure:

task.merge
  comments.merge
    c1.merge
      body.merge
      reactions.merge
      resolved.merge

Suppose A edits a comment body while B increments a reaction count:

A:
  comments.c1.body = "Use the regional router"

B:
  comments.c1.reactions.thumbs_up += 1

After merge, both changes survive because they touched different nested fields:

comments.c1:
  body = "Use the regional router"
  reactions.thumbs_up = 1

The mistake is to assume nested structure automatically gives correctness. It only gives a place to attach policies. If body is LWW, concurrent body edits can still be lost. If resolved is safety-sensitive, LWW may be too weak. If reactions uses counters, the system must still preserve replica identities and handle counter compaction safely.

Nested maps are most useful when the structure matches the domain. If comments, labels, assignees, and timestamps have different meanings, they deserve different merge rules.

Deletes Inside Maps

Deletion is where maps become subtle.

Imagine a profile map with a nested address map:

profile.address:
  city    -> register
  country -> register

Replica A deletes address because the user removed it. At the same time, Replica B updates address.city while offline:

A:
  remove profile.address

B:
  profile.address.city = "Lisbon"

What should merge produce?

There is no universal answer. The data type must choose a policy:

remove-wins:
  address is gone

update-wins:
  address exists with city = "Lisbon"

conflict-preserving:
  expose that address was removed and concurrently updated

Observed-remove maps use the same idea as observed-remove sets. A remove covers the field instances the remover has observed. A concurrent update that creates a new dot for the field may survive under add-wins or update-wins semantics. A remove-wins map records stronger removal evidence so later or concurrent child updates cannot silently revive the subtree.

This choice should be made by domain meaning, not by convenience. Removing a draft field from a collaborative note may allow a concurrent edit to restore it. Removing a user's access rule or payment instrument may need remove-wins behavior or explicit coordination.

The important rule is to define deletion at the boundary where users understand it. If "delete address" means "remove the whole address object," child updates should not accidentally make half an address visible. If "clear city" means "remove one field," the rest of the nested object should remain intact.

Worked Example: Project Preferences

Consider project preferences replicated across clients:

project:
  name
  labels
  notification_settings
  view_count
  last_seen_at

A practical map design might use:

name:
  multi-value register

labels:
  add-wins OR-set

notification_settings:
  nested map:
    email_enabled -> LWW register
    digest_hour   -> LWW register
    muted_topics  -> OR-set

view_count:
  grow-only counter or PN-counter

last_seen_at:
  LWW register

Now suppose three replicas update different parts while disconnected:

A changes:
  name = "Search Platform"

B changes:
  labels += "production"
  notification_settings.muted_topics += "deployments"

C changes:
  view_count += 1
  last_seen_at = 10:05

The merge keeps all independent changes:

project:
  name = "Search Platform"
  labels = {production}
  notification_settings:
    muted_topics = {deployments}
  view_count = previous + 1
  last_seen_at = 10:05

That is the benefit of a map CRDT: the object converges by composing smaller merges. It avoids making last_seen_at and name obey the same rule.

But the map also makes review harder. If someone later changes notification_settings from a nested map into one LWW JSON blob, a concurrent edit to digest_hour can overwrite a concurrent edit to muted_topics. The schema change has changed the merge contract, not only the storage format.

Schema Evolution Is Merge Evolution

Schema evolution is the discipline of changing stored shape while old and new replicas may coexist. In a coordinated database migration, you can often stop writers or force all code through one version. In coordination-avoiding replication, old clients may keep writing old fields while new clients write new fields.

Adding a field is usually the easiest case:

old schema:
  project.name
  project.labels

new schema:
  project.name
  project.labels
  project.color

If color starts at bottom, old replicas simply ignore it. New replicas can merge it when present. The risk appears when a default is treated as a write. If every old client rewrites color = "blue" because it does not know better, it may overwrite a real user choice made by a new client.

Renaming a field is harder:

old:
  display_name

new:
  name

During rollout, some replicas may write display_name while others write name. If those fields are independent, the system now has two names. A safe rename usually needs a bridge period:

read from name if present, otherwise display_name
write both fields or write a migration record
merge old and new values with an explicit rule
retire the old field only after old writers are gone

Changing a field type is the hardest case. A counter, a set, and an LWW register do not preserve the same information. Moving from labels as an LWW list to labels as an OR-set cannot be done by merely changing the decoder. The migration must explain how old writes and new writes combine while both exist.

Good schema evolution asks three questions:

What is bottom for the new field?
How do old and new writes merge during rollout?
When is it safe to drop old metadata, tombstones, or compatibility code?

If the answer requires "all replicas have upgraded before any concurrent write," the design is no longer coordination-avoiding for that migration.

Operational Failure Modes

Practice

Design a CRDT map for this replicated workspace object:

workspace:
  title
  members
  pinned_documents
  billing_plan
  last_activity_at

For each field, choose a merge policy and explain one accepted trade-off. Then choose one schema change, such as renaming title to name or replacing pinned_documents with a richer nested map. Write the compatibility rule that lets old and new clients merge during rollout.

If a field affects authorization, billing, or legal responsibility, do not default to the most available CRDT. Mark the invariant and decide whether remove-wins semantics or coordination is required.

Connections

Resources

Key Takeaways

PREVIOUS CRDTs and Coordination Avoidance: Sets, Tombstones, and Observed-Remove Semantics NEXT CRDTs and Coordination Avoidance: Invariant Confluence, CALM, and Monotonic Programs

← Back to CRDTs and Coordination Avoidance

← Back to Distributed Systems

← Back to Learning Hub