负载均衡算法

1.引言

负载均衡,英文是load balance,意思是将请求请求或数据分摊到多个单元上操作。尤其是针对现在的服务集群部署模式,如何将客户端的请求转发到服务器,达到资源最佳化使用、减少响应时间、提高吞吐量等目的。本文将介绍几种常用的负载均衡算法。

2.随机分配

将请求随机分配到各个节点,从概率统计理论而已,客户端调用的次数越多,每个节点被分配的次数越来越接近平均值,达到了轮询的结果.

func randStrategy() {
   nodes := []string{"A", "B", "C", "D", "E"} // 假设有5个节点
   nodeLength := len(nodes)
   nodeStatistics := make(map[string]int, nodeLength)
   rand.Seed(time.Now().UnixNano())
   for i := 0; i < 100000; i++ {
      selectIndex := rand.Intn(nodeLength) // 每次随机选择一个节点
      node := nodes[selectIndex]
      nodeStatistics[node]++
   }
   for node, count := range nodeStatistics {
      fmt.Printf("node: %s, count: %d\n", node,count)
   }
}

// output
node: B, count: 20167
node: D, count: 19985
node: A, count: 20000
node: C, count: 19960
node: E, count: 19888
复制代码

对于10万调用次数,此时每个节点被选中的次数相差不是很大,趋向于平均值。

3.轮询分配

将请求按顺序分配到每个节点上,不关心每个节点的实际连接数量和系统负载。

func roundRobin()  {
   nodes := []string{"A", "B", "C", "D", "E"}
   nodeLength := len(nodes)
   nodeStatistics := make(map[string]int, nodeLength)
   for i := 0; i < 100000; i++ {
      selectIndex := i % len(nodes)
      node := nodes[selectIndex]
      nodeStatistics[node]++
   }
   for node, count := range nodeStatistics {
      fmt.Printf("node: %s, count: %d\n", node,count)
   }
}

// output
node: A, count: 20000
node: B, count: 20000
node: C, count: 20000
node: D, count: 20000
node: E, count: 20000
复制代码

不考虑每个节点的实际处理能力,集群性能瓶颈在于处理较慢的节点。

4.带权重的轮询分配

不同后端节点的实际负载能力可能不一致,因此,需要给负载能力高的机器更高的权重,使其能处理更多的请求,从而达到集群整体的负载均衡。

func roundRobinWithWeight()  {
   nodes := []string{"A", "B", "C", "D", "E"}
   weights := []int{1,2,3,4,5}  // 每个节点的权重
   nodeLength := len(nodes)
   nodeStatistics := make(map[string]int, nodeLength)
   var sumWeight int
   preWightSum := make([]int, len(weights))
   for i, weight := range weights {
      sumWeight += weight
      preWightSum[i] = sumWeight
   }
   selectNodes := make([]string, 100)
   for i := 0; i < 30; i++ {
      selectIndex := i  % sumWeight + 1 // 加1是因为preWeightSum的起始值不是0
      nodeIndex := binarySearch(preWightSum, selectIndex)
      node := nodes[nodeIndex]
      selectNodes[i] = node
      nodeStatistics[node]++
   }
   fmt.Println(selectNodes)
   for node, count := range nodeStatistics {
      fmt.Printf("node: %s, count: %d\n", node,count)
   }
}

func binarySearch(array []int, target int) int {
   left, right := 0, len(array) - 1
   for left <= right {
      middle := left + (right - left) >> 1
      if array[middle] == target{
         return middle
      }
      if array[middle] < target{
         left = middle + 1
      } else {
         right = middle - 1
      }
   }
   return  left
}

// output
[A B B C C C D D D D E E E E E A B B C C C D D D D E E E E E] // 可以看出来,节点被选中的次数与其权重成正比。
node: D, count: 8
node: E, count: 10
node: A, count: 2
node: B, count: 4
node: C, count: 6
复制代码

这种算法有一个缺点:不够平滑,连续的请求打在同一个节点上,导致权重低的节点处于空闲状态,没有平滑分配请求。