콘텐츠로 이동
hgryoo · Docs

(KO) CUBRID 락프리 원형 큐 — 슬롯별 블록 플래그를 가진 고정 용량 MPMC 링

목차

학술적 배경

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

고정 용량 multi-producer multi-consumer (MPMC) 큐는 고처리량 시스템에서 정통 스레드 간 핸드오프 원시 자료구조다. 한 집단의 스레드 가 페이로드를 push하고, 다른 집단의 스레드가 그것을 pop한다. 처리량 의 목표는 항목당 비용을 어토믹 연산 적은 수로 분할 상환하는 것이다. 교과서 기준점은 Herlihy & Shavit, The Art of Multiprocessor Programming, 13장 §Concurrent Queues다. 구현 패밀리는 세 가지가 반복된다.

  1. 연결 리스트 MPMC (Michael & Scott 1996). 두 어토믹 포인터 (head, tail). 각 enqueue가 노드를 할당하고 CAS-link, 각 dequeue 가 head를 CAS-전진. 무한이며 항목당 한 번의 할당이 강제된다. 운영 사례: Java의 ConcurrentLinkedQueue.
  2. 고정 용량 링 버퍼 (Lamport 1983 SPSC. MPMC 변종 다수). 2의 거듭제곱 슬롯 배열 + 두 커서 어토믹 + 슬롯별 동기화. 항목당 할당 없음. 운영 사례: LMAX Disruptor (Thompson et al. 2011).
  3. 고정 용량 fetch-and-add 링 (Yang & Mellor-Crummey 2016). 프로 듀서와 컨슈머가 각자 자기 커서를 fetch-and-add. 슬롯의 “시퀀스 번호”가 그 슬롯이 produce 준비인지 consume 준비인지를 알려준다. 현재의 가장 깔끔한 운영 설계(Vyukov, Adamson). Boost.Lockfree의 spsc_queue / queue와 다수의 고성능 C++ 라이브러리가 사용.

CUBRID의 lockfree::circular_queue<T>는 패밀리 (2)에 가장 가깝되, fetch-and-add가 아니라 CAS 커서를 쓰며, 시퀀스 번호 대신 슬롯별 블록 플래그를 둔다. 차이가 의미하는 바는 다음과 같다.

  • CAS 커서는 프로듀서가 큐가 가득 찬 상태인지를 싸게 검출하게 해 주지만(consume 커서 + 용량을 produce 커서와 비교), 같은 슬롯에 대한 프로듀서 간 경쟁을 노출시킨다.
  • 블록 플래그가 그 경쟁을 해소한다. 커서 CAS에서 진 프로듀서도 여전히 커서를 한 칸 올렸지만, 슬롯별 블록 플래그 CAS의 승자만이 그 슬롯에 쓸 수 있다. 블록 플래그는 컨슈머에게는 produce 완료 신호로도 기능한다.

설계에는 알려진 약점이 있다. 소스 자체에 명시되어 있다. 커서 bump 와 블록 해제 사이에 선점된 프로듀서는 그 슬롯에서 모든 컨슈머를 깨어 날 때까지 멈추게 한다. 엄격한 진행 조건의 의미에서 락프리가 아니다 (프로듀서가 막힌 동안 컨슈머가 강제로 대기). 소스가 이를 인정하며 관심사 분리 재설계를 향후 작업으로 기록한다.

커서 불변식

섹션 제목: “커서 불변식”

uint64_t 어토믹 커서 두 개.

  • m_produce_cursor — 단조 증가. compare_exchange_strong으로 read-and-bump.
  • m_consume_cursor — 단조 증가. compare_exchange_strong으로 read-and-bump.

용량은 다음 2의 거듭제곱으로 올림된다. 커서의 슬롯 인덱스는 cursor & (capacity - 1)이다.

크기 불변식은 다음과 같다. produce_cursor - consume_cursor이 현재 항목 수다. 큐는 consume_cursor + capacity <= produce_cursor이면 가득 찬 상태, produce_cursor <= consume_cursor이면 비어 있다.

슬롯별 블록 플래그

섹션 제목: “슬롯별 블록 플래그”

