导读：hash分片有没有缺点？除了hash分片还有没有其他分片方式呢？我们带着这些问题，来开始本篇的重点——范围分片。
作者：bdseeker
来源：BigData之路（ID：bigdata3186）
01 hash分片的痛点
我们跳出hash分片的固有思维，重新看下路由分片，hash分片法是通过hash函数对key进行处理，然后分配在某个partition中，partition 最终又会通过一定的映射规则最终落在machine上。
因此当需要查询一个key的value时，要经过key-partition的映射表和partition-machine的映射表去两次寻址，从而实现路由寻址。如果此时有成千上万个key要查询，会是什么样子呢？
如上图所示，我们不难看出，当有海量的Key进行查询的时候，依旧会拆分成若干次单key路由，因此会不断重复两次寻址的过程，即使是相邻的两个Key，如Key1、Key2，也要重复相同的操作。由此也引出了hash分片最大的痛点，受hash路由分片模型的限制，hash分片只适合点查询，而不适合范围查询。
02 破题：构造范围分片
究竟怎样的路由分片架构适合范围查询呢？我们接下来结合《大数据基础-原来这就是路由分片》的思路来一步一步来将点查询模型逐渐演化成范围查询模型。
1. 厘清点查询和范围查询的关系
点查询通常是单Key查询；而范围查询通常是多Key查询（存在Key相邻或者间隔较远的情况）
如上图所示，点查询和范围查询的关系一句话概括，多个有序的点查询约等于范围查询 之所以说是“约等于”，在这种理解上，范围查询只是点查询的封装，每次范围查询，依然会进行多次寻址，因此并没有本质的变化，如果每次Key查询计数为1（实际上每次key查询代表两次寻址）的话，点查询和范围查询可以解释成1 1=2的关系。
2. 为点查询和范围查询增加分片层
在hash分片中，通过hash函数处理后，一般有序的多个Key，会被存放在多个分片中，尤其是相邻的Key大概率不在同一分片中。
此时会发现查询涉及到的Key越多，查询分片也会越多，如果此时能减少查询分片的数量，在key-parititon映射的效率也会变高（为什么高呢？先卖个关子，后面我会提到，各位同学也可以先思考下），干说比较抽象，结合模型来看，如下所示：
我们将Key1对应的分片定为分片a，Key2对应的分片定为分片h，Key(n) 对应分片m，在hash分片模型中会存在多个Key通过hash函数存放于同一个分片中的情况，这里以Key(n-1)对应分片a 进行举例。4个Key在hash分片进行Key-Partition查询时，实际上会路由到3个分片中。此时我们进行两个操作：
1）将已有的三个分片进行重组
将3个分片按照Key的顺序进行拆分重组，分片a(包含Key1、Key(n-1))、分片h(包含Key2)、分片m (包含Keyn)重组为分片a(包含Key(n-1))、分片m(包含Keyn)、新分片x(包含Key1和Key2),当然这里如果所有Key都是连续，合并成一个分片当然是最理想的情况。我们在这个示例的基础上向外延伸，分片拆分合并有什么好处？
无序变有序，针对原本多个无序的分片，按照一定规则，将相近的Key进行合并，之前连续的Key需要在多个分片中查找，而现在可以减少查找的范围,只需要在少量分片中进行查找，提升查询的效率。
2）优化路由表
将Key-Partition由4条元数据(Key1->分片a，Key2 ->分片h，Key(n-1)->分片a，Keyn ->分片m)缩减为3条(Key1->新分片x),Key(n-1)->分片a，Keyn-分片m)，原来4条元数据缩减成3条，由密集索引转化为稀疏索引。什么是密集索引和稀疏索引呢？
在路由分片模型中，KeyPartition映射一般是通过路由表来实现的(实际上一致性hash也是另类的路由表，只不过没有固化成index的结构，需要每次计算)，在路由表中每个Key都会有其路由到分片的位置，即Key1 ->分片a，Key2->分片h，Key(n-1) ->分片a等。
同样的将每个Key的分片位置都记录路由表中进行索引的方式叫做密集索引，而路由表优化后，由于Key是有序的，因此只需要记录Key1->新分片x即可，此时在新分片x中就可以找到Key2。这种索引类型叫做稀疏索引。
上面我们针对分片层进行拆分合并，并且对路由表的元数据进行索引类型转换，更适合于连续Key的范围查询，所以在范围数据寻址效率上，点查询相比于范围查询，可以简单理解成达到了1 1<2的状态。
3. 为点查询和范围查询增加机器层
- IO效率提升
点查询和范围查询的路由分片模型和第一篇基础路由分片模型是相符合的，因此每个分片都会对应的一台机器进行承载。
此时乍一看可能两者可能并没有明显区别，我们在结合上一节来看，由于在上一节增加分片层时，范围查询中的分片中数据是有序的，因此在读写时是顺序IO，而不像在点查询时是随机IO ，而对于大数据服务的应用场景来说，顺序IO的提升效果会更加明显。
为什么顺序IO比随机IO效率高呢？通常一次读写磁盘的过程分为3步：
- 寻道时间：磁头移动定位到指定磁道
- 旋转延迟时间：等待指定扇区从磁头下旋转经过
- 数据传输时间：数据在磁盘与内存之间的实际传输
在顺序io中，由于不需要经常寻道，所以大部分时间都是数据传输时间，但随机io 会有大量的时间都在寻道和等待扇区经过；此外在linux 还会预读多个连续的page页缓存到内存中，读内存的速度是远高于读磁盘的，因此相比之下范围查询预读页的利用率非常高，而点查询对于预读页的利用率是非常低的。
- 适合客户端缓存分片的物理位置
在点查询中由于涉及到海量Key，每个Key都位置都比较分散，此时客户端缓存所有分片位置显然是不现实的。而通过缓存分片合并后的分片位置实际上可以提供缓存的命中率。
03 范围分片的优势
上面详细讲了范围分片的演化过程，优势也很明显：
- 批量读取数据时，可以通过缓存分片的物理地址位置，直接访问，提升读命中率。
- 物理上使用顺序IO，相比随机IO，提升批量读写效率。
- 元数据(路由表)优化，使用稀疏索引，元数据压力降低。
- 范围分片更加灵活，不再受hash函数的限制，可以灵活的调整范围分片中每个分片的大小(分片拆分)和位置。
04 理论上的最佳实践
那么现有系统中有哪个系统使用范围分片的方法进行路由分片呢？实际上有很多，如下图所示。
也许有的服务你没见过，但是不妨碍咱们知道他们的核心分片逻辑也侧面印证了一句话，单纯从技术角度来说，真是越学不会的技术就越多；但反过来看，咱们现在做的事情，正是跳出单一的技术，全局视角审视各个服务。
这里咱们拿HBase进行举例分析。
1. HBase分片模型
在HBase中，分片是基于rowkey排序后，按照不同范围进行拆分的，即[startKey,endKey)这样一个左闭右开区间，每个分片称为一个Region。
- 一个HBase集群中有多张表，每张表包含1个或者多个Region，每个Region有且只有一台机器进行映射，换言之，每台机器会承载0个或者多个Region，这里的机器在HBase中叫做RegionServer。
- 由于Region中rowkey是已经排序好的，因此后一个Region的startKey实际上是前一个Region的endKey。并且在第一个Region中是没有startKey的，同理最后一个Region也是没有endkey的。所以当所有region组合在一起，就可以覆盖这个表中任意的rowkey数值。
2. 元数据路由策略
- 在HBase中数据的查询，涉及两个层级的路由：一是rowkey到region的路由，二是region到RS的路由。两级路由信息均存放在.meta表中,meta表实际上也是稀疏索引，只记录了startKey和endKey的的值，通过稀疏索引可以定位key对应Region的位置。
3. LSM存储结构与优化
- HBase使用LSM(Log-Structured Merge Tree)的存储结构，将磁盘的随机IO转化为顺序IO来提高批量读写的性能，代价就是在点查询上性能有所牺牲。
- 在HBase中当写入一条数据后，率先会写入WAL，然后写入MemStore中。当Mem-Store满足一定条件后，开始flush数据到磁盘中，随着写入的不断增加，磁盘文件HFile也会越来越多，由于数据位置不确定，所以要遍历所有的HFile，因此在点查询时LSM树读性能时没有B 树好（这也是为什么在点查询上HBase不如Mysql的主要原因）。但是HBase也做了一定的优化，会定期合并若干个HFile，即多个文件合并成1个文件，以此来提高读性能。
4. 更加灵活的调度
- 在HBase中每个Region内部都是有序的，当Region过大或者有Hot Key出现时，会按照相应规则切分Region，此时就不必受hash函数的制约，Region可以自由的拆分和迁移。
- HBase存储层和计算层实际上是分离的，这也是现在主流架构，因此当Region迁移时不需要迁移物理数据，因此迁移成本很低。
05 尾记
本篇以hash分片为基础点出发，介绍了hash分片的痛点，基于通用的路由分片模型，逐渐过渡演化到范围分片，然后讲解了范围分片的优势，最后结合HBase的最佳实践来重新印证范围分片的理论。
最后单独拿出文章中的一句话，单纯从技术角度来说，真是越学，不会的技术就越多；但反过来看，咱们现在做的事情，正是跳出单一的技术，全局视角审视各个服务。相信坚持总会有所收获，加油！
