关于java:微信红包业务为什么采用轮询算法

2次阅读

共计 19101 个字符，预计需要花费 48 分钟才能阅读完成。

目录

  • 前言
  • 根本的负载算法
  • 平滑加权轮询算法
  • 一致性哈希算法
  • 最小沉闷数算法
  • 最优响应算法
  • 总结

前言

负载平衡这个概念，简直在所有反对高可用的技术栈中都存在，例如微服务、分库分表、各大中间件（MQ、Redis、MyCat、Nginx、ES）等，也包含云计算、云调度、大数据中也是煊赫一时的词汇。

负载平衡策略次要分为动态与动静两大类：

  • 动态调度算法： 指配置后只会根据配置好的策略进行申请散发的算法。
  • 动静调度算法： 指配置后会依据线上状况（网络 /CPU 负载 / 磁盘 IO 等）来散发申请。

但负载平衡算法数量并不少，本篇次要对于一些罕用且高效的负载策略进行分析。

根本的负载算法

如果聊到最根本的负载平衡算法，那么置信大家多少都有理解，例如：轮询、随机、权重等这类算法。特点就在于实现简略，先来疾速过一遍根本的算法实现。

| 轮询算法

轮询算法是最为简略、也最为常见的算法，也是大多数集群状况下的默认调度算法，这种算法会依照配置的服务器列表，依照程序顺次散发申请，所有服务器都散发一遍后，又会回到第一台服务器循环该步骤。

Java 代码实现如下：

// 服务类：次要用于保留配置的所有节点
public class Servers {

// 模仿配置的集群节点
public static List<String> SERVERS = Arrays.asList(
"44.120.110.001:8080",
"44.120.110.002:8081",
"44.120.110.003:8082",
"44.120.110.004:8083",
"44.120.110.005:8084"
);
}

// 轮询策略类：实现根本的轮询算法
public class RoundRobin{
// 用于记录以后申请的序列号
private static AtomicInteger requestIndex = new AtomicInteger(0);

// 从集群节点中选取一个节点解决申请
public static String getServer(){
// 用申请序列号取余集群节点数量，求得本次解决申请的节点下标
int index = requestIndex.get() % Servers.SERVERS.size();
// 从服务器列表中获取具体的节点 IP 地址信息
String server = Servers.SERVERS.get(index);
// 自增一次申请序列号，不便下个申请计算
requestIndex.incrementAndGet();
// 返回获取到的服务器 IP 地址
return server;
}
}

// 测试类：测试轮询算法
public class Test{public static void main(String[] args){
// 应用 for 循环简略模仿 10 个客户端申请
for (int i = 1; i <= 10; i++){System.out.println("第"+ i + "个申请：" + RoundRobin.getServer());
}
}
}

/****** 输入后果 *******/
第 1 个申请：44.120.110.001:8080
第 2 个申请：44.120.110.002:8081
第 3 个申请：44.120.110.003:8082
第 4 个申请：44.120.110.004:8083
第 5 个申请：44.120.110.005:8084
第 6 个申请：44.120.110.001:8080
第 7 个申请：44.120.110.002:8081
第 8 个申请：44.120.110.003:8082
第 9 个申请：44.120.110.004:8083
第 10 个申请：44.120.110.005:8084

上述案例中，整个算法的实现尤为简略，就是通过一个原子计数器记录以后申请的序列号，而后间接通过 % 集群中的服务器节点总数，最终失去一个具体的下标值，再通过这个下标值，从服务器 IP 列表中获取一个具体的 IP 地址。

轮询算法的劣势：

  • 算法实现简略，申请散发效率够高。
  • 可能将所有申请均摊到集群中的每个节点上。
  • 易于前期弹性伸缩，业务增长时能够拓展节点，业务萎靡时能够缩减节点。

轮询算法的劣势：

  • 对于不同配置的服务器无奈正当关照，无奈将高配置的服务器性能施展进去。
  • 因为申请散发时，是基于申请序列号来实现的，所以无奈保障同一客户端的申请都是由同一节点解决的，因而须要通过 session 记录状态时，无奈确保其一致性。

轮询算法的利用场景：

  • 集群中所有节点硬件配置都是雷同的状况。
  • 只读不写，无需放弃状态的情景。

| 随机算法

随机算法的实现也非常简单，也就是当客户端申请到来时，每次都会从已配置的服务器列表中随机抽取一个节点解决。

实现如下：

// 随机策略类：随机抽取集群中的一个节点解决申请
public class Random {
// 随机数产生器，用于产生随机因子
static java.util.Random random = new java.util.Random();

public static String getServer(){
// 从已配置的服务器列表中，随机抽取一个节点解决申请
return Servers.SERVERS.get(random.nextInt(Servers.SERVERS.size()));
}
}

上述该算法的实现，十分明了，通过 java.util 包中自带的 Random 随机数产生器，从服务器列表中随机抽取一个节点解决申请，该算法的后果也不测试了，大家预计一眼就能看明确。

