(KO) CUBRID 락프리 비트맵 — 스레드 인덱스와 슬롯 풀을 위한 청크 어토믹 할당기

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

학술적 배경

비트맵 할당기는 가장 단순한 동시 슬롯 할당기 모양이다. 슬롯당 한 비트, set이면 사용 중, clear이면 여유다. 할당은 clear 비트를 찾아 CAS-플립하고, 해제는 비트를 clear한다. 교과서 인용은 짧다. 모든 운영체제 교재가 비트맵 할당기를 메모리 관리 챕터에서 가볍게 언급(Tanenbaum, Modern Operating Systems, 4장)하고, 동시 자료구조 교재는 더 어려운 자료구조의 워밍업으로 다룬다.

흥미로운 설계 결정은 확장성에 관한 것이다.

워드 크기. 한 워드 분량의 비트(32 또는 64)는 워드 안 할당에 단일 CAS를 준다. 더 큰 풀은 여러 워드가 필요하고, 할당기가 그것들을 방문해야 한다.
검색 전략. 매번 워드 0부터 선형 스캔하면 첫 워드가 핫해진다 (바쁜 풀에서 캐시 라인 핑퐁). 시작 위치를 회전시키면 부하가 분산된다.
풀 가득 검출. 싼 O(1) 검사. 어토믹 카운터 entry_count_in_use 를 용량과 비교.
마지막 워드 패딩. 비트 수가 워드 크기의 배수가 아니면, 트레일 링 비트(존재하지 않는 슬롯을 나타냄)는 영구히 사용 중으로 set 해 둬야 한다. 그래야 0 비트 찾기 검색이 그것들을 정확히 건너뛴다.

CUBRID의 lockfree::bitmap은 32비트 워드(unsigned int), 회전 시작 힌트가 있는 선형 스캔, LIST_OF_CHUNKS 스타일용 명시적 entry_count_in_use, 그리고 마지막 워드 트레일링 비트 사전 set을 사용한다.

wait-free process 라벨은 왜?

lf_bitmap_get_entry 소스가 루프를 restart: /* wait-free process */ 로 표시한다. 주장은 다음과 같다. LIST_OF_CHUNKS 스타일에서 연산이 경합 아래에서도 유한 단계 안에 완료된다. CAS 실패가 control을 시작 라벨로 돌려보내지만, 매 반복마다 어떤 다른 스레드가 우리가 노리던 슬롯을 성공적으로 claim했으므로 진행이 일어난다. ONE_CHUNK 아래 에서는 동작이 wait-free라기보다 lock-free다(가득 찼을 때의 “이게 일어 나면 안 됨” 단언이, 호출자가 절대 고갈되지 않도록 비트맵 차원을 잡았다고 알려준다. 따라서 실용적 wait-freedom이 성립).

wait-free 주장은 실은 분할 상환 논증이다. 단일 스레드가 clear 비트 를 찾고 CAS-claim하는 사이에 반복적으로 선점될 수 있다. 최악의 경우 스레드가 무한히 루프한다. 그러나 유한 경합에 대해서는 루프가 O(N_threads) 반복 안에 종료되며, 이는 wait-free가 요구하는 유한 조건 이다.

라운드로빈 힌트

동시 비트맵의 흔한 최적화는 다음과 같다. 매 할당마다 회전하는 시작 인덱스를 두어, 연속한 스레드가 모두 첫 워드 위에서 CAS-싸움을 하지 않게 한다. 구현은 다음과 같이 다르다.

스레드별 시작 힌트. Thread-local 시작 인덱스. 경합은 없지만 캐시 친화적이지 않다(스레드 A가 막 풀어준 비트가 스레드 B에 보이지 않음).
전역 어토믹 시작 힌트. 단일 std::atomic<unsigned>가 매 할당 에서 bump된다. bump 위 경합이 있지만 분포가 우수하다.
샤드된 시작 힌트. CPU별 한 개. 하이브리드. CUBRID는 안 쓴다.

