在之前的方案一中,最大的开销是每次检查超时连接时都需遍历所有连接的接收时间,时间复杂度为O(n)。我们可以在此基础上对其进行优化,通过某种策略让检查超时的 *** 作在尽可能短的时间内找出所有的超时连接。
通过分析超时时间可知,对于所有连接而言,系统设定的超时时间是相同的。在均未收到新数据的情况下,上次 先收到数据的连接肯定比后收到数据的连接先超时。这类似于一个先进先出的列。因此我们尝试用队列对超时连接进行管理。
如图4-1所示,我们创建了一个先入先出队列用来管理超时连接。为了保证该队列的线程安全,每次对该队列进行添加和删除 *** 作均需在加锁情况下进行。在每个队列节点中,我们都保存了对应连接的上次接收消息时间。并且我们此时不考虑该连接又收到新的消息导致接收消息时间更新的情景。每当有新连接建立时,我们尝试获取超时队列锁,然后创建一个 新的队列节点,并在该节点中保存该连接信息和当前时间。最后我们将这个新连接对应的节点添加到超时队列的头部。此时该节点之后的超时队列中已有连接1至5对应的节点,且每个节点对应连接的接收时间依次递增,即连接1的接收时间早于连接2,连接2的接收时间早于连接3,以此类推。
系统建立了一个定时器,每隔一段时间检查超时队列中接收时间已经过期的连接。首先会检查超时队列最尾部的节点,如果对该节点对应连接的接收时间进行判断,显示未超时,则整个超时队列中的其他节点对应连接也均未超时,此次定时事件直接结束处理。如果判定该队尾节点对应连接已经超时,则记录该连接信息,并将该节点从队尾移除。然后再判断新的队尾节点是否已超时,如超时则同样记录并且移除,直到新的队尾节点未超时为止。最后系统将会向此次检测超时的所有连接发送超时通知,并最终强制断开这些超时连接。 因为连接1的接收时间早于连接2,所以如果连接1未超时,连接2也显然为超时;但如果连接1此时已经超时,则无法判断之后的连接是否超时,因此还需再检测连接2,直到从超时队列中检测到一个未超时的节点,该节点及之后节点也均未超时。此时我们的超时队列已经能够满足无时间更新时的工作了。我们再添加它对接收到新的消息后,对接收时间的更新工作。依旧是如图的场景,此时连接3接收到了一条新的心跳消息,我们需要将该连接的计时重置。相应的 *** 作其实很简单,获取超时队列的锁,找到该连接在超时队列中的节点,将该节点重新移到队列的头部,并更新节点中保存的.上次接收数据时间即可。此时该节点所对应的连接成为超时队列管理的所有连接中时间最新的连接,当前连接均不变的话,该连接将最后超时。 其中还是存在一个问题,连接如何确定自己对应的超时队列中的节点。如果不建立某种映射信息,我们从超时队列中查找某次连接的节点将需遍历整个超时队列中的所有节点,而获取连接对应节点又是更新超时时间必须的 *** 作。如果每个连接每次更新超时时间都需要遍历超时队列,而超时队列又维护了成千,上万的连接,那这将给整个系统带来极大的性能开销。 我们可以采用STL库的list作为超时队列的底层实现,list数据结构保证其中的每个节点在整个生命周期内对应的内存空间不变。因此我们可以在每个连接对应对象中保存-个指向超时队列中对应节点的指针,当我们需要定位到该连接的超时节点时,只需对该指针取引用就行了,免去了遍历列表的开销。 但是这种方式同样存在一定危险。 因为该指针所指节点为超时队列的内部数据,我们将该指针暴露给连接对象,也就相当于把超时队列内部的数据泄露了出去,这可能会对整个队列的安全产生影响。比如原来多线程环境下对该超时队列的所有访问都需要添加线程锁保证线程
安全,但是现在可以通过该指针绕过线程锁访问甚至修改超时队列中的数据。 在系统实现中,我们设计了名为LinkedHashMap的数据结构,通过该结构来维护超时队列,同时建立了键值对映射机制,来确保通过某个Key就可获取对应的队列节点。
我们设计的LinkedHashMap类似于HashMap,同样提供键值对映射功能,但是它保留键值对插入的顺序,也就是说它既能满足键值对数据根据插入顺序先入先出的要求,同时也能根据键数据映射快速查找出值数据。 LinkedHashMap内部由一个STL的stl:list和一个stl::unordered_ map组成。每当有一个新键值对传入,就在list表头创建一个节点,并保存键值数据。同时在unordered_ map中创建一个该键 与队列中对应节点迭代器的映射。因此我们借助list实现了根据插入顺序排序的队列,而通过键映射我们又能快速找出队列中对应节点的迭代器,从而获取队列节点中数据。
在系统实现中,我们为每个连接对象分配了一个唯一-的ID, 并为其建立了ID与连接对象的映射,通过这个ID,我们可以很方便的获取对应的连接对象。在超时管理的具体实现中,我们使用连接ID代替实际的连接对象。
如图4-2所示,我们将ID作为了LinkedHashMap的键,ID和对 应连接的最后接收消息时间作为了值,构造了以上的LinkedHashMap结构。我们依次添加了连接1至连接5的数据,并更新了连接3的最后接收消息时间,并且连接1已经由于超时原因被移除。
当我们添加一个新的连接时,只需获取该连接的ID和最后接收消息时间,并插入LinkedHashMap中, LinkedHashMap会将新节点插入队列的头部,并建立ID与节点的映射。当我们需要更新某个连接的最后接收消息时间时,只需通过ID便可获得所在节点,并修改最后接收消息时间并将该节点重新连接到队列头部。当该节点被系统检测到超时时,我们可以根据节点中保存的ID获知具体超时的连接对象,并将该ID的相关数据从list和unordered_ map中移除即可。以上对于LinkedHashMap的插入、更新和删除 *** 作均能大致保证在常数时间完成。
通过以上设计,我们能够高效的实现对连接的超时管理。同时整个超时机制仅通过一个ID值保持 与系统实际连接对象的联系,保证了模块间的低耦合度。
部分代码 首先我封装了一个心跳类,作为超时队列的成员 CHeart.h#inclass="superseo">clude
#include
#include
class CHeart
{
int fd;//客户端连接的文件描述符
struct timespec addtime;//系统计时结构体
public:
CHeart(int fd, struct timespec abstime);
bool timecheck(unsigned int outtime);//超时返回true
int getfd();
};
CHeart.cpp
#include "CHeart.h"
CHeart::CHeart(int fd, timespec abstime)
{
this->fd = fd;
this->addtime = abstime;//构造时将连接时的系统时间传入
}
bool CHeart::timecheck(unsigned int outtime)//设置超时时间
{
struct timespec abstime;
clock_gettime(CLOCK_REALTIME, &abstime);//获取当前系统时间
if (abstime.tv_sec - this->addtime.tv_sec > outtime)
{
return true;
}
else
{
return false;
}
}
int CHeart::getfd()
{
return this->fd;
}
list timeoutque;//超时队列
unordered_map::iterator> hash;//LinkedHashmap
pthread_mutex_t quemutex;//超时队列锁
新连接加入超时队列
cout << "网络开始工作,等待客户端上线" << endl;
acceptfd = accept(socketfd, NULL, NULL);
cout << "acceptfd= " << acceptfd << endl;
pthread_mutex_lock(&this->quemutex);
//上线的客户端描述符,绑定事件添加到epoll
epollEvent.data.fd = acceptfd;
epollEvent.events = EPOLLIN;
epoll_ctl(epollfd, EPOLL_CTL_ADD, acceptfd, &epollEvent);
struct timespec abstime;
clock_gettime(CLOCK_REALTIME, &abstime);
CHeart* newheart = new CHeart(acceptfd, abstime);
//新连接的加入到超时队列队尾
timeoutque.push_back(newheart);
cout << "timeoutque的容量为" << timeoutque.size() << endl;
//获取队尾迭代器
list::iterator it;
it = timeoutque.end();
it--;
hash[acceptfd] = it;
cout <<"hash的容量为" << hash.size() << endl;
pthread_mutex_unlock(&this->quemutex);
更新超时时间
pthread_mutex_lock(&this->quemutex);
cout << "服务器接收到数据。。。"<< endl;
cout << "任务类型为" << HD.type << endl;
if (HD.type == 1)//登录业务
{
int res = read(fd, &LG, sizeof(login));
if (res == HD.len)//检查
{
list::iterator it;
it = hash[fd];
//通过映射快速定位超时队列中的节点并删除
timeoutque.erase(it);
struct timespec abstime;
//更新时间
clock_gettime(CLOCK_REALTIME, &abstime);
CHeart* newheart = new CHeart(fd, abstime);
//等于将其移动到队尾
timeoutque.push_back(newheart);
list::iterator itor;
itor = timeoutque.end();
itor--;
hash[fd] = itor;
pthread_mutex_unlock(&this->quemutex);
超时检测线程
void* heartthread(void* arg)
{
CEpollServer* s = (CEpollServer*)arg;
while (1)
{
while (s->timeoutque.size() > 0)
{
pthread_mutex_lock(&s->quemutex);
CHeart* heart=s->timeoutque.front();
//循环判断队首是否超时
bool out = heart->timecheck(30);
if (out)//超时
{
s->timeoutque.pop_front();
cout << "timeoutque的容量为" << s->timeoutque.size() << endl;
int fd = heart->getfd();
unordered_map::iterator>::iterator it;
it = s->hash.find(fd);
if (it != s->hash.end())
{
s->hash.erase(it);
}
cout << "hash的容量为" << s->hash.size() << endl;
struct epoll_event epollEvent;
close(fd);
//从epoll中删除客户端描述符
epollEvent.data.fd = epollEvent.data.fd;
epollEvent.events = EPOLLIN;
epoll_ctl(s->getepollfd(), EPOLL_CTL_DEL, fd, &epollEvent);
pthread_mutex_lock(&CEpollServer::onlinemutex);
map::iterator iter = CEpollServer::online.find(fd);
if (iter != CEpollServer::online.end())
{
CEpollServer::online.erase(iter);
cout << "在线用户人数" << CEpollServer::online.size() << endl;
pthread_mutex_unlock(&CEpollServer::onlinemutex);
}
else
{
cout << "该客户端未登录" << endl;
pthread_mutex_unlock(&CEpollServer::onlinemutex);
}
pthread_mutex_unlock(&s->quemutex);
cout << "客户端fd= " << fd << "超时断开连接" << endl;
}
else
{
pthread_mutex_unlock(&s->quemutex);
break;
}
}
sleep(1);//每秒检查一次
}
}
运行结果
总结
为什么要使用超时队列
保证我检查超时不用遍历全部连接
为什么要使用LinkedHashMap
保证我的超时队列节点的时间更新,删除的时间复杂度保持在常数级。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)