api-gateway中实现基于权重的轮询调度

api-gateway中实现基于权重的轮询调度

June 8, 2018
技术总结
Golang, Api-Gateway, Round-Robin, Weighted-Round-Robin

背景和目标 #

背景 #

项目需要在现有项目的基础上实现权限系统，但为了低耦合，选择实现了一个基于ne7ermore/gRBAC的auth-server，用于实现权限，角色，用户的管理，以及提供鉴权服务。在开发环境对接没有问题，正常的鉴权访问。到了线上部署的时候，才发现：

  1. 线上某服务部署在多台机器上;
  2. 目前的api-gateway并不支持同一服务配置多个node;

想的办法有：

序号 描述 优点 缺点
1 api-gateway通过url来转发请求，之前是配置IP加端口 api-gateway改动小 影响web和APP升级
2 api-gateway能支持多台机器，并进行调度 api-gateway功能更强大，把以后要做的事情提前做好基础 好像没啥缺点，只是费点时间支持下多节点配置，并调度

如果没说清，请看下图：

api-gateway-changing

目标 #

那么，目标也就明确了，需要实现api-gateway中实现基于权重的调度。为啥要基于权重？其一是仿照nginx基于权重的负载均衡，其二是服务器性能差异。

轮询调度算法介绍 #

轮询调度算法: #

轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N(内部服务器个数)，然后重新开始循环。该算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。

假设有一组服务器N台，S = {S1, S2, …, Sn}，一个指示变量i表示上一次选择的服务器ID。变量i被初始化为N-1。其算法如下：

j = i;
do {
  j = (j + 1) mod n;
  i = j;
  return Si;
} while (j != i);
return NULL;

平滑加权轮询调度算法： #

上述的轮询调度算法，并没有考虑服务器性能的差异，实际生产环境中，每一台服务器配置和安装的业务并不一定相同，处理能力不完全一样。因此需要根据服务器能力，分配不同的权值，以免服务的超负荷和过分闲余。

假设有一组服务器S = {S0, S1, …, Sn-1}, 其算法如下：

// i表示上一次选择的服务器，变量i初始化为-1
// W(Si)表示服务器Si的权值
// cw表示当前调度的权值 cw初始化为0
// max(S)表示集合S中所有服务器的最大权值
// gcd(S)表示集合S中所有服务器权值的最大公约数
while (true) {
  i = (i + 1) mod n;
  if (i == 0) {
     cw = cw - gcd(S);
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  }
  if (W(Si) >= cw)
    return Si;
}

Nginx基于权重的轮询算法的实现可以参考它的一次代码提交： Upstream: smooth weighted round-robin balancing。

它不但实现了基于权重的轮询算法，而且还实现了平滑的算法。所谓平滑，就是在一段时间内，不仅服务器被选择的次数的分布和它们的权重一致，而且调度算法还比较均匀的选择服务器，而不会集中一段时间之内只选择某一个权重比较高的服务器。如果使用随机算法选择或者普通的基于权重的轮询算法，就比较容易造成某个服务集中被调用压力过大。

举个例子，比如权重为{a:5, b:1, c:1)的一组服务器，Nginx的平滑的轮询算法选择的序列为{ a, a, b, a, c, a, a },这显然要比{ c, b, a, a, a, a, a }序列更平滑，更合理，不会造成对a服务器的集中访问。

在参考文献平滑的基于权重的调度算法中，作者给出了仿照nginxd的平滑权重轮询调度算法的Golang版本代码，还有一个weighted库自荐。这里做一个延伸～

贴一下测试测试代码及结果：

func Test_Init(t *testing.T) {
	servers := []*conf.ProxyServerConfig{
		{
			Schema: "http://",
			Host:   "127.0.0.1",
			Prefix: "/api",
			Port:   8808,
			Weight: 4,
		},
		{
			Schema: "http://",
			Host:   "127.0.0.1",
			Prefix: "/api",
			Port:   8808,
			Weight: 4,
		},
		{
			Schema: "http://",
			Host:   "127.0.0.1",
			Prefix: "/api",
			Port:   8808,
			Weight: 2,
		},
	}

	bla := InitBalancer(servers)

	cnt := 0
	mark := map[int]int{}

	for cnt < 10 {
		idx := bla.Distribute()
		t.Log(idx)

		mark[idx]++
		cnt++
	}
	t.Log(mark)
}
// === RUN   Test_Init
// --- PASS: Test_Init (0.00s)
// 	balance_test.go:45: 0
// 	balance_test.go:45: 1
// 	balance_test.go:45: 0
// 	balance_test.go:45: 1
// 	balance_test.go:45: 2
// 	balance_test.go:45: 0
// 	balance_test.go:45: 1
// 	balance_test.go:45: 0
// 	balance_test.go:45: 1
// 	balance_test.go:45: 2
// 	balance_test.go:50: map[0:4 1:4 2:2]
// 	在10次调度中，三个服务分别被调用了响应权重的次数，且顺序并不是[0,0,0,0,1,1,1,1,2,2]

