【系統設計】S3 物件儲存

在本文中，我們設計了一個類似於 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:
https://www.amazon.com/System-Design-Interview-Insiders-Guide/dp/1736049119

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

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

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

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

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

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

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

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

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

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

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

[12] grpc: https://grpc.io/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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