随机算法的劣势：集体看来该算法独自应用的意义并不大，个别会配合上面要讲的权重策略协同应用。

随机算法的劣势：

  • 无奈正当地将申请均摊到每台服务器上。
  • 因为解决申请的指标服务器不明确，因而也无奈满足需要记录状态的申请。
  • 可能在肯定水平上施展出高配置的机器性能，但充斥不确定因素。

| 权重算法

权重算法是建设在其余根底算法之上推出的一种概念，权重算法并不能独自配置，因为权重算法无奈做到申请散发的调度，所以个别权重会配合其余根底算法联合应用。

如：轮询权重算法、随机权重算法等，这样能够让之前的两种根底调度算法更为“人性化”一些。

权重算法是指对于集群中的每个节点调配一个权重值，权重值越高，该节点被散发的申请数也会越多，反之同理。

这样做的益处非常显著，也就是可能充分考虑机器的硬件配置，从而调配不同权重值，做到“能者多劳”。

那如何实现呢，先来看看随机权重的实现：

public class Servers{
// 在之前是 Servers 类中再退出一个权重服务列表
public static Map<String, Integer> WEIGHT_SERVERS = new LinkedHashMap<>();
static {
// 配置集群的所有节点信息及权重值
WEIGHT_SERVERS.put("44.120.110.001:8080",17);
WEIGHT_SERVERS.put("44.120.110.002:8081",11);
WEIGHT_SERVERS.put("44.120.110.003:8082",30);
}
}

// 随机权重算法
public class Randomweight {
// 初始化随机数生产器
static java.util.Random random = new java.util.Random();

public static String getServer(){
// 计算总权重值
int weightTotal = 0;
for (Integer weight : Servers.WEIGHT_SERVERS.values()) {weightTotal += weight;}

// 从总权重的范畴内随机生成一个索引
int index = random.nextInt(weightTotal);
System.out.println(index);

// 遍历整个权重集群的节点列表，抉择节点解决申请
String targetServer = "";
for (String server : Servers.WEIGHT_SERVERS.keySet()) {
// 获取每个节点的权重值
Integer weight = Servers.WEIGHT_SERVERS.get(server);
// 如果权重值大于产生的随机数，则代表此次随机调配应该落入该节点
if (weight > index){
// 间接返回对应的节点去解决本次申请并终止循环
targetServer = server;
break;
}
// 如果以后节点的权重值小于随机索引，则用随机索引减去以后节点的权重值，// 持续循环权重列表，与其余的权重值进行比照，// 最终该申请总会落入到某个 IP 的权重值范畴内
index = index - weight;
}
// 返回选中的指标节点
return targetServer;
}

public static void main(String[] args){
// 利用 for 循环模仿 10 个客户端申请测试
for (int i = 1; i <= 10; i++){System.out.println("第"+ i + "个申请：" + getServer());
}
}
}

/******** 运行后果 ********/
第 1 个申请：44.120.110.003:8082
第 2 个申请：44.120.110.001:8080
第 3 个申请：44.120.110.003:8082
第 4 个申请：44.120.110.003:8082
第 5 个申请：44.120.110.003:8082
第 6 个申请：44.120.110.003:8082
第 7 个申请：44.120.110.003:8082
第 8 个申请：44.120.110.001:8080
第 9 个申请：44.120.110.001:8080
第 10 个申请：44.120.110.002:8081

下面这个算法比照之前的根本实现，可能稍微有些简单难懂，咱们先上个图：

仔细观看上图后，逻辑应该会清晰很多，大体捋一下思路：

  • 先求和所有的权重值，再随机生成一个总权重之内的索引。
  • 遍历之前配置的服务器列表，用随机索引与每个节点的权重值进行判断。如果小于，则代表以后申请应该落入目前这个节点；如果大于，则代表随机索引超出了目前节点的权重范畴，则减去以后权重，持续与其余节点判断。
  • 最终随机出的索引总会落入到一个节点的权重范畴内，最初返回对应的节点 IP。

这样一剖析下来，估摸着各位小伙伴应该都了解了，接着再来看看轮询权重算法的实现：

// 轮询权重算法
public class RoundRobinweight {private static AtomicInteger requestCount = new AtomicInteger(0);

public static String getServer(){
int weightTotal = 0;
for (Integer weight : Servers.WEIGHT_SERVERS.values()) {weightTotal += weight;}

String targetServer = "";
int index = requestCount.get() % weightTotal;
requestCount.incrementAndGet();

for (String server : Servers.WEIGHT_SERVERS.keySet()) {Integer weight = Servers.WEIGHT_SERVERS.get(server);
if (weight > index){
targetServer = server;
break;
}
index = index - weight;
}
return targetServer;
}

public static void main(String[] args){for (int i = 1; i <= 10; i++){System.out.println("第"+ i + "个申请：" + getServer());
}
}
}

