神奇的轮询加权算法（平滑轮询加权算法）

你的名字 2022-09-09 04:55 254阅读 0赞

### 神奇的轮询加权算法（平滑轮询加权算法） ###

偶尔学习期间发现有此奇妙的算法，借此记录。

*  示例
    
     *  存在如下IP+权重数据
        
        <table> 
         <thead> 
          <tr> 
           <th align="left">IP</th> 
           <th align="left">weight</th> 
          </tr> 
         </thead> 
         <tbody> 
          <tr> 
           <td align="left">A</td> 
           <td align="left">4</td> 
          </tr> 
          <tr> 
           <td align="left">B</td> 
           <td align="left">1</td> 
          </tr> 
          <tr> 
           <td align="left">C</td> 
           <td align="left">2</td> 
          </tr> 
         </tbody> 
        </table>

普通的加权轮询结果可能是 `AAAABCC`, 存在的问题：在一个 `T` 周期内导致分配不均，期待在 `T` 周期内将连续的 `A` 分拆在 `BC` 中。  
增加 currentWeight，默认是 0，每次请求后会重新计算

<table> 
 <thead> 
  <tr> 
   <th align="left">IP</th> 
   <th align="left">weight</th> 
   <th align="left">currentWeight</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">A</td> 
   <td align="left">4</td> 
   <td align="left">0</td> 
  </tr> 
  <tr> 
   <td align="left">B</td> 
   <td align="left">1</td> 
   <td align="left">0</td> 
  </tr> 
  <tr> 
   <td align="left">C</td> 
   <td align="left">2</td> 
   <td align="left">0</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th align="left">属性</th> 
   <th align="left">初始状态</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">IP</td> 
   <td align="left">A B C</td> 
  </tr> 
  <tr> 
   <td align="left">weight</td> 
   <td align="left">4 1 2</td> 
  </tr> 
  <tr> 
   <td align="left">currentWeight</td> 
   <td align="left">0 0 0</td> 
  </tr> 
  <tr> 
   <td align="left">totalWeight</td> 
   <td align="left">7</td> 
  </tr> 
 </tbody> 
</table>

模拟请求:

<table> 
 <thead> 
  <tr> 
   <th align="center">请求</th> 
   <th align="left">currentWeight（lastCurrentWeight + weight）</th> 
   <th align="left">MAX（currentWeight）</th> 
   <th align="left">return max</th> 
   <th align="left">MAX（currentWeight） = currentWeight - totalWeight</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">1</td> 
   <td align="left">4（A） 1（B） 2（C）</td> 
   <td align="left">4（A）</td> 
   <td align="left">A</td> 
   <td align="left">-3（A） 1（B） 2（C）</td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="left">1（A） 2（B） 4（C）</td> 
   <td align="left">4（C）</td> 
   <td align="left">C</td> 
   <td align="left">1（A） 2（B） -3（C）</td> 
  </tr> 
  <tr> 
   <td align="center">3</td> 
   <td align="left">5（A） 3（B） -1（C）</td> 
   <td align="left">5（A）</td> 
   <td align="left">A</td> 
   <td align="left">-2（A） 3（B） -1（C）</td> 
  </tr> 
  <tr> 
   <td align="center">4</td> 
   <td align="left">2（A） 4（B） 1（C）</td> 
   <td align="left">4（B）</td> 
   <td align="left">B</td> 
   <td align="left">2（A） -3（B） 1（C）</td> 
  </tr> 
  <tr> 
   <td align="center">5</td> 
   <td align="left">6（A） -2（B） 3（C）</td> 
   <td align="left">6（A）</td> 
   <td align="left">A</td> 
   <td align="left">-1（A） -2（B） 3（C）</td> 
  </tr> 
  <tr> 
   <td align="center">6</td> 
   <td align="left">3（A） -1（B） 5（C）</td> 
   <td align="left">5（C）</td> 
   <td align="left">C</td> 
   <td align="left">3（A） -1（B） -2（C）</td> 
  </tr> 
  <tr> 
   <td align="center">7</td> 
   <td align="left">7（A） 0（B） 0（C）</td> 
   <td align="left">9（A）</td> 
   <td align="left">A</td> 
   <td align="left">0（A） 0（B） 0（C）</td> 
  </tr> 
 </tbody> 
</table>

每 7 次请求一个 `T` 周期，从上述表格数据可看出，在一个 `T` 周期内顺序为 `ACABACA`，这样很好地解决了不均的问题

具体算法如下，见 `MagicalPoll` 类

/**
     * 神奇的轮询加权算法（平滑轮询加权算法）
     * @author ouyangrongtao
     * @since 2021-08-29 15:29
     */
    public class MagicalPoll {
    
        private static final Long POLL_NUMBER = 14L;
        private static final List<Server> SERVERS = new ArrayList<>(3);
    
        // 初始化数据
        static {
            SERVERS.add(new Server("A", 4L));
            SERVERS.add(new Server("B", 1L));
            SERVERS.add(new Server("C", 2L));
        }
    
        private static final Logger LOGGER = LoggerFactory.getLogger(MagicalPoll.class);
    
        /**
         * 平滑轮询加权算法
         */
        private String magicalPoll() {
            // 计算当前的权重
            this.getCurrentWeight();
    
            // 获取当前最大权重机器
            Server server = this.getMaxCurrentWeightServer();
    
            // 重新计算当前的权重
            this.resetCurrentWeight(server);
    
            return server.getIp();
        }
    
        /**
         * 重新计算当前的权重
         */
        private void resetCurrentWeight(Server max) {
            SERVERS.parallelStream().forEach(server -> {
                if (server.equals(max)) {
                    server.setCurrentWeight(server.getCurrentWeight() - this.getTotalWeight());
                }
            });
        }
    
        /**
         * 获取总权重值
         */
        private Long getTotalWeight() {
            return SERVERS.parallelStream().mapToLong(Server::getWeight).sum();
        }
    
        /**
         * 获取 currentWeight
         */
        private void getCurrentWeight() {
            SERVERS.parallelStream()
                    .forEach(server -> server.setCurrentWeight(server.getWeight() + server.getCurrentWeight()));
        }
    
        /**
         * 获取最大的 MaxCurrentWeight
         */
        private Server getMaxCurrentWeightServer() {
            return SERVERS.parallelStream()
                    .max(Comparator.comparing(Server::getCurrentWeight)
                            .thenComparing(Comparator.comparing(Server::getWeight).reversed())
                            .thenComparing(Server::getIp))
                    .orElseThrow();
        }
    
        public static void main(String[] args) {
            MagicalPoll poll = new MagicalPoll();
            for (long i = 0L; i < POLL_NUMBER; i++) {
                String ip = poll.magicalPoll();
                LOGGER.info("第 {} 次访问IP = {}", i + 1, ip);
            }
        }
    
        /**
         * 机器信息类
         */
        static class Server {
            private final String ip;
            private final Long weight;
            private Long currentWeight = 0L;
    
            public Server(String ip, Long weight) {
                this.ip = ip;
                this.weight = weight;
            }
    
            public String getIp() {
                return ip;
            }
    
            public Long getWeight() {
                return weight;
            }
    
            public Long getCurrentWeight() {
                return currentWeight;
            }
    
            public void setCurrentWeight(Long currentWeight) {
                this.currentWeight = currentWeight;
            }
    
            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Server server = (Server) o;
                return Objects.equals(ip, server.ip) && Objects.equals(weight, server.weight) && Objects.equals(currentWeight, server.currentWeight);
            }
    
            @Override
            public int hashCode() {
                return Objects.hash(ip, weight, currentWeight);
            }
        }
    }