[登录那些事] 邮件发送，限流，漏桶与令牌桶

wpw 发布于2019-08-23 17:18 / 2639人阅读

摘要：关于如何限速，有两个比较出名的算法，漏桶算法与令牌桶算法，这里对其简单介绍一下，最后再实践在我发邮件的中以下是发送邮件的，已限制为一分钟两次，你可以通过修改进行试验。

前段时间，我使用了 jwt 来实现邮箱验证码的校验与用户认证与登录，还特别写了一篇文章作为总结。

在那篇文章中，提到了一个点，如何限速。

在短信验证码和邮箱验证码，如果不限速，被恶意攻击造成大量的 QPS，不仅拖垮了服务，也会心疼如水的资费。鉴于君子固穷的原则，在我的邮箱服务里加上限速。

关于如何限速，有两个比较出名的算法，漏桶算法与令牌桶算法，这里对其简单介绍一下，最后再实践在我发邮件的API中

以下是发送邮件的 API，已限制为一分钟两次，你可以通过修改 email 进行试验。你也可以在我的站点直接试验

curl "https://graphql.xiange.tech/graphql" -H "Content-Type: application/json" --data-binary "{"query":"mutation SEND($email: String!) {
  sendEmailVerifyCode (email: $email)
}","variables":{"email":"xxxxxx@qq.com"}}"

以下是我关于登录实践的系列文章

【登录那些事】实现 Material Design 的登录样式

【登录那些事】使用 jwt 登录与校验验证码

【登录那些事】邮件发送，限流，漏桶与令牌桶

本文地址：https://shanyue.tech/post/rat...

Leaky Bucket (漏桶算法)

漏桶算法表示水滴（请求）先进入到漏桶里，漏桶（bucket）以一定的速度出水，当漏桶中水满时，无法再加水。

维护一个计数器作为 bucket，计数器的上限为 bucket 的大小

计数器满时拒绝请求

每隔一段时间清空计数器

用 option 代表在 option.window 的窗口时间内最多可以通过 option.max 次请求

以下是使用 redis 的计数器实现限流的伪代码

const option = {
  max: 10,        // window 时间内限速10个请求
  window: 1000    // 1s
}

function access(req) {
  // 根据请求生成唯一标志
  const key = identity(req)
  // 计数器自增
  const counter = redis.incr(key)
  if (counter === 1) {
    // 如果是当前时间窗口的第一个请求，设置过期时间
    redis.expire(key, window) 
  }
  if (counter > option.window) {
    return false
  }
  return true
}

这里有 Redis 官方使用 INCR 实现限流的文档 https://redis.io/commands/INCR

此时有一个不算问题的问题，就是它的时间窗口并不是滑动窗口那样在桶里出去一个球，就可以再进来一个球。而更像是一个固定时间窗口，从桶里出去一群球，再开始进球。正因为如此，它可能在固定窗口的后一半时间收到 max-1 次请求，又在下一个固定窗口内打来 max 次请求，此时在一个随机的窗口时间内最多会有 2 * max - 1 次请求。

另外还有一个redis的 INCR 与 EXPIRE 的原子性问题，容易造成 Race Condition，可以通过 SETNX 来解决

redis.set(key, 0, "EX", option.window, "NX")

另外也可以通过一个 LUA 脚本来搞定，显然还是 SETNX 简单些

local current
current = redis.call("incr",KEYS[1])
if tonumber(current) == 1 then
    redis.call("expire",KEYS[1],1)
end

为了解决 2N 的问题，可以由维护一个计数器，更改为维护一个队列。代价是内存占用空间过高，且更难解决 Race Condition

以下是使用 redis 的 set/get string 实现的限流

const option = {
  max: 10,        // window 时间内限速10个请求
  window: 1000    // 1s
}

function access(req) {
  // 根据请求生成唯一标志
  const key = identity(req)
  const current = Date.now()
  // cache 视为缓存对象
  // 筛选出当前时间窗口的请求个数，每个请求标志为时间戳的格式
  // 为了简单这里不做 json 的序列化和反序列化了...
  const timestamps = [current].concat(redis.get("timestamps")).filter(ts => ts + option.window > current)
  if (timestamps.length > option.max) {
    return false 
  }
  // 此时读写不同步，会有 Race Condition 问题
  redis.set("timestamps", timestamps, "EX", option.window)
  return true
}

这里再使用一个 LUA 脚本解决 Race Condition 的问题

TODO

Token Bucket (令牌桶算法)

由图先看一看令牌桶与漏桶的不同

令牌桶初始状态 bucket 是满的，漏桶初始状态 bucket 是空的

令牌桶在 bucket 空的时候拒绝新的请求，漏桶在 bucket 满的时候拒绝新的请求

当一个请求来临时，假设一个请求消耗一个token，令牌桶的 bucket 减少一个 token，漏桶增加一个 token

以下使用 redis 实现令牌桶

TODO

GPU云服务器云服务器 webrtc漏桶算法令牌桶云服务器那些事发送邮件

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104139.html

接口限流的常用算法汇总

摘要：接口限流的常用算法计数器法计数器法是限流算法里最简单也是最容易实现的一种算法。由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。漏桶算法漏桶算法，又称。接口限流什么是接口限流那么什么是限流呢？顾名思义，限流就是限制流量，包括并发的流量和一定时间内的总流量，就像你宽带包了1个G的流量，用完了就没了，所以控制你的使用频率和单次使用的总消耗。通过限...

gyl_coder 2019-06-27 15:37 评论0 收藏0
限流器及Guava实现分析

摘要：计数限流算法无论固定窗口还是滑动窗口核心均是对请求进行计数，区别仅仅在于对于计数时间区间的处理。令牌桶限流实现原理令牌桶限流的实现原理在有详细说明。因此由此为入口进行分析。目前可返回的实现子类包括及两种，具体不同下文详细分析。限流限流一词常用于计算机网络之中，定义如下： In computer networks, rate limiting is used to control t...

xcc3641 2019-08-19 11:05 评论0 收藏0
几种限流技术

摘要：下面是几种常见的限流技术一限流算法常用的限流算法有令牌桶，漏桶令牌桶令牌桶算法是网络流量整形和速率限制中最常使用的一种算法。就秒杀接口来说，当访问频率或者并发请求超过其承受范围的时候，这时候我们就要考虑限流来保证接口的可用性，以防止非预期的请求对系统压力过大而引起的系统瘫痪。通常的策略就是拒绝多余的访问，或者让多余的访问排队等待服务。下面是几种常见的限流技术一、限流算法常用的限流算...

Warren 2019-08-16 17:30 评论0 收藏0
接口限流算法：漏桶算法&令牌桶算法

摘要：令牌桶算法漏桶算法漏桶漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉也就是所谓的溢出。工作中对外提供的API 接口设计都要考虑限流，如果不考虑限流，会成系统的连锁反应，轻者响应缓慢，重者系统宕机，整个业务线崩溃，如何应对这种情况呢，我们可以对请求进行引流或者直接拒绝等操作，保持系统的可用性和稳定性，防止因流量暴增而导致的系统运行缓慢或宕机。在开发高并发...

dendoink 2019-08-19 10:55 评论0 收藏0