병렬 어토믹 uint64_t 배열 m_blocked_cursors[capacity]. 각 슬롯의 플래그 워드는 다음을 인코딩한다.

  • 낮은 비트에는 기대 커서 값 — 슬롯이 다음에 받아들이려고 준비된 커서 값(처음에는 슬롯 인덱스, 그 후 매 produce마다 +capacity bump).
  • 가장 높은 비트에는 BLOCK_FLAG (0x8000_0000_0000_0000). set이면 produce 진행 중. 컨슈머는 이 슬롯을 읽으면 안 됨이다.

조합이 세 상태를 암묵적으로 인코딩한다.

슬롯 상태플래그 워드
커서 c에서 produce 준비c (BLOCK_FLAG 없음)
커서 c에서 produce 진행 중c | BLOCK_FLAG
Produced. consume 준비c + capacity (unblock 후)

컨슈머는 블록 플래그를 읽고, BLOCK_FLAG가 clear임을 본 뒤 슬롯을 읽는다. 슬롯 세대는 커서 값을 용량으로 modulo한 것으로 인코딩되므로, 같은 슬롯 인덱스에서 다음 세대를 다시 claim하려는 프로듀서는 플래그 워드를 더 이상 이전 기대 값과 일치하지 않는 값으로 bump해야만 한다.

DBMS 공통 설계 패턴

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

백그라운드 작업 스레드를 도는 모든 DBMS는 어떤 형태의 MPMC 큐를 출하한다. 모양은 수렴한다.

Vacuum 디스패치 (PostgreSQL, MySQL InnoDB purge, CUBRID)

섹션 제목: “Vacuum 디스패치 (PostgreSQL, MySQL InnoDB purge, CUBRID)”

패턴은 다음과 같다. 로그 플러시 데몬이 로그 블록 N이 영속됐다 항목 을 발행하고, vacuum 워커가 pop해서 처리한다. 큐의 역할은 로그 플러시 의 지연(동기)과 vacuum의 지연(결국 일관)을 분리하는 것이다.

  • PostgreSQL은 MPMC 큐를 쓰지 않는다. autovacuum-launcher가 pg_class를 주기적으로 스캔하고 공유 메모리 상태로 디스패치한다. 분리는 큐가 아니라 폴링으로 일어난다.
  • InnoDB purge는 단일 디스패치 스레드가 링 버퍼(trx_purge_t::view) 에서 pop하고, 다수의 워커 스레드가 파티션된 집합에서 가져간다.
  • CUBRID vacuum은 lockfree::circular_queue<T> 인스턴스 두 개를 쓴다. vacuum 대상 로그 블록 준비됨용 vacuum_Block_data_buffer 와 블록 N 완료, vacuum의 안전 LSN 전진 가능용 vacuum_Finished_job_queue다.

페이지 버퍼 victim 핸드오프

섹션 제목: “페이지 버퍼 victim 핸드오프”

스레드가 버퍼링되지 않은 페이지를 fix하면 victim을 evict해야만 한다. 결정은 인라인(fixer가 LRU를 워크하고 evict)으로 하거나 파이프라인 (데몬이 LRU를 스캔해 evict 준비된 victim을 발행, fixer가 pop) 으로 한다.

  • MySQL InnoDB는 mutex 보호 buf_LRU 리스트로 인라인 evict 한다.
  • PostgreSQL은 BufFreelist spinlock으로 인라인 evict 한다.
  • CUBRID는 다수의 lockfree::circular_queue<int> 큐 (private_lrus_with_victims, big_private_lrus_with_victims, shared_lrus_with_victims)로 파이프라인 모델을 쓴다. 페이지 버퍼 유틸리티 데몬이 victim LRU 파티션 인덱스를 발행하고, fixer 스레드 가 pop해서 사용한다.

CDC / 복제 전달

섹션 제목: “CDC / 복제 전달”

CUBRID의 CDC 서브시스템은 로그 매니저 스레드에서 CDC 게시 스레드로 log-info 항목을 cdc_Gl.loginfo_queue (lockfree::circular_queue <CDC_LOGINFO_ENTRY *>)로 전달한다. 모양은 PostgreSQL이 SLRU 공유 메모리로, MySQL이 binlog mutex 아래의 Log_event 할당으로 구현하는 producer-consumer 스트리밍 패턴과 같다.

학술 ↔ CUBRID 매핑

