(KO) CUBRID 락프리 해시 맵 — Legacy C, Modern C++, 다리, 그리고 소비자들

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

학술적 배경

동시 해시 테이블은 DBMS에서 가장 많이 쓰이는 락프리 자료구조다. 락 매니저, 페이지 버퍼 맵, 세션 캐시, 플랜 캐시, 통계 테이블 — 경합 하에서 O(1) 조회를 원하는 자원 단위 모든 키-값 쌍이 어떤 형태든 동시 해시를 고른다. 교과서적 설계 공간(Herlihy & Shavit, The Art of Multiprocessor Programming, 13장 §Concurrent Hashing, 그리고 Shalev & Shavit, JACM 53(3) 2006)은 세 축을 가진다.

Open vs. closed addressing. Open addressing(linear / quadratic probing, Robin Hood)은 엔트리를 버킷 배열에 직접 둔다. 캐시 친화적이지만 리사이즈에 약하다. Closed addressing(체이닝)은 엔트리를 버킷마다 연결 리스트에 둔다. 충돌을 체인이 흡수하므로 증분 성장이 쉽다.
Static vs. resizable. 정적 테이블은 버킷 수가 고정된다. 가변 테이블은 부하율이 임계치를 넘으면 자란다. 그러나 락프리 리사이즈는 어렵다. split-ordered 버킷 포인터(Shalev & Shavit) — 체인 자체 를 다시 잇지 않아도 되도록 해 주는 가 필요하거나, 아니면 stop- the-world 재해시(리사이즈 동안 락프리 성질을 포기) 둘 중 하나다.
체인은 누가 보호하는가? 거친 테이블 단위 뮤텍스(PostgreSQL의 LockHashPartitionLock), 버킷별 줄무늬(Java Java-8 이전의 ConcurrentHashMap), 또는 Harris–Michael 프로토콜(Harris 2001, Michael 2002)에 의한 완전 락프리 체인.

CUBRID는 closed addressing + 정적 버킷 + Harris–Michael 체인을 고른다. 비용은 자동 리사이즈가 없다는 점이다. 버킷 배열은 init 시점에 고정된다. 이득은 구현이 작아도 되고 체인 연산이 교과서 그대로 라는 점이다.

Harris–Michael 체인 연산

프로토콜은 각 체인 노드 위에 세 불변식을 둔다.

next 포인터의 최하위 비트는 삭제 마크로 예약된다.
삽입은 단일 CAS다. 선행자의 next에서 시작해 NULL을 새 노드 로 CAS. 선행자가 이미 next 값이 있으면 삽입자는 더 걷고 다시 시도한다. 이미 존재하는 키 삽입은 no-op(또는 find-or-insert 의미론에서는 찾음 반환)이다.
삭제는 두 단계 CAS 프로토콜이다.
- 마크. victim->next를 next_ptr에서 mark(next_ptr)로 CAS — 최하위 비트 set. 이후로 victim은 논리적으로 삭제됨이다. 동시 순회자는 마크를 보고 victim을 없는 것으로 다루지만, predecessor->next로부터 여전히 도달 가능하다.
- Unlink. predecessor->next를 victim에서 victim->next(마크 없는)로 CAS — 체인에서 victim을 물리적으로 제거한다. 이 CAS가 실패하면(마크와 unlink 사이에 누가 체인을 변경) 다시 시도하거나 (드물다) 검색을 처음부터 다시 한다(더 싸다).

부수 조건 두 가지가 있다.

stale에 대한 restart. 모든 체인 연산은 CAS 실패 시 버킷 머리에서 다시 시작해야 할 수 있다. legacy 코드의 LF_LIST_BR_RESTARTED 신호와 modern 코드의 restart_search boolean 이 그것이다.
회수. 논리적으로 삭제됐지만 아직 물리적으로 unlink되지 않은 노드는, predecessor->next로 그 노드에 도달했을 수 있는 모든 리더가 끝날 때까지 디레퍼런싱 가능해야 한다. 트랜잭션 기반 회수 프레임워크(lockfree::tran::*)가 그 역할을 한다.

ABA 위험과 회수에 의한 복구

체이닝 해싱의 고전적 ABA 시나리오는 다음과 같다. 한 스레드가 predecessor->next == A를 읽고 A->next를 CAS-마크하려고 한다. 형제 스레드가 A를 삭제하고 (예: free list로) 같은 주소에 새 A' 를 재할당한 뒤 A'를 어딘가에 삽입한다. 이제 predecessor->next는 A'를 가리킨다(또는 체인을 따라 더 멀리). 원래 스레드의 저장된 A 포인터 위에서의 CAS-마크는 성공해서 A'의 next를 조용히 망가뜨 리거나(use-after-free + 손상), 또는 주소가 바뀌었기 때문에 실패한다 (그게 목표지만 최악은 아니다).

트랜잭션 기반 회수 프레임워크가 이를 막는다. 원래 스레드가 테이블의 descriptor를 열어둔 한, 그 스레드가 관찰할 수 있었던 어떤 노드도 회수되지 않는다. A 포함. CAS-마크는 원래의 A 위에서 (논리적으로 삭제되었더라도 여전히 체인에 있는) 성공하거나, 체인 모양이 바뀌어 실패한다. 두 번째 할당의 앨리어싱은 일어나지 않는다.

해시 함수와 버킷 분포

CUBRID는 해시 함수를 테이블별 디스크립터의 f_hash 콜백에 위임한다. 이 콜백은 키와 버킷 수를 받아 버킷 인덱스를 반환한다. 소비자별로 다음과 같다.

락 매니저는 OID 형 해시를 사용.
페이지 버퍼(legacy LF_HASH_TABLE)는 VPID 해시를 사용: (pageid | ((unsigned int)volid) << 24) % htsize (lock_free.c:154).
세션 테이블은 세션 ID modulo 버킷 수.

버킷 수 자체는 부팅 시 시스템 파라미터에서 골라진 일회성 결정이다. 성장도, 축소도, 재해시도 없다. 리사이즈 형태의 유일한 연산은 clear다. 빈 백버퍼와 원자적으로 스왑한다. §Clear와 백버퍼 참고.

DBMS 공통 설계 패턴

락 매니저는 어디서나 체이닝 해시를 쓴다

PostgreSQL의 lock.c는 한 해시 테이블을 NUM_LOCK_PARTITIONS = 16 파티션으로 나누고 각각을 LWLock으로 보호한다. InnoDB의 lock_sys_t 는 (space_id, page_no) 쌍에 대한 해시 배열을 lock_sys->mutex로 보호한다(최근 버전은 sharded mutex 추가). MySQL의 open-table cache 는 테이블별 뮤텍스를 가진 해시다. 반복되는 패턴은 해시로 파티션, 파티션별 잠금이다.

CUBRID의 접근은 구조적으로 다르다. 파티션별 거친 뮤텍스 대신, 모든 체인이 완전히 락프리이고, 선택적 using_mutex는 파티션 단위가 아니라 엔트리 단위다. 트레이드오프는 다음과 같다.

장점. Find / insert / erase가 체인 길이가 허용하는 한 해시 크기에 비례해 선형으로 확장된다. 파티션 크기 임계치가 없다.
장점. 메모리 접근 패턴이 단순하다. 한 스레드가 한 번에 최대 한 엔트리의 뮤텍스만 잡는다.
단점. 트랜잭션 회수 오버헤드가 모든 find에서 0이 아니다 (start_tran/end_tran 브래킷).
단점. clear가 O(buckets × chain_length)이다. 모든 엔트리 를 은퇴시켜야 하기 때문이다. 백버퍼 트릭이 비용을 분산하지만 제거하지는 않는다.

