天天看點

限流及常用算法

适用場景

當系統需要應用高并發的沖擊時,一個最常用的政策是使用緩存提高系統容量,這通常是效果最好的方式,但如論如何提升系統容量,都會存在一個QPS/TPS的門檻值,超過該門檻值則認為系統不再穩定,是以需要采取措施屏蔽掉這些請求,達到系統穩定可用的目的。

實作這一目标的常見政策為限流:

限流,顧名思義就是限制流量的意思,既然支撐不了,那就不要死撐,而是采用拒絕服務、排隊、降級等手段保證核心功能穩定可用。

限流一般分為兩個層次:

  • 系統級
    • 現在系統龐大和複雜,系統級限流也即在系統入口處,根據限流政策,限流總并發,連接配接,請求數等,通常使用Nginx實作。
  • 應用級
    • 可以限流應用級的并發,總資源數,某時間視窗通路數等,實作起來非常靈活,主要思想基于令牌桶,漏桶等算法

令牌桶算法

一個固定大小存放令牌的桶,按照固定的速率往桶中添加令牌,如果到達一個請求,則從桶中拿走一個另外,如果桶中沒有令牌,則請求傳回或排隊。令牌桶可以應用瞬時流量沖擊(令牌桶滿的時候)

限流及常用算法

漏桶算法

漏桶算法也很好了解,桶的底部有一固定大小的孔,是以可以以固定流量流出,桶的頂部可以以任意速率向其中流入,直到桶滿。漏桶算法常用于流量整形(平滑流量),無論外部請求如何密集,系統以固定速率處理,保證系統不會被瞬時流量壓垮。

限流及常用算法

除此之外,也可以使用計數器進行限流,主要用于限制總并發數,如資料庫連接配接池、線程池等都是計數器的用法,隻要全局流量達到一定門檻值則進行限流。

實作思路

由于我們的應用基于Spring架構實作,對接口級别的限流很容易想到使用切面來實作。主要思路有:

  • 根據配置檔案,采用單例模式,建構每個受控方法的令牌桶對象
  • 使用AOP攔截對Controller層方法的通路
  • 檢查令牌桶中是否由令牌,如果沒有則傳回,有則繼續
限流及常用算法