Immutability, persistence, and data modeling.
A common separation in software design is called Model, View, Controller (or MVC). The model describes what the computer stores. The controller describes what it can do. The view describes how the user interacts with it.
Consider the case of undo in a word processor. The controller for undo has to be able to revert to a previous state of the text. It does this by interacting with the model, which has to store enough information for that previous version of the text to be accessible. The view then provides things like an undo button, a keyboard shortcut Ctrl+Z, and a display of the changes resulting from undoing.
Most of this post is about models and controllers.
Often a program has two distinct models, one to use when running and another to use when saved to disk. For example, most word processors have a model supporting undo while they are running but do not have a model supporting undo in a saved file. Type-undo works, but type-save-load-undo does not. This is not because the view or controller lack the ability to handle undo but because one of the word processor’s models (the saved-to-disk model) does not store information necessary for the controller to perform an undo.
The two-model system is natural for several reasons:
The programmatic interface of memory and storage are significantly different in most languages, so using the same model for both requires some work.
There is information you want the computer to forget between runs, like your password.
A lot of what programs store in their running model is some form of cache, space used to store things you could recompute from other data if needed but which is faster to keep on hand instead.
Running models are more transient than disk models and tend to change a lot. Ever had a program tell you it needs to restart in order to complete an update? That’s because the running model changed and it is much easier to say “toss the old data and rebuild it from the disk model” than to write code that converts the old model to the new one.
Consider the tool family known as text editors. The goal of a text editor is to edit text. Text is defined, in this context, as a sequence of characters. There is no formatting information, pagination, or anything like that: just a sequence of characters.
A text editor’s controller might allow for a persistent “Persistent” and “versioned” are words that have several uses in computing… unfortunately, a clearer word is not in common use. view of the data or it might not. If it is persistent, then every version of the text that ever existed is still accessible: you can ask the editor “what did the text look like at 2014-10-13 13:23:37.746815152 UTC?” Or “what was the 17th version of this text?”; the exact form of the interaction might vary. and it can answer. It it is not persistent then it does not have this ability.
Persistence is not the same as undo. If I type “the cat”, then undo the typing of “cat”, then type “dog” in an undo system the fact that I ever typed “cat” is not longer available. In a persistent system both versions remain.
The simplest model for a text editor would be a list of characters.
I type “the fish” and it stores a list of eight characters:
[t h e f i s h].
There is no version information, no edit history, not even an undo log.
No persistence is possible: the necessary data does not exist in the model.
We could add persistence support to the model in many ways,
but the one I wish to discuss is the list-of-edits model.
One way of soring the result of typing “the” is as three character-insert actions,
each consisting of a character and the position where it was inserted.
I’ll indicate these visually as the list [+t1 +h2 +e3].
If I then press backspace and type “is”, then delete the “th” and replace them with an “H”; the list of edits would become
[+t1 +h2 +e3 -e3 +i3 +s3 -h2 -t1 +H1].
Reading left-to-right and replaying each action we can recover every version of the text:
“” →
“t” →
“th” →
“the” →
“th” →
“thi” →
“this” →
“tis” →
“is” →
“His”
There are various refinements we could make to this model.
For example, we might augment the running model with some snapshots
so that we can get to what the text looks like at various times
without having to run through all the edits.
We might collapse some groups of edits into larger edit actions
like [+the1 -e3 +is3 -th1 +H1],
though doing so would lose some granularity of persistence.
And so on.
A persistence-enabling model doesn’t have to be attached to a persistence-exposing controller, but a persistence-enabled controller does have to have a persistence-enabling model.
Immutable data have the property that once it is created it may never change. Many, though not all, persistence-supporting models make use of immutable data. The example list-of-edits above is close to immutable in that none of the edits records we make ever get changed, but the list itself does change.
One way to change the list-of-edits model to be immutable
is to give each edit a unique identifier
and to have each edit refer to which state of the text it is editing.
So an edit might look like (+i3, id=XK4E, modifies=2PA7),
meaning that the result of edit action XK4E
differs from the result of edit action 2PA7
only in having inserted an “i” into position 3 of the text.
With this model there is nothing to change,
not even a list:
when a new edit is created it automatically refers to the other edits it uses.
Collaboration, from a controller’s point of view, is edit actions coming from two different users. Often collaborative edits don’t have a strict time ordering: because of delays in synchronizing, each user might make several edits before seeing the edits of the other. This creates a challenge: how should the controller merge the edits from two users?
In a model based on immutability, the model has a really easy time of collaboration. No matter what any user does, all it means is more immutable data are created. User gives model a datum, model accepts it. Simple.
From the controller’s point of view, things are a bit messier. Each immutable datum might refer to other data, and while these references are always acyclic they might not be linear. In the text editor example, we might find that two people added different edits to the same starting state and their views of the world are forever after different. This is often called “branching” or “forking” because the view of what model might mean splits in two.
Often controllers can find “compatible” contributions of different users.
For example, suppose datum X refers to the text “tthier”;
one user adds (-t1, id=Y, modifies=X)
and another adds (-i4, id=Y, modifies=X) and (+i5, id=W, modifies=Y).
The meaning of these edits is compatible
and we can apply or “merge” both branches to get the text “their”.
Algorithms for figuring out how to do these merges
are different for every tool domain,
but frequently it is easily possible to readily identify
which edits are independent and can be merged automatically
and which edits are in conflict, requiring human intervention to merge.
The merge itself, however, is just another immutable datum
describing which other two data it merges
and how it resolves any conflicts that merging might entail.
When there are several branches in a set of data, what should the view look like? Do we show just one branch or several? If just one, how do we decide which? In my experience, tools are much worse at making good views of branched data than at modeling and controlling it.
genealogyOne of the problems that faces collaborative efforts is the conflict between ownership and cooperation. I see this a lot in my work with family history data models: people say they want to share their work with others but they complain about how other people keep “messing up my data.” These disagreements usually manifest in the form of edit wars: people changing data back and forth and back again.
One feature of collaborative tools that enables edit wars is the existence of a single shared “master view” of the data. If the data is not persistent and does not support branches then this “master view” is also the “master data”: when I change a name field from “tychonievich” to “tychoniewicz” it changes the one and only copy that exists in the model. But even if all the versions exist in the model, if everyone who uses the tool views my version then I can make someone who disagrees upset.
If, however, you can use immutable data to model each individual piece of the shared ideas individually, and if you let each user pick their “preferred view”, then there is a magical world where I own my view, my data is safe from tampering, and I can still see, use, and benefit from any new datum which you might create.
That magical world is one of the things I am hoping to achieve with polygenea. Currently polygenea is only a model, but it is a model based on small immutable data that I believe can give us this happy owned-and-shared union.
I’m always hesitant when the adjective I think of to describe something is “magical”. Things that seem too good to be true usually aren’t true. But so far, it seems to be holding up. We’ll see what happens when I add more controllers and views.
Looking for comments…