섹션 제목: “학술 ↔ CUBRID 매핑”
개념CUBRID 이름
고정 용량 MPMC 큐lockfree::circular_queue<T>
2의 거듭제곱 용량m_capacity = next_pow2 (size)
슬롯 인덱스 마스크m_index_mask = m_capacity - 1
프로듀서 커서m_produce_cursor (std::atomic<uint64_t>)
컨슈머 커서m_consume_cursor (std::atomic<uint64_t>)
슬롯별 블록 플래그m_blocked_cursors[i] (std::atomic<uint64_t>)
블록 비트BLOCK_FLAG = 1ULL << 63
빈 검사produce_cursor <= consume_cursor
가득 검사consume_cursor + capacity <= produce_cursor
커서로부터 슬롯 인덱스cursor & m_index_mask
Produce 진행 슬롯 신호m_blocked_cursors[i]의 블록 플래그 set
Unblock 시 세대 bumpflag word ← cursor + capacity
Force-produce 대기std::this_thread::yield()
선택적 실행 이력 추적local_history, local_event (DEBUG_LFCQ 아래)

CUBRID의 구현

섹션 제목: “CUBRID의 구현”

모양과 저장소

섹션 제목: “모양과 저장소”
// lockfree::circular_queue<T> — src/base/lockfree_circular_queue.hpp:46
template <class T>
class circular_queue {
public:
  using cursor_type        = std::uint64_t;
  using atomic_cursor_type = std::atomic<cursor_type>;
  using data_type          = T;
  using atomic_flag_type   = atomic_cursor_type;


  circular_queue (std::size_t size);
  ~circular_queue ();


  bool is_empty () const;           // 싼 스냅샷 — 오래된 값일 수 있음
  bool is_full () const;
  bool is_half_full ();
  std::size_t size ();


  bool consume (T &element);        // 비차단; 비면 false
  bool produce (const T &element);  // 비차단; 가득이면 false
  void force_produce (const T &element);  // 성공할 때까지 yield-loop
  std::uint64_t get_consumer_cursor ();


private:
  static const cursor_type BLOCK_FLAG;     // (cursor_type) 1 << 63


  data_type        *m_data;                // m_capacity 슬롯
  atomic_flag_type *m_blocked_cursors;     // m_capacity 플래그 워드
  atomic_cursor_type m_produce_cursor;     // 단조
  atomic_cursor_type m_consume_cursor;     // 단조
  std::size_t       m_capacity;            // 2의 거듭제곱
  std::size_t       m_index_mask;          // m_capacity - 1
};

생성자는 요청 크기를 다음 2의 거듭제곱으로 올린다.

circular_queue<T>::circular_queue (std::size_t size)
  : m_produce_cursor (0), m_consume_cursor (0)
{
  m_capacity   = next_pow2 (size);
  m_index_mask = m_capacity - 1;
  assert ((m_capacity & m_index_mask) == 0);
  m_data = new data_type[m_capacity];
  init_blocked_cursors ();
}


void init_blocked_cursors () {
  m_blocked_cursors = new atomic_flag_type[m_capacity];
  for (cursor_type c = 0; c < m_capacity; c++)
    m_blocked_cursors[c] = c;     // 초기 기대 값 = 슬롯 인덱스
}

슬롯 i의 초기 플래그 워드는 i — “커서 i에서 produce 준비, 블록 플래그 없음”이다. 첫 produce-unblock 사이클 이후 플래그는 i + capacity가 되고, 다음 사이클이면 i + 2*capacity가 된다. 이런 방식 으로 슬롯이 별도 세대 카운터 없이 자기 세대를 추적한다.

Produce — 프로토콜

섹션 제목: “Produce — 프로토콜”
// circular_queue<T>::produce — src/base/lockfree_circular_queue.hpp:230
bool produce (const T &element)
{
  while (true) {
    pc = load_cursor (m_produce_cursor);
    cc = load_cursor (m_consume_cursor);


    if (test_full_cursors (pc, cc))
      return false;                                 // QUEUE FULL


    did_block = block (pc);                         // 슬롯 pc claim 시도


    // 블록 성공 여부와 무관하게 produce 커서 bump
    test_and_increment_cursor (m_produce_cursor, pc);


    if (did_block) {
      store_data (pc, element);
      unblock (pc);                                 // 슬롯을 "consume 준비" 상태로
      return true;
    }
    // 누가 슬롯을 차지함; 루프
  }
}

