一致性 Hash 算法
分布式--特定场景解决方案
分布式：把一个系统拆分为多个子系统，每个子系统负责各自功能实现，独立部署，各司其职。体现的是对系统的拆分。
集群：体现的是多个实例共同工作，最简单/常见的集群即一个应用复制多份部署，实现高可用。
分布式一定是集群，但集群不一定是分布式（因为集群就是多个实例一起工作，分布式将一个系统拆分之后就是多个实例，所以分布式一定是集群，而集群并不一定是分布式，因为复制型的集群不是拆分而是复制）。
一致性 Hash 算法
Hash 算法常见应用场景
比如在安全加密领域MD5、SHA等加密算法，在数据存储和查找方面有 hash 表，Java中的hashcode等都应用到了 Hash 算法。
Hash 算法在很多分布式集群产品中都有应用，比如分布式集群架构 Redis、Hadoop、ElasticSearch，MySQL 分库分表，Nginx 负载均衡等。Hash 算法等使用主要场景分为两个：
-
请求的负载均衡（比如 Nginx 的 ip_hash 策略）。
Nginx 的 IP_hash 策略可以在客户端 IP 不变的情况下，将其发出的请求始终路由到同一个目标服务器上，实现会话粘滞，避免处理 session 共享问题。
如果没有 IP_hash 策略，又想实现会话粘滞，可以维护一个映射表，存储客户端 ip 或者 sessionid 与具体目标服务器的映射关系。缺点：1、在客户端很多的情况下，映射表非常大，浪费内存空间；2、客户端上下线、目标服务器上下线，都会导致重新维护映射表。
-
分布式存储。通过 Hash 算法将不同服务器的请求路由到不同的服务器，进而将数据存储到不同的服务器中。
为什么需要使用 Hash 算法
Hash 算法较多的应用在数据存储和查找领域，最经典的 Hash 表，其查询效率非常高，如果 Hash 算法设计的比较好的话，那么 Hash 表的数据查询时间复杂度可以接近于O(1)。
比如：判断一个结合中是否包含某个元素，例如集合数据：1、3、6、4、8、2、9、12、7 中是否包含数字 4 ，最普通的方法是循环遍历数组，逐个进行判断，或者使用二分查找（需要对元素进行排序）。
直接寻址法
首先创建一个数组，数组的长度根据集合中元素的最大值来确定，数组长度要大于等于集合中的最大值 +1 ，然后将数组中的数据根据下标进行存放入数组中，比如元素 1 存放到数组下标为 1 的位置，元素 3 存放在数组下标为 3 的位置，依次类推，如下图：
1.jpg
只需根据数组下标进行判断，当前位置是否有值即可。
优点：
查询速度快，只需一次查找即可确定。
缺点：
-
浪费内存空间。比如图中的 0、5、10、11 内存位置，并没有存放任何数据，但是需要预留内存空间。更夸张的是，如果集合中元素跨度很大，比如集合中增加元素 12306，其余都不变，那么数组长度将是 12307，数组中 13～12306 的下标位置都将浪费。
-
集合中的元素要求无重复，否则无法存放集合中所有元素。例如将集合元素修改为：1、3、6、4、8、2、9、12、7、4、2 ，那么数组长度变成了15，但是最大值还是 12 ，存放时，元素 2 和 4 要么被覆盖，要么无法存放。
除留余数法
数组的长度可以任意，集合中元素的存放位置通过对数组长度求模后对值来确定：存放位置 = 集合中元素值 % 数组长度 。
2.jpg
这种方式算是一种简单的 Hash 算法，也可以提高查询效率，但是会导致 Hash 冲突。即不同的元素求模之后存放的数组位置是相同的。
开放寻址法
开放寻址法.jpg
哈希冲突时向前或向后占用空闲位置，数据比较混乱，这种方式一般不会使用。而且，当数组的长度确定，且小于结合中数据元素个数时，无论是否发生 hash 冲突，都无法存放集合中所有元素。
拉链法
拉链法.jpg
为了解决在除留余数法中产生的 Hash 冲突问题，当有两个元素求模后存放在相同下标位置时， 通过链表结构，将不同元素存放在相同的下标位置。
使用拉链法之后，查询效率相比直接寻址法会稍有逊色，但是如果 Hash 算法设计的好的话，元素在数组中存放比较均匀，Hash 冲突机率比较低，其查询效率依然很高，且节省了内存空间。
普通 Hash 算法存在的问题
普通 hash 算法通过取模来定位请求的具体服务器地址，这种情况下，增减服务器数量，影响到 hash 结果，导致会话失效。
一致性 Hash 算法
一致性Hash算法.jpg
原理
-
首先将 0 ~ 2^32-1 按照顺指针方向放在一个圆环中，这个环称为 Hash 环。
-
假设当前集群中有4个服务器节点，分别是 node1、node2、node3、node4，根据这 4 个服务器节点的 IP (也可以是其他属性) 计算出一个 Hash 值，分别对应 Hash 环中的某个位置，这里假设 4 个服务器节点经过 Hash 算法之后分别对应 Hash 环中的1、2、3、4 的位置。
-
当请求到达时，再通过 Hash 算法，计算出当前请求在 Hash 环中对应的位置，根据对请求计算出的 Hash 值，顺时针查找最近的一个服务器节点，该节点就是处理当前请求的节点。比如：如果请求通过 Hash 算法之后，在 Hash 环中对应的位置落在 4～1 之间，那么处理当前请求的服务器节点就是 node1，如果请求通过 Hash 算法之后，在 Hash 环中对应的位置落在 1～2 之间，那么处理当前请求的服务器节点就是 node2，依次类推。
缩容
一致性Hash算法缩容.jpg
当有服务器下线时，比如 node3 节点下线，原来路由到 node3 的客户端，重新路由到了 node4，对于其他客户端没有影响，请求的迁移达到了最小，这样的算法对于分布式集群来说非常合适，避免了大量请求的迁移。
扩容
一致性Hash算法扩容.jpg
当新增一个服务器节点5之后，原来路由到 node3 的部分客户端路由到了新增服务器 node5 上，受影响的只有新增节点与其前一个节点之间的请求，其他请求也不会收到影响。请求的迁移达到了最小，这样的算法对于分布式集群来说非常合适，避免了大量请求的迁移。
每台服务器负责一部分客户端的请求，一致性 Hash 算法对于服务器节点的增减都只需要定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
虚拟节点方式
一致性Hash算法虚拟节点方式.jpg
对于一致性 Hash 算法，在服务器节点太少时，容易因为节点分布不均匀而导致数据倾斜问题。例如系统中只有两台服务器，节点2只能负责很小的一部分请求，大量的客户端请求落在了节点1上。
为了解决这种数据倾斜问题，一致性 Hash 算法引入了虚拟节点机制。即对每一个服务节点计算多个 Hash，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器 IP 或主机名后面增加编号来实现。比如，可以为每台服务器计算三个虚拟节点，于是可以分别计算“节点1的ip#1”、“节点1的ip#2”、“节点1的ip#3”、“节点2的ip#1”、“节点2的ip#2”、“节点2的ip#3”的 Hash 值，于是形成 6 个虚拟节点，当客户端被路由到虚拟节点的时候其实是被路由到该虚拟节点对应的真实节点。
Nginx 配置一致性 Hash 负载均衡策略
ngx_http_upstream_consistent_hash 模块是一个负载均衡器，使用一个内部一致性 Hash 算法来选择合适的后端节点， Nginx 默认并没有安装一致性 Hash 模块，需要自己手动安装。
该模块可以根据不同的配置参数采取不同的方式将请求映射到后端机器：
-
consistent_hash $remote_addr：可以根据客户端的 ip 映射
-
consistent_hash $request_uri：根据客户端请求的 uri 映射
-
consistent_hash $args：根据客户端携带的参数进行映射
安装一致性 Hash 负载均衡器
-
下载并上传至云服务器
下载地址：https://github.com/replay/ngx_http_consistent_hash
以压缩包的形式将其下载到本地，并通过 FTP 工具上传至云服务器，此处上传到服务器的 /soft/ 目录下。
-
在此之前已经编译并安装过 Nginx ，此时进入 Nginx 源码目录，执行一下命令进行安装：
# 进入 Nginx 源码目录
cd /soft/nginx-1.18.0
# 配置添加一致性 Hash 负载均衡器模块
./configure --add-module=/soft/ngx_http_consistent_hash-master # 配置
make # 编译
make install # 安装
此时，Nginx 一致性 Hash 负载均衡器已经安装完成。
使用 Nginx 一致性 Hash 负载均衡器
安装完成后，只需要在 nginx.conf 文件中添加如下配置即可使用一致性 Hash 负载均衡策略：
cd /usr/local/nginx/conf
vim nginx.conf
upstream testServer {
consistent_hash $request_uri;
server 127.0.0.1:8080;
server 127.0.0.1:8081;
}
关注公众号第一时间推送
