需求

让我们设计一个文件托管服务，比如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，这将为我们提供10 PB的总存储空间。

100B*100KB=>10PB

•我们还假设每分钟将有一百万个活动连接。

5.高级设计

用户将指定一个文件夹作为其设备上的工作区。放置在此文件夹中的任何文件/照片/文件夹都将上载到云中，无论何时修改或删除文件，都将以相同的方式反映在云存储中。用户可以在其所有设备上指定类似的工作区，并且在一个设备上所做的任何修改都将传播到所有其他设备，以便在任何地方都具有相同的工作区视图。

在较高级别上，我们需要存储文件及其元数据信息，如文件名、文件大小、目录等，以及与谁共享此文件。因此，我们需要一些能够帮助客户端将文件上传/下载到云存储的服务器，以及一些能够帮助更新文件和用户元数据的服务器。我们还需要一些机制，以便在更新发生时通知所有客户机，以便他们能够同步其文件。

如下图所示，块服务器将与客户端一起从云存储上传/下载文件，元数据服务器将在SQL或NoSQL数据库中更新文件的元数据。同步服务器将处理通知所有客户端不同同步更改的工作流。

6.组件设计

让我们逐一介绍一下系统的主要组件：

A.客户端

客户端应用程序监视用户计算机上的工作区文件夹，并将其中的所有文件/文件夹与远程云存储同步。客户端应用程序将与存储服务器协作，将实际文件上载、下载和修改到后端云存储。客户端还与远程服务器进行交互

同步服务，用于处理任何文件元数据更新，例如文件名、大小、修改日期等的更改。

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

1.上传和下载文件。

2.检测工作区文件夹中的文件更改。

3.处理脱机或并发更新引起的冲突。

我们如何有效地处理文件传输？

如上所述，我们可以将每个文件分解为更小的块，以便只传输修改过的块，而不是整个文件。假设我们将每个文件分成固定大小的4MB块。我们可以根据1）我们在云中使用的存储设备来优化空间利用率和每秒输入/输出操作（IOPS）2）网络带宽3）存储中的平均文件大小等静态计算最佳块大小。在我们的元数据中，我们还应该记录每个文件以及构成它的块。

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

保留元数据的本地副本不仅使我们能够进行脱机更新，还可以节省大量更新远程元数据的往返时间。

客户机如何有效地侦听其他客户机发生的更改？

一种解决方案是，客户机定期与服务器检查是否有任何更改。这种方法的问题是，我们在本地反映更改时会有延迟，因为客户端会定期检查更改，而服务器则会在发生更改时发出通知。如果客户机经常检查服务器的更改，这不仅会浪费带宽，因为服务器大部分时间都必须返回空响应，而且会使服务器保持忙碌。以这种方式提取信息是不可伸缩的。

上述问题的解决方案可以是使用HTTP长轮询。

通过长时间轮询，客户机从服务器请求信息，期望服务器不会立即响应。如果在收到轮询时服务器没有客户端的新数据，则服务器将保持请求打开并等待响应信息变为可用，而不是发送空响应。一旦有了新信息，服务器立即向客户端发送HTTP/S响应，完成打开的HTTP/S请求。在收到服务器响应后，客户机可以立即发出另一个服务器请求，以便将来进行更新

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

I.内部元数据数据库，将跟踪所有文件、块、其版本及其在文件系统中的位置。

二,。Chunker将文件分割成更小的块。它还将负责从文件块重建文件。我们的分块算法将检测用户修改的文件部分，并仅将这些部分传输到云存储；这将节省我们的带宽和同步时间。

三、 Watcher将监视本地工作区文件夹，并将用户执行的任何操作（例如，当用户创建、删除或更新文件或文件夹时）通知索引器（如下所述）。Watcher还侦听同步服务广播的其他客户端上发生的任何更改。

四、 Indexer将处理从观察者接收到的事件，并使用有关修改文件块的信息更新内部元数据数据库。一旦区块成功提交/下载到云存储，索引器将与远程同步服务通信，向其他客户端广播更改并更新远程元数据数据库。

客户端应该如何处理速度较慢的服务器？

如果服务器正忙/没有响应，客户端应该以指数方式退出。这意味着，如果服务器响应太慢，客户端应该延迟重试，并且延迟应该成倍增加。

移动客户端是否应立即同步远程更改？

与桌面或web客户端不同，移动客户端通常按需同步以节省用户的带宽和空间。

B元数据库

