(KO) CUBRID 락프리 기본 자료구조 — 개요, 두 세대, 회수 척추

목차

• 학술적 배경
• DBMS 공통 설계 패턴
• CUBRID의 구현
• 소스 코드 가이드
• 소스 검증 (2026-05-07 기준)
• CUBRID 너머 — 비교 설계와 연구 프론티어
• 출처

학술적 배경

lock-free 자료구조의 정의는 한 가지 운영적 조건이다. 임의의 시점에 최소 한 개의 스레드가 유한한 단계 안에 진행을 보장받아야 한다. 뮤텍스 위에서 스레드를 막는 것은 금지되는데, 이는 잠금 보유자가 스왑 아웃되면 그 동안 모든 스레드가 멈춰버린다는 점이 문제이기 때문이다. 경쟁 중인 워드 위에서 CAS 루프를 도는 것은 허용된다. 워드를 한 칸 앞으로 옮긴 스레드는 진행을 한 셈이며, 비록 경쟁자들이 진척이 없더라도 시스템 전체로는 진행이 일어났 기 때문이다. The Art of Multiprocessor Programming (Herlihy & Shavit, 3장 §Progress Conditions)은 이 진행 조건을 세 단계로 나눈다. wait-free는 모든 스레드가 유한 단계 안에 끝난다는 강한 조건, lock-free는 적어도 한 스레드가 끝난다는 조건, obstruction-free는 단독으로 실행되면 끝난다는 가장 약한 조건이다. 운영 환경 코드의 절대다수는 lock-free 수준에서 멈추는데, wait-free까지 끌어올리는 비용이 캐시 트래픽 측면에서 오히려 지연을 늘리는 경우가 많기 때문이다.

락프리 설계가 합쳐 만들어내는 하드웨어 원시 연산은 결국 어떤 형태의 compare-and-swap이다. x86에서는 CMPXCHG와 16바이트 변형 CMPXCHG16B, ARM에서는 load-link / store-conditional 쌍 (LDREX/STREX, ARMv8.1+의 LSE 어토믹) 으로 제공된다. C++11에서는 std::atomic<T>::compare_exchange_weak/ strong 으로 추상화되어 있다. CAS는 한 워드 단위의 원자적 검사-갱신을 제공하며, Treiber 스택, Michael–Scott 큐, Harris 연결 리스트, split- ordered 해시, RCU 리더 같은 다른 모든 자료구조는 결국 자료구조의 불변식을 CAS 대상 워드의 값으로 인코딩한 결과물이다.

이론과 실제 운영 코드 사이의 간극을 만드는 문제는 세 가지가 있고, 본 분석서가 다루는 CUBRID 락프리 파일들은 모두 이 셋 중 일부의 조합을 풀기 위해 존재한다.

1. ABA 문제

CAS가 어떤 값 A를 읽고, 다른 스레드가 그 값을 B로 바꿨다가 다시 A 로 되돌리면, CAS는 변화가 없었던 것처럼 성공한다. A가 가리키던 실제 객체는 그 사이에 파괴되고 재생성됐는데도 그렇다. 가장 자주 인용되는 재현 시나리오는 Treiber 스택이다. 스레드 1이 top → A를 읽고 top을 A에서 A->next로 CAS 갱신하려고 한다. 스레드 2가 A를 pop하고 B를 pop한 뒤 둘 다 free하고, 같은 주소에 새 노드 A'를 할당한 뒤 A'->next가 엉뚱한 곳을 가리키게 push한다. 이제 top → A'다. 스레드 1 이 깨어나면 top이 다시 A처럼 보이므로 CAS가 성공하고, 그 결과 top 은 이미 해제된 메모리를 가리키는 댕글링 포인터가 된다. 고전적 출처는 Treiber의 IBM Almaden 보고서(1986)와 Michael의 Hazard Pointers 논문 (IEEE TPDS, 2004)이다.

2. 안전한 메모리 회수 (Safe Memory Reclamation)

ABA 문제는 더 일반적인 문제의 한 사례다. 락프리 자료구조에서 막 은퇴(retire)된 노드를 언제 할당자에게 돌려보내도 안전한가? 너무 일찍 free하면 ABA와 use-after-free가 일어난다. 너무 늦게 free하면 메모리 누수가 된다. 실제 운영 시스템에는 에포크(epoch) — 일종의 단조 증가 시계 — 와 “에포크 E 이전에 은퇴된 노드를 가리키는 스레드가 더 이상 없다”를 판정하는 메커니즘이 필요하다. 주류 기법은 네 가지다.

기법	동작 원리	읽기 경로 비용	회수 비용
Hazard pointers (Michael 2004)	각 스레드가 현재 디레퍼런싱 중인 포인터 K개를 공개 슬롯에 발행	접근당 원자 store O(1)	회수자가 모든 스레드의 위험 슬롯을 스캔
Epoch-Based Reclamation / EBR (Fraser 2004)	각 스레드가 진입/이탈 시 에포크에 등록·해제, 회수자는 모든 스레드가 경계를 넘을 때까지 대기	임계 구역당 O(1)	주기적인 전역 에포크 진행
RCU (read-copy-update; McKenney 2001)	리더는 막지 않음, 라이터는 모든 리더가 통과할 유예 기간을 기다림	사실상 0	유예 기간 검출 비용
QSBR (quiescent-state-based)	각 스레드가 주기적으로 정적 상태를 보고하며, 은퇴 이후 모든 스레드가 한 번씩 보고하기 전에는 free 금지	핫 패스에서 0	회수 시 스레드별 카운터 한 번 검사

CUBRID는 EBR 계열을 채택했다. 본 분석서들이 §CUBRID의 구현에서 다루 는 트랜잭션 기반 회수는 사실상 EBR을 데이터베이스 어휘로 다시 부른 것이다. 그리고 이 회수 메커니즘은 lockfree::tran 네임스페이스에 한 번 구현되며, 다른 모든 락프리 자료구조 (hashmap, freelist)는 여기에 플러그인된다.

3. 메모리 순서

std::atomic<T> 연산은 메모리 순서 인자(memory_order_relaxed, acquire, release, acq_rel, seq_cst)를 받는다. 잘못된 순서를 고 르면 x86에서는 워드 크기 load/store가 거의 순차적 일관성을 보장 하기 때문에 결함이 드러나지 않을 수 있지만, ARM, POWER, RISC-V 같은 약한 메모리 모델 아키텍처에서는 재정렬되면서 결함으로 나타난다. 교과 서 정설은 C++ Concurrency in Action (Williams) 5장이다. 두 가지 핵심 패턴이 있다는 점에 주목하자.

