4. 设计Dropbox

难度等级:中等

让我们设计一个文件托管服务，如 Dropbox 或 Google Drive。云文件存储使用户能够将他们的数据存储在远程服务器上。通常，这些服务器是由云存储提供商维护并通过网络提供给用户（通常通过互联网）。用户为他们的云数据存储按月付费。

类似服务：OneDrive，Google Drive

1.什么选择云存储？

云文件存储服务因为可以在多终端数据，因而最近变得非常流行。从仅仅使用个人电脑到多终端（这些终端分属于不同的平台，有不同的操作系统，比如说智能手机、平板等）的转变，给云存储服务的流行提供土壤。以下是一些云存储服务的优势：

可用性：

云存储服务的信条是让数据随时随地可用。用户可以从任何地方的任何终端设备访问他们的文件/照片

可靠性和持久性：

云存储的另一个优势是它提供100%的数据可靠性和持久性。云存储确保用户将永远不会通过在不同地方的服务器上存储、保留数据的多个副本而丢失他们的数据。

可扩展性：

用户永远不必担心存储空间不足。有了云存储，只要你愿意为它付费，便能拥有无限的存储空间。

如果您之前没有使用过dropbox.com ，强烈建议在创建一个帐户并上传/编辑文件，试试他们提供的其他服务。这对你理解本章有很大帮助。

2.系统的要求和目标

你应该始终在一开始的时候弄清楚需求。请务必沟通以确定面试官心目中的系统确切的需求。

我们希望从云存储系统中实现哪些需求？这里有我们系统的优先级比较高的需求：

1.用户能够从任何终端上传和下载他们的文件/照片。
2.用户能够与其他用户共享文件或文件夹。
3.服务应该支持设备之间的自动同步，即，在一台设备上更新文件后，它应该在所有设备上同步。
4.系统应支持存储GB级的大文件。
5.ACID是必需的。文件操作要保证原子性、一致性、隔离性和持久性
6.系统应该支持离线编辑。用户应该能够在离线时添加/删除/修改文件，一旦它们上线，他们的所有更改都应同步到远程服务器和其他在线设备。

扩展性需求：

系统应该支持数据快照，这样用户就可以回滚数据。

3.一些设计考量

预期有巨大的读写。
预估读写比率几乎相同。
在内部，文件可以存储在小部分或块中（例如4MB）。这带来好处是，即所有失败的操作只需重试文件的较小部分。如果用户上传文件失败，那么只有失败的块会被重试。
仅通过传输中的更新块文件来减少数据交换。
通过删除重复的块，可以节省存储空间和带宽使用。
在客户端保存一份元数据（文件名、大小等）的本地副本，可以减少轮询服务的频率。
对于小的更改，客户端可以识别出上传差异的部分而不是整个块。

4.容量估算和约束

假设我们有5亿总用户和 1 亿日活跃用户（DAU）。
假设平均每个用户从三个不同的设备登录。
平均而言，如果一个用户有200个文件/照片，我们总共将有1000 亿个文件。
假设平均文件大小为100KB，这将给我们 10PB 的总存储。

100Billion * 100KB => 10PB

还假设每分钟有100万个活跃连接。
- 总用户：5亿
- 单个用户文件数量：200个
- 单个文件平均大小：100KB
- 总文件数量：1000亿个
- 总文件容量：10PB

5.高阶设计

用户将指定一个文件夹作为其设备上的工作空间。任何放置在此文件夹中的文件/照片/文件夹将上传到云端，并且每当文件被修改或删除时，它都会映射到云存储服务器上的同一个文件。用户可以在任何一台设备进行任何修改，这些修改会广播到所有其他设备，其他设备在工作空间中看到的内容是一致的。

更高阶点，需要存储文件及其元数据信息如文件名、文件大小、目录等，以及与谁共享此文件。因此，需要一些可以帮助客户端上传/下载的服务器，一些更新文件元数据和用户信息的服务器。每当更新操作发生时，还需要一些机制来进行消息通知，以便所有客户端都可以同步他们的文件。

如下图所示：

块服务器将与客户端一起从云存储和元数据服务器上传/下载文件
元数据服务器将保存文件的元数据到SQL 或 NoSQL数据库中
同步服务器将处理通知所有客户端发生了哪些更新

6.组件设计

一个个地梳理一遍系统中需要用到的主要组件:

a.客户端

客户端应用程序监听用户的工作空间文件夹，并将其中的所有文件/文件夹同步到远程云存储。客户端应用程序将与存储服务器一起上传，下载并修改文件到后端云存储。客户端还与远程同步服务交互以处理文件元数据更新，例如，文件名、大小、修改日期等的变更。

以下是客户端的一些基本操作：

1.上传和下载文件。
2.检测工作空间文件夹中的文件更改。
3.处理因离线或并发更新引起的冲突。

如何高效处理文件传输？

如上所述，可以将每个文件分成更小的块，以便只传输那些被修改的块而不是整个文件。假设切分每个文件，分成固定大小的4MB一个块。可以计算最佳的块大小：

使用的存储设备云以优化空间利用率和每秒输入/输出操作 (IOPS)
网络带宽
存储中的平均文件大小等

在元数据中，还应该记录每个文件和构成它的块。

应该在客户端保留一份元数据的副本吗？

保留一份元数据的本地副本不仅能够进行离线更新，而且还可以减少轮询服务的频率。

客户端如何高效监听其他发生更新的客户端？

一种解决方案是客户端定期检查服务器是否有任何更新。这种方法的问题是本地看到的更新会有延迟，因为比起服务端发送通知的方式，采用的是定期检查更新的方式。如果客户端经常检查服务器更新，不仅会浪费带宽，服务器大多数时候会返回一个空响应，这也会让服务器保持变得繁忙。以这种方式拉取信息不可扩展的。

可以使用 HTTP 长轮询解决上述问题的方法。使用长轮询的方式，客户端从服务器请求信息，服务器可能不会立即响应。服务器收到轮询时客户端没有新数据，不会发送空响应，服务器保持请求打开并等待以便获得响应信息。一旦它确实有更新，服务器立即向客户端发送 HTTP/S 响应，完成打开的HTTP/S 请求。收到服务器后响应，客户端可以立即发出另一个服务器请求等待更新。

基于以上考虑，可以将客户端分为以下四个部分：

I. Internal Metadata Database将跟踪所有文件、块、版本，以及它们在文件系统中的位置。
II .Chunker 会将文件分割成更小的块。还会还负责从其块中重建文件。分块算法将检测文件中已被由用户修改并仅将这些部分传输到云存储；这将节省带宽和同步时间。
III. Watcher 将监听本地工作空间文件夹并通知Indexer(下面讨论的)用户执行的任何操作，例如当用户创建、删除或更新文件或文件夹时。 Watcher也会监听发生在其他客户端上的任何更新，这些更新是由同步服务器广播的。
IV.Indexer将处理从Watcher接收到的事件，并使用修改后的文件块有关的信息更新Internal Metadata Database。一旦块成功提交/下载到云存储，Indexer将与远程同步服务通信以广播更改其他客户端并更新远程元数据数据库。