Ref-counting vs tracing GC — hai cách tìm rác

TL;DR: Có hai họ GC chính. Reference counting (CPython, Swift ARC) gắn một bộ đếm vào mỗi object: mỗi lần tạo thêm tham chiếu thì tăng, mỗi lần xoá tham chiếu thì giảm; về 0 thì giải phóng ngay. Deterministic, không pause — nhưng không bắt được chu trình tham chiếu (hai object trỏ nhau, đếm mãi không về 0). Tracing GC (Java, Go, JS) định kỳ trace từ root tìm toàn bộ reachable object (mark), phần còn lại là rác (sweep). Bắt được mọi chu trình — nhưng gây stop-the-world pause và cần headroom bộ nhớ. Generational GC tối ưu bằng giả thuyết "hầu hết object chết trẻ": chia heap thành young/old, GC young thường xuyên với chi phí thấp, GC old ít hơn.

Bạn viết một class cache giữ tham chiếu tới từng phần tử đã xử lý — trong CPython, phần tử được giải phóng ngay lập tức khi bạn xoá khỏi cache. Nhưng nếu phần tử trỏ ngược lại cache, cả hai sẽ không bao giờ được giải phóng dù bạn xoá toàn bộ — ref-counting bị mù trước chu trình. Trong Java, GC sẽ thu cả hai dù có chu trình, nhưng có thể dừng chương trình vài chục millisecond để làm điều đó. Hai cơ chế, hai tradeoff căn bản — bài này mổ xẻ cả hai.

1. Analogy — đếm khách vs kiểm tra phòng trống

Hình dung quản lý phòng họp. Cách 1 — đếm khách: cửa phòng có một bộ đếm. Mỗi người vào tăng 1, ra giảm 1. Khi đếm về 0, tắt đèn ngay. Nhanh, tức thì — nhưng nếu hai người cứ đứng chờ nhau ra trước, đếm không bao giờ về 0 dù phòng thực tế bỏ phí. Cách 2 — kiểm tra phòng trống: cứ mỗi giờ, nhân viên đi kiểm tra toàn bộ toà nhà từ lối vào chính, đánh dấu mọi phòng thật sự có người dùng; phòng không đánh dấu thì tắt đèn. Tốn thời gian kiểm tra, trong lúc đó ai cũng phải dừng — nhưng không bao giờ bỏ sót phòng trống dù người dùng đứng thành vòng tròn chờ nhau.

2. Reference counting — giải phóng tức thì, bù bằng chi phí mỗi lần gán

Mỗi object có một trường refcount (số nguyên). Bất cứ khi nào:

• Một biến mới trỏ tới object → refcount++
• Một biến ngừng trỏ (gán lại, ra scope, xoá) → refcount--
• refcount == 0 → không còn ai giữ → giải phóng ngay lập tức

flowchart LR
  X["bien x"] --> A["obj A<br/>refcount=2"]
  Y["bien y"] --> A
  B["obj B<br/>refcount=0<br/>→ GIAI PHONG"]

CPython dùng ref-counting làm cơ chế GC chính. Mỗi phép gán trong Python có chi phí refcount++/refcount-- đi kèm. Khi refcount về 0, Python gọi destructor và giải phóng tại chỗ, không chờ chu kỳ GC.

Ưu điểm: giải phóng deterministic — biết chính xác khi nào destructor chạy. Không có stop-the-world pause. Phân bổ chi phí GC đều theo thời gian (mỗi lần gán trả một ít, không trả gộp).

Nhược điểm chính — reference cycle:

# Chu trinh tham chieu trong Python
class Node:
    def __init__(self):
        self.other = None

a = Node()
b = Node()
a.other = b   # a tro toi b, refcount(b) = 1
b.other = a   # b tro toi a, refcount(a) = 1

del a         # refcount(a) giam... xuong 1 (b van tro a) -- KHONG VE 0
del b         # refcount(b) giam... xuong 1 (a van tro b) -- KHONG VE 0
# Ca hai bien a va b da bi xoa -- nhung object van ton tai tren heap
# Khong the giai phong -- LEAK

Sau del a và del b, không có biến nào trong code trỏ tới hai object đó nữa. Nhưng chúng trỏ lẫn vào nhau — refcount của mỗi cái vẫn là 1. Ref-counting không thu được. CPython phải thêm một cycle collector riêng (module gc) chạy định kỳ để phát hiện và thu chu trình — nghĩa là CPython thực ra dùng cả hai cơ chế.

3. Tracing GC — mark-and-sweep từng bước

Tracing GC không đếm tham chiếu. Thay vào đó, định kỳ nó trace toàn bộ đồ thị object từ root.

Mark phase: bắt đầu từ root set (stack, static, thanh ghi), duyệt theo mọi tham chiếu, đánh dấu mọi object đến được là "live".

Sweep phase: quét toàn bộ heap; object không có dấu "live" là rác — thu hồi.

flowchart TD
  subgraph roots["Root set"]
    R1["stack: bien list"]
    R2["static: config"]
  end

  subgraph heap["Heap"]
    A["Object A<br/>✓ marked"]
    B["Object B<br/>✓ marked"]
    C["Object C<br/>✓ marked"]
    D["Object D<br/>✗ unreachable"]
    E["Object E<br/>✗ unreachable"]
    D -- "D tro E" --> E
  end

  R1 --> A
  A --> B
  A --> C
  R2 --> C

  style D fill:#fee2e2,stroke:#ef4444
  style E fill:#fee2e2,stroke:#ef4444