엔트리별 뮤텍스 선택

미묘한 CUBRID 고유 설계가 있다. 어떤 엔트리는 자기 pthread_mutex_t 를 가진다(lf_entry_descriptor::using_mutex = 1과 of_mutex 필드 오프셋으로 선언). set이면 find와 erase가 엔트리를 찾은 뒤 페이로드 에 대한 연산 직전에 엔트리 뮤텍스를 잡고, 호출자가 이후에 별도 unlock 호출로 뮤텍스를 풀 수 있게 한다. 락 매니저의 자원 엔트리가 이 패턴을 쓴다. 락 자원을 찾은 스레드가 자원의 waiter 리스트를 변경하는 동안 자원 엔트리 뮤텍스를 들고 있어야 하기 때문이다.

using_mutex = 0이면 find/erase 결과는 트랜잭션 브래킷 안에서만 유효하다. 호출자는 페이로드 포인터를 들고 있는 동안 디스크립터의 m_tranid가 INVALID_TRANID로 가도록 두면 안 된다.

Find-or-insert 투기

존재 여부와 무관하게 엔트리를 원하는 흔한 경우가 insert-with-find- fallback(find_or_insert API)다. 구현 패턴은 이렇다. 검색 전에 free list에서 새 엔트리를 투기적으로 claim하고, 체인을 검색하고, 키가 이미 있으면 투기적 엔트리를 버리고, 그렇지 않으면 CAS-link 한다.

CUBRID는 descriptor::save_reclaimable 메커니즘 (cubrid-lockfree-transaction.md 참고)으로 버리는 비용을 최적화한다. 버려진 엔트리는 은퇴되지 않고 호출자 스레드의 디스크립터 위에 주차되며, 다음 호출 지점에서 free list 왕복 없이 재사용된다.

학술 ↔ CUBRID 매핑

개념	CUBRID 이름 (legacy)	CUBRID 이름 (modern)
체이닝 해시 테이블	`LF_HASH_TABLE`	`lockfree::hashmap<K,T>`
버킷 배열	`LF_HASH_TABLE::buckets`	`hashmap::m_buckets`
버킷 수	`LF_HASH_TABLE::hash_size`	`hashmap::m_size`
엔트리별 레이아웃 디스크립터	`LF_ENTRY_DESCRIPTOR`	(같은 구조체 `lf_entry_descriptor`)
해시 함수	`edesc->f_hash (key, htsize)`	(같음)
키 비교	`edesc->f_key_cmp (k1, k2)`	(같음)
키 복사	`edesc->f_key_copy (src, dst)`	(같음)
Init / uninit	`edesc->f_init`, `edesc->f_uninit`	(같음)
중복 키 콜백	`edesc->f_duplicate`	(같음)
엔트리별 뮤텍스 플래그	`edesc->using_mutex`	(같음)
필드 오프셋: next	`edesc->of_next`	(같음)
필드 오프셋: key	`edesc->of_key`	(같음)
필드 오프셋: mutex	`edesc->of_mutex`	(같음)
필드 오프셋: del_tran_id	`edesc->of_del_tran_id`	(legacy 전용 — modern은 free list 노드 사용)
필드 오프셋: local_next	`edesc->of_local_next`	(legacy 전용 — modern은 free list 노드 사용)
동작 플래그	`LF_LIST_BF_*`	(같은 상수 재사용)
Restart 신호	`LF_LIST_BR_RESTARTED`	(같은 상수 재사용)
Find 원시 함수	`lf_hash_find`	`hashmap::find`
Find-or-insert	`lf_hash_find_or_insert`	`hashmap::find_or_insert`
Insert	`lf_hash_insert`	`hashmap::insert`
Insert-given	`lf_hash_insert_given`	`hashmap::insert_given`
Delete	`lf_hash_delete`	`hashmap::erase`
Delete-locked	`lf_hash_delete_already_locked`	`hashmap::erase_locked`
Clear	`lf_hash_clear`	`hashmap::clear`
이터레이터	`LF_HASH_TABLE_ITERATOR`	`hashmap::iterator`
Clear용 백버퍼	`LF_HASH_TABLE::backbuffer`	`hashmap::m_backbuffer`
C++ shim	`lf_hash_table_cpp<K,T>`	(같음 — 다리가 사용)
세대 결정 래퍼	(없음)	`cubthread::lockfree_hashmap<K,T>`

CUBRID의 구현

두 세대, 한 디스크립터

해시 맵은 두 완전한 구현으로 존재하며 단일 디스패치 클래스로 다리가 놓인다. 두 경로가 같은 lf_entry_descriptor를 소비하므로 소비자별 엔트리 레이아웃은 마이그레이션을 거쳐도 변경 없이 동작한다.

Legacy C — `LF_HASH_TABLE` 위의 `lf_hash_*`

// LF_HASH_TABLE — src/base/lock_free.h:299
struct lf_hash_table {
  void **buckets;
  void **backbuffer;
  pthread_mutex_t backbuffer_mutex;
  unsigned int hash_size;
  LF_FREELIST *freelist;
  LF_ENTRY_DESCRIPTOR *entry_desc;
};

절차적 API: lf_hash_init, lf_hash_find, lf_hash_find_or_insert, lf_hash_insert, lf_hash_insert_given, lf_hash_delete, lf_hash_delete_already_locked, lf_hash_clear. 모두 LF_TRAN_ENTRY * (legacy 회수 시스템에서의 스레드별 상태)와 LF_HASH_TABLE *을 받는다.

C++ shim lf_hash_table_cpp<K,T>는 같은 헤더 안의 타입드 래퍼다. lf_freelist와 lf_hash_table을 인라인으로 소유하고, 모든 메서드를 C 함수에 forward한다. 엔트리 포인터는 reinterpret_cast<void**>(&t) 로 바꾼다. 이 shim이 cubthread::lockfree_hashmap이 OLD 경로용으로 들고 있는 것이다.

Modern C++ — `lockfree::hashmap<K,T>`

// lockfree::hashmap<Key, T> — src/base/lockfree_hashmap.hpp:42
template <class Key, class T>
class hashmap {
public:
  void init (tran::system &transys, size_t hash_size,
             size_t freelist_block_size, size_t freelist_block_count,
             lf_entry_descriptor &edesc);
  void destroy ();

  T   *find             (tran::index, Key &);
  bool find_or_insert   (tran::index, Key &, T *&);
  bool insert           (tran::index, Key &, T *&);
  bool insert_given     (tran::index, Key &, T *&);
  bool erase            (tran::index, Key &);
  bool erase_locked     (tran::index, Key &, T *&);

  void unlock           (tran::index, T *&);
  void clear            (tran::index);            // 락프리 아님
  T   *freelist_claim   (tran::index);
  void freelist_retire  (tran::index, T *&);

  void start_tran (tran::index);
  void end_tran   (tran::index);

  // ...
private:
  using address_type = address_marker<T>;
  struct freelist_node_data { T m_entry; lf_entry_descriptor *m_edesc; void on_reclaim (); };
  using freelist_type   = freelist<freelist_node_data>;
  using free_node_type  = typename freelist_type::free_node;

  freelist_type *m_freelist;
  T            **m_buckets;
  size_t         m_size;
  T            **m_backbuffer;
  std::mutex     m_backbuffer_mutex;
  lf_entry_descriptor *m_edesc;
  // 통계 ...
};