元数据数据库负责维护有关文件/块、用户和工作区的版本控制和元数据信息。元数据数据库可以是关系数据库（如MySQL）或NoSQL数据库服务（如DynamoDB）。无论数据库的类型如何，同步服务都应该能够使用数据库提供文件的一致视图，特别是当多个用户同时使用同一文件时。由于NoSQL数据存储不支持有利于可伸缩性和性能的ACID属性，因此我们需要以编程方式将对ACID属性的支持合并到同步服务的逻辑中，以防

选择这种数据库。但是，使用关系数据库可以简化同步服务的实现，因为它们本机支持ACID属性。

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

1.Chunks

2.文件夹

3.使用者

4.装置

5.工作区（同步文件夹）

C同步服务

同步服务是处理客户端所做文件更新并将这些更改应用于其他订阅客户端的组件。它还将客户端的本地数据库与远程元数据数据库中存储的信息同步。同步服务是系统体系结构中最重要的部分，因为它在管理元数据和同步用户文件方面起着关键作用。桌面客户端与同步服务通信，以从云存储获取更新，或将文件和更新发送到云存储，并可能发送给其他用户。如果客户端离线一段时间，它会在新的更新上线后立即轮询系统。当同步服务收到更新请求时，它会检查元数据数据库的一致性，然后继续更新。随后，将向所有订阅的用户或设备发送通知，以报告文件更新

同步服务的设计应确保在客户端和云存储之间传输更少的数据，以实现更好的响应时间。为了达到这个设计目标，同步服务可以使用差异算法来减少需要同步的数据量。我们可以只传输文件的两个版本之间的差异，而不是将整个文件从客户端传输到服务器，或者反之亦然。因此，仅传输已更改的文件部分。这也减少了最终用户的带宽消耗和云数据存储。如上所述，我们将把文件分成4MB的块，并且只传输修改过的块。服务器和客户端可以计算散列（例如，SHA-256），以查看是否更新块的本地副本。在服务器上，如果我们已经有一个具有类似哈希的块（甚至来自另一个用户），我们不需要创建另一个副本，我们可以使用相同的块。这将在后面的重复数据消除中详细讨论。

为了能够提供高效和可扩展的同步协议，我们可以考虑使用客户端和同步服务之间的通信中间件。消息传递中间件应提供可扩展的消息队列和更改通知，以支持使用拉或推策略的大量客户端。这样，多个同步服务实例可以接收来自全局请求队列的请求，并且通信中间件将能够平衡其负载。

D消息队列服务

我们架构的一个重要部分是消息传递中间件，它应该能够处理大量的请求。支持客户端和同步服务之间基于异步消息的通信的可扩展消息队列服务最适合我们应用程序的要求。消息队列服务支持系统分布式组件之间的异步和松散耦合的基于消息的通信。消息队列服务应该能够高效地将任意数量的消息存储在高可用、可靠和可扩展的队列中。

消息队列服务将在我们的系统中实现两种类型的队列。请求队列是一个全局队列，所有客户端都将共享它。客户端更新元数据数据库的请求将首先发送到请求队列，同步服务将从那里获取更新元数据的请求。对应于单个订阅客户端的响应队列负责将更新消息传递给每个客户端。因为一旦客户端接收到消息，就会从队列中删除消息，所以我们需要为每个订阅的客户端创建单独的响应队列来共享更新消息。

E云/块存储

云/块存储存储用户上传的文件块。客户机直接与存储器交互，以从存储器发送和接收对象。元数据与存储的分离使我们能够使用云中或内部的任何存储。

7.文件处理工作流

下面的序列显示了当客户端a更新与客户端B和C共享的文件时，应用程序组件之间的交互，因此它们也应该接收更新。如果其他客户端在更新时未联机，则消息队列服务会将更新通知保留在单独的响应队列中，直到它们稍后联机。

1.客户端A将块上传到云存储。

2.客户端A更新元数据并提交更改。

3.客户端A得到确认，并向客户端B和C发送有关更改的通知。4.客户端B和C接收元数据更改并下载更新的块。

8.重复数据消除

重复数据消除是一种用于消除重复数据拷贝以提高存储利用率的技术。它还可以应用于网络数据传输，以减少必须发送的字节数。对于每个新传入的块，我们可以计算它的散列，并将该散列与现有块的所有散列进行比较，以查看我们的存储中是否已经存在相同的块。

我们可以通过两种方式在系统中实施重复数据消除：

A.后处理重复数据消除

