In Golang’s map structure, when you delete a key-value pair, you don’t actually delete it, you mark it. So as you get more and more key-value pairs, is that going to waste a lot of memory?

First of all, the answer is “yes”, which will probably lead to “OOM”, and there is a discussion about this: github.com/golang/go/i… . In large maps, delete operations that do not actually free memory may cause memory to OOM.

So the general approach is to rebuild the map. The safemap container component is built into Go-Zero. Safemap avoids this to some extent.

First of all, let’s take a look at how the go native map is deleted.

Native Map Deletion

1  package main
2
3  func main(a) {
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 }
Copy the code

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)
Copy the code

Mapdelete_fast64 is executed.

The parameter type of these functions is int64. Mapdelete_fast64 is the same as the original delete operation, so let’s look at mapdelete.

mapdelete

Long picture warning!!

The general code analysis is as above, and I will leave the specific code to you to read. In fact, the general process:

  1. Write protection to prevent concurrent write
  2. Query to deletekeyIf there is a
  3. If it exists, its mark is deleted
  4. count--

So if you delete a large number of keys, the actual map keys 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, eliminating the operation of expansion.

However, this is not appropriate for some scenarios, and if the developers do not insert the same key again for some time, it will probably result in an OOM.

So for this, Go-Zero developed Safemap. Let’s see how Safemap avoids this problem.

safemap

Directly from operating safemap to analyze why it is designed this way:

  1. A defaultDelete the thresholdIf triggered it will be placed in a new presetnewmap 中
  2. twomapIt’s a whole unit, sokeyYou can only keep one

So it’s clear why you want to set up two maps:

  1. dirtyOldAs the storage principal, ifdeleteIf the operation reaches a threshold, the migration is triggered.
  2. dirtyNewAs temporary storage, the portion is stored when the threshold is reachedkey/value

So in the migration operation, what we need to do is: empty the original dirtyOld, store the stored key/value back to the dirtyNew through the for-range, and then point the dirtyNew to the dirtyOld.

Key /value is not removed, but tophash= Empty is marked

In the for-range process, the key with tophash <= emptyOne is filtered out

This ensures that unwanted keys will not be added to the dirtyNew and will not affect the dirtyOld.

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

For more implementation details, see the source code!

The project address

Github.com/tal-tech/go…

Welcome to GO-Zero and star support us!

Wechat communication group

Follow the “Microservice Practice” official account and click the exchange group to get the COMMUNITY group QR code.