Golang's built-in type map is not thread-safe. When we use concurrent operations to write to a map, it will trigger a panic.
package main
import (
"fmt"
"sync"
)
func main() {
var m = make(map[string]string,100)
var wait sync.WaitGroup
for i := 0 ;i < 100 ; i ++ {
wait.Add(1)
go func() {
m[fmt.Sprintf("%d",i)] = "test"
wait.Done()
}()
}
wait.Wait()
}
fatal error: concurrent map writes
fatal error: concurrent map writes
goroutine 11 [running]:
runtime.throw(0x10c6370, 0x15)
/usr/local/go/src/runtime/panic.go:608 +0x72 fp=0xc00002cf08 sp=0xc00002ced8 pc=0x1026e52
runtime.mapassign_faststr(0x10a9860, 0xc00006e120, 0xc0000a0010, 0x2, 0x1)
/usr/local/go/src/runtime/map_faststr.go:199 +0x3da fp=0xc00002cf70 sp=0xc00002cf08 pc=0x100fada
main.main.func1(0xc00006e120, 0xc000016078, 0xc000016080)
...
Therefore, when we need to modify the map concurrently, the first method is to use a mutex lock every time we modify the map value, and the second is to directly use Golang's built-in thread-safe map, which is sync.Map.
This article will introduce how sync.Map achieves thread safety from the source code level of sync.Map.
First, let's look at the data structure of sync.Map.
// Map is like a Go map[interface{}]interface{} but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
// Loads, stores, and deletes run in amortized constant time.
//
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a Map or RWMutex.
//
// The zero Map is empty and ready for use. A Map must not be copied after first use.
type Map struct {
mu Mutex
// read contains the portion of the map's contents that are safe for
// concurrent access (with or without mu held).
//
// The read field itself is always safe to load, but must only be stored with
// mu held.
//
// Entries stored in read may be updated concurrently without mu, but updating
// a previously-expunged entry requires that the entry be copied to the dirty
// map and unexpunged with mu held.
read atomic.Value // readOnly
// 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 map.
//
// Expunged entries are not stored in the dirty map. An expunged entry in the
// clean map must be unexpunged and added to the dirty map before a new value
// can be stored to it.
//
// 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 the read map was last updated that
// needed to lock mu to determine the presence of loops.
//
// Once enough misses have occurred to cover the cost of copying the dirty
// map, the dirty map will be promoted to the read map (in the unamended
// state) and the next store to the map will make a new dirty copy.
misses int
}
From the data structure of Map, it is not difficult to find how Map ensures thread safety.
When adding a new value to the Map, it will not be inserted into read, but directly saved in dirty. When reading data from Map,
it will first read data from read. If it is read, it returns directly. If it is not read, it will read from dirty, and update the value of misses. When misses reaches a certain value,
the value of dirty will be assigned to read. (All operations on dirty are locked, which ensures that this class is thread-safe, and because of the existence of read-only, the efficiency of concurrent reading is improved)
// 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.
}
// An entry is a slot in the map corresponding to a particular key.
type entry struct {
// p points to the interface{} value stored for the 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 recorded in m.read.m[key] and, if m.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{}
}
Load
Wait, the provided context for Load implementation and subsequent methods seems to be cut off in the provided text or I need to infer from standard implementation if not fully present. But sticking to the provided text:
The Load method is used to read the value in the Map based on the Key.
// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// Read directly from readonly. If read, return directly. Because it is readonly, no lock is needed.
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// If there is no value in readonly, and there are values in dirty that do not exist in read
if !ok && read.amended {
m.mu.Lock()
// Lock, double check
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// If the key still does not exist in read, and dirty has values that do not exist in read
if !ok && read.amended {
// Check if the key exists in dirty
e, ok = m.dirty[key]
// Regardless of whether the key exists in dirty, increment misses by 1
// When misses reaches a certain value, m.dirty will be promoted to read
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}