Hacker News Reader

Comment by haberman | Hacker News Reader

This is a beautiful site with tons of information, graphs, lists, examples, etc. and yet omits the one thing that underpins it all: how it actually works.

The claims are: serializable ACID cross-machine transactions "without performance penalty." MVCC with optimistic concurrency control.

Optimistic concurrency control means that the server has to check the version on all modified data before the transaction commits. Cross-machine transactions mean that this version check has to happen on multiple machines. ACID means that both machines have to either commit (if all the version checks succeed) or roll back. How are you going to reconcile all of these requirements without resorting to two-phase commit, which most certainly has a performance penalty? And how are you going to get serializable transactions across machines without processing these cross-machine commits one at a time (waiting for two-phase commit each time)?

I'm just not seeing it.

View on HN

FoundationDB co-founder here.

I'll try to address your questions. This isn't a complete explanation of how our system works!

Most people trying to solve this problem have approached it by trying to take multiple machines, each capable of processing transactions, and do distributed transactions between them. This leads to systems that do local transactions fast but global transactions much more slowly, and a tradeoff between the quality of fault tolerance (paxos=good, 2-phase=bad) and commit performance.

Our approach is instead to decouple the first job you mention (checking if transactions conflict to provide isolation) from the second job (making transactions durable). These can then be scaled independently.

The first job, conflict resolution, is a small fraction of the total work and needs access only to the key ranges used by each transaction, not the existing contents of the database or the actual values being written. This allows it to be very fast.

The rest of the system is a consistent, durable distributed store that has to preserve a predetermined ordering of writes, and provide a limited window of MVCC snapshots for reads.

Does that help at all?

That sounds alot like partialy atleast, the same model datomic has?

I can only speculate, because I have never used datomic.

Like FoundationDB, datomic does appear to separate transaction processing from storage.

A few relevant differences:

- Datomic provides transaction isolation through stored procedures which run on its single "transactor", while FoundationDB provides interactive transactions.

- To my knowledge datomic does not claim to be interested in high write scalability, which we definitely are.

- Datomic is designed to keep multiversion history indefinitely, while FoundationDB keeps it just long enough to execute short transactions.

I still don't see it. Say you have conflicting transactions T1 and T2 that both update data on two machines M1 and M2. If these transactions race to commit, how do you guarantee consistency? Even if you have a perfect, zero-latency oracle that can tell you that T1 and T2 conflict, you still need M1 and M2 to form consensus about which transaction commits first, and to make sure that both machines either commit or roll back (I am assuming that both machines have their own transaction log). It still sounds to me like 2PC is required.

Specific questions: does each machine have its own commit log? Is each machine authoritative for its range of the keyspace, in that it can serve reads without having to consult other machines?

The conflict resolution service assigns a global ordering to transactions as well as pass/fail. Transactions that fail don't do any writes. Transactions that pass still aren't durable, they could be rolled back by a subsequent failure until they get on disk in a few places.

Each machine doesn't have its own commit log at the level of the distributed database. (The key/value store where we locally store data on each node happens to also use write ahead logging, but this is not an architectural requirement). Ideally transactions just have to be made durable in some N places to be considered committed. In practice, we elect specific machines to a transaction logging role, among other reasons because SSDs do better at providing fast durable commits if they aren't also serving random reads.

Each machine is authoritative for reads for some ranges of the keyspace and for the range of versions it knows about. It proactively fetches writes for newer versions. If it gets a request for a version it hasn't managed to get the writes for yet, the read has to wait while that storage server catches up. In practice this lag is very small, as you can see from our latency measurements.

Serialized transactions over a broad distribution of keys isn't a huge problem, but you're right: this bodes poorly for hot data. I'm more concerned about their CAP semantics: I'm sorry, but claiming multidc availability and acid transactions is not gonna work.

FoundationDB co-founder here.

As any ACID database must, we choose Consistency over Availability in the CAP theorem sense. This means that when a datacenter is disconnected or poorly connected to the internet, the database is not available for writes in that datacenter. If you are serving a web site to the internet, and need it to stay available if one Amazon AZ fails, this isn't too bad.

Some applications really do need disconnected operation, and thus 'AP' semantics. (For example, a grocery list for a mobile phone, or an application that must be available everywhere if the entire Internet partitions.)

So you require quorum over data centers to stay up? How do you provide transactional consistency between dcs? Multipaxos over blocks of transactions with delayed failure?

We require a quorum over coordination servers to stay up. For example, if you only have two datacenters with actual DB servers, a third coordination server out in the cloud somewhere can act as a tiebreaker (it will be lightly loaded).

These coordination servers do paxos, but are only needed when there are failures or role changes - they don't participate at all in committing individual transactions. Normally, we only need a single geographic ping time to do a durable transaction if it originates in the current 'primary' datacenter.

For further improved latency, we plan to allow each individual transaction to decide whether it needs multi-datacenter durability. The commit process is the same, but we can notify the client of success earlier if it is willing to take the risk that a WAN partition or meteor strike violates its 'D' guarantee. ACI are guaranteed either way.

Gotcha. That sounds solid to me; would be a good explanation to put in your feature list.

Sounds like your coordinators are authoritative masters for transaction ordering. Does that imply a single-machine limit to throughput in a given dc? Presumably the ordering process is much less expensive than the kv store itself, so this might not be a practical issue.

What happens when nodes are asymmetrically partitioned from the coordinator and peers? E.g. a node is unreachable by a peer, but reachable by a coordinator, or vice versa?

Reply on news.ycombinator.com