/******** 运行后果 *********/
第 1 个申请：44.120.110.001:8080
第 2 个申请：44.120.110.001:8080
第 3 个申请：44.120.110.001:8080
第 4 个申请：44.120.110.001:8080
第 5 个申请：44.120.110.001:8080
第 6 个申请：44.120.110.001:8080
第 7 个申请：44.120.110.001:8080
第 8 个申请：44.120.110.001:8080
第 9 个申请：44.120.110.001:8080
第 10 个申请：44.120.110.001:8080

察看上述中的案例，此刻会发现出端倪，代码实现过程雷同，但此刻的输入后果，居然全副申请都被散发到了 44.120.110.001:8080 这个节点，这是为什么呢？

因为此时是通过申请序列号去进行判断的，所以最终成果会成为：

  • 前 17 个申请会交给 44.120.110.001:8080 节点。
  • 后续 11 个申请会交给 44.120.110.002:8081 节点。
  • 最初 30 个申请会交给 44.120.110.003:8082 节点。
  • 而后继续反复该过程 …..

此时仿佛离咱们预期的负载成果产生了偏离，如果采纳这种计划去实现轮询权重算法，最终会将一个集群变为单点服务，这显然并不是期待中的成果，因而须要一种新的形式去实现，那么又该如何去做呢？

此时须要牵扯到一种申请调度的高级算法：平滑加权轮询算法。

平滑加权轮询算法

平滑轮询加权算法的实质就是为了解决之前实现形式中所存在的问题，可能将申请平均的依照权重值散发到每台机器。

这种算法设计的十分奇妙，实现过程也尤为乏味，咱们一起来看看：

// 权重服务器的配置类
public class Servers {public static Map<String, Integer> WEIGHT_SERVERS = new LinkedHashMap<>();
static {
// 权重值设置的稍微小一点，不便后续了解算法
WEIGHT_SERVERS.put("44.120.110.001:8080",3);
WEIGHT_SERVERS.put("44.120.110.002:8081",2);
WEIGHT_SERVERS.put("44.120.110.003:8082",1);
}
}

// 权重类
public class Weight {
// 节点信息
private String server;
// 节点权重值
private Integer weight;
// 动静权重值
private Integer currentWeight;

// 构造方法
public Weight() {}
public Weight(String server, Integer weight, Integer currentWeight) {
this.server = server;
this.weight = weight;
this.currentWeight = currentWeight;
}

// 封装办法
public String getServer() {return server;}
public void setServer(String server) {this.server = server;}
public Integer getWeight() {return weight;}
public void setWeight(Integer weight) {this.weight = weight;}
public Integer getCurrentWeight() {return this.currentWeight;}
public void setCurrentWeight(Integer currentWeight) {this.currentWeight = currentWeight;}
}

public class RoundRobinWeight {
// 初始化存储每个节点的权重容器
private static Map<String,Weight> weightMap = new HashMap<>();

// 计算总权重值，只须要计算一次，因而放在动态代码块中执行
private static int weightTotal = 0;
static {sumWeightTotal();
}

// 求和总权重值，后续动静伸缩节点时，再次调用该办法即可。public static void sumWeightTotal(){for (Integer weight : Servers.WEIGHT_SERVERS.values()) {weightTotal += weight;}
}

// 获取解决本次申请的具体服务器 IP
public static String getServer(){
// 判断权重容器中是否有节点信息
if (weightMap.isEmpty()){
// 如果没有则将配置的权重服务器列表挨个载入容器
Servers.WEIGHT_SERVERS.forEach((servers, weight) -> {
// 初始化时，每个节点的动静权重值都为 0
weightMap.put(servers, new Weight(servers, weight, 0));
});
}

// 每次申请时，更改动静权重值
for (Weight weight : weightMap.values()) {weight.setCurrentWeight(weight.getCurrentWeight()
+ weight.getWeight());
}

// 判断权重容器中最大的动静权重值
Weight maxCurrentWeight = null;
for (Weight weight : weightMap.values()) {if (maxCurrentWeight == null || weight.getCurrentWeight()
> maxCurrentWeight.getCurrentWeight()){maxCurrentWeight = weight;}
}

// 最初用最大的动静权重值减去所有节点的总权重值
maxCurrentWeight.setCurrentWeight(maxCurrentWeight.getCurrentWeight()
- weightTotal);

// 返回最大的动静权重值对应的节点 IP
return maxCurrentWeight.getServer();}

public static void main(String[] args){
// 应用 for 循环模仿 6 次申请
for (int i = 1; i <= 6; i++){System.out.println("第"+ i + "个申请：" + getServer());
}
}
}

/******** 输入后果 ********/
第 1 个申请：44.120.110.001:8080
第 2 个申请：44.120.110.002:8081
第 3 个申请：44.120.110.001:8080
第 4 个申请：44.120.110.003:8082
第 5 个申请：44.120.110.002:8081
第 6 个申请：44.120.110.001:8080

先看后果，比照之前的实现形式而言，该算法在散发申请时，的确平均了很多很多。

