【系統設計】S3 對象存儲

2022 年 8 月 8 日
筆記

在本文中，我們設計了一個類似於 Amazon Simple Storage Service (S3) 的對象存儲服務。S3 是 Amazon Web Services (AWS) 提供的一項服務，它通過基於 RESTful API 的接口提供對象存儲。根據亞馬遜的報告，到 2021 年，有超過 100 萬億個對象存儲在 S3 中。

在深入設計之前，有必要先回顧一下存儲系統和相關的術語。

存儲系統

在高層次上，存儲系統分類三大類：

塊存儲
文件存儲
對象存儲

塊存儲

塊存儲最早出現在 1960 年。常見的物理存儲設備，比如常說的 HDD 和 SSD 都屬於塊存儲。塊存儲直接暴露出來卷或者盤，這是最靈活，最通用的存儲形式。

塊存儲不局限於物理連接的存儲，也可以通過網絡、光纖和 iSCSI 行業標準協議連接到服務器。從概念上講，網絡附加塊存儲仍然暴露原始塊，對於服務器來說，它的工作方式和使用物理連接的塊存儲是相同的。

文件存儲

文件存儲在塊存儲的上層，提供了更高級別的抽象，文件存儲不需要處理管理塊、格式化卷等，所以它處理文件和目錄更簡單，數據文件存儲在分層目錄結構。

對象存儲

對象存儲相對來說比較新，為了高持久性，大規模和低成本而犧牲性能，這是一個非常刻意的權衡。對象存儲針對的是相對「冷」的數據，主要用于歸檔和備份。對象存儲把所有的數據作為對象存儲在平面結構中，沒有分層的目錄結構。

通常提供了 RESTful API 用來支持數據訪問，和其他的存儲相比，它是比較慢的，大多雲服務商都提供了對象存儲的產品，比如 AWS S3, Azure Blob 存儲等。

對比

術語

要設計一個類似於 S3 的對象存儲，我們需要先了解一些對象存儲的核心概念。

桶（Bucket），桶是對象的邏輯容器，存儲桶名稱是全局唯一的。
對象（Object），對象時我們存儲在桶中的單個數據，它由對象數據和元數據組成。對象可以是我們存儲的任何位元組序列，元數據是一組描述對象的鍵值對。
版本控制（Versioning），數據更新時，允許多版本共存。
統一資源標識符 (URI)，對象存儲提供了 RESTful API 來訪問資源，所以每個資源都有一個URI 唯一標識。
服務等級協議 (SLA)，SLA 是服務提供商和客戶之間的協議。比如 AWS S3 對象存儲，提供了 99.9 的可用性，以及誇張的 99.999999999% （11個9）的數據持久性。

設計要求

在這個面試的系統設計環節中，需要設計一個對象存儲，並且要滿足下面的幾個要求。

基礎功能，桶管理，對象上傳和下載，版本控制。
對象數據有可能是大對象（幾個 GB），也可能是小對象（幾十 kb）。
一年需要存儲 100 PB 的數據。
服務可用性 99.99% （4個9）, 數據持久性 99.9999 % （6個 9）。
需要比較低的存儲成本。

對象存儲的特點

在開始設計對象存儲之前，你需要了解它的下面這些特點。

對象不變性

對象存儲和其他兩種存儲的主要區別是，存儲對象是不可變的，允許進行刪除或者完全更新，但是不能進行增量修改。

鍵值存儲

我們可以使用 URI 來訪問對象數據，對象的 URI 是鍵，對象的數據是值，如下

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

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

[4567 bytes of object data]

寫一次，讀多次

對象數據的訪問模式是一次寫入，多次讀取。根據 LinkedIn 做的研究報告，95 %的請求是讀取操作。

【Ambry: LinkedIn』s Scalable Geo-Distributed Object Store】

支持小型和大型對象

