面试中限流问题
保障分布式应用高可用方案中，限流是必须的，超过一定的流量，我们就拒绝提供服务，从而使得我们的服务不会挂掉，所以限流其实是一种有损的解决方案。但是相比于全部不可用，有损服务是最好的一种解决办法，常见的限流方案主要包括以下几种：
1.计数器
计数器算法是限流算法里最简单也是最容易实现的一种算法。比如我们限制一个接口每分钟调用不能超过1000次，我们可以这样设计，定义2个变量，一个是访问次数，一个是记录访问次数计算的开始时间，如果记录时间和当前时间比较大于1分钟，则重新计时，如果在一分钟以内，我们把访问次数加一。
下面是个简单的示意图
示意图
简单实现：
计数器简单实现
2.信号量
Semaphore(信号量)是java.util.concurrent下的一个工具类.用来控制可同时访问特定资源的线程数.内部是通过维护父类(AQS)的 int state值实现.
Semaphore中有一个"许可"的概念:
访问特定资源前，先使用acquire(1)获得许可，如果许可数量为0，该线程则一直阻塞，直到有可用许可。
访问资源后，使用release()释放许可。
Semaphore用来控制访问某资源的线程数,比如数据库连接.假设有这个的需求，读取几万个文件的数据到数据库中，由于文件读取是IO密集型任务，可以启动几十个线程并发读取，但是数据库连接数只有20个，这时就必须控制最多只有20个线程能够拿到数据库连接进行操作。这个时候，就可以使用Semaphore做流量控制。
public class Semaphore {
private static final int COUNT = 80;
private static Executor executor = Executors.newFixedThreadPool(COUNT);
private static Semaphore semaphore = new Semaphore(20);
public static void main(String[] args) {
for (int i=0; i< COUNT; i++) {
executor.execute(new ThreadTest.Task());
}
}
static class Task implements Runnable {
@Override
public void run() {
try {
//读取文件中...
semaphore.acquire();
// 存储数据中...
semaphore.release();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
}
}
}
}
3. 漏斗桶
漏桶(Leaky Bucket)算法：请求先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大或者漏桶已满会直接溢，然后就拒绝请求，可以看出漏桶算法能强行限制数据的传输速率
示意图
源码简单实现：
package bucket;
public class LeakyBucket {
//桶容量
private int maxVolume;
//流出速率
private int maxOutSpeed;
//当前容量
private int volume;
//当前流出量
private int stream;
public LeakyBucket() {
this.maxVolume = 10;
this.maxOutSpeed = 2;
this.volume = 0;
this.stream = 0;
}
//流入一滴水
public boolean inputWater(){
if (volume < maxVolume){
volume++;
return true;
}
return false;
}
//流出一滴水,添加一滴当前流出量
public boolean outputWater(){
if(volume >0){
if (stream < maxOutSpeed){
stream++;
volume--;
return true;
}
return false;
}
System.err.println("当前容量异常");
return false;
}
//任务完成减少流量
public void outSuccess(){
stream--;
}
}
测试代码:
package bucket;
public class TestController {
//漏桶
private static LeakyBucket leakyBucket= new LeakyBucket();
public String testMethed(){
//流入一滴水
boolean b = leakyBucket.inputWater();
//如果桶满流入失败直接反回
if (!b){
return "桶满了";
}
//执行任务前获取桶中的一滴水
boolean b1 = leakyBucket.outputWater();
//
if (b1){
System.out.println("执行任务");
//任务执行完告诉漏桶
leakyBucket.outSuccess();
return "任务完成";
}
return "流量满了，抛弃你";
}
}
因此这是一种强行限制请求速率的方式，但是缺点非常明显，无法面对突发的大流量----比如请求处理速率为1000，容量为5000，来了一波2000/s的请求持续10s，那么后5s的请求将全部直接被丢弃，服务器拒绝服务，但是实际上网络中突发一波大流量尤其是短时间的大流量是非常正常的，超过容量就拒绝，非常简单粗暴。
4.令牌桶
系统会以一定的速率往桶里添加令牌，处理请求前，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则返回失败。
大概描述如下：
1.所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
2.获取不到令牌，则请求返回失败
3.根据限流大小，设置按照一定的速率往桶里添加令牌；
4.桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝
令牌桶示意图
实现关键点：
初始化固定数量的令牌放入令牌桶中
初始化和开启一个定时的任务，定时往令牌桶添加令牌
提供一个获取令牌的方法，获取一个令牌，令牌桶中减一，如果令牌桶中为空，返回失败
令牌桶简单源码
假设还是1000QPS的速率，那么5秒钟放1000个令牌，第1秒钟800个请求过来，第2~4秒没有请求，那么按照令牌桶算法，第5秒钟可以接受4200个请求，但是实际上这已经远远超出了系统的承载能力，因此使用令牌桶算法特别注意设置桶中令牌的上限即可。
guava实现了令牌桶算法，主要代码:
public double acquire() {
return acquire(1);
}
public double acquire(int permits) {
checkPermits(permits); //检查参数是否合法（是否大于0）
long microsToWait;
synchronized (mutex) { //应对并发情况需要同步
microsToWait = reserveNextTicket(permits, readSafeMicros()); //获得需要等待的时间
}
ticker.sleepMicrosUninterruptibly(microsToWait); //等待，当未达到限制时，microsToWait为0
return 1.0 * microsToWait / TimeUnit.SECONDS.toMicros(1L);
}
private long reserveNextTicket(double requiredPermits, long nowMicros) {
resync(nowMicros); //补充令牌
long microsToNextFreeTicket = nextFreeTicketMicros - nowMicros;
double storedPermitsToSpend = Math.min(requiredPermits, this.storedPermits); //获取这次请求消耗的令牌数目
double freshPermits = requiredPermits - storedPermitsToSpend;
long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
+ (long) (freshPermits * stableIntervalMicros);
this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
this.storedPermits -= storedPermitsToSpend; // 减去消耗的令牌
return microsToNextFreeTicket;
}
private void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
if (nowMicros > nextFreeTicketMicros) {
storedPermits = Math.min(maxPermits,
storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
nextFreeTicketMicros = nowMicros;
}
}
总结:
并不能说明令牌桶一定比漏洞好，她们使用场景不一样。令牌桶可以用来保护自己，主要用来对调用者频率进行限流，为的是让自己不被打垮。所以如果自己本身有处理能力的时候，如果流量突发（实际消费能力强于配置的流量限制），那么实际处理速率可以超过配置的限制。而漏桶算法，这是用来保护他人，也就是保护他所调用的系统。主要场景是，当调用的第三方系统本身没有保护机制，或者有流量限制的时候，我们的调用速度不能超过他的限制，由于我们不能更改第三方系统，所以只有在主调方控制。这个时候，即使流量突发，也必须舍弃。因为消费能力是第三方决定的。
总结起来：如果要让自己的系统不被打垮，用令牌桶。如果保证别人的系统不被打垮，用漏桶算法
5.redis实现限流
6.滑动窗口
参考文章：
1.https://www.cnblogs.com/xuwc/p/9123078.html
2.https://author.baidu.com/home?from=bjh_article&app_id=1658677106265807
