C++中map超时删除方案

2018-01-26 10:32:23来源:oschina作者:问天小凯人点击

分享

开发C/C++程序的时候,经常要使用map,将一些数据插入map当中,同时伴随超时删除的操作,即一个数据记录插入map之后,如果隔一段时间没有被消费掉(从map中删除),那么就认为该数据记录超时了,而且将来也不会被删除,将永远留在map中。对于服务器端开发来说,应用时长期运行,如果任由垃圾记录存留map中,将会无限撑大map,性能受到影响,也有崩溃的可能。比如在接入系统中,客户端登录产生了一个唯一识别码uuid,接入服务端记录了该 uuid 与后台服务的关联,保存在map中,然后在30分钟之内客户端没有发起请求,接入服务端就认为该客户端下线,将删除map中的该uuid的记录。试想一下,如果接入服务端不删除该记录,那么下次客户端登录产生一个新的uuid,旧uuid将一直残留,而没有机会删除。长此以往将会导致map中残留大量的无效记录,所以需要有一个超时删除的机制,用来保证map的容量不会无限增长。下面介绍一下利用桶定时删除过期数据的方法,这个方法是我同事告诉我的。(当然在这个例子中,不一定非要使用超时删除机制,换一套方案可以解决。)


首先准备3个map桶:map1,map2,map3。


假设超时时间是5分钟。


定义一个操作标记operate_flag,用来表示应该对哪一个桶进行插入操作,operate_flag初始值设为1,表示对map1进行操作,取值范围为{1,2,3}。


定义一个删除标记delete_flag,用来表示应该删除哪一个桶的数据,delete_flag初始值设为0,表示不删除任何map,取值范围为{0,1,2,3}。


具体做法:


1,主线程根据operate_flag决定插入哪个map;


2,另起一个超时线程,每5分钟定时做如下操作:


a,将operate_flag = operate_flag%3+1,表示每隔5分钟,主线程会插入下一个map桶;


b,删除delete_flag所标识的map桶中的数据,如果为0,则不删除;


c,将delete_flag = delete_flag%3+1,更新下一次要删除的map桶。


按照以上的算法,我们可以画出如下的事件列表



时间轴(第几分钟)
当前操作的map桶
当前删除的map桶
下一次需要删除的map桶


0
map1
0
0


5
map2
0
map1


10
map3
map1
map2


15
map1
map2
map3


20
map2
map3
map1


25
map3
map1
map2

0~5分钟的时间内,主线程对map1进行操作;


5~10分钟的时间内,主线程对map2进行操作;


10~15分钟的时间内,先清空map3,主线程对map3进行操作,同时在第10分钟,清除map1的内容,因为map1的内容至少过了5分钟,已经超过了超时时间;


15~20分钟的时间内,先清空map1,主线程对map1进行操作,同时在第15分钟,清除map2的内容,因为map2的内容至少过了5分钟,已经超过了超时时间;


20~25分钟的时间内,先清空map2,主线程对map2进行操作,同时在第20分钟,清除map3的内容,因为map3的内容至少过了5分钟,已经超过了超时时间;


25~30分钟的时间内,先清空map3,主线程对map3进行操作,同时在第25分钟,清除map1的内容,因为map1的内容至少过了5分钟,已经超过了超时时间;


通过这样的操作,就能避免map之间的抢锁操作,唯一需要锁的地方就是operate_flag和delete_flag,而这两个锁可以设置为读写锁,更重要的是仅仅每5分钟才抢一次,几乎相当于无锁。


如果不用map桶删除的超时机制,最笨的办法是将所有的数据记录都加上时间戳,放在一个queue里面,然后根据队列头部的记录,判断该记录是否已被map删除,如果没删除,根据时间戳决定多久之后检查是否超时,或者定时检查是否超时。这将会导致map抢锁时间很长,而且队列可能也会很大。


如果大家有其他想法,欢迎在评论区提出。

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台