legacy와 다른 구조적 차이 세 가지.

K, T로 템플릿화. 공개 표면에 void* 캐스트가 없다.
전역 트랜잭션 시스템 참조 없음. 생성자가 tran::system &을 받아 자기 tran::table을 (free list 안에서) 만든다.
엔트리가 freelist<freelist_node_data>::free_node로 살고 단순 T가 아니다. Free list가 노드 헤더(tran::reclaimable_node 베이스 + m_owner 포인터)와 페이로드 T m_entry를 소유한다. §엔트리 레이아웃 참고.

다리 — `cubthread::lockfree_hashmap<K,T>`

// cubthread::lockfree_hashmap<Key,T> — src/thread/thread_lockfree_hash_map.hpp:35
template <class Key, class T>
class lockfree_hashmap {
public:
  void init (lf_tran_system &transys, int entry_idx, int hash_size,
             int freelist_block_size, int freelist_block_count,
             lf_entry_descriptor &edesc);
  void init_as_old (lf_tran_system &, int hash_size, int freelist_block_count,
                    int freelist_block_size, lf_entry_descriptor &, int entry_idx);
  void init_as_new (lockfree::tran::system &, size_t hash_size,
                    size_t freelist_block_size, size_t freelist_block_count,
                    lf_entry_descriptor &);
  // forwards: find, find_or_insert, insert, insert_given, erase, erase_locked,
  //           unlock, clear, freelist_claim, freelist_retire, start_tran, end_tran
private:
  enum type { OLD, NEW, UNKNOWN };
  lf_hash_table_cpp<Key, T> m_old_hash;
  lockfree::hashmap<Key, T> m_new_hash;
  type m_type;
  int  m_entry_idx;
};

디스패치는 init()에서 boolean 한 번 검사다.

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 (), (size_t) hash_size,
                 (size_t) freelist_block_size, (size_t) freelist_block_count, edesc);
  else
    init_as_old (transys, hash_size, freelist_block_count,
                 freelist_block_size, edesc, entry_idx);
}

forward되는 모든 메서드는 m_type을 읽고 매칭되는 호출로 디스패치 한다. 디스패치는 싸지만(조건부 분기 한 번) 모든 호출에서 일어난다. 인라인된 빠른 경로는 없다. 분기는 매크로(lockfree_hashmap_forward_func) 안에 있고, 모든 public 메서드가 그것을 확장한다.

공유 `lf_entry_descriptor`

두 경로가 같은 디스크립터를 소비한다.

// lf_entry_descriptor — src/base/lock_free.h:62
struct lf_entry_descriptor {
  unsigned int of_local_next;     // legacy 전용
  unsigned int of_next;
  unsigned int of_del_tran_id;    // legacy 전용
  unsigned int of_key;
  unsigned int of_mutex;
  int          using_mutex;
  int          max_alloc_cnt;     // legacy 전용

  LF_ENTRY_ALLOC_FUNC          f_alloc;     // legacy 전용
  LF_ENTRY_FREE_FUNC           f_free;      // legacy 전용
  LF_ENTRY_INITIALIZE_FUNC     f_init;
  LF_ENTRY_UNINITIALIZE_FUNC   f_uninit;
  LF_ENTRY_KEY_COPY_FUNC       f_key_copy;
  LF_ENTRY_KEY_COMPARE_FUNC    f_key_cmp;
  LF_ENTRY_HASH_FUNC           f_hash;
  LF_ENTRY_DUPLICATE_KEY_HANDLER f_duplicate;
};

필드는 세 부류다.

항상 사용. of_next, of_key, of_mutex, using_mutex, f_init, f_uninit, f_key_copy, f_key_cmp, f_hash, f_duplicate.
Legacy 전용. of_local_next(legacy 은퇴 리스트와 legacy 스택/free list가 사용), of_del_tran_id(legacy retire-id 스탬핑), max_alloc_cnt, f_alloc, f_free(legacy free list가 디스크립터 의 f_alloc/f_free로 블록 할당/해제. modern은 자기 free_node 타입에 new/delete).
Modern 전용. 없음 — modern 경로는 단지 legacy 전용 필드를 무시한다. 두 경로 모두에 채워진 디스크립터는 조용히 적절한 부분 집합만 사용한다.

이것이 두 세대 공존이 동작하는 이유다. 트리 안의 단일 디스크립터 가 어느 경로 위에서든 동작한다. Modern 코드는 legacy 필드를 그냥 지나치고, legacy 코드는 modern에서 부재한 부분을 신경 쓰지 않는다. 각 소비자(락 매니저, 세션 테이블 등)는 자기 디스크립터를 한 번 정의하고, 다리가 그 아래에서 구현을 뒤집는다.

엔트리 레이아웃 — modern

legacy 테이블이 f_alloc이 할당한 raw T를 엔트리로 저장하는 반면, modern 경로는 T를 free list 노드로 감싼다.

// lockfree::hashmap<K,T>::freelist_node_data — src/base/lockfree_hashmap.hpp:84
struct freelist_node_data {
  T m_entry;
  lf_entry_descriptor *m_edesc;
  freelist_node_data () = default;
  ~freelist_node_data () = default;
  void on_reclaim () {
    if (m_edesc->f_uninit != NULL)
      (void) m_edesc->f_uninit (&m_entry);
  }
};
using freelist_type  = freelist<freelist_node_data>;
using free_node_type = typename freelist_type::free_node;

free_node 템플릿이 tran::reclaimable_node 베이스 + freelist *m_owner back-pointer + 페이로드를 더한다(cubrid-lockfree-freelist.md 참고). 따라서 해시맵은 T m_entry에 대한 포인터를 버킷에 저장하고, 은퇴 시 둘러싸는 free_node로 다시 변환한다.

// hashmap<K,T>::to_free_node — src/base/lockfree_hashmap.hpp:552
free_node_type *to_free_node (T *p) {
  // not nice, but necessary until we fully refactor lockfree hashmap
  const std::ptrdiff_t off = free_node_offset_of_data (free_node_type ());
  char *cp = (char *) p;
  cp -= off;
  return (free_node_type *) cp;
}

free_node_offset_of_data constexpr 헬퍼가 free_node 안에서 m_entry의 오프셋을 계산하므로, 컴파일러 패딩과 무관하게 역캐스트가 정확하다. 헤더 주석이 이를 더 깊은 리팩터링 전까지의 임시 처리라고 인정한다. 올바른 설계는 해시맵 엔트리가 free list의 일반적 free_node를 거치지 않고 reclaimable_node를 직접 임베드하는 모양 이다.

필드 오프셋 접근 — 두 세대 모두

두 경로 모두 T를 멤버 접근이 아니라 바이트 오프셋으로 변경한다. 해시맵은 엔트리의 next 포인터를 다음과 같이 읽는다.

// hashmap<K,T>::get_nextp_ref — src/base/lockfree_hashmap.hpp:530
T *&get_nextp_ref (T *p) {
  return * (T **) get_ref (p, m_edesc->of_next);
}

// hashmap<K,T>::get_keyp — src/base/lockfree_hashmap.hpp:516
void *get_keyp (T *p) {
  return get_ptr (p, m_edesc->of_key);
}