CUBRID는 SERVER_MODE(여러 스레드가 경합하는 서버 측 프로세스)에서 전역 어토믹을 고르고, 클라이언트 모드(단일 스레드 프로세스. 경합 없음)에서는 단일 비-어토믹 마지막으로 할당된 청크를 고른다.

DBMS 공통 설계 패턴

트랜잭션 ID 인덱스 풀로서의 비트맵

트랜잭션 슬롯(또는 스레드 슬롯, 세션 슬롯, …) 의 고정 크기 풀 을 가진 모든 DBMS는 그 슬롯에 대한 할당기가 필요하다. 모양은 동일하다. N비트의 비트맵, 할당 원시 함수, 해제 원시 함수.

PostgreSQL은 sentinel-per-slot 배열에서 할당된 BackendId (InvalidBackendId = 0)를 쓴다. 락프리 아님.
MySQL은 연결당 THD *을 LOCK_thread_count 아래의 free list 에서 할당한다. 뮤텍스 보호.
CUBRID는 legacy LF_TRAN_SYSTEM::lf_bitmap(전역 트랜잭션 시스템마다 하나)과 modern lockfree::tran::system::m_tran_idx_map에 모두 lockfree::bitmap 을 쓴다. 추가로 legacy area_alloc.{h,c}이 클라이언트 모드 컨텍스 트의 범용 슬롯 할당에 LF_BITMAP을 재사용한다.

페이지 할당기로서의 비트맵

비트맵은 디스크 페이지 할당 — 파일 안의 페이지마다 한 비트, set 이면 할당됨 — 의 자연스러운 표현이기도 하다. CUBRID의 disk_manager은 이 디스크 자료구조에 다른(락프리 아닌) 표현을 쓴다 (cubrid-disk-manager.md 참고). 락프리 비트맵은 메모리 상주 슬롯 풀에 한정된다.

학술 ↔ CUBRID 매핑

개념	CUBRID 이름
비트맵 할당기	`lockfree::bitmap` (typedef `LF_BITMAP`)
비트 배열	`bitfield[]` (`std::atomic<unsigned int> *`)
비트=슬롯, 사용 중 의미	`set bit ⇔ 슬롯 할당됨`
워드 크기	`LF_BITFIELD_WORD_SIZE = 32` (`sizeof(unsigned int) * 8`)
스타일 enum	`chunking_style ∈ {ONE_CHUNK, LIST_OF_CHUNKS}`
Full-usage 임계	`FULL_USAGE_RATIO = 1.0f`
95-percentile usage 임계	`NINTETYFIVE_PERCENTILE_USAGE_RATIO = 0.95f`
라운드로빈 시작 힌트	`start_idx` (`std::atomic<unsigned int>`)
사용 중 카운트	`entry_count_in_use` (`std::atomic<int>`, `LIST_OF_CHUNKS` 전용)
용량	`entry_count`
할당	`get_entry()` — 슬롯 인덱스 또는 -1 반환
해제	`free_entry(idx)`
가득 검사	`is_full()`
워드 정렬 용량 헬퍼	`LF_BITMAP_COUNT_ALIGN(count)` 매크로

CUBRID의 구현

클래스

// lockfree::bitmap — src/base/lockfree_bitmap.hpp:31
class bitmap {
public:
  static const float FULL_USAGE_RATIO;                 // 1.0f
  static const float NINTETYFIVE_PERCENTILE_USAGE_RATIO; // 0.95f

  enum chunking_style { ONE_CHUNK = 0, LIST_OF_CHUNKS };

  bitmap ();
  ~bitmap ();

  void init (chunking_style, int entries_count, float usage_ratio);
  void destroy ();
  int  get_entry ();                  // 가득이면 -1
  void free_entry (int entry_idx);
  bool is_full () const;

  // 공개 필드 ("private으로 만들 것" 표시):
  std::atomic<unsigned int> *bitfield;
  int                        entry_count;
  std::atomic<int>           entry_count_in_use;
  chunking_style             style;
  float                      usage_threshold;
  std::atomic<unsigned int>  start_idx;
};