使用后处理重复数据消除，新数据块首先存储在存储设备上，然后某个进程分析数据以查找重复。这样做的好处是，客户机在存储数据之前不需要等待散列计算或查找完成，从而确保存储性能不会降低。这种方法的缺点是：1）我们将不必要地存储重复数据，尽管在短时间内，2）重复数据的传输将消耗带宽。

B在线重复数据消除

或者，当客户端在其设备上输入数据时，可以实时完成重复数据消除散列计算。如果我们的系统识别出一个已经存储的区块，那么元数据中将只添加对现有区块的引用，而不是区块的完整副本。这种方法将为我们提供最佳的网络和存储利用率。

9元数据分区

为了扩展元数据数据库，我们需要对其进行分区，以便它能够存储有关数百万用户和数十亿文件/块的信息。我们需要提出一种分区方案，将数据划分并存储在不同的DB服务器中。

1.垂直分区：

我们可以对数据库进行分区，以便在一台服务器上存储与某个特定功能相关的表。例如，我们可以将所有与用户相关的表存储在一个数据库中，将所有与文件/块相关的表存储在另一个数据库中。尽管这种方法很容易实现，但也存在一些问题：

我们还会有规模问题吗？如果我们要存储数以万亿计的数据块，而我们的数据库无法支持存储如此大量的记录，该怎么办？我们如何进一步划分这些表？

2.在两个单独的数据库中连接两个表可能会导致性能和一致性问题。我们必须多久连接一次用户表和文件表？

2.基于范围的分区：

如果我们根据文件路径的第一个字母将文件/块存储在单独的分区中，会怎么样？在这种情况下，我们将所有以字母“A”开头的文件保存在一个分区中，将以字母“B”开头的文件保存到另一个分区中，依此类推。这种方法称为基于范围的分区。我们甚至可以将某些不太常见的字母组合到一个数据库分区中。我们应该静态地提出这个分区方案，这样我们就可以始终以可预测的方式存储/查找文件。

这种方法的主要问题是，它可能导致服务器不平衡。例如，如果我们决定将所有以字母“E”开头的文件放在一个DB分区中，后来我们发现以字母“E”开头的文件太多，以至于我们无法将它们放在一个DB分区中

3.基于散列的分区：

在这个方案中，我们对正在存储的对象进行散列，并根据这个散列计算出这个对象应该去的DB分区。在我们的情况下，我们可以采取

我们正在存储的文件对象的“FileID”散列，以确定文件将存储的分区。我们的散列函数会将对象随机分布到不同的分区中，例如，我们的散列函数总是可以将任何ID映射到[1…256]之间的一个数字，这个数字将是我们存储对象的分区。

这种方法仍然会导致分区过载，这可以通过使用一致散列来解决。

10缓存

我们的系统中可以有两种缓存。为了处理热文件/块，我们可以为块存储引入缓存。我们可以使用一个现成的解决方案，比如Memcached，它可以使用其各自的id/散列存储整个块，并且在点击块存储之前，块服务器可以快速检查缓存是否具有所需的块。根据客户端的使用模式，我们可以确定需要多少缓存服务器。高端商用服务器可以有144GB的内存；一个这样的服务器可以缓存36K个块。

哪种缓存替换策略最适合我们的需要？当缓存已满，并且我们希望用较新/较热的块替换块时，我们将如何选择？对于我们的系统来说，最近最少使用（LRU）是一个合理的策略。在此策略下，我们首先丢弃最近使用最少的块。类似地，我们可以为元数据数据库提供缓存。

11负载平衡器（磅）

我们可以在系统中的两个位置添加负载平衡层：

1）在客户端和块服务器之间，

2）在客户端和元数据服务器之间。

最初，可以采用一种简单的循环方法，在后端服务器之间平均分配传入的请求。此LB易于实现，不会引入任何开销。这种方法的另一个好处是，如果服务器死机，LB将使其停止旋转，并停止向其发送任何流量。

循环LB的一个问题是，它不会考虑服务器负载。如果服务器过载或速度较慢，LB不会停止向该服务器发送新请求。为了解决这个问题，可以放置一个更智能的LB解决方案，定期查询后端服务器的负载，并根据负载调整流量。

12安全、权限和文件共享

在云中存储文件时，用户最关心的一个问题是他们数据的隐私和安全性，特别是在我们的系统中，用户可以与其他用户共享他们的文件，甚至公开与所有人共享。为了处理这个问题，我们将在元数据数据库中存储每个文件的权限，以反映任何用户都可以看到或修改哪些文件。

参考资料

grok_system_design_interview.pdf