Design Distributed File Storage (like a shared drive)

Requirements

• Functional: upload, download, delete; folders; sync across a user's devices; share with others; version history.
• Non-functional: never lose data; efficient with bandwidth (resume uploads, send only changes); changes appear on other devices within seconds; files up to many GB.

Estimates

Assume 50 million users with 10 GB each on average: 500 PB before replication, so storage cost dominates and deduplication pays off. If each user changes a few files a day, metadata updates run in the thousands per second, while block uploads move far more bytes.

API

POST /files/commit { path: "/docs/plan.pdf", chunks: ["9f2c…", "a71b…", "9f2c…"], base_version: 6 }
  -> 409 { missing: ["a71b…"] }          upload only what is missing:
PUT  /blocks/a71b…  (bytes)
POST /files/commit … -> 200 { version: 7 }
GET  /changes?cursor=…  -> { entries: [...], cursor: "…", has_more: false }

Data model

High-level design

Deep dive: chunking and deduplication

Splitting a file into chunks (often a few MB) and naming each chunk by its SHA-256 hash gives several wins: uploads resume chunk by chunk; editing one part of a large file re-uploads one chunk; identical chunks (the same file in two folders, or shared by many users) are stored once.

import java.security.MessageDigest;
import java.util.*;

class Chunker {
    static String sha256(byte[] data) {
        try {
            return HexFormat.of().formatHex(MessageDigest.getInstance("SHA-256").digest(data));
        } catch (Exception e) {
            throw new IllegalStateException(e);
        }
    }

    static List<String> chunkHashes(byte[] file, int chunkSize) {
        List<String> hashes = new ArrayList<>();
        for (int i = 0; i < file.length; i += chunkSize) {
            hashes.add(sha256(Arrays.copyOfRange(file, i, Math.min(file.length, i + chunkSize))));
        }
        return hashes;
    }

    // Chunks the server does not have yet, each listed once, in file order.
    static List<String> missing(List<String> hashes, Set<String> serverHas) {
        Set<String> out = new LinkedHashSet<>();
        for (String h : hashes) {
            if (!serverHas.contains(h)) {
                out.add(h);
            }
        }
        return new ArrayList<>(out);
    }
}

import hashlib

def sha256(data):
    return hashlib.sha256(data).hexdigest()

def chunk_hashes(file_bytes, chunk_size):
    return [sha256(file_bytes[i:i + chunk_size]) for i in range(0, len(file_bytes), chunk_size)]

def missing(hashes, server_has):
    """Chunks the server does not have yet, each listed once, in file order."""
    return [h for h in dict.fromkeys(hashes) if h not in server_has]

Deep dive: sync and conflicts

Each user (or shared folder) has an ordered change journal. A device stores a cursor into it and asks for everything after the cursor; a notification over a long-lived connection simply says "there is something new". Every commit carries the base version it was edited from: if the server's latest version is newer, two devices edited concurrently, and the server keeps both, saving the second as a "conflicted copy" for the user to resolve.

Bottlenecks and trade-offs

• Metadata is the hard part: it must be strongly consistent and transactional; shard it by user or shared namespace.
• Garbage collection: a chunk can be deleted only when no file version references it; use reference counts or periodic mark-and-sweep, with a grace period.
• Cross-user deduplication saves space but can leak whether a file exists elsewhere; many services limit it to within an account.
• Large shared folders generate many notifications: batch and coalesce them.

The last five minutes

Common mistakes

• Re-uploading whole files for small edits.
• Storing file bytes in the metadata database.
• Last-write-wins on concurrent edits, silently losing work.
• Deleting chunks still referenced by older versions or other files.

Interview questions

Try answering out loud before you open each one.

Check yourself

Related topics

• Blob and Object StorageDatabases
• Clocks and OrderingDistributed Systems Essentials
• Transactions, ACID and Isolation LevelsDatabases
• Idempotent OperationsApplication Layer

Further reading

• Uploading and copying objects using multipart upload Amazon S3 documentation
• The rsync algorithm Tridgell and Mackerras
• HDFS architecture Apache Hadoop