文档章节

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

爱可生
 爱可生
发布于 09/10 16:45
字数 1405
阅读 44
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

背景

  • 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片 跳跃法
4 4484780 812418 315703
8 601593 545599 315587
16 453694 131816 67018
32 213856 74360 86125
64 69313 46618 37939
128 24329 26415 25429

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

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

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

© 著作权归作者所有

爱可生

爱可生

粉丝 12
博文 187
码字总数 332013
作品 1
徐汇
私信 提问
分布式 | DBLE 分区算法系列总结

原创: 管长龙 我们已经通过之前的六篇文章,介绍了 DBLE 和 MyCat 常见的六种分片算法,那么我们来做个总结吧! DBLE 与 MyCat 对应分片算法名和异同 第七种 DBLE分片算法—jumpStringHash ...

爱可生
07/10
19
0
​深度分析 | MyCat与DBLE的对比性能调优

作者简介 蓝寅,开源分布式中间件DBLE项目负责人;持续专注于数据库方面的技术, 始终在一线从事开发;对数据复制,读写分离,分库分表的有深入的理解与实践。 问题起因: 用benchmarksqlfor...

爱可生
03/09
140
0
技术分享 | MyCat的坑如何在分布式中间件DBLE上改善(内含视频链接)

作者简介 蓝寅,开源分布式中间件DBLE项目负责人;持续专注于数据库方面的技术, 始终在一线从事开发;对数据复制,读写分离,分库分表的有深入的理解与实践。 3月14日,爱可生开源社区联合I...

爱可生
03/19
95
0
重磅预告 | 今晚直播:MyCat的坑如何在分布式中间件DBLE上改善

上周,DBLE团队历时3个月准备的开源MySQL分布式中间件DBLE系列公开课发布了,为使社区同学能够更好的评估课程内容、质量以及对DBLE有更清晰深入的认知,我们联合IT168将在第二节课程发布前开...

爱可生
03/14
16
0
用户福利 | DBLE 社区支持免费 Mycat 问题诊断

原创作者:[爱可生开源社区] 2017年10月24日,爱可生正式开源了自主研发的企业级分布式中间件 — DBLE,江湖人送外号 “Mycat Plus”。相对于 Mycat,DBLE 从以下四点进行了增强: 修复了大量...

爱可生
07/10
19
0

没有更多内容

加载失败,请刷新页面

加载更多

ArrayList 源码分析

一、概述 本文基于 JDK8 ArrayList 底层通过动态数组的数据结构实现 内存需要连续的空间保证 添加操作涉及到数组的动态扩容 添加,删除都涉及到位置移动操作 随机查找效率快(下标查找) Ar...

hncboy
今天
4
0
采购单品汇总_华南.xlsx

import pandas as pdimport matplotlib.pyplot as pltimport matplotlib as mp1mp1.rcParams["font.family"] = "STFangsong"# 加载《销售》表数据df1 = pd.read_excel(r"C:\Us......

龙玉滕
今天
5
0
OSChina 周五乱弹 —— 一次四千 要4次还能多给一千

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @这次装个文艺青年吧 :#今日歌曲推荐# 分享金志文的单曲《远走高飞》: 版权又回来了现在听歌得好几个软件 《远走高飞》- 金志文 手机党少年们...

小小编辑
今天
11
0
Spring Cloud Alibaba 实战(十) - Spring Cloud GateWay

> 本文主要内容是:为什么要使用网关,整合Gateway,Gateway核心学习:Route,Predicate,Filter,最后使用Gateway聚合微服务请求 先总结至此的架构 1 网关的价值 不使用网关行嘛? 各个请求直接打在...

JavaEdge
今天
4
0
【CKB.DEV 茶话会】第二期:聊聊 CKB 钱包和 Nervos DAO 全流程

CKB.DEV 茶话会第二期:聊聊 CKB 钱包和 Nervos DAO 全流程 为了鼓励更多优秀的开发者和研究人员参与到 CKB 的开发和生态建设中去,我们希望组织一系列 CKB Developer Seminar(CKB.DEV 茶话...

NervosCommunity
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部