C语言学习网

lucene动态分片简介

发表于:2022-12-07 作者:安全数据网编辑
编辑最后更新 2022年12月07日,最近开发的搜索引擎中,需要对索引进行分片。根据项目的需求,我们提供了两种分片方式。过程博客记录一下。Hash算法原理很简单,通过行键(_id)的Hash值确定所在的分片,然后再进行操作。举个栗(例)子

最近开发的搜索引擎中,需要对索引进行分片。根据项目的需求,我们提供了两种分片方式。过程博客记录一下。


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没有子分片,说明该分片没有分裂,直接保存在该分片即可。


分析一下分片寻找原理:

  1. 按照hash算法找到分片;

  2. 如果分片有子分片,则从子分片中查找;

  3. 如果分片没有子分片,则数据保存在该分片;


再来分析一下分片分裂规则,为什么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算法分片可以支持更高的吞吐量。























0