概念
分布式和集群
分布式和集群的概念非常容易混淆，分布式和集群是不一样的，分布式一定是集群，但是集群不一定是分布式
- 分布式：把一个系统拆分为多个子系统，每个子系统负责各自的那部分功能，独立部署，各司其职
- 集群：多个实例共同工作，最简单的集群是把一个应用复制多份部署
HASH算法
Hash算法应用场景
Hash算法在很多分布式集群产品中都有应用，比如分布式集群架构Redis、Hadoop、ElasticSearch、Mysql分库分表、nginx负载均衡等
Hash主要的应用场景主要有两个：
- 请求的负载均衡( 比如：nginx的ip_hash策略)
- Nginx的Ip_hash策略可以在客户端ip不变的情况下，将其发出的请求始终路由到同一个目标服务器上，实现会话粘滞，避免处理session共享问题
- 分布式存储
- 这种简单的取模hash算法存在很大的问题，以Nginx的ip_hash举例，当服务器数量发生变动的时候，整个客户端要重新取模，那么势必大部分的客户端不会路由到原来的服务器节点，这就造成了很多的问题，比如session会获取不到，在原有服务器的缓存也无法及时的更新和获取。
一致性Hash算法
一致性Hash算法是一种Hash算法，它能够在Hash输出空间发生变化时，引起最小的变动。当增加或者移除一台服务器时，对原有的服务器和用户之间的映射关系产生的影响最小。
好的一致性Hash顺发应该满足以下要求：
- 平衡性：这是Hash算法的最基本要求，是指哈希的结果均匀的分配在整个输出空间中。
- 单调性： 当数据节点变动时，对于相同的数据始终映射到相同的缓冲节点中或者新增加的缓冲节点中，避免无法找到原来的数据
- 稳定性：当出现节点坏掉或者热点访问而需要动态扩容时，尽量减少数据的移动。
一致性Hash算法原理
一致性Hash算法中最重要的是一个Hash环，该环形区域用数字0-2^32-1表示，沿顺时针方向值不断增大，0与2^32重合。依旧拿Nginx的负载均衡举例说明，我们将服务器进行Hash。可以使用服务器的编号或者ip作为输入，得出一个输出值，映射在输出空间的环形区域上。对于用户数据，同样进行Hash操作，映射在环形区域上。然后让该值沿着顺时针方向移动，遇到的第一个服务器就是它分配的服务器。这样能够尽最大程度的保证当扩容或者缩容的时候，客户端与服务端的联系没有发生改变，影响到的只是有变动的服务器周围的一些客户端，将影响降到了最低。
知乎-一致性Hash算法
一致性Hash算法缩容扩容分析
缩容： 当其中一个节点下线时，只会影响到原本依赖该节点的客户端，而不是对其他客户端产生影响。例如：本来用4台服务器(1、2、3、4)，进行Hash后散落在圆环上，此时我们也拥有四个客户端(A,B,C,D)，A落在1号服务器，B落在2号服务器，C落在3号服务器，D落在4号服务器上。当3号服务器下线时，并不会对A，B，D客户端产生影响，只有C客户端会按照顺时针找到4号服务器，而其他客户端没有任何影响。
扩容： 在原有节点不变的情况下，新增一个节点，那么只会对一小部分客户端从旧服务端迁移到新服务端。哪一部分的数据需要进行迁移，取决于hash后顺时针顺延是否能碰到新服务节点。
虚拟节点
上述一致性Hash算法存在部分问题，当一致性Hash在服务器节点太少时，容易因为节点分布不均匀而造成数据倾斜问题,即客户端分配到服务端数量不均匀。
为了解决数据倾斜问题, 一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个Hash，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或者主机名的后面增加编号来实现。
例如：可以为每一台服务器计算三个虚拟节点，于是可以分别计算”节点1的ip#1”、”节点1的ip#2”、”节点1的ip#3”、”节点2的ip#1”、”节点2的ip#2”、”节点2的ip#3”的Hash值，于是形成了六个虚拟节点，当客户端被路由到虚拟节点的时候其实是被路由到该虚拟节点所对应的真实节点。
手写实现Hash算法
手写Hash算法分为三部分，普通Hash算法、一致性Hash算法、携带虚拟节点的一致性Hash算法。
普通Hash算法
普通Hash算法就是对服务器个数进行取模运算。
public class GeneralHash {
public static void main(String[] args) {
String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
int serverCount = 3;
for (String client : clients) {
int hash = Math.abs(client.hashCode());
int index = hash % serverCount;
System.out.println("客户端："+client+" 被路由到服务器编号为："+index);
}
}
}
|
一致性Hash算法(不包含虚拟节点)实现
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashNoVirtual {
public static void main(String[] args) {
String[] tomcatServers = new String[]{"123.111.0.0","123.101.3.1","111,20,35,2","123.98.26.3"};
SortedMap<Integer,String> hashServerMap = new TreeMap<>();
for (String tomcatServer : tomcatServers) {
int serverHash = Math.abs(tomcatServer.hashCode());
hashServerMap.put(serverHash,tomcatServer);
}
String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
for (String client : clients) {
int clientHash = Math.abs(client.hashCode());
SortedMap<Integer, String> tailMap = hashServerMap.tailMap(clientHash);
if(tailMap.isEmpty()){
Integer firstKey = hashServerMap.firstKey();
System.out.println("==========> 客户端："+client+" 被路由到服务器: "+ hashServerMap.get(firstKey));
}else {
Integer firstKey = tailMap.firstKey();
System.out.println("==========> 客户端："+client+" 被路由到服务器: "+ hashServerMap.get(firstKey));
}
}
}
}
|
一致性Hash算法(包含虚拟节点)实现
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashWithVirtual {
public static void main(String[] args) {
String[] tomcatServers = new String[]{"123.111.0.0","123.101.3.1","111,20,35,2","123.98.26.3"};
SortedMap<Integer,String> hashServerMap = new TreeMap<>();
int virtaulCount = 3;
for (String tomcatServer : tomcatServers) {
int serverHash = Math.abs(tomcatServer.hashCode());
hashServerMap.put(serverHash,tomcatServer);
for(int i=0;i<virtaulCount;i++){
int virtualHash = Math.abs((tomcatServer+"#"+i).hashCode());
hashServerMap.put(virtualHash,"---由虚拟节点+"+i+" 映射过来的请求 "+tomcatServer);
}
}
String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
for (String client : clients) {
int clientHash = Math.abs(client.hashCode());
SortedMap<Integer, String> tailMap = hashServerMap.tailMap(clientHash);
if(tailMap.isEmpty()){
Integer firstKey = hashServerMap.firstKey();
System.out.println("==========> 客户端："+client+" 被路由到服务器: "+ hashServerMap.get(firstKey));
}else {
Integer firstKey = tailMap.firstKey();
System.out.println("==========> 客户端："+client+" 被路由到服务器: "+ hashServerMap.get(firstKey));
}
}
}
}
|
Nginx一致性Hash负载均衡策略
ngx_http_upstream_consistent_hash 模块是一个负载均衡器，使用一个内部一致性hash算法来选择合适的后端节点。
该模块可以根据配置参数采取不同的方式将请求均匀映射到后端机器
- consistent_hash $remote_addr : 可以根据客户端ip映射
- consistent_hash $request_uri : 根据客户端请求的uri映射
- consistent_hash $args : 根据客户端携带的参数进行映射
示例如下：# 负载均衡的配置
upstream server{
consistent_hash $request_uri;
server 127.0.0.1:8080;
server 127.0.0.1:8082;
}
|
- github下载nginx一致性hash负载均衡模块
- 将下载的压缩包上传到nginx服务器，并解压
- 我们已经编译安装过nginx，此时进入当时nginx的源码目录，执行如下命令
./configure --add-module=/模块安装路径
make
make install
|
- 配置文件中进行配置后,nginx就可以使用一致性hash模块进行路由了。
