码农戏码

新生代农民工的自我修养

0%

计数器算法

Posted on Edited on

《微服务-熔断机制》中提到了计数器，这篇详细学习一下计数器算法

之前的有次面试，碰到了计数器的的题目

Q：线上服务，设计一个拦截器，一个IP如果短时间内请求次数过多，就屏蔽

A：使用map，key为ip，值为次数与时间

Q：请求相当大，会直接冲垮内存,怎么办？

A：使用redis，像redis cluster，绝对可以满足

Q: 写下伪代码

A：bbbbbbb

其实计数器在互联网开发中很常见，当时刚转互联网比较无知，面试得很烂。

计数器法

计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，具体算法的示意图如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Counter {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        }
        else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
}

以上是示意代码，先忽视其中的并发问题，最大的问题是临界问题

从上图中我们可以看到，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

滑动窗口

滑动窗口，又称rolling window

在上图中，整个红色的矩形框表示一个时间窗口，在我们的例子中，一个时间窗口就是一分钟。然后我们将时间窗口进行划分，比如图中，我们就将滑动窗口 划成了6格，所以每格代表的是10秒钟。每过10秒钟，我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如当一个请求 在0:35秒的时候到达，那么0:30~0:39对应的counter就会加1。

那么滑动窗口怎么解决刚才的临界问题的呢？我们可以看上图，0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触 发了限流。

我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

实现一

根据上面滑动窗口的定义，实现很简单了

  1. 需要一个map,当然是并发安全的，key为时间
  2. 统计窗口内的请求总数

这儿有个以这种方式实现的
https://github.com/zhuxingsheng/yammer-metrics/blob/master/metrics-core/src/main/java/com/codahale/metrics/SlidingTimeWindowReservoir.java

摘点核心的片段：

1
2
3
//一个并发安全map,skip list有序
this.measurements = new ConcurrentSkipListMap<Long, Long>();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 获取map的key,以时间纳秒值为key
 * @return
 */
private long getTick() {
    for (; ; ) {
        final long oldTick = lastTick.get();
        //每纳秒处理的请求很多，减少compareAndSet的失败次数，这儿*COLLISION_BUFFER
        final long tick = clock.getTick() * COLLISION_BUFFER;
        // ensure the tick is strictly incrementing even if there are duplicate ticks
        final long newTick = tick > oldTick ? tick : oldTick + 1;
        if (lastTick.compareAndSet(oldTick, newTick)) {
            return newTick;
        }
    }
}
1
2
3
4
private void trim() {
        //清除window之前的计数
        measurements.headMap(getTick() - window).clear();
    }
缺点

实现简单，但有个问题，map的key是在不停的增加，删除，给GC带来了压力

实现二

考虑key的复用，使用环形结构

环形结构

通过取模来达到这个效果

初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int window; //计算窗口
//整个循环数组窗口
private int ringWindow=window+30; 


requestCounter = new AtomicInteger[ringWindow];
failedCounter = new AtomicInteger[ringWindow];
for (int i = 0; i < ringWindow; i++) {
	requestCounter[i] = new AtomicInteger(0);
	failedCounter[i] = new AtomicInteger(0);
}

initCounterTimeInSecond =
TimeUnit.NANOSECONDS.toSeconds(System.nanoTime());

计算窗口内的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private long countTotal(AtomicInteger[] caculateCounter){
		int currentIndex = getIndex();
		
		long sum = 0;
		
		for (int i = 0; i < window; i++) {
			//这儿并不是直接计算window中的所有counter，
			//而是从currentIndex向前倒取window个
			int index = ((currentIndex + ringWindow) -i) 
			% this.ringWindow;
			sum += caculateCounter[index].get();
		}
		return sum;
	}

为什么需要ringWindow，直接window就可以？这儿有个奇技淫巧。

1
2
3
4
5
6
7
8
9
10
11
CLEAN_UP_BUFFER=10;

public void cleanupFutureCounter() {
		int currentIndex = getIndex();
		
		for (int i = 1 ; i <= CLEAN_UP_BUFFER; i++) {
			int index = (currentIndex + i) % this.ringWindow;
			requestCounter[index].set(0);
			failedCounter[index].set(0);
		}
	}

这儿会有个定时任务，每5秒会去清空未来10秒的数据

因为在一环数组全部填充完成后，下一轮开始时，需要清空，哪个地方是起点，无法区分，所以ringwindow预留点位置用来清空

实现三

还有一些是加锁，当然会是轻量的CAS；每一个轮回完成后，都需要标记开始位置，并清空环。

漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

