CHAPTER 15: 《DESIGN GOOGLE DRIVE》第15章:《设计谷歌驱动器》

近年来，云存储服务如谷歌Drive、Dropbox、Microsoft OneDrive、苹果的iCloud已经变得非常流行。在本章中，你需要设计谷歌开车。

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

步骤1 -了解问题并建立设计范围

设计一个谷歌驱动器是一个大项目，因此提出问题以缩小范围是很重要的的范围。
候选人:最重要的特征是什么?
面试官:上传和下载文件，文件同步和通知。
候选人:这是一个移动应用程序，还是一个web应用程序，还是两者兼有?
面试官:这两个。
候选人:支持的文件格式是什么?
面试官:任何文件类型。
候选人:文件需要加密吗?
面试官:是的，存储中的文件必须加密。
候选人:是否有文件大小限制?
面试官:可以，文件必须小于等于10gb。
候选人:这个产品有多少用户?
面试官:1000万DAU。

本章主要关注以下几个特性。

• 添加文件。添加文件的最简单方法是将文件拖放到谷歌驱动器中。
• 下载文件。
• 跨多个设备同步文件。当一个文件被添加到一个设备时，它是自动的已同步到其他设备。
• 请参阅文件修订。
• 与你的朋友、家人和同事分享文件
• 当文件被编辑、删除或与您共享时，发送通知。

本章不讨论的特性包括:

• 谷歌文档编辑和协作。谷歌文档允许多人编辑同时保存同一份文件。这超出了我们的设计范围。除了明确需求，理解非功能性需求也很重要。
• 可靠性。可靠性对于存储系统来说至关重要。数据丢失为不可接受的。
• 同步速度快。如果文件同步花费太多时间，用户会变得不耐烦放弃产品。
• 带宽占用率;如果一个产品占用了大量不必要的网络带宽，用户就会不开心，尤其是当他们使用移动数据套餐时。
• 可伸缩性。该系统应该能够处理高流量。
• 高可用性。当某些服务器可以使用系统时，用户应该仍然能够使用系统脱机、变慢或出现意外的网络错误。

后面的包络估计

• 假设该应用拥有5000万注册用户和1000万DAU。用户有10 GB的空闲空间。
• 假设用户每天上传2个文件。平均文件大小为500kb。
• 1:1的读写比例。
• 分配的总空间:5000万* 10 GB = 500 pb
• 上传API的QPS: 1000万* 2次上传/ 24小时/ 3600秒= ~ 240
• 峰值QPS = QPS * 2 = 480

第二步——提出高层次的设计，并获得认可

我们不从一开始就显示高级设计图，而是使用一个稍微不同的方法。我们将从简单的事情开始:在单个服务器中构建所有内容。然后，逐渐扩展到支持数百万用户。通过这个练习，它会刷新你对书中一些重要主题的记忆。
让我们从单个服务器设置开始，如下所示:

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

我们花了几个小时设置了一个Apache web服务器，一个MySql数据库和一个目录名为drive/的根目录，用于存放上传的文件。在驱动器/目录下，有一个列表目录的名称，称为命名空间。每个命名空间都包含上传的所有文件用户。服务器上的文件名与原始文件名保持一致。每个文件或文件夹可以通过连接命名空间和相对路径来唯一标识。
图15-3展示了左侧的/drive目录及其目录的样子右侧展开视图。

api
api是什么样的?我们主要需要3个api:上传文件，下载文件和获取文件修订。

1. 上传文件到谷歌驱动器
   支持两种类型的上传:
   • 简单上传。当文件较小时，请使用此上传类型。
   • 可恢复上传。当文件大小较大且有很高时，请使用此上传类型网络中断的机会。

下面是一个resume upload API的例子:
https://api.example.com/files/upload?uploadType=resumable
Params:

• uploadType=resumable
• data: Local file to be uploaded.

可恢复上传通过以下3个步骤实现[2]:
- 发送初始请求，获取可恢复的URL。
- 上传数据并监控上传状态。
- 如果上传受到干扰，请恢复上传。

2. 从谷歌驱动器下载文件
   Example API: https://api.example.com/files/download
   Params:
   ? path: download file path.
   Example params:
   {
   “path”: “/recipes/soup/best_soup.txt”
   }
