Rich Hickey: Deconstructing the Database

Rich Hickey: Deconstructing the Database(youtube.com)

229 points by noidi 13 years ago | 90 comments

saurik 13 years ago |

Watching this talk has so far (I'm halfway through, and now giving up) been very disappointing, primarily because many of the features and implementation details ascribed to "traditional databases" are not true of the common modern SQL databases, and almost none of them are true of PostgreSQL. As an initial trivial example, many database systems allow you to store arrays. In the case of PostgreSQL, you can have quite complex data types, from dictionaries and trees to JSON, or even whatever else you want to come up with, as it is a runtime extensible system.

However, it really gets much deeper than these kinds of surface details. As a much more bothersome example that is quite fundamental to the point he seems to be taking with this talk, at about 15:30 he seriously says "in general, that is an update-in-place model", and then has multiple slides about the problems of this data storage model. Yet, modern databases don't do this. Even MySQL doesn't do this (anymore). Instead, modern databases use MVCC, which involves storing all historical versions of the data for at least some time; in PostgreSQL, this could be a very long time (when a manual VACUUM occurs; if you want to store things forever, this can be arranged ;P).

http://en.wikipedia.org/wiki/Multiversion_concurrency_contro...

This MVCC model thereby directly solves one of the key problems he spends quite a bit of time at the beginning of his talk attempting to motivate: that multiple round-trips to the server are unable to get cohesive state; in actuality, you can easily get consistent state from these multiple queries, as within a single transaction (which, for the record, is very cheap under MVCC if you are just reading things) almost all modern databases (Oracle, PostgreSQL, MySQL...) will give you an immutable snapshot of what the database looked like when you started your transaction. The situation is actually only getting better and more efficient (I recommend looking at PostgreSQL 9.2's serializable snapshot isolation).

At ~20:00, he then describes the storage model he is proposing, and keys in on how important storing time is in a database; the point is also made that storing a timestamp isn't enough: that the goal should be to store a transaction identifier... but again, this is how PostgreSQL already stores its data: every version (as again: it doesn't delete data the way Rich believes it does) stores the transaction range that it is valid for. The only difference between existing SQL solutions and Rich's ideal is that it happens per row instead of per individual field (which could easily be modeled, and is simply less efficient).

Now, the point he makes at ~24:00 actually has some merit: that you can't easily look up this information using the presented interfaces of databases. However, if I wanted to hack that feature into PostgreSQL, it would be quite simple, as the fundamental data model is already what he wants: so much so that the indexes are still indexing the dead data, so I could not only provide a hacked up feature to query the past but I could actually do so efficiently. Talking about transactions is even already simple: you can get the identifier of a transaction using txid_current() (and look up other running transactions if you must using info tables; the aforementioned per-row transaction visibility range is even already accessible as magic xmin and xmax columns on every table).

DanWaterworth 13 years ago | |

In another talk he addresses your point specifically. He said, and I'm paraphrasing:

"It doesn't matter if you're using append only data-structures if your view of the world is update in place".

PostgreSQL exposes a view to the world of an update in place database, no matter what it's doing underneath. You could create a new interface to PostgreSQL's internals that doesn't and if you did, it would look a lot like datomic.

saurik 13 years ago | | |

First, there is a major difference between MVCC and update-in-place that you can detect as a client, and that difference is that the problems that Rich outlines at the beginning of his talk do not happen: if one client edits something in the database, other transactions do not get an inconsistent view because the data on disk has already been permanently and irrevocably "updated in place". (Which, to be clear, means that modern SQL databases do not "expose a view to the world of an update in place database".)

Second, if all that is required to get his model is to add a command to an existing database (such as PostgreSQL, as I feel I know enough about how it works to be confident that this would be a reasonably simple task) "mark the current transaction read-only and pretend that it is as old as transaction X" (something that can be implemented quite rapidly in an existing system like PostgreSQL) we really aren't talking about something that is either very new, or that totally reinvents the "traditional database".

lucian1900 13 years ago | |

The fundamental problem is even though it uses MVCC internally, Postgres doesn't expose that model. Instead, it exposes an update-in-place model.

TheMiller 13 years ago | | |

To elaborate further on what saurik has already pointed out: Hickey's "update-in-place" characterization of relational databases places blame in the wrong place. This is more about how people think about the data models; they think of their primary keys as identifying places, and updating rows as modifying those places. The relational model itself does not encourage this mode of thinking, although SQL arguably does, unless you think of UPDATE as shorthand for DELETE followed by INSERT. It's not that uncommon to build data models, or parts of models, that have the characteristic of never deleting facts. It's true that time-based as-of queries in such models are unwieldy, but that's a problem of the query languages that can be addressed by how queries are constructed, without redesigning the entire database system. There is research on "temporal databases" that addresses this, although I'm not up to date on it.

What I could not understand from the talk or from googling for more information on Datomic afterwards, is how it supposedly simplifies anything about the consistency issues that he talks about, with respect to the read/decide/write sequence. You read; time passes; other people make changes; when you write, the real world (modeled in your "transactor" as the single common store and arbiter of what is) will have changed.

saurik 13 years ago | | |

Please see the response I left from ten minutes ago to DanWaterworth's similar comment (the one where I point out that, as a client, you can tell the difference between those two models by testing for some of the specific problems that are mentioned near the beginning of this talk; yadda yadda).

krosaen 13 years ago | |

I had no idea one could get a consistent read view across multiple queries within a transaction using most sql databases. That does poke a hole in a major benefit that I thought was unique to datomic, great to know!

However, I do think trying to setup a sql database to be able to query against any previous view of the world based on a transaction id as datomic allows wouldn't be as "simple" as you make it out to be.

saurik 13 years ago | | |

The reason I claim this would be simple is that PostgreSQL is almost already doing this. The way the data is stored on disk, every row has two transactions identifiers, xmin and xmax, which represent the transaction when that row was inserted the the transaction that row was deleted; rows, meanwhile, are never updated in place, so the old data stays around until it is deleted by a vacuum.

To demonstrate more tangibly how this works, I just connected to my database server (running PostgreSQL 9.1), created a table and added a row. I did so inside of a transaction, and printed the transaction identifier. I then queried the data in the table from a new transaction, showing that the xmin is set to the identifier of the transaction that added the row.

Connection 1:

    demo=> create table q (data int);
    CREATE TABLE
    demo=> begin; select txid_current();
    BEGIN
    189028
    demo=> insert into q (data) values (0); commit;
    INSERT 0 1
    COMMIT
    demo=> begin; select xmin, xmax, data from q;
    BEGIN
    189028|0|0

Now, while this new transaction is still open, from a second connection, I'm going to create a new transaction in which I am going to update this row to set the value it is storing to 1 from 0, and then commit. In the first connection, as we are still in a "snapshot" (I put this term in quotes, as MVCC is obviously not copying the entire database when a transaction begins) from a transaction started before that update, we will not see the update happen, but the hidden xmax column (which stores the transaction in which the row is deleted) will be updated.

Connection 2:

    demo=> begin; select txid_current();
    BEGIN
    189029
    demo=> update q set data = 1; commit;
    UPDATE 1
    COMMIT
    demo=> select xmin, xmax, data from q;
    189029|0|1

Connection 1:

    demo=> select xmin, xmax, data from q;
    189028|189029|0

As you can see, the data that the other transaction was referencing has not been destroyed: the old row (the one with the value 0) is still there, but the xmax column has been updated to indicate that this column no longer exists for transactions that began after 189029 committed. However, at the same time, the new row (with the value 1) also exists, with an xmin of 189029: transactions that begin after 189029 committed will see that row instead. No data was destroyed: and this data is persisted this way to disk (it isn't just stored in memory).

My contention then is that it should be a fairly simple matter to take a transaction and backdate when it began. As far as I know, there is no reason that this would cause any serious problems as long as a) it was done before the transaction updated or inserted any data, b) there have been no vacuums during the backdated period, c) HOT (heap-only tuple) updates are disabled (in essence, this is an optimization designed to do online vacuuming), and maybe d) the new transaction is read only (although I am fairly confident this would not be a requirement).

