时间轮盘与超时连接

对于网络应用而言，掉线是十分常见的一种故障。原因多种多样，可能网线被生气的老妈给拔掉了，可能光纤被朴实的盗贼给挖掉了......在服务器看来就是一个TCP连接虽然存在但是很长一段时间都没有通信，这是一种资源上的浪费，还不如先把它关掉，等需要的时候再建立连接好了。这就给我们的网络工具箱提出了一个服务器端的超时主动断开链接的需求。

上一篇文章中，我们对timerfd系列的系统调用做了简单的封装，得到了可以用在PollLoop框架下的计时器Timer。借助Timer，我们可以在它的计时溢出回调函数中，遍历一遍所有的连接。当连接数量很多的时候，这个操作就会很耗时，而且我们只有一个线程，意味着它有可能影响其它连接的响应速度。所以我们需要一个高效的超时连接查询机制。一个直接的做法是，给每个连接对象都绑定一个计时器，那么在计时溢出的回调里，我们只需要处理一个连接就可以了。这是一种以空间换时间的方法，速度肯定很快。但是每个连接都将至少消耗两个文件描述符，对系统资源的消耗将是巨大的。

我们花时间来研究数据结构和算法的目的就是要在时间和空间上取得一个较好的平衡，这里我们需要一个算法，既有较高的查询效率，又能够把系统资源的消耗控制在一个较小的范围内。时间轮盘就是能担此重任的一个算法，本文，我们先了解一下该算法，再对echo服务器进行改造，让它具有主动断开超时连接的功能。

1. 时间轮盘算法

现在假设我们有一个如右图所示的轮盘，顺时针的标记着\(n\)个刻度，每一个刻度都对应着一个双向链表。这个链表中记录了一个个的连接。在轮盘上有一个指针，新建的连接都会放置到指针所指的刻度中。每隔一段固定的时间\(t\)，这个指针就顺时针转动一个刻度。此时我们认为，指针所指的链表中所有连接都是超时的，需要服务器主动释放相关资源，并清空该链表。

如右图所示的情形，如果\(t = 1s, n = 8\)，那么一个连接将在8秒之后被指针选中并释放掉，这就达到了检查连接超时的目的。如果在这8s的时间内，某个连接有数据收发，我们就将它从其所在的链表中移除，并添加到指针所指的链表中。这样，只有再等8s才会被判定超时，如此可以保证8s内有通信的所有连接都不被关闭。

我们再来简单看一下它的效率和资源消耗。这个时间轮盘，我们只需要一个计时器就可以实现，可以认为它消耗了最少的系统资源。在计时溢出的回调函数中，它只需要清空指针所指的链表即可。而这个链表中记录的所有连接都是超时的，可以认为没有垃圾操作，效率很高。

虽然时间轮盘在时间和空间上都具有很好的性能，但是，它的精度很差。时间轮盘是在它的回调中批处理超时连接，对于上面的情形，在最坏的情况下，一个连接可能存活接近9s。即刚清空超时的链表，就有新的连接建立了。但这个缺点对于我们的需求而言没有什么影响，我们只要保证长时间无通信的连接被关掉就可以了，多一秒少一秒的无所谓。如果应用对时间精度有较高的要求，那么就还是老老实实的给每个连接一个计时器吧。

2. echo服务器再修改

        ConnectionPtr conn;
        ConnectionNode *prev;    
        ConnectionNode *next;

针对时间轮盘中的链表，我们设计了ConnectionNode的数据结构，把Connection放到了一个双向链表的节点中。如右侧的代码片段所示，ConnectionNode有三个字段。其中，conn是一个记录了连接对象的智能指针。prev和next则是双向链表中分别用于记录前驱和后继的指针。

目前暂时用裸指针来表示链表中的前驱和后继，以后可能会替换为weak_ptr形式的智能指针。一开始我想用shared_ptr来管理这些指针，但是我想用带有哨兵节点的双向链表来保存各个时间刻度上的连接。这就存在一个让对象指向自己的情形，不知道使用shared_ptr会遇到什么问题，所以干脆先用裸指针实现，以后再考虑是否需要用智能指针来管理。

通过ConnectionNode，我们就可以使用带有哨兵节点的双向链表来保存各个时间刻度上的连接。我们提供了接口AddHead和AddTail分别用于把链表节点插到哨兵节点之后或者之前，即放置到链表的首或者尾。并通过Delete函数将指定节点从所在链表中移除。源码的实现很简单直接，这里不再展开，详细内容可以参见源码和数据结构系列文章。

