自適應(yīng)負(fù)載均衡算法原理與實(shí)現(xiàn)

背景

在選擇負(fù)載均衡算法時(shí)，我們希望滿足以下要求：

  1. 具備分區(qū)和機(jī)房調(diào)度親和性
    • 每次選擇的節(jié)點(diǎn)盡量是負(fù)載最低的
    • 每次盡可能選擇響應(yīng)最快的節(jié)點(diǎn)
  2. 無需人工干預(yù)故障節(jié)點(diǎn)
    • 當(dāng)一個(gè)節(jié)點(diǎn)有故障時(shí)，負(fù)載均衡算法可以自動(dòng)隔離該節(jié)點(diǎn)
    • 當(dāng)故障節(jié)點(diǎn)恢復(fù)時(shí)，能夠自動(dòng)恢復(fù)對(duì)該節(jié)點(diǎn)的流量分發(fā)

基于這些考慮，go-zero 選擇了 p2c+EWMA 算法來實(shí)現(xiàn)。

算法的核心思想

p2c

p2c (Pick Of 2 Choices) 二選一: 在多個(gè)節(jié)點(diǎn)中隨機(jī)選擇兩個(gè)節(jié)點(diǎn)。

go-zero 中的會(huì)隨機(jī)的選擇3次，如果其中一次選擇的節(jié)點(diǎn)的健康條件滿足要求，就中斷選擇，采用這兩個(gè)節(jié)點(diǎn)。

EWMA

EWMA (Exponentially Weighted Moving-Average) 指數(shù)移動(dòng)加權(quán)平均法: 是指各數(shù)值的加權(quán)系數(shù)隨時(shí)間呈指數(shù)遞減，越靠近當(dāng)前時(shí)刻的數(shù)值加權(quán)系數(shù)就越大，體現(xiàn)了最近一段時(shí)間內(nèi)的平均值。

  • 公式:

    EWMA公式

  • 變量解釋:

    • Vt: 代表的是第 t 次請(qǐng)求的 EWMA值
    • Vt-1: 代表的是第 t-1 次請(qǐng)求的 EWMA值
    • β: 是一個(gè)常量

EWMA 算法的優(yōu)勢

  1. 相較于普通的計(jì)算平均值算法，EWMA 不需要保存過去所有的數(shù)值，計(jì)算量顯著減少，同時(shí)也減小了存儲(chǔ)資源。
  2. 傳統(tǒng)的計(jì)算平均值算法對(duì)網(wǎng)絡(luò)耗時(shí)不敏感, 而 EWMA 可以通過請(qǐng)求頻繁來調(diào)節(jié) β，進(jìn)而迅速監(jiān)控到網(wǎng)絡(luò)毛刺或更多的體現(xiàn)整體平均值。
    • 當(dāng)請(qǐng)求較為頻繁時(shí), 說明節(jié)點(diǎn)網(wǎng)絡(luò)負(fù)載升高了, 我們想監(jiān)測到此時(shí)節(jié)點(diǎn)處理請(qǐng)求的耗時(shí)(側(cè)面反映了節(jié)點(diǎn)的負(fù)載情況), 我們就相應(yīng)的調(diào)小β。β越小，EWMA值 就越接近本次耗時(shí)，進(jìn)而迅速監(jiān)測到網(wǎng)絡(luò)毛刺;
    • 當(dāng)請(qǐng)求較為不頻繁時(shí), 我們就相對(duì)的調(diào)大β值。這樣計(jì)算出來的 EWMA值 越接近平均值

β計(jì)算

go-zero 采用的是牛頓冷卻定律中的衰減函數(shù)模型計(jì)算 EWMA 算法中的 β 值:

牛頓冷卻定律中的衰減函數(shù)

其中 Δt 為兩次請(qǐng)求的間隔，e，k 為常數(shù)

gRPC 中實(shí)現(xiàn)自定義負(fù)載均衡器

  1. 首先我們需要實(shí)現(xiàn) google.golang.org/grpc/balancer/base/base.go/PickerBuilder 接口, 這個(gè)接口是有服務(wù)節(jié)點(diǎn)更新的時(shí)候會(huì)調(diào)用接口里的Build方法

    type PickerBuilder interface {
    // Build returns a picker that will be used by gRPC to pick a SubConn.
    Build(info PickerBuildInfo) balancer.Picker
}

  2. 還要實(shí)現(xiàn) google.golang.org/grpc/balancer/balancer.go/Picker 接口。這個(gè)接口主要實(shí)現(xiàn)負(fù)載均衡，挑選一個(gè)節(jié)點(diǎn)供請(qǐng)求使用

    type Picker interface {
  Pick(info PickInfo) (PickResult, error)
}

  3. 最后向負(fù)載均衡 map 中注冊我們實(shí)現(xiàn)的負(fù)載均衡器

