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 階。每一階只用前面講過的東西。
- 1block / file / object三種寄放法
- 2bucket / key櫃位與號碼牌
- 3durability幾個 9
- 4metadata登記簿 vs 倉庫
- 5data node倉庫與調度員
- 6replication抄幾份才算數
- 7小物件合併明信片進資料夾
- 8failure domain別放同一棟
- 9erasure coding1 + 1 + 1 = 3
- 10checksum封條上的指紋
- 11versioning舊版留著
- 12multipart分箱搬家
- 13GC定期整理架子
第 1–4 階 · 寄放處長什麼樣
要回答:物件儲存跟硬碟、資料夾差在哪?
第 5–7 階 · 倉庫怎麼放
要回答:一件行李放哪幾間倉庫?小信封怎麼放?
第 8–10 階 · 一件都不能掉
要回答:倉庫燒了、bit 翻了怎麼辦?
第 11–13 階 · 改版、大件、清垃圾
要回答:同名再寄、大檔斷線、刪掉的空間怎麼收?
全程只用一家:機場行李寄放處
每爬 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
相簿 100 頁只換 1 頁:三種寄放法各要重寫多少?
① 先想像
一本 100 頁的相簿,分別放在租來的格子、圖書館、機場行李寄放處。現在想換掉第 3 頁。
你猜猜看:寄放處不讓你打開行李。換 1 頁,要重新寄放幾頁?
只能整本重寄一次,舊的那本變成舊版本。換來的好處:寄放處不用管「改到一半」,所以能做得又大又便宜。
③ 這叫做 block、file、object storage
block:一排編號格子,哪格放什麼自己記。file:照資料夾路徑放,可以直接改。object:整件交出去,只能整件換新。
④ 跟這章的關係
這章要設計的是 object storage。「只能整件換新」會讓後面很多設計變簡單(第 13 頁)。
② 動手玩:換幾頁,要重寫幾頁?
| 誰記得東西在哪 | 誰替你抄備份、搬家 | |
|---|---|---|
| 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。
白話:RESTful API=用網址加上 GET、PUT 這類動詞來存取;volume=一顆(虛擬的)硬碟;VM=在一台電腦裡模擬出來的另一台電腦;archival/backup=封存/備份。
原書Table 1 Storage options
三種儲存,七個面向比一比
這一步要解決的問題三種儲存各自擅長什麼?物件儲存故意放棄了哪些東西?
| Block storage | File storage | Object storage | |
|---|---|---|---|
| Mutable Content | Y | Y | N(支援 object versioning,不支援 in-place update) |
| Cost | High | Medium to high | Low |
| Performance | Medium to high, very high | Medium to high | Low to medium |
| Consistency | Strong consistency | Strong consistency | Strong consistency [5] |
| Data access | SAS / iSCSI / FC | Standard file access, CIFS/SMB, NFS | RESTful API |
| Scalability | Medium scalability | High scalability | Vast scalability |
| Good for | Virtual machines (VM)、資料庫這類高效能應用 | General-purpose file system access | Binary 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
寄放處的櫃位、行李、和行李的名字
① 先想像
寄放處分成很多櫃位,每個櫃位掛一個名字,例如 ann-trip。行李寄在櫃位裡,再取一個名字,例如 album.zip。
你猜猜看:Ann 已經把櫃位取名 photos。住在別國的 Bob 也想叫 photos,可以嗎?
櫃位名字全球共用,Bob 只能改叫 bob-photos 之類。櫃位裡面的行李名字不用全球唯一:每個櫃位都可以有一件 album.zip。
③ 這叫做 bucket、key
bucket:櫃位,裝物件的容器,名字全球唯一。key:物件在 bucket 裡的名字;/bucket/key 合起來就找得到它。
④ 跟這章的關係
原書的 URI /bucket-to-share/script.txt 就是 bucket + key(第 10、13 頁)。
② 動手玩:寄一件、再用名字領回來
別人已經用掉的櫃位名字:photos(Bob)、logs、backup
延伸基礎第 3 階 · durability懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
「一百萬件只會弄丟一件」是幾個 9?
① 先想像
寄放處貼出保證:「每年每一百萬件行李,最多只會弄丟 1 件。」
你猜猜看:換成百分比,行李「還在」的機率是?
掉 1 / 1,000,000 = 0.0001%,還在的是 99.9999%,一共 6 個 9。每多一個 9,掉的件數少 10 倍。
③ 這叫做 durability
durability(耐久度):東西放進去,過一年還在不在。常念成「幾個 9」。
④ 跟這章的關係
S3 寫 11 個 9(下一頁),原書需求是 6 個 9(第 11 頁)。「現在拿不拿得到」是另一件事:availability,02 章講過。
② 動手玩:幾個 9、寄放幾件
原書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 會有多大?先估出數量級。
📖 原書 物件儲存的瓶頸可能在 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
櫃台一本登記簿,後面一整排倉庫
① 先想像
櫃台有一本登記簿:「album.zip,Ann 的,在 3 號倉庫第 12 格」。行李本身放在後面的倉庫。
你猜猜看:倉庫有 1,000 個架子,櫃台沒有登記簿。找 Ann 的相簿平均要翻幾個?
運氣好第 1 個就找到,運氣差翻到最後一個,平均一半。有登記簿:查一行,直接走到那一格。
③ 這叫做 metadata(複習)
④ 跟這章的關係
原書把登記簿叫 metadata store、倉庫叫 data store,兩邊分開設計(下一頁)。
② 動手玩:40 個架子,找一件行李
原書 Step 2和 UNIX 檔案系統一樣:名字和內容分開放 · Figure 2–3
inode 變成 metadata store,硬碟變成 data store
這一步要解決的問題檔案的「名字」和「內容」要放在一起嗎?UNIX 檔案系統早就給了答案。
📖 原書 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 進來,要經過哪些關卡才碰得到資料?先看全貌的五個元件。
- 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 步
這一步要解決的問題一個新物件寫進來:哪一步先、哪一步後?順序反過來會怎樣?
- Client 送 HTTP PUT 建立名為
bucket-to-share的 bucket,轉給 API service - API service 呼叫 IAM,確認使用者已授權、有 WRITE 權限
- API service 呼叫 metadata store,在 metadata DB 建一筆 bucket 資訊;建好就回成功給 client
- Client 送 HTTP PUT 建立物件
script.txt - API service 驗證身份,確認使用者對這個 bucket 有 WRITE 權限
- 驗證通過,API service 把 PUT payload 的物件資料送到 data store;data store 存成物件,回傳 UUID
- 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_name | object_id | bucket_id |
|---|---|---|
| script.txt | 239D5866-0052-00F6-014E-C914E61ED42B | 82AA1B2E-F599-4590-B5E4-1F51AAE5F7E4 |
📖 原書 Table 2Sample entry;按「送出 PUT」會多一列(新 UUID 由瀏覽器隨機產生)
讀懂這個 request
PUT /bucket-to-share/script.txt:URI 就是 keyAuthorization:給 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、不認名字。那用名字下載要怎麼做?
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
- Client 送
GET /bucket-to-share/script.txt到 load balancer - API service 問 IAM:使用者對這個 bucket 有 READ 權限嗎
- 通過後,API service 從 metadata store 拿到物件的 UUID
- API service 用 UUID 從 data store 拿物件資料
- API service 在 HTTP GET response 回傳物件資料
📖 原書 bucket 沒有目錄階層,但可以把 bucket 名和物件名串起來模擬資料夾,例如物件叫 bucket-to-share/script.txt。data store 不存物件名稱,只認 UUID,所以下載一定先查 metadata。
到這裡你已經會了小結 1 / 4
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
到這裡你已經會了:寄放處長什麼樣
- 物件儲存(object storage)像行李寄放:整件交出去、只能整件換新,換來又大又便宜。
- 物件住在全球唯一名字的 bucket 裡,用
/bucket/key找回來;durability 用「幾個 9」說它多不會掉。 - 登記簿(metadata store)和倉庫(data store)分開:上傳先存資料拿 UUID 再登記,下載先查登記再搬。
下一階要解決的問題
倉庫後面長什麼樣?一件行李要放幾間、放哪幾間?小信封又怎麼放?
延伸基礎第 5 階 · data node / placement懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
倉庫有好幾間:新行李放哪幾間?誰決定?
① 先想像
寄放處有 4 間倉庫,每間每 5 秒打卡一次「我還在」。調度員看著一張表:每間剩幾格、多久沒打卡。
你猜猜看:寬限 15 秒。C 倉庫已經 20 秒沒打卡,空位又最多。新行李會派給 C 嗎?
超過寬限期就標成 down,空位再多也不派。它重新打卡,才會回到名單上。
③ 這叫做 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 裡面還要再拆:誰決定放哪、誰真的存、誰負責搬?
白話: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
這一步要解決的問題調度員怎麼知道哪些倉庫還活著?副本要怎麼放才夠分散?
📖 原書 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
一件行李存三份:等幾份存好,才跟客人說「好了」?
① 先想像
行李進了第一間倉庫,再抄到另外兩間。三間存好的時間不一樣:10、20、150 毫秒(示意)。
你猜猜看:要等三間都存好才回客人,客人要等多久?
要等「全部」,就得等最慢的那間。只等 1 間最快,可是那一刻只有 1 份,那間壞了就沒了。
③ 這叫做 replication、quorum(複習)
④ 跟這章的關係
原書 Figure 10 等三台都好;Figure 11 比較三種等法(第 26–27 頁)。
② 動手玩:調三間的速度,選要等幾間
原書 Step 3Data persistence flow · Figure 10
寫一筆資料:routing 問 placement,primary 抄給兩個 secondary
這一步要解決的問題一筆資料從進門到存好三份,路線怎麼走?誰給 UUID、誰抄給誰?
- API service 把物件資料轉給 data store
- Data routing service 替物件產生 UUID,問 placement service 要存在哪個 data node;placement 查 virtual cluster map,回傳 primary
- Routing 把資料連同 UUID 直接送到 primary data node
- Primary 存到本地,再複製到兩個 secondary;全部複製成功才回應 routing
- 物件的 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
要等幾個副本寫完才回「成功」?
這一步要解決的問題等三份都存好最安全,但也最慢。能不能少等幾份?代價是什麼?
- 三台都存好才算成功:best consistency、highest latency
- Primary + 一個 secondary 存好:medium consistency、medium latency
- Primary 存好就算:worst consistency、lowest latency
📖 原書 2 和 3 都是 eventual consistency。選項 1 的代價是「要等最慢的那個副本」。
按按看
每筆寫入:primary 約 5–15ms,每個 secondary 約 10–40ms,偶爾有一台卡 150ms。看三種選項的平均和最慢。
延伸基礎第 7 階 · 小物件合併懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
寄一張明信片,也要租一整個櫃子嗎?
① 先想像
寄放處最小的櫃子一格放得下 4 張明信片。有人只寄 1 張,也佔掉一整格。
你猜猜看:一張 1 KB、一格 4 KB。寄 1,000 張、一張一格,空間浪費幾成?
每格只用 1 KB、空 3 KB,空的佔 3/4。格子總數也是開店時就定好的,小東西一多就先用光。
③ 這叫做 append、offset
append:新東西一律接在最後面。offset:從開頭數過來第幾個位置。記下「哪本、offset、多長」就找得回來。
④ 跟這章的關係
原書把很多小物件 append 到一個大檔,再用一張表記位置(第 29–32 頁)。
② 動手玩:一格 4 個位置
原書 Step 3How data is organized · Figure 12
一個物件一個檔?小檔案太多會出兩個問題
這一步要解決的問題幾十 KB 的小物件一個一個存成檔案,會撞到檔案系統的哪兩面牆?
📖 原書 問題一:浪費 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、物件多大。
| Field | Description |
|---|---|
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 表之後,存一個新物件的步驟變成什麼?
📖 原書 data node 改了不少,重看一次存新物件的流程:
- API service 要求儲存新物件 “object 4”
- Data node service 把 “object 4” append 到 read-write file
/data/c的尾端 - 在 object_mapping 表插入 “object 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
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
到這裡你已經會了:倉庫怎麼放
- 調度員(placement service)看打卡(heartbeat)決定行李放哪幾間 data node;調度員自己有 5 或 7 位,過半數在就能做決定。
- 每件存三份(replication);等越多份存好才回「成功」,越安全,也越慢。
- 小物件 append 進大檔,用(檔名、offset、大小)找回來;檔案寫滿就變 read-only。
下一階要解決的問題
硬碟一定會壞、整區會停電、bit 會偷偷翻掉。一百萬件掉不到一件,要怎麼做到?
延伸基礎第 8 階 · failure domain懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- 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
硬碟一定會壞:抄三份,而且放在不同的地方
這一步要解決的問題硬碟一定會壞。要做到「一百萬件掉不到一件」,抄幾份、放哪裡?
📖 原書 選擇哪一層 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
1 + 1 + 1 = 3:多寫一張「總和紙」,掉一張就救得回來
① 先想像
一組密碼拆成三張紙條:1、1、1,交給三位朋友。你再寫一張「三張加起來是 3」,交給第四位。
你猜猜看:第二位朋友把紙條弄丟了。還知道上面寫什麼嗎?
總和減掉還在的兩張,就是丟掉那張。只多存 1 張紙,不用把三張整套再抄兩份。
③ 這叫做 parity、erasure coding
parity:用原始資料算出來的「總和紙」。erasure coding:資料切塊、多算幾張 parity,掉幾塊都算得回來。
④ 跟這章的關係
原書 4+2:4 塊資料、2 張 parity,任掉 2 塊都救得回(第 37 頁)。
② 動手玩:改數字、弄丟紙條、再算回來
原書 Step 3Erasure coding · Figure 15
不抄整份:切成 4 塊,再多算 2 塊「備援」
這一步要解決的問題三副本要多付 200% 的倉庫錢。能不能少存一點,一樣不怕壞?(第 9 階 1+1+1=3 的放大版)
- 資料切成四塊一樣大的 d1、d2、d3、d4
- 用數學公式算出 parity p1、p2。原書的簡化例子:p1 = d1 + 2·d2 − d3 + 4·d4,p2 = −d1 + 5·d2 + d3 − 3·d4
- d3、d4 因節點當機遺失
- 用已知的 d1、d2、p1、p2 解回 d3、d4
動手解:照原書公式,壞兩塊還救得回來嗎?
寄放處版:把一本相簿拆成 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 再放大:切更多塊、放更多地方,空間和速度怎麼取捨?
📖 原書 (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 贏在其他三項
這一步要解決的問題兩種方法各贏在哪?原書最後選了哪一個?
| Replication | Erasure coding | |
|---|---|---|
| Durability | 6 個 9(資料複製 3 次) | 11 個 9(8+4 erasure coding)。Erasure coding wins |
| Storage efficiency | 200% storage overhead | 50% 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
行李封條上寫一個「指紋」,領取時再算一次
① 先想像
寄放時,櫃台把清單上的數字加起來,總和寫在封條上。領取時再加一次,對不上就知道被動過。
你猜猜看:清單 3、5、2,封條寫 10。領取時清單變成 3、6、2,對得上嗎?
改一個數字,總和就變。可是把 3、5 對調成 5、3,總和還是 10,看不出來。所以真實系統用更講究的算法,例如 MD5。
③ 這叫做 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%,實務上當成相同)。
📖 原書 演算法有 MD5、SHA1、HMAC 等,好的演算法輸入改一點輸出就差很多;本章選 MD5。每個物件尾端附 checksum;檔案標成 read-only 前,再在尾端加整個檔案的 checksum。
白話:process 邊界=資料從一個程式交給另一個程式的那一刻;in-memory=在記憶體裡;HMAC=加了密碼的指紋算法。
動手翻一個 bit
📖 原書 (8+4) + checksum 的讀取流程
- 拿物件資料和 checksum
- 對收到的資料算 checksum:(a) 相同 → 沒錯;(b) 不同 → 損壞,改從其他 failure domain 讀
- 重複 1、2 直到 8 塊都拿到,重建資料回給 client
到這裡你已經會了小結 3 / 4
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
到這裡你已經會了:一件都不能掉
- 副本要放在不同的 failure domain(不同機櫃、不同 AZ),才不會一起壞。
- erasure coding 像 1 + 1 + 1 = 3:多存幾張 parity 就能救回遺失的塊;比三副本省空間,但讀要碰更多台。
- checksum 是指紋:資料一翻 bit 就對不上,改從別的 failure domain 讀。
下一階要解決的問題
回到櫃台的登記簿:幾億筆 metadata 怎麼分、怎麼列出?同名再寄、大件斷線、刪掉的空間又怎麼辦?
原書 Step 3Metadata data model · Schema · Figure 21
兩張表:bucket 和 object,要撐三種查詢
這一步要解決的問題登記簿要有哪些欄位,才撐得起三種查詢?表太大時又怎麼辦?
📖 原書 三種查詢
- 用物件名稱找 object ID
- 用物件名稱插入、刪除物件
- 列出 bucket 裡共用同一個 prefix 的物件
📖 原書 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 的三種用法
- 列出使用者所有 bucket:
aws s3 list-buckets - 列出和 prefix 同一層的物件:
aws s3 ls s3://mybucket/abc/;prefix 後面還有斜線的,會捲成一個 common prefix - 遞迴列出同 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懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
同名的行李再寄一次:舊的那件丟掉,還是留著?
① 先想像
Ann 寄了 album.zip,隔天又寄一本同名的新相簿。寄放處可以丟掉舊的,也可以在登記簿多寫一行,兩本都留。
你猜猜看:「留舊版」模式下,Ann 同名寄 3 次,再按刪除。倉庫裡還有幾本?
刪除只是在登記簿最上面加一行「已刪除」便條。三本都還在,隨時救得回來;代價是倉庫要付三本的錢。
③ 這叫做 versioning、delete marker
versioning:同名再寄不覆蓋,每次多一個版本。delete marker:「已刪除」便條,它本身也是一個新版本。
④ 跟這章的關係
原書第 49–50 頁。不留舊版時,被蓋掉的那本變成垃圾,等第 13 階回收。
② 動手玩:寄、刪、領
登記簿(最新的在最上面)
原書 Step 3Object versioning · Figure 22
開了 versioning:同名再上傳,不覆蓋,多一筆
這一步要解決的問題同名再上傳,怎麼不蓋掉舊版?「目前版本」又怎麼找?
📖 原書 沒有 versioning:同名存檔,metadata store 裡舊版 metadata 被新版取代,舊版被標成 deleted,空間由 garbage collector 回收。有 versioning:所有舊版都留在 metadata store,data store 裡的舊版永遠不會被標成 deleted。要先在 bucket 上開啟。
- Client 送 HTTP PUT 上傳
script.txt - API service 驗證身份,確認有 bucket 的 WRITE 權限
- 驗證後把資料上傳到 data store,存成新物件,回傳新 UUID
- API service 呼叫 metadata store 存這個物件的 metadata
- 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,「刪除」要怎麼做才能反悔?
📖 原書 刪除時所有版本都留在 bucket,另外插入一個 delete marker。delete marker 是物件的新版本,插入後就成為目前版本;目前版本是 delete marker 時 GET 回 404 Object Not Found。
延伸基礎第 12 階 · multipart upload懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
搬家路上翻車:全部重搬,還是只補那一箱?
① 先想像
搬家有 8 箱。一種是全部塞一台卡車一趟運完;另一種是分 8 趟,每箱貼編號,到了再照編號排好。
你猜猜看:1.6 GB 傳到 1.5 GB 斷線。一次傳要重傳多少?切 8 份(每份 200 MB)呢?
一次傳時,伺服器沒辦法保留「傳一半」的東西,只能從頭來。切成 8 份,前 7 份已經收好,只補斷掉的第 8 份。
③ 這叫做 multipart upload、part
multipart upload:大檔切成很多份分開傳,最後照編號拼回來。part:切出來的一份。
④ 跟這章的關係
原書:1.6 GB 切 8 份、每份 200 MB,傳完用編號重組(第 52 頁)。
② 動手玩:選在哪裡斷線
原書 Step 3 · 動手玩Optimizing uploads of large files · Multipart upload · Figure 25
1.6 GB 傳到一半斷線:從頭來,還是只補沒傳完的?
這一步要解決的問題幾 GB 的大檔一次傳,斷線就要從頭來。怎麼辦?
- Client 呼叫物件儲存,initiate multipart upload
- Data store 回傳唯一的 uploadID
- Client 切成小物件上傳:1.6GB 切 8 份、每份 200 MB,連同 uploadID 上傳
- 每份上傳完,data store 回傳 ETag(本質上是那一份的 md5 checksum)
- 全部傳完,送 complete:uploadID、part number、ETag
- Data store 依 part number 重組(物件很大,可能要幾分鐘),回傳成功
白話:ETag=每一份的指紋;part number=每一份的編號。
延伸基礎第 13 階 · garbage collection懂的人可以跳過
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
取消寄放的行李:先貼紅標,每週一起清
① 先想像
有人取消寄放,櫃員不會馬上進倉庫搬,只在那一格貼紅標。每週一次,把沒貼紅標的搬到一排新架子,舊架子整排清空。
你猜猜看:一排 8 格,有 3 格貼紅標。整理後新架子要幾格?
只搬沒貼紅標的 5 件,舊的 8 格整排空出來。為什麼不馬上搬?一件一件跑倉庫太累,攢一批一起整理比較省。
③ 這叫做 garbage collection、compaction
garbage collection(GC):定期回收沒人要的資料。compaction:把活的搬到新檔、排緊,舊檔整個丟掉。
④ 跟這章的關係
原書的垃圾有三種:刪掉的、傳一半的、壞掉的(第 54 頁)。
② 動手玩:點格子貼紅標,再整理
舊架子
新架子
原書 Step 3 · 動手玩Garbage collection · Compaction · Figure 26
刪掉的不馬上刪:等一批 read-only 檔,一次搬家壓實
這一步要解決的問題刪掉的、傳一半的、壞掉的資料,什麼時候清?怎麼清才省事?
白話:orphan data=沒有登記簿指著的資料;transaction=幾個修改要嘛全成功、要嘛全不算(07 章)。
📖 原書 會變成垃圾的三種資料:Lazy object deletion(刪除時只標記)、Orphan data(傳一半的資料、被放棄的 multipart)、Corrupted data(checksum 驗證失敗)。GC 不會立刻從 data store 移除,而是定期用 compaction 清。副本也要清:replication 從 primary 和 backup 都刪;(8+4) 要從 12 個節點都刪。
- GC 把
/data/b的物件複製到新檔/data/d,跳過 delete flag 為 true 的 Object 2、Object 5 - 複製完更新 object_mapping:Object 3 的 obj_id、object_size 不變,file_name、start_offset 改成新位置;這兩欄的更新包在一個 DB transaction 裡
新檔比舊檔小。為了不製造一堆小檔,GC 通常等到有很多 read-only 檔才壓,把多個檔的物件 append 到少數幾個大的新檔。
到這裡你已經會了小結 4 / 4
- block / file / object
- bucket / key
- durability
- metadata
- data node
- replication
- 小物件合併
- failure domain
- erasure coding
- checksum
- versioning
- multipart
- GC
到這裡你已經會了:改版、大件、清垃圾
- 開了 versioning,同名再寄多一個版本;刪除是插入 delete marker,舊版都還在。
- 大檔用 multipart upload 切份傳,斷線只補那一份,最後照編號重組。
- 刪掉的、傳一半的、壞掉的資料,交給 GC 定期 compaction 一起清。
13 階全部走完了
下一頁是原書的收尾。之後是 Triton 的八頁:他沒做過物件儲存,但講 RDBMS 怎麼存資料時,講過同樣的取捨。
原書 Step 4Wrap up · 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 之後會留下什麼?
刪掉中間一筆,那段位置就空著沒人用。原書最後用 compaction 收拾的就是這些空洞(第 54 頁)。Triton 的原文在下面。
「即使檔案只有 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、背景再合併。這種「寫完不改」的結構,讀一筆資料時要付什麼代價?
新資料一直開新檔,同一筆可能在任何一個檔裡。Triton 講 SSTable 時說的就是這件事;原書因此讓 mapping 用讀得快的 RDBMS。
「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-only | memory buffer 滿了 flush 成 immutable SSTable |
| GC compaction 合併多個 read-only 檔 | background worker 把多個 SSTable 合成一個 |
| placement service:virtual cluster map + heartbeat | HBase coordinator:PK→node mapping + heartbeat |
| primary 抄到 2 個 secondary | HDFS 每個 file 存到 n 個 data node |
| object_mapping 選 RDBMS 不選 RocksDB(讀多) | 「讀取 Record X 時需要檢查每一個 SSTable」 |
補充 · Triton 線074 · 073 · 019 · 三副本的數學 vs 一碗泡麵
(0.0081)³ 假設三顆硬碟各壞各的;Triton 說它們是「好兄弟」
你猜猜看:原書用 (0.0081)³ 算三副本。三顆硬碟如果插在同一台機器、共用一個電源,旁邊打翻一碗泡麵,會怎樣?
(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 總量大約多少?
第 12 頁算出約 0.68 TB,一台大機器放得下。Triton 的原則是先 scale up,真的撐不住才 shard(原文在下面)。
「有人說: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 個人上傳,會怎樣?
100 × 200 MB = 20 GB,而且每經過一台都要再一份。右邊的計算機可以改數字。Triton 的說法在下面。
「即使你看完總共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 頁會怎樣?
大家都往後擠一格,從 OFFSET 4 開始讀,就讀到上一頁的最後一筆。右邊按「翻頁中插入」驗證。
「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,該放哪一種儲存?
寫一次、很少讀、要便宜,就是 object storage。Triton 自己的做法也一樣(下面原文)。
「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 記最後一筆
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源與原書對照
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 章講過的詞只做一句話複習並連過去。寄放處是示意情境,延伸基礎頁的數字是示意值。