深入了解Go語言(05)：sync.map原理分析

一、疑惑開篇

有了map為什麼還要搞個sync.map 呢？它們之間有什麼差別？

答：重要的一點是，map并發不是安全的。

在Go 1.6之前，内置的map類型是部分goroutine安全的，并發的讀沒有問題，并發的寫可能有問題。自go 1.6之後，并發地讀寫map會報錯，這在一些知名的開源庫中都存在這個問題，是以go 1.9之前的解決方案是額外綁定一個鎖，封裝成一個新的struct或者單獨使用鎖都可以。

go version go1.13.9 windows/amd64

測試一波

寫一個簡單的并發寫map的測試代碼看看：

testcurmap.go

package main

import (
	"fmt"
	"time"
)

func main() {
	m := map[string]int{"age": 10}

	go func() {
		i := 0
		for i < 1000 {
			m["age"] = 10
			i++
		}
	}()

	go func() { //19 行
		i := 0
		for i < 1000 {
			m["age"] = 11 //22 行
			i++
		}
	}()

	time.Sleep(time.Second * 3)
	fmt.Println(m)
}

多運作幾次：go run testcurmap.go

會報錯，錯誤的扼要資訊如下：

fatal error: concurrent map writes

goroutine 7 [running]:

runtime.throw(0x4d49a3, 0x15)

       /go/src/runtime/panic.go:774 +0x79 fp=0xc000041f30 sp=0xc000041f00 pc=0x42cf19

runtime.mapassign_faststr(0x4b4360, 0xc000066330, 0x4d168a, 0x3, 0x0)

        /go/src/runtime/map_faststr.go:211 +0x41e fp=0xc000041f98 sp=0xc000041f30 pc=0x410f8e

main.main.func2(0xc000066330)

        /mygo/src/study/go-practice2/map/curmap/testcurmap.go:22 +0x5c fp=0xc000041fd8 sp=0xc000041f98 pc=0x49ac9c

runtime.goexit()

      /go/src/runtime/asm_amd64.s:1357 +0x1 fp=0xc000041fe0 sp=0xc000041fd8 pc=0x455391

created by main.main

       /mygo/src/study/go-practice2/map/curmap/testcurmap.go:19 +0xb0

exit status 2

看報錯資訊是src/runtime/map_faststr.go:211 這個函數runtime.mapassign_faststr，它在runtime/map_faststr.go 中，簡要代碼如下：

func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {
   ... ...
   
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
    
    ... ...
}

hashWriting = 4 // a goroutine is writing to the map goroutine寫的一個辨別，

這裡h.flags與自己進行與運算，判斷是否有其他goroutine在操作這個map，不是0說明有其他goroutine操作map，是以報錯。

那咋防止map并發呢，一般有幾種方式：

map+Mutex：

給map加一把大鎖
map+RWMutex

給map加一個讀寫鎖，給鎖細分。适合讀多寫少場景

修改一下程式

加一把讀寫鎖防止并發，修改程式 testcurmap2.go：

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	m := map[string]int{"age": 10}

	var s sync.RWMutex
	go func() {
		i := 0
		for i < 1000 {
			s.Lock()
			m["age"] = 10
			s.Unlock()
			i++
		}
	}()

	go func() {
		i := 0
		for i < 1000 {
			s.Lock()
			m["age"] = 11
			s.Unlock()
			i++
		}
	}()

	time.Sleep(time.Second * 3)
	fmt.Println(m)
}

運作結果：

map[age:11]

沒有報錯了。

就到這裡了嗎？可以在思考思考，還有其他方法控制并發的方法沒？有的，sync.map 登場

控制并的第三種方式：

sync.Map

官方實作的并發map。

原理是通過分離讀寫map和原子指令來實作讀的近似無鎖，并通過延遲更新的方式來保證讀的無鎖化。一般情況下可以替換上面2種鎖。

二、sync.map

先看一個簡單的代碼 testcurmap3.go

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	smap := sync.Map{}

	smap.Store("age", 10)

	go func() {
		i := 0
		for i < 1000 {
			smap.Store("one", 10)
			i++
		}
	}()

	go func() {
		i := 0
		for i < 1000 {
			smap.Store("one", 11)
			i++
		}
	}()

	time.Sleep(time.Second * 2)
	fmt.Println(smap.Load("one"))
}

