设计Dropbox

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

类似服务：OneDrive、Google Drive
难度级别：中等

1. 为什么选择云存储？

云文件存储服务近年来变得非常流行，因为它们简化了多设备之间的数字资源存储和交换。人们从使用单一的个人计算机转向多设备的趋势——包括不同平台和操作系统的智能手机和平板电脑，这些设备可以随时随地便携式访问——被认为是云存储服务迅速普及的原因。以下是此类服务的一些主要优点：

• 可用性：云存储服务的口号是“随时随地的数据可用性”。用户可以在任何设备上随时随地访问他们的文件或照片。
• 可靠性和持久性：云存储的另一个优点是它提供100%的数据可靠性和持久性。通过在不同地理位置的服务器上存储多个数据副本，云存储确保用户不会丢失数据。
• 可扩展性：用户永远不必担心存储空间不足。使用云存储，您可以根据需求获得无限的存储空间，只要您愿意支付相应的费用。

如果您还没有使用过 Dropbox.com，我们强烈建议您创建一个帐户，上传或编辑文件，并浏览他们服务提供的各种选项。这将有助于您更好地理解本章内容。

2. 系统的需求与目标

💡 在面试开始时应当明确需求，确保通过提问来弄清面试官对系统的确切范围设想。

云存储系统的目标是什么？以下是我们系统的顶层需求：

1. 用户应能够在任意设备上上传和下载其文件或照片。
2. 用户应能够与其他用户共享文件或文件夹。
3. 我们的服务应支持设备间的自动同步，即在一台设备上更新文件后，应在所有设备上同步。
4. 系统应支持存储最大1GB的大文件。
5. 需要支持ACID特性。应保证所有文件操作的原子性、一致性、隔离性和持久性。
6. 系统应支持离线编辑。用户应能够在离线状态下添加、删除或修改文件，并在恢复在线后将所有更改同步到远程服务器和其他在线设备。

扩展需求

• 系统应支持数据快照功能，使用户可以回溯到文件的任何版本。

3. 设计考虑

• 预期有大量的读写操作。
• 读写比率预计几乎相同。
• 文件可以以小部分或块（如4MB）的形式存储，这样可以带来许多好处，例如：对于失败的操作只需重试文件的小块部分。如果用户上传文件失败，则只需重试失败的块。
• 通过仅传输更新的块，可以减少数据交换量。
• 删除重复的块可以节省存储空间和带宽。
• 在客户端保留元数据（文件名、大小等）的本地副本可以减少大量与服务器的往返请求。
• 对于小的更改，客户端可以智能地仅上传差异数据而非整个块。

4. 容量估算与约束

• 假设我们共有5亿用户，其中1亿为日活跃用户（DAU）。

• 假设每位用户平均通过三台不同的设备连接。

• 如果每位用户平均拥有200个文件或照片，总文件数将达到1000亿。

• 假设平均文件大小为100KB，则总存储量为10PB。

  1000亿 * 100KB = 10PB

• 假设每分钟有一百万个活跃连接。

5. 高级设计

用户将在其设备上指定一个文件夹作为工作空间，放置在此文件夹中的任何文件、照片或文件夹将被上传至云端。每当文件被修改或删除时，相应更改将同步至云存储。用户可以在其所有设备上指定类似的工作空间，并且在某个设备上的任何修改都会传播到所有其他设备，以便在各处保持工作空间一致。

在高层设计上，我们需要存储文件及其元数据，例如文件名、文件大小、目录等，以及与谁共享该文件。因此，我们需要一些服务器来帮助客户端将文件上传/下载至云存储，同时也需要一些服务器来更新文件和用户的元数据信息。此外，还需要某种机制来通知所有客户端每当有更新发生时，以便它们能够同步文件。

如图所示，块服务器将与客户端协同工作，从云存储上传/下载文件；元数据服务器将使用SQL或NoSQL数据库保持文件元数据的更新。同步服务器将处理通知所有客户端不同更改的工作流，以实现同步。

6. 组件设计

接下来逐一分析系统的主要组件：

a. 客户端

客户端应用程序监控用户设备上的工作区文件夹，将其中的所有文件和文件夹与远程云存储同步。客户端应用程序将与存储服务器协作，将实际文件上传、下载并修改至后端云存储。客户端还将与远程同步服务交互，以处理任何文件元数据的更新（例如文件名、大小、修改日期等）。

以下是客户端的关键操作：

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

如何高效地处理文件传输？
如上所述，我们可以将每个文件分成更小的块（chunk），这样只传输已修改的块，而不是整个文件。例如，将每个文件分成固定大小为4MB的块。可以基于以下标准静态计算最优块大小：

1. 云端存储设备以优化空间利用率和每秒输入/输出操作（IOPS）；
2. 网络带宽；
3. 存储中的平均文件大小等。在元数据中应保留每个文件及其组成块的记录。

是否应在客户端保存一份元数据的副本？
保留本地元数据副本不仅支持离线更新，还能减少更新远程元数据时的大量往返请求。

