File hosting services like Dropbox/ Google Drive require ability to sync files fast between clients. One of the simple techniques is to break the file into multiple fixed-size blocks so
- we only need to sync chunks that are modified, not the whole file.
- all failed operation only be retried for smaller parts of the file.
Each block is hashed with SHA-256 and stored. The file will uniquely identified by this list of SHA-256 hashes, a.k.a
High level architecture of a File-hosting system:
- Metadata Server: maintains database of users, files, blocks ...
- Block Server: maintains a key-value store: hash -> content url. It is responsible for uploading and downloading request from Clients.
- Notification Server: notifying clients about update happens so they can sync.
Simplified schema of files:
Each file's version is identified by
(namespace_id, id) in DB:
namespace_id is id of the folder,
id is monotonically increasing within a namespace.
prev_rev is reference id to previous version.
Initial sync protocol
Let's consider the protocol prior to
Stream Sync first.
When uploading client (UL client) notice a new file appear in its local folder, it attemps to
commit the blocklist to metadata_server with a list of hash of the new file. The server will check if those hashes are known. If not, server returns
need blocks, indicating which blocks are missing.
UL Client talks directly with blockserver to upload these blocks. File maybe large so it may take multiple requests to upload.
When the uploading process is done,
UL Client attemps to commit again. The metaserver will update the Metadata DB with new files, blocks.
When download client (DL Client) was notified that there is a new file uploaded, it will make a
list request to get the list of block need to be download.
DL Client then checks if the blocks exist locally. For new blocks,
DL Client will download from blockserver and construct the file.
Here is the whole sync protocol:
We can see from above diagram, DL Client doesn't need to wait until UL Client upload the file completely to start download. As soon as first block was uploaded, the DL Client can start downloading process. This way can reduce the sync time, especially for large files (which requires multiple upload, download requests)
Changes in protocol:
- After received the failed commit, metaserver write to Memcached the blocklist that is not synced to S3 yet. And it triggers Notification server to notice DL Client.
- DL Client then send
listrequest to metaserver, requesting for information of prefetchable blocks.
- When the downloading process is completed, blocklist in Memcached is evicted.
Overral, this new protocol helps reduce the sync tims by
25%, according to Dropbox