设计Google Drive

近年来，谷歌网盘、Dropbox、微软One driveh和苹果iCoud等云存储服务变得非常流行。在本章中，您被要求设计google drive。

在开始设计前，让我们花点时间了解一下Google Drive。Google Drive是一项文件存储和同步服务，可以帮助您在云中存储文档、照片和其他文件。您可以从任何电脑、智能手机和平板电脑中访问您的文件。下面两张图分别展示了Google Drive在浏览器和手机app上的外观：

在本章中我们会重点介绍以下功能：

• 添加文件：最简单的添加文件方式就是把文件拖到Google Drive里
• 同步文件：当文件添加到一个设备时，它会同步到另一个文件
• 共享文件：文件可以通过链接、二维码等方式分享给其他人
• 通知：当文件被编辑、删除或共享时，发送通知

Step1：Understand the problem and establish design scope

对于”设计Google Drive“这个系统设计话题，我们可以向面试官提出以下问题：

• Q：最重要的功能是什么？

  A：上传和下载文件、文件同步和通知。

• Q：我们要设计的是手机app还是web网页，还是二者兼而有之？

  A：二者都有

• Q：支持那些文件格式？

  A：任何文件类型

• Q：文件需要加密么？

  A：是的，存储的文件必须加密

• Q：有文件大小限制么？

  A： 单个文件暂时不设置大小限制，但总存储容量初始默认为10GB

• Q： 这个产品的日活跃度是多少？

  A： 1000W日活跃用户

Step2：Propose high-level design and get buy-in

这一章中，我们不一开始就展示high-level design设计图。我们先从简单的设计出发—在单个服务器中构建所有内容，然后再逐步扩大规模以支持数百万用户。通过做这个练习，它将帮你回忆起书中涉及的一些重要主题的内容。

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

• 用于上传和下载文件的网络服务器
• 一个数据库，用于跟踪元数据，如用户数据，登录信息、文件信息等
• 用于存储文件的存储系统，我们分配1TB的存储空间
• 我们花了几个小时设置一个apache web服务器、一个mysql数据库和一个名为drive的目录作为根目录来存储上传的文件。在drive目录下，有一个目录列表，称为namespace。每个namespace都包含该用户的所有上传文件。服务器上的文件名与原始文件名保持不变。每个文件或文件夹，都可以通过链接namespace和相对路径进行唯一标识。

下图展示了drive目录的示例，左侧按用户划分namespace，右侧是目录的展开图：

API

我们需要三个api：upload file, download file, get file revisions

Upload file

我们需要支持两种类型的文件上传：

1. Simple upload(简单上传)：当文件很小时，我们直接使用简单的上传
2. resumable upload(断点续传)：当文件大小很大时，上传需要花费较长时间，网络中断的可能性较高

Download file

下载需要记录下载路径

Get file revisions

记录文件的历史版本，版本有最大保留次数，超过该限制的版本不再保存。

上述所有api都需要用户身份验证并使用https通信。安全套接字保护客户端和后端服务器之间的数据传输。

Move away from single server

随着上传的文件越来越多，单个服务器满足不了存储需求。

我们想到的第一个解决方案时对数据进行分片，以便将数据存储在多个存储服务器上。下图显示了一个基于user_id的分片示例：

数据库分片是一种可行的存储方案，但是仍然有存储服务器中断的情况下丢失数据的风险。许多领先的公司都使用Amazon S3是一个对象存储服务，提供业界领先的可扩展性、数据可用性、安全性和高性能。

Amazon S3支持同区域和跨区域复制。区域是指亚马逊网络服务拥有数据中心的地理区域。如下图所示：

可以在同区域(左侧)和跨区域(右侧)复制数据。冗余文件存储在多个区域中，以防止数据丢失并确保可用性。bucket就像文件系统中的文件夹。

添加了文件存储后，你可以添加负载均衡器、web服务器、元数据数据库来继续升级，这些东西在之前的章节中已经详细介绍了，这里就不详细展开，扩展后的high-level design如下图所示：

sync confilct

对于像google drive这样的大型存储系统，同步冲突时有发生。当两个用户同时修改一个文件或文件夹时，会发生冲突。那么如何解决同步冲突呢？这是我们的策略，第一个处理的版本获胜，稍后处理的版本会收到冲突。下图显示了一个同步冲突的示例：

在上图中，用户1和用户2试图同时更新同一个文件，但用户1的文件首先由我们的系统处理，用户1的更新操作完成，但是用户2遇到同步冲突。我们如何解决用户2的冲突？我们的系统提供同一个文件的两个副本：用户2的本地副本和服务器的最新版本。用户2可以选择合并两个文件或用另一个版本替换上一个版本。

high-level design

下图展示了当前的high-level design设计图：

