Hacker News Reader

Comment by misterbowfinger | Hacker News Reader

I hate to be that person, but when I hear "ACID transactions in a distributed database", I hear Citus/Spanner/CockroachDB.

I'm positive that Citus & Spanner are quite different from FoundationDB, but I have no idea how. Googling didn't help much.

Can someone provide an overview of the differences?

View on HN

I think Citus is not really ACID.

Spanner (and to an extent its less mature OSS descendants Cockroach and TiKV) has more comparable goals, but is fairly different architecturally. For example, FoundationDB only requires N+1 replicas instead of 2N+1 to achieve N failure tolerance (even lots of databases with much weaker guarantees are in the latter category!), doesn't trust clocks at all, doesn't lose performance when transactions cross replica sets, and uses optimistic instead of pessimistic concurrency.

Also FoundationDB (and TiKV) make a distributed, transactional key/value store available as an API, while Spanner and Cockroach expose only a relational database layer. FoundationDB is designed philosophically with the idea that you want to have a single storage layer to manage operationally but should be able to mix and match data models and query engines above that layer.

On the other hand, FoundationDB doesn't currently have any full fledged high level database layer available. Someone will probably dig up our SQL layer (which was AGPL, I think) but I wouldn't really recommend using it in production because there is no active development team. Someone will probably try porting the SQL layers from TiDB and Cockroach.

Maybe Apple will open source more stuff in the future, but let's not get too greedy!

Wait how can it be ACID if it can tolerate N failures from N+1 nodes? Doesn't that kill consistency almost by definition? What level of isolation does it support? Snapshot? Serializable?

It is serializable and totally uncompromising. Philosophically pretty much everything defaults to the safest possible thing.

It can't tolerate N failures from N+1 nodes. It can tolerate N failures with N+1 copies of your data. In a big cluster you have plenty of nodes but storing everything 5 times to tolerate 2 failures is really expensive.

> It can't tolerate N failures from N+1 copies of your data

Sorry I got the terminology wrong, but that's a distinction without a difference. If it can tolerate N failures from N+1 copies, that means a network partition would allow any one copy to continue chugging along making changes by itself. You have two options: consistency is dropped and you downgrade to eventually consistent (at best), or availability is dropped meaning a single node can't make changes without a majority, which invalidates the N of N+1 failures claim. (Which is where the N failures of 2N+1 copies claim comes from in the first place: after N failures you still have a majority of copies.)

Or there's some other magic quorum protocol I've never heard of that makes the majority problem disappear.

FoundationDB stores 2N+1 copies of some "coordination state" and does a consensus algorithm whenever it is updated. But this state doesn't contain a copy of your data; basically think of it as storing a replication configuration. It's very small and rarely changes.

In the happy case, replication takes place using the replicas and quorum rules specified by this configuration. For example, you might require writes to succeed synchronously against all N+1 replicas of some transaction log. After N failures, there will still be 1 replica remaining with the latest transactions. But in order to proceed after any failures, you have to do a consensus transaction against a majority of replicas of the coordination state, to specify the new set of N+1 replicas you will be using. And you also make sure that the 1 replica you are recovering from knows you are doing it, so that it won't continue to accept writes under the old replication configuration.

There can't be two partitions capable of committing transactions, because (in this case) you need either

(a) All N+1 replicas of the log, so that you can commit synchronously, or (b) A majority (N+1 out of 2N+1) of the replicas of the coordination state, AND 1 replica of the log

Sorry if this isn't a great explanation. Anyway it does work. I expect that you could rephrase this as an optimization of a consensus protocol, though I think it would be hard to build a performant and realistically featureful implementation that way.

Nope your explanation made sense, thank you!

When I wrote that I was wondering if it used a second 2N+1 dataset just for coordination & consensus. This has the benefit of separating data from consensus, allowing the N of N+1 data failure. But at the end of the day consistency still comes down to a N of 2N+1 failure tolerance of that second coordination state. It's smaller easier to replicate etc etc but it seems like it still has the same fault tolerance as just replicating the data 2N+1 times. It sounds like it's worked out great in practice for FDB.

