MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Go语言映射(Map)线程安全的深入探讨

2023-03-293.5k 阅读

Go 语言映射 (Map) 线程安全的深入探讨

Go 语言 Map 基础回顾

在 Go 语言中，map 是一种无序的键值对集合。它的定义简洁明了，使用起来非常方便。例如，我们可以这样定义一个简单的 map：

package main

import "fmt"

func main() {
    // 定义一个 string 到 int 的 map
    m := make(map[string]int)
    m["one"] = 1
    m["two"] = 2

    fmt.Println(m["one"])
}

在上述代码中，我们首先使用 make 函数创建了一个空的 map[string]int，然后向其中添加了两个键值对，并最后获取了键 "one" 对应的值。

Go 语言的 map 在底层是通过哈希表实现的。哈希表能够提供高效的查找、插入和删除操作。当我们向 map 中插入一个键值对时，map 会根据键的哈希值来决定将这个键值对存储在哈希表的哪个位置。在查找时，同样根据键的哈希值快速定位到可能存储该键值对的位置。

Go 语言 Map 的非线程安全性

Go 语言的 map 本身并不是线程安全的。这意味着当多个 goroutine 同时对一个 map 进行读写操作时，可能会导致程序出现未定义行为。这种未定义行为可能表现为程序崩溃，也可能导致数据的不一致。

考虑以下代码示例：

package main

import (
    "fmt"
    "sync"
)

var m = make(map[string]int)

func write(key string, value int, wg *sync.WaitGroup) {
    defer wg.Done()
    m[key] = value
}

func read(key string, wg *sync.WaitGroup) {
    defer wg.Done()
    fmt.Println(m[key])
}

func main() {
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go write(key, i, &wg)
    }

    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go read(key, &wg)
    }

    wg.Wait()
}

在这段代码中，我们启动了 10 个 goroutine 进行写操作，同时启动 10 个 goroutine 进行读操作。运行这段代码，我们很可能会得到一个运行时错误，提示 fatal error: concurrent map read and map write。这是因为 Go 语言的 map 没有内置对并发访问的保护机制。

线程不安全的本质原因

从底层实现角度来看，map 的非线程安全性主要源于其哈希表的结构。当多个 goroutine 同时对 map 进行操作时，可能会发生以下几种冲突情况：

哈希冲突处理中的竞争

哈希表中不可避免地会出现哈希冲突，即不同的键计算出相同的哈希值。在处理哈希冲突时，map 通常采用链地址法或开放地址法。当多个 goroutine 同时插入键值对导致哈希冲突时，就可能出现竞争条件。例如，在链地址法中，多个 goroutine 可能同时尝试向同一个哈希桶中的链表插入新节点，这就会导致链表结构的不一致。

动态扩容过程中的竞争

随着 map 中元素数量的增加，为了保持哈希表的性能，map 会进行动态扩容。在扩容过程中，map 需要重新计算所有键值对的哈希值并将其重新分布到新的哈希表中。如果在扩容过程中有其他 goroutine 进行读写操作，就会导致数据的不一致。比如，一个 goroutine 可能在旧的哈希表中读取到了部分数据，而另一个 goroutine 正在将数据迁移到新的哈希表中，这就会导致读取到的数据不完整或不准确。

实现线程安全 Map 的方式

使用互斥锁 (Mutex)

互斥锁是一种常用的实现线程安全的手段。通过在对 map 进行读写操作前后加锁，我们可以保证在同一时刻只有一个 goroutine 能够访问 map。以下是一个使用互斥锁实现线程安全 map 的示例：

package main

import (
    "fmt"
    "sync"
)

type SafeMap struct {
    mu sync.Mutex
    data map[string]int
}

func (sm *SafeMap) Set(key string, value int) {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    if sm.data == nil {
        sm.data = make(map[string]int)
    }
    sm.data[key] = value
}

func (sm *SafeMap) Get(key string) (int, bool) {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    if sm.data == nil {
        return 0, false
    }
    value, exists := sm.data[key]
    return value, exists
}

func main() {
    sm := SafeMap{}
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go func(k string, v int) {
            defer wg.Done()
            sm.Set(k, v)
        }(key, i)
    }

    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go func(k string) {
            defer wg.Done()
            value, exists := sm.Get(k)
            if exists {
                fmt.Printf("Key: %s, Value: %d\n", k, value)
            }
        }(key)
    }

    wg.Wait()
}

在上述代码中，我们定义了一个 SafeMap 结构体，其中包含一个互斥锁 mu 和一个普通的 map data。在 Set 和 Get 方法中，我们通过加锁和解锁操作来保证对 data 的安全访问。

使用读写锁 (RWMutex)

读写锁是一种更细粒度的锁机制，它区分了读操作和写操作。多个 goroutine 可以同时进行读操作，但写操作必须是独占的。这种特性在大多数读多写少的场景下能够显著提高性能。以下是使用读写锁实现线程安全 map 的示例：

package main

import (
    "fmt"
    "sync"
)

type RWSafeMap struct {
    mu sync.RWMutex
    data map[string]int
}

