系统设计::设计谷歌硬盘

设计谷歌硬盘

近年来，Google Drive、Dropbox、微软 OneDrive 和苹果 iCloud 等云存储服务已经变得非常流行。在本章中，你被要求设计 Google Drive。

在进入设计之前，让我们花点时间来了解一下 Google Drive。Google Drive 是一个文件存储和同步服务，帮助你在云端存储文档、照片、视频和其他文件。你可以从任何电脑、智能手机和平板电脑访问你的文件。你可以轻松地与朋友、家人和同事分享这些文件[1]。图 15-1 和 15-2 分别显示了谷歌硬盘在浏览器和移动应用程序上的样子。

理解问题并确定设计范围

设计谷歌硬盘是一个大项目，因此，提出问题以缩小范围是很重要的。

应聘者：最重要的功能是什么？
面试官：上传和下载文件，文件同步，以及通知。
应聘者：这是一个移动应用，一个网络应用，还是两者都有？
面试官：都是。
应聘者：支持的文件格式有哪些？
面试官：任何文件类型。
应聘者：文件是否需要加密？
面试官：是的。是的，存储中的文件必须是加密的。
应聘者：文件大小有限制吗？
面试官：有，文件必须是 10GB 或更小。
应聘者：该产品有多少用户？
面试官：10M DAU。

在本章中，我们将重点介绍以下功能。

  • 添加文件。添加文件的最简单方法是将文件拖放到 Google Drive 中。
  • 下载文件。
  • 在多个设备上同步文件。当一个文件被添加到一个设备上时，它将自动同步到其他设备。
  • 查看文件修订情况。
  • 与你的朋友、家人和同事分享文件
  • 当一个文件被编辑、删除或与你分享时，发送通知。本章未讨论的功能包括。
  • 谷歌文档的编辑和协作。Google doc 允许多个人同时编辑同一个文件。这不在我们的设计范围之内。

除了澄清需求之外，了解非功能需求也很重要。

  • 可靠性。可靠性对于一个存储系统是极其重要的。数据丢失是不可接受的。
  • 快速的同步速度。如果文件同步需要太多时间，用户会变得不耐烦并放弃该产品。
  • 带宽使用。如果一个产品需要大量不必要的网络带宽，用户就会不高兴，特别是当他们使用移动数据计划时。
  • 可扩展性。系统应该能够处理大量的流量。
  • 高可用性。当一些服务器离线、速度减慢或出现意外的网络错误时，用户仍应能使用该系统。

粗略估计

  • 假设该应用程序有 5000 万注册用户和 1000 万 DAU。
  • 用户得到 10GB 的免费空间。
  • 假设用户每天上传 2 个文件。平均文件大小为 500KB。
  • 读写比为 1:1。
  • 分配的总空间。5000 万 * 10 GB = 500 Petabyte
  • 上传 API 的 QPS：1000 万 * 2
  • 峰值 QPS = QPS * 2 = 480

提出高水平的设计并获得认同

我们不从一开始就展示高层次的设计图，而是采用一种稍微不同的方法。我们将从简单的东西开始：在一个单一的服务器中建立所有的东西。然后，逐渐扩大规模，支持数百万用户。通过做这个练习，它将刷新你对书中涉及的一些重要话题的记忆。

让我们从下面列出的单一服务器设置开始。

  • 一个网络服务器，用于上传和下载文件。
  • 一个数据库，用于跟踪元数据，如用户数据、登录信息、文件信息等。
  • 一个存储系统来存储文件。我们分配了 1TB 的存储空间来存储文件。

我们花了几个小时建立一个 Apache 网络服务器，一个 MySql 数据库，以及一个名为 drive/的目录作为根目录来存储上传的文件。在 drive/目录下，有一个目录列表，被称为命名空间。每个命名空间包含该用户的所有上传文件。服务器上的文件名与原始文件名保持一致。每个文件或文件夹都可以通过加入命名空间和相对路径来唯一地识别。

图 15-3 显示了/drive 目录在左边的样子和它在右边的扩展视图的一个例子。

APIs

API 是什么样子的？我们主要需要 3 个 API：上传文件、下载文件和获得文件修订。

  1. 上传一个文件到 Google Drive 支持两种类型的上传。

  • 简单上传。当文件大小较小时，使用这种上传类型。

  • 可恢复上传。当文件大小较多，而且网络中断的可能性很大时，使用这种上传类型。

下面是一个可恢复上传 API 的例子： https://api.example.com/files/upload?uploadType=resumable

