进入到第六章了，我们要开始聊聊分布式系统之中的核心问题：数据分区。分布式系统通常是通过大规模的数据节点来处理单机没有办法处理的海量数据集，因此，可以将一个大型数据集可以分布在多个磁盘上，查询负载可以分布在多个处理器上。在这一章中，我们首先讨论划分大型数据集的不同方法，并观察数据索引如何与分区交互，然后将探索数据分区重新平衡的策略。最后，来看看路由技术怎么将查询索引到正确的分区。内容看起来还不少，我们开始吧。
1. 分区与副本
分区与副本是很容易混淆的概念，我们这里离清一下两者。
数据分区的每个副本可以存储在多个节点上。这意味着，即使每个记录恰好属于一个分区，它仍然可以存储在几个不同的节点上进行容错。
由上图可以看出，分区和副本是需要解决不同问题的，并不能混为一谈，两者同样作为分布式系统之中的核心技术，共同为分布式系统提供好的解决方案。
2. 分区策略
数据分区的目的是：将数据和查询负载均匀地分布在节点上。（其实副本也有同样的效果，取决于副本同步机制）而如果数据分区不公平，则会出现某些分区的数据或查询比其他分区要多，我们称之为偏斜。数据偏斜就使得分区效果变差，导致负载不均衡形成分区热点。 所以分区策略通常以分区均匀为考量，接下来我们介绍几种常见的分区策略：
范围分区
范围分区是分配一个连续的范围键，如同几册百科全书一般。如果知道范围之间的边界，就可以很容易地确定哪个分区包含给定的键。如果您还知道哪个分区被分配到哪个节点，那么您可以直接将请求发送到适当的节点。
但是很多时候键的范围不一定是均匀分布的，为了均匀地分布数据，分区边界需要和数据的特点相适应。对于每一个分区，我们可以把按键顺序排列，如SSTable，显然这样可以大幅提升范围扫描的效率。
而范围分区的缺点是某些访问模式会导致热点。如果某个范围的键频繁被访问，将导致某个分区的读写量遥遥领先，而其他分区被闲置。（这种情况考虑细分分区粒度或者级联索引，用一个较均匀的特征先做一次分区）
哈希分区
由于范围分区容易产生热点问题，许多分布式数据存储使用一个哈希函数来确定一个键值的分区。一个好的哈希函数可以将倾斜的数据均匀分布，即使数据范围很接近，但是它们的哈希值是均匀分布的值。如下图所示，时间接近的键值被哈希函数均匀的分区在多个分区，每个键的哈希值落在一个分区的范围将被存储在该分区：
使用哈希分区，我们失去了键范围分区的一个很好的特性，曾经相邻的键现在分散在所有分区上，因此它们的排序顺序丢失。我们可以通过级联索引的方式解决这个问题。级联索引方法支持一对多关系的优雅的数据模型，通过两分区方式来综合不同分区方式的优点，通过键哈希来确定分区的第一部分，但其他列作为SSTables的数据排序串联。因此，查询不能在复合键的第一列内搜索范围内的值，但是如果它为第一列指定一个固定值，它就可以在键的其他列上执行有效的范围扫描。例如，在社交媒体站点上，一个用户可以发布许多更新。如果更新主键（user_id，update_timestamp），那么你可以有效地检索在一定时间间隔内特定用户的所有更新。不同的用户可以存储在不同的分区上，但是在每个用户中，更新是在单个分区上以时间戳顺序存储的。
Tip：缓解热点
通过哈希函数分区的确有助于减少热点。然而，它不能完全避免它们：在极端情况下，所有读写操作都是相同的键，最终仍然会将所有请求到同一分区。例如，在社交媒体网站上，一个拥有数百万追随者的名人用户在做某事时可能会引发一场读写风暴。此事件可能导致短时间内大量写入同一个键（其中的Key可能是名人的用户ID，或者是人们评论的行为ID）。这时哈希函数也无能为力，因为两个相同ID的哈希值仍然相同。
大多数数据系统不能自动补偿这种高度倾斜的工作负载，因此应用程序有责任减少偏斜。例如，如果已知一个键非常热，一个简单的方法就是在键的开头或结尾加上一个随机数。只有一个两位数的十进制随机数将把写入分成100个不同的键，允许这些键被分配到不同的分区。但是将不同的键分开写入后，现在任何读取都必须做额外的工作，因为它们必须从所有100个键读取数据并将其组合起来。而且这种方式还需要额外的记录：因为只为少量的热键添加随机数是有意义的；对于绝大多数具有低写入吞吐量的键，这将是不必要的开销。因此，还需要一些方法来跟踪哪些键正在被分割。
2. 分区与二级索引
上文讨论的分区方案依赖于一个关键值数据模型。通过主键访问记录，可以由该键确定分区，并使用它将读取和写入请求路由到负责该键的分区。
而一旦涉及到二级索引，情况会变得更加复杂。二级索引通常不确定记录的唯一性而应该是寻找一个特定的值出现的方式如：找到所有颜色是红色的车 这样的查询。二级索引的问题是它不能映射到分区。有两种主要方法将数据库分为二级索引：基于分区的索引和基于全局的索引。
基于分区的索引
假如有一个卖二手车的网站，每个列表都有一个唯一的ID，称之为文档。通过文档id（例如，分区0中的IDS 0到499、分区1中的IDS 500到999）对数据库进行分区。
您希望让用户搜索汽车，允许它们按颜色和按颜色进行过滤，因此需要对颜色进行二级索引索引，每当一辆红色的车是添加到数据库中，数据库分区自动添加到索引的文档的ID到红色索引处。如下图所示：
在这种索引方法中，每个分区都是完全独立的，每个分区都保留自己的索引，只覆盖分区中的文档id。它不关心存储在其他分区中的数据。每当您需要向数据库写入添加、删除或更新文档时，只需要处理包含您正在编写的文档ID的分区。
但是，从索引读取时需要注意，如果您想搜索红色的汽车，您需要将查询发送到所有分区，并将所有返回的结果组合起来。这样导致了二级索引上的读取查询非常耗时。即使并行的写入和查询分区，分散/聚集操作会导致延迟放大。
基于全局的索引
上节提到分区索引的缺点，所以我们可以建立一个全局的索引，涵盖所有的分区数据。但是，不能只存储索引在一个节点，因为它可能会成为一个瓶颈和故障点。所以全局索引也必须被分区，但它可以划分不同的主键索引。如下图所示：
全局索引使读操作更加高效：而不用分散/聚集所有分区的数据。但全球索引的缺点是，写入速度较慢，更复杂，因为写一个文件现在可以影响指数的多个分区。（ 文件中的每一项可能会在不同的分区，在不同的节点上，在实践之中，二级全局索引通常通过异步的方式进行更新）。
3 分区平衡
随着时间的推移，数据库中的东西发生了变化：
- (1) 查询吞吐量增加，因此您需要添加更多CPU来处理负载。
- (2) 数据集大小增加，所以您需要添加更多的磁盘和RAM来存储它。
- (3) 机器故障，其他机器需要接管故障机器的责任。
所有这些变化都要求将数据和请求从一个节点移动到另一个节点。而负载从集群中的一个节点转移到另一个节点的过程称为分区平衡。
无论采用哪种分区方案，通常都希望分区平衡以满足下面的要求：
- (1) 重新平衡后，集群中的节点之间应该公平地共享负载（数据存储、读写请求）。
- (2) 当分区平衡工作时，数据库应该继续接受读写操作。
- (3) 在节点之间移动尽量减少数据的移动，以便使平衡快速完整，并减少网络和磁盘I/O负载。
海量分区
节点创建远超节点数目的分区数，并为每个节点分配几个分区。例如，在10个节点的群集上运行的数据库可以从一开始分裂成1000个分区，以便分配给每个节点大约100个分区。当将一个节点添加到集群中，新节点可以从每个现有节点窃取一些分区，直到再次公平分配分区为止。如下图所示：
分区的数量不会改变，分区的键分配也不会改变。唯一改变的是分区与节点之间的映射。这种分区平衡的变化不是即时的，在网络上传输大量数据需要一定的时间，所以旧的分区节点在分区平衡时需要承担这个过程之中的读写操作。通过海量分区同样也可以通过给性能更强悍的节点分配更多的分区，可以强制这些节点承担更大的负载份额。
一开始配置的分区数量就是所能拥有的最大节点数，因此您需要选择足够高的分区数目以适应未来的增长。然而，每个分区也有管理开销，所以选择过高的值会适得其反。
动态分区
对于使用键范围分区的数据库，固定范围值的固定分区数量将非常不方便：如果您的边界错误，您可能会将所有数据放在一个分区中，而所有其他分区都是空的。手动重新分区分区将非常繁琐。所以可以采取动态分区的机制：
当一个分区的增长超过配置的大小，它被分为两个分区，大约一半的数据分配在两个新的分区。相反，如果大量数据被删除，一个分区缩小到某个阈值以下，它可以与相邻分区合并。动态分区的优点是分区的数量与总数据量相适应。如果只有少量的数据，少量的分区就足够了，因此开销很小；如果有大量的数据，每个单独的分区的大小限制为一个可配置的最大值。
4. 请求路由
在多台机器上运行的多个节点上对数据集进行分区，所以会面临一个核心问题：当客户端想要提出请求时，它如何知道要连接哪个节点？当分区被重新平衡，分区节点变化的时候客户端如何感知变化。
在高层次上，对这个问题有几种不同的解决方案：
- 1.允许客户端与任何节点联系。如果该节点恰好拥有请求所应用的分区，则它可以直接处理请求；否则，它将请求转发到适当的节点，接收应答，并将应答传递给客户端。
-
- 将客户端的所有请求首先发送到路由层，这将决定应处理每个请求并相应转发它的节点。
-
- 要求客户端知道分区和分配给节点的分区。在这种情况下，客户机可以直接连接到适当的节点，而不需要任何中介。
在三种情况之中关键的问题是：组成路由决策的组件（可能是其中一个节点，或者路由层，或客户端）如何了解分区分配给节点的变化？
许多分布式数据系统依赖于一个单独的协调服务如ZooKeeper跟踪这个集群的元数据，每个节点在ZooKeeper之中注册自己。ZooKeeper维护分区节点映射的权威，而路由层或客户端，可以订阅这个ZooKeeper。当一个分区发生变化时，或添加一个节点或删除，ZooKeeper通知路由层，这样可以保持它的路由信息更新。如下图所示：
Cassandra和Riak采取了不同的方法：通过使用Gossip协议节点之间传播集群状态的任何变化。请求可以发送到任何节点，该节点将它们转发到所请求分区的适当节点。该模型提出了更复杂的数据库节点，但避免了外部协调服务的依赖。
当使用路由层或向随机节点发送请求时，客户端仍然需要找到连接到的IP地址。这些并不像分区对节点的分配那样快速变化，因此经常使用DNS来达到此目的。
小结：
我们在本篇之中总结了数据分区技术运用到的多种策略与技术，希望大家能够更好的认识数据分区技术在分布式存储之中的重要意义。
