golang实现expiredMap，key带过期时间，超时自动删除

短命女 2022-04-02 10:18 405阅读 0赞

github地址：[https://github.com/hackssssss/ExpiredMap][https_github.com_hackssssss_ExpiredMap]

偶然间看到一篇关于超期删除key的map的文章，感觉很有意思，于是自己去实现了一下。

了解了一下redis中key的过期策略，发现主要有三种策略：一种是被动删除，即key过期之后，先不将其删除，当实际访问到的时候，判断其是否过期，再采取相应的措施。第二种是主动删除，即当key过期之后，立即将这个key删除掉。第三种是当内存超过某个限制，触发删除过期key的策略。

被动删除即惰性删除，在redis中数据量比较小时很好用，不需要实时去删除key，只要在访问时判定就可以，节省cpu性能，缺点是不能及时删除过期key，内存用的稍多一些，但是数据量小时还是能接受的。

主动删除需要后台守护进程不断去删除过期的key，稍微耗费一些cpu资源，但是在数据量很大时，内存能很快降下来供其他数据的存储。

这里采用主动删除和被动删除相结合的方式，后台会创建一个goroutine来不断检测是否有过期的key，检测到了就删除这个key，目前的过期单位能精确到秒。

package expire_map
    
    import (
    	"sync"
    	"time"
    )
    
    type val struct {
    	data        interface{}
    	expiredTime int64
    }
    
    const delChannelCap = 100
    
    type ExpiredMap struct {
    	m       map[interface{}]*val
    	timeMap map[int64][]interface{}
    	lck     *sync.Mutex
    	stop    chan struct{}
    }
    
    func NewExpiredMap() *ExpiredMap {
    	e := ExpiredMap{
    		m:       make(map[interface{}]*val),
    		lck:     new(sync.Mutex),
    		timeMap: make(map[int64][]interface{}),
    		stop:    make(chan struct{}),
    	}
    	go e.run(time.Now().Unix())
    	return &e
    }
    
    type delMsg struct {
    	keys []interface{}
    	t    int64
    }
    
    //background goroutine 主动删除过期的key
    //数据实际删除时间比应该删除的时间稍晚一些，这个误差会在查询的时候被解决。
    func (e *ExpiredMap) run(now int64) {
    	t := time.NewTicker(time.Second * 1)
    	defer t.Stop()
    	delCh := make(chan *delMsg, delChannelCap)
    	go func() {
    		for v := range delCh {
    			e.multiDelete(v.keys, v.t)
    		}
    	}()
    	for {
    		select {
    		case <-t.C:
    			now++ //这里用now++的形式，直接用time.Now().Unix()可能会导致时间跳过1s，导致key未删除。
    			e.lck.Lock()
    			if keys, found := e.timeMap[now]; found {
    				e.lck.Unlock()
    				delCh <- &delMsg{keys: keys, t: now}
    			} else {
    				e.lck.Unlock()
    			}
    		case <-e.stop:
    			close(delCh)
    			return
    		}
    	}
    }
    
    func (e *ExpiredMap) Set(key, value interface{}, expireSeconds int64) {
    	if expireSeconds <= 0 {
    		return
    	}
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	expiredTime := time.Now().Unix() + expireSeconds
    	e.m[key] = &val{
    		data:        value,
    		expiredTime: expiredTime,
    	}
    	e.timeMap[expiredTime] = append(e.timeMap[expiredTime], key) //过期时间作为key，放在map中
    }
    
    func (e *ExpiredMap) Get(key interface{}) (found bool, value interface{}) {
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	if found = e.checkDeleteKey(key); !found {
    		return
    	}
    	value = e.m[key].data
    	return
    }
    
    func (e *ExpiredMap) Delete(key interface{}) {
    	e.lck.Lock()
    	delete(e.m, key)
    	e.lck.Unlock()
    }
    
    func (e *ExpiredMap) Remove(key interface{}) {
    	e.Delete(key)
    }
    
    func (e *ExpiredMap) multiDelete(keys []interface{}, t int64) {
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	delete(e.timeMap, t)
    	for _, key := range keys {
    		delete(e.m, key)
    	}
    }
    
    func (e *ExpiredMap) Length() int { //结果是不准确的，因为有未删除的key
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	return len(e.m)
    }
    
    func (e *ExpiredMap) Size() int {
    	return e.Length()
    }
    
    //返回key的剩余生存时间 key不存在返回负数
    func (e *ExpiredMap) TTL(key interface{}) int64 {
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	if !e.checkDeleteKey(key) {
    		return -1
    	}
    	return e.m[key].expiredTime - time.Now().Unix()
    }
    
    func (e *ExpiredMap) Clear() {
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	e.m = make(map[interface{}]*val)
    	e.timeMap = make(map[int64][]interface{})
    }
    
    func (e *ExpiredMap) Close() { // todo 关闭后在使用怎么处理
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	e.stop <- struct{}{}
    	//e.m = nil
    	//e.timeMap = nil
    }
    
    func (e *ExpiredMap) Stop() {
    	e.Close()
    }
    
    func (e *ExpiredMap) DoForEach(handler func(interface{}, interface{})) {
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	for k, v := range e.m {
    		if !e.checkDeleteKey(k) {
    			continue
    		}
    		handler(k, v)
    	}
    }
    
    func (e *ExpiredMap) DoForEachWithBreak(handler func(interface{}, interface{}) bool) {
    	e.lck.Lock()
    	defer e.lck.Unlock()
    	for k, v := range e.m {
    		if !e.checkDeleteKey(k) {
    			continue
    		}
    		if handler(k, v) {
    			break
    		}
    	}
    }
    
    func (e *ExpiredMap) checkDeleteKey(key interface{}) bool {
    	if val, found := e.m[key]; found {
    		if val.expiredTime <= time.Now().Unix() {
    			delete(e.m, key)
    			//delete(e.timeMap, val.expiredTime)
    			return false
    		}
    		return true
    	}
    	return false
    }

[https_github.com_hackssssss_ExpiredMap]: https://github.com/hackssssss/ExpiredMap