Hash一致算法_一致性hash是如何做数据迁移

Hash一致算法_一致性hash是如何做数据迁移概述这里存在一种场景,当一个服务由多个服务器组共同提供时,key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目),这里乍一看没什么问题,但是当服务器数目发送增加或减少时,分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效迁移,如果后端key对应的是有状态的存储数据,那么毫无疑问,这种做法将导致服务器间大量的数据迁移,从而照成

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

概述

这里存在一种场景, 当一个缓存服务由多个服务器组共同提供时, key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目), 这里乍一看没什么问题, 但是当服务器数目发送增加或减少时, 分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效迁移,如果后端key对应的是有状态的存储数据,那么毫无疑问,这种做法将导致服务器间大量的数据迁移,从而照成服务的不稳定. 为了解决类问题,一致性hash算法应运而生.


1. 一致性hash算法特点

在分布式缓存中, 一个好的hash算法应该要满足以下几个条件:
  • 均衡性(Balance)
       均衡性主要指,通过算法分配, 集群中各节点应该要尽可能均衡.

  • 单调性(Monotonicity)
       单调性主要指当集群发生变化时, 已经分配到老节点的key, 尽可能的任然分配到之前节点,以防止大量数据迁移, 这里一般的hash取模就很难满足这点,而一致性hash算法能够将发生迁移的key数量控制在较低的水平.

  • 分散性(Spread)
        分散性主要针对同一个key, 当在不同客户端操作时,可能存在客户端获取到的缓存集群的数量不一致,从而导致将key映射到不同节点的问题,这会引发数据的不一致性.好的hash算法应该要尽可能避免分散性.

  • 负载(Load)
     负载主要是针对一个缓存而言, 同一缓存有可能会被用户映射到不同的key上,从而导致该缓存的状态不一致.


从原理来看,一致性hash算法针对以上问题均有一个合理的解决.


2. 一致性hash详解
一致性hash的核心思想为将key作hash运算, 并按一定规律取整得出0-2^32-1之间的值, 环的大小为2^32,key计算出来的整数值则为key在hash环上的位置,如何将一个key,映射到一个节点, 这里分为两步.

第一步, 将服务的key按该hash算法计算,得到在服务在一致性hash环上的位置.

第二步, 将缓存的key,用同样的方法计算出hash环上的位置,按顺时针方向,找到第一个大于等于该hash环位置的服务key,从而得到该key需要分配的服务器。
Hash一致算法_一致性hash是如何做数据迁移


如图, 各key根据hash算法分配到各节点,当某一节点失效实效时, 如NODE 2失败, 则NODE 2 上的key将分配到hash环上相邻的节点,而其他key所在位置不变。
Hash一致算法_一致性hash是如何做数据迁移



虚拟节点提高均衡性

如上图可看到, 由于节点只有3个,存在某些节点所在位置周围有大量的hash点从而导致分配到这些节点到key要比其他节点多的多,这样会导致集群中各节点负载不均衡,为解决这个问题,引入虚拟节点, 即一个实节点对应多个虚拟节点。缓存的key作映射时,先找到对应的虚拟节点,再对应到实节点。如下图所示, 每个节点虚拟出两个虚拟节点,从而提高均衡性。
Hash一致算法_一致性hash是如何做数据迁移



3. 一致性hash算法与其他算法对比

对于集群中缓存类数据key的节点分配问题,有这几种解决方法,简单的hash取模,槽映射,一致性hash。
  • hash取模
     对于hash取模,均衡性没有什么问题,但是如果集群中新增一个节点时,将会有N/(N+1)的数据实效,当N值越大,失效率越高。这显然是不可接受的。
  • 槽映射
      其思想是将key值做一定运算(如crc16, crc32,hash), 获得一个整数值,再将该值与固定的槽数取模(slots), 每个节点处理固定的slots。获取key所在的节点时,先要计算出key与槽的对应关系,再通过槽与节点的对应关系找到节点,这里每次新增节点时,只需要迁移一定槽对应的key即可,而不迁移的槽点key值则不会实效,这种方式将实效率降低到了 N/(N+1)。不过这种方式有个缺点就是所有节点都需要知道槽与节点对应关系,如果client端不保存槽与节点的对应关系的话,它需要实现重定向的逻辑。
  • 一致性hash
     一致性hash如上文所言,其新增一个节点的实效率仅为N/(N+1),通过一致性hash最大程度的降低了实效率。同时相比于槽映射的方式,不需要引人槽来做中间对应,最大限度的简化了实现。

