I came across this article: A Concurrent and locking Golang interview question. It’s old, but it’s interesting.

I recently saw sync.map, so I wanted to see if I could use sync.map to do this.

I also found other implementations of Sync.mutex at GayHub [click here].

Due to the

The requirements look like this:

In a highly concurrent Web server, limit frequent IP access. Now 100 IP addresses are simulated to access the server concurrently and each IP address must be accessed 1000 times. Each IP address can be accessed only once in three minutes. Modify the following code to complete the process, requiring success: 100.

And the original code is given:

package main import ( "fmt" "time" ) type Ban struct { visitIPs map[string]time.Time } func NewBan() *Ban { return &Ban{visitIPs: make(map[string]time.Time)} } func (o *Ban) visit(ip string) bool { if _, ok := o.visitIPs[ip]; ok { return true } o.visitIPs[ip] = time.Now() return false } func main() { success := 0 ban := NewBan() for i := 0; i < 1000; i++ { for j := 0; j < 100; J++ {go func () {IP: = FMT. Sprintf (" 192.168.1. % d ", j) if! ban.visit(ip) { success++ } }() } } fmt.Println("success: ", success) }Copy the code

Oh ho, look at the source code and I say, can I just leave the package main and rewrite everything else? (her face)

As you are wise enough to know, the key to this problem is to allow you to add a read/write lock to Ban. And the three minutes in the deal didn’t matter, because the program never made it to the end of the day.

Train of thought

In fact, the original idea has not changed, and a BanList is still used to hold user ids that are temporarily inaccessible. And then each time you visit, determine if that user is in the List.

Modify the

Ok, so now we need a structure, because we will read the map concurrently, so we will use sync.map directly:

type Ban struct {
    M sync.Map
}Copy the code

If you click on sync.map, you’ll see that what it actually stores is an atomic.Value. An interface{} with atomic properties.

Ban also has an IsIn method to determine if the user id IsIn the Map.

