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

This article shows you how to understand the sync.Map in Go. The content is concise and easy to understand. It will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

Foundation construction

In most languages, the original map is not a thread-safe data structure, so if you want to change threads in multiple threads or goroutine, you need to add a lock. In addition to adding a big lock, different languages have different optimization ways. Languages such as java and go actually use linked lists to implement map.

Three ways of map implementation of concurrency Security

There are three main ways to implement multiple goroutine concurrency and secure access to modified map in go language:

The principle of implementation is suitable for scenarios where map+Mutex uses Mutex mutexes to realize serialized access of multiple goroutine to map. Locking and releasing locks are required for both reading and writing of multiple goroutine. When the ratio of reading to writing is close, map+RWMutex uses RWMutex to separate locks and locks for reading and writing of map. Thus, the concurrency performance of reading is improved compared with Mutex. Compared with Mutex, it is suitable for scenarios where there are more reads and less writes. Sync.Map separates read and write map and atomic instructions to achieve approximately lock-free reading. And by delaying the update to ensure that there are more unlocked reads, less modification, less frequent deletion of elements, replacing the above two implementations in most cases.

The specific performance differences of the above three implementations may have to be comprehensively tested for different specific business scenarios, platforms, data volumes, etc., and the learning of the source code is more about the details of their implementation. so that when there is a performance bottleneck, we can analyze and find a solution.

Capacity problem of map

In the concurrent security map implemented by Mutex and RWMutex, the capacity of map increases continuously with the increase and deletion of time and the number of elements. In some cases, such as frequent increase of a large amount of data at a certain point in time, and then a large number of deletions, the capacity of the map does not decrease with the deletion of elements, while in sync.Map, when the element is upgraded from dirty to read map, it will be rebuilt and may be scaled down.

Unlocked reading and separation of reading and writing

Separation of reading and writing

In fact, the main problem with concurrent access map reading is that when the capacity is expanded, it may cause elements to be hash to other addresses, so if the map I read does not expand the capacity, I can access concurrency securely. This method is adopted in sync.map to save the added elements through dirty.

Unlocked reading

The operation is separated by read read-only and dirty write map. In fact, it is only necessary to read the read map through atomic instructions without locking, thus improving the read performance.

Write locking and delayed lifting

Write lock

It is mentioned above that the operation of adding elements may first increase the number of dirty writes in map. For multiple goroutine writes at the same time, Mutex locking is actually required.

Delayed lifting

If read read-only map and dirty write map are mentioned above, there will be a problem. By default, additional elements are placed in dirty. If subsequent access to new elements is locked through mutex, then read read-only map is meaningless. Sync.Map adopts the strategy of delaying promotion all the time to batch promote all elements in the current map to read read-only map, thus providing lock-free support for subsequent read-only access.

Pointer and lazy deletion

Pointers in map

Storing data in map involves a problem, that is, whether to store a value or a pointer. The stored value allows map to be a large object, reducing the pressure of garbage collection (avoiding scanning all small objects), while storing pointers can reduce memory utilization. In fact, pointers combined with lazy deletion are used in sync.Map to store map's value.

Lazy deletion

Lazy deletion is a common design in concurrent design, such as deleting a linked list element. If you want to delete a linked list element, you need to modify the pointer before and after the element. If you delete it, you usually only need to set a flag bit to delete, and then operate in subsequent modifications. This method is also used in sync.Map, by giving the pointer to a pointer that identifies deletion to achieve lazy deletion.

Source code analysis data structure analysis Maptype Map struct {mu Mutex / / read is a pointer to readOnly, which contains a map structure, that is, the access of read-only map to the elements of the map does not need to be locked, just load the latest pointer through atomic to read atomic.Value / / readOnly / / dirty contains some key-value pairs of map If you want to access the mutex fetch / / all the elements in the dirty will be promoted to the map in the read dirty map [interface {}] * entry / / misses is a counter used to record the number of times that data has not been loaded into the read / / attempted to fetch from the dirty, thus determining the timing of data migration from dirty to read misses int} readOnly

Read-only map, the access to the map element does not need to be locked, but the map will not add the element. The element will be first added to the dirty and then transferred to the read read-only map. No locking operation is required through the atomic atomic operation.