이것이 lf_entry_descriptor를 단일 공유 타입으로 만드는 설계다. 두 구현이 모두 T*을 char*로 펀(pun)하고, 바이트 오프셋을 더하고, 필드 타입으로 다시 캐스트해 접근한다. 템플릿 매개변수 T는 접근 경로에 등장하지 않는다. 문서용 타입 결합이다. 따라서 legacy LK_RES (락 자원) 구조체는 소비자가 lf_hash_*에서 lockfree::hashmap<OID, LK_RES>로 옮길 때 변경 없이 저장된다.

컴포넌트 개요

flowchart TB
  Caller["소비자<br/>(lock_manager, session, ...)"]
  Bridge["cubthread::lockfree_hashmap&lt;K,T&gt;<br/>m_type ∈ {OLD, NEW, UNKNOWN}"]
  Caller --> Bridge

  subgraph Legacy["m_type = OLD"]
    Cpp["lf_hash_table_cpp&lt;K,T&gt;<br/>(템플릿, lock_free.h 안)"]
    LFH["lf_hash_table"]
    LFFL["lf_freelist"]
    LFTS["LF_TRAN_SYSTEM (소비자별 전역)"]
    LFTE["LF_TRAN_ENTRY[]"]
    Cpp --> LFH
    Cpp --> LFFL
    LFFL --> LFTS
    LFTS --> LFTE
  end

  subgraph Modern["m_type = NEW"]
    HM["lockfree::hashmap&lt;K,T&gt;"]
    FL["lockfree::freelist&lt;freelist_node_data&gt;"]
    TT["lockfree::tran::table"]
    TS["lockfree::tran::system<br/>(서버 단위)"]
    HM --> FL
    FL --> TT
    TT --> TS
  end

  Bridge --> Cpp
  Bridge --> HM

  PRM["PRM_ID_ENABLE_NEW_LFHASH<br/>(init 시점에 읽음)"]
  PRM --> Bridge

  Edesc["lf_entry_descriptor<br/>(둘이 공유)"]
  Edesc --> Cpp
  Edesc --> HM

리스트 연산 — modern, 자세히

해시맵은 세 사적 체인 원시 함수에 위임한다.

list_find — 읽기 전용 워크.
list_insert_internal — find-or-insert. 옵션으로 given-entry, 중복 콜백, 동작 플래그.
list_delete — Harris-Michael 두 단계 CAS unlink. 옵션으로 사전 잠금된 엔트리.

각각이 LF_LIST_BR_RESTARTED 플래그가 셋되면 재시도하는 외부 루프 (hash_insert_internal, hash_erase_internal)에 감싸진다. 동작 플래그 LF_LIST_BF_*와 응답 플래그 LF_LIST_BR_*는 legacy 헤더에서 그대로 가져왔다. modern 경로는 이 상수들을 다시 발명하지 않고 재사용 한다.

삽입 경로

// hashmap<K,T>::list_insert_internal (간추림) — src/base/lockfree_hashmap.hpp:899
bool list_insert_internal (tran::index tran_index, T *&list_head, Key &key,
                           int *behavior_flags, T *&entry)
{
  pthread_mutex_t *entry_mutex = NULL;
  T **curr_p; T *curr;
  tran::descriptor &tdes = get_tran_descriptor (tran_index);

  while (restart_search) {
    start_tran_force (tdes);                                // 브래킷 열기
    curr_p = &list_head;
    curr = address_type::atomic_strip_address_mark (*curr_p);

    while (curr_p != NULL) {
      if (curr != NULL) {
        if (m_edesc->f_key_cmp (&key, get_keyp (curr)) == 0) {
          // 중복 키 발견
          if (m_edesc->using_mutex) {
            lock_entry_mutex (*curr, entry_mutex);
            end_tran_force (tdes);                          // 뮤텍스가 트랜잭션 대체
            if (address_type::is_address_marked (get_nextp_ref (curr))) {
              // 삭제와 경쟁 — restart
              unlock_entry_mutex_force (entry_mutex);
              return false;     // RESTARTED 플래그 set
            }
          }
          if (m_edesc->f_duplicate != NULL) {
            // 중복 시 restart (현재의 유일한 동작)
            return false;
          }
          if (LF_LIST_BF_IS_FLAG_SET (behavior_flags, LF_LIST_BF_INSERT_GIVEN))
            freelist_retire (tdes, entry);                  // 투기적 엔트리 포기
          if (!LF_LIST_BF_IS_FLAG_SET (behavior_flags, LF_LIST_BF_FIND_OR_INSERT)) {
            // 순수 insert: 실패
            return false;
          }
          entry = curr;                                     // 찾은 엔트리 반환
          return false;                                      // 삽입은 아니지만 발견
        }
        // 다음으로 진행
        curr_p = &get_nextp_ref (curr);
        curr = address_type::strip_address_mark (*curr_p);
      } else {
        // 체인 끝 — 여기에 삽입
        if (entry == NULL) {
          entry = freelist_claim (tdes);                    // 투기적 claim
          if (m_edesc->f_key_copy (&key, get_keyp (entry)) != NO_ERROR)
            return false;
        }
        if (m_edesc->using_mutex) lock_entry_mutex (*entry, entry_mutex);

        if (!ATOMIC_CAS_ADDR (curr_p, (T *) NULL, entry)) {
          // 누가 먼저 link — 투기적 엔트리는 다음 라운드를 위해 저장하고 restart
          if (m_edesc->using_mutex) unlock_entry_mutex_force (entry_mutex);
          if (!LF_LIST_BF_IS_FLAG_SET (behavior_flags, LF_LIST_BF_INSERT_GIVEN))
            save_temporary (tdes, entry);
          LF_LIST_BR_SET_FLAG (behavior_flags, LF_LIST_BR_RESTARTED);
          end_tran_force (tdes);
          return false;
        }
        if (m_edesc->using_mutex) end_tran_force (tdes);    // 뮤텍스가 트랜잭션 대체
        return true;                                        // 삽입 성공
      }
    }
  }
}

삽입은 선행자 next 포인터에 대한 단일 CAS다. 그 주변의 처리는 다음 과 같다.

race-loss 시 save_temporary. 형제 스레드가 먼저 link해 CAS link가 실패하면, 투기적으로 claim된 엔트리는 디스크립터 위에 주차 (tdes.save_reclaimable)되어 다음 외부 while 반복이 그것을 재사용한다. free list 왕복 회피의 정체다.
f_duplicate 콜백 경로. 중복 키에 대한 소비자별 동작 콜백이 등록되어 있으면, 삽입은 그것을 부르고(예: 세션 ID 카운터 증가 후 새 키 요청) RESTARTED를 set해 다른 버킷에서 재시도한다.
뮤텍스가 트랜잭션을 대체. 엔트리가 뮤텍스를 가지면, 삽입은 CAS-link 전에 뮤텍스를 잡고 link 성공 직후에 트랜잭션을 종료한다. 페이로드 보호는 이제 뮤텍스로 충분하며, 트랜잭션 조기 종료가 디스크립터를 다른 연산에 풀어준다.

삭제 경로

