本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云
常见的负载均衡算法,大概有 7 种。它们分别是:完全随机算法、加权随机算法、完全轮询算法、加权轮询算法、平滑加权轮询算法、哈希算法、最小压力算法。本文结合我个人的理解,给大家从头来写出 6 种负载均衡算法。
负载均衡算法,虽然你平时可能用不到,但是面试中可能会被问到。比如,面试 Dubbo,就可能问问你了解不了解 Dubbo 的负载均衡算法。还有 Nginx 等,这些都和并发编程存在着一些关联。了解它们,能让我们避免很多坑。
下面先看第一种,完全随机算法。随机就是没有规律的,随便从负载中获得一台,通常我相信大家第一时间会想到随机数。完全随机算法就和随机数有些关系。看下面的实现代码:
public static List<String> list = new ArrayList<String>() { { add("www.xttblog.com"); add("公众号业余草"); add("业余草微信号:xmtxtt"); } }; static Random random = new Random(); public static String go() { int number = random.nextInt(list.size()); return list.get(number);//随机获取服务器 } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go()); } }
代码非常的简单,我就不在详细的解释。下面再看加权随机算法。
随机算法有一个缺点就是,所有的服务器被访问到的概率都是相同的。如果我某台服务器性能比较好,需要随机的权重高一些,那该怎么办?加权随机算法就是解决这个问题的。代码如下:
public static HashMap<String, Integer> map = new HashMap<String, Integer>() { { put("www.xttblog.com", 2); put("公众号业余草", 7); put("业余草微信号:xmtxtt", 1); } }; static Random random = new Random(); public static String go() { List<String> ipList = new ArrayList<String>(); for (Map.Entry<String, Integer> item : map.entrySet()) { for (int i = 0; i < item.getValue(); i++) { ipList.add(item.getKey()); } } int allWeight = map.values().stream().mapToInt(a -> a).sum(); int number = random.nextInt(allWeight); return ipList.get(number); } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go()); } }
代码也非常的简单。就是根据每个服务器的权重,添加对应权重数量的服务器到集合中。然后产生随机算法,获取服务器列表。构建一个服务器的 List,如果 www.xttblog.com 服务器的权重是 2,那么往 List 里面 Add 两次 www.xttblog.com 服务器,如果“公众号业余草”服务器的权重是 7,那么我往 List 里面 Add 7次“公众号业余草”服务器,以此类推,然后我再生成一个随机数,随机数的上限就是权重的总和,也就是 List 的 Size。这样权重越大的,被选中的概率当然越高。权重大的服务器获得的概率大一些,权重小的服务器获得的概率小一些。
这个算法,虽然解决了权重问题。但是,在我的权重设置过大的时候,比如上万,上千万。那么你的 List 就会被撑爆。所以,还有另外一种写法。代码如下:
public static HashMap<String, Integer> map = new HashMap<String, Integer>() { { put("www.xttblog.com", 2); put("公众号业余草", 7); put("业余草微信号:xmtxtt", 1); } }; static Random random = new Random(); public static String go1() { int allWeight = map.values().stream().mapToInt(a -> a).sum(); int number = random.nextInt(allWeight); for (Map.Entry<String, Integer> item : map.entrySet()) { if (item.getValue() >= number) { return item.getKey(); } number -= item.getValue(); } return ""; } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go1()); } }
算法原理:如果 www.xttblog.com 服务器的权重是 2,“公众号业余草”服务器的权重是 7,“业余草微信号:xmtxtt”服务器的权重是 1。
- 如果我生成的随机数是 1,那么落到 www.xttblog.com 服务器,因为 1<=2(www.xttblog.com 服务器的权重)
- 如果我生成的随机数是 5,那么落到”公众号业余草”服务器,因为 5>2(大于 www.xttblog.com 服务器的权重),5-2( www.xttblog.com 服务器的权重)= 3,3<7(“公众号业余草”服务器的权重)
- 如果我生成的随机数是 10,那么落到“业余草微信号:xmtxtt”服务器,因为 10>2(www.xttblog.com 服务器的权重),10-2(www.xttblog.com服务器的权重)=8,8>7(“公众号业余草”服务器的权重),8-7(“公众号业余草”服务器的权重)=1,1<=1(“业余草微信号:xmtxtt”服务器的权重)。
随机算法有一个缺点就是,有时候有些机器可能很长一段时间都随机不到。所以,就又有了轮询算法。
完全轮询算法,非常的简单,从头到尾,到尾了后,再从头开始。代码如下:
public static List<String> list = new ArrayList<String>() { { add("www.xttblog.com"); add("公众号业余草"); add("业余草微信号:xmtxtt"); } }; static int index; public static String go() { if (index == list.size()) { index = 0; } return list.get(index++); } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go()); } }
但这里还涉及到一个权重问题。因此就又有了加权轮询算法。代码如下:
public static HashMap<String, Integer> map = new HashMap<String, Integer>() { { put("www.xttblog.com", 2); put("公众号业余草", 7); put("业余草微信号:xmtxtt", 1); } }; static Random random = new Random(); static int index; public static String go() { int allWeight = map.values().stream().mapToInt(a -> a).sum(); int number = (index++) % allWeight; for (Map.Entry<String, Integer> item : map.entrySet()) { if (item.getValue() > number) { return item.getKey(); } number -= item.getValue(); } return ""; } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go()); } }
加权轮询,看起来并没什么问题,但是在实际中,可能某个服务器权重大,长时间执行。遇到耗时大的请求,压力非常的大。存在着不合理性。因此就诞生了一种叫平滑加权轮询算法。
代码稍微多一点,先看一个权重类。
public class SmoothWeightServer { private int weight; private int currentWeight; private String ip; public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public int getCurrentWeight() { return currentWeight; } public void setCurrentWeight(int currentWeight) { this.currentWeight = currentWeight; } public String getIp() { return ip; } public void setIp(String ip) { this.ip = ip; } public SmoothWeightServer(int weight, int currentWeight, String ip) { this.weight = weight; this.currentWeight = currentWeight; this.ip = ip; } }
核心代码如下:
public static HashMap<String, SmoothWeightServer> serverMap = new HashMap<String, SmoothWeightServer>() { { put("www.xttblog.com", new SmoothWeightServer(5,5,"www.xttblog.com")); put("公众号业余草", new SmoothWeightServer(1,1,"公众号业余草")); put("业余草微信号:xmtxtt", new SmoothWeightServer(1,1,"业余草微信号:xmtxtt")); } }; public static String go() { SmoothWeightServer maxWeightServer = null; int allWeight = serverMap.values().stream().mapToInt(SmoothWeightServer::getWeight).sum(); for (Map.Entry<String, SmoothWeightServer> item : serverMap.entrySet()) { SmoothWeightServer currentServer = item.getValue(); if (maxWeightServer == null || currentServer.getCurrentWeight() > maxWeightServer.getCurrentWeight()) { maxWeightServer = currentServer; } } assert maxWeightServer != null; maxWeightServer.setCurrentWeight(maxWeightServer.getCurrentWeight() - allWeight); for (Map.Entry<String, SmoothWeightServer> item : serverMap.entrySet()) { SmoothWeightServer currentServer = item.getValue(); currentServer.setCurrentWeight(currentServer.getCurrentWeight() + currentServer.getWeight()); } return maxWeightServer.getIp(); } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go()); } }
算法的原理是:每个服务器都有两个权重变量。weight,配置文件中指定的该服务器的权重,这个值是固定不变的;current_weight,服务器目前的权重。一开始为 0,之后会动态调整。每次当请求到来,选取服务器时,会遍历数组中所有服务器。对于每个服务器,让它的 current_weight 增加它的 weight;同时累加所有服务器的 weight,并保存为 total。遍历完所有服务器之后,如果该服务器的 current_weight 是最大的,就选择这个服务器处理本次请求。最后把该服务器的 current_weight 减去 total。
上面的算法虽好,但是在集群环境下,我想让同一个用户的访问,分流到固定的一台机器上,怎么办?所以就又有了哈希负载均衡算法。
public static List<String> list = new ArrayList<String>() { { add("www.xttblog.com"); add("公众号业余草"); add("业余草微信号:xmtxtt"); } }; private static String go(String client) { int nodeCount = 20; TreeMap<Integer, String> treeMap = new TreeMap(); for (String s : list) { for (int i = 0; i < nodeCount; i++) treeMap.put((s + "—业余草---" + i).hashCode(), s); } int clientHash = client.hashCode(); SortedMap<Integer, String> subMap = treeMap.tailMap(clientHash); Integer firstHash; if (subMap.size() > 0) { firstHash = subMap.firstKey(); } else { firstHash = treeMap.firstKey(); } String s = treeMap.get(firstHash); return s; } public static void main(String[] args) { for (int i = 0; i < 15; i++) { System.out.println(go("用户来访问" + i)); } }
上面的 6 种负载均衡算法是非常常见的,很可能在面试中被问到。我这里只是实现,实际应用中还要结合各种设计模式。另外可能把几种算法组合起来用。
最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!
本文原文出处:业余草: » 手把手教你写出 6 种负载均衡算法