几种均衡负载算法

谁借莪１个温暖的怀抱￠ 2022-11-10 05:47 210阅读 0赞

# 几种均衡负载算法 #

负载均衡load balance的意思由多机器组成的服务集群，集群中的每台机器能够均衡处理来自不同客户端的请求。  
它的作用是可以提升服务的吞吐量，利用多台普通的服务器到达大型主机的性能，节省服务器费用。

负载均衡有硬件负载均衡如F5等;也有软件负载均衡如nginx,LVS等。本文介绍软件负载均衡算法。

## 轮询法 ##

轮询法是指：按照请求的时间顺序分别发送不同的机器，又分为三种：完全轮询，加权轮询，平滑加权轮询。

### 完全轮询 ###

认为每台机器的性能都是一样，地位平等。

public class FullRound{ 
    
        static List<String> serverIps = new ArrayList();
        static int index = 0;
    
        static { 
            serverIps.add('127.0.0.1:8080');
            serverIps.add('127.0.0.2:8080');
            serverIps.add('127.0.0.3:8080');
            serverIps.add('127.0.0.4:8080');
            serverIps.add('127.0.0.5:8080');
        }
    
        public string getServerIp() { 
            if (index == serverIps.size() - 1) { 
                index = 0;
            }
            index = index + 1;
            return serverIps.get(index);
        }
    }

### 加权轮询 ###

实际上我们的服务器之间是有性能差异的，可能一个集群中的包含多中配置的机器如：1核2G，2核4G，4核8G,8核32G，  
带宽也是有差异的如：1M，2M，3M，10M…1000M。 此时我们需要对性能好的机器进行加权，让它承担更多的请求。

public class WeightRound{ 
    
        static List<String> serverIps = new ArrayList();
        static int index = 0;
    
        //这里为了便于理解算法，直接加权了
        static { 
            serverIps.add('127.0.0.1:8080');
            serverIps.add('127.0.0.2:8080');
            serverIps.add('127.0.0.3:8080');
            serverIps.add('127.0.0.4:8080');
            serverIps.add('127.0.0.5:8080');
            serverIps.add('127.0.0.1:8080');
            serverIps.add('127.0.0.2:8080');
            serverIps.add('127.0.0.1:8080');
            serverIps.add('127.0.0.3:8080');
            serverIps.add('127.0.0.1:8080');
        }
    
        public string getServerIp() { 
            if (index == serverIps.size() - 1) { 
                index = 0;
            }
            index = index + 1;
            return serverIps.get(index);
        }
    }

### 平滑加权轮询 ###

上面的加权轮询算法，每台机器是的权重是固定的我们叫他**固定加权轮询**实际上有些时候我们需要根据机器当前的  
性能和资源，需要动态的进行加权。也就是所机器的权重会发生变化。

public class SmoothWeightRound{ 
    
        static List<String> serverIps = new ArrayList();
        static int index = 0;
        List<String> urls = new ArrayList();
        static { 
            urls.add('127.0.0.1:8080');
            urls.add('127.0.0.2:8080');
            urls.add('127.0.0.3:8080');
            urls.add('127.0.0.4:8080');
            urls.add('127.0.0.5:8080');
        }
    
        // 定时任务调用，定时重新根据动态权重计算机器池分布
        pulic static void  buildServerPool  { 
           HashMap<String, Long> urlFreeMap = new HashMap<>();
           
           //集群总容量
           Long totalFree = 0L;
           for (String url : urls) { 
                //http请求获取机器剩余容量(根据cpu负载和剩余内存以及网络流量得出容量值) free越大说明机器越空闲 
                // 伪代码
                free = httpClient.execute(url);
                totalFree = totalFree + free;
                urlFreeMap.put(url, free);
            }
            Set<String> urlFrees =  urlFreeMap.keySet();
            List<String> harborListTemp = new ArrayList<>();
            Iterator<String> it = urlFrees.iterator();
            while (it.hasNext()) { 
                String url =  it.next();
                //计算当前机器在所有机器的权重（MathUitls.percentagede 计算百分比，计算保留小数点后两位 free*100/totalFree ）
                int weight = MathUitls.percentage(urlFreeMap.get(url), totalFree).intValue();
                for (int i = 0; i < weight; i++) { 
                    harborListTemp.add(url);
                }
            }
            serverIps = harborListTemp;
        }
    
        public string getServerIp() { 
            if (index == serverIps.size() - 1) { 
                index = 0;
            }
            index = index + 1;
            return serverIps.get(index);
        }
    }

## 随机法 ##

随机算法生成serverIps和上面的还是一样，不通在于从serverIps获取具体机器是随机获取的。  
根据概率论，当请求到一定数量，流量是接近于平分到每一台服务器

### 完全随机法 ###

public class FullRandom{ 
    
        static List<String> serverIps = new ArrayList();
       