客户端如何有效监听其他客户端发生的更改？
一种解决方案是客户端定期向服务器查询是否有更新，但这种方式会导致本地更新延迟。此外，如果客户端频繁查询服务器，会浪费带宽（因为服务器大部分时间返回空响应）并保持服务器忙碌，这种拉取方式不具备可扩展性。

可以使用HTTP长轮询来解决该问题。使用长轮询时，客户端请求信息，但预期服务器可能不会立即响应。如果服务器在收到轮询请求时没有新数据，服务器会保持请求打开，等待新数据。服务器有新信息时会立即向客户端发送HTTP/S响应，完成该HTTP/S请求。客户端接收响应后可立即发起新请求以获取未来更新。

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

I. 内部元数据数据库
负责跟踪所有文件、块、它们的版本和在文件系统中的位置。

II. 分块器
将文件分成称为块的小片段，并负责根据块重构文件。分块算法会检测用户修改的文件部分，并仅传输这些部分到云存储，节省带宽和同步时间。

III. 监视器
监控本地工作区文件夹，将用户执行的任何操作（如创建、删除或更新文件或文件夹）通知索引器（详见下文）。监视器还会监听由同步服务广播的其他客户端发生的更改。

IV. 索引器
处理从监视器接收到的事件，并更新内部元数据数据库中有关修改文件的块的信息。块成功提交/下载至云存储后，索引器将与远程同步服务通信，以向其他客户端广播更改并更新远程元数据数据库。

如何应对服务器响应缓慢的情况？
当服务器繁忙或无响应时，客户端应采用指数回退（exponential back-off）策略。也就是说，如果服务器响应过慢，客户端应延迟重试，并逐步增加延迟时间。

移动客户端是否应立即同步远程更改？
与桌面或网页客户端不同，移动客户端通常按需同步，以节省用户的带宽和存储空间。

b. 元数据数据库

元数据数据库负责维护文件/块、用户和工作区的版本控制和元数据信息。元数据数据库可以是关系型数据库（如 MySQL）或 NoSQL 数据库服务（如 DynamoDB）。无论数据库类型如何，同步服务都应使用数据库提供文件的一致视图，特别是在多个用户同时操作同一文件的情况下。由于 NoSQL 数据库为追求可扩展性和性能而不支持 ACID 属性，如果选择此类数据库，则需在同步服务的逻辑中程序化地实现 ACID 属性的支持。然而，使用关系型数据库可以简化同步服务的实现，因为它们原生支持 ACID 属性。

元数据数据库应存储以下对象的信息：

1. 块（Chunks）
2. 文件（Files）
3. 用户（User）
4. 设备（Devices）
5. 工作区（同步文件夹，Workspace）

c. 同步服务

同步服务是负责处理客户端文件更新并将这些更改应用到其他订阅客户端的组件。同时，它会将客户端的本地数据库与远程元数据数据库中的信息同步。由于同步服务在管理元数据和同步用户文件方面起着关键作用，它是系统架构中最重要的部分。桌面客户端通过同步服务与云存储进行交互，以获取更新或将文件和更新发送至云存储及其他用户。如果客户端曾处于离线状态，当其重新上线时会立即查询系统以获取新更新。当同步服务收到更新请求后，会首先与元数据数据库进行一致性检查，随后执行更新操作，并向所有订阅的用户或设备发送通知，告知文件更新情况。

同步服务的设计应尽量减少客户端与云存储之间的数据传输，以提高响应速度。为实现该设计目标，同步服务可以使用差异算法来减少需要同步的数据量。与其在客户端和服务器之间传输整个文件，不如仅传输文件两个版本之间的差异部分。这样只传输文件被修改的部分，不仅降低了带宽消耗，也减少了用户的云数据存储需求。如前所述，文件将被分成4MB的块，且只传输修改过的块。服务器和客户端可以计算一个哈希值（如SHA-256）来判断是否更新本地块的副本。如果服务器上已存在一个具有相同哈希的块（即使是来自其他用户），则无需创建新副本，而可以复用现有块。这部分将在“数据去重”章节中详细讨论。

为了实现高效、可扩展的同步协议，我们可以在客户端和同步服务之间使用通信中间件。该消息中间件应提供可扩展的消息队列和变更通知功能，以支持大量客户端的拉取或推送策略。这样，多个同步服务实例可以从一个全局请求队列中接收请求，同时通信中间件能够平衡其负载。

d. 消息队列服务

在我们的架构中，消息中间件是一个关键部分，需能够处理大量请求。一个支持客户端和同步服务之间异步消息通信的可扩展消息队列服务最符合应用需求。消息队列服务支持分布式组件之间的异步和松耦合消息通信，能够在一个高度可用、可靠和可扩展的队列中高效存储任意数量的消息。

消息队列服务将在系统中实现两种队列类型。

1. 请求队列是一个全局队列，所有客户端共享。客户端更新元数据数据库的请求首先会发送至请求队列，然后由同步服务从中取出请求以更新元数据
2. 响应队列对应于每个订阅的客户端，负责将更新消息传递给各个客户端。由于消息在被客户端接收后即从队列中删除，我们需为每个订阅的客户端创建独立的响应队列以共享更新消息。

e. 云/块存储