For a more complete implementation, one would then want to be able to build transactions (probably read-only ones; I imagine this would cause serious problems if used from a writable transaction, and that really isn't required) that "saw all data as if all data in the database was alive", which I also believe would be a pretty simple hack: you just take the code that filters dead rows from being visible based on these comparisons and add a transaction feature that lets you turn them off. You could then use the already-implemented xmin and xmax columns to do your historical lookups.

P.S. BTW, if you want to try that demo at home, to get that behavior you need to use the "repeatable read" isolation level, which uses the start of the transaction as the boundary as opposed to the start of the query. This is not the default; you might then wonder if it is because it is expensive and requires a lot more coordination, and as far as I know the answer is "no". In both cases, all of the data is stored and is tagged with the transaction identifiers: the difference is only in what is considered the reference time to use for "which of the rows is alive".

However, it does mean that a transaction that attempts to update a value that has been changed from another transaction will fail, even if the updating transaction had not previously read the state of the value; as most reasonable usages of a database actually work fine with the relaxed semantics that "data truly committed before the query executes" provides (as that still wouldn't allow data you update to be concurrently and conflictingly updated by someone else: their update would block) and those semantics are not subject to "this transaction is impossible" errors.

Both Connections (setup):

    demo=> set session characteristics as transaction isolation level repeatable read;
    SET

richhickey 13 years ago | | |

Datomic allows one to get a consistent basis for multiple queries, separated by arbitrary amounts of time, outside of any transactions. Having to group queries motivated and conducted by different parts of your system into a single transaction in order to get a consistent basis is a source of coupling.

jeltz 13 years ago | | |

To get a consistent view across multiple queries you just use the SERIALIZABLE isolation level. In PostgreSQL REPEATABLE READ also works, but the standard does not guarantee this (the standard allows for ghost reads since it assume you use locking rather than MVCC snapshots to implement REPEATABLE READ).

The ability to query any historical view of the data is indeed not there in PostgreSQL in any simple or reliable way. That is an advantage of Datomic, but I do not see why it would be impossible to implement in a "traditional database".

lhnz 13 years ago |

There are two people that I will stop what I'm doing and watch every new lecture they make: Rich Hickey and Bret Victor. Both are visionaries.

erikpukinskis 13 years ago |

Fascinating stuff. Some things that came up for me while watching this and the other videos on their site[1]:

It's not Open Source, for anyone who cares about that. It's interesting how strange it feels to me for infrastructure code to be anything other then Open Source.

I'm sort of shocked that the query language is still passing strings, when Hickey made a big deal of how the old database do it that way. I guess for me a query is a data structure that we build programmatically, so why force the developer to collapse it into a string? Maybe because they want to support languages that aren't expressive enough to do that concisely?

[1] http://www.datomic.com/videos.html

jkkramer 13 years ago | |

You are not forced to pass strings. That's merely a convenience (for Java). You can construct and pass data structures instead.

nickik 13 years ago | | |

Yes, and in clojure you acctually use data literals not just strings.

sriram_malhar 13 years ago |

I'm always puzzled when the Datomic folks speak of reads not being covered under a transaction. This is dangerous.

Here's the scenario, that in a conventional update-oriented store, is termed as a "lost update". "A" reads object.v1, "B" reads the same version, "B" adds a fact to the object making it v2, then "A" comes along and writes obj.v3 based on its own _stale_ knowledge of the object. In effect, it has clobbered what "B" wrote, because A's write came later and has become the latest version of the object. The fact that DAtomic's transactor serialized writes is meaningless because it doesn't take into account read dependency.

In other words, DAtomic gives you an equivalent of Read-committed or snapshot isolation, but not true serializability. I wouldn't use it for a banking transaction for sure. To fix it, DAtomic would need to add a test-and-set primitive to implement optimistic concurrency, so that a client can say, "process this write only if this condition is still true". Otherwise, two clients are only going to be talking past each other.

Tuna-Fish 13 years ago | |

You are incorrect -- datomic transactions can depend on the previous state of the DB, and prevent it from being modified from under it. To do this, you do the transaction in the transactor process.

fogus 13 years ago | |

    ...would need to add a test-and-set primitive

Datomic provides CAS via its `:db.fn/cas` database function. I'm not sure that it's documented at the moment.

tensor 13 years ago | |

I think "transaction functions" are intended to provide a solution to that, although I do wonder how it would fair performance wise under very cpu intensive transaction functions.

richhickey 13 years ago | |

Addressed here: http://news.ycombinator.com/item?id=4448351

sriram_malhar 13 years ago | | |

Lovely. That addresses my concern.

bsaul 13 years ago |

Anyone understands how this system would deal with CAP theorem, in the case of a regular "add 100$ then remove 50$ to the bank account, in that order and in one go" type of transaction ? The transactor is supposed to "send" novelty to peers, so that they update their live index. That's one point where i would see trouble (suppose it lags, one "add" request goes to one peer, the "read" goes to the second, you don't find what you just add...) Another place i see where it could mess things up is the "Data store" tier, which uses the same traditional technics as of today to replicate data between different servers (one peer requests facts from a "part" of the data store that's not yet synchronized with the one a second peer requests). It seems like all those issues are addressed on his "a fact can also be a function" slide, but he skips it very quickly, so if anyone here could tell me more...

plaeremans 13 years ago | |

Well there is one transactor, the transactor handles each transaction sequential, so the transactor can abort a transaction when the world has changed since it got queued to the transactor.

There is (virtually) infinite read scalability. Each datum has a time associated with it, so you might not see the latest information (yet), you know the state of the world at a certain point in time.

I think it 's a really well designed system.

azolotko 13 years ago | |

In Datomic you can setup a function the transactor can call within a transaction. This function takes the current value of the database and other supplied arguments (e.g. $100 and -$50 from your example) and according to its logic produces and returns a list of "changes" the transactor should apply to the database. The function is pure in sense that it doesn't have any side effects, it just "expands" into new data. And of course this "expantion" and application of its results happens in the same transaction.

olivergeorge 13 years ago | |

This might only be vaguely related. It's an example of managing bank account balances using datomic taking advantage of transaction functions.

https://gist.github.com/3134849

ilaksh 13 years ago | |

Well he did put "atomic" in the name.

arscan 13 years ago |

I recall Datomic making a bit of a splash on HN when it was announced 6+ months ago, but basically crickets since then. Anybody build something cool that took advantage of Datomic's unique design?

puredanger 13 years ago | |

We're building some stuff with it atm but I can't go into details. I've run into several others using it for a variety of things as well and the support group is active. http://groups.google.com/group/datomic

Tuna-Fish 13 years ago | |

People tend to be more conservative about data than they are about the other parts of their stack -- probably for a good reason.

I don't think datomic (or it's kin) will have that huge of an influence until years from now.

kinleyd 13 years ago | | |

I think Datomic is potentially disruptive and represents some great thinking on the part of an individual. Whether it will be disruptive will hinge on how well that thinking has subsumed the years of industry experience and practicalities, not to forget the conservative approach to data. I'd be interested to see how it pans out.

it 13 years ago | | |

If you want to be conservative about your data, it looks like Datomic is an excellent choice. It preserves the entire history of your data instead of allowing it to be modified in place.

lucian1900 13 years ago | |

At least I avoid using it (even though I really like its design) because it isn't open source. I will not trust my data to something I can't even attempt to maintain myself if necessary.

brlewis 13 years ago |

Anyone have a summary for those of us who don't want to watch an hour-long video?

breckinloggins 13 years ago | |

I'm only a few minutes into it, but so far the tl;dr is:

"There are lots of things we do with respect to databases simply because of the limitations of our databases. Here are some things that could be made far simpler if you just had a better database."

Yes it's partly a sales presentation for Datomic, but you could do worse than be sold by Rich Hickey.

breckinloggins 13 years ago | | |