Introduction to the
Go does not support concurrent map writes because map writes are not concurrency safe. Fatal error: Concurrent map writes occur when you attempt multiple Goroutine operations on the same map.
So sync.map was officially introduced to cater for concurrent programming applications.
The implementation principle of sync.map can be summarized as follows:
- The read and dirty fields are used to separate read and write data. The read data is stored in the read-only field, and the latest data is stored in the dirty field
- Read is read first, dirty is not present, and dirty is only written when writing
- Read does not need to be locked, while read or write dirty does
- There is also a field that misses to count how many times the read is penetrated (when dirty is read), and when the dirty data is synchronized to the read after a certain number of misses
- For deleted data, delay the deletion directly by marking
The data structure
The Map data structure is as follows:
type Map struct {
// Lock dirty fields
mu Mutex
// Read-only data. The actual data type is readOnly
read atomic.Value
// The latest data to be written
dirty map[interface{}]*entry
// count +1 each time you need to read dirty
misses int
}
Copy the codeThe data structure of readOnly is:
type readOnly struct {
/ / built in the map
m map[interface{}]*entry
// Dirty contains a key that is not present in read
amended bool
}
Copy the codeThe entry data structure is used to store Pointers to values:
type entry struct {
p unsafe.Pointer // same as *interface{}
}
Copy the codeAttribute P has three states:
p == nil: The key value has been deleted andm.dirty == nilp == expunged: The key value has been deleted, butm.dirty! =nil且m.dirtyExpunged (null interface pointer) does not exist- Except for the above, then the key-value pair exists, exists in
m.read.m, if them.dirty! =nilIt also exists inm.dirty
The Map methods are as follows:
Load: Reads the specified key and returns valueStore: Stores (add or change) key-valueDelete: Deletes the specified key
The source code parsing
Load
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// First try to read a readOnly object from read
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// If it does not exist, try to fetch it from dirty
if! ok && read.amended { m.mu.Lock()// Check again for security reasons
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// If it does not exist, get it from dirty
if! ok && read.amended { e, ok = m.dirty[key]// Call miss logic
m.missLocked()
}
m.mu.Unlock()
}
if! ok {return nil.false
}
// Read the value from entry.p
return e.load()
}
func (m *Map) missLocked(a) {
m.misses++
if m.misses < len(m.dirty) {
return
}
// When miss counts too much, it will be amended = false and M.dirty = nil
m.read.Store(readOnly{m: m.dirty})
m.dirty = nil
m.misses = 0
}
Copy the codeStore
func (m *Map) Store(key, value interface{}) {
read, _ := m.read.Load().(readOnly)
// If there is one in read, try to save it to entry
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// If the previous step is not successful, it is handled in different cases
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
As with Load, fetch from read again
if e, ok := read.m[key]; ok {
// Case 1: read exists
if e.unexpungeLocked() {
// If p == expunged, you need to assign entry to dirty first (because expunged data does not stay in dirty).
m.dirty[key] = e
}
// Update entry with the value
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
// Case 2: Entry is not present in read but is present in dirty, so update entry with value
e.storeLocked(&value)
} else {
// Case 3: Neither read nor dirty exists
if! read.amended {// If amended == false, dirtyLocked will be called to copy read to dirty (except for the data that has been tagged for deletion)
m.dirtyLocked()
// Then change it to true
m.read.Store(readOnly{m: read.m, amended: true})}// Store the new keys 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(a) (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(a) {
ifm.dirty ! =nil {
return
}
read, _ := m.read.Load().(readOnly)
m.dirty = make(map[interface{}]*entry, len(read.m))
for k, e := range read.m {
// Check whether entry is deleted; otherwise, it is saved in dirty
if! e.tryExpungeLocked() { m.dirty[k] = e } } }func (e *entry) tryExpungeLocked(a) (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
// If there is p == nil (that is, key-value pairs are deleted), it will be set to expunged at this point
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}
Copy the codeDelete
func (m *Map) Delete(key interface{}) {
m.LoadAndDelete(key)
}
// LoadAndDelete acts as Delete and returns the value and presence
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
The fetch logic is similar to 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() }// Query entry and delete it
if ok {
// Mark entry.p as nil, the data is not actually deleted
// The data is actually deleted and set to expunged in the tryExpungeLocked Store
return e.delete()}return nil.false
}
Copy the codeconclusion
It can be seen that the design of read/write separation solves the write security in the case of concurrency, and makes the read speed close to the built-in map in most cases, which is very suitable for the case of more read and less write.
Sync.map has a few other methods:
Range: iterates through all key-value pairs with a callback functionLoadOrStore: Reads data. If no data exists, save it and read it again
Here is no longer detailed explanation, can refer to the source code.
This article belongs to the original, first in the wechat public number “life oriented programming”, if you need to reprint, please leave a message on the background.
