最近在做一个类似 API 限流的功能,参考了不少的资料。首先简单的介绍下什么是服务限流。

场景

比如我们在使用新浪微博 API 的时候,微博在文档中有这么一段描述
````
访问授权限制

请求所有商业接口:
50000次/小时/IP;
````
表示单个 ip 的接口请求限制为每小时50000次。

我们在使用 github 的 API 的时候, https://api.github.com/ 会看到返回的 response header 中包括以下 header

X-RateLimit-Limit:60 //每秒60次请求
X-RateLimit-Remaining:59  //当前还剩下多少次
X-RateLimit-Reset:1437119946 //限制重置时间

以上的 API 服务都实现了服务限流。每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限流来保证接口的可用性或者降级可用性.即接口也需要安装上保险丝,以防止非预期的请求对系统压力过大而引起的系统瘫痪.

通常的策略就是拒绝多余的访问,或者让多余的访问排队等待服务,或者引流.

如何做到限流

那么是如何做到Rate Limiting的呢,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零。此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的TPS。如图所示

simple-limit1

所以这样的做法是不太可行的,更好的做法是使用Leaky Bucket(漏桶)Token Bucket(令牌桶) 算法

关于两种算法的介绍,我就不再重复描述了,直接贴引用了,来自[RateLimiter](http://xiaobaoqiu.github.io/blog/2015/07/02/ratelimiter/)
以下为引用内容:

1.漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

rate-limit1

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate),可以简单的让burst等于rate,也可以让burst更大接收更多突发请求,伪代码如下:

double rate;               // leak rate in calls/s
double burst;              // bucket size in calls

long refreshTime;          // time for last water refresh
double water;              // water count at refreshTime

refreshWater() {
    long  now = getTimeOfDay();
    
    //水随着时间流逝,不断流走,最多就流干到0.
    water = max(0, water- (now - refreshTime)*rate); 
    refreshTime = now;
}

bool permissionGranted() {
    refreshWater();
    if (water < burst) { // 水桶还没满,继续加1
        water ++;
        return true;
    } else {
        return false;
    }
}

在某些情况下,漏桶算法不能够有效地使用网络资源.因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使某一个单独的流突发到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率.

2.令牌桶算法

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.

token_bucket

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.


Guava RateLimiter

上面描述的就是常见的两种限流实现方法。Google 提供了一个RateLimiter的类,它是基于令牌桶算法实现的,使用起来非常简单。

源码注释中的一个例子,比如我们有很多任务需要执行,但是我们不希望每秒超过两个任务执行,那么我们就可以使用RateLimiter:

final RateLimiter rateLimiter = RateLimiter.create(2.0); //每秒最多提交两个任务
void submitTasks(List<Runnable> tasks, Executor executor) {
for (Runnable task : tasks) {
rateLimiter.acquire(); // may wait
executor.execute(task);
}
}

那我们的 API 限流来如何处理呢,一般 API 请求的时候都会提供 access_key_id。来标识请求者的身份。我们可以在后台内存中记录每个access_key_id对应的桶,来实现 API 的限流。为了防止内存不断增长,可以使用guava的内存 cache 来做下简单的缓存,实际可以调整缓存的策略。简单代码如下:

public class APIRateLimiter extends Controller {
    private static Cache<String,RateLimiter> cache= CacheBuilder.newBuilder().initialCapacity(1000)
            .expireAfterAccess(10, TimeUnit.MINUTES).build();
    //qps 60
    private static final double DEFAULT_LIMIT=60;
    @Before
    public static void rateLimiting() {
        Response response = new Response();
        String access_key_id = request.params.get("access_key_id");
        if (StringUtils.isEmpty(access_key_id)) {
            response.setParameterMiss("access_key_id");
            renderText(response.toJSON());
        }
        RateLimiter rateLimiter= null;
        try {
            rateLimiter = cache.get(access_key_id, new Callable<RateLimiter>() {
                @Override
                public RateLimiter call() throws Exception {
                    return RateLimiter.create(DEFAULT_LIMIT);
                }
            });
        } catch (ExecutionException e) {
            Logger.error("get rate limiter error",e);
        }
        if(!rateLimiter.tryAcquire()) { //未请求到limiter则返回超额提示
            response.setCodeWithDefaultMsg(ResponseCode.CLIENT_OVER_QUOTA);
            renderText(response.toJSON());
        }
    }
}

参考:

https://github.com/springside/springside4/wiki/Rate-Limiter

http://xiaobaoqiu.github.io/blog/2015/07/02/ratelimiter/

http://www.cnblogs.com/LBSer/p/4083131.html

http://ifeve.com/guava-ratelimiter/

Comments
Write a Comment