Map

Introduction

说map之前先迅速介绍一下map的内部结构, 只会说说基本逻辑, 比较细节的东西全都不会涉及, 文章里的代码基本都经过简化, 想要达到的效果是:"为什么会这样"以及"原来是这样"

map的内部结构

type hmap struct {
    buckets  []bmap
    count    int
    B        uint8
    hash0    uint32
    extra    *mapextra
}
type mapextra struct {
    overflow *[]*bmap 
}

hamp是map的底层实现, 本身并不是一个基础的数据类型, 因此它是需要被"制造"出来的, 内部的一些结构设置是需要初始化才能用的.

• bmap(桶)用于存储kv对, 一个桶存8个键值对

• 桶的总数量是2^B, 键值对的总数量是count

• 每个桶后面跟着一个overflow(溢出), 它也是一个桶, 如果那个桶里的东西超过8个, 就往它后面的溢出桶里面存, 一个桶后面可以跟好几个溢出桶

• 计算hash键值的时候需要用到hash0作为随机数种子

map的初始化 - new 与 make

m := make(map[string]string,5)
m := map[string]string{}

我们在日常写程序的时候大多数都是通过以上两种方式创建一个map, 以上这两个函数尤其是make这个关键字, 其实是会被翻译成makemap函数制造出一个hmap结构体出来, 我们也看到了里面有不少东西要初始化的, 比如桶的数量, 随机数种子要初始化, 桶的内存都是要预分配才行的.

与make的一系列初始化相对的, 是另一个关键字new, new(map)这种行为只是为hmap分配了一个内存, 至于初始化什么的那是完全没做. 与之类似的是var m map[int]int这种纯var不初始化的. 在这里我做了两个小实验, 分别是:

• 使用new做初始化的: playground

• 使用make做初始化的: playground

// 编译, 并禁用内联优化
go build -gcflags "-l" -o test main.go 
// 看看它都做了什么
go tool objdump -s "main\.test" test

同学们在拿到这两段代码以后复制到本地, 然后执行以下命令, 非常有意思的, 针对这种需要初始化的复杂数据结构, make与new调用的函数都不一样呢

map的初始化 - make什么map?

简单来说, 基本也就是根据你在make(map[k]v,size)的时候给出的参数, 根据loadFactor初始化一下桶的数量, 以及桶的内存预分配

map的查

1. 根据Key计算出hash出来的值, 按照二进制表示出来这个值

2. 取低4位, 计算出一个整数, 这个整数就代表桶的序号: buckets[index] , 再拿出高8位算是一个简略版的key

3. 我们遍历个桶里的8个舱位, 先比较简略版的key, 再比较完整的key, 都对的上就算命中, 退出

4. 没找到就遍历这个桶后面跟着的所有溢出桶, 然后还是遍历所有8个舱位, 并比对, 如果还没命中, 就是没有值

map的写

了解了读写就很快了, 计算桶序号, 然后找出桶内的第一个舱位放进去, 没有舱位就塞到溢出桶里. 像桶里的舱位中间出现一个空缺, 是删除造成的

map的扩容

扩容触发的动机有两个

• 我们把loadFactor定义成 map中元素的个数除以map当前桶的个数. 如果这个数字太大, 就说明桶太少而元素太多, 需要扩容

• 另一个原因就是hash不均匀, 导致某个桶挂了太多溢出桶, 判断条件是溢出桶的数量已经大于等于桶本身的数量了

扩容的方向也有两个

上面这种代表重新整理一下, 因为频繁插入删除, 导致桶内舱位缝隙很大, 虽然元素不多, 但是分散在桶/溢出桶到处都是, 每次遍历需要遍历很久, 这种情况下我们会重新整理一下, 集中在一起, 减少遍历时间

这种就是真的扩容, 扩两倍内存, 扩容不是一次性完成的, 我们把现有内容转移到oldbuckets里面, 每次做增删改查的时候触发搬运一两个过来

一些思考

遍历一个map的时候读key的顺序为什么不是固定的?

