分布式存储基础

上一课的 NFS 和 iSCSI 本质上还是"一台服务器 + 网线"：服务器就是天花板，也是单点。分布式存储要把数据摊到几十、几百台机器上，这时候冒出来三个绕不开的问题：数据放在哪、多份数据怎么保持一致、坏了怎么办。Ceph、GPFS、MinIO、JuiceFS……每个系统的设计文档，本质上都是在回答这三个问题。

学完这一课，你能解释哈希取模、一致性哈希和 CRUSH 式放置各自的优缺点，并用几十行 Python 亲手验证；能用 W+R>N 判断一个法定人数配置是否强一致；知道 Paxos/Raft 在存储系统里负责什么；会按故障域设计放置规则，并用 AFR 和 MTTR 粗算一套集群的可用性。

#为什么要分布式

单机存储能走多远？一台 2U 服务器塞 24 块 30 TB 的 NVMe，裸容量 720 TB，看起来很多。但它有三道墙：

代价同样明确：网络延迟、一致性协议的开销、复杂得多的运维。

#数据分布：一个对象该放在哪

给定一个对象名 photos/2026/cat.jpg，系统必须能回答"它在哪几台机器上"。写的时候要回答，读的时候也要回答，而且答案必须一致。有四种基本思路。

#集中式元数据表

最直接：建一张表，记录每个对象（或每个数据块）在哪。HDFS 的 NameNode、GFS 的 Master、很多商业 NAS 都是这样。

客户端 ──"cat.jpg 在哪?"──▶ 元数据服务器 ──"node3, node7, node9"──▶ 客户端 ──读写──▶ node3...

• 优点：放置完全灵活，可以按容量、负载任意调度，迁移数据只需改表；
• 缺点：元数据服务器是瓶颈和单点，每次访问多一跳；表的规模随对象数增长，几十亿对象时内存装不下。

#哈希取模

node = hash(key) % N。任何客户端都能自己算出位置，不需要查表。问题出在扩容：N 从 10 变成 11，几乎每个 key 的余数都变了，约 91% 的数据需要搬家。

#一致性哈希

Amazon Dynamo、OpenStack Swift、Cassandra 用的是一致性哈希（Consistent Hashing）：把哈希空间想象成一个环，每个节点在环上占若干个点（虚拟节点），key 顺时针找到的第一个节点就是它的归属。

                 0
            ┌────●────┐           ● = 节点的虚拟节点
       nodeC●          ●nodeA     ○ = key
           │   ○ key1   │         key1 顺时针遇到的第一个节点是 nodeA
       nodeB●          ●nodeC     新增 nodeD 只会"切走"它两侧一小段
            └────●────┘
               nodeB

新增一个节点，它只接管环上相邻的一小段，其他数据纹丝不动。虚拟节点让每台机器在环上分散成很多段，负载更均匀，也方便按权重分配（大盘多给几个虚拟节点）。

动手验证一下两者的差别：

import hashlib, bisect

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

KEYS = [f"obj-{i}" for i in range(100_000)]

def mod_n(nodes):
    return {k: nodes[h(k) % len(nodes)] for k in KEYS}

def ring(nodes, vnodes=100):
    points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
    hashes = [p[0] for p in points]
    def lookup(k):
        i = bisect.bisect(hashes, h(k)) % len(points)
        return points[i][1]
    return {k: lookup(k) for k in KEYS}

def moved(a, b):
    return sum(a[k] != b[k] for k in KEYS) / len(KEYS)

old = [f"node{i}" for i in range(10)]
new = old + ["node10"]
print(f"哈希取模   10→11 节点，迁移比例: {moved(mod_n(old), mod_n(new)):.1%}")
print(f"一致性哈希 10→11 节点，迁移比例: {moved(ring(old), ring(new)):.1%}")
print(f"理论最小迁移比例: {1/11:.1%}")

