콘텐츠로 이동
hgryoo · Docs

(KO) CUBRID 락프리 트랜잭션 회수 — system, table, descriptor, address marker

목차

학술적 배경

섹션 제목: “학술적 배경”

락프리 자료구조에서 가장 어려운 문제는 insert도 delete도 아니다. 안전한 메모리 회수 (Safe Memory Reclamation, SMR)이다. 자료구조에서 unlink된 노드를 언제 다시 할당자에게 돌려주어도 되는가? unlink 직후의 순진한 free()는 그 노드를 디레퍼런싱 중인 동시 리더에게 use-after-free를 던져준다. 그렇다고 해서 충분히 오래 기다리는 것은 경계 없는 시간이며 메모리 누수다. 올바른 원시 자료구조는 더 이상 어떤 리더도 그 노드를 들고 있지 않다는 점을 증명하는 어떤 스킴이다. SMR은 Maged Michael (Michael 2004, IEEE TPDS)이 처음 정형화했고 이후 McKenney, Fraser, Brown 등이 발전시켰다.

주류 기법 네 가지를 비용·지연·일반성 측면에서 비교하면 다음과 같다.

기법리더 비용회수 지연자료구조별 스코프?
Hazard pointers (HP)접근당 원자 store O(1)유한 (최악의 경우 K hazard × N threads 스캔)가능
Epoch-based reclamation (EBR / Fraser 2004)O(1) — 진입 시 에포크 등록한 에포크 (수십 마이크로초)가능
RCU (Read-Copy-Update; McKenney 2001+)사실상 0 — rcu_read_lock은 barrier()한 유예 기간Linux에서는 시스템 단위
Quiescent-state-based (QSBR)0 — 리더가 정적 상태를 암묵적으로 보고모든 스레드가 한 번씩 quiesce할 때까지가능

EBR(그리고 그것의 사용자 공간 사촌인 liburcu)은 모든 read-side 임계 구역을 enter_epoch / exit_epoch로 둘러싼다. 회수 시점에는 모든 은퇴 노드를 순회하며 자기 retirement epoch가 현재 진입한 최소 에포크 보다 엄격히 작은 노드만 free한다. 핵심 불변식은 단순하다. 어떤 스레드도 노드 N이 에포크 E로 은퇴된 이후로 E 이하의 에포크에 진입하지 않았다면, N은 어떤 리더로부터도 도달 불가능하므로 회수해도 된다. 이 스킴은 세 가지 성질에 올라타 있다.

  1. 에포크 카운터가 단조 증가한다.
  2. 스레드의 현재 활성 에포크는 그 스레드가 은퇴와 새 읽기를 페어링 한 뒤에야 관찰된다. 따라서 리더가 가진 스냅샷의 에포크보다 라이터 의 은퇴 에포크가 더 클 수 없다.
  3. 최소 활성 에포크 스캔은 게으르게 해도 된다. 리더가 그것 때문에 막히 지 않는다.

운영적 트레이드오프 두 가지가 설계를 좌우한다.

  • 세분도. EBR은 자연스럽게 자료구조별이다. vacuum 스레드의 해시맵 에포크가 쿼리 플랜 캐시의 에포크를 잠가서는 안 된다. 스코프는 시스템 이 아니라 자료구조다.
  • min-active-epoch 스캔은 O(N_threads)이다. 매 은퇴마다 돌리면 비싸다. 한 번도 안 돌리면 지연이 무한이다. 표준적인 절충은 매 K번 은퇴마다인데, K는 스캔 비용을 은퇴 빈도와 분할 상환할 수 있도록 고른 값이다. K가 갱신 주기(refresh interval)다.

CUBRID의 트랜잭션 기반 회수는 정확히 EBR을 데이터베이스 어휘로 다시 부른 것이다. 에포크는 트랜잭션 ID이고, 자료구조별 자료구조는 트랜잭션 테이블이며, 스레드별 상태는 트랜잭션 디스크립터, “은퇴된 노드는 회수 가능 노드”이다. 갱신 주기는 MATI_REFRESH_INTERVAL(Minimum Active Tran Id의 약자)이라는 이름으로, 100으로 설정되어 있다.

이 스킴은 일반적인 의미의 ABA를 풀지 않는다. 보장하는 바는, 트랜잭션 Tr 동안에 은퇴된 노드는 모든 디스크립터가 idle이거나 tranid > Tr인 상태가 되기 전까지는 회수되지 않는다는 점이다. 이 윈도우 안에서, 은퇴 이전부터 살아 있던 리더는 여전히 노드를 원래 주소에서 보며, 그 포인터 위에서 이루어지는 어떤 CAS도 살아 있는 객체를 다룬다. 포인터-값 수준의 ABA — 노드가 은퇴되고 그 바이트가 나중에 회수되어 다른 노드로 재사용 되고, 제3자가 그 같은 주소를 다시 자료구조에 집어넣는 시나리오 — 는 트랜잭션 디스크립터를 열어둔 어떤 스레드에 대해서는 막힌다. 락프리 자료구조를 만지면서도 start_tran/end_tran 브래킷을 두지 않는 리더 는 보호 바깥에 있다.

DBMS 공통 설계 패턴

섹션 제목: “DBMS 공통 설계 패턴”

락프리 내부 자료구조를 출하하는 모든 DBMS는 어떤 형태로든 SMR 비용을 낸다. 구현은 다르지만 개념적 템플릿은 공유된다.

자료구조별 회수 테이블

섹션 제목: “자료구조별 회수 테이블”

회수 원시 자료구조는 자료구조별이지, 프로세스별이 아니다. 락 매니저 의 자원 해시, 페이지 버퍼 BCB 해시, 세션 테이블 — 각자 자기 테이블을 소유하는 이유는, 이들을 섞어버리면 한쪽의 회수가 다른 쪽 리더의 지연 뒤에 잠기기 때문이다.