而且申请散发的数量与咱们配置的权重值也凑巧相符合：

  • 44.120.110.001:8080：3 次
  • 44.120.110.002:8081：2 次
  • 44.120.110.003:8082：1 次

这是不是很神奇？如何做到的呢，接下来简略聊一下该算法的核心思想。

在之前的权重算法中，服务器列表中只有两个值：服务器 IP、对应的权重值，而在以后这种算法中，须要再引入一个动静权重值的概念。

所以咱们再上述案例中，将服务器的列表形象成了一个 Weight 类，在该类中除开本来的 servers、weight 之外，多增加了一个字段 currentWeight，用于记录每个节点的动静权重（该值是变动的）。

在该算法中，会先计算已配置的权重值总和，而后第一次申请，会初始化权重容器 weightMap，将每个配置的节点都封装成一个 Weight 对象，并将其动静权重值初始化为 0。

如下：

  • Weight(“server”:”44.120.110.001:8080″,”weight”:3,”currentWeight”:0)
  • Weight(“server”:”44.120.110.002:8081″,”weight”:2,”currentWeight”:0)
  • Weight(“server”:”44.120.110.003:8082″,”weight”:1,”currentWeight”:0)

OK，至此筹备工作就绪，接下来是算法的外围过程，次要分为三步：

  • 用本来的动静权重值加一次每个节点的动态权重值，计算出新的动静权重值。
  • 遍历权重容器，找出动静权重值最大的节点，将其作为解决本次申请的节点。
  • 用最大的动静权重值减去已配置的动态权重值总和，为一下轮散发做筹备。

联合上述的算法过程和后面给出的案例，把整个过程摊开分析一次：

上表中列出了六次申请的处理过程，整个过程到最初，动静权重值又会回归初始值：0,0,0，而后开启新的一轮计算，周而复始之，分外的神奇 ^_^。

平滑加权轮询算法也是利用最为宽泛的轮询算法，在 Dubbo、Robbin、Nginx、Zookeeper 等一些集群环境中，当你配置了权重时，默认采纳的就是该算法作为申请散发的策略。

一致性哈希算法

其实平滑加权轮询算法对于申请散发而言，是一种比拟优良的策略了，不过后面剖析的所有策略，都存在一个致命问题：不能确保同一客户端的所有申请都散发在同一台服务器解决，因而无奈实现有状态的申请。

好比最简略的登录性能，客户端发送申请登录胜利，而后将其登录的状态保留在 session 中，后果客户端的第二次申请被散发到了另外一台机器。

因为第二台服务器 session 中没有相干的登录信息，因而会要求客户端从新登录，这显然造成的用户体验感是极差的，那么对于这种问题又该如何解决呢？

次要有两种计划：

  • 采纳内部中间件存储 session，例如 Redis，而后从 Redis 中获取登录状态。
  • 采纳非凡的申请散发策略，确保同一客户端的所有申请都会去到同一台机器上解决。

一致性哈希算法就是一种可能可能确保同一客户端的所有申请都会被散发到同一台机器的策略，不过一致性哈希算法依旧会存在问题，就是当集群中某个节点下线，或者集群呈现拓展时，那么也会影响最终散发的指标机器。

所以个别一致性哈希算法并不能 100% 解决 session 一致性的问题，因而该算法个别很少用于网关层的申请散发，更多的场景是利用在分布式缓存等状况，接下来一起来看看。

| 通过其余散发算法实现缓存

在解说一致性哈希算法之前，大家先来简略了解一下一致性哈希算法的产生背景。

先思考一个问题：假如目前单台缓存服务器无奈承当内部的拜访压力，此刻会如何去做呢？

答案是减少新的缓存服务器节点，拓展出一个集群对外提供服务。

好的，那问题又来了，当初缓存服务器是一个集群环境，此刻来了一个申请后该落入哪个节点呢？

假如采纳轮询策略，那么写入 xxx 缓存信息的申请被散发到了第一个节点，客户端读取 xxx 时，申请又被散发到了第三个节点上，那么显然是读不到之前的缓存。

而且最要害的是，个别的轮询策略都是须要基于集群的节点数量进行申请散发的，因而集群中的节点一旦呈现伸缩，最终会导致所有缓存内容全副生效。

就拿最根本的取模轮询来说，本来集群是 3 个节点，所以是基于取模 3 去散发申请，后果有台节点宕机了，成为了取模 2，那最初整个缓存零碎散发申请齐全乱套 …..

如果采纳随机策略 …..，更不靠谱 …..

因而在这种需要背景下，赫赫有名的一致性哈希算法问世了，一致性哈希算法其实也应用的取模形式，只是，方才形容的取模轮询法是对服务器的数量进行取模，而一致性哈希算法是对 2^32 取模，什么意思呢？咱们一点点来讲。

| 一致性哈希外围 - 哈希环

实现一致性哈希算法的外围构造在于哈希环，后面讲到过一致性哈希是基于 2^32 做取模。

