高并发限流的几种方法

当网站的访问量比较大的时候，比如抢购、限时活动，或者有的时候为了防止黑客攻击，服务器资源是承载不了的。服务接口的流量控制策略一般有缓存、降级、限流等。那今天我们来聊下限流这种方式，限流就是控制流量，从而达到保护系统的目的。下面向大家展示几种方法。

1. 计算器法

描述：比如我们限制每个用户每分钟最多能访问页面100次，如果超过100次，则返回太频繁，下面使用PHP+Redis伪代码来实现

<?php
$initMum = 100;
$ip = $_SERVER['REMOTE_ADDR'];  
$redis = new Redis();
$key = "rate_limiting:$ip"
$isExist = $redis->exists($key);
if ($isExist) {
    $times = $redis->Incr($key);
    if ($times > 100) {
       echo '访问频率超过了限制，请稍后再试';
       exit();
    }
}
else {
      $redis->setex($key,1,60);
}

一般情况下这个就能满足需求了，但是这样做小伙伴们可能发现有一个问题，就是临界问题。比如某个用户在键过期前10秒内访问了页面60次，那刚好下一秒这个键就过期了，redis会销毁这个key，然后这个用户接着在10秒内又访问了该页面60次，那其实在不到半分钟内这个用户访问了该页面120次，显然这没有达到我们预期的要求，那接下来再向大家展示一个更为精确的一个方法。
就是我们把用户每次访问的时间都保存到一个队列中，用户的IP作为这个队列的键，当队列的长度不超过100的时候就会直接往队列里面添加最新的访问时间，如果队列的长度大于100，那么这个时候就会比较这次访问的时间和上一次访问的时间，如果超过一分钟，这把最早访问的那个时间从队列中移除，并把新的最新的访问时间添加到队列中；如果这次访问的时间具体上次的访问时间不超过一分钟，则返回访问太频繁，下面使用伪代码来实现下：

<?php
$initMum = 100;
$ip = $_SERVER['REMOTE_ADDR'];  
$redis = new Redis();
$key = "rate_limiting:$ip"
$times = $redis->llen($key);
if ($times < 100 ) {
    $res = $redis->lpush($key,$now);
}
else {
    $time = $redis->lindex($key,-1);
    if (now() - $time < 60) {
          echo '访问频率超过了限制，请稍后再试';
          exit();
    }
    else {
          $res = $redis->lpush($key,now());
          $res1 = $redis->ltrim($key,0,9);
     }
}

这个方法虽然能解决我们上面提到的问题，但是它也有它的弊端，比如当initMum这个值比较大的时候，这种方法会占用比较大的内存，所以实际的应用中还得我们自己去权衡，另外在lpush和ltrim这两个操作之间也可能会存在竞态的情况，我们可以使用事务或者lua脚本功能去实现，不过如果使用事务去处理的话，可能还要考虑失败的情况下重新执行事务。关于lua脚本这里就不做详细的介绍。下面来介绍两种比较经典的限流算法，它们使用一层中间层（桶）来缓冲部分客户端的请求。

2. 漏桶算法

描述：我们有一个固定容量的桶，有水流进来，也有水流出去。流进来的水就类似我们的请求，这个量的大小是不确定的；对于流出去的水，这个速率可以设置一个固定值。当桶满了后，多余的水就会溢出。下面本人从网上找了一些图来帮助大家理解。

图一.png

关于漏桶算法需要注意以下两点：
1）桶的最大容量怎么设置？
2）水流出的速度怎么设置？
先来说下水流出的速度，这个其实需要根据后台程序的处理请求的速度来设置，不过往往我们的机器上会运行多个程序，它们共享计算机资源，这个时候可能会相互影响，所以程序的处理速度是变化的，那我们可以观察一段时间内程序处理请求的数量，然后分析得到平均值或者中位数等数据来作为水流出的速度。
桶的最大容量怎么设置，这个获取要结合请求的处理速度、系统一段时间内能处理的最大请求数、客户端的请求数、用户体验等等来进行设置。比如如果请求的处理速度很慢，但是桶设置得很大，就会导致很多请求得不到及时的处理。
下面使用伪代码来实现下：

