一致性哈希算法的介绍

本文参考资源:

一致性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日

相关推荐

  • leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽…

    2020年1月24日
    0100
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。 示例1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例2: 输入…

    2020年2月25日
    0690
  • leetcode150-逆波兰表达式求值

    原题 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。 给定逆波兰…

    2019年12月12日
    090
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0390
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04540
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode1413-逐步求和得到正数的最小值

    原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组,并将 startValue 依次累加上 nums…

    算法 2020年6月21日
    02930
  • leetcode209-长度最小的子数组

    原题 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = …

    算法 2019年11月20日
    0160
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0120

发表回复

登录后才能评论