文件同步系统设计：Dropbox 式同步的工作原理

你在笔记本电脑上保存了一个 300 MB 的演示文稿，一分钟后它就能在手机上打开。接着你修正了某张幻灯片上的一个错别字，更新只用了一秒，因为只有改动的部分被传输。文件同步服务让这一切看起来很简单，但底层是对两类截然不同的数据的谨慎拆分，外加一套能够承受不稳定网络、离线编辑以及几天后才醒来的设备的协议。

本文设计一个 Dropbox 式的同步服务：需求与估算、元数据与内容的拆分、分块与内容哈希、上传与提交协议、元数据日志与游标、通知、冲突和垃圾回收，并配有一张架构图。

需求

• 在一台设备上保存的文件，在几秒到几分钟内出现在用户的其他设备上。
• 只上传和下载发生变化的数据。
• 离线时所做的编辑在设备重连后同步，并发编辑绝不会悄无声息地相互覆盖。
• 共享文件夹可以跨账户使用。
• 永不丢失数据；提供版本历史用于恢复。

容量

假设有 1,000 万台活跃设备，每台每天同步 20 次变更，去重之后每次变更平均有 256 KB 新数据：

元数据的速率并不高；数据量很大，但存储起来很简单。正是这种不对称决定了设计。

把元数据与内容分开

最重要的决定，是把文件内容和文件元数据当作两个不同的系统来对待：

• 内容以不可变的块来存储，用其字节的哈希来寻址。块很大、只写一次，并且很容易在对象存储中复制。
• 元数据记录哪个路径上的哪个文件、在哪个版本中、由哪些块组成。它很小、持续变化，并且需要事务和严格的顺序。

Dropbox 在其流式同步文章中描述了这种拆分：每个文件被划分为 4 MB 的块，每个块用 SHA-256 计算哈希，文件内容由这些哈希组成的列表来标识，也就是它的块列表。其公开 API 至今仍以内容哈希的形式提供同样的思路：先计算每个 4 MB 块的 SHA-256，再计算这些块哈希拼接后的 SHA-256。

分块：固定还是由内容定义

固定大小的块简单，计算也快。它的弱点在文件开头附近插入字节时暴露出来：插入点之后的每个块边界都会移动，每个块的哈希都会改变。

内容定义分块（content-defined chunking）把边界放在内容上的滚动哈希匹配某种模式的位置，rsync 的滚动校验和以及 FastCDC 等较新的算法都是这样做的。边界会随内容移动，因此一次插入只会改变它附近的分块。

对于主要在末尾追加或整体替换的文件，固定块就足够了。对于在中间被编辑的文件，例如大型文档、磁盘镜像或数据库，内容定义分块能节省多得多的带宽。

上传与提交协议

1. 桌面客户端通过操作系统的文件监视器察觉到变化，等文件不再变化后，再对它分块并计算哈希。
2. 它向元数据服务发送一次提交：这个路径、这份新的块列表，基于父版本 N。
3. 元数据服务检查自己已经存储了哪些哈希，并回复它还需要的那些。
4. 客户端只把这些块并行上传到块服务，每个块都用其哈希校验。中断的上传会从缺少的块处继续。
5. 客户端重试提交。此时所有块都已存在，于是元数据服务把该文件的新版本追加到日志中。

顺序就是安全性所在：一个引用了若干块的版本，在这些块全部存储之前绝不会被提交。无论在哪个时刻崩溃，留下的要么是旧版本，要么是新版本，绝不会出现指向缺失数据的文件。

内容寻址还顺带实现了去重。复制到三个文件夹中的文件，或回滚到早期版本的文件，都不会上传任何新内容。跨账户去重能节省更多空间，但可能暴露出别人存储了同一个文件，因此许多设计只在单个账户或共享文件夹内去重。

元数据日志与游标

把文件分组到命名空间中，例如用户自己的文件夹树或某个共享文件夹。元数据服务为每个命名空间维护一份只追加的日志：每次变更都获得下一个序列号，并记录路径、版本和块列表。

每个客户端为每个命名空间保存一个游标：它已应用的最后一个序列号。这样，向下同步就只剩一个问题：“把这个命名空间中我的游标之后的所有内容给我。”日志让这件事成本低廉、有序且可以续传。离线一周的设备问同样的问题，就会收到一周的变更。按命名空间对元数据分片，因为一个命名空间中的变更从不需要与另一个命名空间共用事务。

通知：告诉设备去同步

让每台空闲设备都去轮询日志太浪费了。取而代之的是，空闲的桌面客户端与通知服务保持一个长轮询连接。当某个命名空间的日志前进时，服务就用“有变更”回复等待中的请求；每个客户端随后列出其游标之后的变更，并下载自己没有的块。Dropbox 的公开 API 以 list_folder/longpoll 和 list_folder/continue 提供了同样的模式。

