首页 > 其他分享 >分布式 | dble 沿用 jumpstringhash,移除 Mycat 一致性 hash 原因解析

分布式 | dble 沿用 jumpstringhash,移除 Mycat 一致性 hash 原因解析

时间:2022-12-20 15:36:37浏览次数:74  
标签:割法 hash 移除 Mycat 均衡性 分片 跳跃 数量


作者:爱可生开源社区

背景

  • 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. 使用不同方法时,方差随分片数量的情况变化表

量\方差

环割法1000片

环割法10000片

跳跃法

4484780

812418

315703

601593

545599

315587

453694

131816

67018

213856

74360

86125

69313

46618

37939

24329

26415

25429

分布式 | dble 沿用 jumpstringhash,移除 Mycat 一致性 hash 原因解析_中间件

summary

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

| 分片数量\耗时| 环割法1000片 | 环割法10000片 | 跳跃法 |

| ----- | ----- | ----- | ----- |

| 4 | 0.419| 0.532| 0.069 |

| 8 | 0.41 | 0.425 | 0.067 |

| 16 | 0.512 | 0.545 | 0.06 |

| 32 | 0.55 | 0.525 | 0.07 |

| 64 | 0.683 | 0.59 | 0.087 |

| 128 | 0.559 | 0.659 | 0.094 |

分布式 | dble 沿用 jumpstringhash,移除 Mycat 一致性 hash 原因解析_分布式_02

summary

  1. 环割法相比于跳跃法有较大的性能差距,大约相差一个数量级。
  2. 跳跃法的时间消耗会随着分片数量的增加而小幅度的上升。
  3. 环割法的时间消耗随着环割数量的增加而小幅度的增加。
  1. 使用不同方法时,节点分配数据量和平均数据量的最大偏差和分片数量的情况变化表

分片数量\最大平均数偏离

环割法1000片

环割法10000片

跳跃法

4

3027

1513

802

8

1530

1488

822

16

1121

622

556

32

1044

358

672

64

673

560

424

128

503

348

682

分布式 | dble 沿用 jumpstringhash,移除 Mycat 一致性 hash 原因解析_中间件_03

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​


标签:割法,hash,移除,Mycat,均衡性,分片,跳跃,数量
From: https://blog.51cto.com/u_15077536/5955938

相关文章

  • 你能谈谈HashMap怎样解决hash冲突吗
    在Java编程语言中,最基本的结构就是两种,一种是数组,一种是模拟指针(引用),所有的数据结构都可以用这两个基本结构构造,HashMap也一样。当程序试图将多个key-value放入HashM......
  • 如何实现移除控件?
    通过使用触发器中触发行为移除控件实现一个点击按钮移除图片的功能。效果展示:前置准备:需要移除的组件用于点击触发移除控件的组件(下文简称“触发组件”)具体步骤:创建移除......
  • 一致性hash算法 - consistent hashing
    consistenthashing ​​算法​​早在 1997 年就在论文 ​​Consistenthashingandrandomtrees​​ 中被提出,目前在cache 系统中应用越来越广泛;1比如你有 N 个 ......
  • ConcurrentHashMap完全解析(jdk6/7,8)
    并发编程实践中,ConcurrentHashMap是一个经常被使用的数据结构,相比于Hashtable以及Collections.synchronizedMap(),ConcurrentHashMap在线程安全的基础上提供了更好的写并发能......
  • HashSet源码解读
    HashSet源码解读publicclassDemo5{finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node......
  • SpringBoot3.x中spring.factories功能被移除的解决方案
    背景笔者所在项目组在搭建一个全新项目的时候选用了​​SpringBoot3.x​​​,项目中应用了很多​​SpringBoot2.x​​​时代相关的第三方组件例如​​baomidou​​​出品的​......
  • Blazor组件自做十二 : Blazor Pdf Reader PDF阅读器 组件 (新版 7.1 移除pdfobject)
    BlazorPdfReaderPDF阅读器组件示例:https://www.blazor.zone/PdfReadershttps://blazor.app1.es/pdfReaders使用方法:1.nuget包BootstrapBlazor.PdfReader2._I......
  • Lua 5.3 hashint函数缺陷导致遍历table性能非常差
    最近发现线上有个服务器某些逻辑耗时比较久,问了下同事,他告诉我是因为lua的pairs函数很慢导致的。“啊!不至于吧,这数据量才多少”我一脸诧异,记忆中Lua不至于慢到这种程度,遍......
  • Hash 算法详细介绍与实现 (二)
    前言书接上回,昨天写了第一部分,《​​Hash算法详细介绍与实现(一)​​》详细介绍了Hash表和Hash算法的相关概念以及算法的基本原理。同时简单介绍几种hash算法的实现:直接......
  • Hash 算法详细介绍与实现 (二)
    前言书接上回,昨天写了第一部分,《​​Hash算法详细介绍与实现(一)​​》详细介绍了Hash表和Hash算法的相关概念以及算法的基本原理。同时简单介绍几种hash算法的实现:直接......