Source code analysis of golang map concurrent read / write problem

map Introduction and problem description

map It's mainly used to store kv data , The bottom layer uses the open chain method to eliminate conflicts hashtable, It has an automatic capacity expansion mechanism . Use map The most convenient thing is that you can O(1) A quick query （ at present slice No query interface is provided , You can only write your own algorithm to determine whether an element exists ）.

map Although easy to use , But it may not apply .

however map There is a very deadly pit , In a concurrent scenario , Concurrent reading / Writing may occur fatal error:concurrent map read and map write Error of , Just beginning to use map At the time of the naive that as long as not the same key Concurrent operation is OK , But it's a reality . There may be no problem when the concurrency is very small during testing （ Just lucky ）, A large amount of concurrency will cause problems .

But not in all scenarios map It's not safe

This is a golang Official documents of , As mentioned above, as long as there is an update operation ,map It's non thread safe , But if the usage scenario is just concurrent reading , Write not involved / Delete operation , So it is concurrency safe .

image.png

Source code analysis

Definition

map head in flags Field , Recorded the current map Some states of , among hashWriting Is to cause concurrent reading and writing map Wrong report “ The culprit ”.

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}

Copy

	// flags
	iterator     = 1 // there may be an iterator using buckets
	oldIterator  = 2 // there may be an iterator using oldbuckets
	hashWriting  = 4 // a goroutine is writing to the map
	sameSizeGrow = 8 // the current map growth is to a new map of the same size

Copy

write in

• towards map The new element in the will eventually call mapassign function , It will be checked before the new operation flags Of hashWriting Whether a is 1, by 1 May be an error .
• After passing the inspection, the position will be set as 1, The tag is currently being written .
• After writing, set the position to 0

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

    ...
    
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	hash := t.hasher(key, uintptr(h.hash0))

	// Set hashWriting after calling t.hasher, since t.hasher may panic,
	// in which case we have not actually done a write.
	h.flags ^= hashWriting

	...
done:
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting

    ...

Copy

Read

The process of reading data is relatively simple , Before reading, determine whether there is a setting , If the verification is passed, the read operation can be performed , The read operation will not be set .

That's why , If one map Initialized ok after , As long as there is no addition, deletion or modification , Read the newspaper incorrectly at the same time .

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	...
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	...
}

Copy

Conclusion

1. After reading the source code , I found it was like a read-write lock , But it doesn't cause any blockage , If there's a problem, it's direct throw.

2. If you do initialize once , Always read concurrently , You can use it boldly map.

Common solutions

1. Self lock read .

2. Use sync.map replace ( I've seen some principles , Locking is implemented when writing data ; Using space for time , Use two hash structures to store Map, There is a layer of cache , Speed up data reading .)

3. Use 2D slice instead of , take key and index Mapping .

# If there is any misunderstanding or misunderstanding ~ Welcome to correct ~~