How does database sharding work?
planetscale.com
planetscale.com
This is the most important paragraph in the article. In a world where things like Dynamo/Cassandra or Spanner/Cockroach exist, manually-sharded DB solutions are pretty much entirely obsolete. Spanner exists because Google got so sick of people building and maintaining bespoke solutions for replication and resharding, which would inevitably have their own set of quirks, bugs, consistency gaps, scaling limits, and manual operations required to reshard or rebalance from time to time. When it's part of the database itself, all those problems just... disappear. It's like a single database that just happens to spread itself across multiple machines. It's an actual distributed cloud solution.
My current employer uses sharded and replicated Postgres via RDS. Even basic things like deploying schema changes to every shard are an unbelievable pain in the ass, and changing the number of shards on a major database is a high-touch, multi-day operation. After having worked with Spanner in the past, it's like going back to the stone age, like we're only a step above babysitting individual machines in a closet. Nobody should do this.
Far from it. Plenty of companies that are now running mysql or postgress will shard manually when they will need to scale.
It's a great option, as long as you're aware of the tradeoffs and don't expect it to act (and cost) exactly like a single Postgres server.
My order of ops generally goes:
- Can you get away with pure (or mostly) key/value for your hottest table(s) and mostly avoid queries? Use Dynamo or Google Cloud Datastore, but deeply understand their quirks (e.g. never index a timestamp field on Datastore or you're worse off than a weak-ass SQL server for write-heavy loads). These can scale basically forever with zero effort if you fit their constraints, and are cheap enough
- Can you tolerate the price of Spanner and deal with it not being normal SQL? Go for it, expect some non-trivial migration cost
- If you have to shard/cluster yourself, can you make Redis work? It'll be easier operationally than managing N SQL DBs of any kind. I know, if you could you'd probably have been fine using Dynamo...
- Can you soft-shard, e.g. use different machines for different tables and spread load enough to get each table onto a single server? Do it.
- Can you minimize re-sharding ops? (If you're in a massive growth phase, the answer is no) Ok, fine, do SQL sharding, and make sure you have well-tested code to do it and you mostly use key/value access patterns.
- Consider a beefy AF bare metal SQL server, see how far that gets you.
- If none of this applies, re-evaluate the cost ($ and time) of Spanner, you're paying a big price one way or another
- Only bad ideas from this point on, just do sharding but it'll suck...
Nowhere on my list: running your own cluster for Cassandra, Mongo, or anything similar, it's such an ops nightmare and there are hosted services that are better in every way but cost.
If you do end up writing your own sharding layer, best of luck, I have yet to see any reasonably production-ready ones that work well with pretty much any web framework or ORM. And writing these is so tough, so many edge cases to consider...not something I hope to ever do again.
Quite far, possibly to millions of users.
Case in point: StackOverflow runs on SQL Server.
Everything becomes fragile at the large end.
Yep, this is of course the default - although you'll at least want replication for availability and disaster recovery, but that's not too bad with PG/RDS.
> they don't just let you drop them in as a scalable replacement for an existing usage pattern, and usually sharding starts first coming up when you're at a huge scale and already have a ton of app code and database design but have grown past what a single db can support
I think once you get beyond what fits on one primary box, you're almost certainly at the point of rethinking your data access models anyway. Manual sharding is disruptive too.
What do you suggest one does if one has to run on Azure though?
PS Azure Cosmos is not a real product, it is a beta toy that Microsoft just has made expensive enough that people think it cannot possibly be as bad as it is..
what kind of problems you ran into with Cosmos?
Last I checked, that “compatibility” run at least a couple major version behind the real MongoDB.
To be fair, the same is probably also true with AWS’s DocumentDB
Most obvious indicator is DocumentDB is single node write whereas Mongo is really not, coming from Aurora Postgres.
Would be interested to hear your challenges.
1. yugabytedb (postgres compatible)
2. cockroachdb (postgres compatible)
3. tidb (mysql compatible)
You could self-host these on azure or subscribe to each of their managed service offering.
Of course, sticker price for managed will be more expensive than self-hosted enterprise product which itself will be more expensive than the self-hosted, community-supported, open-source option (which seems to be a real option with YugabyteDB).
They've just selected a few features from postgres which they're compatible in.
The PostgreSQL organisation should create some trademarked badges to properly label the levels of compatibility other products offer.
Not really. Cassandra is a write optimised, slow, network and IO heavy beast thats a pain in the arse to administer. We replaced a 6 node m4.4xlarge with a single db.m4.2xlarge. on postgres.
You need to pick your DB to match your data, not the otherway around.
Not true. Vitess is far more proven.
At my current job, we have reached a scale and use case that requires either manually sharding the database or using a distributed one. 20 TB including indexes, 10-20 tables with >1B rows, and spikes of up to 10K/s transactions. We put Vitess, TiDB, CockroachDB, and Spanner head-to-head, including running production scale load tests. Spanner won out because it is far superior to them all for scaling geo-replication and sysadmin. But TiDB was a close second because it just works, scales, and fast. Vitess on the other hand was extremely buggy and has a very long, undocumented list of unsupported SQL features. Yes Vitess has better press and more well known, but it is an inferior technology imo. TiDB is already what Vitess claims to be.
The largest Vitess cluster we know of runs on 10s of thousands of servers. So "False, just completely false" is dramatic.
Slack is powered by Vitess https://slack.engineering/scaling-datastores-at-slack-with-v... Twitter runs Vitess https://blog.twitter.com/engineering/en_us/topics/infrastruc...
I am sorry you had a buggy experience running Vitess yourself but you just wrong about the size of these production workloads.
They are pretty happy!
Different people find different things difficult. Don't feel bad.
Is it GitHub? Where can I find more details about them? It will be interesting to read more about it.
For most people(ie 95% of people) After putting a caching layer, paying for a bigger RDS(or equivalent) DB service is the cheapest and fastest option.
If the non-SQL distributed databases, I found FoundationDB to be by far the most robust and zero-overhead.
However, at least through version 6, it had absolutely terrible, service-destroying behavior if any of the nodes became low on storage, dropping transaction levels through the floor and since transactions are used for recovery and cluster expansion... Since it does a very nice job auto-sharding, if you're not paying attention this tends to happen to multiple nodes around the same time.
I wish it would get more attention though. It is a really amazing tool.
My intuition is that a properly sharded database will perform faster-or-same as a non-sharded one in all scenarios. Whereas automatically-sharded database will actually perform worst until you start reaching critical traffic that a single instance won't handle no matter what.
Am i wrong ?
There is no intrinsic performance penalty for automatic sharding, it can be as fast or faster than any other scheme. The "faster" cases are when the sharding structure must be adaptive to have uniform distribution of data and load, such as when the key distribution is intrinsically unpredictable or when you are doing multi-attribute sharding. In these cases, effective sharding can only be created by software at runtime.
This is workload dependent, if your queries only go to one shard, this is likely true. But if you have cross shard queries, then it’s no longer true.
No, because as soon as you have to JOIN across shards performance plummets. I mean, you can't JOIN across shards so you have to simulate that client-side which is very slow.
The secret to performant manual sharding is to figure out a way to minimize JOINs across shards, and that the ones you have to do are very small. Or to start replicating data which quickly becomes its own nightmare of consistency.
you can get expected "single shard" performance in CockroachDB by manually splitting the shards (called "ranges" in CockroachDB) along the lines of the expected single shard queries (what you call a "properly shared database"). This is easy to do with a single SQL command. (This is what we do today; we use CockroachDB for strongly consistent metadata).
The difference between CockroachDB and a manually sharded database is that when you _do_ have to perform some cross-shard transactions (which you inevitably have to do at some point), in CockroachDB you can execute them (with a reasonable performance penalty) with strong consistency and 2PC between the shards, whereas in your manually sharded database... good luck! Hope you implement 2PC correctly.
btw, [distributed] Postgres iirc was never as stellar the single node (the stuff we sing praises of) vs the distributed deployment. I'm sure it has improved significantly.
> "manual operations required to reshard or rebalance from time to time. When it's part of the database itself, all those problems just... disappear."
Not really correct.
* "Choosing the right keys can help Spanner evenly distribute data and processing to avoid hotspots"
https://cloud.google.com/spanner/docs/schema-design
https://cloud.google.com/blog/topics/developers-practitioner...
** https://static.googleusercontent.com/media/research.google.c...
[Spanner certainly did -not- start off as a distributed RDBMS. Because that project would have never been given a green light. Because it is understood just how complex that system would need to be. It started off as a distributed k/v. That's it.]
"[I]n many ways today’s Spanner is very different from what was described [in original Spanner whitepaper]"
...
"The initial focus of Spanner was on scalability and fault-tolerance, much as was the case for many systems at Google. In the last few years Spanner has increasingly become a fully-fledged database system. Production deployment with internal customers taught us a great deal about the requirements of web scale database applications, and shaped the techniques we presented in this paper. Aggressive focus on horizontal scalability enabled widespread deployment without investing too heavily in single machine performance. The latter is one of the areas where we are making continuous improvements, such as upgrading lower level storage to Ressi."
"The original API of Spanner provided NoSQL methods for point lookups and range scans of individual and interleaved tables. While NoSQL methods provided a simple path to launching Spanner, and continue to be useful in simple retrieval scenarios, SQL has provided significant additional value in expressing more complex data access patterns and pushing computation to the data."
That and lock in, open source ecosystem and so on.
It's not a black and white situation.
I am a full stack dev but I end up doing a lot of front end and rarely have to touch SQL. Posts like yours help me to realize there's still a lot I do not know while still being informative. So thanks <3
in some ways the stone age was terrible, and in some ways the stone age was far superior to the current age. we've gotten soft, lazy, stupid, comfortable. we used to be feral animals, but now we're more like house plants. if we got more used to doing things like dumb animals, life would be simpler, and we could appreciate what we have more. but it's hard to resist the temptation of feeling like what we have is never enough. the grass is always greener, and how terrible that it isn't ours.
Microsofts Azure Cloud Patterns is some of the best documentation out there. It's not Azure centric. It focuses on why you may want to do something and describes the techniques that are commonly used to solve it. It's pretty great.
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
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.
what??
if you shard users by user ID and orders by order ID, then a query that joins a bunch of user orders in the same tenant namespace will spread across multiple user shards and multiple order shards
value distribution doesn't really have any impact here
(shard keys are also guaranteed to exist by definition, not clear what you mean by that)
if you don't care that specific queries cross sharding boundaries, okay, then no problem, but in that case sharding is not solving the problem that we are talking about here
> Sharding and multi-tenancy are orthogonal concepts.
sharding and multi-tenancy are only orthogonal if you don't care that a single tenant can have information on multiple shards
> what??
> if you shard users by user ID and orders by order ID, then a query that joins a bunch of user orders in the same tenant namespace will spread across multiple user shards and multiple order shards
Note my recommendation of picking a "stable, guaranteed-to-exist, shard key."
If there is a users table/collection sharded by its id and an orders table/collection sharded by its id, then there is no "guaranteed-to-exist shard key" between them, right? So, in that case, where the two are often accessed together, having a "guaranteed-to-exist shard key" of the "tenant namespace" would be the logical choice.
> value distribution doesn't really have any impact here
I mentioned value distribution strictly in the context of ordering composite shard keys (if applicable). My apologies for any confusion this might have introduced.
> (shard keys are also guaranteed to exist by definition, not clear what you mean by that)
My implication was in reference to what is always available across accessing sharded entities. In the scenario you describe, sharding by either user or order id would not be ideal. In situations where one or the other is not sharded, then identifying a common shard key likely is not needed.
>> Sharding and multi-tenancy are orthogonal concepts.
> sharding and multi-tenancy are only orthogonal if you don't care that a single tenant can have information on multiple shards
My assertion was regarding theory, not specific scenarios. In practice, having multiple tables/collections needing shards with the tenant being the common entity strongly implies sharding on a tenant property and not of those unique to each table/collection, as implied in your reply.
This is a pretty risky approach since it's almost certainly the case that you won't end up evenly distributing your data across shards using this method.
but shard "even-ness" is in direct tension with the concern of the GP, which is execution atomicity
frequently, it's better to have uneven shards (that you can e.g. scale independently when necessary) that give you atomic execution, than even shards that require distributed transactions
For example, consider a system which monitors farm equipment for Caterpillar and John Deere. Lets say each company has 100k devices which send one message per day to the system.
While it is easy to envision sharding device messages based on "DeviceId / Company" in this hypothetical system, there would be no value sharding the two customers.
Distributing data across shards is a function of the properties selected to use for partitioning. So I do not understand how "a stable, guaranteed-to-exist, shard key (composite or atomic properties)" is "a pretty risky approach."
About hot spots, it has always been an issue with K-V stores, and the only real solution is a good key design, though there are some tricks:
* Use a uniformly distributed but deterministic key prefix. For example, instead of using raw user_id as key, attach a small hash before it: (hash(<user_id>), <user_id>) This can help with load distribution if your <user_id> is not uniformly distributed by itself such as a phone or id number.
* Add more data to your key to increase cardinality. For example, with time series data, instead of using object_id as partition key, use (user_id, time_bucket) so the data for a busy object will get split into different partition over time.
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...
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?
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
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.
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
Recently they've been acquired by Microsoft & have started to been integrated into their CosmosDB offering. Anybody have good experience with this DBaaS offering?
Sharding at table level is very complex and expensive. Fully give a single DB per tenant is very practical, and the reasons to do sharding (like reporting) is where you do the other fancy things (like ship events in to kafka, etc, etc).
Also, most issues of scalability are dominated by a few tenants that consume most resources, and distribute the loads is more easy per-tenant.
How do you manage that ?
Availability is kinda good: You could lose one/few tenants but that not take down all the rest (if they are isolated properly).
Is MUCH worse if all the db made the fancy way get down, or worse, you get a cascade of latency and/or crashed by the interlinked nature of the "scalable architecture that is fact share-everything global singleton".
And you can get a bit fancy (not done it myself, my customers tolerate a bit of downtime) of fork the tenant and upload it another node.
Isnt this some wrong simplification? Product number can stay the same, but be a different thing over time. Product 12345 can be a book on first January 2023, while a comic book on first March 2023 . The idea is that product versions can change over time. (What is mostly abused by scammers who farm fake reviews and bait and switch products).
So probably they have some product history table, or save the product information in the order.
Also sharding in big data environment is when your data does not fit into Excel anymore, so you have 20 Acess files (1GB database limit in Access).
Definitely not normal. It’s hard to know why you’re seeing slow queries without more information.
The most common causes are either: missing indexes or network latency between the app and database (are they in the same region?).
We don’t have cold starts, but it is possible for queries to get faster once data is moved into memory. 3-4s is very slow though, I suspect it’s doing a full table scan and an index will solve it.
If you check Insights you can get more info, would also help to run an explain on the query (https://planetscale.com/courses/mysql-for-developers/queries...) to see what’s happening.
Also, if you email support, they’ll help debug it for you. Hope that helps!
Also, I’m not saying “list all”. I’m saying even list 10 or list 1000 is the same problem - you still have to contact all servers in your cluster to do a map/reduce to get the result. Sure, list operations may be less common but their cost seems exponentially more expensive.