네 단계 연산은 다음과 같다.

  1. 가득 검사. produce_cursor + 1 > consume_cursor + capacity ≡ consume_cursor + capacity <= produce_cursor. 싸다. 스냅샷 load 사용. 일시적 경쟁 상의 false-positive는 허용된다. 다음 루프 반복 이 다시 검사한다.
  2. 블록 플래그 CAS. 
    bool block (cursor_type cursor) {
      cursor_type block_val = flag<cursor_type> (cursor).set (BLOCK_FLAG).get_flags ();
      return m_blocked_cursors[cursor & m_index_mask]
        .compare_exchange_strong (cursor, block_val);
    }
    기대 값은 cursor(블록 플래그 없음, 세대 일치). 새 값은 cursor | BLOCK_FLAG. CAS는 (a) 슬롯 세대가 정확히 cursor이고 (b) 다른 프로듀서가 블록 비트를 set하지 않았을 때만 성공.
  3. 커서 bump. pc에서 pc + 1로 compare_exchange_strong. bump는 best-effort다. 경쟁하는 프로 듀서들 중 정확히 한 명이 성공한다. 이 한 명이 커서를 앞으로 미는 사람이며, 나머지는 결과를 무시한다. did_block이 슬롯 소유 여부 를 결정했고, 커서는 다음 루프 반복이 다시 load할 때 따라잡는다.
  4. Store + unblock. 
    void unblock (cursor_type cursor) {
      atomic_flag_type &ref = m_blocked_cursors[cursor & m_index_mask];
      flag<cursor_type> v = ref.load ();
      assert (v.is_set (BLOCK_FLAG));
      cursor_type next_gen = v.clear (BLOCK_FLAG).get_flags () + m_capacity;
      ref.store (next_gen);
    }
    unblock은 cursor + capacity(다음 세대 기대 값)을 플래그 워드에 쓴다. 이는 컨슈머에게 슬롯이 채워졌다고 알리고, 같은 슬롯 인덱스 에서 다음 세대 프로듀서가 무엇을 기대해야 하는지 알려준다.

Consume — 프로토콜

섹션 제목: “Consume — 프로토콜”
// circular_queue<T>::consume — src/base/lockfree_circular_queue.hpp:318
bool consume (T &element)
{
  while (true) {
    cc = load_cursor (m_consume_cursor);
    pc = load_cursor (m_produce_cursor);


    if (test_empty_cursors (pc, cc))
      return false;                                 // QUEUE EMPTY
    if (is_blocked (cc))
      return false;                                 // 첫 항목이 아직 produced 안 됨


    element = load_data (cc);                       // 잠정 복사


    if (test_and_increment_cursor (m_consume_cursor, cc))
      break;                                         // CONSUME COMPLETE
    // 경쟁 — 다른 컨슈머가 슬롯 가져감; 루프
  }
  return true;
}

세 단계 연산은 다음과 같다.

  1. 빈 + 블록 검사. pc <= cc이면 빈 상태. 비어 있지 않더라도 cc의 슬롯이 여전히 블록(프로듀서가 아직 unblock 안 함)이면, 이 호출에 대해서는 큐를 비어 있는 것으로 다루고 false를 반환한 다. 호출자가 나중에 다시 폴링하게 한다. 선점된 프로듀서 완화책 이다. 컨슈머는 멈춘 프로듀서를 기다리지 않는다. 빠져나와 호출자 가 재폴링하게 한다.
  2. 잠정 복사. 슬롯의 페이로드를 호출자 출력 인자로 읽는다. 커서 CAS가 실패하면(누가 먼저 consume) 호출자의 element가 부분적으로 덮어쓰였을 수 있다. 호출자는 false 반환에서 element를 신뢰 하지 않도록 문서화되어 있다.
  3. 커서 CAS. cc에서 cc + 1로 strong CAS. 이긴 스레드가 이 슬롯의 컨슈머다.

따라서 producer-and-consumer 프로토콜은 비대칭이다. 프로듀서들은 블록 플래그로 슬롯을 두고 싸우고, 컨슈머들은 커서 CAS로 커서 값 을 두고 싸운다.

상태 머신

