V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
newmiao
V2EX  ›  Go 编程语言

Dig101-Go 之读懂 map 的底层设计

  •  1
     
  •   newmiao · 2020-03-09 23:10:41 +08:00 · 1767 次点击
    这是一个创建于 1711 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Dig101: dig more, simplified more and know more

    在 golang 中,map是一个不可或缺的存在。

    它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。

    这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。

    我们不会过多在源码分析上展开,只结合代码示例对其背后设计实现上做些总结,希望可以简单明了一些。

    希望看完后,会让你对 map 的理解有一些帮助。网上也有很多不错的源码分析,会附到文末,感兴趣的同学自行查看下。

    (本文分析基于 Mac 平台上 go1.14beta1 版本。长文预警 ... )

    我们先简单过下 map 实现 hash 表所用的数据结构,这样方便后边讨论。

    0x01 map 的内部结构

    map 数据结构

    在这里我们先弄清楚 map 实现的整体结构

    map 本质是 hash 表(hmap),指向一堆桶(buckets)用来承接数据,每个桶(bmap)能存 8 组 k/v。

    当有数据读写时,会用key的 hash 找到对应的桶。

    为加速 hash 定位桶,bmap里记录了tophash数组( hash 的高 8 位)

    hash 表就会有哈希冲突的问题(不同 key 的 hash 值一样,即 hash 后都指向同一个桶),为此 map 使用桶后链一个溢出桶(overflow)链表来解决当桶 8 个单元都满了,但还有数据需要存入此桶的问题。

    剩下noverflow,oldbuckets,nevacuate,oldoverflow 会用于扩容,暂时先不展开

    具体对应的数据结构详细注释如下:

    (虽然多,先大致过一遍,后边遇到会在提到)

    // runtime/map.go
    // A header for a Go map.
    type hmap struct {
      //用于 len(map)
      count     int
      //标志位
      // iterator     = 1 // 可能有遍历用 buckets
      // oldIterator  = 2 // 可能有遍历用 oldbuckets,用于扩容期间
      // hashWriting  = 4 // 标记写,用于并发读写检测
      // sameSizeGrow = 8 // 用于等大小 buckets 扩容,减少 overflow 桶
      flags     uint8
    
      // 代表可以最多容纳 loadFactor * 2^B 个元素( loadFactor=6.5 )
      B         uint8
      // overflow 桶的计数,当其接近 1<<15 - 1 时为近似值
      noverflow uint16
      // 随机的 hash 种子,每个 map 不一样,减少哈希碰撞的几率
      hash0     uint32
    
      // 当前桶,长度为( 0-2^B )
      buckets    unsafe.Pointer
      // 如果存在扩容会有扩容前的桶
      oldbuckets unsafe.Pointer
      // 迁移数,标识小于其的 buckets 已迁移完毕
      nevacuate  uintptr
    
      // 额外记录 overflow 桶信息,不一定每个 map 都有
      extra *mapextra
    }
    
    // 额外记录 overflow 桶信息
    type mapextra struct {
      overflow    *[]*bmap
      oldoverflow *[]*bmap
    
      // 指向下一个可用 overflow 桶
      nextOverflow *bmap
    }
    
    const(
      // 每个桶 8 个 k/v 单元
      BUCKETSIZE  = 8
      // k 或 v 类型大小大于 128 转为指针存储
      MAXKEYSIZE  = 128
      MAXELEMSIZE = 128
    )
    
    // 桶结构 (字段会根据 key 和 elem 类型动态生成,见下边 bmap )
    type bmap struct {
      // 记录桶内 8 个单元的高 8 位 hash 值,或标记空桶状态,用于快速定位 key
      // emptyRest      = 0 // 此单元为空,且更高索引的单元也为空
      // emptyOne       = 1 // 此单元为空
      // evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
      // evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
      // evacuatedEmpty = 4 // 用于表示此单元已迁移
      // minTopHash     = 5 // 最小的空桶标记值,小于其则是空桶标志
      tophash [bucketCnt]uint8
    }
    
    // cmd/compile/internal/gc/reflect.go
    // func bmap(t *types.Type) *types.Type {
    // 每个桶内 k/v 单元数是 8
    type bmap struct{
      topbits [8]uint8 //tophash
      keys [8]keytype
      elems [8]elemtype
      // overflow 桶
      // otyp 类型为指针*Type,
      // 若 keytype 及 elemtype 不含指针,则为 uintptr
      // 使 bmap 整体不含指针,避免 gc 去 scan 此类 map
      overflow otyp
    }
    

    这里有几个字段需要解释一下:

    • hmap.B

    这个为啥用 2 的对数来表示桶的数目呢?

    这里是为了 hash 定位桶及扩容方便

    比方说,hash%n可以定位桶, 但%操作没有位运算快。

    而利用 n=2^B,则 hash%n=hash&(n-1)

    则可优化定位方式为: hash&(1<<B-1)(1<<B-1)即源码中BucketMask

    再比方扩容,hmap.B=hmap.B+1 即为扩容到二倍

    • bmap.keys, bmap.elems

    在桶里存储 k/v 的方式不是一个 k/v 一组, 而是 k 放一块,v 放一块。

    这样的相对 k/v 相邻的好处是,方便内存对齐。比如map[int64]int8, v 是int8,放一块就避免需要额外内存对齐。

    另外对于大的 k/v 也做了优化。

    正常情况 key 和 elem 直接使用用户声明的类型,但当其 size 大于 128(MAXKEYSIZE/MAXELEMSIZE)时,

    则会转为指针去存储。(也就是indirectkey、indirectelem

    • hmap.extra

    这个额外记录溢出桶意义在哪?

    具体是为解决让gc不需要扫描此类bucket

    只要 bmap 内不含指针就不需 gc 扫描。

    mapkeyelem类型都不包含指针时,但其中的overflow是指针。

    此时 bmap 的生成函数会将overflow的类型转化为uintptr

    uintptr虽然是地址,但不会被gc认为是指针,指向的数据有被回收的风险。

    此时为保证其中的overflow指针指向的数据存活,就用mapextra结构指向了这些buckets,这样 bmap 有被引用就不会被回收了。

    关于 uintptr 可能被回收的例子,可以看下 go101 - Type-Unsafe Pointers 中 Some Facts in Go We Should Know

    0x02 map 的 hash 方式

    了解 map 的基本结构后,我们通过下边代码分析下 map 的 hash

    var m = map[interface{}]int{}
    var i interface{} = []int{}
    //panic: runtime error: hash of unhashable type []int
    println(m[i])
    //panic: runtime error: hash of unhashable type []int
    delete(m, i)
    

    为什么不可以用[]int作为 key 呢?

    查找源码中 hash 的调用链注释如下:

    // runtime/map.go
    // mapassign,mapaccess1 中 获取 key 的 hash
    hash := t.hasher(key, uintptr(h.hash0))
    
    // cmd/compile/internal/gc/reflect.go
    func dtypesym(t *types.Type) *obj.LSym {
      switch t.Etype {
        // ../../../../runtime/type.go:/mapType
      case TMAP:
        ...
        // 依据 key 构建 hash 函数
        hasher := genhash(t.Key())
        ...
      }
    }
    
    // cmd/compile/internal/gc/alg.go
    func genhash(t *types.Type) *obj.LSym {
      switch algtype(t) {
      ...
      //具体针对 interface 调用 interhash
      case AINTER:
        return sysClosure("interhash")
      ...
      }
    }
    
    // runtime/alg.go
    func interhash(p unsafe.Pointer, h uintptr) uintptr {
      //获取 interface p 的实际类型 t,此处为 slice
      a := (*iface)(p)
      tab := a.tab
      t := tab._type
      // slice 类型不可比较,没有 equal 函数
      if t.equal == nil {
        panic(errorString("hash of unhashable type " + t.string()))
      }
      ...
    }
    

    如上,我们会发现 map 的 hash 函数并不唯一。

    它会对不同 key 类型选取不同的 hash 方式,以此加快 hash 效率

    这个例子slice不可比较,所以不能作为 key。

    也对,不可比较的类型作为 key 的话,找到桶但没法比较 key 是否相等,那 map 用这个 key 读写都会是个问题。

    还有哪些不可比较?

    cmd/compile/internal/gc/alg.goalgtype1 函数中可以找到返回ANOEQ(不可比较类型)的类型,如下:

    • func,map,slice
    • 内部元素有这三种类型的 array 和 struct 类型

    0x03 map 的扩容方式

    map不可以对其值取地址;

    如果值类型为slicestruct,不能直接操作其内部元素

    我们用代码验证如下:

    m0 := map[int]int{}
    // ❎ cannot take the address of m0[0]
    _ = &m0[0]
    
    m := make(map[int][2]int)
    // ✅
    m[0] = [2]int{1, 0}
    // ❎ cannot assign to m[0][0]
    m[0][0] = 1
    // ❎ cannot take the address of m[0]
    _ = &m[0]
    
    type T struct{ v int }
    ms := make(map[int]T)
    // ✅
    ms[0] = T{v: 1}
    // ❎ cannot assign to struct field ms[0].v in map
    ms[0].v = 1
    // ❎ cannot take the address of ms[0]
    _ = &ms[0]
    }
    

    为什么呢?

    这是因为map内部有渐进式扩容,所以map的值地址不固定,取地址没有意义。

    也因此,对于值类型为slicestruct, 只有把他们各自当做整体去赋值操作才是安全的。go 有个 issue 讨论过这个问题:issues-3117

    针对扩容的方式,有两类,分别是:

    • sameSizeGrow

    过多的overflow使用,使用等大小的 buckets 重新整理,回收多余的overflow桶,提高 map 读写效率,减少溢出桶占用

    这里借助hmap.noverflow来判断溢出桶是否过多

    hmap.B<=15 时,判断是溢出桶是否多于桶数1<<hmap.B

    否则只判断溢出桶是否多于 1<<15

    这也就是为啥hmap.noverflow,当其接近1<<15 - 1时为近似值, 只要可以评估是否溢出桶过多不合理就行了

    • biggerSizeGrow

    count/size > 6.5 (装载因子 :overLoadFactor), 避免读写效率降低。

    扩容一倍,并渐进的在赋值和删除(mapassign 和 mapdelete)期间,

    对每个桶重新分流到x(原来桶区间)和y(扩容后的增加的新桶区间)

    这里overLoadFactor ( count/size )是评估桶的平均装载数据能力,即 map 平均每个桶装载多少个 k/v。

    这个值太大,则桶不够用,会有太多溢出桶;太小,则分配了太多桶,浪费了空间。

    6.5 是测试后对 map 装载能力最大化的一个的选择。

    源码中扩容代码注释如下:

    // mapassign 中创建新 bucket 时检测是否需要扩容
    if !h.growing() && //非扩容中
      (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
      // 提交扩容,生成新桶,记录旧桶相关。但不开始
      // 具体开始是后续赋值和删除期间渐进进行
      hashGrow(t, h)
    }
    
    //mapassign 或 mapdelete 中 渐进扩容
    bucket := hash & bucketMask(h.B)
    if h.growing() {
      growWork(t, h, bucket)
    }
    
    // 具体迁移工作执行,每次最多两个桶
    func growWork(t *maptype, h *hmap, bucket uintptr) {
      // 迁移对应旧桶
      // 若无迭代器遍历旧桶,可释放对应的 overflow 桶或 k/v
      // 全部迁移完则释放整个旧桶
      evacuate(t, h, bucket&h.oldbucketmask())
    
      // 如果还有旧桶待迁移,再迁移一个
      if h.growing() {
        evacuate(t, h, h.nevacuate)
      }
    }
    

    具体扩容evacuate(迁移)时,判断是否要将旧桶迁移到新桶后半区间(y)有段代码比较有趣, 注释如下:

    newbit := h.noldbuckets()
    var useY uint8
    if !h.sameSizeGrow() {
      // 获取 hash
      hash := t.hasher(k2, uintptr(h.hash0))
      if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
      // 这里 key != key 是指 key 为 NaNs,
      // 此时 useY = top & 1 意味着有 50%的几率到新桶区间
        useY = top & 1
        top = tophash(hash)
      } else {
        if hash&newbit != 0 {
      // 举例来看 若扩容前 h.B=3 时, newbit=1<<3
      // hash&newbit != 0 则 hash 形如 xxx1xxx
      // 新 hmap 的 BucketMask= 1<<4 - 1 (1111: 15)
      // 则 hash&新 BucketMask > 原 BucketMask 1<<3-1 (111: 7)
      // 所以去新桶区间
          useY = 1
        }
      }
    }
    
    // 补充一个 key != key 的代码示例
    n1, n2 := math.NaN(), math.NaN()
    m := map[float64]int{}
    m[n1], m[n2] = 1, 2
    println(n1 == n2, m[n1], m[n2])
    // output: false 0 0
    // 所以 NaN 做 key 没有意义。。。
    

    弄清楚 map 的结构、hash 和扩容,剩下的就是初始化、读写、删除和遍历了,我们就不详细展开了,简单过下。

    0x04 map 的初始化

    map 不初始化时为 nil,是不可以操作的。可以通过 make 方式初始化

    // 不指定大小
    s := make(map[int]int)
    // 指定大小
    b := make(map[int]int,10)
    

    对于这两种 map 内部调用方式是不一样的

    • small map

    当不指定大小或者指定大小不大于 8 时,调用

    func makemap_small() *hmap {

    只需要直接在堆上初始化hmap和 hash 种子(hash0)就行。

    • bigger map

    当大小大于 8, 调用

    func makemap(t *maptype, hint int, h *hmap) *hmap {

    hint溢出则置 0

    初始化hmap和 hash 种子

    根据overLoadFactor:6.5的要求, 循环增加h.B, 获取 hint/(1<<h.B) 最接近 6.5 的h.B

    预分配 hashtable 的 bucket 数组

    h.B 大于 4 的话,多分配至少1<<(h.B-4)(需要内存对齐)个 bucket,用于可能的overflow桶使用,

    并将 h.nextOverflow设置为第一个可用的overflow桶。

    最后一个overflow桶指向h.buckets(方便后续判断已无overflow桶)

    0x05 map 的读取

    对于 map 的读取有着三个函数,主要区别是返回参数不同

    mapaccess1: m[k]
    mapaccess2: a,b = m[i]
    mapaccessk: 在 map 遍历时若 grow 已发生,key 可能有更新,需用此函数重新获取 k/v
    

    计算 key 的 hash,定位当前 buckets 里桶位置

    如果当前处于扩容中,也尝试去旧桶取对应的桶,需考虑扩容前 bucket 大小是否为现在一半,且其所指向的桶未迁移

    然后就是按照 bucket->overflow 链表的顺序去遍历,直至找到tophash匹配且 key 相等的记录( entry )

    期间,如果 key 或者 elem 是转过指针( size 大于 128 ),需转回对应值。

    map 为空或无值返回 elem 类型的零值

    0x06 map 的赋值

    计算 key 的 hash,拿到对应的桶

    如果此时处于扩容期间,则执行扩容growWork

    对桶 bucket->overflow 链表遍历

    • 若有空桶(对应 tophash[i]为空),则准备在此空桶存储 k/v

    • 若非空,且和 tophash 相等,且 key 相等,则更新对应 elem

    • 若无可用桶,则分配一个新的 overflow 桶来存储 k/v, 会判断是否需要扩容

    最后若使用了空桶或新overflow桶,则要将对应tophash更新回去, 如果需要的话,也更新count

    0x07 map 的删除

    获取待删除 key 对应的桶,方式和 mapassign 的查找方式基本一样,找到则清除 k/v。

    这里还有个额外操作:

    如果当前 tophash 状态是:当前 cell 为空(emptyOne),

    若其后桶或其后的 overflow 桶状态为:当前 cell 为空前索引高于此 cell 的也为空(emptyRest),则将当前状态也更新为emptyRest

    倒着依次往前如此处理,实现 emptyOne -> emptyRest的转化

    这样有什么好处呢?

    答案是为了方便读写删除(mapaccess,mapassign,mapdelete)时做桶遍历(bucketLoop)能减少不必要的空 bucket 遍历

    截取代码如下:

    bucketloop:
      for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
          if b.tophash[i] != top {
            // 减少空 cell 的遍历
            if b.tophash[i] == emptyRest {
              break bucketloop
            }
            continue
          }
        ...
      }
    

    0x08 map 的遍历

    先调用mapiterinit 初始化用于遍历的 hiter结构体, 这里会用随机定位出一个起始遍历的桶hiter.startBucket, 这也就是为啥 map 遍历无序。

    随机获取起始桶的代码如下:

    r := uintptr(fastrand())
    // 随机数不够用得再加一个 32 位
    if h.B > 31-bucketCntBits {
      r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    

    在调用mapiternext去实现遍历, 遍历中如果处于扩容期间,如果当前桶已经迁移了,那么就指向新桶,没有迁移就指向旧桶


    至此,map 的内部实现我们就过完了。

    里边有很多优化点,设计比较巧妙,简单总结一下:

    • 以 2 的对数存储桶数,便于优化 hash 模运算定位桶,也利于扩容计算
    • 每个 map 都随机 hash 种子,减少哈希碰撞的几率
    • map 以 key 的类型确定 hash 函数,对不同类型针对性优化 hash 计算方式
    • 桶内部 k/v 并列存储,减少不必要的内存对齐浪费;对于大的 k/v 也会转为指针,便于内存对齐和控制桶的整体大小
    • 桶内增加 tophash 数组加快单元定位,也方便单元回收(空桶)标记
    • 当桶 8 个单元都满了,还存在哈希冲突的 k/v,则在桶里增加 overflow 桶链表存储
    • 桶内若只有 overflow 桶链表是指针,则 overflow 类型转为 uintptr,并使用 mapextra 引用该桶,避免桶的 gc 扫描又保证其 overflow 桶存活
    • 写操作增加新桶时如果需要扩容,只记录提交,具体执行会分散到写操作和删除操作中渐进进行,将迁移成本打散
    • 哈希表的装载因子不满足要求是,扩容一倍,保证桶的装载能力
    • 哈希表 overflow 桶过多,则内存重新整理,减少不必要的 overflow 桶,提升读写效率
    • 对指定不同大小的 map 初始化,区别对待,不必要的桶预分配就避免;桶较多的情况下,也增加 overflow 桶的预分配
    • 每次遍历起始位置随机,严格保证 map 无序语义
    • 使用 flags 位标记检测 map 的并发读写,发现时 panic,一定程度上预防数据不一致发生

    趁热打铁,建议你再阅读一遍源码,加深一下理解。

    附上几篇不错的源码分析文章,代码对应的go版本和本文不一致,但变化不大,可以对照着看。

    本文代码见 NewbMiao/Dig101-Go


    欢迎关注公众号:newbmiao,获取及时更新文章。

    推荐阅读:Dig101-Go 系列,挖一挖技术背后的故事。

    4 条回复    2020-03-10 08:39:17 +08:00
    hanssx
        1
    hanssx  
       2020-03-09 23:22:10 +08:00
    源码分析的都是大佬,话说 C 语言用的真是广泛,经久不衰,甚至盖住了 C++的光芒。。。
    wellsc
        2
    wellsc  
       2020-03-09 23:27:39 +08:00
    @hanssx c++ 什么时候盖住过 C 的光芒过了
    CEBBCAT
        3
    CEBBCAT  
       2020-03-10 02:09:43 +08:00 via Android
    感谢分享,明早再看
    newmiao
        4
    newmiao  
    OP
       2020-03-10 08:39:17 +08:00
    @hanssx go 最初是 c 写的,后边自解释了,但源码风格还是有些相似
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1033 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 22:11 · PVG 06:11 · LAX 14:11 · JFK 17:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.