Skip to the solution
HardSystem Design14 min read

How would you design Instagram?

513 views

The problem

Question presented to candidate: "Design Instagram. Users upload photos with captions, follow other users, see a feed of photos from people they follow, and like and comment. Assume a hundred million uploads a day and a few hundred million daily viewers."

What a strong answer should cover:

  • Capacity: uploads per second, storage per day and per year for several resized variants, and image views per second, which shows the system is a read-heavy media delivery problem
  • The upload path: client uploads directly to object storage with a presigned URL, an event triggers asynchronous processing (resize into variants, strip metadata, moderation), and the post becomes visible when processing finishes
  • Serving images through a CDN with immutable, content-addressed URLs, and keeping the origin out of the read path
  • Metadata (users, posts, follows, likes) in a sharded relational store with logical shards mapped onto fewer physical servers, and IDs that embed time and shard (Instagram published a 41-bit time, 13-bit shard, 10-bit sequence layout)
  • The feed built by fan-out as in the timeline design, like counters aggregated asynchronously, and what breaks at 10x (hot posts, celebrity accounts, storage cost)

Clarifying questions expected:

  • Photos only, or video and stories too? (Stories add expiry; video is the YouTube problem.)
  • Which features are in scope: feed, likes, comments, search, explore?
  • What is the read to write ratio and latency target for the feed?

Code / implementation expected: Optional — an ID generator that embeds time and logical shard, routing a post to its database from its id, and the effect of doubling the servers; the example does that and computes the capacity numbers.

  • media
  • feed

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

The solution is hidden so you can try first

14 min read · 15 sections

Read the code

Instagram-style 64-bit IDs (41-bit time, 13-bit logical shard, 10-bit sequence), routing by ID and doubling the database servers
Open in playground
// Instagram-style 64-bit IDs: 41 bits time | 13 bits logical shard | 10 bits sequence, plus shard routing.
const fmt = (n) => n.toLocaleString("en-US");
const EPOCH = 1577836800000n; // 2020-01-01T00:00:00Z, our custom epoch
const LOGICAL = 2000;

console.log("== 1. Capacity (assumptions: 100M uploads/day, 500M DAU viewing 100 images/day) ==");
const variants = [["1080px", 300], ["640px", 120], ["320px", 40], ["150px", 10]];
const perPhotoKB = variants.reduce((a, v) => a + v[1], 0);
console.log("variants " + variants.map((v) => v[0] + "=" + v[1] + "KB").join(" ") + " -> " + perPhotoKB + " KB per photo");
console.log("uploads avg " + fmt(Math.floor(100_000_000 / 86400)) + "/s; new storage " + fmt(100_000_000 * perPhotoKB / 1_000_000_000) + " TB/day, " + fmt(100_000_000 * perPhotoKB * 365 / 1_000_000_000) + " TB/year before replication");
console.log("image views avg " + fmt(Math.floor(500_000_000 * 100 / 86400)) + "/s -> served by the CDN, not the origin");

console.log("\n== 2. Bit budget ==");
const maxMs = (1n << 41n) - 1n;
console.log("41-bit ms field lasts " + (maxMs / (1000n * 86400n * 365n)) + " years from the epoch");
console.log("13-bit shard field: " + fmt(1 << 13) + " logical shards possible, " + fmt(LOGICAL) + " used");
console.log("10-bit sequence: " + (1 << 10) + " ids per shard per millisecond");

console.log("\n== 3. Generate ids inside the shard that owns the user ==");
const seq = new Map();
function nextId(userId, nowMs) {
  const shard = BigInt(userId % LOGICAL);
  const s = ((seq.get(shard) ?? -1n) + 1n) % 1024n; // per-shard counter, like a table sequence mod 1024
  seq.set(shard, s);
  return ((nowMs - EPOCH) << 23n) | (shard << 10n) | s;
}
const decode = (id) => ({ ms: (id >> 23n) + EPOCH, shard: Number((id >> 10n) & 8191n), seq: Number(id & 1023n) });
const t0 = 1760000000000n; // a fixed clock reading
const uploads = [[31341, t0], [31341, t0], [7, t0], [31341, t0 + 1n], [7, t0 + 5n]];
const ids = [];
for (const [user, t] of uploads) {
  const id = nextId(user, t); ids.push(id);
  const d = decode(id);
  console.log("user " + String(user).padEnd(6) + "t=" + t + " id=" + id + " -> shard " + d.shard + " seq " + d.seq + " ms " + d.ms);
}
const sorted = [...ids].sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
console.log("sorting ids gives time order: " + sorted.map((id) => decode(id).ms - t0).join(",") + " (ms after t0)");

console.log("\n== 4. Route by id, then double the database servers ==");
const server = (shard, n) => "db" + (shard % n);
for (const id of [ids[0], ids[2]]) console.log("id " + id + " -> logical " + decode(id).shard + " -> " + server(decode(id).shard, 4) + " of 4");
let moved = 0;
for (let s = 0; s < LOGICAL; s++) if (server(s, 4) !== server(s, 8)) moved++;
console.log("4 -> 8 servers: " + moved + " of " + LOGICAL + " logical shards move (copied whole); ids never change");
console.log("id " + ids[0] + " now -> " + server(decode(ids[0]).shard, 8) + " of 8");

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

Question 83 of 106 in System design

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All System design questions
Up nextHard

How would you design a system that scales to millions of users on AWS?

Continue