[登錄那些事] 郵件發送，限流，漏桶與令牌桶

wpw 發布于2019-08-23 17:18 / 2657人閱讀

摘要：關于如何限速，有兩個比較出名的算法，漏桶算法與令牌桶算法，這里對其簡單介紹一下，最后再實踐在我發郵件的中以下是發送郵件的，已限制為一分鐘兩次，你可以通過修改進行試驗。

前段時間，我使用了 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漏桶算法令牌桶云服務器那些事發送郵件

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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