设计数据密集型应用 —— 分区

序言

在大数据的场景中，单机节点常常无法满足海量数据的存储和访问需求，我们需要把数据库切成多块，分别存储到不同的节点。每一块数据被称作一个分区(partition)，有时也被称作分片(sharding)。

使用分区是为了实现扩展性(scalability)。不同的分区存储在不同的节点上，一次查询请求就可以分发到多个节点，在每个节点上并发执行，收集各个节点的返回数据并获得最终结果。

分区和副本常常是结合在一起使用的。一份数据被存储在某个分区，同一个分区又复制多个副本存储。下图是一个单主集群的存储示例:

分区算法

我们需要找到一种算法，以确定某条记录属于哪一个分区。算法的核心目标是:所有的数据在各个分区均匀分布(fair share)，只有这样才能达到扩展性的效果。

如果分布不均匀的话，就会出现数据倾斜(skewed)————大部分的数据集中在少数的分区，那么这些分区就会成为热点(hot spot)，热点接收大量的读写请求，成为系统的性能瓶颈。

基于键范围的分区

实现分区的一种方式，是根据键的范围来确定分区，每一个分区负责存储一段范围的键值，就像一套百科全书，每一卷负责一段范围的关键词:

我们不需要平均划分键范围，而是可以根据数据分布的特征来手动调整范围。每一个分区内部，数据被排序后存储，这样的存储方式使得范围扫描操作很高效。

当主键设计得不好的时候，基于键范围的分区就可能会出现数据热点。例如，如果把时间戳作为主键，那么最近更新的数据都会被存储到同一个分区中，针对最最新数据的查询都会请求这一个分区，造成数据热点。

在现实系统中，Hbase采用了基于键范围的分区方式。

基于哈希函数的分区

另一种常见的算法是使用哈希函数(hash function)，基于数据的键(key)计算哈希值，来确定所属的分区。数据分布是否均匀，是评价哈希函数性能的标准。

确定哈希函数之后，可以配置各个分区存储一个哈希范围区间数据。对于一条记录来说，如果它的键的哈希值落在了某个区间范围，就被存储到负责这个范围的分区节点:

哈希函数的引入带来了一个问题:相邻的数据被打散存储到不同的分区节点。对于数据的范围查询，常常需要访问大量的分区节点，导致性能较差。

针对这个问题，可以使用组合键(compound primary key)的方式：组合键的第一列作为哈希函数计算分区的依据，剩余列作为数据排序的依据。Cassandra和Hbase中都采用了类似的方案。

在数据查询的时候，如果第一列的值是指定的，剩余列的范围查询就会很高效，因为只需要访问少量的分区节点。一对多数据模型的场景，很适合使用这种方式，例如一个社交网站应用，把(user_id, update_timestamp)作为组合键，那么查询某个用户在一段时间范围内变更的数据，就会很高效。

处理数据倾斜

通过哈希算法可以把数据分散到各个分区，但是有时候仍然不能避免极端情况下出现数据倾斜。比如在某个时间点，所有的读写请求都是针对同一个key，那么所有的请求都会被发送到同一个分区。

目前大部分系统都没有自动处理数据倾斜的能力，所以需要应用程序去处理可能出现的数据倾斜。

如果已知某个key是热点，那么可行的做法是在key的开头或者末尾加上2位随机数，这样就可以把热点key重新打散到100个分区。

分区与二级索引

当通过主键(primary key)访问数据时，我们可以通过哈希函数计算对应的分区，然后在分区中快速找到对应的数据。

但是当需要通过数据的其它字段的值去查询时，就无法通过主键达成目的了，此时我们需要引入二级索引。

分区的存在增加了二级索引实现的复杂度，所以很多分布式数据库没有支持二级索引，比如Hbase。下面我们来看看二级索引的两种主要的实现方式：基于文档(document)切分的二级索引与基于项(term)切分的二级索引。

基于文档切分的二级索引

假设我们将一个汽车销售网站的海量数据按分区存储。每一辆汽车有一个id作为主键，当我们需要按颜色或者制造商查询数据的时候，就需要使用二级索引。

