自适应微服务治理背后的算法

前言

go-zero 群里常常有同窗问：git

服务监控是经过什么算法实现的？github

滑动窗口是怎么工做的？可否讲讲这块的原理？redis

熔断算法是怎么设计的？为啥没有半开半闭状态呢？算法

本篇文章，来分析一下 go-zero 中指标统计背后的实现算法和逻辑。数据库

指标怎么统计

这个咱们直接看 breaker ：微信

type googleBreaker struct {
  k     float64
  stat  *collection.RollingWindow
  proba *mathx.Proba
}

go-zero 中默认的 breaker 是以 google SRE 作为实现蓝本。

当 breaker 在拦截请求过程当中，会记录当前这类请求的成功/失败率：数据结构

func (b *googleBreaker) doReq(req func() error, fallback func(err error) error, acceptable Acceptable) error {
  ...
  // 执行实际请求函数
  err := req()
  if acceptable(err) {
    // 实际执行：b.stat.Add(1)
    // 也就是说：内部指标统计成功+1
    b.markSuccess()
  } else {
    // 原理同上
    b.markFailure()
  }

  return err
}

因此其实底层说白了就是：请求执行完毕，会根据错误发生次数，内部的统计数据结构会相应地加上统计值(可正可负)。同时随着时间迁移，统计值也须要随时间进化。框架

简单来讲：时间序列内存数据库【也没数据库这么猛，就是一个存储，只是一个内存版的】函数

下面就来讲说这个时间序列用什么数据结构组织的。微服务

滑动窗口

咱们来看看 rollingwindow 定义数据结构：

type RollingWindow struct {
    lock          sync.RWMutex
    size          int
    win           *window
    interval      time.Duration
    offset        int
    ignoreCurrent bool
    lastTime      time.Duration
  }

上述结构定义中，window 就存储指标记录属性。

在一个 rollingwindow 包含若干个桶（这个看开发者本身定义）：

每个桶存储了：Sum 成功总数，Count 请求总数。因此在最后 breaker 作计算的时候，会将 Sum 累计加和为 accepts，Count 累计加和为 total，从而能够统计出当前的错误率。

滑动是怎么发生的

首先对于 breaker 它是须要统计单位时间（好比1s）内的请求状态，对应到上面的 bucket 咱们只须要将单位时间的指标数据记录在这个 bucket 便可。

那咱们怎么保证在时间前进过程当中，指定的 Bucket 存储的就是单位时间内的数据？

第一个想到的方式：后台开一个定时器，每隔单位时间就建立一个 bucket ，而后当请求时当前的时间戳落在 bucket 中，记录当前的请求状态。周期性建立桶会存在临界条件，数据来了，桶还没建好的矛盾。

第二个方式是：惰性建立 bucket，当遇到一个数据再去检查并建立 bucket。这样就有时有桶有时没桶，并且会大量建立 bucket，咱们是否能够复用呢？

go-zero 的方式是：rollingwindow 直接预先建立，请求的当前时间经过一个算法肯定到bucket ，并记录请求状态。

下面看看 breaker 调用 b.stat.Add(1) 的过程：

func (rw *RollingWindow) Add(v float64) {
  rw.lock.Lock()
  defer rw.lock.Unlock()
  // 滑动的动做发生在此
  rw.updateOffset()
  rw.win.add(rw.offset, v)
}

func (rw *RollingWindow) updateOffset() {
  span := rw.span()
  if span <= 0 {
    return
  }

  offset := rw.offset
  // 重置过时的 bucket
  for i := 0; i < span; i++ {
    rw.win.resetBucket((offset + i + 1) % rw.size)
  }

  rw.offset = (offset + span) % rw.size
  now := timex.Now()
  // 更新时间
  rw.lastTime = now - (now-rw.lastTime)%rw.interval
}

func (w *window) add(offset int, v float64) {
  // 往执行的 bucket 加入指定的指标
  w.buckets[offset%w.size].add(v)
}

上图就是在 Add(delta) 过程当中发生的 bucket 发生的窗口变化。解释一下：

1. updateOffset 就是作 bucket 更新，以及肯定当前时间落在哪一个 bucket 上【超过桶个数直接返回桶个数】，将其以前的 bucket 重置

   • 肯定当前时间相对于 bucket interval的跨度【超过桶个数直接返回桶个数】
   • 将跨度内的 bucket 都清空数据。reset
   • 更新 offset，也是即将要写入数据的 bucket
   • 更新执行时间 lastTime，也给下一次移动作一个标志
2. 由上一次更新的 offset，向对应的 bucket 写入数据

而在这个过程当中，如何肯定肯定 bucket 过时点，以及更新时间。滑动窗口最重要的就是时间更新，下面用图来解释这个过程：

而 bucket 过时点，说白就是 lastTime 即上一个更新时间跨越了几个 bucket：timex.Since(rw.lastTime) / rw.interval

这样，在 Add() 的过程当中，经过 lastTime 和 nowTime 的标注，经过不断重置来实现窗口滑动，新的数据不断补上，从而实现窗口计算。

总结

本文分析了 go-zero 框架中的指标统计的基础封装、滑动窗口的实现 rollingWindow。固然，除此以外，store/redis 也存在指标统计，这个里面的就不须要滑动窗口计数了，由于自己只须要计算命中率，命中则对 hit +1，不命中则对 miss +1 便可，分指标计数，最后统计一下就知道命中率。

滑动窗口适用于流控中对指标进行计算，同时也能够作到控流。

关于 go-zero 更多的设计和实现文章，能够关注『微服务实践』公众号。

项目地址

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

欢迎使用 go-zero 并 star 支持咱们！

微信交流群

关注『微服务实践』公众号并点击 交流群 获取社区群二维码。

go-zero 系列文章见『微服务实践』公众号