You may have heard of doing GC on Golang map?

                                                                                                                                                                                                                                                                              

The map structure in Golang, when deleting the key-value pair, is not actually deleted, but marked. So as there are more and more key-value pairs, will it cause a lot of memory waste?

First of all, the answer is yes, it is very likely to cause OOM, and there is a discussion about this: github.com/golang/go/issues/20135. The general meaning is that in a large map, the delete operation does not actually release the memory and may cause memory OOM.

So the general approach is to rebuild the map. The container component of safemap is built into go-zero. safemap This can be avoided to a certain extent.

First let’s take a look at how map provided by go is deleted?

Native map deletion

1  package main
2
3  func main() {
4      m := make(map[int]string, 9)
5      m[1] = "hello"
6      m[2] = "world"
7      m[3] = "go"
8
9      v, ok := m[1]
10     _, _ = fn(v, ok)
11
12     delete(m, 1)
13  }
14
15 func fn(v string, ok bool) (string, bool) {
16     return v, ok
17 }

The test code is as above, we can passgo tool compile -S -N -l testmap.go | grep "CALL":

0x0071 00113 (test/testmap.go:4)        CALL    runtime.makemap(SB)
0x0099 00153 (test/testmap.go:5)        CALL    runtime.mapassign_fast64(SB)
0x00ea 00234 (test/testmap.go:6)        CALL    runtime.mapassign_fast64(SB)
0x013b 00315 (test/testmap.go:7)        CALL    runtime.mapassign_fast64(SB)
0x0194 00404 (test/testmap.go:9)        CALL    runtime.mapaccess2_fast64(SB)
0x01f1 00497 (test/testmap.go:10)       CALL    "".fn(SB)
0x0214 00532 (test/testmap.go:12)       CALL    runtime.mapdelete_fast64(SB)
0x0230 00560 (test/testmap.go:7)        CALL    runtime.gcWriteBarrier(SB)
0x0241 00577 (test/testmap.go:6)        CALL    runtime.gcWriteBarrier(SB)
0x0252 00594 (test/testmap.go:5)        CALL    runtime.gcWriteBarrier(SB)
0x025c 00604 (test/testmap.go:3)        CALL    runtime.morestack_noctxt(SB)

Execute delete on line 12, and the actual execution is runtime.mapdelete_fast64.

The parameter types of these functions are specific int64, mapdelete_fast64 operates the same as the original delete, so let’s take a lookmapdelete.

mapdelete

Long picture warning! ! !

#The general code analysis is as above, and the specific code is left for everyone to read. In fact, the general process is:

1. Write protection to prevent concurrent writing
2. Query the key to be deleted if it exists
3. If it exists, do the flag Delete mark
4. count--

So you delete key in a large area, the actual map is stored key will not be deleted, it will just mark the current key status as empty.

In fact, the starting point is similar to the mark deletion of mysql, which prevents the same key from being inserted in the future, eliminating the need for expansion and contraction operations.

But this is inappropriate for some scenarios. If the developer will not insert the same key in the future, it is likely to cause OOM.

So in response to the above situation, go-zero developed safemap. Let's see how safemap avoids this problem?

safemap

Analyze why it is designed like this directly from the operation safemap:

1. Preset a deletion threshold. If triggered, it will be placed in a new preset newmap
2. Two map It is a whole, so key can only keep one copy

So why we need to set up two map is very clear:

1. dirtyOld As a storage principal, migration will be triggered if the delete operation reaches the threshold.
2. dirtyNew As a temporary storage, when the threshold is reached, part of the key/value

will be stored. Therefore, during the migration operation, What we need to do is: Clear the original dirtyOld, store the stored key/value again to dirtyNew through for-range, and then dirtyNew Points to dirtyOld.

You may have questions: Doesn’t it mean that key/value is not deleted? It is just marked tophash=empty

In fact, in the for-range process, the key tophash will be filtered out

This way unnecessary keys are realized It will not be added to dirtyNew and will not affect dirtyOld.

#This is actually the concept of the old generation and the new generation of garbage collection.

For more implementation details, you can view the source code!

Project address

github.com/tal-tech/go-zero

Welcome to use go-zero and star Support us!

The above is the detailed content of You may have heard of doing GC on Golang map?. For more information, please follow other related articles on the PHP Chinese website!