前言

在Go中, map这个结构使用的频率还是比较高的. 其实在所有的语言中, map使用的频率都是很高的.

之前在使用中, 一直都知道map的内存在元素删除的时候不会回收, 但一直没有仔细的研究为什么. 今天就来好好揣摩揣摩.

func main() {
    m := make(map[int][128]byte)
    for i := 0; i < 100000; i++ {
        b := [128]byte{}
        for j := 0; j < 128; j++ {
            b[j] = byte(j + 1)
        }
        m[i] = b
    }
    // 打印堆内存
    var ms runtime.MemStats
    runtime.ReadMemStats(&ms)
    fmt.Printf("堆内存: %d B, map size: %d\n", ms.Alloc, len(m))
    // 释放 map
    for i := 0; i < 100000; i++ {
        delete(m, i)
    }
    runtime.ReadMemStats(&ms)
    fmt.Printf("堆内存(释放后): %d B, map size: %d\n", ms.Alloc, len(m))
    // 手动触发 GC
    runtime.GC()
    runtime.ReadMemStats(&ms)
    fmt.Printf("堆内存(GC): %d B, map size: %d\n", ms.Alloc, len(m))
    // 保存 map 的引用，防止 GC 回收
    runtime.KeepAlive(m)
}

老规矩, 还是先来说说是个什么现象(本文所有例子, 基于 Go1.18)). 如果你运行这个程序, 那么会得到这样的结果:

堆内存: 32197640 B, map size: 100000
堆内存(释放后): 32198752 B, map size: 0
堆内存(GC): 21113120 B, map size: 0

可以看到, 再将map内容清空后, 运行GC, 内存占用仍高达20M. 而这个现象, 就是在前面提到过的, Go中的map内存占用只会增加不会减少.

探究

gdb 分析

为了知道map在Go中的具体实现, 我通过gdb将m的类型打印了出来, 这是ptype m的结果:

type = struct hash<int,[128]uint8> {
int count;
uint8 flags;
uint8 B;
uint16 noverflow;
uint32 hash0;
bucket<int,[128]uint8> buckets;
bucket<int,[128]uint8> oldbuckets;
uintptr nevacuate;
runtime.mapextra *extra;
}

hash结构体明显是编辑器编译过后的, 为了方便, 我直接在源码中通过字段名搜索, 果然找到了字段一模一样的结构体hmap, 此结构体位于runtime/map.go文件中.

再使用print *m命令查看不同阶段结构体中的内容:

初始化之前:

{count = 0, flags = 0 ‘\000’, B = 0 ‘\000’, noverflow = 0, hash0 = 2403831944, buckets = 0xc00013e380, oldbuckets = 0x0, nevacuate = 0, extra = 0x0}

初始化之后:

{count = 100000, flags = 0 ‘\000’, B = 14 ‘\016’, noverflow = 2679, hash0 = 4095224677, buckets = 0xc001540000, oldbuckets = 0x0, nevacuate = 8192, extra = 0xc00012c018}

delete 所有内容之后:

{count = 0, flags = 0 ‘\000’, B = 14 ‘\016’, noverflow = 2679, hash0 = 112371461, buckets = 0xc001540000, oldbuckets = 0x0, nevacuate = 8192, extra = 0xc00012c018}

GC 之后:

{count = 0, flags = 0 ‘\000’, B = 14 ‘\016’, noverflow = 2679, hash0 = 112371461, buckets = 0xc001540000, oldbuckets = 0x0, nevacuate = 8192, extra = 0xc00012c018}

可以看到, 删除所有内容之后, 只有count的值发生了变化. 分析到这里, 就必须要看一下map是如果实现的了,

map原理

如果你对Java中HashMap的实现有了解, 那么这里也一样, 数组+链表来实现hash表.

在内存的分布上, map大致是这样的一个结构:

其中每个Bucket都可以保存8个KV, 数据在存放的时候, 会根据hash函数的结果得出在Bucket 列表的偏移量, 然后将值放到对应的位置.