func (rwsm *RWSafeMap) Set(key string, value int) {
    rwsm.mu.Lock()
    defer rwsm.mu.Unlock()
    if rwsm.data == nil {
        rwsm.data = make(map[string]int)
    }
    rwsm.data[key] = value
}

func (rwsm *RWSafeMap) Get(key string) (int, bool) {
    rwsm.mu.RLock()
    defer rwsm.mu.RUnlock()
    if rwsm.data == nil {
        return 0, false
    }
    value, exists := rwsm.data[key]
    return value, exists
}

func main() {
    rwsm := RWSafeMap{}
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go func(k string, v int) {
            defer wg.Done()
            rwsm.Set(k, v)
        }(key, i)
    }

    for i := 0; i < 100; i++ {
        key := fmt.Sprintf("key%d", i%10)
        wg.Add(1)
        go func(k string) {
            defer wg.Done()
            value, exists := rwsm.Get(k)
            if exists {
                fmt.Printf("Key: %s, Value: %d\n", k, value)
            }
        }(key)
    }

    wg.Wait()
}

在这个示例中，Get 方法使用读锁 RLock 和 RUnlock，而 Set 方法使用写锁 Lock 和 Unlock。这样，在大量读操作的场景下，多个 goroutine 可以同时读取 map，而写操作时会独占锁，保证数据的一致性。

使用 sync.Map

Go 1.9 引入了 sync.Map，它是一个线程安全的 map 实现。sync.Map 适合高并发读写的场景，并且不需要像使用互斥锁或读写锁那样手动进行加锁和解锁操作。以下是 sync.Map 的使用示例：

package main

import (
    "fmt"
    "sync"
)

func main() {
    var sm sync.Map
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go func(k string, v int) {
            defer wg.Done()
            sm.Store(k, v)
        }(key, i)
    }

    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key%d", i)
        wg.Add(1)
        go func(k string) {
            defer wg.Done()
            value, exists := sm.Load(k)
            if exists {
                fmt.Printf("Key: %s, Value: %d\n", k, value.(int))
            }
        }(key)
    }

    wg.Wait()
}

在上述代码中，我们使用 sync.Map 的 Store 方法进行写入操作，使用 Load 方法进行读取操作。sync.Map 内部采用了更复杂的结构和算法来实现线程安全，它在多个 goroutine 并发读写时表现出良好的性能。

sync.Map 的底层实现原理

数据结构

sync.Map 内部使用了两个数据结构：一个是 read，另一个是 dirty。read 是一个 atomic.Value 类型，它存储了一部分键值对，并且可以在不加锁的情况下进行读取操作。dirty 是一个普通的 map，它存储了那些在 read 中不存在的键值对。

读取操作

当执行 Load 方法时，sync.Map 首先尝试从 read 中读取数据。如果在 read 中找到了对应的数据，则直接返回，这个过程不需要加锁，因此读操作的性能很高。如果在 read 中没有找到数据，则需要加锁并从 dirty 中查找。如果在 dirty 中找到了数据，并且 read 中没有这个键，则会将这个键值对提升到 read 中，以便后续更快地读取。

写入操作

当执行 Store 方法时，如果 read 中包含要写入的键，并且 read 是可写的（通过一个标志位判断），则直接在 read 中更新值。否则，需要加锁，将键值对写入 dirty 中。如果 dirty 为空，则将 read 中的数据复制到 dirty 中，然后再进行写入操作。

删除操作

Delete 方法同样首先尝试从 read 中删除键值对。如果在 read 中没有找到，则加锁并从 dirty 中删除。如果 dirty 中也没有找到，则不进行任何操作。

不同实现方式的性能对比

为了更直观地了解不同线程安全 map 实现方式的性能差异，我们可以进行一些性能测试。以下是一个简单的性能测试示例，对比了使用互斥锁、读写锁和 sync.Map 在不同读写比例下的性能：

package main

import (
    "fmt"
    "sync"
    "time"
)

type SafeMap struct {
    mu sync.Mutex
    data map[string]int
}

func (sm *SafeMap) Set(key string, value int) {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    if sm.data == nil {
        sm.data = make(map[string]int)
    }
    sm.data[key] = value
}

func (sm *SafeMap) Get(key string) (int, bool) {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    if sm.data == nil {
        return 0, false
    }
    value, exists := sm.data[key]
    return value, exists
}

type RWSafeMap struct {
    mu sync.RWMutex
    data map[string]int
}

func (rwsm *RWSafeMap) Set(key string, value int) {
    rwsm.mu.Lock()
    defer rwsm.mu.Unlock()
    if rwsm.data == nil {
        rwsm.data = make(map[string]int)
    }
    rwsm.data[key] = value
}

func (rwsm *RWSafeMap) Get(key string) (int, bool) {
    rwsm.mu.RLock()
    defer rwsm.mu.RUnlock()
    if rwsm.data == nil {
        return 0, false
    }
    value, exists := rwsm.data[key]
    return value, exists
}

