Garbage Collection — reachability và ba thuật toán nền tảng

TL;DR: GC coi một object là rác khi không còn đường reference nào từ GC root (static field, stack local, JNI, thread) dẫn tới nó — không phải khi reference count về 0, nên GC xử lý được cả cycle. Trên nền reachability, JVM dựng ba thuật toán nền: mark-sweep (đơn giản, để lại fragmentation), mark-copy (chép live sang nửa heap trống, không fragment nhưng tốn nửa bộ nhớ), mark-compact (dồn live về đầu vùng, không fragment nhưng tốn chi phí dịch). Generational hypothesis — phần lớn object chết trẻ — cho phép chia heap thành young (mark-copy, GC thường xuyên) và old (mark-compact, GC hiếm). Tên collector cụ thể (Parallel, G1, ZGC) chỉ là cách phối ba thuật toán này.

Một service đang chạy êm bỗng có latency p99 nhảy từ 20ms lên 300ms mỗi vài phút, đúng nhịp. Không có request nào chậm ở tầng DB hay network — thời gian bốc hơi bên trong JVM. Thủ phạm quen mặt: garbage collector dừng app thread để dọn heap. Muốn chọn đúng collector và tune nó, trước hết phải hiểu GC quyết định object nào là rác bằng cách nào, và ba thuật toán nền mà mọi collector đều lắp ghép từ đó.

Học xong, bạn Explain được GC quyết định object nào là rác bằng reachability, và ba thuật toán nền mà mọi collector lắp ghép — nền để bài 06b chọn collector theo SLA và bài 12 mổ sâu G1.

1. Analogy — thư viện tự dọn sách

Hình dung thư viện nơi bạn không bao giờ trả sách: rút sách ra bàn đọc, đọc xong bỏ đó. Thủ thư (GC) định kỳ đi một vòng, giữ sách còn có người đang cầm và đem về kho sách không ai đụng tới. Điểm mấu chốt: thủ thư không đếm "cuốn này được mượn mấy lần" mà truy vết từ những người đang ngồi đọc (GC root) xem tay họ với tới cuốn nào. Một chồng hai cuốn kẹp vào nhau ở góc phòng mà không ai cầm — dù "tham chiếu" lẫn nhau — vẫn bị dọn.

2. Khi nào một object bị coi là rác?

Object là rác khi không có chuỗi reference nào dẫn từ một GC root đến nó. GC root là các điểm neo mà runtime chắc chắn còn sống: static field của class đã load, biến local trên stack của mọi thread, JNI reference, và active thread object.

Từ tập root, GC traverse đồ thị reference (BFS/DFS). Object chạm được = live; không chạm được = dead, có thể reclaim.

Stack / Static (GC root)
   |
   v
[A] --> [B] --> [C]
         \
          [D] --> [E]

[F] <--> [G]   (khong co duong tu root -> rac, du F va G tro vao nhau)

A B C D E đều live vì có đường từ root. F và G trỏ vào nhau nhưng không root nào trỏ tới — cả hai là rác.

Đây là lý do Java dùng reachability thay vì reference counting thuần (cơ chế chính của CPython). Reference counting đếm số reference trỏ tới mỗi object, về 0 thì free ngay — nhưng bó tay với cycle: F và G giữ counter của nhau luôn ≥ 1 dù không ai bên ngoài dùng chúng → không tự dọn được (chính vì thế CPython phải bổ sung một cycle detector riêng chạy nền để vá). Reachability đi từ root, không tới được F/G thì thu hồi, bất kể counter.

Đánh đổi: reference counting free tất định (không pause) nhưng leak cycle và mỗi phép gán tốn tăng/giảm counter. Reachability xử lý cycle và cho allocation cực rẻ, đổi lại cần quét heap theo đợt nên latency biến thiên. Java nhắm server nên chọn reachability.

3. Ba thuật toán nền tảng

