TCMalloc - Go的内存分配原理

Golang的内存分配机制主要基于TCMalloc机制,本文根据TCMalloc : Thread-Caching Malloc一文了解原理并总结笔记。

TCMalloc - Go的内存分配原理

本文参考自:

TCMalloc : Thread-Caching Malloc

Sanjay Ghemawat, Paul Menage opensource@google.com

1 简介

TCMalloc(Thread-Caching Malloc)是Google发布的一款线程缓存型内存分配机制。TCMalloc为每一个线程都缓存一些可分配内存,因此,在多线程场景下,TCMalloc能够尽可能规避多个线程同时分配/释放内存时的锁争用问题,这使得TCMalloc相较于其它内存分配机制,内存分配和回收速度更快。另外,TCMalloc还有内存分配利用率高的优势。

2 原理

TCMalloc通过Thread Cache和Central Heap组成的双层结构分配内存。

Thread Cache and Central Heap

线程分配内存时,TCMalloc从该线程的线程缓存(Thread Cache)中取出恰当尺寸的内存块。而线程释放回线程缓存的内存,也会由垃圾回收机制收纳回中央堆区(Central Heap)。具体地,TCMalloc的内存分配分两种情况:

  1. 小对象分配(小于等于32KB)
  2. 大对象分配(大于32KB)

2.1 小对象分配

当线程请求分配不超过32KB的小对象时,线程缓存为其分配恰当尺寸的内存块。

Free Objects Linked List of Thread Cache

线程缓存(Thread Cache)维护着一个数组到单向链表的数据结构,数组中的每一个节点都从小到大依次代表一个可分配尺寸(共约170种尺寸),每个尺寸以单链表的形式维护该尺寸的可分配内存。

当一个线程请求分配内存时:

  1. 首先根据内存需求,找到合适的尺寸(例如:申请961~1024字节,均分配1024字节的内存对象);
  2. 在该尺寸的链表上,检查是否有可分配内存块:
    1. 如果有该尺寸的内存对象,那么取出链表中第一个可分配内存块供线程使用即可;
    2. 如果没有该尺寸的内存对象,那就得从中央堆区去拿一些内存来用:
      1. 如果中央堆区有该尺寸的内存,那么就取过来用就可以了。将取来的一些内存对象补充到该尺寸的链表里,并从补充后的链表中拿一个内存对象出来供线程使用;
      2. 如果连中央堆区也没有该尺寸的内存了,那就需要为其补充更多的内存:
        1. 通过中央页分配器(central page allocator)来分配内存页(page);
        2. 将分配到的内存页分解为该尺寸的一系列对象;
        3. 把分解出的这些对象补充到中央堆区该尺寸的链表上;
        4. 既然中央堆区补充好该尺寸的内存了,那就照常拿一些补充到请求线程的线程缓存中,供其分配使用。

2.2 大对象分配

超过32K的大对象以4K的内存页为单位进行分配。直接由中央堆区负责维护空页,通过链表分别归纳维护长度为1~255页的空内存块,长度超过255页的内存块则由rest链表统一管理。

List of Various Page Sizes

当请求内存时,根据需求的页面数量找到对应页面数的链表;

  1. 如果链表内有内存,则分配;
  2. 如果链表内没有内存,则找下一个更大尺寸的链表,
    1. 如果找到了,则分配内存,并将剩余页面插入对应尺寸的链表中;
    2. 如果整个中央堆区都找不到合适尺寸的内存,则向操作系统申请内存以补充到中央堆区中。

2.3 Spans

TCMalloc通过span对象来组织内存页。一个span代表一些连续的内存页。

通过一个数据结构来维护从页号到span地址的映射:

Central Array of Pages' Span Addresses

在32位环境下,32位的地址能够寻址2^32B的内存空间,如果按每个内存页4KB的尺寸进行分页,总共2^20,即1M个页号。每个span地址为32位,即4B,那么通过4MB的数组就能够实现从页号到span地址的寻址。

在64位环境下,考虑到地址空间很大,因此通过一个3层的基数树(radix tree)来建立页号到span地址的映射。

2.4 释放

当内存对象释放时,首先根据内存页号查出对应的span对象。通过span对象进行判断:

  1. 如果是小对象,则将其插入其线程缓存中对应尺寸的空闲链表(free list)中。
    1. 如果线程缓存超出了预设尺寸(默认2MB),则需要运行垃圾回收,将线程缓存中不用的对象还给中央堆的空闲链表。
  2. 如果是大对象,则将span管理的内存页与相邻内存页合并后,还给中央堆区的空闲链表。

2.5 线程缓存的垃圾回收

当线程缓存中的空余内存超过阈值(默认2MB)时,会触发垃圾回收,把线程缓存中的内存还给中央堆区的空闲链表。

当线程数量增加时,垃圾回收阈值会减小,以免线程数量很多时浪费内存空间。

垃圾回收机制会记录线程缓存中每一个空闲链表的低水位L。L指的是自上一次垃圾回收以来该链表的最短长度。TCMalloc每次将空闲链表中L/2个内存对象回收到中央堆区。每次回收L/2,这样的回收速度能够很快地将长期不用的空闲链表回收到中央堆区的空闲链表中,以便其他有需要的线程快速获取。