限流算法之漏桶、令牌桶

发表于 更新于 Changyan：

漏桶算法

把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::chrono;

class LeakyBucket {
public:
    LeakyBucket(int capacity, int rate){
        this->capacity = capacity;
        this->rate = rate;
        this->water_count = 0;
        this->last_leak_time = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
    }

    bool take_request(){
        auto now = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
        int passed_time = (int)(now - last_leak_time).count();

        water_count -= passed_time * rate; // 固定的速度流水
        if(water_count < 0){
            water_count = 0;
        }

        if(water_count < capacity){ // 请求就是加入的水，加满了就拒绝服务
            water_count++;
            last_leak_time = now;
            return true;
        }

        return false;
    }

private:
    int capacity;
    int rate;
    int water_count;
    time_point<system_clock> last_leak_time;
};

int main() {
    LeakyBucket bucket(10, 2);

    for(int i = 0; i < 20; i++){
        if(bucket.take_request()){
            cout << "request " << i + 1<< " passed" << endl;
        } else {
            cout << "request " << i + 1 << " discarded" << endl;
        }
        if(i != 19){
            std::this_thread::sleep_for(100ms);
        }
    }

    return 0;
}

令牌桶算法

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

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::chrono;

class TokenBucket {
public:
    TokenBucket(int capaticy, int rate){
        this->capacity = capaticy;
        this->rate = rate;
        this->token_count = capaticy;
        this->last_request_time = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
    }

    bool take_token(){
        auto now = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
        int passed_time = (int)(now - last_request_time).count();

        token_count += (passed_time * rate) / 1000; // 请求时计算令牌
        if(token_count > capacity){
            token_count = capacity;
        }

        last_request_time = now;

        if(token_count > 0){
            token_count --;
            return true;
        }
        return false;
    }

private:
    int capacity;
    int rate;
    int token_count;
    time_point<system_clock> last_request_time;
};

int main() {
    TokenBucket bucket(10, 2);

    for(int i = 0; i < 20; i++){
        if(bucket.take_token()){
            cout << "request " << i + 1<< " passed" << endl;
        } else {
            cout << "request " << i + 1 << " discarded" << endl;
        }
        if(i != 19){
            std::this_thread::sleep_for(100ms);
        }
    }

    return 0;
}

选择

漏桶算法与令牌桶算法的区别在于，漏桶算法能够强行限制数据的传输速率，令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输（如果桶里积累了一定的令牌，可以突发取完）。

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