基于文档切分的二级索引，为每一个数据分区，维护对应的二级索引，并且把二级索引也存储在这个分区(local index):

按照这样的方式，写入操作将十分高效:向某个分区写入数据时，在该分区对应的二级索引插入相应的id即可。

但是查询操作将变得昂贵，如果要查询所有颜色是红色的汽车，需要扫描所有的分区，查询相应的记录并汇集起来。

MongoDB、Cassandra、Elasticsearch实现了基于文档切分的二级索引。

基于项切分的二级索引

基于文档切分的二级索引采用了local index方案，另一种方式是使用global index方案，以全局的方式存储二级索引。当然我们不能把二级索引全部存储在同一个节点，那样会造成访问热点。可以基于项(term)把二级索引切分存储。

在上图的示例中，我们把所有颜色为a到s开头的二级索引存储到分区0，把所有r到z开头的二级索引存储到分区1。我们不仅可以通过范围对二级索引进行分区，也可以使用哈希函数进行分区。

此时查找所有颜色为红色的汽车，只需要读取分区1的二级索引即可，非常高效。但是相应的写入操作会变得更加复杂，插入一条数据可能设涉及到多个字段的内容，需要修改多个分区存储的二级索引。

Amazon DynamoDB 、Oracle data warehouse实现了基于项切分的二级索引。

重新平衡分区

数据库的分区数量，以及每个分区存储的数据量，是不断动态变化的。在某些场景下，我们需要对分区执行重新平衡(rebalancing)操作：

• 查询的数据吞吐量增加，希望通过增加节点来增强负载处理能力。
• 数据库的数据量增加了，希望通过添加更多的内存和硬盘来存储数据。
• 某台机器挂了，这台机器上分区存储的数据，需要被重新存储到其它分区。

对于分区重新平衡操作，期望满足以下目标:

• 操作完成之后，集群的负载(数据量、读请求、写请求)在各个区间均衡分布。
• 操作期间，数据库正常向外提供服务。
• 只对部分必要的数据进行移动，避免移动大量的数据在集群中引发高负载。

固定数量分区

可以预先设置一个远超节点数量的分区总数N，并保持N不变，然后让每个节点负责存储某几个分区的数据。

当集群中新增加一个节点时，这个节点可以从其他节点窃取(steal)几个分区的数据，以保持各个节点数据量的均衡，并且只需要移动几个分区的数据。

动态分区

动态分区的核心思想，是基于数据量的大小来动态调整分区的数量。

当某个分区的数据量超过设定的阈值时，该分区就自动*分裂(split)成两个分区，一个分区存放在原来的节点，另一个分区移动到新的节点存储。

Hbase就采用了这种动态分区的实现方式。

按比例分区

另外一种分区算法，是保持每个节点的分区数量不变，分区的总数和节点的数量成正比。

假设每个节点的分区数量设置为n。当集群中新增加一个节点之后，会随机选择n个分区，每个分区分裂成两个新分区，一个新分区存储在原来的节点，另一个新分区存储在新增的节点，以此来保证节点的分区数量仍然为n。

Cassandra采用了按比例分区算法。

总结

本章我们主要介绍了大数据集的分区算法。当数据集的大小超越了单机节点处理能力时，就有必要对数据集进行分区。

分区算法的核心目标是让各个节点之间的数据保持均衡，避免出现数据热点和性能瓶颈。有两种主要的分区算法:

• 基于键范围的分区。将数据的键排序，每一个分区负责管理一段范围的键。
• 基于哈希算法的分区。将数据的键按哈希函数打散，每一个分区负责管理一段哈希值范围。

我们还介绍了二级索引的实现方式：

• 基于文档的二级索引。将二级索引和对应的数据内容存放在同一个节点。这种方式降低了写操作的成本，但是增加了读操作的成本。
• 基于项的二级索引。对二级索引打散之后存储到相应的节点。这种方式降低了读操作的成本，但是增加了写操作的成本。

最后，为了让各分区的数据始终保持平衡，我们还介绍了多种分区再平衡算法，比如固定数量分区、动态分区以及按比例分区。