go-zero 實(shí)現(xiàn)負(fù)載均衡的主要邏輯

  1. 在每次節(jié)點(diǎn)更新，gRPC 會(huì)調(diào)用 Build 方法，此時(shí)在 Build 里實(shí)現(xiàn)保存所有的節(jié)點(diǎn)信息。
  2. gRPC 在獲取節(jié)點(diǎn)處理請(qǐng)求時(shí)，會(huì)調(diào)用 Pick 方法以獲取節(jié)點(diǎn)。go-zero 在 Pick 方法里實(shí)現(xiàn)了 p2c 算法，挑選節(jié)點(diǎn)，并通過節(jié)點(diǎn)的 EWMA值 計(jì)算負(fù)載情況，返回負(fù)載低的節(jié)點(diǎn)供 gRPC 使用。
  3. 在請(qǐng)求結(jié)束的時(shí)候 gRPC 會(huì)調(diào)用 PickResult.Done 方法，go-zero 在這個(gè)方法里實(shí)現(xiàn)了本次請(qǐng)求耗時(shí)等信息的存儲(chǔ)，并計(jì)算出了 EWMA值 保存了起來，供下次請(qǐng)求時(shí)計(jì)算負(fù)載等情況的使用。

負(fù)載均衡代碼分析

  1. 保存服務(wù)的所有節(jié)點(diǎn)信息

    我們需要保存節(jié)點(diǎn)處理本次請(qǐng)求的耗時(shí)、EWMA 等信息，go-zero 給每個(gè)節(jié)點(diǎn)設(shè)計(jì)了如下結(jié)構(gòu)：

    type subConn struct {
    addr     resolver.Address
    conn     balancer.SubConn
    lag      uint64 // 用來保存 ewma 值
    inflight int64  // 用在保存當(dāng)前節(jié)點(diǎn)正在處理的請(qǐng)求總數(shù)
    success  uint64 // 用來標(biāo)識(shí)一段時(shí)間內(nèi)此連接的健康狀態(tài)
    requests int64  // 用來保存請(qǐng)求總數(shù)
    last     int64  // 用來保存上一次請(qǐng)求耗時(shí), 用于計(jì)算 ewma 值
    pick     int64  // 保存上一次被選中的時(shí)間點(diǎn)
}

  2. p2cPicker 實(shí)現(xiàn)了 balancer.Picker 接口，conns 保存了服務(wù)的所有節(jié)點(diǎn)信息

    type p2cPicker struct {
  conns []*subConn  // 保存所有節(jié)點(diǎn)的信息 
  r     *rand.Rand
  stamp *syncx.AtomicDuration
  lock  sync.Mutex
}

  3. gRPC 在節(jié)點(diǎn)有更新的時(shí)候會(huì)調(diào)用 Build 方法，傳入所有節(jié)點(diǎn)信息，我們在這里把每個(gè)節(jié)點(diǎn)信息用 subConn 結(jié)構(gòu)保存起來。并歸并到一起用 p2cPicker 結(jié)構(gòu)保存起來

    func (b *p2cPickerBuilder) Build(info base.PickerBuildInfo) balancer.Picker {
  ......
  var conns []*subConn
  for conn, connInfo := range readySCs {
    conns = append(conns, &subConn{
      addr:    connInfo.Address,
      conn:    conn,
      success: initSuccess,
    })
  }
  return &p2cPicker{
    conns: conns,
    r:     rand.New(rand.NewSource(time.Now().UnixNano())),
    stamp: syncx.NewAtomicDuration(),
  }
}

  4. 隨機(jī)挑選節(jié)點(diǎn)信息，在這里分了三種情況:

    1. 只有一個(gè)服務(wù)節(jié)點(diǎn)，此時(shí)直接返回供 gRPC 使用即可
    2. 有兩個(gè)服務(wù)節(jié)點(diǎn)，通過 EWMA值 計(jì)算負(fù)載，并返回負(fù)載低的節(jié)點(diǎn)返回供 gRPC 使用
    3. 有多個(gè)服務(wù)節(jié)點(diǎn)，此時(shí)通過 p2c 算法選出兩個(gè)節(jié)點(diǎn)，比較負(fù)載情況，返回負(fù)載低的節(jié)點(diǎn)供 gRPC 使用

    主要實(shí)現(xiàn)代碼如下：

    switch len(p.conns) {
  case 0:// 沒有節(jié)點(diǎn)，返回錯(cuò)誤
    return emptyPickResult, balancer.ErrNoSubConnAvailable
  case 1:// 有一個(gè)節(jié)點(diǎn)，直接返回這個(gè)節(jié)點(diǎn)
    chosen = p.choose(p.conns[0], nil)
  case 2:// 有兩個(gè)節(jié)點(diǎn)，計(jì)算負(fù)載，返回負(fù)載低的節(jié)點(diǎn)
    chosen = p.choose(p.conns[0], p.conns[1])
  default:// 有多個(gè)節(jié)點(diǎn)，p2c 挑選兩個(gè)節(jié)點(diǎn)，比較這兩個(gè)節(jié)點(diǎn)的負(fù)載，返回負(fù)載低的節(jié)點(diǎn)
    var node1, node2 *subConn
        // 3次隨機(jī)選擇兩個(gè)節(jié)點(diǎn)
    for i := 0; i < pickTimes; i++ {
      a := p.r.Intn(len(p.conns))
      b := p.r.Intn(len(p.conns) - 1)
      if b >= a {
        b++
      }
      node1 = p.conns[a]
      node2 = p.conns[b]
      // 如果這次選擇的節(jié)點(diǎn)達(dá)到了健康要求, 就中斷選擇
      if node1.healthy() && node2.healthy() {
        break
      }
    }
    // 比較兩個(gè)節(jié)點(diǎn)的負(fù)載情況，選擇負(fù)載低的
    chosen = p.choose(node1, node2)
  }

  5. load計(jì)算節(jié)點(diǎn)的負(fù)載情況

    上面的 choose 方法會(huì)調(diào)用 load 方法來計(jì)算節(jié)點(diǎn)負(fù)載。

    計(jì)算負(fù)載的公式是: load = ewma * inflight

    在這里簡單解釋下： ewma 相當(dāng)于平均請(qǐng)求耗時(shí)，inflight 是當(dāng)前節(jié)點(diǎn)正在處理請(qǐng)求的數(shù)量，相乘大致計(jì)算出了當(dāng)前節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載。

    func (c *subConn) load() int64 {
  // 通過 EWMA 計(jì)算節(jié)點(diǎn)的負(fù)載情況； 加 1 是為了避免為 0 的情況
  lag := int64(math.Sqrt(float64(atomic.LoadUint64(&c.lag) + 1)))
  load := lag * (atomic.LoadInt64(&c.inflight) + 1)
  if load == 0 {
    return penalty
  }
  return load
}

  6. 請(qǐng)求結(jié)束，更新節(jié)點(diǎn)的 EWMA 等信息

    1. 把節(jié)點(diǎn)正在處理請(qǐng)求的總數(shù)減1
    2. 保存處理請(qǐng)求結(jié)束的時(shí)間點(diǎn)，用于計(jì)算距離上次節(jié)點(diǎn)處理請(qǐng)求的差值，并算出 EWMA 中的 β值
    3. 計(jì)算本次請(qǐng)求耗時(shí)，并計(jì)算出 EWMA值 保存到節(jié)點(diǎn)的 lag 屬性里
    4. 計(jì)算節(jié)點(diǎn)的健康狀態(tài)保存到節(jié)點(diǎn)的 success 屬性中
    func (p *p2cPicker) buildDoneFunc(c *subConn) func(info balancer.DoneInfo) {
  start := int64(timex.Now())
  return func(info balancer.DoneInfo) {
    // 正在處理的請(qǐng)求數(shù)減 1
    atomic.AddInt64(&c.inflight, -1)
    now := timex.Now()
    // 保存本次請(qǐng)求結(jié)束時(shí)的時(shí)間點(diǎn)，并取出上次請(qǐng)求時(shí)的時(shí)間點(diǎn)
    last := atomic.SwapInt64(&c.last, int64(now))
    td := int64(now) - last
    if td < 0 {
      td = 0
    }
    // 用牛頓冷卻定律中的衰減函數(shù)模型計(jì)算EWMA算法中的β值
    w := math.Exp(float64(-td) / float64(decayTime))
    // 保存本次請(qǐng)求的耗時(shí)
    lag := int64(now) - start
    if lag < 0 {
      lag = 0
    }
    olag := atomic.LoadUint64(&c.lag)
    if olag == 0 {
      w = 0
    }
    // 計(jì)算 EWMA 值
    atomic.StoreUint64(&c.lag, uint64(float64(olag)*w+float64(lag)*(1-w)))
    success := initSuccess
    if info.Err != nil && !codes.Acceptable(info.Err) {
      success = 0
    }
    osucc := atomic.LoadUint64(&c.success)
    atomic.StoreUint64(&c.success, uint64(float64(osucc)*w+float64(success)*(1-w)))

    stamp := p.stamp.Load()
    if now-stamp >= logInterval {
      if p.stamp.CompareAndSwap(stamp, now) {
        p.logStats()
      }
    }
  }
}

項(xiàng)目地址

https://github.com/tal-tech/go-zero

歡迎使用 go-zero 并 star 支持我們！

微信交流群

關(guān)注『微服務(wù)實(shí)踐』公眾號(hào)并點(diǎn)擊 交流群 獲取社區(qū)群二維碼。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容