In Go, there is a very practical concurrency-safe Map implementation: it was introduced in Go version 1.9. Compared with maps in the standard library, its biggest feature is that it can be read and written safely in concurrency without locking. In this blog, we will dig into the basics of to help readers better understand and use this concurrently secure map.
1. Basic implementation principle of Map
Before introducing the basic implementation principles, we need to understand the map implementation principles in the Go language standard library. In Go, maps are implemented based on hash tables. When we add an element to the map, it calculates a hash value based on the key and maps this value to a bucket. If there are elements in the bucket, it will iterate over the elements in the bucket to find whether the same key already exists. If it exists, update the corresponding value, otherwise add a new key-value pair.
Here is a simple map example:
m := make(map[string]int) m["a"] = 1 m["b"] = 2 (m["a"]) // Output: 1
When we run this code, Go will automatically assign a hash table and several buckets for us, and then add key-value pairs to the corresponding bucket. In this way, when we need to access the value corresponding to a key, Go language will quickly locate the corresponding bucket according to the hash value, then iterate over the elements in the bucket to find whether there is the same key, and if it is found, it will return the corresponding value.
2. Implementation principle
It is a concurrently secure Map implementation in the Go language standard library, which can safely read and write in concurrent situations without locking. So, how does it achieve this concurrency security? Let’s analyze the implementation principle step by step.
Structural definition of 2.1
First, let's take a look at the structure definition:
type Map struct {
mu
read // readOnly
dirty map[interface{}]interface{}
misses int
dirtyLocked uintptr
}As can be seen from the above code, the implementation mainly relies on one mutex() and two maps (read and dirty). Among them, what are the functions of read and dirty? Let's first look at the definition of read:
type readOnly struct {
m map[interface{}]interface{}
amended bool
}As you can see, read has only one member m, which is a map type. amended means whether the key-value pairs in read have been modified. Next, let's take a look at the definition of dirty:
type dirty struct {
m map[interface{}]interface{}
dirty map[interface{}]bool
misses int
}Unlike read, dirty contains two maps: m and dirty. Among them, m stores the modified key-value pairs, while dirty stores which key-value pairs have been modified.
2.2 Reading Implementation
In , the read operation is very simple, just look up from m in readOnly. If the key-value pairs in readOnly have been modified, you need to look up from dirty. The implementation code of the read operation is as follows:
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
read, _ := ().(readOnly)
value, ok = [key]
if !ok && {
()
read, _ = ().(readOnly)
value, ok = [key]
if !ok && {
value, ok = [key]
}
()
}
return
}In this code, we first look up the key-value pairs from m in readOnly. If the key-value pair does not exist and the key-value pair in readOnly has been modified, you need to acquire the mutex and search again from readOnly. If it still doesn't find it, then look it up from dirty.
2.3 write implementation
In , the write operation needs to be completed in two steps. First of all, we need to determine whether the key-value pairs in readOnly have been modified. If they have not been modified, then directly add the key-value pairs to m in readOnly. Otherwise, we need to acquire the mutex, and then add the key-value pair to m in dirty , and add the corresponding key to dirty in dirty . The implementation code of the write operation is as follows:
func (m *Map) Store(key, value interface{}) {
read, _ := ().(readOnly)
if v, ok := [key]; !ok && ! {
()
read, _ = ().(readOnly)
if v, ok := [key]; !ok {
read = readOnly{m: , amended: true}
}
[key] = value
(read)
()
} else {
()
dirty := != 0
if !dirty {
= 1
= make(map[interface{}]interface{})
}
[key] = value
if !ok {
[key] = value
[key] = true
}
if dirty {
()
return
}
(readOnly{m: , amended: true})
()
}
}In this code, we first look up the key-value pairs from m in readOnly. If the key-value pair does not exist and the key-value pair in readOnly has not been modified, you need to acquire the mutex and search again from readOnly. If still not found, add the key-value pair to m in readOnly and set amended to true. Otherwise, we need to acquire the mutex and add the key-value pair to m in dirty , and add the corresponding key to dirty in dirty . If the key already exists in dirty, you only need to update the key value in dirty. If the key is not in dirty, you need to add the key in dirty and set the dirty of the key to true.
Next, we need to determine whether dirty is locked. If dirty is locked, the function is directly exited. Otherwise, we need to set amended in readOnly to true and store readOnly back to read.
2.4 Deletion Implementation
In , the deletion operation also needs to be completed in two steps. First of all, we need to determine whether the key-value pair in readOnly has been modified. If it has not been modified, just delete the key-value pair from m in readOnly. Otherwise, we need to acquire the mutex, then add the key to the dirty in dirty and set the value of the corresponding key in dirty to false. The implementation code of the delete operation is as follows:
func (m *Map) Delete(key interface{}) {
read, _ := ().(readOnly)
if _, ok := [key]; ok || {
()
read, _ = ().(readOnly)
if _, ok := [key]; ok || {
if == nil {
= make(map[interface{}]interface{})
}
[key] = false
[key] = true
(readOnly{m: , amended: true})
}
()
}
}In this code, we first look up the key-value pairs from m in readOnly. If the key-value pair exists or the key-value pair in readOnly has been modified, you need to acquire the mutex and search again from readOnly. If it is still not found, add the key to dirty in dirty and set the value of the corresponding key in dirty to false. Next, we need to determine whether dirty is nil. If it is nil, we need to initialize dirty as an empty map. We then add the key to dirty and set the value of the corresponding key in dirty to true. Finally, we set amended in readOnly to true and store readOnly back to read.
2.5 traversal implementation
In , the traversal operation requires combining all key-value pairs in readOnly and dirty and returning all key-value pairs that have not been deleted. The implementation code of the traversal operation is as follows:
func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := ().(readOnly)
if {
()
read, _ = ().(readOnly)
if {
read = readOnly{
m: merge(, ),
}
= false
(read)
= nil
}
()
}
for k, v := range {
if !f(k, v) {
break
}
}
}
func merge(m1, m2 map[interface{}]interface{}) map[interface{}]interface{} {
if len(m1) == 0 && len(m2) == 0 {
return nil
}
if len(m1) == 0 {
return m2
}
if len(m2) == 0 {
return m1
}
m := make(map[interface{}]interface{})
for k, v := range m1 {
m[k] = v
}
for k, v := range m2 {
if _, ok := m[k]; !ok || !v.(bool) {
m[k] = v
}
}
return m
}In this code, we first get all key-value pairs from readOnly and check whether any key-value pairs have been modified. If the key-value pair has been modified, you need to acquire the mutex, merge the key-value pairs in readOnly and dirty, and then store the combined key-value pairs back into readOnly and set dirty to nil. Next, we iterate through all key-value pairs in readOnly and call the f function to handle the key-value pairs. If the f function returns false, the traversal process ends.
In this Range function, we also implement a helper function called merge to merge two maps. During the merge process, we first determine whether the two maps are empty, and if they are empty, they will directly return nil. If one of the maps is empty, another map is returned. Otherwise, we need to add all the key-value pairs in m1 to the new map and iterate through the key-value pairs in m2 one by one. If the key in m2 does not exist in the new map, or the key in m2 is deleted, add it to the new map.
The above is an article that will take you to explore the detailed content in Go. For more information about Go, please follow my other related articles!