数据在不同节点上的副本,对于非常大的数据集,或非常高的吞吐量，仅仅进行复制是不够的：我们需要将数据进行分区（partitions），也称为分片（sharding）。
分区主要是为了可伸缩性，不同分区可以放在不共享集群的不同节点上。
分区与复制
分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。 这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。
一个节点存储多个分区。如果主从复制模型，每个分区领导者在一个节点，从库在其他节点。每个节点可能是某些分区的领导者，同时是其他分区的追随者。
键值数据的分区
分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量（暂时忽略复制）。
如果分区是不公平的情况下，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。不均衡导致的高负载的分区被称为热点（hot spot）。
根据键的范围分区
一种分区的方法是为每个分区指定一块连续的键范围。如果知道范围之间的边界，则可以轻松确定哪个分区包含某个值。
但这样键的范围不一定分布均匀，因为数据分布可能不均匀。这就需要根据数据调整分区边界。
根据键的散列分区
由于偏斜和热点的风险，许多分布式数据存储使用散列函数来确定给定键的分区。
如果有一个合适的散列函数，那就可以为每个分区分配一个散列范围。
这种技术擅长在分区之间分配键。分区边界可以是均匀间隔的，也可以是伪随机选择的（在这种情况下，该技术有时也被称为一致性哈希（consistent hashing））。
但是，通过使用key散列进行分区，就会失去键范围分区的一个好的属性：高效执行范围查询的能力。
负载倾斜与消除热点
哈希分区可以帮助减少热点。但是，它不能完全避免它们：在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。
这个缺点目前没有好的解决方案，一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为100种不同的主键,从而存储在不同的分区中，然而，将主键进行分割之后，任何读取都必须要做额外的工作，这就需要自己权衡。
分片与二级索引
通过主键分区很简单，只需要通过关键字来确定分区即可。但二级索引通常不能唯一的标记一条记录，而是加速特定值的查询。他们不能规整的映射进分区中。
有两种用二级索引对数据库进行分区的方法：基于文档的分区（document-based）和基于词条（term-based）的分区。
基于文档分区的二级索引
比如用户搜索汽车，允许他们通过颜色和厂商过滤，所以需要一个在颜色和厂商上的二级索引。
在这种索引方法中，每个分区是完全独立的：每个分区维护自己的二级索引，仅覆盖该分区中的文档。它不关心存储在其他分区的数据。出于这个原因，文档分区索引也被称为本地索引（local index）（而不是将在下一节中描述的全局索引（global index））。
这种查询分区数据库的方法有时被称为分散/聚集（scatter/gather），显然这种二级索引的查询代价高昂。但实践中应用也广泛，比如MongoDB，Riak， Elasticsearch 等都是文档方式的二级索引。
基于词条的二级索引
对所有数据构建全局索引， 而不是每个分区维护本地索引。为了避免成为瓶颈，不能将全局索引存储在一个节点上，否则就破坏分区均衡的目标。
如图：所有分区的颜色为红的汽车收录在索引color:red中，索引本身也是分区的。比如从a到r在1区，s到z在2区。可以根据词条本身或它的散列进行分区，对本身分区的好处就是可以范围查询，散列分区可以更好的负载均衡。
全局的词条分区相比文档分区的优点是读取高效，不需要分散/收集所有分区。但写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区。
另一方面，写入的每个数据都要立即反映在索引上，对词条分区来说，这时个跨多个分区的分布式事务，速度受到很大影响，所以所有数据库都不支持同步更新二级索引。在实践中，对全局二级索引的更新通常是异步的。
分区再平衡
随着时间的推移，数据库会有各种变化。
- 查询压力增加，添加更多的CPU来处理负载。
- 数据规模增加，添加更多的磁盘和RAM。
- 节点出现故障，需要其他机器来接管失效的节点。
这些变化都需要将数据和请求从一个节点移动到另一个节点。这个迁移负载的过程称为再平衡。
无论使用哪种分区方案，再平衡通常都要满足一些最低要求：
- 再平衡之后，数据存储，读取和写入请求应该在集群范围更均匀的分布。
- 再平衡发生时，数据库应该继续提供读写服务。
- 避免不必要的负载迁移，加快动态再平衡，并减少网络和磁盘I/O负载。
平衡策略
下面是几种分配策略：
反面教材：取模
取模有很大问题，如果节点数N发生变化，会导致很多关键字从现有节点迁移。不符合避免不必要的负载迁移的最低要求。
固定数量的分区
这个方案较为简单，一开始就创建远超节点数量的分区，比如10个节点，我创建1000个分区，那么，有新节点加入，就可以从每个现有节点匀走几个分区，直到达到均衡。删除则采取相反的均衡措施。
分区在节点迁移，但数量不变，也不改变关键字到分区的映射关系。考虑到节点的网络运输数据的实践，可以逐步完成，在此期间，旧的分区仍旧可以接受读写请求。
更可以将集群中不同的硬件配置考虑进来，强大的节点负责更多分区。
动态分区
多使用关键字区间分区的数据库，如果边界设置有问题，可能导致大多数数据都挤在少部分分区。手动重新配置分区边界将非常繁琐。
所以，一些数据库如HBase和RethinkDB采用动态分区。当分区增长到超过配置的大小时（在HBase上，默认值是10GB），会被分成两个分区，每个分区约占一半的数据。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。类似b树的分裂操作。
仍旧是每个分区在一个节点，一个节点多个分区。大分区裂开后，可以将一半转移到其他节点来平衡负载。在HBase中，分区文件的传输通过HDFS（底层分布式文件系统）来实现
动态分区另一个优点是分区数量可以适配数据总量。少量数据就少量分区，大量数据，则每个分区大小被限制在一个可配置的最大值。
动态分区在初始时一般会创建一系列初始分区（称为预分裂，可以通过一些关键字的分布情况来设置）。动态分区不仅适合关键字区间分区，也适合基于哈希的分区策略。从版本2.4开始，MongoDB同时支持范围和哈希分区，并且都是进行动态分割分区。
按节点比例分区
也就是分区随节点数量变化，分区大小和数据集大小是正比关系。
新节点加入集群时，随机选择固定数量的现有分区进行拆分，这个随机选择需要好的算法来维护。放在不公平的分裂。
随机选择分区边界的前提是采用基于哈希的分区。
自动与手动再平衡操作
全自动与全手动都有缺点，一般让管理员介入到再平衡可能是更好的选择。
请求路由
现在将数据集分布到多个节点上，但仍有一个问题，用户如何知道请求需要发送到哪个节点？如果分区再平衡，分区地址可能也会变化。
这种问题一般使用服务发现来解决：
- 允许客户链接任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求；否则，它将请求转发到适当的节点，接收回复并传递给客户端。
- 将所有客户端的请求发送到路由层，由它来负责请求转发。此路由层本身不处理任何请求；它仅充当一个分区感知的负载均衡器。
- 要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。
方法有多种，但最核心的是：作为路由决策的组件，如何知道分区和节点的对应关系以及变化情况？
许多分布式数据系统都依赖一个独立的协调服务，比如zookeeper。节点在zookeeper中注册自己，zookeeper维护分区到节点的映射，其他参与者（如客户端）向zookeeper订阅信息。一旦信息改变，ZooKeeper就会通知路由层，使路由信息保持最新状态。
