极客时间对于推广渠道会有返利优惠,比如山月在极客时间买了一门课,再把课程分享给好友购买,这时极客时间会向山月返利20元左右。
而我现在做了一个返利平台,你可以在上边通过山月的链接购买课程,此时极客时间会向我返利。为了共同学习,而你可以添加我的微信 (shanyue94),我将把极客时间给我的返利发一个红包全部返给你

# 邮件发送中的限流算法: 漏桶与令牌桶

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

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

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

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

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

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

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

  1. 【登录那些事】实现 Material Design 的登录样式 (opens new window)
  2. 【登录那些事】使用 jwt 登录与校验验证码 (opens new window)
  3. 【登录那些事】邮件发送,限流,漏桶与令牌桶 (opens new window)

本文地址:https://shanyue.tech/post/rate-limit/ (opens new window)

# 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的 INCREXPIRE 的原子性问题,容易造成 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 (令牌桶算法)

令牌算法

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

  1. 令牌桶初始状态 bucket 是满的,漏桶初始状态 bucket 是空的
  2. 令牌桶在 bucket 空的时候拒绝新的请求,漏桶在 bucket 满的时候拒绝新的请求
  3. 当一个请求来临时,假设一个请求消耗一个token,令牌桶的 bucket 减少一个 token,漏桶增加一个 token

以下使用 redis 实现令牌桶

TODO

关于山月

我的项目:
我的微信:shanyue94,欢迎交流
Last Updated: 7/21/2019, 11:25:08 AM