Token Bucket為令牌桶算法，常被用于流量整形，或?qū)蛻舳说南匏佟?/p>

假設(shè)家里是200M的寬帶， 為了保證打游戲的流暢，我要把電視設(shè)置為10M。那么實(shí)現(xiàn)上可以如下：

?

方案一：

累加電視的所有接收/發(fā)出的數(shù)據(jù)包長(zhǎng)度，如果超出10M，則丟棄報(bào)文；每秒更新一次累加值為0。

思路非常簡(jiǎn)單，也非常實(shí)用；從長(zhǎng)時(shí)間統(tǒng)計(jì)上看，結(jié)果上偏差不大。

但可能限制出來(lái)流量圖就會(huì)如下，不均勻，像抽風(fēng)似的。如果設(shè)置了10條限速規(guī)則對(duì)10個(gè)設(shè)備進(jìn)行限速時(shí)，則每秒開始的0.1秒，CPU壓力很大，然后0.9秒很閑。

?

這種漏桶似的算法，利用率和平衡性較差。

方案二：

如果改進(jìn)一下，將統(tǒng)計(jì)時(shí)間細(xì)化0.1秒，將效果會(huì)好不少。再進(jìn)一步，將時(shí)間細(xì)化到每個(gè)報(bào)文接收，則效果就達(dá)到極致。

這就是Token Bucket做的事情。

?

流程出下：

1、當(dāng)收到數(shù)據(jù)報(bào)文時(shí)，先試圖獲取token，如果剩余token足夠則放行；

2、不夠則更新token，等待token足夠再繼續(xù)。token按指定速率添加到bucket中，超過(guò)其容量則設(shè)置為最大值。

預(yù)期效果圖如下：

?

示例代碼實(shí)現(xiàn)如下：假設(shè)允許的速率每秒100，模擬包長(zhǎng)在50~100隨機(jī)，統(tǒng)計(jì)一下發(fā)送時(shí)間和平均速率。

?

# -- coding: utf-8 -- # Good luck.import time import randomclass tb():def __init__(self, token_per_sec):self.captoken = token_per_secself.curr_token = 0self.timestamp = time.time()def refill(self):if time.time() > self.timestamp:refill_token = self.captoken*(time.time() - self.timestamp)self.curr_token = min(self.curr_token + refill_token, self.captoken)print "\tRefill tokens Current: %d. (Add %d)" %(self.curr_token, refill_token)self.timestamp = time.time()else:print "\tNo refill...."def consume(self, num):ret = Falseif self.curr_token > 0: # Control precisionself.curr_token -= numprint "\tGet token %d : remain %d" %(num, self.curr_token)ret = Trueself.refill()return rettest = tb(100) run_time = time.time() all_len = 0; times = 0while True:t = 0.1ts = time.time()send_len = random.randint(10, 50)print "Need send %d" %(send_len)while not test.consume(send_len):time.sleep(t)te = time.time()print "Use Time:%s Send:%d " %(te-ts, send_len)all_len += send_lentimes += 1print "Avg = %s (times=%d)" %(all_len/(ts - run_time+0.1), times)time.sleep(t)

運(yùn)行效果

C:\Python27\python.exe X:/GIT/wxy_code_backup/Flash_tools/tokenbucket.py

Need send 44

No refill....

Refill tokens Current: 9. (Add 9)

Get token 44 : remain -34

Refill tokens Current: -23. (Add 10)

Use Time:0.200999975204 Send:44

Avg = 440.0 (times=1)

Need send 27

Refill tokens Current: -13. (Add 9)

Refill tokens Current: -3. (Add 10)

Refill tokens Current: 6. (Add 10)

Get token 27 : remain -20

Refill tokens Current: -10. (Add 10)

Use Time:0.302000045776 Send:27

Avg = 177.057409665 (times=2)

Need send 33

Refill tokens Current: 0. (Add 10)

Refill tokens Current: 9. (Add 10)

Get token 33 : remain -23

Refill tokens Current: -13. (Add 10)

Use Time:0.200999975204 Send:33

Avg = 129.51431022 (times=3)

Need send 42

Refill tokens Current: -3. (Add 10)

Refill tokens Current: 6. (Add 10)

Get token 42 : remain -35

Refill tokens Current: -25. (Add 10)

Use Time:0.201000213623 Send:42

Avg = 132.126711657 (times=4)

Need send 16

Refill tokens Current: -15. (Add 9)

Refill tokens Current: -5. (Add 9)

Refill tokens Current: 4. (Add 10)

Get token 16 : remain -11

Refill tokens Current: -1. (Add 9)

Use Time:0.300999879837 Send:16

Avg = 115.22048411 (times=5)

......

Need send 21

Refill tokens Current: -4. (Add 10)

Refill tokens Current: 5. (Add 9)

Get token 21 : remain -15

Refill tokens Current: -5. (Add 10)

Use Time:0.200999975204 Send:21

Avg = 100.389763573 (times=138)

Need send 41

Refill tokens Current: 4. (Add 9)

Get token 41 : remain -36

Refill tokens Current: -26. (Add 10)

Use Time:0.101000070572 Send:41

Avg = 100.66413934 (times=139)

Need send 18

Refill tokens Current: -15. (Add 10)

Refill tokens Current: -5. (Add 10)

Refill tokens Current: 4. (Add 10)

