本文主要总结自《redis深度历险》
限流的意义
限流一般是指在一个时间窗口内对某些操作请求的数量进行限制，比如一个论坛限制用户每秒钟只能发一个帖子，每秒钟只能回复5个帖子。限流可以保证系统的稳定，限制恶意请求，防止因为流量暴增导致系统瘫痪宕机。常用的限流算法有：滑动窗口、漏斗以及令牌桶。
滑动窗口算法rolling Window
以限制用户行为为例子，比如一秒内进行某个操作50次，这种行为应该进行限制。
滑动窗口就是记录一个滑动的时间窗口内的操作次数，操作次数超过阈值则进行限流。
网上找的图：
在redis中可以用zset数据结构来实现这个功能：
用唯一的id作为zset的key，可以是user_id + action_key ，value是当前操作的时间戳。每次新的操作请求进来时，先判断当前时间窗口内记录的操作次数 count，小于阈值max则允许进行操作，超过阈值则进行限流。同时对时间窗口之外的数据进行清理，节省内存。
简单代码实现：
public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) { // 生成唯一的key String key = String.format("hist:%s:%s", userId, actionKey); long nowTs = System.currentTimeMillis(); // 使用管道 Pipeline pipe = jedis.pipelined(); pipe.multi(); // 添加当前操作当zset中 pipe.zadd(key, nowTs, "" + nowTs); // 整理zset，删除时间窗口外的数据 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;}
zset中的value没有特殊含义，只是用来保证每次操作都是唯一的能够被zset记录。
漏斗限流
xxdyj就是用一个漏斗来存储（记录请求），一边向漏斗里面加请求一边将请求漏出去。漏斗的漏嘴有一个流水速率，表示单位时间内流出的水量（数据量），当加水的速率（单位时间加进去的请求）小于流水速率时漏斗永远不会满。
我们不用时刻记录漏水，只需记录上一次漏水的开始时间，当一个请求进来时，我们只需要计算上次漏水的时间到当前时间一共漏出的数据量count，用这上次漏水至今的数据总量减去count，了，来判断漏斗是否溢出
漏斗算法的Java实现：
public class FunnelRateLimiter { static class Funnel { // 漏斗大小 int capacity; // 漏嘴流水速率 float leakingRate; // 漏斗剩余容量 int leftQuota; // 上一次漏水时间 long leakingTs; public Funnel(int capacity, float leakingRate) { this.capacity = capacity; this.leakingRate = leakingRate; this.leftQuota = capacity; // 初始化时指定当前时间为第一次漏水时间 this.leakingTs = System.currentTimeMillis(); } void makeSpace() { long nowTs = System.currentTimeMillis(); long deltaTs = nowTs - leakingTs; // 流水速率 * 时间，计算这段时间流出的数据总量 int deltaQuota = (int) (deltaTs * leakingRate); if (deltaQuota < 0) { // 间隔时间太长，整数数字过大溢出 this.leftQuota = capacity; this.leakingTs = nowTs; return; } if (deltaQuota < 1) { // 腾出空间太小，最小单位是 1 return; } this.leftQuota += deltaQuota; this.leakingTs = nowTs; // 流出的数据总量超过漏斗容量，说明漏斗在某些时间是空的，没有实际数据漏出 if (this.leftQuota > this.capacity) { this.leftQuota = this.capacity; } } boolean watering(int quota) { makeSpace(); //比较当前加入的数据量和漏斗剩余容量 if (this.leftQuota >= quota) { this.leftQuota -= quota; return true; } return false; } } // 用一个HashMap存储漏斗数据 private Map<String, Funnel> funnels = new HashMap<>(); public boolean isActionAllowed(String userId, String actionKey, int capacity, float leakingRate){ // 唯一key String key = String.format("%s:%s", userId, actionKey); Funnel funnel = funnels.get(key); if (funnel == null) { funnel = new Funnel(capacity, leakingRate); funnels.put(key, funnel); } return funnel.watering(1); // 需要 1 个 quota }} Redis-Cell
Redis中提供的一个限流Redis模块：redis-cell ，该模块使用漏斗算法并提供原子性的限流指令。
该redis指令：> cl.throttle key capacity operations times 1key：唯一的key代表该漏斗capacity：漏斗初始容量operations times ： 该时间长度内可以进行的最大操作数量，比如 30 60 表示60s内的操作次数最大是30 。1 ： 是一个可选参数，默认值是1 额外加餐：令牌桶限流
谷歌开源项目Guava中的RateLimiter使用的限流算法就是令牌桶限流算法。
网上找的图
以恒定的速度生成令牌并将令牌加到一个桶里，如果桶满了将其丢弃每个请求进来时都会到桶里拿一个令牌，如果没拿到（桶里没有令牌）拒绝该请求，若拿到则正常执行。