? ? ? ? 漏斗是生活中一个非常常见的容器，他自身的形状决定了其拥有的性质，上面宽、下边窄，上面进水快，而窄的那头出水较慢。比如生活中，我们需要向开水瓶里灌水，用一个漏斗会非常的方便。
? ? ? ? 我们用热水壶通过漏斗往开水瓶里倒水，水会沿着漏斗顺流到开水瓶里，如果这个时候你不小心手抖了，一下倒入很多，你会发现漏斗里的水不能一下子进到开水瓶里而是满了出来。
? ? ? ? 这是一个简单的数学问题，可以用以下表达式说明:
? ? ? ?if? ?单位时间内的进水速率> 单位时间内出水速率 :
? ? ? ? ? ? print("漏斗里的水会一直增加!... 直到溢出")
? ? ? else?
? ? ? ? ? ?print("漏斗永远装不满...水一直会顺着流出。")
? ? ? ? 由分析，如果我们能控制进水和出水的速率，那么可以借助漏斗实现单位时间内流量的限制，即限流。
? ? ? ? 实现思路:
? ? ? ? 1.? 定义一个Funnel 静态内部类，相当于漏斗，可以初始化容量和漏斗大口的出水速率。
? ? ? ? 2.? 定义进水方法watering(int capacity),参数为每次出水的量，默认为1。
? ? ? ? 3.? 定义出水方法runningWater(), 由于每次流出水需要统计量，那么就需要记录每次入水的时间戳，以供计算容量，出水的同时剩余容量leftCapcity需要加上出水量 this.leftCapacity += deltaCapacity。
? ? ? ? ? 单位时间内的出水量(deltaCapacity)?=? 速率(waterRate) * (当前出水的时间戳ts- 上一次出水的时间戳ts)
? ? ? ? 4. 如果出水的量超过了漏斗的最大容量，那么直接将leftCapacity置为最大容量，也就是说此刻漏斗里相当于没有水。
? ? ? ? 如果剩余容量> 进水量，那么表示水可以通行，否则不能通行。
package leetcode100;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
/**
* 漏斗算法
* Funnel algorithm
*/
public class FunnelProblem {
/**
* record a logic key and funnel
*/
private static Map<String, Funnel> funnelMap = new HashMap<>();
static class Funnel {
private BigDecimal waterRate;
private Integer capacity;
private Integer leftCapacity;
private Long leakTimes;
public Funnel(BigDecimal waterRate, Integer capacity) {
this.waterRate = waterRate;
this.capacity = capacity;
this.leftCapacity = capacity;
this.leakTimes = System.currentTimeMillis();
}
/**
* water out, space add
*/
public void runningWater() {
long nowTime = System.currentTimeMillis();
long deltaTime = nowTime - leakTimes;
Integer deltaCapacity = waterRate.multiply(new BigDecimal(deltaTime)).intValue();
// the deltaCapacity means how much water are in .
if (deltaCapacity < 0) {
this.leftCapacity = capacity;
this.leakTimes = nowTime;
return;
}
if (deltaCapacity < 1) {
return;
}
this.leftCapacity += deltaCapacity;
this.leakTimes = nowTime;
if (this.leftCapacity < this.capacity) {
this.leftCapacity = this.capacity;
}
}
/**
* water in.
*/
public boolean watering(Integer waterCapacity) {
runningWater();
if (leftCapacity > waterCapacity) {
this.leftCapacity -= waterCapacity;
return true;
}
return false;
}
}
public boolean allow(String userId, String key, Integer initCapacity, BigDecimal leakRate) {
Funnel funnel = funnelMap.get(key);
if (funnel == null) {
funnel = new Funnel(leakRate, initCapacity);
funnelMap.put(key, funnel);
}
return funnel.watering(1);
}
public static void main(String[] args) {
FunnelProblem funnelProblem = new FunnelProblem();
for (int i = 0; i < 10000; i++) {
Boolean allow = funnelProblem.allow("zhangsan", "browser", 10, BigDecimal.valueOf(0.1));
if (allow) {
System.out.println("you can browser!");
} else {
System.out.println("pls wait !");
}
}
}
}
查看打印结果:
????????可以发现，每波数据能顺利通过9个， 然后等一段时间后，再次会通过9个，限流的作用就显现出来了， 我们可以通过设置initCapacity 和 leakRate的值来初始化每个漏斗的大小和进水的速率。
? ? ? ? ?此方案存在的缺陷，由于采用了map做为key和很多漏桶的存储，每次存、取不具备原子性，高并发情况下会出现线程安全问题，需要加分布式锁实现， 不过加锁会损耗一定的性能。