令牌桶算法的使用

背景

負(fù)責(zé)的項目中有一個爬蟲調(diào)度項目卿吐∨越ⅲ基礎(chǔ)的模型就是利用平臺提供的 Token 通過相關(guān)的數(shù)據(jù) API 從平臺獲取數(shù)據(jù)。
對于每個 Token 均存在一個短時間內(nèi)調(diào)用的上限嗡官。一旦超出限制箭窜,將在一段時間內(nèi)不能進(jìn)行繼續(xù)獲取。
之前對于這個限制的管理比較簡單衍腥,當(dāng)任務(wù)觸發(fā)時磺樱,會直接發(fā)起數(shù)據(jù)獲取請求。通過檢查返回信息婆咸,判斷是否超限竹捉,如果超限,設(shè)置一個等待時間之后進(jìn)行重試尚骄。但發(fā)現(xiàn)這樣沒有最大化的利用到 Token. 因為發(fā)起請求本身就是對 Token 的一種消耗块差。
最近跟組長進(jìn)行討論相關(guān)細(xì)節(jié)時,他提到可以利用 Nginx 的流量限制來進(jìn)行改進(jìn)。研究之后發(fā)現(xiàn)令牌桶算法很合適這個需求憾儒。

令牌桶算法

簡介

令牌桶(token bucket)算法是 Nginx 進(jìn)行流量限制的一種常用算法询兴。常用于控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)量乃沙,并允許突發(fā)數(shù)據(jù)的發(fā)送起趾。

基礎(chǔ)流程圖

當(dāng)數(shù)據(jù)請求來臨時,算法通過檢查當(dāng)前桶的令牌量警儒,如果令牌量足以支持消耗训裆,即會進(jìn)行接下來的處理。
如果令牌不足蜀铲,則會將請求拋棄(獲取緩存边琉,看相關(guān)需求)

token_bucket.png

使用

在當(dāng)前的需求中,對每一個 Token 實例添加一個容量桶记劝。存儲當(dāng)前的可調(diào)用次數(shù)。當(dāng)有 worker 發(fā)起請求時厌丑,先檢查當(dāng)前的可調(diào)用余量。
如果余量足夠砍鸠,則返回可調(diào)用狀態(tài)耕驰,并設(shè)置當(dāng)前的處理時間。當(dāng)請求完畢時朦肘,對桶進(jìn)行主動更新。如果當(dāng)前余量不足以進(jìn)行請求媒抠,則可以返回需要等待的時間,或者執(zhí)行切換 Token 實例等操作夫嗓。

簡單實現(xiàn)

import time


class TokenBucket:
    def __init__(self, rate=0.1, capacity=100):
        """
        此 為 單例
        初始化時 應(yīng)設(shè)置 當(dāng)前的容量為 總?cè)萘?        :param rate: 速率 秒為單位
        :param capacity: 總?cè)萘?        """
        self._rate = rate
        self._capacity = capacity
        self.current_amount = capacity
        self._last_consumed_at = int(time.time())

    def consume(self, need_amount=1):
        """
        進(jìn)行消費
        :param need_amount:
        :return:
        """
        increments = (int(time.time()) - self._last_consumed_at) * self._rate
        self.current_amount = min(
            self.current_amount + increments, self._capacity
        )
        if need_amount > self.current_amount:
            return False
        self.current_amount = self.current_amount - need_amount
        self._last_consumed_at = int(time.time())
        return True

    def update(self, amount):
        """
        存在一個更新操作舍咖,用于 Token 余量狀態(tài)主動返回
        并重新計算 最后消費時間
        :param amount: 主動發(fā)送的數(shù)量
        :return:
        """
        self.current_amount = min(amount, self._capacity)
        self._last_consumed_at = int(time.time())

源碼可訪問 code

參考資料

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末排霉,一起剝皮案震驚了整個濱河市民轴,隨后出現(xiàn)的幾起案子球订,更是在濱河造成了極大的恐慌冒滩,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件开睡,死亡現(xiàn)場離奇詭異篇恒,居然都是意外死亡凶杖,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評論 3 392
  • 文/潘曉璐 我一進(jìn)店門腾么,熙熙樓的掌柜王于貴愁眉苦臉地迎上來寻咒,“玉大人,你說我怎么就攤上這事毛秘。” “怎么了艰匙?”我有些...
    開封第一講書人閱讀 162,415評論 0 353
  • 文/不壞的土叔 我叫張陵员凝,是天一觀的道長。 經(jīng)常有香客問我健霹,道長,這世上最難降的妖魔是什么糖埋? 我笑而不...
    開封第一講書人閱讀 58,157評論 1 292
  • 正文 為了忘掉前任瞳别,我火速辦了婚禮,結(jié)果婚禮上祟敛,老公的妹妹穿的比我還像新娘。我一直安慰自己跑揉,他們只是感情好叼架,可當(dāng)我...
    茶點故事閱讀 67,171評論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般具练。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上哥遮,一...
    開封第一講書人閱讀 51,125評論 1 297
  • 那天陵究,我揣著相機(jī)與錄音,去河邊找鬼仪召。 笑死松蒜,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的秸苗。 我是一名探鬼主播,決...
    沈念sama閱讀 40,028評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼玖瘸,長吁一口氣:“原來是場噩夢啊……” “哼檀咙!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起屯断,我...
    開封第一講書人閱讀 38,887評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎氧秘,沒想到半個月后趴久,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,310評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡灭忠,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,533評論 2 332
  • 正文 我和宋清朗相戀三年弛作,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片映琳。...
    茶點故事閱讀 39,690評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡蜘拉,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出谎脯,到底是詐尸還是另有隱情,我是刑警寧澤源梭,帶...
    沈念sama閱讀 35,411評論 5 343
  • 正文 年R本政府宣布咸产,位于F島的核電站,受9級特大地震影響脑溢,放射性物質(zhì)發(fā)生泄漏赖欣。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,004評論 3 325
  • 文/蒙蒙 一社牲、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧搏恤,春花似錦、人聲如沸熟空。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至绍刮,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間孩革,已是汗流浹背油坝。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評論 1 268
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人帆啃。 一個月前我還...
    沈念sama閱讀 47,693評論 2 368
  • 正文 我出身青樓,卻偏偏與公主長得像诽偷,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子报慕,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,577評論 2 353

推薦閱讀更多精彩內(nèi)容