func benchmarkSafeMap(readRatio float64, numGoroutines int) {
    sm := SafeMap{}
    var wg sync.WaitGroup
    start := time.Now()
    for i := 0; i < numGoroutines; i++ {
        if float64(i%100) < readRatio*100 {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for j := 0; j < 1000; j++ {
                    key := fmt.Sprintf("key%d", j)
                    _, _ = sm.Get(key)
                }
            }()
        } else {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for j := 0; j < 1000; j++ {
                    key := fmt.Sprintf("key%d", j)
                    sm.Set(key, j)
                }
            }()
        }
    }
    wg.Wait()
    elapsed := time.Since(start)
    fmt.Printf("SafeMap with %f read ratio, elapsed: %s\n", readRatio, elapsed)
}

func benchmarkRWSafeMap(readRatio float64, numGoroutines int) {
    rwsm := RWSafeMap{}
    var wg sync.WaitGroup
    start := time.Now()
    for i := 0; i < numGoroutines; i++ {
        if float64(i%100) < readRatio*100 {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for j := 0; j < 1000; j++ {
                    key := fmt.Sprintf("key%d", j)
                    _, _ = rwsm.Get(key)
                }
            }()
        } else {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for j := 0; j < 1000; j++ {
                    key := fmt.Sprintf("key%d", j)
                    rwsm.Set(key, j)
                }
            }()
        }
    }
    wg.Wait()
    elapsed := time.Since(start)
    fmt.Printf("RWSafeMap with %f read ratio, elapsed: %s\n", readRatio, elapsed)
}

func benchmarkSyncMap(readRatio float64, numGoroutines int) {
    var sm sync.Map
    var wg sync.WaitGroup
    start := time.Now()
    for i := 0; i < numGoroutines; i++ {
        if float64(i%100) < readRatio*100 {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for j := 0; j < 1000; j++ {
                    key := fmt.Sprintf("key%d", j)
                    _, _ = sm.Load(key)
                }
            }()
        } else {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for j := 0; j < 1000; j++ {
                    key := fmt.Sprintf("key%d", j)
                    sm.Store(key, j)
                }
            }()
        }
    }
    wg.Wait()
    elapsed := time.Since(start)
    fmt.Printf("sync.Map with %f read ratio, elapsed: %s\n", readRatio, elapsed)
}

func main() {
    numGoroutines := 100
    benchmarkSafeMap(0.5, numGoroutines)
    benchmarkRWSafeMap(0.5, numGoroutines)
    benchmarkSyncMap(0.5, numGoroutines)

    benchmarkSafeMap(0.9, numGoroutines)
    benchmarkRWSafeMap(0.9, numGoroutines)
    benchmarkSyncMap(0.9, numGoroutines)
}

通过运行上述代码，我们可以看到在不同读写比例下，三种实现方式的性能表现。一般来说，在读写比例均衡的情况下，sync.Map 和使用读写锁的方式性能优于使用互斥锁的方式。而在读多写少的场景下，sync.Map 和使用读写锁的方式优势更加明显。

选择合适的线程安全 Map 实现

在实际应用中，选择合适的线程安全 map 实现取决于具体的应用场景：

读多写少的场景

如果应用场景中读操作远远多于写操作，那么 sync.Map 或使用读写锁实现的线程安全 map 是比较好的选择。sync.Map 由于其内部优化的读取机制，在高并发读的场景下性能表现优异。而使用读写锁的实现方式也能够通过区分读写操作，提高读操作的并发度。

读写均衡的场景

对于读写操作较为均衡的场景，sync.Map 和使用读写锁的方式仍然是不错的选择。虽然使用互斥锁也能实现线程安全，但由于其在每次读写操作时都需要加锁，性能可能会受到一定影响。

写多读少的场景

在写多读少的场景下，使用互斥锁实现的线程安全 map 可能是最简单直接的方式。虽然每次写操作都需要独占锁，但由于写操作频繁，使用更复杂的机制如 sync.Map 可能并不会带来明显的性能提升，反而会增加代码的复杂度。

总结不同实现方式的优缺点

互斥锁实现

  • 优点：实现简单，易于理解和维护。对于简单的并发场景，能够快速实现线程安全。
  • 缺点：性能较低，每次读写操作都需要加锁，在高并发场景下可能成为性能瓶颈。

读写锁实现

  • 优点：在读写比例不均衡，尤其是读多写少的场景下，性能优于互斥锁。通过区分读写操作，提高了读操作的并发度。
  • 缺点：相比于互斥锁，代码复杂度有所增加，需要正确使用读锁和写锁。并且在写操作频繁时，性能提升不明显。

sync.Map 实现

  • 优点：适合高并发读写场景，内部采用了优化的结构和算法，能够在高并发下提供较好的性能。不需要手动进行加锁和解锁操作，代码简洁。
  • 缺点：实现复杂，内部机制不易理解。在某些特定场景下，如写操作非常频繁且数据量较小的情况下，性能可能不如简单的互斥锁实现。

通过对 Go 语言 map 线程安全问题的深入探讨，我们了解了 map 非线程安全的本质原因，以及多种实现线程安全 map 的方式及其性能特点。在实际编程中，我们应根据具体的应用场景选择合适的实现方式，以确保程序的正确性和性能。