Go語(yǔ)言sync.Map實(shí)現(xiàn)
Go語(yǔ)言sync.Map實(shí)現(xiàn)
Go語(yǔ)言原生map并不是線(xiàn)程安全的，對(duì)它進(jìn)行并發(fā)讀寫(xiě)操作的時(shí)候，需要加鎖。
而sync.map則是一種并發(fā)安全的map，在Go1.9引入。
?
sync.map是線(xiàn)程安全的，讀取，插入，刪除也都保持著常數(shù)級(jí)的時(shí)間復(fù)雜度。
sync.map的零值是有效的，并且零值是一個(gè)空的map。在第一次使用之后，不允許被拷貝。
?
一般情況下解決并發(fā)讀寫(xiě)map的思路是加一把大鎖，或者把一個(gè)map分成若干個(gè)小map，對(duì)key進(jìn)行哈希，只操作相應(yīng)的小map。前者鎖的粒度比較大，影響效率；后者實(shí)現(xiàn)起來(lái)比較復(fù)雜，容易出錯(cuò)。
?
而使用sync.map之后，對(duì)map的讀寫(xiě)，不需要加鎖。并且它通過(guò)空間換時(shí)間的方式，使用read和dirty兩個(gè)map來(lái)進(jìn)行讀寫(xiě)分離，降低鎖時(shí)間來(lái)提高效率。
數(shù)據(jù)結(jié)構(gòu)：
互斥量mu保護(hù)read和dirty。
?
read是atomic.Value類(lèi)型，可以并發(fā)地讀。但如果需要更新read，則需要加鎖保護(hù)。對(duì)于read中存儲(chǔ)的entry字段，可能會(huì)被并發(fā)地CAS更新。但是如果要更新一個(gè)之前已被刪除的entry，則需要先將其狀態(tài)從expunged改為nil，再拷貝到dirty中，然后再更新。
dirty是一個(gè)非線(xiàn)程安全的原始map。包含新寫(xiě)入的key，并且包含read中的所有未被刪除的key。這樣，可以快速地將dirty提升為read對(duì)外提供服務(wù)。如果dirty為nil，那么下一次寫(xiě)入時(shí)，會(huì)新建一個(gè)新的dirty，這個(gè)初始的dirty是read的一個(gè)拷貝，但除掉了其中已被刪除的key。
?
每當(dāng)從read中讀取失敗，都會(huì)將misses的計(jì)數(shù)值加1，當(dāng)加到一定閾值以后，需要將dirty提升為read，以期減少miss的情形。
?
readmap和dirtymap的存儲(chǔ)方式是不一致的。
前者使用atomic.Value，后者只是單純的使用map。
原因是readmap使用lockfree操作，必須保證load/store的原子性；而dirtymap的load+store操作是由lock（就是mu）來(lái)保護(hù)的。
它是一個(gè)指針，指向value。
read和dirty各自維護(hù)一套key，key指向的都是同一個(gè)value。也就是說(shuō)，只要修改了這個(gè)entry，對(duì)read和dirty都是可見(jiàn)的。這個(gè)指針的狀態(tài)有三種：
當(dāng)p==nil時(shí)，說(shuō)明這個(gè)鍵值對(duì)已被刪除，并且m.dirty==nil，或m.dirty[k]指向該entry。
?
當(dāng)p==expunged時(shí)，說(shuō)明這條鍵值對(duì)已被刪除，并且m.dirty!=nil，且m.dirty中沒(méi)有這個(gè)key。
?
其他情況，p指向一個(gè)正常的值，表示實(shí)際interface{}的地址，并且被記錄在m.read.m[key]中。如果這時(shí)m.dirty不為nil，那么它也被記錄在m.dirty[key]中。兩者實(shí)際上指向的是同一個(gè)值。
?
當(dāng)刪除key時(shí)，并不實(shí)際刪除。一個(gè)entry可以通過(guò)原子地（CAS操作）設(shè)置p為nil被刪除。如果之后創(chuàng)建m.dirty，nil又會(huì)被原子地設(shè)置為expunged，且不會(huì)拷貝到dirty中。
?
如果p不為expunged，和entry相關(guān)聯(lián)的這個(gè)value可以被原子地更新；如果p==expunged，那么僅當(dāng)它初次被設(shè)置到m.dirty之后，才可以被更新。
expunged：varexpunged=unsafe.Pointer(new(interface{}))
它是一個(gè)指向任意類(lèi)型的指針，用來(lái)標(biāo)記從dirtymap中刪除的entry。
?
Store流程：
①read中未找到待存儲(chǔ)的key，且p!=expunged→未被刪除，直接更新對(duì)應(yīng)的entry。
?
②若①未成功：要么read中不存在這個(gè)key，要么key被標(biāo)記為刪除。則先加鎖，再操作。
?
③再在read中查找key，doublecheck一下。
A.存在key，p==expunged，說(shuō)明m.dirty!=nil且m.dirty中不存在該key值。此時(shí):
a.?將p的狀態(tài)由expunged更改為nil；
b.?dirtymap插入key。然后，直接更新對(duì)應(yīng)的value。
B.不存在key，查看dirty中是否有此key，如果有，則直接更新對(duì)應(yīng)的value，這時(shí)read中還是沒(méi)有此key。
?
④如果read和dirty中都不存在該key，則：
a.?如果dirty為空，則需要?jiǎng)?chuàng)建dirty，并從read中拷貝未被刪除的元素；
b.?更新amended字段，標(biāo)識(shí)dirtymap中存在readmap中沒(méi)有的key；
c.?將k-v寫(xiě)入dirtymap中，read.m不變。最后，更新此key對(duì)應(yīng)的value。
?
tryStore在Store函數(shù)最開(kāi)始的時(shí)候就會(huì)調(diào)用，是比較常見(jiàn)的for循環(huán)加CAS操作，嘗試更新entry，讓p指向新的值。
unexpungeLocked函數(shù)確保了entry沒(méi)有被標(biāo)記成已被清除。
?
Load：
處理路徑分為fastpath和slowpath，整體流程如下：
①首先是fastpath，直接在read中找，如果找到了直接調(diào)用entry的load方法，取出其中的值。
②如果read中沒(méi)有這個(gè)key，且amended為fase，說(shuō)明dirty為空，那直接返回空和false。
③如果read中沒(méi)有這個(gè)key，且amended為true，說(shuō)明dirty中可能存在我們要找的key。當(dāng)然要先上鎖，再?lài)L試去dirty中查找。在這之前，仍然有一個(gè)doublecheck的操作。若還是沒(méi)有在read中找到，那么就從dirty中找。不管dirty中有沒(méi)有找到，都要"記一筆"，因?yàn)樵赿irty被提升為read之前，都會(huì)進(jìn)入這條路徑。
?
Delete：
先從read里查是否有這個(gè)key，如果有則執(zhí)行entry.delete方法，將p置為nil，這樣read和dirty都能看到這個(gè)變化。
如果沒(méi)在read中找到這個(gè)key，并且dirty不為空，那么就要操作dirty了，操作之前，還是要先上鎖。然后進(jìn)行doublecheck，如果仍然沒(méi)有在read里找到此key，則從dirty中刪掉這個(gè)key。但不是真正地從dirty中刪除，而是更新entry的狀態(tài)。
?
tryExpungeLocked是在新創(chuàng)建dirty時(shí)調(diào)用的，會(huì)將已被刪除的entry.p從nil改成expunged，這個(gè)entry就不會(huì)寫(xiě)入dirty了。
注意到如果key同時(shí)存在于read和dirty中時(shí)，刪除只是做了一個(gè)標(biāo)記，將p置為nil；而如果僅在dirty中含有這個(gè)key時(shí)，會(huì)直接刪除這個(gè)key。原因在于，若兩者都存在這個(gè)key，僅做標(biāo)記刪除，可以在下次查找這個(gè)key時(shí)，命中read，提升效率。若只有在dirty中存在時(shí)，read起不到“緩存”的作用，直接刪除。
?
LoadOrStore
這個(gè)函數(shù)結(jié)合了Load和Store的功能，如果map中存在這個(gè)key，那么返回這個(gè)key對(duì)應(yīng)的value；否則，將key-value存入map。這在需要先執(zhí)行Load查看某個(gè)key是否存在，之后再更新此key對(duì)應(yīng)的value時(shí)很有效，因?yàn)長(zhǎng)oadOrStore可以并發(fā)執(zhí)行。
?
Range：
Range將遍歷調(diào)用時(shí)刻map中的所有k-v對(duì)，將它們傳給f函數(shù)，如果f返回false，將停止遍歷。
當(dāng)amended為true時(shí)，說(shuō)明dirty中含有read中沒(méi)有的key，因?yàn)镽ange會(huì)遍歷所有的key，是一個(gè)O(n)操作。將dirty提升為read，會(huì)將開(kāi)銷(xiāo)分?jǐn)傞_(kāi)來(lái)，所以這里直接就提升了。
之后，遍歷read，取出entry中的值，調(diào)用f(k,v)。
?
總結(jié)
除了Load/Store/Delete之外，sync.Map還提供了LoadOrStore/Range操作，但沒(méi)有提供Len()方法，這是因?yàn)橐y(tǒng)計(jì)有效的鍵值對(duì)只能先提升dirtymap(dirtymap中可能有readmap中沒(méi)有的鍵值對(duì))，再遍歷m.read(由于延遲刪除，不是所有的鍵值對(duì)都有效)，這其實(shí)就是Range做的事情，因此在不添加新數(shù)據(jù)結(jié)構(gòu)支持的情況下，sync.Map的長(zhǎng)度獲取和Range操作是同一復(fù)雜度的。這部分只能看官方后續(xù)支持。
?
sync.Map實(shí)現(xiàn)上并不是特別復(fù)雜，但仍有很多值得借鑒的地方:
①通過(guò)entry隔離map變更和value變更，并且readmap和dirtymap指向同一個(gè)entry,這樣更新readmap已有值無(wú)需加鎖
②doublechecking
③延遲刪除key，通過(guò)標(biāo)記避免修改readmap，同時(shí)極大提升了刪除key的效率(刪除readmap中存在的key是無(wú)鎖操作)
④延遲創(chuàng)建dirtymap，并且通過(guò)p的nil和expunged，amended字段來(lái)加強(qiáng)對(duì)dirtymap狀態(tài)的把控，減少對(duì)dirtymap不必要的使用。
?
?
