Golang GC/垃圾回收機制

1、簡介

Golang GC 算法使用的是無無分代（對象沒有代際之分）、不整理（回收過程中不對對象進行移動與整理）、并發（與使用者代碼并發執行）的三色标記清掃算法。原因在于：

• 對象整理的優勢是解決記憶體碎片問題以及“允許”使用順序記憶體配置設定器。但 Go 運作時的配置設定算法基于 tcmalloc，基本上沒有碎片問題。 并且順序記憶體配置設定器在多線程的場景下并不适用。Go 使用的是基于 tcmalloc 的現代記憶體配置設定算法，對對象進行整理不會帶來實質性的性能提升。
• 分代 GC 依賴分代假設，即 GC 将主要的回收目标放在新建立的對象上（存活時間短，更傾向于被回收），而非頻繁檢查所有對象。但 Go 的編譯器會通過逃逸分析将大部分新生對象存儲在棧上（棧直接被回收），隻有那些需要長期存在的對象才會被配置設定到需要進行垃圾回收的堆中。也就是說，分代 GC 回收的那些存活時間短的對象在 Go 中是直接被配置設定到棧上，當 goroutine 死亡後棧也會被直接回收，不需要 GC 的參與，進而分代假設并沒有帶來直接優勢。并且 Go 的垃圾回收器與使用者代碼并發執行，使得 STW 的時間與對象的代際、對象的 size 沒有關系。Go 團隊更關注于如何更好地讓 GC 與使用者代碼并發執行（使用适當的 CPU 來執行垃圾回收），而非減少停頓時間這一單一目标上。

2、三色标記法

三色标記法将對象分為三類，并用不同的顔色相稱：

• 白色對象（可能死亡）：未被回收器通路到的對象。在回收開始階段，所有對象均為白色，當回收結束後，白色對象均不可達。
• 灰色對象（波面）：已被回收器通路到的對象，但回收器需要對其中的一個或多個指針進行掃描，因為他們可能還指向白色對象。
• 黑色對象（确定存活）：已被回收器通路到的對象，其中所有字段都已被掃描，黑色對象中任何一個指針都不可能直接指向白色對象。

标記過程如下：

（1）起初所有的對象都是白色的；

（2）從根對象出發掃描所有可達對象，标記為灰色，放入待處理隊列；

（3）從待處理隊列中取出灰色對象，将其引用的對象标記為灰色并放入待處理隊列中，自身标記為黑色；

（4）重複步驟（3），直到待處理隊列為空，此時白色對象即為不可達的“垃圾”，回收白色對象；

3、屏障機制

3.1、為什麼需要屏障機制

        一個白色對象被黑色對象引用，是注定無法通過這個黑色對象來保證自身存活的，與此同時，如果所有能到達它的灰色對象與它之間的可達關系全部遭到破壞，那麼這個白色對象必然會被視為垃圾清除掉。 故當上述兩個條件同時滿足時，就會出現對象丢失的問題。

        如果這個白色對象下遊還引用了其他對象，并且這條路徑是指向下遊對象的唯一路徑，那麼他們也是必死無疑的。

        為了防止這種現象的發生，最簡單的方式就是STW，直接禁止掉其他使用者程式對對象引用關系的幹擾，但是STW的過程有明顯的資源浪費，對所有的使用者程式都有很大影響，如何能在保證對象不丢失的情況下合理的盡可能的提高GC效率，減少STW時間呢？

        在Golang中使用并發的垃圾回收，也就是多個指派器與回收器并發執行，與此同時，應用屏障技術來保證回收器的正确性。其原理主要就是破壞上述兩個條件之一。

3.2、屏障機制原理

當回收器滿足下面兩種情況之一時，即可保證不會出現對象丢失問題。

弱三色不變式：所有被黑色對象引用的白色對象都處于灰色保護狀态（直接或間接從灰色對象可達）。 強三色不變式：不存在黑色對象到白色對象的指針。

強三色不變式很好了解，強制性的不允許黑色對象引用白色對象即可。而弱三色不變式中，黑色對象可以引用白色對象，但是這個白色對象仍然存在其他灰色對象對它的引用，或者可達它的鍊路上遊存在灰色對象。

三色抽象除了可以用于描述對象的狀态的，還可用來描述指派器的狀态，如果一個指派器已經被回收器掃描完成，則認為它是黑色的指派器，如果尚未掃描過或者還需要重新掃描，則認為它是灰色的指派器。

在強三色不變式中，黑色指派器隻存在到黑色對象或灰色對象的指針，因為此時所有黑色對象到白色對象的引用都是被禁止的。 在弱三色不變式中，黑色指派器允許存在到白色對象的指針，但這個白色對象是被保護的。

上述這些可以通過屏障技術來保證。

3.3、插入屏障（Dijkstra）- 灰色指派器

寫入前，對指針所要指向的對象進行着色

// 灰色指派器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr) //先将新下遊對象 ptr 标記為灰色
    *slot = ptr
}

