算法:高并发下的锁与map的读写
场景:在一个高并发的web服务器中,要限制IP的频繁访问。现模拟100个IP同时并发访问服务器,每个IP要重复访问1000次。
每个IP三分钟之内只能访问一次。修改以下代码完成该过程,要求能成功输出 success:100
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
package main
import (
"fmt"
"time"
)
type Ban struct {
visitIPs map[string]time.Time
}
func NewBan() *Ban {
return &Ban{visitIPs: make(map[string]time.Time)}
}
func (o *Ban) visit(ip string) bool {
if _, ok := o.visitIPs[ip]; ok {
return true
}
o.visitIPs[ip] = time.Now()
return false
}
func main() {
success := 0
ban := NewBan()
for i := 0; i < 1000; i++ {
for j := 0; j < 100; j++ {
go func() {
ip := fmt.Sprintf("192.168.1.%d", j)
if !ban.visit(ip) {
success++
}
}()
}
}
fmt.Println("success:", success)
}
解析
该问题主要考察了并发情况下map的读写问题,而给出的初始代码,又存在for
循环中启动goroutine
时变量使用问题以及goroutine
执行滞后问题。
因此,首先要保证启动的goroutine
得到的参数是正确的,然后保证map
的并发读写,最后保证三分钟只能访问一次。
多CPU核心下修改int
的值极端情况下会存在不同步情况,因此需要原子性的修改int值。
下面给出的实例代码,是启动了一个协程每分钟检查一下map
中的过期ip
,for
启动协程时传参。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package main
import (
"context"
"fmt"
"sync"
"sync/atomic"
"time"
)
type Ban struct {
visitIPs map[string]time.Time
lock sync.Mutex
}
func NewBan(ctx context.Context) *Ban {
o := &Ban{visitIPs: make(map[string]time.Time)}
go func() {
timer := time.NewTimer(time.Minute * 1)
for {
select {
case <-timer.C:
o.lock.Lock()
for k, v := range o.visitIPs {
if time.Now().Sub(v) >= time.Minute*1 {
delete(o.visitIPs, k)
}
}
o.lock.Unlock()
timer.Reset(time.Minute * 1)
case <-ctx.Done():
return
}
}
}()
return o
}
func (o *Ban) visit(ip string) bool {
o.lock.Lock()
defer o.lock.Unlock()
if _, ok := o.visitIPs[ip]; ok {
return true
}
o.visitIPs[ip] = time.Now()
return false
}
func main() {
success := int64(0)
ctx, cancel := context.WithCancel(context.Background())
defer cancel()
ban := NewBan(ctx)
wait := &sync.WaitGroup{}
wait.Add(1000 * 100)
for i := 0; i < 1000; i++ {
for j := 0; j < 100; j++ {
go func(j int) {
defer wait.Done()
ip := fmt.Sprintf("192.168.1.%d", j)
if !ban.visit(ip) {
atomic.AddInt64(&success, 1)
}
}(j)
}
}
wait.Wait()
fmt.Println("success:", success)
}