Use case of Deque

  java

Order

Two-way Queue (Deque) is a subinterface of queue. Two-way queue refers to elements at both ends of the queue that can both be queued (offer) and queued (poll). Use scenarios such as job theft, such as flow restriction.

Current limiting example

Deque is used to limit the current, where timeIntervalInMs is the event window and maxLimit is the maximum value of the event window.

public class MyRateLimiter {

    private static final Logger LOGGER = LoggerFactory.getLogger(DemoRateLimiter.class);

    private final Deque<Long> queue;

    private long timeIntervalInMs;

    public MyRateLimiter(long timeIntervalInMs, int maxLimit) {
        this.timeIntervalInMs = timeIntervalInMs;
        this.queue = new LinkedBlockingDeque<Long>(maxLimit);
    }

    public boolean incrAndReachLimit(){
        long currentTimeMillis = System.currentTimeMillis();
        boolean success = queue.offerFirst(currentTimeMillis);
        if(success){
            //没有超过maxLimit
            return false;
        }

        synchronized (this){
            //queue is full
            long last = queue.getLast();

            //还在时间窗口内,超过maxLimit
            if (currentTimeMillis - last < timeIntervalInMs) {
                return true;
            }
            LOGGER.info("time window expired,current:{},last:{}",currentTimeMillis,last);
            //超过时间窗口了,超过maxLimit的情况下,重置时间窗口
            queue.removeLast();
            queue.addFirst(currentTimeMillis);

            return false;
        }

    }
}

test

@Test
    public void testDeque() throws InterruptedException {
        DemoRateLimiter limiter = new DemoRateLimiter(5*1000,3);
        Callable<Void> test = new Callable<Void>(){

            @Override
            public Void call() throws Exception {
                for(int i=0;i<1000;i++){
                    LOGGER.info("result:{}",limiter.incrAndReachLimit());
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                return null;
            }
        };
        ExecutorService pool = Executors.newFixedThreadPool(10);
        pool.invokeAll(Arrays.asList(test,test,test,test,test));

        Thread.sleep(100000);
    }

Summary

Deque’s capacity is used here as the current limit of the time window, and the two ends are used to judge the time window, which is relatively clever.