那么首先能够将二的三十二次方设想成一个圆，这个圆总共由 2^32 个点组成，如下：

圆环的正上方第一个点代表 0，0 右侧的点依照 1、2、3、4…. 的程序依此类推，直到 2^32-1，也就是说 0 左侧的第一个点代表着 2^32-1。

最终这个在逻辑上由 2^32 个点组成的圆，被称为哈希环。

联合之前的缓存案例，假如有四台缓存服务器 A、B、C、D，而后再通过每台服务器的 IP 哈希值取模 2^32，最终必然会失去一个 2^32 范畴之内的整数，这个数在哈希环上定然也对应着一个点。

那么每台服务器的 IP 就能够映射到哈希环上，如下：

到此时，服务器曾经和哈希环建设起了分割，那么此时当客户端发送申请时，又能够通过雷同的计算形式，将客户端须要操作的缓存 Key 进行雷同的哈希取模，而后同样将其映射到哈希环上。

例如写入一条缓存 name= 竹子，如下：

那么此时该缓存纠结要落入到哪台服务器呢？答案是 B，为什么？因为在哈希环构造中，沿着顺时针方向走，遇到的第一台服务器是 B，所以最终会落到 B 服务器上。

当然，如果一致性哈希算法被用于申请散发，那么就以用户的 IP 作为哈希取模的条件，这样就能确保同一个客户端的所有申请都会被散发到同一台服务器。

一致性哈希算法中，就利用哈希环构造 + 哈希取模判断每个申请该落入的服务器，因为服务器 IP、客户端 IP 或缓存的 Key 都是雷同的，所以在服务器数量不变的状况，雷同的哈希条件进行哈希取模，最终计算出来的值永远都是雷同的。

而后再通过计算出的值，在哈希环构造上进行顺时针查找，可能定位到的服务器也是雷同的，所以雷同属性的申请永远会落入到同一服务器。

| 哈希环的映射偏移问题

通过上述剖析后，如同发现一致性哈希算法没啥大故障，但上述中属于“现实状态”：

可偏偏现实很饱满，事实却很骨感，理论映射服务器 IP 的过程中，可能会呈现如下状况：

因为服务器 IP 哈希取模后，无奈确保哈希失去的数字可能均匀分布，因而就有可能造成如上状况，所有的服务器 IP 都被映射在“一块儿”，最终导致 A 服务器承载了 90% 以上的拜访压力。

| 映射偏移造成的宕机连锁反应

接上述，如果服务器 IP 映射在哈希环上呈现偏移，在大流量的冲击下，这种状况很容易导致整个集群崩塌，首先是 A 扛不住并发冲击，宕机下线，紧接着流量交给 B，B 也扛不住，接着宕机，而后 C…..

因而哈希环映射偏移问题可能会造成的一系列连锁反应，所以在一致性哈希算法中，为了确保整个集群的健壮性，提出了一种虚构节点的概念来解决此问题。

虚构节点其实实质上就是实在服务器节点的复制品，虚构节点映射的 IP 都是指向于实在服务器的。

就相似平时 .EXE 软件的快捷方式，当初为 QQ 创立了一个快捷方式，而后拷贝到了十个不同的目录下，但实质上这十个快捷方式指向的启动文件都是雷同 exe 程序。

哈希环中的虚构节点也同理，如下：

从上图中能够看出，A、B、C、D 四台服务器别离都映射出了一个虚构节点，引入虚构节点后会显著感觉进去，本来 A 服务器须要承载 90% 以上的流量，但此刻映射出的虚构节点大大加重了 A 的压力，将流量均摊到了集群中的每个节点。

在一致性哈希算法的理论利用场景中，绝非只映射一个虚构节点，往往会为一个实在节点映射数十个虚构节点，以便于减小哈希环偏移所带来的影响。

同时，虚构节点的数量越多，申请在散发时也能更平均的散布，哈希环最终构造如下：

| Java 实现一致性哈希算法

讲了这么多，那么一致性哈希算法到底如何实现呢？接下来一起看看：

public class Servers {
public static List<String> SERVERS = Arrays.asList(
"44.120.110.001:8080",
"44.120.110.002:8081",
"44.120.110.003:8082",
"44.120.110.004:8083",
"44.120.110.005:8084"
);
}

