浅析限流算法

谁践踏了优雅 2022-12-11 05:25 183阅读 0赞

##### 计数器 #####

计数器算法的思想很简单，每当一个请求到来时，我们就将计数器加一，当计数器数值超过阈值后，就拒绝余下请求。一秒钟后，我们将计数器清零，开始新一轮的计数。计数器算法简单粗暴，易于实现。但是缺点也是有的，也就是所谓的"突刺现象"。举例说明一下，假如我们给计数器设置的阈值为100。系统瞬间内（比如10毫秒内）有200个请求到来，这个时候计数器只能放过其中的100个请求，余下的100个请求全部被拒绝掉。如果第二秒内没有请求到来，那么系统就处于空闲状态。也就是上一秒忙的要死，这一秒又闲的要死。如果我们能用一个容器将剩余的100个请求缓存起来，待计数器重置后再将这些请求放出来。这样系统在这两秒内的吞吐量就由100变成了200，提升了一倍

##### 漏桶算法 #####

漏桶算法由流量容器、流量入口和出口组成。其中流量出口流速即为我们期望的限速值，比如 100 QPS。漏桶算法除了具备限流能力，还具备流量整型功能。下面我们通过一张图来了解漏桶算法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center]  
如上图，流入漏桶流量的流速是不恒定的，经过漏桶限速后，流出流量的速度是恒定的。需要说明的是，漏桶的容量是有限的，一旦流入流量超出漏桶容量，这部分流量只能被丢弃了。

##### 令牌桶算法 #####

令牌桶和漏桶颇有几分相似，只不过令牌通里存放的是令牌。它的运行过程是这样的，一个令牌工厂按照设定值定期向令牌桶发放令牌。当令牌桶满了后，多出的令牌会被丢弃掉。每当一个请求到来时，该请求对应的线程会从令牌桶中取令牌。初期由于令牌桶中存放了很多个令牌，因此允许多个请求同时取令牌。当桶中没有令牌后，无法获取到令牌的请求可以丢弃，或者重试。下面我们来看一下的令牌桶示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center 1]

##### guava的RateLimiter #####

guava中主要有两种限流模式，通过两个工厂方法来创建出两个子类。

*  `SmoothBursty`稳定模式，主要表现为令牌生成速度恒定

static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
        RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
        rateLimiter.setRate(permitsPerSecond);
        return rateLimiter;
      }

*  `SmoothWarmingUp`渐进式模式，主要表现为生成令牌的速度逐步提升并维持在一个速度

static RateLimiter create(
          double permitsPerSecond,
          long warmupPeriod,
          TimeUnit unit,
          double coldFactor,
          SleepingStopwatch stopwatch) {
        RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit, coldFactor);
        rateLimiter.setRate(permitsPerSecond);
        return rateLimiter;
      }

*  本文主要以`SmoothBursty`为例，聊一聊源码的实现，首先我们看一下`SmoothBursty`的参数

/** 当前令牌桶个数. */
      double storedPermits;
    
      /** 最大令牌桶数量 */
      double maxPermits;
    
      /**
       * 添加令牌间隔时间
       */
      double stableIntervalMicros;
    
      /**
       	* 下一次请求可以获取令牌的起始时间
     	* 由于RateLimiter允许预消费，上次请求预消费令牌后
     	* 下次请求需要等待相应的时间到nextFreeTicketMicros时刻才可以获取令牌
       */
      private long nextFreeTicketMicros = 0L;

*  resync函数

resync函数用于增加存储令牌，核心逻辑就是`(nowMicros - nextFreeTicketMicros) / stableIntervalMicros`。当前时间大于nextFreeTicketMicros时进行刷新，否则直接返回。

void resync(long nowMicros) {
        // if nextFreeTicket is in the past, resync to now
        if (nowMicros > nextFreeTicketMicros) {
          double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
          storedPermits = min(maxPermits, storedPermits + newPermits);
          nextFreeTicketMicros = nowMicros;
        }
      }

*  reserveEarliestAvailable函数

这个函数的主要作用是增加令牌，另外一个功能主要是刷新令牌数和下次获取令牌时间。这里涉及RateLimiter的一个特性，也就是可以预先支付令牌。主要逻辑在下面注释中

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
      	// 刷新令牌数，相当于每次acquire时在根据时间进行令牌的刷新
        resync(nowMicros);
        long returnValue = nextFreeTicketMicros;
        // 获取当前已有的令牌数和需要获取的目标令牌数进行比较，计算出可以目前即可得到的令牌数。
        double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
        // freshPermits是需要预先支付的令牌，也就是目标令牌数减去目前即可得到的令牌数
        double freshPermits = requiredPermits - storedPermitsToSpend;
        // 因为会突然涌入大量请求，而现有令牌数又不够用，因此会预先支付一定的令牌数
        // waitMicros即是产生预先支付令牌的数量时间，则将下次要添加令牌的时间应该计算时间加上watiMicros
        long waitMicros =
            storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
                + (long) (freshPermits * stableIntervalMicros);
    
        this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
        // 更新令牌数，最低数量为0
        this.storedPermits -= storedPermitsToSpend;
        // 返回旧的nextFreeTicketMicros数值，无需为预支付的令牌多加等待时间。
        return returnValue;
      }

*  构造函数

SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
          super(stopwatch);
          this.maxBurstSeconds = maxBurstSeconds;
        }
    
        @Override
        void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
          double oldMaxPermits = this.maxPermits;
          maxPermits = maxBurstSeconds * permitsPerSecond;
          if (oldMaxPermits == Double.POSITIVE_INFINITY) {
            // if we don't special-case this, we would get storedPermits == NaN, below
            storedPermits = maxPermits;
          } else {
            storedPermits =
                (oldMaxPermits == 0.0)
                    ? 0.0 // initial state
                    : storedPermits * maxPermits / oldMaxPermits;
          }
        }

虽然RateLimiter很好用，但是只适合单机。如果想要集群限流，则需要引入阿里开源的sentinel中间件。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e67f6b8ada244718b0421aad850c4508.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/6931799293954bd28ba011fc0f63845b.png