一致性Hash算法

Hash算法

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。

Hash算法在安全加密领域MD5、SHA等加密算法,数据存储和查找的Hash表等方面均有应用。Hash表的数据查询效率极高,时间复杂度达到O(1)。Hash表通常使用数组下标与数据进行对应的方式进行存储,查找时,通过数据计算出下标(通常是取模)得到下标,然后通过下标直接访问数据。当然,当数组空间有限时,不同的数据计算出相同的下标的情况必然发生,这种情况叫Hash冲突,而解决Hash冲突的常用方法有开放寻址法、拉链法(常用)。

如下图,1和6这两个数据通过对5取模,得到的下标都是1,发生了Hash冲突。

开放寻址法:1放进去了,6再来的时候,向前或者向后找空闲位置存放。但这种方法存在明显缺陷,即数组长度是一定的,当数组被用完时,发生Hash冲突后将无法解决。

拉链法:当发生Hash冲突时,以链表将冲突数据串起来。即数组元素存的一个链表,而不是一个简单数值了。发生Hash冲突时,只需要把新数据放到链表头即可。查找数据时,遍历链表。当然,当链表过长会影响查询性能。此时可以把链表转自平衡二叉查找树(如红黑树,Java8的ConcurrentHashMap 就是使用数组 + 链表 + 红黑树来实现的),这样一来,查询性能将从O(n)降低到 O(log(n))。

Hash算法应用场景

  • 安全加密

日常用户密码加密通常使用的都是 md5、sha等哈希函数,因为不可逆,而且微小的区别加密之后的结果差距很大,所以安全性更好。

  • 唯一标识

比如 URL 字段或者图片字段要求不能重复,这个时候就可以通过对相应字段值做 md5 处理,将数据统一为 32 位长度从数据库索引构建和查询角度效果更好,此外,还可以对文件之类的二进制数据做 md5 处理,作为唯一标识,这样判定重复文件的时候更快捷。

  • 数据校验

比如从网上下载的很多文件(尤其是P2P站点资源),都会包含一个 MD5 值,用于校验下载数据的完整性,避免数据在中途被劫持篡改。

  • 散列函数

  • 负载均衡

对于同一个客户端上的请求,尤其是已登录用户的请求,需要将其会话请求都路由到同一台机器,以保证数据的一致性,这可以借助哈希算法来实现,通过用户 ID 尾号对总机器数取模(取多少位可以根据机器数定),将结果值作为机器编号。

  • 分布式缓存

分布式缓存和其他机器或数据库的分布式不一样,因为每台机器存放的缓存数据不一致,每当缓存机器扩容时,需要对缓存存放机器进行重新索引((参考redis分片集群扩容hash槽重分配) ),这里应用到的也是哈希算法的思想。

普通Hash算法存在的问题

普通Hash算法应用在分布式环境中会存在比较大的问题,比如通过Hash算法将同一会话的客户端路由到相同的服务器上,实现会话保持。当服务器扩缩容时,客户端需要重新取服务器数量进行取模得到Hash索引,确定目标服务器,这时,这些客户端的会话会丢失。(当然,实际的会话保持通常会通过分布式缓存,如redis来实现)。如何将服务器的扩缩容的影响减到最小?这就是一致性Hash算法需要解决的问题。

一致性Hash算法

一致性Hash算法思路如下:

将0到2^32-1作为Hash环,即原本是对有限的服务器数量进行取模,现在是对2^32进行取模,这样取模结果范围更广了,也就是Hash环更大了。这样一来,生产中不可能会使用2^32这么多服务器,扩缩容对客户端的影响是很小的。客户端访问时,是将客户端IP地址对2^32取模,然后得出一个索引值,根据这个值,顺时针找最近的服务器节点,如下图

假设服务器3下线,原来路由到3的客户端重新路由到服务器4,这样一来,影响到的只是原来路由到服务器3的这部分客户端,这在分布式系统里非常有用,避免了大量请求迁移。

1)如前所述,每一台服务器负责一段,一致性Hash算法对于节点的增减都只需要重定位环空间的一小部分数据,具有较好的容错性和可扩展性。

但是一致性哈希算法在服务节点太少时,容易因为节点分布不均匀而造成数据倾斜问题。比方说按顺时针的情况下,服务节点1和2很近,1到2的区间的客户端由服务器2负责,然后剩下的大区间只能由1负责,这就是数据都倾斜到服务节点1上了。

