05.15 限流算法之令牌桶算法、漏桶算法

首先我們要明白限流是什麼?

限流定義

限流的目的是通過對併發訪問/請求進行限速或者一個時間窗口內的請求進行限速來保護系統,一旦到達限制速率則可以拒絕服務(一般是定向到錯誤頁或者告知資源不足)。

限流算法

限流算法之令牌桶算法、漏桶算法

令牌桶算法

聲明一個固定容量的桶,然後固定的向這個桶添加令牌,具體算法如下:

  1. 假設限制2qps,那麼按照每500ms向令牌桶添加令牌

  2. 同種最多存放b個令牌,當桶滿了的時候,新添加的令牌丟棄

  3. 當一個有請求到達時,首先去令牌桶獲取令牌,能夠取到,則處理這個請求

  4. 如果桶中沒有令牌,那麼請求排隊或者丟棄

漏桶算法

聲明一個固定容量的桶,每接受到一個請求向桶中添加一個令牌,桶滿請求丟棄,具體算法如下:


  1. 一個固定容量的漏桶,請求到達時向漏桶添加一個令牌

  2. 如果請求添加令牌不成功,請求丟棄

  3. 另一個線程以固定的速率消費桶裡的令牌

對比

其實不難看出,漏桶算法允許一定的突發出現(當桶不滿的時候),滿載運行情況下兩者的限流是一樣的。


分享到:


相關文章: