超时30分钟自动取消订单

想象一个队列，你可以放任务进去，并且设置每个任务要延迟几分钟后执行。
这里的关键点就是延迟执行，如何保证每个任务按延时时间执行呢？可以把任务按延时时间从小到大排序，每次取第一个，依次取下去直到队列为空。假设取出的第一个任务到时间T才能执行，那么sleep(T-currentTime)之后就可以执行，即：

1
2
3
4
5
while(queue.size > 0)
  task <--- queue.peak()
  remain <--- task.runTime - currentTime
  sleep(remain)
  process(task)

其中queue是一个优先队列，它的数据结构是小堆，最上面的一个值最小，每次插入一个元素的时间复杂度为O(logN)，即便已有10^9个元素，再插入一个元素也不过移动40个左右元素，所以性能完全没有问题。
在多线程情况下，Java已有现有的实现，DelayQueue是一个延迟优先队列，它的队列元素都必须实现Delayed接口。下面分析它是如何实现延时执行的。
Delayed

1
2
long getDelay(TimeUnit unit)  //还剩多长时间方可执行
int compareTo(Delayed o)	//按delay时间比较

这两个方法都是为DelayQueue服务的。
DelayQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//取队列第一个元素，并从队列中移除
public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;	//非公平锁
    lock.lockInterruptibly();	//抢占锁时允许被中断
    try {
        for (;;) {
            E first = q.peek();	//取第一个，如果队列为空，则返回null
            if (first == null)
                available.await();	//1.如果队列为空，则等待
            else {	//2.如果队列中有元素，
                long delay = first.getDelay(NANOSECONDS);	//离可以执行还有多久
                if (delay <= 0)	
                    return q.poll();	//a.时间到了，把第一个元素移除并返回
                //b.时间还没到，    
                first = null; //多线程情况下，就不要有多余引用指向首元素，防止阻碍垃圾回收
                if (leader != null)
                    available.await();	//leader只是个标志，代表哪只线程是第一个获得q.peek()的
                    					//哪只线程先获取到元素task，哪只线程就有权利执行task，
                    					//那么其它线程就不会多执行这个task了
                else {
                    Thread thisThread = Thread.currentThread();
                    leader = thisThread;
                    try {
                        available.awaitNanos(delay);	//await期间会释放锁，其它线程会来争抢锁，但是
                                                        //这个时候由于leader已经设值，所以其它线程只能
                                                        //干等，什么都做不了
                    } finally {
                        if (leader == thisThread)
                            leader = null;	//释放leader，到下一次循环q.peek()的delay就<=0了，元素被移除并返回
                    }
                }
            }
        }
    } finally {
        if (leader == null && q.peek() != null)
            available.signal();	//在return q.poll()之后，如果队列中还有task，那么唤醒一个沉睡的线程
        lock.unlock();
    }
}

由此可见，take()方法永远不会返回null，除非你queue.add(null)。
整个DelayQueue并没有太难的东西，但是却有它很巧妙的地方。利用一个leader标志来防止task被重复执行，在线程await时将first置null。
30分钟订单未支付自动取消，这个原本是道面试题，我首先想的是轮询，但是无论怎么设计都感觉很费效率。之所以没想到用优先队列是因为我隐约觉得任务列表是一个链表结构，订单如果到2亿怎么办，我还没见过2亿一个的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package com.entity;

/**
 * @author hero
 */
public class Order {
    private long id;
    private Status status;     //订单状态
    private long createTime;      //下单时间，毫秒

    public Order(long id, long createTime) {
        this.id = id;
        this.status = Status.UNPAYED;
        this.createTime = createTime;
    }

    public enum Status {
        UNPAYED,
        UNCONFIRMED,
        FINISHED,
        CANCELED
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

    public Status getStatus() {
        return status;
    }

    public void setStatus(Status status) {
        this.status = status;
    }

    public long getCreateTime() {
        return createTime;
    }

    public void setCreateTime(long createTime) {
        this.createTime = createTime;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package com.domain;

import com.entity.Order;

import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

/**
 * @author hero
 */
public class OrderService {
    public static long DELAY_TIME_IN_MILLIS = 2 * 1000;   //下单未支付超时时间
    private DelayQueue<OrderTask> que = new DelayQueue<>();

    public static void main(String[] args) {
        OrderService service = new OrderService();
        service.placeAnOrder(new Order(1, System.currentTimeMillis() + 10));
        service.placeAnOrder(new Order(2, System.currentTimeMillis()));

        while (true) {
            // 找出超时未支付订单，触发取消订单事件
            System.out.println(service.getExpiredOrder());
        }
    }

    public void placeAnOrder(Order order) {
        // 1.入库
        // ...
        // ...
        // ...
        // 2.加一个定时task
        que.add(new OrderTask(order));
    }

    public long getExpiredOrder() {
        try {
            return que.take().orderId;
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    class OrderTask implements Delayed {
        private long orderId;
        private long expiredTime;

        public OrderTask(Order order) {
            this.orderId = order.getId();
            this.expiredTime = order.getCreateTime() + DELAY_TIME_IN_MILLIS;
        }

        @Override
        public long getDelay(TimeUnit unit) {
            return unit.convert(expiredTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }

        @Override
        public int compareTo(Delayed o) {
            return expiredTime > ((OrderTask) o).expiredTime ? 1 : -1;
        }
    }
}