Tombstone Accumulation

A replicated set that supports removal has to answer an awkward question: if a peer arrives carrying an element you deleted last week, is that a new insert or an old one? Without a record of the deletion you cannot tell, so the element comes back. The record is a tombstone, and keeping it is what makes convergence correct.

The cost is that tombstones cannot be discarded locally. Deciding a deletion is safe to forget requires knowing every replica has seen it, which is exactly the coordination a CRDT was chosen to avoid. So the state a device stores is not the current value; it is the current value plus all the evidence needed to merge with a replica that has been offline for an unknown time. A collaborative project with 50,000 edits can carry far more metadata than data, and opening it means deserialising all of it: 40 seconds on a mid-range phone and a 900 MB local store, with nothing having failed.

Why it matters

This is a monotonic failure with a delivery date set by user enthusiasm. Nothing errors, no alert fires, and the symptom is the product getting slower for the customers who use it most. Because the growth is in the data model rather than in any component, capacity work does not help and the usual fixes make it worse: syncing more often adds metadata, adding replicas adds retention obligations.

It also determines the cost of a new device. Sync payloads scale with history rather than with change, so a laptop joining a two-year-old project downloads two years of operations, and the first thing a new user experiences is a timeout.

Implementation patterns

• A membership horizon. State that replicas which have not synced within N days are stale and must re-bootstrap from a snapshot. That declaration is what makes removals older than N days collectable. It has to be designed in from the start, because introducing it later invalidates devices already in the field.
• Snapshot plus tail. Persist a compacted state at a watermark and only the operations after it. New devices fetch the snapshot; existing ones fetch the tail.
• Scope the structure to the unit a user opens. One CRDT per document or project, not per workspace, so cost is bounded by what is actually loaded.
• Choose weaker semantics per field. Many fields never need concurrent-merge behaviour: a last-writer-wins register with a server-assigned timestamp costs a fraction of the metadata, and for a status field it matches what users expect anyway.
• Delta sync keyed on peer knowledge, so a sync sends what this peer lacks rather than everything since a version vector nobody pruned.
• Measure it. Metadata bytes per element and open time at p95 on the oldest project in the fleet are the two numbers that show the curve before a customer does.

Industry example

When Figma described its multiplayer architecture in 2019 it explained that it deliberately did not use a full CRDT. Because a server is always present in the editing session, the server can be the authority on ordering, which removes most per-operation metadata and the need for convergence proofs. The design keeps CRDT-like properties where they are needed and pays for none of the retention elsewhere.

The mirror-image lesson comes from version control and storage systems generally: any structure that only ever appends needs an explicit compaction story, and the ones that survive in production are the ones where compaction was designed alongside the append path rather than after it.

Failure scenarios

• Open time degrading with age, concentrated in the most active accounts, so the metric that matters is invisible in an average.
• New-device sync timeouts, because bootstrap cost grows with history.
• A resurrection bug after an over-eager cleanup, where someone deletes tombstones to reclaim space and a laptop that was in a drawer reintroduces deleted records.
• Backup and export bloat, where a tenant's export is dominated by metadata and restore takes hours.
• Memory pressure on mobile, where the process is killed during load and the user sees an app that will not open at all.

Trade-offs

When not to use it

The question is really when not to use a removal-capable CRDT at all. If a server is always in the path of an edit, you have an authority available and do not need coordination-free merge; use it and keep the metadata. If the concurrency you fear is two devices belonging to one person, sequencing at the server covers it. If the data is append-only by nature — a log, a set of sensor readings, a chat transcript — there are no removals and none of this applies. The precondition for paying tombstone costs is that there are genuinely times when no single node can decide. Peer-to-peer editing with no server, or a fleet that must merge among itself while disconnected from you, is the case that qualifies.

Interview question

Q: A collaborative app built on CRDTs is fast for new projects and takes 40 seconds to open old ones. Walk me through the diagnosis, and tell me what you would have decided on day one to prevent it.

What a strong answer covers: that the state is value plus merge evidence, and tombstones cannot be collected without knowing what every replica has seen; that the cost tracks churn and history rather than current size; the day-one decision — a membership horizon plus snapshot-and-tail sync — and why retrofitting it invalidates field devices; the cheaper alternative of weaker per-field semantics; and the honest precondition test, whether any moment genuinely lacks an authority.

Quick check

Quiz: Why can a replica not delete its own tombstones? Because a peer that has not yet seen the removal would reintroduce the element, and knowing that every replica has seen it requires coordination.

Flashcard: Which design decision must precede the first release of a CRDT-backed app? — A membership horizon that declares long-dormant replicas stale, since it is what makes tombstone collection possible and cannot be added later without invalidating field devices.