参数。

  • uploadType=resumable
  • 数据。要上传的本地文件。

一个可恢复的上传是通过以下 3 个步骤实现的[2]。

  • 发送初始请求以检索可恢复的 URL。
  • 上传数据并监控上传状态。
  • 如果上传受到干扰，恢复上传。
  1. 从 Google Drive 下载一个文件

示例 API：https://api.example.com/files/download Params:

  • path: 下载文件的路径。

例子参数。

{
  "path": "/recipes/soup/best_soup.txt"
}
  1. 获取文件修订版

示例 API：https://api.example.com/files/list_revisions

  • Params:
    • path。你想获得修订历史的文件的路径。
    • limit：要返回的最大修订数。

例子参数。

{
  "path": "/recipes/soup/best_soup.txt",
  "limit": 20
}

所有的 API 都需要用户认证并使用 HTTPS。安全套接字层（SSL）保护客户端和后端服务器之间的数据传输。

脱离单一服务器

随着更多的文件被上传，最终你会得到空间满了的提示，如图 15-4 所示。

只剩下 10MB 的存储空间了! 这是一个紧急情况，因为用户无法再上传文件。我想到的第一个解决方案是将数据分片，因此它被存储在多个存储服务器上。图 15-5 显示了一个基于 user_id 的分片的例子。

你通宵达旦地设置了数据库分片，并密切监控。一切又顺利地运行了。你已经阻止了火灾的发生，但你仍然担心在存储服务器中断的情况下可能出现的数据损失。你四处打听，你的后台大师朋友弗兰克告诉你，许多领先的公司如 Netflix 和 Airbnb 都使用 Amazon S3 进行存储。“亚马逊简单存储服务（Amazon S3）是一种对象存储服务，提供行业领先的可扩展性、数据可用性、安全性和性能” [3]。你决定做一些研究，看看它是否合适。

经过大量的阅读，你对 S3 存储系统有了很好的了解，决定将文件存储在 S3 中。Amazon S3 支持同区域和跨区域的复制。一个区域是指亚马逊网络服务（AWS）拥有数据中心的地理区域。如图 15-6 所示，数据可以在同区域（左侧）和跨区域（右侧）进行复制。冗余文件存储在多个区域，以防范数据丢失并确保可用性。一个桶就像文件系统中的一个文件夹。

把文件放到 S3 后，你终于可以睡个好觉了，不用担心数据丢失。为了阻止类似的问题在未来发生，你决定对可以改进的地方做进一步研究。以下是你发现的几个方面。

  • 负载平衡器。添加一个负载平衡器来分配网络流量。负载平衡器确保流量的均匀分布，如果一个网络服务器发生故障，它将重新分配流量。
  • 网络服务器。在添加了负载平衡器后，可以根据流量负载，轻松添加/删除更多的网络服务器。
  • 元数据数据库。将数据库移出服务器以避免单点故障。同时，设置数据复制和分片，以满足可用性和可扩展性要求。
  • 文件存储。Amazon S3 用于文件存储。为了确保可用性和耐久性，文件被复制在两个独立的地理区域。

在应用了上述改进后，你已经成功地将 Web 服务器、元数据数据库和文件存储从一台服务器上解耦。更新后的设计如图 15-7 所示。

同步冲突

对于像 Google Drive 这样的大型存储系统，同步冲突时有发生。当两个用户同时修改同一个文件或文件夹时，就会发生冲突。我们如何解决这个冲突呢？这里是我们的策略：第一个被处理的版本获胜，而后来被处理的版本则收到冲突。图 15-8 显示了一个同步冲突的例子。

在图 15-8 中，用户 1 和用户 2 试图同时更新同一个文件，但用户 1 的文件被我们的系统首先处理。用户 1 的更新操作通过了，但是，用户 2 得到一个同步冲突。我们怎样才能解决用户 2 的冲突呢？我们的系统展示了同一个文件的两个副本：用户 2 的本地副本和服务器上的最新版本（图 15-9）。用户 2 可以选择合并这两个文件，或者用另一个版本覆盖一个版本。

当多个用户同时编辑同一个文件时，要保持文件的同步性是很有挑战性的。有兴趣的读者请参考参考资料[4] [5]。

高层设计

