昨天看了nginx的加权轮询的平滑算法后,自己尝试编写的PHP程序

原文地址 http://blog.csdn.net/zhangskd/article/details/50194069

每个后端peer都有三个权重变量,先解释下它们的含义。

(1) weight

配置文件中指定的该后端的权重,这个值是固定不变的。

(2) effective_weight

后端的有效权重,初始值为weight。

在释放后端时,如果发现和后端的通信过程中发生了错误,就减小effective_weight。

此后有新的请求过来时,在选取后端的过程中,再逐步增加effective_weight,最终又恢复到weight。

之所以增加这个字段,是为了当后端发生错误时,降低其权重。

(3) current_weight

后端目前的权重,一开始为0,之后会动态调整。那么是怎么个动态调整呢?

每次选取后端时,会遍历集群中所有后端,对于每个后端,让它的current_weight增加它的effective_weight,

同时累加所有后端的effective_weight,保存为total。

如果该后端的current_weight是最大的,就选定这个后端,然后把它的current_weight减去total。

如果该后端没有被选定,那么current_weight不用减小。

 

弄清了三个weight字段的含义后,加权轮询算法可描述为:

1. 对于每个请求,遍历集群中的所有可用后端,对于每个后端peer执行:

peer->current_weight += peer->effecitve_weight。

同时累加所有peer的effective_weight,保存为total。

2. 从集群中选出current_weight最大的peer,作为本次选定的后端。

3. 对于本次选定的后端,执行:peer->current_weight -= total。

 

上述描述可能不太直观,来看个例子。

现在使用以下的upstream配置块:

upstream backend {

server a weight=4;

server b weight=2;

server c weight=1;

}

按照这个配置,每7个客户端请求中,a会被选中4次、b会被选中2次、c会被选中1次,且分布平滑。

我们来算算看是不是这样子的。

initial current_weight of a, b, c is { 0, 0, 0 }

 

通过上述过程,可得以下结论:

1. 7个请求中,a、b、c分别被选取了4、2、1次,符合它们的权重值。

2. 7个请求中,a、b、c被选取的顺序为a, b, a, c, a, b, a,分布均匀,权重大的后端a没有被连续选取。

3. 每经过7个请求后,a、b、c的current_weight又回到初始值{ 0, 0, 0 },因此上述流程是不断循环的。

这个平滑的加权轮询算法背后应该有数学论证,这里就不继续研究了:)

 

然后自己写的PHP

 

<?php
class roundLzx{
    public $weight = array();
    public $current = array();
    public $selArr = array();
    public $first = false;

    public function __construct($arr){
        foreach ($arr as $k => $v){
            $this->weight[$k] = $v;
            $this->current[$k] = 0;
        }
        $this->first = true;
    }

    public function getServer(){
        $total = 0;
        if ($this->isEnd() == true && $this->first == false){
            return true;
        }
        $this->first = false;
        foreach ($this->current as $k => $v){
            $this->current[$k] += $this->weight[$k];
            $total += $this->weight[$k];
        }
        //获取最大值
        $sel = $this->maxValue();
        $this->current[$sel] = $this->current[$sel]-$total;
        array_push($this->selArr, $sel);
        if ($this->getServer()){
            return true;
        }
    }
    public function maxValue(){
        $arr=$this->current;
        asort($arr);
        $rel=array();
        foreach($arr as $k=>$v){
            $rel[]=$k;
        }
        return end($rel);
    }

    public function isEnd(){
        $num = 0;
        foreach ($this->current as $k => $v) {
            if ($v == 0){
                $num++;
            }
        }
        return ($num == count($this->current)) ? true : false;
    }
}
$arr = array('a' => 4, 'b' => 2, 'c' => 1);
$obj = new roundLzx($arr);
if ($obj->getServer()){
    print_r($obj->selArr);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注