overflow Bucket是当Bucket自身存放不下时, 与其组成链表来容纳更多数据

至于Bucket结构体为什么要将K/V分开放, 在源码中也给出解释了, 如果将K/V放到一起, 遇到map[int8]int64这样的, 就会遇到内存对齐的问题, 浪费一部分内存.

插入

插入操作通过调用mapassign函数, 其大体步骤如下:

使用hash 值定位元素在哪一个 Bucket 中
遍历 Bucket 中的元素, 找到第一个空位, 将数据插入

如何处理 hash 冲突

殊途同归, Go中已然是用链表来解决hash冲突的.

我们不是通过 hash 来确定了元素存放在哪一个bucket中嘛. 其实, 每一个Bucket就是一个链表. 它的extraBucket字段用来链接到链表的下一个元素. 只不过这个链表中, 每个元素都可以存放8个K/V.

如何快速找到空位

遍历Bucket内容时, 为了快速定位, 加了一个小小的缓存, 会将key的hash值高8位存起来, 用于快速比较是否相等.

扩容机制

Go中, map每次扩容都会将原来的容量乘2, 也是有一个指数因子来判断是否需要扩容. 大差不差.

查看和修改的操作, 在这里就不赘述了, 按照插入的流程寻找元素即可.

删除

map元素删除的操作十分简单, 可以看下源码实现. 简单说来就是:

找到元素
将key/value的内容清空
将长度count减1

结构体

简单介绍下hmap各个字段的含义:

type hmap struct {
    count     int // 当前 map 中元素个数, len 函数用的就是它
    flags     uint8 // 标志位
    B         uint8  // 指数, 标识当前桶的个数为 2^B
    noverflow uint16 // 溢出桶的大致数目
    hash0     uint32 // 随机种子

    buckets    unsafe.Pointer // Bucket 数组指针
    oldbuckets unsafe.Pointer // 数组扩容时迁移过程中指向就地址的
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // 用来组成 Bucket 链表的内容
}
type mapextra struct {
    overflow    *[]*bmap // 指向溢出Bucket的地址
    oldoverflow *[]*bmap // 同上, 迁移过程使用
    nextOverflow *bmap // 指向第一个空闲的 Bucket, 追加时可快速获取到
}

解惑

现在对Go中的map有了一定的了解了, 再回来看最开始的问题, 为什么内存没有被回收呢? 很简单, 删除元素的时候, 仅仅是将key/value内容置空, 但map占用的内存仍然没有释放. 删除后再向map中添加数据, 是可以使用已经清空内存的.

也就是说, 在将数据从map中删除的时候, 仅仅是map自身的内存没有被回收, value中存放的如果是一个结构体, 那么是不影响结构体本身GC的.

为了验证这个猜想, 你可以将最开始例子中的map换成map[int][1024]byte 或map[int]*[128]byte, 再次运行就会发现, GC后内存占用明显下降了. 更换指针很容易理解, 增大value的内存占用, 也会让Go在编译期将其转为指针类型.

解决

到这里, 我们知道了map自身的内存占用只增不减, 也知道了为什么会出现这个问题.

那么, 如何解决呢? 如果不进行解决, 在某一个流量高峰期, map中保存了大量的数据, 后面流量降下来了, 但是map的内存占用会居高不下.

我简单想了几种方案:

定期备份. 每个一段时间, 将整个map拷贝一份到新的map中
value使用指针类型, 这样map中保留的内存仅为指针所占空间, 与value大小无关. 而value的对象是会被GC回收的. 我简单测试了下, map[int]*[128]byte类型的map, 100w 元素, 全部删除后GC, 内存占用(map自身)仅为38M.

当然了, 肯定还有很多花里胡哨的解决方案, 比如使用多个小map等等, 但这2种方案应该已经能够解决日常开发的问题了.

原文地址 https://hujingnb.com/archives/894

转载请保留原文连接: Go map 内存泄露 | 烟草的香味