Sau khi biết object nào live, GC cần thu hồi vùng nhớ của object dead. Có ba cách nền, mọi collector đều lắp ghép từ đây.

3.1. Mark-Sweep

flowchart LR
    A["Mark: traverse tu root<br/>danh dau object live"] --> B["Sweep: quet toan heap<br/>free o nho khong danh dau"]
    style A fill:#93C5FD
    style B fill:#6EE7B7

Mark: đi từ root, đánh dấu mọi object chạm được. Sweep: quét tuyến tính toàn heap, trả lại vùng nhớ của object không đánh dấu. Đơn giản, nhưng để lại fragmentation: object dead nằm rải rác nên vùng trống rời rạc — tổng free có thể đủ mà không khối liền mạch nào chứa nổi một object lớn.

3.2. Mark-Copy (hiện thực kinh điển: thuật toán Cheney)

flowchart TB
    A["Heap chia doi: From + To"] --> B["Chep object live<br/>tu From sang To (lien mach)"]
    B --> C["Xoa sach ca vung From"]
    C --> D["Doi vai tro From <-> To"]
    style B fill:#93C5FD
    style C fill:#6EE7B7

Chia heap thành hai nửa From và To; app chỉ alloc trong From. Khi GC: chép mọi object live từ From sang To (gom liền mạch), xoá nguyên nửa From một lần, rồi đổi vai trò. Ưu: không fragmentation, allocation nhanh (bump-pointer — chỉ dịch con trỏ top lên đúng kích thước object, không dò ô trống rải rác). Nhược: chỉ dùng được nửa heap. Rất hợp vùng ít object live — chép ít là rẻ.

3.3. Mark-Compact

flowchart LR
    A["Mark: danh dau object live"] --> B["Compact: don live ve dau vung<br/>o trong dong lai lien mach"]
    style A fill:#93C5FD
    style B fill:#6EE7B7

Mark như mark-sweep, nhưng thay vì sweep thì compact: dịch mọi object live về đầu vùng, dồn ô trống thành khối liền mạch. Ưu: không fragmentation, không phí nửa heap. Nhược: tốn chi phí dịch object và sửa mọi reference trỏ tới object vừa dịch. Hợp vùng nhiều object live.

4. Generational hypothesis — chia young/old

Quan sát thực nghiệm từ thập niên 1980: 90-95% object chết trẻ — alloc xong dùng vài microsecond rồi mất reference (object trung gian trong stream, biến local, wrapper tham số). Chỉ 5-10% sống lâu (cache, singleton, state dài hạn).

Tận dụng pattern này để khỏi quét toàn heap mỗi lần: chia heap thành hai vùng, mỗi vùng một chiến lược.

• Young: GC thường xuyên, dùng mark-copy — hầu hết đã chết, chép phần live nhỏ là rẻ.
• Old: GC hiếm, dùng mark-compact — object già đa số còn sống, chép sẽ đắt.

Heap (generational):
+-----------------------+--------------------+
|         Young         |        Old         |
+-------+-------+-------+--------------------+
| Eden  |  S0   |  S1   |      Tenured       |
+-------+-------+-------+--------------------+

Object mới luôn sinh trong Eden; hai vùng Survivor (S0/S1) là "To/From" của mark-copy cho young.

Minor GC chỉ quét young: chép live sang Survivor, promote object đủ già sang Old. Nhanh (vài ms) vì phần lớn Eden là rác. Full GC quét toàn heap (young + old, và cả Metaspace), chậm hơn nhiều (hàng trăm ms với heap lớn), thường trigger khi Old đầy — đây là loại pause hay gây breach SLA, và monitor tần suất của nó là việc bắt buộc. (Log HotSpot dùng nhãn "Pause Young" cho minor và "Pause Full" cho full, cùng vài nhãn khác tùy collector — bài 06b đọc kỹ các nhãn này.)

4.1. Tenuring — khi nào thăng cấp