// hashmap<K,T>::list_delete (간추림) — src/base/lockfree_hashmap.hpp:1111
bool list_delete (tran::index tran_index, T *&list_head, Key &key,
                  T *locked_entry, int *behavior_flags)
{
  while (restart_search) {
    start_tran_force (tdes);
    curr_p = &list_head;
    curr = address_type::atomic_strip_address_mark (*curr_p);

    while (curr != NULL) {
      if (m_edesc->f_key_cmp (&key, get_keyp (curr)) == 0) {
        if (locked_entry != NULL && locked_entry != curr) {
          // erase_locked 의미론: 내가 잡고 있던 엔트리는 이미 은퇴됨.
          // 같은 키로 발견된 현재 엔트리는 *다른* 것이다. 종료.
          return false;
        }
        next_p = &get_nextp_ref (curr);
        next   = address_type::strip_address_mark (*next_p);

        // 1단계: next 포인터 마크
        if (!ATOMIC_CAS_ADDR (next_p, next, address_type::set_adress_mark (next))) {
          // 경쟁 — restart
          if (LF_LIST_BR_RESTARTED) return false;
          break;
        }

        if (m_edesc->using_mutex) {
          if (LF_LIST_BF_IS_FLAG_SET (behavior_flags, LF_LIST_BF_LOCK_ON_DELETE))
            lock_entry_mutex (*curr, entry_mutex);
          else
            entry_mutex = get_pthread_mutexp (curr);  // 이미 잠금 상태
        }

        // 2단계: unlink
        if (!ATOMIC_CAS_ADDR (curr_p, curr, next)) {
          // 경쟁; 마크 제거 후 restart
          if (m_edesc->using_mutex && LF_LIST_BF_IS_FLAG_SET (..., LF_LIST_BF_LOCK_ON_DELETE))
            unlock_entry_mutex_force (entry_mutex);
          ATOMIC_CAS_ADDR (next_p, address_type::set_adress_mark (next), next);
          if (LF_LIST_BR_RESTARTED) return false;
          break;
        }
        if (m_edesc->using_mutex) unlock_entry_mutex_force (entry_mutex);

        promote_tran_force (tdes);                  // 전역 ID bump (은퇴 에포크)
        freelist_retire (tdes, curr);               // 은퇴 링에 append
        end_tran_force (tdes);
        return true;
      }
      curr_p = &get_nextp_ref (curr);
      curr   = address_type::strip_address_mark (*curr_p);
    }
  }
}

두 CAS는 정확히 Harris-Michael 프로토콜이다.

마크. next_p를 next에서 mark(next)로. 실패는 형제 스레드 도 같은 노드를 삭제하려 한다는 뜻(또는 1단계를 이미 끝냈다는 뜻)이다.
Unlink. curr_p를 curr에서 next(마크 없는)로. 실패는 선행자 포인터가 우리 아래에서 변경됐다는 뜻이다. 다른 삽입이나 삭제가 curr을 지나갔다. 복구: 마크를 되돌리고 restart.

은퇴는 unlink CAS가 성공한 뒤로 미뤄진다. 그래서 m_retire_tranid가 어떤 동시 리더의 스냅샷보다도 엄격히 크게 된다. promote_tran_force(전역 ID를 bump하고 자기 디스크립터에 쓰기)를 부르는 시점에는 체인이 더 이상 curr을 포함하지 않으므로, 이후의 어떤 리더도 버킷으로부터 그것을 볼 수 없다. curr을 직접 들고 있는 기존 리더는 자기 스냅샷의 tranid <= our pre-promotion tranid < our_retire_tranid이고, 회수는 min_active > retire_tranid일 때만 일어나기 때문에 안전하게 끝난다.

Find 경로

// hashmap<K,T>::find (간추림) — src/base/lockfree_hashmap.hpp:280
T *find (tran::index tran_index, Key &key)
{
  while (restart) {
    T *&list_head = get_bucket (key);
    entry = NULL;
    bflags = LF_LIST_BF_RETURN_ON_RESTART;
    list_find (tran_index, list_head, key, &bflags, entry);
    restart = (bflags & LF_LIST_BR_RESTARTED) != 0;
  }
  return entry;
}

find는 항상 LF_LIST_BF_RETURN_ON_RESTART를 set하므로, 체인 워크 가 restart하면 버킷-배열 수준으로 돌아가 해시를 다시 계산한다. 체인 의 유일한 in-flight 변경이 무관할 때(다른 키의 삽입/삭제) 의미가 있다. get_bucket에서 깨끗하게 다시 시작하면 버킷 포인터를 다시 디레퍼런싱하므로, clear가 그 아래에서 버킷 배열을 스왑했을 때도 견고하다.

Clear와 백버퍼

hashmap::clear는 유일한 비-락프리 공개 연산이다.

// hashmap<K,T>::clear (간추림) — src/base/lockfree_hashmap.hpp:378
void clear (tran::index tran_index)
{
  tran::descriptor &tdes = get_tran_descriptor (tran_index);
  std::unique_lock<std::mutex> ulock (m_backbuffer_mutex);

  // 1단계: m_buckets와 m_backbuffer를 원자적으로 스왑
  T **old_buckets = ATOMIC_TAS_ADDR (&m_buckets, m_backbuffer);

  // 2단계: 새 백버퍼(옛 m_buckets)가 된 것을 리셋
  for (size_t i = 0; i < m_size; ++i) {
    assert (m_backbuffer[i] == address_type::set_adress_mark (NULL));
    m_buckets[i] = NULL;
  }
  m_backbuffer = old_buckets;

  // 3단계: 옛 버킷의 모든 엔트리를 link 별로 은퇴
  for (size_t i = 0; i < m_size; ++i) {
    do {
      curr = address_type::strip_address_mark (old_buckets[i]);
    } while (!ATOMIC_CAS_ADDR (&old_buckets[i],
                               curr, address_type::set_adress_mark (NULL)));
    while (curr != NULL) {
      next_p = &get_nextp_ref (curr);
      do {
        next = address_type::strip_address_mark (*next_p);
      } while (!ATOMIC_CAS_ADDR (next_p, next, address_type::set_adress_mark (next)));
      if (m_edesc->using_mutex) {
        lock_entry_mutex (*curr, mutex_p);    // in-flight 리더 대기
        unlock_entry_mutex_force (mutex_p);
      }
      freelist_retire (tdes, curr);           // 은퇴 링에 append
      curr = next;
    }
  }
}

세 가지를 짚는다.

버킷 배열 스왑은 원자적이다. 동시 find가 잠깐 m_buckets가 옛 배열 또는 새 배열을 가리키는 모습을 볼 수 있다. 불변식은 어느 쪽을 가리키든 체인 워크가 성공한다는 점이다(restart-on-CAS-fail 모듈로). 모든 체인 link가 여전히 유효하기 때문이다.
백버퍼는 set_adress_mark (NULL)로 사전 마크되어 있어서, 백 버퍼의 버킷 머리를 보는 어떤 스레드도 마크된 NULL 체인 머리를 보고 빈 것으로 다룬다. 이것이 백버퍼 뮤텍스의 불변식이다. 그 아래에서 백버퍼는 항상 모두-마크-NULL이다.
은퇴 도중의 엔트리별 뮤텍스 획득이 in-flight 리더의 대기 지점 이다. clear 시작 전에 엔트리를 찾은 리더는 엔트리 뮤텍스를 들고 있을 것이다. clear는 그 뮤텍스 위에서 직렬화되어, 리더가 끝난 뒤 은퇴를 진행한다.

비용: O(buckets × chain_length) 어토믹 연산 + N pthread 뮤텍스 잠금/ 풀기 사이클 + 디스크립터 은퇴 링 성장. 무겁게 부하가 걸린 테이블에 서는 해시맵 표면에서 가장 무거운 단일 연산이다. clear를 부르는 소비자(로그아웃 시 세션, 종료 시 락 매니저, 플랜 캐시 리셋 시 XASL 캐시)는 이를 드문 이벤트로 받아들인다.

