http://www.tuicool.com/articles/ZvURvq2
摘要
- 我們希望服務器能在請求流量的控制上有一定的自動控制能力；
- 本文通過簡介令牌桶算法和討論算法的 redis 實現給出流量整形(traffic shaping)的示例，來介紹網絡流量整形。
令牌桶算法
令牌桶算法 (token bucket) 并不是網絡流量整形中的奇技淫巧，而是非常常用的算法，從百度百科上已經可以對它有一個概括的了解。對此算法的深入讀者可自行查閱研究，這里我通俗化的來解釋一下這個算法。
在令牌桶算法中，每一個訪客都擁有一個獨立的“令牌桶”，在這個“令牌桶”里放了一些“令牌”，訪客每次來訪都會消耗“令牌桶”中的“令牌”，如果“令牌桶”空了，將會對訪客做特殊處理（如拒絕其繼續訪問以達到限流的目的）。
問題一：訪客來訪是一個持續的過程，如果最初的“令牌”數目固定，“令牌桶”中的令牌會慢慢被消耗殆盡，這樣正常的訪客也將無法訪問—-所以我們需要以一個恒定的速率來向“令牌桶”中添加一定數量的“令牌”， 這樣就可以讓訪客持續的訪問。
問題二：我們以一個恒定速率向“令牌桶”中添加“令牌”， 那么如果訪客一直沒來訪他的“令牌桶”豈不會累積大量“令牌”么？—-所以，我們設定“令牌桶”中“令牌”的最大數量，“令牌桶”滿了就不需要再去添加了。這解決了“令牌”累積的問題，也使它更像一個“桶”。
如此，“令牌桶算法”中的重要的參數有：1. 給“令牌桶”添加“令牌”的速率（如果訪客以這個速率消耗令牌，將一直不會被限流）； 2. “令牌桶”的容量（如果消耗令牌的速率大于添加令牌的速率，將消耗桶中的存貨，如果消耗速率過大，令牌會被消耗殆盡，訪客將被限流）。注意：一般情況下“令牌桶”最初的狀態是滿的。
Redis
- 作為優秀的內存數據庫，redis 可以幫助我們在應用層次快速響應。本文不過多贅述 redis 的優劣，你可以用 redis 做很多事情，在網絡流量整形方面，它是很好的實現方案， 下面我們來解析這樣一個方案。
Show me the code
- 說明：這是一段 Python 代碼，這段代碼來自 GitHub 用戶 justinfay 。為了使邏輯更清楚，我修改了代碼的部分內容和注釋，以下是修改后的代碼，我們用這段代碼來看令牌桶算法的 redis 實現。
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) # 通過時間戳計算這段時間內應該添加多少令牌，如果桶滿，令牌數取桶滿數。 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的值，并跳出循環返回結果。 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. 這段代碼在網絡流量整形策略中起到什么作用?
- 對訪客的一次訪問，我們通過以上代碼可以來判斷此次訪問是否超過了我們的限制，通過返回的判斷結果，我們將對此次訪問選擇正確的處理策略，比如你可以拒絕消耗完令牌的訪客進行訪問，從而控制他的訪問速率，從而達到網絡流量整形的目的。
2. redis 在其中如何工作？
- 對于每個獨立的訪客，redis 會為他建立兩個 key，一個 key 保存了剩余令牌的數量，另外一個 key 保存了最近一次訪問的時間戳。其中，最近一次訪問時間戳在新訪問到來時候用于計算時間間隔，從而計算在此時間間隔內應該向令牌桶中添加多少令牌，進而獲得當前令牌桶的剩余令牌數。
3. redis pipe 起到什么作用？
- 我們看到代碼中 while 循環，執行了 redis pipe 中的 watch 動作，這是對 redis 事務 的使用。 這使這里的算法能處理并發的來訪。在 redis 中，事務執行是對 redis key 的一個加鎖的操作，一個事務沒有執行完，別的動作將無法操作這個 key ，代碼中循環執行 watch 動作，就是去檢查當前 key 是否有未執行完畢的事務，只有所有事務都執行的時候才可能進入執行體，完成令牌判斷或者消耗。 —— 這樣避免了并發的訪問在 set redis key 時候的混亂。
4. 如何調參
- 代碼中 RATE 和 DEFAULT 為主要參數，分別代表每秒鐘消耗令牌的速率，和令牌桶的容量。通過調整這兩個參數來控制你想要的訪問速率。
總結
- 這是一個實用的方式來完成網絡流量整形，可以有效控制一些爆發式的流量訪問，使訪問更加平滑容易控制。