普通hash与一致性hash算法

青旅半醒 2022-12-20 02:13 190阅读 0赞

### 普通hash与一致性hash算法 ###

*  一、普通hash算法（求模）
 *  二、一致性hash算法
 *   *  1、什么是数据倾斜？
     *  2、nginx配置一致性hash

> hash算法是一类算法，不是某一个算法。

# 一、普通hash算法（求模） #

hash查找：相对于`顺序查找`和`二分查找`，查找速度快。  
对数据求模，根据余数确定存储下标，可能导致`hash冲突`，有两种方式解决：每个下标存放一个数组或者一个链表，hash查找的效率直接决定于hash算法

> 应用场景

分布式集群架构如`Redis、Hadoop、Elasticsearch、Mysql分库分表、Nginx负载均衡`。

请求负载均衡（nginx的ip\_hash,是处理session共享的一种方式）

对ip或sessionId计算hash值，对服务器数量取模，得到路由后的服务器编号。这样可以保证同一个客户端发送来的请求被路由到指定的服务器上。

redis负载均衡也是同样，先对key进行hash计算，将得到的结果作为目标服务器的id。

> 普通hash算法（线性结构）存在的问题

在服务器扩容、缩容时，导致服务器原来的客户端请求需要重新hash计算

# 二、一致性hash算法 #

普通hash算法的问题可以由一致性hash算法解决

`一致性hash算法（环形结构）`：服务器扩容/缩容后，只影响一部分请求，重新计算服务器节点hash值（客户端和服务器ip经过hash计算后都会落在一个hash环上，客户端请求会被分发到顺时针离他最近的服务器上）

以上可以得知，一致性hash算法对分布式集群来说是非常合适的，避免了服务器扩容和缩容后大量的请求迁移。

## 1、什么是数据倾斜？ ##

然而，环形结构有利有弊，分布式集群节点越多，请求越能够均匀分布到服务器上。如果只有两台服务器，就有可能会造成`数据倾斜`，即大量请求落在指定的一台服务器上，这时需要引入`虚拟节点`，一个服务器设置n个虚拟节点，这样hash环被虚拟节点均匀分割，请求也会均匀分配到服务器集群中。  
![hash环][hash]

## 2、nginx配置一致性hash ##

通过upstream中配置ip_hash;

由于处理服务器扩容缩容后会引发大量请求迁移问题，nginx负载均衡建议使用`一致性hash算法`来配置，使用该模块需要下载并安装到nginx中，  
1）下载

https://github.com/replay/ngx_http_consistent_hash

2）安装  
找到nginx的configure脚本执行以下命令行

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

3）修改upstream配置

upstream myServer {
    			#请求url
    			consistent_hash $request_uri;
    			#consistent_hash $remote_addr;请求ip
                server 127.0.0.1:8080;
                server 127.0.0.1:8081;
         }

[hash]: /images/20221120/4fdd22bb26284a628763a6170b01e021.png

发表评论取消回复

表情：

评论列表（有 0 条评论，190人围观）

还没有评论，来说两句吧...

相关阅读

相关普通hash与一致性hash算法

普通hash与一致性hash算法一、普通hash算法（求模）二、一致性hash算法 1、什么是数据倾斜？ 2、nginx配置一致

青旅半醒/ 2022年12月20日 02:13/ 0 赞/ 191 阅读

相关一致性HASH算法

用来解决分布式系统中，HASH节点发生变化对原有分配策略产生的影响，使对原有分配策略的影响是局部性的，达到实现动态扩充节点的目的。使用这种算法时，需要针对某一个节点的数据做局部

短命女/ 2022年09月28日 11:58/ 0 赞/ 223 阅读

相关一致性hash算法 - consistent hashing

一致性 hash 算法（ consistent hashing ）张亮 consistent hashing 算法早在 1997 年就在论文 [Consistent

约定不等于承诺〃/ 2022年09月17日 11:20/ 0 赞/ 210 阅读

相关一致性Hash算法

先从历史的角度来一步步分析，探讨一下到底什么是Hash一致性算法！一、Redis集群的使用我们在使用Redis的时候，为了保证Redis的高可用，提高Redis的读

喜欢ヅ旅行/ 2022年09月09日 04:35/ 0 赞/ 232 阅读

相关一致性hash算法 - consistent hashing

1、情景分析前一篇博文分析了[HashMap源码][HashMap]，HashMap在许多场景中作为存储数据的不二选择。但是否使用HashMap就能解决

冷不防/ 2022年08月26日 08:26/ 0 赞/ 25 阅读

相关一致性HASH算法

基本场景比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用

港控/mmm°/ 2022年07月13日 14:08/ 0 赞/ 227 阅读

相关一致性hash算法 - consistent hashing

本来转载于[http://blog.csdn.net/sparkliang/article/details/5279393][http_blog.csdn.net_sparkl

桃扇骨/ 2022年06月13日 14:39/ 0 赞/ 158 阅读

相关一致性Hash算法

一、Redis集群的使用我们在使用Redis的时候，为了保证Redis的高可用，提高Redis的读写性能，最简单的方式我们会做主从复制，组成Master-Master或者

墨蓝/ 2022年05月28日 00:39/ 0 赞/ 275 阅读

相关一致性hash算法

一致性hash 为Redis集群使用hash 或者分库使用hash 因此公式为hash(dataKey) % 4 = 2 ，可知直接定位到了第2号服务器 ![

青旅半醒/ 2022年04月22日 05:12/ 0 赞/ 280 阅读

相关 Hash和一致性Hash算法

Hash Hash无论是数据结构还是分布式缓存，都有应用。Hash更确切的说是hash函数，是一个集合的数据到另一个集合内数据的一个映射。被映射方在数学里面叫做原象，

柔情只为你懂/ 2021年09月25日 18:58/ 0 赞/ 445 阅读