漏桶:漏桶可以看作是一个漏斗类似，水可以以任意速度流入,桶保存一定量的水，水以一定的速率流出。
image.png
令牌桶:桶会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务
image.png
漏桶:
import java.time.LocalDateTime;
/**
* 漏桶
*/
public class LeakyBucket {
//流水速率 固定
private double rate;
//桶的大小
private double burst;
//最后更新时间
private int refreshTime;
//private Long refreshTime;
//桶里面的水量
private int water;
public LeakyBucket(double rate,double burst){
this.rate=rate;
this.burst=burst;
}
/**
* 刷新桶的水量
*/
private void refreshWater(){
//long now = System.currentTimeMillis(); //毫秒生成
LocalDateTime time=LocalDateTime.now(); //每秒生成
int now = time.getSecond();
//现在时间-上次更新的时间 中间花费的时间(秒)*流水速率=流水量(处理的请求的数量) 通过上次水总量减去流水量等于现在的水量
//如果流水量太多导致桶里都没那么多水就应该置0, 所以通过math.max函数实现
water = (int)Math.max(0,water-(now-refreshTime)*rate);
//更新上次时间
refreshTime = now;
}
/**
* 获取令牌
*/
public synchronized boolean tryAcquire(){
//刷新桶的水量
refreshWater();
//如果桶的水量小于桶的容量就可以添加进来
if(water<burst){
water++;
return true;
}else {
return false;
}
}
}
import java.util.concurrent.CountDownLatch;public class LeakyBucketTest {
public static LeakyBucket leakyBucket = new LeakyBucket(10,100);
public static void main(String[] args) {long start = System.currentTimeMillis();
for (int i=0;i<10;i++){
new Thread(new Runnable() {
@Override
public void run() {
System.out.println(leakyBucket.tryAcquire());
}
}).start();
}
System.out.println("总花费:"+(System.currentTimeMillis()-start));
System.out.println("线程执行完毕");
}
}
令牌桶
Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法，所以我们直接使用Guava即可实现。
加入依赖
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>21.0</version>
</dependency>
import com.google.common.util.concurrent.RateLimiter;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.TimeUnit;
/**
* 令牌桶
*/
public class TokenBucket {
private static final SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
/**
* permitsPerSecond为每秒生成的令牌
*
*/
/** 平衡稳定
* * 创建一个稳定输出令牌的RateLimiter，保证了平均每秒不超过permitsPerSecond个请求
* * 当请求到来的速度超过了permitsPerSecond，保证每秒只处理permitsPerSecond个请求
* * 当这个RateLimiter使用不足(即请求到来速度小于permitsPerSecond)，会囤积最多permitsPerSecond个请求
*/
/**平衡预热
* 创建一个稳定输出令牌的RateLimiter，保证了平均每秒不超过permitsPerSecond个请求
* 还包含一个热身期(warmup period),热身期内，RateLimiter会平滑的将其释放令牌的速率加大，直到起达到最大速率
* 同样，如果RateLimiter在热身期没有足够的请求(unused),则起速率会逐渐降低到冷却状态
* 设计这个的意图是为了满足那种资源提供方需要热身时间，而不是每次访问都能提供稳定速率的服务的情况(比如带缓存服务，需要定期刷新缓存的)
* 参数warmupPeriod和unit决定了其从冷却状态到达最大速率的时间
*/
private static final RateLimiter rateLimiter = RateLimiter.create(10,2L, TimeUnit.SECONDS);
//private static final RateLimiter rateLimiter = RateLimiter.create(10);
/**
* tryAcquire尝试获取permit，默认超时时间是0，意思是拿不到就立即返回false
* @return
*/
public String sayHello(){
if(rateLimiter.tryAcquire()){ //一次拿一个
System.out.println(sdf.format(new Date()));
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}else {
return "no";
}
return "hello";
}
/**
* acquire拿不到就等待,拿到为止
* @return
*/
public String sayHi(){
rateLimiter.acquire(1); //一次拿5个 意思就是生成10个令牌才去全部拿去给一个请求
System.out.println(sdf.format(new Date()));
return "hi";
}
}
import java.util.concurrent.CountDownLatch;public class LeakyBucketTest {
private static TokenBucket tokenBucket = new TokenBucket();
public static void main(String[] args) {long start = System.currentTimeMillis();
for (int i=0;i<10;i++){
new Thread(new Runnable() {
@Override
public void run() {
System.out.println(tokenBucket.sayHi());
}
}).start();
}
System.out.println("总花费:"+(System.currentTimeMillis()-start));
System.out.println("线程执行完毕");
}
}
漏桶
漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。
令牌桶
生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。
最后，不论是对于令牌桶拿不到令牌被拒绝，还是漏桶的水满了溢出，都是为了保证大部分流量的正常使用，而牺牲掉了少部分流量，这是合理的，如果因为极少部分流量需要保证的话，那么就可能导致系统达到极限而挂掉，得不偿失。
网友评论