File Backup System

Design a source→destination file backup that mirrors directory structure, supports full + incremental runs, resumes after crashes, and verifies integrity — anchored on a durable manifest as source of truth and stage-then-commit (.tmp+rename / multipart-complete) for atomic writes. Phase 1: Requirements Functional Requirements Back up a source tree to a destination. Given a source path (a directory subtree or volume) and a destination path (another filesystem, S3 bucket, remote NAS, etc.), copy every file across. Mirror the directory structure. A user listing the destination should see the same paths, names, and hierarchy as the source. Permissions and timestamps preserved where possible. Support full and incremental backups. A first run does a full copy; subsequent runs only copy what changed since the last successful backup. Resume after failure. If a backup is interrupted (process crash, network drop, source unavailable), the next run picks up where the last one left off rather than restarting from scratch. Verify integrity. After a backup completes, the system can confirm that the destination contents match the source (typically via checksums recorded in a manifest). Out of Scope (Mention and Defer) Restore (the inverse pipeline), encryption at rest, multi-tenant access control, deletion semantics on the destination ("if a source file is gone, do we delete from destination?" is a policy question — most backup systems keep historical files and rely on retention windows), versioning of backed-up files, point-in-time restore. The interviewer cares less about your full feature list than about whether you scope cleanly. Calling these out as "out of scope for the phone screen, happy to discuss" is a strong signal — it shows you saw them coming. Non-Functional Requirements Scale: 100M to 10B files; tens of terabytes to petabytes total. Individual files range from KB-sized configs to GB-sized media. Reliability: a backup eventually succeeds. Transient errors (network blips, throttling) must not abort the whole job. Resumability: progress survives worker crashes. A 10-hour backup that fails at hour 9 must not start over from hour 0. Throughput: complete the backup within a defined window (e.g., nightly). For Netflix-scale, this drives parallelism hard. Consistency: each backup represents a coherent point-in-time snapshot of the source, not a smear of moments while files were changing underfoot. Correctness: never produce a file at the destination that is partially written or silently truncated. Assume These Primitives Exist The interviewer explicitly hands you the filesystem layer. Treat it as given: listDir(path) -> [DirEntry] # one level, names + types stat(path) -> { size, mtime, mode, isDir, isSymlink } readFile(path, off, n) -> bytes writeFile(path, bytes, mode) mkdir(path, mode) rename(src, dst) # atomic on a single filesystem Your job is to build the backup logic on top of these — not to design POSIX. Capacity Sanity Check Metric Assumption Files 1B Avg file size 200 KB (heavy long tail toward GB-scale media) Total bytes 1B × 200 KB ≈ 200 TB Daily change rate ~5% of files: 50M files/day, ~10 TB delta Backup window 8 hours (overnight) Required throughput 10 TB / 8 h ≈ 350 MB/sec sustained Two takeaways from the math: (1) you must parallelize — a single worker hitting a few hundred MB/s won't finish in time once you account for many small files dominating overhead, and (2) full re-reads are expensive enough that incremental is mandatory after the first run. Phase 2: Data Model The interesting state is not the files themselves (the filesystem owns those) — it's the manifest that records what we backed up, when, and what its checksum was. The manifest is the source of truth for "did this file make it across, and is the destination still correct?" BackupJob( job_id UUID PK, source_root TEXT, dest_root TEXT, type ENUM('full','incremental'), parent_job_id UUID, -- previous successful job, for incrementals status ENUM('running','succeeded','failed','partial'), started_at TIMESTAMP, finished_at TIMESTAMP, snapshot_id TEXT -- e.g. ZFS/LVM snapshot taken at start ) ManifestEntry( job_id UUID, rel_path TEXT, -- path relative to source_root size_bytes BIGINT, mtime TIMESTAMP, mode INT, is_dir BOOLEAN, is_symlink BOOLEAN, symlink_target TEXT, content_hash CHAR(64), -- SHA-256 of file bytes (null for dirs) copy_status ENUM('pending','copied','verified','skipped','failed'), copied_at TIMESTAMP, PRIMARY KEY (job_id, rel_path) ) Checkpoint( job_id UUID, shard_id INT, -- if work is partitioned across walkers/workers last_committed_path TEXT, updated_at TIMESTAMP, PRIMARY KEY (job_id, shard_id) ) Why store a manifest at all, separate from the destination? Because the destination alone cannot answer the questions you actually need answered: which job last copied a file, what the source's bytes hashed to at copy time, whether this run's (size, mtime) matched the prior run's. A ls of a filesystem or an ls of an S3 prefix gives you what's there, not whether it's current, complete, and matches the source. The manifest holds that durable truth, plus the checksums needed to verify integrity later. Mention the manifest before drawing any architecture. It is the single concept that ties together incremental detection, resumability, and verification — three load-bearing properties collapse onto it. Interviewers reward seeing that connection early. Relationships One BackupJob has many ManifestEntry rows (one per path). A new incremental job starts from its parent_job_id's manifest as the baseline. Checkpoint rows are advisory progress state for resumption; the manifest itself is authoritative. Phase 3: API Design This is an internal tool, so the API is service-to-service or CLI-driven, not user-facing. POST /backup/jobs Body: { "source_root": "/data/prod", "dest_root": "s3://backups/prod", "type": "incremental" } Response: { "job_id": "..." } GET /backup/jobs/{job_id} Response: { "status": "running", "files_total": 1000000, "files_done": 612340, "bytes_done": ..., "errors": 3 } POST /backup/jobs/{job_id}/resume # idempotent — picks up from checkpoint GET /backup/jobs/{job_id}/manifest # paginated; for verification or restore POST /backup/verify # sample-check or full-check a completed job Body: { "job_id": "...", "mode": "sample"|"full" } The CLI surface (backup start, backup resume, backup status) is what an SRE or scheduled cron actually calls. An HTTP layer in front is useful for centralized scheduling and dashboards but not architecturally important — flag it and move on. Phase 4: High-Level Design Architecture Components Coordinator. Receives job requests, takes (or requests) a snapshot of the source, creates the BackupJob row, and dispatches walkers. Tracks overall job state. Walker. Enumerates the source tree using listDir recursively. Each walker owns a subtree (e.g., a top-level directory) so multiple walkers run in parallel without overlap. For each entry, it emits a manifest record: (rel_path, size, mtime, mode, is_dir, is_symlink). Diff stage. Compares the new walk against the parent job's manifest to decide what work each entry implies: (path, size, mtime) matches parent → mark skipped, no copy needed. New path or changed (size, mtime) → enqueue a copy job. Directory → ensure mkdir happens at destination (cheap, idempotent). Symlink → record target; reproduce link at destination. Work queue. Persistent queue (e.g., SQS/Kafka, or a DB-backed work table). Each item is one file to copy. Persistent matters because workers crash and we need at-least-once redelivery. Copy workers. The hot path: Pull a job from the queue. Open the source file (against the snapshot, not the live tree). Stream bytes to a destination staging path: dest_root/{rel_path}.tmp.{job_id}. While streaming, compute SHA-256 incrementally. Once the full file is durably written and fsync'd, atomically rename from .tmp to the final path. Update the manifest entry: copy_status = copied, store content_hash. Acknowledge the queue. Verifier. After all copies finish, samples a subset (or, for paranoid mode, all) of files: re-reads the destination, recomputes the hash, compares to the manifest. Updates entries to verified. Discrepancies trigger re-copy. Data Flow: One Incremental Backup How the Destination Ends Up Structurally Identical This is the explicit interviewer probe: "how do you ensure the destination has the same structure?" Three rules: Mirror paths, do not transform. A source file at /data/prod/users/alice/profile.json lands at dest_root/users/alice/profile.json. No content-addressed renaming, no flattening. The destination is browsable as if it were the source. Create directories before files. The walker emits mkdir operations for each unique parent prefix. Workers ensure parent dirs exist before writing (idempotent mkdir -p semantics). Atomic writes only. Never let a partially-written file appear at its final path. The exact mechanism depends on the destination type: Filesystem destination: write to path.tmp.{job_id}, fsync, then rename to the final path (atomic on a single filesystem). Object store destination (S3, GCS): use the multipart upload API. Parts are uploaded out-of-band; the final object key only appears at the moment "complete multipart upload" returns. That completion is the atomic commit. Both achieve the same guarantee: the final path either does not exist, or exists with fully-written, durable bytes — never anything in between. The "construct out-of-band, atomically commit" pattern is the structural guarantee, regardless of destination type. An external observer of the destination at any moment sees only files that were fully copied — never half-copied ones. Combined with the manifest's copy_status, you can always answer "is this destination consistent with that source snapshot?" deterministically. Phase 5: Scaling & Trade-offs Bottlenecks and Fixes Layer Bottleneck Fix Walker Single-threaded directory traversal on a large tree Partition by top-level directory; one walker per partition. For ultra-deep trees, walkers can recurse and re-shard children into sub-walkers Manifest DB Hot writes during diff insertion (millions of rows) Bulk insert in batches (1k-10k rows per transaction); shard by hash(rel_path) if a single DB cannot keep up Work queue Throughput limit Use a partitioned queue (Kafka topic with N partitions); workers consume in parallel Copy workers Network I/O ceiling per worker Horizontally scale workers; the bottleneck moves to source-read or destination-write bandwidth Many small files Per-file overhead (open, stat, network round trip per file) dominates Bundle a directory of small files into a single tarball for transport only, then unpack at the destination so the on-disk structure still mirrors the source. Pure-archive destinations (a .tar file at rest) break the mirror promise — avoid them unless the interviewer explicitly relaxes that requirement One huge file Single worker becomes a long pole Chunk the file into ranges (e.g., 64 MB), parallelize chunk uploads, reassemble at destination (or use object-store multipart upload) Source storage Read amplification during walk + copy Take a snapshot once, read everything from the snapshot (cheaper, consistent) Snapshot Consistency: Why It Matters The source filesystem is live. Files get created, deleted, and modified during the backup. Without a snapshot: A file that exists when the walker sees it may be deleted before the worker copies it. A file may be partially modified mid-copy, producing a logically inconsistent backup (half the change, half the old version). The fix is to do the entire backup against a filesystem snapshot taken at job start. ZFS, LVM, EBS snapshots, and most NAS appliances support this. The snapshot is cheap (copy-on-write) and gives you a frozen, consistent view for the duration of the job. Without snapshots, your backup is "best effort point-in-time" at best, and "scrambled" at worst. If the source filesystem does not support snapshots, the next-best fallback is application-level coordination (e.g., quiesce writes, then walk). Do not pretend you can ignore this. Failure Handling This is the area the interviewer pushed on hardest. Be specific. Worker crashes mid-copy. The staged write (a .tmp file on a filesystem, or an in-progress multipart upload on an object store) is orphaned, but the final path is untouched. The work item is not acknowledged, so the queue redelivers it. Another worker re-runs the copy from scratch — this is safe because the staging name is per-job and the commit is the only mutating step. Periodically clean up orphans: sweep .tmp.{job_id} files at job end on filesystems; abort dangling multipart uploads on S3 (these accrue cost until aborted, so a lifecycle rule that auto-aborts after N days is mandatory in production). Network errors / transient destination failures. Retry the chunk or the file with exponential backoff. After N retries, mark the manifest entry failed and continue with the rest of the job. The job ends in partial state with a list of failures the operator can address. Source file disappears between walk and copy. Worker's readFile errors out. If using a snapshot, this should not happen. Without a snapshot, mark skipped with reason source_missing and move on. Destination disk full. Workers begin failing writes. The coordinator detects elevated error rates, pauses the queue, and pages an operator. This is not a problem to silently retry around. Whole job interrupted (deploy, host failure, OOM). On restart, the coordinator looks up the job's last Checkpoint per shard and re-enqueues only entries with copy_status IN ('pending','failed'). Already-copied entries are skipped, since the manifest is the source of truth. This is what makes the 8-hour-into-9-hour-job recovery cheap. Bad bytes (silent corruption). This is what verification catches. If a sampled re-read disagrees with the manifest's recorded hash, mark the entry failed, re-copy. If it disagrees again, alert — likely a destination storage problem. Frame failure handling around three guarantees: (1) never produce a wrong file (atomic commit — rename or multipart-complete), (2) never lose progress (durable manifest + checkpoints), (3) never silently corrupt (hashes recorded and verified). Almost every failure mode reduces to one of those three. Reducing Bandwidth: Optional Deduplication For an internal Netflix-scale backup, content-addressed dedup (Dropbox-style, sharing block hashes across files and across jobs) cuts storage cost significantly when the source has lots of duplicate content (build artifacts, repeated configs, ML model checkpoints). Trade-off: it breaks the "destination is structurally identical to source" property — you lose the ability to ls the backup and see the source tree. Common compromise: keep the destination as a literal mirror, but compute and dedupe at the source during incremental detection. If two source files share a hash within a single job, copy once and hardlink the second on the destination filesystem. This keeps mirror semantics and saves I/O. (Hardlinks require a POSIX destination — for an object-store destination, the equivalent is "write the object once, store both keys pointing at the same object," which most object stores do not support natively, so the optimization usually applies only to filesystem backups.) Push this only if the interviewer asks about storage cost or has time for a deeper dive. For a phone screen, "we could add dedup later" is enough. Trade-offs Decision Option A Option B Chosen Destination layout Mirror source paths Content-addressed flat store Mirror — required by "same structure" Consistency Snapshot at start Live read Snapshot — required for coherent point-in-time Incremental detection (size, mtime, path) heuristic Full content hash every time Heuristic, with hash recorded once on copy. Hash-every-time is too expensive for large unchanged files Queue durability In-memory Durable (Kafka/SQS/DB-backed) Durable — required for resumability Verification Sample a small subset Full re-read Sample by default, full mode available — full re-read at PB scale is its own backup Many small files Copy individually Bundle into archives Individual by default; transport-bundle (tar over the wire, unpack at destination) as an optimization for known small-file directories — bundling at-rest would break the mirror promise Open Probes for Senior+ Discussion Backup retention and pruning. Multiple historical backups accumulate. Garbage collection: keep N most recent fulls, M most recent incrementals; older jobs and their manifest entries can be pruned along with the destination files they uniquely reference (here a refcount across manifests would help, similar to Dropbox's block GC). Cross-region durability. A single-region backup is one disaster away from total loss. Replicate the destination cross-region asynchronously (S3 cross-region replication, or storage-layer replication for filesystem destinations). The backup job itself doesn't change — replication is a destination concern. Restore. Inverse pipeline: read manifest, walk the destination, copy back to a target. The same primitives (queue, workers, atomic writes, verification) apply. A good design is symmetric: the same code paths handle backup and restore, parameterized by direction. Throttling and bandwidth caps. A backup that saturates production network bandwidth is its own outage. Workers honor per-job and per-host bandwidth budgets; back off under detected congestion on the source side. Common Pitfalls Mistaking the prompt for OOD. Spending the first ten minutes on class File and class Directory UML wastes the screen. As soon as the interviewer says "assume the primitives," pivot to a system-design walkthrough. Skipping the snapshot. Walking a live source produces inconsistent backups. If snapshots are unavailable, you must explicitly handle it (quiesce writes, accept inconsistency) — do not assume the source is frozen because the diagram is. Writing directly to the final path. A worker crash during write leaves a half-file at the real path, indistinguishable from a real backed-up file. Always construct out-of-band first — .tmp + rename on a filesystem, multipart upload + complete on an object store — and only commit to the final path once the full bytes are durable. Treating the destination as the source of truth. The destination — whether filesystem or object store — cannot answer "is this file fully and correctly copied?" without the manifest's recorded hash. Skipping the manifest forces you to re-read every byte to verify, which is exactly what you cannot afford at scale. Ignoring small-file overhead. If your source has 100M files averaging 4 KB, per-file overhead (open, network round trip, manifest write) dwarfs the actual byte transfer. Batch them or prepare for a multi-day "fast" backup. Promising "exactly once" copying. Workers retry on transient failure; the same file may be copied more than once. Atomic commit plus content hashing makes that idempotent and correct, not "exactly once" in the strict distributed-systems sense. Be precise about what you guarantee. Interview Checklist Requirements Stated the five core capabilities: source→destination copy, mirror structure, full + incremental, resume after failure, integrity verification Called out point-in-time consistency as an NFR — and how snapshots provide it Did the back-of-envelope to motivate parallelism and incremental copy Data Model Manifest as the source of truth, not the destination BackupJob, ManifestEntry, Checkpoint with the right keys Explained why content_hash is recorded on copy (so verification doesn't require re-reading source) API Job lifecycle endpoints: start, status, resume, manifest, verify Acknowledged this is internal tooling, not user-facing High-Level Design Coordinator → walkers → diff → queue → workers → destination Stage-then-commit for atomic writes (.tmp + rename on FS, multipart upload + complete on object store) — explicitly named as the structural guarantee Walked the failure modes through to show how the design recovers Scaling & Trade-offs Per-layer bottleneck table Snapshot vs. live source explained Worker-crash, network-failure, partial-write recovery walked through concretely Verification strategy (sample vs. full) discussed Summary Concern Decision Source consistency Filesystem snapshot at job start Destination layout Literal mirror of source paths Atomicity Stage out-of-band, then commit atomically: .tmp.{job_id} + rename on a filesystem, multipart upload + complete on an object store Source of truth Durable manifest with (rel_path, size, mtime, hash, copy_status) Incremental detection Compare (size, mtime, path) against parent manifest; copy only deltas Parallelism Per-subtree walkers, partitioned durable queue, horizontally scaled workers Resume Manifest + per-shard checkpoints; restart re-enqueues pending/failed only Verification Re-read sampled files, recompute hash, compare to manifest Failure handling Atomic commit + idempotent retries + bounded backoff + alert on persistent failure The defining ideas: the manifest, not the destination, is the source of truth, and stage-then-commit is what makes the destination structurally identical to the source under any failure mode. Everything else — parallelism, incrementalism, verification, resume — composes on top.