背景
  • MyCat 对于字符串类型为分片字段的数据,有三种分片模式,分别是:模值 hash(求模法),jumpstringhash(跳跃法),一致性 hash(环割法)。

  • dble 对于 hash 算法选取方面,除了继承 MyCat 的模值 hash,并没有延续使用 MyCat 的一致性 hash,而是推荐使用性能更佳、均衡性更好的“jumpstringhash”算法。

介绍
下面对于环割法(一致性 hash)及跳跃法(jumpstringhash)的原理、特性及优缺点进行简单的介绍。
环割法(一致性 hash)
环割法的原理如下:

1. 初始化的时候生成分片数量 X × 环割数量 N 的固定方式编号的字符串,例如 SHARD-1-NODE-1,并计算所有 X×N 个字符串的所有 hash 值。

2. 将所有计算出来的 hash 值放到一个排序的 Map 中,并将其中的所有元素进行排序。

3. 输入字符串的时候计算输入字符串的 hash 值,查看 hash 值介于哪两个元素之间,取小于 hash 值的那个元素对应的分片为数据的分片。

跳跃法(jumpstringhash)
跳跃法的原理如下:
1. 根据公式:

将数据落在每一个节点的概率进行平均分配。

2. 对于输入的字符串进行计算 hash 值,通过判断每次产生的伪随机值是否小于当前判定的节点 1/x,最终取捕获节点编号最大的作为数据的落点。
3. 在实际使用中使用倒数的方法从最大节点值进行反向判断,一旦当产生的伪随机值大于 x 则判定此节点 x 作为数据的落点。

数据比较

下面将通过测试对环割法和跳跃法的性能及均衡性进行对比,说明 DBLE 为何使用跳跃法代替了环割法。

  • 数据源:现场数据 350595 条

  • 测试经过:

    1. 通过各自的测试方法执行对于测试数据的分片任务。

    2. 测试方法:记录分片结果的方差;记录从开始分片至分片结束的时间;记录分片结果与平均数的最大差值。

    3. 由于在求模法 PartitionByString 的方法中要求分片的数量是 1024 的因数,所以测试过程只能使用 2 的指数形式进行测试,并在 PartitionByString 方法进行测试的时候不对于 MAC 地址进行截断,取全量长度进行测试。

  • 测试结果

1. 使用不同方法时,方差随分片数量的情况变化表
summary
1. 在同样分片数据量的情况下,两种方法的方差都会随着分片数量的增加而减少。
2. 在分片数量足够多的情况下,两种方法并没有太大的区别。
3. 在节点数量相对较少的情况下,跳跃法的均衡性最好。
4. 使用环割法时,增加环切的数量能够提高分片的均衡性,但是均衡性提高的幅度会随着分片数量的增加而减少。

2. 使用不同方法时,消耗的时间随着分片数量的情况变化表

summary
1. 环割法相比于跳跃法有较大的性能差距,大约相差一个数量级。
2. 跳跃法的时间消耗会随着分片数量的增加而小幅度的上升。
3. 环割法的时间消耗随着环割数量的增加而小幅度的增加。

3. 使用不同方法时,节点分配数据量和平均数据量的最大偏差和分片数量的情况变化表

summary
1. 两种方法的最大偏差都会随着分片数量的上升而下降,最后当分片数量足够多的时候,两种方法并没有明显的区别。
2. 在分片数量少的时候,跳跃法的均衡性最好,环割法相对最差。
3. 使用环割法时,增加环切的数量能够提高分片的均衡性,但是均衡性提高的幅度会随着分片数量的增加而减少。

综上测试对比:

从一致性 hash 的多种测试结果来看,都没有很好的性能表现。因此,DBLE 在 hash 算法选取方面,使用 jumpstringhash 代替了一致性 hash。
如果您是从 Mycat 迁移过来的,使用了一致性 hash,可以通过自定义拆分算法来实现。
自定义拆分算法相关链接:
https://github.com/actiontech/dble-docs-cn/blob/master/1.config_file/1.09_dble_route_function_spec.md

社区近期动态

No.1

Mycat 问题免费诊断


诊断范围支持:

Mycat 的故障诊断、源码分析、性能优化

服务支持渠道:

  1. 技术交流群,进群后可提问

    QQ群(669663113)

  2. 社区通道,邮件&电话

    osc@actionsky.com

  3. 现场拜访,线下实地,1天免费拜访

关注“爱可生开源社区”公众号,回复关键字“Mycat”,获取活动详情。


No.2

社区技术内容征稿


征稿内容:

  1. 格式:.md/.doc/.txt

  2. 主题:MySQL、分布式中间件DBLE、数据传输组件DTLE相关技术内容

  3. 要求:原创且未发布过

  4. 奖励:作者署名;200元京东E卡+社区周边

投稿方式:

  1. 邮箱:osc@actionsky.com

  2. 格式:[投稿]姓名+文章标题

  3. 以附件形式发送,正文需注明姓名、手机号、微信号,以便小编及时联系