From Messages to Mutations

This is the second post in a series on the ideas behind Sobamail. The first one introduced a well-defined way of carrying machine-readable data. The next step is to define how each such message relates to others. Addressing the asynchronous and out-of-order nature of email is what makes the Sobamail platform possible.

Email is asynchronous and unordered

Email is a store-and-forward system that keeps chugging along even over spotty connectivity. A message leaves a mailbox and waits on a server for the recipient, who is free to connect whenever they like, be it a second later or a week later. Messages can arrive out of order, or more than once, and the sender usually gets no feedback on when, or whether, a message made it to its recipient.

Conventional apps rely on a synchronous transport: every write goes through a single data store, which makes the central database both the source of truth and the single authority on write ordering. So the moment the central servers become unreachable, the app stops working.

A Sobamail app spreads that authority across several equal replicas. Every mailbox that shares the app has a writable copy of the data, and each keeps working offline and passes events to the others in the background as connectivity permits. For this to work, the backend should accept a write only when it is sure every other replica will be able to apply it too, even though those replicas may see that write late, twice, or ahead of the writes it depends on. Since the transport can’t say what came first, the messages have to say it themselves.

A message that knows its past

So in Sobamail, a structured message that changes an app’s data, a mutation to its state, is defined in terms of its payload as well as the previous mutations it depends on, its parents. Using their hash, a delete names the insert it undoes, an update names the row it changes, and a row that references another row names the mutation that created it. A mutation can have one parent, several, or none at all.

The mutation is then hashed, parent hashes included, and that hash becomes its identity. Because the parents went into the hash, the same change recorded on top of a different past is a different mutation with a different hash. Every edge in the resulting graph is a hash of the thing it points to. The technical term for it is “Merkle Directed Acyclic Graph”, the structure under git’s history and under every blockchain’s ledger.

What a mutation looks like

A mutation is a structured message like any other: an ordinary email with a designated attachment. What differs is the document inside the attachment, which we call a replication SMC. Besides its payload, it carries where the mutation came from, which version of the app’s code produced it, its own hash and the hashes of its parents. That is everything another replica of the app needs to put the mutation in its place.

What the graph buys you

The structure itself handles each of email’s delivery quirks.

Duplicates cost nothing. A mutation is its hash. If the same mutation arrives twice, by two routes or by a retry, the duplicate is recognised and dropped.

Order comes from the graph. A mutation comes after its parents in the graph. Arrival times can differ from one replica to the next, but the parent hashes travel inside the mutation, so every replica agrees on what came before what. A mutation that arrives ahead of its parents waits for them.

History cannot be edited quietly. Changing a mutation after the fact changes its hash, which breaks every edge that pointed at it. The altered copy shows up as a new, unrelated node, and the rest of the graph still points at the original.

Replicas converge. Every replica of the app data holds the same graph and replays each mutation with the same version of the app’s code that produced it. As for data races, the platform solves them deterministically, so every replica converges on the same state. The rules that make this work are strict on purpose: a mutation can insert a row, delete one, or update one with a commutative operation.

What it means for the developer

For the people building apps, the graph is mostly invisible and occasionally strict. The app’s code inserts, updates or deletes a row, and the platform turns that into a mutation and finds its parents. What the platform insists on is that replaying a mutation gives the same result on every replica. So while it replays, the code cannot read the clock, draw a random number or look at anything outside the graph. Anything that varies between runs is decided once, when the mutation is created, and carried inside it. The Sobamail concepts page has more details.

Where this leads

What is still missing is the thing that produces mutations and replays them: the code. Sobamail apps bear a lot of resemblance to traditional Node apps: the backend is plain JavaScript with some runtime facilities beyond the browser environment. The key difference is that in Sobamail’s case, both the backend and the frontend run inside the mail client on your own machine, and on the machine of everyone who shares the app. The next post is going to be about that app platform.

Read more

• Replication SMC in the format reference lists the document field by field.
• Mutations in the Sobamail concepts page: replicated and non-replicated events, determinism, and why identical mutations collapse into one.
• The collaborative counter is the smallest app that shows all of it working.