• acquire-release 동기화. 워드 W에 대한 release store는 같은 W에 대한 acquire load와 짝을 이룬다. load 쪽 스레드는 release 스레드의 release 이전에 sequenced-before였던 모든 store를 관찰할 수 있다. 락프리 큐의 컨슈머가 프로듀서의 페이로드 쓰기를 관찰하는 방식이 바로 이것이다.
• read-modify-write (RMW) 어토믹. 성공한 compare_exchange는 (호출 시 memory_order_acq_rel 이상이면) acquire이자 release 역할을 한다. 라이터의 이전 store들을 공개하고 선행 라이터의 것을 획득하는 결합점(join point)이 된다.

CUBRID의 락프리 코드는 std::atomic<T> 위에서 압도적으로 기본값인 seq_cst 순서를 사용한다. 보수적이지만 CUBRID가 지원하는 모든 타깃 아키텍처에서 안전하다. acquire/release로 조이는 것은 알려진 최적화 기회로 분류되며 현재의 불변식은 아니다.

4. 세 가지 구조 패턴

CUBRID에서 락프리 빌딩 블록은 결국 다음 세 가지 교과서적 형태 중 하나다.

• 락프리 연결 리스트 (Harris 2001 / Michael 2002). 삽입은 새 노드를 체인에 끼워넣는 단일 CAS다. 삭제는 두 단계 CAS 프로토콜로 일어난다. 먼저 노드의 next 포인터에 마크 비트를 세워 논리적 삭제를 알리 고(동시 순회자가 이 노드를 건너뛰도록), 그다음 선행자의 next를 CAS 로 갱신해 물리적 unlink를 한다. 읽기 쪽은 마크를 보면 unlink를 도와주거나 노드가 없는 것으로 간주한다. CUBRID 해시맵의 체인이 바로 Harris-Michael 리스트이며, 마크 비트는 next 포인터의 최하위 비트 이다. 이 인코딩은 lockfree::address_marker가 담당한다.
• 락프리 FIFO 큐 (Michael & Scott 1996). 두 커서 변종 — 프로듀서 커서와 컨슈머 커서가 각자 어토믹에 올라간다. CUBRID의 lockfree::circular_queue는 고정 용량 한정(bounded) 변종으로, 형태상 MS 큐보다 LMAX Disruptor에 더 가깝다. 커서 시퀀스 번호와 슬롯 단위 블록 플래그를 함께 사용한다.
• 락프리 split-ordered 해시 (Shalev & Shavit 2003). 해시 테이블이 하나의 재귀적 락프리 연결 리스트가 되고 버킷 포인터는 그 리스트로 들어가는 단축 경로 역할을 한다. 리사이즈는 새 버킷 포인터를 끼워 넣는 것만으로 끝나서 데이터 자체를 다시 잇지 않아도 된다. CUBRID는 split-ordered를 사용하지 않는다. 해시 테이블은 고정 버킷 수의 체이닝 방식이며, 각 버킷이 Harris-Michael 리스트의 머리를 가리킨다. 리사이즈는 락프리가 아니다. 리사이즈와 비슷한 연산이라고는 clear() 뿐인데, 이는 버킷 배열을 백버퍼와 원자적으로 스왑하는 방식이다.

이 세 패턴이 다음 섹션이 채워나갈 설계 공간의 윤곽이다.

DBMS 공통 설계 패턴

현대의 모든 DBMS는 락프리 측면에서 세 가지 책임을 짊어진다. 스레드 간 큐(레이어 사이에 작업을 넘기는 producer-consumer 랑데부), 공유 연관 테이블(어떤 식별자로 키잉되는 페이지 버퍼, 락 테이블, 세션 캐시), 그리고 스레드 단위 free list(트랜잭션 사적 빠른 경로가 전역 할당자에 부딪히지 않도록). 모양은 수렴한다.

스레드 간 큐

표준적인 역할은 다음과 같다. 데몬 스레드가 큐를 채우고, 워커 스레드가 이를 비운다(또는 그 반대). 변종은 다음과 같다.

• 고정 용량 MPMC 링 버퍼. 2의 거듭제곱 용량, 두 커서 어토믹, 슬롯 단위 시퀀스 번호. 가장 가까운 운영 사례는 LMAX Disruptor다. InnoDB의 redo 로그 라이터 링, PostgreSQL의 autovacuum 워커 큐, 그리고 CUBRID의 lockfree::circular_queue(vacuum, 페이지 버퍼 victim 핸드오프, CDC log-info 전달용)에 사용된다.
• 무한 Michael–Scott 큐. 두 어토믹 포인터 head와 tail이 있고, enqueue마다 노드 할당, dequeue마다 free. 의미론은 깔끔하지만 메모리가 무한이고 연산마다 할당이 필수다.
• CPU별 SPMC / MPSC 큐. CPU/스레드 그룹마다 큐를 두고, 로컬이 비면 훔쳐온다(work-stealing). CUBRID는 락프리 네임스페이스에서 이 패턴을 쓰지 않는다.

공유 연관 테이블

모든 DBMS에는 락 테이블(잠금 대상 자원당 엔트리 하나), 페이지 버퍼 해시((volid, pageid)로 키잉된 메모리 상주 페이지 하나당 엔트리 하나), 세션 캐시(클라이언트 연결당 엔트리 하나), 그리고 문장 캐시 (XASL, 쿼리 플랜)가 있다. 이들은 모두 높은 경합 아래에서 동시 insert / find / erase가 가능해야 한다.

공유되는 엔지니어링 패턴은 다음과 같다.

1. 고정 크기 버킷 배열, hash(key) % size → bucket.
2. 각 버킷이 락프리 연결 리스트의 머리.
3. 리스트 노드는 페이로드와 next 포인터를 가지며, 최하위 비트는 삭제 마크로 예약된다.
4. 삽입은 리스트 끝까지 걷고, 버킷 또는 tail의 next를 NULL에서 새 노드로 CAS 한다.
5. 삭제는 victim의 next를 CAS 마크 → 선행자에서 victim을 CAS unlink.
6. 회수는 epoch / hazard-pointer / RCU / 트랜잭션 방식 중 하나로 지연된다.

CUBRID의 lockfree::hashmap은 정확히 이 모양인데, 한 가지 특별한 선택을 한다. 엔트리 단위 pthread 뮤텍스(선택적). 어떤 엔트리 디스 크립터가 using_mutex = 1을 선언하면, 해시맵은 find/insert/delete 도중 엔트리 뮤텍스를 잡고, 트랜잭션은 버킷 체인만 동시 회수로부터 보호하 며 페이로드 변경은 뮤텍스가 보호한다. using_mutex = 0이면 트랜잭션 자체가 유일한 보호 수단이며, 페이로드 읽기는 트랜잭션 윈도우 안에서 끝나야 한다.

