Reduce Hashing and Safely Delete Shared File Content

A file store should retain only one copy of identical file contents while allowing several paths to refer to that content. An initial design computes a content hash for every write and lets a duplicate path refer to the path that first stored the bytes. Improve the design in two ways: reduce unnecessary content hashing and support deletion without breaking other files that share the same content. Explain the indexes and invariants your design needs. ### Constraints and Clarifying Questions - Assume an in-memory model with exact path keys, immutable file contents, writes to previously unused paths, reads, and deletion by path. - Each incoming file's size is available before computing its content hash. - Hashing a large file has a cost proportional to the amount of data read. A hash match alone must not be treated as proof of byte-for-byte equality. - Define the behavior of reading or deleting a missing path and state whether operations are single-threaded or require coordination. - Focus on retained storage and metadata. No physical operating-system symlink behavior is prescribed. ### Part 1 — Avoid Unnecessary Hashing Explain when a new write can be stored without computing a content hash. Describe how later writes can still find duplicate content, including content whose hash was initially deferred. #### What This Part Should Cover - A cheap condition that rules out duplicate content before a full hash is computed. - Index state for files that have not yet been hashed and how that state is completed when needed. - Exact equality checks for potential duplicates and the limits of the optimization when many files have the same size. ### Part 2 — Delete Paths Without Losing Shared Content Explain why referring to an original file path becomes problematic when that path is deleted. Propose a representation that separates logical file names from retained content, and define write, read, and delete behavior under that representation. #### What This Part Should Cover - A stable content identity independent of any particular path. - Reference counts that track live logical paths and deletion of content only after its last reference disappears. - Coordinated updates to path mappings, reference counts, and the content-discovery index. ```hint Delete the first name Create two paths with equal data, then delete the path that was created first. Identify what the remaining path must still be able to read and which metadata must remain valid. ``` ### What a Strong Answer Covers - One coherent design for lazy hashing, exact deduplication, and deletion. - State transitions that preserve shared data and prevent dangling index entries. - Concrete collision, empty-content, and last-reference cases, with realistic hashing and storage costs. ### Follow-up Questions - What should happen when a new file has the same size and mock hash as an existing file but different bytes? - If the first file of a size was stored without hashing, when must its hash be computed? - How would two concurrent writers avoid creating separate retained copies of the same content or corrupting reference counts?