前言
在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种方案应该已经能够解决日常开发的问题了.