目录
固定窗口算法滑动窗口算法漏桶算法令牌桶算法分布式限流固定窗口算法
固定窗口算法又叫做计数器算法
,主要通过一个支持原子操作
的计数器来累计 1 秒内的请求次数,当 1 秒内计数达到限流阈值时触发拒绝策略。每过 1 秒,计数器重置为 0 开始重新计数。
存在不足:
滑动窗口算法
滑动窗口算法是对固定窗口算法的改进, 和算法题里所涉及到的滑动窗口算法一样的
漏桶算法
漏桶算法,又称leaky bucket
一个系统处理请求,就像一个固定容量的水桶去溜进来的水,同时也让水流出去,但是它无法预见有多少水流进来和水流进来的速度,它只能够控制从桶底水流出去的速度,多出来的水,就只好让它从桶边流出去了。这个从桶底流出去的水就是系统正常处理的请求,从旁边流出去的水就是系统拒绝掉的请求
伪代码
when(b)bt := nowWb = (bt - at) * rateW= max(W - Wb, 0)if W < brust W++return trueelsereturn false
令牌桶算法
系统匀速的产生令牌存放到令牌桶中;令牌桶的容量固定,当令牌桶填满后,再放入其中的令牌会被丢弃;每个请求从令牌桶中获取令牌,如果获取成功则处理请求,如果失败则丢弃请求。伪代码
// 上一次请求为a,本次请求为bwhen(b):bTime := now()Wb = (bTime - aTime) * rateW = min(W + Wb, C)if W > requestedW -= requestedreturn trueelsereturn false
go-zero内置的限流
https://go-zero.dev/cn/docs/blog/governance/tokenlimit
分布式限流
分布式限流就是把原来单体的限流拿到集群场景,对整个集群进行整体的限流。
为了保证并发安全和原子性,一般会使用Redis + lua脚本实现
参考
/post/7075137592265539614
/video/BV1cs411V73Y
/p/9f7df2ebbb82
如果觉得《限流算法分布式限流》对你有帮助,请点赞、收藏,并留下你的观点哦!