我们将算法中的水换成实际应用中的请求，我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法，我们可以保证接口会以一个常速速率来处理请求。所以漏桶算法天生不会出现临界问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeakyDemo {
public long timeStamp = getNowTime();
public int capacity; // 桶的容量
public int rate; // 水漏出的速度
public int water; // 当前水量(当前累积请求数)
public boolean grant() {
    long now = getNowTime();
    water = max(0, water - (now - timeStamp) * rate); // 先执行漏水，计算剩余水量
    timeStamp = now;
    if ((water + 1) < capacity) {
    // 尝试加水,并且水还未满
    water += 1;
    return true;
    }
    else {
    // 水满，拒绝加水
    return false;
    }
    }
}

令牌桶算法（Token Bucket）

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务

令牌桶算法

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class TokenBucketDemo {
public long timeStamp = getNowTime();
public int capacity; // 桶的容量
public int rate; // 令牌放入速度
public int tokens; // 当前令牌数量
public boolean grant() {
    long now = getNowTime();
    // 先添加令牌
    tokens = min(capacity, tokens + (now - timeStamp) * rate);
    timeStamp = now;
    if (tokens < 1) {
    // 若不到1个令牌,则拒绝
    return false;
    }
    else {
    // 还有令牌，领取令牌
    tokens -= 1;
    return true;
    }
    }
}

临界问题

我 们再来考虑一下临界问题的场景。在0:59秒的时候，由于桶内积满了100个token，所以这100个请求可以瞬间通过。但是由于token是以较低的 速率填充的，所以在1:00的时候，桶内的token数量不可能达到100个，那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问 题。

下图比较了计数器（左）和令牌桶算法（右）在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率，但是下一个突发速率必须要等桶内有足够的 token后才能发生：

Guava RateLimiter

在guava中，有现成的实现

RateLimiter使用的是一种叫令牌桶的流控算法，RateLimiter会按照一定的频率往桶里扔令牌，线程拿到令牌才能执行，比如你希望自己的应用程序QPS不要超过1000，那么RateLimiter设置1000的速率后，就会每秒往桶里扔1000个令牌。

有两种方式，SmoothBursty和SmoothWarmingUp

1
2
3
4
5
6
7
8
9
create(double permitsPerSecond)
根据指定的稳定吞吐率创建RateLimiter
这里的吞吐率是指每秒多少许可数（通常是指QPS，每秒多少查询）

create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)
根据指定的稳定吞吐率和预热期来创建RateLimiter
这里的吞吐率是指每秒多少许可数（通常是指QPS，每秒多少个请求量），
在这段预热时间内，
RateLimiter每秒分配的许可数会平稳地增长直到预热期结束时达到其最大速率。（只要存在足够请求数来使其饱和）

SmoothBursty通过平均速率和最后一次新增令牌的时间计算出下次新增令牌的时间的，另外需要一个桶暂存一段时间内没有使用的令牌（即可以突发的令牌数）。另外RateLimiter还提供了tryAcquire方法来进行无阻塞或可超时的令牌消费。

因为SmoothBursty允许一定程度的突发，会有人担心如果允许这种突发，假设突然间来了很大的流量，那么系统很可能扛不住这种突发。因此需要SmoothWarmingUp一种平滑速率的限流工具，从而系统冷启动后慢慢的趋于平均固定速率（即刚开始速率小一些，然后慢慢趋于我们设置的固定速率）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void testSmoothWarmingUp(){
        //每秒5个，1500ms后达到正常速率
        RateLimiter rateLimiter = RateLimiter.create(5,1500, TimeUnit.MILLISECONDS);

        List<Runnable> tasks = new ArrayList<Runnable>();
        for (int i = 0; i < 10; i++) {
            tasks.add(new Request(i));
        }

        ExecutorService executorService = Executors.newCachedThreadPool();
        for(Runnable task:tasks) {
            System.out.println("等待时间：" + rateLimiter.acquire());
            executorService.execute(task);
        }
        executorService.shutdown();

    }

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
等待时间：0.0
0 handle request 1528693920502
等待时间：0.54311
1 handle request 1528693921052
等待时间：0.433531
2 handle request 1528693921486
等待时间：0.332679
3 handle request 1528693921819
等待时间：0.229785
4 handle request 1528693922049
等待时间：0.199668
5 handle request 1528693922249
等待时间：0.199845
6 handle request 1528693922449
等待时间：0.199757
7 handle request 1528693922649
等待时间：0.19981
8 handle request 1528693922849
等待时间：0.199732
9 handle request 1528693923049

可以看出前面几个等待时间长，速度慢；1500ms后，速率达到正常的每秒5的速度

其实这算是一种漏桶算法的变异，在令牌桶中控制一个移除令牌的速度就是个漏桶了。

总结

计数器 VS 滑动窗口

计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。

令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法

参考

接口限流算法总结