负载均衡之加权轮询算法

算法举例说明

服务实例	权重
127.0.0.1:8001	1
127.0.0.1:8002	2
127.0.0.1:8003	3

共有三个实例，总权重为6，那么实现效果应该为每调用6次：

• 每个实例应该被调用权重次数
• 权重数大的优先被调用

根据以上说明，那么进行排列组合：

• 先按照权重大小排序
• 把权重数做为调用次数排列

排列的结果是这样的：

序号	服务实例	权重
1	127.0.0.1:8003	3
2	127.0.0.1:8003	3
3	127.0.0.1:8003	3
4	127.0.0.1:8002	2
5	127.0.0.1:8002	2
6	127.0.0.1:8001	1

貌似没问题，但每个实例调用不是交替的，分布不够均匀，改进一下重新排列组合：

序号	服务实例	权重
1	127.0.0.1:8003	3
2	127.0.0.1:8002	2
3	127.0.0.1:8003	3
4	127.0.0.1:8002	2
5	127.0.0.1:8003	3
6	127.0.0.1:8001	1

或者

序号	服务实例	权重
1	127.0.0.1:8003	3
2	127.0.0.1:8002	2
3	127.0.0.1:8003	3
4	127.0.0.1:8001	1
5	127.0.0.1:8003	3
6	127.0.0.1:8002	2

2个权重变量：weight，current_weight

weight

配置的固定不变的权重

current_weight

会动态调整的权重，初始化为0，运行时动态调整。
选取开始时，先重新调整current_weight= current_weight+weight，然后通过current_weight值从大到小排序，选择current_weight值最大的（实际编程中不一定要排序，可以直接取最大的）；
然后重新计算被选择的current_weight值= current_weight-总weight。

下面是用Lua脚本实现的该算法：

function _M:next()
   local servers=self.servers
   local totalWeight = totalWeight(servers)
   for k,v in pairs(servers) do
       v.cweight=v.weight+v.cweight
   end

   table.sort( servers, 
       function (a,b)
           return a.cweight>b.cweight
       end 
   )
   selected=servers[1]
   selected.cweight=selected.cweight-totalWeight

   return selected

end