$ python3 placement.py
哈希取模   10→11 节点，迁移比例: 90.9%
一致性哈希 10→11 节点，迁移比例: 9.0%
理论最小迁移比例: 9.1%

一致性哈希几乎达到了理论最优：新节点应该分到 1/11 的数据，就只搬 1/11。

#CRUSH 式伪随机确定性放置

一致性哈希解决了扩容问题，但它不认识"机架"：三个副本完全可能落在同一个机柜里，机柜断电就三副本全灭。Ceph 的 CRUSH（Controlled Replication Under Scalable Hashing）在"客户端自己算、不查表"的基础上，加入了两样东西：

1. 层级拓扑：集群被描述成一棵树（root → 机房 → 机架 → 主机 → 盘），每个节点带权重；
2. 放置规则：比如"从 root 出发，选 3 个不同的主机，每个主机里选 1 块盘"。

CRUSH 在每一层用 straw2 算法挑选子节点：每个候选根据 hash(key, 候选) 抽一根"签"，签长按权重缩放，最长者胜。因为每个候选的签只和它自己有关，新增一个候选时，只有被新候选"抽赢"的那部分 key 会迁移，而且只迁往新候选。用 Python 模拟一下：

import hashlib, math

def u(key: str, item: str) -> float:
    """(key, item) → (0,1] 之间确定的伪随机数"""
    x = int.from_bytes(hashlib.sha256(f"{key}/{item}".encode()).digest()[:8], "big")
    return (x + 1) / 2**64

def straw2(key, items, weights, r=0):
    # 每个候选"抽一根签"，签长 = ln(u) / 权重，最长者胜
    return max(items, key=lambda it: math.log(u(f"{key}#{r}", it)) / weights[it])

def place(key, hosts, weights, replicas=3):
    """选 replicas 个不同主机：重名就换一个 r 重抽（CRUSH 的 retry 思路）"""
    chosen, r = [], 0
    while len(chosen) < replicas:
        h = straw2(key, hosts, weights, r)
        if h not in chosen:
            chosen.append(h)
        r += 1
    return chosen

KEYS = [f"pg-{i}" for i in range(20000)]
hosts = [f"host{i}" for i in range(10)]
w = {h: 1.0 for h in hosts}
before = {k: straw2(k, hosts, w) for k in KEYS}

hosts2 = hosts + ["host10"]; w2 = dict(w, host10=1.0)
after = {k: straw2(k, hosts2, w2) for k in KEYS}
moved = [k for k in KEYS if before[k] != after[k]]
print(f"新增 1 台主机，迁移比例 {len(moved)/len(KEYS):.1%}，"
      f"全部迁往新主机: {all(after[k] == 'host10' for k in moved)}")

w3 = dict(w2, host10=2.0)   # 新主机盘是别人的两倍
share = sum(straw2(k, hosts2, w3) == "host10" for k in KEYS) / len(KEYS)
print(f"host10 权重 2.0 时分到 {share:.1%} 的数据（理论 {2/12:.1%}）")
print("pg-42 的三副本:", place("pg-42", hosts2, w2))

$ python3 straw2.py
新增 1 台主机，迁移比例 9.1%，全部迁往新主机: True
host10 权重 2.0 时分到 16.7% 的数据（理论 16.7%）
pg-42 的三副本: ['host0', 'host7', 'host5']

三条性质全部成立：迁移量最小、迁移只流向新节点、按权重分配。真实的 CRUSH 还有两层间接：对象先哈希到放置组（PG），再由 CRUSH 把 PG 映射到盘，这样集群只需要跟踪几千个 PG 而不是几十亿个对象。细节留到 Ceph 架构。

#四种方式对比

实际系统常常混用：MinIO 用哈希把对象分到固定的纠删集（erasure set），JuiceFS 用数据库存元数据、用对象存储存数据，3FS 用 FoundationDB 存元数据、用链表配置决定数据放置。

