Sweaty Imposter

File Storage and Sharing

Design the metadata schema for a cloud drive: users organize files in nested folders, files keep version history, and any file or folder can be shared with users or groups as viewer or editor, with folder shares applying to everything inside.

Clarifying Questions

  • Can a file live in more than one folder, or is the hierarchy a strict tree?
  • How deep can folders nest, and how many items can one folder hold?
  • Do folder shares apply automatically to items added later?
  • Is a trash with restore required, and for how long?
  • Are file bytes in object storage, with only metadata in this database?

Core Requirements

  • Store folders and files in a tree where each item has one parent.
  • List a folder's children sorted by name or modified time.
  • Keep every version of a file with its content hash and size.
  • Share an item with a user or group as viewer or editor; folder shares apply to descendants.
  • Check whether a user can open an item in a single query.
  • Move items between folders, and move items to trash with restore.

Canonical schema (PostgreSQL)

CREATE TABLE nodes (
  id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  owner_id UUID NOT NULL,
  parent_id UUID REFERENCES nodes(id),
  kind TEXT NOT NULL CHECK (kind IN ('folder', 'file')),
  name TEXT NOT NULL,
  current_version_id BIGINT,
  size_bytes BIGINT NOT NULL DEFAULT 0,
  trashed_at TIMESTAMPTZ,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  updated_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- Closure table: one row per ancestor-descendant pair, including each node with itself at depth 0.
CREATE TABLE node_paths (
  ancestor_id UUID NOT NULL REFERENCES nodes(id) ON DELETE CASCADE,
  descendant_id UUID NOT NULL REFERENCES nodes(id) ON DELETE CASCADE,
  depth INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE TABLE file_versions (
  id BIGSERIAL PRIMARY KEY,
  node_id UUID NOT NULL REFERENCES nodes(id) ON DELETE CASCADE,
  version_no INTEGER NOT NULL,
  content_hash CHAR(64) NOT NULL,
  storage_key TEXT NOT NULL,
  size_bytes BIGINT NOT NULL,
  created_by UUID NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  UNIQUE (node_id, version_no)
);

CREATE TABLE groups (
  id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  name TEXT NOT NULL
);

CREATE TABLE group_members (
  group_id UUID NOT NULL REFERENCES groups(id) ON DELETE CASCADE,
  user_id UUID NOT NULL,
  PRIMARY KEY (group_id, user_id)
);

CREATE TABLE shares (
  id BIGSERIAL PRIMARY KEY,
  node_id UUID NOT NULL REFERENCES nodes(id) ON DELETE CASCADE,
  grantee_kind TEXT NOT NULL CHECK (grantee_kind IN ('user', 'group')),
  grantee_id UUID NOT NULL,
  role TEXT NOT NULL CHECK (role IN ('viewer', 'editor')),
  created_by UUID NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  UNIQUE (node_id, grantee_kind, grantee_id)
);

Key Indexes

CREATE UNIQUE INDEX uq_nodes_parent_name ON nodes(parent_id, lower(name)) WHERE trashed_at IS NULL

No two live siblings share a name, and trashed items don't block reusing it.

CREATE INDEX idx_nodes_parent_updated ON nodes(parent_id, updated_at DESC) WHERE trashed_at IS NULL

Folder listing sorted by modified time, the default view in most drives.

CREATE INDEX idx_paths_descendant ON node_paths(descendant_id, depth)

Finds every ancestor of an item, which is the first step of each access check.

CREATE INDEX idx_shares_grantee ON shares(grantee_kind, grantee_id)

Serves the 'Shared with me' view and the grantee side of the access check.

CREATE INDEX idx_nodes_owner_trashed ON nodes(owner_id, trashed_at) WHERE trashed_at IS NOT NULL

The trash view and its restore window touch only trashed rows.

Key Decisions to Defend

  • A closure table (node_paths) stores every ancestor-descendant pair, so 'all ancestors of this file' and 'everything under this folder' are single indexed queries with no recursion.
  • The access check joins the item's ancestors to shares for the user and the user's groups, so one query covers direct and inherited grants.
  • Shares attach to the node where they were granted and apply to descendants at read time; copying grants onto every descendant would turn a share on a 100k-item folder into a 100k-row write.
  • Moving a subtree rewrites its node_paths rows, at a cost of subtree size times depth; moves are rare next to reads, which makes this the right side of the trade.
  • File versions are immutable rows with a content hash, nodes.current_version_id points at the live one, and identical content dedupes in object storage.

Likely follow-ups

  • · A user moves a folder with 500k descendants, how do you keep the move from locking the tree?
  • · Add restricted subfolders that block inherited access.
  • · Show storage used per user, including all versions, without summing on every request.
  • · Allow a file to appear in two folders, what breaks in the closure table?

Dive Deeper

Cloud drive metadata tests hierarchy modeling and permission inheritance together. The core choice is how to represent the tree: adjacency lists make ancestor queries recursive, materialized paths make moves rewrite strings, and closure tables trade storage and move cost for simple, fast reads. Senior candidates tie the choice to the hottest query, the access check on every open, and resolve inherited grants at read time so a share on a large folder stays a single row.

All Database Design Prompts