How Instagram Split One Database Into Thousands
Shard keys, logical shards, and the 64-bit photo ID that says when a photo was made and which shard holds it.
Two different photos. Two different databases. Both stamped with the same ID: 3. That's what happens when you split one database into many pieces and every piece counts on its own.
Instagram had to split its data early, so it had to solve exactly this. Its answer was hidden inside the number itself. This article walks through the whole design: why one server stops being enough, how to choose where each row lives, the difference between a logical shard and a physical server, and the 64-bit ID that ties it all together.
If you'd rather watch, here's the animated version. This is a historical case study, based on Instagram Engineering's posts from 2011 and 2012. Example IDs, dates, shard numbers, servers and the user grouping are illustrative, and the shard-moving steps are a conceptual explanation, not Instagram's exact runbook.
Each database starts its own counter at 1. Give both of them a new photo at the same moment and both hand out 3. A comment, a like or a cache entry that points at "photo 3" can now land on the wrong photo.
Why one server stops being enough
Instagram passed 14 million users in a little over a year. Much of the information behind the app (users, photo details, tags) lived in PostgreSQL. Back then, Instagram described more than 25 photos and 90 likes arriving every second.
A database server has physical limits. Storage fills up. Memory runs out. And there are only so many writes one machine can handle.
You can buy a bigger machine. You can add read replicas, which take reads off the main server. But replicas copy every write; they don't make the main server's writes disappear. Eventually, if that main server is the bottleneck, you have to spread the data and the writes across machines. One way to do that is sharding: each machine holds only part of the data.
Split, but by what?
Sharding starts with one decision: what decides where a row belongs? That's the shard key. It's the choice that's hardest to undo later, so it's worth getting right.
Two tempting keys go wrong.
Split by upload time. This month's photos on one shard, last month's on another. It sounds tidy. But every new photo, from everyone, lands on the newest shard. One machine takes all the writes while the rest sit idle. That's a hot shard.
Split each photo at random. Now the writes spread out nicely. But one person's photos are scattered everywhere, so loading a profile means asking many databases and waiting for the slowest one.
An illustrative design for a social app avoids both: group data around a user. Imagine Ananya uploads a photo. If the data needed for her profile sits on one shard, the app can fetch it without asking every database. And because many users are spread across many shards, the writes spread out too.
But now her data sits on one shard among thousands. When Ananya opens the app, how does it know which one to ask?
Logical shards and physical servers
Here's the key distinction. A logical shard is a named bucket of data. A physical server is the machine holding those buckets. You can have thousands of logical shards without buying thousands of servers, because each server holds many buckets.
The app uses routing information to connect a user to a logical shard, then that shard to a server. It doesn't search every machine; it goes straight to the right one.
In the design Instagram described, logical shards were PostgreSQL schemas: separate namespaces, each with its own tables, many of them living on one database server. Keeping the buckets small turns out to matter later, when a machine needs help.
What does an ID need?
Routing solves where data goes. It doesn't solve what to call it. Instagram needed three things from a photo ID:
- Unique across every shard. A photo's ID travels everywhere: into links, caches, likes and comments. If two photos share one, a comment can land on the wrong photo.
- Made without asking one central counter. If every upload waits on one machine for its number, that machine becomes the bottleneck, and if it goes down, nobody can post.
- Roughly ordered by time. Newer photos get bigger numbers, so a list of photo IDs can be sorted newest first without fetching anything else.
Why not the obvious answers? Random UUIDs avoid a central counter. But the common random kind doesn't sort by creation time. Some newer UUID versions do put time first, at the cost of a longer ID than a 64-bit number.
A central ID service gives orderly numbers, and plenty of companies run one successfully. But every new photo now depends on it, so it has to be built to scale and to stay available.
Instagram chose a different trade-off: let each shard generate its own IDs locally, and make sure IDs from different shards can never collide.
The 64-bit trick
Instead of a plain counter, Instagram packed three pieces of information into one 64-bit number:
- 41 bits of time: milliseconds since a chosen starting point (an epoch). 2โดยน milliseconds is about 69.7 years.
- 13 bits of logical shard: room for 8,192 shard values.
- 10 bits of sequence: a counter for IDs made inside that shard in that millisecond.
id = (ms_since_epoch << 23) | (shard_id << 10) | (sequence % 1024)
Ten bits give 1,024 sequence values per shard per millisecond. That's room in the number, not a speed the system promises. Inside a shard, the sequence hands out a different value to each new ID, so within the same millisecond no two IDs from that shard get the same one. And two different shards can use the same time and the same sequence without clashing, because their shard bits are different.
The number isn't just a name. It carries a clue about where the data belongs.
Pause and decode
Here's an example 64-bit ID built exactly that way: 176482890547422211. Ananya sends it to you. Just the number. No username, no database address. Can you work out when it was generated, and which logical shard it belongs to? Try before you read on.
The reveal, with one catch: yes, to both. Shift the number right by 23 bits and you get the top 41 bits: 21,038,400,000 milliseconds. Add that to the example start date of 1 January 2011 and you get 1 September 2011, 12:00 UTC, the moment the ID was generated. Take the middle 13 bits and you get the logical shard: 217. The last 10 bits are the sequence: 3.
ms = id >> 23 # 21,038,400,000
shard = (id >> 10) & 8191 # 217
seq = id & 1023 # 3
Here's the catch: a logical shard isn't a server address. To find the machine, the app looks up which server currently holds shard 217. The ID answers when and which logical shard. The routing map answers which machine.
In Instagram's reported implementation, PostgreSQL generated these IDs itself, inside each shard, without asking one global counter. (The epoch and the ID above are our examples; Instagram used its own custom epoch.)
Moving shards without changing IDs
Remember the thousands of small logical shards? Imagine one physical server starts running out of room. Instead of changing anyone's IDs, you move some logical shards to another server.
Conceptually, it takes three steps:
- Copy the shard's data to the new server.
- Coordinate the writes that keep arriving, so nothing is lost or written twice while you switch.
- Switch the routing map to the new server.
Copying a database and changing a pointer isn't enough on its own. The writes in between are the hard part. Through all of it, the logical shard identity stays the same. Ananya's photo ID doesn't change; only the server that holds its shard does.
Small movable buckets give you far more flexibility than one enormous chunk.
What sharding costs
Sharding solves one problem by introducing others. Want the most-liked photos across the whole app? The query may now need to reach many shards and combine the results. Want to update data that spans two users? That can involve more than one shard, which makes consistency and transactions harder. And the routing map has to stay correct as shards move.
Sharding isn't a magic performance switch. It's an architectural trade-off, and the shard key you choose early shapes everything that follows.
One number, one architecture
Back to the two photos stamped 3. With Instagram's design, they're made in the same millisecond with the same sequence number, on two different shards, and they still get two different IDs, because the shard bits in the middle are different.
So here's the whole idea:
- Split the data into logical shards.
- Route each request to the right shard and the server that holds it.
- Name every photo with an ID made of time, shard and sequence.
- Move shards carefully when a server fills up, without changing their identities.
Scaling isn't just about adding machines. It's about making sure every piece of data can still be named, and found, after you split the system apart.
Sources
Instagram Engineering, Sharding & IDs at Instagram (archived copy)
Instagram Engineering, What Powers Instagram: Hundreds of Instances, Dozens of Technologies
Mike Krieger on Hacker News
The example ID, epoch, shard numbers, servers and user grouping are illustrative. The shard-moving steps are a conceptual explanation. 2โดยน ms โ 69.7 years is our arithmetic; the original post rounds differently.
โถ๏ธ Watch the animated version: How Instagram Split One Database Into Thousands (YouTube): [
]Follow The Byte Mechanics - How software works, under the hood โ๏ธ
๐ Website โถ๏ธ YouTube ๐ธ Instagram ๐งต Threads ๐ Facebook ๐ X โ๏ธ Medium ๐ป DEV Community ๐ Hashnode
Comments
No comments yet. Start the discussion.