이터레이터

이터레이터(hashmap::iterator)는 버킷 단위, 체인 단위로 워크하며 버킷마다 트랜잭션을 열어둔다. 버킷 끝에서 자동으로 트랜잭션을 풀고 다음 버킷에서 다시 잡는다. 패턴은 의도적으로 보수적이다. 긴 순회는 디스크립터의 m_tranid를 낮게 유지해 서버 전체에 걸쳐 회수를 막을 것이기 때문이다.

// hashmap<K,T>::iterator::iterate (간추림) — src/base/lockfree_hashmap.hpp:1343
T *iterate () {
  do {
    if (m_curr != NULL) {
      if (m_hashmap->m_edesc->using_mutex)
        m_hashmap->unlock_entry (*m_curr);     // 엔트리별 뮤텍스 풀기
      m_curr = address_type::strip_address_mark (m_hashmap->get_nextp_ref (m_curr));
    } else {
      if (m_bucket_index != INVALID_INDEX) m_tdes->end_tran ();
      m_tdes->start_tran ();
      m_bucket_index++;
      if (m_bucket_index >= m_hashmap->m_size) {
        m_tdes->end_tran ();
        return NULL;                            // 끝
      }
      m_curr = address_type::atomic_strip_address_mark (m_hashmap->m_buckets[m_bucket_index]);
    }
    if (m_curr != NULL && m_hashmap->m_edesc->using_mutex) {
      m_hashmap->lock_entry (*m_curr);
      if (address_type::is_address_marked (m_hashmap->get_nextp_ref (m_curr)))
        continue;                               // 도중에 삭제됨, 건너뛰기
    }
  } while (m_curr == NULL);
  return m_curr;
}

메서드별 통계

모든 public 메서드는 ct_stat_type::autotimer로 감싸져 카운터를 증가시키고 시간을 누적시킨다. 누적 대상은 m_stat_find, m_stat_insert, m_stat_erase, m_stat_unlock, m_stat_clear, m_stat_iterates, m_stat_claim, m_stat_retire 중 하나다. autotimer는 m_active_stats == true가 아니면 단락된다. 토글은 테이블별 activate_stats() / deactivate_stats()다. 기본은 off다. 운영 서버는 운영자가 명시적으로 켜지 않는 한 통계 비용을 내지 않는다.

Legacy 구현, 간략히

legacy lf_hash_* 패밀리는 같은 Harris-Michael 워크를 C로 한다. tran::descriptor 대신 LF_TRAN_ENTRY *이고, 테이블별 테이블 대신 전역 LF_TRAN_SYSTEM이다. 핵심 절차적 호출은 다음과 같다.

lf_hash_init이 버킷 배열과 백버퍼를 만들고, free list에 entry_desc를 등록한다.
lf_hash_find이 lf_list_find(hashmap::list_find의 legacy 대응)를 부른다.
lf_hash_insert이 lf_hash_insert_internal → lf_list_insert_internal을 부른다.
lf_hash_delete이 lf_hash_delete_internal → lf_list_delete를 부른다.
lf_hash_clear이 modern clear와 같은 방식으로 백버퍼를 워크한다.

같은 LF_LIST_BF_* 플래그가 양쪽을 운전한다. 같은 백버퍼 레이아웃 (backbuffer[i] == ADDR_WITH_MARK (NULL))이 불변이다.

legacy 스택은 추가로 다음을 노출한다.

lf_io_list_find, lf_io_list_find_or_insert — 삭제 없는 insert-only 단일 연결 리스트로, free list가 없다. 스레드 안전한 append-only 집합이 필요한 코드 경로가 사용한다(현재 legacy 스택에 소수의 내부 호출 지점이 있고, modern 경로에 대응이 없다).
lf_stack_push, lf_stack_pop — Treiber 스택. ABA에 취약함이 명시되어 있고, 현재 어떤 인-엔진 소비자도 쓰지 않는다(잠재 외부 호출자와 컴파일/링크 호환성을 위해 보존).

마이그레이션 서사

legacy 스택은 CUBRID의 C++17 도입보다 앞선다. modern 스택은 C++17 현대화의 일부로 도입되었으며, 다음 두 목표가 명시되어 있다.

타입 안전성. 공개 표면에 더 이상 void*가 없다. lf_entry_descriptor 바이트 오프셋은 남지만 구현부 안에 한정된다.
테이블별 회수. 11개의 전역 LF_TRAN_SYSTEM 인스턴스가 더 이상 필요 없다. 각 lockfree::hashmap이 서버 단위 tran::system에서 자기 tran::table을 만든다. 락 매니저 해시의 회수 압력이 세션 테이블 회수를 조이지 않는다.

마이그레이션은 시스템 파라미터로 opt-in이지, 일제 전환 일자가 아니다. 다리는 각 소비자가 호출 지점을 다시 쓰지 않고 독립적으로 넘어갈 수 있도록 존재한다. 마이그레이션 완료의 기준 막대는 lf_hash_table_cpp 직접 호출 지점이 0이라는 점이다. 모든 소비자가 다리를 거쳐 새 경로로 가고, PRM_ID_ENABLE_NEW_LFHASH 토글이 서버 전체의 단일 결정이 된다.

2026-05-07 기준 토글 기본값은 본 분석서에서 확정하지 못했다 (Open Question 1 참고). 경험적으로, 다리 디스패치 매크로 lockfree_hashmap_forward_func이 해시맵에서 가장 핫한 코드다. 체인 워크보다 더 핫한데, 모든 public 호출이 그것을 거치기 때문이다.

소비자

소비자	소스	엔트리 구조체	세대 토글
오브젝트 락 자원 해시	`src/transaction/lock_manager.c`	`LK_RES`	`enable_new_lfhash`
오브젝트 락 엔트리 해시	`src/transaction/lock_manager.c`	`LK_ENTRY`	`enable_new_lfhash`
세션 테이블	`src/session/session.c`	`SESSION_STATE`	`enable_new_lfhash`
XASL 캐시	`src/query/xasl_cache.c`	`XASL_CACHE_ENTRY`	`enable_new_lfhash`
필터 술어 캐시	`src/query/filter_pred_cache.c`	`FILTER_PRED_CACHE_ENTRY`	`enable_new_lfhash`
시스템 카탈로그	`src/storage/system_catalog.c`	`CATCLS_ENTRY`	`enable_new_lfhash`
Slotted-page saving	`src/storage/slotted_page.c`	`SPAGE_SAVE_ENTRY`	`enable_new_lfhash`
HFID 테이블	`src/storage/heap_file.c`	`HFID_TABLE_ENTRY`	`enable_new_lfhash`
Global unique stats	`src/storage/btree.c`	`LOG_LSA / unique_stats`	`enable_new_lfhash`
DWB 슬롯 테이블	`src/storage/double_write_buffer.cpp`	`DWB_SLOT_HASH_ENTRY`	`enable_new_lfhash`
Sort-list (legacy 전용)	`src/query/sort.c`	`SORT_LIST_ENTRY`	(legacy 전용)

각 소비자는 자기 lf_entry_descriptor를 한 번 정의하고(보통 파일 스코프의 static const), cubthread::lockfree_hashmap<K,T> 멤버를 구성한 뒤 부팅 시에 init()을 한 번 호출한다.

소스 코드 가이드

Modern 스택 — 공개 표면

