모범답안 — 락프리 자료구조의 안전한 메모리 회수

난이도: 최상

1. 문제 정의: 왜 즉시 free 가 위험한가

락프리 자료구조에서 한 스레드(T1)가 노드 N 을 CAS 로 unlink 하더라도, 다른 스레드(T2)가 바로 그 순간 N 을 가리키는 포인터를 이미 읽어 들고 있을 수 있다. T2 는 "head 를 읽음 → next 를 따라감" 같은 무잠금 순회 중이라, T1 의 unlink 와 T2 의 접근 사이에는 어떤 상호배제도 없다. T1 이 unlink 직후 delete N 하면, T2 가 N->next 를 읽는 순간 use-after-free (해제된 메모리 접근)가 된다 — 크래시, 또는 그 메모리가 재할당돼 다른 객체가 들어왔다면 조용한 데이터 오염.

핵심은 "논리적 제거"와 "물리적 회수(free)"를 분리해야 한다는 것이다. 제거는 CAS 로 즉시 가능하지만, free 는 "이 노드를 아직 들고 있는 독자가 아무도 없음" 을 보장한 뒤에만 가능하다. 그 보장을 어떻게 만드느냐가 회수(reclamation) 기법의 핵심.

ABA 와의 구별. ABA 는 CAS 의 정확성 문제다: 값이 A→B→A 로 돌아오면 CAS 가 "안 바뀐 줄" 착각해 성공해 버린다(특히 free 된 노드가 재할당돼 같은 주소로 돌아올 때 악화). 메모리 회수 문제는 수명(use-after-free) 문제다. 둘은 얽혀 있다 — 노드를 너무 빨리 회수하면 그 주소가 재사용돼 ABA 를 유발하기도 한다 — 하지만 별개의 결함이다. ABA 는 태그된 포인터/ 버전 카운터로, 회수는 hazard pointer/EBR/RCU 로 다룬다.

2. 단순 해법의 한계

