(HttpClient超时机制)timeout调度算法探讨


继上一篇文章： HttpClient超时机制(安全问题处理:访问超大文件控制) 
提到了一个需要管理所有request请求的timeout，原先文章的一种处理方式是起一个异步线程的方式，通过jdk的unsafe的await机制控制timeout。 
 
存在的问题：
1.  创建新线程的开销不小。
2.  大量线程的调度和切换，引起不必要的context switch
 
和同事在沟通的过程中，提到一种新思路，就是有一个monitor线程来管理所有request的timeout。
 
启动一个monitor thread，是一个while true运行 
每个请求创建之前都先注册到monitor，比如什么时候过期和对应的request句柄，完成后注销。  
运行的monitor，定时读取注册的request信息，发现有数据过期时间到了，直接拿到request引用，执行强制关闭。 
针对monitor timeout调度设计时，也想过几种思路：
 
思路1： 插入o(1) + 调度o(N)+ 主动轮询式
维护一个list队列，monitor线程间隔固定频遍历一次list队列。挑出时间已经过期的数据，执行关闭。
 
思路2： 插入o(logN) + 调度o(1) + 主动轮询式
维护一个有序队列(根据距离过期时间最近做升序排序)，monitor线程间隔固定频取出头节点，进行关闭处理。
 
思路3： 插入o(logN) + 调度o(1) + 阻塞通知式
维护一个二叉树(根据距离过期时间最近做升序排序)，monitor阻塞于二叉树队列，获取头节点，通过signal方式唤醒。
 
很明显，思路3在处理上比较靠谱，性能上和处理成本比较好。
 
二叉树第一直觉就是选择PriorityQueue或者TreeMap。 
 
PriorityQueue是一个基于object[]数组实现的二叉树，而TreeMap走的是红黑树，比较传统的left,right节点的树实现。
 
考虑再加上timeout时间需要进行delay处理，最后就有一个不二之选DelayQueue了，其内部包含了一个PriorityQueue做为其数据存储。
 
DelayQueue的Item对象是需要实现Delayed接口
 
 
Java代码  
public inte易做图ce Delayed extends Comparable<Delayed> {   
  
     long getDelay(TimeUnit unit);   
}  
public inte易做图ce Delayed extends Comparable<Delayed> {
     long getDelay(TimeUnit unit);
} 说明：getDelay主要返回对应距离目标time还存在剩余的delay时间。这里插入一个request后，立马调用该方法返回的应该就是你想要的timeout时间。
 
 
代码实现：
 
Java代码  
/**  
 * 超时控制线程，基于DelayQueue实现的一套超时管理机制  
 *   
 * <pre>  
 * 几个特点  
 * 1. O(logN)的超时控制算法  
 * 2. timout处理更精确，时间控制精度为毫秒(ms)  
 * 3. thread-safe(线程安全)  
 * </pre>  
 *   
 * @author jianghang 2011-3-7 下午12:39:17  
 */  
class HttpTimeoutThread extends Thread {   
  
    // init time for nano   
    private static final long                       MILL_ORIGIN = System.currentTimeMillis();   
    // thread-safe,定时触发timeout   
    private volatile DelayQueue<HttpTimeoutDelayed> queue = new DelayQueue<HttpTimeoutDelayed>();   
  
    public void run() {   
        while (true) {   
            try {   
                HttpTimeoutDelayed delay = this.queue.take();   
                delay.doTimeout();   
            } catch (InterruptedException e) {   
                // ignore interrupt   
            }   
        }   
    }   
  
    public void addHttpRequest(HttpClientRequest request, long timeout) {   
        this.queue.put(new HttpTimeoutDelayed(request, timeout));   
    }   
  
    // 内部timeout Delay控制   
    class HttpTimeoutDelayed implements Delayed {   
  
        private HttpClientRequest request; // 管理对应的request   
        private long              now;    // 记录具体request产生时的now的偏移时间点，单位ms   
        private long              timeout; // 记录具体需要被delayed处理的偏移时间点,单位ms   
  
        public HttpTimeoutDelayed(HttpClientRequest request, long timeout){   
            this.request = request;   
            this.timeout = timeout;   
            this.now = System.currentTimeMillis() - MILL_ORIGIN;   
        }   
  
        /**  
         * 对应的超时处理  
         */  
        public void doTimeout() {   
            this.request.forceRelease();// 强制关闭对应的链接   
        }   
  
        @Override  
        public long getDelay(TimeUnit unit) {   
            long currNow = System.currentTimeMillis() - MILL_ORIGIN;   
            long d = unit.convert(now + timeout - currNow, TimeUnit.MILLISECONDS);   
            return d;   
        }   
  
        @Override  
        public int compareTo(Delayed other) {   
            if (other == this) { // compare zero ONLY if same object   
                return 0;   
            } else if (other instanceof HttpTimeoutDelayed) {   
                HttpTimeoutDelayed x = (HttpTimeoutDelayed) other;   
                long diff = now + timeout - (x.now + x.timeout);

补充：综合编程 , 安全编程 ,