Ruby2.2 中的增量式垃圾回收

Ruby2.2 中的增量式垃圾回收

本文是http://engineering.heroku.com/blogs/2015-02-04-incremental-gc?utm_source=rubyweekly&utm_medium=email 的翻譯。鄙人是Ruby新手，英語渣，如果翻譯不妥之處還請輕噴。。。。

本文介紹了 被引入Ruby2.2中的增量式GC。我們將這個算法稱為 RincGC。 與Ruby2.1 相比RincGC縮短了GC的停頓時間。
關(guān)于作者：Koichi Sasada 和 Nobu，Matz 一起為Heroku工作 同時也是 C Ruby 核心成員。先前，他編寫了Ruby的虛擬機(jī) （YARV）。
他為Ruby2.1引入了 分代垃圾回收。 Koichi Sasada為Ruby2.2 實現(xiàn)了增量式GC并撰寫了此文。

背景
  Ruby使用GC來自動回收未被使用的對象。歸功于GC，Ruby程序員不需要手動釋放對象，也無需擔(dān)憂對象釋放的bug。
  初版的RubyGC使用了標(biāo)記-清除算法。標(biāo)記-清除算法是最簡單的垃圾回收算法之一，它包含了兩部分：
 
 1）標(biāo)記：遍歷所有的活動的對象并標(biāo)記為“活動對象”。
 2）清除：未被標(biāo)記的作為未使用的對象被回收。

標(biāo)記-清除算法是基于被遍歷的對象都是活動的對象的前提。標(biāo)記-清除算法簡單有效。


這個簡單有效保守的垃圾回收技術(shù)使C擴(kuò)展的編寫變得容易。Ruby因此獲得了很多有用的擴(kuò)展類庫。然而，也由于標(biāo)記-清除算法，使Ruby采用其他GC算法如復(fù)制收集變得困難。
現(xiàn)在由于采用了FFI技術(shù)(foreign function interface)，編寫C擴(kuò)展類庫已經(jīng)變得不那么重要了。當(dāng)初Ruby由于享有擁有許多擴(kuò)展類庫并提供了許多基于C擴(kuò)展的特性而獲得了巨大的優(yōu)勢。并使Ruby解釋器變得更為的流行。
雖然標(biāo)記-清除算法能很好地工作，但同時它也有幾個問題。最重要的兩個問題是“吞吐量”（throughput） 和 “停頓時間”(pause time)。過高的GC開銷會減慢你的程序運(yùn)行速度。換言之，較低的吞吐量增加了你的應(yīng)用運(yùn)行時間。
每次GC執(zhí)行時，會暫停你的Ruby應(yīng)用。長時間的停頓會影響用戶體驗。（UI/UX ？）

Ruby2.1引入了分代垃圾回收來解決“吞吐量”問題。分代GC將堆分成了多個空間對應(yīng)于不同的世代（就Ruby而言，我們將堆分成了“新生代” 和 “老年代”兩代。）新生成的對象會被標(biāo)記為“新生代對象”并放入“新生代空間”。

在存活過幾次GC之后（Ruby2.2 中 3次），“新生代對象”會變成“老年代對象”并被移入“老年代空間”。在OOP中，我們知道大部分對象英年早逝（哈哈，惡搞一下）。有鑒于此，我們只需要對“新生代空間”進(jìn)行GC操作。
如果“新生代空間”沒有沒空間生成新對象了，我們就會對“老年代空間”做GC操作。針對“新生代代”的GC操作，稱之為“小GC”（minor GC）。同時對“新生代”和“老年代”做GC操作的稱之為“主GC”（major GC）。
我們實現(xiàn)了做個定制的分代GC算法，稱之為"RGenGC"。更多關(guān)于"RGenGC"的信息，參見 RGenGC at my talk at EuRuKo and slides。

因為小GC非?？焖伲訰GenGC 改進(jìn)了 GC的動態(tài)吞吐量。然而主GC會長時間的停頓，其停頓長度與Ruby2.0及其更早的版本的GC停頓時間相當(dāng)。大部分的GC都是小GC，
少數(shù)幾個Major GC可能造成你的應(yīng)用長時間停頓。

為了解決長時間的停頓，增量式GC算法是個知名的解決方案。

增量式GC的基本概念

增量式GC算法將GC處理過程分解成細(xì)顆粒度的處理過程并插入到Ruby的進(jìn)程處理過程中。增量式GC會在一個周期內(nèi)用多個短時間停頓以代替一個長時間的停頓。總的停頓時間相同
（或略長 因使用增量式GC引起的較高的GC開銷。），但是每個GC造成的停頓都很短。這使得總體的性能更穩(wěn)定。