運作輸出：11 true

正常輸出，沒有報錯。

sync.Map 的主要思想就是讀寫分離，空間換時間。

看看 sync.map 優點：

空間換時間：通過備援的兩個資料結構(read、dirty)，實作加鎖對性能的影響。
使用隻讀資料(read)，避免讀寫沖突。
動态調整，miss次數多了之後，将dirty資料遷移到read中。
double-checking。
延遲删除。删除一個鍵值隻是打标記，隻有在遷移dirty資料的時候才清理删除的資料。
優先從read讀取、更新、删除，因為對read的讀取不需要鎖。

sync.Map 資料結構

Map 資料結構

在 src/sync/map.go 中

type Map struct {
    // 當涉及到髒資料(dirty)操作時候，需要使用這個鎖
    mu Mutex
    
    // read是一個隻讀資料結構，包含一個map結構，
    // 讀不需要加鎖，隻需要通過 atomic 加載最新的指正即可
    read atomic.Value // readOnly
    
    // dirty 包含部分map的鍵值對，如果操作需要mutex擷取鎖
    // 最後dirty中的元素會被全部提升到read裡的map去
    dirty map[interface{}]*entry
    
    // misses是一個計數器，用于記錄read中沒有的資料而在dirty中有的資料的數量。
    // 也就是說如果read不包含這個資料，會從dirty中讀取，并misses+1
    // 當misses的數量等于dirty的長度，就會将dirty中的資料遷移到read中
    misses int
}

read的資料結構 readOnly：

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m包含所有隻讀資料，不會進行任何的資料增加和删除操作 
    // 但是可以修改entry的指針因為這個不會導緻map的元素移動
    m       map[interface{}]*entry
    
    // 标志位，如果為true則表明目前read隻讀map的資料不完整，dirty map中包含部分資料
    amended bool // true if the dirty map contains some key not in m.
}

隻讀map，對該map的通路不需要加鎖，但是這個map也不會增加元素，元素會被先增加到dirty中，然後後續會遷移到read隻讀map中，通過原子操作是以不需要加鎖操作。

entry

readOnly.m和Map.dirty存儲的值類型是*entry,它包含一個指針p, 指向使用者存儲的value值，結構如下：

type entry struct {
    p unsafe.Pointer // *interface{}
}

p有三種值：

nil: entry已被删除了，并且m.dirty為nil
expunged: entry已被删除了，并且m.dirty不為nil，而且這個entry不存在于m.dirty中
其它： entry是一個正常的值

三、查找

根據key來查找 value，函數為 Load()，源碼如下：

// src/sync/map.go

// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先從隻讀ready的map中查找，這時不需要加鎖
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    // 如果沒有找到，并且read.amended為true，說明dirty中有新資料，從dirty中查找，開始加鎖了
    if !ok && read.amended {
        m.mu.Lock() // 加鎖
        
       // 又在 readonly 中檢查一遍，因為在加鎖的時候 dirty 的資料可能已經遷移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        // read 還沒有找到，并且dirty中有資料
        if !ok && read.amended {
            e, ok = m.dirty[key] //從 dirty 中查找資料
            
            // 不管m.dirty中存不存在，都将misses + 1
            // missLocked() 中滿足條件後就會把m.dirty中資料遷移到m.read中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

從函數可以看出，如果查詢的鍵值正好在m.read中，不需要加鎖，直接傳回結果，優化了性能。

即使不在read中，經過幾次miss後， m.dirty中的資料也會遷移到m.read中，這時又可以從read中查找。

是以對于更新／增加較少，加載存在的key很多的case，性能基本和無鎖的map類似。

missLockerd() 遷移資料：

// src/sync/map.go

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {//misses次數小于 dirty的長度，就不遷移資料，直接傳回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //開始遷移資料
    m.dirty = nil   //遷移完dirty就指派為nil
    m.misses = 0  //遷移完 misses歸0
}

四、新增和更新

方法是 Store()，更新或者新增一個 entry，源碼如下：

// src/sync/map.go

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在read中查找值，找到了，就嘗試 tryStore() 更新值
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() { // 未被标記成删除，前面講到entry資料結構時，裡面的p值有3種。1.nil 2.expunged，這個值含義有點複雜，可以看看前面entry資料結構 3.正常值
            
            m.dirty[key] = e // 加入到dirty裡
        }
        e.storeLocked(&value) // 更新值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中，直接更新
        e.storeLocked(&value)
    } else { // 新的值
        if !read.amended { // m.dirty 中沒有新資料，增加到 m.dirty 中
            // 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中複制未删除的資料
            m.read.Store(readOnly{m: read.m, amended: true}) 
        }
        m.dirty[key] = newEntry(value) //将這個entry加入到m.dirty中
    }
    m.mu.Unlock()
}

