PolarDB-X同时支持Hash与Range的分区算法，但是默认情况下，我们选择了使用Hash算法。
像YugabyteDB默认也是Hash的分区算法，而TiDB、CockroachDB是Range分区算法。
那么，Hash与Range对于数据库，到底意味着什么？作为应用，又该如何选择？PolarDB-X的Hash分区与其它数据库的Hash分区有什么区别？
先直接抛结论：
- Hash适合预分片，系统会更具确定性；Range更依赖调度系统
- Range对范围查询很友好，Hash范围查询基本等价于全表扫描
- Range对前缀查询很友好，实际上属于一种范围查询；PolarDB-X的Hash分区也能很好的支持前缀查询；其他数据库的Hash分区需要依赖非模板化的subpartition来支持部分的前缀查询
- Range分区与PolarDB-X的Hash分区都能很好的解决数据分布热点问题
- Range在自增序列、时间等字段的写入上容易导致热点，但可以通过使用不自增的序列等方法规避
- PolarDB-X从设计理念上更关注稳定性与确定性
一致性Hash与取模
首先我们需要再次明确的是，PolarDB-X中的Hash指的是一致性Hash的。其实一致性Hash与Range是非常类似的，底层都是按范围区间划分分区，像PolarDB-X、YugabyteDB的Hash都是这样实现的一致性Hash。
可以简单的理解为，这里的一致性Hash就是对Hash值做Range。例如，对于同一个值value：
- 一致性Hash：Range(Hash(value))
- Range：Range(value)
一致性Hash示意：
因此一致性Hash支持很多对Range的操作，例如对某个Partition做分裂、合并某些Partition等。所以一致性Hash在增减分片数上，可以做到局部性。
与之对应的，是一些采用取模算法实现的Hash，例如大部分数据库中间件。
取模算法实现简单，但有一个很大的问题是，你无法对一个单独的分片做分裂等操作，做不到局部性。
例如，当前是4个分片，其取模算法就是ID % 4，当你要增加到5个分片的时候，取模算法就是ID %5，这时你会发现，超过80%的数据都要重新移动，其代价和完全重建一遍数据没有什么太大差异，如图：
所以取模实现的Hash在分布式数据库中是非常糟糕的一种分布策略。
我们这里比较的是一致性Hash与Range。
预分区
Hash值的分布一般是比较均匀的，因此Hash可以非常便捷的做预分区。例如提前分为64个分区，那只需要在整个哈希值的范围区间上等分为64份就可以了。
但是对于Range分区，数据本身的分布是跟业务特征强相关的，没有办法提前预测到分布的情况，很难做预分区。常见的Range的分区方法有两类：
- 用户提前定义，常见于时间类型分区里
- 依赖调度器，随着数据的写入，逐渐的将Range进行分裂
第一种方式适用场景有限。第二种依赖调度器的方式，需要业务进行长时间的运行，才能达到一个比较稳定的状态，存在一些不确定性。
对于稳定性比较高的OLTP业务，一般会希望数据库在性能和稳定性方面是比较确定性的，因此会更倾向于使用预分区的方式。
范围查询
Hash与Range显而易见的区别，在于范围查询上。
Range由于具备顺序性，能够做到相邻的值在同一个或者相邻的分区上，在面对范围查询时，可很好的做到分区裁剪。
但是对于Hash，其Hash值具备顺序性，但其值是不具备顺序性的。因此一般情况下，一个范围查询涉及到几个值，大概率就会涉及到几个分区。
查一个分区的代价显然比查多个分区要小。
范围查询常见于几个场景：
- 时间类型上的范围查询。时间是天然跟顺序相关的数据了，例如查询最近一个月的日志等，都是典型的范围查询
- 另外常见的是一个benchmark，典型的如sysbench中的oltp_read_only脚本，会测试一个范围查询。这个其实很容易理解，sysbench诞生的时候单机数据库还是主流，测测范围查询是很正常的，实际上并无明显的业务意义，这个让很多使用Hash的分布式数据库吃亏不少。
对于大多数业务来说，查一个范围的用户id，查一个范围的商品id，这些绝对不会是主流用法。从业务实际意义上来看，范围查询主要还是针对时间类型。
对于范围查询，Range一定是有优势的，所以我们也推荐用户在一些时间类型的Global Index上，使用Range分区。
另外还有另外一种不那么明显的范围查询，用处是非常广泛的。
前缀查询
索引的前缀匹配查询其实是一种范围查询。
组合索引是很常用的索引类型，它的特点是包含多个索引字段。一般情况下，我们期望在满足前缀匹配的情况下，即使没有办法提供所有的索引字段的值，也能将数据的扫描范围缩小。
例如组合索引(a,b)，如果a有一定的区分度，那么对条件a=1也有过滤效果。
Range分区对前缀查询的处理
Range对前缀匹配查询的处理是很自然的。上文提到，索引的前缀匹配查询其实是一种范围查询，例如对a=1的查询，实际上可以表示成：
(1,b.MIN) <= key <= (1,b.MAX) 这样的范围查询对于Range分区，能够很好的做分区裁剪。直观的理解是，对于a=1所有记录，都在同一个或者相邻的分区里。
因此，当组合索引使用Range分区时，并不需要做多级分区，只需一级分区即可。
Hash分区对前缀查询的处理
对于组合索引(a,b)，使用Hash分区的话，分区键应该如何设计？
方案1：使用a作为分区键。 这里会出现的问题是，a的区分度如果很低，例如，a代表的省份，那就会出现热点数据。这是YugabyteDB使用的方案。
方案2：使用(a,b)同时作为分区键。 也即Hash(a,b)=Hash(concat(a,b))。
如图示意：
这种方案下，只要(a,b)整体的区分度比极高，就不会出现热点。这个和使用单机数据库的理念是一样的。
但是，给定的查询条件只有a时，则无法计算出hash值，不能做任何的分区裁剪。
这个和单机数据库二级索引一般情况下都支持前缀查询是不一样的。
注意，大多数提供类似partition by hash(a,b)语法的数据库，无论是单机的还是分布式的，都是这样无法做前缀裁剪的实现。
方案3：使用二级分区，a、b分别作为一级分区和二级分区的分区键。 如图示意：
这样在匹配到前缀的情况下，依然能做一定的分区裁剪。
但是，这样做，需要支持无限层级的子分区（索引支持多少列，就能建多少级的子分区。），用法上会比较奇怪，目前也没有数据库实现无限级的子分区。
事实上，这是大多数支持Hash分区的分布式数据库你能使用到的方法，例如OceanBase等，你只能用它来解决不超过两个列的前缀查询问题。
方案4：使用a的hash值与b的hash值作为range分区键，也即定义Hash(a,b)=Range(Hash(a),Hash(b))。
这样在匹配到前缀的情况下，依然能做一定的分区裁剪。同时，只有一级分区，并不需要多级分区。
例如对a=1的查询，实际上可以表示成：
(hash(1),b.HASH_MIN) <= key <= (hash(1),b.HASH_MAX) 如图示意：
通过上图可以发现，a=1会包含p45与p46两个相邻的分区，a=99仅包含p47一个分区。
PolarDB-X中的partition by hash(a,b)使用的是方案4，可以很好的支持前缀查询。
热点值
这是非常有趣的一个点。
这里的热点值指的是某个key的某个值的行数或者写入量非常多。例如，一个典型的电商系统，存储订单表：
create table orders (
id bigint,
buyer_id varchar(128) comment '买家',
seller_id varchar(128) comment '卖家',
primary key(id),
index sdx(seller_id),
index bdx(buyer_id)
)数据如下：
我们关注下sdx这个Global Index。
这个字段表示的是卖家ID，我们可以想象到，电商系统里一般会存在一些大卖家，例如天猫超市，就是淘宝系统里的一个大卖家。这种大卖家会产生非常多的订单，如上图，sdx这个Global Index，seller_id=88的数据行会非常的多，远高于普通的卖家。
这种数据就是我们这里要讨论的热点值。
注意： 热点很容易被理解为数据量的热点。但实际的生产系统中，数据量本身往往并不会构成瓶颈（本例中，单一的卖家数据再多，超过T的量级也是很罕见的）。更常见的是写入量成为热点，例如单一的卖家产生了远大于单DN能力的写入TPS（双十一零点的订单写入量就是典型的此类场景）。
我们来看下，这种热点数据，PolarDB-X的Range和Hash分别是如何处理的。
Range分区对热点值的处理
按照常规做法，使用Range对索引进行分区，我们会使用索引Key与主键一起作为分区键，对于本例，也即partition by range(seller_id,id)。我们稍后来看为什么。
本例中的数据按照(seller_id, id)有序，分布如下：
当发现p1存在热点时，我们将p1分区进行分裂即可：
seller_id=88的记录分布在了两个partition内。好处是，数据被打散了，两个partition可以被调度到不同的DN上，共同承载写入的负载与存储空间；但是，针对seller_id的查询，也需要同时去查两个分片。这种方式，拓展了写的能力与存储空间的上限，但是读的代价是变大了的。
对于88这种大卖家，这个代价是可以接受的，但是对于普通的小卖家，我们还是希望尽可能让其数据分布在一个partition内。Range的特点很好的保证了这一点。
这里可以发现Range处理热点的特点：
- 由于Range能很好的支持前缀查询，直接对热点分区进行分裂即可
- 对于非热点数据，Range能做到将它们放在最多相邻的两个分区里，其查询不会有放大的问题；对于热点数据，Range又能通过分裂将他们放在多个分区里
可以看出，我们似乎什么都没做，Range的特性（范围查询，前缀匹配，分裂）自然而然的很好的消除了数据的热点。
也正因如此，我们会把主键一起作为索引分区键的一部分拼在最后（对于TiDB、CockroachDB等基于分布式KV做的数据来说，这么做还有一个原因是用来实现非唯一键）。
PolarDB-X Hash分区对热点值的处理
同Range分区的索引类似，使用Hash分区的索引，我们也会使用索引Key与主键一起作为分区键，对于本例，也即partition by hash(seller_id,id)。
本例中的数据按照(hash(seller_id), hash(id))有序，分布如下：
例子中，seller_id=88的数据集中在分区p1，这个分区相对于其他分区就是明显的热点。
与range分区类似，当发现p1存在热点时，我们将p1分区进行分裂即可：
可以看到，PolarDB-X的Hash分区对热点数据的处理的结果与Range分区类似，也能做到只打散大卖家的数据而不影响小卖家的数据。
其他数据库Hash分区对热点值的处理
如上文所述，对于非PolarDB-X的数据库，大多数多列的Hash分区不支持前缀查询，因此无法像PolarDB-X一样简单的对分区进行分裂即可打散热点。此类数据库一般通过子分区来部分解决此类问题。
与PolarDB-X使用(seller_id, id)做分区键不同，由于不支持前缀查询，所以分区键只能选择seller_id，也即partition by hash(seller_id)，本例中的数据分布如图所示：
例子中，seller_id=88的数据集中在分区p1，这个分区相对于其他分区就是明显的热点。
在其它数据库中，典型的处理此类问题的方法是对该分区按其他字段（一般主键字段即可）做子分区，如图：
这样p1变成了p1_0与p1_1两个分区，每个分区的数据量重新达到了均衡的状态，没有了热点。
这里值得注意的是：为了保证上文提到的不对小卖家造成读放大的问题，我们必须对 特定的热点分区做subpartition，但不能对所有分区做subpartition。 这个一般称之为非模板化的subpartition。
所以如果一个数据库的Hash分区不支持前缀查询，那它能否解决部分热点问题，需要看其是否具备非模板化的subpartition能力。
连续写入
这是Range分区特有的一类也是很常见的问题。
例如当我们生成的主键具备一定的单调性，当发生连续INSERT的时候，就会将写请求集中在最后的分片上。
这个例子大家已经很常见了，常见的做法是对生成的主键做一下打散，例如TiDB中的SHARD_ROW_ID_BITS就是将生成的序列值的前几位随机的进行反转，实际上就是完全放弃了AUTO_INCREMENT的单调性。
另一个有趣的例子是Date与Datetime。
例如我们有一张使用Range进行分区的日志表：
CREATE TABLE log(
id int primary key,
c1 datetime,
c2 date,
index idx1(c1),
index idx2(c2)
)当我们往这个表里不停的写记录时，我们会发现idx1上会出现写入的热点，而idx2不会，为什么？
因为c2的精度只到日期，前后写入的数据的c2的值是一样的，因此它并不具备单调性，此时c2="2021-08-11"的记录，会成为一个热点，但随着数据的不断写入，按我们上一个章节的描述，c2="2021-08-11"所在的分区会进行分裂，等于按照id做了打散，热点会逐渐消失。
但是c1的精度到毫秒（甚至更高），前后写入的数据的c1值是不一样的，并且是增长的，因此c1上会出现热点，并且这种热点是不会消失的，无论如何分裂，最后一个分区都会是热点。
我们为什么选择默认使用Hash
Range分区在对范围查询上相对于Hash分区有着很强的优势。但是，Range要能很好的做到这样的效果，无法做到预分区，强依赖“随着数据变化，Range不停的进行分裂、合并”这样的自动调度机制。你的数据库系统内，会随时发生Range的分裂、合并等操作，是一个动态的过程，具有比较强的不确定性。
例如在双十一的0点，一个分片触发分裂带来的抖动可能会是致命的。
调度依赖的变量非常多，例如数据量、读写量、IO、CPU、网络等等。双十一前我们都会做压测，但大促真正到来时，这些变量很难和压测的时候是一致的。你很难去对调度器的行为做很多的预设，你只能相信它是正确的。但作为DBA或者应用开发者，肯定希望在这样的关键时刻，数据库的运行状态和压测时的状态一致。
而Hash能够做预分区，具备更强的确定性，可以确保在一些重稳定性的系统上，数据分布处于一种相对静态的状态。同时，PolarDB-X的Hash分区同样能够很好的处理热点等问题。
PolarDB-X源于淘宝的电商、交易等核心场景，对稳定性、确定性的要求放在了第一位，因此选择了使用Hash作为默认的分区方式。对于包含大量范围查询的场景，我们也推荐使用Range分区。