섹션 제목: “상태 머신”
stateDiagram-v2
    [*] --> Initial : alloc, slot i flag = i
    Initial --> ProduceInProgress : block flag CAS i -> i\nset BLOCK_FLAG
    ProduceInProgress --> Produced : unblock\nflag = i + capacity
    Produced --> Consumed : consume cursor CAS\nadvance to i+1
    Consumed --> Initial : next generation\nslot reused at cursor i+capacity
    note right of ProduceInProgress
      컨슈머는 BLOCK_FLAG를 보고\n"empty"로 반환
    end note
    note right of Consumed
      슬롯이 cursor i+capacity의 대상이 됨
    end note

force_produce — yield-loop

섹션 제목: “force_produce — yield-loop”
void force_produce (const T &element) {
  while (!produce (element))
    std::this_thread::yield ();
}

가장 단순한 차단 프로듀서 래퍼. 지수 backoff도, 조건 변수도 없다. yield 후 재시도뿐이다. force_produce를 쓰는 큐는 빠르게 비도록 설계되었거나(vacuum의 finished-job 큐) 다른 곳에서는 가득 찼을 때 drop이 허용되기 때문에 받아들여지는 트레이드오프다.

명시된 한계 — 선점된 프로듀서

섹션 제목: “명시된 한계 — 선점된 프로듀서”

produce 소스 주석은 최악 시나리오를 명명한다.

// NOTE: I have an implementation issue I don't know how to fix
// without a significant overhead. When the queue is very stressed
// (many threads produce/consume very often), the system may preempt
// a thread while it has a slot blocked and may keep it preempted
// for a very long time (long enough to produce and consume an entire
// generation). I'd like to any blocking of any kind.
//
// One possible direction is to separate data storage (and slot index)
// from cursor. When one wants to produce an element, it first reserves
// a slot in storage, adds his data, and then saves slot index/cursor in
// what is now m_blocked_cursors using CAS operation. if this succeeds,
// produced data is immediately available for consumption. any
// preemption would not block the queue (just delay when the produce
// is happening).

주석이 설계의 미해결 이슈를 가리킨다. 현재 운영 동작은 다음과 같다. 슬롯의 BLOCK_FLAG를 들고 있는 선점된 프로듀서는 그 슬롯의 컨슈머 만 막지, 큐 전체를 막지는 않는다. 프로듀서 커서는 앞으로 가고, 다른 프로듀서가 뒤따르는 슬롯을 채우고, 다른 컨슈머가 그것들을 소비한다. 멈춘 단일 슬롯의 컨슈머는 첫 항목이 블록 상태, empty 반환 분기를 타고, 컨슈머 측은 다음으로 진행(또는 나중에 재시도)한다. 큐 전체 가 막히는 경우는 in-flight 프로듀서 모두가 동시에 선점되는 드문 경우뿐이다.

is_empty / is_full / size은 best-effort

섹션 제목: “is_empty / is_full / size은 best-effort”

공개 술어는 두 커서를 동기화하지 않는다. 각각을 독립적으로 스냅샷한 뒤 검사를 적용한다.

bool is_empty () const { return test_empty_cursors (m_produce_cursor, m_consume_cursor); }
bool is_full  () const { return test_full_cursors  (m_produce_cursor, m_consume_cursor); }
std::size_t size () {
  cursor_type cc = load_cursor (m_consume_cursor);
  cursor_type pc = load_cursor (m_produce_cursor);
  if (pc <= cc) return 0;
  return pc - cc;
}

호출자는 이를 조기 종료 힌트로 쓰도록 기대된다. 강한 정확성에는 의존하지 않는다. 헤더 주석이 이를 명시한다. 방금 is_full() == false 가 나온 큐에 대한 produce 호출도 형제 프로듀서에게 졌다면 false를 반환할 수 있다. 호출자 루프가 그것을 처리해야 한다.

선택적 실행 이력 추적 — DEBUG_LFCQ

섹션 제목: “선택적 실행 이력 추적 — DEBUG_LFCQ”

헤더는 DEBUG_LFCQ 아래에서 조건부로 컴파일되는 병렬 produce_debug / consume_debug / force_produce_debug 패밀리를 가진다. 각각이 프로토콜을 thread-local local_history 링 버퍼로 계측해, 모든 커서 load, 블록 CAS 시도, store, unblock을 local_event로 기록한다. 의도는 스트레스 벤치에서 멈춘 또는 잃어버린 항목 시나리오의 사후 디버깅이다. 프로덕션 빌드에서는 죽은 코드다.

