Hacker News Reader

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)

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.

"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.