现在我们根据时间轮盘的思路来修改TcpServer中连接的存储方式。首先修改头文件，用一个存放ConnectionNode的裸指针的双端队列mTimeWheel来记录各个链表的哨兵对象。

        std::deque<ConnectionNode*> mTimeWheel;

之所以选择一个双端队列，是想通过进队和出队的操作来模拟指针顺时针转动的作用。在计时器的溢出回调函数OnTimeOut中，我们先清空対首链表中的连接，再把它移到队尾，如下面左侧代码所示每当有新的连接建立，就把它添加到队尾的链表中，下面右侧的代码片段，是对函数TcpServer::OnNewConnection中新建连接部分的修改。

        void TcpServer::OnTimeOut() {
            ConnectionNode * head = mTimeWheel.front();
            for (ConnectionNode * it = head->next; it != head; it = it->next)
                it->conn->Close();
            mTimeWheel.pop_front();
            mTimeWheel.push_back(head);
        }

        ConnectionPtr conn(new Connection(fd, peer_addr));
        ApplyOnLoop(conn, mLoop);

        ConnectionNode *node = new ConnectionNode();
        node->conn = conn;
        ConnectionNode * head = mTimeWheel.back();
        AddTail(node, head);

当一个连接有数据通信时，就通过Delete接口把它从其所在的轮盘链表中移除，并添加到mTimeWheel队尾所在的链表中。如下面的代码所示。

        void TcpServer::OnNewRawMsg(ConnectionNode * con, RawMsgPtr const & msg) {
            if (mNewRawMsgCallBk)
                mNewRawMsgCallBk(con->conn, msg);

            ConnectionNode * head = mTimeWheel.back();
            Delete(con);
            AddTail(con, head);
        }

除了时间轮盘mTimeWheel之外，我们还需要给TcpServer增加了一个Timer对象，用于定时触发时间轮盘的转动。在如下左侧的接口SetTimeOut中，设定了轮盘刻度数量(n)以及定时溢出周期(sec, nsec)，完成了mTimer的构造。在该函数中，我们先确认时间轮盘至少有一个刻度，否则没有意义。然后创建n-1个刻度的链表哨兵，同时创建计时器对象。通过计时器的接口RunEvery，让它周期的触发溢出事件，来运行回调函数OnTimeOut。最后将计时器对象的事件句柄注册到PollLoop上。

void TcpServer::SetTimeOut(time_t sec, long nsec, int n) {
    assert(n > 1);

    for (int i = 1; i < n; i++)
        mTimeWheel.push_back(new ConnectionNode);
    mTimer = TimerPtr(new Timer());

    struct timespec t;
    t.tv_sec = sec;
    t.tv_nsec = nsec;
    mTimer->RunEvery(t, std::bind(&TcpServer::OnTimeOut, this));

    ApplyOnLoop(mTimer, mLoop);
}

// t_echo_server_0.cpp
int main() {
    PollLoopPtr loop = CreatePollLoop();
    TcpServer tcp(loop, 65530, 3);

    tcp.SetTimeOut(1, 0, 5);
    tcp.SetNewConnCallBk(std::bind(OnNewConnection, _1));
    tcp.SetCloseConnCallBk(std::bind(OnCloseConnection, _1));
    tcp.SetNewRawMsgCallBk(std::bind(OnNewRawMsg, _1, _2));

    loop->Loop(10000);

    return 0;
}

上面右侧的代码是修改后echo服务器的main函数。在这次修改中，我们增加了SetTimeOut的调用，给tcp服务器安装一个有5个时间刻度的轮盘，让tcp服务器每隔1秒产生一次溢出事件，来清除超时的连接。下面是注册的各个回调函数的实现，不细述了。

        void OnNewConnection(ConnectionPtr const & conn) {
            std::cout << "新建连接:" << conn->GetPeerAddr().GetIpPort() << std::endl;
        }
        void OnCloseConnection(ConnectionPtr const & conn) {
            std::cout << "关闭连接:" << conn->GetPeerAddr().GetIpPort() << std::endl;
        }
        void OnNewRawMsg(ConnectionPtr const & conn, RawMsgPtr const & msg) {
            conn->SendRawMsg(msg);
        }

3. 完

时间轮盘是一个比较高效的定时批处理方法，它不需要过多的查询操作，也不需要额外的增加计时器对象。但是它的时间精度有限，不能提供小于其时间刻度的精度。所以对时间精度有要求的场合，还得老老实实的增加计时器来获得更细致的定时。对于我们的超时连接而言，时间精度并不是很强的要求，长一秒短一秒的无所谓的。