But you say it rarely changes... but wouldn't it have to change every time there's a change to the dataset? I feel like this means you have to do even more replication and consensus than just replicating the data without this second consensus state.

You only have to write to the coordination state when there is a failure. You can commit millions of transactions in the happy case without ever doing such a write. And failure detector performance and other engineering concerns are usually more of a limitation, in practice, on the performance of recovery than the latency of the coordination state consensus, even when the coordinators are geographically distributed.

So the strategy is to optimistically assume that there are no failures and just replicate to all N+1 copies. If there's a failure then back off to the consensus state to coordinate the fix rigorously.

In the best case with no failures this works great. But as the number of failures increases, I feel like due to the extra synchronization there will be an inflection point where the cost of the extra layers of coordination will be higher than just synchronizing the data directly. But due to 'other concerns' that inflection point is pushed back by a lot.

Is that a reasonable characterization?

If you expect to have lots of (hopefully very temporary!) node failures, I think FoundationDB has another trick up its sleeve. You can store (say) N+2 replicas of transaction logs, which are also relatively small and (since sequential) efficient. Then you have a write quorum of N+1 and a recovery quorum of 2 logs, and you don't have to do coordination on every failure.

It's certainly true that with enough failures you aren't going to make much progress. I'm not sure that is any less true with plain old state machine replication protocols, though.

Yup, this works. I wonder if this is the first commercial application of this insight? http://hh360.user.srcf.net/blog/2016/08/majority-agreement-i...

Can you tell us what consensus algorithm you're using? Raft, or something else? Your own implementation or something off the shelf?

I know VSAN uses these and calls them witnesses.

https://cormachogan.com/2014/04/01/vsan-part-21-what-is-a-wi...

I'm not sure.

