theme: cyanosis
分区数据库在20世纪80年代提出。分区是将大型数据库分解成小型数据库的方式。分区主要为了可扩展性，不同分区可以放在不共享集群中的不同节点上。因此，大数据集可以分布在多个磁盘上，并且查询可以负载在多个处理器上。
对于在单个分区上运行的查询，每个节点可以独立执行对自己的查询，因此可以通过添加更多节点来扩大查询吞吐量。大型，复杂的查询可能会跨越多个节点并行处理，但是这也带来了新的困难。
1 分区与复制
分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。
一个节点可能存储多个分区，若使用主从复制模型，则每个节点都有一个领导者和几个追随者。
大多数情况下选择和复制方案是独立的，本章中忽略复制。
2 键值数据的分区
假设有大量数据并且想要分区，如何决定在哪些节点上存储哪些记录呢？
分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量（暂时忽略复制）。
偏斜（skew） ：分区不公平，一些分区有更多数据或查询。数据偏斜的存在使得分区效率下降。
热点（hot spot） ：偏斜导致的不均衡的高负载，极端情况下所有的负载可能压在一个分区上。
避免热点：将记录随机分配给节点，在所有节点上上平均分配数据。缺点：当你读取一个特定的值时，不知道在哪个节点上，所以需要并行查询所有节点。
为了解决问题，我们可以使用简单的键值模型记录主键以访问记录。
2.1 根据键的范围分区
为每个分区指定一块连续的键范围，当我们知道范围之间的边界时，就能确定哪个分区包含哪个值（类似于B+Tree）。如果您还知道分区所在的节点，那么可以直接向相应的节点发出请求。分区边界可以由管理员手动选择或数据库自动选择。
键的范围不一定均匀分布，因为数据也很可能不均匀分布。每个分区中，可以按照一定的顺序保存键，这会使得范围扫描变简单。也可以将键作为联合索引来处理，以便一次查询多个相关记录。
Key Range分区的缺点：某些特定的访问模式会导致热点。例如主键是时间戳时，所有写入都会放到今天的分区。
2.2 根据键的散列分区
许多分布式数据存储使用散列函数来确定给定键的分区，以应对偏斜和热点 —— 一个好的散列函数可以将偏斜的数据均匀分布。散列函数不需要很强的加密算法，但是许多编程语言的内置hash算法不适合分区，例如Java的Object.hashCode()会导致同一个键在不同进程中有不同的哈希值。
这种技术擅长在分区之间分配键。分区边界可以是均匀间隔的，当分区边界是伪随机的时，此技术称为一致性哈希。
缺点：无法高效执行范围查询。由于顺序丢失，任何范围查询都需要发送到所有分区中（例如MongoDB）。Cassandra采取了折衷的做法，它的键中只有第一列会作为散列的依据。
2.3 负载倾斜与消除热点
哈希分区可以减少但不能完全避免热点。例如一个大v下面评论区突然开战，会导致大量写入同一个键（大v的ID等）。哈希策略不起作用，因为两个相同ID的哈希值是相同的。
如今，大多数数据系统无法自动补偿这种偏斜，因此可以用应用程序减少偏斜。例如，可以额外记录这些少量的热点，在这个主键后增加随机数以取得不同的哈希值，以分散出不同的主键。
3 分片与次级索引
若只通过主键访问时，只需要确定分区并路由。但若设计次级索引，情况会变得复杂。
次级索引是关系型数据库的基础，文档数据库中也很普遍，许多键值存储为了减少实现的复杂度而放弃了次级索引，但是由于他们对于数据模型很有用，一部分键值存储的数据库开始加入这个功能。
次级索引的问题是它们不能整齐地映射到分区。有两种用二级索引对数据库进行分区的方法：基于文档的分区（document-based）和基于关键词（term-based）的分区
3.1 文档分区二级索引
每个分区完全独立，每个分区维护自己的二级索引，仅覆盖该分区中的文档。所以文档分区索引也被称为本地索引。
辅助索引通常并不能唯一地标识记录，而是一种搜索记录中出现特定值的方式：想让用户搜索汽车，允许他们通过颜色和厂商过滤，就需要一个在颜色和厂商上的次级索引（文档数据库中这些是字段（field） ，关系数据库中这些是列（column） ）。
而在声明索引后，数据库就应该可以自动执行索引：无论何时将红色汽车添加到数据库，数据库分区都会自动将其添加到索引条目color：red的文档ID列表中。同时需要注意索引与底层数据不一致的问题。
我们一般不能将两个ID放在同个分区中，这导致当我们搜索时，需要将查询发送到所有分区，这种查询分区数据库的方法称为分散/聚集（scatter/gather），即并行查询分区，这会使二级索引查询变得昂贵，尾部延迟放大。
3.2 根据关键词（Term）的二级索引
构建一个覆盖所有分区数据的全局索引，然后将全局索引进行分区（可以采用与主键不同的分区方式），这就是关键词分区索引。
关键词来自全文搜索索引（一种特殊的次级索引），指文档中出现的所有单词。可以对关键词进行哈希分区以增加均衡负载能力。
优点：读取效率比文档分区索引高，不需要分散/收集所有分区，只需要向包含关键词的分区发出请求
缺点：写入慢且复杂，因为写入单个文档可能影响索引的多个分区。因此在实践中，对全局二级索引的更新通常是异步的，在写入后不久读取索引。
理想情况下，索引总是最新的。但是，这需要跨分区的分布式事务，并不是所有数据库都支持。在实践中，对全局二级索引的更新通常是异步的。
4 分区再平衡
随着时间的推移，数据库会有各种变化。
- 查询吞吐量增加，需要添加更多的CPU来处理负载。
- 数据集大小增加，需要添加更多的磁盘和RAM来存储。
- 机器出现故障，其他机器需要接管故障机器的责任。
这些更改需要数据和请求从一个节点移动到另一个节点。负载在集群的节点中移动的过程称为再平衡（reblancing） 。
再平衡需要满足以下要求：
- 再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
- 再平衡发生时，数据库应该继续接受读取和写入。
- 节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘I/O负载。
4.1 平衡策略
固定数量的分区
创建比节点更多的分区，并为每个节点分配多个分区。当一个节点加入集群时，新节点从每个节点中拿一些分区直到分区平衡。（删除则相反）
分区的数量通常在数据库第一次建立时确定，虽然原则上可以分割和合并分区，但固定数量的分区操作更简单，因此，一开始配置的分区数就是你的最大节点数量。所以您需要选择合适的分区数量以适应未来的增长。
选择正确的分区数是困难的，如果分区数量固定，但数据量变动很大，则难以达到最佳性能。
动态分区
对于使用键范围分区的数据库，固定边界固定数量的分区，如果出现边界错误会很麻烦——分区数据可能会清空，但是手动重新配置分区边界会非常繁琐。所以，按键的范围进行分区的数据库会动态创建分区。
当分区增长到超过配置大小时，会被分为两个分区，此时可以将一个分区转移给另一个节点。相反，当分区数量缩小到某个阈值则会与相邻分区合并。因此，分区数量能适应总数据量。每个分区分配给一个节点，每个节点可以处理多个分区，大型分区拆分后，可以将其中一半转移给另一个节点以平衡负载。
预分割：数据集一开始很小的时候只有一个节点在处理操作，为了解决此问题，预分割允许在一个空数据库上配置一组初始分区。在键范围分区的情况下，预分割需要提前指定键是如何进行分配的。
动态分区也适用于散列分区，例如MongoDB同时支持动态分割的范围和哈希分区。
按节点比例分区
使分区数和节点数成正比，每个节点有固定数量的分区，那么每个分区的大小都于数据集大小成比例的增长，而节点数量保持不变。而当增加节点数时，分区变小。
当一个新节点加入集群时，随机选择固定数量的现有分区进行拆分，然后拿走每个选中的分区的一半。随机化会产生不公平的分割，但是平均在更大数量的分区上时，新节点会获得公平的负载份额。
4.2 运维：手动还是自动？
再平衡要手动还是自动进行呢？
全自动重新平衡很方便但不可预测。再平衡是个昂贵的操作，会使网络节点负载增加，降低其他请求的性能。
自动化再平衡和自动故障检测的结合十分危险，可能会造成级联失效（节点连锁的死亡）：当发现节点过载响应慢时自动故障检测可能会认为节点已经死亡，并自动重新平衡集群，而再平衡使得其他节点负载增加并被判定为死亡。
因此，再平衡需要有人参与，虽然比自动化慢，但是可以防止运维出现意外。
5 请求路由
当客户发出请求时，如何知道连接哪个节点？这可以概括为服务发现问题。
方案：
- 允许客户连接任何节点，如果该节点恰巧有请求的分区，则可以直接处理该请求。否则则将请求转发到适当的节点，接收回复并传递给客户端。
- 将所有请求发送到路由层进行转发。路由层只负责分区的均衡负载。
- 直接在客户端中配置分区和节点的路由。
关键问题是，做出路由决策的组件如何了解分区-节点之间的分配关系的变化？
分布式数据系统可以依赖于一个独立的协调服务，比如ZooKeeper。每个节点向ZooKeepper注册自己，路由层或客户端在ZooKeeper中订阅此信息，当分区或节点发生改变时，ZooKepper通知路由层使路由信息保持最新状态。
Cassandra和Riak在节点中使用流言协议来传播集群状态的变化。请求可以发送到任意节点，该节点会转发到目标分区的节点。这避免了对外部协调服务的依赖。
6 小结
本章讨论了大数据集怎么划分成小的子集。分区的目标是在多台机器上均匀分布数据和查询负载，避免出现热点。
分区主要有两种方法：键范围分区、散列分区。
次级索引页需要分区：按文档分区（本地索引）、按关键词分区（全局索引）。