分区

对于非常大的数据集，或非常高的吞吐量，仅仅进行复制是不够的：我们需要将数据进行分区（partitions），也称为分片（sharding）。通常情况下，每条数据（每条记录，每行或每个文档）属于且仅属于一个分区。每个分区都是自己的小型数据库，尽管数据库可能支持同时进行多个分区的操作。

分区和复制

1. 分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。
2. 即使每条记录属于同一个分区，但是这个分区仍有多个不同的节点，提高容错。

3. 一个节点有多个分区，如果使用主从复制模型，每个分区领导者被分配给一个节点，追随者被分配个其他节点。

   
   组合使用复制和分区：每个节点充当某些分区的领导者，其他分区充当追随者。

根据键的范围分区

假设你有大量数据并且想要分区,如何决定在哪些节点上存储哪些记录呢？

分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量（暂时忽略复制）。

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据偏斜的存在使分区效率下降很多。在极端的情况下，所有的负载可能压在一个分区上，其余9个节点空闲的，瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为热点（hot spot）。

怎么避免热点？
● 避免热点最简单的方法是将记录随机分配给节点。
● 缺点：读特定的值时，不知道在哪个节点上，必须并行查所有的节点。

根据键的范围分区

印刷版百科全书按照关键字范围进行分区

一种分区的方法是为每个分区指定一块连续的键范围（从最小值到最大值），类似纸质的百科全书。
可能分布不均匀。
分区边界可以由管理员手动选择，也可以由数据库自动选择
使用该策略的有：Bigtable， HBase，RethinkDB和MongoDB

优点：
● 在每个分区中，我们可以按照一定的顺序保存键。
● 范围扫描非常简单
● 可以将键作为联合索引来处理，以便在一次查询中获取多个相关记录
● 比如获取一段时间内的记录。

缺点：
● Key Range分区的缺点是某些特定的访问模式会导致热点。
● 可一个修改主键：比如传感器名称+时间，避免数据打到同一分区。

根据键的散列分区

按哈希键分区

1. 很多分布式数据存储使用散列函数来分区。
2. 一个好的散列函数可以将偏斜的数据均匀分布。
3. 注意保证同一个键在不同的进程中有相同的哈希值: 出于分区的目的，散列函数不需要多么强壮的加密算法：例如，Cassandra和MongoDB使用MD5，Voldemort使用Fowler-Noll-Vo函数。许多编程语言都有内置的简单哈希函数（它们用于哈希表），但是它们可能不适合分区：例如，在Java的Object.hashCode()和Ruby的Object#hash，同一个键可能在不同的进程中有不同的哈希值

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

缺点：
● 失去了 高效执行范围查询的能力。
● 范围查询要么不支持，要么需要查询所有分区。

组合索引：
● 组合索引方法为一对多关系提供了一个优雅的数据模型。
● 社交网络的一条更新主键被选择为 (user_id, update_timestamp)，那么可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。

负载倾斜与消除热点

如前所述，哈希分区可以帮助减少热点。但是，它不能完全避免它们：在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。 这种场景也许并不常见，但并非闻所未闻：例如，在社交媒体网站上，一个拥有数百万追随者的名人用户在做某事时可能会引发一场风暴

如今，大多数数据系统无法自动补偿这种高度偏斜的负载，因此应用程序有责任减少偏斜。例如，如果一个主键被认为是非常火爆的，一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为100种不同的主键,从而存储在不同的分区中。

然而，将主键进行分割之后，任何读取都必须要做额外的工作，因为他们必须从所有100个主键分布中读取数据并将其合并。此技术还需要额外的记录：只需要对少量热点附加随机数;对于写入吞吐量低的绝大多数主键来是不必要的开销。因此，您还需要一些方法来跟踪哪些键需要被分割。

分区与次级索引

基于文档的二级索引进行分区

● 假如一个销售二手车的网站， 每个列表都有一个唯一的ID——称之为文档ID——并且用文档ID对数据库进行分区
● 用户搜索汽车，允许他们通过颜色和厂商过滤，所以需要一个在颜色和厂商上的次级索引（文档数据库中这些是字段（field），关系数据库中这些是列（column） ）

按文档分区二级索引

特点：
● 分区完全独立：每个分区维护自己的二级索引
● 只需处理包含您正在编写的文档ID的分区即可
● 文档分区索引也被称为本地索引（local index）

注意：
● 没有理由把特定颜色或者品牌的汽车放到同一个分区。
● 查询时需要查询所有的分区，合并所有的结果返回。

缺点：
● 查询分区数据库的方法有时被称为分散/聚集（scatter/gather）；
● 可能使二级索引的查询代价高。
● 即使并行查询分区，分散/聚集也容易导致尾部延迟放大。