操作都是先從m.read開始，不滿足條件再加鎖，然後操作m.dirty。

五、删除

根據key删除一個值：

// src/sync/map.go

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
    // 從 m.read 中開始查找
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    if !ok && read.amended { // m.read中沒有找到，并且可能存在于m.dirty中，加鎖查找
        m.mu.Lock() // 加鎖
        read, _ = m.read.Load().(readOnly) // 再在m.read中查找一次
        e, ok = read.m[key]
        if !ok && read.amended { //m.read中又沒找到，amended标志位true，說明在m.dirty中
            delete(m.dirty, key) // 删除
        }
        m.mu.Unlock()
    }
    if ok { // 在 m.ready 中就直接删除
        e.delete()
    }
}

還有更好的方法沒？java裡面有一個分段鎖，保證在操作不同 map 段的時候，可以并發執行，操作同段 map 的時候，進行鎖的競争和等待。進而達到線程安全，且效率大于 synchronized。而不是直接加一把大鎖，鎖住整個map。

那go裡面有木有？有人已經想到了

六、concurrent-map

項目位址：concurrent-map

中文wiki：位址

正如這裡和這裡所描述的, Go語言原生的map類型并不支援并發讀寫。concurrent-map提供了一種高性能的解決方案:通過對内部map進行分片，降低鎖粒度，進而達到最少的鎖等待時間(鎖沖突)。

在Go 1.9之前，go語言标準庫中并沒有實作并發map。在Go 1.9中，引入了sync.Map。新的sync.Map與此concurrent-map有幾個關鍵差別。标準庫中的sync.Map是專為append-only場景設計的。是以，如果您想将Map用于一個類似記憶體資料庫，那麼使用我們的版本可能會受益。你可以在golang repo上讀到更多，這裡 and 這裡

譯注: sync.Map在讀多寫少性能比較好，否則并發性能很差

有興趣的可以自己研究下。

七、參考：

Go 1.9 sync.Map揭秘
go sync.Map使用和介紹
golang sync.map源碼

== just do it ==

深入了解Go語言(05)：sync.map原理分析

一、疑惑開篇

測試一波

修改一下程式

二、sync.map

sync.Map 資料結構

Map 資料結構

read的資料結構 readOnly：

entry

三、查找

四、新增和更新

五、删除

六、concurrent-map

七、參考：

繼續閱讀

Golang學習——結構體struct(二)一.匿名結構體和匿名字段二.結構體嵌套三.結構體模拟繼承性

golang 學習（二十四）結構體struct 和 json之間的轉換結構體struct 和 json之間的轉換

golang中結構體與jsongolang中結構體與json

golang結構體tag編譯錯誤的問題

Golang結構體中的tag

GO語言筆記--結構體1.說明2.工廠函數

Go語言之map與結構體初入map結構體初入（場景map的value通常為struct）

Go初探 (5) – 結構體與接口

go(7)結構體，方法，接口

Go學習筆記: 結構體、方法、接口

06結構體、接口結構體接口

go語言筆記（結構體、方法、接口）go語言筆記（結構體、方法、接口）

Go中結構體和接口的定義

Rich Domain Model

Linux之父警告全球程式員：我剛釋出的5.12核心有bug，你們千萬别用

php的運作模式