The map structure in Golang, when a key-value pair is deleted, is not actually deleted, but marked. So as we get more and more key-value pairs, is there going to be a lot of memory wasted?

First of all, the answer is, is likely to lead to OOM, and for this there is a discussion: https://github.com/golang/go/issues/20135. On a very large map, the delete operation may cause memory OOM without actually freeing memory.

So the general approach is to rebuild the map. The SafeMap container component is built into Go-Zero. SafeMap prevents this from happening to some extent.

First let’s look at how to remove the map provided by Go native.

Native map delete

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 as above, we can go through 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. Runtime.mapDelete_fast64 is actually executed.

The parameter types of these functions are specific int64, and mapDelete_fast64 is the same as the original delete operation, so let’s look at mapDelete.

mapdelete

Long map warning!!

Roughly code analysis as above, the specific code for you to read. In fact, the general process:

  1. Write protection, which prevents concurrent writes
  2. The query to deletekeyIf there is a
  3. If it exists, it will be marked for deletion
  4. count--

So if you delete a key in a large area, the actual key stored in the map will not be deleted, but the current key state will be marked as empty.

In fact, the starting point is similar to the MySQL tag delete, to prevent the subsequent insertion of the same key, save the expansion of capacity operation.

However, this is not appropriate for some scenarios, if the developer does not insert the same key again in the future, it will probably cause OOM.

So for the above situation, Go-Zero developed SafeMap. How does Safemap avoid this problem?

safemap

Analyze the reasons for this design directly from the operation of SAFEMap:

  1. A defaultDelete the thresholdIf triggered it will be put into a new presetnewmap 中
  2. twomapIt’s a unit, sokeyOnly one can be kept

So it should be clear why there are two maps:

  1. dirtyOldAs the storage body, ifdeleteWhen the threshold value is reached, the migration is triggered.
  2. dirtyNewAs a temporary storage, it will store the part when the threshold is reachedkey/value

Therefore, what we need to do is to clean up the original dirtyOld, store the stored key/value to dirtyNew through for-range, and then point dirtyNew to dirtyOld.

The key/value is not deleted, it is just marked with tophash=empty

In fact, in the for-range process, it will filter out the key of tophash <= emptyOne

This enables unneeded keys not to be added to dirtyNew and thus not to affect dirtyOld.

This is the concept of the old generation and the new generation of garbage recycling.

For more details, see the source code!

The project address

https://github.com/tal-tech/go-zero

Welcome to Go-Zero and Star Support!

WeChat communication group

Follow the public account of “micro-service practice” and click on the exchange group to get the QR code of the community group.