Order by across multiple database in sharding

0
votes

Assume that we're developing an Instagram with billions of users. We shard photo tables in multiple databases(in different sharding instances/servers/devices), and in photo tables we have a createdAt column. Now a user opens the home tab in the app, the app should show the most recent 20 photos(order by createdAt desc) globally(not locally) across the photo tables in multiple databases. How the SQL query should be?

We must shard the photo table because billions of users would make hundred billions of photos. We can't store and serve hundred billions of photos in one table in one database in one server.

Say we have 100 database servers, one possible solution is that querying select id from photo order by createdAt desc limit 20 over the photo tables over 100 database servers. Then in our backend, we get 20*100 = 2000 photo rows, and sort them by createdAt in backend(Node.js, Java, Python, etc) and return only first 20 rows.

3
mysqldatabasepostgresqldatabase-design
Maybe you shouldn't be preemptively splitting. Why do you think multiple database on the same server is better? How are you sharding the photo tables? because if its by user its only a single database query, and a very basic one. Have you picked MySQL/Postgres yet? - danblack
@danblack I didn't mean that multiple database are on the same server. MySQL/Postgres or other RDMS are good. Please see my edit. Thanks! - user2790103

3 Answers

1
votes

It sounds like what you are looking for is the Spider storage engine from MariaDB. That will let you have each partition on a different server. You should be aware that architectures like this are never entirely transparent - to get the best (or even good) performance out of it you will have to engineer your entire application around the performance side-effects of the underlying data storage.

1
votes

It is premature to talk about sharding. Don't think about it until you have millions of entries in your dataset.

By then, you will have redesigned the schema at least once. Only after, say, the second or third redesign, should you worry about sharding. Such as...

When you get there, here are some tips:

  • One table (or a small group of closely related tables) will be split across multiple machines ("sharding").
  • Other tables will need to be either duplicated across the shards, or kept on separate machine(s). Maintaining these tables becomes a separate admin task.
  • It will be sharded by some "id". Your choice of id may have to change then; but don't dwell on it yet. UUIDs have performance problems, but let multiple clients independently construct unique ids. There are better ways; call back later.
  • You will need multiple layers of machines -- for databases, web servers, routers, etc.
  • A query that needs to look at all shards will be complex to write and slow to run. So try to avoid such.
  • Sharding can be done by hashing or dictionary or a hybrid of both.
  • Write a tool to migrate a user from one shard to another. That tool is the key to simplifying a number of tasks -- hardware upgrades, software upgrades, crash repair, load balancing, etc, etc.
  • Put photos on separate servers; keep only URLs in the database. This simplifies things, makes more effective use of hardware, etc.
  • 100B photos at 1MB each -- that will take many standard machines or a few huge SANs. Keeping this independent of the database lets you scale it separately.
  • "20 most recent photos across all shards" -- Suggest you use a non-sharded server with an API whose main purpose is to receive URLs and maintain that list; plus deliver the list. It may be all that one server can handle. And reaching into all shards all the time would probably bring the whole system to its knees.
  • You will need hundreds of servers for what you describe; what is your budget? And what is your HA requirement? Hundreds of machines == one crashing every few days. And you will need to add another server every few days just for capacity growth. How many SAs / DBAs IT specialists will you be hiring?

Flickr was built years ago on sharded MySQL servers. So, it is possible. They had one "group" whose sole goal was was to upload one million pictures. that "whale" gave them some challenges.

0
votes

If splitting database server by users is the logical map for this table, the apply the mapping in the application (preferably a mapping that doesn't need a database lookup), and then just directly that database server with SELECT .. FROM photos ORDER BY createdAt DESC