PostgreSQL의 XactLockTable과 LockHashPartitionLock은 무거운 LWLock 을 쓴다. 회수는 암묵적이다(락프리 자료구조가 없음). InnoDB의 lock_sys_t 는 뮤텍스로 보호된다. Redis는 단일 스레드 모델을 쓰므로 동시 회수 문제가 없다. 락프리 내부 자료구조를 실제로 돌리는 DBMS(Citus, Yugabyte, FoundationDB, CockroachDB)는 언어 런타임의 GC(Go, Java)에 기대고, 할당당 오버헤드를 내는 대신 SMR 문제 자체를 회피한다.

CUBRID는 C++ 아웃라이어다. 락프리 내부 + 수동 메모리 관리 + 자체 EBR이다. 처리량을 사는 대가로 lockfree::tran::* 기계가 통째로 존재 하고 옳아야 한다.

스레드별 디스크립터

섹션 제목: “스레드별 디스크립터”

모든 리더는 노드 X를 사용하는 임계 구역에 들어가 있다를 발행해야 한다. 발행은 싸야 한다. 모든 읽기 핫 패스에 들어가니까. 그리고 발행 은 은퇴하는 스레드가 유한 시간 안에 관찰 가능해야 한다. 실제 구현은 다음과 같이 한다.

  • 스레드별 local epoch 정수. 진입 시 원자 store, 이탈 시 원자 clear. 회수자는 모든 스레드의 엔트리를 루프하며 읽는다. EBR / liburcu / CUBRID modern 스택이 이 방식이다.
  • 스레드별 hazard-pointer 배열 K 슬롯. 각 슬롯이 스레드가 현재 디레퍼런싱 중인 대상 포인터다. 리더는 store, unlink 검사, 디레퍼런싱 순서로 진행한다. CUBRID는 안 쓴다.
  • CPU별 시퀀스 카운터 + 회수자 스레드 주기적 호출. CUBRID는 안 쓴다.

min-스캔 분할 상환

섹션 제목: “min-스캔 분할 상환”

N개 스레드 사이의 전역 최소를 계산하는 일은 read/write 경로에서 유일하 게 O(1)이 아닌 연산이다. 모든 구현은 이를 분할 상환한다.

  • liburcu는 gp_seq를 콜백 시점(call_rcu)에 게으르게 계산.
  • Java G1 컬렉터는 GC 루트를 동시에 추적하고 백그라운드로 스윕.
  • CUBRID는 매 MATI_REFRESH_INTERVAL(=100)번째 전역 ID 증가마다 그 증가를 일으킨 스레드 안에서 min_active_tranid를 다시 계산한다. 비용은 은퇴하는 스레드가 내며, 리더는 내지 않는다.

은퇴 리스트 소유권

섹션 제목: “은퇴 리스트 소유권”

설계는 두 가지가 있다.

  • 자료구조 단위 전역 은퇴 리스트. 은퇴하는 모든 스레드가 공유 리스트에 append. 장점: 부기가 단순. 단점: 공유 리스트 위에서 경합이 생기고, 회수자가 매 스캔마다 모든 항목을 순회해야 함.
  • 스레드별 은퇴 리스트. 각 스레드가 내가 은퇴시킨 것들의 정렬된 리스트를 들고 있다. 회수는 tranid < min_active인 접두사만 순회. CUBRID는 이쪽을 택했다. 모든 lockfree::tran::descriptor가 자기 m_retired_head, m_retired_tail 링을 가진다.

스레드별 리스트가 작동하는 근거는, 은퇴 순서가 tranid 순서와 같다는 점에 의존한다. (그리고 그것은 start_tran_and_increment_id가 CAS 아래 에서 신선한 전역 ID를 가져오기 때문에 성립한다.) 따라서 접두사 워크는 엄격히 증가하는 스캔이며, 첫 번째로 tranid >= min_active인 노드를 만나면 멈춘다.

학술 ↔ CUBRID 매핑

섹션 제목: “학술 ↔ CUBRID 매핑”
개념CUBRID 이름
EBR 에포크 카운터table::m_global_tranid (단조 어토믹)
스레드별 활성 에포크descriptor::m_tranid (start_tran이 설정)
Idle 센티넬INVALID_TRANID = numeric_limits<id>::max()
스레드별 은퇴 리스트descriptor::m_retired_head/tail (m_retired_next로 연결)
Min-active-epochtable::m_min_active_tranid (게으르게 계산되는 어토믹)
갱신 주기MATI_REFRESH_INTERVAL = 100
스레드별 상태 베이스tran::reclaimable_node
사용자 정의 소멸자 훅reclaimable_node::reclaim() (가상, 기본 delete this)
스레드별 인덱스tran::index (typedef size_t); tran::system::assign_index로 할당

CUBRID의 구현

섹션 제목: “CUBRID의 구현”

세 클래스, 한 가지 목적

섹션 제목: “세 클래스, 한 가지 목적”

modern 회수 스택은 정확히 세 클래스 + 은퇴 가능 노드용 베이스 클래스 하나로 구성된다.

// lockfree::tran::system — src/base/lockfree_transaction_system.hpp
//   시스템 안의 모든 테이블이 공유하는 인덱스 디스펜서.
class system {
public:
  system () = delete;
  system (size_t max_tran_count);
  index assign_index ();         // 신선한 스레드별 인덱스 발급
  void  free_index (index idx);  // 반환
  size_t get_max_transaction_count () const;
private:
  size_t m_max_tran_per_table;
  bitmap m_tran_idx_map;         // ONE_CHUNK 스타일, full-usage 임계
};


// lockfree::tran::table — src/base/lockfree_transaction_table.hpp
//   락프리 자료구조마다 한 개; 전역 tranid와 디스크립터 배열을 소유.
class table {
public:
  table (system &sys);
  descriptor &get_descriptor (const index &tran_index);
  void start_tran (const index &);
  void end_tran (const index &);
  id get_current_global_tranid () const;
  id get_new_global_tranid ();           // 어토믹 bump 후 반환
  id get_min_active_tranid () const;
private:
  static const id MATI_REFRESH_INTERVAL = 100;
  void compute_min_active_tranid ();
  system &m_sys;
  descriptor *m_all;                     // 크기 = sys.get_max_transaction_count()
  std::atomic<id> m_global_tranid;
  std::atomic<id> m_min_active_tranid;
};


