In computer science, garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program.GC Strategies
- Reference counting
在Object上紀錄reference的次數，被引用時加一，引用對象消失時減一，當Count為0時即可視為垃圾被清除。
優點：方法簡單、回收速度快。
缺點：無法清除有reference cycle的Objects。
Note: Swift使用Automatic Reference Counting
2. Tracing
目前最常見的垃圾回收機制，並有多種不同實作方式。基本架構是將Objects視為一個樹狀結構，從GC roots為出發點開始尋找所有被引用的objects，最終不可到達的objects即可視為垃圾被清除。
2–1. Mark and Sweep
Mark and Sweep是最基本的tracing strategy，從roots開始將所有被引用的objects標記。標記完成後，有標記的objects survive，未標記objects的即可視為垃圾被清除。
缺點：
- 標記過程需要將所有執行中程序暫停(Stop the World)
- 清除過程可能造成Memory fragmentation，並且需要Keep一個free list來記錄memory可用的位置
- 2–2. Mark-Sweep-Compact
在mark and sweep之後，多一個步驟將surviving objects移動整理在一起。
優點：可以避免Memory fragmentation，新的memory allocation也可以比較高效率的進行。
缺點：需要花費額外的整理時間。
2–3. Copying
和 Mark-Sweep-Compact的做法與目標相似，但是會將Memory劃分成兩個不同的區塊，當下只有一個區塊供程序使用，在GC時將該區塊中的 surviving objects複製到另一個區塊，就可以把已經使用過的區塊一次清理掉。
優點：相較Mark-Sweep-Compact，需要花費的整理時間較短。
缺點：需要分配多餘的記憶體空間用於等待下一次複製。
2–4. Generational GC
根據objects存活的週期不同，可劃分出不同的generation，並在記憶體中分開存放。新生的objects多數存活週期不長，因此new generation需要較高頻率的GC來處理。若在GC過程中survive多次的objects則可以歸到old generation，以較低GC頻率處理。
根據不同的generation，也可以選擇使用不同的strategy處理。例如new generation生成的垃圾較多、surviving objects較少，適合使用Copying處理。old generation的surviving objects較多，可以使用Mark-Sweep-Compact處理。
Note: Andriod kotlin是基於JVM，使用的是Generational GC。
Golang’s Garbage Collection
Golang使用的是concurrent, tri-color, mark-sweep的GC機制。
What is tri-color marking?
三色標記法是用三種顏色描述標記過程中objects的狀態。
(A)白色：未被標記的objects
(B)灰色：已被標記且正在處理隊列中的objects
(C)黑色：已被標記且完成處理的objects
How to do concurrent mark?
mark階段過程中，使用者執行程序進行新的allocaction或改變reference，可能造成標記出錯。所以mark階段需要write barrier來確保新的寫操作能被追蹤到。
What is write barrier?
在GC的mark階段，新的pointer賦值操作會先經過write barrier進行標記處理，以避免資料丟失。
從Go 1.8開始使用Hybrid write barrier，將pointer原先的值以及新的賦值對像都標記成灰色。
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(*slot)
shade(ptr)
*slot = ptr
}該方法结合了 Dijkstra write barrier shade(ptr)和 Yuasa write barrier shade(*slot) 的優勢，也使STW所需的時間下降*。但著色的效能成本也雙倍增加，因此Go 1.10 和 Go 1.11 中實現了批量 write barrier的機制，將需要著色的pointer寫入cache再批次進行著色。
*Go 1.8以前只有在stack之外開啟Dijkstra write barrier，因此標記結束的STW須重新掃描stack
When to start a garbage collection in Go?
- GC Pacing計算memory增長的使用量，達到閾值時觸發。
- 系統監控超過2分鐘沒有執行GC時觸發。
- 工程師調用
runtime.GC()來觸發
工程師可以通過GOGC 或者 debug.SetGCPercent 設置參數控制(1) GC觸發的頻率。簡單示意如下圖，GCPercent預設值為100，大致在本次GC執行後的In-use記憶體使用量增長100%時，會觸發下一次GC。
實際上GC Pacing的算法更加複雜，可參考：https://www.bookstack.cn/read/qcrao-Go-Questions/spilt.11.GC-GC.md
Phases of Go's GC
- Mark Setup — STW
- Marking — Concurrent
- Mark Termination — STW
Mark Setup — STW
第一次STW會開啟write barrier的以及進行標記的準備工作。這時需要等所有運行中的Gorutine暫停，一般來說不會花費太多時間。
但如果有其中一個Gorutine無法在短時間內暫停時，另外三個G會先暫停，GC也還無法開始，這會導致當前只有25%的CPU在工作。
例如以下程式碼，由於gorutine無法停止，將永遠Print不出“OK”。
func main() {
go func() {
for {
}
}()
time.Sleep(time.Millisecond)
runtime.GC()
println("OK")
}註：該問題在Go 1.14引入asynchronous preemption後應已得到解決。
Marking — Concurrent
在Marking階段，Garbage collector會使用25%CPU來進行掃描標記工作。
因為同步執行用戶程序，如果執行中的程序allocation的速度超過GC的處理速度時，可能導致GC工作無法完成、或在完成前heap的使用量就超過限制。所以當新的allocation進行時，Go會判斷目前GC的工作量是否可以順利處理完，並適時請申請新allocation的P成為Mark Assist，協助GC處理部分工作量。這會降低用戶程序的執行速度，但可以加快該次GC的完成速度。
Mark Termination — STW
標記工作完成後會需要第二次STW，關閉write barrier並進行一些統計操作。這時如果有gorutine處於無法短時間暫停的狀況，一樣會造成較高的latency。
Sweeping — Concurrent
Why not use compact/copy or generational GC in Go?
Go並沒有採用整理記憶體或分generation的做法，主要和Go的記憶體管理方式有關，大致理由如下，詳細可參閱Go記憶體管理相關文章。
由於使用參照tcmalloc 的方式，將記憶體按size分配，可以避免memory fragmentation的問題，所以不需要整理的步驟。
Go在參數賦值時會使用escape analysis，多數短存活週期的objects會被放在stack上，在程序執行結束時直接被回收，因此不需要對GC處理的heap上的objects區分generation。
Possible issues of Go’s GC
Go的GC機制演進方向主要是為了減少STW停頓的時間，目前Go團隊宣稱Go GC的STW latency已達到100µs的等級，極低的GC latency也使Go很適合編寫web service。然而目前的Go GC仍可能存在一些隱含的成本，是分散在STW latency之外的：
- 大量的memory allocation仍會對Go GC造成壓力。GC過程作為Mark Assist會佔用部分CPU使用時間，使用戶程序運行速度下降，這是沒有算在STW latency內的。
- Go Pacing的觸發閾值會隨記憶體使用量上升，如果高峰時記憶體使用量大量增加，後續達到閾值觸發gc的機率會下降許多，可能要等2min的自動觸發GC。
- 如gorotine由於channel阻塞等原因無法被回收時，仍可能造成memory leak。如果大量創建gorotine並且未能即時回收，也會導致GC持續增加對CPU的使用壓力。
Go的GC機制在每個版本都有一些新的演進，這些或許也是未來會被改善的方向。
參考資料：
