http://www.tuicool.com/articles/ZvURvq2
摘要
- 我們希望服務(wù)器能在請求流量的控制上有一定的自動控制能力；
- 本文通過簡介令牌桶算法和討論算法的 redis 實現(xiàn)給出流量整形(traffic shaping)的示例，來介紹網(wǎng)絡(luò)流量整形。
令牌桶算法
令牌桶算法 (token bucket) 并不是網(wǎng)絡(luò)流量整形中的奇技淫巧，而是非常常用的算法，從百度百科上已經(jīng)可以對它有一個概括的了解。對此算法的深入讀者可自行查閱研究，這里我通俗化的來解釋一下這個算法。
在令牌桶算法中，每一個訪客都擁有一個獨立的“令牌桶”，在這個“令牌桶”里放了一些“令牌”，訪客每次來訪都會消耗“令牌桶”中的“令牌”，如果“令牌桶”空了，將會對訪客做特殊處理（如拒絕其繼續(xù)訪問以達(dá)到限流的目的）。
問題一：訪客來訪是一個持續(xù)的過程，如果最初的“令牌”數(shù)目固定，“令牌桶”中的令牌會慢慢被消耗殆盡，這樣正常的訪客也將無法訪問—-所以我們需要以一個恒定的速率來向“令牌桶”中添加一定數(shù)量的“令牌”， 這樣就可以讓訪客持續(xù)的訪問。
問題二：我們以一個恒定速率向“令牌桶”中添加“令牌”， 那么如果訪客一直沒來訪他的“令牌桶”豈不會累積大量“令牌”么？—-所以，我們設(shè)定“令牌桶”中“令牌”的最大數(shù)量，“令牌桶”滿了就不需要再去添加了。這解決了“令牌”累積的問題，也使它更像一個“桶”。
如此，“令牌桶算法”中的重要的參數(shù)有：1. 給“令牌桶”添加“令牌”的速率（如果訪客以這個速率消耗令牌，將一直不會被限流）； 2. “令牌桶”的容量（如果消耗令牌的速率大于添加令牌的速率，將消耗桶中的存貨，如果消耗速率過大，令牌會被消耗殆盡，訪客將被限流）。注意：一般情況下“令牌桶”最初的狀態(tài)是滿的。
Redis
- 作為優(yōu)秀的內(nèi)存數(shù)據(jù)庫，redis 可以幫助我們在應(yīng)用層次快速響應(yīng)。本文不過多贅述 redis 的優(yōu)劣，你可以用 redis 做很多事情，在網(wǎng)絡(luò)流量整形方面，它是很好的實現(xiàn)方案， 下面我們來解析這樣一個方案。
Show me the code
- 說明：這是一段 Python 代碼，這段代碼來自 GitHub 用戶 justinfay 。為了使邏輯更清楚，我修改了代碼的部分內(nèi)容和注釋，以下是修改后的代碼，我們用這段代碼來看令牌桶算法的 redis 實現(xiàn)。
import redis from redis import WatchError import time RATE = 0.1 # 令牌桶的最大容量 DEFAULT = 100 # redis key 的過期時間 TIMEOUT = 60 * 60 r = redis.Redis() def token_bucket(tokens, key): pipe = r.pipeline() while 1: try: pipe.watch('%s:available' % key) pipe.watch('%s:ts' % key) current_ts = time.time() # 獲取令牌桶中剩余令牌 old_tokens = pipe.get('%s:available' % key) if old_tokens is None: current_tokens = DEFAULT else: old_ts = pipe.get('%s:ts' % key) # 通過時間戳計算這段時間內(nèi)應(yīng)該添加多少令牌，如果桶滿，令牌數(shù)取桶滿數(shù)。 current_tokens = float(old_tokens) + min( (current_ts - float(old_ts)) * RATE, DEFAULT - float(old_tokens) ) # 判斷剩余令牌是否足夠 if 0 <= tokens <= current_tokens: current_tokens -= tokens consumes = True else: consumes = False # 以下動作為更新 redis 中key的值，并跳出循環(huán)返回結(jié)果。 pipe.multi() pipe.set('%s:available' % key, current_tokens) pipe.expire('%s:available' % key, TIMEOUT) pipe.set('%s:ts' % key, current_ts) pipe.expire('%s:ts' % key, TIMEOUT) pipe.execute() break except WatchError: continue finally: pipe.reset() return consumes if __name__ == "__main__": tokens = 5 key = '192.168.1.1' if token_bucket(tokens, key): print 'haz tokens' else: print 'cant haz tokens'需要說的幾點
1. 這段代碼在網(wǎng)絡(luò)流量整形策略中起到什么作用?
- 對訪客的一次訪問，我們通過以上代碼可以來判斷此次訪問是否超過了我們的限制，通過返回的判斷結(jié)果，我們將對此次訪問選擇正確的處理策略，比如你可以拒絕消耗完令牌的訪客進(jìn)行訪問，從而控制他的訪問速率，從而達(dá)到網(wǎng)絡(luò)流量整形的目的。
2. redis 在其中如何工作？
- 對于每個獨立的訪客，redis 會為他建立兩個 key，一個 key 保存了剩余令牌的數(shù)量，另外一個 key 保存了最近一次訪問的時間戳。其中，最近一次訪問時間戳在新訪問到來時候用于計算時間間隔，從而計算在此時間間隔內(nèi)應(yīng)該向令牌桶中添加多少令牌，進(jìn)而獲得當(dāng)前令牌桶的剩余令牌數(shù)。
3. redis pipe 起到什么作用？
- 我們看到代碼中 while 循環(huán)，執(zhí)行了 redis pipe 中的 watch 動作，這是對 redis 事務(wù) 的使用。 這使這里的算法能處理并發(fā)的來訪。在 redis 中，事務(wù)執(zhí)行是對 redis key 的一個加鎖的操作，一個事務(wù)沒有執(zhí)行完，別的動作將無法操作這個 key ，代碼中循環(huán)執(zhí)行 watch 動作，就是去檢查當(dāng)前 key 是否有未執(zhí)行完畢的事務(wù)，只有所有事務(wù)都執(zhí)行的時候才可能進(jìn)入執(zhí)行體，完成令牌判斷或者消耗。 —— 這樣避免了并發(fā)的訪問在 set redis key 時候的混亂。
4. 如何調(diào)參
- 代碼中 RATE 和 DEFAULT 為主要參數(shù)，分別代表每秒鐘消耗令牌的速率，和令牌桶的容量。通過調(diào)整這兩個參數(shù)來控制你想要的訪問速率。
總結(jié)
- 這是一個實用的方式來完成網(wǎng)絡(luò)流量整形，可以有效控制一些爆發(fā)式的流量訪問，使訪問更加平滑容易控制。