I'll try to give you a quick introduction. The architecture talk I recorded for new engineers working on the product ran to four or five hours, I think :-). In short, it is serializable optimistic MVCC concurrency.

A FDB transaction roughly works like this, from the client's perspective:

1. Ask the distributed database for an appropriate (externally consistent) read version for the transaction

2. Do reads from a consistent MVCC snapshot at that read version. No matter what other activity is happening you see an unchanging snapshot of the database. Keep track of what (ranges of) data you have read

3. Keep track of the writes you would like to do locally.

4. If you read something that you have written in the same transaction, use the write to satisfy the read, providing the illusion of ordering within the transaction

5. When and if you decide to commit the transaction, send the read version, a list of ranges read and writes that you would like to do to the distributed database.

6. The distributed database assigns a write version to the transaction and determines if, between the read and write versions, any other transaction wrote anything that this transaction read. If so there is a conflict and this transaction is aborted (the writes are simply not performed). If not then all the writes happen atomically.

7. When the transaction is sufficiently durable the database tells the client and the client can consider the transaction committed (from an external consistency standpoint)

The implementations of 1 and 6 are not trivial, of course :-)

So a sufficiently "slow client" doing a read write transaction in a database with lots of contention might wind up retrying its own transaction indefinitely, but it can't stop other readers or writers from making progress.

It's still the case that if you want great performance overall you want to minimize conflicts between transactions!

Great write-up.

Is this similar to how Software Transactional Memory (STM) is implemented? It sounds very very similar indeed.

This is a good explanation of how it happens on a single node. What do you do when the transaction is distributed? How do you achieve consensus? Is there a write up on it anywhere?

The only thing that's different in a distributed cluster is the implementations of steps 1 and 6. As voidmain said, the details of that are not trivial, ESPECIALLY the details of how it never produces wrong answers during fault conditions.

I don't know that there's been an exhaustive writeup of that part, but maybe one of us or somebody on the Apple team will put something together. It probably won't fit in an HN comment though!

Or... maybe this is the part where I point out that the product is now open-source, and invite you to read the (mostly very well commented) code. :-)

The documentation ( https://apple.github.io/foundationdb/technical-overview.html ) sells the product, but doesn't give a deep enough explanation. As a closed source product, that's understandable.

Going forward as an opensource product, I hope to see some clarity on the "how it works"... Distributed, performant ACID sounds good, almost too good to be true. Not that I doubt it at the moment, I just want to understand it better :)

Thanks. Can you elaborate on how 6 is actually accomplished? Various earlier comments have hinted that the transactional authority (conflict checking) can actually scale 'horizontally' beyond the check-throughput that can be archived by a single node. Is that the case? and whats the magic sauce for doing that for multi-object transactions? :)

Yes, conflict resolution is for most workloads a pretty small fraction of total resource use so you usually don't need a ton of resolvers (I think out of the box it still comes configured with just one?), but it can scale conflict resolution horizontally.

The basic approach isn't super hard to understand, though the details are tricky. The resolvers partition the keyspace; a write ordering is imposed on transactions and then the conflict ranges of each transaction are divided among the resolvers; each resolver returns whether each transaction conflicts and transactions are aborted if there are any conflicts.

(In general the resolution is sound, but not exact - it is possible for a transaction C to be aborted because it conflicts with another transaction B, but transaction B is also aborted because it conflicts with A (on another resolver), so C "could have" been committed. When Alec Grieser was an intern at FoundationDB he did some simulations showing that in horrible worst cases this inaccuracy could significantly hurt performance. But in practice I don't think there have been a lot of complaints about it.)

Does the implementation handle the case that you want to do a write that is conditioned on a prior read finding no corresponding record(s)?

Of course. FDB thinks about read and write conflict ranges, which are functions of the keys, not the values (or lack thereof). A read of a non-existent key conflicts with a write to that key. A read of a range of keys conflicts with a write to a key in that range, even if that key did not have an associated value at the time of the original read.

Any chance you’d be able to find that video, it sounds extremely interesting.

Thanks, that explanation is really helpful!

> I didn't think an MVCC implementation could provide that level of isolation

MVCC needs a bit of additional logic ontop to be serializable - "Serializable snapshot isolation" is a good keyword to search for - But it's definitely possible.

https://courses.cs.washington.edu/courses/cse444/08au/544M/R...

https://drkp.net/papers/ssi-vldb12.pdf

https://wiki.postgresql.org/wiki/Serializable

Edit: Formatting

Apache Trafodion does as well:

http://trafodion.apache.org

I mean, PostgreSQL is MVCC and it clearly supports serializable as an isolation level... have you tried using Google?

https://wiki.postgresql.org/wiki/Serializable

A lot of people apparently hated that I attacked this person, and downvoted me; but what the person who posted this comment was doing is intentionally throwing shade at and casting doubt on a project by saying "I think that the claims on this webpage don't make any sense as this should be impossible". It comes off as "oh come on, this doesn't even sound plausible; I call bullshit".

This then causes people who aren't versed with the product or the technology to decrease their perception of the product, and puts the team behind it in a position of having to not just come to its defense but to do so quickly due to the perception concerns.

Meanwhile, if they just do a basic search for "MVCC serializable" they would find that they were wrong; which means that it took more time to leave this insulting comment than it would have taken them to learn how this can work.

As a community, we really really really really need to beat down on casual cynics like this, who like to lazily "call bullshit" or play the "citation needed" card as a way to undermine the credibilty of other peoples' products. We live in a future where the answers to these kinds of doubts are a moment away: this particular form of debate tactic needs to die.

I absolutely was not throwing shade at the project, I was just trying to understand. I have a great interest in distributed systems that can efficiently implement serializable ACID transactions, and looked at their documentation with great interest to see how they implemented it. I honestly thought that MVCC could only efficiently implement Snapshot Isolation. So I figured my understanding was wrong, or at worst there's a typo in their documentation and they use something other than MVCC under the hood. Either way, I wanted to know more about their architecture.

I'll take your feedback under consideration, and I'm sorry to have irritated you.

I suspect the downvoting was for the "LMGTFY"-esque part of your response. Dunno, don't care, just offering a possible suggestion.