Sync.map is like a native Map in Go, but thread-safe in multiple goroutines without locking or coordination. Load, store and delete run at amortized fixed times.

The Map type is optimized for two common use cases :(1) entries for a given key are written only once but read multiple times (such as only in caches within caches), or (2) entries for disjoint key sets are written and overwritten when multiple goroutines are reading. In both cases, using sync.map can significantly reduce lock contention compared to Mutex alone or RWMutex paired with Go Map. A Map cannot be copied after it is used for the first time.


type Map struct {
	mu Mutex

	// read contains the portion of the map// Contents that are safe for // concurrent access (with or without mu held). // The read contains portions of map contents that can be accessed concurrently The field itself is always safe to load, but must only be stored with // mu held. However, locks must be used when loading. // Entries stored in read may be updated without mu, but updating // a previously-expunged entry requires that the entry be copied to the dirty // map and unexpunged with mu Held. // It is possible to simultaneously update an entry stored as read without mu, // but updating a previously deleted entry requires that the entry be copied to the dirty map and not deleted without preserving MU. Read atomic.Value // readOnly // Dirty contains the contents of maps that need mu protection. To ensure that dirty maps can be quickly promoted to read maps, it also includes all undeleted entries in the read // map. // dirty contains the portion of the map's contents that require mu to be
	// held. To ensure that the dirty map can be promoted to the read map quickly,
	// it also includes all of the non-expunged entries in the read// The deleted entries do not exist in the dirty map. // The deleted entries in the map must be cleaned and added to the dirty map before the new value can be stored in the dirty map. // Expunged entries are not storedin the dirty map. An expunged entry inThe // clean map must be unexpunged and added to the dirty map before a new value // can be stored to it. The next write to the map initializes it by creating a shallow copy of the clean map and ignoring the stale entries. // If the dirty map is nil, the next write to the map will initialize it by // making a shallow copy of the clean map, omitting stale entries. dirty map[interface{}]*entry // misses counts the number of loads since thereadMap was last updated that // needed to lock mu to determine whether the key was presentread// Once enough misses have occurred to cover the cost of copying the dirty // map the dirty map will be promoted to theread map (inThe unamended // state) and the next store to the map will make a new dirty copyreadMap, when there is a store, re-generate a dirty map misses int} //readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
	m       map[interface{}]*entry
	amended bool // true if the dirty map contains some key not in m.
}

// expunged is an arbitrary pointer that marks entries whichVar expunged = unsafe.Pointer(new(interface{})) // An entry is a slotin the map corresponding to a particular key.
type entry struct {
	// p points to the interface{} value stored forthe entry. // // If p == nil, the entry has been deleted and m.dirty == nil. // // If p == expunged, the entry has been deleted, m.dirty ! = nil, and the entry // is missing from m.dirty. // // Otherwise, the entry is valid and recordedin m.read.m[key] and, ifm.dirty // ! = nil,in m.dirty[key].
	//
	// An entry can be deleted by atomic replacement with nil: when m.dirty is
	// next created, it will atomically replace nil with expunged and leave
	// m.dirty[key] unset.
	//
	// An entry's associated value can be updated by atomic replacement, provided
	// p != expunged. If p == expunged, an entry's associated value can be updated
	// only after first setting m.dirty[key] = e so that lookups using the dirty
	// map find the entry.
	p unsafe.Pointer // *interface{}
}

func newEntry(i interface{}) *entry {
	return &entry{p: unsafe.Pointer(&i)}
}
Copy the code

The read native dictionary can be viewed as a snapshot that will always re-save all key-value pairs contained in the sync.map value when the condition is met. The read dictionary does not add or subtract keys, but it does allow you to change the values of the keys. Therefore, it is not a snapshot in the traditional sense, its read-only nature is only for the set of keys in it.

The dirty field represents a native dictionary that stores key-value pairs in the same way as the native dictionary in the read field, has the same key type interface{}, and also converts and encapsulates values before storing them. Let’s call it a dirty dictionary.

Note that if both the dirty dictionary and the read-only dictionary have the same key-value pair, then the two keys must refer to the same base value, even for both values.

As mentioned earlier, both dictionaries store keys and values with only a pointer to them, not the base value.

Sync.map always searches a read-only dictionary for the value of a given key without locking the mutex. It will only access the dirty dictionary protected by the lock if it determines that “the read-only dictionary does not have this key, but the dirty dictionary may have this key.”

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	m.mu.Lock()
	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.
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		e.storeLocked(&value)
	} else {
		if! read.amended { // We're adding the first new key to the dirty map. // Make sure it is allocated and mark the read-only map as incomplete. m.dirtyLocked() m.read.Store(readOnly{m: read.m, amended: true}) } m.dirty[key] = newEntry(value) } m.mu.Unlock() }Copy the code

Sync.map, on the other hand, stores key-value pairs and returns them as long as the key is already in the read-only dictionary and the pair is not marked “deleted,” in which case locking is not required. Otherwise, it stores key-value pairs in a dirty dictionary under the protection of a lock. At this point, the “deleted” flag for the key-value pair is erased.

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 code

Incidentally, only when a key-value pair should be deleted, but still exists in a read-only dictionary, will it be logically deleted by marking it “deleted”, not physically deleted directly.

// Delete deletes the value for a key.
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()
	}
}

func (e *entry) delete() (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 code

This will happen some time after the dirty dictionary is rebuilt. But it won’t be long before they are actually deleted.

Key-value pairs that have been logically removed are always ignored when they are found and traversed. To delete key-value pairs, sync.map first checks to see if there is a key in the read-only dictionary. If it doesn’t, as it probably does in the dirty dictionary, it tries to delete it from the dirty dictionary under the protection of the lock.

Finally, sync.map sets the pointer to the value in the key-value pair to nil, which is another logical deletion.

In addition, there is another detail to note that read-only dictionaries and dirty dictionaries are converted to each other.

func (m *Map) missLocked() {
	m.misses++
	if m.misses < len(m.dirty) {
		return
	}
	m.read.Store(readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}
Copy the code

When enough key-value pairs are looked up in the dirty dictionary, sync.map stores the dirty dictionary directly as a read-only dictionary in its read field, and sets the value of the dirty field representing the dirty dictionary to nil.

After that, as soon as new key-value pairs are saved, it will rebuild the dirty dictionary from the read-only dictionary. At this point, it filters out the key-value pairs in the read-only dictionary that have been logically deleted. Of course, these conversions must be protected by locks.

In summary, the set of key-value pairs in sync.map’s read-only dictionary and dirty dictionary are not synchronized in real time, and they may differ over certain periods of time.

Because the set of keys in a read-only dictionary cannot be changed, the key-value pairs may sometimes be incomplete.

In contrast, the set of key-value pairs in a dirty dictionary is always complete and does not contain key-value pairs that have been logically removed.

Therefore, it can be seen that concurrency safe dictionaries tend to perform better when there are many reads but few writes.

Of the write operations, adding key-value pairs has the greatest impact on concurrent safe dictionary performance,

The second is delete,

The last step is the modification.

If the key-value pair being operated on already exists in the read-only dictionary of sync.map and has not been logically deleted, modifying it does not use a lock and has little impact on its performance.

Content Source:

  • Some of the content is excerpted from Mr. Hollin’s Geek Hour