-
Notifications
You must be signed in to change notification settings - Fork 37
Transaction model
To support undo and concurrent editing, we update our model following a set of "transactions".
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, and a divergent version, which is what the user wants the trunk version to become.
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. (Server deltas are always compressed; client and database deltas can be both, but they cannot be transmitted when expanded.)
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.
(This is the "why". Skip this section to arrive at the "how".)
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, the database cannot throw errors.
- (No user errors) Because the database cannot throw errors, the user cannot cause errors. Everything the user does is accepted. (The client may provide interaction before creating a delta--such as an "are you sure?"--and the server may throw an error if a buggy client generates a syntactically incorrect delta.)
- (Programmer errors) If a delta fails to apply correctly in its entirety, it will not be applied at all.
- (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.
A transaction involves a delta. For details on what data these deltas contain, see Deltas.
The client maintains a trunk version and an outbox. Combined, they create a divergent version. It also maintains a client-side delta archive, which comes in handy for undo operations.
When the user makes a change, the client:
- Creates a delta, creating and attaching a GUID (which must be globally unique)
- Expands the delta
- Applies the expanded delta to its divergent version
- Adds the expanded delta to the outbox
- Sends the compressed delta to the server
When the server broadcasts a delta to the client, it will contain a version number and the GUID. The client:
- (optimization) Compares the delta's GUID with the first GUID in the outbox. Removes the item from the outbox and returns, if they are equal.
- Inverts all expanded deltas in the outbox and applies them all to the divergent version (returning the divergent version to trunk, temporarily)
- Expands the delta from the server
- Applies the expanded delta to its divergent version (trunk), updating trunk
- Adds the expanded delta and its GUID to the delta archive
- Updates the trunk version number
- For each delta in the outbox, re-expands the delta (re-storing it in the outbox) and re-applies it
The client can tell when the server is not up to speed with the latest changes, by checking the length of the outbox.
This loop can be run on a batch of deltas at a time, for an enormous speedup. Remember to apply step 1 to every incoming delta.
When the client submits a compressed delta (or list of compressed deltas), the server:
- Checks that the user has access to the given document set
- Validates the delta for syntax and semantics (not checking anything on the database)
- Transcribes the compressed delta to a compressed delta in a format the database understands (e.g., an SQL instruction)
- Submits the delta to the database
- Returns "Ok"
When the server submits a compressed delta to the database, the database:
- Expands the delta
- Applies the expanded delta to the complete version
- Increments the complete version number (a natural number starting at 0)
- Stores the compressed delta, the expanded delta, the client's GUID and the complete version number in the delta archive
After a database transaction is complete, the server must broadcast the result to clients. For now, we do this by polling:
- The client polls the server for changes, sending its trunk version number
- The server queries the database for all compressed deltas with a higher version number, in order
- The database responds with an ordered list of (version number, client GUID, compressed delta)
- The server returns the list to the client
- The client handles each delta
For undo, the client needs a bit more machinery:
- An undo list, a list which only stores the user's own deltas. (This mimics the outbox more than it does the delta archive.)
- An undo list pointer, which helps us manage "redo" as well.
When the client performs a transaction, it:
- Truncates the undo list, removing everything after the undo list pointer
- Appends the expanded delta and its GUID to the undo list
- Increments the undo list pointer
When the user hits "undo", the client:
- Creates a compressed delta for the "undo" action, which consists of the GUID of the delta the undo list pointer points to
- Decrements the undo pointer
- Follows the steps in "client transactions"
When the user hits "redo", the client:
- Returns, if the undo list pointer points to the end of the list
- Increments the undo pointer
- Creates a compressed delta for the "redo" action, which consists of the GUID of the delta the undo list pointer points to
- Follows the steps in "client transactions"
Aside from this, "undo" and "redo" transactions are identical to any other. The compressed delta consists solely of a GUID, and both the client and the server can expand it, based on their delta archives.
[ TODO: expound here. Sometimes a client won't be able to expand a delta perfectly. For instance, when documents that one client doesn't see are tagged, the client won't be able to update its nodes' tag counts. We need to introduce the concept of "scope", so clients will know what information they're missing and how to query for it. ]