클래스는 .cpp에 static으로 정의된 자유 함수 4개 (lf_bitmap_init / destroy / get_entry / free_entry)를 감싸는 얇은 래퍼다. 공개 필드는 헤더에 “todo: make private”로 표시되어 있다. 래퍼는 부분적인 C-to-C++ 마이그레이션 단계다.

두 청킹 스타일

chunking_style enum은 두 값만 가진다.

ONE_CHUNK — usage_threshold가 1.0f(전체 사용)여야 한다. 비트맵에 사용 한도가 없다. 모든 비트가 할당 가능하다. 모든 비트가 점유되면 get_entry()가 -1을 반환(그리고 디버그에서 단언 실패). ONE_CHUNK는 트랜잭션 인덱스 풀처럼 절대 고갈되지 않도록 차원을 잡은 사용 사례를 위한 것이기 때문이다.
LIST_OF_CHUNKS — usage_threshold가 (0, 1] 안의 어떤 값이든 가능하다. 별도 어토믹 카운터 entry_count_in_use이 유지된다. is_full()은 사용 중 카운트가 usage_threshold * entry_count에 도달하면 true를 반환. list of chunks 라는 이름은 역사적으로 다중 청크 확장 계획을 가리켰지만 끝나지 않았다. 현재 구현은 두 스타일 모두 단일 연속 비트필드다.

두 스타일 선택은 두 소비자 패턴을 대표한다.

스타일	사용처	이유
`ONE_CHUNK`	스레드별 트랜잭션 인덱스 할당(`tran::system`, legacy `LF_TRAN_SYSTEM`)	풀 크기는 `max_threads`로 제한된다. 고갈은 구성 오류이지 정상 동작이 아니다. 비트맵이 카운터 위 추가 어토믹을 감당할 수 없다.
`LIST_OF_CHUNKS`	부드러운 가득 상태가 의미 있는 범용 슬롯 할당(`area_alloc`)	95-percentile 임계가 배열이 진짜로 가득 차기 전에 할당기가 가득이라고 말하게 한다. in-flight 할당이 끝낼 헤드룸을 남긴다.

`init`

// lf_bitmap_init — src/base/lockfree_bitmap.cpp:83
static void lf_bitmap_init (LF_BITMAP *bitmap, LF_BITMAP_STYLE style,
                            int entries_cnt, float usage_threshold)
{
  /* We only allow full usage for LF_BITMAP_ONE_CHUNK. */
  assert (style == LF_BITMAP_LIST_OF_CHUNKS || usage_threshold == 1.0f);

  bitmap->style = style;
  bitmap->entry_count = entries_cnt;
  bitmap->entry_count_in_use = 0;
  bitmap->usage_threshold = usage_threshold;
  if (usage_threshold < 0.0f || usage_threshold > 1.0f)
    bitmap->usage_threshold = 1.0f;
  bitmap->start_idx = 0;

  /* initialize bitfield */
  size_t chunk_count = CEIL_PTVDIV (entries_cnt, LF_BITFIELD_WORD_SIZE);
  bitmap->bitfield = new std::atomic<unsigned int>[chunk_count] ();
  for (size_t it = 0; it < chunk_count; it++)
    bitmap->bitfield[it] = 0;

  /* pad out the rest bits with 1, It will simplify the code in lf_bitmap_get_entry() */
  if (entries_cnt % LF_BITFIELD_WORD_SIZE != 0) {
    unsigned int chunk = 0, mask = 1;
    int i = entries_cnt % LF_BITFIELD_WORD_SIZE;
    for (mask <<= i; i < LF_BITFIELD_WORD_SIZE; i++, mask <<= 1)
      chunk |= mask;
    bitmap->bitfield[chunk_count - 1] = chunk;
  }
}

두 가지를 짚는다.

