真希望你也明白runtime.Map和sync.Map

站长

2022年12月26日 04:04 · 阅读数 10

Map 官方介绍

One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table. 哈希表是计算机中最有用的数据结构之一。提供快速查找、添加和删除。 Go 提供了一个实现哈希表的内置Map类型。

Hash冲突

那对于Hash的一个最重要的问题，就是hash冲突。下面我们看一下常用的解决方案。

开放寻址法

开放寻址法想象成一个停车问题。若当前车位已经有车，则继续往前开，直到找到一个空停车位。真希望你也明白runtime.Map和sync.Map

上图，每个方格子，就是一个车位，当一辆车来的时候，会依次查询是否有空位，如果没有，则继续向后面找，如果发现空位置，就会停到空位置中。

真希望你也明白runtime.Map和sync.Map

下面看一下，我们的代码是如何实现的？

真希望你也明白runtime.Map和sync.Map

m["面向加薪学习"]="从0到Go语言微服务架构师-训练营"
要对键-"面向加薪学习"，进行hash
拿到全体格子的总数，然后取模
如果取模发现是位子1，但是发现1已经被别人占了，那么就向后走，直到有空位，再把自己放进去。

看了上面的步骤是不是和停车，是一个道理？

那我们再看，如果想读取数据的时候:

同样对J键进行hash
拿到全体格子的总数，然后取模
找到位置是1，但是发现key不一样，它可能在后面，就一直向后查找。

拉链法

真希望你也明白runtime.Map和sync.Map

m["面向加薪学习"]="从0到Go语言微服务架构师-训练营"
要对键-"面向加薪学习"，进行hash
找到对应到槽位，每个槽位并不存储具体数据，只是一个指针，它指向下面的链表
当新增数据的时候，会把数据添加到链表头部（上图中黄色小球为例）

Go语言的Map

runtime/map.go，看到hmap这个结构体，它就go语言的map

type hmap struct {
    count     int
    flags     uint8
    B         uint8 
    noverflow uint16
    hash0     uint32
    buckets    unsafe.Pointer 
    oldbuckets unsafe.Pointer 
    nevacuate  uintptr
    extra *mapextra
}

count 键值对的数量
B 是以2为底，桶个数的对数
hash0 hash的种子
oldbuckets 旧的hash桶
buckets hash桶

下面看一个Go语言的哈希桶具体长什么样？用bmap结构体表示

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits

type bmap struct {
    tophash [bucketCnt]uint8
}

bucketCntBits 一个哈希桶可以存放最大的KV键值对的数量 bucketCnt Hash桶的数量(左移3位，也就是8。)

tophash [8]uint8

uint8是无符号的8为数字，也就是1个字节。 tophash 是存储桶中的每个键的哈希值的顶部字节(1个字节)。同样，k和v也是对应的8个。然后在编译的时候，将所有键和值再打包，这样就避免了在bmap中固定K和V的类型，最后还有一个overflow的指针，指向一个溢出桶。

真希望你也明白runtime.Map和sync.Map

新建Map

package main

import "fmt"

func main() {
    m := make(map[string]int, 16)
}

16代表预计要有16个Key，当然你也可以放更多的Key,Map会扩容，后面我们介绍到。

下面到命令行执行 go build -gcflags -S main.go

真希望你也明白runtime.Map和sync.Map

看到它调用了runtime.makemap这个函数。到runtime/map.go中，找到makemap()函数。

func makemap(t *maptype, hint int, h *hmap) *hmap {
    ...
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()
	
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B
}
...
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
    h.extra = new(mapextra)
    h.extra.nextOverflow = nextOverflow
}
...

4行新建hmap 6行获取hash种子 9-11行计算B的个数，根据初始化的时候传入的数据。(make(map[string]int, 16) 就是这个数字16) 15行生成多个hash桶 16-19行生成溢出桶，并存放在.extra中，当一个正常的Bmap装满数据后，会去到NextOverflow中找到空闲的溢出桶，因为Bmap字段中，也有个overflow的指针。（也就是说，一开始先保持空闲捅的指针，每个bmap数据也不多，当哪个桶装满了，就是那个桶的overflow指针指向原来闲置的的溢出桶地址，然后nextOverflow再继续指向下一个空闲的溢出桶，也就是nextOverflow永远指向下一个空闲的溢出桶，等待着哪个捅满了需要新桶来装数据了，再通过那个装满数据桶的overflow指向这个桶，然后NextOverflow接着移动指针指向新空闲桶）

