sync.Map

Let's take a look to sync.Map usage and it's sources.

Far ago in year 2016, GO 1.9 was released with new sync.Map type.

Interface

Following methods are available to work with sync.Map:

Load(key interface{}) (value interface{}, ok bool)
Store(key, value interface{})
Delete(key interface{})
Range(f func(key, value interface{}) bool)
LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)

That covers every map use case — insert, read, delete, iterating. Also there is LoadOrStore bonus method, that allows to set value by key if value is not set before.

To perform iterating there is Range, receiving function that is called on every map element. If that function returns false, iterating is going to be stopped.

When seeing sync.Map name one can imagine that sync.Map is simple map with some sync package features. But actually sync.Map is much more complex. Let's dive into the sources and find out how it works.

Sources

sync.Map struct is looks as below:

type Map struct {
	mu sync.Mutex

	read atomic.Value
	dirty map[interface{}]*entry
	misses int
}

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

read — pointer to readOnly struct. This struct stores part of the data, that is used to read data by a key or to check that there is data behind that key. There is no inserts into read, that's why no mutex is used accessing read.

dirty — a map, that stores other part of elements. It is used to place new elements generally and for read too. In that case mu mutex is used when dirty is accessed.

So sync.Map has two internal maps (read and dirty). By using one map only for reading and second for writing sync.Map trying to avoid using mutex when it is possible. Let's take a look to sync.Map operations.

Reading

At first read is accessed to check if there is a data behind the key. If it is — the data is returned. It is the most simple scenario — to return data from read.

Then dirty is searched — the mu mutex is activated before. misses — counter of access to dirty — is incremented. Important thing — if that counter's value is more that number of element in dirty, elements in dirty will be copied to read, counter will be reset. The copying will happen right after dirty access — mu is activated at that moment.

To avoid extra dirty access, there is amended field in readOnly struct (which is read). amended = true means there is non-empty dirty map in sync.Map.

So, reading from sync.Map is most effective on read only. In this case this reading is equal to simple map (without mutex) reading. If there is only reading from a large map set up before, sync.Map is good in that case.

Updating

At first there is check against read — if there is a data behind the key. If yes — the value is updated by atomic.CompareAndSwap.

If there is no data read by the key, the same reading is performed against dirty. If dirty is not initialized — it will be.

So, updating already existent key is simple, but adding data with new key is complex.

Iterating

Before iterating dirty is copied into read, if dirty stores anything. It is made with mu mutex activated.

Next, there is read iterating — simple map iterating.

Summary

sync.Map is complex struct, generally consisting of two map — one for reading and one for new elements. sync.Map is not only close to map+sync.RWMutex on speed metrics, but also can be the best in the reading case. When there is both reading and updating sync.Map will have element in both read and dirty. In that case sync.Map performs worse than map+sync.RWMutex because of reading from two internal maps. Also there is a counter that needs to be update when accessing dirty.