트레일링 비트 패딩이 설계의 깔끔한 트릭이다. 할당기 비트 수가 예컨대 100이면, 마지막 워드는 비트 96..127 — 32비트 — 를 나타낸다. 그러나 96..99만 실제 슬롯이다. 비트 100..127은 미리 1로 set되어, 0 비트 찾기 검색이 정확히 그것들을 건너뛴다.
방어적 클램프 usage_threshold < 0.0f || > 1.0f → 1.0f는 호출자 잘못 구성에 대한 안전장치다. 실제로는 FULL_USAGE_RATIO (1.0f)와 NINTETYFIVE_PERCENTILE_USAGE_RATIO (0.95f)만 쓰인다.

`get_entry`

// lf_bitmap_get_entry — src/base/lockfree_bitmap.cpp:138
static int lf_bitmap_get_entry (LF_BITMAP *bitmap)
{
  int chunk_count = CEIL_PTVDIV (bitmap->entry_count, LF_BITFIELD_WORD_SIZE);
  unsigned int mask, chunk, start_idx;
  int chunk_idx, slot_idx, i;

restart:                              /* wait-free process */
  chunk_idx = -1;
  slot_idx  = -1;

  if (LF_BITMAP_IS_FULL (bitmap))
    return -1;

#if defined (SERVER_MODE)
  /* round-robin: bump global hint, mod chunk count */
  start_idx = bitmap->start_idx++;
  start_idx = start_idx % chunk_count;
#else
  /* iterate from the last allocated chunk */
  start_idx = bitmap->start_idx;
#endif

  /* find a chunk with at least one zero bit */
  i = start_idx;
  do {
    chunk = bitmap->bitfield[i].load ();
    if (~chunk) {                     // any bit clear?
      chunk_idx = i;
      break;
    }
    i++;
    if (i >= chunk_count) i = 0;
  } while (i != (int) start_idx);

  if (chunk_idx == -1) {              // wrapped around — full
    if (bitmap->style == LF_BITMAP_ONE_CHUNK)
      assert (false);
    return -1;
  }

  /* find first zero bit in chunk */
  for (i = 0, mask = 1; i < LF_BITFIELD_WORD_SIZE; i++, mask <<= 1)
    if ((~chunk) & mask) { slot_idx = i; break; }

  if (slot_idx == -1) goto restart;   // chunk filled in the meantime

  /* CAS-flip the bit */
  do {
    chunk = bitmap->bitfield[chunk_idx].load ();
    if (chunk & mask) goto restart;   // somebody else took this bit
  } while (!bitmap->bitfield[chunk_idx].compare_exchange_weak (chunk, chunk | mask));

  if (bitmap->style == LF_BITMAP_LIST_OF_CHUNKS)
    bitmap->entry_count_in_use++;

#if !defined (SERVER_MODE)
  bitmap->start_idx = chunk_idx;
#endif

  return chunk_idx * LF_BITFIELD_WORD_SIZE + slot_idx;
}

프로토콜은 다음과 같다.

Full 조기 종료. is_full()은 사용 중 카운터의 싼 스냅샷 비교(LIST_OF_CHUNKS) 또는 항상 false(ONE_CHUNK). 잘못된 방향으로 기운다. 실제 가득이어도 false를 반환할 수 있다. 루프가 wrap-around 검사로 그것을 잡는다.
시작 청크 선택. SERVER_MODE는 전역 어토믹 start_idx를 bump하고 청크 수로 modulo. 비-SERVER_MODE는 현재 값을 읽는다. 전역 bump는 경합 지점이지만 싼 것이다.
clear 비트가 있는 청크 선형 스캔. ~chunk != 0 ⇔ 청크에 적어도 한 0 비트가 있다. 끝에 닿으면 다시 start_idx까지 wrap.
첫 clear 비트 찾기. 청크 안 선형 스캔. mask = 1 << i.
비트 set CAS. 청크 워드에 대한 compare-exchange-weak. “현재 값에서 현재 값 | mask”로. 성공하거나, 아래에서 비트가 set됐음 을 검출(누가 이김)할 때까지 루프.
사용 중 카운터 유지(LIST_OF_CHUNKS 전용)하고 슬롯 인덱스 반환.