图 15-10 说明了拟议的高层设计。让我们来看看系统的每个组成部分。

  • 用户。用户通过浏览器或移动应用程序使用该应用程序。
  • 块服务器。块服务器将区块上传到云存储。块存储，被称为块级存储，是一种在基于云的环境中存储数据文件的技术。一个文件可以分成几个块，每个块都有一个独特的哈希值，存储在我们的元数据数据库中。每个区块被视为一个独立的对象，并存储在我们的存储系统（S3）中。为了重建一个文件，块以特定的顺序被连接。至于块的大小，我们使用 Dropbox 作为参考：它将块的最大大小设置为 4MB[6]。
  • 云存储。一个文件被分割成更小的块并存储在云存储中。
  • 冷存储。冷存储是为存储非活动数据而设计的计算机系统，这意味着文件在很长一段时间内不会被访问。
  • 负载平衡器。负载平衡器在 API 服务器之间均匀地分配请求。
  • API 服务器。这些服务器几乎负责除上传流程以外的所有工作。API 服务器用于用户认证、管理用户资料、更新文件元数据等。
  • 元数据数据库。它存储用户、文件、块、版本等的元数据。请注意，文件被存储在云端，元数据数据库只包含元数据。
  • 元数据缓存。一些元数据被缓存起来，以便快速检索。
  • 通知服务。它是一个发布者/订阅者系统，允许数据在某些事件发生时从通知服务传输到客户端。在我们的具体案例中，当一个文件在其他地方被添加/编辑/删除时，通知服务会通知相关客户，这样他们就可以拉到最新的变化。
  • 离线备份队列。如果客户处于离线状态，无法提取最新的文件变化，离线备份队列会存储信息，这样当客户在线时，变化会被同步。

我们已经在高层讨论了 Google Drive 的设计。有些组件很复杂，值得仔细研究；我们将在深入研究中详细讨论这些组件。

设计深究

在本节中，我们将仔细研究以下内容：块服务器、元数据数据库、上传流程、下载流程、通知服务、保存存储空间和故障处理。

块服务器

对于定期更新的大文件，每次更新时发送整个文件会消耗大量的带宽。提出了两个优化方案，以尽量减少传输的网络流量。

  • Delta 同步。当一个文件被修改时，只有被修改的块被同步，而不是使用同步算法的整个文件 [7] [8]。
  • 压缩。对块进行压缩可以大大减少数据大小。因此，根据文件类型，使用压缩算法对块进行压缩。例如，gzip 和 bzip2 被用来压缩文本文件。压缩图像和视频则需要不同的压缩算法。

在我们的系统中，块服务器为上传文件做繁重的工作。块服务器通过将文件分割成区块，压缩每个区块，并对其进行加密，来处理从客户端传来的文件。与其将整个文件上传到存储系统，不如只传输经过修改的块。

图 15-11 显示了当一个新文件被添加时，块服务器是如何工作的。

  • 一个文件被分割成更小的块。
  • 每个区块都使用压缩算法进行压缩。
  • 为了确保安全，每个区块在被发送到云存储之前都要进行加密。
  • 块被上传到云存储。

图 15-12 说明了 delta 同步，意味着只有修改过的块被传输到云存储。突出显示的区块 “block 2 “和 “block 5 “代表改变的区块。使用 delta 同步，只有这两个块被上传到云存储中。

块服务器使我们能够通过提供 delta 同步和压缩来节省网络流量。

高一致性要求

我们的系统默认要求强一致性。一个文件在同一时间被不同的客户端显示出不同的内容，这是不可接受的。系统需要为元数据缓存和数据库层提供强一致性。

内存缓存默认采用最终一致性模型，这意味着不同的副本可能有不同的数据。为了实现强一致性，我们必须确保以下几点。

  • 缓存复制中的数据和主站是一致的。
  • 在数据库写入时使缓存无效，以确保缓存和数据库持有相同的值。在关系型数据库中实现强一致性很容易，因为它保持了 ACID（原子性、一致性、隔离性、持久性）属性[9]。然而，NoSQL 数据库默认不支持 ACID 属性。ACID 属性必须以编程方式纳入同步逻辑中。在我们的设计中，我们选择了关系型数据库，因为 ACID 是原生支持的。

元数据数据库

图 15-13 显示了数据库模式的设计。请注意这是一个高度简化的版本，因为它只包括最重要的表和有趣的字段。

  • 用户：用户表包含用户的基本信息，如用户名、电子邮件、个人照片等。
  • 设备。设备表存储设备信息。Push_id 用于发送和接收移动推送通知。请注意一个用户可以有多个设备。
  • 命名空间。命名空间是一个用户的根目录。
  • 文件：文件表存储所有与最新文件有关的信息。
  • File_version。它存储了一个文件的版本历史。现有的行是只读的，以保持文件修订历史的完整性。
  • 块：区块表存储所有与文件区块相关的内容。它存储与一个文件块有关的一切。任何版本的文件都可以通过以正确的顺序连接所有的块来重新构建。