對象存儲的設計理念和 UNIX 文件系統的設計理念非常相似。在 UNIX 中，當我們在本地文件系統中保存文件時，它不會把文件名和文件數據一起保存。那是怎麼做的呢？它把文件名存儲在 inode 的數據結構中，把文件數據存儲在不同的磁盤位置。inode 包含一個文件塊指針列表，這些指針指向文件數據的磁盤位置。當我們訪問本地文件時，首先會獲取 inode 中的元數據。然後我們按照文件塊指針來讀取磁盤的文件數據。

對象存儲的工作方式也是如此，元數據和數據存儲分離，如下

看一看我們的存儲桶和對象的設計

整體設計

下圖顯示了對象存儲的整體設計。

Load balancer 負載均衡，向多個 API 服務分發 RESTful API 請求。
API Service，編排身份驗證服務，元數據服務和存儲服務，它是無狀態的，可以很好的支持水平擴展。
Identity & Access Management （IAM），身份和訪問管理，這是處理身份驗證、授權和訪問控制的服務。
Data Store 數據存儲，存儲和檢索對象數據，所有和數據有關的操作都是基於對象 ID（UUID）。
Metadata Service 元數據服務，存儲對象的元數據。

接下來我們一起來探索對象存儲中的一些重要的工作流程。

上傳對象
下載對象
版本控制

上傳對象

在上面的流程中，我們首先創建了一個名為 “bucket-to-share” 的存儲桶，然後把一個名為 “script.txt” 的文件上傳到這個桶。

客戶端發送一個創建「bucket-to-share」桶的 HTTP PUT 請求，經過負載均衡器轉發到 API 服務。
API 服務調用 IAM 確保用戶已獲得授權並且有 Write 權限。
API 服務調用元數據服務，創建存儲桶，並返回成功給客戶端。
客戶端發送創建「script.txt」對象的 HTTP PUT 請求。
API 服務驗證用戶的身份並確保用戶對存儲桶具有 Write 權限。
API 服務把 HTTP 請求發到到數據存儲服務，完成存儲後返回對象的 UUID。
調用元數據服務並創建元數據項，格式如下

上傳數據的 Http 請求示例如下

下載對象

存儲對象可以通過 HTTP GET 請求進行下載，示例如下

下載流程圖

客戶端發送 GET 請求，GET /bucket-to-share/script.txt
API 服務查詢 IAM 驗證用戶是否有對應桶的讀取權限。
驗證後，API 服務會從元數據服務中獲取對象的 UUID。
通過對象的 UUID 從數據存儲中獲取相應的對象。
API 服務返回對象給客戶端。

深入設計

接下來，我們會討論下面幾個比較重要的部分。

數據一致性
元數據
版本控制
優化大文件的上傳
垃圾收集 GC

數據一致性

對象數據只存放在單個節點肯定是不行的，為了保證高可用，需要把數據複製到多個節點。這種情況下，我們需要考慮到一致性和性能問題。

保證強一致性就要犧牲性能，如果性能要求比較高時，可以選擇弱一致性。魚和熊掌不可兼得。

數據存儲方式

對於數據存儲，一個簡單的方式是把每個對象都存儲在一個獨立的文件中，這樣當然是可以的。但是，當有大量的小型文件時，會有下面兩個問題。

第一個問題是，會浪費很多數據塊。文件系統把文件存儲在磁盤塊中，磁盤塊的大小在卷初始化的時候就固定了，一般是 4 kb。所以，對於小於 4kb 的文件，它也會佔滿整個磁盤塊。如果文件系統中保存了大量的小文件，那就會就會有很多浪費。

第二個問題是，系統的 inode 容量是有限的。文件系統把文件元數據存儲在 inode 特殊類型的磁盤塊中。對於大多數文件系統，inode 的數量在磁盤初始化時是固定的。所以有大量的文件時，要考慮到 inode 容量滿的問題。

