34 Concurrent Safe Dictionary sync #

In the previous discussions, I have covered almost all the built-in synchronization tools in Go language. Have you understood and started using them?

Regardless, I hope you can practice and use them more. They are not conflicting with Go’s unique concurrency programming style. On the contrary, if used together, they can definitely achieve a “one plus one is greater than two” effect.

Of course, how to combine them is a subject of study. I have already discussed many methods and techniques, but there may be more things that you need to gradually comprehend and summarize in practice.

Today we will discuss another advanced concurrent safe data structure: sync.Map. As we all know, the built-in dictionary type map in Go language is not concurrent safe.

Background Knowledge: The Birth of Concurrency-Safe Dictionary #

In other words, it is not safe to read and write to the same dictionary in different goroutines at the same time. The values in the dictionary itself may become chaotic due to these operations, and the related program may also encounter unpredictable problems.

Before the appearance of sync.Map, if we wanted to implement a concurrency-safe dictionary, we had to do it ourselves. However, this is not a difficult task. We can easily achieve it by using sync.Mutex or sync.RWMutex, along with the native map.

There are already many libraries on GitHub that provide similar data structures. I also provided a fairly complete implementation of a concurrency-safe dictionary in the second edition of “Go Concurrency in Practice”. Its performance is better than other similar data structures because it largely avoids reliance on locks.

Although there are already many reference implementations, Go enthusiasts still hope that the Go language officials can release a standard concurrency-safe dictionary.

After many years of suggestions and complaints, the Go language officials finally officially introduced the concurrency-safe dictionary type sync.Map in Go 1.9, which was released in 2017.

This dictionary type provides some commonly used key-value storage and retrieval methods, and guarantees the concurrency safety of these operations. At the same time, the storage, retrieval, deletion, and other operations can be completed in constant time. In other words, their algorithm complexity is also O(1), just like the map type.

In some cases, using sync.Map can significantly reduce lock contention compared to using the native map and mutex solution. Although sync.Map also uses locks internally, it actually tries to avoid using locks as much as possible.

As we all know, using locks means forcing some concurrent operations to be serialized. This often reduces the performance of the program, especially when the computer has multiple CPU cores.

Therefore, we often say that if atomic operations can be used, locks should not be used. However, this has limitations because atomic operations can only support some basic data types.

Regardless of the scenario in which sync.Map is used, we need to pay attention to the fact that, unlike the native map, it is only a member of the Go standard library and not a language-level feature. This is precisely why the Go compiler does not perform special type checking on its keys and values.

If you have read the documentation of sync.Map or have actually used it, then you will know that all the methods involved in it have interface{} types for both keys and values, which means they can be of any type. Therefore, we must ensure the correctness of their key and value types in the program on our own.

Well, now the first question comes. Today’s question is: Does the concurrency-safe dictionary have any requirements on the type of keys?

The typical answer to this question is: Yes, there are requirements. The actual type of the key cannot be a function type, dictionary type, or slice type.

Let’s analyze this question. As we all know, the key type of the native Go dictionary cannot be a function type, dictionary type, or slice type.

Since the underlying storage medium used in the concurrency-safe dictionary is the native dictionary, and because the key type used by it is the all-encompassing interface{}, we absolutely cannot operate the concurrency-safe dictionary with key-value pairs whose actual types are function types, dictionary types, or slice types.

Since the actual types of these key-value pairs can only be determined during program execution, the Go language compiler is unable to check them during compilation, and operating with incorrect actual key-value types will definitely cause a panic.

Therefore, the first thing we need to do here is: never violate the above rules. We should explicitly check the actual types of the key-value pairs every time we operate the concurrency-safe dictionary, whether it is storage, retrieval, or deletion.

Of course, a better approach is to consolidate these operations on the same concurrency-safe dictionary and write the checking code in a unified manner. In addition, encapsulating the concurrency-safe dictionary in a struct type is often a good choice.

In summary, we must ensure that the key type is comparable (or in other words, hashable). If you are unsure, you can first use the reflect.TypeOf function to get a reflection type value corresponding to a key-value pair (i.e., a value of type reflect.Type), and then call the Comparable method of this value to get the exact judgment result.

Knowledge Expansion #

Question 1: How can we ensure the correctness of the types of keys and values in a concurrent-safe dictionary? (Solution 1) #

Simply put, we can use type assertion expressions or reflection operations to ensure the correctness of their types.

To further clarify the actual types of keys and values in a concurrent-safe dictionary, there are roughly two options.

The first option is to allow the concurrent-safe dictionary to only store keys of a specific type.

For example, specify that the keys can only be of type int, or only strings, or a certain type of structure. Once the type of the key is fully determined, you can use type assertion expressions to check the type when performing storage, retrieval, or deletion operations.

In general, this check is not cumbersome. Moreover, if you encapsulate the concurrent-safe dictionary in a struct type, it will be even more convenient. At this point, you can rely on the Go compiler to assist in type checking. Please refer to the code below:

type IntStrMap struct {
	m sync.Map
}

func (iMap *IntStrMap) Delete(key int) {
	iMap.m.Delete(key)
}

func (iMap *IntStrMap) Load(key int) (value string, ok bool) {
	v, ok := iMap.m.Load(key)
	if v != nil {
		value = v.(string)
	}
	return
}

func (iMap *IntStrMap) LoadOrStore(key int, value string) (actual string, loaded bool) {
	a, loaded := iMap.m.LoadOrStore(key, value)
	actual = a.(string)
	return
}

func (iMap *IntStrMap) Range(f func(key int, value string) bool) {
	f1 := func(key, value interface{}) bool {
		return f(key.(int), value.(string))
	}
	iMap.m.Range(f1)
}

func (iMap *IntStrMap) Store(key int, value string) {
	iMap.m.Store(key, value)
}

As shown above, I created a struct type called IntStrMap, which represents a concurrent-safe dictionary with keys of type int and values of type string. In this struct type, there is only one field m of type sync.Map. Additionally, all the methods this type has are very similar to the methods of sync.Map type.

The names of the corresponding methods are exactly the same, and the method signatures are very similar, except that the types of the parameters and return values related to the keys and values are different. In the method signatures of IntStrMap type, the type of the key is specified as int, and the type of the value is specified as string.

Obviously, these methods do not need to perform type checks when accepting keys and values. Furthermore, when retrieving keys and values from m, there is no need to worry about their types being incorrect, because their correctness has already been guaranteed by the Go compiler when they were stored.

To summarize briefly, the first solution is suitable when we can completely determine the specific types of the keys and values. In this case, we can use the Go compiler to perform type checking and use type assertion expressions as assistance, just like in IntStrMap.

Summary #

Today we discussed the sync.Map type, which is a concurrent-safe dictionary. It provides common methods for key-value access and ensures their concurrency safety. It also guarantees constant execution time for operations like storing, retrieving, and deleting.

Similar to native dictionaries, concurrent-safe dictionaries also have requirements for the key type. They cannot be function types, dictionary types, or slice types.

Additionally, since the methods provided by concurrent-safe dictionaries involve the types of keys and values as interface{}, we often need to check the actual types of keys and values when calling these methods.

There are roughly two solutions to this. Today we mainly discussed the first solution, which is to completely determine the types of keys and values at coding time and rely on the Go language compiler to perform the checks.

In the next article, we will mention another solution and compare the advantages and disadvantages of these two solutions. Besides, I will continue to explore related issues of concurrent-safe dictionaries.

Thank you for your attention, see you next time.

Click here to view the detailed code accompanying the Go language column article.