System Design Interview Vol. 2 · 第 9 章Triton 覆蓋度:🟠 低Triton 線

S3-like Object Storage
把 100 PB 的東西寄放好,一個 bit 都不能壞

原書從零設計一個像 Amazon S3 的物件儲存:metadata 和資料分開放、小物件合併成大檔、三副本或 erasure coding、checksum、versioning、multipart upload、垃圾回收。Triton 沒有設計過物件儲存,他只「用」過 S3。所以這份簡報以把原書講清楚為主,最後幾頁只在他談 data page、SSTable、RAID、streaming、分頁的原則真的用得上的地方加卡片,多數標 🔭。

給文組

全程用「機場行李寄放處」比喻,一階一階爬 13 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。三十多個小互動:殺掉節點、翻一個 bit、斷線後續傳。

給工程師

原書 26 張圖、Table 1–5、Listing 1–3 全部依描述重繪或重排;數字都照原書,原書前後不一致處在圖說註明。最後一頁列出出處。

標籤怎麼看

📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 💬 作者未標示 📅 2026 補充

先用生活理解三種儲存,三種寄放方式

租倉庫格子、圖書館書架、機場行李寄放

同一本相簿,三種地方的放法完全不同。你得到的彈性越少,對方能替你管的就越多:存得越多、越便宜、越不怕壞。

對照表

  • Block = 租一整排空格子,哪格放什麼你自己記(資料庫、VM 自己管)
  • File = 圖書館,照「資料夾/檔名」的路徑放,大家都找得到,也能改
  • Object = 機場行李寄放:整件交出去拿一張號碼牌(ID),附一張標籤(metadata);要改只能整件換新

這章要設計的就是那個寄放處:一年收 100 PB 的行李,一百萬件裡掉一件都不行。

學習地圖本章的概念階梯

今天爬 13 階。每一階只用前面講過的東西。

  1. 1block / file / object三種寄放法
  2. 2bucket / key櫃位與號碼牌
  3. 3durability幾個 9
  4. 4metadata登記簿 vs 倉庫
  5. 5data node倉庫與調度員
  6. 6replication抄幾份才算數
  7. 7小物件合併明信片進資料夾
  8. 8failure domain別放同一棟
  9. 9erasure coding1 + 1 + 1 = 3
  10. 10checksum封條上的指紋
  11. 11versioning舊版留著
  12. 12multipart分箱搬家
  13. 13GC定期整理架子

第 1–4 階 · 寄放處長什麼樣

要回答:物件儲存跟硬碟、資料夾差在哪?

第 5–7 階 · 倉庫怎麼放

要回答:一件行李放哪幾間倉庫?小信封怎麼放?

第 8–10 階 · 一件都不能掉

要回答:倉庫燒了、bit 翻了怎麼辦?

第 11–13 階 · 改版、大件、清垃圾

要回答:同名再寄、大檔斷線、刪掉的空間怎麼收?

全程只用一家:機場行李寄放處

寄放處 = object storage櫃位 = bucket行李 = object行李的名字 = key櫃台登記簿 = metadata store後面的倉庫 = data node調度員 = placement service「總和紙」 = parity

每爬 3–4 階,有一頁「到這裡你已經會了」。13 階走完,最後八頁是 Triton。

路線圖Triton 覆蓋度:🟠 低

這份簡報怎麼走

📖 原書 Storage 101 與 Step 1–2

  • S3 的歷史、三種儲存、Figure 1、Table 1(第 6–7 頁)
  • 術語與 SLA(10)
  • 需求、估算(11–12)
  • 物件儲存的特性、inode、Figure 2–3(13–15)
  • 高階設計、上傳、下載、Figure 4–6(16–19)

📖 原書 Step 3 深入

  • Data store:routing、placement、data node、Figure 7–11(22–27)
  • 資料怎麼組織、object lookup、Figure 12–13 與動手玩(29–32)
  • Durability:failure domain、erasure coding、checksum、Figure 14–20(35–42)
  • Metadata、listing、versioning、multipart、GC、Figure 21–26(44–54)
  • Wrap up 與章節總結圖(56)

🔭 / 🗣️ Triton 八頁

  • 他沒做過物件儲存,有什麼可以用(57)
  • 小檔合併 = RDBMS data page(58)、immutable + 合併 = SSTable(59)
  • 三副本的數學 vs 泡麵(60)
  • metadata 放 RDBMS(61)、stream(62)、分頁(63)、他怎麼用 S3(64)

為什麼覆蓋度是「低」:materials/core 裡沒有任何談物件儲存設計的講義或文章。能用的是 Triton 在 RDBMS 底層、NoSQL、RAID 與備份、IO streaming、分頁這些別的情境講的話。原書 data node 的設計剛好和這些原理同源,所以原文照引,但「套到物件儲存」一律標 🔭。

延伸基礎第 1 階 · block / file / object懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

相簿 100 頁只換 1 頁:三種寄放法各要重寫多少?

① 先想像

一本 100 頁的相簿,分別放在租來的格子、圖書館、機場行李寄放處。現在想換掉第 3 頁。

你猜猜看:寄放處不讓你打開行李。換 1 頁,要重新寄放幾頁?

③ 這叫做 block、file、object storage

block:一排編號格子,哪格放什麼自己記。file:照資料夾路徑放,可以直接改。object:整件交出去,只能整件換新。

④ 跟這章的關係

這章要設計的是 object storage。「只能整件換新」會讓後面很多設計變簡單(第 13 頁)。

② 動手玩:換幾頁,要重寫幾頁?

Block 格子
1
File 圖書館
1
Object 寄放處
100
誰記得東西在哪誰替你抄備份、搬家
Block你自己你自己
File圖書館(路徑)大多你自己
Object寄放處(號碼牌)寄放處全包

原書開場 · Storage System 101 · Figure 1

S3 是什麼,三種儲存各長什麼樣

這一步要解決的問題物件儲存是怎麼來的?跟硬碟、資料夾差在哪?

📖 原書 關於 AWS S3

  • 透過 RESTful API 提供物件儲存,2006 年 6 月推出
  • 2010:versioning、bucket policy、multipart upload
  • 2011:server-side encryption、multi-object delete、object expiration
  • 2013:存了 2 兆個物件;2014–2015:life cycle policy、event notification、cross-region replication
  • 2021:超過 100 兆個物件
  • Block(1960 年代就有):HDD、SSD 這種接在 server 上的都是。把原始 block 當成一個 volume 交給 server,可以格式化成檔案系統,也可以讓 DB、VM engine 直接管 block 榨效能。透過 Fibre Channel、iSCSI 走網路接也一樣是 block。
  • File:蓋在 block 之上,用階層式目錄存檔案。用 SMB/CIFS、NFS 讓很多台 server 共用,不必管 block、格式化。最通用。
  • Object:新的。刻意犧牲效能,換高耐久、超大規模、低成本;主要放「冷」資料,用在 archival 和 backup。扁平結構、沒有目錄,走 RESTful API,比較慢。AWS S3、Google object storage、Azure blob storage。
📖 原書 Figure 1Three different storage options:block、file、object(依原書內容重繪)

白話:RESTful API=用網址加上 GET、PUT 這類動詞來存取;volume=一顆(虛擬的)硬碟;VM=在一台電腦裡模擬出來的另一台電腦;archival/backup=封存/備份。

原書Table 1 Storage options

三種儲存,七個面向比一比

這一步要解決的問題三種儲存各自擅長什麼?物件儲存故意放棄了哪些東西?

Block storageFile storageObject storage
Mutable ContentYYN(支援 object versioning,不支援 in-place update)
CostHighMedium to highLow
PerformanceMedium to high, very highMedium to highLow to medium
ConsistencyStrong consistencyStrong consistencyStrong consistency [5]
Data accessSAS / iSCSI / FCStandard file access, CIFS/SMB, NFSRESTful API
ScalabilityMedium scalabilityHigh scalabilityVast scalability
Good forVirtual machines (VM)、資料庫這類高效能應用General-purpose file system accessBinary data、unstructured data

📖 原書 Table 1Storage options(依原書內容重排)

動手選:這個東西該放哪?

點一個按鈕,表格會亮出該選的那一欄。

白話:SAS/iSCSI/FC=把硬碟接到機器上的幾種線路;CIFS/SMB、NFS=讓很多台電腦共用資料夾的方式;strong consistency=寫完馬上讀,一定讀到新的。

📖 原書 Object storage 的一致性欄寫 strong consistency,附註 [5] 是 AWS 的「Amazon S3 Strong Consistency」頁。

📅 2026 補充 S3 是在 2020 年 12 月才改成所有 GET/LIST 都 strong read-after-write;更早的書和部落格常寫 S3 是 eventual consistency,看資料時要注意年份。

延伸基礎第 2 階 · bucket / key懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

寄放處的櫃位、行李、和行李的名字

① 先想像

寄放處分成很多櫃位,每個櫃位掛一個名字,例如 ann-trip。行李寄在櫃位裡,再取一個名字,例如 album.zip。

你猜猜看:Ann 已經把櫃位取名 photos。住在別國的 Bob 也想叫 photos,可以嗎?

③ 這叫做 bucket、key

bucket:櫃位,裝物件的容器,名字全球唯一。key:物件在 bucket 裡的名字;/bucket/key 合起來就找得到它。

④ 跟這章的關係

原書的 URI /bucket-to-share/script.txt 就是 bucket + key(第 10、13 頁)。

② 動手玩:寄一件、再用名字領回來

別人已經用掉的櫃位名字:photos(Bob)、logs、backup


      

延伸基礎第 3 階 · durability懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

「一百萬件只會弄丟一件」是幾個 9?

① 先想像