3. 获取文件修订
   Example API: https://api.example.com/files/list_revisions
   Params:
   ? path: The path to the file you want to get the revision history.
   ? limit: The maximum number of revisions to return.
   Example params:
   {
   “path”: “/recipes/soup/best_soup.txt”,
   “limit”: 20
   }
   所有api都需要用户身份验证并使用HTTPS。安全套接层(SSL)保护客户端与后端服务器之间的数据传输。
   远离单服务器
   随着上传的文件越来越多，最终你会看到如图15-4所示的空格满警告框。
   
   只剩下10mb的存储空间!用户无法上传文件，属于紧急情况了。第一个解决方案是对数据进行分片，这样数据就可以存储在多个地方存储服务器。图15-5展示了一个基于user_id的分区示例。
   

你花了一整夜的时间来设置数据库分片并密切监控它。一切工作又顺利。您已经停止了火灾，但您仍然担心潜在的数据存储服务器中断造成的损失。你四处打听，还有你的后台专家朋友弗兰克我说过，Netflix和Airbnb等许多领先公司都使用Amazon S3进行存储。Amazon S3 (Amazon Simple Storage Service)是一种提供对象存储服务的服务业界领先的可扩展性、数据可用性、安全性和性能。你决定
做一些调查，看看它是否合适。

在大量阅读之后，您可以很好地理解S3存储系统并决定使用在S3中存储文件。Amazon S3支持同区域和跨区域复制。一个区域是亚马逊网络服务(AWS)数据中心所在的地理区域。如图所示15-6、数据可以复制在同一区域(左边)和跨区域(右边)。冗余文件存储在多个区域，以防止数据丢失和保证可用性。存储桶类似于文件系统中的文件夹。

将文件放入S3后，您终于可以放心地睡个好觉了数据损失。为了防止类似的问题在将来再次发生，你决定做更多的事情研究一下你可以改进的地方。以下是你会发现的几个方面:

• 负载均衡器:通过添加负载均衡器，实现网络流量的分流。负载均衡器可以确保均匀分布的流量，如果web服务器宕机，它将重新分配流量。
• Web服务器:添加负载均衡器后，可以添加/移除更多的Web服务器很容易，这取决于交通负载。
• 元数据库:将数据库移出服务器，以避免单点故障。同时，设置数据复制和分片以满足可用性和可扩展性要求。
• 文件存储:使用Amazon S3存储文件。为了确保可用性和持久性，文件复制在两个独立的地理区域中。

应用上述改进后，您已经成功解耦了web服务器，元数据数据库，以及来自单个服务器的文件存储。更新后的设计显示在图15-7。

同步冲突
对于像谷歌驱动器这样的大型存储系统，同步冲突时有发生。当两个用户同时修改同一个文件或文件夹，产生冲突。我们怎么能解决冲突?这是我们的策略:第一个被处理的版本获胜，而稍后处理的版本会收到冲突。图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服务器用于用户身份验证、管理用户配置文件、更新文件元数据等。
元数据数据库:存储用户、文件、块、版本等的元数据。请注意文件存储在云端，元数据数据库只包含元数据。
元数据缓存:缓存一些元数据以快速检索。
通知服务:它是一个允许数据传输的发布者/订阅者系统当某些事件发生时，从通知服务到客户端。在我们的具体例子中，通知当在其他地方添加/编辑/删除文件时，服务通知相关客户端，以便他们可以拉取最新的更改。
离线备份队列:如果客户端处于离线状态，无法拉取最新的文件更改，则离线备份队列存储信息，以便在客户端在线时同步更改。从高层讨论了谷歌驱动的设计。有些组件是复杂的，值得仔细检查的;我们将在深入讨论中详细讨论这些。

步骤3 -深入设计

在本节中，我们将仔细研究以下内容:块服务器、元数据数据库、上传流程，下载流程，通知服务，节省存储空间和故障处理。
块服务器
对于定期更新的大文件，在每次更新时发送整个文件需要消耗a大量的带宽。提出了两种优化方法来最小化网络流量传播:

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

在我们的系统中，块服务器完成了上传文件的繁重工作。块服务器处理来自客户端的文件，方法是将文件分割成块，压缩每个块，然后加密。不需要上传整个文件到存储系统，只需要修改即可传输块。

图15-11展示了添加新文件时块服务器的工作方式。

• 文件被分割为更小的块。
• 使用压缩算法对每个块进行压缩。
• 为了保证安全性，每个数据块在上传到云存储前都会被加密。
• 将数据块上传到云存储。

图15-12展示了增量同步，这意味着只有被修改的块才会被传输到云端存储。高亮显示的区块“区块2”和“区块5”代表更改的区块。使用δ同步时，只有这两个块被上传到云存储。

