05.15 限流算法之令牌桶算法、漏桶算法

首先我们要明白限流是什么?

限流定义

限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的请求进行限速来保护系统,一旦到达限制速率则可以拒绝服务(一般是定向到错误页或者告知资源不足)。

限流算法

限流算法之令牌桶算法、漏桶算法

令牌桶算法

声明一个固定容量的桶,然后固定的向这个桶添加令牌,具体算法如下:

  1. 假设限制2qps,那么按照每500ms向令牌桶添加令牌

  2. 同种最多存放b个令牌,当桶满了的时候,新添加的令牌丢弃

  3. 当一个有请求到达时,首先去令牌桶获取令牌,能够取到,则处理这个请求

  4. 如果桶中没有令牌,那么请求排队或者丢弃

漏桶算法

声明一个固定容量的桶,每接受到一个请求向桶中添加一个令牌,桶满请求丢弃,具体算法如下:


  1. 一个固定容量的漏桶,请求到达时向漏桶添加一个令牌

  2. 如果请求添加令牌不成功,请求丢弃

  3. 另一个线程以固定的速率消费桶里的令牌

对比

其实不难看出,漏桶算法允许一定的突发出现(当桶不满的时候),满载运行情况下两者的限流是一样的。


分享到:


相關文章: