网站吞吐量指标

网站吞吐量指单位时间内系统处理的请求数量，体现系统的整体处理能力。 可以用请求数/秒，或者页面数/每秒来衡量，也可以用访问人数/天，或者处理的业务数/小时等来衡量。

QPS（Queries Per Second，每秒查询数）是吞吐量的一个常用量化指标，此外还有TPS（Transaction Per Second，每秒事务数）、HPS（每秒 HTTP 请求数）等。

通常就将QPS理解为请求数，强调服务器的处理能力。

常见限流算法

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。限流就是通过限制网站吞吐量，防止系统不被瞬时大流量冲垮。

常见的限流算法有三种：
+ 计数算法（也称时间窗口限流）
+ 漏桶算法
+ 令牌桶算法

计数算法

这种限流算法最简单，也是最容易实现的，通过在单位时间内设置最大访问数就可以达到限流的目的。这个单位时间我们也称作时间窗口，在一个时间窗口内，限制最大的请求数。例如想要限制系统的QPS为60，就可以限制接口在一秒内只能被访问60次即可（设置一个计数器用于计数）。这种算法有一个缺陷，假如在时间窗口的前1%的时间内流量就达到顶峰了，那么在时间窗口内即使还有99%的时间系统能够继续提供服务，还是会被限流算法的这种缺陷阻断在门外，这种缺陷也被称为 “突刺效应”。

还有一个临界值问题：假设我们设定1秒内允许通过的请求阈值是200，如果有用户在时间窗口的最后几毫秒发送了200个请求，紧接着又在下一个时间窗口开始时发送了200个请求，那么这个用户其实在一秒内成功请求了400次，显然超过了阈值但并不会被限流。

漏桶算法

关于漏桶算法有一张很经典的图：

这张图形象地描述了漏桶算法的原理，活塞流出的水为流入流量，漏桶有一个固定大小，所有请求在这个漏桶中进行排队，而底部匀速流出一定的水，代表放行的流量。如果漏桶已满，还有流量流入，则会拒绝（即溢出）。

因为没有时间窗口的概念，限流较为平滑，它有效的避免了计数器法的“突刺效应”和临界值问题。实现也不复杂，通过固定大小的队列+定时取队列元素的方式即可实现。不过因为漏桶算法限制了流出速率是一个固定常量值，所以漏桶算法不支持出现突发流出流量。但是在实际情况下，流量往往是突发的。 例如漏桶的容积是100，出水速率是10/s，则漏桶为空的时候能承载的最大QPS是100/s，但因为流量通过的速率始终是10/s，无法很快地将这些流量放行，于是QPS很快就又下来了。

令牌桶算法

令牌桶法也是基于桶的原型，但是和漏桶算法截然不同的是，没有出水口。令牌桶通过令牌的产生速率+令牌桶的容积来控制流量，有效的解决了漏桶效率不高的问题。

在令牌桶算法中，有一个令牌流会向桶中匀速放置令牌，当一个请求过来的时候，可以从令牌桶中取走令牌，拿到令牌的请求即可通行，若桶中没有令牌，则请求需要排队等待，直到取到令牌。由于令牌桶的令牌是源源不断生成的,当访问量小时,可以留存令牌达到令牌桶的上限,这样当短时间的突发访问量来时,积累的令牌数可以处理这个问题。当访问量持续大量流入时,由于生成令牌的速率是固定的,最后也就变成了类似漏斗算法的固定流量处理。

如，容积为100的桶，令牌产生速率为50/s，那么就代表当桶中令牌已满的时候，最大能够承载100的流量，后面如果流量一直居高不下，也会以每秒50个流量的速度恒速处理请求。令牌桶的这种特性有效的处理了洪峰流量也能做到不被洪峰压垮，是目前限流比较常见的实现方法。比较著名的实现有谷歌guava中的RateLimiter。

使用Redis实现简单的计数算法

主要思想是使用Sorted Set的score维护一个滑动时间窗口，每一个请求到来的时候将一个时间窗口之前的请求全部丢弃，看set里面元素的个数。

代码来源：《Redis深度历险：核心原理与应用实践》，我做了一点修改。

import redis.clients.jedis.Jedis;
import redis.clients.jedis.Pipeline;
import redis.clients.jedis.Response;

import java.util.UUID;

public class SimpleRateLimiter {
    private Jedis jedis;

    public SimpleRateLimiter(Jedis jedis) {
        this.jedis = jedis;
    }

    /**
     * @param userId 标识用户
     * @param actionKey 标识处理请求的方法（或服务）
     * @param period 时间窗口的大小，单位为秒
     * @param maxCount 时间窗口内允许的最大请求
     * @return 请求是否放行
     */
    public boolean isActionAllowed(String userId,String actionKey,int period,int maxCount){
        String key = String.format("hist:%s:%s", userId,actionKey);
        //当前毫秒时间戳，作为插入元素的score
        long nowTs = System.currentTimeMillis();
        //使用Pipeline管道化进行Redis请求
        Pipeline pipe = jedis.pipelined();
        pipe.multi();
        //插入元素，score为当前时间戳，value并无具体含义，但注意每次请求必须唯一
        pipe.zadd(key, nowTs, UUID.randomUUID().toString());
        //移除距当前时间一个时间窗口之前的所有元素
        pipe.zremrangeByScore(key, 0, nowTs-period*1000);
        //获取集合中元素数量
        Response<Long> count = pipe.zcard(key);
        //若时间窗口的有效期没有续上，则会从内存中移除，节省存储空间
        pipe.expire(key, period+1);
        pipe.exec();
        pipe.close();
        //获取集合中元素数量是否小于等于允许的最大请求数
        return count.get()<=maxCount;
    }

    public static void main(String[] args) {
        Jedis jedis = new Jedis("192.168.176.128");
        SimpleRateLimiter limiter = new SimpleRateLimiter(jedis);
        //短时间处理20个请求
        for(int i = 0;i<20;i++){
            boolean isAllowed = limiter.isActionAllowed("123","reply" , 1, 10);
            System.out.println("第"+(i+1)+"个请求："+isAllowed);
        }
    }
}

注意这是一种滑动时间窗口，和我们一开始介绍的时间窗口算法又有一些不同，应当说是计数算法的改进。它的时间窗口不是固定在两个时间点之间的，而是每次请求的时间点向前推了一个时间窗口，避免了临界值问题。

查看输出：

第1个请求：true
第2个请求：true
第3个请求：true
第4个请求：true
第5个请求：true
第6个请求：true
第7个请求：true
第8个请求：true
第9个请求：true
第10个请求：true
第11个请求：false
第12个请求：false
第13个请求：false
第14个请求：false
第15个请求：false
第16个请求：false
第17个请求：false
第18个请求：false
第19个请求：false
第20个请求：false

这里提一下，原书中的代码是将每次请求的时间戳作为插入元素的value，然而由于是Set，元素的值不能重复，很有可能在一毫秒内处理几个请求，这样的话插入的元素会覆盖同一时间戳的元素，导致集合内元素的个数没有增加，最后运行的结果通过的请求数也是大于或等于5的。使用这个实现方式应当避免value重复，我这里使用的UUID，可能有点长了，还可以使用其他方式例如时间戳加随机数，通常来说小概率value重复也是可以忍受的。

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%b8%b8%e8%a7%81%e9%99%90%e6%b5%81%e7%ae%97%e6%b3%95%e4%b8%8e%e4%bd%bf%e7%94%a8redis%e5%ae%9e%e7%8e%b0%e7%ae%80%e5%8d%95%e7%9a%84%e8%ae%a1%e6%95%b0%e9%99%90%e6%b5%81%e7%ae%97%e6%b3%95/