第六章：分区

通常情况下，每条数据属于且仅属于一个分区

分区主要是为了可伸缩性，不同的分区可以放在不共享集群中的不同节点上。因此，大数据可以分布在多个磁盘上，并且负载可以分布在多个处理器上

分区与复制

分区与复制通常结合使用，使得每个分区的副本存储在多个节点上

一个节点可能存储多个分区。每个节点可能是某些分区的主库，同时也是其他分区的从库

键值数据的分区

分区目标是将数据和查询负载均匀分布在各个节点上

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们成之为偏斜（shew） 。数据偏斜的存在使分区效率下降很多。不均衡导致的高负载的分区被称为热点（hot spot）

避免热点最简单的方法是将记录随机分配给节点

平均分配数据
缺点是无法知道特定值在哪个节点上，必须并行地查询所有的节点

根据键的范围分区

为每个键指定一块连续的键范围。如果知道范围之间的边界，则可以轻松确定哪个分区包含值。如果还知道分区所在的节点，就可以直接向相应的节点发出请求

为了均匀分配数据，分区边界需要依据数据调整。分区边界可以由管理员手动选择，也可以由数据库自动选择

在每个分区中，可以按照一定的顺序保存键。好处是进行范围扫描很简单

按照键的分区的缺点是某些特定的访问模式会导致热点。例如主键是时间戳，分区对应时间范围，则最近的写入都可能会转到同一个分区，而其它分区则处于空闲状态

根据键的散列分区

一个好的散列函数可以将偏斜的数据均匀分布

许多编程语言有内置的简单哈希函数，但它们可能不适合分区，同一个键可能在不同的进程中有不同的哈希值

为每个分区分配散列范围，通过哈希散列落在分区范围内的键将被存储在该分区中

这种技术擅长在分区之间公平地分配键。分区边界可以是均匀间隔的，也可以是伪随机的（在这种情况下，该技术有时也被称为一致性哈希）

一致性哈希

一致性哈希由 Karger 等人定义。用于跨互联网级别的缓存系统，例如 CDN 中，是一种能均匀分配负载的方法。它使用随机选择的 分区边界（partition boundaries） 来避免中央控制或分布式共识的需要

缺点是使用散列进行分区失去了键范围分区快速执行范围查询的能力

可以采用组合索引的方式进行折中，例如多个列作为主键，第一个列作为散列依据，其余列进行排序，在第一个列固定的情况下，可以根据后面的键进行范围查询

负载偏斜与热点消除

哈希分区可以帮助减少热点，但是不能完全避免它们：极端情况下所有读写操作都是针对同一个键的

大多数数据库无法自动补偿高度偏斜的负载，因此应用程序有责任减少偏斜，例如在被认为是火热的主键结尾添加一个随机数进行分区

当主键进行分割后，任何读取都必须要做额外的工作，因此对于写入吞吐量低的绝大多数主键来说是不必要的开销

分区与次级索引

前面的方案依赖于键值数据模型，都只通过主键访问，如果涉及次级索引，情况会变得更加复杂

次级索引通常不能唯一标识记录，而是一种搜索记录中特定值的方式

次级索引的问题是它们不能整齐地映射到分区

基于文档的分区

如果每个列表有一个ID，称之为文档ID，用文档ID进行分区

在将数据添加到数据库时，如果字段申明了索引，数据库分区会自动将其添加到索引条目[索引字段]的文档ID列表中

在这种索引方法中，每个分区是完全独立的：每个分区维护自己的次级索引，仅覆盖该分区中的文档，不关心存储在其它分区的数据。写入数据库时只需要处理包含你正在编写的文档ID的分区即可。文档分区索引也被称为本地索引

搜索次级索引，需要将查询发送到所有分区，并合并所有返回的结果

这种查询分区数据库的方法有时被称为分散/聚集（scatter/gather） ，并且可能会使次级索引上的读取查询相当昂贵。即使并行查询分区，也容易导致尾部延迟放大

但是这种方法被广泛使用

基于关键词(term)的次级索引进行分区