public class ConsistentHash {
// 应用有序的红黑树结构，用于实现哈希环构造
private static TreeMap<Integer,String> virtualNodes = new TreeMap<>();
// 每个实在节点的虚构节点数量
private static final int VIRTUAL_NODES = 160;

static {
// 对每个实在节点增加虚构节点，虚构节点会依据哈希算法进行散列
for (String serverIP : Servers.SERVERS) {
// 将实在节点的 IP 映射到哈希环上
virtualNodes.put(getHashCode(serverIP), serverIP);
// 依据设定的虚构节点数量进行虚构节点映射
for (int i = 0; i < VIRTUAL_NODES; i++){
// 计算出一个虚构节点的哈希值（只有不同即可）int hash = getHashCode(serverIP + i);
// 将虚构节点增加到哈希环构造上
virtualNodes.put(hash, serverIP);
}
}
}

public static String getServer(String IP){int hashCode = getHashCode(IP);
// 失去大于该 Hash 值的子红黑树
SortedMap<Integer, String> sortedMap = virtualNodes.tailMap(hashCode);
// 失去该树的第一个元素，也就是最小的元素
Integer treeNodeKey = sortedMap.firstKey();
// 如果没有大于该元素的子树了，则取整棵树的第一个元素，相当于取哈希环中的最小元素
if (sortedMap == null)
treeNodeKey = virtualNodes.firstKey();
// 返回对应的虚构节点名称
return virtualNodes.get(treeNodeKey);
}

// 哈希办法：用于计算一个 IP 的哈希值
public static int getHashCode(String IP){
final int p = 1904390101;
int hash = (int)1901102097L;
for (int i = 0; i < IP.length(); i++)
hash = (hash ^ IP.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;

// 如果算进去的值为正数则取其绝对值
if (hash < 0)
hash = Math.abs(hash);
return hash;
}

public static void main(String[] args){
// 用 for 循环模仿五个不同的 IP 拜访
for (int i = 1; i <= 5; i++){System.out.println("第"+ i + "个申请：" + getServer("192.168.12.13"+i));
}
System.out.println("-----------------------------");
// 用 for 循环模仿三个雷同的 IP 拜访
for (int i = 1; i <= 3; i++){System.out.println("第"+ i + "个申请：" + getServer("192.168.12.131"));
}
}
}

/******** 输入后果 *******/
第 1 个申请：44.120.110.002:8081
第 2 个申请：44.120.110.003:8082
第 3 个申请：44.120.110.004:8083
第 4 个申请：44.120.110.003:8082
第 5 个申请：44.120.110.004:8083
-----------------------------
第 1 个申请：44.120.110.002:8081
第 2 个申请：44.120.110.002:8081
第 3 个申请：44.120.110.002:8081

上述便是 Java 实现一致性哈希算法的全过程，其实并不难理解，外面用到了 TreeMap 实现了哈希环构造，并且指定了每个服务器节点的虚构节点数量，同时实现了一个简略的哈希办法，用于计算入参的哈希值。

算法过程如下：

  • 启动时先依据指定的数量，映射对应的虚构节点数量在哈希环上。
  • 通过计算客户端哈希值，而后在哈希环上获得大于该值的节点，而后返回对应的 IP。因为哈希环是取顺时针方向的第一个节点作为解决申请的指标服务器，所以获取大于该哈希值的节点中的第一个节点即可。
  • 如果哈希环中没有大于客户端哈希值的节点，那么则将这些客户端的申请散发到整个 Map 上的第一台服务器，从此实现哈希闭环。

一致性哈希算法因为其个性，因而个别多被用于分布式缓存中的集群分片，尤其是 MemCache 的缓存分片，就是采纳一致性哈希算法实现的。

而 Redis 本身推出的 RedisCluster 分片集群中，也借用了一致性哈希算法的思维，不过进行了改版实现，外部采纳 CRC16+HashSolt 实现了缓存分片，但核心思想也是雷同的。

当然，文中给出的算法过程都是较为简单的实现，如若想要参考残缺的实现，能够参考：