块服务器通过提供增量同步和压缩来节省网络流量。
高一致性要求
我们的系统默认要求强一致性。文件被展示是不可接受的由不同的客户同时提供不同的服务。系统需要提供强有力的支持元数据缓存和数据库层的一致性。

内存缓存默认采用最终一致性模型，这意味着不同副本可能具有不同的数据。要实现强一致性，就必须保证后:

• cache副本与主节点的数据保持一致。
• 在数据库写入时使缓存失效，以确保缓存和数据库保存相同的值。

在关系数据库中实现强一致性很容易，因为它维护了ACID(原子性、一致性、隔离性、持久性)属性然而，NoSQL数据库可以默认不支持ACID属性。ACID属性必须以编程方式实现合并到同步逻辑中。在我们的设计中，我们选择关系型数据库是因为酸是原生支持的。
元数据数据库
如图15-13所示。请注意，这是高度简化的版本，因为它只包含最重要的表和有趣的字段。

User: User表包含用户的基本信息，如用户名、email、头像照片等。
Device: Device table用于存储设备信息。Push_id用于发送和接收mobile推送通知。请注意，一个用户可以有多个设备。
命名空间:命名空间是用户的根目录。
文件:文件表存储与最新文件相关的所有内容。
File_version:存储文件的版本历史。现有的行是只读的文件修订历史的完整性。
块(Block):存储与文件块相关的所有内容。任何版本的文件都可以被重建
通过按正确的顺序连接所有块。
上传流量
我们来讨论一下客户端上传文件时会发生什么。为了更好地理解流程，我们请绘制如图15-14所示的时序图。

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

1. 客户端1发送一个请求来添加新文件的元数据。
2. 将新创建的文件元数据存储到元数据数据库中，并将文件上传状态修改为
   “等待”。
3. 通知通知服务有新文件添加。
4. 通知服务通知相关的客户端(客户端2)有一个文件正在运行上传。

• 上传文件到云存储。
  2.1客户端1上传文件内容到块服务器。
  2.2块服务器将文件分块，压缩、加密和将它们上传到云存储。
  2.3文件上传完成后，云存储触发上传完成回调。的请求被发送到API服务器。
  2.4元数据数据库中文件状态变为“已上传”。
  2.5通知通知服务文件状态为“已上传”。
  2.6通知服务通知相关客户端(客户端2)某个文件已用完上传。
  在编辑文件时，流程是类似的，所以我们不会重复。
  下载流量
  当在其他地方添加或编辑文件时，将触发下载流。客户是怎么知道的如果文件是由另一个客户端添加或编辑的?有两种方法可以让客户端知道:
• 如果客户A在线，而某个文件被另一个客户端更改，通知服务将会通知客户端A某处发生了变化，需要获取最新的数据。
• 如果客户端A离线，而另一个客户端修改文件时，数据将被保存到缓存。当离线客户端再次上线时，它会拉取最新的更改。

一旦客户端知道文件被修改，它首先通过API服务器请求元数据，然后下载块来构造文件。具体流程如图15-15所示。注意，只有由于空间限制，大多数重要的组件都显示在图中。

1. 通知服务通知客户端2某个文件在其他地方发生了更改。
2. 一旦客户端2知道有新的更新可用，它就会发送一个获取元数据的请求。
3. API服务器调用元数据数据库(metadata DB)来获取更改的元数据。
4. 元数据返回到API服务器。
5. 客户端2获取元数据。
6. 一旦客户端收到元数据，它就会发送请求阻止服务器下载
   块。
7. 块服务器首先从云存储下载块。
8. 云存储向块服务器返回块。
9. 客户端2下载所有新的块来重建文件。

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

• 长轮询。Dropbox使用长轮询[10]。
• WebSocket。WebSocket提供了客户端和服务器。沟通是双向的。

尽管这两种方式都能很好地工作，但我们选择长轮询的原因如下。

• 通知服务的通信不是双向的。服务器发送关于客户端文件更改的信息，但反之则不然。
• WebSocket适合实时双向通信，如聊天应用谷歌驱动器，通知发送不频繁，没有突发数据。

使用长轮询时，每个客户端都建立到通知服务的长轮询连接。如果当检测到对文件的更改时，客户端将关闭长轮询连接。关闭连接意味着客户端必须连接到元数据服务器才能下载最新的元数据的变化。在收到响应或到达连接超时后，立即启动客户端发送一个新请求保持连接打开。

