In-Memory Cloud Storage System Design
Context
Design an in-memory storage library that maps fully qualified POSIX-style file paths (e.g., "/a/b/c.txt") to file metadata. This system does not interact with a real filesystem; all data structures must reside in memory. Assume that requests will not create naming collisions between files and directories (e.g., "/a" will not be simultaneously a file and a directory).
Requirements
Implement the following feature levels. Each subsequent level must preserve and build upon the behaviors of earlier levels.
Level 1 — Basic File Operations
bool AddFile(const std::string& name, int size)- Adds a new file at the specified
namepath with a givensizein bytes. - Returns
falseif a file with the same path already exists;trueotherwise.
- Adds a new file at the specified
bool CopyFile(const std::string& name_from, const std::string& name_to)- Copies the file located at
name_fromtoname_to. - Fails if
name_fromdoes not exist or is not a file, or ifname_toalready exists. - Returns
trueon success,falseotherwise.
- Copies the file located at
std::optional<int> GetFileSize(const std::string& name)- Returns the file size if the file exists; otherwise, returns
std::nullopt.
- Returns the file size if the file exists; otherwise, returns
Level 2 — File Discovery
- Support finding files efficiently by:
- Matching path prefixes (similar to directory-like queries).
- Matching suffixes (e.g., file extensions or arbitrary suffixes).
- Define appropriate APIs and choose data structures to ensure these queries are efficient.
- Describe the expected time and space complexity for these operations.
Level 3 — Users and Capacity Limits
- Introduce a user concept with per-user storage capacity limits (in bytes).
- Associate files with specific users and enforce these capacity limits during
AddFileandCopyFileoperations. - Specify the error handling mechanisms and what each API returns when a user's capacity limit would be exceeded.
Level 4 — Compression Support
- Implement support for compressing and decompressing files.
- Define APIs to compress or decompress a file and update its stored size accordingly.
- Clarify whether
GetFileSizeshould return the logical (uncompressed) size or the physical (stored, potentially compressed) size, and how capacity accounting should work in the presence of compression.
General Constraints and Deliverables
- The entire system must remain in-memory; do not use the operating system's filesystem.
- Provide clear class and method interfaces, along with the core data structures (e.g., maps, tries, indexes) you would use. Justify your trade-offs.
- Concurrency handling is optional, but you should describe how you would make operations thread-safe.
- Include a brief test strategy with example scenarios that demonstrate the expected behavior of your system.
AI interview prep
Core dilemma
Balancing efficient hierarchical path operations (like a filesystem) with efficient arbitrary string searches (prefix/suffix) and managing complex metadata (users, compression), all within strict in-memory constraints and evolving requirements. The core conflict lies in optimizing for diverse access patterns while managing memory footprint and ensuring data consistency.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
In-Memory Cloud Storage System Design
Context
Design an in-memory storage library that maps fully qualified POSIX-style file paths (e.g., "/a/b/c.txt") to file metadata. This system does not interact with a real filesystem; all data structures must reside in memory. Assume that requests will not create naming collisions between files and directories (e.g., "/a" will not be simultaneously a file and a directory).
Requirements
Implement the following feature levels. Each subsequent level must preserve and build upon the behaviors of earlier levels.
Level 1 — Basic File Operations
bool AddFile(const std::string& name, int size)- Adds a new file at the specified
namepath with a givensizein bytes. - Returns
falseif a file with the same path already exists;trueotherwise.
- Adds a new file at the specified
bool CopyFile(const std::string& name_from, const std::string& name_to)- Copies the file located at
name_fromtoname_to. - Fails if
name_fromdoes not exist or is not a file, or ifname_toalready exists. - Returns
trueon success,falseotherwise.
- Copies the file located at
std::optional<int> GetFileSize(const std::string& name)- Returns the file size if the file exists; otherwise, returns
std::nullopt.
- Returns the file size if the file exists; otherwise, returns
Level 2 — File Discovery
- Support finding files efficiently by:
- Matching path prefixes (similar to directory-like queries).
- Matching suffixes (e.g., file extensions or arbitrary suffixes).
- Define appropriate APIs and choose data structures to ensure these queries are efficient.
- Describe the expected time and space complexity for these operations.
Level 3 — Users and Capacity Limits
- Introduce a user concept with per-user storage capacity limits (in bytes).
- Associate files with specific users and enforce these capacity limits during
AddFileandCopyFileoperations. - Specify the error handling mechanisms and what each API returns when a user's capacity limit would be exceeded.
Level 4 — Compression Support
- Implement support for compressing and decompressing files.
- Define APIs to compress or decompress a file and update its stored size accordingly.
- Clarify whether
GetFileSizeshould return the logical (uncompressed) size or the physical (stored, potentially compressed) size, and how capacity accounting should work in the presence of compression.
General Constraints and Deliverables
- The entire system must remain in-memory; do not use the operating system's filesystem.
- Provide clear class and method interfaces, along with the core data structures (e.g., maps, tries, indexes) you would use. Justify your trade-offs.
- Concurrency handling is optional, but you should describe how you would make operations thread-safe.
- Include a brief test strategy with example scenarios that demonstrate the expected behavior of your system.