소비자

섹션 제목: “소비자”
소유자타입 매개변수필드파일
Vacuum 블록 데이터 버퍼vacuum_data_entryvacuum_Block_data_buffersrc/query/vacuum.c:467
Vacuum 완료 작업 큐VACUUM_LOG_BLOCKIDvacuum_Finished_job_queuesrc/query/vacuum.c:475
CDC log-info 큐CDC_LOGINFO_ENTRY *cdc_Gl.loginfo_queuesrc/transaction/log_manager.c:14534
페이지 버퍼 고우선순위 waiter 큐THREAD_ENTRY *pgbuf_Pool.waiter_threads_high_prioritysrc/storage/page_buffer.c:741
페이지 버퍼 저우선순위 waiter 큐THREAD_ENTRY *pgbuf_Pool.waiter_threads_low_prioritysrc/storage/page_buffer.c:742
페이지 버퍼 post-flush 큐PGBUF_BCB *pgbuf_Pool.flushed_bcbssrc/storage/page_buffer.c:813
페이지 버퍼 사적 LRU victim 힌트int (LRU 인덱스)pgbuf_Pool.private_lrus_with_victimssrc/storage/page_buffer.c:815
페이지 버퍼 큰-사적 LRU victim 힌트intpgbuf_Pool.big_private_lrus_with_victimssrc/storage/page_buffer.c:816
페이지 버퍼 공유 LRU victim 힌트intpgbuf_Pool.shared_lrus_with_victimssrc/storage/page_buffer.c:817

대부분의 큐는 프로듀서 측에 force_produce(차단 수신)를 두고, 컨슈머 측에 consume(비차단 폴링, 데몬 looper에서 재시도)를 둔다.

왜 트랜잭션 회수가 없는가?

섹션 제목: “왜 트랜잭션 회수가 없는가?”

큐는 회수 척추 위에 없다. 항목당 동적 메모리를 할당하지 않는다 (슬롯이 m_data에 미리 할당). 포인터 형태 노드를 은퇴시키지 않는다. 커서 위에 ABA 위험이 없다(커서는 64비트 카운터이며 어떤 현실적인 가동시간에서도 wrap하지 않는다). tran::system / tran::table / tran::descriptor 기계가 여기엔 필요 없다.

트레이드오프: 큐의 페이로드 T는 값 복사 가능해야 한다. 실제로 CUBRID의 큐는 trivially-copyable 타입(int, THREAD_ENTRY *, PGBUF_BCB *, VACUUM_LOG_BLOCKID)이나 작은 POD 구조체를 저장한다. 더 큰 페이로드는 힙 할당하고 포인터를 enqueue해야 한다. CDC_LOGINFO_ENTRY * 큐가 그 예다.

소스 코드 가이드

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

공개 표면

섹션 제목: “공개 표면”
  • lockfree::circular_queue<T> — 클래스 템플릿, lockfree_circular_queue.hpp:46
  • circular_queue::circular_queue (size) — :208
  • circular_queue::~circular_queue — :222
  • circular_queue::is_empty / is_full / is_half_full / size — :373 / :381 / :387 / :394
  • circular_queue::consume — :318
  • circular_queue::produce — :230
  • circular_queue::force_produce — :301
  • circular_queue::get_consumer_cursor — :311

사적 헬퍼

섹션 제목: “사적 헬퍼”
  • next_pow2 — :409
  • test_empty_cursors / test_full_cursors — :419 / :425
  • load_cursor — :432
  • test_and_increment_cursor — :439 (커서 bump CAS. 주석에 따르면 weak vs strong은 perf 차이 없음)
  • get_cursor_index — :447
  • store_data / load_data — :454 / :461
  • is_blocked / block / unblock — :467 / :476 / :485
  • init_blocked_cursors — :498

디버그 변종 (DEBUG_LFCQ 아래)

섹션 제목: “디버그 변종 (DEBUG_LFCQ 아래)”
  • produce_debug — :511
  • force_produce_debug — :563
  • consume_debug — :572
  • local_history / local_event / local_action enum — :118+

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