為了解決這個問題，我們可以把很多小文件合併到一個更大的文件中。從概念上講，類似於預寫日誌（WAL）。當我們保存一個對象時，它被附加到一個現有的文件中。文件大小達到一定值（比如說 1 GB）後，創建一個新的文件來存儲對象，下圖解釋了它的工作流程。

數據持久性

對存儲系統來說，數據持久性非常重要，如何設計出一個 6 個 9 (99.9999%) 持久性的存儲系統？

硬件故障和故障域

無論使用哪種存儲，硬件故障都是不可避免的。所以為了數據持久性，需要把數據複製到多個硬盤中。

假設硬盤的年故障率是 0.81 %, 當然不同的型號和品牌這些是不一樣的，那個我們需要三個數據副本，1-(0.0081)^3=~0.999999, 才可以滿足要求。

另外，我們還需要考慮到不同故障域的影響。這樣可以在極端情況下，帶來更好的可靠性，比如大規模停電，自然災害等。

Erasure Coding 糾刪碼

上面提到，我們用三個完整的數據副本可以提供大概 6 個 9 的數據持久性，但是，這樣的成本太高了。

還能不能優化呢？我們可以使用糾刪碼技術，它的原理其實很簡單，假設現在有 a 和 b 兩條數據，進行異或（XOR）運算後得到 c，a ^ b = c , 而 b = c ^ a，a = c ^ b，所以這三條數據丟失任意一條數據，都可以通過剩餘兩條數據計算出丟失數據。

下面是一個 4 +2 糾刪碼的例子。

數據被分成四個大小均勻的數據塊 d1、d2、d3 和 d4。

使用 Reed-Solomon 數學公式計算校驗塊，比如

p1 = d1 + 2*d2 - d3 + 4*d4 
p2 = -d1 + 5*d2 + d3 - 3*d4

節點崩潰，導致數據 d3 和 d4 丟失。
通過數據公式和現有數據，計算出丟失的數據並恢復。
```
d3 = 3*p1 + 4*p2 + d1 - 26*d2
d4 = p1 + p2 - 7*d2
```

和多副本複製相比，糾刪碼佔用的存儲空間更少。但是，在進行丟失數據恢復時，它需要先根據現有數據計算出丟失數據，這也消耗了 CPU 資源。

數據完整性校驗

糾刪碼技術在保證數據持久性的同時，也降低的存儲成本。接下來，我們可以繼續解決下一個難題：數據損壞。

我們可以給數據通過 Checksum 算法計算出校驗和。常見的 checksum 算法有 MD5, SHA1 等。

當需要驗證數據時，只需要對比校驗和即可，如果不一致，說明文件數據發生了改變。

我們同樣可以把校驗和添加到存儲系統中，對於讀寫文件，每個對象都計算校驗和，而對於只讀文件，只需要在文件的末尾添加上整個文件的校驗和即可。

版本控制

版本控制可以讓一個對象的多個版本同時保存在存儲桶中。這樣的好處是，我們可以恢復意外刪除或者覆蓋的對象。

為了支持版本控制，元數據存儲的列表中需要有一個 object_version 的列。上傳對象文件時，不是直接覆蓋現有的記錄，而是插入一個新記錄。

當進行對象刪除的時候，不需要刪除這條記錄，而是添加一個刪除標記即可，然後等垃圾收集器自動處理它。

優化大文件上傳

對於比較大的對象文件（可能有幾個 GB），上傳可能需要較長的時間。如果在上傳過程中網絡連接失敗，就要重新進行上傳了。

為了解決這個問題，我們可以使用分段上傳，上傳失敗時可以快速恢復。

客戶端調用對象存儲服務發起分段上傳請求。
數據存儲服務返回一個唯一的 uploadID。
客戶端把大文件拆分為小對象並開始上傳，假設文件大小是 1.6 GB, 每個部分的大小是 200 MB, 客戶端上傳第一部分和 uploadID 。
上傳第一部分後，數據存儲服務會返回一個 ETag，本質上它是第一部分的 md5 校驗和，客戶端通過它來判斷數據是否發生了更改，如果是則重新上傳。
當每個部分都上傳成功後，客戶端發送一個分段上傳成功的請求。
數據存儲服務組裝小對象為大文件，並返回一個成功消息。