lockfree::hashmap<K,T> — 클래스 템플릿, lockfree_hashmap.hpp:42. .cpp(25줄)는 스텁.
hashmap::find — :280
hashmap::find_or_insert — :301
hashmap::insert — :308
hashmap::insert_given — :315
hashmap::erase — :325
hashmap::erase_locked — :345
hashmap::unlock — :360
hashmap::clear — :378
hashmap::freelist_claim — :656 (그리고 :663이 tran::descriptor & 오버로드)
hashmap::freelist_retire — :579 (그리고 :646이 tran::descriptor & 오버로드)
hashmap::list_find — :813
hashmap::list_insert_internal — :899
hashmap::list_delete — :1111
hashmap::hash_insert_internal — :1269
hashmap::hash_erase_internal — :1305
hashmap::iterator::iterate — :1343

Legacy 스택 — 공개 표면

LF_HASH_TABLE 구조체 — lock_free.h:299
LF_ENTRY_DESCRIPTOR 구조체 — lock_free.h:62
lf_hash_init — lock_free.c (파일 후반에 정의)
lf_hash_find — lock_free.c
lf_hash_find_or_insert — lock_free.c
lf_hash_insert / lf_hash_insert_given — lock_free.c
lf_hash_delete / lf_hash_delete_already_locked — lock_free.c
lf_hash_clear — lock_free.c
lf_list_find / lf_list_insert_internal / lf_list_delete 내부 체인 워크 (lock_free.c)
lf_io_list_find / lf_io_list_find_or_insert — insert-only 리스트 (lock_free.c:1077+)
lf_stack_push / lf_stack_pop — Treiber 스택 (lock_free.c:555+)
lf_freelist_init / lf_freelist_claim / lf_freelist_retire / lf_freelist_transport — lock_free.c:676+
lf_hash_table_cpp<K,T> — C++ shim, lock_free.h:367+

다리

cubthread::lockfree_hashmap<K,T> — thread_lockfree_hash_map.hpp:35
init (파라미터로 토글) — :129
init_as_old / init_as_new — :145, :155
forward되는 모든 메서드 (find, insert, erase, …) — :171-:294. lockfree_hashmap_forward_func 매크로 확장.
cubthread::get_thread_entry_lftransys — thread_lockfree_hash_map.cpp:27

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

심볼	파일	라인
`lockfree::hashmap<K,T>` (클래스 템플릿)	`src/base/lockfree_hashmap.hpp`	42
`hashmap::init`	`src/base/lockfree_hashmap.hpp`	261
`hashmap::find`	`src/base/lockfree_hashmap.hpp`	280
`hashmap::find_or_insert`	`src/base/lockfree_hashmap.hpp`	301
`hashmap::erase`	`src/base/lockfree_hashmap.hpp`	325
`hashmap::erase_locked`	`src/base/lockfree_hashmap.hpp`	345
`hashmap::clear`	`src/base/lockfree_hashmap.hpp`	378
`hashmap::list_find`	`src/base/lockfree_hashmap.hpp`	813
`hashmap::list_insert_internal`	`src/base/lockfree_hashmap.hpp`	899
`hashmap::list_delete`	`src/base/lockfree_hashmap.hpp`	1111
`hashmap::hash_insert_internal`	`src/base/lockfree_hashmap.hpp`	1269
`hashmap::iterator::iterate`	`src/base/lockfree_hashmap.hpp`	1343
`hashmap::freelist_node_data::on_reclaim`	`src/base/lockfree_hashmap.hpp`	92
`hashmap::to_free_node`	`src/base/lockfree_hashmap.hpp`	552
`lf_hash_table` (구조체)	`src/base/lock_free.h`	299
`lf_entry_descriptor` (구조체)	`src/base/lock_free.h`	62
`lf_hash_table_cpp<K,T>` (템플릿)	`src/base/lock_free.h`	367
`lf_freelist_alloc_block`	`src/base/lock_free.c`	621
`lf_freelist_claim`	`src/base/lock_free.c`	760
`lf_freelist_retire`	`src/base/lock_free.c`	873
`lf_freelist_transport`	`src/base/lock_free.c`	934
`lf_io_list_find`	`src/base/lock_free.c`	1077
`lf_io_list_find_or_insert`	`src/base/lock_free.c`	1131
`lf_stack_push` / `lf_stack_pop`	`src/base/lock_free.c`	554 / 584
`cubthread::lockfree_hashmap<K,T>`	`src/thread/thread_lockfree_hash_map.hpp`	35
`cubthread::lockfree_hashmap::init`	`src/thread/thread_lockfree_hash_map.hpp`	129
`cubthread::lockfree_hashmap::init_as_new`	`src/thread/thread_lockfree_hash_map.hpp`	155
`cubthread::lockfree_hashmap::init_as_old`	`src/thread/thread_lockfree_hash_map.hpp`	145
`cubthread::get_thread_entry_lftransys`	`src/thread/thread_lockfree_hash_map.cpp`	27

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

검증된 사실

다리는 init()에서만 디스패치한다. 호출별 토글이 없다. cubthread::lockfree_hashmap::init이 prm_get_bool_value (PRM_ID_ENABLE_NEW_LFHASH)를 정확히 한 번 읽고 m_type = OLD or NEW을 쓴다. 이후 호출은 m_type으로 디스패치된다. thread_lockfree_hash_map.hpp:129-141에서 확인.
두 구현이 같은 lf_entry_descriptor 타입을 소비한다. 구조체는 lock_free.h:62에 한 번 정의되고, lf_hash_*와 lockfree::hashmap<K,T>::init(인자로 lf_entry_descriptor &)이 사용. 두 시그니처를 직접 읽어 확인.
Modern 해시맵은 엔트리를 freelist_node_data 래핑으로 저장한다. 각 엔트리가 freelist<freelist_node_data>::free_node이며, tran::reclaimable_node 베이스, free list 소유자 back-pointer, 페이로드 T m_entry를 가진다. lockfree_hashmap.hpp:84-100에서 확인. 헤더가 to_free_node 오프셋 핵을 리팩터링 전까지의 임시 처리라고 인정함.
엔트리별 뮤텍스는 선택적이며 lf_entry_descriptor::using_mutex 로 제어된다. lockfree_hashmap.hpp:777(lock_entry_mutex의 assert (m_edesc->using_mutex))와 :362-371(unlock이 m_edesc->using_mutex로 분기)에서 확인.
f_duplicate 콜백은 현재 항상 restart한다. list_insert_internal이 lockfree_hashmap.hpp:962-976에서 f_duplicate이 NULL이 아니면 (예: 카운터 증가 같은) 부수 효과를 위해 부른 뒤 LF_LIST_BR_RESTARTED를 set하고 새 키로 검색을 재시작한다. #if 1 블록이 현재 죽어 있는 no-restart 대안 경로를 가리고 있다. 주석은 더 넓은 리뷰 전까지 의도적이라고 설명한다.
address_marker<T>::set_adress_mark이 코드 전반에 사용된 오타 표기다. lockfree_address_marker.hpp:49. 호출 지점들과 헤더가 모두 같은 오타를 쓴다.
clear의 백버퍼는 set_adress_mark (NULL)로 사전 마크되어 있다. lockfree_hashmap.hpp:272-275(init)와 :393(clear의 불변식 단언)에서 확인.
통계 기본값은 off. 테이블별 activate_stats() / deactivate_stats()로 토글. lockfree_hashmap.hpp:632-642에서 확인. m_active_stats은 기본 생성자(:219)에서 false로 초기화.

풀리지 않은 질문

