Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现

时间:2022-01-12 来源:未知网络 作者:996建站网

要说现在工程师最重要的能力,我觉得工程能力要排第一。

就算现在大厂面试经常要手撕算法,也是更偏向考查代码工程实现的能力,之前在群里看到这样的图片,就觉得很离谱(大概率是假的~)。

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图

算法与工程实现

在 Sentinel-Go 中,一个很核心的算法是流控(限流)算法。

流控可能每个人都听过,但真要手写一个,还是有些困难。为什么流控算法难写?以我的感觉是算法和工程实现上存在一定差异,虽然算法好理解,但却没法照着实现。

举个例子,令牌桶算法很好理解,只需给定一个桶,以恒定的速率往桶内放令牌,满了则丢弃,执行任务前先去桶里拿令牌,只有拿到令牌才可以执行,否则拒绝。

如果实现令牌桶,按道理应该用一个单独线程(或进程)往桶里放令牌,业务线程去桶里取,但真要这么实现,怎么保证这个单独线程能稳定执行,万一挂了岂不是很危险?

所以工程实现上和算法原本肯定存在一定的差异,这也是为什么需要深入源码的一个原因。

滑动时间窗口的演进

通常来说,流控的度量是按每秒的请求数,也就是 QPS

QPS:query per second,指每秒查询数,当然他的意义已经泛化了,不再特指查询,可以泛指所有请求。如果非要区分,TPS 指每秒事务数,即写入数,或 RPS,每秒请求数,本文不分这么细,统一叫QPS。

当然也有按并发数来度量,并发数的流控就非常简单

并发数流控

并发是一个瞬时概念,它跟时间没有关系。和进程中的线程数、协程数一样,每次取的时候只能拿到一个瞬间的快照,但可能很快就变化了。

并发数怎么定义?可以近似认为进入业务代码开始就算一个并发,执行完这个并发就消失。

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图

这样说来,实现就非常简单了,只需要定义一个全局变量,责任链开始时对这个变量原子增1,并获取当前并发数的一个快照,判断并发数是否超限,如果超限则直接阻断,执行完了别忘了原子减1即可,由于太过简单,就不需要放代码了。

固定时间窗口

参考并发数流控,当需要度量 QPS 时,是否也可以利用这样的思想呢?

由于 QPS 有时间的度量,第一直觉是和并发数一样弄个变量,再起个单独线程每隔 1s 重置这个变量。

但单独线程始终不放心,需要稍微改一下。

如果系统有一个起始时间,每次请求时,获取当前时间,两者之差,就能算出当前处于哪个时间窗口,这个时间窗口单独计数即可。

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图1

如果稍微思考下,你会发现问题不简单,如下图,10t 到20t 只有60个请求,20t到30t之间只有80个请求,但有可能16t到26t之间有110个请求,这就很有可能把系统打垮。

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图1

滑动时间窗口

为了解决上面的问题,工程师想出了一个好办法:别固定时间窗口,以当前时间往前推算窗口

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图1

但问题又来了,这该怎么实现呢?

滑动时间窗口工程实现

在工程实现上,可以将时间划分为细小的采样窗口,缓存一段时间的采样窗口,这样每当请求来的时候,只需要往前拿一段时间的采样窗口,然后求和就能拿到总的请求数。

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图1

Sentinel-Go 滑动时间窗口的实现

前方代码高能预警~

Sentinel-Go 是基于 LeapArray 实现的滑动窗口,其数据结构如下

type LeapArray struct {
 bucketLengthInMs uint32 // bucket大小
 sampleCount      uint32 // bucket数量
 intervalInMs     uint32 // 窗口总大小
 array            *AtomicBucketWrapArray // bucket数组
 updateLock mutex // 更新锁
}

type AtomicBucketWrapArray struct {
 base unsafe.Pointer // 数组的起始地址
 length int // 长度,不能改变
 data   []*BucketWrap // 真正bucket的数据
}

type BucketWrap struct {
 BucketStart uint64 // bucket起始时间
 Value atomic.Value // bucket数据结构,例如 MetricBucket
}

type MetricBucket struct {
 counter        [base.MetricEventTotal]int64 // 计数数组,可放不同类型
 minRt          int64 // 最小RT
 maxConcurrency int32 // 最大并发数
}

Sentinel-Go 源码系列(三)滑动时间窗口算法的工程实现插图2

微信扫一扫 关注公众号

微信扫一扫 使用小程序

百度扫一扫 使用小程序