可以构建一个覆盖所有分区的全局索引，而不是给每个分区创建自己的次级索引（本地索引）

不能把这个索引存储在一个节点上，因为它可能会称为瓶颈，违背了分区的目的
全局索引也必须分区，但可以采用与主键不同的分区方式

例如：来自所有分区的红色汽车在个红色索引中，并且索引是分区

这种索引被称为关键词分区（term-partitioned） ，因为寻找的关键词决定了索引的分区

我们可以通过关键词本身或它的散列进行索引分区

根据关键词本身来分区对于范围查询扫描非常有用
对关键词的哈希分区提供负载均很的能力

关键词分区的全局索引优于文档问去索引的地方是它可以使读取更有效率，不需要分散/手机所有分区。客户端只需要向包含关键词的分区发出请求

缺点是写入速度较慢，因为单个写可能会影响索引的多个分区

理想情况下，索引总是最新的，写入数据库的每个文档都会立即反映在索引中。但是在关键词分区索引中，这需要跨分区的分布式事务

在实践中，对全局次级索引的更新通常是异步的，所做的更改可能不会立即反映在索引中

分区再平衡

随时间的推移，数据库会有各种变化

查询吞吐量增加，想添加更多CPU
数据集大小增加，想添加更多磁盘和RAM
机器出现故障，其它机器需要接管故障机器的责任

所有这些更改都需要数据和请求从一个节点移动到另一个节点，将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（rebalancing）

需要满足的最低要求

再平衡之后，负载应该在集群中的节点之间公平共享
再平衡发生时，数据库应该继续接受读取和写入
节点之间只移动必须的数据。以便快速再平衡，并减少网络和磁盘I/O负载

再平衡策略

为什么不采用hash mod n

如果节点数量n发生变化，大多数键都需要移动位置，再平衡成本过高

固定数量的分区

创建比节点更多的分区，并为每个节点分配多个分区

如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配，如果从集群中删除一个节点，则会发生相反的情况

只有分区在节点之间的移动。分区数量不会改变，键所指定的分区也不会改变。唯一改变的是分区所在的节点。这种变更并不是即时的-在网络上传输大量的数据需要一些时间，所以在传输过程中分区仍然会接受读写操作

通过为更强大的节点分配更多的分区，可以强制这些节点承载更多的负载，原则上可以解决集群中的硬件不匹配问题

在这种配置中，分区的数量通常在数据库第一次建立时就确定，虽然原则上可以分割和合并分区，但固定数量的分区在操作上更简单

因此，一开始配置的分区就是最大的节点数量，需要足够多的分区以适应未来的增长。但分区太多管理开销也很大

分区大小

分区太大，再平衡和从节点故障恢复变得昂贵
分区太小，会产生太多开销

如果分区数量固定，但数据变动很大，则难以达到最佳性能

动态分区

对于使用键值范围分区的数据库，具有固定边界的固定数量的分区将非常不方便：如果边界错误可能导致一个分区中的所有数据或其它分区中的数据为空，手动重新分配分区边界将非常繁琐

按键的范围进行分区的数据库会创建动态分区

当分区增长到超过配置的大小时会被分成两个分区，每个约一半
如果大量数据被删除并且缩小到某个阈值之下，可以将其与相邻分区合并

每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。大型分区拆分后，可以将其中的一半转移到另一个节点以平衡负载

动态分区的一个优点是分区数量适应总数据量

如果只有少量数据，少量分区就够了，开销很小
如果有大量数据，每个分区的大小被限制在一个可配置的最大值

初始时只有一个分区，所有写入只能由单个节点处理。为了解决这个问题，一些数据库允许在一个空的数据库上配置一组初始分区（预分割 pre-splitting）

动态分区不仅适用于数据的范围分区，而且也适用于散列分区

按节点比例分区

动态分区中，分区的数量与数据集的大小成正比

固定数量的分区中，分区的大小与数据集的大小成正比