上传流程

让我们讨论一下客户上传文件时发生了什么。为了更好地理解这个流程，我们画出如图 15-14 所示的顺序图。

在图 15-14 中，两个请求被平行发送：添加文件元数据和上传文件到云存储。这两个请求都来自客户端 1。

  • 添加文件元数据。
  1. 客户端 1 发送一个请求，添加新文件的元数据。
  2. 将新文件元数据存储在元数据数据库中，并将文件上传状态改为 “待定”。
  3. 通知通知服务，正在添加一个新文件。
  4. 通知服务通知相关的客户端（客户端 2）有文件正在被上传。
  • 上传文件到云存储。

2.1 客户端 1 将文件内容上传到块服务器。
2.2 块服务器将文件分块，对区块进行压缩、加密，并将其上传到云存储。
2.3 一旦文件被上传，云存储会触发上传完成回调。该请求被发送到 API 服务器。
2.4 在 Metadata DB 中，文件状态变为 “已上传”。
2.5 通知通知服务，文件状态变为 “上传”。
2.6 通知服务通知相关客户（客户 2），一个文件已完全上传。

当一个文件被编辑时，流程是类似的，所以我们将不重复它。

下载流程

当一个文件在其他地方被添加或编辑时，下载流程被触发。客户端如何知道一个文件是由另一个客户端添加或编辑的？有两种方法可以让客户端知道。

  • 如果客户端 A 在线，而文件被另一个客户端更改，通知服务会通知客户端 A，某处发生了变化，所以它需要调取最新的数据。- 如果客户端 A 处于离线状态，而另一个客户端更改了文件，数据将被保存到缓存中。当脱机的客户端再次上线时，它就会拉出最新的变化。

一旦客户端知道一个文件被改变，它首先通过 API 服务器请求元数据，然后下载块来构建文件。图 15-15 显示了详细的流程。注意，由于空间的限制，图中只显示了最重要的部分。

  1. 通知服务通知客户端 2，一个文件在其他地方被改变。
  2. 一旦客户端 2 知道有新的更新，它就会发送一个请求来获取元数据。
  3. API 服务器调用元数据 DB 来获取变化的元数据。
  4. 元数据被返回给 API 服务器。
  5. 客户端 2 获得元数据。
  6. 一旦客户端收到元数据，它就向块服务器发送请求，下载区块。
  7. 块服务器首先从云存储中下载区块。
  8. 云存储将区块返回给块服务器。
  9. 客户端 2 下载所有的新区块来重建文件。

通知服务

为了保持文件的一致性，任何在本地进行的文件突变都需要通知其他客户端以减少冲突。通知服务就是为这个目的而建立的。在高层，通知服务允许在事件发生时将数据传输给客户端。这里有几个选择。

  • 长时间轮询。Dropbox 使用长轮询[10]。
  • WebSocket。WebSocket 在客户端和服务器之间提供一个持久的连接。通信是双向的。

尽管这两个选项都很好用，但由于以下两个原因，我们选择了长轮询。

  • 通知服务的通信不是双向的。服务器向客户端发送有关文件变化的信息，但不是反过来。
  • WebSocket 适用于实时双向通信，如聊天应用程序。对于谷歌硬盘，通知的发送频率不高，没有突发数据。

通过长轮询，每个客户端与通知服务建立一个长轮询连接。如果检测到一个文件的变化，客户端将关闭长轮询连接。关闭连接意味着客户端必须连接到元数据服务器以下载最新的变化。在收到响应或达到连接超时后，客户端立即发送一个新的请求，以保持连接开放。

节省存储空间

为了支持文件版本历史并确保可靠性，同一文件的多个版本被存储在多个数据中心。如果频繁地备份所有文件的修订版，存储空间会很快被填满。提出了三种技术来减少存储成本。

  • 去除重复的数据块。在账户层面消除冗余块是节省空间的一个简单方法。如果两个块有相同的哈希值，那么它们就是相同的。
  • 采用智能数据备份策略。可以采用两种优化策略。
  • 设置一个限制：我们可以为存储的版本数量设置一个限制。如果达到限制，最旧的版本将被新的版本取代。
  • 只保留有价值的版本。有些文件可能经常被编辑。例如，为一个大量修改的文件保存每个编辑过的版本可能意味着该文件在短时间内被保存超过 1000 次。为了避免不必要的复制，我们可以限制保存版本的数量。我们对最近的版本给予更多的权重。实验有助于找出保存的最佳版本数。
  • 将不经常使用的数据移至冷库。冷数据是指几个月或几年都没有活动的数据。像亚马逊 S3 glacier[11]这样的冷存储要比 S3 便宜得多。

