限速算法之令牌捅算法

限流算法[返回到目录]

服务端限制请求速率时，就会用到限流算法。常用的限流算法有漏斗算法、令牌捅算法。

1，漏斗算法：

漏斗有一个进水口和一个出水口，出水口以一定速率出水，并且有一个最大出水速率：

在漏斗中没有水的时候，
- 如果进水速率小于等于最大出水速率，那么，出水速率等于进水速率，此时，不会积水
- 如果进水速率大于最大出水速率，那么，漏斗以最大速率出水，此时，多余的水会积在漏斗中
在漏斗中有水的时候
- 出水口以最大速率出水
- 如果漏斗未满，且有进水的话，那么这些水会积在漏斗中
- 如果漏斗已满，且有进水的话，那么这些水会溢出到漏斗之外

2，令牌桶算法：

系统以恒定的速率产生令牌，然后把令牌放到令牌桶中，令牌桶有一个容量，当令牌桶满了的时候，再向其中放令牌，那么多余的令牌会被丢弃；当想要处理一个请求的时候，需要从令牌桶中取出一个令牌，如果此时令牌桶中没有令牌，那么则拒绝该请求。

Python实现[返回到目录]


xxxxxxxxxx
from threading import Lock
import time
import math


class RateLimiter:
    def __init__(self, capacity, average_rate):
        # 令牌桶的容量
        self._capacity = capacity
        # 每毫秒产生的令牌数（可以是小数，比如 0.2 表示每 5 毫秒产生一个令牌）
        self._average_rate = average_rate
        # 上次更新时间
        self._last_refresh_time = 0
        # 已消耗的令牌数
        self._consumed_tokens = 0
        self._lock = Lock()

    def acquire(self):
        """申请一个令牌，申请成功返回 True，否则返回 False"""
        with self._lock:
            return self._acquire()

    def _acquire(self):
        # 计算新产生的令牌数
        now = long(math.floor(time.time() * 1000))
        ms_elapsed = now - self._last_refresh_time
        new_tokens = long(math.floor(ms_elapsed * self._average_rate))

        # 调整更新时间，注意：不能吃掉不足以产生一个令牌的时间
        self._last_refresh_time = now - (ms_elapsed - 
            long(new_tokens / self._average_rate))
    
        # 获取消耗的令牌数。
        # 当调小令牌桶的容量时，保证消耗的令牌数不能超过令牌桶的容量
        self._adjust_consumed_tokens = min(self._capacity, self._consumed_tokens)

        # 填充已消耗的令牌
        self._consumed_tokens = max(0, self._adjust_consumed_tokens - new_tokens)

        # 当消耗的令牌数小于容量时，获取成功
        if self._consumed_tokens < self._capacity:
            self._consumed_tokens = self._consumed_tokens + 1
            return True
        # 否则，获取失败
        return False

Redis实现[返回到目录]

请参考Spring-Cloud-Gateway 源码解析 —— 过滤器 (4.10) 之 RequestRateLimiterGatewayFilterFactory 请求限流。

目录

限流算法[返回到目录]

Python实现[返回到目录]

Redis实现[返回到目录]

参考文档[返回到目录]