数据库分片 — 单机的尽头是分片，分片的尽头是后悔Sharding: Hash vs Range, Consistent Hashing, Hot Spots, Resharding

问题场景

『加一台机器就能扛 10 倍流量』——这是新手对 sharding 的幻想。现实是：分片是不可逆的架构债务。一旦分了，你失去跨分片事务、失去全表 join、失去自动二级索引；获得的是『可以无限加机器』和『从此每个 schema change 都是噩梦』。

那为什么还分？因为单机有硬上限：Postgres 单机写 ~50k QPS、数据量 ~10TB；MySQL InnoDB buffer pool 几百 GB 就到顶；垂直加 CPU/内存/SSD 价格曲线非线性陡升（r6i.32xlarge 月费 ~$8k，再大没有 SKU 了）。当单机不够，sharding 是必然。问题不是要不要分，是何时分、怎么分、怎么改。

反面教材：Foursquare 2010 年 MongoDB 单 shard 装不下，迁移时一台从节点 OOM 全集群雪崩，宕机 11 小时；Slack 2017 年第一次 reshard 花了 9 个月（按 team_id 分片，热门 workspace 还是不均匀）；Notion 2021 年从单 Postgres 拆 32 shard 用了半年，2023 年又从 32 拆到 480。

需求与约束（面试必问）

• 当前规模与增长：数据量、写 QPS、读 QPS、增速。如果一年内不会超过单机上限，不要分。
• 主导访问模式：90% 的查询是按什么 key 走的？这就是分片键候选。
• 跨分片查询占比：如果 30% 查询要 fan-out 到所有 shard，分片几乎没收益。
• 数据分布：用户、订单、租户的『size 分布』是均匀还是长尾？长尾 = hot shard 风险。
• 事务需求：跨用户/跨租户事务多吗？分片后这些必须改为 saga 或最终一致。
• 未来再分代价：能接受 1-2 次再分片（数月工程）吗？还是要 consistent hashing 一开始就免再分？
• 运维与组件成熟度：自建 application-side sharding？用 Vitess（MySQL）/ Citus（Postgres）？还是直接换分布式 SQL（TiDB / CockroachDB）？

高层架构