云/块存储用于存储用户上传的文件块。客户端直接与存储交互以发送和接收对象。将元数据与存储分离使我们可以选择使用云存储或内部存储。

消息队列服务是系统架构中不可或缺的一部分，它需要能够处理大量请求，支持客户端和同步服务之间的异步消息通信。消息队列服务能以异步、松耦合的方式实现系统分布式组件之间的消息通信，并具备高可用性、可靠性和可扩展性。

7. 文件处理流程

以下顺序描述了在客户端A更新与客户端B和C共享的文件时，应用组件之间的交互。如果其他客户端在更新时不在线，消息队列服务会将更新通知保存在各自的响应队列中，等待它们上线后再传送。

1. 客户端A将文件块上传至云存储。
2. 客户端A更新元数据并提交更改。
3. 客户端A收到确认信息，同时向客户端B和C发送变更通知。
4. 客户端B和C接收元数据更新并下载更新的文件块。

8. 数据去重

数据去重是一种消除重复数据副本的技术，用于提高存储利用率。该技术也可用于网络数据传输，以减少传输的字节数。对于每个新接收的文件块，我们可以计算其哈希值，并与已有文件块的哈希值进行比较，以确定存储中是否已存在相同文件块。

在系统中，我们可以通过以下两种方式实现去重：

a. 后处理去重

在后处理去重中，新文件块会先存储到设备中，随后某个进程会分析数据以查找重复项。其优点是客户端无需等待哈希计算或查找完成便可存储数据，确保不会影响存储性能。此方法的缺点是：

1. 我们会暂时存储重复数据；
2. 重复数据传输会消耗带宽。

b. 实时去重

实时去重则在客户端录入数据时实时计算哈希值。如果系统发现已存在相同的文件块，元数据中将只记录指向该块的引用，而非完整的块副本。此方法能优化网络和存储的使用。

9. 元数据分区

为了扩展元数据数据库，我们需要对其进行分区，以存储数百万用户和数十亿文件/块的信息。我们需要设计一个分区方案，将数据分布存储在不同的数据库服务器上。

1. 垂直分区：可以将数据库按照功能分区，将特定功能相关的表存储在同一服务器上。例如，可以将所有用户相关的表存储在一个数据库中，将所有文件/块相关的表存储在另一个数据库中。虽然这种方法实现简单，但存在以下问题：

   • 我们仍会面临扩展性问题。如果需要存储数万亿个块，数据库可能无法支持如此巨大的记录量，如何进一步分区这些表？
   • 在两个不同数据库中连接表可能导致性能和一致性问题。我们需要多频繁地连接用户和文件表？

2. 基于范围的分区：可以根据文件路径的首字母将文件/块分配到不同的分区。例如，将所有以字母“A”开头的文件存储在一个分区，将以字母“B”开头的文件存储在另一个分区。这种方法称为基于范围的分区。对于较少见的首字母，可以将其合并到同一个数据库分区中。我们应静态地设计该分区方案，以便能够始终以可预测的方式存储和查找文件。

   • 主要问题在于可能导致服务器负载不平衡。例如，如果将所有以字母“E”开头的文件放入一个分区，后来发现文件过多，可能会超出该分区的存储容量。

3. 基于哈希的分区：在该方案中，利用存储对象的哈希值确定该对象应存储的数据库分区。在此场景下，可以计算文件对象“FileID”的哈希值，以确定文件的存储分区。哈希函数会将对象随机分布到不同的分区中，例如，哈希函数将任何ID映射到1到256之间的一个数字，该数字即为对象的存储分区。

   • 此方法仍可能导致某些分区负载过高，可以通过使用一致性哈希来解决。

10. 缓存

在系统中可设置两种缓存。为处理热门文件/块，可为块存储引入缓存。例如，可使用 Memcached 这样的现成方案，将整个块及其ID/哈希存储起来，块服务器在访问块存储之前可快速检查缓存是否已包含所需的块。根据客户端的使用模式，我们可确定所需的缓存服务器数量。一个高端商用服务器可具备144GB的内存，可缓存约36,000个块。

关于缓存替换策略，最适合的策略是当缓存满时，用新/热门的块替换旧块。最近最少使用（LRU）策略是一个合理的选择，根据此策略，优先丢弃最近最少使用的块。此外，还可以为元数据数据库设置缓存。

11. 负载均衡器（LB）

系统中可在两个位置增加负载均衡层：

1. 客户端与块服务器之间
2. 客户端与元数据服务器之间

初始可采用简单的轮询方法，将请求均匀分配给后端服务器。该方法易于实现且无额外开销，其优势在于当服务器宕机时，负载均衡器会将其移出并停止向其发送流量。然而，轮询不考虑服务器负载，如果某服务器超载或响应缓慢，LB仍将继续发送新请求。为应对这种情况，可采用更智能的负载均衡解决方案，定期查询后端服务器的负载情况并动态调整流量。

12. 安全性、权限与文件共享

在云中存储文件时，用户最关心的是数据的隐私和安全性，尤其是在系统中用户可共享文件给其他用户，甚至公开共享。为处理此需求，我们将在元数据数据库中存储每个文件的权限，以便管理用户对文件的可见性与可修改性。