System requirements

Functional:

• User can create, read, update, and delete a file.
• The system is optimized for large files - MBs to GBs.
• The system is optimized for OLAP (analytics) use case, i.e., writes are mostly appending, and reads are sequential. Random access reads and writes are uncommon.

Non-Functional:

• Scalability
• Reliability
• Read and write throughput
• Consistency

[It is important to specify what kind of file system we're trying to build. And get the interviewer's buy-in. Here we are building FS for huge data mainly for analytics, similar to Google File System. If the interviewer is looking for something else, like a system similar to Dropbox or Box, that's fine. We just need to specify that.]

Capacity estimation

• Each file is 100MB on average
• We have 1 billion files on the entire file system
• Total storage is 100MB * 1 billion = 100PB
• 10 million DAU
• Each user accesses the filesystem 5 times on average.
• 50 * 1000 * 1000 / (60 * 60 * 24) = 580 requests / s
• Read/Write ratio is 1 to 1

API design

• create_file(user_id, path, content) # returns file ID
• append_file(user_id, file_id, content) # append content to the end of the file
• delete_file(user_id, file_id)
• read_file(user_id, file_id, start_offset, length)

Database design

Since this system is a file system, it would provide abstractions for higher level systems such as databases.

As such, files should be store on each server's disk.

Assuming each server can store 10TB of data on disk

100PB / 10TB = we'd need 10,000 servers

High-level design

There are two main microservices:

File System Service, which is highly multiplexed and stores the gigantic data (100PB) total on their disks (or SSDs).

Manager Service is the glue that puts them together. This is the first service to be contacted the client, and this decides which servers the client should talk to.

[It is OK for architecture diagram to be simple like this. This is a very hard and deep problem as it is. You don't need to complicate it even more by adding a bunch of boxes in the architecture.]

Request flows

Requests from clients are first handled by API Gateway.

API Gateway chooses right Manager Service.

It then uses File System Service to read and write files.

Detailed component design

Partitioning

[Senior-level deep dive topic]

As we are attempting to store a huge amount of data (100PB), data partitioning is critical. Each file should be split into chunks. Chunks are stored by File System Workers' disks.

Because there need to be thousands of FS Workers, the membership will change often. Some servers crash, others need to be restarted after patching, some servers are added. A good way to handle a dynamic membership is Consistent Hashing.

Consistent Hashing should be applied to this system lazily. For example, let's say a new Worker is added and is now responsible for Chunks IDs X, Y and Z. Instead of moving the Chunks to the new server immediately, we can wait until the chunks are updated or added in the range before writing the data to the new Worker.

Manager Service

[Senior-level deep dive topic]

Manager Services takes care of the membership changes and is responsible for a mapping between Chunk ID and FS Worker.

FS Workers send periodic heartbeats to Manager Service. A hearbeat includes the information about which Chunk IDs the Worker server is storing. Therefore, Manager Service has an updated view of which Worker has which Chunks.

When a file read request comes, Manager Service uses this mapping to determine the Chunk IDs that make up this file, e.g.,:

Manager Service gives this information to FS Service. Manager returns file_id to the client.

When the client tries to read this file, FS Service uses this mapping information to access the proper Worker. It reads the chunk from the appropriate Worker, and return the data.

When the client creates a new file, Manager Service assigns new Chunk IDs to some FS Workers, considering how full Worker's disk is, and how many request it is getting per hour. It sends the mapping data to FS Service. FS Service uses this information to send the chunks to the right Worker.

Trade offs/Tech choices

Chunking

[Mid-level deep dive topic]

We need to pick the right chunk size.

As we have discussed in requirements, we are designing this system for large files (GBs, TBs), such as files used for analytics. As such, we should set chunk sizes fairly large.

It is also important to consider Manager Service. Manager Service has to store the mapping information (which FS Worker has the chunk). If the chunk size is small (let's say 64KB), it would require huge number of mappings, overwhelming Manager Service.

Let's pick 64MB chunk size.

Failure scenarios/bottlenecks

Manager Service Fault Tolerance

[Senior-Level Deep Dive Topic]

Manager Service is a critical component. If the data in Manager Service (mapping Chunk ID -> Worker) is lost, the system will not be able to function until the mapping is rebuilt.

To make this recovery fast, Manager Service would store a log that captures every operation that is executed on Manager Service. When Manager Service crashes, a new replica recover the state and take over as the primary, using this log.

But applying millions of log events takes a long time. As such, Manager Service should also take a snapshot of the mapping data periodically. It would be quicker to use a snapshot (and log events representing fewer operations) to recover Manager Service.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?