令牌與漏桶的區(qū)別
1. 漏桶是出，令牌是進
2. 令牌是允許伸縮
漏桶算法
漏桶算法(Leaky Bucket)是網(wǎng)絡世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經(jīng)常使用的一種算法，它的主要目的是控制數(shù)據(jù)注入到網(wǎng)絡的速率交汤，平滑網(wǎng)絡上的突發(fā)流量琴许。漏桶算法提供了一種機制，通過它晾浴，突發(fā)流量可以被整形以便為網(wǎng)絡提供一個穩(wěn)定的流量负乡。
漏桶可以看作是一個帶有常量服務時間的單服務器隊列，如果漏桶（包緩存）溢出脊凰，那么數(shù)據(jù)包會被丟棄抖棘。 在網(wǎng)絡中，漏桶算法可以控制端口的流量輸出速率狸涌，平滑網(wǎng)絡上的突發(fā)流量切省，實現(xiàn)流量整形，從而為網(wǎng)絡提供一個穩(wěn)定的流量杈抢。
如圖所示数尿，把請求比作是水，水來了都先放進桶里惶楼，并以限定的速度出水右蹦，當水來得過猛而出水不夠快時就會導致水直接溢出，即拒絕服務歼捐。
可以看出何陆，漏桶算法可以很好的控制流量的訪問速度，一旦超過該速度就拒絕服務豹储。
令牌桶算法
令牌桶算法是網(wǎng)絡流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法贷盲。典型情況下，令牌桶算法用來控制發(fā)送到網(wǎng)絡上的數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送巩剖。
令牌桶算法的原理是系統(tǒng)會以一個恒定的速度往桶里放入令牌铝穷，而如果請求需要被處理，則需要先從桶里獲取一個令牌佳魔，當桶里沒有令牌可取時曙聂，則拒絕服務。從原理上看鞠鲜，令牌桶算法和漏桶算法是相反的宁脊，一個“進水”，一個是“漏水”贤姆。
Google的Guava包中的RateLimiter類就是令牌桶算法的解決方案榆苞。
漏桶算法和令牌桶算法的選擇
漏桶算法與令牌桶算法在表面看起來類似，很容易將兩者混淆霞捡。但事實上坐漏，這兩者具有截然不同的特性，且為不同的目的而使用弄砍。
漏桶算法與令牌桶算法的區(qū)別在于仙畦，漏桶算法能夠強行限制數(shù)據(jù)的傳輸速率，令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時還允許某種程度的突發(fā)傳輸音婶。
需要注意的是慨畸，在某些情況下，漏桶算法不能夠有效地使用網(wǎng)絡資源衣式，因為漏桶的漏出速率是固定的寸士，所以即使網(wǎng)絡中沒有發(fā)生擁塞，漏桶算法也不能使某一個單獨的數(shù)據(jù)流達到端口速率碴卧。因此弱卡，漏桶算法對于存在突發(fā)特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發(fā)特性的流量住册。通常婶博，漏桶算法與令牌桶算法結(jié)合起來為網(wǎng)絡流量提供更高效的控制。
常用的算法介紹
從簡單到復雜依次介紹了如下幾種算法：
- Leaky Bucket
- Fixed Window
- Sliding Log
- Sliding Window
Leaky Bucket
桶算法荧飞，做法是預先設置一個請求數(shù)的上限凡人，小于這個上限的時候會接收請求， 大于這個上限的話會直接拒絕叹阔，只有等到系統(tǒng)處理掉了一些在桶里的請求挠轴， 桶里有新的坑位了，才會接收新的請求耳幢。
優(yōu)點：
- 能夠平滑請求數(shù)岸晦，使系統(tǒng)以一個均勻的速率處理請求
- 容易實現(xiàn)，可以用一個隊列／FIFO 來做
- 可以只用很小的內(nèi)存做到為每個用戶限流
缺點：
- 桶滿了以后，新的請求都會被扔掉启上，系統(tǒng)忙著處理舊請求
- 無法保證請求能夠在一個固定的時間內(nèi)處理完
Fixed Window
固定窗口算法邢隧，設置一個時間段內(nèi)（窗口）接收的請求數(shù)，超過的這個請求數(shù)的請求會被丟棄冈在。
- 窗口通常選擇人們熟悉的時間段：1 分鐘／1小時
- 窗口的起始時間通常是當前時間取地板（floor）府框，比如 12:00:03 所在的窗口 （以一分鐘的窗口為例）就是 12:00:00 - 12:01:00
優(yōu)點：
- 和漏桶相比，能夠讓新來的請求也能夠被處理到
缺點：
- 在窗口的起始時間讥邻，最差情況下可能會帶來 2 倍的流量
- 很多消費者可能都在等待窗口被重置，造成驚群效應
Sliding Log
滑動日志算法院峡，利用記錄下來的用戶的請求時間兴使，請求數(shù)，當該用戶的一個新的 請求進來時照激，比較這個用戶在這個窗口內(nèi)的請求數(shù)是否超過了限定值发魄，超過的話 就拒絕這個請求。
優(yōu)點：
- 避免了固定窗口算法在窗口邊界可能出現(xiàn)的兩倍流量問題
- 由于是針對每個用戶進行統(tǒng)計的俩垃，不會引發(fā)驚群效應
缺點：
- 需要保存大量的請求日志
- 每個請求都需要考慮該用戶之前的請求情況励幼，在分布式系統(tǒng)中尤其難做到
Sliding Window
滑動窗口算法，結(jié)合了固定窗口算法的低開銷和滑動日志算法能夠解決的邊界情 況口柳。
- 為每個窗口進行請求量的計數(shù)
- 結(jié)合上一個窗口的請求量和這一個窗口已經(jīng)經(jīng)過的時間來計算出上限苹粟，以此 平滑請求尖鋒
舉例來說，限流的上限是每分鐘 10 個請求跃闹，窗口大小為 1 分鐘嵌削，上一個 窗口中總共處理了 6 個請求。現(xiàn)在假設這個新的窗口已經(jīng)經(jīng)過了 20 秒望艺，那么 到目前為止允許的請求上限就是 10 - 6 * (1 - 20 / 60) = 8苛秕。
滑動窗口算法是這些算法中最實用的算法：
- 有很好的性能
- 避免了漏桶算法帶來的饑餓問題
- 避免了固定窗口算法的請求量突增的問題
分布式實現(xiàn)
同步的策略
難點在于限流上限都是針對全站的流量設置的，那么每個節(jié)點該如何協(xié)調(diào)各自處理的量呢找默？
解決的方法通常都是使用一個統(tǒng)一的數(shù)據(jù)庫來存放計數(shù)艇劫，比如 Redis 或者 Cassandra。 數(shù)據(jù)庫中將存放每個窗口和用戶的計數(shù)值惩激。這種方法的主要問題是需要多訪問一次數(shù)據(jù)庫店煞， 以及競爭問題。
競爭問題
競爭問題就是當有兩個以上的線程同時執(zhí)行 i += 1 的時候咧欣，如果沒有同步這 些操作的話浅缸，i 的值可能會有多種情況。
處理競爭問題可以通過加鎖來做魄咕，不過在限流的場景下衩椒，這樣做肯定會成為系統(tǒng)的瓶頸， 畢竟限流時每個請求都會來競爭這個鎖。
更好的辦法是通過 set-then-get 的方法毛萌，限流場景中用到的只是計數(shù) +1苟弛， 利用這一點以及數(shù)據(jù)庫實現(xiàn)的性能更好的原子操作可以達到我們的目的。
性能優(yōu)化
利用集中式的數(shù)據(jù)庫的另一個問題是每次請求都要查一下數(shù)據(jù)庫帶來的延遲開銷阁将， 數(shù)據(jù)庫再快也會帶來幾毫秒的延遲膏秫。
解決這個問題的方法可以通過在內(nèi)存里面維護一個計數(shù)值，代價是稍微的放松限 流的精確度做盅。通過設置一個定時任務從數(shù)據(jù)庫拿計數(shù)值缤削，周期內(nèi)在內(nèi)存中維護這 個計數(shù)，周期結(jié)束時把計數(shù)同步到數(shù)據(jù)庫并拿取新的計數(shù)吹榴，如此往復亭敢。
這個同步周期往往是做成可以配置的，小的周期能夠帶來更精確的限流图筹， 大的周期則能減輕數(shù)據(jù)庫的 I/O 壓力帅刀。
python 可用limits庫
https://github.com/hugoren/limits
可選用的limit策略