class LeakyDemo{
     $capacity = 200; // 桶的容量，假如是200bit
     $rate = 5; //水流出的速度，假如是5bit/秒
     $water; //当前的水量
     $timeStamp =1587355877; //初始时间
     //加水操作
      public function addWater ($num = 1) {
            $this->water = max(0,$this->water - ( time()-$this->timestamp) * $rate );
             if (  $this->water + $num < $capacity ) {
                   $this->water = $this->water + $num;
                   return true;
               }
               else {
                      echo '桶已满';
                      return false;
               }
      }
}
$obj = new LeakyDemo();
$res = $obj->addWater(1);// 请求数
if ($res) {
     echo '加水成功，可以进行后续操作';
}
else {
    echo '加水失败，拒绝请求或者进行一些其他的处理';
}

这种限流算法其实是不管当前有多少并发数，通过这个出水速率保证后台程序接到的请求数是一定的，从而达到了限流的目的。由于出水速率是固定的，所以会有个缺点就是对于突发流量的处理效率并不高，为了解决这个问题下面来介绍下另外一种限流算法。

3. 令牌桶算法

描述：简单来说就是客户端要访问服务器（后端接口），需要先从令牌桶里面获得令牌才能访问，否则拒绝请求或者加入队列进行排队等等。令牌桶这个桶它的容量是一定的，令牌是以一定的速率加进去的，如果桶已经满了就不再继续添加。

图二.png

看到这张图，相信小伙伴们对令牌桶算法流程会有个清晰的认识了吧。
不过如果要深层次的考虑，还需注意以下几点：
1）生成令牌的速度怎么定？也就是生成令牌的算法
2）令牌桶的大小怎么定比较合适？

如果某段时间内请求量很大，并且这些请求全部拿到了token（拿到token的速度是很快的），那他们会同时去请求后台接口，这个时候服务器势必会扛不住，所以为了使系统在突发流量的时候不至于崩溃，令牌桶的大小会设置成我们系统能处理的最大并发数。当然这个最大并发数需要我们对系统进行相关的测试等方式获得。
另外，对于生成令牌的速度可能要结合系统正常情况下的客户端请求次数、系统的一般情况下的并发数、限流的大小等因素来考虑。如果小于系统正常情况下处理请求的速度的话，那系统的利用率就没有达到最大值，又或者生成令牌的速率比较小，这样对突发流量的处理也不是很好，会导致大量的请求拿不到token而被丢弃或者加入排队进行等待，所以设置一个合理的大小是比较重要的。下面使用伪代码来实现下：

public function TokenBucketDemo {
       $capacity = 200; // 桶的容量，假如是200bit
       $rate = 5; //令牌放入速度，假如是5bit/秒
       $tokens = 10; //当前令牌数量，初始化为10
       $timestamp = 1587355877;// 初始时间
       
        public function getToken($num = 1) {
              $now = time();
              $this->tokens = min( $this->capacity,$this->tokens+($now- $this->timestamp) * $this->rate );
              $this->timestamp = $now;
               if ($tokens < 1) { 
                    echo '没有令牌了，拒绝请求';
                    return false;
               }
               else {
                       echo '还有令牌';
                       $this->token -= $num;
                       return true;
               }
        }
}

这里的代码只是简单的展示下这种算法的实现思路，实际不一定是这么写，比如我们可以使用redis来存储当前的token数量，然后使用一个定时任务不断的往这个里面加入token，当有请求过来的时候就会实时的去获取当前的token数，如果请求需要的token数大于当前令牌桶中的令牌数，就会被认为超出了当前的限制，请求就会被拒绝或者进行一些其他的处理。

漏桶算法VS令牌桶算法
1） 漏桶算法进水速率是不确定的，但是出水速率是一定的，当大量的请求到达时势必会有很多请求被丢弃。
2） 令牌桶算法会根据限流大小，设置一定的速率往桶中加令牌，这个速率可以很方便的修改，如果我们要提高系统对突发流量的处理，我们可以适当的提高生成token的速率。

关于限流的方法暂时就写到这，其实使用过nginx的小伙伴知道，对nginx 进行相关的配置也可以实现限流，又或者是使用第三方的开源工具比如Google的开源工具包Guava提供了限流工具类RateLimiter，该类是基于令牌桶算法来完成限流的。这里就不具体说了。后面会专门写一篇文章来介绍。
如果有地方需要补充的，欢迎小伙伴们在下面给我留言，看到会及时回复的。