前言
通过双向链表实现session的过期扫描。
双向链表
go 中实现为 list.List
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}
// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value interface{}
}
实例
web开发中服务端需要维护session， session的实现可以有多种方式。例如内存，文件，数据库，redis 等。所以，对于不同的实现，抽象出Provider接口，实现有MemProvider FileProvider RedisProvider ...
另外，session通常有过期时间，所以需要服务端定期回收过期session。
provider接口定义如下：
type Provider interface {
SessionInit(gclifetime int64, config string) error
SessionRead(sid string) (Store, error)
SessionExist(sid string) bool
SessionDestroy(sid string) error
SessionAll() int //get all active session
SessionGC()
}
以内存session provider为例，通常通过map保存session，通过map而不是list，因为map保证了查找时间是o(1), 即SessionRead 通过session id 获取session。
type MemProvider struct {
lock sync.RWMutex // locker
sessions map[string]*list.Element // map in memory
list *list.List // for gc
maxlifetime int64
}
如果只有map保存数据，当每次定期清理过期session时，需要遍历 时间复杂度为o(n)。所以为了提高清理效率，使用list维护记录session，当更新session最后使用时间时，将list中的session放到列表首部。list首部是最近使用的session。
当清理过期遍历时，从list尾部遍历，直到遇到第一个没有过期的session结束。
map的value中存储的是*list.Element类型，通过map的key获取element，然后通过element操作list。如果map的value中只存了使用方的value类型，则无法通过map的key快速找到list中的元素。
链表的节点存储key和value，使用节点中的key可以操作map。 类似于java中linkedhashmap 的内部类Entry<k,v>
java中 类似需求 可以使用 LinkedHashMap ，将构造函数第三个参数 设为true
参考资料
思考
- 使用堆大堆，按session的最后更新时间排序。代替list
堆 提供添加和删除接口，对于变更session的最后更新时间，无法方便维护堆结构。而双向链表将元素移动到首尾，时间复杂度为o(1) - 使用 单向链表，代替。
将元素移动到首尾，单向链表无法实现o(1)的复杂度。 - 堆 与 双向链表 使用场景对比
双向链表维护顺序时，包含3个操作， 新增，删除，更新
新增，更新操作时，元素都会被放到首部或尾部。不会存在新增元素，排序的结构是放到链表中。
堆维护顺序时， 包含2个操作，新增，从顶点删除
新增元素后，堆重新排序，将元素放到符合结构的位置，最终结果元素不一定在顶点。
网友评论