寄放處貼出保證:「每年每一百萬件行李,最多只會弄丟 1 件。」

你猜猜看:換成百分比,行李「還在」的機率是?

③ 這叫做 durability

durability(耐久度):東西放進去,過一年還在不在。常念成「幾個 9」。

④ 跟這章的關係

S3 寫 11 個 9(下一頁),原書需求是 6 個 9(第 11 頁)。「現在拿不拿得到」是另一件事:availability,02 章講過。

② 動手玩:幾個 9、寄放幾件

1平均每年弄丟幾件1 年平均多久丟一件

原書Terminology

Bucket、Object、Versioning、URI、SLA

這一步要解決的問題往下講之前,先把整章天天出現的五個詞講好(前兩階已經玩過三個)。

  • Bucket:物件的邏輯容器,名稱全球唯一。上傳前一定要先建 bucket。
  • Object:存在 bucket 裡的一份資料,包含 object data(payload):任何 byte 序列;和 metadata:一組描述它的 name-value pair。
  • Versioning:同一個 bucket 裡保留一個物件的多個版本,以 bucket 為單位開啟,用來救回誤刪或被覆寫的物件。
  • URI:RESTful API 存取 bucket 和 object,每個資源由 URI 唯一識別。
  • SLA:服務提供者與客戶間的合約。原書舉 Amazon S3 Standard-Infrequent Access:
    • 跨多個 Availability Zone,設計耐久度 99.999999999%(11 個 9)
    • 整個 AZ 毀掉,資料仍在
    • 設計可用性 99.9%

原書的參考資料編號在這裡對調了:內文說 SLA 是 [7]、aws s3 ls 是 [8],但參考清單 [7] 是 ls 指令、[8] 才是 SLA。

11 個 9 到底多可靠?耐久度 ≠ 可用性

—平均多久掉一個物件—一年最多連不上

耐久度是「東西還在不在」:寄放處失火,你的行李有沒有燒掉。可用性是「現在拿不拿得到」:櫃台午休,行李還在但你今天拿不到。原書的 SLA 兩個數字差了 8 個 9,因為「拿不到」比「不見了」便宜得多。

白話:Availability Zone(AZ)=電和網路都獨立的一區機房(第 8 階細講);Standard-Infrequent Access=S3 裡「不常讀、比較便宜」的一種存法。

原書 Step 1Understand the problem and establish design scope

面試一開始:要做哪些功能、多大、多可靠

這一步要解決的問題要做哪些功能、存多少、多可靠?這幾個數字會決定後面所有設計。

📖 原書 應徵者 × 面試官

應徵者問面試官答
設計要包含哪些功能?Bucket 建立;物件上傳與下載;object versioning;列出 bucket 裡的物件(類似 aws s3 ls)
典型的資料大小?要有效率地存大型物件(幾 GB 以上),也要存大量小物件(幾十 KB)
一年要存多少資料?100 PB
可以假設資料耐久度 6 個 9(99.9999%)、服務可用性 4 個 9(99.99%)嗎?可以,聽起來合理

白話:PB=1,000 TB,100 PB 大約是 10 萬顆 1 TB 的硬碟;non-functional requirements=功能以外的要求:多大、多快、多可靠、多便宜。

📖 原書 Non-functional requirements

  • 100 PB 的資料
  • 資料耐久度 6 個 9
  • 服務可用性 4 個 9
  • Storage efficiency:維持高可靠性與效能的同時,降低儲存成本

文組翻譯

寄放處要收大行李箱也要收小信封;一年收 100 PB;一百萬件掉不到一件;一年櫃台關門不超過 53 分鐘;而且倉庫租金要省。最後這條會一路影響到 erasure coding(第 37 頁)。

原書 Step 1Back-of-the-envelope estimation

100 PB 能放多少個物件?瓶頸在容量或 IOPS

這一步要解決的問題100 PB 到底能放多少個物件?metadata 會有多大?先估出數量級。


      
—可存的物件數—metadata 總量

📖 原書 物件儲存的瓶頸可能在 disk capacity 或 disk IOPS:

  • 物件大小分布:20% 小(<1MB)、60% 中(1MB–64MB)、20% 大(>64MB);計算時各取中位數 0.5MB、32MB、200MB
  • 一顆 SATA、7200 rpm 硬碟每秒約 100–150 次 random seek(100–150 IOPS)
  • 100 PB = 100×1000×1000×1000 MB = 1011 MB;40% usage ratio
  • 1011×0.4 / (0.2×0.5 + 0.6×32 + 0.2×200) = 6.8 億個物件;metadata 每個約 1KB → 0.68 TB

原書:「就算最後用不到這些數字,對系統的規模和限制有個概念也好。」

實算 4×1010 / 59.3 ≈ 6.75 億,原書四捨五入寫 0.68 billion。

白話:IOPS=硬碟每秒能做幾次讀寫;random seek=讀寫頭跳到任意位置一次;usage ratio=硬碟實際能用掉的比例。數量級的讀法見 02 章。

原書 Step 2物件儲存的四個特性 · Listing 1

動手設計前,先看物件儲存「有什麼不必做」

這一步要解決的問題物件儲存有哪些事「不必做」?每一條限制,都替後面的設計省事。

1 · Object immutability

和另外兩種最大的差別:物件不可變。可以刪掉、可以整個換成新版本,但不能做增量修改。

2 · Key-value store

用 object URI 取資料:URI 是 key,object data 是 value。

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

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

[4567 bytes of object data]

📖 原書 Listing 1Use object URI to retrieve object data

3 · Write once, read many

寫一次、讀很多次。原書引 LinkedIn(Ambry 論文)的研究:95% 的 request 是讀。

4 · 大小物件都要支援

物件大小差很多:幾十 KB 的縮圖到幾 GB 的影片,兩種都要支援。這條會在第 29 頁(小物件合併)和第 52 頁(multipart)各解一次。

延伸基礎 · 複習第 4 階 · metadata懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

櫃台一本登記簿,後面一整排倉庫

① 先想像

櫃台有一本登記簿:「album.zip,Ann 的,在 3 號倉庫第 12 格」。行李本身放在後面的倉庫。

你猜猜看:倉庫有 1,000 個架子,櫃台沒有登記簿。找 Ann 的相簿平均要翻幾個?

④ 跟這章的關係

原書把登記簿叫 metadata store、倉庫叫 data store,兩邊分開設計(下一頁)。

② 動手玩:40 個架子,找一件行李

0翻了幾個架子

原書 Step 2和 UNIX 檔案系統一樣:名字和內容分開放 · Figure 2–3

inode 變成 metadata store,硬碟變成 data store

這一步要解決的問題檔案的「名字」和「內容」要放在一起嗎?UNIX 檔案系統早就給了答案。

📖 原書 Figure 2Unix file system and object store(依原書內容重繪)

📖 原書 UNIX 存檔案時,檔名不和內容放在一起:檔名放在叫 inode 的資料結構,裡面有一串 file block pointer 指到資料在磁碟上的位置。讀檔時先拿 inode 的 metadata,再照指標去讀資料。

📖 原書 物件儲存一樣:inode → metadata store,硬碟 → data store;file block pointer → object ID,差別是要透過網路請求去 data store 拿。

為什麼要分開

data store 存的是不可變的資料,metadata store 存的是會變的資料(名字、版本、權限)。分開之後兩邊可以各自實作、各自優化。寄放處版:行李放倉庫,登記簿放櫃台;倉庫要大要便宜,登記簿要好查。

白話:inode=檔案系統裡每個檔案的一張小卡,記資料在磁碟的哪幾格;UUID=亂數產生、幾乎不會撞號的編號(07 章)。

原書 Step 2High-level design · Figure 4

五個元件:LB、API service、IAM、data store、metadata store

這一步要解決的問題一個 request 進來,要經過哪些關卡才碰得到資料?先看全貌的五個元件。

📖 原書 Figure 4High-level design(依原書內容重繪)
  • Load balancer:把 RESTful API request 分給多台 API server。
  • API service:協調對 IAM、metadata service、storage 的 RPC。stateless,可以水平擴展。
  • IAM:authentication(你是誰)、authorization(依你是誰,能做哪些操作)、access control 的中央。
  • Data store:存取實際資料,所有操作都用 object ID(UUID)。
  • Metadata store:存物件的 metadata。

📖 原書 metadata store 和 data store 只是邏輯元件,實作方式很多。例如 Ceph 的 Rados Gateway 沒有獨立的 metadata store,連 bucket 在內全部存成一或多個 Rados object。

接下來看三個工作流程:上傳、下載;versioning 與 listing 留到 deep dive。

白話:load balancer=帶位員(01 章);stateless=不記客人,換哪台都一樣(01 章);RPC=一台機器呼叫另一台機器上的功能;Ceph=一套開源的分散式儲存。

原書 Step 2Uploading an object · Figure 5

上傳:先建 bucket,再放 script.txt,共 7 步

這一步要解決的問題一個新物件寫進來:哪一步先、哪一步後?順序反過來會怎樣?

📖 原書 Figure 5Uploading an object(依原書內容重繪)
  1. Client 送 HTTP PUT 建立名為 bucket-to-share 的 bucket,轉給 API service
  2. API service 呼叫 IAM,確認使用者已授權、有 WRITE 權限
  3. API service 呼叫 metadata store,在 metadata DB 建一筆 bucket 資訊;建好就回成功給 client
  4. Client 送 HTTP PUT 建立物件 script.txt
  5. API service 驗證身份,確認使用者對這個 bucket 有 WRITE 權限
  6. 驗證通過,API service 把 PUT payload 的物件資料送到 data store;data store 存成物件,回傳 UUID
  7. API service 呼叫 metadata store 建一筆新 entry:object_id(UUID)、bucket_id、object_name 等(Table 2)

