怎么把脱机的打印机变为联机（打印机不能打印怎样联机）

要求

我们来设计一个文件托管服务，比如Dropbox或者Google Drive。云存储允许用户将数据存储在远程服务器上。通常，这些服务器由云存储提供商维护，并通过网络(通常是互联网)提供给用户。用户每月为云数据存储付费。类似服务:OneDrive、Google Drive

难度级别:中等

1.为什么是云存储？

云存储服务最近变得非常流行，因为它们简化了多个设备之间数字资源的存储和交换。从使用单台个人电脑到使用多台不同平台、不同操作系统的设备，如智能手机、平板电脑，每一台都可以随时从不同的地理位置访问，这被认为是云存储服务大受欢迎的原因。以下是此类服务的一些主要优势:

可用性:云存储服务的座右铭是随时随地提供数据可用性。用户可以随时随地从任何设备访问他们的文件/照片。

可靠性和耐用性:云存储的另一个好处是它提供了100%的数据可靠性和耐用性。云存储通过在不同地理位置的服务器上存储多个数据副本，确保用户永远不会丢失数据。

可扩展性:用户永远不必担心存储空间不足。有了云存储，只要你愿意付费，就可以拥有无限的存储空间。

如果您以前没有使用过dropbox.com，强烈建议在那里创建一个帐户，上传/编辑一个文件，并查看其服务提供的不同选项。这将有助于你理解该文章内容的知识点。

你应该在面试开始时明确要求。一定要问问题，找出面试官心目中的系统的确切范围

我们希望通过云存储系统实现什么？以下是我们系统的顶级要求：

1.用户应该能够从任何设备上传和下载他们的文件/照片。

2.用户应该能够与其他用户共享文件或文件夹。

3.我们的服务应该支持设备之间的自动同步，即在更新文件之后在一个设备上，它应该在所有设备上同步。

4.系统应支持存储高达GB的大型文件。

5.ACID是必需的。所有文件操作的原子性、一致性、隔离性和持久性应该得到保证。

6.我们的系统应该支持离线编辑。用户应能够在以下情况下添加/删除/修改文件：脱机，并且一旦联机，所有更改都应同步到远程服务器和其他联机设备。

扩展要求

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

3.一些设计考虑

我们应该有巨大的阅读和写作能力。

预期读写比几乎相同。

在内部，文件可以存储在小的部分或块中(如4mb)；这可以提供许多信息优势，即所有失败的操作只能针对文件的一小部分重试。如果用户上传文件失败，将只重试失败的块。

我们可以通过仅传输更新的数据块来减少数据交换量。

通过删除重复数据块，我们可以节省存储空间和带宽。

保存元数据的本地副本(文件名、大小等)。)可以节省我们往返服务器的大量时间。

对于小的变化，客户端可以智能上传差异，而不是整个数据块，即增量上传。

•假设我们有5亿总用户和1亿每日活动用户（DAU）。

•假设每个用户平均从三个不同的设备连接。

•平均而言，如果用户拥有200个文件/照片，我们将拥有1000亿个文件。

•假设平均文件大小为100KB，这将为我们提供10 PB的总存储空间。

100B*100KB=>10PB

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

5.高级设计

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

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

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

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

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

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

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

1.上传和下载文件。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.Chunks

2.文件夹

3.使用者

4.装置

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

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

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

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

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

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

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

7.文档处理工作流

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

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

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

3.客户甲确认后，向客户乙和客户丙发送变更通知。客户端B和C接收元数据更改并下载更新的块。

8.重复数据删除

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

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

A.后处理重复数据消除

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

在线重复数据消除

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

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

1.垂直分区：

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

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

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

2.基于范围的分区：

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

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

3.基于散列的分区：

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

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

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

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

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

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

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

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

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

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

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

grok_system_design_interview.pdf