令牌环桶算法

女爷i 2022-11-08 15:29 156阅读 0赞

### 文章目录 ###

*  令牌桶算法模拟抢购
 *   *  令牌环桶
     *  模拟抢购

# 令牌桶算法模拟抢购 #

令牌环桶，在对某个资源或者方法进行调用之前首先要获取到令牌也就是获取到许可证才能进行相关的操作，否则将不被允许。比如，常见的互联网秒杀抢购等，商品的数量有限，为了防止大量的并发请求流量进入系统后导致普通商品的消费出现影响，我们需要对类似这样的操作增加令牌授权，许可证放行等操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDg3MDk_size_16_color_FFFFFF_t_70_pic_center]

*  根据固定的速率向桶里提交请求
 *  新加数据时如果超过了桶的容量，则请求将会被拒绝
 *  如果令牌不足，则请求也会被拒绝(请求可以再次尝试)

## 令牌环桶 ##

import com.google.common.util.concurrent.Monitor;
    import com.google.common.util.concurrent.RateLimiter;
    
    import java.util.concurrent.TimeUnit;
    import java.util.function.Consumer;
    
    /**
     * @author MI
     * @version 1.0
     * @date 2021/3/14 9:15
     */
    //令牌环桶 模拟商品抢购
    public class RateLimiterTokenBucket {
        
        //当前活动商品数量
        public static final int MAX = 100;
    
        //订单编号，订单成功之后会产生一个新的订单
        private int orderID;
    
        //单位时间内只允许10个用户能够抢购到商品，也就是说订单服务会被匀速地调用
        private final RateLimiter rateLimiter = RateLimiter.create(10.0D);
    
        private Monitor bookOrderMonitor = new Monitor();
    
        //商品售罄的时候抛出异常
        static class NoProductionException extends Exception {
        
            public NoProductionException(String message) {
        
                super(message);
            }
        }
    
        static class OrderFailedException extends Exception {
        
            public OrderFailedException(String message) {
        
                super(message);
            }
        }
    
        // 前台用户下单，但是只允许云速地进行订单服务调用
        public void bookOrder(Consumer<Integer> consumer) throws NoProductionException, OrderFailedException {
        
            //如果当前商品有库存则进行抢购操作
            if (bookOrderMonitor.enterIf(bookOrderMonitor.newGuard(() -> orderID < MAX))) {
        
                try {
        
                    //抢购商品，最多等待100毫秒
                    if (!rateLimiter.tryAcquire(100, TimeUnit.MILLISECONDS)) {
        
                        //如果在100 毫秒抢购失败，抛出订购失败异常，客户端可以重新尝试操作
                        throw new OrderFailedException("book order failed,please try again later.");
                    }
                    //执行订单订购操作
                    orderID++;
                    consumer.accept(orderID);
                } finally {
        
                    bookOrderMonitor.leave();
                }
            } else {
        
                //当前商品已经没有库存，则抛出没有商品的异常，该异常不会再次进行尝试
                throw new NoProductionException("No avaliable production now.");
            }
        }
    }

## 模拟抢购 ##

public class RateLimiterExample4 {
        
        private static final RateLimiterTokenBucket tokenBucket = new RateLimiterTokenBucket();
        public static void main(String[] args) {
        
            for (int i = 0; i < 20; i++) {
        
                new Thread(() -> {
        
                    while (true) {
        
                        //抢购商品
                        try {
        
                            tokenBucket.bookOrder(proID -> System.out.println("user:" + Thread.currentThread().getName() + " book the prod order and prodID:" + proID));
                        } catch (RateLimiterTokenBucket.NoProductionException e) {
        
                            //商品已经售罄，退出抢购
                            System.out.println("all of production already sold out");
                            break;
                        } catch (RateLimiterTokenBucket.OrderFailedException e) {
        
                            //抢购失败，重新尝试抢购
                            System.out.println("user:" + Thread.currentThread().getName() + " book order failed,will try again");
                        }
                    }
                }).start();
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDg3MDk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/7580b796fde14d13ad7ce5d98021ba77.png