移动应用无法在后台保持连接，因此依靠平台的推送通知，并在应用打开时同步。

客户端这一侧

桌面客户端占了系统的一半。它维护一个本地数据库，记录每个文件最后一次同步时的状态：路径、版本、块列表、大小和修改时间。比较三种状态即可决定每个动作：

本地块缓存可以避免下载设备在其他文件中已经持有的块。

冲突

两台设备在离线时编辑了同一个文件。之后两者都基于父版本 N 提交。元数据服务接受第一次提交，生成版本 N+1，并拒绝第二次提交，因为它的父版本已经不是最新的了。失败的客户端不会去合并它无法理解的二进制文件，而是把自己的版本作为冲突副本保存在原文件旁边，并同步两者。由用户来决定。

这就是乐观并发控制：每次提交都写明它所基于的版本。同样的检查也处理目录操作，而这在实践中更难：一台设备上的重命名与另一台设备上的编辑，或者与编辑同时发生的删除。把这些情况明确写下来；同步引擎正是在这些地方丢失数据的。

版本历史与垃圾回收

旧版本保留着它们的块列表，因此恢复一个文件，只需把旧的块列表作为最新版本提交即可。只有当保留期内没有任何版本引用某个块时，它才成为垃圾。用带宽限期的标记-清除来运行垃圾回收，绝不要在最后一个引用消失时立即删除，因为某个客户端可能正要提交一份块列表，而其中复用的块恰好被服务器认为是孤立的。

文件同步图

这张图的读法如下：

• 左侧的笔记本电脑向元数据服务提交块列表，并拿回服务器缺少的哈希。
• 块上传发往块服务，并以哈希为键存入对象存储。
• 元数据服务把新版本追加到 Postgres 中的命名空间日志，并发布这次变更。
• 通知服务响应手机的长轮询；手机列出其游标之后的变更，只下载缺少的块。
• Markdown 块按顺序列出了协议的六个步骤。

清晰地绘制同步系统

• 把元数据和内容画成两条独立的路径。 存储不同，扩展方式不同，故障模式也不同。
• 在连线上为协议步骤编号。 提交、缺少的哈希、上传、再次提交：顺序本身就是正确性的论证。
• 画出第二台设备。 同步关乎读取方，也同样关乎写入方；只有一个客户端的图会掩盖通知和游标。
• 标注分区键：元数据用命名空间，块用哈希。

通用方法请参阅系统设计图示例。推送部分与通知系统设计类似，向对象存储分块上传也出现在视频流架构图中，而元数据的分区则遵循数据库分片图。

在 Archboard 中构建

1. 使用 Google 或 GitHub 登录，并新建一张图。
2. 添加两个网络节点包中的 设备 节点：一台笔记本电脑和一部手机。
3. 为同步后端添加一个基础节点包中的 框架，并在其边缘放一个云节点包中的 API 网关。
4. 在框架内，为元数据、块和通知服务添加三个云节点包中的 计算实例 节点，为日志添加一个数据节点包中的 Postgres 节点，为块添加一个云节点包中的 对象存储 节点，并为日志事件添加一个数据节点包中的 Kafka 节点。
5. 按协议顺序为连线编号：提交、缺少的哈希、上传、再次提交、通知、列出与下载。
6. 添加一个基础节点包中的 Markdown 块，写明协议和容量。

这个示例共用 11 个图表节点，在 Free 套餐的限制之内。

常见问题

同步服务为什么要把文件切分成块？ 分块让客户端只上传有变化的部分、续传中断的传输，并对相同数据去重。块的哈希就是它的身份，因此服务器能立刻知道自己已经有哪些块。

应该使用固定大小分块还是内容定义分块？ 固定大小的块更简单，计算成本更低。内容定义分块在文件中间插入字节时能保持分块边界稳定，对于原地编辑的文件可以节省带宽。

客户端如何知道服务器上有什么变化？ 它为每个命名空间保存一个游标，并向元数据服务请求游标之后的所有日志条目。何时去请求，由长轮询或推送通知告诉它。

冲突的编辑如何处理？ 每次提交都写明它所基于的版本。如果另一台设备先提交了，这次提交就会失败，客户端会把自己的编辑保存为冲突副本，而不是覆盖对方的编辑。

去重能跨用户生效吗？ 可以，但这可能暴露出另一个账户存储了同一个文件，而且它无法与按用户加密同时使用。许多服务把去重限制在单个账户或共享文件夹之内。

免费开始 — 1 个席位，无需信用卡。