4. 基于golang的一致性hash算法实现

这里讲采用golang实现一致性hash,考虑到实际使用场景中,存在服务节点之间机器配置可能不一样,因此提供了基于节点权重进行虚拟节点再分配的逻辑,从而尽可能让权重高的节点多承担一些key,而权重低的节点少承担一些key,当然这里权重的计算也涉及到较多东西,代码见:

5. 总结
本文分析了一致性性hash的原理,并与其它的分布式集群分配算法进行了对比,从分布式缓存的角度来说,两大出名的分布存储系统redis, memcached分别采用了槽映射,及一致性hash来实现,由于采用的算法不同,集群中节点变更时所触发的一系列动作也不尽相同,各有各的考虑。








版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188688.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • ie兼容性视图怎么设置_电脑找不到兼容性视图

    ie兼容性视图怎么设置_电脑找不到兼容性视图许多用户在升级操作系统之后,里面自带的ie浏览器也会跟着一起升级,然而有些网站可能需要使用低版本的ie浏览器才可以打开,该怎么办呢,其实我们只要设置ie兼容性视图模式就可以了,不过很多用户可能还不知道ie兼容性视图设置在哪,为此,小编这就告诉大家ie兼容性视图的详细设置方法。步骤阅读工具/原料IE浏览器方法/步骤11、在Windows10系统桌面,我们依次点击“开始/Windows附件/Inter…

  • 做电商网站服务器在哪里,电商网站服务器如何选择「建议收藏」

    做电商网站服务器在哪里,电商网站服务器如何选择「建议收藏」网络上的电商人数越来越多,那么现在我们做电商还有的做嘛!其实,还是有机会的,这里面有两个关键点,一是所提供的产品及服务、另一个是别人访问我们网站时的感觉,也就相关到电子商务网站网站服务器。使用电子商务网站网站服务器前提,做好网络市场环境分析网络市场的贸易方式有多种,B2B、B2C、B2G、C2C、O2O等,每位卖方都是借助这些方式使用网络工具在网络上进行产品的宣传推广,展现自家产品,提供给所需的…

  • leetcode-103二叉树的锯齿形层序遍历「建议收藏」

    leetcode-103二叉树的锯齿形层序遍历「建议收藏」给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。例如:给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回锯齿形层序遍历如下:[ [3], [20,9], [15,7]]/** * Definition for a binary tree node. * struct TreeNode { * int

  • WinRAR去广告(简体中文版)[通俗易懂]

    WinRAR去广告(简体中文版)[通俗易懂]1.官网下载WinRAR:www.rarlab.com选择简体中文版-ChineseSimplified(32bit,64bit),根据自己需要选择32或64位2.安装并注册(1)直接安装即可(2)注册:新建一个txt文件,拷入一下文本保存,并将文件重命名为:rarreg.key,注意文件后缀为.key,并将文件拷到WinRAR安装路径下。…

  • navicat15永久激活码-激活码分享

    (navicat15永久激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~BI7JCUH1TG-eyJsaWNlbnNlSWQiOi…

  • linux apache2配置_虚拟主机开启ssl

    linux apache2配置_虚拟主机开启ssl测试环境*操作系统:Ubuntu5.10*测试机地址:10.39.6.59*测试机域名:*.firehare.com基本配置我们都知道,如果我们想在单台机器上设置多个域名或主机名时,我们就要用到基于名称的虚拟主机了。那么要如何进行设置呢?这就是本指南想解决的问题了。在Ubuntu的/etc/apache2/目录下有个Ap

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号