Guide language | in recall ordering business, because of the large amount of upstream request, cause great pressure to the downstream storage service, business scenarios require high performance and the strong consistency, so I use golang concurrent security k – v open source library cache performance tuning, the following is a research, comparison and analysis on it. If there are any mistakes, please correct them.

A, Golang map

(1) Concurrent reading and writing test

In Golang, the native map is thread unsafe to read and write simultaneously in concurrent scenarios, regardless of whether the key is the same or not. Here is the test code:

package main
import "time"
func main() {  testMapReadWriteDiffKey()}
func testMapReadWriteDiffKey() {  m := make(map[int]int)  go func() {    for {      m[100] = 100    }  }()  go func() {    for {      _ = m[12]    }  }()  select {}
}
Copy the code

As shown in the demo above, read and write different keys to the map concurrently. The result is as follows:

The map reads the hashWriting flag and reports a concurrency error if it has one. Write will be set on the sign: h.f lags | = hashWriting. This flag will be cancelled when it is set. Map concurrency problems are not so easy to spot and can be checked with the -race parameter. The map concurrent read/write conflict detection mechanism is not the focus of this article, but interested students can learn more about it through the following links.

Related article analysis: medium.com/a-journey-w…

The compile-time option -race, for how concurrency problems can be analyzed, see:

Go.dev /blog/race-d…

Article analysis: medium.com/@blanchon.v…

Video explanation: www.youtube.com/watch?v=5er…

Map + read/write lock

Before the official library sync.map is available, Go Maps in Action recommends using map+RWLock. For example, define an anonymous struct variable that contains map and RWLock, as shown below:

var counter = struct{   
sync.RWMutex   
m map[string]int
}{m: make(map[string]int)}
Copy the code

You can read data from counter like this

counter.RLock()n 
:= counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)
Copy the code

You can write data to counter like this

counter.Lock()
counter.m["some_key"]++
counter.Unlock()
Copy the code

What’s the difference between the Go 1.9 implementation of Sync.map and this one? What scenarios does it apply to? Where is it optimized for performance?

Second, sync. The map

Sync.map is implemented with read/write separation, with the idea of space for time. Compared to the map+RWLock implementation, it makes some optimizations: Read map can be accessed without lock, and read Map is preferred. If only read Map can satisfy the requirement (add, delete, change, search and iterate), then write Map is not required (lock both read and write). So in certain scenarios, lock contention will occur much less frequently than map+RWLock implementation.

Let’s take a look at the source code for Sync.map to see how it works.

Sync.map source: github.com/golang/go/b…

(I) Introduction of variables

  • Structure Map

