How Nginx implements polling algorithm

Simple polling algorithm

This algorithm is relatively simple. For example, you have three servers

First Server	192.168.1.1
Second server	192.168.1.2
Third server Server	192.168.1.3

After the first request comes, it will access the first server by default, the second request will access the second server, and the third server The first request comes to access the third station, the fourth request comes to access the first station, and so on. The following is a simple algorithm implemented by my code:

public class simplepolling {

  /**
   * key是ip
   */
  public static list <string> ipservice = new linkedlist <>();
  static {
    ipservice.add("192.168.1.1");
    ipservice.add("192.168.1.2");
    ipservice.add("192.168.1.3");
  }
  public static int pos = 0;
  public static string getip(){
    if(pos >= ipservice.size()){
      //防止索引越界
      pos = 0;
    }
    string ip = ipservice.get(pos);
    pos ++;
    return ip;

  }

  public static void main(string[] args) {
    for (int i = 0; i < 4; i++) {
      system.out.println(getip());

    }
  }
}

The result of simulated execution 4 times is

If I have a server performance comparison at this time OK (such as 192.168.1.1), I want this server to handle more requests. At this time, the weight probability is involved. This algorithm cannot be implemented. Please see the polling upgrade algorithm I describe later.

Weighted polling algorithm

At this time, I need to set the weights of the three servers in front of me. For example, the first one is set to 5, the second one is set to 1, and the first one is set to 1. Three settings 1

##Third server192.168.1.31

First server	192.168.1.1	5
Second server	192.168.1.2	1

At this time, the first 5 requests will access the first server, the sixth request will access the second server, and the seventh request will access to the third server.

The following is the code example I gave:

public class weightpolling {

  /**
   * key是ip,value是权重
   */
  public static map<string, integer> ipservice = new linkedhashmap<>();
  static {
    ipservice.put("192.168.1.1", 5);
    ipservice.put("192.168.1.2", 1);
    ipservice.put("192.168.1.3", 1);
  }
  public static int requestid = 0;
  public static int getandincrement() {
    return requestid++;
  }

  public static string getip(){
    //获取总的权重
    int totalweight =0;
    for (integer value : ipservice.values()) {
      totalweight+= value;
    }
    //获取当前轮询的值
    int andincrement = getandincrement();
    int pos = andincrement% totalweight;
    for (string ip : ipservice.keyset()) {
      if(pos < ipservice.get(ip)){
        return ip;
      }
      pos -= ipservice.get(ip);
    }
    return null;
  }

  public static void main(string[] args) {
    for (int i = 0; i < 7; i++) {
      system.out.println(getip());
    }
  }

}

The running result at this time is

The first one you can see The first server has been executed 5 times, the next 2 servers have been executed once, and so on. Maybe you think this algorithm is not bad. In fact, one disadvantage of this algorithm is that if the weight of the first server is too large, I may need to execute many requests to the first server. In this case, the distribution is uneven and will cause pressure on a certain server. Excessive size leads to collapse. So I will introduce a third algorithm to solve this problem later

Smooth Weighted Polling Algorithm

This algorithm may be more complicated, and it was a bit confusing when I first looked at it. I don’t quite understand. I’ve read relevant information later and combined it with my own understanding to explain it with pictures and text. The server configuration and weights I gave as an example here are still the same as above

Request Current weight = own weight current weight after selection Total weightCurrent maximum weightReturned ipCurrent after selection Weight = current maximum weight - total weight ##1##2{3,2 ,2}73192.168.1.1{-4,2,2}3{1,3,3}73192.168.1.2{1,-4 ,3}4{6,-3,4}76 192.168.1.1{-1,-3,4}5{4,-2,5}75192.168.1.3{4,-2,-2}6{9,-1,-1}79192.168.1.1{2,-1,-1}7{7,0,0}77192.168.1.1{0,0,0}As can be seen from the above figure, although the weight of the first server is set to 5, it is not the fifth request. In the past, it was always executed on the first server, but it was executed in a distributed manner. The scheduling sequence was very even, and after the seventh scheduling was selected, the current weight returned to {0, 0, 0}, and the state of the instance was consistent with the initial state. Therefore, the scheduling operation can be repeated in the future.

{5,1,1}	7	5	192.168.1.1	{-2,1,1}

Some people may not clearly understand the meaning of the previous picture. Let me briefly describe it here:

1. First of all, the total weight will not change. The default is the currently set weight. The sum of

2. When the first request comes in, I initialize the current weight selected value by default to {0,0,0}, so the current weight value is {5 0,1 0,1 0} ,5,1,1 here are the weights set by each server in front of us.

3. Here we can conclude that the maximum weight of the first request is 5. Then return to the first server ip

4. Then we set the current weight after selection. Here is the current maximum weight minus the total weight (5-7). The weight of the unselected weight remains unchanged. At this time, the current weight is obtained. Select the weight value {5-7,1,1}

5. When the second request comes, we continue the above steps 2, 3, and 4.

If there is still If you don’t understand, I will provide the algorithm I implemented using java code below:

public class polling {

  /**
   * key是ip,value是权重
   */
  public static map <string,integer> ipservice = new linkedhashmap <>();
  static {
    ipservice.put("192.168.1.1",5);
    ipservice.put("192.168.1.2",1);
    ipservice.put("192.168.1.3",1);
  }
  private static map<string,weight> weightmap = new linkedhashmap <>();

  public static string getip(){
    //计算总的权重
     int totalweight = 0;
    for (integer value : ipservice.values()) {
      totalweight+=value;
    }
    //首先判断weightmap是否为空
    if(weightmap.isempty()){
      ipservice.foreach((ip,weight)->{
        weight weights = new weight(ip, weight,0);
        weightmap.put(ip,weights);
      });
    }
    //给map中得对象设置当前权重
    weightmap.foreach((ip,weight)->{
      weight.setcurrentweight(weight.getweight() + weight.getcurrentweight());
    });

    //判断最大权重是否大于当前权重,如果为空或者小于当前权重，则把当前权重赋值给最大权重
    weight maxweight = null;
    for (weight weight : weightmap.values()) {
      if(maxweight ==null || weight.getcurrentweight() > maxweight.getcurrentweight()){
        maxweight = weight;
      }
    }
    //最后把当前最大权重减去总的权重
    maxweight.setcurrentweight(maxweight.getcurrentweight() - totalweight);
    //返回
    return maxweight.getip();
  }

  public static void main(string[] args) {
    //模拟轮询7次取ip
    for (int i = 0; i < 7; i++) {
      system.out.println(getip());
    }
  }

}

class weight{
  /**
   * ip
   */
  private string ip;
  /**
   * 设置得权重
   */
  private int weight;
  /**
   * 当前权重
   */
  private int currentweight;

  public weight(string ip, int weight,int currentweight) {
    this.ip = ip;
    this.weight = weight;
    this.currentweight = currentweight;
  }

  public string getip() {
    return ip;
  }

  public void setip(string ip) {
    this.ip = 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;
  }
}

The execution result of the code here is:

You can see The execution results here are consistent with those described in the table.

The above is the detailed content of How Nginx implements polling algorithm. For more information, please follow other related articles on the PHP Chinese website!