Katkat
Back

Design an in-memory cloud storage system

MetaSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentSystem Design

Last updated

This question tests your ability to design a high-performance, in-memory distributed metadata store that supports hierarchical file structures, quota management, and efficient retrieval of top-k largest files.

Problem Statement

Design an in-memory cloud storage metadata service. The system should manage a hierarchical file system (folders and files) and support the following operations with low latency:

  1. create(path, size): Create a file at a specific path with a given size. Assume all parent directories exist.
  2. delete(path): Remove a file or folder. If it is a folder, recursively delete all contents.
  3. get_top_k(path, k): Return the k largest files (by size) within a directory and its subdirectories.
  4. update_quota(path, limit): Set a maximum storage limit for a directory. Return false if the current usage exceeds the limit or if the update violates parent constraints.

Assumptions

  • The system must fit in memory.
  • The system should handle 10^6 files/folders total.
  • get_top_k must be highly optimized, potentially sacrificing some write latency.
  • The system operates on a single machine for this exercise, but discuss how you would scale it to multiple nodes.

Example

  • create("/home/user/data.txt", 100)
  • create("/home/user/logs/app.log", 200)
  • get_top_k("/home/user", 1) -> ["/home/user/logs/app.log"]

Constraints

  • Paths are strings. Use a tree structure to represent the hierarchy.
  • Files have a 'size' attribute.
  • Quotas are inherited (a child's total usage cannot exceed a parent's limit).

Hints

Hint 1

Use a Trie or a N-ary tree to represent the file hierarchy, where each node stores metadata and current aggregate size.

Hint 2

For top-k queries, maintain a min-heap or a balanced binary search tree at each directory node representing the files in its subtree.

Hint 3

Use a recursive update mechanism to propagate file size changes up to the root to enforce quota limits in O(depth) time.

Follow-up questions

  • How would you handle concurrent updates to the same directory or quota limits using locking mechanisms?
  • If the metadata grows too large for one machine, how would you partition the tree across multiple servers?
  • Explain how you would implement a snapshot feature to revert the file system state to a previous point in time.