快捷導(dǎo)航

15行Python代碼帶你輕松理解令牌桶算法

更新時(shí)間：2018年03月21日 10:34:57 作者：simpleapples

這篇文章主要介紹了15行Python代碼帶你輕松理解令牌桶算法,需要的朋友可以參考下

在網(wǎng)絡(luò)中傳輸數(shù)據(jù)時(shí)，為了防止網(wǎng)絡(luò)擁塞，需限制流出網(wǎng)絡(luò)的流量，使流量以比較均勻的速度向外發(fā)送，令牌桶算法就實(shí)現(xiàn)了這個(gè)功能，可控制發(fā)送到網(wǎng)絡(luò)上數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送。

什么是令牌

從名字上看令牌桶，大概就是一個(gè)裝有令牌的桶吧，那么什么是令牌呢？

紫薇格格拿的令箭，可以發(fā)號施令，令行禁止。在計(jì)算機(jī)的世界中，令牌也有令行禁止的意思，有令牌，則相當(dāng)于得到了進(jìn)行操作的授權(quán)，沒有令牌，就什么都不能做。

用令牌實(shí)現(xiàn)限速器

我們用1塊令牌來代表發(fā)送1字節(jié)數(shù)據(jù)的資格，假設(shè)我們源源不斷的發(fā)放令牌給程序，程序就有資格源源不斷的發(fā)送數(shù)據(jù)，當(dāng)我們不發(fā)放令牌給程序，程序就相當(dāng)于被限流，無法發(fā)送數(shù)據(jù)了。接下來我們說說限速器，所謂限速器，就是讓程序在單位時(shí)間內(nèi)，最多只能發(fā)送一定大小的數(shù)據(jù)。假設(shè)在1秒發(fā)放10塊令牌，那么程序發(fā)送數(shù)據(jù)的速度就會(huì)被限制在10bytes/s。如果1秒內(nèi)有大于10bytes的數(shù)據(jù)需要發(fā)送，就會(huì)因?yàn)闆]有令牌而被丟棄。

改進(jìn)限速器——加個(gè)桶

我們實(shí)現(xiàn)的限速器，速度是恒定的，但是在實(shí)際的應(yīng)用中，往往會(huì)有突發(fā)的傳輸需求（需要更快速的發(fā)送，但是不會(huì)持續(xù)太久，也不會(huì)引起網(wǎng)絡(luò)擁塞），這種數(shù)據(jù)碰上我們的限速器，就因?yàn)槟貌坏搅钆贫鵁o法發(fā)送。

對限速器進(jìn)行一下改動(dòng)，依然1秒產(chǎn)生10塊令牌，但是我們把產(chǎn)生出來的令牌先放到一個(gè)桶里，當(dāng)程序需要發(fā)送的時(shí)候，從桶里取令牌，不需要的時(shí)候，令牌就會(huì)在桶里沉淀下來，假設(shè)桶里沉淀了10塊令牌，程序最多就可以在1秒內(nèi)發(fā)送20bytes的數(shù)據(jù)，滿足了突發(fā)數(shù)據(jù)傳輸?shù)囊螅⑶矣捎谕袄锏牧钆票挥猛?，下一秒最多依然只能發(fā)10bytes的數(shù)據(jù)，不會(huì)因?yàn)槌掷m(xù)發(fā)送大量數(shù)據(jù)，對網(wǎng)絡(luò)造成壓力。

15行Python代碼實(shí)踐令牌桶

令牌桶需要以一定的速度生成令牌放入桶中，當(dāng)程序要發(fā)送數(shù)據(jù)時(shí)，再從桶中取出令牌。這里似乎有點(diǎn)問題，如果我們使用一個(gè)死循環(huán)，來不停地發(fā)放令牌，程序就被阻塞住了，有沒有更好的辦法？

我們可以在取令牌的時(shí)候，用現(xiàn)在的時(shí)間減去上次取令牌的時(shí)間，乘以令牌的發(fā)放速度，計(jì)算出桶里可以取的令牌數(shù)量（當(dāng)然不能超過桶的大?。?，從而避免循環(huán)發(fā)放的邏輯。

接下來看代碼：

import time
class TokenBucket(object):
 # rate是令牌發(fā)放速度，capacity是桶的大小
 def __init__(self, rate, capacity):
  self._rate = rate
  self._capacity = capacity
  self._current_amount = 0
  self._last_consume_time = int(time.time())
 # token_amount是發(fā)送數(shù)據(jù)需要的令牌數(shù)
 def consume(self, token_amount):
  increment = (int(time.time()) - self._last_consume_time) * self._rate # 計(jì)算從上次發(fā)送到這次發(fā)送，新發(fā)放的令牌數(shù)量
  self._current_amount = min(
   increment + self._current_amount, self._capacity) # 令牌數(shù)量不能超過桶的容量
  if token_amount > self._current_amount: # 如果沒有足夠的令牌，則不能發(fā)送數(shù)據(jù)
   return False
  self._last_consume_time = int(time.time())
  self._current_amount -= token_amount
  return True

總結(jié)

以上所述是小編給大家介紹的15行Python代碼帶你輕松理解令牌桶算法，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！