轉(zhuǎn)載:深入 Go 內(nèi)存分配超級棒的文章：Go 內(nèi)存分配器可視化指南
本文譯者：coldnight
譯文原鏈接：https://github.com/coldnight/go-memory-allocator-visual-guide
當我第一次開始嘗試理解 Go 語言的內(nèi)存分配器時，整個過程讓我抓狂。一切看起來都像一個神秘的黑盒子。因為幾乎所有技術魔法（technical wizardry）都隱藏在抽象之下，所以你需要一層一層的剝離才能去理解它。
我們將通過這篇文章來一層層的剝離這些細節(jié)。如果你想學習所有關于 Go 內(nèi)存分配器的知識，那么這篇文章正適合你。
物理內(nèi)存和虛擬內(nèi)存
每一個內(nèi)存分配器都需要運行在由底層操作系統(tǒng)管理的虛擬內(nèi)存空間（Virtual Memory Space）之上。
下圖是一個物理內(nèi)存單元（Physical Memory Cell）的簡要說明（非精準）
A simple illustration of a Physical Memory Cell
一個內(nèi)存單元的概述經(jīng)過大大簡化之后描述如下：
地址線（Address line）（晶體管做的開關）用于訪問電容器（數(shù)據(jù)到數(shù)據(jù)線（Data Lines））。
如果地址線有電流流動（顯式為紅色），數(shù)據(jù)線可以寫入到電容器，所以電容器帶電，邏輯值表示 “1”。
如果地址線沒有電流流動（顯式為綠色），數(shù)據(jù)線不可以寫入到電容器，所以電容器不帶電，邏輯值表示 “0”
當 CPU 需要從 RAM 中“讀取”值，則順著“地址線（ADDRESS LINE）”（關閉開關）發(fā)送一個電流。如果電容器帶電，則電流流向“數(shù)據(jù)線（DATA LINE）”（值為 1）；否則沒有電流流向數(shù)據(jù)線，所以電容器保持不帶電（值為 0）。
下圖簡單的描述 CPU 和物理內(nèi)存單元如何交互
Simple Illustration of how a Physical Memory Cell interacts with CPU
數(shù)據(jù)總線（Data Bus）：用于在 CPU 和內(nèi)存中間傳輸數(shù)據(jù)。
還有一點關于地址線（Address line）和按字節(jié)尋址（Addressable bytes）。
下圖是 CPU 和物理內(nèi)存之間地址線的說明
Illustrative Representation of an Address Line between CPU and Physical Memory.
DRAM 中的每一個字節(jié)都分配了一個唯一的數(shù)字標識符（地址）?！?b>物理字節(jié) != 地址線的數(shù)量（Physical bytes present != Number of address line）”（e.g. 16 位 Intel 8088、PAE）
每一個“地址線”可以發(fā)送 1-bit 的值，用于表示給定字節(jié)地址中的“一個位（SINGLE BIT）”
在我們的上面給出的圖中，我們有 32 個地址線。所以每個?字節(jié)（BYTE）?都有“32 位”作為地址。
[ 00000000000000000000000000000000 ]—? 低內(nèi)存地址
[ 11111111111111111111111111111111 ]—? 高內(nèi)存地址
由于我們每字節(jié)都有一個 32 位的地址，所以我們的地址空間包含 2 的 32 次方個可尋址字節(jié)（bytes）（4GB）。
綜上所述，可尋址的字節(jié)數(shù)量取決于地址總線的數(shù)量，所以對于 64 個地址線最大可尋址 2 的 64 次方個字節(jié)數(shù)（16 EB），但是由于大部分架構實際上僅使用 48-bit 地址線（AMD）和 42-bit 地址線（Intel）作為 64-bit 指針，所以理論上允許 256TB 物理內(nèi)存（Linux 在 x86-64 下通過 with 4 level page tables 允許每個處理器 128TB 地址空間，Windows 192TB）。
由于物理內(nèi)存的大小是受限制的，所以進程運行在自身的內(nèi)存沙盒內(nèi) -- “虛擬內(nèi)存地址（virtual address space）”，稱作?虛擬內(nèi)存（Virtual Memory）。
字節(jié)的地址在這個虛擬地址空間內(nèi)不再和處理器放在地址總線上的地址相同。因此必須建立轉(zhuǎn)換數(shù)據(jù)結構和系統(tǒng)將虛擬地址空間中的字節(jié)映射到物理字節(jié)。
虛擬地址表示參見下圖（/proc/$PID/maps）：
Virtual Address Space Representation
綜上所述當 CPU 執(zhí)行一個指令需要引用內(nèi)存地址時。首先將在 VMA（Virtual Memory Areas）中的邏輯地址轉(zhuǎn)換為線性地址。這個轉(zhuǎn)換通過 MMU 完成。
This is not a physical diagram, only a depiction. address translation process not included for simplicity
由于邏輯地址太大幾乎很難獨立的管理，所以引入術語?頁（pages）?進行管理。當必要的分頁操作被激活后，虛擬地址空間被分成更小的稱作頁的區(qū)域（大部分操作系統(tǒng)下是 4KB，可以修改）。頁是虛擬內(nèi)存中數(shù)據(jù)內(nèi)存管理的最小單元。虛擬內(nèi)存不存儲任何內(nèi)容，只是簡單的將程序地址空間映射到底層物理內(nèi)存之上。
獨立的進程只能使用 VMA 作為他們的地址。所以當我們的程序需要更多 “堆內(nèi)存（heap memory）時發(fā)生了什么？
下圖是簡單的匯編代碼用于分配更多的堆內(nèi)存
A simple assembly code asking for more heap memory.
下圖描述堆內(nèi)存的增長
heap memory increment
應用程序通過系統(tǒng)調(diào)用?brk[1]（sbrk/mmap?等）獲得內(nèi)存。內(nèi)核僅更新堆 VMA 并調(diào)用它。
當前時間點實際上不分配頁幀且新頁在物理內(nèi)存中并不存在。這也是 VSZ 和 RSS 大小的不同點。
內(nèi)存分配器
通過對“虛擬地址空間”基本了解和它對在堆分配的意義，內(nèi)存分配器現(xiàn)在變得更加容易解釋。
如果堆上有足夠的空間的滿足我們代碼的內(nèi)存申請，內(nèi)存分配器可以完成內(nèi)存申請無需內(nèi)核參與，否則將通過操作系統(tǒng)調(diào)用（brk）進行擴展堆，通常是申請一大塊內(nèi)存。（對于?malloc?大默認指的是大于?MMAP_THRESHOLD?個字節(jié) - 128KB）。
但是，內(nèi)存分配器除了更新?brk address?還有其他職責。其中主要的一項就是如何減少?內(nèi)部（internal）和外部（external）碎片和如何快速分配當前塊。考慮我們的程序以串行的方式（p1 到 p4）通過?malloc(size)?函數(shù)申請一塊連續(xù)的內(nèi)存然后通過?free(pointer)?函數(shù)進行釋放。
An external fragmentation demonstration
在 p4 階段由于內(nèi)存碎片化即使我們有足夠的內(nèi)存塊依然無法滿足申請的 6 個連續(xù)的內(nèi)存塊。
所以我們該如何減少內(nèi)存碎片化呢?？答案取決是使用哪種內(nèi)存分配算法，也就是使用哪個底層庫。
我們將簡單看一下一個和 Go 內(nèi)存分配器建模相近的內(nèi)存分配器：TCMalloc。
TCMalloc
TCMalloc 的核心思想是將內(nèi)存分為多個級別縮小鎖的粒度。在 TCMalloc 內(nèi)存管理內(nèi)部分為兩個部分：線程內(nèi)存（thread memory)和頁堆（page heap）。
線程內(nèi)存
每一個內(nèi)存頁都被分為多個固定分配大小規(guī)格的空閑列表（free list） 用于減少碎片化。這樣每一個線程都可以獲得一個用于無鎖分配小對象的緩存，這樣可以讓并行程序分配小對象（<=32KB）非常高效。
Thread Cache (Each Thread gets this Thread Local Thread Cache)
頁堆
TCMalloc 管理的堆由一組頁組成，一組連續(xù)的頁面被表示為 span。當分配的對象大于 32KB，將使用頁堆（Page Heap）進行內(nèi)存分配。
Page Heap (for span management)
當沒有足夠的空間分配小對象則會到頁堆獲取內(nèi)存。如果頁堆頁沒有足夠的內(nèi)存，則頁堆會向操作系統(tǒng)申請更多的內(nèi)存。
Note: 即使 Go 的內(nèi)存分配器最初是基于 TCMalloc，但是現(xiàn)在已經(jīng)有很大的不同。
Go 內(nèi)存分配器
我們知道 Go 運行時（Go Runtime）調(diào)度器在調(diào)度時會將?Goroutines(G)?綁定到?邏輯處理器（P）(Logical Processors）?運行。類似的，Go 實現(xiàn)的 TCMalloc 將內(nèi)存頁（Memory Pages）分為 67 種不同大小規(guī)格的塊。
如果你不熟悉 Go 的調(diào)度器可以先參見《Go scheduler: Ms, Ps & Gs》,然后繼續(xù)閱讀。
Size Classes in Go
如果頁的規(guī)格大小為 1KB 那么 Go 管理粒度為?8192B?內(nèi)存將被切分為 8 個像下圖這樣的塊。
8 KB page divided into a size class of 1KB (In Go pages are maintained at the granularity of 8KB)
Go 中這些頁通過?mspan?結構體進行管理。
mspan
簡單的說，mspan?是一個包含頁起始地址、頁的 span 規(guī)格和頁的數(shù)量的雙端鏈表。
Illustrative Representation of a mspan in Go memory allocator
mcache
Go 像 TCMalloc 一樣為每一個?邏輯處理器（P）（Logical Processors）?提供一個本地線程緩存（Local Thread Cache）稱作?mcache，所以如果 Goroutine 需要內(nèi)存可以直接從?mcache?中獲取，由于在同一時間只有一個 Goroutine 運行在?邏輯處理器（P）（Logical Processors）?上，所以中間不需要任何鎖的參與。
mcache?包含所有大小規(guī)格的?mspan?作為緩存。
Illustrative Representation of a Relationship between P, mcache, and mspan in Go.
由于每個 P 都擁有各自的 mcache，所以從 mcache 分配內(nèi)存無需持有鎖。
對于每一種大小規(guī)格都有兩個類型：
scan?-- 包含指針的對象。
noscan?-- 不包含指針的對象。
采用這種方法的好處之一就是進行垃圾回收時?noscan?對象無需進一步掃描是否引用其他活躍的對象。
mcache 的作用是什么？
<=32K?字節(jié)的對象直接使用相應大小規(guī)格的?mspan?通過?mcache?分配
當 mcache 沒有可用空間時會發(fā)生什么？
從?mcentral?的 mspans 列表獲取一個新的所需大小規(guī)格的?mspan。
mcentral
mcentral?對象收集所有給定規(guī)格大小的 span。每一個?mcentral?都包含兩個 mspan 的列表：
empty?mspanList -- 沒有空閑對象或 span 已經(jīng)被 mcache 緩存的 span 列表
nonempty?mspanList -- 有空閑對象的 span 列表
Illustrative Representation of a mcentral
每一個 mcentral 結構體都維護在?mheap?結構體內(nèi)。
mheap
Go 使用 mheap 對象管理堆，只有一個全局變量。持有虛擬地址空間。
Illustrative Representation of a mheap.
就上我們從上圖看到的：mheap 存儲了 mcentral 的數(shù)組。這個數(shù)組包含了各個的 span 的 mcentral。
central [numSpanClasses]struct{
mcentral mcentral
pad? ? ? [sys.CacheLineSize unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
}
由于我們有各個規(guī)格的 span 的 mcentral，當一個?mcache?從 mcentral 申請?mspan?時，只需要在獨立的?mcentral?級別中使用鎖，所以其它任何?mcache?在同一時間申請不同大小規(guī)格的?mspan?將互不受影響可以正常申請。
對齊填充（Padding）用于確保 mcentrals 以?CacheLineSize?個字節(jié)數(shù)分隔，所以每一個?MCentral.lock?都可以獲取自己的緩存行（cache line），以避免偽共享（false sharing）[2]問題。
當?mcentral?列表空的時候會發(fā)生什么？mcentral?從?mheap?獲取一系列頁用于需要的大小規(guī)格的 span。
free[_MaxMHeapList]mSpanList：一個?spanList?數(shù)組。每一個?spanList?中的?mspan?包含 1 ~ 127（_MaxMHeapList - 1）個頁。例如，free[3]?是一個包含 3 個頁的?mspan?鏈表。free?表示?free list，表示未分配。對應?busy list。
freelarge mSpanList：一個?mspan?的列表。每一個元素(mspan)的頁數(shù)大于 127。通過?mtreap?結構體管理。對應?busylarge。
大于 32K 的對象被定義為大對象，直接通過 mheap 分配。這些大對象的申請是以一個全局鎖為代價的，因此任何給定的時間點只能同時供一個 P 申請。
對象分配流程
大于 32K 的大對象直接從?mheap?分配。
小于 16B 的使用?mcache?的微型分配器分配
對象大小在 16B ~ 32K 之間的的，首先通過計算使用的大小規(guī)格，然后使用?mcache?中對應大小規(guī)格的塊分配
如果對應的大小規(guī)格在?mcache?中沒有可用的塊，則向?mcentral?申請
如果?mcentral?中沒有可用的塊，則向?mheap?申請，并根據(jù) BestFit 算法找到最合適的 mspan。如果申請到的?mspan?超出申請大小，將會根據(jù)需求進行切分，以返回用戶所需的頁數(shù)。剩余的頁構成一個新的?mspan?放回?mheap?的空閑列表。
如果?mheap?中沒有可用 span，則向操作系統(tǒng)申請一系列新的頁（最小 1MB）。
但是 Go 會在操作系統(tǒng)分配超大的頁（稱作 arena）。分配一大批頁會減少和操作系統(tǒng)通信的成本。
所有在堆上的內(nèi)存申請都來自 arena。讓我們看看 arena 是什么。
Go 虛擬內(nèi)存
讓我們看一個簡單的 Go 程序的內(nèi)存情況
funcmain(){
for{}
}
process stats for a program
從上面可以即使是一個簡單的程序虛擬空間占用頁大概?~100MB?左右，但是 RSS 僅僅占用?696KB。讓我們先搞清楚這之間的差異。
map and smap stats.
這里有一塊內(nèi)存區(qū)域大小在 ~?2MB、64MB?和?32MB。這些是什么？
Arena
事實證明 Go 的虛擬內(nèi)存布局中包含一系列?arenas。初始的堆映射是一個?arena，如?64MB（基于 go 1.11.5）。
current incremental arena size on a different system.
所以當前內(nèi)存根據(jù)我們的程序需要以小增量映射，并且初始于一個 arena（~64MB）。
請首先記住這些數(shù)字。主題開始改變。早期 Go 需要預先保留一個連續(xù)的虛擬地址，在一個 64-bit 的系統(tǒng) arena 的大小是 512GB。（如果分配的足夠大且?被 mmap 拒絕?會發(fā)生什么？）
這些 arenas 就是我們所說的堆。在 Go 中每一個 arena 都以?8192B?的粒度的頁進行管理。
下圖表示一個 64MB 的 arena
Single arena ( 64 MB ).
Go 同時存在其他兩個塊：span?和?bitmap。兩者都在堆外分配并且包含每個 arena 的元數(shù)據(jù)。大多用于垃圾回收期間（所以我們就討論到這）。
在我們剛剛討論的 Go 的內(nèi)存分配策略種類里，只涉及到內(nèi)存分配奇妙且多樣性的冰山一角。
然而，Go 內(nèi)存管理的一般思想是使用不同的內(nèi)存結構為不同大小的對象使用不同的內(nèi)存緩存級別來分配內(nèi)存。將一個從操作系統(tǒng)接收的連續(xù)地址的塊切分到多級緩存來減少鎖的使用，同時根據(jù)指定的大小分配內(nèi)存減少內(nèi)存碎片以提高內(nèi)存分配的效率和在內(nèi)存釋放之后加快 GC 運行的速度。
現(xiàn)在我們將通過下圖結束 Go 內(nèi)存分配可視化指南。
Visual Overview of Runtime Memory Allocator.
翻譯參考：
總線內(nèi)部結構[3]
DRAM[4]
PAE[5]
Byte addressing[6]
內(nèi)存管理[7]
原文鏈接?A visual guide to Go Memory Allocator from scratch (Golang)[8]
文中鏈接
[1]brk:?http://man7.org/linux/man-pages/man2/brk.2.html
[2]偽共享（false sharing）:?https://en.wikipedia.org/wiki/False_sharing
[3]總線內(nèi)部結構:?http://share.onlinesjtu.com/mod/tab/view.php?id=253
[4]DRAM:?https://zh.wikipedia.org/zh/%E5%8A%A8%E6%80%81%E9%9A%8F%E6%9C%BA%E5%AD%98%E5%8F%96%E5%AD%98%E5%82%A8%E5%99%A8
[5]PAE:?https://zh.wikipedia.org/wiki/%E7%89%A9%E7%90%86%E5%9C%B0%E5%9D%80%E6%89%A9%E5%B1%95
[6]Byte addressing:?https://www.wikiwand.com/en/Byte_addressing
[7]內(nèi)存管理:?https://www.csie.ntu.edu.tw/~wcchen/asm98/asm/proj/b85506061/chap2/overview.html
[8]A visual guide to Go Memory Allocator from scratch (Golang):?https://blog.learngoprogramming.com/a-visual-guide-to-golang-memory-allocator-from-ground-up-e132258453ed
推薦閱讀