  • Dubbo 的 com.alibaba.dubbo.rpc.cluster.loadbalance 包
  • 或参考 SpringCloudRibbon 的 com.netflix.loadbalancer 包下的实现

最小沉闷数算法

上述剖析的根本算法、平滑轮询加权、一致性哈希等算法都属于动态算法，也就是说这些算法配置后，并不会依据线上的理论运行状况进行调整，只会依据已配置的规定进行申请散发。

最小沉闷数算法则会依据线上的理论状况进行散发，可能灵便的检测出集群中各个节点的状态，可能主动寻找并调用活跃度最低的节点解决申请。

Java 实现如下：

// 节点类：用于封装集群中的每个节点
public class Server {
private String IP;
private AtomicInteger active;
// private Integer weight;

public Server(){}
public Server(String IP,int active) {
this.IP = IP;
// 将内部传递的沉闷数作为默认沉闷数
this.active = new AtomicInteger(active);
}

public String getIP() {
// 每散发一个申请时自增一次沉闷数
active.incrementAndGet();
return IP;
}

public AtomicInteger getActive() {return active;}
}

// 集群类：用于模仿集群节点列表
public class Servers {
// 活跃度衰减器
public static void attenuator(){new Thread(()->{
// 遍历集群中的所有节点
for (Server server : Servers.SERVERS) {
// 如果活跃度不为 0
if (server.getActive().get() != 0){
// 则自减一个活跃度
server.getActive().getAndDecrement();
}
}
try {
// 每隔 2 秒中衰减一次活跃度
Thread.sleep(2000);
} catch (InterruptedException e) {e.printStackTrace();
}
}).start();}

// 模仿的集群节点信息，沉闷数最开始默认为 0
public static List<Server> SERVERS = Arrays.asList(new Server("44.120.110.001:8080",0),
new Server("44.120.110.002:8081",0),
new Server("44.120.110.003:8082",0)
);
}

// 最小沉闷数算法实现类
public class LeastActive {public static String getServer(){
// 初始化最小沉闷数和最小沉闷数的节点
int leastActive = Integer.MAX_VALUE;
Server leastServer = new Server();
// 遍历集群中的所有节点
for (Server server : Servers.SERVERS) {
// 找出沉闷数最小的节点
if (leastActive > server.getActive().get()){leastActive = server.getActive().get();
leastServer = server;
}
}

// 返回沉闷数最小的节点 IP
return leastServer.getIP();}

public static void main(String[] args){Servers.attenuator();
for (int i = 1; i <= 10; i++){System.out.println("第"+ i + "个申请：" + getServer());
}
}
}

/******** 运行后果 *********/
第 1 个申请：44.120.110.001:8080
第 2 个申请：44.120.110.002:8081
第 3 个申请：44.120.110.003:8082
第 4 个申请：44.120.110.001:8080
第 5 个申请：44.120.110.002:8081
第 6 个申请：44.120.110.003:8082
第 7 个申请：44.120.110.001:8080
第 8 个申请：44.120.110.002:8081
第 9 个申请：44.120.110.003:8082
第 10 个申请：44.120.110.001:8080

察看如上案例的运行后果，仿佛后果如同是轮询的成果呀？的确是的，这是因为在最开始，所有节点的沉闷数都为 0，三个节点的沉闷数都雷同。

所以默认会先取集群中的第一个沉闷数为 0 的节点解决申请，第一个节点的沉闷数会变成 1，第二次申请时最小沉闷数也为 0，而后取第二个节点解决申请，依此类推 ……

在线上环境下，不会呈现轮询的成果，因为每台服务器随着运行工夫的增长，沉闷数必然会不同，因而该算法总会取沉闷数最小的节点提供服务。

当然，上述案例中实现的最小沉闷数，是比拟繁难的版本，对于欠缺的实现能够参考 Dubbo 框架中的 com.alibaba.dubbo.rpc.cluster.loadbalance.LeastActiveLoadBalance 类，其中也实现了权重机制。

简略论述一下其中的原理实现：

