这篇文章是ddia第六章的阅读笔记。

0x00 Pre

第五章的复制有一个假设，数据副本可以在一台机器上存储。

如果不行的话，就需要将一个副本放在多个机器上了。

这就是分区（partitions），也叫分片（sharding）。

分区一般和复制结合使用，每个分区在多个节点上都有副本。比如：

既然要将一个数据副本分成多块，那么第一个问题就是，怎么决定一个副本的记录放到那个分区上呢？

0x01 键值数据的分区

将数据分到多个节点上，那么就应该尽量均衡，否则就会出现热点（Hotspot）。

避免热点最简单的就是将数据随机分配给所有的节点。

不过这样的话读取数据的时候就麻烦了。

如果数据是键值类型的话，可以简单改进。

1.1 基于关键字区间分区

如下图：

每个分区的范围可以手动设置，也可以自动设置。

基于关键字区间的分区方式的缺点是某些访问模式会导致热点，比如按天分区。

1.2 基于关键字哈希值分区

可以将key进行hash然后确定分区：

不过使用hash分区，就不能使用区间查询了。

一致性哈希（consistent hashing）：是一种平均分配负载的方法，采用随机选择的分区边界来规避中央控制或分布式共识。这个和副本一致性、ACID一致性没有任何关联。

1.3 负载倾斜与热点

热点不可避免。极端情况下，所有的读写都是针对同一个关键字。

这在社交网络的名人上是很有可能的。

避免这种热点可以在key之后加上一个随机数，就可以把一个key分到多个不同的key上。

不过读取的时候就要有额外的操作了。

可以只对少量的热点key进行这种操作。

0x02 分区与二级索引

前面的是键值类型数据，如果涉及到二级索引的话就麻烦了。

二级索引的主要挑战是不能规整地映射到分区中，因为二级索引不能唯一标识一条记录。

不过可以通过两种方式来对二级索引进行分区。

2.1 基于文档的二级索引

比如下面的一个例子：

相当于每个分区有一个自己的索引，而不是全局索引。

所以想要搜索全部的话，需要对多个分区进行搜索然后合并结果。

2.2 基于词条的二级索引分区

基于词条的分区可以维护一个全局索引，并且将这个全局索引也进行分区：

全局索引的分区可以采用和数据关键字不同的策略。

这种方式读取简单，但是写入就比较复杂了。

主要是因为单个文档更新时，可能涉及到多个二级索引，而这些二级索引可能分布在不同的分区上，写放大。

理想情况下，索引应该时刻保持更新。

但是对于词条分区来说，这需要一个跨多个相关分区的分布式事务支持，影响写操作。

实践中，对全局二级索引的更新往往都是异步的。

0x03 分区再平衡

数据库在不断变化，所以一开始的分区可能到后面需要进行更改。

这要求数据和请求可以从一个节点转移到另一个节点上，这就是再平衡（Rebalancing）。

分区再平衡至少需要满足：

• 平衡之后，负载、数据存储和读写请求等应该在集群范围内均匀分布；
• 再平衡过程中，数据库应该可以继续正常运行；
• 避免不必要的负载迁移，加快再平衡，并尽量减少网络和磁盘影响。

3.1 动态再平衡的策略

3.1.1 取模

对节点数取模方法的问题是，如果节点数N发生了变化，会导致很多关键字需要迁移。

不建议使用这种方法。

3.1.2 固定数量的分区

可以首先创建数量远超节点数的分区数，然后为每个节点分配多个分区。

如果新加一个节点，那么可以从其他的节点上移走几个到这个新的节点上：

选中的分区会在节点之间迁移，但是分区的总数不变，也不改变关键字到分区的映射，改变的是分区与节点的映射。

3.1.3 动态分区

HBase和RethinkDB采用的动态分区，如果分区的数据增长到一个阈值，就自动拆分成两个分区。

动态分区的一个优点是分区数量可以自动适配数据总量。

且不仅适用于关键字分区，也适用于基于哈希的分区。

3.1.4 按节点比例分区

采用动态分区，每个分区的大小维持在设定的最小值和最大值之间，那么分区的数量就和数据总量有关。

而如果分区数量固定的话，每个分区的大小也和数据总量有关。

这两种方式的分区数量都与节点数量无关。

Cassandra和Ketama采用了第三种方式，分区数量和节点数量有关。

也就是说每个节点具有固定数量的分区。

当节点数固定时，分区数固定，分区大小和数据总量有关。

当新加节点时，随机选择固定数量的现有分区进行分裂，然后拿走一半的数据。

3.2 自动与手动再平衡策略

再平衡可以手动，也可以自动执行。

全自动方便，但是也可能出现意想不到的问题。

最好是在再平衡过程中有管理员介入。

0x04 请求路由

现在的问题就是，客户端发送请求时，需要知道应该连接的是哪个节点。

这就是服务发现问题。

有以下几种策略：

• 随机选择然后请求转发；
• 有一个路由层统一管理；
• 客户端感知节点与分区的关系。

不管在哪里作出决策，都需要知道具体的节点与分区之间的关系。

那么怎么管理这些信息呢？

可以使用独立的协调服务（比如ZooKeeper）。

还可以自己实现协议，来同步这些信息。