一個物件一定住在某個 bucket 裡,所以要先有 bucket。

原書 Step 2Table 2 · Listing 2

上傳的 API 長這樣,寫進 metadata 的那一筆長這樣

這一步要解決的問題上傳時 client 實際送出什麼?登記簿裡又多了哪一行?


      

📖 原書 Listing 2Uploading an object(可編輯版;預設值照原書)

object_nameobject_idbucket_id
script.txt239D5866-0052-00F6-014E-C914E61ED42B82AA1B2E-F599-4590-B5E4-1F51AAE5F7E4

📖 原書 Table 2Sample entry;按「送出 PUT」會多一列(新 UUID 由瀏覽器隨機產生)

讀懂這個 request

  • PUT /bucket-to-share/script.txt:URI 就是 key
  • Authorization:給 IAM 驗身份
  • Content-Length: 4567:payload 有多大
  • x-amz-meta-author: Alex:使用者自訂的 metadata(name-value pair)

原書 Step 2Downloading an object · Listing 3 · Figure 6

下載:先用名字查 UUID,再用 UUID 拿資料

這一步要解決的問題data store 只認 UUID、不認名字。那用名字下載要怎麼做?

📖 原書 Figure 6Downloading an object(依原書內容重繪)
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

📖 原書 Listing 3Downloading an object

  1. Client 送 GET /bucket-to-share/script.txt 到 load balancer
  2. API service 問 IAM:使用者對這個 bucket 有 READ 權限嗎
  3. 通過後,API service 從 metadata store 拿到物件的 UUID
  4. API service 用 UUID 從 data store 拿物件資料
  5. API service 在 HTTP GET response 回傳物件資料

📖 原書 bucket 沒有目錄階層,但可以把 bucket 名和物件名串起來模擬資料夾,例如物件叫 bucket-to-share/script.txt。data store 不存物件名稱,只認 UUID,所以下載一定先查 metadata。

到這裡你已經會了小結 1 / 4

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

到這裡你已經會了:寄放處長什麼樣

下一階要解決的問題

倉庫後面長什麼樣?一件行李要放幾間、放哪幾間?小信封又怎麼放?

延伸基礎第 5 階 · data node / placement懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

倉庫有好幾間:新行李放哪幾間?誰決定?

① 先想像

寄放處有 4 間倉庫,每間每 5 秒打卡一次「我還在」。調度員看著一張表:每間剩幾格、多久沒打卡。

你猜猜看:寬限 15 秒。C 倉庫已經 20 秒沒打卡,空位又最多。新行李會派給 C 嗎?

③ 這叫做 data node、placement service

data node:真正放資料的機器(倉庫)。placement service:調度員,決定新資料放哪幾台。打卡就是 heartbeat(12 章)。

④ 跟這章的關係

原書的 data store 有三個角色:搬運工(routing)、調度員(placement)、倉庫(data node),第 22–24 頁。

② 動手玩:每件行李放 3 間

原書 Step 3Design deep dive · Data store · Figure 7–8

Data store 對外只有兩件事:給我資料換 ID、給我 ID 換資料

這一步要解決的問題data store 裡面還要再拆:誰決定放哪、誰真的存、誰負責搬?

📖 原書 Figure 7Upload and download an object(依原書內容重繪)

白話:gRPC=另一種機器之間互相呼叫的格式;cluster=一群一起分工的機器。

📖 原書 Deep dive 六個主題:data store、metadata data model、listing objects、object versioning、大檔上傳優化、garbage collection。

Data routing service

提供 RESTful 或 gRPC API 存取 data node cluster;stateless,加機器就能擴展。三個工作:

  • 問 placement service:哪個 data node 最適合存
  • 從 data node 讀資料回給 API service
  • 把資料寫到 data node

寄放處版:routing 是搬運工,placement 是調度員(知道每個倉庫在哪、還有沒有空),data node 是倉庫本身。

原書 Step 3Placement service · Virtual cluster map · Figure 9

調度員手上有一張地圖:哪個機房、哪台主機、哪個 partition

這一步要解決的問題調度員怎麼知道哪些倉庫還活著?副本要怎麼放才夠分散?

📖 原書 Figure 9Virtual cluster map(依原書內容重繪;每台 host 的 partition 數 alt 未給,畫 3 個)
—距上次心跳(模擬時鐘,3 倍速)

📖 原書 Placement service 決定物件要存在哪些 data node(primary 和 replicas)。它維護一張 virtual cluster map,記錄 cluster 的實體拓撲,用來確保副本在物理上分開,這是高耐久的關鍵(第 35 頁)。

📖 原書 它用 heartbeat 持續監控所有 data node:超過可設定的 15 秒寬限期沒收到心跳,就在 map 上標成 down。

試試看:拔掉 Host-3 的網路線,模擬時鐘走到 15 秒時,它底下的 partition 全變灰,placement service 不會再把新資料派給它。

白話:topology=哪台機器在哪個機房的地圖;partition=一台機器的磁碟再分成的幾區;heartbeat=定時打卡「我還在」。

原書 Step 3Placement service 的 HA · Data node 的心跳

調度員不能只有一個:5 或 7 台,過半數活著就能用

這一步要解決的問題調度員自己壞了怎麼辦?調度員也要有好幾位,而且要能投票。

📖 原書 Placement service cluster

這是關鍵服務,原書建議用 Paxos 或 Raft 共識協議建 5 或 7 台的 cluster:只要超過半數健康,整體就能運作。7 台可以容忍 3 台故障。

點節點讓它當機

白話:Paxos、Raft=讓好幾台機器投票、過半數同意才算數的規則(consensus,共識);daemon=一直在背景跑的小程式。

📖 原書 Data node 與它的心跳

Data node 存實際的物件資料,把資料複製到多個 data node(一個 replication group)來確保可靠與耐久。每台上面跑一個 data service daemon,持續送心跳給 placement service,內容包含:

  • 這台管幾顆磁碟(HDD 或 SSD)
  • 每顆磁碟存了多少資料

placement service 第一次收到某台的心跳時,替它指派 ID、加進 virtual cluster map,並回傳:

  • 這台 data node 的唯一 ID
  • virtual cluster map
  • 資料要複製到哪裡

延伸基礎 · 複習第 6 階 · replication懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

一件行李存三份:等幾份存好,才跟客人說「好了」?

① 先想像

行李進了第一間倉庫,再抄到另外兩間。三間存好的時間不一樣:10、20、150 毫秒(示意)。

你猜猜看:要等三間都存好才回客人,客人要等多久?

④ 跟這章的關係

原書 Figure 10 等三台都好;Figure 11 比較三種等法(第 26–27 頁)。

② 動手玩:調三間的速度,選要等幾間

150 ms客人要等3 份回「好了」那一刻已存好的份數

原書 Step 3Data persistence flow · Figure 10

寫一筆資料:routing 問 placement,primary 抄給兩個 secondary

這一步要解決的問題一筆資料從進門到存好三份,路線怎麼走?誰給 UUID、誰抄給誰?

📖 原書 Figure 10Data persistence flow(依原書內容重繪)
  1. API service 把物件資料轉給 data store
  2. Data routing service 替物件產生 UUID,問 placement service 要存在哪個 data node;placement 查 virtual cluster map,回傳 primary
  3. Routing 把資料連同 UUID 直接送到 primary data node
  4. Primary 存到本地,再複製到兩個 secondary;全部複製成功才回應 routing
  5. 物件的 UUID(ObjId)回傳給 API service

📖 原書 第 2 步:給 UUID,placement 回傳 replication group。這個查詢必須是 deterministic,而且 replication group 增減時還要成立。常見實作是 consistent hashing(Vol.1 第 5 章)。

白話:deterministic=同樣的輸入永遠得到同樣的答案;consistent hashing=同一個 key 永遠算到同一組機器(05 章)。

原書 Step 3Trade-off between consistency and latency · Figure 11

要等幾個副本寫完才回「成功」?

這一步要解決的問題等三份都存好最安全,但也最慢。能不能少等幾份?代價是什麼?

📖 原書 Figure 11Trade-off between consistency and latency(依原書內容重繪;藍色粗線 = API service wait time,延遲數字為示意亂數)
  1. 三台都存好才算成功:best consistency、highest latency
  2. Primary + 一個 secondary 存好:medium consistency、medium latency
  3. Primary 存好就算:worst consistency、lowest latency

📖 原書 2 和 3 都是 eventual consistency。選項 1 的代價是「要等最慢的那個副本」。

按按看

每筆寫入:primary 約 5–15ms,每個 secondary 約 10–40ms,偶爾有一台卡 150ms。看三種選項的平均和最慢。

白話:latency=要等多久(02 章);eventual consistency=副本過一陣子才跟上(06 章)。

延伸基礎第 7 階 · 小物件合併懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

寄一張明信片,也要租一整個櫃子嗎?

① 先想像

寄放處最小的櫃子一格放得下 4 張明信片。有人只寄 1 張,也佔掉一整格。

你猜猜看:一張 1 KB、一格 4 KB。寄 1,000 張、一張一格,空間浪費幾成?

③ 這叫做 append、offset

append:新東西一律接在最後面。offset:從開頭數過來第幾個位置。記下「哪本、offset、多長」就找得回來。

④ 跟這章的關係

原書把很多小物件 append 到一個大檔,再用一張表記位置(第 29–32 頁)。

② 動手玩:一格 4 個位置

6用掉幾格75%浪費的空間

原書 Step 3How data is organized · Figure 12

一個物件一個檔?小檔案太多會出兩個問題

