令牌與漏桶的區(qū)別

 1. 漏桶是出，令牌是進
 2. 令牌是允許伸縮

漏桶算法

漏桶算法(Leaky Bucket)是網(wǎng)絡(luò)世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經(jīng)常使用的一種算法，它的主要目的是控制數(shù)據(jù)注入到網(wǎng)絡(luò)的速率，平滑網(wǎng)絡(luò)上的突發(fā)流量。漏桶算法提供了一種機制，通過它，突發(fā)流量可以被整形以便為網(wǎng)絡(luò)提供一個穩(wěn)定的流量。

漏桶可以看作是一個帶有常量服務(wù)時間的單服務(wù)器隊列，如果漏桶（包緩存）溢出，那么數(shù)據(jù)包會被丟棄。 在網(wǎng)絡(luò)中，漏桶算法可以控制端口的流量輸出速率，平滑網(wǎng)絡(luò)上的突發(fā)流量，實現(xiàn)流量整形，從而為網(wǎng)絡(luò)提供一個穩(wěn)定的流量。

如圖所示，把請求比作是水，水來了都先放進桶里，并以限定的速度出水，當水來得過猛而出水不夠快時就會導(dǎo)致水直接溢出，即拒絕服務(wù)。

image.png

可以看出，漏桶算法可以很好的控制流量的訪問速度，一旦超過該速度就拒絕服務(wù)。

令牌桶算法

令牌桶算法是網(wǎng)絡(luò)流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送。

令牌桶算法的原理是系統(tǒng)會以一個恒定的速度往桶里放入令牌，而如果請求需要被處理，則需要先從桶里獲取一個令牌，當桶里沒有令牌可取時，則拒絕服務(wù)。從原理上看，令牌桶算法和漏桶算法是相反的，一個“進水”，一個是“漏水”。

image.png

Google的Guava包中的RateLimiter類就是令牌桶算法的解決方案。

漏桶算法和令牌桶算法的選擇

漏桶算法與令牌桶算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。

漏桶算法與令牌桶算法的區(qū)別在于，漏桶算法能夠強行限制數(shù)據(jù)的傳輸速率，令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時還允許某種程度的突發(fā)傳輸。

需要注意的是，在某些情況下，漏桶算法不能夠有效地使用網(wǎng)絡(luò)資源，因為漏桶的漏出速率是固定的，所以即使網(wǎng)絡(luò)中沒有發(fā)生擁塞，漏桶算法也不能使某一個單獨的數(shù)據(jù)流達到端口速率。因此，漏桶算法對于存在突發(fā)特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發(fā)特性的流量。通常，漏桶算法與令牌桶算法結(jié)合起來為網(wǎng)絡(luò)流量提供更高效的控制。

常用的算法介紹

從簡單到復(fù)雜依次介紹了如下幾種算法：

1. Leaky Bucket
2. Fixed Window
3. Sliding Log
4. Sliding Window

Leaky Bucket

桶算法，做法是預(yù)先設(shè)置一個請求數(shù)的上限，小于這個上限的時候會接收請求， 大于這個上限的話會直接拒絕，只有等到系統(tǒng)處理掉了一些在桶里的請求， 桶里有新的坑位了，才會接收新的請求。

image

優(yōu)點：

1. 能夠平滑請求數(shù)，使系統(tǒng)以一個均勻的速率處理請求
2. 容易實現(xiàn)，可以用一個隊列／FIFO 來做
3. 可以只用很小的內(nèi)存做到為每個用戶限流

缺點：

1. 桶滿了以后，新的請求都會被扔掉，系統(tǒng)忙著處理舊請求
2. 無法保證請求能夠在一個固定的時間內(nèi)處理完

Fixed Window

固定窗口算法，設(shè)置一個時間段內(nèi)（窗口）接收的請求數(shù)，超過的這個請求數(shù)的請求會被丟棄。

• 窗口通常選擇人們熟悉的時間段：1 分鐘／1小時
• 窗口的起始時間通常是當前時間取地板（floor），比如 12:00:03 所在的窗口 （以一分鐘的窗口為例）就是 12:00:00 - 12:01:00