스레드 단위 free list

매 삽입마다 새 리스트 노드를 할당하고 매 삭제마다 free 한다면, 아무리 좋은 할당자라도 malloc 병목이 된다. DBMS의 전형적인 답은 자료구조 단위로 타입이 정해진 노드의 free list이다. 엔트리가 버킷 체인에서 은퇴하면 free()로 가지 않고, 그 자료구조가 소유한 free list로 들어간 다. 이후의 삽입은 new를 호출하기 전에 free list에서 pop을 한다. 이것 이 lockfree::freelist<T>의 역할이다.

구현마다 부딪히는 두 가지 설계상의 결단이 있다.

• 단일 available 리스트의 경합 — 가장 최근 pop 대상의 캐시 라인이 코어 사이를 튕긴다. 표준적인 처방은 back-buffer 블록을 옆에 들고 있다가 available 리스트가 비면 통째로 갈아끼우는 방식이다. 새 블록을 할당하는 느린 경로가 단일 CAS 스왑 뒤에 숨는다는 점이 핵심이다. CUBRID free list는 정확히 이 패턴을 따른다.
• head 포인터의 ABA — pop이 head를 읽고 head->next를 계산한 뒤 head를 head->next로 CAS 스왑한다. 그 사이에 형제 스레드가 같은 head를 pop하고, 또 다른 스레드가 그것을 다시 push한다면, 저장된 head->next는 이미 낡은 값이다. CUBRID free list는 pop_from_available() (lockfree_freelist.hpp) 안에 이 위험을 명시적 으로 적어두었으며, 태그된 포인터 대신 트랜잭션 시스템에 기대어 윈도우 를 좁힌다.

일반화된 트랜잭션 기반 회수

네 번째 공유 부분 — 그리고 CUBRID가 가장 깔끔하게 자기 자신의 클래스로 끄집어낸 부분 — 은 스레드 활동에 묶인 지연 회수다. 락프리 자료구조 의 모든 소비자가 자기 free list를 가지더라도, 은퇴된 노드를 물리적으로 재사용해도 되는 시점은 누군가 결정해야 한다. 공유되는 템플릿은 다음과 같다.

1. 자료구조마다 한 개의 tranid 카운터. 모든 은퇴와 모든 “이제부터 읽을 거다” 이벤트가 이 카운터에서 스냅샷을 뜬다.
2. 자료구조마다, 그리고 스레드마다 디스크립터 한 개. 스레드가 마지막 으로 가져온 tranid와 내가 은퇴시켰지만 아직 회수 불가능한 노드 리스트를 들고 있다.
3. 모든 스레드 간 min(active_tranid)의 주기적 계산.
4. tranid = X로 은퇴된 노드는 min_active_tranid > X가 되는 즉시 회수 가능하다.

이 템플릿은 Linux 커널의 RCU(per-CPU 카운터로 read-side 임계 구역을 열고 닫는 것 + 전역 카운터 추적으로 유예 기간 검출)와 같은 모양이며, 스코프가 시스템 전역이 아니라 자료구조별로 좁아진 변종이다. CUBRID는 이를 lockfree::tran 패밀리로 일반화하고, 락프리 자료구조마다 자기 tran::table을 소유하게 한다.

학술 ↔ CUBRID 매핑

개념	CUBRID 이름 (legacy)	CUBRID 이름 (modern)
자료구조별 회수 에포크	LF_TRAN_SYSTEM::global_transaction_id	lockfree::tran::table::m_global_tranid
스레드별 reader 브래킷	lf_tran_start / lf_tran_end	descriptor::start_tran / end_tran
스레드별 은퇴 리스트	LF_TRAN_ENTRY::retired_list	descriptor::m_retired_head/tail
최소 활성 에포크 스캔	lf_tran_compute_minimum_transaction_id	table::compute_min_active_tranid
갱신 주기	LF_TRAN_SYSTEM::mati_refresh_interval = 100	MATI_REFRESH_INTERVAL = 100
스레드별 인덱스 할당기	LF_TRAN_SYSTEM::lf_bitmap (LF_BITMAP)	tran::system::m_tran_idx_map (bitmap)
포인터 마크 비트	ADDR_HAS_MARK / ADDR_WITH_MARK 매크로	lockfree::address_marker<T> 템플릿
고정 용량 MPMC 큐	없음 (C++로 처음 도입)	lockfree::circular_queue<T>
타입 단위 free list	LF_FREELIST	lockfree::freelist<T>
해시 테이블	LF_HASH_TABLE / lf_hash_table_cpp<K,T>	lockfree::hashmap<K,T>
해시 디스패치 래퍼	(lf_hash_*에 통합되어 있었음)	cubthread::lockfree_hashmap<K,T>
비트맵 할당기	LF_BITMAP	lockfree::bitmap (같은 클래스, 두 이름)

CUBRID의 구현

두 세대, 한 엔진, 토글 한 개

CUBRID 락프리 네임스페이스는 두 개의 완전한 구현이 공존한다는 점이 가장 큰 특징이다.

• Legacy C — src/base/lock_free.{h,c}. 원본 패밀리로, 2020년 훨씬 전에 출시되었다. 절차적이고 포인터 테이블 기반이며, 소비자별로 전역 인스턴스화된 LF_TRAN_SYSTEM(obj_lock_res_Ts, sessions_Ts, xcache_Ts 등)을 사용한다. 자료구조는 LF_HASH_TABLE, LF_FREELIST, 그리고 lf_io_list_*(insert-only 리스트), lf_stack_*(Treiber 스택), lf_list_*(Harris-Michael 원시 함수)이다. C++ shim lf_hash_table_cpp<K,T>(같은 헤더에 있음)이 C 함수들을 타입드 클래스 뒤로 감싼다.
• Modern C++ — src/base/lockfree_*.{hpp,cpp}. C++17 현대화의 일부 로 재설계된 결과물이다. 템플릿화되어 있고, 네임스페이스 스코프 (lockfree::*)이며, 회수가 lockfree::tran::*으로 떼어져 나왔고, address_marker<T>가 매크로 패밀리를 대체한다. circular_queue<T>는 새 원시 자료구조로 도입되었고, bitmap은 legacy typedef (LF_BITMAP)와 modern 이름을 모두 노출한 채로 이식되었다. 새 해시맵 은 각자 자기 tran::table을 소유하며, 전역 인스턴스화되는 회수 시스템은 없다.

