一致性哈希算法的介绍

本文参考资源:

一致性Hash算法详解 - 知乎

一致性哈希算法概述

分布式系统中,常常听到一种算法叫一致性哈希算法,而最常用的领域相信大家也有所耳闻——负载均衡。负载均衡有许多算法,例如轮询、随机、加权轮询/随机、最小连接数。但是假如我们需要会话粘滞(session sticky)呢?

什么是会话粘滞:给同一个客户提供服务的服务器永远是同一台,就能实现每次连接都是上次的session。例如我去银行办手续,谈到一半发现自己身份证忘带了,需要回家拿身份证,那么我拿完身份证回来之后希望还是同一个业务员来接待我。

一致性哈希算法就保证了分布式系统中每次给同一台客户机服务的主机都是同一台,而分辨是否是同一台客户机的依据就是客户机的IP。那么如何根据这个IP来选取同一台服务器来服务呢,如果使用哈希算法获取同一个哈希值,则这个哈希值的生成必须不能和服务器的个数相关,否则一旦服务器增加或者减少,最终生成的哈希值都会变化。

一致性哈希算法原理

环形hash空间

按照常用的hash算法来将对应的key哈希到一个具有2^32次方个节点的空间中,即0 ~ (2^32)-1的数字空间中。现在我们可以将这些数字头尾相连,想象成一个闭合的环形。

一致性哈希算法的介绍

映射服务器节点

将各个服务器进行一个哈希,具体可以选择服务器的ip或唯一主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置。假设我们将四台服务器使用ip地址哈希后在环空间的位置如下:

一致性哈希算法的介绍

映射数据

现在我们将objectA、objectB、objectC、objectD四个对象(代表客户机的IP)通过特定的Hash函数计算出对应的key值,然后散列到Hash环上,然后从数据所在位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。

一致性哈希算法的介绍

服务器的删除与添加

如果此时NodeC宕机了,此时Object A、B、D不会受到影响,只有Object C会重新分配到Node D上面去,而其他数据对象不会发生变化。

这时可能就有问题了,不是说能保证每次给同一个客户服务的都是同一台服务器吗?那现在把C重新分配给Node D是怎么回事?

我们只能尽可能地保证每次给同一个客户服务的都是同一台服务器,但是Node C宕机了也没办法啊?而且影响到的只有之前分配给Node C的客户机,对于A、B、D都没有影响到。

如果在环境中新增一台服务器Node X,通过hash算法将Node X映射到环中,通过按顺时针迁移的规则,那么Object C被迁移到了Node X中,其它对象还保持这原有的存储位置。

虚拟节点

前面部分讲述到的都是节点较多和节点分布较为均衡的情况,当服务器节点比较少的时候,会出现一个问题,就是此时必然造成大量数据集中到一个节点上面,极少数数据集中到另外的节点上面。

一致性哈希算法的介绍

为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以先确定每个物理节点关联的虚拟节点数量,然后在ip或者主机名后面增加编号。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

一致性哈希算法的介绍

同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。每个物理节点关联的虚拟节点数量就根据具体的生产环境情况在确定。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e4%b8%80%e8%87%b4%e6%80%a7%e5%93%88%e5%b8%8c%e7%ae%97%e6%b3%95%e7%9a%84%e4%bb%8b%e7%bb%8d/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月4日 19:55
下一篇 2020年4月5日

相关推荐

  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0150
  • leetcode94-二叉树的中序遍历

    原题 给定一个二叉树,返回它的 中序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2019年12月12日
    01120
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0710
  • leetcode373-查找和最小的K对数字

    原题 给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。 找到和最…

    算法 2020年2月13日
    0160
  • 蓝桥杯试题-黑色星期五

    原题 资源限制 时间限制:1.0s 内存限制:512.0MB 问题描述  有些西方人比较迷信,如果某个月的13号正好是星期五,他们就会觉得不太吉利,用古人的说法,就是“诸事不宜”。…

    算法 2020年2月28日
    0130
  • leetcode402-移掉K位数字

    原题 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 …

    算法 2020年1月29日
    0100
  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0150
  • 用一个栈实现另一个栈的排序

    原题(来源牛客网) 一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序? 解法 …

    算法 2020年4月20日
    02110
  • 剑指offer51-数组中的逆序对

    原题(来源Leetcode) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7…

    算法 2020年4月24日
    0410

发表回复

登录后才能评论