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