두 세대가 공존하는 이유는 마이그레이션이 호출 지점마다 opt-in으로 이루어지기 때문이다. 다리는 src/thread/thread_lockfree_hash_map.hpp의 cubthread::lockfree_hashmap<K,T>에 있다. 이 클래스는 legacy의 lf_hash_table_cpp<K,T>와 modern의 lockfree::hashmap<K,T>를 모두 들고 있고, m_type ∈ {OLD, NEW, UNKNOWN} 필드로 어느 쪽으로 갈지를 결정한다. 결정은 init() 시점에 시스템 파라미터 PRM_ID_ENABLE_NEW_LFHASH를 보고 일어난다.

// cubthread::lockfree_hashmap::init — src/thread/thread_lockfree_hash_map.hpp
void init (lf_tran_system &transys, int entry_idx, int hash_size,
           int freelist_block_size, int freelist_block_count, lf_entry_descriptor &edesc)
{
  if (prm_get_bool_value (PRM_ID_ENABLE_NEW_LFHASH))
    init_as_new (get_thread_entry_lftransys (), ...);
  else
    init_as_old (transys, hash_size, ...);
}

운영적으로 보면, 오늘날의 CUBRID 서버는 enable_new_lfhash가 켜져 있지 않으면 여전히 legacy 경로를 기본값으로 사용한다. 새 경로가 권장되는 방향이며, legacy 경로는 위험 완화와 아직 마이그레이션 안 된 호출 지점 때문에 남아 있다.

설계 분리는 의도적이다. cubthread::lockfree_hashmap의 모든 소비자 (락 매니저의 자원 / 엔트리 테이블, 세션 테이블, XASL 캐시, FP 캐시, slotted-page saving, 카탈로그, global-unique-stats, hfid 테이블, DWB 슬롯 테이블)는 토글을 공짜로 받는다. 그 외 다른 소비자(vacuum의 circular queue, 페이지 버퍼의 victim 큐, CDC의 log-info 큐)는 C++ 전용 이며, 무조건 modern 스택 위에 올라가 있다.

회수 척추

modern 스택은 단일한 회수 원시 자료구조 위에 세워져 있고, 다른 모든 락프리 자료구조가 여기에 플러그인된다. 세 클래스로 이루어진다.

// lockfree::tran::system — src/base/lockfree_transaction_system.hpp
class system {
  size_t m_max_tran_per_table;  // 한 테이블이 수용해야 하는 동시 스레드 수
  bitmap m_tran_idx_map;        // 인덱스 할당기 (스레드마다 한 개)
  index assign_index ();
  void  free_index (index idx);
};

// lockfree::tran::table — src/base/lockfree_transaction_table.hpp
class table {
  system &m_sys;
  descriptor *m_all;            // 할당된 인덱스마다 디스크립터 한 개
  std::atomic<id> m_global_tranid;
  std::atomic<id> m_min_active_tranid;
  static const id MATI_REFRESH_INTERVAL = 100;
  // ...
};

// lockfree::tran::descriptor — src/base/lockfree_transaction_descriptor.hpp
class descriptor {
  table *m_table;
  id m_tranid;                  // 트랜잭션 미시작이면 INVALID_TRANID
  reclaimable_node *m_retired_head, *m_retired_tail;
  void start_tran ();
  void start_tran_and_increment_id ();
  void end_tran ();
  void retire_node (reclaimable_node &);
  void reclaim_retired_list ();
  // ...
};

프로토콜은 다음과 같다. 스레드는 자료구조 안의 어떤 노드를 만지기 전에 descriptor::start_tran()을 부르고, 작업이 끝나면 end_tran()을 부른다. 은퇴는 전역 카운터를 한 칸 올리고, 은퇴된 노드를 호출자 스레드의 디스크립터-단위 리스트 끝에 매단다. 주기적으로(매 MATI_REFRESH_INTERVAL = 100번째 은퇴마다) 테이블이 디스크립터들을 순회하며 min(active_tranid)를 다시 계산한다. 자기 tranid가 지금의 min_active_tranid보다 엄격히 작은 은퇴 노드는 회수 가능하다.

이 메커니즘은 cubrid-lockfree-transaction.md에서 자세히 다룬다. 본 개요에서는 다음 사항만 알면 된다.

• 모든 락프리 자료구조 (hashmap, freelist, 그리고 포인터 형태로 은퇴되는 노드가 없으니 회수가 필요 없는 circular_queue만 예외)는 자기 tran::table을 소유한다. 전역 회수 그래프는 없다.
• 락프리 자료구조를 만질 수 있는 모든 스레드는 시스템의 bitmap에서 tran::index를 받아 그 스레드의 수명 동안 보유한다.
• 디스크립터 링의 크기는 동시 스레드 수 (max_transaction_count)로 정해지며, 은퇴 발생 빈도와는 무관하다. 은퇴 비용은 디스크립터 리스트에서 O(1)이며, 주기적 min-스캔은 O(N_threads)이다.

포인터 마킹 — address_marker<T>

Harris-Michael 삭제 프로토콜은 노드가 논리적으로 삭제되었지만 아직 물리적으로 unlink 되지 않은 상태임을 추가 메모리를 쓰지 않고 표시할 방법이 필요하다. 표준적인 기법은 플래그를 포인터 자체의 최하위 비트에 넣는 것이다. 실제 포인터는 최소 2바이트 정렬이 보장되므로(CUBRID의 경우 포인터 형태의 락프리 노드는 8바이트 정렬), 최하위 비트는 평소엔 0이다. legacy의 ADDR_HAS_MARK / ADDR_WITH_MARK / ADDR_STRIP_MARK 매크로(lock_free.c)는 이를 raw 캐스트로 처리한다. modern의 lockfree::address_marker<T> 템플릿(lockfree_address_marker.hpp)은 타입 안전한 정적 헬퍼 set_adress_mark / strip_address_mark / atomic_strip_address_mark와, std::atomic<T*>를 감싸는 인스턴스 형 address_marker<T>를 함께 제공한다.

두 표현은 바이트 호환이다. 같은 비트 위치에 같은 비트를 인코딩하므로, 마이그레이션 도중 코드 경로 사이를 이동하는 노드도 안정적인 표현을 유지한다.

스레드별 인덱스 할당 — bitmap

두 세대 모두 디스크립터 / 엔트리 조회용으로 안정적인 스레드별 인덱스 를 할당할 수단이 필요하다. lockfree::bitmap이 그 할당기다. 청크 배열은 std::atomic<unsigned int> 워드들이고, 각 비트가 하나의 슬롯 이다. get_entry()는 start_idx 카운터를 회전시키며(SERVER_MODE에서 는 라운드로빈, 클라이언트 모드에서는 마지막 할당) 빈 비트가 있는 청크를 찾고, CAS로 비트를 뒤집는다. free_entry()는 비트를 지운다. 두 모드(ONE_CHUNK — 반드시 성공해야 하는 트랜잭션 시스템 같은 용도, LIST_OF_CHUNKS — 사용량 임계치가 있는 컨텍스트용)는 chunking_style로 인코딩된다. 자세한 내용은 cubrid-lockfree-bitmap.md를 참고.

