第5章：分布式数据（Distributed Data）

一、导读

1.1 本章学习目标

第5章从单机存储引擎扩展到分布式数据系统。当数据量或访问量超过单机能力时，必须将数据分布到多个节点上。这引入了数据分片、复制策略、一致性哈希等核心问题。

本章核心学习目标：

掌握数据分片的策略：哈希分片、范围分片、一致性哈希的优劣
理解复制策略：单主、多主、无主复制的权衡
掌握 CAP 定理的含义：为什么不能同时满足一致性、可用性和分区容忍？
理解 PACELC 扩展：在没有分区时，延迟和一致性如何权衡？
掌握数据放置策略：如何将数据分配到节点以平衡负载？

1.2 为什么本章如此重要

几乎所有现代数据库系统都是分布式的——从 MySQL 的主从复制，到 Cassandra 的无主复制，再到 TiDB 的分布式事务。理解分布式数据的基本原理，是设计和运维大规模系统的基础。

1.3 核心问题引导

一致性哈希如何解决数据分片中的负载不均衡问题？

CAP 定理中的"一致性"具体指什么？与 ACID 中的一致性有何不同？

为什么 Cassandra 选择最终一致性而不是强一致性？

数据分片的再平衡（Rebalancing）为什么是一个棘手的问题？

二、核心概念详解

2.1 数据分片（Sharding/Partitioning）

2.1.1 范围分片（Range Partitioning）

按键值的范围将数据分配到不同节点：

节点 0: [A, D)   → 键值以 A-C 开头的数据
节点 1: [D, H)   → 键值以 D-G 开头的数据
节点 2: [H, Z]   → 键值以 H-Z 开头的数据

优势: 范围查询高效（只需访问一个节点）
劣势: 数据倾斜（某些范围的数据量远大于其他范围）
代表: HBase, MongoDB (默认)

2.1.2 哈希分片（Hash Partitioning）

对键值取哈希后分配到节点：

shard = hash(key) % num_shards

key="user:1001" → hash=0x3a7f → 0x3a7f % 4 = 3 → 节点 3
key="user:1002" → hash=0x8b2c → 0x8b2c % 4 = 0 → 节点 0

优势: 数据分布均匀
劣势: 范围查询需要广播到所有节点
代表: Cassandra, Voldemort

2.1.3 一致性哈希（Consistent Hashing）

一致性哈希解决了普通哈希分片在节点增减时大量数据迁移的问题：

哈希环 (0 到 2^32-1):

       节点A (hash=1000)
         /
        /
节点D  /   节点B (hash=8000)
(15000) \ /
         \
          \
       节点C (hash=22000)

数据分配:
key1 → hash=3000  → 顺时针找到节点B
key2 → hash=12000 → 顺时针找到节点C
key3 → hash=25000 → 顺时针找到节点A

新增节点E (hash=5000):
只需要将 A→B 之间的数据从 B 迁移到 E
其他节点的数据不受影响

虚拟节点:
每个物理节点对应多个虚拟节点（如 100-200 个）
解决数据倾斜问题，使分布更均匀

2.2 复制策略

2.2.1 单主复制（Single-Leader）

写入流程:
Client → Leader → Follower 1
                  → Follower 2

同步复制: Leader 等待所有 Follower 确认 → 强一致，延迟高
异步复制: Leader 不等待 Follower → 低延迟，可能丢数据
半同步: Leader 等待至少一个 Follower → 折中方案

代表: MySQL 主从复制, PostgreSQL Streaming Replication

2.2.2 多主复制（Multi-Leader）

写入流程:
Client → Leader A → Leader B
Client → Leader B → Leader A

冲突解决:
- 最后写入胜出 (LWW): 用时间戳解决冲突
- 合并: 自动合并不同节点的修改
- 手动: 交给用户决定

代表: GitHub (git), CouchDB, Baidu DTS

2.2.3 无主复制（Leaderless）

写入流程:
Client → 同时发送到 N 个节点
读取流程:
Client → 同时从 N 个节点读取
         → 取最新版本（通过版本号或时间戳）