// lockfree::tran::descriptor — src/base/lockfree_transaction_descriptor.hpp
//   스레드별·테이블별 상태.
class descriptor {
public:
  void start_tran ();                    // 현재 전역 ID 스냅샷 (bump 안 함)
  void start_tran_and_increment_id ();   // 전역 bump 후 새 ID 보유
  void end_tran ();
  void retire_node (reclaimable_node &); // 은퇴 링에 append
  void reclaim_retired_list ();          // tranid < min_active 접두사 순회
  bool is_tran_started () const;
  // ...
private:
  table *m_table;
  id m_tranid;                           // idle이면 INVALID_TRANID
  id m_last_reclaim_minid;
  reclaimable_node *m_retired_head;
  reclaimable_node *m_retired_tail;
  bool m_did_incr;
  reclaimable_node *m_saved_node;        // find-and-insert 핑퐁용 로컬 보관소
  size_t m_retire_count, m_reclaim_count;
};

관계는 일대다·한 방향이다.

  • 한 tran::system이 여러 tran::table 인스턴스의 토대가 될 수 있다. CUBRID 서버에는 정확히 한 개의 서버 단위 tran::system이 있고 (cubthread::get_thread_entry_lftransys()가 반환), 최대 스레드 수로 파라미터화된다.
  • 각 tran::table은 자기 descriptor[] 배열을 소유한다. 배열 크기는 생성 시 m_sys.get_max_transaction_count()로 정해지고, 모든 슬롯이 초기화된다. 희소 맵이 아니라 tran::index로 인덱싱되는 미리 할당된 밀집 배열이다.
  • tran::index는 스레드 수명 동안 고정이다. 스레드 셋업 때 할당받아 같은 시스템 안의 모든 table에서 유효하다.

프로토콜 — 읽기

섹션 제목: “프로토콜 — 읽기”

리더 측 임계 구역은 다음과 같다.

  1. 디스크립터 위치 확인. tran::descriptor &tdes = table.get_descriptor (my_index).
  2. 브래킷 열기. tdes.start_tran()이 현재 전역 ID를 스냅샷한다. 디스크립터의 m_tranid가 그 스냅샷이 된다.
  3. 락프리 자료구조 만지기. 포인터 읽기, 값 CAS, 체인 워크. 읽은 어떤 포인터든 end_tran() 전에는 회수되지 않음이 보장된다. 네 뒤에 오는 모든 은퇴 스레드가 네가 end_tran() 하기 전까지 min_active_tranid <= m_tranid를 본다.
  4. 브래킷 닫기. tdes.end_tran()이 m_tranid = INVALID_TRANID로 리셋.

접근당 비용은 어토믹 load 한 번(전역 ID 스냅샷)과 어토믹 store 한 번(디스크립터 쓰기). 둘 다 기본값으로 seq-cst다. 디스크립터 쓰기는 다른 디스크립터와 동기화되지 않는다. 디스크립터의 소유 스레드만이 그것에 쓰기 때문이다. 은퇴 스레드의 compute_min_active_tranid()는 모든 디스크립터의 m_tranid를 읽는다. 읽기는 평범한 get_transaction_id() load이며 x86에서는 워드 크기 읽기가 순차적 일관성을 가진다.

start_tran / end_tran을 호출자 스레드의 디스크립터 위에서만 (공유 캐시 라인 위의 어토믹 없이) 처리하기로 한 결단이 읽기 경로를 싸게 만든다. 리더는 자기 캐시 라인 비용만 낸다.

프로토콜 — 은퇴

섹션 제목: “프로토콜 — 은퇴”

은퇴 측은 다음과 같다.

  1. 디스크립터 위치 확인. 읽기와 같음.
  2. bump를 동반한 브래킷 열기. tdes.start_tran_and_increment_id()이 원자적으로 m_table->m_global_tranid를 한 칸 올리고 새 ID를 m_tranid에 할당한다. bump는 은퇴 에포크가 어떤 동시 리더의 스냅샷보다도 엄격히 크다는 점을 보장한다.
  3. 회수 가능한 노드 먼저 회수. reclaim_retired_list()이 m_retired_head 링에서 m_retire_tranid < min_active_tranid인 접두사를 순회하며 각 노드의 reclaim() (가상, 기본 delete this) 을 호출한다. 분할 상환이다. 매 retire는 지난 호출 이후로 회수 가능해진 노드들을 같이 정리하는 비용을 낸다.
  4. 새 은퇴 노드 append. retire_node()가 은퇴 노드의 m_retire_tranid를 m_tranid로 설정하고 은퇴 링의 tail에 매단다.
  5. 브래킷 닫기. end_tran().

은퇴 노드의 m_retire_tranid는 현재 전역 ID이지 다음 것이 아니다. 왜 안전한가? 이미 tranid <= my_tranid를 스냅샷한 모든 리더는 자기 트랜잭션이 끝날 때까지 m_tranid가 my_tranid 이하로 열려 있다. 따라 서 min_active_tranid는 그런 리더들이 모두 끝날 때까지 my_tranid를 초과할 수 없다. 결국 min_active > my_tranid ⇔ 어떤 리더도 my_tranid 이하의 스냅샷을 가지지 않음 ⇔ 어떤 리더도 은퇴 노드를 디레퍼런싱할 수 없음.

min-active-tranid 스캔

섹션 제목: “min-active-tranid 스캔”

매 100번째 get_new_global_tranid()마다 게으르게 계산된다.

// lockfree::tran::table::get_new_global_tranid — src/base/lockfree_transaction_table.cpp:73
id table::get_new_global_tranid ()
{
  id ret = ++m_global_tranid;
  if (ret % MATI_REFRESH_INTERVAL == 0)
    {
      compute_min_active_tranid ();
    }
  return ret;
}