• 원자적 참조계수(노드별): 노드에 atomic refcount 를 두고 접근 시 증가, 끝나면 감소, 0 이면 free. 문제: ① "노드 포인터를 읽고 → refcount 를 올린다" 사이에 그 노드가 free 될 수 있어(읽는 순간 이미 0→free) 닭-달걀 문제. 이를 풀려면 더블 워드 CAS 나 특수 프로토콜이 필요. ② 모든 읽기마다 atomic 증감 → 캐시 라인 경합(bouncing) 으로 읽기 많은 워크로드에서 느리다. ③ 순환 참조 누수.
• C++ shared_ptr: std::atomic<shared_ptr>(C++20) 또는 atomic_load/store(shared_ptr*) 로 락프리 비슷하게 만들 수 있으나, 구현이 내부 락/더블 워드 CAS 에 의존하고 사실상 락프리가 아니거나 매우 느릴 수 있다. 제어블록 원자 증감 비용도 위 refcount 와 동일.
• GC 언어(C#/Java): GC 가 "도달 불가" 를 판정해 회수하므로 use-after-free 가 원천 사라진다 → 락프리 자료구조 구현이 훨씬 쉽다. 대신 GC 일시정지/압박이라는 다른 비용, 그리고 결정적(deterministic) 회수 시점을 포기. C++ 진영의 EBR/RCU 는 "수동 GC" 에 가깝다.

3. 세 기법

• Hazard Pointer (HP): 각 스레드가 "지금 내가 접근 중인 노드" 를 공개된 hazard 슬롯에 게시(publish)한다. 회수하려는 스레드는 free 후보를 즉시 지우지 않고 retire 리스트에 모았다가, 주기적으로 "모든 스레드의 hazard 슬롯을 스캔" 해 아무도 가리키지 않는 노드만 free 한다. 보장: free 직전에 모든 hazard 를 확인하므로 use-after-free 없음.

  • 읽기 경로: 노드 접근 전 hazard 슬롯에 store + 메모리 펜스 → 약간의 오버헤드(원자 store).
  • 메모리: 미회수 노드 수가 스레드 수에 비례(상한 있음). 회수 지연 작음.
  • 복잡도: 중간. 스레드별 슬롯 관리·스캔 필요.

• Epoch-Based Reclamation (EBR) / QSBR: 전역 에포크(세대) 카운터를 둔다. 스레드는 자료구조 접근 구간(critical section)에 들어갈 때 현재 에포크를 "내가 이 에포크에서 활동 중" 이라고 표시한다. retire 된 노드는 에포크 태그와 함께 보관하고, 모든 활동 스레드가 그 에포크를 지나갔을 때(=아무도 옛 에포크에 머물지 않을 때) 비로소 free. QSBR 은 "정지점(quiescent state)" 을 스레드가 주기적으로 알리는 변형.

  • 읽기 경로: 거의 공짜(에포크 표시뿐, 노드마다 펜스 불필요) → 읽기 가장 빠름.
  • 메모리: 한 스레드라도 critical section 에 오래 머물면 회수가 막혀 미회수 누적(메모리 팽창) 위험. "락프리 순회는 짧게" 가 전제.
  • 복잡도: 중간. 단, 블로킹/긴 작업이 critical section 에 들어가면 위험.

• RCU (Read-Copy-Update): 읽기는 락 없이(거의 공짜) 진행. 쓰기는 새 버전을 만들고 포인터를 교체(publish) 한 뒤, 모든 기존 독자가 떠날 때까지 대기(grace period) 하고 옛 버전을 free. 커널/리눅스에서 널리 쓰이며, 사실상 EBR 과 사촌(둘 다 "유예 기간" 개념).

  • 읽기 경로: 최강(read-side critical section 이 매우 가벼움).
  • 쓰기: copy 비용 + grace period 대기(쓰기 지연↑).
  • 적합: read-mostly. 쓰기 빈번하면 copy 비용·유예 비용이 커 부적합.

요약 비교: 읽기 속도 RCU≈EBR > HP. 회수 지연/메모리 안전 상한은 HP 가 가장 타이트(스레드별 상한), EBR/RCU 는 "긴 독자" 가 있으면 회수가 밀린다. 구현 난이도는 셋 다 만만치 않다 → 가능하면 검증된 라이브러리(folly, libcds, userspace-RCU)를 쓴다.

4. 실무 선택 (MMORPG read-mostly)

존의 엔티티 인덱스, 라우팅/설정 테이블처럼 읽기 압도적·쓰기 드문 자료구조에는 RCU 또는 EBR 이 잘 맞는다: 읽기 경로가 거의 공짜라 매 틱 수많은 조회를 싸게 처리하고, 가끔의 변경은 "새 스냅샷 publish + 유예 후 옛 것 회수" 로 흡수한다. 단 전제는 읽기 critical section 이 짧을 것(틱 처리 중 블로킹 호출 금지) — 길면 회수가 막혀 메모리가 팽창한다.

반대로 쓰기가 잦고 노드 수명이 짧으며 메모리 상한을 타이트하게 지켜야 하면 Hazard Pointer 가 안전하다(미회수량이 스레드 수에 묶여 예측 가능). C# 서버라면 애초에 GC 가 회수를 처리하므로, 락프리 컬렉션(ConcurrentDictionary 등)이나 불변 스냅샷 + 원자적 교체 (Interlocked.Exchange(ref _snapshot, newSnapshot))로 RCU 와 유사한 효과를 GC 위에서 간단히 얻는 게 보통 최선이다.

결론: "락프리 = 빠르다" 는 절반의 진실이고, 안전한 메모리 회수까지 설계해야 비로소 정확하다. read-mostly 면 RCU/EBR(또는 GC 언어의 불변 스냅샷 교체), 쓰기 잦고 상한이 중요하면 HP, 그리고 검증된 라이브러리를 우선 고려한다.