Quorum 机制:
写入: W 个节点确认
读取: R 个节点确认
条件: W + R > N → 保证读写重叠，一定能读到最新数据

典型配置: N=3, W=2, R=2
代表: Cassandra, DynamoDB, Riak

2.3 CAP 定理

CAP 定理指出，分布式系统不可能同时满足以下三个性质：

C（Consistency）：所有节点在同一时刻看到相同的数据
A（Availability）：每个请求都能得到非错误的响应
P（Partition Tolerance）：即使网络分区，系统仍能运行

网络分区时:
节点A ←──×──→ 节点B

选择 C: 拒绝部分请求，保证一致性 → CP 系统
选择 A: 继续接受请求，但可能不一致 → AP 系统

注意: P 不是可选项——网络分区一定会发生
真正的选择是: 分区发生时，选 C 还是 A?

CP 系统: ZooKeeper, HBase, Redis Cluster
AP 系统: Cassandra, DynamoDB, CouchDB

2.4 PACELC 扩展

PACELC 是对 CAP 的扩展，考虑了没有分区时的情况：

Partition: 分区发生时，选 A 还是 C？
Else: 没有分区时，选 Latency 还是 Consistency？

PACELC 分类:
CP/EC: 分区时选一致性，正常时选一致性 (如 ZooKeeper)
CP/EL: 分区时选一致性，正常时选延迟 (如 Bigtable)
AP/EL: 分区时选可用性，正常时选延迟 (如 Cassandra, DynamoDB)
AP/AL: 分区时选可用性，正常时也选延迟 (如 PNUTS)

三、实战案例

3.1 案例一：一致性哈希的实现

python

import hashlib
from sortedcontainers import SortedDict

class ConsistentHash:
    def __init__(self, replicas=100):
        self.replicas = replicas
        self.ring = SortedDict()
        self.nodes = {}

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

    def add_node(self, node):
        self.nodes[node] = True
        for i in range(self.replicas):
            vnode_key = f"{node}:vnode{i}"
            vnode_hash = self._hash(vnode_key)
            self.ring[vnode_hash] = node

    def remove_node(self, node):
        self.nodes.pop(node, None)
        for i in range(self.replicas):
            vnode_key = f"{node}:vnode{i}"
            vnode_hash = self._hash(vnode_key)
            self.ring.pop(vnode_hash, None)

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = self.ring.bisect_left(h)
        if idx == len(self.ring):
            idx = 0
        return self.ring.iloc[idx]

# 测试
ch = ConsistentHash(replicas=150)
for node in ["node_a", "node_b", "node_c"]:
    ch.add_node(node)

# 分布测试
from collections import Counter
distribution = Counter()
for i in range(10000):
    node = ch.get_node(f"key_{i}")
    distribution[node] += 1

for node, count in sorted(distribution.items()):
    print(f"{node}: {count} keys ({count/100:.1f}%)")

# 输出示例 (虚拟节点使分布更均匀):
# node_a: 3412 keys (34.1%)
# node_b: 3298 keys (33.0%)
# node_c: 3290 keys (32.9%)

四、本章小结

数据分片将数据分布到多个节点，范围分片适合范围查询，哈希分片保证均匀分布

一致性哈希通过虚拟节点解决数据倾斜，并在节点增减时最小化数据迁移

复制策略分为单主、多主、无主三种模式，各有适用场景

CAP 定理表明分区时必须在一一致性和可用性之间选择；PACELC 进一步考虑了正常情况下的延迟与一致性权衡

五、思考与练习

思考题

一致性哈希中，虚拟节点的数量对系统有什么影响？太少或太多各有什么问题？

为什么 Cassandra 选择 AP 而不是 CP？这对其应用场景意味着什么？

在多主复制中，如何处理跨节点的写冲突？

编程练习

实现一致性哈希，测试不同虚拟节点数量下的数据分布均匀度。

模拟 Quorum 读写：实现 N=5, W=3, R=3 的读写逻辑，验证读写重叠保证一致性。