在系统应对大流量,高并发的拜访时,限流算法能够帮助咱们操控流量,从而避免系统负载过高而溃散。接下来将介绍几种常见的限流算法,包括漏桶算法、令牌桶算法、计数器算法、滑动窗口算法和漏斗算法。

漏桶算法

限流算法 | 漏桶算法、令牌桶算法

漏桶算法是一种经典的限流算法,它能够用来操控恳求速率。漏桶算法的原理是将水放入一个固定容量的桶中,桶底有一个固定巨细的洞,水会以固定速率从洞中流出。假如水的流入速度超过了洞口的流出速率,那么剩余的水会被丢掉。因此,漏桶算法通常用于约束网络流量、操控数据传输速率等场景,但是无法应对突发的高流量。

利用这个思路,咱们能够用这个算法来操控一个系统能接受的拜访流量

下面给一个简略的完成
经过这个例子能够看到如何使用漏桶算法来约束流量

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)
}

总结

漏桶算法:

  • 常用于约束网络流量、操控数据传输速率等场景
  • 类似前端的节省函数,经过恒定速率来操控拜访流量
  • 无法应对突发流量

令牌桶算法:

  • 恒定速率发放令牌
  • 能够经过累积令牌来突发流量

关于其他几个算法,且听下回分解


本文正在参加「金石方案」