How does database sharding work?
planetscale.com
How does database sharding work?
1–10 of 113 posts
Re: How does database sharding work?
#2The first link in the article [1], to a blogpost about the etymology of the definition of "shard" that we now think of as the primary meaning of the word, is super interesting.
The release of Ultima Online doesn't really seem too close to any inflection point of the word on Google Ngram, but I'm not sure exactly how close we should expect it to be to 1980 or 2000.
1. https://www.raphkoster.com/2009/01/08/database-sharding-came...
Re: How does database sharding work?
#3One thing I notice is the over-usage of sharding, especially hash-based, might turn your Relational Database into just another key-value store, with consistency constraints moving into application code, and you lose many advantages of a traditional RDBMS
Re: How does database sharding work?
#4Thanks 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?
Re: How does database sharding work?
#5Thanks 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" 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
Re: How does database sharding work?
#6One thing I notice is the over-usage of sharding, especially hash-based, might turn your Relational Database into just another key-value store, with consistency constraints moving into application code, and you lose many advantages of a traditional RDBMS
What's the alternative as things get too big? Sharding by date? By client? How do you prevent hotspots?
Re: How does database sharding work?
#7One thing I notice is the over-usage of sharding, especially hash-based, might turn your Relational Database into just another key-value store, with consistency constraints moving into application code, and you lose many advantages of a traditional RDBMS
What's the alternative as things get too big? Sharding by date? By client? How do you prevent hotspots?
the only real answer here is to shard by customer
optimistically, you can try to shard by read use case, but that's never gonna be stable over time
if you need a true multi-tenant system you can only shard by individual entity and move all of the composition logic to the next layer up, there's no way to cheat
Re: How does database sharding work?
#8Thanks 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…
> 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.
Re: How does database sharding work?
#9Thanks 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…
Spock may be of interest to you: https://pgedge.github.io/spock/
Re: How does database sharding work?
#10Earlier quoted context omitted.
What's the alternative as things get too big? Sharding by date? By client? How do you prevent hotspots?
the only real answer here is to shard by customer optimistically, you can try to shard by read use case, but that's never gonna be stable over time if you need a true multi-tenant system you can only shard by individual entity and move all of the composition logic to the next layer up, there's no way to cheat
> the only real answer here is to shard by customer
No.
Pick a a stable, guaranteed-to-exist, shard key (composite or atomic properties) and use that. If composite, order properties used in most-to-least distinct value distribution.
> if you need a true multi-tenant system you can only shard by individual entity and move all of the composition logic to the next layer up, there's no way to cheat
This is incorrect. Sharding and multi-tenancy are orthogonal concepts.