• 計數(shù)器
• 滑動窗口
• 漏桶
• 令牌桶

計數(shù)器

計數(shù)器是一種最簡單限流算法，其原理就是：在一段時間間隔內(nèi)，對請求進(jìn)行計數(shù)，與閥值進(jìn)行比較判斷是否需要限流，一旦到了時間臨界點，將計數(shù)器清零。
這種方法雖然簡單，但也有個大問題就是沒有很好的處理單位時間的邊界。

滑動窗口

滑動窗口是針對計數(shù)器存在的臨界點缺陷，所謂 滑動窗口（Sliding window） 是一種流量控制技術(shù)，這個詞出現(xiàn)在 TCP 協(xié)議中。滑動窗口把固定時間片進(jìn)行劃分，并且隨著時間的流逝，進(jìn)行移動，固定數(shù)量的可以移動的格子，進(jìn)行計數(shù)并判斷閥值。
假設(shè)一個時間窗口是一分鐘，每個時間窗口有 6 個格子，每個格子是 10 秒鐘。每過 10 秒鐘時間窗口向右移動一格。我們?yōu)槊總€格子都設(shè)置一個獨立的計數(shù)器 Counter，假如一個請求在 0:45 訪問了那么我們將第五個格子的計數(shù)器 +1（也是就是 0:40~0:50），在判斷限流的時候需要把所有格子的計數(shù)加起來和設(shè)定的頻次進(jìn)行比較即可。
想讓限流做的更精確只需要劃分更多的格子就可以了，為了更精確我們也不知道到底該設(shè)置多少個格子，格子的數(shù)量影響著滑動窗口算法的精度，依然有時間片的概念，無法根本解決臨界點問題。

漏桶

漏桶算法（Leaky Bucket），原理就是一個固定容量的漏桶，按照固定速率流出水滴。用過水龍頭都知道，打開龍頭開關(guān)水就會流下滴到水桶里，而漏桶指的是水桶下面有個漏洞可以出水。如果水龍頭開的特別大那么水流速就會過大，這樣就可能導(dǎo)致水桶的水滿了然后溢出。
一個固定容量的桶，有水流進(jìn)來，也有水流出去。對于流進(jìn)來的水來說，我們無法預(yù)計一共有多少水會流進(jìn)來，也無法預(yù)計水流的速度。但是對于流出去的水來說，這個桶可以固定水流出的速率（處理速度），從而達(dá)到 流量整形 和 流量控制 的效果。
漏桶算法有以下特點：

• 漏桶具有固定容量，出水速率是固定常量（流出請求）
• 如果桶是空的，則不需流出水滴
• 可以以任意速率流入水滴到漏桶（流入請求）
• 如果流入水滴超出了桶的容量，則流入的水滴溢出（新請求被拒絕）

漏桶限制的是常量流出速率（即流出速率是一個固定常量值），所以最大的速率就是出水的速率，不能出現(xiàn)突發(fā)流量。

type LeakyBucket struct {
    rate        int//固定每秒出水速率
    capacity    int //桶的容量
    water       int //桶中當(dāng)前水量
    requestList []*Request //請求隊列

    lock sync.Mutex
}

令牌桶

令牌桶算法（Token Bucket）是網(wǎng)絡(luò)流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送。
我們有一個固定的桶，桶里存放著令牌（token）。一開始桶是空的，系統(tǒng)按固定的時間（rate）往桶里添加令牌，直到桶里的令牌數(shù)滿，多余的請求會被丟棄。當(dāng)請求來的時候，從桶里移除一個令牌，如果桶是空的則拒絕請求或者阻塞。
令牌桶有以下特點：

• 令牌按固定的速率被放入令牌桶中
• 桶中最多存放 B 個令牌，當(dāng)桶滿時，新添加的令牌被丟棄或拒絕
• 如果桶中的令牌不足 N 個，則不會刪除令牌，且請求將被限流（丟棄或阻塞等待）

令牌桶限制的是平均流入速率（允許突發(fā)請求，只要有令牌就可以處理，支持一次拿3個令牌，4個令牌...），并允許一定程度突發(fā)流量。

type TokenBucket struct {
    rate         int //固定的token放入速率, r/s
    capacity     int //桶的容量
    tokens       int //桶中當(dāng)前token數(shù)量

    lock sync.Mutex
}

參考：
https://mp.weixin.qq.com/s/GOZkM2PGctqim4sp_uIEsg
https://mp.weixin.qq.com/s/-wU7SA8Hjh1Y2vOySdgGJw