并行和分布式存储
21.1 概述
传统单机数据库将全部数据放在一台服务器的一组磁盘上,当数据规模突破 TB 乃至 PB 级、并发访问达到数万 QPS 时,单机的 CPU、内存与磁盘带宽都成为瓶颈。并行与分布式存储通过把数据切分到多台机器上、并在多台机器上保存副本,来同时获得容量、吞吐与容错能力:
- 容量与吞吐: 台机器共同承担一份数据,总的可用磁盘、内存、网络带宽近似线性扩展。
- 可用性:单机故障不再意味着整个数据库不可用,只要副本仍然存活即可继续服务。
- 就近访问:跨地域部署时可以让副本靠近用户,降低访问延迟。
分布式存储系统需要在一致性(consistency)、可用性(availability) 与分区容忍(partition tolerance) 三者之间做出权衡(CAP 定理)。本章聚焦"数据如何在多台节点上摆放",后两章分别讨论查询与事务处理。
按体系结构可以将并行数据库分为三类:
| 体系结构 | 共享资源 | 典型代表 | 优缺点 |
|---|---|---|---|
| 共享内存(Shared-Memory) | CPU 共享内存与磁盘 | 单机多核 SMP | 编程简单,扩展性受限(几十核) |
| 共享磁盘(Shared-Disk) | 各节点独立内存,共享存储 | Oracle RAC | 存储层瓶颈,扩展性中等 |
| 无共享(Shared-Nothing) | 各节点私有内存与磁盘,仅通过网络通信 | Bigtable、Spanner、Greenplum | 扩展性最好,编程复杂 |
现代云原生数据库多采用无共享架构,并辅以远程共享存储(如 Aurora、PolarDB)以简化副本管理。
21.2 数据分区
分区(partitioning,也称 sharding) 是把一张表按行水平切分到多台节点上,每台节点只保存一部分行。设关系 有 行、分区到 台节点,理想情况下每台节点保存约 行。
21.2.1 分区策略
按照决定"某一行应放到哪台节点"的规则,常见策略有三种:
-
轮转分区(round-robin):按插入顺序把第 行放到第 号节点。
- 优点:均匀,实现简单。
- 缺点:无法根据键快速定位行,任何点查/范围查询都要广播到全部节点。
-
散列分区(hash partitioning):选一个分区属性 ,用散列函数 得到分区号 。
- 优点:点查只需访问一个节点;散列函数选得好可以均衡负载。
- 缺点:不支持高效的范围查询;扩容/缩容时需要重散列。
-
范围分区(range partitioning):定义一个划分向量 ,若 则该行属于第 号节点。
- 优点:范围查询只扫描相关节点;便于按时间维度归档。
- 缺点:容易出现分区偏斜(数据热点集中在少数节点)。
在无共享的连接与聚集计算中,分区属性的选择直接影响能否**"就地"** 完成计算——例如两张表按同一属性散列分区后,等值连接可以完全在各节点本地完成,避免跨节点数据搬运。
21.2.2 分区技术的对比
三种策略在不同工作负载下的表现差异明显:
| 策略 | 点查 | 范围查询 | 全表扫描 | 偏斜风险 |
|---|---|---|---|---|
| 轮转 | 广播到所有节点, 次访问 | 广播 | 完美并行 | 极低 |
| 散列 | 单节点 | 广播(键无序) | 完美并行 | 中等(散列冲突/热键) |
| 范围 | 单节点 | 只扫描区间覆盖的节点 | 完美并行 | 高(数据分布不均) |
选择原则可归纳为:
- 若工作负载以主键点查为主(如键值存储),首选散列分区。
- 若工作负载存在大量范围扫描(如按时间取日志),首选范围分区。
- 若数据分布未知且只做顺序扫描,选轮转分区最省事。
在 Bigtable/HBase 中默认采用行键范围分区,因为其面向的是"取一段时间的连续日志/记录"这类工作负载;而在 Cassandra/DynamoDB 中默认采用一致性散列分区,因为其目标是随机点查。
21.3 分区中的偏斜处理
即便选对了分区策略,实际数据分布也可能高度倾斜——例如某个明星账号的粉丝远多于普通账号,导致对应节点变成热点。偏斜会使加速比远低于理论上的 倍。常见的三种对策如下。
21.3.1 平衡的范围分区向量
对于范围分区,一个直接的做法是通过对样本数据做分位数估计得到均衡的划分向量。设我们希望划出 个大小相当的分区,只需在样本 上取分位数
样本可以来自表的现有直方图统计信息,也可以通过一次预先的采样扫描获得。为了减小抖动,实践中还会引入"目标区间大小",超过阈值就对该区间再做细分。
21.3.2 虚拟节点分区
虚拟节点(virtual nodes,vnodes) 把物理节点数从 提升到 ,把每个虚拟节点再散列/范围映射到某台物理节点上。好处是:
- 单个物理节点承载多个虚拟节点,"平均效应"抹平了单键的偏斜。
- 扩容时只需把部分虚拟节点从旧节点搬到新节点,不必全表重散列。
- 与一致性散列(consistent hashing) 天然结合,减少节点加入/离开时的搬迁量。
一致性散列把节点与键都散列到同一个环上(如 ),键顺时针"归属"到下一个节点。加入一个新节点,只影响它与前一个节点之间的键。Cassandra、DynamoDB、Riak 均采用这种思路。
21.3.3 动态再分区
面对热点漂移(例如某个商品突然爆红),静态划分向量已经无法应对。动态再分区的思路是:
- 监控每个分区的负载(QPS、字节读/写)。
- 当某分区超过阈值时,把它再切一刀(split),得到两个更小的分区,其中一个迁到较空闲的节点。
- 反过来,长期低负载的相邻分区可以合并(merge)。
Bigtable/HBase 中的 tablet split、Spanner 中的 split/move、TiKV 中的 region split-merge 都属于此类机制。为保证迁移期间的可用性,通常采用"新分区先建立复制、再切换路由"的两阶段方案。
21.4 复制
复制(replication) 是在多个节点上保存同一份数据。目的有二:容错(副本可以在主节点宕机时接管),读扩展(读请求可以分发到任一副本)。
21.4.1 副本的位置
副本放置策略需要在容错级别与通信代价之间权衡:
- 同机架副本:延迟低、带宽高,但不能抵抗机架级别故障(电源、交换机)。
- 跨机架副本:抵抗单机架故障。
- 跨可用区/跨数据中心副本:抵抗数据中心级故障,但同步开销大。
一个典型的分级方案是" 副本 + 跨机架/跨 AZ":主副本、同机架热备份、跨 AZ 冷备份,兼顾读延迟与灾备。
21.4.2 更新与副本的一致性
维持副本一致性有两大 范式:
- 同步复制(synchronous):写事务必须等所有副本确认才返回。强一致,但可用性受最慢副本约束。
- 异步复制(asynchronous):主节点写完立即返回,副本在后台追齐。低延迟、高可用,但存在副本滞后(replica lag),读者可能读到旧值。
在此基础上,工业界广泛使用法定人数复制(quorum replication):设有 个副本,读法定人数为 ,写法定人数为 。若满足
则任意一次读操作的 个副本至少与最近一次写操作的 个副本相交于一个副本,从而能读到最新值。常见配置:
| 配置 | 含义 |
|---|---|
| 写全部、读一个:读快,写慢,写不可用于任一副本宕机 | |
| 多数派读写:读写都能容忍一台副本宕机 | |
| 写一读一:延迟最低但可能读到旧值() |
对副本不一致,可通过读修复(read repair) 与后台反熵(anti-entropy) 修复:读到旧副本时顺手把新版本回填过去;后台周期性对副本集做默克尔树比对,快速找到差异段落。
21.5 并行索引
分区之后,索引也必须分区。有两种基本布局:
-
本地索引(local index / partitioned index):每个节点各自为自己的分区维护一份索引。索引数据与主表数据同分区键。
- 优点:更新只需本地事务;点查若命中分区键则性能极佳。
- 缺点:若查询谓词不包含分区键,则需要广播到所有节点做本地查再合并。
-
全局索引(global index):整个集群维护一份逻辑上完整的索引,索引本身按索引键单独分区。
- 优点:非分区键的点查/范围查询无需广播。
- 缺点:一次表更新可能触发跨节点的索引更新,需要分布式事务或异步维护。
工业界常见的取舍:DynamoDB 支持"局部二级索引 LSI(与主表同分区)"和"全局二级索引 GSI(另行分区,异步维护)";MySQL 分库分表中间件通常只支持本地索引,全局索引需要业务自行维护。
21.6 分布式文件系统
分布式数据库的存储层可以直接落在分布式文件系统(DFS) 之上。GFS(Google File System)与其开源实现 HDFS(Hadoop Distributed File System)是最有影响的两个例子。它们的共同设计要点:
- 面向大文件(GB 以上)与顺序读为主的工作负载。
- 文件被切成固定大小的块(chunk / block),典型 64 MB 或 128 MB。
- 每个块有 份副本,跨机架放置。
- 有一个元数据节点(NameNode / Master) 维护"文件→块列表"、"块→节点列表"两级映射,实际数据流不经过元数据节点。
- 客户端读时先向 NameNode 询问块所在节点,然后直接从最近的 DataNode 拉数据;写时采用流水线复制,客户端只推给第一个副本,副本之间接力转发。
这种"单主元数据 + 多副本数据"的结构在延续了近二十年后仍是分布式存储的主流骨架。近年出现的对象存储(如 S3、GCS)在接口层做了简化(无目录语义、扁平命名空间),但底层依旧沿用分块 + 多副本 + 元数据分片的思想。
21.7 并行的键值存储
键值存储(Key-Value Store,KV store) 提供最简单的接口——put(key, value)、get(key)、delete(key)。它牺牲了 SQL 的表达能力,换来极佳的水平扩展性。Bigtable、HBase、Cassandra、DynamoDB、Redis Cluster 都可以纳入这一类别。
21.7.1 数据表示
比起单纯的 (key, value),工业级 KV 系统往往支持列族(column family)、多版本时间戳、稀疏行。以 Bigtable/HBase 为例,一行的数据模型可看作:
(row_key, column_family : qualifier, timestamp) -> value
示例:Webtable 存网页内容与反向链接:
| row_key | contents:html @t1 | contents:html @t2 | anchor:cnn.com | anchor:sina.com |
|---|---|---|---|---|
| com.example.www | <html>...</html> | <html>v2</html> | "Example" | |
| com.example.blog | <html>...</html> | "博客" |
要点:
- 行按行键字典序排序,便于范围扫描。
- 单元格可有多版本,按时间戳倒序保存,读时可指定"最近 版"或"某时间点前最新版"。
- 稀疏矩阵:缺失的列不占空间。
- 列族是访问的物理单元,同列族的列一起存到同一个 SSTable。
Cassandra 引入了分区键 + 聚簇键的两级键结构:分区键决定行归属哪台节点,聚簇键决定行在节点内的排序。这使得 Cassandra 天然支持"按分区键查一批、按聚簇键排序取范围"这种模式。
21.7.2 存储与检索数据
主流的现代 KV 存储底层普遍采用LSM 树(Log-Structured Merge Tree):
- 写入先追加到预写日志(WAL),再写入内存中的MemTable(有序结构,如跳表)。
- MemTable 满后冻结并异步刷成不可变的SSTable 文件。
- 后台Compaction 线程把多个 SSTable 归并成更大的 SSTable,去除旧版本与墓碑(tombstone)。
读路径:MemTable → 各层 SSTable,从新到旧查找,直到找到有效版本。 为加速读,SSTable 内部有布隆过滤器(Bloom Filter) 与稀疏索引。
与 B+ 树相比,LSM 树的写代价从"随机写"降为"顺序写 + 后台归并",代价是读放大与空间放大——需要通过 compaction 策略(size-tiered、leveled)来控制。
21.7.3 对事务的支持
早期的 KV 存储只保证单行原子性,跨行更新要靠业务层实现补偿。后来的系统逐步增强了事务能力:
- CAS(Compare-And-Set):单键上的乐观更新原语,是构建更复杂协议的基石。
- 单行多列原子更新:Bigtable/HBase 支持单行范围内的原子 read-modify-write。
- 多行/跨表事务:Spanner、CockroachDB、TiDB 通过 2PC + Paxos/Raft 提供可串行化事务;Percolator(Bigtable 上)通过分布式乐观锁提供快照隔离。
工业界"KV + 事务"的普遍做法:底层 KV 提供单键 CAS 与多版本,上层通过 2PC 协议协调多分片写入(详见第 23 章)。
21.7.4 不使用声明式查询的管理
不同于 SQL 数据库把"查什么"交给优化器,KV 存储让应用显式指定"从哪台节点、按什么顺序取":
- 需要按非主键查询时,应用要自己维护倒排索引表。
- 需要连接两张表时,应用可以选择"客户端连接"或"应用层反规范化"。
- 需要聚集时,通常配合 MapReduce/Spark 之类的离线框架。
这让 KV 存储更贴近底层,但把 SQL 查询优化器承担的复杂度转嫁给了应用开发者。
21.7.5 性能优化
KV 存储的常见性能优化手段:
- 批量操作:把 100 个
put合成一个 RPC,摊薄网络往返延迟。 - 异步/流水线接口:客户端一次发多个请求,服务端顺序响应。
- 数据本地化:把关联数据放到同一行(同分区键),减少跨节点调用。
- 压缩与列存:列族内做块级压缩(Snappy、Zstd);对分析场景可以按列存储。
- 热点缓存:进程内 LRU 或独立缓存层(Memcached、Redis)。
- 分层存储:热数据在 SSD/内存,冷数据在 HDD 或对象存储。
21.8 总结
- 大规模数据必须分区到多台节点,常见策略有轮转/散列/范围三种,各有适用工作负载与偏斜风险。
- 偏斜可以通过平衡范围向量、虚拟节点、动态再分区(split/merge)来治理。
- 副本同时提供容错与读扩展;一致性可以用同步/异步或法定人数()来调节。
- 索引在分区之上有本地与全局两种布局,选择取决于查询是否总能带上分区键。
- 分布式文件系统(GFS/HDFS)用"块 + 副本 + 单一元数据"支撑了几乎所有大数据栈。
- 并行 KV 存储(Bigtable/HBase/Cassandra/DynamoDB)以 LSM 树 + 列族数据模型为基础,牺牲部分表达能力换取极致的水平扩展能力,是本章讨论的现代分布式存储主线。
下一章将在此存储层之上讨论查询处理,尤其是排序、连接与聚集这几种基本运算的并行化。