// lockfree::tran::table::compute_min_active_tranid — src/base/lockfree_transaction_table.cpp:90
void table::compute_min_active_tranid ()
{
  // note: all transactions are actually claimed from boot. this code is optimized
  //       for this case. if we ever change how transactions are requested, this
  //       must be updated too
  id minvalue = INVALID_TRANID;  // nothing is bigger than INVALID_TRANID
  for (size_t it = 0; it < m_sys.get_max_transaction_count (); it++)
    {
      id tranid = m_all[it].get_transaction_id ();
      if (minvalue > tranid)
        minvalue = tranid;
    }
  m_min_active_tranid.store (minvalue);
}

두 가지를 짚어둘 만하다.

  • 스캔은 현재 점유된 디스크립터만이 아니라 모든 디스크립터를 본다. 헤더 주석은 그 이유를 “all transactions are actually claimed from boot”라고 명시한다. 스레드 인덱스가 시작 시점에 할당되어 평생 보유 된다는 가정 때문이다. 미래 리팩터링이 동적 on-demand 인덱스 할당을 도입한다면 이 스캔은 빈 슬롯을 건너뛰도록 다시 써야 한다(그렇지 않으면 빈 슬롯의 INVALID_TRANID(=numeric_limits<id>::max())는 최소값에 영향을 못 주지만, 빈 슬롯이 무의미한 캐시 미스를 추가한다).
  • INVALID_TRANID가 numeric_limits<id>::max()인 것은 의도적이 다. Idle 디스크립터는 최댓값을 저장하므로 최소값을 낮추지 못한 다. 은퇴 측의 tranid < min_active 검사는 모두가 idle인 세상을 모든 은퇴 노드가 회수 가능으로 다룬다(min_active == INVALID_TRANID이고 모든 은퇴 노드의 m_retire_tranid는 어떤 실제 ID <= m_global_tranid < INVALID_TRANID).

디스크립터 단위 은퇴 링

섹션 제목: “디스크립터 단위 은퇴 링”

각 디스크립터는 단일 연결의 순서 보존된 은퇴 노드 링을 m_retired_head / m_retired_tail로 유지한다. 각 노드는 m_retired_next와 m_retire_tranid를 가진다. 삽입은 m_retired_tail 끝으로 가고, 회수는 m_retired_head 앞에서 시작된다.

// lockfree::tran::descriptor::retire_node — src/base/lockfree_transaction_descriptor.cpp:65
void descriptor::retire_node (reclaimable_node &node)
{
  bool should_end = !is_tran_started ();
  start_tran_and_increment_id ();           // 전역 ID bump


  reclaim_retired_list ();                  // 분할 상환 정리


  node.m_retire_tranid = m_tranid;
  node.m_retired_next = NULL;
  // add to tail to keep delete ids ordered
  if (m_retired_tail == NULL) {
    assert (m_retired_head == NULL);
    m_retired_head = m_retired_tail = &node;
  } else {
    m_retired_tail->m_retired_next = &node;
    m_retired_tail = &node;
  }
  ++m_retire_count;


  if (should_end)
    end_tran ();                            // 이전 브래킷 상태 복원
}

은퇴 경로는 잠금을 잡지 않는다. 디스크립터의 m_retired_* 포인터 는 아무와도 경쟁하지 않는 단일 라이터(소유 스레드)만 쓴다. min-스캔이 각 디스크립터의 m_tranid(워드 한 개)를 읽기는 하지만 링은 읽지 않는 다. 링은 소유 스레드 사적 데이터다.

reclaim_retired_list()의 빠른 경로는 m_min_active_tranid를 한 번 읽고 변화가 없으면 바로 빠져나간다.

// lockfree::tran::descriptor::reclaim_retired_list — src/base/lockfree_transaction_descriptor.cpp:133
void descriptor::reclaim_retired_list ()
{
  id min_tran_id = m_table->get_min_active_tranid ();
  if (min_tran_id <= m_last_reclaim_minid) {
    // nothing changed
    return;
  }
  while (m_retired_head != NULL && m_retired_head->m_retire_tranid < min_tran_id)
    reclaim_retired_head ();
  if (m_retired_head == NULL)
    m_retired_tail = NULL;


  m_last_reclaim_minid = min_tran_id;
}

이 빠른 빠져나옴이 은퇴를 분할 상환된 O(1)으로 만든다. MATI_REFRESH_INTERVAL 경계를 넘는 호출만 자기 디스크립터 위에서 스캔 비용을 낸다.

Reclaim은 노드의 가상 메서드다

섹션 제목: “Reclaim은 노드의 가상 메서드다”

은퇴 노드가 자기 소멸자를 소유한다. 기본은 delete this이고, free list가 이를 오버라이드해 노드를 free list의 available 리스트로 다시 push한다.

// lockfree::tran::reclaimable_node — src/base/lockfree_transaction_reclaimable.hpp:46
class reclaimable_node {
public:
  reclaimable_node () : m_retired_next (NULL), m_retire_tranid (0) {}
  virtual ~reclaimable_node () = default;
  virtual void reclaim () { delete this; }   // 재활용을 원하면 오버라이드
protected:
  reclaimable_node *m_retired_next;
private:
  friend descriptor;
  id m_retire_tranid;
};


// lockfree::freelist<T>::free_node::reclaim — src/base/lockfree_freelist.hpp:523
void free_node::reclaim () final override
{
  m_t.on_reclaim ();              // 페이로드의 on_reclaim 훅
  m_retired_next = NULL;
  --m_owner->m_retired_count;
  ++m_owner->m_available_count;
  m_owner->push_to_list (*this, *this, m_owner->m_available_list);
}

계약은 다음과 같다. 노드 저장소를 어딘가가 소유하고 있고(free list, 힙, 임베디드 슬롯 등), reclaim()은 그 저장소를 돌려놓는 훅이다. delete this는 new로 할당되어 별도 free list가 없는 코드의 기본값 이다. 해시맵 엔트리는 free list가 오버라이드한 reclaim을 거치므로 노드에 delete가 호출되지 않는다. 재활용된다.

save / pull-saved-reclaimable 메커니즘

섹션 제목: “save / pull-saved-reclaimable 메커니즘”

