分区 (Partitioning)

复制(第 5 章)在多个节点上保留同一数据的副本。但若数据集对任何单节点太大、或查询负载太重,你需要把数据拆成叫分区(partition)(也叫分片 shard)的片。第 6 章讲如何明智地拆分数据,让每片能住在不同节点上,让你随机器数大致线性地扩展存储和吞吐。分区几乎总与复制结合:每个分区本身跨多个节点复制以容错。

分区与复制,一起

分区和复制正交且通常结合。数据被拆成分区,每个分区按第 5 章的复制方案存在多个节点上。一个节点可能存多于一个分区;leader-follower 设置里,每个节点能是某些分区的 leader、其他分区的 follower。在脑中把这两个想法分开至关重要——分区关乎拆分,复制关乎拷贝。

键值数据的分区

目标是均匀分散数据和查询负载。若拆分不公平,某些分区拿到比其他更多数据或查询——这叫倾斜(skew),负载不成比例高的分区是热点(hot spot)。热点击败分区的目的:一个过载节点拖累整个系统,而其他空闲。避免倾斜最简单的方式是随机把记录分给节点,但那样你没法找到特定记录而不查每个节点。所以我们需要一个既均匀又利于查找的方案。两种主要方法。

按键范围分区

给每个分区分配一个连续的键范围(从某最小到某最大),像纸质百科全书的各卷(A–B、C–D、…)。若你知道边界,你就知道哪个分区持有一个键。边界无需均匀间隔——它们被选来平衡数据。大优势是键在每个分区内保持有序,所以范围扫描高效。大风险是倾斜访问模式造成的热点:若键是时间戳,那么当前那天的每个写都去同一分区,使它过载而历史分区空闲。HBase 和 Bigtable 使用。常见缓解是给键加个前缀(如传感器名)使写分散。

按键的哈希分区

对每个键应用哈希函数并把哈希范围分给分区。一个好的哈希函数把倾斜输入变成均匀分布,所以数据和负载均匀分散。代价:你失去做高效范围查询的能力,因为相邻键现在散布在所有分区——范围扫描必须查每个分区。Cassandra 和 MongoDB(带基于哈希的分片)使用。Cassandra 用复合主键提供折中:第一列被哈希以选分区,其余列用于在那个分区内排序数据——所以你跨分区得到均匀分布、在一个分区内得到高效范围扫描。

哈希也救不了的热点

哈希减少但不消除热点。单个被重度访问的键——一个收到数百万互动的名人用户 ID——仍哈希到单个分区,而没有哈希函数有帮助因为它是一个键。今天大多数系统不能自动补偿;它留给应用。一个典型技巧是给热点键加一个随机两位后缀,把它的写拆到比如不同分区上的 100 个键——代价是读时必须读并合并全部 100 个。

分区与二级索引

目前为止一切都假设一个键值模型,你按主键查记录。真实系统也有二级索引(找所有 color = red 的记录)。二级索引不整齐映射到分区,有两种方式处理它们。

按文档(本地索引)

每个分区维护自己的二级索引,只覆盖那个分区里的文档——本地索引。写简单:你只触及持有该文档的那一个分区。但读昂贵:因为匹配文档可能在任何分区,二级索引上的查询必须发给所有分区并合并结果。这种 scatter/gather 方法使读延迟受制于最慢分区,且易于尾延迟放大。大多数数据库(MongoDB、Cassandra、Elasticsearch、Riak)用文档分区的索引。

按 Term(全局索引)

构造一个覆盖所有分区的全局索引,但分区索引本身——按被查找的 term。例如,所有 color = red 的记录列在一个索引分区里,无论文档住哪。读现在高效:查询只去持有那个 term 的分区。但写更慢更复杂:单个文档写可能影响多个 term、从而多个索引分区,常需要分布式事务。实践中全局二级索引通常被异步更新,所以索引可能短暂落后数据。

再平衡分区

随时间事情会变:查询吞吐增长(加 CPU)、数据集增长(加磁盘),或一台机器失败(其他必须接管)。所有这些都需要把数据和负载从一个节点移到另一个——再平衡(rebalancing)。一个好的再平衡方案有三个属性:负载最终公平分享、数据库在移动期间继续服务读写,且只移动必要的数据(以限制网络和磁盘 I/O)。

hash mod N 陷阱

诱人的朴素方案——把键分给 hash(key) mod N 个节点——恰恰是错误选择,因为改 N 重洗几乎每个键。

key 123456,  hash = 123456

  N = 10 :  123456 mod 10 = 6    → 节点 6
  N = 11 :  123456 mod 11 = 3    → 节点 3   (移动了!)
  N = 12 :  123456 mod 12 = 0    → 节点 0   (又移动了!)

  加一个节点重映射几乎每个键 → 巨大数据移动

更好的策略

• 固定分区数。提前创建远比节点多的分区(比如 10 个节点 1000 个分区)并分几个给每个节点。加节点时,它从现有节点偷取整个分区直到平衡恢复;只移动整个分区,不是单个键。Riak、Elasticsearch、Couchbase 使用。问题:你必须在开始时明智地选分区数,因为它固定。
• 动态分区。分区在增长超过大小阈值时拆分、收缩时合并,像 B-tree——所以分区数适应数据量。HBase 和 RethinkDB 使用。避免提前猜数量。
• 与节点成比例。有固定的每节点分区数;加节点拆分一些现有分区以接管。Cassandra 使用。

请求路由

一旦数据散布在节点上、分区四处移动,客户端需要知道对给定键联系哪个节点——一般服务发现问题的一个实例。有三大方法:

• 联系任何节点(如通过轮询负载均衡器);若那个节点不拥有该键,它把请求转发到正确节点并转达回复。
• 把所有请求发给一个路由层,它知道分区分配并充当分区感知的负载均衡器。
• 让客户端分区感知,使它们直接连到拥有该键的节点。

难的是,做路由决策的那方必须有最新的分区分配知识,而它在再平衡期间变化。许多系统把这个委托给一个单独的协调服务如 ZooKeeper,它权威地跟踪集群的分区到节点映射并通知路由器变化。(Cassandra 和 Riak 转而用 gossip 协议,让节点彼此共享状态,避免外部依赖。)对分析负载,大规模并行处理(MPP)查询引擎把这个更进一步,把单个复杂查询拆成跨许多分区并行运行的阶段。