当前位置： 漏桶算法 java实现-蚁群算法java实现cmd
限流是什么
顾名思义就是限制流量，也叫流量控制。限流是保护高并发系统的三把利器之一，其他两个是缓存和降级。
为什么限流
限流能起到保证系统稳定的作用，防止流量过大，导致资源不足，系统不稳定。
怎么限流
常见的限流算法：
固定窗口限流算法滑动窗口限流算法漏桶算法令牌桶算法
前两种都属于计数器限流。
计数器固定时间窗口
将时间划分为若干周期，使用计数器统计请求数。一个周期开始时，计数器清零重新计数，如果计数达到上限，则不会再响应多余的请求，直到进入下一个周期。
实现：固定窗口实现相对容易，如利用redis计数，过期时间为窗口长度。
示例代码：
/***
* 固定时间窗口限流简单实现，具体使用可根据需要用lua脚本改写，避免非原子性操作问题
*
* @param key 限流的key
* @param limit 一个时间窗口请求数的最大限制
* @param timeWindow 时间窗口的长度 单位：秒
* @return 是否达到限流
*/
public boolean tryAcquire(String key,int limit, int timeWindow){
try {
if (limit < 1){
limit = 1;
}
long res = redis.incr(key);
if (1L == res){
redis.expire(key,timeWindow);
}
if (limit >= res){
return true;
}
return false;
}catch (Exception e){
log.error("limit_redisError key:[{}]",key,e);
redis.del(key);
return true;
}
}缺点：限流过于粗略，有恢复空窗期, 在这个恢复时间内请求全部拒绝，同时也无法应对两个窗口临界时间内的流量。
例如：限制qps100，前一个窗口后半秒通过100个请求，紧接着的窗口前半秒又通过100个请求，实际中间这1秒的请求数到了200。
2. 滑动窗口
设定单位时间为一个窗口，将窗口拆分为多个小单元，随着时间的推移，窗口会向右移动，每次统计窗口内的请求数，判断是否达到限流条件。可以看出窗口拆分得越细，滑动窗口算法越平滑。
实现：这里我使用队列实现了一个简版的单机滑动窗口限流漏桶算法 java实现，可以使用lua脚本改写分布式版本。
public class SlidingWindow {
private volatile static Queue timeQueue = new LinkedList();
/***
* 滑动时间窗口限流单机简单实现
*
* @param limit 限制次数
* @param timeWindow 时间窗口大小
* @return 是否达到限流
*/
public static synchronized boolean tryAcquire(int limit, long timeWindow) {
long now = System.currentTimeMillis();
if (timeQueue.size() < limit) {
timeQueue.offer(now);
return true;
}
// 队列已满，获取最早入队的元素
long earliestTime = timeQueue.element();
if (now - earliestTime <= timeWindow) {
// 小于timeWindow，说明在时间窗口内，通过请求数大于limit，达到限流，返回false
return false;
}
// 大于timeWindow，说明队列中有不在timeWindow中的请求,也就是在timeWindow内，请求数小于limit
timeQueue.poll();
timeQueue.offer(now);
return true;
}
// 可以测试一下
public static void main(String[] args) throws Exception {
int c = 0;
while (true) {
if (++c > 100) {
break;
}
// 任意10秒内，只允许2次通过
System.out.println(LocalTime.now().toString() + "：" + tryAcquire(2, 10000L));
Thread.sleep(1000 * new Random().nextInt(10));
}
}
} 滑动窗口在阿里开源的Sentinel有实现应用，具体可以研究下Sentinel。
缺点：窗口内单元数不好评估，无法完全解决固定窗口的问题。
漏桶算法（leaky bucket）
当请求进来时，相当于水倒入漏斗，然后从下端小口慢慢匀速地流出。不管入口流量多大，出口流出的速度始终保持不变。 相比计数器在恢复期内全部拒绝请求, 漏斗桶则以一定的速率消费请求, 能够让后续的请求有机会进入到漏斗桶里面。
实现：可以参考 （出口速率不均匀）
缺点：无法短时间应对突发流量，因为当入口流量速度过大时, 漏斗会溢出, 同样会造成服务拒绝。
令牌桶算法（Token bucket）
系统以恒定的速率产生令牌，把令牌放到令牌桶中。令牌桶有一个容量，当令牌桶满了的时候，再向其中放令牌漏桶算法 java实现，那么多余的令牌就会被丢弃。当要处理一个请求的时候，需要从令牌桶中取出一个令牌，如果此时令牌桶中没有令牌，那么则拒绝该请求。
实现：guava采用的就是这种算法，具体可以看RateLimiter的实现。
RateLimiter源码解析可以看这篇：
上一篇 