descriptor는 보조 원시 함수 한 쌍을 노출한다.

void save_reclaimable (reclaimable_node *&node);
reclaimable_node *pull_saved_reclaimable ();

사용 사례는 이렇다. 어떤 스레드가 해시맵에서 find_or_insert를 한다. free list에서 새 노드를 투기적으로 claim(freelist_claim)하고, 체인에 CAS-link하려다가, 다른 스레드가 같은 키로 이미 삽입했음을 발견한다. 투기적으로 claim한 노드는 이제 쓸모없다. 그러나 아직 은퇴시키면 안 된다. 은퇴는 전역 ID를 bump하고 분할 상환 비용을 부과한다. free list의 available 리스트로 push하고 싶지도 않다. 다음 호출 지점과 경쟁 이 생긴다. 대신 자기 디스크립터 위에 저장한다.

// freelist_claim — src/base/lockfree_hashmap.hpp:663
T *
hashmap<Key, T>::freelist_claim (tran::descriptor &tdes)
{
  T *claimed = NULL;
  free_node_type *fn =
    reinterpret_cast<free_node_type *> (tdes.pull_saved_reclaimable ());
  // ... fn != NULL이면 free list로 가지 않고 저장된 노드 재사용
  if (fn == NULL) {
    fn = m_freelist->claim (tdes);
    // f_init으로 초기화
  }
  // ...
}

다음 번에 같은 스레드가 freelist_claim을 부르면 저장된 노드가 free list CAS-pop 전에 꺼내져서 재사용된다. 이 트릭이 경쟁 키 위에서 find_or_insert를 싸게 만드는 이유 중 하나다. 투기적 claim이 낭비되지 않는다.

주의할 점: save_reclaimable은 디스크립터당 한 번에 한 노드만 저장 가능함을 단언한다(assert (m_saved_node == NULL)). 어떤 스레드가 저장 후 다음 save_reclaimable 전에 pull을 잊는다면, 두 번째 save가 디버그에서는 단언 실패하고 릴리스에서는 조용히 덮어쓴다. 해시맵 호출 지점은 저장 노드의 수명이 단일 해시 연산을 벗어나지 못하도록 작성되어 있다.

스레드별 인덱스 할당 — 생애 주기

섹션 제목: “스레드별 인덱스 할당 — 생애 주기”

스레드는 태어나서 system::assign_index()를 불러 고유한 인덱스를 받고, 죽거나 free_index로 인덱스를 반환할 때까지 계속 쓴다. CUBRID 서버에서 모든 스레드는 thread-pool 디스패치 시점에 인덱스를 받고 워커의 수명 동안 보유한다. 인덱스는 cubthread::entry::m_lf_tran_index 에 저장되고 entry::get_lf_tran_index()로 노출된다.

// lockfree::tran::system::assign_index — src/base/lockfree_transaction_system.cpp:39
index system::assign_index ()
{
  int ret = m_tran_idx_map.get_entry ();
  if (ret < 0) { assert (false); return INVALID_INDEX; }
  return static_cast<index> (ret);
}

비트맵은 ONE_CHUNK 스타일에 FULL_USAGE_RATIO(1.0) — “모든 슬롯이 사용 가능” — 이다. 따라서 assign_index가 실패하는 경우는 모든 슬롯 이 점유된 경우뿐이고, 부팅 시 모두 claim하는 모델 아래에서는 max_tran_count 잘못 잡았을 때만 일어난다.

생애 주기 다이어그램

섹션 제목: “생애 주기 다이어그램”
sequenceDiagram
  participant Reader as 리더 스레드
  participant Retirer as 은퇴 스레드
  participant Tdes_R as 리더 디스크립터
  participant Tdes_W as 은퇴자 디스크립터
  participant Tab as tran::table

  Note over Tab: m_global_tranid = G<br/>m_min_active_tranid = G_min
  Reader->>Tdes_R: start_tran()
  Tdes_R->>Tab: load m_global_tranid → G
  Tdes_R->>Tdes_R: m_tranid = G
  Reader->>Reader: 노드 N 디레퍼런싱
  Retirer->>Tdes_W: retire_node(N)
  Tdes_W->>Tab: ++m_global_tranid → G+1
  Tdes_W->>Tdes_W: m_tranid = G+1
  Note over Tdes_W: 매 100번째 증가:<br/>compute_min_active_tranid()<br/>모든 디스크립터 스캔
  Tdes_W->>Tdes_W: N.m_retire_tranid = G+1
  Tdes_W->>Tdes_W: N을 은퇴 링에 append
  Tdes_W->>Tdes_W: m_retire_count++
  Note over Reader: ... N을 계속 사용 중 ...
  Reader->>Tdes_R: end_tran()
  Tdes_R->>Tdes_R: m_tranid = INVALID_TRANID
  Note over Tab: 다음 갱신:<br/>min_active가 G+1을 넘어 올라감
  Retirer->>Tdes_W: reclaim_retired_list()
  Tdes_W->>Tdes_W: head를 m_retire_tranid &lt; min_active 동안 순회
  Tdes_W->>Tdes_W: N.reclaim() (delete 또는 재활용)

Address marker — 포인터 마크 동반자

섹션 제목: “Address marker — 포인터 마크 동반자”

회수 프레임워크는 언제 회수할지를 푼다. Harris-Michael 삭제 프로토콜 은 노드를 논리적으로 삭제됐지만 아직 물리적으로 unlink되지 않은 상태로 표시할 방법이 필요하다. 추가 메모리를 할당해서는 안 된다. 표준 기법은 next 포인터의 최하위 비트에 마크를 두는 것이다. 실제 포인터는 적어도 2바이트 정렬 (CUBRID는 8바이트 정렬)이므로 최하위 비트 는 평소 0이다. CUBRID는 이를 lockfree::address_marker<T>로 인코딩한다.

