目录


限流算法[返回到目录]

服务端限制请求速率时,就会用到限流算法。常用的限流算法有漏斗算法令牌捅算法
1,漏斗算法:
leaky-bucket.png
漏斗有一个进水口 和 一个出水口,出水口以一定速率出水,并且有一个最大出水速率:

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


Python实现[返回到目录]

# coding: utf8

from threading import Lock
import time
import math

class RateLimiter(object):
    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 请求限流


参考文档[返回到目录]