這一步要解決的問題幾十 KB 的小物件一個一個存成檔案,會撞到檔案系統的哪兩面牆?

—浪費的空間—用掉的 inode(示意上限 1 億)
📖 原書 Figure 12Store multiple small objects in one big file(依原書內容重繪)

📖 原書 問題一:浪費 block。檔案系統用固定大小的 block(通常約 4 KB,格式化時決定)存檔,小於 4 KB 的檔案也佔一整個 block。

📖 原書 問題二:超過 inode 容量。多數檔案系統的 inode 數量在初始化時就固定,幾百萬個小檔可能用光;而且即使積極 cache metadata,OS 也處理不好大量 inode。

📖 原書 解法:把很多小物件合併成一個大檔,概念像 WAL。存物件 = append 到目前的 read-write file;檔案到達門檻(通常幾 GB)就標成 read-only,開新的 read-write file。read-only 檔只能讀。

寫入必須序列化:物件在檔案裡一個接一個排,多核心並行處理寫入時得輪流寫,嚴重限制吞吐。解法:每個核心一個專用的 read-write file。

白話:block=檔案系統的固定大小格子;WAL=依序往後寫的流水帳;序列化=排隊一個一個來。

原書 Step 3Object lookup · Table 3–4

一個大檔塞了很多物件,怎麼用 UUID 找到其中一個?

這一步要解決的問題很多物件擠在同一個大檔裡,要怎麼用 UUID 找到其中一個?

📖 原書 data node 要知道三件事:物件在哪個檔、在檔裡的起始 offset、物件多大。

📖 原書 Table 3object_mapping table(原書以圖呈現,依內容重繪)
FieldDescription
object_id物件的 UUID
file_name包含這個物件的檔案名稱
start_offset物件在檔案中的起始位址
object_size物件的 byte 數

📖 原書 Table 4Object_mapping fields

RocksDB

file-based KV store,基於 SSTable:寫快、讀慢

Relational DB ✓

通常用 B+ tree storage engine:讀快、寫慢

📖 原書 存取模式是寫一次、讀很多次,所以選 relational database。

📖 原書 怎麼部署?mapping 的量很大,用一個大 cluster 服務所有 data node 可行但難管。注意 mapping 只屬於各自的 data node,不需要跨節點共享,所以每台 data node 各放一個簡單的 relational DB:原書選 SQLite,檔案型、口碑好。

寄放處版:每個倉庫門口一本自己的登記簿:「12 號行李,在 C 架、從第 340 格開始、佔 5 格」。這本登記簿不用跟別的倉庫共享。

白話:B+ tree=照順序分頁的索引,讀得快(07 章);SSTable=寫完不改、一批一批歸檔的檔(06 章);SQLite=一個檔案就是一個小資料庫。

原書 Step 3Updated data persistence flow · Figure 13

改版後的寫入:append 到大檔、寫一筆 mapping、回傳 UUID

這一步要解決的問題加了大檔和 mapping 表之後,存一個新物件的步驟變成什麼?

📖 原書 Figure 13Updated data persistence flow(依原書內容重繪;alt 寫表中那筆是 object 6,內文的步驟講 object 4,兩筆都畫)

📖 原書 data node 改了不少,重看一次存新物件的流程:

  1. API service 要求儲存新物件 “object 4”
  2. Data node service 把 “object 4” append 到 read-write file /data/c 的尾端
  3. 在 object_mapping 表插入 “object 4” 的一筆紀錄
  4. Data node service 回傳 UUID 給 API service

寄放處版:新行李一律擺到「現在這排架子」的最後面,然後在門口的登記簿寫一行「幾號、哪排、從第幾格開始、佔幾格」,再把號碼牌交回櫃台。

原書 Step 3 · 動手玩小物件合併 + object lookup

連按 PUT 把檔案寫滿,再用 UUID 找回其中一個

這一步要解決的問題自己動手:檔案怎麼寫滿、怎麼變 read-only、怎麼用 UUID 找回來?

PUT 做了什麼

  • append 到目前的 read-write file 尾端
  • object_mapping 多一列 (object_id, file_name, start_offset, object_size)
  • 檔案滿了(示範 6 格,真實是幾 GB)→ 標成 read-only,開新的 read-write file

GET 做了什麼

  • 用 UUID 查 object_mapping:一次 B+ tree 查詢
  • 從那個檔的 offset 讀 size 個 bytes:一次讀
  • data node 從頭到尾不需要物件名稱,名字只存在 metadata store

📖 原書 寫入要序列化,所以真實系統每個處理寫入的核心有自己的 read-write file(第 29 頁)。

到這裡你已經會了小結 2 / 4

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

到這裡你已經會了:倉庫怎麼放

下一階要解決的問題

硬碟一定會壞、整區會停電、bit 會偷偷翻掉。一百萬件掉不到一件,要怎麼做到?

延伸基礎第 8 階 · failure domain懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

三份影本,放在同一棟大樓的三個樓層,安全嗎?

① 先想像

護照影印三份,放在同一棟大樓的 1F、2F、3F。某天整棟大樓停電。

你猜猜看:停電那天,還拿得到幾份?

③ 這叫做 failure domain、AZ

failure domain:會一起壞的範圍(一台機器、一個機櫃、一個機房)。AZ(Availability Zone):電和網路都不共用的獨立機房區。

④ 跟這章的關係

原書把三份副本放到不同 AZ(第 35 頁);placement service 的地圖就是用來分散它們。

② 動手玩:點格子放 3 份,再製造災難

原書 Step 3Durability · Hardware failure and failure domain · Figure 14

硬碟一定會壞:抄三份,而且放在不同的地方

這一步要解決的問題硬碟一定會壞。要做到「一百萬件掉不到一件」,抄幾份、放哪裡?

📖 原書 Figure 14Multi-datacenter replication(依原書內容重繪)

📖 原書 選擇哪一層 failure domain 不會直接提高耐久度,但在大停電、冷卻失效、天災這類極端情況下可靠性更好。

📖 原書 不管用什麼媒介,硬碟壞是必然的,不能靠單一顆達成耐久目標。已證實有效的做法是複製到多顆;本設計複製 3 份。

原書:假設年故障率 0.81%(Backblaze 的數字,高度依廠牌型號),1 − (0.0081)3 ≈ 0.999999,「非常粗略的估計」。

📖 原書 Failure domain:關鍵服務出問題時,一起受影響的實體或邏輯區塊。一個 rack 共用網路交換器和電源 → rack-level;一台 server 共用主機板、CPU、電源、硬碟 → node-level。最大的例子是互不共用任何東西的 Availability Zone。

延伸基礎第 9 階 · erasure coding懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

1 + 1 + 1 = 3:多寫一張「總和紙」,掉一張就救得回來

① 先想像

一組密碼拆成三張紙條:1、1、1,交給三位朋友。你再寫一張「三張加起來是 3」,交給第四位。

你猜猜看:第二位朋友把紙條弄丟了。還知道上面寫什麼嗎?

③ 這叫做 parity、erasure coding

parity:用原始資料算出來的「總和紙」。erasure coding:資料切塊、多算幾張 parity,掉幾塊都算得回來。

④ 跟這章的關係

原書 4+2:4 塊資料、2 張 parity,任掉 2 塊都救得回(第 37 頁)。

② 動手玩:改數字、弄丟紙條、再算回來

點紙條讓它不見

抄三份
+200%
3 張 + 1 張總和
+33%

原書 Step 3Erasure coding · Figure 15

不抄整份:切成 4 塊,再多算 2 塊「備援」

這一步要解決的問題三副本要多付 200% 的倉庫錢。能不能少存一點,一樣不怕壞?(第 9 階 1+1+1=3 的放大版)

📖 原書 Figure 15Erasure coding(4 + 2)(依原書內容重繪)
  1. 資料切成四塊一樣大的 d1、d2、d3、d4
  2. 用數學公式算出 parity p1、p2。原書的簡化例子:p1 = d1 + 2·d2 − d3 + 4·d4,p2 = −d1 + 5·d2 + d3 − 3·d4
  3. d3、d4 因節點當機遺失
  4. 用已知的 d1、d2、p1、p2 解回 d3、d4

動手解:照原書公式,壞兩塊還救得回來嗎?

點方塊讓它遺失(最多 2 塊)

寄放處版:把一本相簿拆成 4 冊放 4 個倉庫,再額外寫 2 本「解題本」放另外 2 個倉庫。任兩個倉庫燒掉,都能從剩下 4 本推回來。

原書 Step 3(8+4) erasure coding · Extra space · Figure 16–17

(8+4):12 塊分散到 12 個 failure domain,壞 4 個都還在

這一步要解決的問題4+2 再放大:切更多塊、放更多地方,空間和速度怎麼取捨?

📖 原書 Figure 16(8+4) erasure coding(依原書內容重繪)

📖 原書 (8+4) 把資料平均切 8 塊、算 4 個 parity,12 塊一樣大,放在 12 個不同的 failure domain;數學保證最多 4 個節點掛掉還能重建。

📖 原書 代價:replication 只要從一個健康節點讀;erasure coding 至少要從 8 個健康節點讀。用更複雜、更慢的方案換更高耐久和更低儲存成本,對「主要成本就是儲存」的物件儲存可能值得。

📖 原書 額外空間:每 2 塊資料要 1 塊 parity → 50% overhead;三副本是 200% overhead。

📖 原書 耐久度:一樣假設年故障率 0.81%,依 Backblaze 的計算,erasure coding 可達 11 個 9(數學很複雜,見原書 [20])。

白話:overhead=為了不怕壞多付的空間;Backblaze=一家公開硬碟故障統計的雲端備份公司。

原書 Step 3 · 動手玩Replication vs erasure coding 模擬器

