一致性哈希算法的介绍

本文参考资源:

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

相关推荐

  • leetcode108-将有序数组转换为二叉搜索树

    原题 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数…

    算法 2020年1月18日
    080
  • leetcode450-删除二叉搜索树中的节点

    原题 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一…

    2020年1月16日
    080
  • 程序员面试金典17.16-按摩师

    原题(来源Leetcode) 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,…

    算法 2020年3月24日
    0630
  • leetcode1111-有效括号的嵌套深度

    原题 有效括号字符串 仅由 "(" 和 ")" 构成,并符合下述几个条件之一: 空字符串 连接,可以记作 AB(A 与 B 连接),其中 A 和 B 都是有效括号字符串 嵌套,可以…

    算法 2020年4月1日
    090
  • 海量数据算法-BitMap介绍和实现

    作为一个有素质的程序员,在面试中(不是) 难免会遇到海量数据相关的问题,之前有注意过java.util下面有一个BitSet数据结构,但不是很明白是做什么用的。今天就来研究一下它背…

    算法 2020年2月27日
    03350
  • leetcode118-杨辉三角

    原题 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]…

    2019年11月15日
    0100
  • leetcode189-旋转数组

    原题 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4…

    算法 2019年11月22日
    040
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01220
  • 蓝桥杯试题-翻硬币

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写…

    算法 2020年3月1日
    0140
  • 剑指offer59-队列的最大值

    原题(来源Leetcode) 请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度…

    算法 2020年3月7日
    0130

发表回复

登录后才能评论