해시 맵 구조

lockfree::hashmap<K,T>로 만든 모든 modern CUBRID 해시 테이블은 여섯 부분으로 구성된다.

1. 버킷 배열 T **m_buckets[m_size]. 각 엔트리가 Harris-Michael 체인의 머리.
2. 백버퍼 T **m_backbuffer[m_size](마크된 NULL 포인터로 채워져 있음). clear() 연산이 사용한다. 라이브 배열을 백버퍼와 원자적으로 스왑한 뒤, 옛 배열을 순회하며 모든 엔트리를 free list로 은퇴시킨다.
3. 테이블별 free list(타입드 엔트리; freelist<freelist_node_data>이며 freelist_node_data는 T m_entry 와 on_reclaim에 필요한 lf_entry_descriptor *m_edesc를 들고 있다).
4. 테이블별 tran::table, free list가 소유.
5. lf_entry_descriptor — 오프셋과 콜백(f_hash, f_key_cmp, f_key_copy, f_init, f_uninit, f_duplicate, using_mutex, of_* 필드 오프셋)을 담는 디스크립터. legacy와 공유하는 유일한 타입.
6. 메서드별 통계 링(atomic_counter_timer_stat). find/insert/erase/unlock/clear/iter/claim/retire별로 분리되며, activate_stats()로 켤 수 있다.

타입 T와 키 포인터의 상호작용은 멤버 접근이 아니라 바이트 오프셋 으로 이루어진다. 디스크립터가 of_next, of_key, of_mutex, of_del_tran_id(legacy 전용)를 선언하면, 해시맵은 T* 형태의 필드를 (char*)p + offset 캐스팅으로 읽는다. 이것이 lf_entry_descriptor가 다리 역할을 할 수 있는 이유다. 같은 디스크립터 하나가 legacy C 경로와 modern C++ 경로 둘 다를 같은 오프셋으로 운전한다.

자세한 내용은 cubrid-lockfree-hashmap.md.

고정 용량 MPMC 큐 — circular_queue<T>

세 번째 구조 조각은 고정 용량 multi-producer multi-consumer 큐다. 구현은 2의 거듭제곱 슬롯 배열에 두 커서 어토믹(m_produce_cursor, m_consume_cursor)과 슬롯별 블록 플래그 워드(m_blocked_cursors[N])를 얹은 형태다. 프로듀서는 슬롯을 CAS로 획득하고, 페이로드를 복사한 뒤, 슬롯을 unblock한다. 컨슈머는 슬롯이 unblocked 됐는지 감지한 뒤 페이로드를 복사하고, 컨슈머 커서를 CAS로 한 칸 올린다. 구현은 lockfree_circular_queue.hpp 헤더 안에 전부 들어 있다(스텁 외에는 .cpp가 없다). 자세한 내용은 cubrid-lockfree-circular-queue.md.

이 큐는 무조건 modern 스택 위에 있다. 사용처는 다음과 같다.

• 페이지 버퍼(src/storage/page_buffer.c) — victim을 기다리는 fixer를 위한 waiter_threads_high_priority, waiter_threads_low_priority, flush 후 처리를 위한 flushed_bcbs, LRU 파티션 사이의 victim 핸드오프를 위한 private_lrus_with_victims, big_private_lrus_with_victims, shared_lrus_with_victims.
• Vacuum(src/query/vacuum.c) — 로그 플러시 데몬에서 vacuum 워커로 로그 블록을 디스패치하는 vacuum_Block_data_buffer, 완료 통지를 되돌려 보내는 vacuum_Finished_job_queue.
• CDC(src/transaction/log_manager.c) — CDC 로그 정보 전달용 cdc_Gl.loginfo_queue.

자료구조별 free list — freelist<T>

네 번째 조각은 타입드 free list다. lockfree::freelist<T>는 tran::system &을 받아 자기 tran::table을 만든다. available 리스트 의 머리 한 개와, available이 비면 늦지 않게 한 블록을 갈아끼우는 백버퍼 한 개를 유지한다. 항목은 freelist<T>::free_node 타입이며, tran::reclaimable_node를 상속하므로 은퇴가 회수 척추로 곧장 연결된다. T에 대한 계약은 on_reclaim() 메서드를 노출하는 것이다. free list가 노드를 은퇴 상태에서 회수됨 상태로 옮길 때 이 메서드 를 부른다. 타입별 정리(예: freelist_node_data::on_reclaim이 lf_entry_descriptor::f_uninit 콜백을 호출)가 여기서 일어난다.

자세한 내용은 cubrid-lockfree-freelist.md.

소비자 지도

다음은 인-엔진 소비자의 비망목적 목록이다. 각 항목이 어느 세대에 묶여 있는지를 함께 표시했다.

소비자	파일	세대
오브젝트 락 자원 테이블	src/transaction/lock_manager.c	토글 (legacy obj_lock_res_Ts)
오브젝트 락 엔트리 테이블	src/transaction/lock_manager.c	토글 (legacy obj_lock_ent_Ts)
세션 테이블	src/session/session.c	토글 (legacy sessions_Ts)
XASL 캐시	src/query/xasl_cache.c	토글 (legacy xcache_Ts)
필터 술어 캐시	src/query/filter_pred_cache.c	토글 (legacy fpcache_Ts)
Slotted-page saving	src/storage/slotted_page.c	토글 (legacy spage_saving_Ts)
시스템 카탈로그	src/storage/system_catalog.c	토글 (legacy catalog_Ts)
Global unique stats	src/storage/btree.c (log_manager 경유)	토글 (legacy global_unique_stats_Ts)
HFID 테이블	src/storage/heap_file.c	토글 (legacy hfid_table_Ts)
DWB 슬롯 테이블	src/storage/double_write_buffer.cpp	토글 (legacy dwb_slots_Ts)
Free-sort-list	(legacy 전용)	legacy (free_sort_list_Ts)
Vacuum 블록 데이터 버퍼	src/query/vacuum.c	신형 전용 (circular_queue)
Vacuum 완료 작업 큐	src/query/vacuum.c	신형 전용 (circular_queue)
페이지 버퍼 victim/waiter 큐	src/storage/page_buffer.c	신형 전용 (circular_queue)
CDC log-info 큐	src/transaction/log_manager.c	신형 전용 (circular_queue)
스레드별 lf_tran_entry 맵	src/thread/thread_manager.cpp	둘 다 (legacy는 lf_tran_request_entry, modern은 lockfree::tran::system)

컴포넌트 개요

