13518219792
最近开发的搜索引擎中，需要对索引进行分片。根据项目的需求，我们提供了两种分片方式。过程博客记录一下。
Hash算法
原理很简单，通过行键（_id）的Hash值确定所在的分片，然后再进行操作。
举个栗（例）子，现在有个索引，初始化5个分片，分别为shard0， shard1， shard2， shard3， shard4。
现在需要保存一行数据，_id为0001000000123，_id的HashCode为1571574097，对5求余（1571574097 % 5）为2，从而确定数据应该保存在shard2。下面是一个简单的图解：
Hash算法分片实现非常简单，计算过程只需要知道分片数量即可完成定位。但也正因为分片数量是算法的一部分，修改分片数量的代价也非常昂贵。
有一种解决方案是重新排列，比如从M个分片切增加到N个分片，先将每个分片切分为N个小分片，然后再将所有小分片合并为大分片。从网络上复制了一张图解说明，
这种方式的优点是，可以任意设定新的分片数量。缺点是需要对所有数据进行重新排列，如果数据量很大，可能会非常耗时。
当然，由于项目数据增长是不可预测性，我们没有选择上面增片方式，而是选择了另外一种增片的方式。
动态分片
结合Hash算法和二叉树的原理，进行动态增加分片。
首先，Hash算法与之前一样，搜索创建时，可以设置一个初始化的分片数量，例如初始化5个分片，分别为shard_0， shard_1， shard_2， shard_3， shard_4。添加数据时，通过_id的Hash值确定数据需要保存到哪个分片。不同的是，我们设置了每个分片的大行数，当某个分片的数量达到大行数时，该分片会分拆分为两个小的分片，并且作为当前分片的子分片。
例如，设置分片大行数为1000万，当shard_2超过1000万时，分裂为两个子分片shard_2_2和shard_2_7。如果shard_2_2数据继续增长到1000万，则分裂子分片shard_2_2_2和shard_2_2_12。
从示例中可以看出，分裂并不是毫无规则，假设分片的初始数量为m，k表示二叉树深度，则分片n的分裂规则为
shard_n 分裂为 shard_n_n和shard_n_(n + m * 1)
shard_n_n 分裂为 shard_n_n_n和shard_n_n_(n + m * 2)
shard_n_(n + m * 1) 分裂为 shard_n_(n + m * 1)_(n + m * 1) 和 shard_n_(n + m * 1)_(n + m * 1 + m * 2)
...
上面的公式看起来很复杂，我们使用图解来说明分裂过程
如果还没有明白，我们可以通过_id寻找对应的分片来梳理一下思路，还是上面的例子，
需要保存一行数据，_id为0001000000123，_id的HashCode为1571574097，对5求余（1571574097 % 5）为2，从而确定数据应该保存在shard_2。
shard_2已经分裂为shard_2_2和shard_2_7两个子分片了，这一层的基数为10（基数=初始化分片数量*层数），我们将1571574097对10求余(1571574097 % 10)为7,则数据保存在shard_2_7。
shard_2_7没有子分片，说明该分片没有分裂，直接保存在该分片即可。
分析一下分片寻找原理：
按照hash算法找到分片；
如果分片有子分片，则从子分片中查找；
如果分片没有子分片，则数据保存在该分片；
再来分析一下分片分裂规则，为什么shard_1会分裂为shard_1_1和shard_1_6？
原因很简单，shard_1表示id的hash值对5取余后值为1，如果shard_1分裂为2份，则第2层的基数10=上一层基数*2，即5 * 2。对5取余值为1，那么对10取余结果只会是1和6，因此
shard_1分裂为shard_1_1和shard_1_6。
数据一致性
动态分片是在使用过程中自动分片，分片过程会非常长，经过测试，索引32列500万行的分裂为两个子分片，耗时245秒。分裂过程如果原始数据发生修改，这些修改可能会丢失。因此，在分裂过程中需要一定的措施保障数据安全性。
方法一，使用悲观锁。
分裂前对锁定分片不能再修改，直到分裂完成后才能再修改。
优点：逻辑简单粗暴，开发难度低。
缺点：锁的时间太长可能会导致调用服务方产生大量的异常请求。
方法二，使用事务日志。
分裂前创建事务日志，当前shard所有新增、修改和删除操作都写入事务日志。分裂完成后，锁定分片和子分片，从事务日志中恢复数据到子分片，然后解锁。
优点：只有在创建事务日志和恢复数据时会锁定分片，锁定时间比较短暂，影响服务调用方几乎不受影响。
缺点：开发难度大，需要开发一套事务日志和日志恢复操作接口。但是底层lucene存储已经有一套事务日志接口和实现，该缺点几乎可以忽略。
行键递增分片
如果保存数据的行键整体上是递增的，例如，行键是000000001,000000002,000000003,...这种格式，可以按行键进行分片。这种分片实现方式比较简单，
1. 创建索引时设置一个初始化分片；
2. 添加数据过程中，并且记录分片行键最小值minId和大值maxId；
3. 当分片数据量超过设置的大值是，创建一个新的分片，新增的数据保存在该分片；
4. 更新数据时，通过与每个分片的minId和maxId比较，确定所在的分片。
行键递增分片与Hash算法分片比较：
1.行键递增分片方式实现更简单，开发成本更低；
2.行键递增分片通过minId和maxId定位分片，如果每个分片信息中需要记录分片的minId和maxId；
3.行键递增分片存入数据时，需要按照一定的顺序存入，否则可能会导致数据倾斜；
4.行键递增分片按需添加分片，只需要设置每个分片的大行数，没有分裂过程；
5.行键递增分片大量的压力集中在最新的分片上，Hash算法分片压力分散到各个分片，理论上Hash算法分片可以支持更高的吞吐量。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