然而被广泛使用：MongoDB，Riak ，Cassandra ，Elasticsearch ，SolrCloud 和VoltDB都使用文档分区二级索引

基于关键词(Term)的二级索引进行分区

● 可以构建一个覆盖所有分区数据的全局索引，而不是给每个分区创建自己的次级索引（本地索引）。
● 但是，我们不能只把这个索引存储在一个节点上，因为它可能会成为瓶颈，违背了分区的目的。
● 全局索引也必须进行分区，但可以采用与主键不同的分区方式。
● 下图是对二级索引按照首字母是否在 "[a, r]" 之间分区。

按关键词对二级索引进行分区

● 这种分区叫做关键词分区。
● 以通过关键词本身或者它的散列进行索引分区。
○ 根据关键词本身来分区对于范围扫描非常有用：比如数值类的属性。
○ 对关键词的哈希分区提供了负载均衡的能力。
优点：
● 读取更有效率：不需要分散/收集所有分区，客户端只需要向包含关键词的分区发出请求。

缺点：
● 写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区（文档中的每个关键词可能位于不同的分区或者不同的节点上） 。
● 需要跨分区的分布式事务，并不是所有数据库都支持。
● 在实践中，对全局二级索引的更新通常是异步的。

分区再平衡

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

反面教材：hash mod N(不是很明白为什么要重新调整)

前面已经讲了，最好将可能的散列分成不同的范围，给每个范围分配一个分区。取模 mod 运算可以给每个键分配一个节点.问题:当节点数目变化时，使得再平衡过于昂贵。

固定数量的分区

● 简单的解决方案：创建比节点更多的分区，并为每个节点分配多个分区。
● 仍然是取模，但是新增节点之后，总节点数变成了 5 个，只需要把取模 = 4 的部分放到 node 4。

将新节点添加到每个节点具有多个分区的数据库群集。

优点
● 只有分区在节点中移动。
● 分区总数不变
● 键所在的分区也不会改变
● 唯一改变的是分区所在的节点
● 变更不是及时的：在传输过程中，原有分区仍然接受读写操作。
● 甚至可以解决硬件不匹配问题：更强大的节点分配更多的分区。
● Riak ，Elasticsearch ，Couchbase 和Voldemort 中使用了这种再平衡的方法。

特点
● 分区的数量通常在数据库第一次建立时确定，之后不会改变。
● 一开始配置的分区数就是您可以拥有的最大节点数量，所以您需要选择足够多的分区以适应未来的增长。
● 但是，每个分区也有管理开销，所以选择太大的数字会适得其反。

缺点
● 当数据集的总大小难以预估，选择正确的分区数很难。

动态分区

采用关键字区间分区的数据库，如果边界设置有问题，可能导致数据倾斜到一个分区中。
● 按键的范围进行分区的数据库（如HBase和RethinkDB）会动态创建分区。
● 当分区增长到超过配置的大小时（在HBase上，默认值是10GB），会被分成两个分区，每个分区约占一半的数据。
● 与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。此过程与B树顶层发生的过程类似。

特点：
● 每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。
● 大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。
● 在HBase中，分区文件的传输通过HDFS（底层使用的分布式文件系统）来实现。

优点：
● 分区数量适应总数据量。

缺点：
● 空数据库从一个分区开始，导致所有写入都必须单个节点处理，其他节点空闲。

解决方法：
● HBase和MongoDB允许在一个空的数据库上配置一组初始分区（这被称为预分割（pre-splitting））。
● 在键范围分区的情况中，预分割需要提前知道键是如何进行分配的。

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

按节点比例分区

● 动态分区和固定数量的分区，分区数量都与节点数量无关。
● Cassandra和Ketama使用的第三种方法是使分区数与节点数成正比：每个节点有固定数量的分区。
○ 当节点数不变，分区大小与数据集大小成比例增长；
○ 当节点数改变，分区大小将变小。

操作方式：
● 当一个新节点加入集群时，它随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。
● 随机化可能会产生不公平的分割，但是平均在更大数量的分区上时，新节点最终从现有节点获得公平的负载份额。
● 随机选择分区边界要求使用基于散列的分区（可以从散列函数产生的数字范围中挑选边界）。实际上，这种方法最符合一致性哈希的原始定义。

运维：手动还是自动再平衡

请求路由

当客户想要发出请求时，如何知道要连接哪个节点？随着分区重新平衡，分区对节点的分配也发生变化。为了回答这个问题，需要有人知晓这些变化：如果我想读或写键“foo”，需要连接哪个IP地址和端口号？

1. 允许客户联系任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
2. 首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。
3. 要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。

作出路由决策的组件（可能是节点之一，还是路由层或客户端）如何了解分区-节点之间的分配关系变化？

将请求路由到正确节点的三种不同方式