enable_new_lfhash의 기본값. 본 분석서에서 확정하지 못했다. 조사: system_parameter.c의 prm_def[] 그리고 토글 관련 릴리스 노트 git 이력. 기본값이 false라면 운영 현실은 legacy 경로다. modern 경로는 단계적 도입이지만 굴러가지 않는다.
lf_hash_table_cpp<K,T>을 직접 호출하는 지점이 남아 있나? 다리의 존재는 모든 소비자가 cubthread::lockfree_hashmap을 쓴다는 가정에 기반한다. 어떤 소비자가 여전히 lf_hash_table_cpp 을 직접 인스턴스화한다면 그 소비자는 legacy 경로에 묶인다. 조사: lf_hash_table_cpp<을 grep해 모든 매치가 cubthread::lockfree_hashmap::m_old_hash 안에 있는지 확인.
modern 경로가 디스크립터에서 of_local_next를 왜 보존하는가? 필드는 legacy 전용이다. modern 해시맵은 엔트리를 free_node 안에 저장하고 은퇴 링에는 tran::reclaimable_node::m_retired_next 를 쓴다. 디스크립터가 of_local_next를 필요로 하지 않는다. 필드가 남은 이유는 짐작컨대 마이그레이션 도중 단일 디스크립터 객체가 두 경로를 모두 운전할 수 있어야 하기 때문이다. 마이그레이 션이 끝나면 of_local_next, of_del_tran_id, f_alloc, f_free, max_alloc_cnt은 모두 죽은 코드라서 정리해도 된다.
f_duplicate 의미론 — restart-only 동작이 최종 설계인가? lockfree_hashmap.hpp:972-1005의 #if 1 / #else / #endif 블록 이 두 대안을 트리에 남겨 둔다. no-restart 경로가 미래 기능 (키 재발행 없이 카운터만 증가)을 위한 것이라면, 죽은 분기는 되살리거나 제거해야 한다.
이터레이터가 열린 상태에서의 clear. clear가 m_backbuffer_mutex를 잡고 버킷 배열을 원자적으로 스왑한다. 옛 버킷 배열에서 m_curr을 들고 있는 열린 이터레이터는, 회수가 발화하기 전까지 은퇴된 메모리로 워크를 계속한다. 회수는 이터레이터의 m_tdes 브래킷으로 한정되므로 엔트리들은 여전히 살아 있다. 그러나 m_curr 포인터는 더 이상 라이브 테이블을 반영하지 않는다. 조사: clear-vs-iterator 경쟁이 문서화되어 있나? 안 되어 있다면 이터레이터 클래스에 테이블 세대 카운터 검사를 추가해야 한다.

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

Split-ordered 해싱 (Shalev & Shavit 2003). 단일 재귀 락프리 연결 리스트와 단축 경로 역할의 버킷 포인터. 락프리 리사이즈를 지원한다. 도입하면 해시맵이 init에서 고정되지 않고 경합 아래에 자랄 수 있다. 비용: 더 복잡한 체인 포인터와 버킷 배열 의미론에 대한 다른 불변식.
Folly의 ConcurrentHashMap. hazard-pointer 기반 회수, 더 단순한 API, 엔트리별 뮤텍스 없음. 락 매니저의 자원 해시에 대한 side-by-side 마이크로 벤치마크가 엔트리별 뮤텍스가 실제 비용인지 실제 이득인지 알려줄 것이다.
쿠쿠 해싱. 최악의 경우 O(1) 조회를 가지는 open-addressing 대안이다. 락프리 변종이 존재한다(Li et al. EuroSys 2014). 읽기 중심 워크로드(XASL 캐시)에서 비교할 만하다.
Legacy 경로 폐지. 가장 구체적인 프론티어는 lf_hash_*와 다리를 은퇴시키는 것이다. 단계: 최근 릴리스에서 enable_new_lfhash 기본값이 true인지 확인 → 한 릴리스 사이클 burn-in → lock_free.{h,c}와 다리의 m_old_hash 필드를 삭제.
소비자별이 아니라 서버 단위 해시 테이블. 오늘날 모든 소비자 가 자기 cubthread::lockfree_hashmap을 인스턴스화한다. 미래 리팩터링이 소비자 이름으로 인덱싱된 서버 단위 레지스트리를 노출한다면, 부팅 시 셋업 보일러플레이트가 줄고 튜닝이 중앙화될 것이다.
f_hash 콜백을 std::hash<K> 트레이트로 교체. C++17에 기계 가 이미 마련되어 있다. 유일한 장애물은 lf_entry_descriptor이 legacy 코드와 공유하는 C 형 구조체라는 점이다. legacy 경로가 사라지면 디스크립터는 C++ 클래스가 되고 f_hash는 템플릿 매개변수가 된다.

출처

소스 파일 (CUBRID 소스 트리, /data/hgryoo/references/cubrid/):
- src/base/lock_free.h, src/base/lock_free.c (legacy 절차적 API + lf_hash_table_cpp<K,T> 템플릿 shim)
- src/base/lockfree_hashmap.{hpp,cpp} (modern 템플릿화 클래스)
- src/base/lockfree_address_marker.hpp (포인터 마크 헬퍼)
- src/base/lockfree_freelist.hpp (modern 엔트리 저장소)
- src/base/lockfree_transaction_descriptor.hpp (read / retire 브래킷)
- src/thread/thread_lockfree_hash_map.{hpp,cpp} (다리 cubthread::lockfree_hashmap<K,T>)
소비자 소스 파일 (샘플):
- src/transaction/lock_manager.c (오브젝트 락 자원 & 엔트리 테이블 — 본 분석서의 주요 카나리아)
- src/session/session.c
- src/query/xasl_cache.c
- src/query/filter_pred_cache.c
- src/storage/system_catalog.c
- src/storage/slotted_page.c
- src/storage/double_write_buffer.cpp
인용한 교과서 챕터:
- Herlihy & Shavit, The Art of Multiprocessor Programming, 9장 §Lock-Free Linked Lists (Harris-Michael), 13장 §Concurrent Hashing (open vs. closed addressing, 줄무늬 vs. 락프리 체인).
- Williams, C++ Concurrency in Action, 7장 §“Designing lock-free concurrent data structures.”
기반 논문:
- Harris, T. L. “A Pragmatic Implementation of Non-Blocking Linked-Lists.” DISC 2001 — 두 CUBRID 세대가 모두 사용하는 next 마크 비트 프로토콜.
- Michael, M. M. “High Performance Dynamic Lock-Free Hash Tables and List-Based Sets.” SPAA 2002.
- Shalev, O., Shavit, N. “Split-Ordered Lists: Lock-Free Extensible Hash Tables.” JACM 53(3), 2006.
- Michael, M. M. “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects.” IEEE TPDS 15(8), 2004 — CUBRID가 채택하지 않은 대안 회수 모델.
본 저장소의 자매 분석서:
- cubrid-lockfree-overview.md — 우산 문서, 두 세대 지도.
- cubrid-lockfree-transaction.md — modern 해시맵이 올라가는 회수 프레임워크.
- cubrid-lockfree-freelist.md — 엔트리 저장소 계층.
- cubrid-lockfree-bitmap.md — tran::system 아래의 인덱스 할당기.
- cubrid-lock-manager.md — 본 해시맵의 모든 코드 경로를 훈련시키는 소비자.
- cubrid-thread-worker-pool.md — 다리가 사용하는 cubthread::entry::get_lf_tran_index()을 정의.