服务器雪崩的应对策略之----限流

码农世界 2024-06-21 后端 108 次浏览 0个评论

限流是一种控制流量的技术，旨在防止系统在高并发请求下被压垮。通过限流，可以确保系统在负载高峰期依然能保持稳定运行。常见的限流策略包括令牌桶算法、漏桶算法、计数器算法和滑动窗口算法。

常见的限流方法

1. 令牌桶算法 (Token Bucket Algorithm)
2. 漏桶算法 (Leaky Bucket Algorithm)
3. 计数器算法 (Counter Algorithm)
4. 滑动窗口算法 (Sliding Window Algorithm)

结论

1. 令牌桶算法 (Token Bucket Algorithm)

令牌桶算法是一种允许突发流量的限流算法。系统按照固定速率生成令牌，请求只有在获取到令牌后才能被处理。

原理：

系统按照固定速率往桶中添加令牌。
当桶满时，多余的令牌会被丢弃。

每个请求需要从桶中获取一个令牌，若令牌数量不足，请求被拒绝或等待。

示例代码：

#include 
#include 
#include 
#include 
class TokenBucket 
{
public:
    TokenBucket(int rate, int burst) : rate(rate), burst(burst), tokens(0) 
    {
        last_refill = std::chrono::steady_clock::now();
    }
    bool allow_request() 
    {
        std::lock_guard lock(mutex);
        refill();
        if (tokens > 0) 
        {
            tokens--;
            return true;
        }
        return false;
    }
private:
    void refill() 
    {
        auto now = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast(now - last_refill).count();
        tokens = std::min(burst, tokens + duration * rate);
        last_refill = now;
    }
    int rate; // 令牌生成速率
    int burst; // 桶的容量
    int tokens; // 当前令牌数量
    std::chrono::steady_clock::time_point last_refill;
    std::mutex mutex;
};
int main() 
{
    TokenBucket bucket(5, 10); // 每秒生成5个令牌，桶容量为10个令牌
    for (int i = 0; i < 20; ++i) 
    {
        if (bucket.allow_request()) 
        {
            std::cout << "Request " << i << " is allowed\n";
        } 
        else 
        {
            std::cout << "Request " << i << " is denied\n";
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(200));
    }
    return 0;
}

2. 漏桶算法 (Leaky Bucket Algorithm)

漏桶算法是一种严格控制流量速率的限流算法。它将请求放入一个固定容量的桶中，并以固定速率处理请求，溢出的请求会被丢弃。

原理：

请求以任意速率进入桶。
桶以固定速率漏出请求进行处理。

如果桶满了，后续请求会被丢弃。

示例代码：

#include 
#include 
#include 
#include 
#include 
class LeakyBucket 
{
public:
    LeakyBucket(int rate, int capacity) : rate(rate), capacity(capacity), water(0) 
    {
        last_check = std::chrono::steady_clock::now();
    }
    bool allow_request() 
    {
        std::lock_guard lock(mutex);
        leak();
        if (water < capacity) 
        {
            water++;
            return true;
        }
        return false;
    }
private:
    void leak() 
    {
        auto now = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast(now - last_check).count();
        int leaked = duration * rate;
        if (leaked > 0) 
        {
            water = std::max(0, water - leaked);
            last_check = now;
        }
    }
    int rate; // 漏出速率
    int capacity; // 桶的容量
    int water; // 当前水量
    std::chrono::steady_clock::time_point last_check;
    std::mutex mutex;
};
int main() 
{
    LeakyBucket bucket(1, 10); // 每秒处理1个请求，桶容量为10个请求
    for (int i = 0; i < 20; ++i) 
    {
        if (bucket.allow_request()) 
        {
            std::cout << "Request " << i << " is allowed\n";
        } 
        else 
        {
            std::cout << "Request " << i << " is denied\n";
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(200));
    }
    return 0;
}

3. 计数器算法 (Counter Algorithm)

计数器算法是一种简单的限流策略，通过计数器在固定时间窗口内计数请求数量，如果超过限制，则拒绝请求。

原理：

在固定时间窗口内计数请求数量。
如果请求数量超过设定的阈值，则拒绝请求。

时间窗口结束后，重置计数器。

示例代码：

#include 
#include 
#include 
#include 
class CounterRateLimiter 
{
public:
    CounterRateLimiter(int limit, int window_size) : limit(limit), window_size(window_size), count(0) 
    {
        window_start = std::chrono::steady_clock::now();
    }
    bool allow_request() 
    {
        std::lock_guard lock(mutex);
        auto now = std::chrono::steady_clock::now();
        if (std::chrono::duration_cast(now - window_start).count() >= window_size) 
        {
            window_start = now;
            count = 0;
        }
        if (count < limit) 
        {
            count++;
            return true;
        }
        return false;
    }
private:
    int limit; // 时间窗口内允许的最大请求数
    int window_size; // 时间窗口大小（秒）
    int count; // 当前请求数
    std::chrono::steady_clock::time_point window_start;
    std::mutex mutex;
};
int main() 
{
    CounterRateLimiter limiter(5, 1); // 每秒最多处理5个请求
    for (int i = 0; i < 20; ++i) 
    {
        if (limiter.allow_request()) 
        {
            std::cout << "Request " << i << " is allowed\n";
        } 
        else 
        {
            std::cout << "Request " << i << " is denied\n";
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(200));
    }
    return 0;
}

4. 滑动窗口算法 (Sliding Window Algorithm)

滑动窗口算法是计数器算法的改进版，通过滑动窗口精确统计请求数量，避免固定窗口带来的突发流量问题。

原理：

将时间窗口划分为多个小的子窗口。
记录每个子窗口的请求数量。

滑动窗口通过移动时间窗口来更新请求数量。

示例代码：

#include 
#include 
#include 
#include 
#include 
class SlidingWindowRateLimiter 
{
public:
    SlidingWindowRateLimiter(int limit, int window_size, int bucket_count) 
        : limit(limit), window_size(window_size), bucket_count(bucket_count), buckets(bucket_count, 0), count(0) 
        {
        last_check = std::chrono::steady_clock::now();
    	}
    bool allow_request() 
    {
        std::lock_guard lock(mutex);
        slide_window();
        if (count < limit) 
        {
            buckets[current_bucket]++;
            count++;
            return true;
        }
        return false;
    }
private:
    void slide_window() 
    {
        auto now = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast(now - last_check).count();
        int slide_count = duration * bucket_count / (window_size * 1000);
        if (slide_count > 0) 
        {
            for (int i = 0; i < slide_count && count > 0; ++i) 
            {
                current_bucket = (current_bucket + 1) % bucket_count;
                count -= buckets[current_bucket];
                buckets[current_bucket] = 0;
            }
            last_check = now;
        }
    }
    int limit; // 时间窗口内允许的最大请求数
    int window_size; // 时间窗口大小（秒）
    int bucket_count; // 子窗口数量
    std::vector buckets; // 存储每个子窗口的请求数
    int count; // 当前请求总数
    int current_bucket = 0; // 当前子窗口索引
    std::chrono::steady_clock::time_point last_check;
    std::mutex mutex;
};
int main() 
{
    SlidingWindowRateLimiter limiter(5, 1, 10); // 每秒最多处理5个请求，划分为10个子窗口
    for (int i = 0; i < 20; ++i) 
    {
        if (limiter.allow_request()) 
        {
            std::cout << "Request " << i << " is allowed\n";
        } 
        else 
        {
            std::cout << "Request " << i << " is denied\n";
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(200));
    }
    return 0;
}