• User: 用户通过浏览器或移动应用城西使用该google drive
• Block servers：区块服务器将区块上传到云服务器。一个文件可以分为几个块，每个块都有唯一的哈希值，存储在元数据库中
• Cloud Storage：云存储，文件被划分为块，存储在云服务中
• Cold Storage：冷存储是一种用于存储非活跃数据的计算机系统，这意味着文件在很长一段时间内不会被访问。
• Load balancer：负载均衡器
• API server：API服务器负责处理非常多的常规请求
• Metadata database： 元数据库，存储用户，文件，块，版本等元数据。
• Metadata cache：为了快速检索，缓存了一些元数据
• Notification service：它是一个发布者、订阅者系统，允许在某些事件发生时推送通知。在Google drive中，当发生添加、编辑、删除文件时，通知服务会通知相关用户
• Offline backup queue：如果客户端脱机导致无法拉取最新修改，则该队列会存储信息，以便在客户端联机时同步更改

有些组件很复杂，我们将在Step3中详细讨论这些问题。

Step3：Design deep dive

在本节中，我们将仔细探讨以下内容：block servers，meta database，upload flow，download flow, notification service, save storage space.

Block servers

对于定期更新的大文件，每次更新时发送整个文件会消耗大量带宽。，这里提出了两种优化方案，可以最大限度地减少正在传输的网络流量：

• 增量同步：当修改文件时，使用同步算法。只同步跟新修改后的块，而不是整个文件。
• 压缩：对块应用压缩可以显著减少数据大小。不同的文件类型需要使用不同的压缩算法，例如，gzip和bzip2用于压缩文本文件。

因此，在我们的系统中，我们设计了块服务器为上传文件做繁重的工作。块服务器通过将文件拆分为块、压缩每个块来处理从客户端上传的文件，如下图所示：

下图显示了增量同步，这意味着只有修改后的块才能传输到云存储。高亮显示的块表示已更改的块，只有这两个块被上传到云存储：

High consistency requirement

默认情况下，我们的系统需要强一致性：不同客户端从云上拉取的数据必须要保证相同。

因此，该系统需要为元数据缓存和数据库层提供强一致性。默认情况下，内存缓存采用最终一致性模型，这意味着不同的副本可能具有不同的数据，为了实现强大的一致性，我们必须确保以下几点：

• 缓存副本和主机中的数据时一致的
• 在数据库写入时使缓存无效，以确保缓存和数据库保存相同的值。在关系数据库中实现强一致性很容易，因为它维护ACID(原子性、一致性、隔离性、持久性)。但是默认情况下，NoSQL不支持ACID属性。因此在我们的设计中，我们选择关系型数据库。

Meta database

下图展示了数据库架构设计。请注意，这只是一个高度简化的版本，因为它只包含最重要的表和关键字段。

Download flow

在其他地方添加或编辑文件时，将触发下载流程：

如果客户端A在另一个客户端更改文件时处于联机状态，则通知服务将通知客户端A“在某处进行了更改，需要拉取最新云端数据”。如果客户端A脱机，另一个客户端更改了文件，则数据将保存在缓存中，等到联机时再同步。

一旦客户端知道文件已更改，它首先通过API服务器请求元数据，然后下载块来构建文件。下图显示了详细流程，由于空间限制，图中仅显示了最重要的组件：

• 通知服务通知客户端，某个文件在其他地方发生了更改
• 一旦客户端知道了有新的更新可用，它就发送获取元数据更新的请求
• API服务器调用元数据D来获取变更的元数据
• 元数据返回API服务器
• 客户端获取元数据
• 一旦客户端接收到元数据，它就向块服务器发送下载块的请求
• 云存储将块返回到块服务器
• 客户端重新下载所有新的块来重构文件

Notification service

为了保持文件一致性，本地执行的任何文件冲突都要通知其他客户端，以减少冲突，通知服务就是为了这个目的而构建的。

在上一章中，通知服务允许在事件发生时将数据将传输到客户端。以下时一些选项：

• 长时间轮询， Dropbox是用长时间轮询机制来发送通知
• Web Socket。WebSocket 提供双向持久连接

虽然这里两种都可以，但是因为双向持久连接会占用服务器资源，而且这种通知服务没有像聊天服务那样高频，因此长时间轮询显然时更佳的选择。

Save storage space

为了支持文件版本历史记录并确保可靠性，同一文件的多个版本存储在多个数据中心中。频繁备份文件的多个版本会快速占用服务器的存储空间，这里提出了三种降低存储成本的技术：

• 消除重复数据块：MD5哈希值来鉴别重复数据块
• 采用智能数据备份策略：设置存储版本数量限制或只保留有价值的版本
• 将不常用的数据转移到冷库

Failure Handling

这里的内容都是无意义的重复内容，就不翻译了

Step4：Warm up

如果还有几分钟时间，你可以谈谈不同的设计选择，例如：

• 首先，我们可以从客户端直接将文件上传到云存储，而不是通过块服务器间接上传
• 客户端由于很容易被黑客入侵，因此在客户端实现存储加密并不理想，转移到服务器加密该怎么做？

祝贺你完成了所有章节的学习，Good job!