  • 先从注册核心中拉取所有的服务实例，而后找出沉闷数最小的节点。
  • 如果只有一个，那么则间接返回对应的实例节点解决本次申请。
  • 如果存在多个，则依据每个节点配置的权重值来决定本次解决申请的具体节点。
  • 如果权重值不同，优先选取权重值最大的实例，作为解决本次申请的节点。
  • 如果存在雷同的最大权重值，那么则通过随机的形式抉择一个节点提供服务。

当然，因为须要对每个节点去实现沉闷数监听，所以在 Dubbo 框架中，想要配置最小沉闷数策略，那么须要首先启用 ActiveLimitFilter 记录每个节点的沉闷数。

或者也能够参考 Ribbon 框架 com.netflix.loadbalancer 包上面的 BestAvailableRule 最小沉闷数算法实现类。

从最小沉闷数算法个性不难得悉，该算法带来的劣势极为显著，永远都能选取节点列表中最闲暇的那台服务器解决申请，从而防止某些负载过高的节点，还仍旧承当须要承当新的流量拜访，造成更大的压力。

最优响应算法

与后面剖析的最小沉闷数算法一样，最优响应算法也是一种动静算法，但它比最小沉闷数算法更加智能，因为最小沉闷数算法中，如果一台节点存在故障，导致它本身解决的申请数比拟少，那么它会蒙受最大的拜访压力，这显然是并不合理的。

最小沉闷数算法就相似于平时的搬砖工作，谁事件做的起码谁留下来加班，在失常状况下，这种算法都可能找到“摸鱼”最厉害的员工留下来加班。

但如果有一天，某个员工因为身材出问题了，导致本人做的工作量比拟少，但依照这种算法的逻辑，依旧会断定为该员工明天最闲，所以留下来加班。

从上述这个案例中，大家稍微可能感触进去最小沉闷数算法的不合理性。

而最优响应算法则更加智能，该算法在开始前，会对服务列表中的各节点收回一个探测申请（例如 Ping 或心跳包检测），而后依据各节点的响应工夫来决定由哪台服务器解决客户端申请，该算法能较好依据节点列表中每台机器的以后运行状态散发申请。

Java 实现如下：

public class Servers {
// 模仿的集群节点信息，沉闷数最开始默认为 0
public static List<Server> SERVERS = Arrays.asList(new Server("44.120.110.001:8080"),
new Server("44.120.110.002:8081"),
new Server("44.120.110.003:8082")
);
}

public class Server {
private String IP;

public Server(){}
public Server(String IP) {this.IP = IP;}
public String getIP() {return IP;}
public void setIP(String IP){this.IP = IP;}

public String ping(){
// 生成一个 1000~3000 之间的随机数
int random = ThreadLocalRandom.current().nextInt(1000, 2000);
try {
// 随机休眠一段时间，模仿不同的响应速度
Thread.sleep(random);
} catch (InterruptedException e) {e.printStackTrace();
}
// 最初返回本身的 IP
return this.IP;
}
}

public class ResponseTime {
// 创立一个定长的线程池，用于去执行 ping 工作
static ExecutorService pingServerPool = 
Executors.newFixedThreadPool(Servers.SERVERS.size());

public static String getServer() throws InterruptedException {
// 创立一个 CompletableFuture 用于拼接工作
CompletableFuture cfAnyOf;
// 创立一个接管后果返回的 server 节点对象
final Server resultServer = new Server();
// 依据集群节点数量初始化一个异步工作数组
CompletableFuture[] cfs = new CompletableFuture[Servers.SERVERS.size()];

// 遍历整个服务器列表，为每个节点创立一个 ping 工作
for (Server server : Servers.SERVERS) {
// 获取以后节点在集群列表中的下标
int index = Servers.SERVERS.indexOf(server);
// 为每个节点创立一个 ping 工作，并交给 pingServerPool 线程池执行
CompletableFuture<String> cf =
CompletableFuture.supplyAsync(server::ping,pingServerPool);
// 将创立好的异步工作退出数组中
cfs[index] = cf;
}

// 将创立好的多个 Ping 工作组合成一个聚合工作并执行
cfAnyOf = CompletableFuture.anyOf(cfs);

// 监听执行实现后的回调，谁先执行实现则返回谁
cfAnyOf.thenAccept(resultIP -> {System.out.println("最先响应检测申请的节点为：" + resultIP);
resultServer.setIP((String) resultIP);
});
// 阻塞主线程一段时间，避免 CompletableFuture 退出
Thread.sleep(3000);

// 返回最先响应检测申请（ping）的节点作为本次解决客户端申请的节点
return resultServer.getIP();}

public static void main(String[] args) throws InterruptedException {for (int i = 1; i <= 5; i++){System.out.println("第"+ i + "个申请：" + getServer());
}
}
}

/****** 运行后果：******/
最先响应检测申请的节点为：44.120.110.002:8081
第 1 个申请：44.120.110.002:8081
最先响应检测申请的节点为：44.120.110.002:8081
第 2 个申请：44.120.110.002:8081
最先响应检测申请的节点为：44.120.110.003:8082
第 3 个申请：44.120.110.003:8082
最先响应检测申请的节点为：44.120.110.003:8080
第 4 个申请：44.120.110.001:8080
最先响应检测申请的节点为：44.120.110.002:8081
第 5 个申请：44.120.110.002:8081

在该案例中，其实现过程比照之前的算法稍微简单一些，首先在 Server 实例类中定义了一个 Ping() 办法，该办法中应用随机数 + 线程休眠的形式简略模仿了一下节点的不同的响应速度。

而后在算法实现类中，利用 CompletableFuture 别离对每一个节点都创立了对应的 Ping 工作，而后同时执行，又通过 thenAccept() 回调办法监听了执行后果，谁最先响应，则取其作为解决本次申请的节点。

这个算法的实现过程中，惟一难了解的就是 CompletableFuture，它是 JDK8 中推出的一种异步工作。

这里只是举例实现，所以通过 CompletableFuture 实现了检测申请，但理论过程中如果要抉择这种算法，那么基于 Netty 会更为适合。

从上述案例的运行后果中也能够得悉：最优响应算法无论在何种状况下，都能从集群中选取性能最好的节点对外服务，Nginx 中也反对配置这种算法，但须要先装置对应的 nginx-upstream-fair 模块。

总结

在本文中，对于比拟罕用的申请散发算法进行了分析及手写实际，其中提到了较为传统的动态调度算法：轮询、随机、加权、一致性哈希等，也谈到了一些较为智能的动静算法：最小沉闷数、最优响应等。

但须要牢记的一点是：并非越智能的算法越好，越是并发高、流量大的场景下，反而选用最根本的算法更适合，例如微信的红包业务，就是采纳最根本的轮询算法进行集群调度。

那这又是为何呢？因为越智能的调度算法，进行节点抉择时的开销会更大，如果你对于文中给出的调度算法实现都一一运行过，那么大家会显著感知出：越到前面的算法，散发申请的速度越慢。

因而在面临微小拜访压力的情景中，抉择最简略的算法反而带来的收益更高，但前提是须要集群中所有的节点硬件配置都统一，所有节点调配的资源都雷同，轮询算法则是最佳的调度算法。

正文完
java
发表至： java
2022-07-12
 0
Halo-v10-正式版发布一款惊艳的动态博客系统
寻找两个数之和算法解密
关于java:Java数组这一篇文章就真够了
LeetCode-206反转链表-Reverse-Linked-List

站内搜索

-「」