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

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

// 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;
}

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))
}

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
}