graph TD
    APP["Application"]
    PROXY["Shard Router
Vitess vtgate / 应用层 / Citus coordinator"]
    META["Shard Metadata
ZK / etcd / config DB"]

    S1[("Shard 0
user_id % 16 == 0")]
    S2[("Shard 1
user_id % 16 == 1")]
    S3[("...")]
    SN[("Shard 15
user_id % 16 == 15")]

    R1[("Shard 0
Replica")]
    R2[("Shard 1
Replica")]

    APP --> PROXY
    PROXY -.读 routing 表.-> META
    PROXY --> S1
    PROXY --> S2
    PROXY --> S3
    PROXY --> SN
    S1 -.async repl.-> R1
    S2 -.async repl.-> R2

    classDef app fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    classDef proxy fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    classDef meta fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef shard fill:#0e2030,stroke:#5eead4,color:#e8eef5
    class APP app
    class PROXY proxy
    class META meta
    class S1,S2,S3,SN,R1,R2 shard

三层：应用 → 路由层（查 metadata 决定去哪个 shard）→ 物理 shard（每个 shard 还有自己的主从复制）

关键技术点

1. Hash sharding vs Range sharding：性能、热点、跨分片查询的三角

原理：两种基本分片策略，决定数据怎么映射到物理节点。

# 简单 hash sharding（应用层）
import hashlib
NUM_SHARDS = 16

def shard_of(user_id: int) -> int:
    h = hashlib.md5(str(user_id).encode()).digest()
    return int.from_bytes(h[:4], 'big') % NUM_SHARDS

def get_conn(user_id):
    return shard_pool[shard_of(user_id)]

# ⚠️ 不要用 Python 内置 hash()——进程间不一致 (PYTHONHASHSEED)
# ⚠️ 不要直接 user_id % N——若 user_id 顺序生成且 N 很小,
#    新用户会集中落在少数 shard

2. Consistent Hashing：让加节点不要全表搬

原理：朴素 hash(key) % N 在 N 变化时，几乎所有 key 都要迁移（N: 8→9 时 ~88% 的 key 重映射）。Consistent hashing：把 hash 空间想象成一个环（0 到 2^32），节点和 key 都映射到环上，key 顺时针找到第一个节点。加/减一个节点只影响相邻的一段 key。

graph LR
    subgraph Ring["Hash Ring (2^32)"]
        direction LR
        N1["Node A
vnode 0..200"]
        N2["Node B
vnode 201..400"]
        N3["Node C
vnode 401..600"]
        N4["Node D (new)
插入处只接管
这段 key"]
    end
    K1["key1 hash=150"] --> N1
    K2["key2 hash=350"] --> N2
    K3["key3 hash=480"] --> N3
    K4["key4 hash=270"] --> N4
    classDef node fill:#0e2030,stroke:#5eead4,color:#e8eef5
    classDef key fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef new fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class N1,N2,N3 node
    class K1,K2,K3,K4 key
    class N4 new

但裸 consistent hashing 有问题：节点分布不均时负载倾斜。虚拟节点（vnode）解决——每个物理节点在环上放 100-200 个虚拟点，统计上更均匀；删节点时其负载也均匀分摊到其他节点而非全压到下一个邻居。

# Consistent hashing 简化版 (vnode 版)
import bisect, hashlib

class ConsistentHash:
    def __init__(self, nodes, vnodes=150):
        self.ring = []        # sorted list of (hash, node)
        self.vnodes = vnodes
        for n in nodes:
            self.add_node(n)

    def _h(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.vnodes):
            h = self._h(f"{node}#{i}")
            bisect.insort(self.ring, (h, node))

    def get(self, key):
        h = self._h(key)
        i = bisect.bisect(self.ring, (h, ''))
        return self.ring[i % len(self.ring)][1]

# 加 1 个节点 (N → N+1), 重映射比例 ≈ 1/(N+1)
# 朴素 mod: 重映射比例 ≈ N/(N+1)

3. Hot Spots：均匀分片为什么仍会被打爆

原理：『统计均匀』 ≠ 『实际均匀』。三类 hot spot：

1. Key hot：单 key 流量过高（明星账号 1 亿粉、爆款商品 100k QPS）。哈希再好，这个 key 永远落同一 shard。
2. Range hot：range 分片下『最新数据』集中（按 timestamp 分片，写流量永远在最后一个 shard）。
3. Tenant hot：multi-tenant 系统中大客户（Slack 中的 Salesforce、Notion 中的 Adobe）占用一个 shard 的 90%。

缓解策略：

# Salting 示例：write-heavy celebrity 账户的 follower 表
# 原 schema:
#   follower(celebrity_id, follower_id, ts)  partition by celebrity_id
# 问题: celebrity_id=42 (Elon) 写 QPS 50k, 远超单 partition 1000 WCU 上限

# 改造：加散列后缀
shard_suffix = random.randint(0, 15)
write(table, partition=f"42#{shard_suffix}", row={...})

# 读时 fan-out
results = []
for i in range(16):
    results += query(partition=f"42#{i}")
return merge_sort_by_ts(results)

# Trade-off: 读吞吐放大 16x; 但写解决了
# 适合 write >> read 场景; 反过来不适用

4. Resharding：从 32 个 shard 到 480 个的工程噩梦

原理：再分片是分布式系统中最痛的操作之一，因为它要做到：（a）数据从旧拓扑搬到新拓扑；（b）业务不能停；（c）切换前后强一致；（d）出错可回滚。没有 shadow read/write 和回滚预案的 resharding 都是赌博。

sequenceDiagram
    participant App
    participant Router
    participant Old as Old Shard (16)
    participant New as New Shard (32)

    Note over Router: Phase 1 · 双写
    App->>Router: write k1
    Router->>Old: write k1 (主)
    Router->>New: write k1 (影子, 异步)

    Note over Router: Phase 2 · backfill 历史
    Router-->>New: 后台 copy: 全量 + 增量 CDC

    Note over Router: Phase 3 · shadow read 校验
    App->>Router: read k1
    Router->>Old: read (返回给用户)
    Router->>New: read (对比, 不返回)
    Note right of Router: diff > 阈值 → 暂停切换

    Note over Router: Phase 4 · 切流 (按 % 灰度)
    App->>Router: write k1
    Router->>New: write k1 (主)
    Router->>Old: write k1 (回写, 备份)

    Note over Router: Phase 5 · 拆链 / 删除旧数据

# Resharding 关键: idempotent dual write + version stamp
def write(key, value):
    version = current_ms()
    # 双写, 带 version 防止旧值覆盖新值
    write_old(key, value, version)
    if reshard_phase >= DUAL_WRITE:
        try:
            write_new(key, value, version)  # if-newer
        except Exception as e:
            log_drift(key, e)   # 告警, 不阻塞主流程

def read(key):
    if reshard_phase == SHADOW_READ:
        v_old = read_old(key)
        v_new = read_new(key)
        if v_old != v_new:
            metrics.diff_count.inc()
            log_diff(key, v_old, v_new)
        return v_old  # 还是返回老的, 直到切换
    elif reshard_phase >= CUTOVER:
        return read_new(key)
    else:
        return read_old(key)

扩展与优化（增长后怎么办）

• 选择 shard key 比选数据库更重要。错的 shard key 是一辈子的债。原则：高基数（cardinality 高，区分度好）、与主导查询模式匹配（90% 查询带这个 key）、随时间稳定（不会从一个值变到另一个）。
• Co-location（同位）：相关数据放同一 shard。Pinterest 把 user 的 boards 和 pins 跟随 user shard；Citus 用 colocation group；Vitess 用 keyspace + sequence。这样 user 维度的事务和 join 都在单 shard 完成。
• 跨 shard 二级索引：要么应用层维护『全局索引表』（同步双写），要么走外部搜索（ES / 反向索引服务）。强一致跨 shard 索引非常贵。
• 跨 shard join / 聚合：放弃实时 join；通过 CDC → 数仓做分析；交互 API 改成 fan-out + 应用层 merge（限制 K 个 shard）。
• 容量规划提前 2x：每个 shard 占用不要超过 50%，否则再分片来不及。Foursquare 教训。
• 逻辑 shard 远多于物理实例（1024 vs 32）：扩容时迁移逻辑 shard，不改路由函数，零代码改动。

常见陷阱

面试问题示例

1. 设计 Twitter，你怎么分 tweets 表？user_id 还是 tweet_id？为什么？分别有什么问题？
2. 解释 consistent hashing 和 vnode；用一个『加节点』场景说明 mod hash 与 consistent hash 的迁移比例差异。
3. DynamoDB 一个 partition 突然被限流（hot partition），你不能改 schema，能想到几种缓解方案？
4. 你设计一个 multi-tenant SaaS，某客户突然涨到全平台 30% 流量，怎么把它『单独搬出来』而其他人无感？
5. online resharding 的关键阶段是什么？双写期间数据漂移怎么发现？
6. 为什么 logical shard 数量要远大于物理实例数？给一个具体的扩容场景说明它的好处。

关键资源

• 《Designing Data-Intensive Applications》Ch 6 — Partitioning（Kleppmann）：hash/range、二级索引、resharding 的系统讨论，本主题最权威读物。
• Notion 工程博客《Sharding Postgres》(2021) + 《The great re-shard》(2023)：从单库 → 32 shard → 480 shard 的完整复盘，含 logical-over-physical 设计。
• Vitess 官方文档 + Slack 博客《Scaling Datastores at Slack with Vitess》：MySQL 横向扩展的工业级参考。

English Summary

Sharding is irreversible architectural debt — you trade away cross-shard transactions, joins, and global secondary indexes for unbounded horizontal scale. Two basic strategies: hash sharding distributes evenly but kills range scans; range sharding preserves locality but creates hotspots on monotonically increasing keys. Consistent hashing with virtual nodes minimizes data movement when adding/removing nodes — N→N+1 moves only 1/N of keys versus ~N/(N+1) with naive mod-hash. Hot spots are inevitable: celebrity accounts, tenant whales, and time-series tails all break statistical uniformity. Mitigations include salting, dedicated shards, adaptive capacity, and caching. Modern best practice is logical-over-physical sharding: provision many more logical shards (e.g., 1024) than physical instances, so scaling out is just migrating logical shards without changing the routing hash. Online resharding requires dual writes, shadow reads, and gradual cutover; expect 3-9 months of engineering. Default to vertical scale and read replicas first — only shard when you must.

深入思考（点击展开答案）