4 ms·

I'm not an expert, but don’t all modern databases suffer from these issues? I thought they all depended on clock sync like Google Spanner.

aphyr 8y ago
In short, no: many transactional databases don't rely on clocks for safety. I'm going to speak in broad terms here--there's a lot of nuance and special cases that we can dig into, but I'd like to keep this accessible: You can use CRDTs, and other commutative data structures, to obtain totally-available replicated objects across wide area networks. Systems like Riak do this. CRDTs can't express some types of computation safely, though! For instance, you can't do something like a minimum-balance constraint, ensuring that an account always contains $25 or more, if you allow both deposits and withdrawals, in a commutative system. Why? Because order matters! Deposit, withdraw is different than withdraw, deposit, in terms of their intermediate states. For order, you can use a consensus mechanism, like ZAB (Zookeeper), Paxos (Riak SC, Cassandra LWT), or Raft (etcd, consul) to replicate arbitrary state machines without any clock dependence at all. These systems require at least one round trip to establish consensus, and their guarantees only apply within the consensus system itself. What if you have multiple consensus groups? Say, one per shard? Then you need a protocol to coordinate transactions on top of that. You can execute an atomic commit protocol for cross-shard transactions, perhaps using a consensus system. Or you can use a protocol like Calvin to obtain serializability (or stronger) across shards without relying on clocks. That's what FaunaDB does. That adds a round-trip, but if you're clever, you may only have to pay that round-trip cost between different datacenters once. Another tactic is to exploit well-synchronized clocks to obtain consistent views across independent consensus groups. You can use this technique to (theoretically) reduce the number of round trips a transaction costs, and there are different ways to balance whether you pay increased latency on read or write transactions. Spanner, CockroachDB, and YugaByte DB all take this approach, with different tradeoffs. Spanner is backed by custom hardware and carefully designed software, to obtain tight bounds on clock error. CockroachDB and YugaByte DB leave that problem to you, the operator. Often, a database uses a stronger replication mechanism inside a datacenter, but when it comes to replicating between datacenters, backs off to a weaker strategy which doesn't offer the same safety invariants.
- williamallthing 8y ago
  Thanks, this is a really helpful overview!
- ryanworl 8y ago
  While FoundationDB uses Paxos for cluster state (like leader election), it is not on the commit path for a transaction. If any process fails in the transaction system (not storage processes), the cluster is reconfigured by the coordinators and every component is replaced. Transactions do not proceed during failures, but the cluster will replace the failed process in a few seconds and resume. (This is not meant to be a contradiction, just pointing out an important difference compared to systems that allow progress in parallel with failures.)
  - aphyr 8y ago
    Ah, my mistake, thank you! It's been a long while since I talked to the FDB folks and I guess I misunderstood where they were using Paxos!

aphyr 8y ago

In short, no: many transactional databases don't rely on clocks for safety. I'm going to speak in broad terms here--there's a lot of nuance and special cases that we can dig into, but I'd like to keep this accessible: You can use CRDTs, and other commutative data structures, to obtain totally-available replicated objects across wide area networks. Systems like Riak do this. CRDTs can't express some types of computation safely, though! For instance, you can't do something like a minimum-balance constraint, ensuring that an account always contains $25 or more, if you allow both deposits and withdrawals, in a commutative system. Why? Because order matters! Deposit, withdraw is different than withdraw, deposit, in terms of their intermediate states. For order, you can use a consensus mechanism, like ZAB (Zookeeper), Paxos (Riak SC, Cassandra LWT), or Raft (etcd, consul) to replicate arbitrary state machines without any clock dependence at all. These systems require at least one round trip to establish consensus, and their guarantees only apply within the consensus system itself. What if you have multiple consensus groups? Say, one per shard? Then you need a protocol to coordinate transactions on top of that. You can execute an atomic commit protocol for cross-shard transactions, perhaps using a consensus system. Or you can use a protocol like Calvin to obtain serializability (or stronger) across shards without relying on clocks. That's what FaunaDB does. That adds a round-trip, but if you're clever, you may only have to pay that round-trip cost between different datacenters once. Another tactic is to exploit well-synchronized clocks to obtain consistent views across independent consensus groups. You can use this technique to (theoretically) reduce the number of round trips a transaction costs, and there are different ways to balance whether you pay increased latency on read or write transactions. Spanner, CockroachDB, and YugaByte DB all take this approach, with different tradeoffs. Spanner is backed by custom hardware and carefully designed software, to obtain tight bounds on clock error. CockroachDB and YugaByte DB leave that problem to you, the operator. Often, a database uses a stronger replication mechanism inside a datacenter, but when it comes to replicating between datacenters, backs off to a weaker strategy which doesn't offer the same safety invariants.

williamallthing 8y ago
Thanks, this is a really helpful overview!
ryanworl 8y ago
While FoundationDB uses Paxos for cluster state (like leader election), it is not on the commit path for a transaction. If any process fails in the transaction system (not storage processes), the cluster is reconfigured by the coordinators and every component is replaced. Transactions do not proceed during failures, but the cluster will replace the failed process in a few seconds and resume. (This is not meant to be a contradiction, just pointing out an important difference compared to systems that allow progress in parallel with failures.)
- aphyr 8y ago
  Ah, my mistake, thank you! It's been a long while since I talked to the FDB folks and I guess I misunderstood where they were using Paxos!