S3-like 对象存储

在本章中，我们设计了一个类似于亚马逊简单存储服务（S3）的对象存储服务。S3 是亚马逊网络服务（AWS）提供的通过基于 RESTful API 的接口提供对象存储的服务。以下是关于 AWS S3 的一些事实：

于 2006 年 6 月发布。
S3 在 2010 年增加了版本控制、桶策略和分部上传支持。
S3 在 2011 年增加了服务器端加密、多对象删除和对象过期功能。
亚马逊到 2013 年报告称 S3 存储了 2 万亿个对象。
生命周期策略、事件通知和跨区域复制支持分别在 2014 年和 2015 年引入。
亚马逊报告到 2021 年存储在 S3 中的对象超过 100 万亿个。

在我们深入研究对象存储之前，让我们首先回顾一下存储系统的一般知识并定义一些术语。

存储系统 101

在高层次上，存储系统大致可分为三类：

块存储
文件存储
对象存储

块存储

块存储先于 1960 年代出现。常见的存储设备如硬盘驱动器（HDD）和固态驱动器（SSD），这些设备物理上连接到服务器上，都被视为块存储。

块存储将原始块以卷的形式呈现给服务器。这是最灵活和多功能的存储形式。服务器可以格式化这些原始块并将其用作文件系统，或者可以将这些块的控制权交给应用程序。一些应用程序，如数据库或虚拟机引擎，会直接管理这些块，以榨取它们的每一点性能。

块存储不限于物理连接的存储。块存储可以通过高速网络或像光纤通道（FC）[1] 和 iSCSI [2] 这样的标准连接协议连接到服务器。从概念上讲，网络连接的块存储仍然提供原始块。对服务器来说，它的工作方式与物理连接的块存储相同。

文件存储

文件存储基于块存储构建。它提供了一种高级抽象，使处理文件和目录更加容易。数据以文件的形式存储在层次化的目录结构下。文件存储是最常见的通用存储解决方案。文件存储可以通过使用常见的文件级网络协议（如 SMB/CIFS [3] 和 NFS [4]）使大量服务器访问。访问文件存储的服务器无需处理管理块、格式化卷等复杂性。文件存储的简洁性使其成为在组织内部共享大量文件和文件夹的理想解决方案。

对象存储

对象存储是新的。它故意牺牲性能以换取高耐用性、大规模和低成本。它针对相对“冷”的数据，并主要用于归档和备份。对象存储将所有数据以对象的形式存储在扁平结构中。没有层次化的目录结构。数据访问通常通过 RESTful API 提供。与其他存储类型相比，它相对较慢。大多数公共云服务提供商都提供了对象存储服务，例如 AWS S3、Google 对象存储和 Azure 块存储。

比较

Figure 1 Three different storage options — 图 1 三种不同的存储选项

表 1 比较了块存储、文件存储和对象存储。

