Dropbox - File Sharing System

Functional requirement

Core requirements:

1. User should be able to upload a file from any device
2. User should be able to download a file from any device
3. User should be able to share a file with ohter users and view files shared with them
4. User can automatically sync file across device

Out of scope:

• User should be able to edit files
• User should be able to view files without downloading them

Non functional requirement

Core requirement:

1. System should be highly available
2. System should support file as large as 50 GB
3. System should be secure and reliable. We should be able to recover files if they lost or corrupted
4. System should make upload/download, sync time as fast as possible (low latency)

[!note]
In all most all scenario, we consider availability > consistency. We only consider consistency if every read must receive the most recent write i.e stock trading app, bank system.

For Dropbox system, it's okay if user see stale file

Core identity

Now we need to go through the functional requirement one by one to detect the main identity, so far we can see

1. File: raw data that users will be uploading/downloading and sharing
2. FileMetadata: Metadata associated with the file, include info like files name, size, mime type, who uploade it
3. User: the user of the system

[!note]
Our objective for the system design should be meeting all the functional and non functional requirements. We start with functional first and then lay the non-functional one on top

API or system interface

Lets start simple to just finish the functional requirement. Uploading a file, we may have something like

POST /v1/files
Request: {
    File, Metadata
}

To download the file, we can have something like

GET /files/{fileId} -> File & FileMetadata

To share the file, we can have

POST /files/{fileId}/share

Requests:
{
    User[] // Other user that also have this file
}

[!danger]
These apis might change later, it's important to let the interviewer know that this is for the first stage and you may come back and improve them

To get the changes of the file, we need to do

GET /files/changes?since={timestamp} -> ChangeEvent[]

Each ChangeEvent will include fileId, the type of change created, updated or deleted and the updated Metadata. We support ?since={} params so that the client can only fetch the changes from the last seen.

[!note]
For user information, we need to go from the headers side (either via session token or JWT) to ensure that alll the users are authenticated and authorised. We should not pass user information in request body as it's easy to manipulated

High level design

1) User should be able to upload a file from any device

We need to take care of

• File Metadata
• File (Raw byte)

For metadata, we can use NoSQL like DynamoDB since the metadata is likely to change and loosly structured. However PostgresSQL would work as well here, so either option should be fine

The schema can be simple like

{
    "id": "123",
    "name": "file.txt",
    "size": 1000,
    "mimeType": "text/plain",
    "uploadedBy": "user1"
}

Option 1: File service split file into Blob Stroage and Metadata DB

The FileService once receive the file from the user can store the metadata part in the metadata db, and the actual raw part in the S3 Blob Storage

Challenges

1. We need to handle the case where metadata is saved but the file is not uploaded.
   1. Solution: Transactional approach, only save the metadata is file is uploaded
2. We technically upload twice:
   1. From client to File Service
   2. From File Service to S3
      This would double the bandwidth and redundant

Option 2: Let the user upload the file directly to blob storage

From the previous option, we need to upload twice. The better way is let the user to upload to S3 directly using PresignedURL. We can do the following

POST /v1/files -> PresignedUrl
Request:
{
    FileMetadata
}

The post now only take the file metadata, after user received the presigned url they can upload using PUT

PUT PresignedUrl 
Request:
{
    File
}

Once the file is uploaded, we will send a notification to our backend using S3 Notification. The backend then update the file metadata with status "uploaded"

2) Users should be able to download a file from any device

Download from blob storage

The user can download directly from the blob storage. They can request a presigned url from our backend

GET /files/{fileId} -> PresignedURL

The user can use the presigned url to download the file from blobstorage directly

Challenge

1. The user in different geography will have a slow problem to download. How you address this

Download from CDN

This method is to address the geography problem stated above. We can use a CDN to cache the file closer to the user location. This helps reduce the latency and speed up download time

When a user requests a file, we can use CDN to serve the file from the closest server to user. We can generate a signed URL for the user to download directly from CDN

Challenges: CDN are expensive

• Solution:
  • We only cache specific files that downloaded frequently, and specify how long the file should be cached on CDN
  • We use cache invalidation to remove files from CDN as they're updated or deleted

[!danger]
CDN is only good for immutable object and repeated download. A better solution is to enable S3 Transfer Acceleration where AWS will route network via regional edge nodes.

