(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接口
?
?
private static HttpTimeoutThread timeoutGuard = null; static { timeoutGuard = new HttpTimeoutThread(); timeoutGuard.setDaemon(true); // 设置为daemon线程,允许主进程关闭后退出 timeoutGuard.setName("HttpClientHelper Timeout Guard"); timeoutGuard.start(); // 启动 }//注册request到monitor线程HttpClientHelper.timeoutGuard.addHttpRequest(request, connectTimeOut + waitDataTimeOut);后记：最后思考一下timeout的处理机制，就类似于一个定时器的概念，只不过这个定时器执行一次。所以最后也查了下linux的定时器调度算法，前面3种思路也是大同小异。?
?
现在linux操作系统使用的应该是wheel调度算法，具体可以参看一篇IBM的文章：?Linux 下定时器的实现方式分析
?
其对应的几种算法复杂度：?
?
实现方式StartTimerStopTimerPerTickBookkeeping基于链表O(1)O(n)O(n)基于排序链表O(n)O(1)O(1)基于最小堆O(lgn)O(1)O(1)基于时间轮O(1)O(1)O(1)?
?
ps : ?最后感慨一下，java的确给我们封装了很多不错的工具包，比较方便。java.util.*还是有许多比较不错的算法和实现，可以深挖下。
1 楼 NanguoCoffee 2011-03-10 给你顶一个 2 楼 rgun 2011-03-10 挖掘的蛮深入的，同顶~~ 3 楼 tou3921 2011-03-10 这种帖子才有思想 4 楼 whaosoft 2011-03-10 555 看了上一贴才明白 lz这一贴 哈哈 lz研究东西挺强的 有别的什么联系方式吗 5 楼 agapple 2011-03-10 whaosoft 写道555 看了上一贴才明白 lz这一贴 哈哈 lz研究东西挺强的 有别的什么联系方式吗哈，多谢支持。 项目中的需要，为了安全考虑，不然系统容易被人秒杀了。
这也是我同事发现的问题，我负责分析+编码。顺便研究了Linux wheel定时器调度算法，有空也可以实现个简单的。 6 楼 agapple 2011-03-10 说白了timeout超时扫描，也就是定时Timer的一种特殊应用场景，每个Timer只会触发一次而已。
类似的应用场景蛮多的，特别是在一些异步RPC调用中 7 楼 frankiegao123 2011-03-11 MultiThreadedHttpConnectionManager 对于同一个 HOST，默认只有 2 个 HTTP 连接的池。在大量 HTTP 请求时使用这个就需要调整 HTTP 连接数的，呵呵。 8 楼 cz2009 2011-03-11 我用的是httpclient自带的设置,一个是建立连接时间,一个是读数据时间. 目前表现还好.请问我这样设置有什么缺点? 9 楼 agapple 2011-03-11 cz2009 写道我用的是httpclient自带的设置,一个是建立连接时间,一个是读数据时间. 目前表现还好.请问我这样设置有什么缺点?
正如上一篇文件描述的，如果给定的一部电影的url地址，链接会一直不能被关闭，直到数据流被读完，如果来个几十次这样的请求，应用估计也差不多崩溃了。
目前httpClient3.1只支持3种timeout的设置：
connectionTimeout : socket建立链接的超时时间，Httpclient包中通过一个异步线程去创建socket链接，对应的超时控制。
timeoutInMilliseconds : socket read数据的超时时间， socket.setSoTimeout(timeout);
httpConnectionTimeout : 如果那个的是MultiThreadedHttpConnectionManager，对应的是从连接池获取链接的超时时间。
timeoutInMilliseconds就是你说的读取时间，它的定义是多长时间内如果无数据同步就认为超时。但如果是一个超大文件流，每隔1S给你来点数据，所以你这两个设置的时间，很快你的线程就会被一直RUNNING。来个几十请求，系统就差不多over了。
这里我们就需要给整个HttpClient请求做一个总的timeout时间控制，避免出现类似的情况。或者你也可以改写HttpClient关于输出流的实现，但不是很建议。因为HttpClient这样的设计也是有自己一定的理由，它为了链接共享,pooling，支持chunk协议等，就必须在一个请求关闭时把上一次未读完的流数据给消费光。避免对下一次请求的影响 10 楼 agapple 2011-03-11 frankiegao123 写道MultiThreadedHttpConnectionManager 对于同一个 HOST，默认只有 2 个 HTTP 连接的池。在大量 HTTP 请求时使用这个就需要调整 HTTP 连接数的，呵呵。
因为我完全是一个对外系统的访问，对应url都是客户输入，重用链接没任何意义，用完一次就可以关闭。
我这里使用MultiThreadedHttpConnectionManager并不是为了共享连接。而是利用了它可以强制关闭链接的功能。
其他我找不到相应的public入口操作http socket链接，不过非正常手段到可以用反射，不是很愿意这么搞。 11 楼 zjhlht 2011-03-11 确实研究好深，发现能学到的东西不仅仅是这一点啊！ 12 楼 dennis_zane 2011-03-11 Netty3自带了一个timer wheel算法的实现，可以直接扣出来用。不过通常来说，基于优先队列的ScheduleThreadPoolExecutor已经足够用了。 13 楼 hquxiezk 2011-03-11 过2年看能不能看个明白，呵呵 14 楼 agapple 2011-03-11 dennis_zane 写道Netty3自带了一个timer wheel算法的实现，可以直接扣出来用。不过通常来说，基于优先队列的ScheduleThreadPoolExecutor已经足够用了。
得抽空看看netty的源码实现，一直想看mina和netty的源码可一直没时间