// lockfree::address_marker<T> — src/base/lockfree_address_marker.hpp:31
template <class T>
class address_marker {
public:
  bool is_marked () const;
  T *get_address () const;            // 마크 제거
  T *get_address_no_strip () const;
  static T *set_adress_mark (T *addr);
  static T *strip_address_mark (T *addr);
  static bool is_address_marked (T *addr);
  static T *atomic_strip_address_mark (T *addr);
private:
  using convert_type = std::uint64_t;
  static const convert_type MARK = 0x1;
  // ...
  std::atomic<T *> m_addr;
};

구현은 데이터를 거의 가지지 않는다. 모든 정적 헬퍼가 포인터를 uint64_t로 캐스트하고, 마크 비트를 OR/AND-NOT한 뒤 다시 캐스트한다. 인스턴스 형 address_marker<T>는 std::atomic<T*>를 감싸므로 호출자 가 캐스트 없이 마크된 포인터를 store할 수 있다. 해시맵은 둘 다 쓴다. 엔트리 안의 마크된 next 포인터는 정적 헬퍼(set_adress_mark, strip_address_mark)로 다루고, 마크된 백버퍼 head는 인스턴스 address_marker<T>로 다룬다.

set_adress_mark(adress에 d가 한 개) 라는 오타에 주의. 모든 호출 지점에서 같은 오타로 쓰이고 있어 이제는 짐을 짊어진 이름이다.

Legacy LF_TRAN_*와의 공존

섹션 제목: “Legacy LF_TRAN_*와의 공존”

legacy 스택(src/base/lock_free.{h,c})은 같은 EBR 모양을 다른 이름으로 구현한다.

ModernLegacy
tran::system::assign_indexlf_tran_request_entry
tran::system::free_indexlf_tran_return_entry
tran::table::m_global_tranidLF_TRAN_SYSTEM::global_transaction_id
tran::table::m_min_active_tranidLF_TRAN_SYSTEM::min_active_transaction_id
MATI_REFRESH_INTERVAL = 100LF_TRAN_SYSTEM::mati_refresh_interval = 100
descriptor::start_tranlf_tran_start (entry, false)
descriptor::start_tran_and_increment_idlf_tran_start (entry, true)
descriptor::end_tranlf_tran_end (entry)
descriptor::retire_node(lf_freelist_retire에 인라인됨)
descriptor::m_retired_*LF_TRAN_ENTRY::retired_list (단일 연결 리스트)
compute_min_active_tranidlf_tran_compute_minimum_transaction_id
reclaimable_node(베이스 클래스 없음. void* 노드를 LF_ENTRY_DESCRIPTOR::of_local_next로 워크)

구조적 차이가 두 가지다.

  1. Legacy는 11개의 전역 인스턴스 LF_TRAN_SYSTEM을 쓴다 (spage_saving_Ts, obj_lock_res_Ts, …, dwb_slots_Ts). Modern은 전역이 없다. 모든 tran::table이 tran::system & 참조에서 생성된다.
  2. Legacy는 명시적 MEMORY_BARRIER() 매크로를 가진다 (lf_tran_start_with_mb / lf_tran_end_with_mb 헬퍼). Modern은 std::atomic의 seq_cst 기본값에 의존한다. 의도는 같다. 노드 디레퍼런싱 전에 디스크립터 쓰기를 공개하고, 전역 ID 증가 이후에 관찰. 그러나 modern 코드는 명시적 펜스 대신 타입 시스템으로 표현 한다.

두 스킴 모두 같은 EBR 불변식을 만족한다. 다리 cubthread::lockfree_hashmap 아래에서 도는 코드는 어느 쪽이 활성이든 정상 동작한다.

소스 코드 가이드

섹션 제목: “소스 코드 가이드”

lockfree_transaction_def.hpp

섹션 제목: “lockfree_transaction_def.hpp”

타입 별칭 둘뿐이다.

namespace lockfree { namespace tran {
  using index = size_t;            // 스레드별 디스크립터 인덱스
  using id = std::uint64_t;        // 단조 전역 tranid
}}

lockfree_transaction_system.{hpp,cpp}

섹션 제목: “lockfree_transaction_system.{hpp,cpp}”

인덱스 디스펜서. system::system(size_t) 생성자가 내부 bitmap을 크기 max_tran_count, ONE_CHUNK FULL_USAGE_RATIO 모드로 초기화 한다. assign_index()는 bitmap::get_entry()를 호출하고 free_index()는 bitmap::free_entry()를 호출한다. 시스템 클래스 자체에는 테이블별 상태가 없다. 비트맵을 감싸는 얇은 껍질이다.

lockfree_transaction_table.{hpp,cpp}

섹션 제목: “lockfree_transaction_table.{hpp,cpp}”

회수 테이블. table(system &) 생성자가 new descriptor[m_sys.get_max_transaction_count()]을 할당하고, 각 디스크립터를 워크하며 그 back-pointer를 설정한다 (m_all[i].set_table(*this)). 소멸자 delete[] m_all은 모든 디스 크립터의 소멸자가 자기 은퇴 링을 비웠음을 전제로 한다(디스크립터 소멸자가 !is_tran_started()를 단언하고 링을 워크하며 reclaim_retired_head를 호출한다).

get_new_global_tranid()이 은퇴 측 핫 패스다. ++m_global_tranid 이후 모듈러 경계에서 조건부로 compute_min_active_tranid().

lockfree_transaction_descriptor.{hpp,cpp}

섹션 제목: “lockfree_transaction_descriptor.{hpp,cpp}”

스레드별 상태. 메서드는 의도적으로 잘게 쪼개져 있다.

  • start_tran() — bump 없이 스냅샷. 리더용.
  • start_tran_and_increment_id() — 전역 bump. 은퇴자용. 그리고 신선한 에포크가 필요한 코드용 (예: hashmap::list_delete가 unlink CAS 이후에 부른다. 은퇴자의 에포크 가 어떤 동시 리더 스냅샷보다도 엄격히 크게 만들기 위해서다).
  • end_tran() — INVALID_TRANID로 리셋.
  • retire_node() — bump 후 append.
  • reclaim_retired_list() — 적격 접두사 워크.
  • save_reclaimable / pull_saved_reclaimable — 투기적 claim 핑퐁 용.

