Shulou(Shulou.com)06/01 Report--

This article introduces what is the implementation principle of sync.Map in Golang. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

Brief introduction

Go's built-in map does not support concurrent write operations because map writes are not concurrent secure. When you try multiple Goroutine operations on the same map, an error occurs: fatal error: concurrent map writes.

Therefore, officials have introduced sync.Map to meet the application of concurrent programming.

The implementation principle of sync.Map can be summarized as follows:

Read and write are separated by read and dirty fields. The read data is stored on the read-only field read, and the newly written data is stored on the dirty field.

The read will be queried first when reading, and then the dirty will be queried if it does not exist. Only dirty will be written when writing

Reading read does not require locking, while reading or writing dirty requires locking

In addition, there is a misses field to count the number of times read has been penetrated (which refers to the need to read dirty), and more than a certain number of times will synchronize the dirty data to the read.

For deleting data, the deletion is delayed directly through the tag.

Data structure

The data structure of Map is as follows:

Type Map struct {/ / lock function to protect dirty field mu Mutex / / read-only data. The actual data type is readOnly read atomic.Value / / newly written data dirty map [interface {}] * entry / / counter, and + 1 misses int} each time you need to read dirty

The data structure of readOnly is:

Type readOnly struct {/ / built-in map m map [interface {}] * entry / / indicates that there is a key in dirty that is not in read. Use this field to decide whether to lock dirty amended bool}.

The entry data structure is used to store pointers to values:

Type entry struct {p unsafe.Pointer / / is equivalent to * interface {}}

Attribute p has three states:

P = = nil: the key value has been deleted and m.dirty = = nil

P = = expunged: the key value has been deleted, but m.dirtydirectornil and m.dirty does not exist (expunged is actually a null interface pointer)

In addition to the above, key-value pairs exist in m.read.m, and in m.dirty if m. Dirtyroomnil

The methods commonly used in Map are as follows:

Load: read the specified key and return value

Store: store (add or modify) key-value

Delete: deletes the specified key

Source code parsing Loadfunc (m * Map) Load (key interface {}) (value interface {}, ok bool) {/ / first try to read the readOnly object read, _: = m.read.Load (). (readOnly) e from read Ok: = read.m [key] / / if it does not exist, try to get if from dirty! ok & & read.amended {m.mu.Lock () / / because the above read acquisition is not locked For safety, check read again, _ = m.read.Load (). (readOnly) e, ok = read.m [key] / / if it does not exist, get if! ok & & read.amended {e from dirty Ok = m.dirty [key] / / call miss's logic m.missLocked ()} m.mu.Unlock ()} if! ok {return nil False} / / read the value return e.load ()} func (m * Map) missLocked () {m.missesystems + if m.misses < len (m.dirty) {return} / / when miss accumulates too much Dirty is stored in read, then amended = false, and m.dirty = nil m.read.Store (readOnly {m: m.dirty}) m.dirty = nil m.misses = 0} Storefunc (m * Map) Store (key, value interface {}) {read, _: = m.read.Load (). (readOnly) / / if it exists in read, try to save if e, ok: = read.m [key] in entry Ok & & e.tryStore (& value) {return} / / if the previous step is not performed successfully, process m.mu.Lock () read on a case-by-case basis, _ = m.read.Load (). (readOnly) / / like Load, get if e, ok: = read.m [key] from read again If if e.unexpungeLocked () {/ / if p = = expunged exists in ok {/ / case 1:read, you need to assign entry to dirty (because expunged data will not be left in dirty) m.dirty [key] = e} / / update entry e.storeLocked (& value)} else if e, ok: = m.dirty [key] Ok {/ / case 2:read does not exist, but exists in dirty, then update entry e.storeLocked (& value)} else {/ / case if {/ / if amended = = false does not exist in both 3:read and dirty Then call dirtyLocked to copy the read to dirty (except for the marked deleted data) m.dirtyLocked () / / and then change amended to true m.read.Store (readOnly {m: read.m) Amended: true})} / / store the new key value in dirty m.dirty [key] = newEntry (value)} m.mu.Unlock ()} func (e * entry) tryStore (I * interface {}) bool {for {p: = atomic.LoadPointer (& e.p) if p = expunged {return false} if atomic.CompareAndSwapPointer (& e.p, p Unsafe.Pointer (I)) {return true}} func (e * entry) unexpungeLocked () (wasExpunged bool) {return atomic.CompareAndSwapPointer (& e.p, expunged, nil)} func (e * entry) storeLocked (I * interface {}) {atomic.StorePointer (& e.p, unsafe.Pointer (I))} func (m * Map) dirtyLocked () {if m.dirty! = nil {return} read _: = m.read.Load (). (readOnly) m.dirty = make (map [interface {}] * entry, len (read.m)) for k, e: = range read.m {/ / determine whether entry is deleted Otherwise, if! e.tryExpungeLocked () {m.dirty [k] = e} func (e * entry) tryExpungeLocked () (isExpunged bool) {p: = atomic.LoadPointer (& e.p) for p = = nil {/ / if there is p = = nil (that is, the key-value pair is delete) Will be set as expunged if atomic.CompareAndSwapPointer (& e.p, nil, expunged) {return true} p = atomic.LoadPointer (& e.p)} return p = = expunged} Deletefunc (m * Map) Delete (key interface {}) {m.LoadAndDelete (key)} / / LoadAndDelete function is equivalent to Delete at this time. And the return value is similar to whether there is func (m * Map) LoadAndDelete (key interface {}) (value interface {}, loaded bool) {/ / get logic and Load If read does not exist, query dirty 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] m.missLocked ()} m.mu.Unlock ()} / / Delete if ok {/ / Mark entry.p as nil after query to entry The data is not actually deleted / / actually deleted and is set to expunged. It is return e.delete ()} return nil, false} summary in the tryExpungeLocked of Store.

It can be seen that this read-write separation design not only solves the write security of the concurrent situation, but also makes the read speed close to the built-in map in most cases, which is very suitable for the case of more reading and less writing.

Sync.Map has some other ways to do this:

Range: traverses all key-value pairs, and the parameter is a callback function

LoadOrStore: read the data, save it and read it again if it doesn't exist

What is the implementation principle of sync.Map in Golang is shared here, I hope that the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.