System requirements

Functional:

• Users can create, read, update or delete files (blobs) from the file system
• The user can synchronise a folder from one machine to another
  • Update to the file should be replicated across all sync machines

Non-Functional:

• Strong Consistency: users should always have access to the latest version of a file, and editing a file should not create conflicts or out-of-sync files. (ensuring data integrity)
• High availability: the server should always be able to sync a file from a folder (99.99% availability)
• Fault tolerance: A server failure should not result in data loss or render the file inaccessible.

Capacity estimation

Assumption:

Average file size: 2GB

Average user file storage: 100GB

Average file update per user: 1 per min

Total users: 1M active users

storage:

total: 100PB of data

This represents a large amount of disk storage, disregarding the replication factor (for example, RAID 10 with a minimum of four drives). This indicates we will need dedicated storage hardware to support such a large amount of data. Even considering different tiers of data storage

throughput:

100k update per minute ~ 1k rep/s

This is fairly acceptable bandwidth, might be more of a concern

bandwidth:

2GB * 100K/s = 200GB /s

This is a huge bandwidth telling us that a single data centre can't handle all the load (10GB/s internal connection is usually very high commercial). Thus the system must be geo-distributed

API design

Define what APIs are expected from the system...

Realistically, the distributed file storage should be accessed via a drive using sys calls open, write, and close

We can also imagine a matching rest api with CRUD operations, but an RPC service might be more appropriate, especially when it comes to streaming large files.

Thus, let's define 4 commands:

• stats, open, write, and close

Stats(file_id): retrieve file metadata

Open(file_id): lock and read, and stream the content of the file to our server

Write(file_id): upload a new version of a file (must be open first)

Close(file_id): unlock access to the file and commit the changes (if write was invoked)

Database design

Metadata Database -> SQL database storing information about the file and where it is physically stored. Sharded per user, with geo-replicated shards to prevent data loss.

Storage Nodes (Chunk Servers): A large number of simple, commodity servers that do one thing: store and retrieve chunks of data. Sharded per user, with geo-replicated shards to prevent data loss.

User/Tenant database: SQL database for handling user/tenant data and managing authentication and authorisation data.

High-level design

1. Loadbalancer + API gateway: ensure the requests are routed to the right location that has the data, this can be achieved with consistent hashing since data is shard per user or tenant
   1. Note that a large tenant might require additional sharding by introducing a suffix
   2. The api gateway part would ensure authz/authn and rate limiting to secure and prevent abuse of the system
2. Metadata Service: handles updating file metadata (CRUD) and file locks to ensure strong consistency, blocking user requests (writing or reading) if the file is already being interacted with by another user.
   1. The metadata server should handle lock contention and expiration.
3. Storage node: handles receiving and processing file uploads and downloads.
   1. Instead of overwriting the file, write to a new file to provide file versioning and backup capabilities.
   2. The storage node computes the file metadata and updates the metadata server after each write.
   3. Chunk the data into smaller pieces to allow concurrent retrieval.

Request flows

First user will retrieve the file descriptor or metadata -> stats(fileid). This request is sent to the metadata server via the load balancer and the api gateway.

• For security, we can think that stats also return a signed token to access the file from the storage node directly

Then the user can lock and download the file to the local machine -> open(fileid), using the provided token(from the stats) request the user query will be directly routed (by the load balanceer and the api gateway) to the storage server to start the download (we can assume that the file is chunked, a multipart download or concurrent download can be done)

In short, we prefer `Direct Data Transfer` and only perform authorisation once on stats

After fetching the file, reading it and editing, the user can update the file (write(fileid)). Once again, the request is routed to the storage node via the load balancer and api gateway. The storage server

Once the user is done, the `close(fileid)` function can be used to release the lock on the file, allowing other users to read the latest version. The Storage server notifies the metadata server about the new version of the stored file.

Detailed component design

• Distributed Locking Mechanism: The metadata server is responsible for file locking. Since we have many metadata servers, the lock needs to be handled in a distributed fashion. Given that writes are infrequent, I would argue that using a database field to store the lock is sufficient, considering the system's requirements.
• Replication and Consistency Management: Given the strong consistency requirement, we decided that replication should be done synchronously. Every time a chunk is written, the storage server notifies the replicas (over RPC) about the new chunk, only once the majority of servers

Trade offs/Tech choices

• We chose a hard locking mechanism (open/close) to ensure strong consistency
  • This could be relaxed, but mitigation strategies must be implemented to resolve conflicts on write
  • We could relax the lock constraint on reads so that a large number of users can read the same file, even if it is outdated (best effort read with eventual consistency)
• Using a Linux-inspired RPC call is a trade-off: it utilises a well-established interface, making driver development easier, but a more stateless approach (no open -> write -> close) would be equally efficient.
• Direct communication between storage node vs using a message broker. This remove the need for external component like kafka and make the system self sufficent but in impose use to implement protocal for concensus about writes and consistency,

Failure scenarios/bottlenecks

• Storage server failure: We utilise replication, so a single server failure is acceptable. Requests are load-balanced, and data is chunked. If downloading a chunk fails, the client requests the same chunk again, and the request is routed to a healthy server.
  • Using dedicated storage hardware, such as a storage bay acting as a NAS, or a hyperdisk for Google storage, storage servers are stateless, and disks can be reattached to any new server.
  • Adding a new server should be as simple as telling the coordinator the ordinal number of the new server
• Scaling: adding a new server is as simple as telling the manager, and the new server will be considered a new node in the hash ring. Once the backfilling of the disk has completed the server becomes healthy and ready to serve traffic
• DDOS: all requests should be rate-limited to prevent unusually frequent access to a given file. If a file is frequently requested, we can reduce the load on the storage server using a CDN.

Future improvements

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

• Garbage collection and version archiving and lifecycle.