9.3 雲端儲存的架構#

概念說明#

Amazon S3、Google Cloud Storage 這類物件儲存把數千台機器組成「無限大的磁碟」。對外只有簡單介面：PUT(鍵, 物件)、GET(鍵)、DELETE(鍵)——沒有目錄樹、不能部分修改（物件不可變）、一致性模型偏鬆（最終一致或讀寫一致可選）。這個「極簡介面」正是它能伸縮到 EB 級的秘訣。

核心架構組件：

中繼資料服務：鍵 → 資料塊清單的映射（自身必須是分散式且高可用的，常用一致性雜湊或分散式 B+tree）。
資料放置：物件切成固定大小塊（如 4MB），以副本（常見 3 份）或糾刪碼（erasure coding）存放。
糾刪碼（k+m）：把塊切成 k 份資料分片，算出 m 份同位分片，分散到 k+m 台機器。任意 k 份即可還原——容 m 台故障，空間開銷只有 (k+m)/k 倍，遠優於 3 副本的 3 倍。以 (10+4) 為例：容 4 台故障，空間僅 1.4 倍（RAID 6 是它在單機上的特例）。
一致性協定：副本寫入用多數派（quorum，如 W>R 滿足讀到新值）；修復（anti-entropy）靠 Merkle 樹比對差異，只同步不一致的塊。

Merkle 樹：葉節點是各塊的雜湊，父節點是子雜湊的雜湊。兩台機器比較根雜湊，不同就逐層下行，最後只傳輸真正不同的塊——把「比對 TB 級資料」壓到「傳輸數 KB 的雜湊」。

演算法步驟：物件寫入（副本 + quorum）#

用一致性雜湊定位主節點與副本節點。
主節點把物件切塊，並行寫 W 份（W=2~3）。
收到 W 個成功確認後回應客戶端。
讀取時並行問 R 個副本，取最新版本（版本號或時間戳比較）；R+W > 副本數保證讀到最新。

Python 範例：糾刪碼與 Merkle 樹#

import hashlib

def xor_bytes(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

class SimpleErasureCode:
    """k 資料片 + 1 異或同位（RAID5 式；真實系統用 Reed-Solomon）"""
    def __init__(self, k=4, size=None):
        self.k = k
        self.size = size

    def split(self, data):
        n = -(-len(data) // self.k)
        self.size = n
        shards = [data[i*n:(i+1)*n] for i in range(self.k)]
        shards[-1] = shards[-1].ljust(n, b"\x00")
        parity = b"\x00" * n
        for s in shards: parity = xor_bytes(parity, s)
        return shards + [parity]

    def recover(self, shards, lost):
        avail = [s for i, s in enumerate(shards) if i != lost]
        rec = b"\x00" * self.size
        for s in avail: rec = xor_bytes(rec, s)
        shards[lost] = rec
        return shards

def merkle_root(leaves):
    level = [hashlib.sha256(l).digest() for l in leaves]
    while len(level) > 1:
        if len(level) % 2: level.append(level[-1])
        level = [hashlib.sha256(level[i] + level[i+1]).digest()
                 for i in range(0, len(level), 2)]
    return level[0].hex()[:16]

ec = SimpleErasureCode(k=4)
shards = ec.split(b"Hello, distributed storage world!")
print("分片數:", len(shards), "每片:", len(shards[0]), "bytes")
damaged = list(shards)
damaged[2] = b"\x00" * ec.size            # 假設片 2 遺失
recovered = ec.recover(damaged, 2)
orig = b"Hello, distributed storage world!".ljust(ec.size * 4, b"\x00")
print("還原成功:", b"".join(recovered[:4]) == orig)
print("Merkle 根:", merkle_root(shards))
shards2 = list(shards); shards2[3] = b"XXXX" + b"\x00"*(ec.size-4)
print("資料受損後 Merkle 根不同:", merkle_root(shards2) != merkle_root(shards))

複雜度與 I/O 成本分析#

3 副本：寫 3 次網路 I/O，讀 1 次，空間 3×，恢復快（直接複製）。
(k+m) 糾刪碼：空間 (k+m)/k×（(10+4) 為 1.4×），容 m 故障；但修復需讀 k 份（修復放大），讀取需湊齊 k 份分片，延遲略高——熱資料用副本、冷資料用糾刪碼是業界慣例。
Merkle 樹同步：比對成本 O(塊數) 雜湊計算，網路傳輸僅 O(差異數)。
一致性取捨：W+R>N 保證強一致讀；W=1, R=1 吞吐最高但可能讀到舊版。

練習#

計算 (6+3) 糾刪碼相對 3 副本節省的儲存空間百分比，以及兩者可容故障數。
用 8 個葉的 Merkle 樹模擬兩節點各 1 塊不同，說明比對過程需要傳多少雜湊。
討論：物件儲存為何「禁止修改、只允許整檔覆寫」？這對中繼資料設計有何簡化？