GolangHttpSession
目录
- 1. 版权
- 2. 概述
- 3. p_map.go
- 4. t_ses.go
- ses
- sesmgr
- 新建session
- 查找session
- 删除session
- 测试增删改
- 测试性能
- 5. 补充
- 拷贝的性能
- sesmgr 查删性能比较
- 6. 参考
1. 版权
本文为原创, 遵循 CC 4.0 BY-SA 版权协议, 转载需注明出处: .
文中代码属于 public domain (无版权).
2. 概述
关于Golang里实现http session, 以前写过一篇博客, 数据结构是:
type sesmgr struct {lock *sync.Mutexm map[string]*list.Elementl *list.List
}
举例: key1 => e1 (ses1, 15:25过期), key2 => e2 (ses2, 15:20过期). l 按过期时间倒序: e1(15:25) -> e2(15:20).
获取ses2 时, 它的过期时间加上固定的有效期(例如30min), 它变成最后才过期的, 所以移到链头: e2(15:50) -> e1(15:25).
即这个设计限制过期时间总是固定值, 这样无论获取到哪个session 后都会移到链头 - 链尾就逐渐堆积着所有(将要)过期的session, 清理起来很方便.
此设计主要不足是固定有效期. 另外个人认为它的引用关系较多: Element 被m 引用、前/后Element 会互相引用、Element 引用l、l 又引用链头Element. 在数据量增大时gc(内存垃圾回收) 的开销可能相对较大.
关键是在m 之余 维护一个所有session 过期的顺序, 使得在各session 过期值随时变化的情况下, 能快速找到当前最早要过期的session. 按此方向了解了平衡二叉树、红黑树, 最后发现堆 是符合需求的, 因为前2 种都追求所有节点的排序, 而堆(参考) 只保证找出最小的那个节点 - 这就够用了.
通常堆 是用数组实现, 重排时只需交换元素的位置很快. 设计这个数据结构时要考虑:
- 由于m session值 引用-> 堆节点, 堆节点改变位置时要考虑对应session值 里的引用是否也要修改. 如果直接是对象引用, 不需修改, 但是如前所述认为这对于gc 来说并非最好
- 堆 使用slice 的话, 一个问题是扩容: 例如当容纳了10万个节点后要扩容, 需要拷贝这10万节点到新slice - 这或多或少会耗时, 对某些类型的应用可能不能接受
- (堆节点删除后的空位回收不是问题, 因为堆删除的元素会先移到slice 尾, 只要把slice 长度-- 即可)
想要一个引用少、不需拷贝的结构. 在试验中发现Go map的性能很好, 于是想到不如用map 来模拟数组, map key就是数组下标:
- 堆节点下标本来就是从0 开始连续. 例如堆原有3个节点下标分别是0、1、2, 删除1节点后剩余2个节点的下标会调整成0、1
- 没有slice 的扩容问题, 新增节点就是map.set
为减少引用, 可以m session值 存放-> 堆节点的下标. 当堆节点改变下标时, 同步修改对应session值里存放的下标. 一切的前提是Go map的get/set性能.
3. p_map.go
测试3种map key: Longstr、Shortstr、int, 数据量可调:
func main() {rand.Seed(time.Now().Unix())n := 100_000keys := []string{}for i := 0; i < n; i++ {keys = append(keys, genKeyLongstr())// keys = append(keys, genKeyShortstr())// keys = append(keys, rand.Int())}m := map[string][2]int{}t0 := time.Now()for _, key := range keys {m[key] = [2]int{rand.Int(), rand.Int()}}println("init map\n\t", len(m), time.Now().Sub(t0).String())...
}func genKeyLongstr() string {b := make([]byte, 16)rand.Read(b)return fmt.Sprintf("%X", b)
}func genKeyShortstr() string {return strconv.FormatInt(int64(rand.Int()), 36)
}
首先单线程遍历一遍的时间:
println("单线程遍历一遍")t0 = time.Now()for _, key := range keys {if _, ok := m[key]; ok {}}println("\t", time.Now().Sub(t0).String())
其次用4根线程并发做 读+改:
println("4线程查改20s")chX := make(chan int)chOut := make(chan int)mu := new(sync.Mutex)for i := 0; i < 4; i++ {go func(i0 int) {cnt := 0for {select {case <-chX: // 退出chOut <- cntreturndefault:mu.Lock()key := keys[(i0+cnt*4)%n]if v, ok := m[key]; ok {v[1] = rand.Int()m[key] = v}cnt++mu.Unlock()}}}(i)}
每根线程处理不同的数据集, 处理的代码sync.
打印结果:
time.Sleep(20 * time.Second)close(chX)cnts, total := [4]int{}, 0for i := 0; i < 4; i++ {cnts[i] = <-chOuttotal += cnts[i]}fmt.Printf("\t %v total %d(%d)\n", cnts, total, len(strconv.Itoa(total)))
手测(Intel Core i5 2.20GHz 2.19GHz; go1.16 windows/amd64) 结果如下:
// key 数据量 init 单线程遍历一遍 4线程查改20s 内存
// Longstr 10w 30ms 10ms 4kw 21M
// Longstr 100w 500ms 90ms 4kw 220M
// Shortstr 10w 30ms 10ms 4kw 19M
// Shortstr 100w 400ms 100ms 4kw 210M
// int 10w 20ms 5ms 4kw 10M
// int 100w 200ms 80ms 4kw 120M
可见int key 更快, 尤其省内存. 另, 4kw/20s = 2000次/毫秒.
4. t_ses.go
session的概念性实现, 验证新增、修改过期时间、删除操作, 及对比性能.
ses
package mainimport ("container/heap""errors""fmt""math/rand""strconv""sync""time"
)const default_duration = 30 * time.Minute // 默认有效期, 30mintype ses struct {key2 int // 在m2 的下标attrs map[string]interface{} // session 属性
}func (s ses) String() string {return fmt.Sprintf("ses/key2=%d", s.key2)
}
sesmgr
type sesmgr struct {// m2 是map 模拟的堆, key2 是下标, 总是从0 开始连续. 节点0 过期时间最小.//// 堆节点swap 时, 由节点.key1 同步更新m1 ses.key2. 例如:// 123 => ses1(key2=0) => 堆节点0 {123, t1}, 456 => ses2(key2=1) => 堆节点1 {456, t2}.// 堆节点0,1 swap时, 由123,456 找到ses1,ses2 后更新ses.key2:// 123 => ses1(key2=1) => 堆节点1 {123, t1}, 456 => ses2(key2=0) => 堆节点0 {456, t2}.mu *sync.Mutexm1 map[uint32]*ses // session map: key1 => ses.m2 map[int][2]uint32 // session过期时间map: key2 => {key1, 过期时间 (unix seconds)}.
}func (psm *sesmgr) Len() int {sm := *psmreturn len(sm.m2)
}
func (psm *sesmgr) Less(i, j int) bool {sm := *psmreturn sm.m2[i][1] < sm.m2[j][1]
}
func (psm *sesmgr) Swap(i, j int) {sm := *psmsm.m1[sm.m2[i][0]].key2 = jsm.m1[sm.m2[j][0]].key2 = ism.m2[i], sm.m2[j] = sm.m2[j], sm.m2[i]
}
func (psm *sesmgr) Push(x interface{}) {sm := *psmsm.m2[len(sm.m2)] = x.([2]uint32)
}
func (psm *sesmgr) Pop() interface{} {sm := *psmx := sm.m2[len(sm.m2)-1]delete(sm.m2, len(sm.m2)-1)return x
}func newSesmgr() *sesmgr {return &sesmgr{mu: new(sync.Mutex),m1: map[uint32]*ses{},m2: map[int][2]uint32{},}
}
Go 堆 只要求实现heap.Interface 接口, 我们让sesmgr 本身实现它. 其中Swap 互换堆节点位置时, 也同步修改m1 ses.key2.
新建session
// 新建session.
func (psm *sesmgr) newSes() (*ses, error) {sm := *psmsm.mu.Lock()defer sm.mu.Unlock()var key1 uint32for i := 0; i < 11; i++ {if i == 10 { // 尝试10次return nil, errors.New("sesmgr: new key fail")} else {j := rand.Uint32()if _, ok := sm.m1[j]; !ok {key1 = jbreak}}}key2 := len(sm.m2)v1 := &ses{key2: key2,attrs: map[string]interface{}{},}sm.m1[key1] = v1v2 := [2]uint32{key1, rand.Uint32()} // 过期时间用随机值代替heap.Push(psm, v2)return v1, nil
}
由于key1 是uint32, 所以这里最多允许40多亿个session.
查找session
// 查找session. 如果找到, 过期时间增加默认有效期.
func (psm *sesmgr) getSes(key1 uint32) *ses {sm := *psmsm.mu.Lock()defer sm.mu.Unlock()ses, ok := sm.m1[key1]if !ok {return nil}v2 := sm.m2[ses.key2]v2[1] = v2[1] + uint32(default_duration/time.Second)sm.m2[ses.key2] = v2heap.Fix(psm, ses.key2)return ses
}
留意m2 的值 是值类型([2]uint32), 所以修改时要重新set 一次, 否则改的只是一个copy.
修改过期时间后, heap.Fix 内部会调用sesmgr.Less/Swap 方法, 将该节点重排到合适位置, 使得堆头总是最小. Swap 内部会保持m1 与m2 同步.
删除session
// 删除session.
func (psm *sesmgr) delSes(key1 uint32) {sm := *psmsm.mu.Lock()defer sm.mu.Unlock()ses, ok := sm.m1[key1]if !ok {return}heap.Remove(psm, ses.key2)delete(sm.m1, key1)
}
heap.Remove 内部会先把待删节点Swap 到堆尾, 然后调用sesmgr.Pop 方法删掉堆尾节点, 具体参考container/heap 源码. 之后我们同步删除m1 里的值.
测试增删改
func main() {rand.Seed(time.Now().Unix())sm := newSesmgr()ses1, _ := sm.newSes()ses2, _ := sm.newSes()debug(sm, ses1, ses2)fmt.Println("\nses2 过期时间减到0")ses2V2 := sm.m2[ses2.key2]ses2V2[1] = 0sm.m2[ses2.key2] = ses2V2heap.Fix(sm, ses2.key2)debug(sm, ses1, ses2)fmt.Println("\n删除ses2, 新增ses3(显示为ses2)")ses2Key1 := ses2V2[0]sm.delSes(ses2Key1)ses2, _ = sm.newSes()debug(sm, ses1, ses2)...
}func debug(sm *sesmgr, ses1, ses2 *ses) {ses1V2 := sm.m2[ses1.key2]ses2V2 := sm.m2[ses2.key2]fmt.Printf("ses1\n\tkey1=>ses\t\t%d => %v\n\tkey2=>{key1 expire}\t%d => %v\n",ses1V2[0], ses1, ses1.key2, ses1V2)fmt.Printf("ses2\n\tkey1=>ses\t\t%d => %v\n\tkey2=>{key1 expire}\t%d => %v\n",ses2V2[0], ses2, ses2.key2, ses2V2)
}
实测结果一例:
ses1key1=>ses 2130801059 => ses/key2=0key2=>{key1 expire} 0 => [2130801059 2488002794]
ses2key1=>ses 2825755196 => ses/key2=1key2=>{key1 expire} 1 => [2825755196 3040392722]ses2 过期时间减到0
ses1key1=>ses 2130801059 => ses/key2=1key2=>{key1 expire} 1 => [2130801059 2488002794]
ses2key1=>ses 2825755196 => ses/key2=0key2=>{key1 expire} 0 => [2825755196 0]删除ses2, 新增ses3(显示为ses2)
ses1key1=>ses 2130801059 => ses/key2=0key2=>{key1 expire} 0 => [2130801059 2488002794]
ses2key1=>ses 944377615 => ses/key2=1key2=>{key1 expire} 1 => [944377615 4200946011]
ses1 过期时间(2488002794) 小于ses2 的(3040392722), 所以堆顺序是ses1 -> ses2.
将ses2 过期时间改为0 后, 堆顺序变为ses2 -> ses1.
删掉ses2 后由于ses3 的过期时间(4200946011) 大于ses1 的, 所以堆顺序变成ses1 -> ses2(ses3).
测试性能
fmt.Println("\ninit map")n := 1_000_000t0 := time.Now()keys1 := make([]uint32, n)for i := 0; i < n; i++ {if ses, err := sm.newSes(); err != nil {panic(err)} else {keys1[i] = sm.m2[ses.key2][0]}}fmt.Println("\t", n, time.Now().Sub(t0).String())
单线程遍历一遍的时间:
fmt.Println("单线程遍历一遍")t0 = time.Now()for _, key1 := range keys1 {sm.getSes(key1)}fmt.Println("\t", time.Now().Sub(t0).String())
4根线程并发遍历:
fmt.Println("4线程遍历20s")chX := make(chan int)chOut := make(chan int)for i := 0; i < 4; i++ {go func(i0 int) {cnt := 0for {select {case <-chX: // 退出chOut <- cntreturndefault:key1 := keys1[(i0+cnt*4)%n]sm.getSes(key1)cnt++}}}(i)}
打印结果:
time.Sleep(20 * time.Second)close(chX)cnts, total := [4]int{}, 0for i := 0; i < 4; i++ {cnts[i] = <-chOuttotal += cnts[i]}fmt.Printf("\t %v total %d(%d)\n", cnts, total, len(strconv.Itoa(total)))
手测结果:
// 数据量 init 单线程遍历一遍 4线程遍历20s 内存// 10w 120ms 40ms 2kw 16M// 100w 1s 500ms 1.9kw 190M
内存稍大于p_map int 的, 4线程并发数接近p_map 的一半, 由于getSes 内部实际有多次查改, 所以似乎可以.
5. 补充
拷贝的性能
// 10w 1ms 100w 10ms
func oneDim() {n := 100_000src := make([][2]int, n)for i := 0; i < n; i++ {src[i][0] = rand.Int()src[i][1] = rand.Int()}// println(src[0][0], src[0][1], src[99][0], src[99][1])dst := make([][2]int, 2*n)t0 := time.Now()cn := copy(dst, src)println(cn, time.Now().Sub(t0).String())// println(dst[0][0], dst[0][1], dst[99][0], dst[99][1])
}// 10w 4ms 100w 30ms - 这里拷贝指针比拷贝值 更慢.
func oneDimP() {n := 100_000src := make([]*[2]int, n)for i := 0; i < n; i++ {src[i] = &[2]int{rand.Int(), rand.Int()}}// println(src[0][0], src[0][1], src[99][0], src[99][1])dst := make([]*[2]int, 2*n)t0 := time.Now()cn := copy(dst, src)println(cn, time.Now().Sub(t0).String())// println(dst[0][0], dst[0][1], dst[99][0], dst[99][1])
}
手测结果: 10w 1ms, 100w 10ms. 由于sesmgr 性能是1000次/毫秒, 可见拷贝还是会有影响的.
sesmgr 查删性能比较
fmt.Println("单线程删除1/10")t0 = time.Now()for i := n / 10; i >= 0; i-- {sm.delSes(sm.m2[0][0])}fmt.Println("\t", time.Now().Sub(t0).String(), len(sm.m1))
手测10w和100w时, 单线程遍历一遍 : 单线程删除1/10 ≈ 2 : 3, 即删1次的耗时约等于读15次.
6. 参考
GolangHttpSession-2 数据结构l2
Golang三叉堆
更多推荐
GolangHttpSession
发布评论