3) Users should be able to share a file with other users

For this we can create a table contains which file is shared with which user.

[!note]
We avoid to keep track of the sharedUser in the file metadata because the cost of keeping its in sync is high, we better store this in a separate table and lookup when necessary

We can have a table SharedFiles like this

In this case, (userId, fileId) is Composite Primary Key. Using this, we no longer need the sharedUser in the file metadata, we can simply query this SharedFiles table

4) Users can sync files across device

We need to handle 2 way of syncing

1. Local → Remote
2. Remote → Local

Local → Remote

From local side, we need to have a sync agent, which can use the following apis:

• MacOS: FSEvents
• Windows: FileSystemWatcher
• Linux: inotify

These would let the client to sync the data to the remote machine detect for file change. The step are:

1. Using the OS api to monitor the file
2. When detect the change, it queues and upload the modified file
3. The change then send to our server with updated metadata
4. Conflict resolves as last write wins — who most recent edit has the latest version of the file

Remote → local

Client needs to ask the server for new update to poll in. There are 2 way to do this

1. Polling: periodically ask the server "anything changes since my last sync?" Server would query the DB to see if any files has a updatedAt timestamp
2. Websocket or SSE: server maintain an open connection with each client and pushes notification when changes occur. This is more complex but provides real-time update

We can use a hybrid approach:

1. Active notification: server pushes change through websocket or SSE for real-time sync
2. Periodic polling: Client poll in background (every few minutes using GET /v1/files/changes?since={timestamp}) to catch the missed message to ensure eventual consistency

Potential Deep Dives

1) How can you support large files

Typically, there are some limitations that we need to know when uploading a large file

1. Timeouts: to upload a 50GB files, we would need 50gb * 8 bits/byte / 100 Mbps = 4000 seconds (assume internet conneciton is 100 Mbps) which means 1.11 hours. This is very prone to disconnect, network issue
2. Browser and server limitation: some servers and api gateway have hard limit of the maximum files you can upload. i.e AWS API Gateway is 10MB
3. Network interruptions: if an user upload 50 GB file in one go and there is an internet disruption, they will need to restart from scratch
4. User experience: They have no idea how long it takes until their file upload is finished.

Solution — Chunking

We break the file into smaller chunks. These chunks can be uploaded sequentially or parallely depends on the bandwidth. Chunking needs to be done form the client so that the file can be broken into pieces before uploading.

[!danger]
Do not chunk on the server, it does not solve anything

We can chunk a file into 5-10 MBpieces. This can be adjusted base on the network conditions.

[!important]
When chunking, if we use fixed-size chunk (e.g every 5MB) if we have a content added in the beginning of the file, we will shift all the subsequent chunks. The solution for this is to use Content-Defined Chunking (CDC) so that only the surrounding chunks will be updated.

Resumable upload

Chunking also allow us to track the progress status of each chunk, therefore improving the user experience. We can also handle resumable upload by keeping track of which chunk has been uploaded or not.

To support this, our metadata can be something like this:

{
  "id": "123",
  "name": "file.txt",
  "size": 1000,
  "mimeType": "text/plain",
  "uploadedBy": "user1",
  "status": "uploading",
  "chunks": [
    {
      "id": "chunk1",
      "status": "uploaded"
    },
    {
      "id": "chunk2",
      "status": "uploading"
    },
    {
      "id": "chunk3",
      "status": "not-uploaded"
    }
  ]
}

When the user resume upload, they only need to resume from the part that's not-uploaded. In order to do this, we need a way to verify which chunk is uploaded or not.

[!danger]
DynamoDB has 400KB item size limit, this chunks here can grow for very large file. Consider using another table for chunking

Server-side chunk uploaded verification

We can use S3 Etags, when a chunk uploaded successfully, it will get an Etags. The client when finished uploading the chunk, it will send a PATCH request to our backend, saying that the chunk has been uploaded.

The backend then validate this request by checking the Etags on S3 using ListParts API, this is efficient to validate multiple chunks at once.