flowchart LR
  subgraph LegacyC["Legacy C (src/base/lock_free.{h,c})"]
    LFTS["LF_TRAN_SYSTEM<br/>소비자별 (전역 10개)"]
    LFFL["LF_FREELIST"]
    LFHT["LF_HASH_TABLE"]
    LFTS --> LFFL --> LFHT
    LFLI["lf_list_*<br/>Harris-Michael"]
    LFHT --> LFLI
    LFCPP["lf_hash_table_cpp&lt;K,T&gt;"]
    LFCPP --> LFHT
    LFCPP --> LFFL
  end

  subgraph ModernCpp["Modern C++ (src/base/lockfree_*)"]
    TS["lockfree::tran::system<br/>(bitmap 보유)"]
    TT["lockfree::tran::table"]
    TD["lockfree::tran::descriptor[]"]
    TS --> TT
    TT --> TD
    BM["lockfree::bitmap"]
    AM["lockfree::address_marker&lt;T&gt;"]
    FL["lockfree::freelist&lt;T&gt;"]
    HM["lockfree::hashmap&lt;K,T&gt;"]
    CQ["lockfree::circular_queue&lt;T&gt;"]
    TS --> BM
    FL --> TT
    HM --> FL
    HM --> AM
  end

  Bridge["cubthread::lockfree_hashmap&lt;K,T&gt;<br/>m_type = OLD or NEW"]
  Bridge --> LFCPP
  Bridge --> HM

  PRM["PRM_ID_ENABLE_NEW_LFHASH"]
  PRM --> Bridge

메모리 순서 자세

modern 스택의 모든 std::atomic 접근은 별다른 명시가 없으면 기본값 memory_order_seq_cst를 사용한다. 명시적 compare_exchange_weak/strong 이 쓰이는 곳도 마찬가지(x86에서는 acq_rel 기본, 전체적으로 seq_cst). legacy 스택은 porting.h에 정의된 ATOMIC_INC_*, ATOMIC_CAS_ADDR, ATOMIC_TAS_* 매크로를 쓴다. 이들은 GCC __atomic_* 빌트인의 __ATOMIC_SEQ_CST 로 확장되며, lf_tran_* 핫 패스에는 명시적 MEMORY_BARRIER() 매크로(__atomic_thread_fence (__ATOMIC_SEQ_CST))도 들어간다. 두 가지 귀결이 있다.

1. 약한 메모리 모델 아키텍처에서의 정확성은 보수적이지만 옳다. POWER/ARM 빌드는 모든 CAS에서 full sync 비용을 그대로 내지만, 결함 이 가려지지는 않는다.
2. acquire/release로 조이는 것은 열린 최적화 과제다. 측정 캠페인이 진행된 적 없다. 어차피 핫 패스에서는 훨씬 더 무거운 트랜잭션 테이블 min-스캔(lf_tran_compute_minimum_transaction_id)에 비용이 가려진다.

ABA에 대한 자세

트랜잭션 기반 회수 스킴은 트랜잭션 윈도우 바깥의 읽기에 대해서는 ABA를 풀지 않는다. descriptor::start_tran()을 먼저 부르지 않은 스레드가 포인터를 읽으면, 재활용된 노드가 원본인 양 보일 수 있고 검출되지 않는다. 따라서 다음과 같은 규율이 따라붙는다.

• 해시맵 체인의 모든 읽기는 트랜잭션 안에서. hashmap::list_find, list_insert_internal, list_delete는 모두 포인터를 디레퍼런싱하기 전에 tdes.start_tran()을 호출하고, 반환 직전에 tdes.end_tran()을 부르거나 그 자리를 대신할 뮤텍스를 잡는다.
• free list의 pop_from_available()은 명시된 예외다. 함수 자체에 ABA 윈도우를 명시한 다중 라인 주석이 들어 있다.

  // todo: this is a dangerous preemption point; if I am preempted
  // here, and thread 2 comes and does:
  //   - second thread gets same rhead and successfully moves m_available_list to next
  //   - third thread gets next and successfully moves m_available_list to next->next
  //   - second thread retires rhead. m_available_list becomes rhead and its next
  //     becomes next->next
  //   - I wake up, compare exchange m_available_list successfully because it is
  //     rhead again, but next will become the item third thread already claimed.

  위험은 백버퍼 패턴으로 좁혀진다(은퇴된 노드가 백버퍼에 머무는 시간이 길어, 다시 돌아올 때까지 충분히 긴 윈도우를 만든다). 그러나 완전히 제거되는 것은 아니다. 알려진 약점이며, 현재 완화책은 백버퍼 시간 뿐이고 태그된 포인터 재설계는 아직 적용되지 않았다.

다른 분석서로의 진입점

알고 싶은 것	읽을 문서
회수 프로토콜을 처음부터	cubrid-lockfree-transaction.md
두 해시 테이블이 왜 둘 다 있고 lf_entry_descriptor를 어떻게 공유하는지	cubrid-lockfree-hashmap.md §두 세대
Harris-Michael insert/delete 워크	cubrid-lockfree-hashmap.md §리스트 연산
MPMC 링 버퍼 프로토콜	cubrid-lockfree-circular-queue.md
트랜잭션 인덱스용 비트맵 할당기	cubrid-lockfree-bitmap.md
free list 백버퍼 트릭	cubrid-lockfree-freelist.md

소스 코드 가이드

Modern C++ 스택

• lockfree::tran::system (lockfree_transaction_system.{hpp,cpp}) 인덱스 디스펜서. m_tran_idx_map(bitmap)을 소유.
• lockfree::tran::table (lockfree_transaction_table.{hpp,cpp}) 자료구조별 회수 테이블. m_global_tranid, m_min_active_tranid와 descriptor 배열을 소유. 전역 ID가 MATI_REFRESH_INTERVAL(=100) 만큼 증가할 때마다 compute_min_active_tranid()를 호출.
• lockfree::tran::descriptor (lockfree_transaction_descriptor.{hpp,cpp}) — 스레드별·자료구조별 상태. (table, tran::index) 쌍마다 하나씩.
• lockfree::tran::reclaimable_node (lockfree_transaction_reclaimable.hpp) — 모든 은퇴 가능한 노드의 베이스 클래스. m_retired_next, m_retire_tranid, 그리고 가상 함수 reclaim()(기본은 delete this)을 제공.
• lockfree::address_marker<T> (lockfree_address_marker.hpp) — 포인터 최하위 비트 마크 트릭의 타입드 래퍼.
• lockfree::bitmap (lockfree_bitmap.{hpp,cpp}) — 청크 단위 어토믹 비트필드 할당기. chunking_style 두 모드.
• lockfree::freelist<T> (lockfree_freelist.hpp, 헤더 전용 템플릿) 백버퍼가 있는 타입드 free list. tran::system &로부터 자기 tran::table을 직접 만든다.
• lockfree::hashmap<K,T> (lockfree_hashmap.hpp, 헤더 전용 템플릿; lockfree_hashmap.cpp는 스텁) — Harris-Michael 체인을 가진 체이닝 해시맵. 엔트리별 뮤텍스가 선택적이며, clear()는 백버퍼로 구동된다.
• lockfree::circular_queue<T> (lockfree_circular_queue.hpp, 헤더 전용) — 커서 시퀀스 번호와 슬롯별 블록 플래그를 쓰는 고정 용량 MPMC 링 버퍼.