        static { 
            serverIps.add('127.0.0.1:8080');
            serverIps.add('127.0.0.2:8080');
            serverIps.add('127.0.0.3:8080');
            serverIps.add('127.0.0.4:8080');
            serverIps.add('127.0.0.5:8080');
        }
    
        public string getServerIp() { 
            java.util.Random random = new java.util.Random();
            int randomPos = random.nextInt(serverIps.size());
            return serverIps.get(index);
        }
    }

### 加权随机法 ###

生成serverIps池和**加权轮询法**是一样的，在获取具体服务器是和**完全随机**getServerIp一样的

### 平滑加权随机法 ###

生成serverIps池和**平滑加权轮询法**是一样的，在获取具体服务器是和**完全随机**getServerIp一样的

## 源地址哈希法 ##

源地址哈希法的思想是获取客户端访问的源Ip,通过计算源地址的hash,并且对计算出来的hash值进行取模运算得到  
具体的服务器。源地址哈希法可以保证同一个客户端会被转发到同一台服务器，客户端与服务端可以建立有状态的session会话。

pulic class Hash{ 
        static List<String> serverIps = new ArrayList();
        static int index = 0;
    
        static { 
            serverIps.add('127.0.0.1:8080');
            serverIps.add('127.0.0.2:8080');
            serverIps.add('127.0.0.3:8080');
            serverIps.add('127.0.0.4:8080');
            serverIps.add('127.0.0.5:8080');
        }
    
        public string getServerIp(String ip) { 
            int hashcode = ip.hashCode();
            int index = hashcode % serverIps.size();
            index = index < 0 ? -index : index; 
            return serverIps.get(index);
        }
    }

上面生成serverIps也可以参考**加权轮询**和**平滑加权轮询**生成服务器池。

## 最小连接数 ##

上面的几种算法，是站在请求nginx这种软件的角度均匀的分发的请求，但是实际上，不同请求，不通参数  
处理起来所需要耗费的资源，以及处理时间是不尽相同的。因此可以站在服务器角度，根据每台机器的连接数  
来进行均衡负载。可以在 **平滑加权轮询**的**buildServerPool**看到我们计算权重是有依赖机器的资源的。

## 一个实际场景 ##

之前在工作实现过一种均衡负载算法。

场景是这样的：制品库需要承担存储集团各个bu的docker镜像。  
我们采用了底层存储用harbor来存储。但是单台harbor的性能是瓶颈的，因此我们需要搭建多台harbor来  
构建一个集群，均匀的存储镜像到harbor，有为了便于后面管理查找，我们把同一个镜像不同tag的镜像存储  
于同一个harbor。

实现算法：计算**buildServerPool**，定时查询harbor的剩余容量，计算单个harbor的权重，根据镜像名计算  
hash分发到不同的harbor

下面看伪代码:

pulic class HarborLoadBalance{ 
    
    
        static List<String> serverIps = new ArrayList();
        static int index = 0;
        List<String> urls = new ArrayList();
        static { 
            urls.add('127.0.0.1:8080');
            urls.add('127.0.0.2:8080');
            urls.add('127.0.0.3:8080');
            urls.add('127.0.0.4:8080');
            urls.add('127.0.0.5:8080');
        }
    
        // 定时任务调用，定时重新根据动态权重计算机器池分布
        pulic static void  buildServerPool  { 
           HashMap<String, Long> urlFreeMap = new HashMap<>();
           
           //集群总容量
           Long totalFree = 0L;
           for (String url : urls) { 
                //http请求获取harbor剩余容量(free越大说明机器越空闲)
                // 伪代码
                free = httpClient.execute(url);
                totalFree = totalFree + free;
                urlFreeMap.put(url, free);
            }
            Set<String> urlFrees =  urlFreeMap.keySet();
            List<String> harborListTemp = new ArrayList<>();
            Iterator<String> it = urlFrees.iterator();
            while (it.hasNext()) { 
                String url =  it.next();
                //计算当前机器在所有机器的权重（MathUitls.percentagede 计算百分比，计算保留小数点后两位 free*100/totalFree ）
                int weight = MathUitls.percentage(urlFreeMap.get(url), totalFree).intValue();
                for (int i = 0; i < weight; i++) { 
                    harborListTemp.add(url);
                }
            }
            serverIps = harborListTemp;
        }
    
        //下面伪代码s
        public string getServerIp(String imagesName) { 
            // 缓存查
            String harbor = redis.get(imagesName)
            if (!StringUtils.isEmpty(harbor)) { 
                return harbor
            }
            // db查
            harbor = db.find(imagesName)
            if (!StringUtils.isEmpty(harbor)) { 
                //缓存失效，加入缓存
                redis.set(imagesName, harbor)
                return harbor
            }
            // db缓存都没有,则计算分发
            int hashcode = imagesName.hashCode();
            int index = hashcode % serverIps.size();
            index = index < 0 ? -index : index; 
            harbor = serverIps.get(index);
            // 缓存
            redis.set(imagesName, harbor);
            //db持久化
            db.insert(imagesName, harbor);
            return harbor;
        }
    }