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