一文掌握垃圾回收：原理、算法與高性能 GC 優化
在面試過程中，垃圾回收算法經常會被問到，本文就來分享下常見的垃圾回收算法及其優缺點，以幫助你在面試過程中更好的應對這些面試問題。
一、GC 入門：GC 基礎概念
垃圾回收（Garbage Collection，GC） 是一種自動內存管理機制。當程序申請的堆內存不再被使用時，GC 會主動將這些內存回收，以供后續分配或返還給操作系統。
1. 內存管理三大參與者
在程序進行 GC 時，有以下 3 個參與者參與到了 GC 的過程中：
- Mutator（用戶程序）
- Allocator（內存分配器）
- Collector（垃圾回收器）
上圖是內存管理的三個參與者，Mutator 用戶程序、Allocator 內存分配器和 Collector 垃圾回收。用戶程序 Mutator 會通過內存分配器 Allocator 去申請內存 Memory，而垃圾回收器 Collector 則會回收無用的堆內存。
2. GC 核心優勢與劣勢
使用 GC 會給開發者帶來很多好處，以下是 GC 的核心優勢：
- 開發者無需手動管理內存，降低心智負擔；
- 自動釋放殘留內存，減少內存泄漏風險；
- 可通過調控 API（如觸發時機、暫停策略）進行優化。
使用 GC 通常也會帶來以下劣勢：
- 暫停（Stop-The-World，STW）可能影響實時性
- 性能開銷與程序吞吐率相關
3. 不同語言內存管理策略對比
不同編程語言采用的內存管理策略是不一樣的，下表是常見內存管理策略比較：
方式 | 代表語言 | 特點 | 缺點 |
手動管理 | C/C++ | 性能高、可控性強 | 易出錯（內存泄漏、懸掛指針） |
自動管理 | Java、Go | 開發者無需釋放，安全性好 | 暫停、性能開銷 |
所有權機制 | Rust | 編譯期安全、無運行時 GC | 學習曲線陡峭 |
二、能否回收：基礎垃圾識別算法
對堆垃圾回收前的第一步就是要判斷哪些對象已經死亡（即不能再被任何途徑使用的對象）。判斷一個對象是否存活有引用計數、可達性分析這兩種算法，兩種算法各有優缺點。、
Java 和 Go 都使用可達性分析算法，一些動態腳本語言（如：ActionScript）一般使用引用計數算法。
1. 引用計數（Reference Counting）
引用計數會為每個對象維護一個計數器，當該對象被其他對象引用時加1，引用失效時減 1，當引用次數為 0 后即可回收對象。
引用計數通過在對象上增加自己被引用的次數，被其他對象引用時加 1，引用自己的對象被回收時減1，引用數為 0 的對象即為可以被回收的對象，這種算法在內存比較緊張和實時性比較高的系統中使用比較廣泛，如 PHP，Python 等。
優點：
- 原理和實現都比較簡單；
- 回收及時性高，引用計數為0則立即回收，不需要想其他GC機制需要等待特定的時間回收；
- 不需要暫停應用即可完成回收。
缺點：
- 無法解決循環引用的問題，例如：a.b=b; b.a=a；
- 時間和空間成本高：每個對象需要額外的空間來存儲引用計數，在棧上修改引用計數的時間成本高（因為需要額外的原子操作來保證線程安全）；
- 無法保證耗時：引用計數是一種攤銷算法，會將內存的回收分攤到整個程序的運行過程，當銷毀一個很大的樹形結構時無法保證響應時間。
2. 可達性分析（Reachability Analysis）
可達性分析的核心思想是判斷一個對象是否可達，如果這個對象一旦不可達就可以立刻被 GC 回收了，那么我們怎么判斷一個對象是否可達呢？第一步，從根節點開始找出所有的全局變量和當前函數棧里的變量，標記為可達。第二步，從已經標記的數據開始，進一步標記它們可訪問的變量，以此類推，專業術語叫傳遞閉包。當追蹤結束時，沒有被打上標記的對象就被判定是不可觸達。
該算法屬于追蹤式算法，目的是回收不可達對象，可達對象主要包括兩類：
- GC Roots 對象： 包括全局對象，棧上對象；
- 與 GC Roots 對象通過引用鏈相連的對象。
對于不可達對象，我們認為該對象為垃圾對象，應該被回收。
同上述的引用計數法相比，追蹤式算法具有如下優點：
- 解決了循環引用的問題；
- 占用的空間少了。
和引用計數法相比，也有以下缺點：
- 無法立刻識別出垃圾對象，需要依賴 GC 線程；
- 算法在標記時必須暫停整個程序，即 STW(stop the world)，否則其他線程有可能會修改對象的狀態從而回收不該被回收的對象。
三、如何回收：基于可達性分析的 GC 算法
現代主流的 GC 算法都基于可達性分析，并在此基礎上實現了不同的回收策略。
1. 標記-復制算法（Copying Collector）
它把內存空間劃分為兩個相等的區域，每次只使用其中一個區域。在垃圾收集時，遍歷當前使用的區域，把存活對象復制到另一個區域中，最后將當前使用的區域的可回收對象進行回收。
實現主要分為標記和復制兩個步驟：
- 標記： 記錄需要回收的垃圾對象；
- 復制： 將內存分為大小相同的兩塊，當某一塊的內存使用完了之后就將使用中的對象挨個復制到另一塊內存中，最后將當前內存恢復為未使用狀態。
優點：
- 不用進行大量垃圾對象的掃描：標記-復制算法需要從 GC-root 對象出發，將可達的對象復制到另外一塊內存后直接清理當前這塊的內存即可；
- 解決了內存碎片問題，防止分配大空間對象時提前 GC 的問題。
缺點：
- 復制成本問題：在可達對象占用內存高的時候，復制成本會很高；
- 內存利用率低：相當于可利用的內存僅有一半。
2. 標記-清除算法（Mark-and-Sweep）
標記-清除算法是最常見的垃圾收集算法，標記清除收集器是跟蹤式垃圾收集器，其執行過程可以分成標記（Mark）和清除（Sweep）兩個階段：
- 標記階段：暫停應用程序的執行，從根對象觸發查找并標記堆中所有存活的對象；
- 清除階段：遍歷堆中的全部對象，回收未被標記的垃圾對象并將回收的內存加入空閑鏈表，恢復應用程序的執行。
優點：
- 實現簡單；
- 算法吞吐量高，即運行用戶代碼時間 /（運行用戶代碼時間+運行垃圾收集時間）；
- 空間利用率高，和標記-復制相比，不需要額外的空間復制對象，和引用計數法相比，也不需要額外的空間設置計數器
缺點：
- 執行期間需要把整個程序完全暫停，不能異步的進行垃圾回收；
- 容易產生大量不連續的內存隨便，碎片太多可能會導致后續沒有足夠的連續內存分配給較大的對象，從而提前觸發新的一次垃圾收集動作。
3. 標記-整理算法（Mark-and-Compact）
標記-整理算法（也叫標記-壓縮算法）標記出所有可達對象，然后將可達對象移動到空間的另外一段，最后清理掉邊界以外的內存。
優點：
- 避免了內存碎片化的問題；
- 適合老年代算法，老年代對象存活率高的情況下，標記整理算法由于不需要復制對象，效率更高。
缺點：整理的過程復雜，需要多長遍歷內存，導致 STW 時間比標記清除算法高。
四、性能優化：GC 優化策略
在解決了“能否回收”和“如何回收”的基礎問題后，垃圾回收技術演進的下一個核心目標便是“如何更高效、更低延遲地回收”。
為了應對“Stop-The-World”暫停過長這一核心痛點，現代垃圾回收器主要從兩個維度進行優化：一是通過分代收集（Generational GC），根據對象的生命周期特點“區別對待”，從而減少單次回收的工作量。二是通過增量與并發 GC（Incremental & Concurrent GC），改變回收的執行方式，將巨大的暫停拆解或與用戶程序并行，從而最大化地降低對程序的影響。
1. 分代收集算法（Generational GC）
分代收集算法按照對象生命周期的長短劃分到不同分區：
- 對于生命周期短的新生代區域（Young），每次回收僅需要考慮如何保留少量存活對象，因此可以采用標記-復制法完成 GC；
- 對于生命周期長的老年代區域（Old），可以通過減少 GC 的頻率來提供效率，同時由于對象存活率高沒有額外的空間用于復制，因此一般可以使用標記清除法或標記整理法。
這樣劃分，堆就分成了 Young 和 Old 兩個分區，因此 GC 也分為新生代 GC 和老年代 GC。
對象的分配策略：
- 對象優先在新生代上 Eden 區域分配；
- 大對象直接進入老年代；
- 新生代中周期較長的對象在 s0 或 s1 區每經過一次新生代 GC，就增加一歲，增加到一定閾值的時候，就進入老年代區域。
2. 增量與并發 GC
前面提到的傳統 GC 算法都會 STW，這存在兩個嚴重的弊端：
- 對實時性程序來說，很致命；
- 對多核計算機來說，會造成計算資源的浪費。
為了避免一次性完成所有 GC 工作導致的長時間 STW，可以將 GC 過程拆分為多個小步驟，與用戶程序交替執行。
- 增量 GC（Incremental GC）：將 GC 工作分成多個階段，穿插在用戶程序中執行，分攤了暫停時間；
- 并發 GC（Concurrent GC）：讓 GC 線程與用戶程序線程在一段時間內同時運行，極大地減少了 STW。
這兩種策略都依賴于三色標記法和屏障技術來保證在并發環境下的正確性。
3. 增量 GC（Incremental GC）
分攤 GC 時間，避免程序長時間暫停；
內存屏障技術，需要額外時間開銷，并且由于內存屏障技術的保守性，一些垃圾對象不會被回收，會增加一輪 GC 的總時長。
4. 并發 GC（Concurrent GC）
- 運行 GC 和用戶程序并行；
- 一定程度上利用多核計算機的優勢減少了對用戶程序的干擾，不該寫屏障的額外開銷和保守性問題仍然存在，這是不可避免的。
五、并發保證：三色標記與屏障技術
引入并發 GC 的目的是為了消除或顯著縮短“Stop-The-World”的暫停時間，但這帶來了一個棘手的挑戰：當 GC 線程正在遍歷對象圖時，用戶線程可能同時在修改對象間的引用關系。這種并發修改可能導致 GC“看錯”對象的可達性，從而錯誤地回收仍在使用的對象。
為了保證在并發環境下數據的一致性和 GC 的正確性，現代垃圾回收器引入了 三色標記法（Tri-color Marking）作為核心算法框架，并配合屏障技術（Barrier）來追蹤并發間的引用變化，確保萬無一失。
1. 三色標記（Tri-color Marking）
前面的標記-X 類算法都有一個問題，那就是 STW（即 GC 時暫停整個應用程序），三色標記法是對標記階段進行改進的算法。目的是在不暫停程序的情況下即可完成對象的可達性分析，GC 線程將所有對象分為三類：
- 白色對象：未搜索的對象（潛在的垃圾），在回收周期開始時所有對象都是白色，在回收周期結束時，所有對象都是垃圾回收對象；
- 灰色對象：正在搜索的對象（活躍的對象），但是對象身上還有一個或多個引用沒有掃描；
- 黑色對象：已搜索完成的對象（活躍的對象），所有的引用已被掃描完
三色標記算法屬于增量式 GC 算法，回收器首先將所有對象著色成白色，然后從 GC Roots 出發，逐步把所有可達的對象變成灰色再到黑色，最終所有的白色對象都是不可達對象。
GC Roots 區域主要是程序運行到當前時刻的棧和全局數據區域。
具體實現：
- 初始時所有對象都是白色的；
- 從 GC Roots 對象出發，掃描所有可達對象并標記為灰色，放入待處理隊列；
- 從隊列取出一個灰色對象并標記為黑色，將其引用對象標記為灰色，放入隊列；
- 重復上一步驟，直到灰色對象隊列為空；
- 此時剩下的所有白色對象都是垃圾對象。
結合如下動圖理解：
可以看出：A、F 為 GC Roots 根直接引用的對象，E、G、H 對象為垃圾，需要回收。
優點：不需要 STW。
缺點：
- 如果產生垃圾速度大于回收速度時，可能會導致程序中垃圾對象越來越多而無法及時收集；
- 線程切換和上下文轉換的消耗會使得垃圾回收的總體成本上升，從而降低系統吞吐量。
三色標記法存在并發性問題：
- 可能會出現野指針（指向沒有合法地址的指針），從而造成嚴重的程序錯誤；
- 漏標，錯誤的回收非垃圾對象。
2. 屏障技術
屏障技術是在用戶程序讀取、創建以及更新對象指針時執行的一段代碼，簡單來說，內存屏障是一種能夠保證內存操作順序的技術。根據操作類型的不同，屏障技術分為讀屏障和寫屏障兩種。
由于讀屏障需要在讀操作時加入代碼片段，對用戶程序的影響較大。因此，Go 語言采用寫屏障來保證三色不變式，寫屏障技術包括 Dijkstra 在 1978 年提出插入寫屏障和 Yuasa 在 1990 年提出刪除寫屏障兩種。
Go 語言中使用到的屏障技術包含以下 3 種：
類型 | 工作原理 | 解決的問題 | 缺點 |
插入寫屏障 | 黑色→白色引用時標記白色為灰 | 強三色不變性 | 棧需 STW 掃描 |
刪除寫屏障 | 刪除引用時標記白色為灰 | 弱三色不變性 | 回收精度低 |
混合寫屏障(Go 1.8+) | 棧對象全黑+堆寫屏障 | 免S TW 重掃描 | 最佳實踐方案 |
3. 插入寫屏障
插入寫屏障的原理是：當有黑色對象 A 指向新對象 D 時，如果被指向對象 D 為白色，則將 D 對象設置為灰色，它實現了強三色不變式。
如上圖的標記過程：
- 垃圾收集器將根集合上的 A 對象標記為黑色，并將 A 對象指向的 B 對象標記成灰色；
- 用戶程序修改 A 對象的指針，將原本指向 B 對象的指針指向 C 對象，這時，觸發插入寫屏障將 C 對象標記為灰色；
- 垃圾收集器依次遍歷其它灰色對象，標記為黑色。
插入寫屏障將被添加引用的白色對象都標記為了灰色，這種方法實現簡單，但也有明顯的缺點：
- 缺點一：未存活的對象可能需要兩次回收，假設上述第 2 步到第 3 步之間，A 對象的指針又從指向 C 改為指向 B，那 C 對象就是垃圾，應該回收。但是此時灰色的對象 C 會被垃圾收集器認為是存活的，這些被錯誤標記的對象只有在下一個循環才會被回收；
- 缺點二：寫屏障只會對堆上的內存對象啟動寫屏障（插入和刪除寫屏障共有的）。而棧上的對象需要保證內存安全時，必須在標記階段重新對棧上的對象進行 STW 掃描。重新掃描時需要暫停程序，影響整體性能。
4. 刪除寫屏障
刪除寫屏障的原理是：對象 A 被引用時，如果引用它的對象被刪除了，那么白色的 A 對象將被標記為灰色，它實現了弱三色不變式。
如上圖的標記過程：
- 垃圾收集器將根集合上的 A 對象標記為黑色，并將 A 對象指向的 B 對象標記成灰色；
- 用戶程序將 A 指向 B 對象的指針，修改為指向 C 對象。這時，觸發刪除寫屏障，但因為 B 對象不為白色，所以不做改變；
- 用戶程序將 B 指向 C 對象的指針刪除，觸發刪除寫屏障，此時，白色的 C 對象被標記為灰色；
- 垃圾收集器依次遍歷程序中的灰色對象，將它們標記為黑色。
刪除寫屏障將被刪除引用的白色對象都標記為了灰色，但是它也有缺點和局限性：
- 缺點一：回收精度低，當對象 B 已經被刪除時，它仍然可以活過這一輪在下一個循環才被回收；
- 缺點二：同插入寫屏障，重新 STW 掃描棧對象。
5. 混合寫屏障（Go 1.8+）
傳統的寫屏障在處理棧內存時仍需短暫的 STW 進行重新掃描。Go 語言的混合寫屏障結合了插入和刪除寫屏障的優點，并進行了優化：
(1) GC 開始時，將棧上所有可達對象標記為黑色，無需 STW 重掃描。
(2) GC 期間，棧上創建的新對象均為黑色。
(3) 對堆上的指針操作，同時啟用插入和刪除寫屏障的邏輯：
- 將被刪除引用的對象標記為灰色；
- 將被添加引用的對象標記為灰色。
這種方式幾乎消除了 STW 的重掃描階段，使得 Go 的 GC 暫停時間達到亞毫秒級別。
六、總結
本文回顧了各類垃圾回收算法的原理與演進后，GC 技術可以分為兩大模塊：
- 判定可回收對象：引用計數 vs. 可達性分析
- 執行回收策略：標記-復制、標記-清除、標記-整理 + 并發／增量調度
分代收集、三色標記與屏障技術是現代高性能 GC 的核心。面試中應熟練掌握各方案的原理、優缺點與適用場景，并能結合具體語言（如 Java、Go）的實現細節進行答題。
