限流

限流算法

令牌桶算法

有一个装有固定容量令牌的大桶,按照固定速率往桶里添加令牌,当装满时,新添加的令牌被拒绝添加;当一个n字节大小的数据包到达时,如果桶内令牌数大于n,从桶中删除n个令牌,放数据包通过,如果桶中令牌数不足n个,不会删除令牌,且该数据包被限流(丢弃,或进入缓冲队列等待)

使用Guava提供的令牌桶实现:

1
2
3
4
RateLimiter limiter = RateLimiter.create(5); // 桶容量为5,且每秒增加5个令牌
for (int i=0; i<5; i++)
// 消费一个令牌,如果桶中有足够的令牌,成功,返回0;如果桶中没有令牌,暂停一段时间直到桶中有令牌
System.out.println(limiter.acquire());

令牌桶允许一下全部取走所有令牌,也可以消费未来的令牌,这样系统可能扛不住瞬间很大的突发请求

1
2
3
4
5
RateLimiter limiter = RateLimiter.create(5);
System.out.println(limiter.acquire(10)); // 0.0 消费了未来的令牌
System.out.println(limiter.acquire()); // 1.996597 由于没有令牌,要等待产生令牌
System.out.println(limiter.acquire()); // 0.18827 0.2 秒产生一个令牌
System.out.println(limiter.acquire()); // 0.198813

漏桶算法

有一个固定容量的漏桶,按照常量速率流出水滴,流出水滴相当于处理请求;如果水空了,不会流出;当有请求来时,流入水,如果水满了,新流入的请求被拒绝;

令牌桶和漏桶的区别:

令牌桶限制的是流入速率(固定值),允许突发请求,只要有足够的令牌即可;

漏桶限制的是流出速率,流出水滴意味着处理请求,可以平滑突发流入速率;

应用级限流

可以从以下方面考虑:

  • 限制总并发,连接数,请求数

  • 限制总资源数:如线程池,连接池

  • 限制某个接口的总并发/请求数(粒度更细)

  • 限制某个接口的时间窗请求数:每秒(分钟,天)请求数

    使用GuavaCache存储计数器,过期时间为2秒,保证能够存储1秒以内访问数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void main(String[] args) throws Exception {
LoadingCache<Long, AtomicLong> counter = CacheBuilder.newBuilder()
.expireAfterWrite(2, TimeUnit.SECONDS)
.build(new CacheLoader<Long, AtomicLong>() {
@Override
public AtomicLong load(Long aLong) throws Exception {
return new AtomicLong(0);
}
});
long limit = 95; // 每秒请求最大次数
int turn = 0; // 测试中发送的请求次数
Random r = new Random();
while (turn < 1000) {
long currentSeconds = System.currentTimeMillis() / 1000;
// 发送一次请求,记录时间,统计1秒内的次数,并判断是否需要限流
if (counter.get(currentSeconds).incrementAndGet() > limit) {
System.out.println("当前" + currentSeconds + "秒限流了:" + (counter.get(currentSeconds).longValue() - limit) + "次");
continue;
}
// 没有被限流
// 业务代码...
Thread.sleep(r.nextInt(10) + 5); // 下一次间隔5~14毫秒
turn ++;
}
}
  • 平滑限流

以上的限流方法都不能很好地处理突发请求,即瞬间请求可以很大。一些场景需要对突发请求进行平滑:

RateLimiter limiter = RateLimiter.create(double permitsPerSecond, long warmupPeriod, TimeUnit unit),其中,permitsPerSecond表示每秒新增的令牌数,warmupPeriod表示从冷启动速率过渡到平均速率的时间间隔

  • 分布式限流(不懂)

节流

throttleFirst/throttleLast

在一个时间窗内,如果有多个相同事件要处理,只处理第一个(或最后一个),则一个时间段内重复的事件变为一个,减少重复事件处理的次数

应用场景:当我们使用滚轮改变浏览器放缩比时,会触发resize事件 ,当我们快速连续执行这个操作时(110%,120%,…,200%),如果连续地触发resize事件,会造成UI反应慢卡顿,节流的做法是只处理最后一个放缩命令:200%

throttleWithTimeout

两个连续时间的时间间隔小于最小间隔时间窗口时,就会丢弃上一个时间,如果最后一个事件等待了最小间隔时间窗口,还没有新的事件到来,处理最后一个事件。

应用场景:搜索关键词的自动补全和下面的搜索提示列表时,如果用户每录入一个字就发送一次请求,先输入的字的自动补全很快被下一个字符覆盖,下面的提示列表也会随之变化,会导致先期的自动补全无用。throttleWithTimeout可以解决这个问题,减少频繁的网络请求,避免每输入一个字就请求一次。(在线翻译,等等场景)

您的支持鼓励我继续创作!