按节点比例分区，每个节点具有固定数量的分区。每个分区的大小与数据集大小成比例地增长，而节点数量保持不变。但是当增加节点数时，分区将再次变小。这种方法使得每个分区的大小较为稳定

当一个新节点加入集群时，它随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。随机化可能会产生不公平的分割，但是平均在更大数量的分区上时，新节点最终从现有节点获得公平的负载份额

随机选择分区边界要求使用基于散列的分区（从散列函数产生的数字范围中挑选边界）。实际上，这种方法最符合一致性哈希的原始定义

运维

再平衡是选择自动还是手动？

在全自动和完全手动之间有一个权衡

全自动再平衡很方便，但是是不可预测的。再平衡是一个昂贵的操作，如果没有做好可能会使网络或节点负载过重，降低请求性能

这种自动化与自动故障检测相结合可能十分危险。例如，假设一个节点过载，并且对请求的响应暂时很慢。其他节点得出结论：过载的节点已经死亡，并自动重新平衡集群，使负载离开它。这会对已经超负荷的节点，其他节点和网络造成额外的负载，从而使情况变得更糟，并可能导致级联失败。

再平衡过程中有人参与是一件好事，这比全自动的过程慢，但可以帮助防止运维意外

请求路由

用户想要发出请求时，如何知道连接到哪个节点？随着分区重新分配，分区对节点的分配也产生了变化

这个问题可以概括为服务发现（service discovery）

几个解决方案

允许客户联系任何节点（例如通过循环策略的负载均衡）。如果该节点恰巧拥有请求分区则可以直接处理该请求；否则将请求转发到适当的节点，接收回复并传递给客户端
首先将所有请求发送到路由层，它决定了应该处理请求的节点，并相应地转发
要求客户端知道分区和节点的分配，直接连接到合适的节点

关键问题是，作出路由决策的组件如何了解分区-节点之间的分配关系变化

这是一个具有挑战性的问题，因为重要的是所有参与者都达成共识，否则请求将被发送到错误的节点

许多分布式数据系统都依赖一个独立的协调服务。例如ZooKeeper来跟踪集群元数据。节点在ZooKeeper中注册自己，ZooKeeper维护分区到节点的可靠映射。其它参与者可以在ZooKeeper中订阅此信息，只要有分区或节点的改变，ZooKeeper就会通知路由层使路由信息保持最新状态

HBase、SolrCloud和Kafka使用ZooKeeper来跟踪分区分配。MongoDB具有类似的体系结构，但它依赖于自己的配置服务器（config server） 实现和mongos守护进程作为路由层

Cassandra和Riak在节点之间采用流言协议（gossip protocol） 来传播集群状态的变化。请求可以发送到任意节点，该节点会转发到包含所请求的分区的适当节点。这个模型在数据库节点中增加了更多的复杂性，但避免了对外部协调服务的依赖

当使用路由层或向随机节点发送请求时，客户端仍然需要找到要连接的IP地址。这些地址并不像分区的节点分布变化的那么快，所以使用DNS就足够了

执行并行查询

通常用于分析的大规模并行处理（MPP） 关系型数据库产品在其支持的查询类型方面要复杂得多。MPP查询优化器可以将典型数据仓库的复杂查询分解成许多执行阶段和分区，其中许多可以在数据库集群的不同节点上并行执行

小结

分区的目的是在多台机器上均匀分布数据和查询负载，避免出现热点

两种主要的分区方法

键范围分区
- 优势是范围查询快
- 缺点是如果应用程序经常访问相邻的键则存在热点的风险
- 分区变得很大时通常将分区分成连个子分区来动态重新平衡分区
散列分区
- 优势是均匀分配负载
- 缺点是范围查询效率低下
- 通常提前创建固定数量的分区，为每个节点分配多个分区，并在添加或删除节点时将分区再节点之间移动。也可以使用动态分区

次级索引分区的两种主要方法

基于文档分区（本地索引）
基于关键词分区（全局索引）

按照设计，多数情况下每个分区是独立运行的，这就是分区数据库可以伸缩到多台机器的原因，但是需要写入多个分区的操作结果可能难以预料