殺掉幾台節點,資料還在嗎?要付多少倉庫錢?

這一步要解決的問題自己動手比:三副本、4+2、8+4,各壞幾台還在?各付多少倉庫錢?

—實際佔用—額外開銷—正常讀要碰幾台—最多可壞幾塊

簡化的耐久度算法

假設各節點獨立、一年內壞了都不修。原書的 11 個 9 是 Backblaze 把「壞了會在幾天內重建」算進去的結果,所以會比這裡高。

也可以直接點節點

原書 Step 3Table 5 Replication vs erasure coding

五個面向:EC 贏在耐久和空間,replication 贏在其他三項

這一步要解決的問題兩種方法各贏在哪?原書最後選了哪一個?

ReplicationErasure coding
Durability6 個 9(資料複製 3 次)11 個 9(8+4 erasure coding)。Erasure coding wins
Storage efficiency200% storage overhead50% storage overhead。Erasure coding wins
Compute resource不需要計算。Replication wins計算 parity 要用較多運算資源
Write performance複製到多個節點,不需要計算。Replication wins寫入延遲增加:寫磁碟前要先算 parity
Read performance正常時從同一個副本讀;故障時從沒壞的副本讀,不受影響。Replication wins正常時每次讀都要從 cluster 的多個節點拿;故障時更慢,要先重建遺失的資料

📖 原書 Table 5Replication vs erasure coding(依原書內容重排)

📖 原書 總結:latency 敏感的應用廣泛用 replication;要壓低儲存成本常用 erasure coding。EC 便宜又耐久,但大幅增加 data node 設計的複雜度,所以本設計主要聚焦在 replication。

文組翻譯:三副本像把整本相簿影印三份,誰要看隨手拿一本;EC 像把相簿拆冊再加解題本,省倉庫,但每次看都要從 8 個倉庫調冊子回來拼。

延伸基礎第 10 階 · checksum懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

行李封條上寫一個「指紋」,領取時再算一次

① 先想像

寄放時,櫃台把清單上的數字加起來,總和寫在封條上。領取時再加一次,對不上就知道被動過。

你猜猜看:清單 3、5、2,封條寫 10。領取時清單變成 3、6、2,對得上嗎?

③ 這叫做 checksum、bit flip

checksum:用資料算出的一小段指紋,用來發現資料壞了。bit flip:電腦裡一個 0 偷偷變成 1。算指紋的方法就是 hash(15 章)。

④ 跟這章的關係

原書每個物件尾端附 MD5 checksum(第 42 頁)。parity 是「救回來」,checksum 是「發現壞了」。

② 動手玩:點數字讓它 +1,或把前兩個對調

原書 Step 3Correctness verification · Figure 18–20

硬碟整顆壞了看得出來;一個 bit 偷偷翻掉呢?

這一步要解決的問題硬碟沒壞,但資料裡一個 bit 偷偷翻了,要怎麼發現?

📖 原書 磁碟整顆壞掉、偵測得到,就當成 data node 故障,用 EC 重建。但大型系統裡 in-memory data corruption 是常態。解法:在process 邊界之間驗證 checksum:一小塊用來偵測錯誤的資料。不同 → 損壞;相同 → 極可能沒壞(不是 100%,實務上當成相同)。

📖 原書 Figure 18Generate checksum(依原書內容重繪)

📖 原書 演算法有 MD5、SHA1、HMAC 等,好的演算法輸入改一點輸出就差很多;本章選 MD5。每個物件尾端附 checksum;檔案標成 read-only 前,再在尾端加整個檔案的 checksum。

白話:process 邊界=資料從一個程式交給另一個程式的那一刻;in-memory=在記憶體裡;HMAC=加了密碼的指紋算法。

動手翻一個 bit


        

📖 原書 (8+4) + checksum 的讀取流程

  1. 拿物件資料和 checksum
  2. 對收到的資料算 checksum:(a) 相同 → 沒錯;(b) 不同 → 損壞,改從其他 failure domain 讀
  3. 重複 1、2 直到 8 塊都拿到,重建資料回給 client

到這裡你已經會了小結 3 / 4

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

到這裡你已經會了:一件都不能掉

下一階要解決的問題

回到櫃台的登記簿:幾億筆 metadata 怎麼分、怎麼列出?同名再寄、大件斷線、刪掉的空間又怎麼辦?

原書 Step 3Metadata data model · Schema · Figure 21

兩張表:bucket 和 object,要撐三種查詢

這一步要解決的問題登記簿要有哪些欄位,才撐得起三種查詢?表太大時又怎麼辦?

📖 原書 三種查詢

  1. 用物件名稱找 object ID
  2. 用物件名稱插入、刪除物件
  3. 列出 bucket 裡共用同一個 prefix 的物件
📖 原書 Figure 21Database tables(依原書內容重繪;alt 說 object 表「五個欄位」但只列出四個;後面 SQL 用的是 bucket_id)

📖 原書 Scale the bucket table

使用者能建的 bucket 數通常有上限,所以這張表很小。

整張表輕鬆放進一台現代 DB server。但一台可能 CPU 或網路頻寬不夠應付所有讀取 → 把讀分散到多個 read replica。

📖 原書 Scale the object table:object 表存物件 metadata,這個規模很可能放不進單一 DB instance,要 sharding。下一頁看三種 shard key。

白話:schema=表格有哪些欄位;read replica=只負責讀的抄本;sharding=把一張大表切到很多台(01 章)。

原書 Step 3 · 動手玩Scale the object table · Sharding key

object 表要用什麼 shard key?三個候選

這一步要解決的問題object 表太大要切。依哪一欄切,才會又平均又好查?

📖 原書 依 bucket_id:同一個 bucket 的物件都在同一個 shard。不行:一個 bucket 可能有幾十億個物件,造成 hotspot shard。

📖 原書 依 object_id:負載平均。但查詢 1、2 都是用 URI(名字),沒辦法有效率地執行。

📖 原書 選 bucket_name + object_name 的組合:大部分 metadata 操作都基於 URI(用 URI 查 ID、用 URI 上傳),為了平均分佈,用 hash(bucket_name, object_name) 當 shard key。

這樣查詢 1、2 很直接,但查詢 3(列出同 prefix 的物件)就不明顯了 → 下兩頁。

白話:shard key=決定一筆資料去哪一台的那一欄;hotspot=大家都擠向同一台(05 章)。

原書 Step 3Listing objects in a bucket · Prefixes

沒有資料夾,只有「名字開頭一樣」

這一步要解決的問題物件儲存沒有資料夾,那 aws s3 ls 列出來的「資料夾」是怎麼來的?

📖 原書 物件儲存是扁平結構。路徑格式 s3://bucket-name/object-name,例如 s3://mybucket/abc/d/e/f/file.txt:bucket name 是 mybucket,object name 是 abc/d/e/f/file.txt。

📖 原書 S3 引入 prefix:物件名稱開頭的字串,用類似目錄的方式組織,但 prefix 不是目錄。上例的 prefix 是 abc/d/e/f/。

📖 原書 aws s3 listing 的三種用法

  1. 列出使用者所有 bucket:aws s3 list-buckets
  2. 列出和 prefix 同一層的物件:aws s3 ls s3://mybucket/abc/;prefix 後面還有斜線的,會捲成一個 common prefix
  3. 遞迴列出同 prefix 的全部物件:aws s3 ls s3://mybucket/abc/ --recursive

白話:prefix=名字開頭那一段;common prefix=把後面還有斜線的名字收成一行;recursive=連底下每一層都列出來。

bucket 裡的物件(原書例子):


      

回傳:


      

單一資料庫的 SQL(rollup 在 application code 做):


    

原書 Step 3Single database · Distributed databases · Pagination

分片之後,翻頁要記住「每一個 shard 讀到哪」

這一步要解決的問題表切成很多片之後,「下一頁」要從哪裡接著讀?

SELECT * FROM bucket WHERE owner_id={id}

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

-- 第一頁(每頁 10 個)
SELECT * FROM object WHERE
bucket_id = "123" AND object_name LIKE `a/b/%`
ORDER BY object_name OFFSET 0 LIMIT 10
-- 第二頁:cursor 裡帶 offset = 10
... ORDER BY object_name OFFSET 10 LIMIT 10

📖 原書 分片後:metadata service 對每個 shard 跑同一句查詢,再彙整結果。可行,但分頁麻煩:每個 shard 回的筆數不一樣,彙整排序後只回 10 個,沒用上的下一輪要重新考慮 → 每個 shard 的 offset 都不同,server 要把所有 offset 跟 cursor 綁在一起。幾百個 shard 就要追幾百個 offset。

原書的第二頁 SQL 寫成 FROM metadata,和第一頁的 FROM object 不一致,這裡照原書。

白話:cursor=「下一頁從哪裡接」的書籤(11 章);OFFSET=跳過前面幾筆;denormalize=為了好查,同一份資料再多存一份。

📖 原書 取捨:物件儲存為規模和耐久優化,listing 效能很少是優先;所有商業物件儲存的 listing 效能都不算好。所以把 listing 資料 denormalize 到一張依 bucket ID 分片的獨立表,只用來 listing。即使幾十億物件的 bucket 也有可接受的效能,listing 查詢被隔離在一個 DB,大幅簡化實作。

延伸基礎第 11 階 · versioning懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

同名的行李再寄一次:舊的那件丟掉,還是留著?

① 先想像

Ann 寄了 album.zip,隔天又寄一本同名的新相簿。寄放處可以丟掉舊的,也可以在登記簿多寫一行,兩本都留。

你猜猜看:「留舊版」模式下,Ann 同名寄 3 次,再按刪除。倉庫裡還有幾本?