#一致性：多份数据说的是不是同一件事

数据存了三份，客户端写入时，要等几份写完才返回？读的时候读哪一份？这就是一致性模型要回答的问题。

#强一致与最终一致

CAP 定理说：网络分区发生时，一致性（C）和可用性（A）只能二选一。存储系统几乎都选 C——宁可暂停服务，也不能把数据写坏。对象存储的跨地域复制是少数选 A 的场景。

#法定人数：W + R > N

在无主（leaderless）复制里，常用法定人数（quorum）调节一致性：N 份副本，写入要 W 份确认才算成功，读取要读 R 份取最新版本。

只要 W + R > N，读集合和写集合必然有交集，读一定能看到最新写入。

N=3, W=2, R=2:    写入确认: [A] [B]  C          读取: A  [B] [C]
                            └─── B 同时在两个集合里 ───┘  → 一定读到新值

N=3, W=1, R=1:    写入确认: [A]  B   C          读取: A   B  [C]
                            没有交集 → 可能读到旧值

Ceph RADOS 不用这种 quorum，而是主副本（primary-copy）复制：每个 PG 有一个主 OSD，客户端只和主 OSD 通信，主 OSD 把写入转发给其他副本，所有副本都持久化后才确认客户端。读默认也只从主 OSD 读。它相当于 W=N、R=1，再加上"只要可写副本数不低于 min_size 就继续服务"的降级规则。

#Paxos 与 Raft：谁说了算

数据可以靠复制保证可靠，但"集群里有哪些节点、谁是主、当前拓扑是什么"这类元数据必须所有人看法一致，否则就会像网络存储那一课的脑裂一样，两个节点都以为自己是主。

Paxos 和 Raft 就是解决这个问题的共识算法。核心思想一句话：2f+1 个成员组成一个组，任何决定必须获得多数（f+1）同意。任何两个多数派必然有交集，所以不可能同时产生两个互相矛盾的决定。

存储系统里的共识组：

• Ceph MON：基于 Paxos 维护 cluster map（MON、OSD、CRUSH、MDS 等各种 map），通常 3 或 5 个；
• etcd（Kubernetes 的大脑）、TiKV（JuiceFS 的元数据引擎之一）：Raft；
• GPFS：仲裁节点（quorum node）选出集群管理者；
• FoundationDB（3FS 的元数据）：自己的协调者（coordinators）+ 事务系统。

#故障域与放置规则

#故障是相关的

副本数不等于可靠性。三个副本放在同一台机器的三块盘上，这台机器电源一坏，三份一起没。故障域（failure domain）是"会一起坏的一组东西"：

放置规则的原则：同一份数据的多个副本（或 EC 分片）必须分布在不同的故障域。Ceph 默认的副本规则是 chooseleaf firstn 0 type host，即每个副本在不同主机上。

#故障域选多大

故障域越大越安全，但约束也越多：

• 选 rack 作为故障域、三副本，至少要 3 个机架；EC 8+3 就要至少 11 个机架；
• 各故障域容量要大致均衡：3 个机架里有一个特别小，它会最先写满，整个存储池跟着写满；
• 一个故障域坏掉后，它的数据要在剩余故障域里重建，剩余空间必须装得下。

#可用性计算

#AFR、MTTF 与 MTTR

• AFR（Annualized Failure Rate，年故障率）：一年内坏掉的盘占比。企业级 HDD 和 SSD 的实测 AFR 通常在 0.5%～2%，Backblaze 每季度公开的硬盘统计是很好的参考；
• MTTF（Mean Time To Failure）：平均无故障时间，大致是 AFR 的倒数（AFR 1% ≈ MTTF 87.6 万小时）；
• MTTR（Mean Time To Repair）：从故障到恢复冗余的时间。对分布式存储，它主要是数据重建时间，而不是换盘时间。