Legacy C 스택

• LF_TRAN_SYSTEM, LF_TRAN_ENTRY — lock_free.{h,c}. 부팅 시 lf_initialize_transaction_systems()로 11개의 전역 시스템이 인스턴스화된다.
• LF_FREELIST — lock_free.{h,c}. 단일 available 스택을 보유하며, 엔트리는 of_local_next로 연결된다.
• LF_HASH_TABLE, lf_hash_* — lock_free.{h,c}. legacy 해시맵. 엔트리 레이아웃은 LF_ENTRY_DESCRIPTOR로 기술된다.
• lf_list_find / lf_list_insert_internal / lf_list_delete — lf_hash_*에서 호출되는 Harris-Michael 체인 워크.
• lf_io_list_find / lf_io_list_find_or_insert — insert-only 리스트 (트랜잭션 시스템도, free list도 없음).
• lf_stack_push / lf_stack_pop — Treiber 스택. 현재 인-엔진 소비자가 없으며 역사적 이유로 남아 있다.
• lf_hash_table_cpp<K,T> — lf_hash_*를 감싸는 C++ shim. legacy 스택에 modern 해시맵 형태와 닿는 타입드 표면을 제공한다.

다리

• cubthread::lockfree_hashmap<K,T> (src/thread/thread_lockfree_hash_map.{hpp,cpp}) — lf_hash_table_cpp<K,T>와 lockfree::hashmap<K,T>를 둘 다 보유하며, init() 시점에 prm_get_bool_value (PRM_ID_ENABLE_NEW_LFHASH)로 결정된 m_type ∈ {OLD, NEW, UNKNOWN}로 디스패치한다.
• cubthread::get_thread_entry_lftransys() — 한 서버에서 모든 신형 해시맵이 공유하는, thread-manager 단위 lockfree::tran::system에 대한 접근자.

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

심볼	파일	라인
lockfree::tran::system::system	src/base/lockfree_transaction_system.cpp	29
lockfree::tran::table::table	src/base/lockfree_transaction_table.cpp	36
lockfree::tran::table::compute_min_active_tranid	src/base/lockfree_transaction_table.cpp	90
lockfree::tran::table::get_new_global_tranid	src/base/lockfree_transaction_table.cpp	73
lockfree::tran::descriptor::retire_node	src/base/lockfree_transaction_descriptor.cpp	65
lockfree::tran::descriptor::reclaim_retired_list	src/base/lockfree_transaction_descriptor.cpp	133
lockfree::address_marker<T>	src/base/lockfree_address_marker.hpp	31
lockfree::bitmap::get_entry (lf_bitmap_get_entry)	src/base/lockfree_bitmap.cpp	138
lockfree::freelist<T>::claim	src/base/lockfree_freelist.hpp	291
lockfree::freelist<T>::pop_from_available	src/base/lockfree_freelist.hpp	322
lockfree::hashmap<K,T>::find	src/base/lockfree_hashmap.hpp	280
lockfree::hashmap<K,T>::list_insert_internal	src/base/lockfree_hashmap.hpp	899
lockfree::hashmap<K,T>::list_delete	src/base/lockfree_hashmap.hpp	1111
lockfree::hashmap<K,T>::clear	src/base/lockfree_hashmap.hpp	378
lockfree::circular_queue<T>::produce	src/base/lockfree_circular_queue.hpp	230
lockfree::circular_queue<T>::consume	src/base/lockfree_circular_queue.hpp	318
lf_tran_start (legacy)	src/base/lock_free.c	413
lf_tran_compute_minimum_transaction_id (legacy)	src/base/lock_free.c	379
cubthread::lockfree_hashmap::init (다리)	src/thread/thread_lockfree_hash_map.hpp	129

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

검증된 사실

• 트리에 두 구현이 공존한다. src/base/lock_free.{h,c} (legacy) 와 src/base/lockfree_*.{hpp,cpp} 패밀리(modern)가 모두 존재하며 컴파일된다. src/thread/thread_lockfree_hash_map.hpp의 다리는 init() 시점에 prm_get_bool_value (PRM_ID_ENABLE_NEW_LFHASH)로 분기한다 (2026-05-07 기준 소스 직접 확인).
• 최소 활성 트랜잭션 ID 갱신 주기는 100으로 하드 코딩되어 있다. legacy LF_TRAN_SYSTEM::mati_refresh_interval(lf_tran_system_init 에서 100으로 초기화)과 modern lockfree::tran::table::MATI_REFRESH_INTERVAL이 모두 100. 런타임 파라미터가 아니므로 튜닝하려면 소스 수정이 필요하다.
• legacy 스택은 부팅 시 11개의 전역 LF_TRAN_SYSTEM을 만든다. spage_saving_Ts, obj_lock_res_Ts, obj_lock_ent_Ts, catalog_Ts, sessions_Ts, free_sort_list_Ts, global_unique_stats_Ts, hfid_table_Ts, xcache_Ts, fpcache_Ts, dwb_slots_Ts. 각각이 회수 도메인 한 개이며, lf_initialize_transaction_systems에서 채워진다. modern 스택에는 전역 tran::system이 없다. 소비자가 자기 것을 만든다.
• address-mark 비트는 포인터의 최하위 비트다. legacy ADDR_* 매크로와 modern lockfree::address_marker<T>::MARK = 0x1이 같은 비트 위치를 사용한다 (직접 비교 확인).
• pop_from_available의 ABA 윈도우는 소스에 명시되어 있다. freelist<T>::pop_from_available의 다중 라인 주석 (src/base/lockfree_freelist.hpp:336)을 참고. 백버퍼 시간이 지금 완화책이며, 태그된 포인터는 적용되어 있지 않다.
• modern 해시맵의 통계는 opt-in이다. m_active_stats의 기본값은 false이며 activate_stats() / deactivate_stats()로 토글한다. legacy 경로에는 자체 정적 카운터(lf_inserts, lf_deletes 등)가 lock_free.c에 있다. 무조건 존재하지만 UNITTEST_LF가 켜진 빌드 에서만 증가한다.

풀리지 않은 질문

