go随聊-负载均衡[加权轮询]

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

本文内容参考了网上其他文章，懒得自己打字了，拷贝过来直接用：）

在分布式系统中，负载均衡是非常重要的环节，通过负载均衡将请求派发到网络中的一个或多个节点上进行处理。通常来说，负载均衡分为硬件负载均衡及软件负载均衡。硬件负载均衡，顾名思义，在服务器节点之间安装专门的硬件进行负载均衡的工作，F5便为其中的佼佼者。软件负载均衡则是通过在服务器上安装的特定的负载均衡软件或是自带负载均衡模块完成对请求的分配派发。

轮询算法并没有考虑每台服务器的处理能力，实际中可能并不是这种情况。由于每台服务器的配置、安装的业务应用等不同，其处理能力会不一样。所以，加权轮询算法的原理就是：根据服务器的不同处理能力，给每个服务器分配不同的权值，使其能够接受相应权值数的服务请求。

首先看一个简单的Nginx负载均衡配置。

http {  
    upstream cluster {  
        server a weight=1;  
        server b weight=2;  
        server c weight=4;  
    }  
    ...
}

按照上述配置，Nginx每收到7个客户端的请求，会把其中的1个转发给后端a，把其中的2个转发给后端b，把其中的4个转发给后端c。

加权轮询算法的结果，就是要生成一个服务器序列。每当有请求到来时，就依次从该序列中取出下一个服务器用于处理该请求。比如针对上面的例子，加权轮询算法会生成序列{c, c, b, c, a, b, c}。这样，每收到7个客户端的请求，会把其中的1个转发给后端a，把其中的2个转发给后端b，把其中的4个转发给后端c。收到的第8个请求，重新从该序列的头部开始轮询。总之，加权轮询算法要生成一个服务器序列，该序列中包含n个服务器。n是所有服务器的权重之和。在该序列中，每个服务器的出现的次数，等于其权重值。并且，生成的序列中，服务器的分布应该尽可能的均匀。比如序列{a, a, a, a, a, b, c}中，前五个请求都会分配给服务器a，这就是一种不均匀的分配方法，更好的序列应该是：{a, a, b, a, c, a, a}。

在Nginx源码中，实现了一种叫做平滑的加权轮询（smooth weighted round-robin balancing）的算法，它生成的序列更加均匀。比如前面的例子，它生成的序列为{ a, a, b, a, c, a, a}，转发给后端a的5个请求现在分散开来，不再是连续的。该算法的原理如下：

　　每个服务器都有两个权重变量：

　　a：weight，配置文件中指定的该服务器的权重，这个值是固定不变的；

　　b：current_weight，服务器目前的权重。一开始为0，之后会动态调整。

　　每次当请求到来，选取服务器时，会遍历数组中所有服务器。对于每个服务器，让它的current_weight增加它的weight；同时累加所有服务器的weight，并保存为total。

　　遍历完所有服务器之后，如果该服务器的current_weight是最大的，就选择这个服务器处理本次请求。最后把该服务器的current_weight减去total。

GO实现

接口定义：

type LoadBalance interface {
    //选择一个后端Server
    //参数remove是需要排除选择的后端Server
    Select(remove []string) *tool.Server
    //更新可用Server列表
    UpdateServers(servers []*tool.Server)
}

后端Server定义：

type Server struct {
    //主机地址
    Host string
    //主机名		
    Name string		
    Weight int	
    //主机是否在线	
    Online bool		
}

算法实现：

type Weighted struct {
	Server 			*tool.Server
	Weight          int
	CurrentWeight   int
	EffectiveWeight int
}

func (this *Weighted) String() string {
	return fmt.Sprintf("[%s][%d]",this.Server.Host,this.Weight)
}

type LoadBalanceWeightedRoundRobin struct{
	servers []*tool.Server
	weighted []*Weighted
}

func NewLoadBalanceWeightedRoundRobin(servers []*tool.Server) *LoadBalanceWeightedRoundRobin{
	new:=&LoadBalanceWeightedRoundRobin{}
	new.UpdateServers(servers)
	return new
}

func (this *LoadBalanceWeightedRoundRobin) UpdateServers(servers []*tool.Server) {
	if len(this.servers)==len(servers) {
		for _,new:=range servers {
			isEqual:=false
			for _,old:=range this.servers {
				if new.Host==old.Host&&new.Weight==old.Weight&&new.Online==old.Online {
					isEqual=true
					break
				}
			}
			if isEqual==false {
				goto build
			}
		}
		return
	}

build:
	log.Debug("clients change")
	log.Debug(this.servers)
	log.Debug(servers)
	weighted:=make([]*Weighted,0)
	for _,v:=range servers {
		if v.Online==true {
			w:=&Weighted{
				Server:v,
				Weight:v.Weight,
				CurrentWeight:0,
				EffectiveWeight:v.Weight,
			}
			weighted=append(weighted,w)
		}
	}
	this.weighted=weighted
	this.servers=servers
	log.Debugf("weighted[%v]",this.weighted)
}

func (this *LoadBalanceWeightedRoundRobin) Select(remove []string) *tool.Server {
	if len(this.weighted)==0 {
		return nil
	}
	w:=this.nextWeighted(this.weighted,remove)
	if w==nil {
		return nil
	}
	return w.Server
}

func (this *LoadBalanceWeightedRoundRobin) nextWeighted(servers []*Weighted,remove []string) (best *Weighted) {
	total := 0
	for i := 0; i < len(servers); i++ {
		w:= servers[i]
		if w == nil {
			continue
		}
		isFind:=false
		for _,v:=range remove {
			if v==w.Server.Host {
				isFind=true
			}
		}
		if isFind==true{
			continue
		}

		w.CurrentWeight += w.EffectiveWeight
		total += w.EffectiveWeight
		if w.EffectiveWeight < w.Weight {
			w.EffectiveWeight++
		}

		if best == nil || w.CurrentWeight > best.CurrentWeight {
			best = w
		}
	}
	if best == nil {
		return nil
	}
	best.CurrentWeight -= total
	return best
}

func (this *LoadBalanceWeightedRoundRobin) String() string {
	return "WeightedRoundRobin"
}

测试：

func TestNewLoadBalanceWeightedRoundRobin(t *testing.T) {
	count:=make([]int,4)
	servers:=make([]*tool.Server,0)
	servers=append(servers,&tool.Server{Host:"0",Weight:10,Online:true})
	servers=append(servers,&tool.Server{Host:"1",Weight:20,Online:true})
	servers=append(servers,&tool.Server{Host:"2",Weight:30,Online:true})
	servers=append(servers,&tool.Server{Host:"3",Weight:40,Online:true})
	lb:=NewLoadBalanceWeightedRoundRobin(servers)

	for i:=0;i<100000;i++{
		s:=lb.Select(nil)
		id,_:=helper.StringToInt(s.Host)
		count[id]++
	}
	fmt.Println(count)
}
----------------------------------------------------
[10000 20000 30000 40000]

创建4个后端Server，权重分别为10、20、30、40，调用100000选择，结果为10000 20000 30000 40000，效果比较理想