在系统应对大流量,高并发的拜访时,限流算法能够帮助咱们操控流量,从而避免系统负载过高而溃散。接下来将介绍几种常见的限流算法,包括漏桶算法、令牌桶算法、计数器算法、滑动窗口算法和漏斗算法。
漏桶算法
漏桶算法是一种经典的限流算法,它能够用来操控恳求速率。漏桶算法的原理是将水放入一个固定容量的桶中,桶底有一个固定巨细的洞,水会以固定速率从洞中流出。假如水的流入速度超过了洞口的流出速率,那么剩余的水会被丢掉。因此,漏桶算法通常用于约束网络流量、操控数据传输速率等场景,但是无法应对突发的高流量。
利用这个思路,咱们能够用这个算法来操控一个系统能接受的拜访流量
下面给一个简略的完成
经过这个例子能够看到如何使用漏桶算法来约束流量
class LeakyBucket {
private water: number = 0 // 水位
private lastLeakTime: number = Date.now();
constructor(private readonly capacity: number, private readonly rate: number) {}
/**
* 处理传入的数据包,并回来是否答应经过
*/
processPacket(packetSize: number): boolean {
// 先漏水
const currentTime = Date.now();
const timeElapsed = currentTime - this.lastLeakTime;
const leakedWater = timeElapsed * this.rate / 1000; // 计算漏水量
this.water = Math.max(this.water - leakedWater, 0); // 漏完水后更新桶内水量
this.lastLeakTime = currentTime;
// 参加新的水量
if (packetSize > this.capacity - this.water) {
// 数据包巨细超过了桶的剩余容量,丢掉该数据包
return false;
} else {
// 数据包能够经过,参加桶中
this.water += packetSize;
return true;
}
}
}
const bucket = new LeakyBucket(100, 10); // 创立一个容量为100,流出速率为10的漏桶
function sendDataPacket(packetSize: number): void {
if (bucket.processPacket(packetSize)) {
console.log(`发送成功,数据包巨细为 ${packetSize} 字节。`);
} else {
console.log(`发送失利,数据包巨细为 ${packetSize} 字节,超过了桶的容量。`);
}
}
sendDataPacket(50); // 发送一个巨细为50字节的数据包,应该能够经过
sendDataPacket(80); // 发送一个巨细为80字节的数据包,应该失利
sendDataPacket(30); // 发送一个巨细为30字节的数据包,应该能够经过
sendDataPacket(50); // 发送一个巨细为50字节的数据包,应该失利
当然,咱们也能够做一下修改,把流量约束改成次数约束,用来操控恳求数量,这就像前端常考的节省功能了。
令牌桶算法
令牌桶算法是另一种经典的限流算法,它的原理是将恳求放入一个令牌桶中,然后按照必定速率不断地放出令牌。只需在令牌桶中有令牌时,才能够发出恳求。令牌桶算法能够操控单位时间内的恳求速率,同时能够应对突发流量,由于只需有足够多的令牌,就能够放恳求过去。
class TokenBucket {
private tokens: number = 0 // 当前桶内令牌的数量
private lastRefillTime: number = Date.now(); // 上一次加令牌的时间
constructor(private readonly capacity: number, private readonly rate: number) {}
/**
* 处理传入的恳求,并回来是否答应经过
*/
processRequest(): boolean {
// 先加令牌
const currentTime = Date.now();
const timeElapsed = currentTime - this.lastRefillTime;
const tokensToAdd = timeElapsed * this.rate / 1000; // 生成令牌数量
this.tokens = Math.min(this.tokens + tokensToAdd, this.capacity); // 加完令牌后更新桶内令牌数量
this.lastRefillTime = currentTime;
// 判断是否答应经过
if (this.tokens < 1) {
// 限流
return false;
} else {
// 经过
this.tokens -= 1;
return true;
}
}
}
const bucket = new TokenBucket(10, 1);
let c = 0
function handleRequest(): void {
c += 1;
if (bucket.processRequest()) {
console.log("经过。",c);
} else {
console.log("限流。",c);
}
}
// 模拟连续恳求,每次经过一个
for(let i = 1; i <= 3; i++) {
setTimeout(() => {
handleRequest()
handleRequest()
}, 1000 * i)
}
总结
漏桶算法:
- 常用于约束网络流量、操控数据传输速率等场景
- 类似前端的节省函数,经过恒定速率来操控拜访流量
- 无法应对突发流量
令牌桶算法:
- 恒定速率发放令牌
- 能够经过累积令牌来突发流量
关于其他几个算法,且听下回分解
“本文正在参加「金石方案」”