섹션 제목: “위치 힌트 (2026-05-07 기준)”
심볼파일라인
lockfree::circular_queue<T> (클래스 템플릿)src/base/lockfree_circular_queue.hpp46
BLOCK_FLAG ((cursor_type) 1 << 63)src/base/lockfree_circular_queue.hpp80 / 203
circular_queue::circular_queuesrc/base/lockfree_circular_queue.hpp208
circular_queue::producesrc/base/lockfree_circular_queue.hpp230
circular_queue::force_producesrc/base/lockfree_circular_queue.hpp301
circular_queue::consumesrc/base/lockfree_circular_queue.hpp318
circular_queue::is_emptysrc/base/lockfree_circular_queue.hpp373
circular_queue::is_fullsrc/base/lockfree_circular_queue.hpp381
circular_queue::sizesrc/base/lockfree_circular_queue.hpp394
circular_queue::next_pow2src/base/lockfree_circular_queue.hpp409
circular_queue::blocksrc/base/lockfree_circular_queue.hpp476
circular_queue::unblocksrc/base/lockfree_circular_queue.hpp485
circular_queue::init_blocked_cursorssrc/base/lockfree_circular_queue.hpp498
circular_queue::test_and_increment_cursorsrc/base/lockfree_circular_queue.hpp439
vacuum_Block_data_buffersrc/query/vacuum.c467
vacuum_Finished_job_queuesrc/query/vacuum.c475
cdc_Gl.loginfo_queue 필드src/transaction/log_impl.h877
pgbuf_Pool.waiter_threads_high_prioritysrc/storage/page_buffer.c741
pgbuf_Pool.flushed_bcbssrc/storage/page_buffer.c813

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

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

검증된 사실

섹션 제목: “검증된 사실”
  • 용량은 다음 2의 거듭제곱으로 올림된다. next_pow2이 lockfree_circular_queue.hpp:409. 생성자가 (m_capacity & m_index_mask) == 0을 단언.
  • BLOCK_FLAG은 uint64_t의 최상위 비트다. :203에서 ((cursor_type) 1) << ((sizeof (cursor_type) * CHAR_BIT) - 1)로 정의. 64비트 커서에서는 0x8000_0000_0000_0000.
  • 커서 bump CAS는 compare_exchange_strong. :443의 주석은 “I tested, no performance difference from using one or the other” 로, 선택은 본질적이라기보다 방어적임을 시사한다.
  • 슬롯별 블록 플래그는 슬롯 인덱스로 초기화된다. init_blocked_cursors가 :498-507. 첫 세대는 flag = i인 슬롯 에서 produce하고, BLOCK_FLAG를 set한 뒤, flag = i + capacity로 unblock한다.
  • consume은 블록된 슬롯에서 기다리지 않는다. is_blocked (cc)이 true이면 consume은 :349에서 즉시 false 반환. 명시된 첫 항목이 아직 produced 안 됨 조기 종료다.
  • force_produce은 yield-loop. backoff 없음. :301-307.
  • 큐는 tran::* 회수 프레임워크를 쓰지 않는다. tran::reclaimable_node 없음, 디스크립터 브래킷 없음, 은퇴 링 없음. 슬롯은 m_data에 미리 할당.
  • 9개의 활성 인-엔진 소비자. §소비자 표 참고. grep -rn 'lockfree::circular_queue'로 확인.

풀리지 않은 질문