Ruby1.9.3中引入的一個“惰性清除”GC，它降低了清除階段的停頓時間。惰性清除的要點(diǎn)在于不是一次而是多次執(zhí)行清除。惰性清除降低了單個清除過程造成的停頓時間。算是半個增量式GC算法。
現(xiàn)在，我們要使主GC的標(biāo)記階段增量化。

讓我們介紹三個術(shù)語以解釋增量標(biāo)記：“白對象”即沒有被標(biāo)記的對象。“灰對象”被標(biāo)記了但可能有指向“白對象”，“黑對象”被標(biāo)記且沒有指向任何“白對象”。
通過這三種顏色，我們可以像這樣解釋標(biāo)記與清除算法：
   1）所有存在的對象會被標(biāo)記為白色
   2）諸如堆棧上的有著明確引用對象會被標(biāo)記為灰色
   3）選取一個灰色對象，遍歷每一個它指向的對象并標(biāo)記為灰色，最后將源頭的對象標(biāo)記為黑色。重復(fù)上述步驟，直至只剩下黑色與白色對象。
   4）回收白色對象,因為被使用的對象都是黑色的。
為了使上述過程 增量化，我們必須將第三步增量化。我們需要做到，選取一些灰色對象遍歷標(biāo)記然后返回執(zhí)行Ruby代碼，然后再繼續(xù)增量標(biāo)記階段，如此往復(fù)。


要做到增量標(biāo)記就有一個問題：黑色對象可能在Ruby執(zhí)行的過程中指向了白色對象。這個問題是由于黑色對象是定義表明它不會指向白色對象。為了防止此類問題，我們需要使用“內(nèi)存屏障”（write-barrier）

來偵測“黑對象”向“白對象”創(chuàng)建了引用。
例如 一個數(shù)組對象 ary 已經(jīng)被標(biāo)記為黑色

ary = []
# GC runs, it is marked black

如果我們運(yùn)行了代碼，會有一個對象 obj = Object.new 標(biāo)記為白色

ary << obj
# GC has not run since obj got created

現(xiàn)在一個黑色對象 有了一個指向白色對象的引用。如果沒有灰色對象指向obj，那在標(biāo)記階段結(jié)束的時候 ，obj會被標(biāo)記為白色并被錯誤的回收了?；厥照谑褂玫膶ο笫且粋€致命的bug，我們需要避免的大錯。
內(nèi)存屏障在每一次一個對象獲取另一個新對象的引用時會被調(diào)用。當(dāng)一個引用從黑色對象指向白色對象時，內(nèi)存屏障會探測到。內(nèi)存屏障會將黑色對象標(biāo)記為灰色對象（灰變白）。內(nèi)存屏障完整的解決了這類災(zāi)難性的GC BUG。
以上是關(guān)于增量式GC算法的基本概念。如你所見，不是太難。也許你會想問“為什么Ruby還不使用呢？”

Ruby2.2 的增量式GC

要在Ruby解釋器(CRuby)中實現(xiàn)增量式標(biāo)記有一個大問題：缺少內(nèi)存屏障。CRuby沒有足夠的內(nèi)存屏障。

在Ruby2.1中實現(xiàn)的分代垃圾回收同樣也需要內(nèi)存屏障。為了引入分代垃圾回收，我們發(fā)明了一種叫做“write barrier unprotected objects“的新技術(shù)。這意味著我們將所有的對象分為
"write barrier protected objects" (protected objects) and "write barrier unprotected objects" (unprotected objects)。我們保證所有來自被保護(hù)對象的引用是可控的。我們無法保證
來自未受保護(hù)的對象的引用也可控。通過引入”未保護(hù)對象“，使我們能夠?qū)崿F(xiàn)Ruby2.1的分代垃圾回收。
通過使用未受保護(hù)對象，我們也能夠使用增量式GC。

1) 將所有存在的對象標(biāo)記為白色。
2）將所有有著明確引用的活動對象標(biāo)記為灰色（包括堆棧上的對象）。
3）選取一個灰色對象，遍歷每個它所引用的對象并標(biāo)記為灰色，將源頭的對象標(biāo)記為黑色。重復(fù)上述步驟，直至只剩下黑色與白色對象。這步驟是增量式完成的。
4）黑色未受保護(hù)對象可以指向白色對象，并立即掃描所有來自未被保護(hù)的黑色對象。
5）回收白色對象 因為正在被使用的對象都被標(biāo)記為黑色。
通過引入第四步驟，我們能夠保證沒有正在使用的白色對象。


