You Cannot Correctly Represent Change Without Immutability

The title of this blog post is a quote by Rich Hickey, talking about the Datomic database. Its a beautiful statement, at once illuminating and paradoxical. It drives at the heart of the design of both Clojure and Datomic, and embraces the difference between identity and state.

What is change? That seems like an obvious question, but my first attempt at defining it was "some change to a quantifiable set of qualities about some object." Woops, I used change recursively there ... that's not going to help.

In the real world, things change in ways we can observe; the leaf falls from the tree, the water in the pot boils, the minute hand moves ever forward.

How do we recognize that things have changed? We can, in our memories, remember a prior state. We remember when the leaf was green and attached to a branch; we remember when the water came out of the tap, and we remember looking at the clock a few minutes ago. We can hold both states in our mind at the same time, and compare them.

How do we represent change in traditional, object-oriented technologies? Well, we have fields (or columnus) and we change the state in place:

• leaf.setColor(BROWN).detachFromTree()
• UPDATE LEAVES SET COLOR = 'BROWN' WHERE ID = ?ID
• water.setTemperature(212)
• or we see time advancing via System.currentTimeMillis()

Here's the challenge: given an object, how do you ask it about its prior state? Can you ask leaf.getTreeDetachedFrom()? Generally, you can't unless you've gone to some herculean effort: the new state overwrites the old state in place.

When Rich talks about conflating state with identity, this is what he means. With the identity and state conflated, then after the change in state, the leaf will now-have-always-been fallen from the tree, the water will now-have-always-been boiled, and the clock will now-eternally be at 9:49 AM.

What Clojure does in memory, and Datomic does in the database, is split identity and state. We end up with leaf1 as {:id "a317a439-50bb-4d37-838a-c8eef289e22f" :color :green :attached-to maple-tree} and leaf2 as {:id "a317a439-50bb-4d37-838a-c8eef289e22f" :color :brown :on-ground true}. The id is the same, but the other attributes can vary.

With immutability, changes in state are really new objects; a new version, or "quantifiable set of qualities", that does not affect the original version. It is possible to compare two different iterations of the same object to see the "deltas". In Datomic, you even have more meta-data about when such state changes occur, what else changed within the same transaction, and who is the responsible party for that transaction.

The essence here is not to think of an object as a set of slots you can put new data into. Instead, think of it as a time-line of different configurations of the object. The fact that late in the time-line, the leaf has fallen from the tree does not affect the fact that earlier on the time-line, the leaf was a bud on a branch. The identity of the leaf transcends all those different states.

In the past, I've built systems that required some of the features that Datomic provides; for example, being able to reconstruct the state of the entire database at some prior time, and strong auditing of what changes occurred to what entities at a specific time (or transaction). Rich knows that others have hit this class of problem; part of his selling point is to ask "and who really understands that query" (the one that reconstructs prior state). He knows people have done it, but he also knows no one is very happy about its performance, correctness, or maintainability ... precisely because traditional databases don't understand mutability: they live in that eternal-now, and drag your application into the same world view.

That's why I'm excited by Datomic; it embraces this key idea: separate identity from state by leveraging immutability and from the ensuing design, much goodness is an automatic by-product. Suddenly, we start seeing much of what we take as dogma when developing database-driven applications to be kludges on top of an unstable central idea: mutable state.

For example: read transactions are a way to gain stable view of interrelated data even as the data is being changed (in place); with Datomic, you always have a stable view of all data, because you operate on an immutable view of the entire database at some instance in time. Other transactions may add, change, or replace Datoms in the database, but any code that is reading from the database will be completely unaware of those changes, even as they lazily navigate around the entire database.