Type readOnly struct {/ / m contains all read-only data and does not perform any data addition and deletion operations / / but the pointer of entry can be modified because this will not cause the element of map to move m map [interface {}] * entry / / flag bit. If it is true, it indicates that the data of the current read read-only map is incomplete. Dirty map contains some data amended bool} entry.

Entry is a worthy pointer in sync.Map. If the p pointer points to the pointer expunged, it indicates that the element has been deleted, but it will not be deleted from the map immediately. If it is re-assigned before it is deleted, the element will be reused.

Type entry struct {/ / points to the element actually worth posting p unsafe.Pointer / / * interface {}} data storage

2.2.1 element exists read-only map

If the element is stored in a read-only map, you only need to get the entry element and then modify its p pointer to point to the new element. The map will not change because it is operated in place.

Read, _: = m.read.Load (). (readOnly) if e, ok: = read.m [key]; ok & & e.tryStore (& value) {return} element exists in the changed read-only map

If the element is found in the read-only map at this time, it proves that a previous operation triggered the migration from dirty to read map. If the element is found to exist at this time, you can modify the pointer.

Read, _ = m.read.Load (). (readOnly) if e, ok: = read.m [key]; ok {if e.unexpungeLocked () {/ / The entry was previously expunged, which implies that there is a / / non-nil dirty map and this entry is not in it. / / if the key has been deleted before, this place will add the key from the pointer / / deleted before the nil overwrite to the dirty m.dirty [key] = e} / / call atomic for value storage e.storeLocked (& value)} element exists in the dirty map

If the element exists in dirty, just like the read map logic, you only need to modify the pointer of the corresponding element.

} else if e, ok: = m.dirty [key]; ok {/ / if it is already in dirty, it will directly store e.storeLocked (& value)} else {element does not exist before

If the element does not exist in the current Map, it needs to be stored in the dirty map first, and the amended is identified as true, that is, the data in the current read is incomplete, and some of the data is stored in the dirty.

/ / if you are not currently in a modified state, if! read.amended {/ / the newly added key will be added to the dirty map first And proceed with read marked as incomplete / / if dirty is empty, all undeleted data in read will be migrated to m.dirtyLocked () m.read.Store (readOnly {m: read.m, amended: true})} m.dirty [key] = newEntry (value) data migration read map to dirty map

After initializing and migrating all elements to read, dirty defaults to nil elements. If new elements are added, all undeleted data in read map needs to be migrated to dirty first.

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 {if! e.tryExpungeLocked () {m.dirty [k] = e}} dirty to read map

When continuous access from read is penetrated into dirty, a migration from dirty to read is triggered, which means that if our element read / write ratio is relatively small, it will actually lead to frequent migration operations, and the performance may not be as good as that of implementations such as rwmutex.

Func (m * Map) missLocked () {m.missesystems + if m.misses < len (m.dirty) {return} m.read.Store (readOnly {m: m.dirty}) m.dirty = nil m.misses = 0} data load

Read-only without lock

Get the Load data from read first. If you find an element at this time, you can return it directly.

Read, _: = m.read.Load (). (readOnly) e, ok: = read.m [key] locked read read and dirty

After locking, an attempt is made to read from read and dirty, and the misses counter is incremented. If the migration conditions are met, the data will be migrated.

Read, _ = m.read.Load (). (readOnly) e, ok = read.m [key] if! ok & & read.amended {e, ok = m.dirty [key] / / slow migration strategy will be adopted here / / only if misses count = = len (m.dirty) Only then will all the data in dirty be promoted to read m.missLocked ()} data deletion.

Data deletion is divided into two processes. If the data is in read, you can directly modify the pointer that the flag bit of entry points to deletion. If the data in the current read is incomplete, you need to delete elements in dirty. If it exists, you can delete it directly from dirty.

Func (m * Map) Delete (key interface {}) {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 {delete (m.dirty Key)} m.mu.Unlock ()} if ok {e.delete ()}} mutex is read repeatedly with locked read map

Because mutex mutually exclusive is all operations, including dirty map modification, data migration and deletion, if a dirty-to-read operation is already in progress during the m.lock, then the dirty actually has no data after the execution, so repeat the read reading at this time

The above content is how to understand the sync.Map in Go. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

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.