限流又称为流量控制，是指限制到达系统的并发请求数，当达到限制条件则可以拒绝请求，可以起到保护下游服务，防止服务过载等作用

Go语言限流 : 链接

限流的常用处理手段有：计数器、滑动窗口、漏桶算法、令牌桶算法。
总结

  • 固定窗口计数器：比如我想限制1分钟以内请求为100个，从现在算起的一分钟内，请求就最多就是100个，这分钟过完的那一刻把计数器归零，重新计算，但这个算法会出现请求量是限制的两倍的情况。
  • 滑动窗口计数器：通过将窗口再细分，简单来说就是随着时间的推移，时间窗口也会持续移动，有一个计数器不断维护着窗口内的请求数量，这样就可以保证任意时间段内，都不会超过最大允许的请求数
  • 漏桶：可以将请求想象成是水流，水流可以任意速率流入漏桶中，同时漏桶以固定的速率将水流出，如果流入速度太大会导致水满溢出。缺陷也很明显，无法应对短时间内的突发请求
  • 令牌桶：先以固定的速率生成令牌，然后把令牌放到固定容量的桶里，如果超过桶容量的令牌则丢弃，每来一个请求则去桶中获取一次令牌，规定只有获得令牌的请求才能放行，没有获得令牌的请求则丢弃。优点是能够应对一定程度上的突发请求

计数器

image.png

固定窗口法是限流算法里面最简单的，比如我想限制1分钟以内请求为100个，从现在算起的一分钟内，请求就最多就是100个，这分钟过完的那一刻把计数器归零，重新计算，周而复始。
局限性：
这个方法虽然简单，但有个大问题是无法应对两个时间边界内的突发流量。如上图所示，如果在计数器清零的前1秒以及清零的后1秒都进来了100个请求，那么在短时间内服务器就接收到了两倍的(200个)请求，这样就有可能压垮系统。会导致上面的问题是因为我们的统计精度还不够，为了将临界问题的影响降低，我们可以使用滑动窗口法。

  1. def can_pass_fixed_window(user, action, time_zone=60, times=30):
  2.     """
  3.     :param user: 用户唯一标识
  4.     :param action: 用户访问的接口标识(即用户在客户端进行的动作)
  5.     :param time_zone: 接口限制的时间段
  6.     :param time_zone: 限制的时间段内允许多少请求通过
  7.     """
  8.     key = '{}:{}'.format(user, action)
  9.     # redis_conn 表示redis连接对象
  10.     count = redis_conn.get(key)
  11.     if not count:
  12.         count = 1
  13.         redis_conn.setex(key, time_zone, count)
  14.     if count < times:
  15.         redis_conn.incr(key)
  16.         return True
  17.     return False

滑动窗口

滑动窗口法，简单来说就是随着时间的推移，时间窗口也会持续移动，有一个计数器不断维护着窗口内的请求数量，这样就可以保证任意时间段内，都不会超过最大允许的请求数。例如当前时间窗口是0s~60s，请求数是40，10s后时间窗口就变成了10s~70s，请求数是60。
时间窗口的滑动和计数器可以使用redis的有序集合(sorted set)来实现。score的值用毫秒时间戳来表示，可以利用 当前时间戳 - 时间窗口的大小 来计算出窗口的边界，然后根据score的值做一个范围筛选就可以圈出一个窗口；value的值仅作为用户行为的唯一标识，也用毫秒时间戳就好。最后统计一下窗口内的请求数再做判断即可。
image.png
局限性：
虽然滑动窗口法避免了时间界限的问题，但是依然无法很好解决细时间粒度上面请求过于集中的问题，就例如限制了1分钟请求不能超过60次，请求都集中在59s时发送过来，这样滑动窗口的效果就大打折扣。 为了使流量更加平滑，我们可以使用更加高级的令牌桶算法和漏桶算法。

  1. def can_pass_slide_window(user, action, time_zone=60, times=30):
  2.     """
  3.     :param user: 用户唯一标识
  4.     :param action: 用户访问的接口标识(即用户在客户端进行的动作)
  5.     :param time_zone: 接口限制的时间段
  6.     :param time_zone: 限制的时间段内允许多少请求通过
  7.     """
  8.     key = '{}:{}'.format(user, action)
  9.     now_ts = time.time() * 1000
  10.     # value是什么在这里并不重要，只要保证value的唯一性即可，这里使用毫秒时间戳作为唯一值
  11.     value = now_ts
  12.     # 时间窗口左边界
  13.     old_ts = now_ts - (time_zone * 1000)
  14.     # 记录行为
  15.     redis_conn.zadd(key, value, now_ts)
  16.     # 删除时间窗口之前的数据
  17.     redis_conn.zremrangebyscore(key, 0, old_ts)
  18.     # 获取窗口内的行为数量
  19.     count = redis_conn.zcard(key)
  20.     # 设置一个过期时间免得占空间
  21.     redis_conn.expire(key, time_zone + 1)
  22.     if not count or count < times:
  23.         return True
  24.     return False

