前言
TTLMap是一个比较实用的数据结构，特别是在需要缓存数据的场景下。TTLMap的实现现不算复杂，但也有许多需要注意的地方，这也是这篇文章出现的原因。
在TTLMap里，移除失效的数据有三种策略：立即删除、惰性删除和定期删除策略。立即删除策略会在数据过期时立即将数据删除；惰性删除策略只在碰到过期键时才进行删除操作；定期删除策略则每隔一段时间，主动查找并删除过期键。第一种策略对CPU不友好，第二种策略容易造成内存泄露。Redis对设置了TTL的数据采取的是惰性删除和定期删除策略，而本篇文章会将重点放在性能上，所以只会采取定期删除策略。
注：本篇文章使用go1.13.5 linux/amd64
接口定义
先来看看TTLMap的接口定义：
1
2
3
4
5
6
7
8
9
10
11
| type TTLMap interface {
Get(key string) (interface{}, bool)
Set(key string, val interface{}, ex time.Duration)
Len() int
clean(tick time.Duration)
}
type item struct {
value interface{}
expire int64
}
|
Get()函数负责从TTLMap中获取数据，如数据不存在或已失效则第二个返回值为false，行为和内置的map保持一致。Set()函数负责将数据放入TTLMap，并接收一个time.Duration参数用来标示数据的生命周期。Len()函数返回TTLMap中数据的数量，不过为了性能考虑，一般不区分数据是否已经失效。clean()函数则负责实现上文提到的定期删除策略。
初步实现（V0版本）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| type TTLMapV0 struct {
items map[string]item
mux *sync.Mutex
}
func (tm *TTLMapV0) Get(key string) (interface{}, bool) {
tm.mux.Lock()
defer tm.mux.Unlock()
if item, ok := tm.items[key]; !ok || time.Now().UnixNano() > item.expire {
return nil, false
} else {
return item.value, true
}
}
func (tm *TTLMapV0) Set(key string, val interface{}, ex time.Duration) {
tm.mux.Lock()
tm.items[key] = item{value: val, expire: time.Now().Add(ex).UnixNano()}
tm.mux.Unlock()
}
func (tm *TTLMapV0) Len() int {
tm.mux.Lock()
defer tm.mux.Unlock()
return len(tm.items)
}
func (tm *TTLMapV0) clean(tick time.Duration) {
for range time.Tick(tick) {
tm.mux.Lock()
for key, item := range tm.items {
if time.Now().UnixNano() >= item.expire {
delete(tm.items, key)
}
}
tm.mux.Unlock()
}
}
func NewTTLMapV0(cleanTick time.Duration) *TTLMapV0 {
tm := &TTLMapV0{items: map[string]item{}, mux: new(sync.Mutex)}
go tm.clean(cleanTick)
return tm
|
防止内存泄露（V1版本）
上面的V0版本实现在功能上已经基本完整了，但由于clean()函数会一直运行，所以V0版本的TTLMap不会被Golang的垃圾回收机制回收，进而引起内存泄露。所以我们需要对V0版本做出一点改进，并将改进后的TTLMap包裹起来以启动自动回收机制：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| type TTLMapV1 struct {
*TTLMapV0
stop chan bool
}
func (tm *TTLMapV1) clean(tick time.Duration) {
for range time.Tick(tick) {
select {
case <-tm.stop:
return
default:
tm.mux.Lock()
for key, item := range tm.items {
if time.Now().UnixNano() >= item.expire {
delete(tm.items, key)
}
}
tm.mux.Unlock()
}
}
}
type TTLMapWrapper struct {
TTLMap
}
func NewTTLMapV1(cleanTick time.Duration) *TTLMapWrapper {
tm0 := &TTLMapV0{items: map[string]item{}, mux: new(sync.Mutex)}
tm1 := &TTLMapV1{TTLMapV0: tm0, stop: make(chan bool)}
go tm1.clean(cleanTick)
tmw := &TTLMapWrapper{TTLMap: tm1}
runtime.SetFinalizer(tmw, func(_ interface{}) { tm1.stop <- true })
return tmw
}
|
验证自动回收是否启用
为了验证上文的改进是否有效，将代码改动如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func (tm *TTLMapV0) clean(tick time.Duration) {
defer fmt.Println("v0.clean() stopped")
}
func NewTTLMapV0(cleanTick time.Duration) *TTLMapV0 {
runtime.SetFinalizer(tm, func(_ interface{}) { fmt.Println("v0 gone") })
return tm
}
func (tm *TTLMapV1) clean(tick time.Duration) {
defer func() { fmt.Println("v1.clean() stopped") }()
}
func NewTTLMapV1(cleanTick time.Duration) *TTLMapWrapper {
runtime.SetFinalizer(tm1, func(_ interface{}) { fmt.Println("v1 gone") })
runtime.SetFinalizer(tm0, func(_ interface{}) { fmt.Println("v1.v0 gone") })
return tmw
}
|
然后编写测试代码并运行：
1
2
3
4
5
6
7
8
9
10
11
12
13
| func TestTTLMap(t *testing.T) {
func() {
NewTTLMapV0(time.Millisecond * 100)
NewTTLMapV1(time.Millisecond * 100)
}()
fmt.Println("--> first gc")
runtime.GC()
time.Sleep(time.Millisecond * 200)
fmt.Println("--> second gc")
runtime.GC()
fmt.Println("--> third gc")
runtime.GC()
}
|
1
2
3
4
5
6
7
8
9
| $ go test .
=== RUN TestTTLMap
--> first gc
v1.clean() stopped
--> second gc
v1 gone
--> third gc
v1.v0 gone
--- PASS: TestTTLMap (0.20s)
|
可以看到，改进后的代码确实生效了，未被引用的TTLMap（V1版本）会被自动回收，不会出现内存泄露。
PS：在接下来的版本将省略TTLMapWrapper的实现部分
使用读写锁提高性能（V2版本）
在之前的版本里，TTLMap使用的并发控制锁都是普通的sync.Mutex，也就是说同一时刻只能有一个Goruntime访问该对象。但TTLMap应用的场景大多是读多写少，所以我们可以使用读写锁，即sync.RWMutex来获得更好性能：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| type TTLMapV2 struct {
items map[string]item
mux *sync.RWMutex
}
func (tm *TTLMapV2) Get(key string) (interface{}, bool) {
tm.mux.RLock()
defer tm.mux.RUnlock()
if item, ok := tm.items[key]; !ok || time.Now().UnixNano() > item.expire {
return nil, false
} else {
return item.value, true
}
}
func (tm *TTLMapV2) Set(key string, val interface{}, ex time.Duration) {
}
func (tm *TTLMapV2) clean(tick time.Duration) {
}
func (tm *TTLMapV2) Len() int {
tm.mux.RLock()
defer tm.mux.RUnlock()
return len(tm.items)
}
func NewTTLMapV2(cleanTick time.Duration) *TTLMapV2 {
tm := &TTLMapV2{map[string]item{}, new(sync.RWMutex)}
go tm.clean(cleanTick)
return tm
}
|
使用不精确的时间提高性能（V3版本）
在之前的版本里，每次调用Get()和Set()函数时都会调用time.Now()以获取精确时间。但在对时间的精确度要求不那么高的场合下，可以缓存time.Now()的结果来获得更好的性能：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| type TTLMapV3 struct {
items map[string]item
mux *sync.RWMutex
now int64
}
func (tm *TTLMapV3) Get(key string) (interface{}, bool) {
tm.mux.RLock()
defer tm.mux.RUnlock()
if item, ok := tm.items[key]; !ok || tm.now > item.expire {
return nil, false
} else {
return item.value, true
}
}
func (tm *TTLMapV3) Set(key string, val interface{}, ex time.Duration) {
tm.mux.Lock()
tm.items[key] = item{value: val, expire: tm.now + ex.Nanoseconds()}
tm.mux.Unlock()
}
func (tm *TTLMapV3) Len() int {
}
func (tm *TTLMapV3) clean(tick time.Duration) {
for range time.Tick(tick) {
tm.mux.Lock()
for key, item := range tm.items {
if tm.now >= item.expire {
delete(tm.items, key)
}
}
tm.mux.Unlock()
}
}
func (tm *TTLMapV3) updateNow(tick time.Duration) {
for range time.Tick(tick) {
tm.mux.Lock()
tm.now = time.Now().UnixNano()
tm.mux.Unlock()
}
}
func NewTTLMapV3(cleanTick time.Duration) *TTLMapV3 {
tm := &TTLMapV3{map[string]item{},
new(sync.RWMutex), time.Now().UnixNano()}
go tm.clean(cleanTick)
go tm.updateNow(time.Second)
return tm
}
|
性能测试&结语
编写测试代码用于测试以上版本的性能并运行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func BenchmarkTTLMap(b *testing.B) {
rand.Seed(time.Now().UnixNano())
key := RandStringBytesRmndr(20)
tasks := []struct {
name string
ttl TTLMap
}{
{"TTLMapV0", NewTTLMapV0(time.Minute)},
{"TTLMapV2", NewTTLMapV2(time.Minute)},
{"TTLMapV3", NewTTLMapV3(time.Minute)},
}
for _, task := range tasks {
b.Run(task.name, func(sb *testing.B) {
sb.RunParallel(func(pb *testing.PB) {
for pb.Next() {
task.ttl.Set(key, key, time.Minute)
task.ttl.Get(key)
}
})
})
}
}
|
1
2
3
4
5
6
7
| $ go test -bench .
goos: linux
goarch: amd64
BenchmarkTTLMap/TTLMapV0-8 3972699 301 ns/op
BenchmarkTTLMap/TTLMapV2-8 4972598 241 ns/op
BenchmarkTTLMap/TTLMapV3-8 9125235 132 ns/op
PASS
|
可以看出，V2相比V0性能提升了20%左右，而V3相比V0的性能提升幅度更是超过了56%。而从PPROF的分析结果来看，剩下的时间主要消耗在互斥锁上，应该很难有进一步优化的空间了。
虽然理论上来说用int当Map的键而不是string时会有更好的性能表现，但是从实际测试来看，对于长度为20的string，fnv32等哈希算法的开销还是超过了其能带来的收益，更别提还要考虑潜在的哈希冲突。
最后要重申一点的是，V2和V3版本的实现省略了V1中提到的TTLMapWrapper部分，所以请不要直接使用V2和V3版本的代码😂
引用