块存储	文件存储	对象存储
可变内容	Y	Y	N (支持对象版本控制，就地更新不支持）
成本	高	中等到高	低
性能	中等到高，非常高	中等到高	低到中等
一致性	强一致性	强一致性	强一致性 [5]
数据访问	SAS [6]/iSCSI/FC	标准文件访问，CIFS/SMB 和 NFS	RESTful API
可扩展性	中等规模扩展性	高可扩展性	vast 扩展性
适合	虚拟机（VM）、高性能应用程序如数据库	通用文件系统访问	二进制数据，非结构化数据

表 1 存储选项

术语

为了设计 S3 类似的对象存储，我们首先需要了解一些核心的对象存储概念。本节提供了对象存储中相关术语的概述。

Bucket. 一个对象的逻辑容器。桶名是全局唯一的。要上传数据到 S3，我们必须首先创建一个桶。

Object. 对象是我们存储在桶中的个体数据。它包含对象数据（也称为负载）和元数据。对象数据可以是任意字节序列，我们想要存储的内容。元数据是一组名称-值对，用于描述对象。

版本控制。一种可以在同一个桶中保存对象多个版本的特性。它在桶级别启用。此特性使用户能够恢复意外删除或覆盖的对象。

统一资源标识符（URI）。对象存储提供了 RESTful API 以访问其资源，即桶和对象。每个资源通过其 URI 唯一标识。

服务级别协议（SLA）。服务级别协议是服务提供商与客户之间的一项合同。例如，Amazon S3 标准不频繁访问存储类提供了以下 SLA [7]：

设计用于在多个可用区中实现 99.999999999%的对象持久性。
数据在单一可用区毁灭的情况下具有韧性。
设计用于 99.9%可用性。

Step 1 - 理解问题并确定设计范围

以下问题有助于澄清需求并缩小范围。

候选人: 设计中应该包含哪些功能？

面试官: 我们希望你设计一个类似于 S3 的对象存储系统，具备以下功能：

桶的创建。
对象上传和下载。
对象版本控制。
列出桶中的对象。这类似于“aws s3 ls”命令 [8]。

候选者: 典型的数据量是多少？

面试官：我们需要高效地存储大量大对象（几 GB 及以上）和大量小对象（几十 KB）。

候选人: 我们一年需要存储多少数据？

面试官: 100 千兆字节 (PB)。

候选人: 我们可以假设数据持久性为 6 个 9（99.9999%）且服务可用性为 4 个 9（99.99%）吗？

面试官：是的，这听起来合理。

非功能需求

100 PB 的数据
数据耐用性是六个九
服务可用性为 99.99%
存储效率。在保持高可靠性与性能的同时降低存储成本。

粗略估算

对象存储很可能在磁盘容量或每秒输入输出操作次数（IOPS）上存在瓶颈。让我们来看一下。

磁盘容量。假设对象遵循以下分布：
- 20% 的所有对象是小对象（小于 1MB）。
- 60%的对象是中等大小的对象（1MB ~ 64MB）。
- 20%是大对象（大于 64MB）。
IOPS. 假设一个硬盘（SATA 接口，7200 转/分钟）每秒可以进行 100~150 次随机寻道（100-150 IOPS）。

在这些假设下，我们可以估算系统可以持久化的对象总数。为了简化计算，让我们使用每种对象类型的中位数大小（小型对象为 0.5MB，中型对象为 32MB，大型对象为 200MB）。40%的存储使用率给我们：

100 PB = 100*1000*1000*1000 MB = 10^11 MB
10^11*0.4/( 0.2*0.5MB + 0.6 *32MB + 0.2*200MB) = 0.68 十亿个对象。
如果我们假设一个对象的元数据大小约为 1KB，我们需要 0.68 TB 的空间来存储所有元数据信息。

即使我们可能不会用到那些数字，了解系统的规模和约束条件还是很有帮助的。

Step 2 - 提出高层次设计并获得认同

在深入设计之前，让我们探索一下对象存储的一些有趣属性，因为它们可能会对其产生影响。

对象不可变性。对象存储与其他两种存储系统的主要区别之一是，对象存储中的对象是不可变的。我们可能删除它们或用全新的版本完全替换它们，但不能对其进行增量修改。

键值存储。我们可以使用对象 URI 来检索对象数据（列表 1）。对象 URI 是键，对象数据是值。

Request:
GET /bucket1/object1.txt HTTP/1.1

Response:
HTTP/1.1 200 OK
Content-Length: 4567

[4567 bytes of object data]

列出 1 使用对象 URI 获取对象数据

写一次，读多次。对象数据的数据访问模式写一次读多次。根据 LinkedIn 的研究，95%的请求是读操作[9]。

支持小对象和大对象。对象大小可能不同，我们需要支持两者。

对象存储的设计理念与 UNIX 文件系统非常相似。在 UNIX 中，当我们把文件保存到本地文件系统时，并不会将文件名和文件数据一起保存。相反，文件名存储在一个称为“inode”的数据结构中[10]，而文件数据则存储在不同的磁盘位置。inode 包含一个指向文件数据磁盘位置的文件块指针列表。当我们访问本地文件时，首先从 inode 中获取元数据，然后通过跟随文件块指针到实际的磁盘位置来读取文件数据。

对象存储的工作方式类似。inode 成为元数据存储，存储所有对象的元数据。硬盘成为数据存储，存储对象的数据。在 UNIX 文件系统中，inode 使用文件块指针记录数据在硬盘上的位置。在对象存储中，元数据存储使用对象的 ID 通过网络请求找到数据存储中的相应对象数据。图 2 显示了 UNIX 文件系统和对象存储。

Figure 2 Unix file system and object store — 图 2 Unix 文件系统和对象存储

分离元数据和对象数据简化了设计。数据存储包含不可变数据，而元数据存储包含可变数据。这种分离使我们能够独立实现和优化这两个组件。图 3 展示了桶和对象的外观。

高层设计

图 4 显示了高层次的设计。

让我们一一介绍各个组件。

负载均衡器。将 RESTful API 请求分发到多个 API 服务器。

API 服务。协调对身份和访问管理服务、元数据服务以及存储库的远程过程调用。此服务无状态，因此可以水平扩展。

身份和访问管理（IAM）。处理身份验证、授权和访问控制的中心位置。身份验证验证你是谁，而授权则根据你是谁来验证你可以执行哪些操作。

数据存储。存储和检索实际数据。所有与数据相关的操作基于对象 ID（UUID）。

元数据存储。存储对象的元数据。

请注意，元数据和数据存储只是逻辑组件，并且有不同的实现方式。例如，在 Ceph 的 Rados Gateway [11] 中，并没有独立的元数据存储。对象桶等一切内容都以一个或多个 Rados 对象的形式持久化存储。

现在我们对高級設計有了基本的理解，让我们探索一下对象存储中最重要的工作流程。

上传对象。
下载一个对象。
对象版本控制和列出桶中的对象。它们将在“深入探讨”部分解释。

上传对象

一个对象必须存在于一个桶中。在这个例子中，我们首先创建一个名为“bucket-to-share”的桶，然后将一个名为“script.txt”的文件上传到该桶中。图 5 解释了这个流程的 7 个步骤。

客户端发送一个 HTTP PUT 请求以创建名为“bucket-to-share”的桶。该请求被转发到 API 服务。
API 服务调用 IAM 以确保用户具有 WRITE 权限并已被授权。
API 服务调用元数据存储在元数据数据库中创建包含桶信息的条目。一旦条目被创建，就会向客户端返回成功消息。
桶创建后，客户端发送一个 HTTP PUT 请求以创建一个名为“script.txt”的对象。
API 服务验证用户身份并确保用户对桶具有 WRITE 权限。
一旦验证成功，API 服务会将对象数据通过 HTTP PUT 请求的负载发送到数据存储。数据存储将负载作为对象持久化，并返回对象的 UUID。
API 服务调用元数据存储在元数据数据库中创建一个新的条目。它包含对象_id（UUID）、桶_id（对象所属的桶）、对象名称等重要元数据。一个示例条目如表 2 所示。

对象名称	对象_id	桶_id
script.txt	239D5866-0052-00F6-014E-C914E61ED42B	82AA1B2E-F599-4590-B5E4-1F51AAE5F7E4

表 2 样本条目

上传对象的 API 可以像这样：

PUT /bucket-to-share/script.txt HTTP/1.1
Host: foo.s3example.org
Date: Sun, 12 Sept 2021 17:51:00 GMT
Authorization: authorization string
Content-Type: text/plain
Content-Length: 4567
x-amz-meta-author: Alex

[4567 bytes of object data]

列出 2 上传对象

下载对象

一个桶没有目录层次结构。然而，我们可以创建一个逻辑层次结构，通过将桶名和对象名连接起来模拟文件夹结构。例如，我们将对象命名为“bucket-to-share/script.txt”而不是“script.txt”。在 GET 请求中指定对象名以获取对象。下载对象的 API 如下所示：

GET /bucket-to-share/script.txt HTTP/1.1
Host: foo.s3example.org
Date: Sun, 12 Sept 2021 18:30:01 GMT
Authorization: authorization string

列出 3 下载对象

Figure 6 Downloading an object — 图 6 下载对象

如前所述，数据存储不存储对象的名称，仅通过 object_id（UUID）支持对象操作。为了下载对象，我们首先将对象名称映射到 UUID。下载对象的工作流如下所示：

客户端向负载均衡器发送 HTTP GET 请求：GET /bucket-to-share/script.txt
API 服务查询 IAM 以验证用户是否有读取桶的权限。
一旦验证通过，API 服务将从元数据存储中获取相应对象的 UUID。
接下来，API 服务通过其 UUID 从数据存储中获取对象数据。
API 服务将对象数据通过 HTTP GET 响应返回给客户端。

第 3 步 - 设计深度解析

在本节中，我们将深入探讨几个领域：

数据存储
元数据数据模型
列出桶中的对象
对象版本控制
优化大文件上传
垃圾收集

数据存储

让我们更详细地看一下数据存储的设计。如前所述，API 服务处理来自用户的外部请求，并调用不同的内部服务来满足这些请求。为了持久化或检索一个对象，API 服务会调用数据存储。图 7 展示了 API 服务与数据存储之间在上传和下载对象时的交互。

Figure 7 Upload and download an object — 图 7 上传和下载对象

高级数据存储设计

数据存储有三个主要组件，如图 8 所示。

Figure 8 Data store components — 图 8 数据存储组件

数据路由服务

数据路由服务提供 RESTful 或 gRPC [12] API 以访问数据节点集群。这是一项无状态服务，可以通过添加更多服务器进行扩展。该服务具有以下职责：

查询放置服务以获取最佳数据节点以存储数据。
从数据节点读取数据并返回给 API 服务。
将数据写入数据节点。

放置服务

放置服务确定应选择哪些数据节点（主节点和副本）来存储对象。它维护一个虚拟集群映射，提供了集群的物理拓扑结构。虚拟集群映射包含每个数据节点的位置信息，放置服务使用这些信息确保副本在物理上是分离的。这种分离对于高持久性至关重要。有关详细信息，请参阅下方的“持久性”部分。图 9 展示了虚拟集群映射的一个示例。

Figure 9 Virtual cluster map — 图 9 虚拟集群地图

放置服务持续通过心跳监测所有数据节点。如果数据节点在可配置的 15 秒宽限期内未发送心跳，放置服务将在虚拟集群图中将该节点标记为“下线”。

这是一个关键服务，所以我们建议构建 5 或 7 个放置服务节点的集群，使用 Paxos [13] 或 Raft [14] 共识协议。共识协议确保只要超过半数的节点是健康的，服务整体就能继续运行。例如，如果放置服务集群有 7 个节点，它可以容忍 3 个节点的故障。要了解共识协议，请参阅参考资料 [13] [14]。

数据节点

数据节点存储实际的对象数据。通过将数据复制到多个数据节点，也称为复制组，来确保可靠性和持久性。

每个数据节点上运行着一个数据服务守护进程。该数据服务守护进程会持续向放置服务发送心跳。心跳消息包含以下关键信息：

数据节点管理多少个磁盘驱动器（HDD 或 SSD）？
每个磁盘存储了多少数据？

当放置服务首次接收到数据节点的心跳时，它会为此数据节点分配一个 ID，将其添加到虚拟集群映射中，并返回以下信息：

数据节点的唯一 ID
虚拟集群地图
在哪里复制数据

数据持久化流程

Figure 10 Data persistence flow — 图 10 数据持久化流程

现在让我们来看看数据在数据节点中是如何持久化的。

API 服务将对象数据转发到数据存储。
数据路由服务为此对象生成一个 UUID，并查询存储服务以确定存储此对象的数据节点。存储服务检查虚拟集群映射并返回主数据节点。
数据路由服务将数据直接发送到主数据节点，同时包含其 UUID。
主数据节点将数据保存在本地，并将其复制到两个次要数据节点。当数据成功复制到所有次要节点时，主节点会响应数据路由服务。
对象（ObjId）的 UUID 返回给 API 服务。

在第 2 步中，给定一个对象的 UUID 作为输入，放置服务返回该对象的复制组。放置服务是如何做到这一点的？请注意，这种查找需要是确定性的，并且必须能够应对复制组的增加或删除。一致哈希是一种常见的此类查找函数的实现方式。更多信息请参阅[15]。

在第 4 步中，主数据节点在向所有从节点复制数据之前不会返回响应。这使得所有数据节点中的数据具有强一致性。这种一致性会带来延迟成本，因为我们必须等待最慢的副本完成。图 11 展示了一致性和延迟之间的权衡。

Figure 11 Trade-off between consistency and latency — 图 11 一致性与延迟之间的权衡

数据只有在所有三个节点存储数据后才被视为成功保存。这种方法具有最佳的一致性但延迟最高。
数据在主节点和其中一个从节点存储数据后被视为成功保存。此方法的一致性为中等，延迟也为中等。
数据在主节点持久化数据后被视为成功保存。这种方法的一致性最差，但延迟最低。

两者都是最终一致性的一种形式。

数据是如何组织的

现在让我们看看每个数据节点是如何管理数据的。一个简单的解决方案是将每个对象存储在一个独立的文件中。这可以工作，但在有很多小文件时性能会下降。当文件系统上有太多小文件时，会出现两个问题。首先，它浪费了很多数据块。文件系统将文件存储在离散的磁盘块中。磁盘块的大小相同，并且在卷初始化时固定。典型的块大小约为 4 KB。对于小于 4 KB 的文件，它仍然会消耗整个磁盘块。如果文件系统包含很多小文件，它会浪费很多磁盘块，每个磁盘块只包含一个小文件，填充率很低。

其次，这可能会超出系统的 inode 容量。文件系统通过一种特殊类型的块（称为 inode）来存储文件的位置和其他信息。对于大多数文件系统而言，inode 的数量在磁盘初始化时是固定的。在有数百万个小文件的情况下，这会面临消耗完所有 inode 的风险。此外，即使有积极的文件系统元数据缓存，操作系统也不太能很好地处理大量的 inode。由于这些原因，将小对象作为单独的文件存储在实践中并不奏效。

为了解决这些问题，我们可以将许多小对象合并到一个较大的文件中。这在概念上类似于写前滚日志（WAL）。当我们保存一个对象时，它会被追加到现有的可读写文件中。当可读写文件达到其容量阈值——通常设置为几 GB 时，该可读写文件会被标记为只读，并创建一个新的可读写文件来接收新的对象。一旦文件被标记为只读，它只能用于处理读请求。图 12 解释了这一过程是如何工作的。

Figure 12 Store multiple small objects in one big file — 图 12 将多个小对象存储在一个大文件中

注意，对读写文件的写访问必须进行序列化。如图 12 所示，对象按顺序一个接一个地存储在读写文件中。为了保持这种磁盘布局，必须让多个核心依次处理并行到来的写请求并轮流向读写文件写入。对于有大量核心并行处理大量到来请求的现代服务器，这严重限制了写入吞吐量。为了解决这个问题，我们可以提供专用的读写文件，每个处理到来请求的核心一个。

对象查找

每个数据文件包含许多小对象，数据节点是如何通过 UUID 定位对象的？数据节点需要以下信息：

包含对象的数据文件
数据文件中对象的起始偏移量
对象的大小

支持此查找的数据库模式如表 3 所示。

Table 3 Object_mapping table — 表 3 对象映射表

字段	描述
对象_id	对象的 UUID
文件名	包含对象的文件名
起始偏移量	文件中对象的起始地址
对象大小	对象的字节数量

表 4 Object_mapping 字段

我们考虑了两种存储这种映射的方法：基于文件的键值存储，如 RocksDB [16]，或者关系型数据库。RocksDB 基于 SSTable [17]，写入速度快但读取速度较慢。关系型数据库通常使用基于 B+ 树 [18] 的存储引擎，读取速度快但写入速度较慢。如前所述，数据访问模式是一次写入多次读取。由于关系型数据库提供了更好的读取性能，因此它比 RocksDB 更合适。

我们应该如何部署这个关系型数据库？在我们的规模下，映射表的数据量非常庞大。部署一个大型集群来支持所有数据节点是可以工作的，但管理起来比较困难。请注意，这些映射数据在每个数据节点内是隔离的。不需要在数据节点之间共享这些数据。为了利用这一特性，我们可以在每个数据节点上简单地部署一个关系型数据库。SQLite [19] 是一个不错的选择。它是一个基于文件的关系型数据库，声誉良好。

更新了数据持久化流程

由于我们对数据节点进行了不少修改，让我们重新看看如何在数据节点中保存一个新的对象（图 13）。

API 服务发送请求以保存一个名为“object 4”的新对象。
The data node service 将名为“object 4”的对象追加到名为“/data/c”的读写文件末尾。
"object_mapping"表中插入了新的记录“object 4”。
数据节点服务将 UUID 返回给 API 服务。

Figure 13 Updated data persistence flow — 图 13 更新的数据持久化流程

耐久性

数据可靠性对于数据存储系统至关重要。我们如何能够创建一个提供九九九九九九 durability 的存储系统？每个故障案例都需要仔细考虑，并且数据需要适当复制。

硬件故障和故障域

硬盘故障是不可避免的，无论我们使用哪种介质。某些存储介质可能比其他介质更耐用，但我们不能依赖单个硬盘来实现我们的耐久性目标。一种 proven 的方法是将数据复制到多个硬盘，这样单个磁盘故障不会影响数据的可用性，整体来看是安全的。在我们的设计中，我们将数据复制三次。

让我们假设旋转硬盘的年度故障率为 0.81% [20]。这个数字高度依赖于型号和品牌。制作数据的 3 份副本可以得到 1-(0.0081)^3=~0.999999 的可靠性。这是一个非常粗略的估计。对于更复杂的计算，请参阅[20]。

为了进行全面的耐久性评估，我们还需要考虑不同故障域的影响。故障域是当关键服务出现故障时，环境中的物理或逻辑部分受到负面影响的部分。在现代数据中心中，服务器通常被放置在机架中[21]，而机架则被分组为行/层/房间。由于每个机架共享网络交换机和电源，因此机架中的所有服务器都在机架级故障域中。现代服务器共享主板、处理器、电源供应、HDD 驱动器等组件。服务器中的组件处于节点级故障域中。

这里是一个大规模故障域隔离的良好示例。通常，数据中心会将没有任何共享的基础设施划分为不同的可用区（AZ）。我们将数据复制到不同的 AZ 以最小化故障影响（图 14）。请注意，故障域级别的选择并不会直接增加数据的持久性，但在大规模断电、冷却系统故障、自然灾害等极端情况下，它会导致更好的可靠性。

Figure 14 Multi-datacenter replication — 图 14 多数据中心复制

纠删码

制作三份完整拷贝的数据给我们大约提供了六位数的数据持久性。还有其他方法可以进一步提高持久性吗？是的，纠删码是一种选择。纠删码[22]以不同的方式处理数据持久性。它将数据分割成更小的片段（放置在不同的服务器上），并创建校验和以实现冗余。在发生故障时，我们可以使用片段数据和校验和来重构数据。让我们来看一个具体的例子（4 + 2 纠删码），如图 15 所示。

数据被分成四个大小相等的数据块 d1、d2、d3 和 d4。
数学公式[23]用于计算校验位 p1 和 p2。为了给出一个简化得多的例子，p1 = d1 + 2*d2 - d3 + 4*d4 且 p2 = -d1 + 5*d2 + d3 - 3*d4 [24]。
Data d3 和 d4 由于节点崩溃而丢失。
数学公式用于重构丢失的数据 d3 和 d4，使用已知的 d1、d2、p1 和 p2 的值。

让我们看看图 16 中的另一个例子，以便更好地理解在故障域中擦除编码的工作原理。一个(8+4)的擦除编码设置会将原始数据均匀分割成 8 个数据块，并计算出 4 个校验位。这 12 个数据片段大小相同。这 12 个数据块分布在 12 个不同的故障域中。擦除编码背后的数学确保最多有 4 个节点故障时，原始数据可以被重建。

Figure 16 (8+4) erasure coding — 图 16 (8+4) 擦除编码

与复制相比，数据路由器在擦除编码中不仅需要从一个健康的节点读取对象的数据，还需要从至少 8 个健康的节点读取数据。这是架构设计的权衡。我们使用一个更复杂的解决方案，访问速度较慢，以换取更高的持久性和更低的存储成本。对于主要成本为存储的对象存储，这种权衡可能是值得的。

纠删码需要多少额外空间？对于每两个数据块，我们需要一个校验块，因此存储开销为 50%（图 17）。而在 3 副本复制中，存储开销为 200%（图 17）。

Figure 17 Extra space for replication and erasure coding — 图 17 复制和擦除编码的额外空间

数据擦除编码是否能增加数据持久性？假设一个节点的年度故障率为 0.81%。根据 Backblaze [20]的计算，擦除编码可以实现 11 个 9 的持久性。计算过程需要复杂的数学运算。如果你感兴趣，可以参阅[20]获取详细信息。

表 5 比较了复制和擦除编码的优缺点。

	复制	纠删码
耐久性	6 位数的耐用性（数据复制 3 次）	11 位的耐用性（8+4 擦除编码）。擦除编码胜出。
存储效率	200% 存储开销。	50% 存储开销。擦除编码胜出。
计算资源	没有计算。复现获胜。	提高计算资源的使用率以计算校验位。
写性能	复制数据到多个节点。不需要进行计算。复制胜出。	增加了写延迟，因为数据写入磁盘之前需要计算校验和。
读取性能	在正常运行时，读取操作由相同的副本提供服务。在故障模式下，读取操作不会受到影响，因为读取操作可以从非故障副本提供。复制机制胜出。	在正常运行时，每次读取都必须来自集群中的多个节点。在故障模式下，读取速度较慢，因为必须先重建缺失的数据。

表 5 重复复制 vs 擦除编码

总结来说，复制在对延迟敏感的应用中被广泛采用，而擦除编码常被用于减少存储成本。擦除编码因其成本效益和耐用性而具有吸引力，但会大大复杂化数据节点的设计。因此，对于此设计，我们主要关注复制。

正确性验证

Erasure coding 在相似的存储成本下提高了数据的耐用性。现在我们可以解决另一个难题：数据损坏。

如果磁盘完全失效并且可以检测到该故障，可以将其视为数据节点故障。在这种情况下，可以使用纠删码重建数据。然而，在大规模系统中，内存数据损坏是常见现象。

这个问题可以通过在进程边界之间验证校验和[25]来解决。校验和是用于检测数据错误的小块数据。图 18 展示了校验和的生成过程。

Figure 18 Generate checksum — 图 18 生成校验和

如果我们知道原始数据的校验和，可以在传输后计算数据的校验和：

如果不同，数据已损坏。
如果相同，数据不被损坏的可能性非常高。概率不是 100%，但在实践中，我们可以假设它们是相同的。

Figure 19 Compare checksums — Figure 19 比较校验和

有许多校验和算法，如 MD5 [26]、SHA1[27]、HMAC [28] 等。一个好的校验和算法通常会对输入的微小更改输出显著不同的值。对于本章，我们选择如 MD5 这样的简单校验和算法。

在我们的设计中，我们在每个对象的末尾附加校验和。在将文件标记为只读之前，我们在文件末尾添加整个文件的校验和。图 20 显示了布局。

Figure 20 Add checksum to data node — 图 20 向数据节点添加校验和

使用(8+4)纠删码和校验和验证，当我们读取数据时会发生以下情况：

获取对象数据和校验和。
计算接收到的数据的校验和。

(a). 如果两个校验和匹配，数据无误。

(b). 如果校验和不同，数据已损坏。我们将尝试通过从其他故障域读取数据来恢复。
重复第 1 步和第 2 步，直到返回所有 8 件数据。然后我们重组数据并将其发送回客户端。

元数据数据模型

在本节中，我们首先讨论数据库架构，然后探讨数据库的扩展。

模式

数据库模式需要支持以下 3 个查询：

查询 1: 通过对象名称查找对象 ID。

查询 2：根据对象名称插入和删除一个对象。

查询 3：列出桶中具有相同前缀的对象。

图 21 显示了架构设计。我们需要两个数据库表：bucket 和 object。

扩展桶表

由于用户通常可以创建的桶的数量有限，桶表的大小较小。假设我们有 100 万客户，每个客户拥有 10 个桶，每个记录占用 1 KB。这意味着我们需要 10 GB（100 万 * 10 * 1KB）的存储空间。整个表很容易 fitting 在一个现代数据库服务器上。然而，单个数据库服务器可能没有足够的 CPU 或网络带宽来处理所有读取请求。如果这样，我们可以在多个数据库副本之间分散读取负载。

缩放对象表

对象表存储了对象元数据。在我们的设计规模下，数据集很可能无法 fitting 在单个数据库实例中。我们可以通过分片来扩展对象表。

一种方法是按 bucket_id 分片，这样同一桶下的所有对象都会存储在同一个分片中。但这不行，因为一个桶可能包含数十亿个对象，会导致热点分片。

另一种选择是按 object_id 分片。这种分片方案的优点是能够均匀分布负载。但由于查询 1 和查询 2 是基于 URI 的，所以我们无法高效地执行这两个查询。

我们选择通过 bucket_name 和 object_name 的组合来分片，因为大多数元数据操作都是基于对象 URI 的，例如，通过 URI 查找对象 ID 或通过 URI 上传对象。为了均匀分布数据，可以使用 (bucket_name, object_name) 的哈希值作为分片键。

采用这种分片方案，前两个查询很容易支持，但最后一个查询就不那么明显了。让我们来看一下。

列出桶中的对象

对象存储以扁平结构组织文件，而不是层次结构，就像文件系统一样。对象可以使用这种格式的路径进行访问，例如，s3://bucket-name/object-name。例如，s3://mybucket/abc/d/e/f/file.txt 包含：

Bucket name: mybucket
对象名称: abc/d/e/f/file.txt

为了帮助用户组织桶中的对象，S3 引入了一个名为‘前缀’的概念。前缀是对象名称开头的字符串。S3 使用前缀以类似于目录的方式组织数据。然而，前缀不是目录。通过前缀列出桶只会返回那些以前缀开头的对象名称。

在上述路径 s3://mybucket/abc/d/e/f/file.txt 中，前缀是 abc/d/e/f/。

AWS S3 列出命令有 3 种典型用途：

列出某个用户拥有的所有桶。命令如下： ```
```
aws s3 list-buckets
```
列出存储桶中与指定前缀处于同一级别的所有对象。命令如下：
```
aws s3 ls s3://mybucket/abc/
```
在这种模式下，名称前缀之后带有更多斜杠的对象会被卷积到一个公共前缀中。例如，桶中包含这些对象：
```
CA/cities/losangeles.txt
CA/cities/sanfranciso.txt
NY/cities/ny.txt
federal.txt
```
列出以‘/’前缀的桶将返回这些结果，其中 CA/和 NY/下的所有内容都会被汇总到这些桶中：

CA/ NY/ federal.txt
递归列出桶中具有相同前缀的所有对象。命令如下： ``` ```
```
aws s3 ls s3://mybucket/abc/ --recursive
```
使用上面的同一个示例，列出带有 CA/ 前缀的桶将返回这些结果：
```
CA/cities/losangeles.txt
CA/cities/sanfranciso.txt
```

单数据库

让我们首先探索如何使用单个数据库支持列出命令。要列出某个用户拥有的所有桶，我们运行以下查询：

SELECT * FROM bucket WHERE owner_id={id}

要列出桶中具有相同前缀的所有对象，我们可以运行这样的查询。

SELECT * FROM object WHERE bucket_id = "123" AND object_name LIKE `abc/%`

在本示例中，我们查找所有 bucket_id 等于“123”且名称以“abc/”为前缀的对象。如前面用例 2 所述，在应用程序代码中，任何在指定前缀之后名称中包含更多斜杠的对象都会被合并。

相同的查询将支持递归列表模式，如之前用例 3 所述。应用程序代码将列出所有具有相同前缀的对象，而不进行任何汇总。

分布式数据库

当元数据表进行分片时，实现列表功能比较困难，因为我们不知道哪些分片包含数据。最明显的解决方案是在所有分片上运行搜索查询，然后聚合结果。为了实现这一点，我们可以这样做：

元数据服务通过运行以下查询来查询每个分片：

SELECT * FROM object WHERE bucket_id = “123” AND object_name LIKE `a/b/%`

元数据服务聚合每个分片返回的所有对象，并将结果返回给调用者。

这个解决方案可行，但为这个功能实现分页稍微有些复杂。在解释原因之前，我们先回顾一下单个数据库的简单分页工作原理。要返回每页包含 10 个对象的列表页，SELECT 查询将从这里开始：

SELECT * FROM object WHERE
bucket_id = "123" AND object_name LIKE `a/b/%`
ORDER BY object_name OFFSET 0 LIMIT 10

The OFFSET 和 LIMIT 会将结果限制在前 10 个对象。在下一次调用中，用户发送请求给服务器一个提示，以便服务器知道如何构造第二页的查询，OFFSET 为 10。这个提示通常通过服务器在每页返回给客户端的游标来完成。游标中编码了偏移信息。客户端会在请求下一页时包含这个游标。服务器解码游标，并使用其中嵌入的偏移信息来构造下一页的查询。以上述示例为例，第二页的查询看起来像这样：

SELECT * FROM metadata
WHERE bucket_id = "123" AND object_name LIKE `a/b/%`
ORDER BY object_name OFFSET 10 LIMIT 10

这个客户端-服务器请求循环将持续进行，直到服务器返回一个特殊的游标，标志着整个列表的结束。

现在，让我们探讨一下为什么为分片数据库支持分页会变得复杂。由于对象分布在不同的分片上，各个分片返回的结果数量可能会有所不同。有些分片可能包含完整的 10 个对象页面，而其他分片则可能是部分的或空的。应用程序代码会从每个分片接收结果，汇总并排序，然后只返回我们示例中的 10 个页面。那些未包含在当前轮次中的对象必须在下一轮中再次考虑。这意味着每个分片很可能有不同的偏移量。服务器必须跟踪所有分片的偏移量，并将这些偏移量与游标关联起来。如果有数百个分片，就需要跟踪数百个偏移量。

我们有一个解决方案可以解决问题，但存在一些权衡。由于对象存储针对大规模和高持久性进行了优化，对象列表性能通常不是优先考虑的事项。实际上，所有商用对象存储都以次优性能支持对象列表。为了利用这一点，我们可以将列表数据规范化到一个单独的表中，并按桶 ID 分片。这个表仅用于列出对象。在这种配置下，即使有数十亿个对象的桶也能提供可接受的性能。这将列表查询隔离到单个数据库中，大大简化了实现。

对象版本控制

版本控制是一个功能，可以在桶中保存对象的多个版本。通过版本控制，我们可以恢复意外删除或覆盖的对象。例如，我们可能修改一个文档并在同一个名称下将其保存在同一个桶中。如果没有版本控制，元数据存储中的旧版本文档元数据将被新版本替换。旧版本的文档将被标记为删除，因此其存储空间将被垃圾回收器回收。通过版本控制，对象存储将在元数据存储中保留文档的所有先前版本，并且文档的旧版本永远不会在对象存储中被标记为删除。

图 22 解释了如何上传版本化的对象。为了实现这一点，我们首先需要在桶上启用版本化。

Figure 22 Object versioning — 图 22 对象版本控制

客户端发送一个 HTTP PUT 请求以上传名为“script.txt”的对象。
API 服务验证用户身份并确保用户对桶具有 WRITE 权限。
一旦验证通过，API 服务将数据上传到数据存储。数据存储将数据作为新对象持久化，并返回一个新的 UUID 给 API 服务。
API 服务调用元数据存储来存储此对象的元数据信息。
为了支持版本控制，元数据存储中的对象表包含一个名为 object_version 的列，只有在启用版本控制时才会使用。而不是覆盖现有记录，会插入一个新的记录，该记录具有与旧记录相同的 bucket_id 和 object_name，但具有新的 object_id 和 object_version。object_id 是步骤 3 中返回的新对象的 UUID。object_version 是在插入新行时生成的 TIMEUUID [29]。无论我们为元数据存储选择哪种数据库，查找对象的当前版本都应高效。当前版本是具有相同 object_name 的所有条目中 TIMEUUID 值最大的一条。参见图 23 以了解我们如何存储版本化元数据的示例。

Figure 23 Versioned metadata — Figure 23 版本化的元数据

除了上传版本化的对象，还可以删除。让我们来看一下。

当我们删除一个对象时，所有版本都将保留在桶中，并插入一个删除标记，如图 24 所示。

Figure 24 Delete object by inserting a delete marker — 图 24 通过插入删除标记删除对象

删除标记是一个对象的新版本，在插入后成为当前版本的对象。当对象的当前版本是删除标记时，执行 GET 请求会返回 404 对象未找到错误。

优化大文件上传

在粗略估算中，我们估计有 20% 的对象是大型的。有些可能大于几 GB。可以直接上传如此大的对象文件，但可能会花费很长时间。如果在上传过程中网络连接中断，我们不得不重新开始。更好的解决方案是将大型对象分割成较小的部分并独立上传。在所有部分上传完成后，对象存储会将这些部分重新组装成对象。这个过程称为分块上传。

图 25 说明了分块上传的工作原理：

Figure 25 Multipart upload — Figure 25 多部分上传

客户端调用对象存储开始分块上传。
数据存储返回一个 uploadID，它唯一标识了此次上传。
客户端将大文件拆分成小对象并开始上传。假设文件大小为 1.6GB，客户端将其拆分成 8 部分，因此每部分的大小为 200MB。客户端在上传第一部分的同时，还上传了在第 2 步中收到的 uploadID。
当一个部分被上传时，数据存储会返回一个 ETag，这实际上是该部分的 md5 校验和。它用于验证多部分上传。
在所有部分上传完成后，客户端发送一个完整的多部分上传请求，该请求包括 uploadID、部分编号和 ETags。
数据存储根据部件编号将对象从其部件中重新组装。由于对象非常大，这个过程可能需要几分钟。重新组装完成后，它会向客户端返回成功消息。

这种做法的一个潜在问题是，一旦对象从这些部件重新组装后，旧部件就不再有用。为了解决这个问题，我们可以引入一个垃圾收集服务，负责释放不再需要的部件所占用的空间。

垃圾收集

垃圾回收是自动回收不再使用的存储空间的过程。数据可能变成垃圾有几种方式：

懒惰对象删除。在删除时标记对象为已删除，而不实际删除该对象。
孤儿数据。例如，上传了一半的数据或被放弃的多部分上传。
损坏的数据。未能通过校验和验证的数据。

垃圾收集器不会立即从数据存储中移除对象，删除的对象将会周期性地通过压缩机制清理。

垃圾回收器还负责回收副本中未使用的空间。对于副本复制，我们从主节点和备份节点删除对象。对于擦除编码，如果我们使用(8+4)配置，我们将从所有 12 个节点删除对象。

图 26 显示了压缩工作的一个例子。

垃圾收集器将对象从“/data/b”复制到一个新的文件“/data/d”中。注意垃圾收集器跳过了“Object 2”和“Object 5”，因为这两个对象的删除标志都被设置为 true。
在所有对象复制完成后，垃圾回收器会更新对象_mapping 表。例如，“Object 3”的 obj_id 和 object_size 字段保持不变，但 file_name 和 start_offset 会被更新以反映其新的位置。为了确保数据一致性，将对 file_name 和 start_offset 的更新操作包裹在一个数据库事务中是个好主意。

如图 26 所示，经过压缩后的新文件大小小于旧文件。为了避免创建大量小文件，垃圾回收器通常会等到读-only 文件数量较多时才进行压缩，并且压缩过程会将许多只读文件中的对象追加到少数几个较大的新文件中。

第 4 步 - 总结

在本章中，我们描述了类似 S3 的对象存储的高级设计。我们比较了块存储、文件存储和对象存储之间的差异。

这次面试的重点是对象存储的设计，所以我们列出了桶中对象的上传、下载、列出以及对象版本管理通常是如何实现的。

然后我们深入探讨了设计。对象存储由数据存储和元数据存储组成。我们解释了数据如何被持久化到数据存储中，并讨论了两种提高可靠性和持久性的方法：复制和纠删码。对于元数据存储，我们解释了多部分上传的执行过程，并讨论了如何设计数据库模式以支持典型用例。最后，我们解释了如何对元数据存储进行分片以支持更大的数据量。

恭喜你走到了这一步！现在给自己一个鼓掌。干得好！