一篇有趣的负载均衡算法实现
文章已经收录在 Github.com/niumoo/JavaNotes ,更有 Java 程序员所需要掌握的核心知识,欢迎Star和指教。
欢迎关注我的公众号,文章每周更新。
负载平衡(Load balancing)是一种在多个计算机(网络、CPU、磁盘)之间均匀分配资源,以提高资源利用的技术。使用负载均衡可以最大化服务吞吐量,可能最小化响应时间,同时由于使用负载均衡时,会使用多个服务器节点代单点服务,也提高了服务的可用性。
负载均衡的实现可以软件可以硬件,硬件如大名鼎鼎的 F5 负载均衡设备,软件如 NGINX 中的负载均衡实现,又如 Springcloud Ribbon 组件中的负载均衡实现。
如果看到这里你还不知道负载均衡是干嘛的,那么只能放一张图了,毕竟没图说个啥。
负载均衡要做到在多次请求下,每台服务器被请求的次数大致相同。但是实际生产中,可能每台机器的性能不同,我们会希望性能好的机器承担的请求更多一些,这也是正常需求。
如果这样说下来你看不懂,那我就再举个例子好了,一排可爱的小熊(服务器)站好。
这时有人(用户)要过来打脸(请求访问)。
那么怎么样我们才能让这每一个可爱的小熊被打的次数大致相同呢?
又或者熊 4 比较胖,抗击打能力是别人的两倍,我们怎么提高熊 4 被打的次数也是别人的两倍呢?
又或者每次出手的力度不同,有重有轻,恰巧熊 4 总是承受这种大力度啪啪打脸,熊 4 即将不省熊事,还要继续打它吗?
这些都是值的思考的问题。
说了那么多,口干舌燥,我双手已经饥渴难耐了,迫不及待的想要撸起代码了。
1. 随机访问
上面说了,为了负载均衡,我们必须保证多次出手后,熊 1 到熊 4 被打次数均衡。比如使用随机访问法,根据数学上的概率论,随机出手次数越多,每只熊被打的次数就会越相近。代码实现也比较简单,使用一个随机数,随机访问一个就可以了。
/** 服务器列表 */ private static List<String> serverList = new ArrayList<>(); static { serverList.add("192.168.1.2"); serverList.add("192.168.1.3"); serverList.add("192.168.1.4"); serverList.add("192.168.1.5"); } /** * 随机路由算法 */ public static String random() { // 复制遍历用的集合,防止操作中集合有变更 List<String> tempList = new ArrayList<>(serverList.size()); tempList.addAll(serverList); // 随机数随机访问 int randomInt = new Random().nextInt(tempList.size()); return tempList.get(randomInt); }
因为使用了非线程安全的集合,所以在访问操作时操作的是集合的拷贝,下面几种轮训方式中也是这种思想。
写一个模拟请求方法,请求10w次,记录请求结果。
public static void main(String[] args) { HashMap<String, Integer> serverMap = new HashMap<>(); for (int i = 0; i < 20000; i++) { String server = random(); Integer count = serverMap.get(server); if (count == null) { count = 1; } else { count++; } // 记录 serverMap.put(server, count); } // 路由总体结果 for (Map.Entry<String, Integer> entry : serverMap.entrySet()) { System.out.println("IP:" + entry.getKey() + ",次数:" + entry.getValue()); } }
运行得到请求结果。
IP:192.168.1.3,次数:24979 IP:192.168.1.2,次数:24896 IP:192.168.1.5,次数:25043 IP:192.168.1.4,次数:25082
每台服务器被访问的次数都趋近于 2.5w,有点负载均衡的意思。但是随机毕竟是随机,是不能保证访问次数绝对均匀的。
2. 轮训访问
轮训访问就简单多了,拿上面的熊1到熊4来说,我们一个接一个的啪啪 - 打脸,熊1打完打熊2,熊2打完打熊3,熊4打完打熊1,最终也是实现了被打均衡。但是保证均匀总是要付出代价的,随机访问中需要随机,轮训访问中需要什么来保证轮训呢?
/** 服务器列表 */ private static List<String> serverList = new ArrayList<>(); static { serverList.add("192.168.1.2"); serverList.add("192.168.1.3"); serverList.add("192.168.1.4"); serverList.add("192.168.1.5"); } private static Integer index = 0; /** * 随机路由算法 */ public static String randomOneByOne() { // 复制遍历用的集合,防止操作中集合有变更 List<String> tempList = new ArrayList<>(serverList.size()); tempList.addAll(serverList); String server = ""; synchronized (index) { index++; if (index == tempList.size()) { index = 0; } server = tempList.get(index);; } return server; }
由代码里可以看出来,为了保证轮训,必须记录上次访问的位置,为了让在并发情况下不出现问题,还必须在使用位置记录时进行加锁,很明显这种互斥锁增加了性能开销。
依旧使用上面的测试代码测试10w次请求负载情况。
IP:192.168.1.3,次数:25000 IP:192.168.1.2,次数:25000 IP:192.168.1.5,次数:25000 IP:192.168.1.4,次数:25000
3. 轮训加权
上面演示了轮训方式,还记的一开始提出的熊4比较胖抗击打能力强,可以承受别人2倍的挨打次数嘛?上面两种方式都没有体现出来熊 4 的这个特点,熊 4 窃喜,不痛不痒。但是熊 1 到 熊 3 已经在崩溃的边缘,不行,我们必须要让胖着多打,能者多劳,提高整体性能。
/** 服务器列表 */ private static HashMap<String, Integer> serverMap = new HashMap<>(); static { serverMap.put("192.168.1.2", 2); serverMap.put("192.168.1.3", 2); serverMap.put("192.168.1.4", 2); serverMap.put("192.168.1.5", 4); } private static Integer index = 0; /** * 加权路由算法 */ public static String oneByOneWithWeight() { List<String> tempList = new ArrayList(); HashMap<String, Integer> tempMap = new HashMap<>(); tempMap.putAll(serverMap); for (String key : serverMap.keySet()) { for (int i = 0; i < serverMap.get(key); i++) { tempList.add(key); } } synchronized (index) { index++; if (index == tempList.size()) { index = 0; } return tempList.get(index); } }
这次记录下了每台服务器的整体性能,给出一个数值,数值越大,性能越好。可以承受的请求也就越多,可以看到服务器 192.168.1.5
的性能为 4,是其他服务器的两倍,依旧 10 w 请求测试。
IP:192.168.1.3,次数:20000 IP:192.168.1.2,次数:20000 IP:192.168.1.5,次数:40000 IP:192.168.1.4,次数:20000
192.168.1.5
承担了 2 倍的请求。
4. 随机加权
随机加权的方式和轮训加权的方式大致相同,只是把使用互斥锁轮训的方式换成了随机访问,按照概率论来说,访问量增多时,服务访问也会达到负载均衡。
/** 服务器列表 */ private static HashMap<String, Integer> serverMap = new HashMap<>(); static { serverMap.put("192.168.1.2", 2); serverMap.put("192.168.1.3", 2); serverMap.put("192.168.1.4", 2); serverMap.put("192.168.1.5", 4); } /** * 加权路由算法 */ public static String randomWithWeight() { List<String> tempList = new ArrayList(); HashMap<String, Integer> tempMap = new HashMap<>(); tempMap.putAll(serverMap); for (String key : serverMap.keySet()) { for (int i = 0; i < serverMap.get(key); i++) { tempList.add(key); } } int randomInt = new Random().nextInt(tempList.size()); return tempList.get(randomInt); }
依旧 10 w 请求测试,192.168.1.5
的权重是其他服务器的近似两倍,
IP:192.168.1.3,次数:19934 IP:192.168.1.2,次数:20033 IP:192.168.1.5,次数:39900 IP:192.168.1.4,次数:20133
5. IP-Hash
上面的几种方式要么使用随机数,要么使用轮训,最终都达到了请求的负载均衡。但是也有一个很明显的缺点,就是同一个用户的多次请求很有可能不是同一个服务进行处理的,这时问题来了,如果你的服务依赖于 session ,那么因为服务不同, session 也会丢失,不是我们想要的,所以出现了一种根据请求端的 ip 进行哈希计算来决定请求到哪一台服务器的方式。这种方式可以保证同一个用户的请求落在同一个服务上。
private static List<String> serverList = new ArrayList<>(); static { serverList.add("192.168.1.2"); serverList.add("192.168.1.3"); serverList.add("192.168.1.4"); serverList.add("192.168.1.5"); } /** * ip hash 路由算法 */ public static String ipHash(String ip) { // 复制遍历用的集合,防止操作中集合有变更 List<String> tempList = new ArrayList<>(serverList.size()); tempList.addAll(serverList); // 哈希计算请求的服务器 int index = ip.hashCode() % serverList.size(); return tempList.get(Math.abs(index)); }
6. 总结
上面的四种方式看似不错,那么这样操作下来真的体现了一开始说的负载均衡吗?答案是不一定的。就像上面的最后一个提问。
又或者每次出手的力度不同,有重有轻,恰巧熊 4 总是承受这种大力度啪啪打脸,熊 4 即将不省熊事,还要继续打它吗?
服务器也是这个道理,每次请求进行的操作对资源的消耗可能是不同的。比如说某些操作它对 CPU 的使用就是比较高,也很正常。所以负载均衡有时不能简单的通过请求的负载来作为负载均衡的唯一依据。还可以结合服务的当前连接数量、最近响应时间等维度进行总体均衡,总而言之,就是为了达到资源使用的负载均衡。
最后的话
文章已经收录在 Github.com/niumoo/JavaNotes ,欢迎Star和指教。更有一线大厂面试点,Java程序员需要掌握的核心知识等文章,也整理了很多我的文字,欢迎 Star 和完善,希望我们一起变得优秀。
文章有帮助可以点个「赞」或「分享」,都是支持,我都喜欢!
文章每周持续更新,要实时关注我更新的文章以及分享的干货,可以关注「 未读代码 」公众号或者我的博客。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
MySQL 的 crash-safe 原理解析
本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/5i9wmJs4_Er7RaYfNnETyA 作者:xieweipeng MySQL作为当下最流行的开源关系型数据库,有一个很关键和基本的能力,就是必须能够保证数据不会丢。那么在这个能力背后,MySQL是如何设计才能保证不管在什么时间崩溃,恢复后都能保证数据不会丢呢?有哪些关键技术支撑了这个能力?本文将为我们一一揭晓。 一、前言 MySQL保证数据不会丢的能力主要体现在两方面: 能够恢复到任何时间点的状态; 能够保证MySQL在任何时间段突然奔溃,重启后之前提交的记录都不会丢失; 对于第一点将MySQL恢复到任何时间点的状态,相信很多人都知道,只要保留有足够的binlog,就能通过重跑binlog来实现。 对于第二点的能力,也就是本文标题所讲的crash-safe。即在 InnoDB 存储引擎中,事务提交过程中任何阶段,MySQL突然奔溃,重启后都能保证事务的完整性,已提交的数据不会丢失,未提交完整的数据会自动进行回滚。这个能力依赖的就是redo log和unod log两个日志。 ...
- 下一篇
解Bug之路-记一次存储故障的排查过程
解Bug之路-记一次存储故障的排查过程 高可用真是一丝细节都不得马虎。平时跑的好好的系统,在相应硬件出现故障时就会引发出潜在的Bug。偏偏这些故障在应用层的表现稀奇古怪,很难让人联想到是硬件出了问题,特别是偶发性出现的问题更难排查。今天,笔者就给大家带来一个存储偶发性故障的排查过程。 Bug现场 我们的积分应用由于量非常大,所以需要进行分库分表,所以接入了我们的中间件。一直稳定运行,但应用最近确经常偶发连接建立不上的报错。报错如下: GetConnectionTimeOutException 而笔者中间件这边收到的确是: NIOReactor - register err java.nio.channels.CloasedChannelException 这样的告警。整个Bug现场如下图所示: 偶发性错误 之前出过类似register err这样的零星报警,最后原因是安全扫描,并没有对业务造成任何影响。而这一次,类似的报错造成了业务的大量连接超时。由于封网,线上中间件和应用已经稳定在线上跑了一个多月,代码层面没有任何改动!突然出现的这个错误感觉是环境出现了某些问题。而且由于线上的应用和...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Hadoop3单机部署,实现最简伪集群
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16