垃圾收集 GC

垃圾收集是自動回收不再使用的存儲空間的過程，數據可能變成垃圾的幾種方式：

延遲刪除的對象，對象在刪除時標記成已刪除，但實際上還沒有刪除。
孤兒數據，比如上傳一半的數據。
損壞的數據。

對於需要刪除的對象，我們使用壓縮機制定期清理，下圖顯示了它的工作流程。

垃圾收集器把對象「/data/b」複製到一個名為「/data/d」的新文件中。這裡會跳過對象 2 和 5，因為它們的刪除標誌都是 true。
複製完所有的對象後，垃圾收集器會更新 object_mapping 表，指向新的文件地址，然後刪除掉舊的文件。

總結

在本文中，介紹了類似於 S3 的對象存儲，比較了塊存儲、文件存儲和對象存儲之間的區別，設計了對象上傳，對象下載，版本控制功能，並討論了兩種提高可靠性和持久性的方法：複製和糾刪碼，最後介紹了對象存儲的垃圾收集的工作流程。

希望這篇設計對象存儲的文章對大家有用！

Reference

[0] System Design Interview Volume 2:
//www.amazon.com/System-Design-Interview-Insiders-Guide/dp/1736049119

[1] Fibre channel: //en.wikipedia.org/wiki/Fibre_Channel

[2] iSCSI: //en.wikipedia.org/wiki/ISCSI

[3] Server Message Block: //en.wikipedia.org/wiki/Server_Message_Block

[4] Network File System: //en.wikipedia.org/wiki/Network_File_System

[5] Amazon S3 Strong Consistency: //aws.amazon.com/s3/consistency/

[6] Serial Attached SCSI: //en.wikipedia.org/wiki/Serial_Attached_SCSI

[7] AWS CLI ls command: //docs.aws.amazon.com/cli/latest/reference/s3/ls.html

[8] Amazon S3 Service Level Agreement: //aws.amazon.com/s3/sla/

[9] Ambry: LinkedIn』s Scalable Geo-Distributed Object Store:
//assured-cloud-computing.illinois.edu/files/2014/03/Ambry-LinkedIns-Scalable-GeoDistributed-Object-Store.pdf

[10] inode: //en.wikipedia.org/wiki/Inode

[11] Ceph』s Rados Gateway: //docs.ceph.com/en/pacific/radosgw/index.html

[12] grpc: //grpc.io/

[13] Paxos: //en.wikipedia.org/wiki/Paxos_(computer_science)

[14] Raft: //raft.github.io/

[15] Consistent hashing: //www.toptal.com/big-data/consistent-hashing

[16] RocksDB: //github.com/facebook/rocksdb

[17] SSTable: //www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

[18] B+ tree: //en.wikipedia.org/wiki/B%2B_tree

[19] SQLite: //www.sqlite.org/index.html

[20] Data Durability Calculation: //www.backblaze.com/blog/cloud-storage-durability/

[21] Rack: //en.wikipedia.org/wiki/19-inch_rack

[22] Erasure Coding: //en.wikipedia.org/wiki/Erasure_code

[23] Reed–Solomon error correction: //en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

[24] Erasure Coding Demystified: //www.youtube.com/watch?v=Q5kVuM7zEUI

[25] Checksum://en.wikipedia.org/wiki/Checksum

[26] Md5: //en.wikipedia.org/wiki/MD5

[27] Sha1: //en.wikipedia.org/wiki/SHA-1

[28] Hmac: //en.wikipedia.org/wiki/HMAC

[29] TIMEUUID: //docs.datastax.com/en/cql-oss/3.3/cql/cql_reference/timeuuid_functions_r.html