Skip to the solution
HardSystem Design18 min read

How would you design Google Drive?

0 views

The problem

Question presented to candidate: "Design Google Drive. Users upload files of any size from web, desktop and mobile, organise them in folders, share files and folders with people and groups at different permission levels, see changes from other people quickly, and search across everything they can access. Focus on the metadata, sharing and sync parts; assume a blob store exists."

What a strong answer should cover:

  • Metadata as a graph of items with stable IDs and a parent pointer (Drive moved to one parent per item in 2020, with shortcuts for extra locations), separate from the blob store holding file content
  • Sharing: permissions granted on a file or folder and inherited by everything below; effective access = strongest grant on the item or any ancestor; a folder move changes access for a whole subtree with one parent-pointer write
  • A dedicated authorization service (Google's Zanzibar paper describes relation tuples such as "doc#viewer@user" in the system Google built for authorization across many of its products), with caching and consistency tokens so a revoke is not ignored
  • A per-user change feed with page tokens (Drive's API exposes changes.getStartPageToken and changes.list), including "removed" entries when access is lost, plus push notifications
  • Resumable uploads with a session URI and byte offsets (the server reports what it has with 308 and a Range header; chunks in multiples of 256 KiB per Google's upload docs), and quotas such as 5 TB per file and 750 GB per user per day
  • Search over names, content and permissions; native Docs editing as a separate collaborative system; capacity math and what breaks at 10x

Clarifying questions expected:

  • Which clients, and is offline desktop sync in scope or only web and mobile?
  • Sharing model: users, groups, domains, link sharing?
  • Scale: users, items per user, read/write ratio for metadata?

Code / implementation expected: Optional โ€” the data model and the permission and change-feed logic matter most; the example simulates inherited sharing, a revoking move, a change feed and a resumable upload.

  • system-design
  • case-study

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

18 min read ยท 17 sections

Read the code

Drive metadata: inherited sharing, a folder move that revokes access, per-user change feed, resumable upload session
// Drive-style metadata: a folder tree of IDs, inherited sharing, a move that changes access, a change feed,
// and a resumable upload session.
const ROLES = ["none", "reader", "commenter", "writer", "owner"];
const items = new Map();                       // id -> {name, parent, acl: {user: role}}
const changes = [];                            // {seq, id, user, kind}
const add = (id, name, parent, acl = {}) => items.set(id, { name, parent, acl });

add("root", "My Drive", null, { alice: "owner" });
add("team", "Team", "root", { bob: "writer" });
add("q3", "Q3", "team");
add("plan", "plan.doc", "q3");
add("budget", "budget.xlsx", "q3", { carol: "reader" });
add("priv", "Private", "root");

// Effective role = the strongest grant on the item or any ancestor. Returns [role, where it came from].
function access(user, id) {
  let best = "none", from = "-";
  for (let cur = id; cur; cur = items.get(cur).parent) {
    const r = items.get(cur).acl[user];
    if (r && ROLES.indexOf(r) > ROLES.indexOf(best)) { best = r; from = items.get(cur).name; }
  }
  return [best, from];
}
const show = (user, id) => { const [r, f] = access(user, id); return `${user} on ${items.get(id).name}: ${r}${r === "none" ? "" : " (via " + f + ")"}`; };
const subtree = (id) => [id, ...[...items.keys()].filter((k) => items.get(k).parent === id).flatMap(subtree)];

console.log("== 1. Inherited permissions ==");
for (const [u, id] of [["bob", "plan"], ["carol", "budget"], ["carol", "plan"], ["alice", "budget"]]) console.log(show(u, id));

console.log("== 2. Move Q3 from Team to Private (one parent pointer changes) ==");
const users = ["alice", "bob", "carol"];
const before = new Map(subtree("q3").map((id) => [id, users.map((u) => access(u, id)[0])]));
items.get("q3").parent = "priv";
let feedRows = 0;
for (const id of subtree("q3")) users.forEach((u, i) => {
  const was = before.get(id)[i], now = access(u, id)[0];
  if (was !== "none" || now !== "none") { changes.push({ seq: changes.length + 1, id, user: u, kind: now === "none" ? "removed" : "changed" }); feedRows++; }
});
console.log(`metadata rows written: 1, items whose access was recomputed: ${subtree("q3").length}, change-feed rows: ${feedRows}`);
for (const [u, id] of [["bob", "plan"], ["carol", "budget"]]) console.log(show(u, id));

console.log("== 3. Bob syncs with his page token ==");
const feed = (user, token) => { const rows = changes.filter((c) => c.seq > token && c.user === user); return { rows, next: changes.length }; };
const f = feed("bob", 0);
for (const c of f.rows) console.log(`seq ${c.seq}: ${items.get(c.id).name} ${c.kind}`);
console.log(`bob next page token: ${f.next}; alice sees ${feed("alice", 0).rows.length} changes`);

console.log("== 4. Same move on a big folder: inherited vs copied-down ACLs ==");
for (const n of [10, 5000, 200000]) console.log(`${String(n).padStart(6)} files: inherited ACL writes 1 row; ACLs copied to every item write ${n + 1}; feed rows for 2 affected users ${2 * (n + 1)}`);

console.log("== 5. Resumable upload: 1,000,000 bytes in 262,144-byte chunks ==");
const TOTAL = 1000000, CHUNK = 262144;
let persisted = 0;                             // server-side offset for this session URI
function putChunk(start, bytesArrived, finalChunk) {
  if (start !== persisted) return `409 expected offset ${persisted}`;
  const keep = finalChunk && bytesArrived === TOTAL - start ? bytesArrived : Math.floor(bytesArrived / CHUNK) * CHUNK;
  persisted += keep;
  return persisted === TOTAL ? "200 OK file created" : `308 Range: bytes=0-${persisted - 1}`;
}
let off = 0, sent = 0, attempt = 0;
while (off < TOTAL) {
  const len = Math.min(CHUNK, TOTAL - off);
  const arrived = attempt === 2 ? 100000 : len;   // the third request is cut off after 100,000 bytes
  attempt++;
  sent += arrived;
  const res = putChunk(off, arrived, off + len === TOTAL);
  console.log(`PUT bytes ${off}-${off + len - 1}/${TOTAL}${arrived < len ? ` (dropped after ${arrived})` : ""} -> ${res}`);
  if (arrived < len) console.log(`status query PUT bytes */${TOTAL} -> 308 Range: bytes=0-${persisted - 1}`);
  off = persisted;
}
console.log(`bytes sent ${sent}, wasted ${sent - TOTAL}`);

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 104 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.

Up nextHard

How would you design a payment system?

Continue