lockfree_transaction_reclaimable.hpp

섹션 제목: “lockfree_transaction_reclaimable.hpp”

은퇴 가능 노드의 베이스 클래스. 흥미로운 필드는 m_retired_next이며 protected이다. “may be repurposed by derived classes”라는 주석이 달려 있다. free list의 free_node가 이를 활용한다. 노드가 free list 의 available 리스트 위에 있으면 m_retired_next는 free list 링크, 디스크립터의 은퇴 링 위에 있으면 retire-ring 링크다. 두 역할은 절대 공존하지 않는다(노드는 한 번에 정확히 한 리스트 위에 있다). 그래서 오버로드가 안전하다.

m_retire_tranid는 private이고 friend descriptor만 쓴다.

lockfree_address_marker.hpp

섹션 제목: “lockfree_address_marker.hpp”

템플릿화된 헤더 전용. 정적 헬퍼는 stateless 캐스트다. 인스턴스 형은 std::atomic<T*>를 보유해서 호출자가 재로드 없이 am.is_marked()를 부를 수 있다. 정적 헬퍼 atomic_strip_address_mark(T*)는 임시 address_marker<T>를 박싱하고 즉시 strip한다. legacy 코드의 인라인 strip 매크로보다 방어적이다.

위치 힌트 (2026-05-07 기준)

섹션 제목: “위치 힌트 (2026-05-07 기준)”
심볼파일라인
tran::system::systemsrc/base/lockfree_transaction_system.cpp29
tran::system::assign_indexsrc/base/lockfree_transaction_system.cpp39
tran::system::free_indexsrc/base/lockfree_transaction_system.cpp51
tran::table::tablesrc/base/lockfree_transaction_table.cpp36
tran::table::get_descriptorsrc/base/lockfree_transaction_table.cpp54
tran::table::get_new_global_tranidsrc/base/lockfree_transaction_table.cpp73
tran::table::compute_min_active_tranidsrc/base/lockfree_transaction_table.cpp90
tran::table::get_min_active_tranidsrc/base/lockfree_transaction_table.cpp107
tran::descriptor::descriptorsrc/base/lockfree_transaction_descriptor.cpp32
tran::descriptor::~descriptorsrc/base/lockfree_transaction_descriptor.cpp45
tran::descriptor::retire_nodesrc/base/lockfree_transaction_descriptor.cpp65
tran::descriptor::start_transrc/base/lockfree_transaction_descriptor.cpp94
tran::descriptor::start_tran_and_increment_idsrc/base/lockfree_transaction_descriptor.cpp103
tran::descriptor::end_transrc/base/lockfree_transaction_descriptor.cpp119
tran::descriptor::reclaim_retired_listsrc/base/lockfree_transaction_descriptor.cpp133
tran::descriptor::reclaim_retired_headsrc/base/lockfree_transaction_descriptor.cpp154
tran::descriptor::save_reclaimablesrc/base/lockfree_transaction_descriptor.cpp170
tran::descriptor::pull_saved_reclaimablesrc/base/lockfree_transaction_descriptor.cpp178
tran::reclaimable_node (클래스)src/base/lockfree_transaction_reclaimable.hpp46
address_marker<T> (클래스)src/base/lockfree_address_marker.hpp31
lf_tran_start (legacy)src/base/lock_free.c413
lf_tran_end (legacy)src/base/lock_free.c446
lf_tran_compute_minimum_transaction_id (legacy)src/base/lock_free.c379
lf_tran_request_entry (legacy)src/base/lock_free.c281

소스 검증 (2026-05-07 기준)

섹션 제목: “소스 검증 (2026-05-07 기준)”

검증된 사실

섹션 제목: “검증된 사실”
  • MATI_REFRESH_INTERVAL은 정확히 100이며 legacy/modern이 같다. Legacy: LF_TRAN_SYSTEM::mati_refresh_interval = 100이 lf_tran_system_init(lock_free.c:236)에서 설정. Modern: lockfree::tran::table::MATI_REFRESH_INTERVAL = 100이 lockfree_transaction_table.hpp:78에 선언. 런타임 튜닝 불가.
  • INVALID_TRANID == numeric_limits<id>::max() — lockfree_transaction_descriptor.hpp:49에 선언되어 idle 센티넬로 쓰임. Legacy는 LF_NULL_TRANSACTION_ID == ULONG_MAX(lock_free.h:119) 로 같은 max-value 패턴.
  • Min-스캔은 모든 디스크립터를 무조건 워크한다. compute_min_active_tranid이 lockfree_transaction_table.cpp:90에서 0 .. m_sys. get_max_transaction_count()를 조기 종료 없이 순회. 헤더 주석은 부팅 시 모두 claim 가정 아래에서 의도적이라고 명시.
  • reclaim()은 가상이며 기본 delete this다. lockfree_transaction_reclaimable.hpp:57에 선언되어 있고, free list의 free_node::reclaim이 final 한정자로 오버라이드 (lockfree_freelist.hpp:523).
  • 디스크립터 소멸자는 은퇴 링을 워크한다. ~descriptor()이 lockfree_transaction_descriptor.cpp:45에서 while (m_retired_head != NULL) 루프를 돌며 reclaim_retired_head()를 부른다. 스레드가 은퇴 도중에 죽는다면 (CUBRID 수명 모델에서는 일어나지 말아야 함), 소멸자가 그래도 비운다.
  • 저장된 reclaimable은 단일 슬롯이다. descriptor::save_reclaimable이 lockfree_transaction_descriptor.cpp:170에서 m_saved_node == NULL을 단언. pull 없이 두 번 save하면 디버그 빌드에서 단언 실패.
  • address_marker<T>::MARK == 0x1 — lockfree_address_marker.hpp:36에 선언. 같은 비트 위치를 legacy ADDR_HAS_MARK / ADDR_WITH_MARK 매크로(lock_free.c:72-74)도 쓴다.

풀리지 않은 질문