先感受一下规模效应：1000 块盘、AFR 2%，一年坏 20 块，平均每 18 天坏一块。在分布式存储里，坏盘不是事故，是日常。

单个组件的稳态可用性：

A = MTTF / (MTTF + MTTR)

MTTR 出现在分母里，所以缩短重建时间和提高硬件质量一样有效。这也是 Ceph 把数据打散成大量 PG 的原因之一：一块盘坏了，几十上百块盘同时参与重建，而不是像传统 RAID 那样只有同组几块盘在干活。

#串联与冗余

多个组件串联（任一坏了都不可用）时可用性相乘；冗余（至少 k 个可用即可）时用二项分布计算：

from math import comb

def at_least(k, n, a):
    """n 个独立副本/节点中至少 k 个可用的概率"""
    return sum(comb(n, i) * a**i * (1 - a)**(n - i) for i in range(k, n + 1))

a = 0.99   # 单节点可用性：一年约 3.65 天不可用
print(f"单节点            : {a:.6f}")
print(f"3 副本，至少 1 个 : {at_least(1, 3, a):.6f}")
print(f"3 副本，至少 2 个 : {at_least(2, 3, a):.6f}   # min_size=2 时可写")
print(f"EC 4+2，至少 4 个 : {at_least(4, 6, a):.6f}")
print(f"EC 4+2，至少 5 个 : {at_least(5, 6, a):.6f}   # min_size=k+1 时可写")

$ python3 avail.py
单节点            : 0.990000
3 副本，至少 1 个 : 0.999999
3 副本，至少 2 个 : 0.999702   # min_size=2 时可写
EC 4+2，至少 4 个 : 0.999980
EC 4+2，至少 5 个 : 0.998540   # min_size=k+1 时可写

几个值得注意的结论：

1. "数据不丢"（至少 1 份）和"可以写入"（至少 min_size 份）是两个不同的可用性，后者低得多；
2. EC 4+2 和三副本都能容忍 2 个故障，但为了安全，Ceph 默认要求 k+1 个分片在线才允许写，"可写"的可用性比三副本低；
3. 这里假设故障相互独立。现实里同批次的盘会一起老化，一个机架断电会带走一片——这正是要按故障域放置的原因，也是这类计算只能当数量级参考的原因。

把"几个 9"换算成停机时间，方便和业务方沟通：

#动手练习

1. 运行 placement.py，把虚拟节点数 vnodes 分别改成 1、10、100、1000，统计每个节点分到的 key 数量的最大值与最小值之比，观察虚拟节点对均衡度的影响。
2. 修改 straw2.py，把 host3 的权重改为 0（模拟下线），验证只有原本在 host3 上的数据发生迁移，并且均匀分散到了其他主机。
3. 给 straw2.py 加一层拓扑：4 个机架、每个机架 3 台主机，实现"先选 3 个不同机架、再在每个机架里选 1 台主机"的规则，并验证任意一个 key 的三副本都不在同一机架。
4. 用 avail.py 计算：单节点可用性分别为 99%、99.9% 时，三副本（min_size=2）和 EC 8+3（min_size=9）的可写可用性。
5. 估算：一个集群 600 块 16 TB HDD、AFR 1.5%，单盘重建需要 8 小时。一年大约要处理多少次坏盘？任意时刻处于重建中的概率大约是多少？

#自测

#参考资料

• Sage A. Weil 等：CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data（SC'06）
• Giuseppe DeCandia 等：Dynamo: Amazon's Highly Available Key-value Store（SOSP'07）
• Diego Ongaro、John Ousterhout：In Search of an Understandable Consensus Algorithm（Raft 论文）
• Raft 共识算法可视化
• Ceph 文档：CRUSH Maps
• Ceph 文档：Monitor Config Reference
• Backblaze 硬盘故障率统计
• Martin Kleppmann,《Designing Data-Intensive Applications》第 5 章 Replication、第 9 章 Consistency and Consensus