Object phải sống sót qua bao nhiêu vòng minor GC trước khi promote sang Old? Mỗi lần sống sót, tuổi tăng 1; chạm ngưỡng thì lần GC sau chuyển sang Old. HotSpot đặt trần qua -XX:MaxTenuringThreshold (mặc định 15 — và là trần: JVM có thể tự hạ ngưỡng thực tế khi Survivor chật, để promote sớm).

Promote sớm nghĩa là object đáng lẽ chết trong young lại nằm ở Old → Old đầy nhanh hơn → Full GC thường xuyên hơn → pause dài xuất hiện nhiều hơn. Đây là một trong những nguyên nhân "GC pause tăng dần" mà bài 06b dạy cách nhận ra từ GC log.

5. Collector — chỉ là cách phối ba thuật toán

Các collector JVM 21 cung cấp đều xây trên ba thuật toán nền + generational hypothesis; điểm khác nhau là làm việc song song với app tới đâu và do đó pause dài bao nhiêu:

Bài này dừng ở mức tên gọi và pause profile. Cơ chế riêng của từng collector nằm ở bài 12 (G1) và 12b (ZGC/Shenandoah); cách chọn collector theo SLA và đọc GC log ở bài 06b.

6. Pitfall tổng hợp

❌ Nhầm 1: "Java có GC nên không bao giờ memory leak."

static final List<byte[]> CACHE = new ArrayList<>();
// Moi request add vao CACHE, khong bao gio remove
// -> object VAN reachable tu static field -> GC khong the thu hoi -> leak

✅ GC chỉ thu hồi object unreachable. Object còn reference từ root (collection static, listener chưa gỡ, ThreadLocal chưa clear) vẫn "sống" mãi. Leak trong Java = giữ reference ngoài ý muốn.

❌ Nhầm 2: Gọi System.gc() để "dọn ngay cho chắc".

System.gc();   // Hint - JVM co the ignore, thuong trigger Full GC -> pause dai

✅ Tin heuristic của GC. System.gc() thường ép Full GC ngoài lịch → pause dài vô ích. Tắt hẳn bằng -XX:+DisableExplicitGC.

7. 📚 Deep Dive Oracle

8. Liên hệ các bài khác

• Bộ nhớ JVM — heap, metaspace, stack — heap generational mà bài này dọn được bố trí ở đâu, Eden/Survivor/Tenured nằm trong heap ra sao.
• Chọn collector theo SLA và đọc GC log — bước tiếp: từ ba thuật toán nền, chọn Serial/Parallel/G1/ZGC theo latency và xác nhận bằng -Xlog:gc*.
• GC modern — G1 sâu — cơ chế sâu của G1 và cách nó giữ pause ở mức soft target 50-200ms.
• ZGC và Shenandoah — làm sao chạy mark-compact concurrent với app để pause dưới 10ms.

9. Tóm tắt

• GC coi object là rác khi không reachable từ GC root (static field, stack local, JNI ref, active thread). Reachability xử lý được cycle; reference counting thì không.
• Mark-sweep để lại fragmentation; mark-copy không fragment nhưng phí nửa heap (hợp vùng ít live); mark-compact không fragment nhưng tốn dịch + sửa reference (hợp vùng nhiều live).
• Generational hypothesis: 90-95% object chết trẻ → chia young (mark-copy, minor GC nhanh, thường) + old (mark-compact, full GC chậm, hiếm).
• Tenuring: sống sót đủ vòng minor GC (MaxTenuringThreshold mặc định 15) thì promote; Survivor chật ép promote sớm → Old đầy nhanh → Full GC nhiều.
• Collector cụ thể chỉ khác nhau ở cách phối ba thuật toán và mức concurrent — cơ chế ở bài 12/12b, cách chọn ở bài 06b.

10. Tự kiểm tra

Bài tiếp theo: Chọn GC collector theo SLA và đọc GC log