image

優(yōu)點：

1. 和漏桶相比，能夠讓新來的請求也能夠被處理到

缺點：

1. 在窗口的起始時間，最差情況下可能會帶來 2 倍的流量
2. 很多消費者可能都在等待窗口被重置，造成驚群效應(yīng)

Sliding Log

滑動日志算法，利用記錄下來的用戶的請求時間，請求數(shù)，當該用戶的一個新的 請求進來時，比較這個用戶在這個窗口內(nèi)的請求數(shù)是否超過了限定值，超過的話 就拒絕這個請求。

image

優(yōu)點：

1. 避免了固定窗口算法在窗口邊界可能出現(xiàn)的兩倍流量問題
2. 由于是針對每個用戶進行統(tǒng)計的，不會引發(fā)驚群效應(yīng)

缺點：

1. 需要保存大量的請求日志
2. 每個請求都需要考慮該用戶之前的請求情況，在分布式系統(tǒng)中尤其難做到

Sliding Window

滑動窗口算法，結(jié)合了固定窗口算法的低開銷和滑動日志算法能夠解決的邊界情 況。

1. 為每個窗口進行請求量的計數(shù)
2. 結(jié)合上一個窗口的請求量和這一個窗口已經(jīng)經(jīng)過的時間來計算出上限，以此 平滑請求尖鋒

舉例來說，限流的上限是每分鐘 10 個請求，窗口大小為 1 分鐘，上一個 窗口中總共處理了 6 個請求?，F(xiàn)在假設(shè)這個新的窗口已經(jīng)經(jīng)過了 20 秒，那么 到目前為止允許的請求上限就是 10 - 6 * (1 - 20 / 60) = 8。

image

滑動窗口算法是這些算法中最實用的算法：

1. 有很好的性能
2. 避免了漏桶算法帶來的饑餓問題
3. 避免了固定窗口算法的請求量突增的問題

分布式實現(xiàn)

同步的策略

難點在于限流上限都是針對全站的流量設(shè)置的，那么每個節(jié)點該如何協(xié)調(diào)各自處理的量呢？

解決的方法通常都是使用一個統(tǒng)一的數(shù)據(jù)庫來存放計數(shù)，比如 Redis 或者 Cassandra。 數(shù)據(jù)庫中將存放每個窗口和用戶的計數(shù)值。這種方法的主要問題是需要多訪問一次數(shù)據(jù)庫， 以及競爭問題。

競爭問題

image

競爭問題就是當有兩個以上的線程同時執(zhí)行 i += 1 的時候，如果沒有同步這 些操作的話，i 的值可能會有多種情況。

處理競爭問題可以通過加鎖來做，不過在限流的場景下，這樣做肯定會成為系統(tǒng)的瓶頸， 畢竟限流時每個請求都會來競爭這個鎖。

更好的辦法是通過 set-then-get 的方法，限流場景中用到的只是計數(shù) +1， 利用這一點以及數(shù)據(jù)庫實現(xiàn)的性能更好的原子操作可以達到我們的目的。

性能優(yōu)化

image

利用集中式的數(shù)據(jù)庫的另一個問題是每次請求都要查一下數(shù)據(jù)庫帶來的延遲開銷， 數(shù)據(jù)庫再快也會帶來幾毫秒的延遲。

解決這個問題的方法可以通過在內(nèi)存里面維護一個計數(shù)值，代價是稍微的放松限 流的精確度。通過設(shè)置一個定時任務(wù)從數(shù)據(jù)庫拿計數(shù)值，周期內(nèi)在內(nèi)存中維護這 個計數(shù)，周期結(jié)束時把計數(shù)同步到數(shù)據(jù)庫并拿取新的計數(shù)，如此往復(fù)。

這個同步周期往往是做成可以配置的，小的周期能夠帶來更精確的限流， 大的周期則能減輕數(shù)據(jù)庫的 I/O 壓力。

python 可用limits庫

https://github.com/hugoren/limits

可選用的limit策略

image.png