③ 這叫做 versioning、delete marker

versioning:同名再寄不覆蓋,每次多一個版本。delete marker:「已刪除」便條,它本身也是一個新版本。

④ 跟這章的關係

原書第 49–50 頁。不留舊版時,被蓋掉的那本變成垃圾,等第 13 階回收。

② 動手玩:寄、刪、領

登記簿(最新的在最上面)

0倉庫裡的相簿0等著回收的垃圾

原書 Step 3Object versioning · Figure 22

開了 versioning:同名再上傳,不覆蓋,多一筆

這一步要解決的問題同名再上傳,怎麼不蓋掉舊版?「目前版本」又怎麼找?

📖 原書 Figure 22Object versioning(依原書內容重繪;圖上編號照原書 alt,③ 上傳、④ 檢查)

📖 原書 沒有 versioning:同名存檔,metadata store 裡舊版 metadata 被新版取代,舊版被標成 deleted,空間由 garbage collector 回收。有 versioning:所有舊版都留在 metadata store,data store 裡的舊版永遠不會被標成 deleted。要先在 bucket 上開啟。

  1. Client 送 HTTP PUT 上傳 script.txt
  2. API service 驗證身份,確認有 bucket 的 WRITE 權限
  3. 驗證後把資料上傳到 data store,存成新物件,回傳新 UUID
  4. API service 呼叫 metadata store 存這個物件的 metadata
  5. object 表有一欄 object_version,只在開 versioning 時用:不覆寫舊紀錄,而是插入新的一列:同 bucket_id、object_name,新的 object_id 和 object_version(插入時產生的 TIMEUUID)

不管 metadata store 選哪種 DB,都要能有效率地查到目前版本:同 object_name 裡 TIMEUUID 最大的那筆。

白話:TIMEUUID=照時間排序的 UUID,越晚產生越大。

原書 Step 3 · 動手玩Versioned metadata · Delete marker · Figure 23–24

刪除也是一個新版本:delete marker

這一步要解決的問題開了 versioning,「刪除」要怎麼做才能反悔?

📖 原書 Figure 23Versioned metadata(依原書內容重繪)

📖 原書 刪除時所有版本都留在 bucket,另外插入一個 delete marker。delete marker 是物件的新版本,插入後就成為目前版本;目前版本是 delete marker 時 GET 回 404 Object Not Found。

延伸基礎第 12 階 · multipart upload懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

搬家路上翻車:全部重搬,還是只補那一箱?

① 先想像

搬家有 8 箱。一種是全部塞一台卡車一趟運完;另一種是分 8 趟,每箱貼編號,到了再照編號排好。

你猜猜看:1.6 GB 傳到 1.5 GB 斷線。一次傳要重傳多少?切 8 份(每份 200 MB)呢?

③ 這叫做 multipart upload、part

multipart upload:大檔切成很多份分開傳,最後照編號拼回來。part:切出來的一份。

④ 跟這章的關係

原書:1.6 GB 切 8 份、每份 200 MB,傳完用編號重組(第 52 頁)。

② 動手玩:選在哪裡斷線

200 MB斷線後要重傳1,700 MB總共傳了

原書 Step 3 · 動手玩Optimizing uploads of large files · Multipart upload · Figure 25

1.6 GB 傳到一半斷線:從頭來,還是只補沒傳完的?

這一步要解決的問題幾 GB 的大檔一次傳,斷線就要從頭來。怎麼辦?

0總共傳了(MB)—狀態

    
📖 原書 Figure 25Multipart upload(依原書內容重繪)
  1. Client 呼叫物件儲存,initiate multipart upload
  2. Data store 回傳唯一的 uploadID
  3. Client 切成小物件上傳:1.6GB 切 8 份、每份 200 MB,連同 uploadID 上傳
  4. 每份上傳完,data store 回傳 ETag(本質上是那一份的 md5 checksum)
  5. 全部傳完,送 complete:uploadID、part number、ETag
  6. Data store 依 part number 重組(物件很大,可能要幾分鐘),回傳成功

白話:ETag=每一份的指紋;part number=每一份的編號。

延伸基礎第 13 階 · garbage collection懂的人可以跳過

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

取消寄放的行李:先貼紅標,每週一起清

① 先想像

有人取消寄放,櫃員不會馬上進倉庫搬,只在那一格貼紅標。每週一次,把沒貼紅標的搬到一排新架子,舊架子整排清空。

你猜猜看:一排 8 格,有 3 格貼紅標。整理後新架子要幾格?

③ 這叫做 garbage collection、compaction

garbage collection(GC):定期回收沒人要的資料。compaction:把活的搬到新檔、排緊,舊檔整個丟掉。

④ 跟這章的關係

原書的垃圾有三種:刪掉的、傳一半的、壞掉的(第 54 頁)。

② 動手玩:點格子貼紅標,再整理

舊架子

新架子

—搬了幾件—空出幾格

原書 Step 3 · 動手玩Garbage collection · Compaction · Figure 26

刪掉的不馬上刪:等一批 read-only 檔,一次搬家壓實

這一步要解決的問題刪掉的、傳一半的、壞掉的資料,什麼時候清?怎麼清才省事?

點物件切換 delete flag

白話:orphan data=沒有登記簿指著的資料;transaction=幾個修改要嘛全成功、要嘛全不算(07 章)。

📖 原書 會變成垃圾的三種資料:Lazy object deletion(刪除時只標記)、Orphan data(傳一半的資料、被放棄的 multipart)、Corrupted data(checksum 驗證失敗)。GC 不會立刻從 data store 移除,而是定期用 compaction 清。副本也要清:replication 從 primary 和 backup 都刪;(8+4) 要從 12 個節點都刪。

📖 原書 Figure 26Compaction(依原書內容重繪;alt 沒給 obj_size,畫成不變)
  1. GC 把 /data/b 的物件複製到新檔 /data/d,跳過 delete flag 為 true 的 Object 2、Object 5
  2. 複製完更新 object_mapping:Object 3 的 obj_id、object_size 不變,file_name、start_offset 改成新位置;這兩欄的更新包在一個 DB transaction 裡

新檔比舊檔小。為了不製造一堆小檔,GC 通常等到有很多 read-only 檔才壓,把多個檔的物件 append 到少數幾個大的新檔。

到這裡你已經會了小結 4 / 4

  1. block / file / object
  2. bucket / key
  3. durability
  4. metadata
  5. data node
  6. replication
  7. 小物件合併
  8. failure domain
  9. erasure coding
  10. checksum
  11. versioning
  12. multipart
  13. GC

到這裡你已經會了:改版、大件、清垃圾

13 階全部走完了

下一頁是原書的收尾。之後是 Triton 的八頁:他沒做過物件儲存,但講 RDBMS 怎麼存資料時,講過同樣的取捨。

原書 Step 4Wrap up · Chapter summary

原書的收尾:一張心智圖

這一步要解決的問題整章收起來:哪些是骨架、哪些是原書自己承認的取捨?

📖 原書 Chapter Summary章節總結心智圖(依原書內容重繪)

📖 原書 本章介紹類似 S3 的物件儲存高階設計,比較了 block、file、object 三種儲存。

📖 原書 面試重點是物件儲存本身,所以列出上傳、下載、listing、versioning 通常怎麼做。

📖 原書 深入設計:物件儲存由 data store 和 metadata store 組成。說明資料怎麼持久化到 data store,以及提高可靠與耐久的兩種方法:replication 和 erasure coding。metadata store 說明了 multipart upload 怎麼執行、schema 怎麼撐典型用例,最後怎麼 shard 撐更大的量。

原書最後一句:「恭喜你看到這裡!拍拍自己的背,做得好!」

補充 · Triton 線先說清楚:他沒有做過物件儲存

Triton 沒設計過 S3,但他講 RDBMS 怎麼存資料時,講過同樣的取捨

沒有的

  • 沒有任何談物件儲存、erasure coding、placement service、multipart 的講義或文章
  • 沒有評論過 S3 的架構,也沒評論過原書這章
  • 所以這章沒有「Triton 不同意」那種直球頁

有的(都是別的主題)

  • RDBMS 為什麼不一筆一個檔、data page 的 metadata 與 checksum(070、054、015)
  • SSTable 為什麼 immutable、背景合併;HDFS、HBase coordinator(080)
  • RAID、replication 擋不住什麼,離線備份(073、074、019)
  • blob 外置、metadata 放 RDBMS、先 scale up(181、144、106、073)
  • 檔案當 stream、分頁 cursor(130、128、049、062、087、104)
  • 他在 HYPEBEAST 怎麼用 S3、EFS(046、051、076;085 作者未標示)

怎麼標

原文一律照引並附檔名,標 🗣️;「這句話套到物件儲存是什麼意思」一律標 🔭,不寫成「Triton 認為 S3 應該……」。085 沒有署名,標 💬。

一句話預告:原書 data node 的三個核心決定(小物件合併成大檔、檔案寫滿就 read-only 再背景壓實、每塊附 checksum),和 Triton 講 RDBMS/SSTable 底層時描述的是同一組物理限制。這是本章 Triton 線最站得住的地方,也大多是「同意」。

補充 · Triton 線070 · 054 · 015 · 小檔合併 = RDBMS 早就這樣做

「一筆資料一個檔」是 RDBMS 課第一個被淘汰的幻想

你猜猜看:原書把小物件一個接一個 append 進大檔。Triton 在 RDBMS 課講過這種「巨型檔案」,delete 之後會留下什麼?

