5 ms·

Thanks for this article planetscale. I've been enamoured with sharding recently but more for multithreaded performance. I want multimaster postgres. I started

Thanks for this article planetscale. I've been enamoured with sharding recently but more for multithreaded performance. I want multimaster postgres. I started trying to write a postgres synchronizer, by sorting every data by row and column and hashing the data of every column and row, then doing a rolling hash of the data. In theory, two databases can synchronize by sending the final hash of their data and then doing a binary search backwards until the hashes match. This way you can work out which parts of the databases differ and need to be transmitted. If the databases are identical, very little data gets transferred. One problem I've not worked out is how to decide which database is the winning database without having to change application queries. If you synchronize two multimaster Postgres databases that have had independent writes to different sections, how do you identify which database is the source of truth for a column/row combination?

preseinger 4y ago
"a binary search backwards" is not well defined and doesn't guarantee any upper bound on consistency sharding data based on individual rows within tables is tricky, you won't get reliable guarantees for queries in this way "which database is the winning database" is a function of individual rows, a query that reads data from N different row-owners needs to query N different instances, or else accept that it will work against stale data
AdieuToLogic 4y ago
> One problem I've not worked out is how to decide which database is the winning database without having to change application queries. I believe this is a case of the "Two Generals' Problem"[0], which implies that there is no provably correct solution to achieve this. > If you synchronize two multimaster Postgres databases that have had independent writes to different sections, how do you identify which database is the source of truth for a column/row combination? You can't without a quorum[1] and even that does not guarantee success. 0 - https://en.wikipedia.org/wiki/Two_Generals%27_Problem https://en.wikipedia.org/wiki/Two_Generals%27_Problem 1 - https://en.wikipedia.org/wiki/Split-brain_(computing) https://en.wikipedia.org/wiki/Split-brain_(computing)
- setr 4y ago
  > You can't without a quorum[1] and even that does not guarantee success. Isn’t split-brain largely resolved by the rules: 1. Must have a strict majority of the total group agree to commit 2. Total should be an odd number
  - anamexis 4y ago
    Only if there can only be one simultaneous split.
    - deleted 4y ago
      [deleted]
    - bpicolo 4y ago
      If all nodes lose traffic to each other (which is plausible with bad config changes), good luck!
myzie 4y ago
Spock may be of interest to you: https://pgedge.github.io/spock/ https://pgedge.github.io/spock/
brightball 4y ago
You need Citus
- yuji 4y ago
  Citus follows a single-master architecture for replication just like standard postgres. Citus would be a good solution to add additional writable nodes via sharding tables accross multiple databases. Recently they've been acquired by Microsoft & have started to been integrated into their CosmosDB offering. Anybody have good experience with this DBaaS offering?
  - brightball 4y ago
    It does, but if you’re sharding do you still need multi master?

preseinger 4y ago

"a binary search backwards" is not well defined and doesn't guarantee any upper bound on consistency sharding data based on individual rows within tables is tricky, you won't get reliable guarantees for queries in this way "which database is the winning database" is a function of individual rows, a query that reads data from N different row-owners needs to query N different instances, or else accept that it will work against stale data

AdieuToLogic 4y ago

> One problem I've not worked out is how to decide which database is the winning database without having to change application queries. I believe this is a case of the "Two Generals' Problem"[0], which implies that there is no provably correct solution to achieve this. > If you synchronize two multimaster Postgres databases that have had independent writes to different sections, how do you identify which database is the source of truth for a column/row combination? You can't without a quorum[1] and even that does not guarantee success. 0 - https://en.wikipedia.org/wiki/Two_Generals%27_Problem https://en.wikipedia.org/wiki/Two_Generals%27_Problem 1 - https://en.wikipedia.org/wiki/Split-brain_(computing) https://en.wikipedia.org/wiki/Split-brain_(computing)

setr 4y ago
> You can't without a quorum[1] and even that does not guarantee success. Isn’t split-brain largely resolved by the rules: 1. Must have a strict majority of the total group agree to commit 2. Total should be an odd number
- anamexis 4y ago
  Only if there can only be one simultaneous split.
  - deleted 4y ago
    [deleted]
  - bpicolo 4y ago
    If all nodes lose traffic to each other (which is plausible with bad config changes), good luck!

myzie 4y ago

Spock may be of interest to you: https://pgedge.github.io/spock/ https://pgedge.github.io/spock/

brightball 4y ago

You need Citus

yuji 4y ago
Citus follows a single-master architecture for replication just like standard postgres. Citus would be a good solution to add additional writable nodes via sharding tables accross multiple databases. Recently they've been acquired by Microsoft & have started to been integrated into their CosmosDB offering. Anybody have good experience with this DBaaS offering?
- brightball 4y ago
  It does, but if you’re sharding do you still need multi master?