Reference / crdt

Shared data that still agrees.

Almost everything in Goer has one owner, and that keeps life simple. But some data really does need to live on several machines at once: who’s online, a hit counter, a few shared settings. And those machines can’t always reach each other. What you want is for each one to keep taking changes on its own, and for all of them to end up with the same answer once they’re talking again. That’s what a CRDT does (the name is short for conflict-free replicated data type), and goer/crdt is a small library of them. This page tells you when to reach for it, what’s in the box, and how it keeps the copies in step.

When to use it, and when not to

Use an ordinary process

When it’s fine for one process to own the value and everyone else to ask it. It’s simpler and there’s never any doubt about the answer. For most data, this is right.

Use a CRDT

When every machine has to keep accepting changes even while cut off from the others, and agree later with nobody in charge. The price is that copies can disagree for a short while.

Here’s a made-up example. Two nodes each count page views. The link between them drops for a minute. Both keep counting. When the link comes back, the totals have to add up, with nothing counted twice and nothing lost. A CRDT counter does that on its own.

You use it from Go. Your code holds a *crdt.Replica and calls methods on it. An imgo process reaches one the way it reaches anything outside itself: by messaging a native actor that owns it.

The types

Every type has the same few methods: Type(), Merge(other Value) error, Clone(), StateJSON(), and MergeJSON([]byte). When you change one, it changes in place and hands back just the bit that changed, ready to send to the other copies.

Type	What it is	How two copies merge	What gets sent on a change
`Register`	One value. The last write wins. It can hold anything that turns into JSON, and every copy reads it back in JSON form.	Keep the one with the later `Stamp`	The whole register (it’s tiny)
`GCounter`	A counter that only goes up. Each node keeps its own tally.	Take the bigger tally for each node	The one tally that changed
`PNCounter`	A counter that goes up and down. It’s two up-only counters, one for adds and one for subtracts.	Take the bigger tally on each side	The side that changed
`ORSet`	A set you can add to and remove from.	Keep every add, apply every remove that saw it	The new add or the remove markers
`ORMap`	A map whose values are other types from this table.	Merge the keys like a set, then merge each value	The key change and the value change
`LWWMap`	A map where the last write to each key wins.	Per key, keep the later `Stamp`	The one entry
`Presence`	A “who’s here” list of `{node, pid, meta}` that forgets anyone who stops checking in.	Per entry, keep the later `Stamp`	One entry or one remove marker

The set: what if one copy adds while another removes?

A remove only removes what that copy had actually seen. So if one node removes “alice” and, at the same moment, another node adds “alice” again, the new add survives, because the remover never saw it. Anything the remover had seen stays removed for good. That rule is what lets removes arrive in any order, or twice, and still give the same result.

Who wrote last?

For “last write wins” you need to agree on what “last” means, and you can’t trust every machine’s clock. So each write gets a Stamp{T, Node}. The bigger T wins. On a tie, the node name decides. Every copy applies the same rule, so every copy picks the same winner.

T is a plain counter. Each time a node hears a stamp from another node, it moves its own counter past it, so its next write is definitely later than everything it has seen. A replica starts its counter from the wall clock, so a node that restarts doesn’t begin below its own old writes.

Separately, each value numbers its own changes 1, 2, 3 with no gaps, per node and per restart. Those numbers are how a copy can say “I’ve seen everything from node A up to change 7”. That statement is called a Context, and it matters for cleaning up, below.

How merging works

Merging two copies has three properties, and we test each type for all three. Order doesn’t matter. Grouping doesn’t matter. And merging the same thing twice changes nothing.

Put together, that means: if every change eventually reaches every copy, by any route, in any order, even more than once, all the copies end up identical. We test that with random orderings, dropped messages, and duplicates, and across real nodes.

Sending only what changed

When you change a value you get back a small piece holding only the change. Merging that piece is the same operation as merging a whole copy, so there’s one code path for both. We haven’t tried to make those pieces as tiny as theoretically possible. They’re simple and correct.

How copies stay in sync

A Replica is one node’s copy of a named group of values. The name (the sync id) is how replicas on different nodes find each other, and it stays the same across restarts. Your code calls ordinary methods on it: CounterAdd, RegisterSet, SetAdd, MapSet, PresenceHeartbeat, and so on. Each change is sent to the other copies straight away.

Finding each otherA replica asks Goer which nodes are connected and introduces itself to each. A node that doesn’t answer, maybe because it isn’t running that sync id, gets asked again less and less often.

Catching upEvery SyncEvery (half a second unless you change it) each replica sends its whole state to the others. So if a change got lost on the way, it’s fixed within one round. A node that goes quiet for StaleAfter (1.5 seconds) gets re-introduced, which is also how a restarted node is found and brought up to date.

Who’s onlineEach round, a replica refreshes its own “I’m here” entries and removes any that haven’t been refreshed within PresenceTTL. A node that crashes stops refreshing, and the others drop it.

Cleaning up after deletes

There’s an awkward thing about deleting from shared data. If you simply forget an item, an old copy on another machine can hand it straight back to you. So a delete leaves a marker behind, usually called a tombstone, that says “this was removed”. Left alone, tombstones pile up forever.

Goer cleans them up once every replica it knows about has reported seeing the delete. A replica that knows of no others cleans up straight away.

And what if an old copy turns up later anyway, say from a node nobody had heard from? It still can’t bring the item back. Each copy remembers which changes it has seen (that’s the Context). If it’s offered an item it has seen before and no longer holds, it knows that item was deleted, and refuses it. The node holding the stale copy drops it at the next catch-up round.

So what are tombstones still for? Speed. A tombstone lets one tiny message do the deleting on other nodes, without waiting for a full catch-up.

What it doesn’t do.Nothing is saved to disk: a replica that restarts begins empty and catches up from the others. There’s no imgo syntax for it. Each catch-up round sends the whole state, which suits small data. And if two replicas use the same name for two different types, they can’t be merged. Each keeps its own, and Replica.Conflicts (or Config.OnConflict) tells you about it.