「即使檔案只有 1bytes,在以 4KB為區塊大小的檔案系統中,他還是用掉了 4KB」「幻想中的儲存方式1:RDBMS為每一 Record建立檔案 – 大量的空間會被浪費 … – 大量的 file descriptor會浪費大量系統資源」「幻想中的儲存方式 2:RDBMS建立一個巨型的檔案…把同一 table內的 Record緊密地(一個接一個地)存到這個連續性的空間內。在初期階段,這的確最節省空間還有 IO啦 – 在 Delete / Update(varchar變短)時,便會留下空洞」🗣️ Triton 本人說 070-lesson2.pdf.md · 第 7–9 頁〈淺談檔案結構〉

「萬一發生 bit-flipping 呢?」「為了降低 bit-flipping 災難 – RDBMS 不使用 delimitor – 每一個 data page 會有獨立的 meta data」🗣️ Triton 本人說 054-data-analysis.pdf.md · 第 6–7 頁(談 csv 用逗號換行分隔的風險)

🗣️「越大的 data block,structural overhead (header, checksum, remaining space) 比率越低」015 · Data Block Size 解說

文組版:寄放處一開始每件行李租一個櫃子(浪費),後來改成一排長架子依序擺(省),但有人取走後中間會空一格,所以要定期整理架子。行李不能改內容,所以不用替「行李變胖」預留空間。

🔭 推論 套到原書的 data node

  • 原書「一物件一檔 → 浪費 4KB block、用光 inode」= 070 的「方式 1」,連 4KB 的例子都一樣。
  • 原書的 read-write file + object_mapping(file, offset, size) = 070 的「方式 2」。方式 2 的缺點是 delete 留下空洞,這正是原書最後用 compaction 收拾的東西(第 54 頁)。
  • RDBMS 最後放棄方式 2、改用 8/16KB data page,是因為要支援 update 讓 row 變長變短。物件 immutable,沒有這個問題,所以方式 2 在物件儲存反而成立。
  • 原書每個物件尾端附 checksum、檔案關閉前加整檔 checksum,和 054「每頁有獨立 metadata、不靠 delimiter」是同一種防 bit-flip 的想法:壞也只壞一小塊,而且看得出來。

補充 · Triton 線080 · 054 · immutable + 背景合併 = SSTable

read-only 檔加 compaction,Triton 在 NoSQL 課叫它 SSTable

你猜猜看:原書的檔案寫滿就 read-only、背景再合併。這種「寫完不改」的結構,讀一筆資料時要付什麼代價?

「SSTable一旦建立後就永不改動(immutable)」「Memory buffer快要滿時,再一口氣把全部新資料去建立新的 SSTable file – 所以沒有了 Random Write IO」「當你要讀取 Record X時,你需要檢查每一個 SSTable」「database的 background worker,會把多個 SSTable file合成一個」🗣️ Triton 本人說 080-nosql-intro.pdf.md · 第 7–8 頁

「HDFS = Hadoop file system – 所有 file都是 immutable – 每一個 file會存到 n個 data node來避免 data loss」「HBase coordinator … 儲存/管理 PK to node的mapping table – 聆聽 HBase node的 heartbeat」🗣️ Triton 本人說 080 · 第 19–20 頁

🗣️「Storage level compression,理想是配上 Write-once架構 – 例子: SSTable in cassandra / HBase – 例子: apache parquet in OLAP」054 · 第 15 頁

🔭 最後一列是同意:原書說 RocksDB「寫快讀慢」,080 說的正是讀時要翻多個 SSTable。物件儲存寫一次讀很多次,mapping 用 B+ tree 合理。080 也說用 SSTable 系統「應該先 scale up,直到 server cost會 non-linearly增加時才 scale-out」,原書每台 data node 一個 SQLite 也是「先不要分散」的思路。

🔭 推論 對照表

原書080 裡的對應
read-write file 滿了變 read-onlymemory buffer 滿了 flush 成 immutable SSTable
GC compaction 合併多個 read-only 檔background worker 把多個 SSTable 合成一個
placement service:virtual cluster map + heartbeatHBase coordinator:PK→node mapping + heartbeat
primary 抄到 2 個 secondaryHDFS 每個 file 存到 n 個 data node
object_mapping 選 RDBMS 不選 RocksDB(讀多)「讀取 Record X 時需要檢查每一個 SSTable」

補充 · Triton 線074 · 073 · 019 · 三副本的數學 vs 一碗泡麵

(0.0081)³ 假設三顆硬碟各壞各的;Triton 說它們是「好兄弟」

你猜猜看:原書用 (0.0081)³ 算三副本。三顆硬碟如果插在同一台機器、共用一個電源,旁邊打翻一碗泡麵,會怎樣?

「使用Raid 1時,一個打翻了的泡麵引起的電源短路將會讓磁碟全滅 – Raid 1中的磁碟是好兄弟,總會同時趴掉」🗣️ Triton 本人說 074-lesson4.pdf.md · 第 45 頁〈沒有良好備份〉

「RAID 只能保護單一 SSD 故障 – 電源短路/打翻泡麵時,所有 SSD 都會一起陣亡」「Master/Slave Replication 保護不了壞人刪除數據」「只有以離線儲存的備份數據,才是真正安全的」🗣️ Triton 本人說 073-lesson3.pdf.md · 第 24 頁 Main DB

「Amazon S3 只保證資料流失機會率< 10^-9」「越接近100%可靠性,額外要付的錢便越高 – 甚至比數據流失的應變費用更高」🗣️ Triton 本人說 019-Introduction_to_database.pdf.md · 〈勇敢地面對數據流失〉

🔭 示意模型 「好兄弟」有多兄弟?

P(三份全壞) ≈ p × [q + (1−q)p]²,p = 0.81%。q = 0 就是原書的 (0.0081)³。這是簡報自己的示意公式,不是 Triton 或原書的。

  • 🔭 同意 原書自己也知道:它馬上接著講 failure domain、把副本放到不同 rack 和 AZ(第 35 頁)。那正是在拆散「好兄弟」。
  • 🔭 補充 原書的耐久度只算硬體。073 說 replication「保護不了壞人刪除數據」:bug 或手滑刪掉,三份副本會一起被刪。原書的 versioning 擋得住誤刪(第 49 頁),但仍在同一個系統裡;Triton 的標準是「離線儲存的備份」。

補充 · Triton 線106 · 073 · 181 · 144 · metadata 放 RDBMS、檔案不放 DB row

原書把檔案和 metadata 分開、metadata 放 RDBMS:Triton 同一邊

你猜猜看:原書說 object 表「很可能放不進單一 DB」,所以要 sharding。原書自己估的 metadata 總量大約多少?

「有人說:File 應該以 BLOB物件放到 Main DB,但是 – File 一般建立後極少被改動 – RDBMS 一般用上系統中最高級的 SSD,而 File 一般不需要這種效能」🗣️ Triton 本人說 073-lesson3.pdf.md · 第 30 頁 File DB

「RDBMS會把這些text / blob的內客externalize,然後在row record內只存放externalized address 這樣做的後果,是讓本來能一次disk IO解決東西,變成了需要二次disk IO才能解決」🗣️ Triton 本人說 181(「內客」照原文)· PostgreSQL 的機制叫 TOAST,「default觸發點為單一column 2KB」見 144

「主要還是一句:不能不見的data,我一定存到RDBMS」「如果是小型系統,單純scale up便算了」「要RDBMS的clustering其中雷區冒險,我還不如走傳統的sharding路線」🗣️ Triton 本人說 106-喵 data.md(從「主要還是一句」起)

073 還有一句「延伸思考:在檔案名字中額外加上 MD5,許多能解決很多 File caching 問題」:內容不變名字就不變,和原書 ETag 是 md5 同一個想法。

🔭 推論 套回原書

  • 同意:原書 metadata 和 data 分離、object_mapping 選 RDBMS、object 表用 hash(bucket_name, object_name) 做傳統 sharding,都和 106、073 同方向。073 的理由(檔案很少改、不需要最貴的 SSD)就是原書 Table 1「object storage 便宜、慢」那一欄。
  • 要先問的:原書估算頁自己算出 metadata 總量約 0.68 TB(第 12 頁),卻在第 44 頁說 object 表「很可能放不進單一 DB instance」。依 106「先 scale up」的原則,第一步是確認一台大機器 + read replica 撐不撐得住,撐不住才 shard。
  • 106 也說「如果要考慮水平擴充,請走noSQL路線」。到了 S3 那種 100 兆物件的規模,那是另一個問題,這章的 100 PB 還不到。

補充 · Triton 線130 · 128 · 049 · GB 級的物件:當 stream,不要當 byte array

API service 收到 200 MB 的 part,先整個讀進記憶體?

你猜猜看:API service 收到 200 MB 的 part,先整份讀進記憶體再轉送。同時 100 個人上傳,會怎樣?

「即使你看完總共23GB的影片也好,你也只用上了固定的很小塊Memory。」「reqBodyData := ioutil.ReadAll(req.Body); …」「如果一份data只會用一次的,你應該用streaming的手段來處理。」「你的Application code應該是把不同階段的上下游,用 Reader(如果是data input)/Writer(如果是data output)串接起來。」🗣️ Triton 本人說 130-喵談 io streaming.md

「我們應該把File當成Stream而不是ByteArray」「如果你不懂什麼需要放進local cache 你應該依賴OS level的file cache而不是自己亂來」🗣️ Triton 本人說 128-喵談 buffer stream and local cache.md · 只引主文

🗣️「每一個 file 都開一個 Importer thread – 這樣子 file descriptor 會不夠用! – local file還不一定有事,像 Amazon S3 這種 non-local file,死定了」049 · 智障架構