The coordination consensus is (our own implementation of) disk paxos, which we liked for its operational properties in our context (the coordinators don't need to know about each other or communicate directly). An early version of fdb had a dependency on Zookeeper for this purpose; you can use anything.

Maybe not all data is replicated across all zones, so zones provide consensus but replicas provide data. Basically you have witness with enough information to provide consistency but without the full data store.

The datacenter-aware mode documentation [0] says “Although data will always be triple replicated in this mode, it may not be replicated across all datacenters.”

Why is that?

[0] https://apple.github.io/foundationdb/configuration.html?data...

I think it's just saying that it's willing to place two of the three replicas in a datacenter, for example if one of the three datacenters is down. This has downsides, since losing a datacenter will make it aggressively fill up disks, but mitigates against subsequent failures causing data loss.

Most of the people who have run FoundationDB at scale have, for performance reasons, used configurations other than the "datacenter aware" mode for their inter region replication, so they may not be the strongest thing operationally.

There is some work that from what I can see in the code is still in progress to build a new, almost magical inter-region replication mode that I am very excited about, which combines synchronous replication to a "satellite" datacenter within region with asynchronous replication between regions and recovery logic that will finish replication and fail over in case of a partial failure of a region. You get fast transaction commits (much less than the inter region ping time), can fail over to a secondary region automatically and safely (without losing any committed transactions) in the vast majority of circumstances, and in the worst case you can (manually, because you are accepting data loss!) give up very recently committed transactions to fail over.

How would FoundationDB stay externally consistent with asynchronous cross-region replication?

Thank you for your time and FoundationDB—along with @nlavezzo, and team(s)!

The satellite mode that I described is an active/passive mode. One region is accepting reads and writes; the other is just replicating everything. When it looks like the active region is in trouble, the asynchronous replication is "finished up" before switching over to the other region. The multiple datacenters in each region ensure that usually a regional failure will be "slow enough" that this automatic process (which after all only takes hundreds of milliseconds to seconds) can usually complete before a region goes away. And this will be handled pretty transparently by the datastore.

If a region is blown up instantly by an orbital laser cannon, then the database will go down and you will have to manually tell it to recover ACI in the other region, sacrificing the durability of whatever committed transactions in the lost region were destroyed by the laser cannon.

While that’s perfect to shield from orbital laser cannons, is active/active geo-independent replication possibile?

Well, if you want ACID then you are going to have to pay for at least one geographic round trip per committed transaction. (So why not go active/passive, and have at least one of your datacenters be fast?)

But what if you have different pieces of data and you want them to be fast in different datacenters? I think a great solution to this can be layered on top of multiple FoundationDB clusters, each using the satellite mode, but this is one thing that I at least haven't been able to think of a way to provide properly at the data model agnostic key/value store layer - the details about what to put where seem fundamentally dependent on your data model.

> So why not go active/passive, and have at least one of your datacenters be fast?

While local writes would stay fast, wouldn’t active/passive see higher-latency non-local writes than Spanner or Fauna’s (assuming a NAM-EUR-ASIA topology)?

I agree with and do appreciate the multiple FoundationDB clusters suggestion.

I'm speculating, but I think in this mode, from the "slow" datacenters you would see one round trip time to start a transaction, then reads will be fast (they can be done safely from your local datacenter because of MVCC), and then one round trip time to commit the transaction. I think that's as good as Spanner does with the same geography, but I'm not sure. I think you could get rid of the first round trip time even without any clock synchronization nonsense, by speculating on a read version for read/write transactions. And 1xRTT is obviously as fast as physically possible for ACID.

Update: Apparently Spanner is way slower than I thought in "slow" datacenters, doing a round trip for every transactional read. So this would absolutely stomp that. (Although spanner, as a higher level system, has the ability to move different data to be fast in different regions built in, which is nice, and as I said it will probably have to be a layer feature in the fdb world)

"or example, FoundationDB only requires N+1 replicas instead of 2N+1 to achieve N failure tolerance"

Wait, don't you need 3N+1 to tolerate N number of failures for it to be Byzantine fault tolerant? Is that not a goal of FoundationDB?

FoundationDB is not Byzantine fault tolerant.

Spanner is geographically distributed and synchronizes over Google’s fiber. I’m not sure where FoundationDB falls on the spectrum, but there is “distributed” meaning runs on multiple machines, vs multiple availability zones (which could be in the same rough geographic area to minimize latency), vs multiple geographic regions, which is one of Google’s design goals for its distributed infrastructure nowadays: to be able to withstand a natural disaster or other disruption that takes a whole region offline, without missing a beat.

There’s still a lot to be said for the property, “scales horizontally to N machines,” of course, even if those machines have to be in the same data center.

It's more like what CockroachDB or TiDB use underneath. They all are suited for local clusters, but cannot perform well enough replicating across multiple far away datacenters over public internet, latency trade offs would be unbearable. Spanner is a bit different, with Google's fancy clocks and fancy networks, it can get better latency trade offs that might satisfy more applications.

Citus I can't remember, but if Citus does it properly wrt consistency, it should be in the same category as CockroachDB and TiDB, there is no magic.

CockroachDB (and I assume TiDB as well) can have the same properties and same awesome latencies as Spanner, if you have the same hardware.

So if you actually put down your own fiber, and install GPS clocks in each rack, you’ll be able to enjoy the same results.

Does CockroachDB use TrueTime or a similar technique?

See CockroachDB’s Living Without Atomic Clocks [0]. TrueTime [1] is a proprietary Google technology. Considering TrueTime upper bound uncertainty (< 10ms) [2], it may depend on Google’s network quality and breadth.

[0] https://www.cockroachlabs.com/blog/living-without-atomic-clo...

[1] https://cloud.google.com/spanner/docs/true-time-external-con...

[2] https://static.googleusercontent.com/media/research.google.c...

Do they do something like: http://fireless.cs.cornell.edu/publications/dtp_sigcomm16.pd... ?

CockroachDB assumes you use NTP on your servers — but if you actually put GPS clocks into your servers, you could adjust the safety interval it assumes for clock drift down, and it'd behave pretty much the same as Google's.

Well for one, Spanner is not available except as a service.

Reply on news.ycombinator.com