本文將介紹 Ruby 2.2 引入的增量垃圾收器（GC）。我們稱該算法為 RincGC。與 Ruby 2.1 相比縮短了GC中斷時間。
關於作者： Koichi Sasada ，供職於 Heroku ，還在 Nobu 和 Matz 開發 C Ruby 內核。此前他寫了YARV Ruby 的虛擬機，並且將分代垃圾收集 (RgenGC) 引入到 Ruby 2.1。Koichi 為 Ruby 2.2 寫了增量垃圾收集器和本文。
Ruby 使用 GC 自動收集不再使用的對象。感謝 GC，Ruby 程序員不用手動釋放對象，而且不需要關心對象釋放引起的bug。
Ruby 在第一個版本就已經有了 GC，使用的算法是 mark and sweep (M&S)。從兩個層面上講 M&S是最簡單的 GC 之一：
(1) 標記: 遍歷所有活動的類，標記為“活動類”。 (2) 清理: 未標記且不再使用的類將被當作垃圾收集。
M&S 基於一種假定：可被訪問的活動類才是活動類。 M&S 算法簡單且有效。
圖：標記和清除，GC 算法
這種簡單且有效的算法（它是一種保守的垃圾收集算法）因為允許使用 C 擴展，所以算法比較容易擴展。因此 Ruby 獲得許多有用的擴展庫。同時也是因為這種算法，導致遷移到類似 compaction and copying 算法時很困難。
今天，因為我們可以使用 FFI (外部功能接口)，所以 C 擴展已經不那麼重要。然而在起初擁有大量的擴展庫，提供豐富的功能是 Ruby的一大特色，並因此而流行開來。
盡管 M&S 算法簡且好用，但仍然存在一些問題。最重要的問題就是“吞吐量”和“暫停時間”。GC過載時會拖慢你的 Ruby程序。換句話說，低吞量增加你程序的執行時間。每一次垃圾收集都要中斷你的 Ruby 應用程序。長時間的中斷影響 web 應用程序的 UI/UX 效果。
Ruby 2.1 引入分代 GC 克服“吞吐量”問題。分代 GC將堆空間分割為若干個空間，稱為代（Ruby 將堆空間分成兩個空間，一個是“young",一個是“old"）。新創建的對象放在“young”，標記為 "young object"，GC 處理過幾次（Ruby 2.2 是 3 次）之後，"young object" 將標記為“old object"並且放在 "old" 空間。在面向對象編程中，我們知道大部分對象是在“young” 時期生命周期就結束了，基於此我們只需要在“young space”運行 GC，如果在“young”沒有足夠的空間創建新對象，我們才在“old space”運行GC。我們把運行在“young space”的 GC 稱為“Minor GC”，把運行在兩個空間的 GC 稱為“Major GC"，我們定制實現分代GC算法，我們稱之為 "RGenGC"。了解更多請點擊 RGenGC at my talk at EuRuKo 和 slides。
RGenGC戲劇性地提升了 GC 的吞量，因為 minor GC 非常快。但是 major GC 必須中斷較長時間，相當於 Ruby 2.0 及之前版本。大多數 GC 是 minor GC，但是少數 major GC 會中斷你的 Ruby 較長時間。
圖：Major GC 和 minor GC 中斷時間
增量 GC 算法是一個知名算法用來解決長時間中斷問題。
增量垃圾收集器的基本思路
增量 GC 算法將執進程分為幾個細粒度的進程和交錯 GC 進程和 Ruby 進程。在一段時間內，增量垃圾收集器使用多次短的中斷，而不是一次長的中斷。與後者相比，雖然總的中斷時長是一樣的（也可能因為增量 GC 的開銷而更長一些），但每次中斷時間很短暫。這使得性能更穩定。
Ruby 1.9.3 引入了“延遲清理”GC，在清理階段可以減少中斷時間。延遲清理的思路是清理不是一次性的，而是分步的。延遲清理將增量垃圾算法的單次清理次數降低一半。現在我們需要將 major GC 標記為階段增長。
讓我們通過三個術語來解決增量標記：“白對象”是沒有被標記的對象，“灰對象”是已經標記的對象，而且可能引用了一個白對象，“黑對象”是被標記的對象，但它不指向任何白對象。
使用這三種顏色，我們可以解釋標記和清理算法，如下：
(1)所有存在的類標記為白色 (2) 清理棧中標記為灰色的類(3) 選擇一個灰色類，訪問該類引用 的每一個類，並標記為灰色。將先前的類標記為黑色。重復操作直到沒有灰色類，只剩下黑色類和折色類。 (4) 清理白色類，因為所有活動的類已經標記為黑色。
為了使這一過程是增量的，我們必須讓 (3)是增量的。 我們這樣來做，選擇一些灰色類並將他人的引用標記為灰色，然後返回 Ruby 執行過程，再繼續增量標記，不斷重復這一過程。
圖：普通標記 (STW: 停止整個應用) vs. 增量標記
增量標記存在一個問題。在 Ruby 執行過程中黑色類會引用白色類。引起該問題的原因是我們把黑色類定義為沒有引用白色類的類。為了阻止這種情況，我們需要"write-barrier“，在創建過程中發現引用白色類的黑色類。
假如，一個數組對象已經被標記為”黑色“。
ary = []
# GC runs, it is marked black
現在，創建一個新對象 object obj = Object.new 是白色的，如果我們運行以下代碼
現在一個黑色類指向了一個白色類。如果沒有灰色類指向 obj，obj 在標記階段結束時是白色，這將產生一個錯誤。清理時會產生重大 bug，我們要避免這個錯誤。
一個類指向一個新類時，write-barrier 將被調用。write-barrier 會檢測到一個黑色類指向了一個白色類。當該事件發生時，黑色類將被標記為灰色（或者將白色類標記為灰色），write-barrier 徹底解決了GC 的這人災難性 bug。
如你所見，增量 GC 算法的基本思路並不困難，或許你會問：“為什麼 Ruby 還沒有使用這種簡單的 GC 算法”。
Ruby 2.2 的增量 GC
在 Ruby 解釋器裡實現增量標記有一個大問題。 (CRuby)：缺少write-barriers。Ruby 沒有足夠的write-barriers。
在 2.1 上實現的分代 GC 也需要write-barriers。為了引入分代 GC，我們發明了一種新技術叫做”write barrier unprotected objects“。這意味著我們將所有類分成“write barrier protected objects”（保護類）和”write barrier protecte objects“（非保護類）我們可以保障所有保護類的引用都是被管理的。我們不能控制非保護類的引用。引用”非保護類“我們可以為 Ruby2.1 實現分代 GC。
使用非保護類，我們也可以做增量GC：
（1）將所有活動對象置為白色。
（2）將確定活動的類置為灰色，包括棧裡的類。
（3）選擇一個灰色類，訪問類的每一個引用，並置為灰色。將我們最初選擇的類置為黑色。
重復以上過程，直到沒有灰色類，只剩下白色類和黑色類。這一步是增量實現。
（4）將可以指向白色的非保護類置為黑色，這樣所有非保護的黑色類只需一次掃描。
（5）收集所有白色類，因為所有活動類已經被置為黑色。
引入（4）可以保證沒有非活動的白色類。
圖：在標記結束時重新掃描寫屏障的非保護類。
不幸的是引入步驟（4）會引起我們希望避免的長中斷次數。
中斷時間和寫屏障的非保護類的數量有關。在Ruby語言中，大部分對象是String,Array,Hash和用戶定義類，它們都是有寫屏障的保護類。所有寫屏障非保護類引起的長中斷在大多實際運行中並不會產生什麼問題。
我們只在major GC引入了增量標記，因為沒有抱怨minor GC的中斷時間。增量垃圾收集器的最大中斷時間要小於minor GC的中斷時間。如果你在minior GC不存在中斷時間問題，就不用擔心major GC的中斷時間。
我還介紹過為Ruby實現增量垃圾收集器的一人小技巧。我們得到一系列“黑色非保護”類。為了快速執行垃圾清理，我們准備了一個非保護的bitmap代表非保護類，一個獨立的已標記bitmap代表已標記類。使用兩個bitmaps的邏輯可以獲取“黑色非保護”類。
增量垃圾收集器中斷時間評測
為了計量垃圾收集器產生在的中斷時間，讓我們使用 gc_tracergem. gc_tracer gem引用了 GC::Tracer模塊在垃圾收集事件中獲取相關參數。gc_tracergem將每個參數都保存在文件中。
垃圾收集事件包括以下事件：
如我前面所解釋，Ruby的垃圾收集包含兩個階段：“標記附件”和“清理”階段。“開始“是”開始標記附件“事件，”標記結束“是”標記附件結束“事件，”標記結束“也現時意味著”開始清理階段",當然“清理結束”代表”清理階段“結束，也意味著垃圾清理過程的結束。
”創建對象“和”釋放對象”很容易理解：對象分配和對象釋放事件。
我們通過“進入”和“離開”事件計量中斷時間。增量垃圾收集（增量標記和延遲清理）引入中斷標記和清理階段。“進入“是”進入垃圾清理“事件，”離開“是”離開垃圾清理“事件。
下圖顯示了當前增量垃圾收集器的事件時間。
垃圾收集器事件
我們可以計量每一個事件的當前時間（在 Linux 上當前時間是通過 gettimeofday() 獲得）。所以我們可以通過“進入”和“離開”事件計量垃圾收集器的中斷時間。
我使用 ko1-test-app 做為我們中斷時間的基准。ko1-test-app 是我們的一個英雄“Aaron Patterson"為我寫的一個小的 rails app
為了使用 gc_tracer，我添加了一條命名為“test_gc_tracer”的規則，如下：
diff --git a/perf.rake b/perf.rake
index f336e33..7f4f1bd 100644
--- a/perf.rake
+++ b/perf.rake
@@ -54,7 +54,7 @@ def do_test_task app
body.close
end
-task :test do
+def test_run
app = Ko1TestApp::Application.instance
app.app
@@ -67,6 +67,22 @@ task :test do
}
end
+task :test do
+ test_run
+end
+
+task :test_gc_tracer do
+ require 'gc_tracer'
+ require 'pp'
+ pp GC.stat
+ file = "log.#{Process.pid}"
+ GC::Tracer.start_logging(file, events: %i(enter exit), gc_stat: false) do
+ test_run
+ end
+ pp GC.stat
+ puts "GC tracer log: #{file}"
+end
+
task :once do
app = Ko1TestApp::Application.instance
app.app
運行 bundle exec rake test_gc_tracer KO1TEST_CNT=30000。我們通過數值“30000”指定模擬30,000個請求。我們可以在文件“log.xxxx”裡得到結果（xxxx是程序的進程ID）。文件如下
type tick major_by gc_by have_finalizer immediate_sweep state
enter 1419489706840147 0 newobj 0 0 sweeping
exit 1419489706840157 0 newobj 0 0 sweeping
enter 1419489706840184 0 newobj 0 0 sweeping
exit 1419489706840195 0 newobj 0 0 sweeping
enter 1419489706840306 0 newobj 0 0 sweeping
exit 1419489706840313 0 newobj 0 0 sweeping
enter 1419489706840612 0 newobj 0 0 sweeping
...
在我的環境下，這裡有 1,142,907 行。
“type”列是事件類型，tick 是當前時間（gettimeofday（）的輸出結果，epoc總時間，單位是毫秒）。通過這些信息我們可以獲取垃圾收集器的中斷時間。通過前兩行我們可以計算出中斷時間為10 微秒 （1419489706840157 - 1419489706840147）。
以下小腳本顯示每次中斷時間。
enter_tick = 0
open(ARGV.shift){|f|
f.each_line{|line|
e, tick, * = line.split(/\s/)
case e
when 'enter'
enter_tick = tick.to_i
when 'exit'
st = tick.to_i - enter_tick
puts st if st > 100 # over 100 us
else
# puts line
end
}
}
這裡有很多行，這個腳本打印了 100 微秒內的中斷次數。
下圖顯示了統計結果
在分代垃圾收集器中產生了7個較大的中斷時間，他們應該是由“major GC”產生的。最大中斷時間大概15毫秒（15Kus），不管怎樣，增量垃圾收集器減少了最大中斷時間（差不多2ms(2Kus))，太好了。
Ruby 2.2 通過引入增量垃圾收集算法縮短了垃圾收集的中斷時間。
請注意，增量垃圾收集器不是一個銀彈。我曾解釋過增量垃圾收集並不改善“吞吐量”，這意味著如果請求很長並產生多個 major GC，反應時間並不會得到有效改善。使用增量垃圾收集器並不會縮短總的中斷時間。
請在 Heroku 嘗試你的應用，期待你的挑戰！
Ruby中的遍歷指定目錄的文件方法 http://www.linuxidc.com/Linux/2015-01/111525.htm
Ubuntu下搭建Ruby On Rails http://www.linuxidc.com/Linux/2012-06/61981.htm
實測 Ubuntu 13.10 上搭建 Ruby on Rails http://www.linuxidc.com/Linux/2014-02/96399.htm
Ruby on Rails 4 Tutorial 中文版 高清完整PDF http://www.linuxidc.com/Linux/2014-04/100253.htm
Ruby 的詳細介紹：請點這裡
Ruby 的下載地址：請點這裡
英文原文：Incremental Garbage Collection in Ruby 2.2