이중 CAS 패턴(내부 do { ... } while (!CAS_weak)와 외부 goto restart) 은 표준 Treiber 식 프로토콜이다. weak CAS는 가짜 실패할 수 있으므로 루프한다. 비트가 다른 사람에 의해 set됐으면 청크를 포기하고 start_idx에서 재시작.

`free_entry`

// lf_bitmap_free_entry — src/base/lockfree_bitmap.cpp:239
static void lf_bitmap_free_entry (LF_BITMAP *bitmap, int entry_idx)
{
  int pos = entry_idx / LF_BITFIELD_WORD_SIZE;
  int bit = entry_idx % LF_BITFIELD_WORD_SIZE;
  unsigned int inverse_mask = (unsigned int) (1 << bit);
  unsigned int mask = ~inverse_mask;
  unsigned int curr;

  do {
    curr = bitmap->bitfield[pos].load ();
    if (! (curr & inverse_mask)) {
      assert (false);                 // 이미 free — 호출자 버그
      return;
    }
  } while (!bitmap->bitfield[pos].compare_exchange_weak (curr, curr & mask));

  if (bitmap->style == LF_BITMAP_LIST_OF_CHUNKS)
    bitmap->entry_count_in_use--;

#if !defined (SERVER_MODE)
  bitmap->start_idx = pos;            /* 여유 슬롯 힌트 */
#endif
}

단일 CAS 루프. 단언된 불변식 curr & inverse_mask은 호출자 오류 (double-free)를 잡는다. NDEBUG로 빌드된 프로덕션은 두 번째 free를 조용히 no-op한다. 잘못이지만 한정적이다.

`is_full`

bool bitmap::is_full () const {
  return ((float) entry_count_in_use.load ()) >= usage_threshold * entry_count;
}

싼 O(1)이다. 단일 어토믹 load와 곱한 float 한 개의 비교. 스캔 없음. ONE_CHUNK 스타일에서도 이는 (0 >= 1.0 * entry_count)을 반환하는 데, 그것은 항상 false다(entry_count > 0이므로). 따라서 is_full() 은 ONE_CHUNK에서 no-op이며, 이는 ONE_CHUNK 비트맵이 절대 고갈되지 않도록 차원을 잡는다는 설계 계약과 일치한다.

참고: entry_count_in_use는 ONE_CHUNK 스타일에서는 유지되지 않는다 (get_entry / free_entry 끝의 증가/감소가 style == LIST_OF_CHUNKS로 게이팅됨). ONE_CHUNK 비트맵에서 entry_count_in_use을 조회하면 항상 0이 반환된다. get_entry의 사용 중 검출은 대신 wrap-around-without-finding-clear-bit 신호에 의존한다.

컴포넌트 개요

flowchart LR
  Caller["호출자"]
  Init["init(style, count, ratio)"]
  Caller --> Init
  Init --> Bitfield["bitfield[]:<br/>std::atomic&lt;uint&gt; * chunk_count"]
  Init -.패딩.-> LastWord["마지막 워드:<br/>트레일링 1들"]

  Caller --> Get["get_entry()"]
  Get --> StartIdx["start_idx (어토믹)"]
  StartIdx -.SERVER_MODE: bump.-> Get
  Get --> Scan["~chunk != 0인 청크 스캔"]
  Scan --> Find["첫 clear 비트 찾기"]
  Find --> CAS["CAS bit 0->1"]
  CAS -- 성공 --> Counter["LIST_OF_CHUNKS:<br/>entry_count_in_use++"]
  Counter --> Return["chunk_idx * 32 + bit 반환"]

  Caller --> Free["free_entry(idx)"]
  Free --> CAS2["CAS bit 1->0"]
  CAS2 --> Counter2["LIST_OF_CHUNKS:<br/>entry_count_in_use--"]

소비자 조사

