Ruby 3.0 GC 解說
帶你一次看懂 Ruby 處理 Memory 回收的核心演算法和精神！
本文章會由以下幾個小章節組成，帶著大家從零開始慢慢認識GC，以及Ruby 3.0 如何控制 GC：
- Memory 的機制？
- GC是什麼？為什麼我們需要GC?
- Ruby 3.0 GC 的核心演算法和概念：
- Tri-Color Mark and Sweep Algorithm
- Generational Garbage Collection
- Compaction
廢話不多說，我們直接進入正題！
▍1. Memory 的機制
如果大學是就讀資訊相關科系，可能會修過一門課叫做「作業系統」，英文是 “Operating System”，課程裡面講了很多有關讓作業系統運行必要的知識元素：CPU、處理進程、Thread、Memory 以及 Dead lock 等等。
GC 的機制和 Memory 息息相關，因此先來複習一下課程裡面會提及有關Memory的機制原理吧！
Heap & Stack
在 Memory 的儲存機制裡，共可以簡略拆分兩種方式做儲存，分別為 Heap (堆積) 和 Stack (堆疊)。以下是兩者最明顯的差異：
- Heap
- 存放在Heap裡面的資料沒有固定的生命週期，需要透過程式語言刻意的定時檢測機制或開發者安排程式操控將不需要的資料從Memory當中刪除釋放空間。
- 舉例像是：新增了一些物件、宣告了全域變數、一些啟動該程式語言所需要使用到的緩衝內容。 - Stack
- 存放在Stack裡面的資料有固定且已知的生命週期，使用Last in First out的儲存方式，當使用完即可清掉，程式撰寫者不需要刻意清掉他，程式語言會自動幫忙回收掉。
- 舉例像是：迴圈裡面計數使用i、在某個函式裡使用的區域變數等。
如果你的函式寫的不好，寫了一個效能極差的無窮迴圈、或者無止盡遞迴，那你的 Stack Memory 將會很快被吃光，最後 out of memory，這種情況，我們叫做 Stack Overflow (堆疊溢位)。Yap，就是當你遇到程式不知道怎麼寫，大家最後會去的求救論壇的名字由來！
反之，要是在程式裡面新增一堆 Object、Array、各種全域變數而且完全不做清理，那總有一天 Heap Memory 的空間也會被消耗殆盡，如果消耗殆盡 out of memory ，我們就叫做 Heap Overflow (堆積溢味)。
我們發現，Stack Memory 因為具有固定且已知的生命週期，因此現在使用的程式語言都會自動幫你回收完畢，開發者只要專注在函式或遞迴寫的效能夠好，基本上不需要擔心Memory 相關問題。
反而 Heap Memory 所儲存的資料的生命週期不固定，每個 Object 哪時候該被從 Memory 裡清掉，何時該保留繼續使用是未知的，對於開發者和程式語言控管是很難的課題，因此我們今天主要會聊聊的主要對象是 Heap Memory 的控制。
Pages & Slots
在 Heap 裡面，Memory 的最小單位是什麼呢？來看個一張圖了解Heap Memory 是怎麼存放物件的：
在 Heap 裡面有許多的 Pages，是 OS 分配給 Application 時的最小單位，我們可以類似這樣說： OS 共分配給該 Application 400 Pages Memory。
每個 Pages 裡面會有 1個 Headers 和許多 Slots。Headers 是來存放該 Page 的相關資訊；Slot 就是我們存放物件資源的最小空間單位。
以ARM常見架構為例的話 (每個OS架構的數字皆不相同)：
- 每個 Page 有 419 個 Slots 和 1個 Header。
- 每個 page 有 16 KB。
- 每個 Slot 有 40 bytes。
Slot 裡面，你可以儲存一個 Object、一串 String、或者一個Symbol等等，儲存之後會指向一串Memory Address。
但如果我們存放的物件是一個超長的String，超出一個Slot所以可使用的 40 bytes 怎麼辦呢？
答案是：程式語言會在原本的 Memory 透過 Reference 的方式指向外部的其他 Slot 進行存放。
Ruby裡面要怎麼看這些Memory資訊？
如果是想要看分配的 pages 和 heap 空間等等資訊，可以透過這個指令：
如果想要了解裡面每個數據所代表的意義，可以看這篇文章。後續我們也會提到一些裡面相關的數據來展示Ruby操作GC的方式。
如果想知道 Reference 的情況，我們可以透過下列的操作方式了解原理：
2. GC是什麼？為什麼我們需要GC?
GC的全名是 “Garbage Collection” 或者 “Garbage Collector”，亦即垃圾回收器，主要是用來 「控制系統記憶體回收行程，自動回收未使用之記憶體的服務」。
硬體的實際擁有的記憶體是有限的，你的電腦可能擁有 16GB 的記憶體，了不起再從硬體 SWAP 個 4G 左右當備用的記憶體空間。總共就是 20 GB 的資源可以分配想去。
想當然，不會全部都是你所撰寫的 Application 全吃掉這 20 GB Memory 資源，實際上可能分配到能使用的 Memory 少之又少，如果你所使用的程式語言沒有一套好的邏輯機制控制將不需要的記憶體回收，或者程式撰寫者沒有刻意的做GC，可想而知，你的Application 會常常自己莫名的crash或變得異常緩慢，這時候維運的工程師可就有得罪受了。
再舉一個例子，例如我們啟動一個 Ruby on Rails Server，一個 request 來了，中間運算建立許多的 ActiveRecord 物件、還有一些需要運算邏輯的變數，最後組成一個 JSON format response回去。
理論上，我們會希望當一個response成功回覆後，在中間過程中使用到的物件、變數應該都要被清理掉，如果 Rails 框架沒有處理好這些回收，只要request 流量一提升，那 Application 就會很快的 Memory Overflow了。
Ruby有在背後偷偷地執行GC嗎？
有的，可以用以下的方式確認：
3. Ruby 實作GC的核心演算法和概念
前言鋪的那麼久，我們總算要來講Ruby的實作演算法和概念了，首先來講講Ruby Heap。
在我們啟動了一個 Ruby Application 像是 Rails 專案時，Ruby 會和 OS 請求並劃分一個 Heap Memory Block 作為使用。
但 Ruby 很賊，劃分的 Heap 空間是絕對不滿足的，因此有時指出去的Reference Address 會是在外部 OS Heap 的空間，這也就導致你會有時會看到Ruby 使用的 Memory 空間會比實際劃分出去的還要大上許多。
Ruby 實際放置 Memory 的狀況
透過這張圖，我們可以了解Ruby放物件的方式：
我們會用 RVALUE 來表示被塞進去 Slot 裡面的物件， RVALUE 是指在C內部的物件表示方式。 RVALUE相對應的值是 LVALUE 。
# 可以這樣理解
# LVALUE (左側的值) = RVALUE (右側的值)
# string, obj 是 LVALUE (左側的值)
# "abc", Object.new 出來的物件是 RVALUE (右側的值)
string = "abc"
obj = Object.newTri-Color Mark and Sweep Algorithm
Mark and Sweep Algorithm ，又簡稱 MS Algorithm，是一個很典型的GC機制運算模型，在許多程式語言都是用這套機制為基礎來實作 GC。而 Ruby 也不例外，而且衍伸出了 Tri-Color 的獨門三色標記演算法。
- Tri-Color Mark
顧名思義，我們會用三種不同的顏色去區分在 Slot 中的 RVALUE ，並且將他們標記起來，以下是最基礎的演算法：
什麼是 root RVALUE呢？就是執行 Ruby 時不可或缺的資訊，如果當 root RVALUE被砍掉，你的程式將會出現問題。他是不可或缺不可被GC走的內容。
了解 root RVALUE後，來用幾張圖解釋一下這個演算法一連串連貫動作的機制：
WHITE)
GREY)
執行到最後僅有白色和黑色，黑色是重要的Memory資料，由 root RVALUE 和其reference出去的內容組成，因此最後就是把白色的 RVALUE 做記憶體回收就好啦！
- Sweep
Sweep 指的就是把白色的 RVALUE給清空，只留下重要的黑色 RVALUE。Ruby 做 sweep 的方式和 Java 的 JVM 很相像，他會 停止一切程式運作，去做 Tri-Color Mark 然後 Sweep 掉不重要的資料。
因此，整個 Ruby 程式運作的感覺會像是：
只是我們體感上無法察覺，但實際上如同上面做了新增5萬個Object的例子，在執行中 Ruby 已默默的中斷了程式138次。
因此，評估 GC 效能指標中，其中一項就是觸發 GC 機制時程式無響應的時間長短。但接著又有個疑問了，所有的白色 RVALUE 都是不重要的嗎？
Generational Garbage Collection
能提出這個想法表示你有抓到重點，因為確實有些白色的 RVALUE是重要的，例如我們new出來的 Object，他也不是重要的 root RVALUE，但驚人的是經歷了 138次 GC 後，我們還是能呼叫該 object 時，顯然他並沒有被GC清掉。
所以像 Java 一樣，在白色 RVALUE裡，也區分成兩種類別，用了世代 (Generational) 區分成 old 和 young 的RVALUE。
這裡要提一個假說：
weak generational hypothesis (弱世代假說)：越年輕的物件越不重要，越可以拋棄。
我們想一下 Rails 的例子，通常我們想要回收的目標是 某個API request response 完成後，該運算期間所使用到的所有物件和變數。 這些變數和物件的生存週期很短，一旦response 出去之後就不需要了，因此是做GC的最好對象。
存在時間越短的物件，越不需要保留。
Ruby 會將白色的 RAVLUE拆分成 old 和 young。每次做sweep時，有時候會 只清掉 young object，有時候則會 young 和 old 全部清掉 。
Minor GC & Major GC
Minor GC：僅清除 young objects。
Major GC：清除所有 objects，Major GC 僅會在觸發多次 Minor GC仍無法獲得足夠空間時才會啟動。在需要手動操作GC時，Ruby 提供了我們以下的方式做 Minor 和 Major GC：
此外，我們來看看 Ruby 在執行 new 5000 次 Object後，做了幾次 Minor 和 Major GC 吧。
Ruby 怎麼衡量該 Object 是 young 還是 old 呢？
我們用上面之前的函式 dump ，來寫一個測試確認到底一個 object 什麼時候會被標上 old flag吧！
我們發現 Ruby 的物件要是經歷過3次的 Minor GC，但仍被歸類在尚在使用的物件無法移除時，那他就會被上了一個 old flag 。
也就是說，在每個 RVALUE裡，會利用了 2 bytes 來存他是否為 old object ，當2個 bytes 2進位的數值皆是 11的時候 (00 -> 01 -> 10 -> 11)，這個 object 就被歸類成 old 了。
到這裡，可能你還有最後一個問題：
頻繁的做GC會有什麼副作用嗎？
Compaction
答案是肯定的，這個問題要由最後的這一小章節來回答。頻繁的GC的確會有副作用的，而這副作用的病名叫做 記憶體碎片化 (memory fragmentation)。
不知道小時候使用 Windows 98 較古老的微軟作業系統時，有沒有使用過「磁碟重組工具」，這個工具會把磁碟各處的散亂檔案標示出來並重新歸類擺放，在下面的圖示可以看到各種散亂資料示意圖，而記憶體也不例外，也會因為頻繁的GC而導致這樣的狀況。
此時，Ruby 3 提供了一種新的方式，可以像磁碟重組工具一樣把散亂的 RVALUE 集中存放，也就是執行所謂的 Compaction (壓實)。
這樣的好處是可以利用更少的 Pages 存放 RVALUE，也更好地做到 CoW (copy-on-write)。
用最後一個例子來看看 Ruby 怎麼達成 Compaction！
結論和後記
到這裡，已經把 Ruby GC 最核心的基礎給講完了，其實所有的程式語言GC的實作方式皆大同小異。因此這篇也可以當作GC的核心概念知識學習。
最後我們來看一下 Ruby 2.7 以及 Ruby 3.0 在發佈時的 Release Note 與 GC相關的內容。
可以看到在 Ruby 2 和 3 對於GC最大的進展在於加入了 Compact 的機制，而在 Ruby 3.0.2 又進一步加入 auto_compact 自動壓實的 method。 (但他有說使用上記得先測試要小心使用)
至於我們一般在使用時需不需要留意GC的狀況呢？或許純 Ruby 開發可能需要考慮，但 Rails 框架下的話，Rails 會幫你一切處理得穩妥妥的，因此請盡情專注在功能開發你的網站吧！
