令牌桶过滤算法的 C++ 实现
最编程
2024-03-07 13:57:41
...
什么是令牌桶算法
令牌桶算法通过限制令牌桶的固定容量,实现对资源以及流量的延迟控制。请求者需先获取令牌,方可执行动作。若令牌桶内具有足够令牌便可通过消耗相等数量放过请求;而若令牌不足,则会拒绝请求。
该算法具备平滑的资源使用率控制功能,有效避免突发流量对系统的破坏。此外,令牌桶算法还适用于流量控制、预防DDoS攻击及防止资源过载等多种场景。同时,因其能根据需求动态调整填充速率,故在各种流量模式下均可适用。
操作示例
当然,以下是一个示例的C++代码,用于实现令牌桶过滤算法。令牌桶算法用于限制对一组资源的访问速率,它通过维护一个固定容量的令牌桶来控制对资源的访问。
#include <iostream>
#include <chrono>
#include <thread>
class TokenBucket {
public:
TokenBucket(int capacity, int rate) : capacity_(capacity), rate_(rate), tokens_(capacity) {}
bool consume(int tokens) {
if (tokens <= tokens_) {
tokens_ -= tokens;
return true;
} else {
return false;
}
}
void refill() {
while (true) {
std::this_thread::sleep_for(std::chrono::seconds(1));
tokens_ = std::min(capacity_, tokens_ + rate_);
}
}
private:
int capacity_;
int rate_;
int tokens_;
};
int main() {
TokenBucket bucket(10, 2); // 令牌桶容量为10,每秒增加2个令牌
// 启动令牌桶的自动补充线程
std::thread refill_thread([&] { bucket.refill(); });
// 模拟资源访问
for (int i = 0; i < 20; ++i) {
if (bucket.consume(1)) {
std::cout << "Access granted" << std::endl;
} else {
std::cout << "Access denied" << std::endl;
}
std::this_thread::sleep_for(std::chrono::milliseconds(500)); // 模拟资源访问间隔
}
// 等待自动补充线程结束
refill_thread.join();
return 0;
}
这段代码主要是创建了一个TokenBucket类,其中包含了令牌桶的容量、速率和当前令牌数量。主函数模拟了对资源的访问,并在访问时检查是否有足够的令牌。
令牌桶算法VS漏桶算法
令牌桶算法,它生成的令牌速率是一定的。当短时间内有大量的流量来请求的时候,他会瞬间获取大量的令牌,不会对他的请求产生太大的影响。与之相对的可能就是漏桶算法,漏洞算法它控制的是请求速率,而不是向令牌桶一样去控制它的生成速率。但是漏桶算法它有一个特点,就是当地大量的流量进来的时候,它实际请求的流量也是固定的。所以这就要看你当前使用的场景。
总结
总的来说,令牌桶算法是一种简单且实用的限速方式,适用于网络流量控制、API调用限制以及系统资源管理等领域,经常可能会在gateway里面去用到。一些常用的流量限制,是我们常说的限流处理。在日常使用中,可以根据其中生产令牌速率的特点,去选择合适的场景使用它。
推荐阅读
-
二维高斯曲面拟合法的 C++ 实现,用于寻找光斑中心和算法
-
BM 算法的 C/C++ 代码实现
-
贪婪算法在 Python、JavaScript、Java、C++ 和 C# 中的多种实现及其在硬币变化、分数骑士、活动选择和使用哈夫曼编码的最小生成树问题中的应用实例
-
画圆的吴氏防对齐算法(C++/MFC 实现)
-
协作过滤推荐算法的 Python 实现 完整代码示例
-
流量限制:计数器、泄漏桶、令牌桶 三大算法的原理与实践(史上最全)
-
令牌桶和泄漏桶的算法思路
-
高度并发系统的流量限制--泄漏桶算法和令牌桶算法 服务治理 - 流量限制(令牌桶算法)
-
常见限流算法(漏斗算法、令牌桶算法)及实现介绍-III。
-
令牌桶算法:让分布式系统的流量限制更优雅