Get token 18 : remain -13

Refill tokens Current: -3. (Add 10)

Use Time:0.301999807358 Send:18

Avg = 100.607594694 (times=140)

?

穩(wěn)定后效果還算可以，從發(fā)包點(diǎn)上也相對(duì)均勻。當(dāng)然初始僅為波動(dòng)而已，可以通過(guò)調(diào)整優(yōu)化掉，但從長(zhǎng)時(shí)間看，效果是一致的。

?

方案三：

方案一、二都缺少緩沖的支持。如果報(bào)文來(lái)了，但是現(xiàn)在資源不夠，不能發(fā)送，直接丟棄，則客戶端再重發(fā)，這個(gè)過(guò)程太浪費(fèi)。

因此增加緩沖隊(duì)列，根據(jù)系統(tǒng)的內(nèi)存，設(shè)定隊(duì)列的大小，對(duì)于不能發(fā)送的報(bào)文，先入隊(duì)。

如果隊(duì)列滿了呢？ 那只能丟棄了，毫無(wú)辦法。（不考慮共享寬帶的情況）。

從Linux收發(fā)包角度，每個(gè)以太網(wǎng)設(shè)備有一個(gè)發(fā)送隊(duì)列，如果滿了，則設(shè)置為狀態(tài)不可用，則不再收包。道理是一樣的。

?

關(guān)于更新Token時(shí)間的設(shè)計(jì)，如上例程序，僅為演示，我沒(méi)有加線程額外處理。

在存在緩沖隊(duì)列的情況下，則必須增加更新線程，因?yàn)榇嬖谑瞻l(fā)異常的情況。

?

示例如下，不過(guò)緩沖不過(guò)是增加一些彈性，丟包依然不可避免。結(jié)果可預(yù)知：由于緩沖的存在，平均流量會(huì)在一段時(shí)間后，才能趨向限制值。

# -- coding: utf-8 -- # Good luck.import time import random import threadingclass tb():def __init__(self, token_per_sec):self.captoken = token_per_secself.curr_token = 0self.timestamp = time.time()self.queue = []self.q_max = 5def refill(self):if time.time() > self.timestamp:refill_token = self.captoken*(time.time() - self.timestamp)self.curr_token = min(self.curr_token + refill_token, self.captoken)print "\tRefill tokens Current: %d. (Add %d)" %(self.curr_token, refill_token)self.timestamp = time.time()else:print "\tNo refill...."def consume(self, num):ret = Falseif self.curr_token > 0: # Control precisionself.curr_token -= numprint "\tGet token %d : remain %d" %(num, self.curr_token)ret = Trueelif len(self.queue) < self.q_max:# Enter queueself.queue.append(num)print "Enqueue Action."ret = Trueelse:# Drop it.ret = Falseself.refill()return retdef dequeue(self):if len(self.queue) and self.curr_token > 0:tmp = self.queue.pop()self.curr_token -= tmpprint "Dequeue Action : %d (remain %d)" %(tmp, self.curr_token)def update_bucket(args):print "Args=%s" %(args.captoken)while True:time.sleep(0.1)args.refill()args.dequeue()test = tb(100) run_time = time.time() all_len = 0 times = 0 tx_queue = []# update bucket thread. update_t = threading.Thread(target=update_bucket, args=(test,)) update_t.start()while True:t = 0.2ts = time.time()send_len = random.randint(40, 50)print "Need send %d" %(send_len)if test.consume(send_len):te = time.time()print "Use Time:%s Send:%d " %(te-ts, send_len)all_len += send_lenelse:print "Drop Action."times += 1print "Avg = %s (times=%d)" %(all_len/(ts - run_time+0.1), times)time.sleep(t)

運(yùn)行結(jié)果：

Args=100

Need send 46

Enqueue Action.

Refill tokens Current: 0. (Add 0)

Use Time:0.0 Send:46

Avg = 455.44587139 (times=1)

Refill tokens Current: 10. (Add 9)

Dequeue Action : 46 (remain -35)

Need send 41

Enqueue Action.

Refill tokens Current: -25. (Add 10)

Use Time:0.0 Send:41

Avg = 289.036568661 (times=2)

Refill tokens Current: -25. (Add 0)

Refill tokens Current: -15. (Add 10)

Need send 47

Enqueue Action.

Refill tokens Current: -5. (Add 9)

Use Time:0.0 Send:47

Avg = 266.932297286 (times=3)

Refill tokens Current: -5. (Add 0)

Refill tokens Current: 4. (Add 10)

Dequeue Action : 47 (remain -42)

?

......

Drop Action.

Avg = 106.217083485 (times=170)

Refill tokens Current: -9. (Add 2)

Refill tokens Current: 0. (Add 10)

Dequeue Action : 42 (remain -41)

Need send 50

Enqueue Action.

Refill tokens Current: -34. (Add 7)

Use Time:0.0 Send:50

Avg = 107.055107617 (times=171)

Refill tokens Current: -31. (Add 2)

?

在有針對(duì)多個(gè)用戶的多個(gè)限速規(guī)則，必然存在多個(gè)隊(duì)列后，就需要有一定的調(diào)度算法，常用的RR、DRR、WRR，后面使用一些示例，展開討論一下。

?

?

?

?

?

?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Token Bucket在QoS中入门级介绍python示例的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。