소비자	스타일	용량	목적
`lockfree::tran::system::m_tran_idx_map`	`ONE_CHUNK`	`max_tran_count`	Modern 스레드별 트랜잭션 인덱스 디스펜서
`LF_TRAN_SYSTEM::lf_bitmap` (legacy)	`ONE_CHUNK`	`max_threads`을 워드 정렬	Legacy 회수의 스레드별 `LF_TRAN_ENTRY` 인덱스
`area_alloc` (`area_alloc.{h,c}`)	`LIST_OF_CHUNKS`	area별	범용 슬롯 할당기(legacy 메모리 풀)

처음 두 개가 지배적인 사용처다. area_alloc은 SERVER_MODE 핫 패스 에서 훈련되지 않는 작은 클라이언트 모드 헬퍼다.

`bitmap`은 `LF_BITMAP`으로도 노출된다

헤더는 다음을 가진다.

using LF_BITMAP        = lockfree::bitmap;
using LF_BITMAP_STYLE  = lockfree::bitmap::chunking_style;
static const LF_BITMAP_STYLE LF_BITMAP_ONE_CHUNK     = LF_BITMAP_STYLE::ONE_CHUNK;
static const LF_BITMAP_STYLE LF_BITMAP_LIST_OF_CHUNKS = LF_BITMAP_STYLE::LIST_OF_CHUNKS;

#define LF_BITMAP_FULL_USAGE_RATIO          lockfree::bitmap::FULL_USAGE_RATIO
#define LF_BITMAP_95PERCENTILE_USAGE_RATIO  lockfree::bitmap::NINTETYFIVE_PERCENTILE_USAGE_RATIO
#define LF_BITFIELD_WORD_SIZE               (int) (sizeof (unsigned int) * 8)
#define LF_BITMAP_IS_FULL(bitmap)           (bitmap)->is_full ()
#define LF_BITMAP_COUNT_ALIGN(count)        (((count) + (LF_BITFIELD_WORD_SIZE) - 1) & ~((LF_BITFIELD_WORD_SIZE) - 1))

이 듀얼 어휘 지원은 다음과 같이 동작한다. lock_free.c와 area_alloc.c의 코드는 LF_BITMAP_* 매크로를 참조하고, modern C++ 코드는 lockfree::bitmap::* 직접 이름을 참조한다. 둘 다 같은 클래스로 해석된다.

메모리 순서 자세

bitfield[]와 start_idx 위의 모든 어토믹 접근은 seq_cst다 (std::atomic 연산의 기본). 연산은 워드 크기이고 캐시 라인 친화적 이다. x86에서 seq_cst 오버헤드는 거의 무시할 만하다. ARM에서는 추가 펜스 비용을 낸다. acquire/release 쌍으로 조이는 것은 초점 최적화 다(fetch_or/fetch_and 패턴이 자연스러운 memory_order_acq_rel RMW이다).

오타 `NINTETYFIVE_PERCENTILE_USAGE_RATIO`에 대한 주석

상수는 “ninetyfive에서 e가 한 개 빠진 오타로 표기되어 있다(ninety” 가 맞다). 모든 호출 지점이 오타 표기를 쓰므로 이제는 짐을 짊어진 이름이다. 이름 바꾸기는 코드베이스 전반의 일괄 작업이다. 향후 정리 대상으로 표시.

소스 코드 가이드

공개 표면

lockfree::bitmap (클래스) — lockfree_bitmap.hpp:31
bitmap::init — lockfree_bitmap.cpp:53
bitmap::destroy — :59
bitmap::get_entry — :65
bitmap::free_entry — :71
bitmap::is_full — :77

정적 헬퍼

lf_bitmap_init — lockfree_bitmap.cpp:83
lf_bitmap_destroy — :124
lf_bitmap_get_entry — :138
lf_bitmap_free_entry — :239

매크로와 별칭(헤더)

LF_BITFIELD_WORD_SIZE — 32 (sizeof(unsigned int) == 4 가정)
LF_BITMAP_COUNT_ALIGN(count) — 워드 크기의 배수로 올림
LF_BITMAP_IS_FULL(bm) — (bm)->is_full() 별칭
LF_BITMAP_FULL_USAGE_RATIO / LF_BITMAP_95PERCENTILE_USAGE_RATIO

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