调度器实现 #

算法讲完了，我就直接上代码了。

type Balancer struct {
	serverWeights map[int]int // host and weight
	maxWeight     int         // 0
	maxGCD        int         // 1
	lenOfSW       int         // 0
	i             int         //表示上一次选择的服务器, -1
	cw            int         //表示当前调度的权值, 0
}

// 根据服务配置初始化调度器
// conf.ProxyServerConfig 配置可以参见上述测试代码
func InitBalancer(servers []*conf.ProxyServerConfig) *Balancer {
	bla := &Balancer{
		serverWeights: make(map[int]int),
		maxWeight:     0,
		maxGCD:        1,
		lenOfSW:       len(servers),
		i:             -1,
		cw:            0,
	}

	_tmp_gcd := make([]int, 0, bla.lenOfSW)

	for idx, psc := range servers {
		bla.serverWeights[idx] = psc.Weight
		if psc.Weight > bla.maxWeight {
			bla.maxWeight = psc.Weight
		}
		_tmp_gcd = append(_tmp_gcd, psc.Weight)
	}

	// 求最大公约数
	bla.maxGCD = nGCD(_tmp_gcd, bla.lenOfSW)
	return bla
}

// 调度
func (bla *Balancer) Distribute() int {
	for true {
		bla.i = (bla.i + 1) % bla.lenOfSW

		if bla.i == 0 {
			bla.cw = bla.cw - bla.maxGCD
			if bla.cw <= 0 {
				bla.cw = bla.maxWeight
				if bla.cw == 0 {
					return 0
				}
			}
		}

		if bla.serverWeights[bla.i] >= bla.cw {
			return bla.i
		}
	}
	return 0
}

// 求最大公约数
func GCD(a, b int) int {
	if a < b {
		a, b = b, a // swap a & b
	}

	if b == 0 {
		return a
	}

	return GCD(b, a%b)
}

// N个数的最大公约数
func nGCD(data []int, n int) int {
	if n == 1 {
		return data[0]
	}
	return GCD(data[n-1], nGCD(data, n-1))
}

嵌入Api-Gateway #

已经实现了调度器，并测试妥当，那么如何实际放到网关服务中去呢？我先简单描述下，之前的服务是如何调用的。在Golang标准库里有一个东西叫做：

httputil.NewSingleHostReverseProxy 文档由此去

这就是本网关中主要用于请求转发的关键。在转发请求之前，我需要做的事就是：匹配本次请求应该转发给哪一个服务？大家都通过：api.xxx.com的域名来访问，但是对于不同的功能会有不同的路径前缀如："/api", “/auth”, “/res"等等。匹配完成，那么问题来了：我要转发给的服务有多个，咋个调度呢？这个位置就是我需要把调度器嵌入的位置，上代码：

type ProxyServer struct {
	// ... some other data
	Servers  map[string][]*conf.ProxyServerConfig
	Balancer map[string]*Balancer
}

func (ps *ProxyServer) InitBalancer() {
	for srv_name, srvs := range ps.Servers {
		ps.Balancer[srv_name] = InitBalancer(srvs)
	}
}

// 匹配需要转发的前缀
func (ps *ProxyServer) MatchProxy(path string, req *http.Request) (error, *url.URL) {
	for srv_name, srvs := range ps.Servers {
		// default set 0, to choose srvs to service
		srv := srvs[0]
		if strings.HasPrefix(path, srv.Prefix) {

			// load balance
			srv_idx := ps.Balancer[srv_name].Distribute()
			srv = srvs[srv_idx]

			_url := utils.Fstring("%s%s:%d", srv.Schema, srv.Host, srv.Port)
			remote, err := url.Parse(_url)
			if err != nil {
				return err, nil
			}
			req.URL.Path = strings.TrimPrefix(path, srv.Prefix)
			return nil, remote
		}
	}
	return errors.New("did not match any proxy server"), nil
}

至此，也就完成了在api-gateway中嵌入基于权重的轮询调度。

注 #

用词表述不当，还望谅解并及时告知。其次没有过多的分析算法是如何设计的，这并非我所擅长，也不是本文的重点～ 以上

参考文献 #

访问量 访客数