因为Go认为这会对新手程序员造成误解, 因此遍历map的时候并不会从0号桶开始读, 而是由一个随机数开始遍历的

map是线程安全的吗?

不是, 并发读写会导致concurrent map writes的panic, 按照官方文档的说法并发读写会导致不可预期的后果. 那应该怎么办呢?

1. 简单省事的做法是加sync.Mutex

2. 如果更有经验一些, 会知道如果加sync.RWMutex得到的效果更好, 因为读写锁允许多个G并行读, 或者一个G单独写.

3. Java中的ConcurrentHashMap为我们提供了一些灵感, 简单来说就是把整个哈希表打碎成好多块, 每一小块都单独上一个sync.RWMutex, 每次你的键来了, 我的第一步是计算出你属于哈希表中的哪一块, 然后我们安排你进子表, 然后再在子表里搞读写锁里上锁解锁那一套, 他们把这个叫做"降低锁粒度"

4. 或者, 你可以看看我们下面介绍的sync.Map

sync.Map

Map拥有两个数据队列, 一个read一个dirty, 我们后面简称读表与脏表, 其中数据最新最全的总是脏表, 因为任何写操作都是像脏表里写的, 读表则是出于无锁访问的目的, 生成出来为脏表服务的. 有了这些基本概念, 来看一下sync.Map的组成单元

type Map struct {
  Mutex
  read   readonly
  dirty  map[interface{}]*entry
  miss   int
}
type readonly struct {
  m        map[interface{}]*entry
  amended  bool 
}
type entry struct {
  p unsafe.Pointer
}

• 无论是脏表还是读表, 存储单元都是entry指针, 这么做的原因是二者虽然是两个不同的map, 但指向的却还是同一个实际存储位置, 同样的数据只用存一份就可以了

• 无论是脏表还是读表, 本质上到底都还是一个map, 区别无非就是:

  • 脏表有一个mutex作为辅助, 因为写操作都是往脏表里写的,搞个锁是可以理解的

  • 读表有一个amended字段作为辅助, 用于表示脏表中是否存在什么键, 是我读表里没有的

  • 读表还有一个miss作为辅助, 考虑到脏表永远比读表更新更全, 这个字段用于表示我在读表中没找到没命中, 但是在脏表中却命中的次数, 等到这个次数变多了, 我们就把脏表同步更新到读表里去, 更新一下数据

sync.Map查

func(m *Map)Load(key) {

  read, _ := m.read.Load()
  e, ok := read.m[key]

  if !ok && read.amended {
      m.Lock()
      e, ok = m.dirty[key]
      m.missLocked()
      m.Unlock()
  }

  if ok {
      return e.load()
  }else{
      return nil,false
  }
}

1. 首先我们尝试在读表里找一找这个键, 如果有就直接返回读表里的值, 因为读表里只要键是有的, 那值肯定是跟脏表一样的, 读表又不用加锁, 当然是优先使用咯

2. 如果读表里没有, 但又显示说"脏表里有些新数据", 那我们就去脏表里找找, 到脏表这儿就要加锁了, 毕竟只要你是map, 就得小心并发读写的问题

3. 两个表都找完了, 如果到这里你还没找到那就是真没有了, 只能返回你一个nil,false了

sync.Map删

func (m *Map) Delete(key) {

    read, _ := m.read.Load()
    e, ok := read.m[key]

    if ok {
        e.p = nil
    }
    if !ok && read.amended {
        m.Lock()
        delete(m.dirty, key)
        m.Unlock()
    }
}

流程大体跟上面一致, 就是读表里有我们就删读表, 读表里没有我们就尝试一下删脏表. 两边都删嘛, 但是有一点比较有意思, 就是我们对于读表的删是置成nil, 但对脏表的删就是真删, 大家都是map为什么搞区别对待呢?

在一个map里, 如果你把一个键的值设置成nil, 那么在 _, ok = map[key]里就能得到一个true, 就键还是存在的, 只是值为nil而已, 折腾这一下又是为什么呢? 回答这个问题, 先回顾上面sync.Map查的过程, 如果是true的话我们就能绕过上锁+查脏表的过程, 直接前往e.load()

