4 ms·

I've come to the realization that sharding might be the only way to actually scale multi-master systems without allowing stale (or potentially outright wrong) r

I've come to the realization that sharding might be the only way to actually scale multi-master systems without allowing stale (or potentially outright wrong) reads. Sharding is complex and makes parallel queries a requirement but it really does seem like the only way to distribute a database. In the end, once you have the op log on more than one machine, they're going to have to synchronize with each other, otherwise you risk giving out not just stale answers, but completely wrong answers. This is fine for a site like FB but is not OK if it's attached to military equipment. CRDTs don't help in the case that you don't want to deliver wrong answers, they only help making sure merges (during synch time) are resolvable without conflicts. Lamport clocks only give you a partial order, and you need something else (physical clocks) for total order, which is what you get from raft (because you only let one node manage the log in the first place). What I haven't seen yet/want to try is to see if sharded + replicated raft could introduce some interesting performance benefits. It's basically max complexity (the complexity plus sharding, plus multiple instances of raft at the same time), but it could be only way to distribute write load (smart routing/forwarding of requests) and increase availability (eventually consistent replication for every node of every shard) at the same time. This is basically what Faunda does but I'm not 100% sure about splitting a single table across replicas...

sporkland 8y ago
Sounds like foundationdb to some extent. All data is sharded (and replicated) i.e. chunks of the keyspace up to the small blocksize limit are spread across the cluster. With this you can scale read throughput with the size of the cluster through parrallel reads. Though their write performance is bounded by the more limited number of transactors, but they still acheive fairly large write scale.
rystsov 8y ago
CRDT may help: if you read from quorum, merge(+modify) and write back to quorum for read (write) then you'll always get right answers.
- hardwaresofton 8y ago
  I'm not sure if I'm understanding what you're suggesting right, but it sounds like you're just quorum-ing for everything. You shouldn't need improved merging if you quorum both reads and writes, since it implies the majority agreeing on the contents of the log to begin with.
  - evanweaver 8y ago
    Quorum/quorum does not guarantee agreement or serializability even for a single key. Imagine a write that commits to one replica but is delayed committing to two others. Some quorum reads will see it (but also see a tie with the old value...what breaks the tie? Certainly not a timestamp) and others will not see it at all, indefinitely. It’s easy to end up in a state where every replica has a different value because of torn writes.
    - hardwaresofton 8y ago
      Sorry, I think either my fundamental understanding is off or I wasn't clear enough in how I was imagining this happening... If you and a majority of nodes agree on a value like an CRDT OpSet (more simplistically, just agreeing on the state of the log), how does that not guarantee agreement and serializability? It is impossible from that point on to have a another majority of nodes have some other view of what happened. Consensus algorithms are One copy serializability is exactly what would be achieved by having a read and write quorum[0][1]. It intuitively makes sense to me (and maybe my intuition is wrong), but if you talk to a majority of nodes and ask "this is what we all have, right?" before every write and every read, you've got a guaranteed consistent (of course, progress isn't guaranteed if partitions/nodes die, etc) state. AFAIK Quorums are the state of the art (and arguably the only relatively efficient option) as far as achieving serializability in a distributed system... [0]: https://en.wikipedia.org/wiki/Quorum_(distributed_computing)#Quorum-based_voting_for_replica_control https://en.wikipedia.org/wiki/Quorum_(distributed_computing)... [1]: https://arxiv.org/pdf/1406.7423.pdf https://arxiv.org/pdf/1406.7423.pdf
      - 8y ago

sporkland 8y ago

Sounds like foundationdb to some extent. All data is sharded (and replicated) i.e. chunks of the keyspace up to the small blocksize limit are spread across the cluster. With this you can scale read throughput with the size of the cluster through parrallel reads. Though their write performance is bounded by the more limited number of transactors, but they still acheive fairly large write scale.

rystsov 8y ago

CRDT may help: if you read from quorum, merge(+modify) and write back to quorum for read (write) then you'll always get right answers.

hardwaresofton 8y ago
I'm not sure if I'm understanding what you're suggesting right, but it sounds like you're just quorum-ing for everything. You shouldn't need improved merging if you quorum both reads and writes, since it implies the majority agreeing on the contents of the log to begin with.
- evanweaver 8y ago
  Quorum/quorum does not guarantee agreement or serializability even for a single key. Imagine a write that commits to one replica but is delayed committing to two others. Some quorum reads will see it (but also see a tie with the old value...what breaks the tie? Certainly not a timestamp) and others will not see it at all, indefinitely. It’s easy to end up in a state where every replica has a different value because of torn writes.
  - hardwaresofton 8y ago
    Sorry, I think either my fundamental understanding is off or I wasn't clear enough in how I was imagining this happening... If you and a majority of nodes agree on a value like an CRDT OpSet (more simplistically, just agreeing on the state of the log), how does that not guarantee agreement and serializability? It is impossible from that point on to have a another majority of nodes have some other view of what happened. Consensus algorithms are One copy serializability is exactly what would be achieved by having a read and write quorum[0][1]. It intuitively makes sense to me (and maybe my intuition is wrong), but if you talk to a majority of nodes and ask "this is what we all have, right?" before every write and every read, you've got a guaranteed consistent (of course, progress isn't guaranteed if partitions/nodes die, etc) state. AFAIK Quorums are the state of the art (and arguably the only relatively efficient option) as far as achieving serializability in a distributed system... [0]: https://en.wikipedia.org/wiki/Quorum_(distributed_computing)#Quorum-based_voting_for_replica_control https://en.wikipedia.org/wiki/Quorum_(distributed_computing)... [1]: https://arxiv.org/pdf/1406.7423.pdf https://arxiv.org/pdf/1406.7423.pdf
    - 8y ago