真希望你也明白runtime.Map和sync.Map

Map读取数据

1.计算在哪个桶里？

Hash("锅包肉"+hash0)，如果生成的二进制是 0110001101001011，如果我们的HMap中的B是3，那么末尾取3位 011，换算成十进制就是3，就可以拿到buket 3,由于数组是从0开始，所以也就是4号桶。

2.获取TopHash

获取二进制前8位01100011，换算成16位是0x63

3.遍历TopHash

到数组中遍历，看看哪个位置的tophash是0x63

4.TopHash相同

继续查看key，如果相等，就返回元素，如果不相等，继续对比查找。

5.TopHash不同

如果4号桶的数组都遍历完了，没有0x63的tophash,如果有溢出桶，那就再去溢出桶中查找。如果都没有找到，那就是找不到key所对应的元素。

Map写数据

1.找到对应的桶（桶自身或溢出桶）

2.找到对应的key

3.修改数据的值

4.如果这个桶里没有对应的key,那么就直接插入一个

Map扩容都做了什么？

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    ...
}

可以看到有2个条件可以触发Map的扩容

hmap不在增加并且溢出因子很多

func overLoadFactor(count int, B uint8) bool {
     return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

bucketCnt是8，loadFactorNum是13，loadFactorDen是2

太多的溢出桶（这个会形成非常长的链表，导致严重的性能下降）

真希望你也明白runtime.Map和sync.Map

看一下代码

func hashGrow(t *maptype, h *hmap) {
    ...
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
    ...
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    if h.extra != nil && h.extra.overflow != nil {
        ...
    }
}

3行把原来的桶给oldbuckets
4行 h.B+bigger进行创建新桶和溢出桶
6行更新B的值
7行更新flags
8行把oldbuckets给h.oldbuckets
9行把newbuckets给h.buckets
10行溢出桶如果不为空，更新新桶的溢出桶

此时，新桶和老桶都存在，还没涉及到数据迁移的问题，下面我们看 Hash(“锅包肉”+hash0)，如果生成的二进制是 0110001101001011，如果我们的HMap中的B是1，那么末尾取1位 1，换算成十进制就是1，现在扩容，B是2，末尾取2位，就是11，换算十进制就是3，也就是说，未来数据会分配到buket-1和buket-3上。接下来看如何处理数据

func growWork(t *maptype, h *hmap, bucket uintptr) {
    evacuate(t, h, bucket&h.oldbucketmask())

    // evacuate one more oldbucket to make progress on growing
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

growWork()将旧桶上的数据放到新桶中去。

数据迁移完成后，把旧桶给GC了。

Map是并发安全的吗？

基于上面的学习，我们也可以看到扩容前和扩容后，当旧桶和新桶同时存在的时候，小明发起读数据，小刚发起写数据，小刚就会进入旧桶，进行数据迁移，那么小明很有可能在读取的时候，旧桶的数据已经被迁移到了新桶中，这样数据就会读错乱。

下面看一下Snyc.Map（注:上面的map是runtime包下的）

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[any]*entry
    misses int
}

type readOnly struct {
    m map[any]*entry
    amended bool 
}

type entry struct {
    p unsafe.Pointer // *interface{}
}

2行 mu 是一个锁
8-11 行 read 对应readOnly的结构体，readOnly中的m是一个任意类型键和任意类型值的map，entry是包含一个unsafe.Pointer的指针p的结构体。
10行 amended是修正的意思。
4行 dirty是一个任意类型键和任意类型值的map
5行 misses 未击中

真希望你也明白runtime.Map和sync.Map

func (m *Map) Store(key, value any) {
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        e.storeLocked(&value)
    } else {
        if !read.amended {
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

上面就是存储数据的代码。

2-5 如果read中中可以找到这个Key,并且没有被标记被删除，就tryStore(),试图去更新值。

7-24 如果read中不存在这个Key或者被标记为已删除的情况，此时加锁/解锁。

9-13 再次读取read,此时已经找到了Key,如果entry被删除了，那么就把这个key和value存储到dirty的map中

14-16 dirty的map中存在这个key，更新这个值

17 到这一步，这个判断证明read和dirty都没有这个key,如果read的amended为假，证明read和dirty的两个map中的数据是相等的

18 如果dirty是nil，就把read的数据都放到dirty中，否则dirty有数据，就怎么都不做，直接返回。

19 标记amended为true,证明read和dirty不同了

21 把数据放到dirty的map中。

单协程代码演示

真希望你也明白runtime.Map和sync.Map

上图，从goland中打印出来的消息看，数据都在dirty的map中。

func (m *Map) Load(key any) (value any, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

2-3 到read中的map查找key

4-13 read中没找到，并且amended为真，意味read和dirty,这2个map数据不一致。（dirty的数据通常是多的）

5-12 加锁，操作dirty的map

6-7 再次读取map

8 read中仍然找不到这个key,并且amended为真

9 去dirty中读取该key

10 给misses +1，如果m.misses == len(m.dirty)，那么就把m.dirty放到read中的m变量里，然后dirty设置nil，misses设置为0

14 read中没找到,但是amended为假，说明read和dirty数据相同，所以，直接返回nil，false

17 read中找到了entry,直接调用entry的load()方法就可以了

    var m sync.Map
    num := 100
    var w sync.WaitGroup
    w.Add(num)
    m.Store("《Go语言极简一本通》第4次印刷", 1)
    m.Store("《Go语言微服务架构核心22讲》", 2)
    m.Store("《Go语言+Redis》实战课", 3)
    m.Store("《Go语言+RabbitMQ》实战课", 4)
    m.Store("《从0到Go语言微服务架构师》训练营", 5)
    m.Store("《Web3与Go语言》实战课", 6)

    for i := 0; i < num; i++ {
        go func() {
            v2, _ := m.Load("《Web3与Go语言》实战课")
            fmt.Println(v2)
            w.Done()
        }()
    }
    w.Wait()
    fmt.Println(m)

真希望你也明白runtime.Map和sync.Map

删除方法源代码分析

func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            delete(m.dirty, key)
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        return e.delete()
    }
    return nil, false
}

6-7 读取read中的map的key

8 如果没找到，并且amended为真，证明read和dirty中的map数据不相等

9-17 加锁操作dirty的map

10-12 再次读取read中的map,如果没找到，并且amended为真

13 查找dirty的map中key

14 删除dirty的map中key

15 判断是否把dirty的map提升到read中去

19-20 在read中找到了entry，那么就直接调用entry的delete()

在main协程内，执行删除操作

    var m sync.Map
    m.Store("《Go语言极简一本通》第4次印刷", 1)
    m.Store("《Go语言微服务架构核心22讲》", 2)
    m.Store("《Go语言+Redis》实战课", 3)
    m.Store("《Go语言+RabbitMQ》实战课", 4)
    m.Store("《从0到Go语言微服务架构师》训练营", 5)
    m.Store("《Web3与Go语言》实战课", 6)
    m.Delete("《Web3与Go语言》实战课")
    fmt.Println(m)

真希望你也明白runtime.Map和sync.Map

多协程删除操作

    var m sync.Map
    num := 100
    var w sync.WaitGroup
    w.Add(num)
    m.Store("《Go语言极简一本通》第4次印刷", 1)
    m.Store("《Go语言微服务架构核心22讲》", 2)
    m.Store("《Go语言+Redis》实战课", 3)
    m.Store("《Go语言+RabbitMQ》实战课", 4)
    m.Store("《从0到Go语言微服务架构师》训练营", 5)
    m.Store("《Web3与Go语言》实战课", 6)

    for i := 0; i < num; i++ {
        go func() {
            m.Delete("《Web3与Go语言》实战课")
            w.Done()
        }()
    }
    w.Wait()
    fmt.Println(m)