func (e *entry)load() { 
  if e.p == nil || e.p == expunged {
    return nil, false
  }
  return *(*interface{})e.p, true
}

sync.Map增/改

func (m *Map) Store(key,val) {

    read, _ := m.read.Load()
    if e, ok := read.m[key]; ok && e.p != expunged {
          e.p = &val
          return
    }

    m.Lock()
    defer m.Unlock()

    if e, ok := read.m[key]; ok {
        m.dirty[key] = e 
        e.p = &val
    }else if e, ok := m.dirty[key]; ok {
        e.p = &val
    }else {
        if read.amended == false {
            m.dirtyLocked()
            m.read = readonly{m:read.m, amended:true}
            m.dirty[key] = newEntry(val)
        }
    }

}

func(e *entry) store(val) {
    if e == expunged {
        return false
    }else{
        e.p = unsafe.Pointer(&val)
        return true
    }
}

• 如果读表里有键:

  • 如果值不是expunged, 说明我们在往一个已经存在的键里写, 同时说明这是一次sync.Map的改操作, 因为脏表读表的键指向同一个位置, 直接修改读表就可以了

  • 如果值是expunged, 我们就不能在上一步改完就退出, 为什么呢? 因为expunged代表键已经被删除, 被删除的键在脏表里是没有的, 你不能搞出一个读表里有, 但脏表里没有的键, 所以expunged代表你除了需要更新键值, 还需要给脏表添加上这个键

• 如果读表里没键, 但脏表里有键:

  • 这说明我们在更新一个"新增的数据", 直接修改脏表就好了, 不用担心这个新增的数据, 我们马上就更新读表

• 如果读表+脏表里都没键

  • 这说明我们在插入一个之前没见过的新键, 这是一次插入操作, 我们创建了一个"新增的数据", 一个(暂时)只存在于脏表, 后面会同步到读表里的,"新增的数据", 同时说明这是一次sync.Map的增操作

  • 如果amended是false, 那就要更新为true了, 因为现在脏表已经有一个键读表里是没有的了, 然后搞数据同步

脏表与读表的同步

我们叭叭了半天脏表/读表, 但是我们却一直没提怎么搞数据同步, 什么时候搞数据同步, 如果你仔细看, sync.Map的查操作里有一个m.missLocked()函数还没有提, 这个函数, 结合插入操作里的m.dirtyLocked()共同构成了脏表/读表的同步过程

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

missLocked函数是用来决定什么时候将更新更全的脏表转移到读表去的. 我们都知道脏表更新更全, 但是什么时候同步过去呢? sync.Map中的miss参数发挥作用了, 每次查表的时候, 只要出现一次"读表没有,但脏表有"这种未命中的现象, 就增加一次, 一直增加到len(dirty)那么多次, 我们就认为read数据实在太不全了, 需要做同步了.

此时直接将脏表转移到读表里去, 脏表置空, 这很疑惑, 脏表本身代表了最新最全的数据, 你现在把它置空算什么呢? 别着急下面的函数会再把数据从读表转移回来的.

func (m *Map) dirtyLocked() {

    read, _ := m.read.Load()
    m.dirty = map[interface{}]*entry{}

    for k, e := range read.m {
        if e.p != nil && e.p != expunged {
            m.dirty[k] = e
        }
    }
}

我们上面说了脏表转移到读表以后脏表会置空, 那我们就需要把数据从读表转移回来, 这个过程发生在sync.Map第一次插入新键的时候, 见上面sync.Map的增操作. 具体过程是把读表中所有的expunged重新设置回nil, 然后非空的数据迁移回脏表, 毕竟nil只有读表需要, 脏表是不需要的

Summary

这么折腾真的带来什么作用了吗? 从上面的过程中, 我们可以发现所有读的过程都尽量走无锁的读表, 改的过程也尽量走无锁的读表去改, 只有插入/读最新数据的时候才会上锁读脏表, 已经尽力把锁操作降低到最少了

Reference

• qcrao

• linkin_star

• go-maps

• java-concur-hmap