섹션 제목: “풀리지 않은 질문”
  1. 선점된 프로듀서 시나리오가 운영 환경에서 본 적 있는가? 소스 주석이 알려진 약점으로 명명한다. 조사: 스트레스 아래의 stuck-vacuum 또는 stuck-page-buffer 보고를 이슈 트래커에서 검색. 없다면 큐 끝 재사용 패턴이 경험적으로 최악 사례를 압도한다.
  2. force_produce에 backoff을 추가해야 하는가? 가득 찬 큐에 대한 빠른 std::this_thread::yield은 현대 Linux에서 놀라울 만큼 싸지만(다른 스레드가 그 CPU에서 runnable이 아니면 sched_yield는 no-op), 지수 backoff이 지속 압력 아래에선 더 쌀 것이다. 측정 캠페인이 없다.
  3. 컨슈머의 잠정 복사 패턴이 swap-then-CAS 보다 선호되는 이유는? 현재 컨슈머는 커서 CAS 전에 페이로드를 복사한다. CAS가 실패하면 잠정 복사는 낭비다. swap 패턴(CAS 먼저, 복사 나중)은 “consumed 되었지만 슬롯은 여전히 점유” 상태를 표시할 센티넬을 요구하며, 복잡성이 따로 있다. 현재 설계의 명시된 계약 — false 반환에서 element를 신뢰하지 말 것 — 이 의도된 단순화다.
  4. DEBUG_LFCQ 활성화 패턴. 추적은 스레드별 (local_history)이며, 주석에 따르면 호출자가 이력을 “thread context에 보관해서 필요할 때 검사”해야 한다. 최근에 누가 추적을 훈련한 적이 있는가? 듀얼 produce/consume 코드 경로는 프로덕션 경로가 디버그 경로와 동기화 없이 표류하면 유지 보수 위험이 된다.
  5. 64비트 커서 wrap. 초당 10억 enqueue(현재 어떤 부하보다도 훨씬 넘는)에서 uint64_t 커서는 ~580년 만에 wrap한다. 사실상 무한. 커서 산술 검사(pc <= cc, cc + capacity <= pc)는 wrap에서 오작동할 것이다. 완화책은 없다. 정확히 범위 밖으로 간주.

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

섹션 제목: “CUBRID 너머 — 비교 설계와 연구 프론티어”
  • Vyukov MPMC 큐. 현재 가장 깔끔한 운영 MPMC 링이다. 슬롯별 시퀀스 번호(별도 블록 플래그 없음), fetch-and-add 커서, 프로듀서 스톨 위험 없음. CUBRID의 vacuum과 페이지 버퍼 경로에 대한 직접 비교가 마이그레이션 비용에 비례하는 처리량을 사는지 알려줄 것이다.
  • LMAX Disruptor. batched claim(프로듀서가 한 CAS로 연속 N개 슬롯 claim 가능)과 대기 전략 정책(BlockingWait, BusySpin, Yielding, LiteBlocking)을 추가한다. CUBRID의 force_produce 은 yield로 하드 코딩되어 있다. 플러그블로 만들면 DWB는 차단을, 페이지 버퍼 victim 핸드오프는 busy-spin을 쓸 수 있다.
  • Folly의 ProducerConsumerQueue(SPSC 락프리)와 MPMCQueue. 광범위한 측정 이력을 가진 운영 등급. CUBRID 큐와 정신적으로 비슷 하다. API 차이는 사소하다(tryEnqueue, tryDequeue이 && perfect- forwarded 페이로드).
  • 프로듀서 스톨 위험 제거. 소스 주석이 제안하는 재설계 — 슬롯 예약과 커서 발행을 분리 — 이 정확히 Vyukov 알고리즘이다. 도입하면 큐가 프로듀서 쪽에서 wait-free가 된다.
  • 명시적 메모리 순서를 가진 std::atomic<T>. 오늘날 모든 커서와 플래그 접근은 seq_cst다. 프로듀서의 store-payload-then-unblock은 자연스러운 acquire/release 쌍이다. 약한 메모리 모델 아키텍처에서 배리어 오버헤드를 줄일 수 있다.

출처

섹션 제목: “출처”
  • 소스 파일 (CUBRID 소스 트리, /data/hgryoo/references/cubrid/):
    • src/base/lockfree_circular_queue.hpp (구현 전체. .cpp 동반자 없음)
    • src/base/base_flag.hpp (블록 비트를 인코딩하는 flag<T> 헬퍼)
  • 소비자 소스 파일:
    • src/query/vacuum.c
    • src/transaction/log_manager.c, src/transaction/log_impl.h
    • src/storage/page_buffer.c
  • 인용한 교과서 챕터:
    • Herlihy & Shavit, The Art of Multiprocessor Programming, 13장 §Concurrent Queues — bounded vs. unbounded, MS queue, fetch-and-add ring.
  • 기반 논문:
  • 본 저장소의 자매 분석서:
    • cubrid-lockfree-overview.md — 우산 문서.
    • cubrid-vacuum.md(있다면) — vacuum_Block_data_buffer와 vacuum_Finished_job_queue의 주요 소비자.
    • cubrid-page-buffer-manager.md — waiter와 victim 큐 소비자.