版本
- go version 1.10.1
使用方法
var m sync.map
value,ok:=m.Load(key)
m.Store(key,value)
value,loaded,ok := m.LoadOrStore(key,value)
m.Delete(key)
m.Range(func(key,value) bool)
數(shù)據(jù)結(jié)構(gòu)
/*
package: sync
file： map.go
line: 27
*/
type Map struct {
mu Mutex
read atomic.Value
dirty map[interface{}]*entry
misses int
}
/*
package: sync
file： map.go
line: 27
*/
type readOnly struct {
m map[interface{}]*entry
amended bool
}
/*
package: sync
file： map.go
line: 73
*/
type entry struct {
p unsafe.Pointer
}
/*
package: sync
file： map.go
line: 70
*/
var expunged = unsafe.Pointer(new(interface{}))
mu: Mutex鎖番挺，在對dirty進(jìn)行操作的時候心铃，需要上鎖
read: atomic.Value對象腥沽，對readOnly對象進(jìn)行原子讀取和存儲萧恕，對map進(jìn)行操作時，優(yōu)先操作read中的數(shù)據(jù)乎婿。
readOnly：維護(hù)一個只讀的map和一個判斷dirty是否有新值的字段测僵。
dirty：保存最新數(shù)據(jù)的map，當(dāng)從read中多次讀取不到數(shù)據(jù)時次酌，會將dirty提升成read恨课。
misses：從read讀取不到數(shù)據(jù)的次數(shù)，當(dāng)dirty提升為read的時候置零岳服。
entry：指針p保存?zhèn)魅雟alue的地址
expunged：隨機(jī)地址剂公，當(dāng)entry從dirty中刪除的時候，將entry的p指向expunged
方法
Nwomap
/*
package: sync
file： map.go
line: 95
*/
func newEntry(i interface{}) *entry {
return &entry{p: unsafe.Pointer(&i)}
}
newEntry傳入一個interface對象吊宋，返回保存了interface對象指針的entry指針纲辽。
Load
/*
package: sync
file： map.go
line: 102
*/
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
read, _ := m.read.Load().(readOnly) //step 1
e, ok := read.m[key]
if !ok && read.amended { //step 2
m.mu.Lock()
read, _ = m.read.Load().(readOnly) //step 3
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key] //step 4
m.missLocked()
}
m.mu.Unlock()
}
if !ok { //step 5
return nil, false
}
return e.load() //step 6
}
- 從read中讀取readOnly，并嘗試從readOnly的map中尋找key對應(yīng)的entry璃搜。
- 若在readOnly中不存在這個key拖吼，但是dirty中存在新的entry（不一定是key對應(yīng)的entry，只是表示dirty中存在read中不存在的entry）这吻，則獲取Mutex鎖吊档。
- 雙檢查，重復(fù)step1和step2唾糯。若獲得鎖之前key在dirty中存在怠硼，并且dirty被提升read，則這個時候key在read中存在移怯，讀取read中的entry并解鎖柴底。
- 若在read中還是不存在尤筐，則直接從dirty中讀取entry，并且將miss數(shù)加1。若miss數(shù)大于等于dirty中的數(shù)據(jù)在塔，則將dirty提升為read，將readOnly中的amended設(shè)為false蛀蜜，dirty設(shè)為nil办斑，miss置零,然后解鎖。
/*
package: sync
file： map.go
line: 343
*/
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
}
- 若key在dirty和read中都不存在赖草，則返回空值和false炸站。
- 從entry中讀取存儲的數(shù)據(jù),若entry的p為空或者被標(biāo)記為expunged，則表示該值已經(jīng)被刪除疚顷，則返回nil和false旱易，否則返回對應(yīng)的值和true。
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
/*
package: sync
file： map.go
line: 136
*/
func (m *Map) Store(key, value interface{}) {
read, _ := m.read.Load().(readOnly) //step 1
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
m.mu.Lock() //step 2
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {
m.dirty[key] = e
}
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok { //step 3
e.storeLocked(&value)
} else { //step 4
if !read.amended {
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}
-
從read中讀取readOnly腿堤，并嘗試從readOnly的map中尋找key對應(yīng)的entry阀坏，若存在則嘗試直接將entry的p指向value。
func (e *entry) tryStore(i *interface{}) bool { p := atomic.LoadPointer(&e.p) //step a if p == expunged { return false } for { //step b if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } p = atomic.LoadPointer(&e.p) if p == expunged { return false } } }a. 判斷p是否被標(biāo)記為expunged笆檀，若是則表示key已經(jīng)在dirty中刪除忌堂，不能直接在read中存儲。
b. 循環(huán)嘗試進(jìn)行CAS操作將當(dāng)前Value的值存儲到entry中酗洒，除非key在dirty中被刪除士修。 上鎖然后進(jìn)行雙檢查枷遂，若dirty被提升為read，并且key在新的read中存在棋嘲，則將新的值存入entry中酒唉。中間會判斷p是否被標(biāo)記為expunged，若是則將key存到dirty中沸移。
若在dirty中存在痪伦，則直接將值存到entry中。
-
若在dirty中也不存在雹锣，則創(chuàng)建新的entry存到dirty中网沾。并且將read的amended設(shè)為ture，表示dirty中有新的數(shù)據(jù)蕊爵。若dirty為nil辉哥，會將read的值賦值給新的dirty。
/* package: sync file： map.go line: 353 */ func (m *Map) dirtyLocked() { if m.dirty != nil { //step a return } read, _ := m.read.Load().(readOnly) //step b m.dirty = make(map[interface{}]*entry, len(read.m)) for k, e := range read.m { if !e.tryExpungeLocked() { //step c m.dirty[k] = e } } } /* package: sync file： map.go line: 367 */ 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 }a. 若dirty不為nil攒射，則直接返回证薇。
b. 讀出read，創(chuàng)建長度同read的map賦值給dirty匆篓。
c. 循環(huán)遍歷read浑度，若read中的entry的值為nil，則將p標(biāo)記為expunged鸦概，若不為nil箩张，則將entry賦值給dirty。因此窗市，p只有在dirty在重新創(chuàng)建的時候才會被標(biāo)記為expunged先慷，并且對應(yīng)的key不會在dirty中出現(xiàn)。所以咨察，在step2的時候论熙，若entry的p被標(biāo)記為expunged了，那么dirty一定不為nil摄狱，并且key在dirty中不存在脓诡，需要將key加入到dirty中。
LoadOrStore
/*
package: sync
file： map.go
line: 203
*/
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
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 {
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
}
/*
package: sync
file： map.go
line: 243
*/
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
p := atomic.LoadPointer(&e.p) //step 1
if p == expunged {
return nil, false, false
}
if p != nil { //step 2
return *(*interface{})(p), true, true
}
ic := i
for { //step 3
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
}
}
}
基本邏輯同Load方法媒役，在read中找對應(yīng)的entry祝谚，若存在則嘗試讀并寫入，若不存在則上鎖后依次在read酣衷、dirty中進(jìn)行讀取和寫入交惯。唯一區(qū)別則是若key在read中不存在，而在dirty中存在，會像Store方法一樣席爽，進(jìn)行miss數(shù)增加和判斷是否需要提升dirty的操作意荤。
而在entry的tryLoadOrStore方法中
- 判斷key是否被刪除，若是則返回nil
- 若不為nil只锻，則返回對應(yīng)的值
- 若為nil玖像，則循環(huán)嘗試原子CAS操作將新的值存到entry中和進(jìn)行step 1、step 2的判斷
Delete
/*
package: sync
file： map.go
line: 271
*/
func (m *Map) Delete(key interface{}) {
read, _ := m.read.Load().(readOnly) //step 1
e, ok := read.m[key]
if !ok && read.amended { //step 2
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
delete(m.dirty, key)
}
m.mu.Unlock()
}
if ok { //step 3
e.delete()
}
}
/*
package: sync
file： map.go
line: 288
*/
func (e *entry) delete() (hadValue bool) {
for {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return false
}
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return true
}
}
}
- 從read中讀取readOnly炬藤，并嘗試從readOnly的map中尋找key對應(yīng)的entry。
- 若在read中不存在碴里，并且dirty中有新的數(shù)據(jù)沈矿，則上鎖并進(jìn)行雙檢查，若dirty中依然有新的數(shù)據(jù)咬腋，則直接調(diào)用delete方法刪除dirty中的對應(yīng)的key羹膳，無論在dirty中是否存在這個key。
- 若entry存在根竿，則將entry中的p標(biāo)記為nil陵像。
Range
/*
package: sync
file： map.go
line: 310
*/
func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := m.read.Load().(readOnly) //step 1
if read.amended {
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 { //step 2
v, ok := e.load()
if !ok {
continue
}
if !f(k, v) {
break
}
}
}
- 從read中讀取readOnly，若dirty中有新數(shù)據(jù)寇壳，則立即提升dirty為read醒颖。
- 使用原生的range方法遍歷read，若數(shù)據(jù)不為nil壳炎，則調(diào)用回調(diào)方法傳入key和value泞歉，若回調(diào)方法返回false，則跳出循環(huán)匿辩。
總結(jié)
sync.map通過使用一個只讀的read和一只寫的dirty來保證讀寫時候的并發(fā)效率腰耙，只有在對read中不存在的key進(jìn)行讀寫的時候，才會去上鎖寫dirty铲球。
read和dirty通過使用entry進(jìn)行數(shù)據(jù)共享挺庞，若一個key在read中存在，則只修改read中這個key對應(yīng)的entry的值稼病，就可以保證在dirty中數(shù)據(jù)同步选侨。而不需要對map進(jìn)行修改，保證了不會對read造成并發(fā)讀寫異常然走。比如delete操作侵俗，只是將read中的entry的p設(shè)置為nil，而不是將這個key刪除丰刊。
在讀取操作的時候隘谣，若key在read中多次不存在，而在dirty中有新數(shù)據(jù)（不管在dirty中是否存在），則會將dirty提升為read寻歧，保證讀取的命中率掌栅，減少上鎖次數(shù)。
在寫操作的時候码泛，若read不存在這個key猾封，才會對dirty進(jìn)行寫，并且若dirty為空噪珊，會從read中復(fù)制不為空的數(shù)據(jù)晌缘。
sync.map適合在對大量重復(fù)key的讀寫操作的場景下使用，這個時候約等于都在對read進(jìn)行讀寫痢站，不需要上鎖磷箕，效率非常高。但是不適合在對大量新增key的讀寫場景下使用阵难，這個時候大部分操作都是在對dirty進(jìn)行操作岳枷，幾乎都需要上鎖，而且由于大量miss和大量新增key的寫呜叫，導(dǎo)致頻繁的dirty提升和dirty復(fù)制空繁，效率反而可能低于讀寫鎖。