//說明：
添加下遊對象(目前下遊對象slot, 新下遊對象ptr) {   
  //step 1
  标記灰色(新下遊對象ptr)   
  
  //step 2
  目前下遊對象slot = 新下遊對象ptr                    
}

//場景：
A.添加下遊對象(nil, B)   //A 之前沒有下遊， 新添加一個下遊對象B， B被标記為灰色
A.添加下遊對象(C, B)     //A 将下遊對象C 更換為B，  B被标記為灰色

           

避免條件1（ 指派器修改對象圖，導緻某一黑色對象引用白色對象；）因為在對象A 引用對象B 的時候，B 對象被标記為灰色

Dijkstra 插入屏障的好處在于可以立刻開始并發标記。但存在兩個缺點：

• 由于 Dijkstra 插入屏障的“保守”，在一次回收過程中可能會殘留一部分對象沒有回收成功，隻有在下一個回收過程中才會被回收；
• 在标記階段中，每次進行指針指派操作時，都需要引入寫屏障，這無疑會增加大量性能開銷；為了避免造成性能問題，Go 團隊在最終實作時，沒有為所有棧上的指針寫操作，啟用寫屏障，而是當發生棧上的寫操作時，将棧标記為灰色，但此舉産生了灰色指派器，将會需要标記終止階段 STW 時對這些棧進行重新掃描。

3.4、删除屏障 （Yuasa）- 黑色指派器 

寫入前，對指針所在對象進行着色

// 黑色指派器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot) 先将*slot标記為灰色
    *slot = ptr
}

//說明：
添加下遊對象(目前下遊對象slot， 新下遊對象ptr) {
  //step 1
  if (目前下遊對象slot是灰色 || 目前下遊對象slot是白色) {
          标記灰色(目前下遊對象slot)     //slot為被删除對象， 标記為灰色
  }  
  //step 2
  目前下遊對象slot = 新下遊對象ptr
}

//場景
A.添加下遊對象(B, nil)   //A對象，删除B對象的引用。B被A删除，被标記為灰(如果B之前為白)
A.添加下遊對象(B, C)     //A對象，更換下遊B變成C。B被A删除，被标記為灰(如果B之前為白)
           

特點：标記結束不需要STW，但是回收精度低，GC 開始時STW 掃描堆棧記錄初始快照，保護開始時刻的所有存活對象；且容易産生“備援”掃描；

 3.5、混合屏障

大大縮短了 STW 時間

• GC 開始将棧上的對象全部掃描并标記為黑色；
• GC 期間，任何在棧上建立的新對象，均為黑色；
• 被删除的堆對象标記為灰色；
• 被添加的堆對象标記為灰色；

// 混合寫屏障
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot)
    shade(ptr)
    *slot = ptr
}
           

4、Golang GC過程 

4.1、Marking setup（STW）

        為了打開寫屏障，必須停止每個goroutine，讓垃圾收集器觀察并等待每個goroutine進行函數調用， 等待函數調用是為了保證goroutine停止時處于安全點。

        下面的代碼中，由于

for{}

 循環所在的goroutine 永遠不會中斷，導緻始終無法進入STW階段，資源浪費；Go 1.14 之後，此類goroutine 能被異步搶占，使得進入STW的時間不會超過搶占信号觸發的周期，程式也不會因為僅僅等待一個goroutine的停止而停頓在進入STW之前的操作上。

func main() {
    go func() {
        for {
        }
    }()
    time.Sleep(time.Milliecond)
    runtime.GC()
    println("done")
}
           

 4.2、Marking（startTW）

一旦寫屏障打開，垃圾收集器就開始标記階段，垃圾收集器所做的第一件事是占用25%CPU。

标記階段需要标記在堆記憶體中仍然在使用中的值。首先檢查所有現goroutine的堆棧，以找到堆記憶體的根指針。然後收集器必須從那些根指針周遊堆記憶體圖，标記可以回收的記憶體。

當存在新的記憶體配置設定時，會暫停配置設定記憶體過快的那些 goroutine，并将其轉去執行一些輔助标記（Mark Assist）的工作，進而達到放緩繼續配置設定、輔助 GC 的标記工作的目的。

4.3、Marking終止（STW）

關閉寫屏障，執行各種清理任務（STW - optional ）

4.4、Sweep

        到這一階段，所有記憶體要麼是黑色的要麼是白色的，清除所有白色的即可。清理階段用于回收标記階段中标記出來的可回收記憶體。當應用程式goroutine嘗試在堆記憶體中配置設定新記憶體時，會觸發該操作，清理導緻的延遲和吞吐量降低被分散到每次記憶體配置設定時。

清除階段出現新對象：

清除階段是掃描整個堆記憶體，可以知道目前清除到什麼位置，建立的新對象判定下，如果新對象的指針位置已經被掃描過了，那麼就不用作任何操作，不會被誤清除，如果在目前掃描的位置的後面，把該對象的顔色标記為黑色，這樣就不會被誤清除了

什麼時候進行清理？

主動觸發（runtime.GC()） 被動觸發 （GC百分比、定時）

 5、調優