分布式限流
经典限流算法
在介绍分布式限流之前，先介绍经典限流算法。经过笔者自己的整理，核心的算法主要可以总结为以下两类四种： A类：计数器法，滑动窗口法 B类：令牌桶法，漏桶法
这里的四种算法通常都是在应用级别讨论的，这里不重复介绍这四种算法的实现思路了，只不过我人为的将他们分成了A，B两类。
- A类算法，否决式限流。即如果系统设定限流方案是1分钟允许100次调用，那么真实请求1分钟调用200次的话，意味着超出的100次调用，得到的是空结果或者调用频繁异常。
- B类算法，阻塞式限流。即如果系统设定限流方案是1分钟允许100次调用，那么真实请求1分钟调用200次的话，意味着超出的100次调用，会均匀安排到下一分钟返回。（当然B类算法，也可以立即返回失败，也可以达到否决式限流的效果）
B类算法，如Guava包提供的RateLimiter，内部其实就是一个阻塞队列，达到阻塞限流的效果。然后分布式场景下，有一些思路悄悄的发生了变化。多个模块之间不能保证相互阻塞，共享的变量也不在一片内存空间。为了使用阻塞限流的算法，我们不得不将统计流量放到redis一类的共享内存中，如果操作是一系列复合的操作，我们还不能使用redis自带的CAS操作(CAS操作只能保证单个操作的原子性)或者使用中间件级别的队列来阻塞操作，显示加分布式锁的开销又是非常的巨大。最终选择放弃阻塞式限流，而在分布式场景下，仅仅使用redis+lua脚本的方式来达到分布式-否决式限流的效果。redis执行lua脚本是一个单线程的行为，所以不需要显示加锁，这可以说避免了加锁导致的线程切换开销。
锁的演变
下面记录一下这个设计的演变过程。
- 单体式应用中显示加锁 首先还是回到单体应用中对共享变量进行+1的例子。
Integer count = 0;
//sychronized锁
public synchronized void synchronizedIncrement(){
count++;
}
//juc中的lock
Lock lock = new ReentrantLock();
public void incrementByLock(){
lock.lock();
try{
count++;
}finally {
lock.unlock();
}
}用synchronized或者lock同步的方式进行统计，当单位时间内到达限定次数后否决执行。限制：单体应用下有效，分布式场景失效，显示加锁，开销大。
- 单体式应用中CAS操作
public AtomicInteger atomicInteger = new AtomicInteger(0);
public increamt(){
atomicInteger.incrementAndGet();
}虽然没有显示加锁，但是CAS操作有一定的局限性，限流中不仅要对计数器进行+1，而且还要记录时间段，所以复合操作，还是无法避免加锁。
- 分布式应用中显示加锁
RedisDistributeLock lock = new RedisDistributeLock();
public void incrementByLock(){
lock.lock();
try{
count++;
}finally {
lock.unlock();
}
}分布式阻塞锁的实现，我的博客里曾经实现过，但生产中更多人自然是使用开源的分布式锁实现。虽然能达到多个模块之间的同步，但还是开销过大。不得已时才会考虑使用。
- redis+lua脚本限流（最终方案）
local key = KEYS[1] --限流KEY（一秒一个）
local limit = tonumber(ARGV[1]) --限流大小
local current = tonumber(redis.call('get', key) or "0")
if current + 1 > limit then --如果超出限流大小
redis.call("INCRBY", key,"1") -- 如果不需要统计真是访问量可以不加这行
return 0
else --请求数+1，并设置2秒过期
redis.call("INCRBY", key,"1")
if tonumber(ARGV[2]) > -1 then
redis.call("expire", key,tonumber(ARGV[2])) --时间窗口最大时间后销毁键
end
return 1
endlua脚本返回值比较奇怪，用java客户端接受返回值，只能使用Long，没有去深究，(学习openResty的过程中了解到lua这门动态语言的数字只有double类型)。这个脚本只需要传入key（url+时间戳/预设时间窗口大小），便可以实现限流。 这里也贴下java中配套的工具类
package sinosoftgz.apiGateway.utils;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.script.RedisScript;
import org.springframework.util.Assert;
import java.util.Arrays;
/**
* Created by xujingfeng on 2017/3/13.
* <p>
* 基于redis lua脚本的线程安全的计数器限流方案
* </p>
*/
public class RedisRateLimiter {
/**
* 限流访问的url
*/
private String url;
/**
* 单位时间的大小,最大值为 Long.MAX_VALUE - 1,以秒为单位
*/
final Long timeUnit;
/**
* 单位时间窗口内允许的访问次数
*/
final Integer limit;
/**
* 需要传入一个lua script,莫名其妙redisTemplate返回值永远是个Long
*/
private RedisScript<Long> redisScript;
private RedisTemplate redisTemplate;
/**
* 配置键是否会过期，
* true：可以用来做接口流量统计，用定时器去删除
* false：过期自动删除
*/
private boolean isDurable = false;
public void setRedisScript(RedisScript<Long> redisScript) {
this.redisScript = redisScript;
}
public void setRedisTemplate(RedisTemplate redisTemplate) {
this.redisTemplate = redisTemplate;
}
public String getUrl() {
return url;
}
public void setUrl(String url) {
this.url = url;
}
public boolean isDurable() {
return isDurable;
}
public void setDurable(boolean durable) {
isDurable = durable;
}
public RedisRateLimiter(Integer limit, Long timeUnit) {
this.timeUnit = timeUnit;
Assert.isTrue(timeUnit < Long.MAX_VALUE - 1);
this.limit = limit;
}
public RedisRateLimiter(Integer limit, Long timeUnit, boolean isDurable) {
this(limit, timeUnit);
this.isDurable = isDurable;
}
public boolean acquire() {
return this.acquire(this.url);
}
public boolean acquire(String url) {
StringBuffer key = new StringBuffer();
key.append("rateLimiter").append(":")
.append(url).append(":")
.append(System.currentTimeMillis() / 1000 / timeUnit);
Integer expire = limit + 1;
String convertExpire = isDurable ? "-1" : expire.toString();
return redisTemplate.execute(redisScript, Arrays.asList(key.toString()), limit.toString(), convertExpire).equals(1l);
}
}总结
一个小小的统计次数的需求，如果真想在分布式下做到最完善，还真需要花不小的精力。这篇文章原写于今年的三月份，当时我正在我老大（@钱钱）的带领下开发我们公司的网关，涉及到限流功能时做的一个调研，记录成了博客，到了如今的9月有了更深的理解，限流功能不仅可以放到应用层实现，如nginx+lua或者说是openResty都提供了限流算法，从性能和架构设计的角度来看都更加合适。但实际上掌握一门新的语言（nginx二次开发+lua），又要考虑到公司人力投入和项目规模是否需要等因素，这也是从事技术开发之外个人的一点思考，更大的一点收获便是，对于以前的想法，过一段时间再来看，会有更加深刻的认识。这或许也是我想要维护公众号和博客的初衷。
腾讯云开发者