节省存储空间
为了支持文件的版本历史记录，保证可靠性，同一个文件可以有多个版本跨多个数据中心存储。存储空间会因频繁使用而迅速被填满所有文件修订的备份。提出了三种降低存储成本的技术:

• 对重复的数据块进行重复数据删除。在帐户级别消除冗余区块很容易节省空间的方法。如果两个块具有相同的哈希值，则它们是相同的。
• 采用智能数据备份策略。
  有两种优化策略可以应用:
  • 设置限制:可以设置要存储的版本数。如果极限是到达后，最旧的版本将被新版本取代。只保留有价值的版本:有些文件可能经常编辑。例如,
  • 保存大量修改的文档的每个编辑版本可能意味着文件是短时间内节省1000倍以上。为了避免不必要的拷贝，我们可以限制保存的版本数。我们更重视最新的版本。实验有助于确定保存的最佳版本数。

将不常用的数据移到冷库。冷数据是指没有被处理过的数据活跃数月或数年。像亚马逊S3冰川[11]这样的冷库比S3。

故障处理
故障可能发生在大型系统中，我们必须采用设计策略来解决这些失败。你的面试官可能会对你如何处理以下系统故障:

• 负载均衡器故障:如果负载均衡器故障，备用服务器将变为活动状态增加交通流量。负载均衡器通常使用心跳(心跳周期)来监控彼此负载均衡器之间发送的信号。如果负载均衡器没有发送，则认为它失败心跳一段时间。
• 块服务器故障:如果一个块服务器故障，其他服务器将继续未完成或挂起就业机会。
• 云存储故障:S3桶在不同区域复制多次。如果如果文件在一个region中不可用，它们可以从不同的region中获取。
• API服务器故障:该服务是无状态的。如果API服务器失败，流量将被重定向通过负载均衡器连接到其他API服务器。
• 元数据缓存失败:元数据缓存服务器多次复制。如果一个节点发生故障后，您仍然可以访问其他节点来获取数据。我们将启用一个新的缓存更换故障服务器。
• 元数据数据库故障。
  • Master down:如果Master down，提升其中一个slave作为新的Master并启动一个新的从节点。
  • Slave down:如果一个Slave down，则可以使用另一个Slave进行读操作和使用另一个数据库服务器替换故障的数据库服务器。
• 通知服务失败:每个在线用户都与服务器保持长时间轮询连接通知服务器。因此，每个通知服务器都与多个用户连接。根据对于2012年的Dropbox talk[6]，每台机器有超过100万个连接被打开。如果一个服务器宕机，所有长轮询连接丢失，因此客户端必须重新连接到a不同的服务器。即使一台服务器可以保持多个打开的连接，它也不能立即重新连接所有丢失的连接。重新连接所有丢失的客户端是一个相对缓慢的过程。
• 离线备份队列失败:队列复制多次。如果一个队列失败，
  队列的使用者可能需要重新订阅备份队列。

步骤4 -打包

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

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

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

• 首先，必须实现相同的分块、压缩和加密逻辑不同的平台(iOS, Android, Web)。它很容易出错，需要大量的工程工作努力。在我们的设计中，所有这些逻辑都在一个集中的地方实现:块服务器。
• 其次，由于客户端很容易被黑客攻击或操纵，因此实现了加密逻辑在客户端并不理想。

系统的另一个有趣演变是将在线/离线逻辑移动到单独的服务。我们把它称为在线服务。通过将到场服务移出通知服务器，在线/离线功能可以很容易地与其他服务集成。

恭喜你走到了这一步!现在给自己一点鼓励吧。好工作!

Reference materials
[1] Google Drive: https://www.google.com/drive/
[2] Upload file data: https://developers.google.com/drive/api/v2/manage-uploads
[3] Amazon S3: https://aws.amazon.com/s3
[4] Differential Synchronization https://neil.fraser.name/writing/sync/
[5] Differential Synchronization youtube talk https://www.youtube.com/watch?
v=S2Hp_1jqpY8
[6] How We’ve Scaled Dropbox: https://youtu.be/PE4gwstWhmc
[7] Tridgell, A., & Mackerras, P. (1996). The rsync algorithm.
[8] Librsync. (n.d.). Retrieved April 18, 2015, from https://github.com/librsync/librsync
[9] ACID: https://en.wikipedia.org/wiki/ACID
[10] Dropbox security white paper:
https://www.dropbox.com/static/business/resources/Security_Whitepaper.pdf
[11] Amazon S3 Glacier: https://aws.amazon.com/glacier/faqs/