Map and sync.map
1.1. Map Concurrency
In the concurrent case, map concurrent reads are thread-safe, but concurrent reads and writes are thread-unsafe.
Func main () {m: = make (map [int] int) go func () {for {_ = m [1] [3] / / read / / m = 3 / / write}} () go func () {for {/ / m [2] = 2 Write / / _ = m}} [4] / / read () the select / / maintain the main goroutine} {}Copy the codeFatal error: Concurrent map read and map write fatal error: Concurrent map read and map write
1.2 mutex/RWMutext+map concurrency
The solution to thread insecurity is simple: use locks.
Type LockMap struct {sync.rwmutex // or sync.mutex Map Map [int]int} func main() {m := LockMap{Map: Make (map[int]int)} go func() {for {m.lock () v := m.tap [2] // read m.unlock ()}}() go func() {for I := 1; i > 0; M.M ap i++ {m.L ock () [2] = I / / write m.U nlock ()}} () select {}}Copy the code1.3 sync.map concurrency
A thread-safe map, sync.map, is officially available for concurrent scenarios. In operation, it can directly use the sync.Map method provided externally, without the need for active control lock. The code is relatively clean.
func main() { m := sync.Map{} go func() { for i := 0; i < 10000; I++ {Margaret spellings tore (I, I) / / write}} () go func () {for I: = 10000; i > 0; I -- {_, _ = m.load (I) // read}}() select {}}Copy the codeNote that sync.map does not need to be initialized and can be used if declared with a zero value.
1.4 Operation method of sync.Map
Delete(key interface{}) func (m *Map) Load(key interface{}) (value interface{}, Ok bool) 3, read or write exists the specified key read, otherwise write. Loaded Returns true for reads and false for writes. Actual indicates an existing value or a newly written value. Loaded returns true for reads and false for writes. Func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}) loaded bool Func (m *Map) Range(f func(key, value interface{}) bool)
Sync. Map source code analysis
The source code for sync.map (go1.14) is very small, with less than 400 lines (and lots of comments). There is no system/compilation involved, just a wrapper on top of the Map to support high performance concurrent reads and writes. So, the source code is relatively easy to read, but for those who can’t, you can go straight to Chapter 3. In addition, with the behavior analysis in Chapter 4, it is easier to understand the source code.
2.1. Data structure
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
type readOnly struct {
m map[interface{}]*entry
amended bool // true if the dirty map contains some key not in m.
}
type entry struct {
p unsafe.Pointer // *interface{}
}
var expunged = unsafe.Pointer(new(interface{}))
Copy the code- Mu: Mutex lock. A Mutex lock is required for dirty map operations.
- Read: Stores read-only data. Because it is of type atomic.Value and read-only, concurrency is safe. It is a readOnly data structure that needs to be converted with interface{}.
- Amended: Mark whether the data in dirty and readOnly. M are identical or true if they are not.
- = The number of misses is very small. On each read operation, if the read fails, the count is +1.
- Dirty: Stores read/write data or full data. It is a native map and requires locks during operations.
- Entry: In readOnly. M and dirty, the value type stored in map is * Entry, and the entry is a pointer to the address of the real map->value, avoiding space waste when multiple copies of value data are stored.
1. Essentially, sync.Map consists of two maps, one for read-only data and one for read/write data. The two names read Map (readone.m) and dirty map(dirty) are described below.
Expunged is a placeholder/sentinel value assigned randomly at initialization to indicate whether the value in the read map has been deleted. However, when deleting, the value is set to nil and then converted to expunged.
2.2. Add/change Store
func (m *Map) Store(key, value interface{}) { // 1. Read, _ := m.read.load ().(readOnly) if e, ok := read. M [key]; Ok && e.store (&value) {return} // if read does not exist or the key has been marked for deletion m.m.lock () read, If e, ok := read.m[key]; if e, ok := read.m[key]; Ok {// 2. If entry is marked expunge, it indicates that dirty does not have a key, and can be added to dirty and updated entry. If e.unexpungelocked () {m.dirty[key] = e // join dirty} e.locked (&value) // update value} else if e, ok := m.dirty[key]; } else {// 4. Read and dirty are not available. If! Read. Amended {// read. Amended =false; Dirty = nil / / will not delete the data in a read join the dirty m. irtyLocked () / / tag amended = true, says read the same as the dirty don't m.r ead.pa Store (readOnly {m: read.m, amended: true}) } m.dirty[key] = newEntry(value) } m.mu.Unlock() }Copy the code1. If the key exists in the read map and is not marked as deleted, store the key directly. Note that even if the key is present in m.girl, there is no need to operate m.girl, and its value will keep the latest entry value.
Func (e *entry) tryStore(I *interface{}) bool {for {p := atomy.loadPointer (&e.p) if p == expunged {// Already deleted return False} if atomic.Com pareAndSwapPointer (& e.p, p, unsafe. The Pointer (I)) {/ / I value is the return true}}}Copy the code2. If the key exists in the Read map but is marked as expunged, the key does not exist in the dirty map. In this case, write the key-value pair to the dirty map. At the same time, update the key-value in the Read map with the atomic.storePointer operation.
If e.nexpungelocked () {m.dirty[key] = e // Add dirty} func (e *entry) storeLocked(I *interface{}) { atomic.StorePointer(&e.p, unsafe.Pointer(i)) }Copy the code3. If the key does not exist in read but exists in dirty, the dirty map is directly updated.
4. If the key does not exist in both read and dirty, the operation is added. The undeleted elements in the Read map are imported into the dirty map using dirtyLocked(). And set read. Amended =true.
Func (m *Map) dirtyLocked() {if m.dirty! Dirty return} read, _ := m.read.load ().(readOnly) m.dirty = make(map[interface{}]*entry, Len (read.m)) for k, e := range read.m {// tryExpungeLocked() e.tryExpungeLocked() { m.dirty[k] = e } } }Copy the codeWhen adding, Store-> dirtyLocked-> tryExpungeLocked will try to set the nil value in the read map to a sentinel value.
func (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { if atomic.CompareAndSwapPointer(&e.p, nil, Expunged) {return true} p = atomy.loadPointer (&e.p)} return p == expungedCopy the codeIf addr==old, change the value of addr and return true; otherwise, the value of *addr remains unchanged and return false. This series of functions is usually modified in practice using a loop.
for {
oldValue := atomic.LoadUint64(&sharedValue)
newValue := oldValue + XXX
if atomic.CompareAndSwapUint64(&sharedValue, oldValue , newValue ) {
// quit only when CompareAndSwap success, otherwise retry
break
}
}
Copy the code2.3, Delete the Delete
- If the key does not exist in the Read map and may exist in the dirty map, run the func delete(m map[Type]Type1, key Type) command to delete the element.
- If the key exists in the Read map, mark the element’s value as nil. If the key also exists in the dirty map, its value also becomes nil, because the value used in the two maps is the same.
Func (m *Map) Delete(key interface{}) {// Read from read Map, _ := m.read.load ().(readOnly) e, Ok := read. M [key] // If the key does not exist in the read map, it may exist in the dirty map. ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if ! Ok & read. Amended {delete (m. irty, key) / / map delete} m.m u.U nlock ()} if ok {e.d elete () / / is not delete the map, Just to put a value of nil}} func (e * entry) the delete () (hadValue bool) for {{p: = atomic LoadPointer (& e.p) if p = = nil | | p = = Expunged {/ / if p pointer is null, or marked cleared, that has been deleted return false} if atomic.Com pareAndSwapPointer (& e.p, p, nil) {/ / atomic operations, Mark it as nil. Return true}}}Copy the code1. In read map, there are two delete tags (nil and expunged) marked as nil, indicating normal delete operation, and the element may not exist in dirty: When delete key, value is set to nil if keys exist in the dirty. When a key is deleted, no operation is performed if no key exists in the dirty. Marked expunged indicates that the operation is performed during initialization of dirty, which definitely does not exist.
2, Delete element from read map is nil. When does it become placeholder expunged? When is it actually deleted? When a new key is inserted, dirtyLocked->tryExpungeLocked is triggered, marking the nil value as expunged value. On the next Promoted, read is pointed to dirty so that deleted content can be GC.
So, in sync.map, when an element is deleted, it doesn’t disappear immediately. A bug with others: placing a connection as a key in sync.map makes it hard to free the memory associated with the connection (such as buffer).
2.4, read the Load
Func (m *Map) Load(key interface{}) (value interface{}, ok bool) { _ := m.read.load ().(readOnly) e, ok := read. M [key] Ok && Read. Amended {m.m.rock () // Non-atomic operation, Read, _ = m.ead.Load().(readOnly) e, ok = read. M [key] E =read. M [key] if! {e, OK = M.dirty [key] // Count of misses +1 M.isslocked ()} m.u.nlock ()} if! ok { return nil, false } return e.load() } 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 }Copy the code1. Operation process: First, find read Map without lock; If yes, the data is read by atomic operation and returned; If the dirty map cannot be found and there are updates in the dirty map, search the dirty map under lock condition. Also update the number of misses.
The purpose of read is to give priority to the query before the dirty, so that when the same element is encountered, the dirty will not be penetrated (equivalent to the lock free read cache).
2. Read. Amended =true; for instance, it states that some data is not included in the Read map; for instance, it states that keys that do not exist in the Read map may or may not exist in the dirty map.
3, The role of misses: trigger promoted
- Misses: The number of times that the key is not in the read map when the load is searched.
- Promoted: Switch dirty Map to Read Map (transfer dirty data requiring lock operation to read-only thread-safe READ), the memory pointed by the original Read Map will be GC; Control promoted trigger by comparing miss count and dirty length.
Func (m *Map) missLocked() {m.isses ++ // compare the number of misses and the length of dirty, Control promoted trigger if m.misses < len(m.dirty) {return} // Set dirty to read because the penetration rate is too high. M.dirty = nil m.misses = 0 // misses reset to 0}Copy the codePromoted is fast because only read and dirty Pointers are switched without consideration of other influences. Notice that read. Amended is already initialized to false, so it is never explicitly assigned in the source code to be amended.
In contrast, if sync.map is large, dirtyLocked is slow because it iterates through assignments and locks.
So why do dirty maps need to hold all data after dirtyLocked? — Prepare for the next Promoted day.
2.5. Traverse Range
- If read. Amended =false, it indicates that there is no data in the dirty map and you need to go through the Read Map only.
- Read. Amended =true If the dirty map stores the full amount of data, only the dirty map can be amended.
- However, instead of traversing the dirty map, promote once, switch dirty to read.m, and traverse the Read Map again.
- Note that the parameters passed in are functions. In range, f(k,v) is called for data processing.
func (m *Map) Range(f func(key, value interface{}) bool) { read, _ := m.read.Load().(readOnly) if read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) if read.amended { // promote read = readOnly{m: m.dirty} m.read.Store(read) m.dirty = nil m.misses = 0 } m.mu.Unlock() } for k, e := range read.m { v, ok := e.load() if ! ok { continue } if ! f(k, v) { break } } }Copy the code2.6 Other Instructions
1. Why can dirty be changed to read? Because writes only operate on dirty maps and copy data from reads into dirty maps when creating a dirty map, data in the dirty is guaranteed to be up to date and complete (data sets must contain reads).
2. When a read operation is performed for promoted, dirty data is transferred to read.
3. Creating dirty data is done when adding keys. All undeleted data is copied from the read map.
4. Key-value can be nil. Nil, when it’s value, is in the form of an address, so it’s not confused with delete.
Three, suitable for the scene & use efficiency
3.1 Official description
3.1. Official pressure test
/usr/local/go/ SRC /sync: map_reference_test.go: map_reference_test.go: map_reference_test.go: map_reference_test.go: map_reference_test.go // DeepCopyMap=struct{mutex+read map}
1, read, miss a lot — BenchmarkLoadMostlyHits
/*sync_test. deepcopymap-8 139111147 11.7 ns/op /*sync_test. rwmutexmap-8 21769174 50.3 ns/op /* sync.map-8 143320003 8.47 ns/opCopy the code2, read, hit a lot – BenchmarkLoadMostlyHits
/*sync_test. deepcopymap-8 91466886 13.3 ns/op /*sync_test. rwmutexmap-8 23083020 52.4 ns/op /*sync. map-8 87908635 13.6 ns/opCopy the code3, read and write the half – BenchmarkLoadOrStoreBalanced
/*sync_test.RWMutexMap-8 3588764 356 ns/op
/*sync.Map-8 3582439 369 ns/op
Copy the code4, LoadAndStore unique value – BenchmarkLoadOrStoreUnique
/*sync_test.RWMutexMap-8 2070034 590 ns/op
/*sync.Map-8 1787559 685 ns/op
Copy the code5. Traversal — BenchmarkRange
/*sync_test.DeepCopyMap-8 443395 2541 ns/op
/*sync_test.RWMutexMap-8 21390 57320 ns/op
/*sync.Map-8 401102 2709 ns/op
Copy the code6, delete – BenchmarkAdversarialDelete
/*sync_test. deepcopymap-8 6994172 184 ns/op /*sync_test. rwmutexmap-8 14045349 76.5 ns/op /* sync.map-8 19644759 59.0 ns/opCopy the code3.2. Pressure test written by yourself
To be honest, part of the official pressure test code is hard to read. In addition, the results of the test cases all confirm that sync.map performs better. However, this is not the case……. “Self-written stress test” – not my code, of course, but “TonyBai”, I feel the results are much more intuitive and comparative.
1, test pressure test code at github.com/bigwhite/ex… Here are the running results:
/ / write BenchmarkBuiltinMapStoreParalell - 8, 8811454, 199 ns/op BenchmarkSyncMapStoreParalell - 8 3034864 379 ns/op BenchmarkBuiltinRwMapStoreParalell - 8, 8888641, 206 ns/op / / find BenchmarkBuiltinMapLookupParalell - 8 8363475 179 ns/op BenchmarkBuiltinRwMapLookupParalell - 8-2358116 56.5 ns/op BenchmarkSyncMapLookupParalell - 8-57642225 23.8 ns/op / / delete BenchmarkBuiltinMapDeleteParalell-8 8313638 167 ns/op BenchmarkBuiltinRwMapDeleteParalell-8 8413243 199 ns/op BenchmarkSyncMapDeleteParalell - 8-59606284 19.3 ns/opCopy the codeBuiltinMap = Mutex + map
BuiltinRwMap = RWMutex + map
SyncMap = sync.Map
2. Conclusion Sync. Map performs better in both read and delete aspects. Sync.map is only half as efficient at writing this. In summary, the sync.map type is significantly better for scenarios with more reads and less writes.
3. Extension: What about the scenario of writing too much and reading too little? After all, lock +map is not efficient either. Lock segmentation technology: The map is divided into multiple sub-maps and the concurrency is controlled by multiple locks to reduce the lock granularity and improve efficiency.
3.3 Result analysis
Sync.Map is not a single Map, but two maps. The read Map can be considered as a cache layer, storing “old” data and performing lock-free + atomic operations. Newly written elements are stored in the dirty map, and at certain times, all data in the dirty is transferred to the Read Map. Therefore, in the case of less writing, most of the execution data will be in read map, and it is more efficient to search for amendments in combination with the amended attribute.
However, when there are too many writes, new data is always found in the dirty map. New data is searched in both the Read map and the dirty Map, and the latter needs to be locked, which is inefficient. Meanwhile, dirty Map will also trigger Promoted to Read Map continuously, resulting in poor overall performance.
2, poor write performance write must go through the Read map, so in any case one more layer of operation than others; Later, we need to check the data status and status, which is more expensive than performance.
In addition, full data (from read to dirty) is often copied when a new key is added. If a map has a large amount of data, the efficiency is low.
3, fast deletion because only tag deletion, the deleted elements will actually be cleared from read Map during Promoted, which is equivalent to delayed deletion.
4. Experiment & Behavior analysis
The article by “TonyBai” analyzes the internal data changes during sync.map operation from the point of view of the sync.map instance and interprets its source logic. I found it interesting and put something similar (logging analysis sync.map) in this chapter. With really look at the source code, easier to understand, more image. To do this, copy the sync.Map code and make it your own package. Add print method; Finally, the sync.map internal data is continuously printed for each phase.
4.1. Initialization
var m sync_map.Map
m.Print()
-------------
-------------
start =======>> sync.Map:
read(amendend=false):
dirty:
misses:0
expunged:0xc0000981e0
end <<======= sync.Map
Copy the codeIt’s not nil, so you can just use it
4.2, write
var m sync_map.Map
m.Store("key1", "val1")
-------------
-------------
start =======>> sync.Map:
read(amendend=true):
dirty:
"key1": &sync_map.entry{p:(unsafe.Pointer)(0xc000098740)}
misses:0
expunged:0xc0000981e0
end <<======= sync.Map
Copy the codeAmendend’s value changes to true, and the newly written data exists in dirty.
4.3 Dirty Map Data Promoted to Read Map
var m sync_map.Map m.Store("key1", "Val1") m.L oad (" key "), / / the load any key -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - start = = = = = = = > > sync. The Map: read (amendend = false) : "key1" : &sync_map.entry{p:(unsafe.Pointer)(0xc000098740)} dirty: misses:0 expunged:0xc0000981e0 end <<======= sync.MapCopy the codeMissLocked () logic is triggered because the key does not exist in the Read map during load and may exist in the Dirty Map. When misses>=len(dirty map), promote.
4.4. Copy data from read map to Dirty Map
var m sync_map.Map
m.Store("key1", "val1")
m.Store("key2", "val2")
m.Load("key2")
m.Load("key2") // promote
m.Delete("key1") // delete
m.Store("key3", "val3") // copy to dirty
-------------
-------------
start =======>> sync.Map:
read(amendend=true):
"key1": &sync_map.entry{p:(unsafe.Pointer)(0xc000012200)} //delete
"key2": &sync_map.entry{p:(unsafe.Pointer)(0xc000012780)}
dirty:
"key2": &sync_map.entry{p:(unsafe.Pointer)(0xc000012780)}
"key3": &sync_map.entry{p:(unsafe.Pointer)(0xc0000127c0)}
misses:0
expunged:0xc000012200
end <<======= sync.Map
Copy the codeAs key2 is added, undeleted data from read is added to the dirty map through dirtyLocked(). On the next Promoted day, deleted keys in read Map will be reclaimed (memory pointed by old Read will be GC).
4.5, update,
1. When data exists only in the Read Map, only the value in the Read Map is updated.
2. Read Map and Dirty Map are updated when unpromoted.
4.6, delete,
1. When data exists only in read Map
var m sync_map.Map
m.Store("key1", "val1")
m.Store("key2", "val2")
m.Load("key1")
m.Load("key1")
m.Delete("key1")
m.Print()
-------------
-------------
start =======>> sync.Map:
read(amendend=false):
"key1": &sync_map.entry{p:(unsafe.Pointer)(nil)}
"key2": &sync_map.entry{p:(unsafe.Pointer)(0xc000100760)}
dirty:
misses:0
expunged:0xc0001001e0
end <<======= sync.Map
Copy the codeRead map does not remove keys, only sets value to nil
2. When keys only exist in a dirty map
var m sync_map.Map
m.Store("key1", "val1")
m.Store("key2", "val2")
m.Load("key1")
m.Load("key1")
m.Store("key3", "val3")
m.Delete("key3")
-------------
-------------
start =======>> sync.Map:
read(amendend=true):
"key1": &sync_map.entry{p:(unsafe.Pointer)(0xc000012760)}
"key2": &sync_map.entry{p:(unsafe.Pointer)(0xc000012780)}
dirty:
"key1": &sync_map.entry{p:(unsafe.Pointer)(0xc000012760)}
"key2": &sync_map.entry{p:(unsafe.Pointer)(0xc000012780)}
misses:0
expunged:0xc000012200
end <<======= sync.Map
Copy the codeThere is no data in the Read Map, so there is no processing; Data in dirty maps is deleted in map.delete mode.
3. If a key exists in both a Read map and a dirty map
var m sync_map.Map
m.Store("key1", "val1")
m.Store("key2", "val2")
m.Load("key2")
m.Load("key2")
m.Delete("key1")
m.Store("key3", "val3")
m.Delete("key2")
-------------
-------------
start =======>> sync.Map:
read(amendend=true):
"key1": &sync_map.entry{p:(unsafe.Pointer)(0xc0000981e0)}
"key2": &sync_map.entry{p:(unsafe.Pointer)(nil)}
dirty:
"key3": &sync_map.entry{p:(unsafe.Pointer)(0xc0000987a0)}
"key2": &sync_map.entry{p:(unsafe.Pointer)(nil)}
misses:0
expunged:0xc0000981e0
end <<======= sync.Map
Copy the codeBoth Read and Dirty maps set value to nil. Note that there is no delete call to the dirty map.
In this case, key2 cannot be deleted after promoted and still exists in Read Map. Only when other keys are added, key2 will be set as a sentinel and then deleted after the second Promoted.
reference
Juejin. Cn/post / 684490… Mp.weixin.qq.com/s/rsDC-6paC… Mp.weixin.qq.com/s/8aufz1IzE… Mp.weixin.qq.com/s/s-JbeVsym…