日常開發(fā)過程中，map結(jié)構(gòu)應(yīng)該登場率是較為頻繁的。但是Go的內(nèi)建map類型并不是協(xié)程安全的办桨。如下面這個栗子搭综，如果業(yè)務(wù)開發(fā)過程中不注意很容易中招垢箕。
func main() {
m := make(map[int]int)
go func() {
for {
m[0] = 1
}
}()
go func() {
for {
if v, ok := m[0]; ok {
fmt.Println(v)
}
}
}()
ch := make(chan os.Signal)
signal.Notify(ch, os.Interrupt)
<-ch
}
聲明一個map[int]int用兩個協(xié)程去同時操作一個key，得到panic
fatal error: concurrent map read and map write
為了解決這種問題兑巾，我們有幾個選擇
- 使用
Go1.9在sync包下引入了并發(fā)安全的map条获。sync.Map功能上跟map[interface{}]interface{}很像，但是sync.Map是協(xié)程安全的闪朱，并通過讀寫分離的機制月匣，降低鎖的粒度，提高并發(fā)性能奋姿。 - 使用第三方的類庫
concurrent-map(https://github.com/orcaman/concurrent-map)
今天我們先來聊聊sync.Map,本文基于go1.15.7
基本使用
讓我們用sync.Map來改寫上面的栗子
func main() {
m := sync.Map{}
go func() {
for {
m.Store(0, 1)
}
}()
go func() {
for {
if v, ok := m.Load(0); ok {
fmt.Println(v)
}
}
}()
ch := make(chan os.Signal)
signal.Notify(ch, os.Interrupt)
<-ch
}
另外,sync.Map還支持Range锄开、Delete方法
m.Range(func(key, value interface{}) bool {
fmt.Println(key, value)
return true
})
m.Delete(0)
sync.Map源碼分析
數(shù)據(jù)結(jié)構(gòu)
先看下sync.Map的數(shù)據(jù)結(jié)構(gòu)
type Map struct {
mu Mutex
// 持有部分map的數(shù)據(jù)并且并發(fā)讀不需要持有鎖，但是改變指針需要持有鎖
read atomic.Value // readOnly
// 包含部分map數(shù)據(jù)需要持有鎖保護 為了保證dirty map能夠快速晉升為read map称诗，
// 它還包含所有在read map未清除的數(shù)據(jù)
// expunged數(shù)據(jù)不會存儲在dirty map
// 如果dirtymap為nil則下一次寫會從read map拷貝一份數(shù)據(jù)
dirty map[interface{}]*entry
// 記錄從read map中讀不到數(shù)據(jù)萍悴，加鎖去判斷key是否存在的次數(shù)
// 當(dāng)misses等于dirty map長度時，dirty map會直接晉升為read map
// 下次寫操作再從read map拷貝一份數(shù)據(jù)
misses int
}
sync.Map中的 read實際指向的是readOnly結(jié)構(gòu)體對象
// readOnly 是一個不可變結(jié)構(gòu)體 自動存儲在Map.read字段中
type readOnly struct {
m map[interface{}]*entry
amended bool // 如果key在dirty不在m中 則為true如果為false則表示dirty為空
}
// map中的key 指向的value
type entry struct {
// p指向interface{}類型的值
// 如果p==nil寓免，表明entry已經(jīng)被刪除并且m.dirty==nil
// 如果p==expunged癣诱，表明entry已經(jīng)被刪除且m.dirty!=nil 并且entry不在m.dirty中
// 否則entry是有效的并且記錄m.read.m[key] 并且如果m.dirty!=nil 則也存在m.dirty[key]
// 當(dāng)m.dirty重建的時候被刪除的entry會被檢測到并自動由nil替換為expunged 并且不會設(shè)置m.dirty[key]
// 若p!=expunged，則entry關(guān)聯(lián)的值可以通過原子替換來更新
// 若p==expunged袜香，則需要先設(shè)置m.dirty[key]=e之后才能更新entry關(guān)聯(lián)的值撕予，這樣以便使用dirty map查找值
p unsafe.Pointer // *interface{}
}
操作方法
Load操作
Load操作返回存儲在map中指定key的value，有兩個返回值蜈首，ok表示key對應(yīng)的value是否存在实抡。
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended {
m.mu.Lock()
// double-check 避免我們獲得鎖期間 ditry map已經(jīng)晉升為了read map
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {//不存在 且map.dirty包含了部分不在read map中的數(shù)據(jù)
e, ok = m.dirty[key]
//記錄miss 當(dāng)前這個key會一直執(zhí)行slow path直到dirty map晉升為read map
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
因為sync.Map設(shè)計了一個read map和一個dirty map。他倆的區(qū)別在于
-
read map指向了readOnly結(jié)構(gòu)體對象欢策，readOnly結(jié)構(gòu)體本身是只讀的 但是read map指向的引用是可變的 -
dirty map是一個結(jié)構(gòu)為map[interface{}]*entry的內(nèi)建map類型
讓他倆之間產(chǎn)生關(guān)聯(lián)的是sync.Map 中的misses字段吆寨。為什么呢？讓我們看看Load的具體過程：
- 首先從
read map中嘗試讀取數(shù)據(jù)踩寇，若read map中不存在且read.amended為true(注釋：當(dāng)存在數(shù)據(jù)存在dirty map但不在read map中時read.amended為true)則嘗試獲得鎖 - 獲得鎖后啄清，并沒有直接從
dirty map中拿數(shù)據(jù)，而是進行了double-check俺孙，再次從read map中嘗試獲取數(shù)據(jù)辣卒，為何要這么做呢掷贾？我們接著看。 -
double-check之后發(fā)現(xiàn)還是沒有拿到數(shù)據(jù)添寺，那么此時就從dirty map中獲取胯盯，然后執(zhí)行missLocked()這個方法很關(guān)鍵，我們來看看它的實現(xiàn)
func (m *Map) missLocked() {
m.misses++
if m.misses < len(m.dirty) {
return
}
m.read.Store(readOnly{m: m.dirty})
m.dirty = nil
m.misses = 0
}
missLocked()方法首先針對m.misses++遞增操作（這里已獲得鎖计露，協(xié)程安全）博脑，這里也印證了misses字段的含義：記錄從read map中讀不到數(shù)據(jù)，加鎖去判斷key是否存在的次數(shù)票罐。接著是重頭戲
如果m.misses小于m.dirty的長度直接返回叉趣，但是如果大于或者等于，則會將m.dirty的引用包裝成readOnly結(jié)構(gòu)并更新給read map并將m.dirty置為nil该押，m.misses置為0疗杉。(注意：這里read.amended為false時，m.dirty為nil 事實也是這樣)
到這里你應(yīng)該能理清楚蚕礼，read map烟具、dirty map以及misses之間的關(guān)系：
所以剛剛的double-check就很好理解了，因為第一次從read map查找數(shù)據(jù)到加鎖成功之間奠蹬，有可能dirty map已經(jīng)完成了read map 的晉升過程朝聋。
-
Load()的最后一步，查找數(shù)據(jù)囤躁，則調(diào)用entry.load()獲取數(shù)據(jù)冀痕。
func (e *entry) load() (value interface{}, ok bool) {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return nil, false
}
return *(*interface{})(p), true
}
Store操作
Store()操作在key存在并且value不處于expunged狀態(tài)下會覆蓋原有的值
// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
// 情況1
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {//情況2
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}
e.storeLocked(&value) // 情況3 e.unexpungeLocked()為false的情況
} else if e, ok := m.dirty[key]; ok {//情況4
e.storeLocked(&value)
} else {//情況5
if !read.amended {
// We're adding the first new key to the dirty map.
// Make sure it is allocated and mark the read-only map as incomplete.
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}
源碼面前無秘密，Store()操作大概會存在5種情況：
- 如果key已經(jīng)在
read map存在了 且dirty map中未被刪除
通過調(diào)用e.tryStore(&value)直接無鎖情況下,更新對應(yīng)值狸演。前提是對應(yīng)值 非expunged
func (e *entry) tryStore(i *interface{}) bool {
for {
p := atomic.LoadPointer(&e.p)
if p == expunged { //表示dirty map已刪除對應(yīng)值 返回false 讓其更新完dirty map 再更新read map
return false
}
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {// 直接更新值
return true
}
}
}
- 如果key存在于
read map言蛇，不在dirty map中
先將key-value放到dirty map中艰争，然后直接更新value教硫，因為read map和dirty map持有的是相同的引用 故而一改全改
- 如果key同時存在于
read map和dirty map
這個情況跟情況一類似抬吟，這個邏輯的原因是我們加鎖過程中可能數(shù)據(jù)已經(jīng)被加回dirty map算柳，則直接更新read map的值即可 原因見情況2
- 如果key不在
read map但存在于dirty map
這種情況直接更新即可，因為已經(jīng)拿到鎖了 所以是協(xié)程安全的
- 如果key不在
read map也不存在于dirty map
首先判斷read.amended若為false 則表明dirty map剛剛晉升為read map,此時dirty map為nil雳攘。然后調(diào)用m.dirtyLocked()
func (m *Map) dirtyLocked() {
if m.dirty != nil { //不為nil 直接返回
return
}
read, _ := m.read.Load().(readOnly)
m.dirty = make(map[interface{}]*entry, len(read.m))
for k, e := range read.m {
if !e.tryExpungeLocked() { //刪除則跳過復(fù)制
m.dirty[k] = e //從read map拷貝一份數(shù)據(jù)引用給到dirty map
}
}
}
// 判斷read map中的數(shù)據(jù)是否為nil 若是 則將其更新為expunged
// 同時數(shù)據(jù)也不會copy到dirty map耻姥，所以expunged表明數(shù)據(jù)已經(jīng)從dirty map移除了
func (e *entry) tryExpungeLocked() (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}
將read map中的數(shù)據(jù)引用拷貝一份后秧了，針對新來的數(shù)據(jù) m.dirty[key] = newEntry(value)新建并插入
LoadOrStore操作
LoadOrStore顧名思義翩瓜，如果值存在則直接返回受扳，若不存在則存儲携龟，返回值loaded兔跌，true表示數(shù)據(jù)被加載，false表示數(shù)據(jù)被存儲
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
// Avoid locking if it's a clean hit.
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
actual, loaded, ok := e.tryLoadOrStore(value)
if ok {
return actual, loaded
}
}
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {
m.dirty[key] = e
}
actual, loaded, _ = e.tryLoadOrStore(value)
} else if e, ok := m.dirty[key]; ok {
actual, loaded, _ = e.tryLoadOrStore(value)
m.missLocked()
} else {
if !read.amended {
// We're adding the first new key to the dirty map.
// Make sure it is allocated and mark the read-only map as incomplete.
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
actual, loaded = value, false
}
m.mu.Unlock()
return actual, loaded
}
大體邏輯跟Store差不了太多峡蟋，我們主要關(guān)注下tryLoadOrStore
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
p := atomic.LoadPointer(&e.p)
if p == expunged {
return nil, false, false
}
if p != nil {
return *(*interface{})(p), true, true
}
// p==nil
ic := i
for {
if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
return i, false, true
}
p = atomic.LoadPointer(&e.p)
if p == expunged {//刪除直接返回
return nil, false, false
}
if p != nil { // 有值了 返回值
return *(*interface{})(p), true, true
}
}
}
如果entry不是expunged 則自動加載或存儲值, 如果entry為expunged 則直接返回 并且loaded和ok為false
Range操作
Range()要求一個函數(shù)f func(key, value interface{}) bool作為入?yún)⒎匚Γ瑢ap中的key-value依次調(diào)用這個函數(shù)华望。如果函數(shù)返回false，則Range停止迭代仅乓。需要注意的是：Range使用的快照赖舟，并發(fā)插入的情況下不一定準(zhǔn)確。
func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := m.read.Load().(readOnly)
if read.amended {//如果dirty map中存在read map中沒有的值 則先晉升下
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if read.amended {
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}
//依次迭代
for k, e := range read.m {
v, ok := e.load()
if !ok {
continue
}
if !f(k, v) {
break
}
}
}
邏輯比較簡單：如果當(dāng)前dirty map中存在read map中沒有的值 則先將dirty map晉升為read map夸楣，然后再依次迭代調(diào)用傳入的函數(shù) 宾抓，返回false時中斷。
Delete操作
刪除指定key的value豫喧。
func (m *Map) Delete(key interface{}) {
m.LoadAndDelete(key)
}
// 刪除key對應(yīng)的value 并返回之前的值 loaded表示key是否存在
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended {
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
delete(m.dirty, key)
// 遞增misses 找準(zhǔn)時機晉升dirty map
m.missLocked()
}
m.mu.Unlock()
}
if ok {
return e.delete()
}
return nil, false//key不存在
}
刪除分3中情況：
- key存在于
read map則直接調(diào)用e.delete()將其置為nil 為了減少鎖的開銷提供并發(fā)性能石洗，使用了個小技巧延遲刪除，
即這種情況下并沒有直接物理刪除紧显，而是通過CAS將entry.p指針置為nil讲衫。
- key不在
read map但存在于dirty map，則直接調(diào)用內(nèi)建delete方法從map中刪除元素 - key都不存在 直接返回
至此孵班，全部操作都解析完畢涉兽，你可能對entry延遲刪除的狀態(tài)有點兒懵 沒關(guān)系 上圖
expunged算是一個標(biāo)記，表示dirty map中對應(yīng)的值已經(jīng)被干掉了篙程。
需要注意的是 最好不要用占用內(nèi)存比較大的類型作為key枷畏，因為sync.Map軟刪除并不會立刻將key-value刪除掉，只是value置為了nil房午，所以大key有內(nèi)存泄露的危險矿辽。
但是話說回來 應(yīng)該沒人這么干吧？
我看還有人專門討論了一下(https://github.com/golang/go/issues/40999) 可以圍觀下
總結(jié)
整個源碼看下來郭厌，不難發(fā)現(xiàn)袋倔，對于高頻讀寫少的情況下，sync.Map基本時無鎖情況下完成折柠。但是對于寫操作比較頻繁的情況下宾娜，如果read map中拿不到數(shù)據(jù)，就會降級為加鎖獲取扇售，然后misses增長變化速度勢必比較快前塔，連鎖反應(yīng)dirty map晉升為read map的操作也會比較頻繁，其性能也勢必會下降承冰。所以寫頻繁的場景下sync.Map還是不太夠看华弓。