不幸的是，第四步可能會引入我們希望避免的長時間停頓。然而，這個停頓時間與正在使用的內(nèi)存屏障的未受保護(hù)對象的數(shù)量有關(guān)。在Ruby語言中，大部分的對象都是String
，Array，Hash或是 由用戶定義的純Ruby對象。他們都是使用的內(nèi)存屏障的受保護(hù)對象。所以使用的內(nèi)存屏障的未受保護(hù)對象所引起的長時間停頓，并不會在實際使用中引起問題。

  因為沒人抱怨minor GC的暫停時間，所以我們只為 Major GC 引入增量式標(biāo)記。增量式GC上的最長的停頓時間也比minor GC的停頓時間短。如果你對minor GC的停頓時間沒意見，那你更不需要擔(dān)心major GC的停頓時間了

我在實現(xiàn)增量式GC的過程中也耍了一個小花招。我們獲取了一系列“黑色且未受保護(hù)的”對象。為了實現(xiàn)快速的GC，我們預(yù)備了一個“未受保護(hù)”的位圖用來表示哪些是未受保護(hù)的對象，一個“標(biāo)記“位圖用來表示哪些對象是被標(biāo)記了的。
我們通過使用兩張位圖的邏輯乘積來獲取 “黑色且未受保護(hù)的”對象。

增量式GC的暫停時間評估

為了能測量由GC造成的停頓時間，讓我們使用 gc_tracer gem。gc_tracer gem 引入了 GC::Tracer 模塊來捕獲 每次GC事件時GC相關(guān)的參數(shù)。gc_tracer會將每個參數(shù)輸入到文件中。

GC事件如下所示：
 start
  end_mark
 end_sweep
 newobj
freeobj
enter
exit

如我之前所描述的，Ruby的GC分為兩部分“標(biāo)記階段”和“清除階段”。“start”事件表示“開始標(biāo)記階段”而 “end_mark”表示“標(biāo)記階段結(jié)束”。“end_mark”同時也表示“開始清除階段”。當(dāng)然，“end_sweep”在表示結(jié)束“清除階段的同時也表示一個GC處理過程的結(jié)束。
“newobj” 和 “freeobj”很容易理解：關(guān)于對象的分配和釋放的事件。
我們使用“enter”和“exit”事件來測量停頓時間。增量式GC（增量式的標(biāo)記 和 惰性清除）引入了標(biāo)記和清除兩個階段。“enter”事件表示
“進(jìn)入GC相關(guān)事件” 而 “exit”事件表示“退出GC的相關(guān)事件”。
下圖展示了當(dāng)前增量式GC的事件持續(xù)時間


GC事件
我們能夠測量出每個事件的當(dāng)前時間（在Linux機(jī)器上，當(dāng)前時間是gettimeofday()的結(jié)果）。所以我們能夠通過“enter”和“exit”時間
來測量GC停頓時間。
我以 ko1-test-app 為基準(zhǔn)來做測試。 ko1-test-app是一個由我們的英雄 "Aaron Patterson" 為我編寫的簡單Rails應(yīng)用。為了使用
gc_tracer ，我添加了一個像這樣的rake rule “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

然后執(zhí)行了 bundle exec rake test_gc_tracer KO1TEST_CNT=30000。指定30000，表示我姐們將會模擬30000個請求。我們
會在一個名為“l(fā)og_XXX”的文件中找到結(jié)果。該文件應(yīng)包含如下內(nèi)容

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
...

在我的測試環(huán)境中，共有1142907行。
“type”字段表示 事件類型 而 tick 表示當(dāng)前時間（gettimeofday()的結(jié)果， elapesd time from the epoc in microseconds）
我們能通過此信息獲知GC造成的停頓時間。通過開頭兩行，我們能測量出一個10us的停頓時間。
下面的腳本展示了每個停頓時間

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
  }
}

這里有太多行了，所以該腳本打印出了超過100us的停頓時間。
下面的圖表展示了測試結(jié)果。
我們在分代垃圾回收中可能有7個長時間的停頓。它們應(yīng)該是由MajorGC造成的。最長的停頓時間大約15ms。然而，增量式GC降低了最長停頓時間
大約2ms。太棒了。

總結(jié)
Ruby2.2 引入了增量式GC算法以縮短由于GC造成的停頓時間。
需要注意的是增量式GC不是萬能的。如我所描述的，增量式GC不會影響”吞吐量“。這意味著它對由于一個過長的請求的響應(yīng)所造成的長時間響應(yīng)
并由此引起的多個majorGC無能為力?？傮w上的GC停頓時間并沒有因為增量式GC而縮短。