섹션 제목: “풀리지 않은 질문”
  1. compute_min_active_tranid이 빈 디스크립터 슬롯을 건너뛰어야 하는가? 헤더 주석은 부팅 시 모두 claim 가정을 인정한다. 미래의 변경이 동적 인덱스 할당을 도입하면 스캔도 같이 바뀌어야 한다. 조사 경로: assign_index 호출 지점을 검색해 모두 부팅 시점에 도는지 확인.
  2. set_adress_mark 오타(d가 한 개)는 의도인가, 정리해야 하는가? 모든 호출 지점이 오타 표기를 쓰므로 이름 바꾸는 일은 코드베이스 전반의 일괄 작업이다. 가치는 낮다. 더 큰 락프리 리팩터링이 일어날 때 함께 정리할 후보로 남긴다.
  3. 약한 메모리 모델 타깃에서 seq_cst 기본값의 비용은? 측정 캠페인 이 없다. legacy 코드의 lf_tran_start_with_mb 매크로는 풀 배리어 의도를 시사하지만, modern 코드는 읽기 경로에서 acquire/release 가 충분한지 측정한 적이 없다.
  4. tran::table 바깥에서 노드를 은퇴시키며 delete this에 직접 기대는 자료구조가 있는가? 기본 reclaim()은 delete this다. 힙 소유가 아닌 저장소에 박힌 reclaimable_node(예: 배열 슬롯에 임베디드)를 은퇴시키는 코드 경로가 있다면, 기본 reclaim은 더블 프리다. 조사 경로: tran::reclaimable_node 파생 클래스를 grep해 각 오버라이드를 확인.
  5. 디스크립터의 m_did_incr 플래그가 여전히 의미가 있는가? start_tran_and_increment_id()에서 한 트랜잭션당 단일 bump를 보장하기 위해 쓰인다. free list의 claim()은 start_tran()(bump 없음)을 부르고, 해시맵의 list_delete는 promote_tran_force()(bump)를 부르는 상황에서, 플래그는 관찰 중과 은퇴 중 사이의 센티넬이다. 스트레스 테스트 아래에서 초점 잡힌 리뷰를 받을 만하다.

CUBRID 너머 — 비교 설계와 연구 프론티어

섹션 제목: “CUBRID 너머 — 비교 설계와 연구 프론티어”
  • 사용자 공간 RCU(liburcu) 통합. liburcu는 운영 등급 EBR이며 유예 기간 검출을 가진다. API(rcu_read_lock, rcu_read_unlock, synchronize_rcu, call_rcu)가 CUBRID의 start_tran/end_tran/retire_node에 거의 그대로 매핑된다. liburcu 도입은 시스템 의존성을 추가하는 대가로 lockfree::tran 코드 수백 줄을 줄일 수 있다.
  • DEBRA / IBR (Brown, ICDCS 2015). 디스크립터를 파티셔닝해 min-스캔 비용을 줄이는 더 빠른 EBR 변종. 고스레드 머신에서 CUBRID의 매-100 풀 스캔 비용과 비교할 만하다.
  • NBR+ (Singh et al., PPoPP 2021). 중립화(neutralization) 기반 회수. 접근당 에포크 발행을 OS 시그널 기반 quiescence 검출로 완전히 대체한다. 공격적이지만 읽기 중심 워크로드(CUBRID 해시맵 find가 retire를 압도적으로 능가)에 유망하다.
  • Hyaline (Nikolaev & Ravindran, PPoPP 2020). hazard-eras로 상수 시간 회수. EBR보다 더 타이트한 지연 한계 — 모든 은퇴 노드가 분할 상환 O(1) 안에 회수 가능 — 를 가지나 접근당 reference-counting 기계를 추가하는 대가가 있다.
  • 스레드별 은퇴 링을 전역 CPU별 샤드로 교체. 현재 디스크립터의 은퇴 링은 사적이다. 스레드별 인덱스 풀이 커지면 전체 은퇴 노드 메모리가 O(threads × pending-reclaims)이다. 스레드 affinity 기반 CPU별 샤드 풀이라면 스레드 수와 무관하게 한계를 잡을 수 있다.

출처

섹션 제목: “출처”
  • 소스 파일 (CUBRID 소스 트리, /data/hgryoo/references/cubrid/):
    • src/base/lockfree_transaction_def.hpp
    • src/base/lockfree_transaction_system.{hpp,cpp}
    • src/base/lockfree_transaction_table.{hpp,cpp}
    • src/base/lockfree_transaction_descriptor.{hpp,cpp}
    • src/base/lockfree_transaction_reclaimable.hpp
    • src/base/lockfree_address_marker.hpp
    • src/base/lock_free.h, src/base/lock_free.c (legacy 대응)
  • 인용한 교과서 챕터:
    • Herlihy & Shavit, The Art of Multiprocessor Programming, 9장 §Lock-Free Linked Lists (포인터 마크 비트 Harris-Michael delete), 10장 §Concurrent Hashing (split-ordered 체이닝 테이블), 7장 §Spin Locks and Contention (CAS 위험).
    • Williams, C++ Concurrency in Action, 5장 §“Memory ordering for atomic operations, 7장 §Designing lock-free concurrent data structures.”
  • 기반 논문:
    • Michael, M. M. “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects.” IEEE TPDS 15(8), 2004.
    • Fraser, K. Practical Lock-Freedom. Univ. of Cambridge Tech Report UCAM-CL-TR-579 (2004) — CUBRID 스킴이 따르는 epoch-based reclamation 형태의 출처.
    • McKenney, P. E., Slingwine, J. “Read-Copy Update: Using Execution History to Solve Concurrency Problems.” PDCS 1998.
    • Brown, T. A. “Reclaiming Memory for Lock-Free Data Structures.” PODC 2015.
  • 본 저장소의 자매 분석서:
    • cubrid-lockfree-overview.md — 우산 문서. 두 세대 지도를 찾으려면 여기로.
    • cubrid-lockfree-hashmap.md — 회수 프레임워크의 가장 큰 소비자.
    • cubrid-lockfree-freelist.md — 두 번째 소비자.
    • cubrid-lockfree-bitmap.md — tran::system이 인덱스 할당에 내부적으로 사용.