🔭 推論 算算 API service 的記憶體

  • 原書的資料要經過 API service → data routing → primary → 兩個 secondary。每一跳如果都 ReadAll,就是每一跳都要一整份的記憶體。
  • MD5(ETag、checksum)和 erasure coding 都可以邊讀邊算,不需要先拿到整份資料。
  • 原書沒有寫 API service 怎麼收 payload,這頁是把 130 的原則套進去,不是說原書寫錯。

補充 · Triton 線062 · 087 · 104 · cursor 要記「最後一筆」,不要記 offset

原書的 cursor 裝 offset;Triton 的 cursor 裝「上一頁最後一筆」

你猜猜看:原書的 cursor 裝 OFFSET。你看完第 1 頁,有人在最前面多上傳一個檔。第 2 頁會怎樣?

「GET /v1/chatrooms/<roomId>/messages – Optional parameter: lastTs … 支持 pagination,返回大約上限 50 個訊息 – 除了 array of message,還會有 nextPageTs」🗣️ Triton 本人說 062-im-system design.pdf.md

「想像一下:你在看一個持續改動中的排名榜 – 如果沒有 snapshotting,剛好第十名的物品變第十一,然後你拿 Page 2的資料 – 你就會看到重覆的物品」🗣️ Triton 本人說 087-redis-2019.pdf.md · 案例 2 data snapshotting

「Random IO是Sequential IO的1 / 10效能也沒有。」「Range Scan on Primary Key能使用Sequential IO對tablespace作局部掃瞄,效能非常快的。」🗣️ Triton 本人說 104-利用Range Scan on Primary Key的好處.md(談 MySQL InnoDB)

  • 🔭 用 WHERE object_name > :last ORDER BY object_name LIMIT 10:每個 shard 都用同一個 :last,cursor 只要一個字串,不必追幾百個 offset;新插入的物件也不會讓下一頁重複。
  • 🔭 listing 表的 PK 若是 (bucket_id, object_name),在 index-organized table 上就是 104 說的 range scan on PK。
  • 📅 2026 補充 真正的 S3 ListObjectsV2 用的也是 key 型 cursor:continuation-token 與 start-after,不是 offset。

🔭 推論 翻頁時有人上傳新檔

補充 · Triton 線046 · 051 · 076 · 181 · 他怎麼「用」三種儲存

Triton 的 S3 經驗都是「拿來用」:log、事件、靜態檔

你猜猜看:每天的 log 要封存起來,很少再讀,越便宜越好。依 Table 1,該放哪一種儲存?

「Migrate NFS to AWS EFS」「Afterthought on AWS EFS – Just a NFS – On Ubuntu 16.04.1, failed to automount – No monitoring – Poor performance for hosting php code – Any one particular file can have up to 87 locks across all users of the file system.」🗣️ Triton 本人說 046-aws-sharing.pdf.md · HYPEBEAST(2015 架構圖裡也有 Amazon S3 和 Central NFS)

「沒錢就單純 logrotate時存到 AWS S3 – 有錢就建 ELK」🗣️ Triton 本人說 051-concurrency.pdf.md · Logging 「Amazon Firehose and S3 – Store the events for future data mining」🗣️ Triton 本人說 076-mini-bigdata.pdf.md

「今天都是用SSD(如果你的公司的RDBMS還是建立在HDD上,請認真考慮換工作)」🗣️ Triton 本人說 181

💬 作者未標示「partition 設計良好,而且壓縮格式有選對的狀況下,S3 + Athena 確實很神(效能/花費的CP值來說)」085(無署名)

🔭 推論 放回 Table 1

他的選擇Table 1 的哪一欄
RDBMS 放 SSD(181)Block:高效能、DB
共用 php 程式碼放 NFS / EFS,效能差、87 個 lock(046)File:通用、共享,但不是為高頻小檔讀寫做的
log 封存、事件留給 data mining(051、076)Object:冷資料、寫一次、便宜

🔭 他的每個選擇都和原書 Table 1 的「Good for」一致。他從沒說過要自己做一個 S3;在他的講義裡,物件儲存是買來用的雲端服務。對多數團隊,讀這章的價值是知道 S3 為什麼便宜、為什麼慢、為什麼 listing 不快,而不是照著蓋一個。

一句話記住

名字和內容分開放;內容只能整件換、
抄到不同的地方、每塊附上指紋。

原書的骨架

  • API service(stateless)+ IAM + metadata store + data store
  • data store:routing、placement(Raft、15 秒心跳)、data node
  • 小物件 append 到大檔,SQLite 存 file / offset / size
  • 三副本或 EC 8+4,跨 failure domain;MD5 checksum
  • versioning 用 TIMEUUID 與 delete marker;multipart;compaction

原書自己承認的取捨

  • strong consistency 要等最慢的副本
  • EC 省空間但讀要碰 8 台、設計複雜,所以本設計主打 replication
  • listing 效能不是重點,另開一張依 bucket 分片的表

🔭 Triton 原則套進來

  • 小檔合併、immutable、背景合併:和 RDBMS / SSTable 底層同一組物理限制(同意)
  • 副本會「一起趴掉」,replication 擋不住誤刪:要離線備份
  • 0.68 TB 的 metadata:先 scale up 再 shard
  • GB 級資料走 stream;cursor 記最後一筆

本章名詞小卡課後複習用 · 每個名詞一句白話

今天出現的名詞,一句話講完

block storage一排編號格子,哪格放什麼自己記(DB、VM)
file storage照資料夾路徑放,很多台共用(NFS)
object storage整件交出去、拿號碼牌;只能整件換新(S3)
immutable放進去就不改;要改就整件換新版
bucket裝物件的櫃位,名字全球唯一
key、URI物件在 bucket 裡的名字//bucket/key 這種網址
durability放進去的東西過一年還在不在(幾個 9)
availability現在拿不拿得到
SLA寫進合約的保證
metadata關於資料的資料:名字、誰的、放在哪
metadata store、data store櫃台登記簿/後面的倉庫
UUID亂數產生、幾乎不會撞號的編號
inode檔案系統裡每個檔案的小卡,記資料在磁碟哪裡
IAM門禁:你是誰、能做什麼

給工程師的重點出處與標籤

引述來源與原書對照

Triton 本人的講義 / 文章(都不是講物件儲存)

  • 070-lesson2.pdf.md — 1 byte 檔案佔 4KB、一筆一檔與一個巨型檔兩種「幻想」、delete 留空洞
  • 054-data-analysis.pdf.md — csv 的 bit-flipping、data page 獨立 metadata、壓縮配 write-once
  • 015-From_MySQL_to_postgreSQL.pdf.md — data block 的 header / checksum overhead
  • 080-nosql-intro.pdf.md — SSTable immutable、讀要查每個 SSTable、背景合併、HDFS、HBase coordinator 與 heartbeat、先 scale up
  • 074-lesson4.pdf.md、073-lesson3.pdf.md、019-Introduction_to_database.pdf.md — RAID 好兄弟、replication 擋不住刪除、離線備份、File DB、檔名加 MD5、S3 < 10^-9、越可靠越貴
  • 106-喵 data.md(從「主要還是一句」起)、181、144-喵談分表.md — RDBMS 存不能掉的資料、scale up、傳統 sharding、blob 外置、TOAST 2KB
  • 130-喵談 io streaming.md、128(只引主文)、049-concurrency-demo.pdf.md — stream 不是 byte array、OS file cache、S3 non-local file
  • 062-im-system design.pdf.md、087-redis-2019.pdf.md、104 — lastTs / nextPageTs、移動中的資料分頁會重複、range scan on PK
  • 046-aws-sharing.pdf.md、051-concurrency.pdf.md、076-mini-bigdata.pdf.md — EFS「Just a NFS」、log 存 S3、Firehose → S3

作者未標示:085(S3 + Athena,標 💬)。未使用:學員筆記、014 等 NotebookLM 摘要、Roy 的專案報告。

一個可以直接問自己的問題

你的三份副本,共用了什麼?同一個 rack、同一批硬碟、同一個刪除指令、同一個 bug?共用的東西,就是它們會一起壞的地方。

原書對照

Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.9。S3 facts、Storage 101、Figure 1(第 6 頁);Table 1(7);Terminology(10);Step 1 問答與需求(11);估算(12);四個特性與 Listing 1(13);inode 與 Figure 2–3(15);High-level design 與 Figure 4(16);Uploading 與 Figure 5(17)、Table 2 與 Listing 2(18);Downloading、Listing 3、Figure 6(19);Data store、Figure 7–8(22);Placement 與 Figure 9(23–24);Persistence flow 與 Figure 10(26);Figure 11(27);How data is organized 與 Figure 12(29);Object lookup、Table 3–4(30);Figure 13(31)與動手玩(32);Durability 與 Figure 14(35);Erasure coding 與 Figure 15–17(37–39);Table 5(40);Correctness 與 Figure 18–20(42);Metadata 與 Figure 21(44–45);Listing(46–47);Versioning 與 Figure 22–24(49–50);Multipart 與 Figure 25(52);GC 與 Figure 26(54);Wrap up 與章節總結圖(56)。26 張圖、Table 3 的圖與章節總結圖都依原書圖說與 alt 描述重繪,不是原圖。

循序漸進(文組版)的頁面

學習地圖(第 3 頁);延伸基礎 13 階:block / file / object(5)、bucket / key(8)、durability(9)、metadata 複習(14)、data node(21)、replication 複習(25)、小物件合併(28)、failure domain(34)、erasure coding(36)、checksum(41)、versioning(48)、multipart(51)、GC(53);小結(20、33、43、55);名詞小卡(66)。已在 01、02、05、06、07、11、12、14、15 章講過的詞只做一句話複習並連過去。寄放處是示意情境,延伸基礎頁的數字是示意值。

← → 翻頁 · S 講者備註 · D 深/淺色
1 / 1目錄