网站建设人员的分工,做网站看百度脸色,销售管理系统包括哪几大模块,需要代理记账的公司文章目录 一、负载均衡算法概述二、轮询#xff08;RoundRobin#xff09;算法1、概述2、Java实现轮询算法3、优缺点 三、随机#xff08;Random#xff09;算法1、概述2、Java实现随机算法 四、源地址哈希#xff08;Hash#xff09;算法1、概述2、Java实现地址哈希算法… 文章目录 一、负载均衡算法概述二、轮询RoundRobin算法1、概述2、Java实现轮询算法3、优缺点 三、随机Random算法1、概述2、Java实现随机算法 四、源地址哈希Hash算法1、概述2、Java实现地址哈希算法3、一致性哈希1原理2特性3优化4Java实现一致性哈希算法 五、加权轮询WRR算法1、概述2、Java实现加权轮询算法 六、加权随机WR算法1、概述2、Java实现加权随机算法 七、最小连接数LC算法1、概述2、Java实现最小连接数算法 八、应用案例1、nginx upstream2、springcloud ribbon IRule3、dubbo负载均衡 一、负载均衡算法概述
负载均衡英文名称为Load Balance其含义就是指将负载工作任务进行平衡、分摊到多个操作单元上进行运行例如FTP服务器、Web服务器、企业核心应用服务器和其它主要任务服务器等从而协同完成工作任务。既然涉及到多个机器就涉及到任务如何分发这就是负载均衡算法问题。
二、轮询RoundRobin算法
1、概述
轮询即排好队一个接一个。
2、Java实现轮询算法
手动写一个双向链表形式实现服务器列表的请求轮询算法。
public class RR {//当前服务节点Server current;//初始化轮询类多个服务器ip用逗号隔开public RR(String serverName){System.out.println(init server list : serverName);String[] names serverName.split(,);for (int i 0; i names.length; i) {Server server new Server(names[i]);if (current null){//如果当前服务器为空说明是第一台机器current就指向新创建的serverthis.current server;//同时server的前后均指向自己。current.prev current;current.next current;}else {//否则说明已经有机器了按新加处理。addServer(names[i]);}}}//添加机器void addServer(String serverName){System.out.println(add server : serverName);Server server new Server(serverName);Server next this.current.next;//在当前节点后插入新节点this.current.next server;server.prev this.current;//修改下一节点的prev指针server.next next;next.prevserver;}//将当前服务器移除同时修改前后节点的指针让其直接关联//移除的current会被回收期回收掉void remove(){System.out.println(remove current current.name);this.current.prev.next this.current.next;this.current.next.prev this.current.prev;this.current current.next;}//请求。由当前节点处理即可//注意处理完成后current指针后移void request(){System.out.println(this.current.name);this.current current.next;}public static void main(String[] args) throws InterruptedException {//初始化两台机器RR rr new RR(192.168.0.1,192.168.0.2);//启动一个额外线程模拟不停的请求new Thread(new Runnable() {Overridepublic void run() {while (true) {try {Thread.sleep(500);} catch (InterruptedException e) {e.printStackTrace();}rr.request();}}}).start();//3s后3号机器加入清单Thread.currentThread().sleep(3000);rr.addServer(192.168.0.3);//3s后当前服务节点被移除Thread.currentThread().sleep(3000);rr.remove();}class Server{Server prev; // 前驱Server next; // 后继String name; // 名称public Server(String name){this.name name;}}}
初始化后只有12两者轮询 3加入后123三者轮询 移除2后只剩1和3轮询
3、优缺点
实现简单机器列表可以自由加减且时间复杂度为o(1)。 无法针对节点做偏向性定制节点处理能力的强弱无法区分对待。
三、随机Random算法
1、概述
从可服务的列表中随机取一个提供响应。
2、Java实现随机算法
随机存取的场景下适合使用数组更高效的实现下标随机读取。 定义一个数组在数组长度内取随机数作为其下标即可。非常简单。
public class Rand {// 所有服务ipArrayListString ips ;//初始化随机类多个服务器ip用逗号隔开public Rand(String nodeNames){System.out.println(init list : nodeNames);String[] nodes nodeNames.split(,);//初始化服务器列表长度取机器数ips new ArrayList(nodes.length);for (String node : nodes) {ips.add(node);}}//请求void request(){//下标随机数注意因子int i new Random().nextInt(ips.size());System.out.println(ips.get(i));}//添加节点注意添加节点会造成内部数组扩容//可以根据实际情况初始化时预留一定空间void addnode(String nodeName){System.out.println(add node : nodeName);ips.add(nodeName);}//移除void remove(String nodeName){System.out.println(remove node : nodeName);ips.remove(nodeName);}public static void main(String[] args) throws InterruptedException {Rand rd new Rand(192.168.0.1,192.168.0.2);//启动一个额外线程模拟不停的请求new Thread(new Runnable() {Overridepublic void run() {while (true) {try {Thread.sleep(500);} catch (InterruptedException e) {e.printStackTrace();}rd.request();}}}).start();//3s后3号机器加入清单Thread.currentThread().sleep(3000);rd.addnode(192.168.0.3);//3s后当前服务节点被移除Thread.currentThread().sleep(3000);rd.remove(192.168.0.2);}
}
初始化为12两者不按顺序轮询而是随机出现。 3加入服务节点列表。 移除2后只剩13依然是两者随机无序。
四、源地址哈希Hash算法
1、概述
对当前访问的ip地址做一个hash值相同的key被路由到同一台机器去。场景常见于分布式集群环境下用户登录时的请求路由和会话保持。
2、Java实现地址哈希算法
使用HashMap可以实现请求值到对应节点的服务其查找时的时间复杂度为o(1)。固定一种算法将请求映射到key上即可。
举例将请求的来源ip末尾按机器数取余作为key
public class Hash {// 所有服务ipArrayListString ips ;//初始化hash类多个服务器ip用逗号隔开public Hash(String nodeNames){System.out.println(init list : nodeNames);String[] nodes nodeNames.split(,);//初始化服务器列表长度取机器数ips new ArrayList(nodes.length);for (String node : nodes) {ips.add(node);}}//添加节点注意添加节点会造成内部Hash重排思考为什么呢//这是个问题在一致性hash中会进入详细探讨void addnode(String nodeName){System.out.println(add node : nodeName);ips.add(nodeName);}//移除void remove(String nodeName){System.out.println(remove node : nodeName);ips.remove(nodeName);}//映射到key的算法这里取余数做下标private int hash(String ip){int last Integer.valueOf(ip.substring(ip.lastIndexOf(.)1,ip.length()));return last % ips.size();}//请求//注意这里和来访ip是有关系的采用一个参数表示当前的来访ipvoid request(String ip){//下标int i hash(ip);System.out.println(ip--ips.get(i));}public static void main(String[] args) {Hash hash new Hash(192.168.0.1,192.168.0.2);for (int i 1; i 10; i) {//模拟请求的来源ipString ip 192.168.0. i;hash.request(ip);}hash.addnode(192.168.0.3);for (int i 1; i 10; i) {//模拟请求的来源ipString ip 192.168.0. i;hash.request(ip);}hash.remove(192.168.0.2);for (int i 1; i 10; i) {//模拟请求的来源ipString ip 192.168.0. i;hash.request(ip);}}}
初始化后只有12下标为末尾ip取余数多次运行响应的机器不变实现了会话保持。 3加入后重新hash机器分布发生变化。 2被移除后原来hash到2的请求被重新定位给3响应。
3、一致性哈希
源地址hash算法让某些请求固定的落在对应的服务器上。这样可以解决会话信息保留的问题。
同时标准的hash如果机器节点数发生变更。那么请求会被重新hash打破了原始的设计初衷怎么解决呢答案就是一致性hash。
1原理
以4台机器为例一致性hash的算法如下 首先求出各个服务器的哈希值并将其配置到0232的圆上 然后采用同样的方法求出存储数据的键的哈希值也映射圆上 从数据映射到的位置开始顺时针查找将数据保存到找到的第一个服务器上 如果到最大值仍然找不到就取第一个。这就是为啥形象的称之为环。 添加节点 删除节点原理雷同
2特性
单调性(Monotonicity)单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理又有新的服务器加入到系统中时候应保证原有的请求可以被映射到原有的或者新的服务器中去而不会被映射到原来的其它服务器上去。
分散性(Spread)分布式环境中客户端请求时可能只知道其中一部分服务器那么两个客户端看到不同的部分并且认为自己看到的都是完整的hash环那么问题来了相同的key可能被路由到不同服务器上去。以上图为例加入client1看到的是1,4client2看到的是2,3那么2-4之间的key会被俩客户端重复映射到3,4上去。分散性反应的是这种问题的严重程度。
平衡性(Balance)平衡性是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到尽量分散但是不能保证每个服务器处理的请求的数量完全相同。这种偏差称为hash倾斜。如果节点的分布算法设计不合理那么平衡性就会收到很大的影响。
3优化
增加虚拟节点可以优化hash算法使得切段和分布更细化。即实际有m台机器但是扩充n倍在环上放置m*n个那么均分后key的段会分布更细化。
4Java实现一致性哈希算法
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;/*** 不带虚拟节点的一致性Hash算法*/
public class ConsistentHashingWithoutVirtualNode {//服务器列表private static String[] servers { 192.168.0.0, 192.168.0.1,192.168.0.2, 192.168.0.3, 192.168.0.4 };//key表示服务器的hash值value表示服务器private static SortedMapInteger, String serverMap new TreeMapInteger, String();static {for (int i0; iservers.length; i) {int hash getHash(servers[i]);//理论上hash环的最大值为2^32//这里为做实例将ip末尾作为上限也就是254//那么服务器是0-4乘以60后可以均匀分布到 0-254 的环上去//实际的请求ip到来时在环上查找即可hash * 60;System.out.println(add servers[i] , hash hash);serverMap.put(hash, servers[i]);}}//查找节点private static String getServer(String key) {int hash getHash(key);//得到大于该Hash值的所有serverSortedMapInteger, String subMap serverMap.tailMap(hash);if(subMap.isEmpty()){//如果没有比该key的hash值大的则从第一个node开始Integer i serverMap.firstKey();//返回对应的服务器return serverMap.get(i);}else{//第一个Key就是顺时针过去离node最近的那个结点Integer i subMap.firstKey();//返回对应的服务器return subMap.get(i);}}//运算hash值//该函数可以自由定义只要做到取值离散即可//这里取ip地址的最后一节private static int getHash(String str) {String last str.substring(str.lastIndexOf(.)1,str.length());return Integer.valueOf(last);}public static void main(String[] args) {//模拟5个随机ip请求for (int i 0; i 5; i) {String ip 192.168.0. new Random().nextInt(254);System.out.println(ip --- getServer(ip));}//将5号服务器加到2-3之间取中间位置150System.out.println(add 192.168.0.5hash150);serverMap.put(150,192.168.0.5);//再次发起5个请求for (int i 0; i 5; i) {String ip 192.168.0. new Random().nextInt(254);System.out.println(ip --- getServer(ip));}}
}4台机器加入hash环 模拟请求根据hash值准确调度到下游节点 添加节点5key取150 再次发起请求
五、加权轮询WRR算法
1、概述
WeightRoundRobin轮询只是机械的旋转加权轮询弥补了所有机器一视同仁的缺点。在轮询的基础上初始化时机器携带一个比重。
2、Java实现加权轮询算法
维护一个链表每个机器根据权重不同占据的个数不同。轮询时权重大的个数多自然取到的次数变大。举个例子abc 三台机器权重分别为421排位后会是a,a,a,a,b,b,c每次请求时从列表中依次取节点下次请求再取下一个。到末尾时再从头开始。
但是这样有一个问题机器分布不够均匀扎堆出现了…
解决为解决机器平滑出现的问题nginx的源码中使用了一种平滑的加权轮询的算法规则如下 每个节点两个权重weight和currentWeightweight永远不变是配置时的值current不停变化 变化规律如下选择前所有current weight选current最大的响应响应后让它的current - total。 统计a4b2c1 且分布平滑均衡
public class WRR {//所有节点的列表ArrayListNode list ;//总权重int total;//初始化节点列表public WRR(String nodes){String[] ns nodes.split(,);list new ArrayList(ns.length);for (String n : ns) {String[] n1 n.split(#);int weight Integer.valueOf(n1[1]);list.add(new Node(n1[0],weight));total weight;}}//获取当前节点Node getCurrent(){//执行前current加权重for (Node node : list) {node.currentWeight node.weight;}//遍历取权重最高的返回Node current list.get(0);int i 0;for (Node node : list) {if (node.currentWeight i){i node.currentWeight;current node;}}return current;}//响应void request(){//获取当前节点Node node this.getCurrent();//第一列执行前的currentSystem.out.print(list.toString()---);//第二列选中的节点开始响应System.out.print(node.name---);//响应后current减掉totalnode.currentWeight - total;//第三列执行后的currentSystem.out.println(list);}public static void main(String[] args) {WRR wrr new WRR(a#4,b#2,c#1);//7次执行请求看结果for (int i 0; i 7; i) {wrr.request();}}class Node{int weight,currentWeight; // 权重和currentString name;public Node(String name,int weight){this.name name;this.weight weight;this.currentWeight 0;}Overridepublic String toString() {return String.valueOf(currentWeight);}}
}
六、加权随机WR算法
1、概述
WeightRandom机器随机被筛选但是做一组加权值根据权值不同选中的概率不同。在这个概念上可以认为随机是一种等权值的特殊情况。
2、Java实现加权随机算法
设计思路依然相同根据权值大小生成不同数量的节点节点排队后随机获取。这里的数据结构主要涉及到随机的读取所以优选为数组。
与随机相同的是同样为数组随机筛选不同在于随机只是每台机器1个加权后变为多个。
public class WR {//所有节点的列表ArrayListString list ;//初始化节点列表public WR(String nodes){String[] ns nodes.split(,);list new ArrayList();for (String n : ns) {String[] n1 n.split(#);int weight Integer.valueOf(n1[1]);for (int i 0; i weight; i) {list.add(n1[0]);}}}void request(){//下标随机数注意因子int i new Random().nextInt(list.size());System.out.println(list.get(i));}public static void main(String[] args) {WR wr new WR(a#2,b#1);for (int i 0; i 9; i) {wr.request();}}}
运行9次ab交替出现a6,b3,满足2:1比例 注意既然是随机就存在随机性不见得每次执行都会严格比例。样本趋向无穷时比例约准确
七、最小连接数LC算法
1、概述
LeastConnections即统计当前机器的连接数选最少的去响应新的请求。前面的算法是站在请求维度而最小连接数是站在机器的维度。
2、Java实现最小连接数算法
定义一个链接表记录机器的节点id和机器连接数量的计数器。内部采用最小堆做排序处理响应时取堆顶节点即是最小连接数。
public class LC {//节点列表Node[] nodes;//初始化节点创建堆// 因为开始时各节点连接数都为0所以直接填充数组即可LC(String ns){String[] ns1 ns.split(,);nodes new Node[ns1.length1];for (int i 0; i ns1.length; i) {nodes[i1] new Node(ns1[i]);}}//节点下沉与左右子节点比对选里面最小的交换//目的是始终保持最小堆的顶点元素值最小//i:要下沉的顶点序号void down(int i) {//顶点序号遍历只要到1半即可时间复杂度为O(log2n)while ( i 1 nodes.length){//左子为何左移1位回顾一下二叉树序号int left i1;//右子左1即可int right left1;//标记指向 本节点左、右子节点里最小的一开始取i自己int flag i;//判断左子是否小于本节点if (nodes[left].get() nodes[i].get()){flag left;}//判断右子if (right nodes.length nodes[flag].get() nodes[right].get()){flag right;}//两者中最小的与本节点不相等则交换if (flag ! i){Node temp nodes[i];nodes[i] nodes[flag];nodes[flag] temp;i flag;}else {//否则相等堆排序完成退出循环即可break;}}}//请求。非常简单直接取最小堆的堆顶元素就是连接数最少的机器void request(){System.out.println(---------------------);//取堆顶元素响应请求Node node nodes[1];System.out.println(node.name accept);//连接数加1node.inc();//排序前的堆System.out.println(before:Arrays.toString(nodes));//堆顶下沉down(1);//排序后的堆System.out.println(after:Arrays.toString(nodes));}public static void main(String[] args) {//假设有7台机器LC lc new LC(a,b,c,d,e,f,g);//模拟10个请求连接for (int i 0; i 10; i) {lc.request();}}class Node{//节点标识String name;//计数器AtomicInteger count new AtomicInteger(0);public Node(String name){this.name name;}//计数器增加public void inc(){count.getAndIncrement();}//获取连接数public int get(){return count.get();}Overridepublic String toString() {return namecount;}}
}初始化后堆节点值都为0即每个机器连接数都为0 堆顶连接后下沉堆重新排序最小堆规则保持成立
八、应用案例
1、nginx upstream
upstream frontend {#源地址haship_hash;server 192.168.0.1:8081;server 192.168.0.2:8082 weight1 down;server 192.168.0.3:8083 weight2;server 192.168.0.4:8084 weight3 backup;server 192.168.0.5:8085 weight4 max_fails3 fail_timeout30s;
}ip_hash即源地址hash算法 down表示当前的server暂时不参与负载 weight即加权算法默认为1weight越大负载的权重就越大。 backup备份机器只有其它所有的非backup机器down或者忙的时候再请求backup机器。 max_fails最大失败次数默认值为1这里为3也就是最多进行3次尝试 fail_timeout超时时间为30秒默认值是10s。 注意weight和backup不能和ip_hash关键字一起使用。
2、springcloud ribbon IRule
#设置负载均衡策略 eureka‐application‐service为调用的服务的名称
eureka‐application‐service.ribbon.NFLoadBalancerRuleClassNamecom.netflix.loadbalancer.RandomRuleRoundRobinRule轮询 RandomRule随机 AvailabilityFilteringRule先过滤掉由于多次访问故障而处于断路器跳闸状态的服务还有并发的连接数量超过阈值的服务然后对剩余的服务轮询 WeightedResponseTimeRule根据平均响应时间计算所有服务的权重响应时间越快服务权重越大。刚启动时如果统计信息不足则使用RoundRobinRule策略等统计信息足够会切换到该策略 RetryRule先按照RoundRobinRule的策略如果获取服务失败则在指定时间内重试获取可用的服务 BestAvailableRule会先过滤掉由于多次访问故障而处于断路器跳闸状态的服务然后选择一个并发量最小的服务 ZoneAvoidanceRule默认规则综合判断server所在区域的性能和server的可用性
3、dubbo负载均衡
使用Service注解
Service(loadbalance roundrobin,weight 100)RandomLoadBalance: 随机这种方式是dubbo默认的负载均衡策略 RoundRobinLoadBalance轮询 LeastActiveLoadBalance最少活跃次数dubbo框架自定义了一个Filter用于计算服务被调用的次数 ConsistentHashLoadBalance一致性hash