1. 운영 서버에서 modern 경로로 도는 인-엔진 소비자 비율은? enable_new_lfhash의 기본값은 본 분석서에서 확정하지 못했다. system_parameter.c의 prm_def[]와 토글 관련 릴리스 노트 이력을 확인할 필요가 있다. 기본값이 false라면 운영 현실은 여전히 legacy이며, modern 경로는 장전된 총에 가깝지 굴러가는 엔진이 아니다.
2. modern 핫 패스의 seq_cst 접근이 ARM/POWER에서 측정 가능한 비용인가? 캠페인이 진행된 적이 없다. 경합 상태의 lockfree::hashmap find/insert/erase로 perf-test를 돌리고, 안전한 곳에서 acquire/release로 좁히는 프로파일 가이드 작업이 가치가 있다.
3. free_sort_list_Ts는 왜 legacy 전용인가? 마이그레이션이 의도적 으로 미완인지, 아니면 단순히 누가 손을 안 댄 후보인지가 분명하지 않다. query_executor.c에서 free_sort_list_Ts를 쓰는 부분의 git 이력을 살펴봐야 한다.
4. free list의 pop_from_available ABA 윈도우가 운영 환경에서 터진 적이 있는가? 위험은 명시되어 있지만 한계가 정량적으로 증명된 적은 없다. 워커에 의도적인 선점(SIGSTOP 등)을 걸어 재현-재획득 시나리오를 강제하는 스트레스 테스트가 백버퍼 거리가 경험적으로 충분한지를 알려줄 것이다.

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

• Hazard pointers 대 트랜잭션 기반 회수. Michael의 hazard-pointer 설계 (Michael 2004, IEEE TPDS)는 스레드별로 발행된 포인터를 회수한다. 트랜잭션 단위가 아니다. 비용은 트랜잭션 브래킷이 아니라 접근당 release store다. CUBRID 해시맵 워크로드에서 곁눈질로 비용 비교를 해보면, MATI_REFRESH_INTERVAL = 100의 분할 상환이 접근당 HP 발행보다 경험적으로 더 싼지를 알 수 있을 것이다.
• 사용자 공간 RCU (liburcu, Mathieu Desnoyers). 막지 않는 읽기를 rcu_read_lock/unlock으로 브래킷하고, 라이터는 회수를 유예 기간으로 미룬다. CUBRID의 트랜잭션 기반 회수는 구조상 자료구조별 사용자 공간 RCU다. 의문은 (대부분의 Linux 배포판에서 이미 시스템 라이브러리인) liburcu를 도입하면 자료구조별 스코프를 잃지 않으면 서도 lockfree::tran 패밀리의 코드량을 줄일 수 있느냐다.
• Folly의 ConcurrentHashMap(Facebook 오픈 소스). hazard-pointer 회수와 split-ordered 의미론을 적용한 운영 등급 C++ 락프리 해시 테이블. lockfree::hashmap과 비교하면 clear()-via-백버퍼 트릭이 실제 비용인지, 아니면 값싼 사치인지가 드러날 것이다.
• LMAX Disruptor (Thompson et al., 2011). 표준이 된 고정 용량 MPMC 링이다. CUBRID의 lockfree::circular_queue는 batched-claim과 대기 전략 일반화를 빼고 같은 모양이다. batched claim을 도입하면 DWB와 페이지 버퍼 victim 큐를 슬롯 하나당 CAS가 아니라 묶음 단위로 소진할 수 있다.
• 단일 서버 단위 lockfree::tran::system으로 통합. 오늘날 모든 modern 자료구조는 (cubthread::get_thread_entry_lftransys()로 반환되는) 서버 단위 tran::system에서 자기 tran::table을 만든다. 앞으로의 리팩터링이 legacy 11-시스템 동물원을 같은 서버 단위 시스템에 흡수한다면, 소비자 코드의 legacy/modern 구분이 무너지고 cubthread::lockfree_hashmap 다리는 은퇴할 수 있다.
• Wait-free flat combining (Hendler et al., SPAA 2010). CAS 루프 핫스팟을 스레드별 발행 기록으로 바꾸고, 지정된 결합자(combiner) 스레드가 일괄 처리하는 기법. 갱신이 드물고 리더가 많은 자료구조에 서 효과가 좋다. 락 매니저의 wait-for 그래프가 후보 중 하나다.

출처

• 소스 파일 (CUBRID 소스 트리, /data/hgryoo/references/cubrid/):
  • src/base/lock_free.h, src/base/lock_free.c
  • 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/lockfree_bitmap.{hpp,cpp}
  • src/base/lockfree_freelist.hpp
  • src/base/lockfree_hashmap.{hpp,cpp}
  • src/base/lockfree_circular_queue.hpp
  • src/thread/thread_lockfree_hash_map.{hpp,cpp}
• 인용한 교과서 챕터:
  • Herlihy & Shavit, The Art of Multiprocessor Programming, 3장 §Progress Conditions, 9–10장(락프리 연결 리스트), 13장 (동시 큐), 13장 §Bounded Lock-Free Queues.
  • Williams, C++ Concurrency in Action, 5장(메모리 모델), 7장 (락프리 자료구조 설계).
• 기반 논문:
  • Michael, M. M. “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects.” IEEE TPDS 15(8), 2004.
  • Harris, T. L. “A Pragmatic Implementation of Non-Blocking Linked-Lists.” DISC 2001.
  • Michael, M. M., Scott, M. L. “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.” PODC 1996.
  • Shalev, O., Shavit, N. “Split-Ordered Lists: Lock-Free Extensible Hash Tables.” JACM 53(3), 2006.
  • Treiber, R. K. “Systems Programming: Coping with Parallelism.” IBM Almaden RJ 5118, 1986.
  • Fraser, K. Practical Lock-Freedom. Univ. of Cambridge PhD thesis (epoch-based reclamation), 2004.
• 본 저장소 안의 자매 분석서:
  • cubrid-lockfree-transaction.md — 회수 프레임워크의 깊이 있는 설명.
  • cubrid-lockfree-hashmap.md — 두 해시 테이블 세대와 마이그레이션 서사.
  • cubrid-lockfree-circular-queue.md — 고정 용량 MPMC 링.
  • cubrid-lockfree-bitmap.md — 청크 단위 어토믹 비트맵 할당기.
  • cubrid-lockfree-freelist.md — 백버퍼가 있는 타입드 free list.
• 인접 분석서:
  • cubrid-thread-worker-pool.md — cubthread::entry::tran_entries[]와 get_lf_tran_index()가 락프리 프레임워크에 어떻게 연결되는지 설명.
  • cubrid-mvcc.md, cubrid-lock-manager.md — lf_hash_* (legacy) / cubthread::lockfree_hashmap(다리)의 주요 소비자.