Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

一道涉及锁的Go面试题 #32

Open
AbelLai opened this Issue Apr 26, 2018 · 2 comments

Comments

Projects
None yet
3 participants
@AbelLai
Copy link
Owner

AbelLai commented Apr 26, 2018

昨天去面试Go开发岗位,遇到了一道关于锁的题目。一看题目,我大概知道要考的内容是什么。当时一想到需要在纸上写那么多代码,便留空白了。后来与面试官聊的时候,我说了这道题空白的原因。然后他问你知道要考什么么。我说要加锁实现。最后,他说你只要写上要加锁这道对我来说都算过了。

这题目网上也能找到,如Csdn上这哥们的就说到这道题,不过他的实现还是有问题。下面我实现的一个,跟那哥们的做法差不多,只不过我个人偏向于把Mutex嵌入到Struct里面去。

题目

在一个高并发的web服务器中,要限制IP的频繁访问。现模拟100个IP同时并发访问服务器,每个IP要重复访问1000次。每个IP三分钟之内只能访问一次。修改以下代码完成该过程,要求能成功输出 success: 100。

代码:

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)
}

考点

  1. 锁。map这个数据结构不是并发安全的。所以,需要加锁来确保map的写与读是安全的。
  2. 协程同步。给出的样例代码里面用了嵌套的for循环,产生1000 x 100个协程。所以,这里需要用WaitGroup来确保所有协程都跑完,才打印success的结果。
  3. 值覆盖。main函数里面,for循环里面的协程不能直接使用j,需要通过函数参数传递的方式。
  4. 原子操作。由于success在多个协程里面进行递增,所以最好的方式还是需要使用原子操作。

实现

明确了考点,那实现的代码如下。

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

type Ban struct {
	visitIPs map[string]time.Time
	lock     sync.Mutex
}

func NewBan() *Ban {
	return &Ban{visitIPs: make(map[string]time.Time)}
}

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()
	o.timeAllow(ip)
	return false
}

func (o *Ban) timeAllow(ip string) {
	go func() {
		time.Sleep(time.Minute * 3)

		o.lock.Lock()
		defer o.lock.Unlock()

		delete(o.visitIPs, ip)
	}()
}

func main() {
	var wg sync.WaitGroup
	var success int64
	ban := NewBan()

	for i := 0; i < 1000; i++ {
		for j := 0; j < 100; j++ {
			wg.Add(1)

			go func(ip int) {
				defer wg.Done()
				ipStr := fmt.Sprintf("192.168.1.%d", ip)

				if !ban.visit(ipStr) {
					atomic.AddInt64(&success, 1) // 原子操作
				}
			}(j) // 值传递,防止值覆盖
		}
	}

	wg.Wait() // 协程同步
	fmt.Println("success: ", success)
}

END ~~~

@AbelLai AbelLai added the Golang label Apr 26, 2018

@RainbowMango

This comment has been minimized.

Copy link

RainbowMango commented Nov 15, 2018

还是首次见文章写到issue里呢 :)

@cookedsteak

This comment has been minimized.

Copy link

cookedsteak commented Feb 15, 2019

偶然看见,我觉得可以直接用 sync.Map
上代码:

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

type Ban struct {
	M sync.Map
}

func (b *Ban) IsIn(user string) bool {
	fmt.Printf("%s 进来了\n", user)
	v, ok := b.M.LoadOrStore(user, time.Now())
	if !ok {
		fmt.Printf("名单里没有 %s,可以访问\n", user)
		return false
	}
	if time.Now().Second() - v.(time.Time).Second() > 180 {
		fmt.Printf("时间为:%d-%d\n", v.(time.Time).Second(), time.Now().Second())
		b.M.Delete(user)
		return false
	}

	fmt.Printf("名单里有 %s,拒绝访问\n", user)
	return true
}

func NewBanList() *Ban {
	return &Ban{}
}

func main() {
	var success int64 = 0
	ban := NewBanList()
	wg := sync.WaitGroup{}
	for i := 0; i < 1000; i++ {
		for j := 0; j < 100; j++ {
			wg.Add(1)
			go func(c int) {
				defer wg.Done()
				ip := fmt.Sprintf("%d", c)
				if !ban.IsIn(ip) {
					atomic.AddInt64(&success, 1)
				}
			}(j)
		}
	}
	wg.Wait()
	fmt.Println("此次访问量:", success)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.