Type Map struct {// Mutex, Mutex, Mutex, Mutex, Mutex, Mutex, Mutex, Mutex, Mutex, Mutex, Mutex ReadOnly contains real data --entry (see 1.3). Read is a subset of dirty. Read atomic.Value // readOnly // Dirty is a data structure that can be read and written at the same time. Access to it is locked, and new keys are placed in dirty first. 2. Promoted to read, but it cannot remain nil, otherwise read and dirty will be inconsistent. // When a new key is present, the data in read (not all of the data in read, but the data not marked as deleted, see 3.2) will be populated with dirty // dirty! Dirty map[interface{}]*entry // Count the number of accesses to dirty that have not been missed and then passed through // When miss is equal to the number of misses on the dirty list, the number of misses on the dirty list goes up to read. When miss is equal to the number of misses on the dirty list, the number of misses on the dirty list goes up to read.Copy the code

  • Structure readOnly

type readOnly struct {  
m       map[interface{}]*entry  
amended bool 
}
Copy the code

For instance, if the number of entries in the dirty is changed to true, it shall be amended to true or true. For instance, if the number of entries in the dirty is changed to true or true, it shall be amended to true or true.

  • Structure entry

Type entry struct {// p == nil: entry deleted from readOnly but in dirty // p == expunged: Entry deleted from Map and not in dirty // p == other values: // *interface{}}Copy the code

The pointer P in entry points to the address where the real value is. Dirty and readonly. m store values of type *entry. What do nil and expunged do here? Just nil doesn’t work? These questions will be addressed later.

(2) Function introduction

Here are the four methods of sync.map: Load, Store, Delete, and Range

  • The Load method

  • The illustration

  • Source code analysis

The Load method is used to Load the values in sync.map. The input parameter is key, and the return value is the corresponding value and whether the value exists

Func (m *Map) Load(key interface{}) (value interface{}, ok bool) { Read, _ := m.reade.load ().(readOnly) e, ok := read.m[key] // This key does not exist in readOnly but map.dirty may exist if! {// Count map.dirty m.m.lock (); {// Count map.dirty m.m.lock (); {// Count m.read.Load(); Read, _ = m.read.load ().(readOnly) e, ok = read. M [key] // read. Ok && read. Amended {// To obtain the corresponding entry e of the key from the dirty, OK = m.dirty[key] // Miss shall be incremented whether the key is present in map. dirty or not, or if miss is equal to the length of the dirty, Dirty elements are // added to map.read m.isslocked ()} m.u.nlock ()} if! Ok {return nil, false} // If entry.p is deleted (equal to nil or expunged) return nil and does not exist (false), otherwise return the corresponding value and does exist (true) return e.lloyd ()}Copy the code

How did map.dirty get promoted to map.read? Let’s take a look at missLocked

Func (m *Map) missLocked() {// Access to map.dirty, When m.counts ++ if m.counts < len(m.dirty) {return} // When the number of misses is equal to the length of the dirty, m.dirty is raised to readOnly, Amended by default to false m.read.Store(readOnly{m: m.read}) m.read = nil m.misses = 0}Copy the code

Summary:

  • The Load method preferentially accesses readOnly without locks, and locks map. dirty if the data may exist in map. dirty.

  • The Load method incurs additional overhead by locking access to map. dirty if it accesses keys that are not present in readOnly but are present in dirty.

  • Store method

  • The illustration

  • The source code parsing

The Store method adds new keys and values to a Map or updates values

Func (m *Map) Store(key, value interface{}) { _ := m.reade.load ().(readOnly) // If the key is in readOnly. M and entry.p is not expunged (not marked as deleted), the key exists in both readOnly If e, ok := read.m[key]; if e, ok := read.m[key]; Ok && e.store (&value) {return} // Key does not exist in readonly. m or entry.p==expunged(entry marked as deleted), lock access to dirty m.u.lock () // double check: If map. dirty is promoted to readOnly before locking, the previous read. M [key] may be invalid. Read, _ = m.read.Load().(readOnly) if e, ok := read. M [key]; Ok {// entry.p was expunged and set it to nil if e.unexpungelocked () {// There was no such key in the dirty before, // Update (assign the address of value to the pointer entry.p) e.store locked (&value) // If key is in the dirty} else if e, ok := m.dirty[key]; Ok {// update (assign the address of value to the pointer entry.p) e.strelocked (&value) // a new key is coming in} else {// There is no new data in the dirty, add the first new key to the dirty if! Read. Amended {// Copy the data in readOnly that is not marked for deletion to m.dirtylocked () // differentiate :true, Read.Store(readOnly{m: read. M, amended: True})} // add this newEntry to dirty.Copy the code
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 } }}Copy the code
func (e *entry) unexpungeLocked() (wasExpunged bool) {  return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}
Copy the code
func (m *Map) dirtyLocked() { if m.dirty ! = nil {// If dirtyLocked is called, dirty must be nil return} Dirty read, _ := m.read.load ().(readOnly) m.dirty = make(map[interface{}]*entry, Len (read.m)) for k, e := range read.m {// tryExpungeLocked (e.p!=expunged&&e.p!) // e.p==nil sets it to expunged and returns true if! E.treexpungelocked () {m.dirty[k] = e // Entry is not deleted, add it to dirty}}}Copy the code

Summary:

  • The Store method gives priority to the unlocked access to readOnly.

  • The double detection mechanism used in the Store method is used in the Load, Delete, and Range methods. The reason is that map. dirty may have been promoted to map. read before the lock, so the key must be checked again to see if it exists in map. read.

  • DirtyLocked methods copy data from readOnly when dirty is nil (when it has just been promoted to readOnly or when a Map is initialized), and may occasionally experience performance jitter if readOnly is very large.

  • Sync. map is not suitable for scenarios where new key-values are frequently inserted, because this operation frequently locks access to dirty, resulting in performance degradation. Update operations use lock-free CAS for performance optimization in scenarios where the key exists in readOnly and the value is not marked as expunged, otherwise access dirty is locked.

  • The Delete method

  • The illustration

  • The source code parsing

The Delete method deletes the key from the Map and returns the value that was deleted and whether it was successfully deleted. Its underlying call is LoadAndDelete

Func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) { Read, _ := m.read.load ().(readOnly) e, ok := read.m[key] // readOnly This key does not exist, but if! {// It is necessary to differentiate {// it is necessary to differentiate {// it is necessary to differentiate {// it is necessary to differentiate {// it is necessary to differentiate {// it is necessary to differentiate {// It is necessary to differentiate {// It is necessary to differentiate {// It is necessary to differentiate {// It is necessary to differentiate { Read, _ = m.read.load ().(readOnly) e, ok = read. M [key] // readOnly Does not have this key, but if! ok && read.amended { e, ok = m.dirty[key] delete(m.dirty, Key) m.isslocked ()} m.u.nlock ()} if ok {// If entry.p is not nil or expunged, Return e.dele ()} return nil, false}Copy the code
func (e *entry) delete() (value interface{}, Ok bool) for {{p: = atomic LoadPointer (& e.p) if p = = nil | | p = = expunged {return nil, false} / / e.p's true value, Put it to nil if atomic.Com pareAndSwapPointer (& e.p, p, nil) {return * (* interface {}) (p), true}}}Copy the code

Summary:

  • Delete keys that exist in readOnly without locking.

  • If you delete a key that does not exist in readOnly or Map, you need to lock it.

  • Range method

  • The illustration

  • The source code parsing

The Range method traverses the Map and takes a function (key and value, return value: whether to stop traversing the Range method).

func (m *Map) Range(f func(key, value interface{}) bool) { read, _ := M.read.load ().(readOnly) if read. Amended {// Dirty exists elements that do not exist in readOnly // lock access to dirty M.u.lock () // Detect read. Because it might have changed from true to false read before the lock, _ = m.read.Load().(readOnly) if read. Amended {// readOnly. M for k, e := range read. M {v, e := range read. M {v, ok := e.load() if ! ok { continue } if ! f(k, v) { break } } }Copy the code

Summary:

  • When all keys of the Map of the Range method are present in readOnly, it is lockless and performs best.

  • When readOnly contains only some keys in the Map, the Range method copies the dirty elements to readOnly at one time, reducing the number of times the lock is used to access the dirty data.

(c) Summary of Sync.map

  • Usage scenarios

Sync.map is more suitable for scenarios where many reads and updates are performed and few new values are inserted (appendOnly mode, especially when the key is stored once and read many times without being deleted) because read/write operations without locking readOnly is not suitable for scenarios where repeated insertions and readings of new values are performed. Because this scenario involves frequent dirty operations, it requires frequent locking and updating of read.

  • Design point: expunged

Entry. p can be nil, expunged, or pointing to a true value. When does expunged appear? Why expunged design? What does it do?

  • When will expunged appear?

When a new key is inserted using the Store method, it locks access to the dirty and copies all entry Pointers in readOnly that are not marked as deleted to the dirty, and all entries previously marked as soft deleted by the Delete method (entry.p set to nil) become expunged. Entries marked expunged will not appear in the dirty.

  • Inversely, what happens if there’s no expunged, just nil?

  • Delete entry==nil instead of expunged: When inserting a new key using the Store method, copy the readOnly data to the dirty and delete the NI entry directly. However, this locks readOnly, and sync.map is designed with read-write separation in mind, so access to readOnly cannot be locked.

  • Do not delete entry==nil, copy all: When inserting a new key using Store, copy all data in readOnly where entry. P is nil to dirty. After the dirty data is readOnly, the deleted dirty data will remain, meaning that it will never be cleaned up, taking up more and more memory.

  • Do not copy entry.p==nil elements: When a new key is inserted into the dirty file using the Store method, the data entry. P nil in readOnly is not copied to the dirty file. When the value is updated with the Store method, the state of readOnly and dirty is not synchronized, that is, there are keys in the readOnly file that are not in the dirty file. Data loss will occur when dirty is promoted to readOnly.

(4) Other problems with Sync.map

Why doesn’t Sync.map implement the Len method? Personally, it’s a trade-off between costs and benefits.

  • Implementing len to count readOnly and dirty data will inevitably introduce lock contention, resulting in performance degradation and additional code implementation complexity.

  • The data volume of sync.map can change rapidly due to concurrent operations on it, and the statistical results of len method are of little reference value.

Third, orcanman/concurrent – map

Orcaman/concurrent-Map is applicable to the scenario where new values are repeatedly inserted and read. The implementation idea is as follows: Fragment and lock the Go native map to reduce the lock granularity and minimize the lock wait time (lock conflict).

Concurrent-map source code: github.com/orcaman/con…

Its implementation is relatively simple, intercept part of the source code is as follows:

(1) Data structure

// SHARD_COUNT Fragment size var SHARD_COUNT = 32 type ConcurrentMap []*ConcurrentMapShared // ConcurrentMapShared concurrent mapType ConcurrentMapShared struct {items map[string]interface{} sync.RWMutex // Create a concurrent struct {items map[string]interface{} sync.RWMutex // create a concurrent struct map.func New() ConcurrentMap { m := make(ConcurrentMap, SHARD_COUNT) for i := 0; i < SHARD_COUNT; i++ { m[i] = &ConcurrentMapShared{items: make(map[string]interface{})} } return m}Copy the code

( Two) Function introduction

  • The GET method

// Hash the partition number corresponding to the key, then lock, read the value, Func (m ConcurrentMap) Get(key string) (interface{}, bool) { // Get shard shard := m.GetShard(key) shard.RLock() // Get item from shard. val, ok := shard.items[key] shard.RUnlock() return val, ok}Copy the code

  • SET method

// Hash the partition number corresponding to the key, then lock it, set the new value, Func (m ConcurrentMap) Set(key string, value interface{}) { // Get map shard. shard := m.GetShard(key) shard.Lock() shard.items[key] = value shard.Unlock()}Copy the code

  • The Remove method

// Hash the partition number corresponding to the key, then lock it, delete the key, Func (m ConcurrentMap) Remove(key string) {// Try to get shard. Shard := m.gaetshard (key) shard.lock () delete(shard.items, key) shard.Unlock()}Copy the code

  • The Count method

Func (m ConcurrentMap) Count() int {Count := 0 for I := 0; i < SHARD_COUNT; i++ { shard := m[i] shard.RLock() count += len(shard.items) shard.RUnlock() } return count}Copy the code

  • Upsert method

/ / hash to get the key corresponding to the partition number first, then lock, if the key is to update the value, or insert a new k - v, Func (ConcurrentMap) Upsert(key string, value interface{}, cb UpsertCb) (res interface{}) { shard := m.GetShard(key) shard.Lock() v, ok := shard.items[key] res = cb(ok, v, value) shard.items[key] = res shard.Unlock() return res}Copy the code

Four, subsequent

Of course, in other business scenarios, we might need more local KV cache component libraries and require them to support key expiration time Settings, elimination policies, storage optimization, GC optimization, etc. Freecache, GoCache, FastCache, BigCache, Groupcache, etc.

The resources :

1.Golang fatal error: concurrent map read and map write.

2.sync: add Map.Len method?

3.concurrent map. 

Author’s brief introduction

clancyliang

Tencent background development engineer.