background
It is well known that go plain maps do not support concurrency, in other words, are not thread (Goroutine) safe. The blogger has been using it since Golang 1.4, when map concurrent reads were not supported, but concurrent writes produced dirty data. After Golang 1.6, concurrent reads and writes will panic:
fatal error: concurrent map read and map write
Copy the codepackage main
func main(a) {
m := make(map[int]int)
go func(a) {
for {
_ = m[1]}} ()go func(a) {
for {
m[2] = 2
}
}()
select{}}Copy the codeTherefore, bloggers use two methods when they need to support concurrent reads and writes to the map:
- The third-party class library concurrent-Map.
- Map plus sync.rwmutex to keep threads (goroutine) safe.
After Golang 1.9, Go introduced concurrency-safe Map in the Sync package, which also provides a third way for bloggers. This article also focuses on this, in order to timeliness, this article based on golang 1.10 source analysis.
sync.Map
The structure of the body
Map
type Map struct {
mu Mutex // Mutex to lock dirty maps
read atomic.Value // Read map first, support atomic operation, annotation readOnly is not read only, but its structure. Read actually does write
dirty map[interface{}]*entry // Dirty is a current map that allows reading and writing
misses int // When the number of misses is equal to the length of dirty, the dirty is copied to read
}
Copy the codereadOnly
ReadOnly is primarily used for storage, storing elements in map.read through atomic operations.
type readOnly struct {m map[interface{}]*entry amended bool // If the data is in the dirty but not inread, the value istrue, as a modification identifier}Copy the codeentry
typeEntry struct {// nil: indicates deleted. Call Delete() to DeletereadSet elements in map to nil // expunged: also means deleted, but this key is only available inreadWhile not in Dirty, this situation appears in willreadUnsafe. Pointer // *interface{}} // unsafe.Pointer // *interface{}}Copy the codeThe principle of
If you’re familiar with Java, you’ll remember how CocurrentHashMap uses lock fragmentation to increase the number of locks, thereby controlling the number of threads competing for the same lock. Does Golang’s Sync.map use the same principle? The principle of sync.map is very simple. It uses a space for time policy to realize the impact of locking on performance through two redundant data structures (read and dirty). Separate reads and writes into separate maps by introducing two maps, where the Read Map provides concurrent reads and atomic writes of existing elements, and the dirty map takes care of reads and writes. If no value is read in a Read map, the lock is added for subsequent reads and the number of misses is added. When the number of misses is greater than or equal to the length of a dirty map, the dirty map is upgraded to a Read map. As you can see from the previous structure definition, although two maps are introduced, the underlying data store is a pointer pointing to the same value.
Sync.map starts by writing data
X=1
Y=2
Z=3
Copy the codeA dirty map receives write requests. A Read map has no data. In this case, read map and dirty Map data are shown in the following figure.
Miss records the number of misses that fail to read from the read map. When the number of misses>=len(dirty map), When the dirty map is upgraded to read Map, the address of the dirty map is copied and the dirty map is cleared and misses is set to 0. The following figure shows the read map and dirty map data.
Now that we need to modify the Z element Z=4, sync.Map directly modifies the read Map element.
If the number of misses is successful, the dirty map is upgraded to read map and the dirty map is amended==false. If the number of misses is successful, the dirty map is successfully upgraded to read Map. The dirty map needs to copy data from the Read map.
The upgrade results are as follows.
If Z needs to be deleted, it needs to be amended in one of the following ways: one of the read map exists and the element of read is amended==false: the element in read is directly set to nil.
If an element has just been written to a dirty map and has not been upgraded to a Read map, the golang built-in function delete is called directly to delete elements in the dirty map.
Or if the element exists in both a Read map and a dirty map: set elements in the Read map to nil, because both read and dirty maps use element addresses, so they are set to nil.
Optimal point
- Space for time. Two redundant data structures (read and DIRTY) are used to realize the impact of locking on performance.
- Use read-only data (read) to avoid read/write conflicts.
- Dynamic adjustment, upgrade dirty data to read after too many misses.
- Double-checking.
- Delayed deletion. Deleting a key is just a marker, and the deleted data is only cleaned up when dirty is promoted.
- Read, update, and delete from read preferentially because read does not require a lock.
Method source code analysis
Load
Load returns the key value stored in the map, or nil if there is no value. The OK result indicates whether a value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// First check to see if the element exists
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if! ok && read.amended {// Lock dirty map
m.mu.Lock()
// The second time to check whether the element exists, the main purpose is to prevent the lock process,dirty map is converted into read map, so that the data cannot be read
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if! ok && read.amended {// Fetch from dirty map to deal with new elements that do not exist in Read Map
e, ok = m.dirty[key]
// The number of misses needs to be recorded regardless of whether the element exists, so that the dirty map can be upgraded to a read map
m.missLocked()
}
/ / unlock
m.mu.Unlock()
}
// There is no direct return for the element
if! ok {return nil.false
}
return e.load()
}
Copy the codeThe dirty map was upgraded to read Map
func (m *Map) missLocked(a) {
// The number of misses increases 1
m.misses++
// Check whether dirty maps can be upgraded to Read maps
if m.misses < len(m.dirty) {
return
}
// Upgrade dirty map to Read map
m.read.Store(readOnly{m: m.dirty})
// Dirty map cleared
m.dirty = nil
// misses reset to 0
m.misses = 0
}
Copy the codeElement values
func (e *entry) load(a) (value interface{}, ok bool) {
p := atomic.LoadPointer(&e.p)
// The element does not exist or is deleted
if p == nil || p == expunged {
return nil.false
}
return* (*interface{})(p), true
}
Copy the codeRead map is used for reading; each Load is read first from read; when read does not exist and it is amended to true, the Load is read from dirty. MissLocked is executed regardless of whether the element is present in the Dirty map, which misses+1, and when M.misses < len(m.dirty), dirty is copied to read, where dirty is set to nil, and misses=0.
storage
Set the Key = > Value.
func (m *Map) Store(key, value interface{}) {
// If read exists and the entry is not marked for deletion, attempt to write directly, write successfully, end
// First check
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
/ / dirty map locks
m.mu.Lock()
// The second test
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// unexpungelocc ensures that the element is not marked for deletion
// Determine that the element is identified as deleted
if e.unexpungeLocked() {
// This element was removed earlier, which means there is a non-nil dirty element that is not in it.
m.dirty[key] = e
}
// Update the read Map element value
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
// The read map does not have this element, but the Dirty map does, and needs to change the dirty Map element value to the latest value
e.storeLocked(&value)
} else {
Amended ==false if the dirty map is empty and a copy of the Read map needs to be copied to the dirty Map
if! read.amended { m.dirtyLocked()// Set read. Amended ==true to indicate that the dirty map has data
m.read.Store(readOnly{m: read.m, amended: true})}// Set the element to enter the Dirty Map, where the dirty Map has the read map and the latest element
m.dirty[key] = newEntry(value)
}
If the read map is very large, m.dirtylocked () will take a long time to execute. It is possible to lock the dirty map only when it is locked, because m.dirtylocked () has write operations
m.mu.Unlock()
}
Copy the codeTry to store elements.
func (e *entry) tryStore(i *interface{}) bool {
// Get the element corresponding to the Key and determine whether it is marked as deleted
p := atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
for {
// CAS attempts to write the new element value
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
return true
}
// Check whether it is marked as delete
p = atomic.LoadPointer(&e.p)
if p == expunged {
return false}}}Copy the codeUnexpungelocc ensures that elements are not marked for deletion. If the element was previously removed, it must be added to the Dirty Map before it is unlocked.
func (e *entry) unexpungeLocked(a) (wasExpunged bool) {
return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}Copy the codeCopy from read map to Dirty Map.
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 {
// If marked nil or expunged, the dirty map is not copied to
if! e.tryExpungeLocked() { m.dirty[k] = e } } }Copy the codeLoadOrStore
Return the value of the corresponding element if it exists, or write the element to sync.map if it does not. If a value has been loaded, the result is true; False if stored.
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
// Read the map without locking
// First check
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// If the element exists (whether marked for deletion is handled by tryLoadOrStore), try to get the existing value of the element or write the element to it
actual, loaded, ok := e.tryLoadOrStore(value)
if ok {
return actual, loaded
}
}
m.mu.Lock()
// The second test
// See Store for the following logic
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
}
Copy the codeIf no element is removed, tryLoadOrStore automatically loads or stores a value. If an element is deleted, tryLoadOrStore leaves the entry unchanged and returns OK = false.
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
p := atomic.LoadPointer(&e.p)
// The element identifier is deleted
if p == expunged {
return nil.false.false
}
// If the element value exists, the original element value is returned
ifp ! =nil {
return* (*interface{})(p), true.true
}
// If p is nil(where nil does not mean the element's value is nil, but atomic.loadPointer (&e.p) is nil, the element's nil has a value in unsafe.Pointer), the element's value is updated
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
}
ifp ! =nil {
return* (*interface{})(p), true.true}}}Copy the codeDelete
If there are elements in the Read map, the element is set to nil, and the number of deleted elements is only cleaned up when the dirty is promoted. Delayed deletion prevents locking of deleted elements later. If the read map does not have any elements, the dirty map is deleted
func (m *Map) Delete(key interface{}) {
// First check
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if! ok && read.amended { m.mu.Lock()// The second test
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if! ok && read.amended {// This element is deleted regardless of whether it exists in the dirty map
delete(m.dirty, key)
}
m.mu.Unlock()
}
if ok {
// If in read, mark it as deleted (nil)
e.delete()}}Copy the codeElement value set to nil
func (e *entry) delete(a) (hadValue bool) {
for {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return false
}
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return true}}}Copy the codeRange
Iterating over all elements in sync.map is a snapshot, so it may not be accurate.
func (m *Map) Range(f func(key, value interface{}) bool) {
// First check
read, _ := m.read.Load().(readOnly)
// Read. Amended =true to state that the dirty map contains all valid elements (including newly added elements but not deleted elements) and that the dirty Map is used
if read.amended {
// Second check
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if read.amended {
// Use dirty map and upgrade to read map
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}
// As a general rule, use read map as a read
for k, e := range read.m {
v, ok := e.load()
// Deleted items are not counted
if! ok {continue
}
// The function returns false and terminates
if! f(k, v) {break}}}Copy the codeconclusion
According to the above analysis,sync.Map is not suitable for a scenario with a large number of simultaneous reads and writes. As a result, the Read Map fails to read data and locks for further reads, and dirty maps are constantly upgraded to Read maps. The overall performance is low, especially in cache scenarios. Sync. Map is suitable for append-only and heavy read and small write scenarios.
Sync.map does not provide a Len() method to get the number of elements, but it can be done through Range().
func Len(sm sync.Map) int {
lengh := 0
f := func(key, value interface{}) bool {
lengh++
return true
}
one:=lengh
lengh=0
sm.Range(f)
ifone ! = lengh { one = lengh lengh=0
sm.Range(f)
if one <lengh {
return lengh
}
}
return one
}
Copy the codereference
- Go sync.Map
- Go 1.9 Sync.map revealed