Transaction model

Transaction model

To support undo and concurrent editing, we update our model following a set of "transactions".

Definitions

The server is our cluster of web servers. They communicate with a database, another cluster.

The model is all the data in a single document set. It is too big to be copied between the database and the server, so only the database can see the complete model. But the server, being a crafty proxy, can query for any parts of the complete model that it needs, whenever it wants, so as far as the client is concerned, the server model is complete. The client model is at the lower end of the food chain.

We alter the model (client, server or complete) via a transaction (client transaction, server transaction and database transaction). Conceptually, transactions are applied to models one-at-a-time, that is, in serial. So each transaction brings a model from one version to the next. A version is a snapshot of the complete model; for each complete version, each client will hold a client version, which is a subset of the complete version.

As users edit the model, client versions will diverge from server versions. On the client, we have the concept of a trunk version, which is what the client version would look like if no edits were ever made by the user.

Transactions behave differently in the client, server and database. They all share the concept of a delta, which contains all the information we need to transition the model from one version to another.

A delta can be too large for the client to transmit to the server and too large for the server to transmit to the database. (Tagging 5 million documents, each with an 8-byte ID, will consume 40MB.) So we introduce the notion of a compressed delta, which is quick to transmit (i.e., "add tag 3 to node 7"), and a expanded delta, which is what the database works with.

A compressed delta can only be expanded when it is combined with a version.

An expanded delta can be inverted, which gives "undo" behavior. A compressed delta cannot be inverted (because it would depend upon the version it means to revert to).

We can also categorize deltas as client delta, server delta and database delta. (Client deltas and server deltas are always compressed; database deltas can be both.)

There will be lots of deltas flying around in the rest of this page, as tricky chains of events play out. Remember that each delta can be traced back to one action on a client.

The challenge

We want a collaborative workspace with undo. That means:

• (Multiple clients) Many users, all editing at once
• (Divergent clients) As users make changes, applying deltas to their client versions, their versions will not be the same as the complete version or each other's client versions.
• (Eventual consistency) If every user takes a deep breath (or two) and waits for all transactions to complete, every client version will again be a subset of the server version.
• (Serialized versions) If two users send a delta at the exact same time, the server will pick one to run first.
• (Atomicity) There is no intermediate state between versions.
• (Asynchronous transactions) Any delta must apply successfully to any version of the model. (Otherwise we'd create user-interface hell when serializing versions.) If a delta makes no sense when applied to a version, it should silently become a no-op.
• (Undo) If every database delta is undone in order, the model will return to its initial version.

We can combine these requirements to make more design decisions explicit:

• (Invertible deltas) Any expanded delta must have an inverse.
• (Non-commutative) Sometimes, reordering deltas (as we must do, for serialized versions) produces different results. That's okay.
• (Write-only transactions) Since deltas travel from a single user to the server, and from the server to all users, there is no need for the server to fetch data from the database in a transaction ("transaction" in our lingo--not in the SQL sense). The client can write and forget, and the server can write and forget.

It's not too hard to expand this into broad error-handling policy, too:

• (No logical errors) Because transactions are write-only, they never throw errors.
• (Programmer errors) If a delta fails to apply correctly, it will not be applied to the database.
• (Connection errors) If the client fails to communicate to the server, the server fails to communicate to the database, or the server fails to broadcast to clients, the affected transactions will stall.

If the client can't connect to the server, the user will be notified; if the server can't connect to the database, the user can be notified, as well. If the server can't broadcast to clients, the client can detect the issue (by polling, for instance) and notify the user.