심볼	파일	라인
`lockfree::bitmap` (클래스)	`src/base/lockfree_bitmap.hpp`	31
`chunking_style` enum	`src/base/lockfree_bitmap.hpp`	37
`bitmap::is_full`	`src/base/lockfree_bitmap.cpp`	77
`lf_bitmap_init`	`src/base/lockfree_bitmap.cpp`	83
`lf_bitmap_get_entry`	`src/base/lockfree_bitmap.cpp`	138
`lf_bitmap_free_entry`	`src/base/lockfree_bitmap.cpp`	239
`LF_BITMAP_COUNT_ALIGN` 매크로	`src/base/lockfree_bitmap.hpp`	89
`LF_BITFIELD_WORD_SIZE` 매크로	`src/base/lockfree_bitmap.hpp`	85
`tran::system::system` (비트맵 사용)	`src/base/lockfree_transaction_system.cpp`	29
`lf_tran_system_init` (legacy 비트맵 사용)	`src/base/lock_free.c`	194

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

검증된 사실

워드 크기는 unsigned int 선택으로 32비트로 하드 코딩. LF_BITFIELD_WORD_SIZE = (int) (sizeof (unsigned int) * 8)이 lockfree_bitmap.hpp:85. CUBRID가 지원하는 모든 플랫폼에서 sizeof(unsigned int) == 4이므로 청크 워드당 32비트.
ONE_CHUNK은 FULL_USAGE_RATIO == 1.0f을 요구한다. lockfree_bitmap.cpp:91에서 단언: assert (style == LF_BITMAP_LIST_OF_CHUNKS || usage_threshold == 1.0f).
마지막 워드의 트레일링 비트는 1로 사전 set. lf_bitmap_init이 :112-121에서 요청 수보다 위의 모든 비트 마스크를 만들어 마지막 워드에 쓴다.
SERVER_MODE은 어토믹 전역 라운드로빈 시작을 쓴다. lf_bitmap_get_entry이 :160-167에서 bitmap->start_idx를 bump한 뒤 청크 수로 modulo. 비-SERVER_MODE 분기는 start_idx를 bump 없이 읽고, free 함수가 힌트로 start_idx = pos을 쓴다.
entry_count_in_use은 LIST_OF_CHUNKS 전용. :228의 증가와 :269의 감소가 bitmap->style == LF_BITMAP_LIST_OF_CHUNKS로 게이팅. ONE_CHUNK 비트맵은 카운터를 영원히 0으로 둔다.
CAS는 compare_exchange_weak을 쓴다. get_entry(:224)와 free_entry(:265) 둘 다 weak CAS를 써서, 약한 메모리 모델 아키 텍처에서 가짜 실패가 루프 안에서 재시도된다.
is_full은 O(1). 단일 어토믹 load와 곱한 float의 비교. 스캔 없음.
LIST_OF_CHUNKS라는 list of chunks 이름은 역사적이다. 구현은 단일 연속 비트필드. lf_bitmap_init을 읽어 확인: bitmap->bitfield = new std::atomic<unsigned int>[chunk_count]()이 스타일과 무관하게 한 번의 연속 할당.

풀리지 않은 질문