漏桶算法

uber团队有一个开源的uber-go/ratelimit库

虽然滑动窗口有效避免了时间临界点的问题，但是依然有时间片的概念，而漏桶算法在这方面比滑动窗口更加先进。
漏桶算法的思路与令牌桶算法有点相反。可以将请求想象成是水流，水流可以任意速率流入漏桶中，同时漏桶以固定的速率将水流出。如果流入速度太大会导致水满溢出，溢出的请求被丢弃。

  1. 给nginx配置一个处理请求速率。比如每秒处理5个请求。
  2. 大访问量下没有处理到的请求进行排队等待。
  3. 给排队的请求配置一个长度，超过了长度的请求直接返回错误 。比如设置队列长度为5，有5个请求正在排队的情况下，下一个请求直接返回错误。

image.png
通过上图可以看出漏桶法的特点是：不限制请求流入的速率，但是限制了请求流出的速率。这样突发流量可以被整形成一个稳定的流量，不会发生超频。

令牌桶

先以固定的速率生成令牌，然后把令牌放到固定容量的桶里，如果超过桶容量的令牌则丢弃，每来一个请求则去桶中获取一次令牌，规定只有获得令牌的请求才能放行，没有获得令牌的请求则丢弃。
image.png
局限性：
令牌桶法限制的是请求的平均流入速率，优点是能应对一定程度上的突发请求，也能在一定程度上保持流量的来源特征

  1. # 令牌桶法，具体步骤：
  2. # 请求来了就计算生成的令牌数，生成的速率有限制
  3. # 如果生成的令牌太多，则丢弃令牌
  4. # 有令牌的请求才能通过，否则拒绝
  6. def can_pass_token_bucket(user, action, time_zone=60, times=30):
  7.     """
  8.     :param user: 用户唯一标识
  9.     :param action: 用户访问的接口标识(即用户在客户端进行的动作)
  10.     :param time_zone: 接口限制的时间段
  11.     :param time_zone: 限制的时间段内允许多少请求通过
  12.     """
  13.     # 请求来了就倒水，倒水速率有限制
  14.     key = '{}:{}'.format(user, action)
  15.     rate = times / time_zone # 令牌生成速度
  16.     capacity = times # 桶容量
  17.     tokens = redis_conn.hget(key, 'tokens') # 看桶中有多少令牌
  18.     last_time = redis_conn.hget(key, 'last_time') # 上次令牌生成时间
  19.     now = time.time()
  20.     tokens = int(tokens) if tokens else capacity
  21.     last_time = int(last_time) if last_time else now
  22.     delta_tokens = (now - last_time) * rate # 经过一段时间后生成的令牌
  23.     if delta_tokens > 1:
  24.         tokens = tokens + tokens # 增加令牌
  25.         if tokens > tokens:
  26.             tokens = capacity
  27.         last_time = time.time() # 记录令牌生成时间
  28.         redis_conn.hset(key, 'last_time', last_time)
  30.     if tokens >= 1:
  31.         tokens -= 1 # 请求进来了，令牌就减少1
  32.         redis_conn.hset(key, 'tokens', tokens)
  33.         return True
  34.     return False

漏桶和令牌桶的区别

漏桶算法能够强行限制数据的传输速率，而令牌桶算法在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在令牌桶算法中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。