Timing Wheel

不管是之前做的Bada还是最近在做的Pika，只要是服务端，都面临一个问题：如何有效清除长时间不活动的客户端连接？这个还是很有必要的，现实中保不齐就有用客户端连上服务器后什么都不做，“占着茅坑不拉屎”的现象，其实解决办法很简单，就是对每个客户端的最后请求时间做记录然后定时检查，超过设定时间就关闭连接就可以了，不管是bada，pika，还是redis，实现都很简单，都是在cron里做定期扫描，无意中发现了时间轮盘（Timing Wheel），原理也不难，不过感觉实现起来挺好玩的，以后没准也会把它用在pika中

原理

除了之前说的，对每个客户端的最后访问时间做记录然后定期扫描的办法，有没有什么不记录时间，超时后自动淘汰的办法呢？有！首先有一个定长队列，队列长度和设定的超时时间一样，假如超时时间是10s，那么队列长度就是10，每次从队尾插入一个新成员的时候，淘汰对头的成员，是不是感觉有点接近了？没错，队列的每个成员是一个链表的head指针，链表的每个节点就是对应每个客户端的Conn对象，假如有新的连接过来，accept线程构造好一个Conn对象，将它插入到队列尾的链表中，代表还有10s过期，然后，每过1s，就在队尾插入新的空head指针，删除对头被顶出来的链表（关闭超时客户端连接），假如在2s的链表中，有一个客户端来了新的请求，就将他从2s的链表中摘出来，插入到10s的链表，这样也就刷新了超时时间，通过这样的结构实现了超时客户端的淘汰

实现

上一节说的原理很简单，不过实现起来的方式有很多的，结合C++的shared_ptr和weak_ptr，可以很好地实现Timing Wheel，如下图：

链表中的每个节点并不是实际Conn对象，而是一个指向Entry的shared_ptr，暂且称为EntryPtr，那么什么是Entry呢，他是和Conn相伴相生的struct，结构非常简单，仅包含一个指向Conn对象的weak_ptr，另外Conn中还要有一个指向Entry的weak_ptr，举个例子，假设在1s链表中，有一个Conn来了新请求，现在需要将它从1s链表移动到10s链表中，怎么做呢？首先Conn中有指向Entry的weak_ptr，将它提升成为shared_ptr，此时指向这个Entry的shared_ptr的引用计数为2，一个是1s链表中已经存在的EntryPtr，一个是刚刚从weak_ptr提升而来，然后将提升得到的shared_ptr插入到10s链表里就可以了，注意，此时虽然1s链表中那个指向Entry的shared_ptr还在，不过不会有影响，为什么呢？假如又一秒过去，刚才的1s链表被推出，整体淘汰，那么在析构这个shared_ptr指向的Entry是，发现此时引用计数为2，所以不会析构Entry，仅仅是将shared_ptr的引用计数减1，直到刚才10s链表析构的时候才会真正析构Entry，在Entry析构时才会真正析构Conn，为什么Conn指向Entry的一定要是weak_ptr呢？很简单，如果是shared_ptr的话，那么引用计数永远不可能为0，这个Entry永远不会被析构的。

总结

有一个问题需要思考一下：为什么Entry中指向Conn的指针是weak_ptr呢？如果用普通指针会有什么问题？

本篇Timing Wheel的实现还是挺有意思的，也算是的shared_ptr和weak_ptr的典型用法，值得学习

Ps：昨天在哈尔滨办完女方新婚答谢宴，今天是和媳妇在一起7周年，还挺有纪念意义的，写完这篇，准备回京，继续过小日子，哈哈哈~~~，墨鱼丸第一次离开我俩自己在家呆了这么多天，回去多喂几罐猫罐头安慰一下^^