2)为了解决这种数据倾斜问题,一致性哈希算法引入 了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。

具体做法可以在服务器IP或主机名的后面增加编号来实现。比如,可以为每台服务器计算三个虚拟节点,于是可以分别诸“节点1的IP#1”、“节点1的IP#2”、“节点1的IP#3”的哈希值,于是形成六个虚拟节点,当客户端被路由到虚拟节点的时候其实是被路由到该虚拟节点所对应的真实节点。

nginx配置一致性Hash负载均衡策略

ngx_http_upstream_consistent_hash模块是一个负载均衡器,通过一致性Hash算法来为客户端选择合适的后端节点。

该模块可以根据配置参数采取不同的方式将请求均匀映射到后面机器。

consistent_hash $remote_addr :根据客户端IP映射

consistent_hash $request_uri :根据客户端uri映射

consistent_hash $args :根据客户端携带的参数进行映射

ngx_http_upstream_consistent_hash是一个第三方模块,需要我们下载安装后使用

1,下载

https://github.com/replay/ngx_http_consistent_hash

2,编译nginx(进入nginx的源码目录)

./configure —add-module=/root/ngx_http_consistent_hash-master
make
make install

3,配置使用

upstream test_server_nodes {#ip_hash;consistent_hash $request_uri;server 192.168.43.71:7771;server 192.168.43.72:7772;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/208194.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MOS管的静电击穿问题

MOS管输入电阻很高,为什么一遇到静电就不行了? 静电击穿:由于静电的积累导致电压超过了原本MOS的绝缘能力,导致电流突然增大的现象。 MOS管基础知识了解: G极(gate)—栅极,不用说比较好认 S极(source)—源…

分享一个国内可用的免费GPT4-AI提问AI绘画网站工具

一、前言 ChatGPT GPT4.0,Midjourney绘画,相信对大家应该不感到陌生吧?简单来说,GPT-4技术比之前的GPT-3.5相对来说更加智能,会根据用户的要求生成多种内容甚至也可以和用户进行创作交流。 然而,GPT-4对普…

2017年五一杯数学建模A题公交车排班问题解题全过程文档及程序

2017年五一杯数学建模 A题 公交车排班问题 原题再现 随着徐州市经济的快速发展,公交车系统对于人们的出行扮演着越来越重要的角色。在公交车资源有限的情况下,合理的编排公交车的行车计划成为公交公司亟待解决的问题。以下给出公交车排班问题中的部分名…

vue+echarts实现依赖关系无向网络拓扑结图节点折叠展开策略

目录 引言 一、设计 1. 树状图(不方便呈现节点之间的关系,次要考虑) 2. 力引导依赖关系图 二、力引导关系图 三、如何实现节点的Open Or Fold 1. 设计逻辑 节点展开细节 节点收缩细节 代码实现 四、结果呈现 五、完整代码 引言 我…

重生奇迹MU再生原石

通过坎特鲁提炼之塔的NPC艾尔菲丝提炼成功就可以可获得再生宝石。 重生奇迹mu里的再生原石的用法: 1、打怪获得再生原石去提炼之塔(进入坎特鲁遗址的141188位置的传送台)。 2、找到(艾儿菲丝)把原石提炼成再生宝石。…

2016年五一杯数学建模C题二孩政策问题解题全过程文档及程序

2016年五一杯数学建模 C题 二孩政策问题 原题再现 多年来实施的严、紧计划生育政策对控制人口增长起到关键作用。在优生优育政策的指引下,我国人口质量显著提高,但也带来了不利影响,生育率偏低、男女比例失衡、人口老龄化情况严重等问题。2…

小程序如何进行一键修复

在使用小程序过程中,难免会遇到一些问题,比如程序崩溃、功能异常等等。这时,版本一键修复就显得尤为重要了。下面,我们就来介绍一下小程序如何进行版本一键修复。 一、什么是版本一键修复? 版本一键修复是指在小程序…

ELK---filebeat日志收集工具

elk---filebeat日志收集工具 filebeat是一个轻量级的日志收集工具,所使用的资源比logstash部署和启动时使用的资源小的多。 filebeat可以在非Java环境收集日志,它可以代替logstash在非Java环境上收集日志。 filebeat无法实现数据的过滤,一般…

Linux 调试工具:gdb

调试复习 调试可谓是 “贯穿” 了程序员的一生,调试的重要性,就不再赘述啦!如果你还不知道什么是调试,可以看看 Windows 系统的 Visual Studio 是如何调试的:➡️ visual stuudio 使用调试技巧 下载调试软件 gdb yu…

java学习part29线程通信

139-多线程-线程间的通信机制与生产者消费者案例_哔哩哔哩_bilibili 1.等待唤醒 类似于golang的channel, 1.1用法 类似于go的wait(), 1.sleep和wait的一个重大区别是,sleep不会让线程失去同步监视器,而wait会释放 2.wait必须tr…

半监督语义分割综述

paper link:https://arxiv.org/pdf/2302.09899.pdf 1. Introduction 图像分割是最古老、研究最广泛的计算机视觉 (CV) 问题之一。图像分割是指将图像划分为不同的非重叠区域,并将相应的标签分配给图像中的每个像素,最终获得ROI区域位置及其类…

【交换排序 简单选择排序 堆排序 归并排序】

文章目录 交换排序简单选择排序堆排序归并排序 交换排序 冒泡排序的算法分析: 冒泡排序最好的时间复杂度是O(n)冒泡排序最好的时间复杂度是O(n平方)冒泡排序平均时间复杂度为O(n的平方)冒泡排…

shareMouse 使用中遇到的问题

一、shareMouse 使用中遇到的问题 1、鼠标不能移动到另一个显示器 明明是两个显示器,但是 只显示一个,鼠标也不能移到另一个显示器上 后来, 设置了 wrap mouse pointer around display就好了,虽然还是显示一个显示器&#xff0c…

【傻瓜级JS-DLL-WINCC-PLC交互】1.C#用windows窗体控件创建.net控件

思路 JS-DLL-WINCC-PLC之间进行交互,思路,先用Visual Studio创建一个C#的DLL控件,然后这个控件里面嵌入浏览器组件,实现JS与DLL通信,然后DLL放入到WINCC里面的图形编辑器中,实现DLL与WINCC的通信。然后PLC与…

【多线程】-- 09 线程同步之三大不安全案例举例

多线程 6 线程同步 “多个线程操作同一个资源” 处理多线程问题时,多个线程访问同一个对象,并且某些线程还想修改这个对象,这时候就需要线程同步。线程同步其实就是一种等待机制,多个需要同时访问此对象的线程进入这个对象的等…

Java Throwable

如图展示了 Java 整个异常体系的关系。 Throwable 的 Java 异常体系的基类, 他的直接子类有 Error 和 Exception 2 个。 1 Error Error 表示的是由于系统错误, Java 虚拟机抛出的异常, 例如 Java 虚拟机崩溃, 内存不够等, 这种情况仅凭程序自身是无法处理的, 在程序中也不会…

【MATLAB】LMD分解+FFT+HHT组合算法

有意向获取代码,请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 LMDFFTHHT组合算法是一种基于局部均值分解(LMD)、快速傅里叶变换(FFT)和希尔伯特-黄变换(HHT)的组合算法。 LMD是…

计网Lesson6 - IP 地址分类管理

文章目录 1. I P IP IP 地址定义2. I P v 4 IPv4 IPv4 的表示方法2.1 I P v 4 IPv4 IPv4 的分类编址法2.2 I P v 4 IPv4 IPv4 的划分子网法2.2.1 如何划分子网2.2.2 如何确定子网的借位数2.2.3 总结2.2.4 题目练习 2.3 I P v 4 IPv4 IPv4 的无分类编址法 1. I P IP IP 地…

C++作业4

代码整理&#xff0c; 将学过的三种运算符重载&#xff0c;每个至少实现一个运算符的重载 代码&#xff1a; #include <iostream>using namespace std;class Stu {friend const Stu operator*(const Stu &L,const Stu &R);friend bool operator<(const Stu …

动态规划------方法汇总

核心&#xff1a; 状态定义 状态转移方程 启发思路&#xff08;两种情况&#xff09;&#xff1a;选 或 不选 / 选哪个 DP三步&#xff1a;先写回溯&#xff0c;时间复杂度 指数级别&#xff1b;递归的过程中会重复计算&#xff0c;要保存计算结果&#xff0c;递归搜索…