• 計(jì)數(shù)器
• 滑動(dòng)窗口
• 漏桶
• 令牌桶

計(jì)數(shù)器

計(jì)數(shù)器是一種最簡(jiǎn)單限流算法运挫，其原理就是：在一段時(shí)間間隔內(nèi)侵俗，對(duì)請(qǐng)求進(jìn)行計(jì)數(shù)痛倚，與閥值進(jìn)行比較判斷是否需要限流殿较，一旦到了時(shí)間臨界點(diǎn)耸峭，將計(jì)數(shù)器清零。
這種方法雖然簡(jiǎn)單淋纲，但也有個(gè)大問(wèn)題就是沒有很好的處理單位時(shí)間的邊界劳闹。

滑動(dòng)窗口

滑動(dòng)窗口是針對(duì)計(jì)數(shù)器存在的臨界點(diǎn)缺陷，所謂 滑動(dòng)窗口（Sliding window） 是一種流量控制技術(shù)洽瞬，這個(gè)詞出現(xiàn)在 TCP 協(xié)議中本涕。滑動(dòng)窗口把固定時(shí)間片進(jìn)行劃分伙窃，并且隨著時(shí)間的流逝菩颖，進(jìn)行移動(dòng)，固定數(shù)量的可以移動(dòng)的格子为障，進(jìn)行計(jì)數(shù)并判斷閥值晦闰。
假設(shè)一個(gè)時(shí)間窗口是一分鐘，每個(gè)時(shí)間窗口有 6 個(gè)格子鳍怨，每個(gè)格子是 10 秒鐘呻右。每過(guò) 10 秒鐘時(shí)間窗口向右移動(dòng)一格。我們?yōu)槊總€(gè)格子都設(shè)置一個(gè)獨(dú)立的計(jì)數(shù)器 Counter鞋喇，假如一個(gè)請(qǐng)求在 0:45 訪問(wèn)了那么我們將第五個(gè)格子的計(jì)數(shù)器 +1（也是就是 0:40~0:50）声滥，在判斷限流的時(shí)候需要把所有格子的計(jì)數(shù)加起來(lái)和設(shè)定的頻次進(jìn)行比較即可。
想讓限流做的更精確只需要?jiǎng)澐指嗟母褡泳涂梢粤巳丰悖瑸榱烁_我們也不知道到底該設(shè)置多少個(gè)格子醒串，格子的數(shù)量影響著滑動(dòng)窗口算法的精度，依然有時(shí)間片的概念鄙皇，無(wú)法根本解決臨界點(diǎn)問(wèn)題芜赌。

漏桶

漏桶算法（Leaky Bucket），原理就是一個(gè)固定容量的漏桶伴逸，按照固定速率流出水滴缠沈。用過(guò)水龍頭都知道，打開龍頭開關(guān)水就會(huì)流下滴到水桶里，而漏桶指的是水桶下面有個(gè)漏洞可以出水洲愤。如果水龍頭開的特別大那么水流速就會(huì)過(guò)大颓芭，這樣就可能導(dǎo)致水桶的水滿了然后溢出。
一個(gè)固定容量的桶柬赐，有水流進(jìn)來(lái)亡问，也有水流出去。對(duì)于流進(jìn)來(lái)的水來(lái)說(shuō)肛宋，我們無(wú)法預(yù)計(jì)一共有多少水會(huì)流進(jìn)來(lái)州藕，也無(wú)法預(yù)計(jì)水流的速度。但是對(duì)于流出去的水來(lái)說(shuō)酝陈，這個(gè)桶可以固定水流出的速率（處理速度）床玻，從而達(dá)到 流量整形 和 流量控制 的效果。
漏桶算法有以下特點(diǎn)：

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

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

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

    lock sync.Mutex
}

令牌桶

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

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

令牌桶限制的是平均流入速率（允許突發(fā)請(qǐng)求，只要有令牌就可以處理都办，支持一次拿3個(gè)令牌嫡锌，4個(gè)令牌...）虑稼，并允許一定程度突發(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