偶然看見(jiàn)這么篇文章：一道并發(fā)和鎖的golang面試題。
雖然年代久遠(yuǎn)，但也稍有興趣。
正好最近也看到了 sync.Map缠犀，所以想試試能不能用 sync.Map 去實(shí)現(xiàn)上述的功能。
我還在 gayhub上找到了其他人用 sync.Mutex 的實(shí)現(xiàn)方式狭归，【點(diǎn)擊這里】夭坪。
歸結(jié)一下
需求是這樣的：
在一個(gè)高并發(fā)的web服務(wù)器中，要限制IP的頻繁訪問(wèn)」担現(xiàn)模擬100個(gè)IP同時(shí)并發(fā)訪問(wèn)服務(wù)器，每個(gè)IP要重復(fù)訪問(wèn)1000次戏仓。每個(gè)IP三分鐘之內(nèi)只能訪問(wèn)一次疚宇。修改以下代碼完成該過(guò)程亡鼠，要求能成功輸出 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)
}
哦吼敷待，看到源代碼我想說(shuō)间涵，我能只留個(gè)package main其他都重新寫嗎？（捂臉）
聰明的你已經(jīng)發(fā)現(xiàn)榜揖，這個(gè)問(wèn)題關(guān)鍵就是想讓你給 Ban 加一個(gè)讀寫鎖罷了勾哩。
而且條件中的三分鐘根本無(wú)傷大雅，因?yàn)檫@程序壓根就活不到那天举哟。
思路
其實(shí)思劳，原始的思路并沒(méi)有發(fā)生改變，還是用一個(gè) BanList 去盛放哪些暫時(shí)無(wú)法訪問(wèn)的用戶 id妨猩。
然后每次訪問(wèn)的時(shí)候判斷一下這個(gè)用戶是否在這個(gè) List 中潜叛。
修改
好，那我們現(xiàn)在需要一個(gè)結(jié)構(gòu)體壶硅，因?yàn)槲覀儠?huì)并發(fā)讀取 map威兜，所以我們直接使用 sync.Map：
type Ban struct {
M sync.Map
}
如果你點(diǎn)進(jìn) sync.Map 你會(huì)發(fā)現(xiàn)他真正存儲(chǔ)數(shù)據(jù)的是一個(gè)atomic.Value。
一個(gè)具有原子特性的 interface{}庐椒。
同時(shí)Ban這個(gè)結(jié)構(gòu)提還會(huì)有一個(gè) IsIn 的方法用來(lái)判斷用戶 id 是否在Map中椒舵。
func (b *Ban) IsIn(user string) bool {
fmt.Printf("%s 進(jìn)來(lái)了\n", user)
// Load 方法返回兩個(gè)值，一個(gè)是如果能拿到的 key 的 value
// 還有一個(gè)是否能夠拿到這個(gè)值的 bool 結(jié)果
v, ok := b.M.Load(user) // sync.Map.Load 去查詢對(duì)應(yīng) key 的值
if !ok {
// 如果沒(méi)有约谈，說(shuō)明可以訪問(wèn)
fmt.Printf("名單里沒(méi)有 %s逮栅，可以訪問(wèn)\n", user)
// 將用戶名存入到 Ban List 中
b.M.Store(ip, time.Now())
return false
}
// 如果有，則判斷用戶的時(shí)間距離現(xiàn)在是否已經(jīng)超過(guò)了 180 秒窗宇，也就是3分鐘
if time.Now().Second() - v.(time.Time).Second() > 180 {
// 超過(guò)則可以繼續(xù)訪問(wèn)
fmt.Printf("時(shí)間為：%d-%d\n", v.(time.Time).Second(), time.Now().Second())
// 同時(shí)重新存入時(shí)間
b.M.Store(ip, time.Now())
return false
}
// 否則不能訪問(wèn)
fmt.Printf("名單里有 %s措伐，拒絕訪問(wèn)\n", user)
return true
}
下面看看測(cè)試的函數(shù)：
func main() {
var success int64 = 0
ban := new(Ban)
wg := sync.WaitGroup{} // 保證程序運(yùn)行完成
for i := 0; i < 2; i++ { // 我們大循環(huán)兩次，每個(gè)user 連續(xù)訪問(wèn)兩次
for j := 0; j < 10; j++ { // 人數(shù)預(yù)先設(shè)定為 10 個(gè)人
wg.Add(1)
go func(c int) {
defer wg.Done()
ip := fmt.Sprintf("%d", c)
if !ban.IsIn(ip) {
// 原子操作增加計(jì)數(shù)器军俊，用來(lái)統(tǒng)計(jì)我們?nèi)藬?shù)的
atomic.AddInt64(&success, 1)
}
}(j)
}
}
wg.Wait()
fmt.Println("此次訪問(wèn)量：", success)
}
其實(shí)測(cè)試的函數(shù)并沒(méi)有做大的改動(dòng)侥加，只不過(guò)，因?yàn)槲覀兪遣l(fā)去運(yùn)行的粪躬，需要增加一個(gè) sync.WaitGroup() 保證程序完整運(yùn)行完畢后才退出担败。
我特地把運(yùn)行數(shù)值調(diào)小一點(diǎn)，以方便測(cè)試镰官。
把1000次請(qǐng)求提前，改為2次。100人改為10人泳唠。
所以整個(gè)代碼應(yīng)該是這樣的：
package main
import (
"fmt"
"sync"
"sync/atomic"
"time"
)
type Ban struct {
M sync.Map
}
func (b *Ban) IsIn(user string) bool {
...
}
func main() {
...
}
運(yùn)行一下...
誒狈网，似乎不太對(duì)哦，發(fā)現(xiàn)會(huì)出現(xiàn) 10~15 次不等的訪問(wèn)量結(jié)果。為什么呢拓哺？
尋思著勇垛，其實(shí)因?yàn)椴l(fā)導(dǎo)致的，看到這里了嗎士鸥？
func (b *Ban) IsIn(user string) bool {
...
v, ok := b.M.Load(user)
if !ok {
fmt.Printf("名單里沒(méi)有 %s闲孤，可以訪問(wèn)\n", user)
b.M.Store(ip, time.Now())
return false
}
...
}
并發(fā)發(fā)起的 sync.Map.Load 其實(shí)并沒(méi)有與 sync.Map.Store 連接起來(lái)形成原子操作。
所以如果有3個(gè) user 同時(shí)進(jìn)來(lái)烤礁，程序同時(shí)查詢讼积，三個(gè)返回結(jié)果都會(huì)是 false（不在名單里）。
所以也就增加了訪問(wèn)的數(shù)量脚仔。
其實(shí) sync.Map 也已經(jīng)考慮到了這種情況勤众，所以他會(huì)有一個(gè) LoadOrStore 的原子方法--
如果 Load 不出，就直接 Store玻侥，如果 Load 出來(lái)决摧，那啥也不做。
所以我們小改一下 IsIn 的代碼：
func (b *Ban) IsIn(user string) bool {
...
v, ok := b.M.LoadOrStore(user, time.Now())
if !ok {
fmt.Printf("名單里沒(méi)有 %s凑兰，可以訪問(wèn)\n", user)
// 刪除b.M.Store(ip, time.Now())
return false
}
...
}
然后我們?cè)龠\(yùn)行一下掌桩，運(yùn)行幾次。
發(fā)覺(jué)不會(huì)再出現(xiàn) 此次訪問(wèn)量大于 10 的情況了姑食。
深究一下
到此為止波岛，這個(gè)場(chǎng)景下的代碼實(shí)現(xiàn)我們算是成功了。
但是真正限制用戶訪問(wèn)的場(chǎng)景需求可不能這么玩音半，一般還是配合內(nèi)存數(shù)據(jù)庫(kù)去實(shí)現(xiàn)则拷。
那么，如果你只想了解 sync.Map 的應(yīng)用曹鸠，就到這里為止了煌茬。
然而好奇心驅(qū)使我看看 sync.Map 的實(shí)現(xiàn)，我們繼續(xù)吧彻桃。
制造問(wèn)題
如果硬是要并發(fā)讀寫一個(gè) go map 會(huì)怎么樣坛善？
試一下：
先來(lái)個(gè)主角 A
type A map[string]int
我們定義成了自己一個(gè)類型 A，他骨子里還是 map邻眷。
type A map[string]int
func main() {
// 初始化一個(gè) A
m := make(A)
m.SetMap("one", 1)
m.SetMap("two", 3)
// 讀取 one
go m.ReadMap("one")
// 設(shè)置 two 值為 2
go m.SetMap("two", 2)
time.Sleep(1*time.Second)
}
// A 有個(gè)讀取某個(gè) Key 的方法
func (a *A)ReadMap(key string) {
fmt.Printf("Get Key %s: %d",key, a[key])
}
// A 有個(gè)設(shè)置某個(gè) Key 的方法
func (a *A)SetMap(key string, value int) {
a[key] = value
fmt.Printf("Set Key %s: %d",key, a[key]) // 同協(xié)程的讀寫不會(huì)出問(wèn)題
}
誒眠屎，看上去不錯(cuò)，我們給 map A 類型定義了 get肆饶， set 方法改衩，如果 golang 不允許并發(fā)讀寫 map 的話，應(yīng)該會(huì)報(bào)錯(cuò)吧驯镊，我們跑一下葫督。
> Get Key one: 1
> Set Key two: 2
喵喵喵???
為什么正常輸出了竭鞍？
說(shuō)好的并發(fā)讀寫報(bào)錯(cuò)呢？
好吧候衍，其實(shí)原因是上面的 map 讀寫笼蛛，雖然我們?cè)O(shè)置了協(xié)程洒放，但是對(duì)于計(jì)算機(jī)來(lái)說(shuō)還是有時(shí)間差的蛉鹿。只要一個(gè)微小的先后，就不會(huì)造成 map 數(shù)據(jù)的讀寫異常往湿，所以我們改一下妖异。
func main() {
m := make(A)
m["one"] = 1
m["two"] = 3
go func() {
for {
m.ReadMap("one")
}
}()
go func(){
for {
m.SetMap("two", 2)
}
}()
time.Sleep(1*time.Second)
}
為了讓讀寫能夠盡可能碰撞，我們?cè)黾恿搜h(huán)领追。
現(xiàn)在我們可以看到了：
> fatal error: concurrent map read and map write
*這里之所以為有 panic 是因?yàn)樵?map 實(shí)現(xiàn)中進(jìn)行了并發(fā)讀寫的檢查他膳。
解決問(wèn)題
其實(shí)上面的例子和 go 對(duì) sync.Mutex 鎖的入門教程很像。
我們證實(shí)了 map 并發(fā)讀寫的問(wèn)題绒窑，現(xiàn)在我們嘗試來(lái)解決棕孙。
既然是讀寫造成的沖突，那我們首先考慮的便是加鎖些膨。
我們給讀取一個(gè)鎖蟀俊，寫入一個(gè)鎖。那么我們現(xiàn)在需要講單純的 A map 轉(zhuǎn)換成一個(gè)帶有鎖的結(jié)構(gòu)體：
type A struct {
Value map[string]int
mu sync.Mutex
}
Value 成了真正存放我們值的地方订雾。
我們還要修改下 ReadMap 和 SetMap 兩個(gè)方法肢预。
func (a *A)ReadMap(key string) {
a.mu.Lock()
fmt.Printf("Get Key %s: %d",key, a.Value[key])
a.mu.Unlock()
}
func (a *A)SetMap(key string, value int) {
a.mu.Lock()
a.Value[key] = value
a.mu.Unlock()
fmt.Printf("Set Key %s: %d",key, a.Value[key])
}
注意，這里兩個(gè)方法中洼哎，哪一個(gè)少了 Lock 和 Unlock 都不行烫映。
我們?cè)倥芤幌麓a，發(fā)現(xiàn)可以了噩峦，不會(huì)報(bào)錯(cuò)锭沟。
到此為止了嗎？
我們算是用最簡(jiǎn)單的方法解決了眼前的問(wèn)題识补，但是這樣真的沒(méi)問(wèn)題嗎族淮？
細(xì)心的你會(huì)發(fā)現(xiàn)，讀寫我們都加了鎖李请，而且沒(méi)有任何特殊條件限制瞧筛，所以當(dāng)我們要多次讀取 map 中的數(shù)據(jù)的時(shí)候，他喵的都會(huì)阻塞导盅！就算我壓根不想改 map 中的 value...
盡管現(xiàn)在感覺(jué)不出來(lái)慢较幌，但這對(duì)密集讀取來(lái)說(shuō)是一個(gè)性能坑。
為了避免不必要的鎖白翻，我們似乎還要讓代碼“聰明些”乍炉。
讀寫分離
沒(méi)錯(cuò)绢片，讀寫分離就是一個(gè)十分適用的設(shè)計(jì)思路。
我們準(zhǔn)備一個(gè) Read map岛琼，一個(gè) Write map底循。
但這里的讀寫分離和我們平時(shí)說(shuō)的不太一樣（記住我們的場(chǎng)景永遠(yuǎn)是并發(fā)讀寫），我們不能實(shí)時(shí)或者定時(shí)讓寫入的 map 去同步（增刪改）到讀取的 map 中槐瑞，
因?yàn)?..這樣和上面的 map 操作沒(méi)有任何區(qū)別熙涤，因?yàn)樽x取 map 沒(méi)有鎖，還是會(huì)發(fā)生并發(fā)沖突困檩。
我們要解決的是祠挫，不“顯示”增刪改 map 中的 key 對(duì)應(yīng)的 value。
我們把問(wèn)題再分類一下：
1. 修改（刪除）已有的 key 的 value
2. 增加不存在的 key 和 value
第一個(gè)問(wèn)題：我們把 key 的 value 變成指針怎么樣悼沿？
相同的 key 指向同一個(gè)指針地址等舔，指針地址又指向真正值的地址。
key -> &地址 -> &真正的值地址
Read 和 Write map 的值同時(shí)指向一個(gè)&地址糟趾，不論誰(shuí)改慌植，大家都會(huì)變。
當(dāng)我們需要修改已有的 key 對(duì)應(yīng)的 value 時(shí)义郑，我們修改的是&真正的值地址的值蝶柿，并不會(huì)修改 key 對(duì)應(yīng)的&地址或值。
同時(shí)魔慷，通過(guò)atomic包只锭，我們能夠做到對(duì)指針修改的原子性。
太棒了院尔，修改已有的 key 問(wèn)題解決蜻展。
第二個(gè)問(wèn)題：因?yàn)椴⒉淮嬖谶@個(gè) key，所以我們一定會(huì)增加新 key邀摆，
既然我們有了 Read map & Write map纵顾，那我們可以利用起來(lái)呀，
我們?cè)?Write map 中加鎖并增加這個(gè) key 和對(duì)應(yīng)的值栋盹，這樣不影響 Read map 的讀取施逾。
不過(guò)，Read map 我們終究是要更新的例获，所以我們加一個(gè)計(jì)數(shù)器 misses汉额，到了一定條件，我們把 Write map 安全地同步到 Read map 中榨汤，并且清空 Write map蠕搜。
Read map 可以看做是 Write map 的一個(gè)只讀拷貝，不允許自行增加新 key收壕，只能讀或者改妓灌。
上面的思想其實(shí)和 sync.Map 的實(shí)現(xiàn)離得很近了轨蛤。
只不過(guò)，sync.Map 把我們的 Write map 叫做了 dirty虫埂，把 Write map 同步到 Read map 叫做了 promote（升級(jí)）祥山。
又增加了一些結(jié)構(gòu)體封裝，和狀態(tài)標(biāo)識(shí)掉伏。
其實(shí) google 一下你就會(huì)發(fā)現(xiàn)很多分析 sync.Map 源碼的文章缝呕，都寫得很好。我這里也不贅述了岖免，但是我想用我的理解去概括下
sync.Map 中的方法思路岳颇。
結(jié)合 sync.Map 源碼食用味道更佳照捡。
讀取 Map.Load
1. Read map 直接讀得到嗎颅湘？
2. 么有？好吧栗精，我們上鎖闯参，再讀一次 Read map
3. 還沒(méi)有？那我只能去讀 Dirty map 了
4. 讀到了悲立，不錯(cuò)鹿寨，我們記錄下這次讀取屬于未命中（misses + 1），順便看看我們的 dirty 是不是可以升級(jí)成 Read 了
5. 解鎖
*這里2中之所以再上鎖薪夕，是為了double-checking脚草，防止在極小的時(shí)間差內(nèi)產(chǎn)生臟讀（dirty突然升級(jí) Read）。
寫入 Map.Store
1. Read map 有沒(méi)有這個(gè) key 原献？
2. 有馏慨，那我們?cè)硬僮髦苯有薷闹抵羔槅h
3. 沒(méi)有？依舊上鎖再看看有沒(méi)有姑隅？
4. 還沒(méi)有写隶，好吧，看看 Dirty map
5. 有誒讲仰！那就修改 Dirty map 這個(gè) key 的值指針
6. 沒(méi)有慕趴？那就要在 Dirty map 新增一個(gè) key 咯，為了方便之后 Dirty map 升級(jí)成 Read map鄙陡，我們還要把原先的 Read map 全復(fù)制過(guò)來(lái)
7. 解鎖
刪除 Map.Delete
1. Read map 有這個(gè) key 嗎冕房？
2. 有啊，那就把 value 直接改成 nil（防止之后讀取沒(méi)有 key 還要去加鎖趁矾，影響性能）
3. 沒(méi)有耙册？直接刪 dirty 里的這個(gè) key 吧
讀取或者存 Map.LoadOrStore
emmmm......
- Map.Load + Map.Store
編不下去了
大致就是這樣的思路，我這里再推薦一些正統(tǒng)的源碼分析和基準(zhǔn)測(cè)試愈魏，相信看完以后會(huì)對(duì) sync.Map 更加清晰觅玻。
另外想际，如果你注意到 Map.Store 中第6步的全部復(fù)制的話，你就會(huì)有預(yù)感溪厘，sync.Map 的使用場(chǎng)景其實(shí)不太適合高并發(fā)寫的邏輯胡本。
的確，官方說(shuō)明也明確指出了 sync.Map 適用的場(chǎng)景：
// Map is like a Go map[interface{}]interface{} but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
...
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.
sync.Map 只是幫助優(yōu)化了兩個(gè)使用場(chǎng)景：
1. 多讀少寫
2. 多 goroutine 操作鍵值
其實(shí) sync.Map 還是在性能和安全之間畸悬，找了一個(gè)自己覺(jué)得合適的平衡點(diǎn)侧甫，就如同我們開(kāi)頭的案例一樣，其實(shí) sync.Map 也并不適用蹋宦。
另外披粟，這里有一個(gè) 【sync.Map 的進(jìn)階版本】。
*atomic 和 mutex
其實(shí)在很久以前翻看 sync Map 源碼的時(shí)候冷冗，我不經(jīng)會(huì)拋出疑問(wèn)守屉，如果能夠用 atomic 來(lái)解決并發(fā)安全問(wèn)題，為什么還要 mutex 呢蒿辙？
而且拇泛，在進(jìn)行 map.Store 的過(guò)程中，還是會(huì)直接修改 read 的 key 所對(duì)應(yīng)的值（并且無(wú)鎖狀態(tài)）思灌，這和普通修改一個(gè) key 的值有什么區(qū)別呢俺叭？
如果 atomic 可以保證原子性，那和 mutex 有什么區(qū)別呢泰偿？
在翻查了一些資料后熄守，我知道了：
Mutexes are slow, due to the setup and teardown, and due to the fact that they block other goroutines for the duration of the lock.
Atomic operations are fast because they use an atomic CPU instruction, rather than relying on external locks to.
互斥鎖其實(shí)是通過(guò)阻塞其他協(xié)程起到了原子操作的功能，但是 atomic 是通過(guò)控制更底層的 CPU 指令耗跛，來(lái)達(dá)到值操作的原子性的裕照。
所以 atomic 和 mutex 并不是一個(gè)層面的東西，而且在專職點(diǎn)上也不盡相同课兄，mutex 很多地方也是通過(guò) atomic 去實(shí)現(xiàn)的牍氛。
而 sync Map 很巧妙地將兩個(gè)結(jié)合來(lái)實(shí)現(xiàn)并發(fā)安全。
1. 它用一個(gè)指針來(lái)存儲(chǔ) key 對(duì)應(yīng)的 value烟阐，當(dāng)要修改的時(shí)候只是修改 value 的地址（并且是地址值的副本操作）搬俊，這個(gè)可以通過(guò) atomic 的 Pointer 操作來(lái)實(shí)現(xiàn)，并且不會(huì)又沖突蜒茄。
2. 另外唉擂，又使用了讀寫分離+mutex互斥鎖，來(lái)控制 增刪改查 key 的操作檀葛，防止沖突玩祟。
其中第一點(diǎn)是很多源碼解讀中常常一筆帶過(guò)的，然而萌新我覺(jué)得反而是相當(dāng)重要的技巧（捂臉）屿聋。
*一些疑問(wèn)
misses 條件
一直沒(méi)有明白空扎，為什么從 dirty map 升級(jí)成 read map 的條件是
misses 次數(shù)大于等于 len(m.dirty)藏鹊？
Go map 為什么不加鎖？
我們可以看到下面兩篇關(guān)于不加鎖的敘述：
1. https://golang.org/doc/faq#atomic_maps
2. https://blog.golang.org/go-maps-in-action
