0%

Restful Rate Limiter(接口频率限制)

Posted on In

限流技术(time limiting)被用作控制服务请求的速率，监控Restful Api的运行状态。 可以用来优化性能，减少延迟和提高带宽等。最常用的两种限流的算法如下

  • Leacy Bucket 漏桶算法
  • Token Bucket 令牌桶算法

Leacy Bucket 漏桶算法

顾名思义，就像是一定容量的漏桶通过出水口和入水口来限制数据的传速率。

它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。

简单来说：

漏桶算法思路很简单，水（数据或者请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

可以通过定时器以一定的频率清空漏桶容量，来达到基于时间频率的漏桶算法。

在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以，即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使某一个单独的流突发到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。

小结

  • 漏桶算法强制常量的输出速率而不管输入数据流的突发性

当输入空闲时，该算法不执行任何动作

实现原理：

  1. 队列接收到准备转发的数据包
  2. 队列被调度，得到转发机会，由于队列配置了流量整形，其中的数据包先进入漏桶
  3. 根据数据包到达漏桶的速率与漏桶的输出速率关系，确定数据包是否被转发：
    1. 如果到达速率 ≤ 输出速率，则漏桶不起作用
    2. 如果到达速率 > 输出速率，则考虑漏桶是否能承担瞬间流量
      1. 数据包到达的速率 - 漏桶流出的速率 ≤ 配置的漏桶突发速率，则数据包可被不延时的送出
      2. 若数据包到达的速率 - 漏桶流出的速率 > 配置的漏桶突发速率，则多余的数据包被存储到漏桶中

      暂存在漏桶中的数据包在不超过漏桶容量的情况下延时发出

      1. 若数据包到达的速率 - 漏桶流出的速率 > 配置的漏桶突发速率，且数据包的数量已经超过漏桶的容量，则这些数据包将被丢弃

简单实现：

1
public class LeakyBucket {
2
    private final long capacity;
3
    private final long leaksIntervalInMillis;
4
5
    private double used;
6
    private long lastLeakTimestamp;
7
8
    public LeakyBucket(long capacity, long leaksIntervalInMillis) {
9
        this.capacity = capacity;
10
        this.leaksIntervalInMillis = leaksIntervalInMillis;
11
12
        this.used = 0;
13
        this.lastLeakTimestamp = System.currentTimeMillis();
14
    }
15
16
    synchronized public boolean tryConsume(int drop) {
17
        leak();
18
        if (used + drop > capacity) {
19
           return false;
20
        }
21
        used = used + drop;
22
        return true;
23
    }
24
25
    private void leak() {
26
        long currentTimeMillis = System.currentTimeMillis();
27
        if (currentTimeMillis > lastLeakTimestamp) {
28
            long millisSinceLastLeak = currentTimeMillis - lastLeakTimestamp;
29
            long leaks = millisSinceLastLeak / leaksIntervalInMillis;
30
            if(leaks > 0){
31
                if(used <= leaks){
32
                    used = 0;
33
                }else{
34
                    used -= (int)leaks;
35
                }
36
                this.lastLeakTimestamp = currentTimeMillis;
37
            }
38
        }
39
    }
40
}
  • 这个实现设计了lastLeakTimestamp字段，用于计算时间差，以及在这个时间段内需要漏水的数量
  • 每次tryConsume的时候，方法内部首先调用leak，根据设定的速度以及时间差计算这个时间段需要漏水的数量，更新桶的当前使用量以及lastLeakTimestamp
  • 之后限流判断，就是判断used与请求的drop是否会超过桶容量，超出则限流，否则放入桶中，更新桶容量

Token Bucket 令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

令牌桶的另外一个好处是可以方便的改变速度。 一旦需要提高速率，则按需提高放入桶中的令牌的速率。

一般会定时(比如100毫秒)往桶中增加一定数量的令牌， 有些变种算法则实时的计算应该增加的令牌的数量。

比如华为的专利"采用令牌漏桶进行报文限流的方法"(CN 1536815 A),提供了一种动态计算可用令牌数的方法， 相比其它定时增加令牌的方法， 它只在收到一个报文后，计算该报文与前一报文到来的时间间隔内向令牌漏桶内注入的令牌数， 并计算判断桶内的令牌数是否满足传送该报文的要求。

小结

  • 令牌桶算法可控制发送到网络上数据的数目，并允许突发数据的发送

是网络流量整形和速率限制中最常使用的一种算法

  • 大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌

令牌桶中的每一个令牌都代表一个字节：

  • 如果令牌桶中存在令牌，则允许发送流量
  • 如果令牌桶中不存在令牌，则不允许发送流量
  • 若令牌不被消耗，或被消耗速度小于产生速度，令牌就会不断地增多，直到把桶填满
  • 传送到令牌桶的数据包需要消耗令牌，不同大小的数据包，消耗的令牌数量不同

令牌桶算法的基本过程：

  1. 假如用户配置的平均发送速率为 r，则每隔 1/r 秒一个令牌被加入到桶中
  2. 假设桶最多可以存放 b 个令牌，若令牌桶已满，则后续到达的令牌会被丢弃
  3. 当一个 n 字节的数据包到达时，从令牌桶删除 n 个令牌，并且数据包被发送到网络
  4. 若令牌桶中少于 n 个令牌，则不会删除令牌，并且认为这个数据包在流量限制之外

在流量限制外的数据包的处理方式：

  • 被丢弃
  • 可以排放在队列中，以便当令牌桶中累积了足够多的令牌时再传输
  • 可以继续发送，但需要做特殊标记，网络过载时将特殊标记的包丢弃
  1. 算法允许最长 b 个字节的突发，但从长期结果看，数据包的速率被限制成常量 r

实现原理：

  • 方式一： 开启一个定时任务，由定时任务持续生成令牌

问题： 会极大的消耗系统资源
如某接口需要分别对每个用户做访问频率限制，假设存在 6W 用户，则至多需要开启 6W 个定时任务来维持每个桶中的令牌数，开销巨大

  • 方式二： 延迟计算

resync 函数会在每次获取令牌前调用
实现思路： 若当前时间晚于 nextFreeTicketMicros，则计算该段时间内可以生成多少令牌，将生成的令牌加入令牌桶中并更新数据。这样一来，只需要在获取令牌时计算一次