CUBRID의 비트맵이 현실적인 ONE_CHUNK 사용에서 고갈된 적이 있는가? wrap-around 분기의 assert (false)은 구성된 풀이 너무 작을 때만 발화한다. 조사: 정상 동작에서 tran::system::assign_index가 INVALID_INDEX을 반환하지 않음을 확인하기 위해 고스레드 카운트로 스트레스 테스트.
전역 어토믹 start_idx bump가 측정된 병목인가? SERVER_MODE의 모든 get_entry가 그것을 bump한다. 64코어 머신에서 공격적으로 은퇴하는 해시맵이라면 start_idx 캐시 라인이 핫하다. CPU별 샤드 변종이 이를 피하겠지만, 프로파일링 데이터가 없다.
free_entry의 단언이 운영 빌드에서는 왜 조용한가? LIST_OF_CHUNKS 비트맵의 더블 free는 entry_count_in_use을 두 번 감소시켜, 결국 0 아래로 wrap된다(signed int이므로 정의되지 않은 동작). 단순히 컴파일 아웃되는 assert보다는 시끄러운 er_set이 더 안전하다.
워드 크기 가정의 이식성. LF_BITFIELD_WORD_SIZE = sizeof(unsigned int) * 8은 unsigned int이 32비트라고 가정한다. 가상의 16비트 플랫폼에서는 LF_BITMAP_COUNT_ALIGN 매크로와 트레일링 비트 패딩이 여전히 동작하지만, 큰 풀에서 (int) (...) 캐스트가 오버플로할 수 있다. CUBRID는 그런 플랫폼을 타깃하지 않는다. 명료성을 위해 표시. 조치 항목 아님.
필드를 private으로 만드는 리팩터링. 헤더의 // todo: make private fields 주석은 충분히 오래되어 todo보다는 안 할 것 처럼 읽힌다. private으로 승격하면 lf_tran_system_init(현재 lock_free.c:387에서 sys->lf_bitmap.bitfield[i]을 직접 접근) 이 접근자를 거치도록 만들어야 한다. 작지 않은 리팩터링 비용.

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

샤드된 시작 힌트. CPU별 start_idx(sched_getcpu() 또는 스레드 인덱스로 샤딩)이 다코어 머신에서 전역 어토믹 bump 경합을 제거할 것이다.
64비트 청크 워드. uint64_t로 전환하면 같은 용량에서 워드 안 할당 밀도가 두 배가 되고 청크 수가 절반이 된다. CAS도 64비트 가 되며, x86-64에서는 무료다.
계층적 비트맵. 다층 비트맵(상위 레이어가 “이 자식이 적어도 한 0 비트를 가짐”으로 표시)이 스캔을 O(chunks)에서 O(log chunks)로 줄인다. 매우 큰 풀에만 가치가 있고, CUBRID는 그런 풀이 없다.
첫-0-비트 검색에 __builtin_ctz. 현재 내부 루프는 비트 0부터 의 선형 스캔이다. __builtin_ctz (~chunk)로 바꾸면 첫 clear 비트 를 O(1)에 찾는다. 사소한 마이크로 최적화. 내부 루프가 측정된 핫스팟이 아니므로 미루어졌다.
트랜잭션 인덱스에 비트맵 대신 CPU별 free list. CPU별 tran::index free list와 빈 시 스틸 정책을 두면 비트맵 자체를 제거하고 라운드로빈 bump를 없앨 수 있다. 트레이드는 더 적은 경합 을 위해 더 많은 코드.
오타를 깔끔한 이름으로 승격. NINTETYFIVE_PERCENTILE_USAGE_RATIO은 일관되게 오타다. grep- replace 패스가 의미 변화 없이 철자를 고칠 것이다.

출처

소스 파일 (CUBRID 소스 트리, /data/hgryoo/references/cubrid/):
- src/base/lockfree_bitmap.{hpp,cpp} (구현 전체)
- src/base/lock_free.h (legacy 별칭과 매크로)
- src/base/lock_free.c (legacy LF_TRAN_SYSTEM 측 사용)
- src/base/lockfree_transaction_system.{hpp,cpp} (modern 사용)
- src/base/area_alloc.h (LIST_OF_CHUNKS을 쓰는 legacy 슬롯 할당기)
인용한 교과서 챕터:
- Tanenbaum, Modern Operating Systems, 4장 §“Memory Management” — 슬롯 할당기에 대한 비트맵 vs free list 트레이드.
- Herlihy & Shavit, The Art of Multiprocessor Programming, 5장 §Wait-Free Synchronization — 진행 조건과 wait-free 분할 상환 논증.
본 저장소의 자매 분석서:
- cubrid-lockfree-overview.md — 우산 문서.
- cubrid-lockfree-transaction.md — 비트맵의 지배적 소비자 (스레드별 인덱스 할당).