sequenceDiagram
    participant C as Browser
    participant S3 as S3
    participant F as File Service
    participant DB as Metadata DB

    C->>S3: UploadPart partNumber 7 and chunk bytes
    S3-->>C: ETag abc123
    C->>F: PATCH chunk 7 with ETag abc123
    F->>S3: ListParts uploadId
    S3-->>F: Part 7 with ETag abc123
    F->>DB: Mark chunk 7 as uploaded
    F-->>C: Chunk 7 verified

Check which file is uploaded, should I resume or reupload?

In order to check which file is uplaoded or not, we need a way to check if this file has been uploaded before. In this case, we can implement some fingerprint such as using SHA-256 to uniquely identify the files. This will provide a way to check the file uniqueness even the file name has changed

[!note]
We dont use md5 here since md5 has been vulnerable for known hash collision

For resumable upload, we need to have a fingerprint for each chunk to know which one has been uploaded or not.

So the whole process will be:

1. Client chunk the file into 5-10MB pieces and calculate the finger print for each chunk. Client also calculate the finger print for the entire file — this is used to check for resumability and duplicates
2. Client send a request to check if a file with the same fingerprint exists for the same user, if it does and already has a status of uploading, client can resume the upload
3. If the file does not exist, we will send the POST request to initiate multipart upload. Backend can call CreateMultipartUpload API from S3, generate presigned URLs for each part, save file metadata with status uploadingnd return uploadId with presigned URLs for each chunk
4. Client upload each chunk to S3 using its corresponding presigned URL (each part has its own presigned url with uploadId and partNumber) our backend will verify the chunk uploads with S3 ListParts before updating the chunks field in FileMetadata table to mark it as uploaded
   1. Note: S3 MultiPart upload does not emit S3 event notification per chunk uploading. Therefore we would need to do something like this to keep track of the chunks
5. Once all chunks in our chunks are marked as uploaded, backend will call S3 CompleteMultipartUpload API with the list of part numbers and ETags. This tells S3 to assemble all the parts into single object. Once S3 confirmed successful, we mark the file as uploaded

[!note]
S3 also have Multipart Upload feature that allow us to upload in part, however it does not support S3 event notification for chunks, the S3 event notification only trigger for the whole file. Therefore we need ot use ListParts and client send in the chunks completed separately.

[!danger]
If we call CompleteMultipartUpload it will be 1 single object, that kills the purpose of delta sync. to do this, we do the parts combination locally.

No need to download chunk

When CompleteMultipartUpload is called, S3 will assemble all parts into single object. After that, downloads work like any normal file, the client get presigned URL or CDN signed URL and downloads the complete file.

For large file, S3 and HTTP support Range request let the client download different byte ranges or resume an interrupted download without starting over

2. How can we make uploads, downloads and sync as fast as possible?

So far we have the following optimisation:

1. Downloading:
   1. User download directly from CDN file closest to the user
2. Uploading:
   1. User chunk the file and have resumable upload

To improve further, we need to use compression to speed up both upload and download. However, compression only worth it if time_to_compress/decompress < time_to_download/upload. For file such as images and videos, it's generally not worth it. For text based file, it's worth it.

Since we uploading to S3 directly, compression and decompresison will be at client side.

Some of the compression algorithm we have: gzip, broli, zstd. zstd (zstandard) is a strong choice for us because it compress and decompress the fastest but this is also heavily dependent on what the client support

3) How can we ensure the file security?

We can have:

1. Encryption in transit: we can use HTTPS to encrypt the data transfering between client and server
2. Encryption at rest:
   • When the file are stored in S3, we can enable this feature. We can encrypt with an unique key.
   • Decryption will also happen on S3 side, when the client download it, they will just send the raw byte back
3. Access control:
   • We only provide the download link to authenticated user
   • Signed URL make it available in a short amount of time only.

If we want more security or afraid that signed url will be leaked, we can do the following:

1. Signed URL generated from the server side, we include specific restriction like client IP address. For Cloudfront, this can be encrypted using the server private key
2. When the user download from the signed url, the CDN will use server public key to decrypt and validate these restriction before allowing/denying the access

Final Design

API:

POST /v1/files -> PresignedURL
Request: FileMetadata

PUT {presignedURl}
Request: FileChunk

Patch /v1/files -> 200
Request Partial<FileMetadata> (chunk updates)

GET /v1/files/:fileId -> PresignedURL & FileMetadata

GET /changes?since={timestamp} -> FileMetadata[]