GO GC 垃圾回收機制
垃圾回收(Garbage Collection,簡稱GC)是程式語言中提供的記憶體管理功能。
在傳統的系統級程式語言(主要指C/C++)中,程式設計師定義了一個變數,就是在記憶體中開闢了一段相應的空間來存值。由於記憶體是有限的,所以當程式不再需要使用某個變數的時候,就需要銷燬該物件並釋放其所佔用的記憶體資源,好重新利用這段空間。在C/C++中,釋放無用變數記憶體空間的事情需要由程式設計師自己來處理。就是說當程式設計師認為變數沒用了,就手動地釋放其佔用的記憶體。但是這樣顯然非常繁瑣,如果有所遺漏,就可能造成資源浪費甚至記憶體洩露 。當軟體系統比較複雜,變數多的時候程式設計師往往就忘記釋放記憶體 或者在不該釋放的時候釋放記憶體了。這對於程式開發人員是一個比較頭痛的問題。
為了解決這個問題,後來開發出來的幾乎所有新語言(java,python,php等等)都引入了語言層面的自動記憶體管理 – 也就是語言的使用者只用關注記憶體的申請而不必關心記憶體的釋放,記憶體釋放由虛擬機器(virtual machine)或執行時(runtime)來自動進行管理。而這種對不再使用的記憶體資源進行自動回收的功能就被稱為垃圾回收。
垃圾回收常見的方法
引用計數(reference counting)
引用計數通過在物件上增加自己被引用的次數,被其他物件引用時加1,引用自己的物件被回收時減1,引用數為0的物件即為可以被回收的物件。這種演算法在記憶體比較緊張和實時性比較高的系統中使用的比較廣泛,如ios cocoa框架,php,python等。
優點:
1、方式簡單,回收速度快。
缺點:
1、需要額外的空間存放計數。
2、無法處理迴圈引用(如a.b=b;b.a=a這種情況)。
3、頻繁更新引用計數降低了效能。
標記-清除(mark and sweep)
該方法分為兩步,標記從根變數開始迭代得遍歷所有被引用的物件,對能夠通過應用遍歷訪問到的物件都進行標記為“被引用”;標記完成後進行清除操作,對沒有標記過的記憶體進行回收(回收同時可能伴有碎片整理操作)。這種方法解決了引用計數的不足,但是也有比較明顯的問題:每次啟動垃圾回收都會暫停當前所有的正常程式碼執行,回收是系統響應能力大大降低!當然後續也出現了很多mark&sweep演算法的變種(如三色標記法)優化了這個問題。
複製收集
複製收集的方式只需要對物件進行一次掃描。準備一個「新的空間」,從根開始,對物件進行掃,如果存在對這個物件的引用,就把它複製到「新空間中」。一次掃描結束之後,所有存在於「新空間」的物件就是所有的非垃圾物件。
這兩種方式各有千秋,標記清除的方式節省記憶體但是兩次掃描需要更多的時間,對於垃圾比例較小的情況佔優勢。複製收集更快速但是需要額外開闢一塊用來複制的記憶體,對垃圾比例較大的情況佔優勢。特別的,複製收集有「區域性性」的優點。
在複製收集的過程中,會按照物件被引用的順序將物件複製到新空間中。於是,關係較近的物件被放在距離較近的記憶體空間的可能性會提高,這叫做區域性性。區域性性高的情況下,記憶體快取會更有效地運作,程式的效能會提高。
對於標記清除,有一種標記-壓縮演算法的衍生演算法:
對於壓縮階段,它的工作就是移動所有的可達物件到堆記憶體的同一個區域中,使他們緊湊的排列在一起,從而將所有非可達物件釋放出來的空閒記憶體都集中在一起,通過這樣的方式來達到減少記憶體碎片的目的。
分代收集(generation)
這種收集方式用了程式的一種特性:大部分物件會從產生開始在很短的時間內變成垃圾,而存在的很長時間的物件往往都有較長的生命週期。
根據物件的存活週期不同將記憶體劃分為新生代和老年代,存活週期短的為新生代,存活週期長的為老年代。這樣就可以根據每塊記憶體的特點採用最適當的收集演算法。
新建立的物件存放在稱為 新生代(young generation)中(一般來說,新生代的大小會比 老年代小很多)。高頻對新生成的物件進行回收,稱為「小回收」,低頻對所有物件回收,稱為「大回收」。每一次「小回收」過後,就把存活下來的物件歸為老年代,「小回收」的時候,遇到老年代直接跳過。大多數分代回收演算法都採用的「複製收集」方法,因為小回收中垃圾的比例較大。
這種方式存在一個問題:如果在某個新生代的物件中,存在「老生代」的物件對它的引用,它就不是垃圾了,那麼怎麼制止「小回收」對其回收呢?這裡用到了一中叫做寫屏障的方式。
程式對所有涉及修改物件內容的地方進行保護,被稱為「寫屏障」(Write Barrier)。寫屏障不僅用於分代收集,也用於其他GC演算法中。
在此演算法的表現是,用一個記錄集來記錄從新生代到老生代的引用。如果有兩個物件A和B,當對A的物件內容進行修改並加入B的引用時,如果①A是「老生代」②B是「新生代」。則將這個引用加入到記錄集中。「小回收」的時候,因為記錄集中有對B的引用,所以B不再是垃圾。
三色標記演算法
三色標記演算法是對標記階段的改進,原理如下:
- 起初所有物件都是白色。
- 從根出發掃描所有可達物件,標記為灰色,放入待處理佇列。
- 從佇列取出灰色物件,將其引用物件標記為灰色放入佇列,自身標記為黑色。
- 重複 3,直到灰色物件佇列為空。此時白色物件即為垃圾,進行回收。
視覺化如下。
三色標記的一個明顯好處是能夠讓使用者程式和 mark 併發的進行,具體可以參考論文:《On-the-fly garbage collection: an exercise in cooperation.》。Golang 的 GC 實現也是基於這篇論文,後面再具體說明。
GO的垃圾回收器
go語言垃圾回收總體採用的是經典的mark and sweep演算法。
-
v1.3以前版本 STW(Stop The World)
golang的垃圾回收演算法都非常簡陋,然後其效能也廣被詬病:go runtime在一定條件下(記憶體超過閾值或定期如2min),暫停所有任務的執行,進行mark&sweep操作,操作完成後啟動所有任務的執行。在記憶體使用較多的場景下,go程式在進行垃圾回收時會發生非常明顯的卡頓現象(Stop The World)。在對響應速度要求較高的後臺服務程序中,這種延遲簡直是不能忍受的!這個時期國內外很多在生產環境實踐go語言的團隊都或多或少踩過gc的坑。當時解決這個問題比較常用的方法是儘快控制自動分配記憶體的記憶體數量以減少gc負荷,同時採用手動管理記憶體的方法處理需要大量及高頻分配記憶體的場景。
-
v1.3 Mark STW, Sweep 並行
1.3版本中,go runtime分離了mark和sweep操作,和以前一樣,也是先暫停所有任務執行並啟動mark,mark完成後馬上就重新啟動被暫停的任務了,而是讓sweep任務和普通協程任務一樣並行的和其他任務一起執行。如果執行在多核處理器上,go會試圖將gc任務放到單獨的核心上執行而儘量不影響業務程式碼的執行。go team自己的說法是減少了50%-70%的暫停時間。
-
v1.5 三色標記法
go 1.5正在實現的垃圾回收器是“非分代的、非移動的、併發的、三色的標記清除垃圾收集器”。引入了上文介紹的三色標記法,這種方法的mark操作是可以漸進執行的而不需每次都掃描整個記憶體空間,可以減少stop the world的時間。 由此可以看到,一路走來直到1.5版本,go的垃圾回收效能也是一直在提升,但是相對成熟的垃圾回收系統(如java jvm和javascript v8),go需要優化的路徑還很長(但是相信未來一定是美好的~)。
-
v1.8 混合寫屏障(hybrid write barrier)
這個版本的 GC 程式碼相比之前改動還是挺大的,採用一種混合的 write barrier 方式 (Yuasa-style deletion write barrier [Yuasa ‘90] 和 Dijkstra-style insertion write barrier [Dijkstra ‘78])來避免 堆疊重新掃描。
混合屏障的優勢在於它允許堆疊掃描永久地使堆疊變黑(沒有STW並且沒有寫入堆疊的障礙),這完全消除了堆疊重新掃描的需要,從而消除了對堆疊屏障的需求。重新掃描列表。特別是堆疊障礙在整個執行時引入了顯著的複雜性,並且干擾了來自外部工具(如GDB和基於核心的分析器)的堆疊遍歷。
此外,與Dijkstra風格的寫屏障一樣,混合屏障不需要讀屏障,因此指標讀取是常規的記憶體讀取; 它確保了進步,因為物體單調地從白色到灰色再到黑色。
混合屏障的缺點很小。它可能會導致更多的浮動垃圾,因為它會在標記階段的任何時刻保留從根(堆疊除外)可到達的所有內容。然而,在實踐中,當前的Dijkstra障礙可能幾乎保留不變。混合屏障還禁止某些優化:特別是,如果Go編譯器可以靜態地顯示指標是nil,則Go編譯器當前省略寫屏障,但是在這種情況下混合屏障需要寫屏障。這可能會略微增加二進位制大小。
小結:
通過go team多年對gc的不斷改進和憂化,GC的卡頓問題在1.8 版本基本上可以做到 1 毫秒以下的 GC 級別。 實際上,gc低延遲是有代價的,其中最大的是吞吐量的下降。由於需要實現並行處理,執行緒間同步和多餘的資料生成複製都會佔用實際邏輯業務程式碼執行的時間。GHC的全域性停止GC對於實現高吞吐量來說是十分合適的,而Go則更擅長與低延遲。
並行GC的第二個代價是不可預測的堆空間擴大。程式在GC的執行期間仍能不斷分配任意大小的堆空間,因此我們需要在到達最大的堆空間之前實行一次GC,但是過早實行GC會造成不必要的GC掃描,這也是需要衡量利弊的。因此在使用Go時,需要自行保證程式有足夠的記憶體空間。
垃圾收集是一個難題,沒有所謂十全十美的方案,通常是為了適應應用場景做出的一種取捨。
相信GO未來會更好。
參考:
https://github.com/golang/pro...
http://legendtkl.com/2017/04/...
https://blog.twitch.tv/gos-ma...
https://blog.plan99.net/moder...