故障处理

大规模系统中可能会出现故障，我们必须采取设计策略来处理这些故障。你的面试官可能会有兴趣听到你如何处理以下系统故障的情况。

  • 负载平衡器故障。如果一个负载均衡器发生故障，次要的将成为活动的，并接过流量。负载平衡器通常使用心跳来监控对方，这是负载平衡器之间发送的定期信号。如果一个负载平衡器在一段时间内没有发送心跳信号，则被认为是失败。
  • 块服务器故障。如果一个块服务器发生故障，其他服务器就会接收未完成的或待处理的作业。
  • 云存储失败。S3 桶在不同地区被多次复制。如果文件在一个地区不可用，它们可以从不同的地区取回。
  • API 服务器故障。它是一个无状态的服务。如果一个 API 服务器失败，流量会被负载平衡器重定向到其他 API 服务器。
  • 元数据缓存失败。元数据缓存服务器是多次复制的。如果一个节点发生故障，你仍然可以访问其他节点来获取数据。我们会调出一个新的缓存服务器来替换故障的那个。
  • Metadata DB 故障。
  • 主站停机。如果主节点宕机，提升一个从属节点作为新的主节点，并带起一个新的从属节点。
  • 从机停机。如果一个从属服务器宕机，你可以使用另一个从属服务器进行读取操作，并带来另一个数据库服务器来替代故障的服务器。
  • 通知服务失败。每个在线用户都与通知服务器保持长期的轮询连接。

通知服务器的长期轮询连接。因此，每个通知服务器都与许多用户相连。根据 Dropbox 在 2012 年的谈话[6]，每台机器有超过 100 万个连接被打开。如果一台服务器发生故障，所有的长轮询连接都会丢失，因此客户必须重新连接到不同的服务器。即使一台服务器可以保持许多开放的连接，它也不能一次重新连接所有丢失的连接。与所有丢失的客户重新连接是一个相对缓慢的过程。

  • 离线备份队列故障。队列是多次复制的。如果一个队列发生故障，该队列的消费者可能需要重新订阅备份队列。

总结

在本章中，我们提出了一个支持 Google Drive 的系统设计。强一致性、低网络带宽和快速同步的结合使得这个设计很有意思。我们的设计包含两个流程：管理文件元数据和文件同步。通知服务是该系统的另一个重要组成部分。它使用长时间的轮询来让客户了解最新的文件变化。

像任何系统设计面试问题一样，没有完美的解决方案。每个公司都有其独特的限制，你必须设计一个系统来适应这些限制。了解你的设计和技术选择的权衡是很重要的。如果还有几分钟的时间，你可以谈谈不同的设计选择。

例如，我们可以从客户端直接向云存储上传文件，而不是通过块状服务器。这种方法的优点是，它使文件上传的速度更快，因为一个文件只需要传输一次到云存储。在我们的设计中，一个文件首先被传输到块服务器，然后再传输到云存储。然而，这种新方法有一些缺点。

  • 首先，同样的分块、压缩和加密逻辑必须在不同的平台（iOS、Android、Web）上实现。这很容易出错，需要大量的工程努力。在我们的设计中，所有这些逻辑都在一个集中的地方实现：块服务器。
  • 其次，由于客户端很容易被入侵或操纵，在客户端实现加密逻辑并不理想。

该系统的另一个有趣的演变是将在线/离线逻辑转移到一个单独的服务。让我们称它为存在感服务。通过将存在服务从通知服务器中移出，在线/离线功能可以很容易地被其他服务所整合。

祝贺你走到了这一步! 现在给自己拍拍屁股吧。干得好!

参考资料

[1]Google Drive
[2]Upload file data
[3]Amazon S3
[4]Differential Synchronizatio
[5]Differential Synchronization youtube tal
[6]How We’ve Scaled Dropbox
[7] Tridgell, A., & Mackerras, P. (1996). The rsync algorithm.
[8]Librsync. (n.d.). Retrieved April 18, 2015, fro
[9]ACID
[10]Dropbox security white paper
[11]Amazon S3 Glacier