D và E trỏ nhau (chu trình) nhưng không reachable từ root → cả hai bị sweep. Tracing GC bắt được chu trình mà ref-counting không bắt được.

Vì sao phải stop-the-world? Trong khi GC đang trace, nếu ứng dụng vẫn chạy và thay đổi đồ thị tham chiếu, GC có thể đánh dấu sai (mark object còn sống là rác, hoặc bỏ qua object vừa trở thành unreachable). GC đơn giản nhất dừng tất cả thread ứng dụng (stop-the-world) trong suốt mark+sweep để đảm bảo consistency.

Thread ung dung: [=====chay=====|PAUSE|=====chay=====|PAUSE|...]
GC thread:                      [mark+sweep]         [mark+sweep]

Với heap nhỏ, pause vài ms. Heap lớn (vài GB), pause có thể đến hàng trăm ms với GC cũ.

4. Generational GC — khai thác "object chết trẻ"

Quan sát thực nghiệm: phần lớn object có lifetime rất ngắn — object tạm trong một hàm, intermediate result, request object trong web server. Một số nhỏ object sống lâu (cache, singleton, connection pool).

Generational hypothesis: hầu hết object chết trẻ (young) — nên tập trung GC vào đó.

Heap được chia thành young generation (mới cấp phát) và old generation (đã sống qua nhiều lần GC):

• Minor GC (young): chạy thường xuyên, chỉ quét young generation. Rất nhanh (young gen nhỏ, hầu hết object đã chết → ít live object để copy). Pause ngắn.
• Major GC / Full GC (old): quét cả heap. Hiếm hơn, pause dài hơn. Object sống qua đủ lần minor GC được promote lên old gen.

flowchart LR
  NEW["new Object()"] --> EDEN["Eden (young)"]
  EDEN -- "con song sau minor GC" --> S1["Survivor 1"]
  S1 -- "con song sau nhieu lan GC" --> OLD["Old Generation"]
  EDEN -- "chet" --> DEAD1["❌ thu hoi"]
  S1 -- "chet" --> DEAD2["❌ thu hoi"]
  OLD -- "major GC" --> DEAD3["❌ thu hoi"]

Java HotSpot chia young generation thành Eden và hai Survivor space (S0, S1). Mỗi minor GC copy object còn sống từ Eden+S0 sang S1 (hoặc ngược lại), giải phóng toàn bộ Eden và Survivor cũ trong một thao tác — hiệu quả vì hầu hết là rác.

5. Bảng so sánh

6. Pitfall tổng hợp

❌ Pitfall 1 — Ref-counting cycle leak. Pattern phổ biến: parent giữ list con, con giữ tham chiếu ngược tới parent. Trong CPython, cả cây sẽ không bao giờ được giải phóng qua ref-counting (cần cycle collector). Fix: dùng weakref cho chiều ngược — weak reference không tăng refcount.

❌ Pitfall 2 — Tracing GC pause ở latency-nhạy. Hệ thống cần latency dưới 10ms (trading, game, real-time API) dễ bị GC pause vượt SLA. Giải pháp: dùng GC low-latency (G1, ZGC, Shenandoah cho Java; Go GC với pause dưới 1ms), hoặc giảm allocation rate để giảm tần suất GC.

❌ Pitfall 3 — Nhầm "GC nào cũng như nhau". CPython gc bổ sung (cycle collector) khác Java G1 khác Go GC khác Swift ARC. Hành vi pause, tần suất, headroom bộ nhớ khác nhau nhiều. Khi tối ưu GC, phải biết mình đang dùng GC nào và cơ chế cụ thể của nó.

7. Đào sâu (tuỳ chọn)

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

• Bài 01 — Cấp phát thủ công vs GC: khái niệm reachability và root set — nền tảng để hiểu tracing GC trace từ đâu.
• Bài 03 — Vì sao vẫn rò bộ nhớ dù có GC: tracing GC bắt được cycle, nhưng không bắt được object reachable mà bạn không còn cần — bài đó giải thích logical leak.
• Module 3 — Page fault và swap: khi GC tracing duyệt qua heap lớn, nó có thể chạm tới các trang ảo đã bị swap ra đĩa → page fault — GC pause thực tế dài hơn GC time thuần tuý.

9. Tóm tắt

• Reference counting: mỗi object có refcount; về 0 → giải phóng ngay. Deterministic, không STW pause. Không thu được chu trình tham chiếu — CPython phải thêm cycle collector riêng.
• Tracing GC (mark-and-sweep): trace từ root, mark live, sweep rác. Thu được chu trình. Gây stop-the-world pause; cần headroom bộ nhớ.
• Generational GC: khai thác "object chết trẻ" — GC young thường xuyên + rẻ, GC old hiếm hơn + đắt. Java HotSpot dùng Eden + Survivor + Old generation.
• Không có GC hoàn hảo: ref-counting không thể thu cycle; tracing GC phải trả giá bằng pause và overhead.

10. Tự kiểm tra

Bài tiếp theo: Vì sao vẫn rò bộ nhớ dù có GC