Func (b *Ban) IsIn(user string) bool {fmt.Printf("%s in \n", user) // Load returns two values, V, ok := b.m.load (user) // sync.map. Load if! Printf(" There is no %s in the list, // Add user name to Ban List b.m.tore (IP, time.now ()) return false} If time.now ().second () -v.(time.time).second () > 180 {// If time.now ().second () -v.(time.time). % d, % d \ n ", v. (time. Time). The Second (), the time. Now (). The Second ()) / / at the same time to deposit B.M.S tore (IP, Time.now ()) return false}Copy the code

Let’s look at the test function:

Func main() {var success int64 = 0 ban := new(ban) wg := sync.waitgroup {} i < 2; For j := 0; for j := 0; for j := 0; j < 10; Wg.add (1) go func(c int) {defer wg.done () IP := FMT.Sprintf("%d", c) if! Ban.isin (IP) {// Atom.addint64 (&success, 1)}}(j)} wg.wait () FMT.Println(" this time: ", success)}Copy the code

There are no major changes to the test function, but since we are running it concurrently, we need to add a sync.waitgroup () to ensure that the program runs completely before exiting.

I specifically set the running value to be lower for testing purposes. Instead of 1000 requests, I have 2. There are 10 people instead of 100.

So the entire code should look like this:

package main import ( "fmt" "sync" "sync/atomic" "time" ) type Ban struct { M sync.Map } func (b *Ban) IsIn(user string)  bool { ... } func main() { ... }Copy the code

Run it…

Ah, it doesn’t seem to be right, but there will be 10~15 different results. Why is that? And I thought, well, it’s actually caused by concurrency. See here?

func (b *Ban) IsIn(user string) bool { ... v, ok := b.M.Load(user) if ! Ok {FMT.Printf(" list not %s, can access \n", user) b.m.tore (IP, time.now ()) return false}... }Copy the code

Synchronously initiated sync.map. Load is not actually linked to sync.map. Store to form an atomic operation. So if three users enter at the same time and the program queries at the same time, all three will return false (not in the list). So that increases the number of visits.

Sync. Map already takes this into account, so it has an atomic method of LoadOrStore — if it doesn’t Load, it stores, and if it loads, it doesn’t do anything.

So let’s change the IsIn code slightly:

func (b *Ban) IsIn(user string) bool { ... v, ok := b.M.LoadOrStore(user, time.Now()) if ! // delete b.m.tore (IP, time.now ()) return false}... }Copy the code

And then we run it again, a couple of times. We don’t see more than 10 visits this time.

examining

So far, we’ve succeeded in implementing the code in this scenario. But the scenario requirements that really limit user access can’t be played this way, generally with in-memory databases to achieve.

So, if you just want to know about sync.Map, that’s it. However, curiosity led me to take a look at the sync.map implementation, so let’s move on.

Manufacturing problems

What if you had to read and write a Go Map simultaneously? Try it on:

Let’s start with protagonist A

type A map[string]intCopy the code

We define ourselves as A type A, which is still A map at heart.

Type A map[string]int func main() {// initialize A m := make(A) m.setmap ("one", 1) m.setmap ("two", One go m.readmap ("one") // Set two to 2. Func (A *A)ReadMap(Key string) {FMT.Printf("Get Key %s: Func (a * a)SetMap(key string, Value int) {a[key] = value fmt.Printf("Set key %s: %d",key, a[key])Copy the code

If golang does not allow concurrent reading and writing to A map, it should get an error.

> Get Key one: 1
> Set Key two: 2Copy the code

Meow meow meow??? Why is the output normal? What about concurrent read/write errors? Well, actually the reason is that the map reads and writes above, although we set up coroutines, there is still a time difference for the computer. A small order will not cause map data read/write exceptions, so let’s change it.

func main() {
    m := make(A)
    m["one"] = 1
    m["two"] = 3

    go func() {
        for {
            m.ReadMap("one")
        }
    }()

    go func(){
        for {
            m.SetMap("two", 2)
        }
    }()

    time.Sleep(1*time.Second)
}Copy the code

To make reading and writing as colliding as possible, we added loops. Now we can see:

> fatal error: concurrent map read and map writeCopy the code

* Panic is present because of concurrent read and write checks in the map implementation.

To solve the problem

In fact, the above example is very similar to go’s introductory tutorial on sync.mutex locks. We have verified the problem with concurrent map reads and writes, and now we are trying to solve it.

Since conflicts are caused by reads and writes, the first thing to consider is locking. We read a lock and write a lock. So now we need to convert the simple A map into A structure with A lock:

type A struct {
    Value map[string]int
    mu sync.Mutex
}Copy the code

Value becomes the real place to put our Value. We also need to modify the ReadMap and SetMap methods.

func (a *A)ReadMap(key string) {
    a.mu.Lock()
    fmt.Printf("Get Key %s: %d",key, a.Value[key])
    a.mu.Unlock()
}
func (a *A)SetMap(key string, value int) {
    a.mu.Lock()
    a.Value[key] = value
    a.mu.Unlock()
    fmt.Printf("Set Key %s: %d",key, a.Value[key])
}Copy the code

Notice that you can’t do either method without Lock or Unlock.

Let’s run through the code again and see that it works, no error.

Is this the end of it?

We may have solved the problem in the simplest way possible, but is it really ok? If you are careful, you will notice that reading and writing are locked, and there are no special conditions, so when we try to read the map more than once, it will block. Even if I don’t want to change the value in the map… Although it doesn’t feel slow right now, this is a performance pit for dense reads.

In order to avoid unnecessary locks, we seem to have to make the code “smart.”

Reading and writing separation

Yes, read/write separation is a very useful design idea. We prepare a Read map and a Write map.

However, the read/write separation is not quite what we usually say (remember that our scenario is always concurrent read/write). We cannot synchronize (add/delete) the written map to the read map in real time or on time, because… This is no different from the map operations above, because the map is read without locking, and concurrency conflicts still occur.

The solution is not to “show” the value of a key in a map. Let’s reclassify the questions:

  1. Modify (delete) the value of an existing key
  2. Add nonexistent keys and values

First question: How about we change the value of the key to a pointer? The same key points to the same pointer address, which in turn points to the address of the real value.

Key -> & address -> & the real value address

Both Read and Write map values point to the same & address, and no matter who changes it, everyone changes it. When we need to change the value of an existing key, we change the real & address, not the & address or value of the key. Also, through the atomic package, we can make changes to Pointers atomically. Great, fix the existing key problem.

Second question: Now that we have Read map & Write map, we can use it. We lock the Write Map and increment the key and its value. This does not affect the Read Map reading.

However, we want to update the Read Map after all, so we count the misses, and when we get to a certain point, we safely sync the Write Map to the Read Map and clear the Write Map.

A Read map can be regarded as a read-only copy of a Write map. New keys cannot be added, but can be Read or modified.

The idea above is actually quite close to the implementation of Sync.map. Instead, sync.map calls our Write Map dirty, and synchronizing a Write Map to a Read Map promotes. Some structure encapsulation and state identification have been added.

In fact, if you do a Google search, you will find many articles analyzing sync.map source code, which are well written. I won’t repeat it here, but I want to summarize the approach in Sync.map with my understanding.

Combine sync.Map source code to taste better.

Read the Map. The Load

  1. Can Read map be Read directly?
  2. There are? Okay, let’s lock it up and Read Read Map again
  3. Has not yet? I’ll just have to read the Dirty Map
  4. Yes. Good. Let’s record that this read belongs toNot hitWhen misses + 1, let’s see if we can upgrade the dirty to Read
  5. unlock

* Double-checking is used to prevent dirty reads from happening within a very small time difference.

Write a Map. The Store

  1. Does Read Map have this key?
  2. Yes, let’s modify the value pointer by atomic manipulation
  3. No? Keep it locked and see if it’s there?
  4. Not yet. Okay, look at the Dirty map
  5. There are either! Change the Dirty map key pointer
  6. No? Add a key to the Dirty map and copy the original Read map
  7. unlock

Delete the Map. The Delete

  1. Does Read Map have this key?
  2. Yes, set value to nil.
  3. No? Delete the key in the dirty

Read or save map. LoadOrStore

emmmm……

  • Map.Load + Map.Store

I can’t make this up

With that in mind, I recommend some legitimate source code analysis and benchmarks that will make sync.map much clearer.

  • Have to know Golang sync.Map source analysis
  • Go sync. Map implementation
  • Go 1.9 Sync.map revealed

Also, if you notice the full copy of step 6 in map. Store, you’ll have a hunch that sync.map’s usage scenario doesn’t really lend itself well to the logic of high-concurrency writes. Indeed, the official instructions specify where sync.map is applicable:

// Map is like a Go map[interface{}]interface{} but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
...
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.Copy the code

Sync.map just helps optimize two usage scenarios:

  1. Read write less
  2. Multiple Goroutine operation keys

Sync.map strikes a balance between performance and security, and as in the case we started with, sync.Map doesn’t work either. In addition, there is an advanced version of Sync.map.

* atomic and mutex

In fact, when I looked at the Sync Map source code a long time ago, I always wondered why mutex when I could use atomic to solve concurrency security problems. In addition, map.store changes the key of read (without locking) directly. How is this different from changing a key?

If atomic can guarantee atomicity, how is it different from Mutex? After looking through some information, I know:

Mutexes are slow, due to the setup and teardown, and due to the fact that they block other goroutines for the duration of the lock.

Atomic operations are fast because they use an atomic CPU instruction, rather than relying on external locks to.

Mutexes actually perform atomic operations by blocking other coroutines, but atomic operations perform atomic operations by controlling the underlying CPU instructions.

Therefore, atomic and Mutex are not on the same level, and they are also different in terms of specialization. Mutex is also implemented by atomic in many aspects.

Sync Map cleverly combines the two for concurrency security.

  1. It uses a Pointer to store the value of the key, and only changes the address of the value (and a copy of the address). This can be done by using an atomic Pointer without conflicting.
  2. In addition, read/write separation + MUtex is used to control the operation of adding, deleting, changing and checking keys to prevent conflicts.

The first point is often mentioned in a lot of source code interpretation, but I think it is rather important skill (face covering).

* Some questions

Misses conditions

When you fail to get a dirty map, you must fail more than len(M.Dee) to get a read map.

Why is Go Map unlocked?

We can see the following two statements about not locking:

  1. Golang.org/doc/faq#at….
  2. blog.golang.org/go-ma…

* reference

  • www.jianshu.com/p/aa0…
  • www.zhihu.com/questio…
  • juejin.cn/post/1…
  • juejin.cn/post/1…
  • wudaijun.com/2018/02/g.. …
  • Colobu.com/2017/07/11….