CUBRID Bestspace (차기 버전) — 샤딩 lock-free 여유 공간 인덱스

이론적 배경
일반적인 DBMS 설계
동기
CUBRID의 접근
소스 워크스루
교차 확인 노트
열린 질문
출처

이론적 배경

힙 파일은 INSERT마다 한 가지 질문에 답해야 한다. 이 레코드가 들어갈 만큼 여유 공간이 있는 페이지는 어느 것인가? 이것이 행 기반 저장의 여유 공간 관리(free-space management) 하위 문제다. 슬롯 페이지·레코드 식별자·forwarding 레코드·overflow 파일 같은 더 넓은 힙 기반은 cubrid-heap-manager.md §“Theoretical Background”에서 다룬다. 이 문서는 여유 공간 추적만 집중해서 본다.

Database Internals(Petrov, 3–4장)는 slotted page(슬롯 단위로 공간을 나눈 페이지)를 단위로 설명한다. 고정 헤더가 있고, 한쪽 끝에서 슬롯 디렉터리가 자라고, 반대쪽에서 레코드 본문이 자라며, 그 가운데에 여유 공간 틈이 있다는 것이다. 이 틈이 insert가 들어갈 수 있는 유일한 자리다. 그래서 “여유 있는 페이지 찾기”는 “여유 틈이 record_length + slot_overhead 이상인 페이지 찾기”로 줄어든다. 이것을 insert마다 힙 전체를 스캔해서 푸는 것은 감당할 수 없다. 그래서 어느 엔진이든 보조 여유 공간 구조 — 페이지와 그 대략적인 여유 공간을 담은 맵이나 캐시 — 를 두고 먼저 참조한다.

문제 자체에서 비롯되어 모든 구현을 좌우하는 성질이 셋 있다.

근사는 설계상 허용된다. 여유 공간 힌트는 오래되었을 수 있다. 기록된 뒤 다른 트랜잭션이 그 페이지를 채웠을 수 있기 때문이다. 잘못된 힌트의 대가는 헛된 페이지 fix — 페이지를 fix했다가 꽉 찬 걸 발견하고 다른 페이지를 시도 — 일 뿐, 데이터 오류가 아니다. 잘못된 힌트는 싸고 정확한 추적은 비싸기 때문에, 이 구조는 일부러 느슨하고 스스로 치유하도록 만든다.
재사용 대 성장. 삭제와 vacuum은 기존 페이지의 공간을 비운다. 새 insert에 늘 새 페이지만 할당하는 엔진은 대량 삭제된 테이블의 저장소를 새게 만든다. 반대로 비워진 바이트를 즉시 다 재사용하는 엔진은 방금 비운 페이지를 다시 더럽힌다. 그래서 구조는 어떤 페이지가 되돌려줄 만큼 충분히 비었는지를 언제 판단할지 정해야 한다. 엔진마다 다른 진입 정책이다.
동시성이 어려운 축이다. 여러 트랜잭션이 같은 테이블에 insert하면 여유 공간 구조는 insert마다 건드려진다. 이것이 하나의 공유 객체이고 래치 하나로 보호된다면, 그 구조가 직렬화 지점이 된다. 하드웨어 병렬성과 무관하게 엔진은 한 번에 한 행씩만 insert하게 된다. 그래서 설계의 긴장은 정확도 대 경합이다. 정밀하고 중앙에 모인 구조는 직렬화하고, 분산되고 근사한 구조는 확장되지만 오래된 값을 견뎌야 한다.

차기 버전 bestspace는 특히 3번 성질에 대한 응답이다. 레거시 CUBRID 설계는 정확하고 중앙 집중형이었는데, 재설계는 분산과 근사를 조금 더 받아들이는 대신 뜨거운 단일 래치를 없앤다.

일반적인 DBMS 설계

교과서는 모델을 준다. 이 절은 행 기반 엔진들이 여유 공간 추적에서 수렴하는 엔지니어링 관례를 짚는다. §“CUBRID의 접근”에 나오는 차기 버전 선택은 이 공유 공간 안의 다이얼 하나로 읽는 편이 낫지, 발명으로 볼 것은 아니다. (레거시 CUBRID 설계와 그 타사 대응물은 cubrid-heap-manager.md §“Common DBMS Design” → Free-space hint cache에도 요약되어 있다. 이 절은 재설계가 겨냥하는 동시성 축을 더 깊이 본다.)

구조는 전역이 아니라 객체별로 둔다

PostgreSQL은 여유 공간 맵(FSM, Free Space Map) 을 전역 맵 하나가 아니라 릴레이션 별로(별도 fork <relfilenode>_fsm) 둔다. Oracle은 여유 공간을 세그먼트별로 추적한다. 관례는 여유 공간 metadata를 테이블(또는 그 저장 세그먼트)이 소유해서, 상관없는 테이블끼리 경합하지 않게 하는 것이다. 레거시 CUBRID heap_Bestspace 캐시는 여기서 예외다. 모든 힙이 공유하는 프로세스 전역 해시 하나이며, 재설계가 바꾸는 두 가지 중 하나다.

여유 공간 요약을 계층으로 두면 “N 이상 여유 페이지 찾기”가 싸진다

PostgreSQL의 FSM은 FSM 페이지에 저장된 이진 트리다. 각 리프는 페이지 하나의 여유 공간을 1바이트로 양자화해(1/256 해상도) 담고, 각 내부 노드는 자식들의 최댓값을 담는다. 그래서 “N 이상 여유 페이지” 검색은 스캔 대신 O(log pages) 노드만 밟으며 트리를 내려간다. Oracle의 자동 세그먼트 공간 관리(ASSM, Automatic Segment Space Management) 는 옛 freelist를 비트맵 블록 계층 — L1, L2, L3 — 으로 대체했다. L1 블록은 데이터 블록 묶음의 채움 정도를 몇 가지 상태(예: 여유 0–25%, 25–50%, 50–75%, 75–100%)로 추적하고, L2 블록은 L1 블록을, L3 블록은 L2 블록을 인덱싱한다. 되풀이되는 아이디어는 이렇다. 여유 공간 등급으로 키를 잡은 다단계 요약을 두면 검색이 짧은 하강이 된다. CUBRID의 차기 버전 bestspace는 바로 이 모양 — 여유 공간 tier로 키를 잡은 3단계(L3/L2/L1) 비트맵 — 을 채택하며, 이름도 ASSM을 일부러 따라 붙인 것이다.

여유 공간은 바이트 단위가 아니라 굵은 등급으로 묶는다

FSM(1/256)도 ASSM(네다섯 채움 상태)도 여유 공간을 정확히 추적하지 않는다. “충분히 큰가?”를 페이지를 fix하지 않고 답하기에는 굵은 등급이면 충분하고, 그래야 요약이 작아진다(등급당 비트맵 비트 하나). 그다음 엔진은 고른 페이지를 fix해 진짜 여유 공간을 읽고, 그 과정에서 추정치를 고친다. CUBRID의 tier FS0..FS8(아홉 개의 여유 공간 등급)이 이 관례다.

진입 문턱으로 여유가 거의 없는 페이지를 걸러낸다

95% 찬 페이지는 삽입자에게 내놓을 가치가 없다. 레코드가 안 들어갈 가능성이 높고, 그걸 인덱싱하면 구조만 요동친다. 그래서 엔진은 문턱을 둔다. PostgreSQL FSM은 한 양자 아래 페이지를 사실상 무시하고, 레거시 CUBRID는 단일 30% 문턱(HEAP_DROP_FREE_SPACE) 을 썼다. 차기 버전 설계도 문턱을 두되 이를 tier로 표현한다. 페이지는 tier ≥ FS3 (약 25%)일 때만 재사용 candidate로 추천된다.

경합 회피는 일등 목표다 — freelist 교훈

정석적인 경고담은 Oracle의 옛 freelist다. 세그먼트 헤더에 매달린, 여유 블록들의 링크드 리스트였다. 동시 insert 아래에서 이것이 뜨거운 블록이 되었다. 모든 삽입자가 세그먼트 헤더에서 직렬화된 것이다. Oracle의 해법은 먼저 FREELIST GROUPS (freelist를 독립된 N개 리스트로 샤딩)였고, 끝내는 ASSM(리스트를 블록별 비트맵으로 대체해, 공유하는 가변 head 없이 삽입자가 세그먼트에 흩어지게 함)이었다. 교훈은 일반화된다. 여유 공간 구조는 insert 경로에 가변 단일 직렬화 지점을 가져서는 안 된다. 차기 버전 CUBRID 설계는 두 해법을 한꺼번에 적용한다. 샤딩(freelist groups 처럼)과 lock-free 비트맵(ASSM처럼)을, 레거시 형태가 힙 헤더 래치에서 직렬화하던 설계에 적용하는 것이다.

이론 ↔ CUBRID 대응

여유 공간 개념	PostgreSQL	Oracle	CUBRID (차기 버전)
객체별 소유	릴레이션별 FSM fork	세그먼트별	`(class_oid, HFID)`별 `bestspace`
다단계 요약	FSM 이진 트리	ASSM L1/L2/L3 비트맵 블록	`L3`/`L2`/`L1` 메모리 비트맵
여유 공간 등급	1/256 바이트 양자	4–5개 채움 상태	9개 tier `FS0..FS8`
진입 문턱	한 양자	세그먼트 `PCTFREE`	tier ≥ FS3 (candidate)
경합 해법	릴레이션별 격리	FREELIST GROUPS + ASSM	샤딩 + lock-free CAS
재사용 예비	FSM이 비운 페이지 재표시	ASSM 비트맵	candidates 큐

동기

힙 헤더 래치 병목

CUBRID의 레거시 여유 공간 선택은 insert 페이지 검색 전체를 힙 헤더 페이지로 몰아넣는데, 그것도 작업 내내 WRITE 래치를 건 채로 처리한다. 레거시 heap_stats_find_best_page (cubrid-heap-manager-detail.md 9장에서 해부)를 보면, 어떤 추정치를 건드리기 전에 헤더를 PGBUF_LATCH_WRITE로 fix하고 단 하나의 출구에서야 푼다. 추정치 갱신, 힌트 스캔, 제한된 재동기화, 심지어 페이지 할당까지 모두 그 한 래치 아래에서 일어난다. 이 불변식이 두 삽입자가 head / best[] 링을 망가뜨리는 것을 막지만, 동시에 그들을 직렬화한다.

best space를 찾기 위해 삽입 경로 대부분이 힙 헤더 페이지에 WRITE 래치를 걸고 있다. 이 구조는 한 번에 한 스레드만 insert할 수 있게 하는 병목 지점이 된다. — CBRD-26176 (한국어 원문 요약)

여러 트랜잭션이 같은 테이블에 insert하면 헤더 페이지 하나가 뜨거운 단일 래치가 되고, 동시성은 힙당 사실상 한 번에 한 삽입자 수준으로 무너진다. CBRD-26806이 더 넓게 추적하는 “중앙 집중형 metadata 경합” 패턴이자, §“일반적인 DBMS 설계”의 freelist 교훈 그 자체다.

대체되는 레거시 구조 (기준선)

레거시 설계는 두 계층으로 된, 근사적이고, 로깅하지 않는 힌트 시스템이다(전체 내용: heap-manager-detail 9장). 기준선으로서 핵심만 적으면 이렇다.

디스크 힌트는 힙 헤더의 estimates 하위 구조체에 있다. HEAP_BESTSPACE {VPID; int freespace;} 형태의 best[10] 링, second_best[10] 예비 링, head 커서, 집계 카운터들이다.
메모리 캐시 heap_Bestspace는 HFID+VPID로 키를 잡는 프로세스 전역 해시다. PRM_ID_HF_MAX_BESTSPACE_ENTRIES로 크기가 제한되고, bestspace_mutex로 보호되며, 모든 힙이 공유한다.
heap_stats_find_best_page 가 헤더 WRITE 래치 아래에서 지휘한다. 캐시 그다음 디스크 링을 스캔하고(바쁜 페이지는 LK_FORCE_ZERO_WAIT로 건너뜀), 마르면 heap_stats_sync_bestspace(페이지의 min(20%, 100)개를 다시 걷는 제한된 재구축)를, 그다음 heap_vpid_alloc을 쓴다.
HEAP_DROP_FREE_SPACE = 30%가 유일한 진입 문턱이다. second_best는 치환 1000번마다 밀려난 페이지 하나를 받아들여 쓰기를 분산시킨다.
정확성을 위해 로깅하는 것은 아무것도 없다. 잘못된 힌트의 대가는 기껏해야 헛된 페이지 fix 한 번이다.

근사적이고 스스로 치유되며 크래시에 견딘다는 장점은 정신을 그대로 이어받는다. INSERT-heavy 부하에서 치명적인 약점 — 전역 캐시 하나에 힙별 헤더 래치를 선택 과정 내내 거는 것 — 이 바로 재설계가 겨냥하는 지점이다.

상태와 범위

이 문서는 PR #7353 — [CBRD-26176] bestspace (작성자 hyahong, base develop, head 브랜치 CBRD-26858)를 분석한다. 작성 시점에 이 PR은 draft이며 아직 develop에 머지되지 않았다. 즉 이 분석은 의도적으로 머지보다 앞선다. 여기 나오는 모든 심벌, 라인 힌트, 구조체 필드는 PR head 커밋 81061660a5 기준이며 PR이 머지되기 전에 달라질 수 있다(§“교차 확인 노트” 참고). 이 작업은 EPIC CBRD-26857(Sharded Lock-free Bestspace Index) 아래에 있다. 설계 하위 과제 CBRD-26858이 Oracle과 PostgreSQL의 여유 공간 관리를 조사했고(§“일반적인 DBMS 설계”의 출처), CBRD-26176이 이 구현이며, 완료 기준은 INSERT-heavy 부하에서의 측정된 처리량 증가다.

CUBRID의 접근

차기 버전 bestspace는 새 C++ 번역 단위 src/storage/bestspace.{hpp,cpp}에 있으며 네임스페이스는 cubstorage다. 전역 캐시와 헤더 링을, 힙 파일마다 따로 두는 샤딩된 lock-free 인덱스에 candidate 큐와 지속 스냅샷을 더한 것으로 대체한다.

한눈에 보는 설계

세 겹으로 중첩된 구조에 전역 registry가 더해진다.

그림 1 — bestspace 구조 계층

그림 1: 네 개의 구조 계층. registry는 힙 파일을 그 bestspace로 해석하고, bestspace는 페이지를 샤드로 흩뿌리며 후보 페이지의 concurrent 큐를 갖는다. 각 샤드는 64개 페이지 슬롯을 두 요약 계층으로 인덱싱하는 3단계 비트맵이다.

핵심을 떠받치는 아이디어들을, §“일반적인 DBMS 설계”의 관례에 대응해 정리하면 이렇다.

힙 파일 단위 격리. bestspace는 (class_oid, HFID)마다 존재한다 — 객체별 관례다. 두 테이블이 경합할 일이 없다.
샤딩. 각 bestspace는 bestspace_shard_count개(기본 8, 1–28)의 샤드를 갖는다 — freelist-groups 해법이다.
샤드 내부는 lock-free. 모든 노드(L1, L2, L3)는 64바이트로 정렬된 std::atomic 안의 8바이트 값이며 compare_exchange_strong으로 갱신된다. static_assert가 lock-free임과 캐시라인 크기임을 강제한다(false sharing 없음) — ASSM 해법이다.
tier로 나눈 여유 공간. 아홉 개 tier FS0..FS8가 단일 30% 문턱을 대체한다 — 굵은 등급 관례다.
candidate 재활용. concurrent 큐가 방금 여유 공간을 얻은 페이지를 인덱스에 되먹인다 — 재사용 예비 관례다.
지속시키되, 저렴하게. 압축된 형태(샤드 수, L1 엔트리, 후보 목록)를 힙 헤더와 전용 페이지 몇 장에 지속시키고 재시작 뒤 필요할 때 다시 만든다.

자료구조: tier와 3단계 비트맵

bestspace_entry — 페이지 하나의 힌트다. lock-free 원자 워드에 들어가도록 정확히 8바이트로 패킹되어 있다.

// bestspace_entry — src/storage/bestspace.hpp
struct bestspace_entry
{
  std::uint16_t freespace;   // 여유 바이트 (offset 0)
  short         volid;       // (offset 2)
  int32_t       pageid;      // (offset 4)
};
static_assert (sizeof (bestspace_entry) == 8, "bestspace_entry must be 8 bytes");

freespace를 맨 앞에 둔 것은 의도적이다. L1 리프가 같은 레이아웃을 공유하므로, 페이지를 로드 한 번으로 여유 공간 기준 사전 필터링할 수 있다.

그림 2 — bestspace_entry의 8바이트 레이아웃

그림 2 — 8바이트 페이지 힌트. freespace가 맨 앞 2바이트를 차지한다는 점이 핵심이다. L1 리프가 이 레이아웃을 그대로 공유하기 때문에, 페이지를 fix하기 전에 원자 로드 한 번으로 여유 공간을 미리 걸러낼 수 있다.

tier FS0–FS8 — size_to_tier는 바이트 수를 페이지 대비 백분율로 보고 아홉 등급 중 하나로 매핑한다.

tier	여유 공간	역할
`FS0` (−1)	1–7%	인덱싱하기엔 너무 작음 — 비트맵 비트를 절대 못 받음
`FS1` (0)	8–15%
`FS2` (1)	16–24%
`FS3` (2)	25–34%
`FS4` (3)	35–45%
`FS5` (4)	46–57%
`FS6` (5)	58–70%
`FS7` (6)	71–84%
`FS8` (7)	85–100%	(거의) 빈 페이지
`FSEND` (8)	—	루프 센티널

// bestspace::size_to_tier — src/storage/bestspace.cpp
static constexpr std::int16_t threshold[] = { 7, 15, 24, 34, 45, 57, 70, 84 };
percentage = size * 100 / DB_PAGESIZE;
for (i = 0; i < (int) tier::FS8 + 1; i++)
  if (percentage <= threshold[i])
    return static_cast<tier> (i - 1);   // FS0..FS7
return tier::FS8;

FS1..FS8 범위(8개 tier)는 정확히 바이트 크기 비트맵의 8비트에 대응한다. 구조 자체가 이 대응 위에 세워져 있다.

그림 3 — FS0–FS8 여유 공간 tier

그림 3 — 아홉 개의 여유 공간 tier. size_to_tier는 페이지 대비 여유 비율로 등급을 나눈다. FS0은 인덱싱하기엔 너무 작고, candidate로 받아들이는 문턱은 FS3(약 25%)에 있다. 인덱싱되는 여덟 tier FS1..FS8은 바이트 크기 비트맵의 여덟 비트와 1:1로 대응한다.

L1 — 리프 (페이지 하나). bestspace_entry와 같은 8바이트 레이아웃이며, 64바이트 atomic_wrapper<L1>에 담겨 샤드 안 64개 슬롯이 각자 자기 캐시라인에 앉는다.

// bestspace::L1 — src/storage/bestspace.hpp  (접근자 생략)
class L1 {
  std::uint16_t m_freespace;
  short         m_volid;
  int32_t       m_pageid;
};
static_assert (sizeof (L1) == 8 && std::atomic<L1>::is_always_lock_free, "...");

L2와 L3 — 요약 비트맵. 각각 8바이트 값 = std::array<bitmap, 8>이며, tier FS1..FS8마다 1바이트 비트맵을 하나씩 둔다.

L2[k] 는 그룹 k의 8개 L1 슬롯을 요약한다. FSt 비트맵의 비트 j는 L1[k*8 + j]가 tier FSt에 있을 때 켜진다.
L3 는 8개 L2 그룹을 요약한다. FSt 비트맵의 비트 k는 그룹 k에 tier FSt인 페이지가 하나라도 있을 때 켜진다.

한 샤드는 L3_FANOUT (8) × L2_FANOUT (8) = 64개 페이지(ENTRIES_PER_SHARD)를 인덱싱한다. tier FSt 검색은 L3 워드 하나를 읽어(그 tier의 페이지가 있는 그룹), 그다음 후보 그룹마다 L2 워드 하나를 읽고(어느 슬롯), 그 L1 리프들만 본다. 요약 로드 두 번에 리프 몇 개다. 8개 tier 전체에서 tier 비트 하나를 지우는 것은 마스크된 64비트 쓰기 한 번이다(val &= ~(0x0101010101010101ULL << index)).

그림 4 — 3단계 비트맵

그림 4 — 한 샤드가 64개 페이지를 인덱싱하는 방식. L3은 여덟 개 L2 그룹으로, 각 그룹은 다시 여덟 개 L1 리프로 뻗어 나간다(8 × 8 = 64). L2/L3 워드 하나는 tier별로 쌓인 여덟 개의 1바이트 비트맵이다. 한 워드 안에서 FSt 바이트의 비트 j는 자식 j가 tier FSt의 페이지를 가짐을 뜻한다. 그래서 tier t 검색은 요약 로드 두 번에 리프 읽기 몇 번이면 된다.

shard와 bestspace — 담는 그릇:

// bestspace::shard — src/storage/bestspace.hpp  (필드, 압축)
class alignas (64) shard {
  atomic_wrapper<bool> m_allocating;               // 단일 할당자 게이트
  atomic_wrapper<L3>   m_L3;
  atomic_wrapper<L2>   m_L2[L3_FANOUT];             // 8
  atomic_wrapper<L1>   m_L1[L3_FANOUT * L2_FANOUT]; // 64
  std::atomic<std::uint64_t> m_recs_num, m_recs_sumlen;
  bestspace           &m_parent;
  struct { /* 샤드별 디버그 통계 */ } m_stats;
};
static_assert (sizeof (shard) == 4800 && alignof (shard) == 64, "...");

// bestspace — src/storage/bestspace.hpp  (필드, 압축)
class bestspace {
  std::deque<shard>                        m_shards;       // shard_count개
  tbb::concurrent_queue<bestspace_entry>   m_candidates;   // 재활용 큐
  std::uint16_t                            m_unfill_space; // 힙별 갱신 여유분
};

샤드 하나는 4800바이트이고, 기본 8개 샤드를 가진 bestspace는 인덱스만 약 38 KB에 후보 큐가 더해진다. 힙 파일이 열릴 때마다 한 번 치르는, 클래스별·샤드별 설계의 메모리 비용이다.

find 경로 — lock-free 하강

bestspace::find는 INSERT가 호출하는 핫패스다. 레코드 크기를 주면, 이미 인덱스에 공간을 예약한 채로, 여유가 있는 fix된 WRITE 래치 페이지를 돌려준다.

// bestspace::find — src/storage/bestspace.cpp  (제어 흐름, 압축)
consume_space = size + SPAGE_SLOT_SIZE;                 // 레코드가 실제로 쓰는 양
needed_space  = consume_space + m_unfill_space;         // + 갱신 여유분
if (needed_space > heap_nonheader_page_capacity ())
  needed_space = consume_space;                          // 여유분이 결코 안 맞으면
while (true) {
  for (i = 0; i < m_shards.size (); i++) {
    error = m_shards[(shard + i) % m_shards.size ()]
              .find (class_oid, hfid, needed_space, consume_space, bias, page_watcher);
    if (error == FOUND)   return NO_ERROR;
    if (error == FAILURE) return er_errid ();
    // else ALLOCATING: 이 샤드는 할당 중, 다음 샤드로
  }
  // 모든 샤드가 ALLOCATING: yield / 짧은 sleep, 인터럽트 확인, 재시도
}

두 개의 요청 크기가 아래로 함께 전달된다. needed_space(레코드 + 슬롯 + unfill_space 여유분)는 tier 적격성을 정하고, consume_space(레코드 + 슬롯만)는 성공 시 페이지의 기록된 여유 공간에서 빼는 양이다. unfill_space 예약분은 나중의 in-place 갱신이 페이지를 옮기지 않고 커질 자리를 남겨 둔다.

샤드 안에서 하강은 L3_find → L2_find → L1_find다.

flowchart TD
  A["shard::find(needed_size)"] --> B["minimum = size_to_tier(needed_size);\nminimum &lt; FS8 이면 minimum++"]
  B --> C["L3_find: tier t를 minimum부터 FS8까지\nL3 로드, t인 페이지가 있는 그룹 나열"]
  C --> D["L2_find: 후보 그룹마다\nL2 로드, tier t인 L1 슬롯 나열"]
  D --> E["L1_find: L1 슬롯 로드"]
  E --> F{"기록된 freespace\n>= needed_size?"}
  F -- 아니오 --> C
  F -- 예 --> G["페이지 ordered_fix\n(LK_FORCE_ZERO_WAIT)"]
  G -- 타임아웃 --> H["CONTENDED: 이 페이지 건너뜀"]
  G -- 잘못된 pageid --> I["스테일: L1_remove, 롤업"]
  G -- 성공 --> J{"아직 이 클래스? 실제\nspage 여유 >= needed?"}
  J -- 아니오 --> I
  J -- 예 --> K["CAS로 L1 freespace -= consume_size\nL2_update / L3_update 롤업"]
  K --> L["FOUND: fix된 페이지 반환"]

그림 5: 샤드 내부 하강. minimum은 딱 맞는 tier보다 한 단계 올려, 고른 페이지가 요청을 넉넉히 넘도록 한다. 첫 tier가 비었으면 검색은 더 풍부한 tier로 계속 위로 걷는다.

미묘하지만 핵심적인 세부사항들:

여유를 위해 한 tier 올림. minimum = size_to_tier(needed_size) 뒤 minimum++(이미 FS8이면 그대로). 더 풍부한 tier에서 고르면 간신히 맞는 페이지에 반복해서 걸리는 것을 피한다.
공정성을 위한 bias (뼈대만 있고, head에서는 비활성). 이 구조는 각 계층에서 pos[(i + bias) % length]로 쓰이는 bias와 회전하는 시작 샤드를 함께 실어 나른다. 그러면 같은 비트맵을 하강하는 동시 삽입자들이 첫 슬롯 하나로 몰리지 않는다. 그러나 head 81061660a5에서 bestspace::find는 shard = 0; bias = 0;을 한 번 설정하고 이후로 전혀 올리지 않는다. 그래서 이 몰림 방지 회전은 코드에는 있지만 아직 켜져 있지 않다. PR이 진행되면 다시 확인할 만한 부분이다.
기록된 여유 공간은 거짓일 수 있다. L1_find는 먼저 원자 freespace 워드로 사전 필터링한다. 그것을 통과할 때만 페이지를 fix해 spage_max_space_for_new_record 로 진짜 값을 읽는다. 진짜 값이 모자라면 L1 워드를 CAS로 고치고(그 수정을 L2/L3로 롤업) NOT_FOUND를 반환한다. 레거시의 “다시 확인하고 고친다”를 그대로 반영한, 스스로 치유하는 동작이다.
소유권 확인. fix한 뒤 그 페이지가 여전히 PAGE_HEAP이고 여전히 class_oid에 속하는지 확인한다. 아니면 엔트리를 제거한다. 인덱싱된 이후 그 페이지가 해제되어 다른 곳에서 재사용됐을 수 있기 때문이다.
경합은 대기가 아니라 건너뛰기다. L1_fix는 pgbuf_ordered_fix를 LK_FORCE_ZERO_WAIT와 함께 쓴다. 래치 타임아웃은 블록이 아니라 CONTENDED(다음 후보로)가 된다. 레거시가 쓰던 비차단 규율과 같지만, 이제는 그 위에 헤더 래치가 전혀 없다.
CAS로 예약. 성공하면 이긴 스레드가 그 페이지의 L1 freespace를 consume_size만큼 CAS로 내린다. 페이지를 fix했고 여전히 같은 VPID를 보는 스레드만 갱신하므로, 구조는 lock-free여도 예약은 슬롯당 단일 기록자다.
어디서나 pgbuf_ordered_fix. 경로 전체가 ordered fix를 쓰므로 여러 페이지 래치가 데드락에 빠질 수 없다 — PR이 명시적으로 고친 부분이다(“bestspace 경로의 데드락을 피하려고 ordered fix 사용”).

어느 샤드도 페이지를 못 내놓고 아무 샤드도 할당 중이 아니면, 바깥 루프가 yield하고 (20번 스핀 뒤에는 10 µs sleep) 재시도하며 인터럽트를 존중한다. 할당 중인 샤드는 ALLOCATING을 반환하고 호출자는 그냥 다음으로 넘어간다. 할당이 find를 막는 일은 없다.

allocate 경로 — victim, candidate, 신규 페이지

샤드의 하강이 여유 있는 페이지를 못 찾으면 shard::find가 allocate를 호출한다. 인덱스를 다시 채우는 곳이다. 가장 빈약한 슬롯을 내보내고 더 나은 페이지를 설치하되, 새로 할당한 저장소보다 재활용된 candidate를 먼저 쓴다.

flowchart TD
  A["shard::allocate(consume_size)"] --> B{"allocate_mark:\nm_allocating false를 true로 CAS"}
  B -- 이미 켜짐 --> Z["ALLOCATING: 호출자는\n다음 샤드로"]
  B -- 성공 --> C["allocate_pick_victims:\n여유 공간이 가장 적은 L1 슬롯 4개\n(resident VPID도 스냅샷)"]
  C --> D["allocate_pick_candidates:\ncandidates 큐에서 pop,\n가장 풍부한 victim보다 더 나은 것만 유지,\nresidents 대비 중복 제거  (최대 3)"]
  D --> E["allocate_new_pages:\n나머지는 heap_alloc_new_pages\n(ALLOC_BATCH_SIZE = 4 묶음)"]
  E --> F["호출자용 페이지 하나 예약\n(candidate[last].freespace -= consume_size)"]
  F --> G["allocate_replace_pages:\n새 엔트리를 victim L1 슬롯에 저장,\nL2_update / L3_update 롤업"]
  G --> H["allocate_unmark; FOUND"]

그림 6: 샤드 다시 채우기. 한 번에 샤드당 할당자 하나(m_allocating 게이트)이며, 나머지는 그동안 다른 샤드를 계속 검색한다.

샤드당 할당자 하나. allocate_mark는 m_allocating에 대한 CAS다. 지면 곧바로 ALLOCATING을 반환하므로, 값비싼 할당 작업이 샤드 사이에서 중복되거나 직렬화되지 않는다.
네 개 묶음. ALLOC_BATCH_SIZE == 4. 샤드는 할당마다 가장 약한 슬롯을 최대 네 개까지 새로 채운다. 세 개는 무조건, 네 번째(victim 중 가장 풍부한 것)는 교체분이 그것을 이길 때만이다. 비용을 분산하고 하나가 아니라 여러 개의 새 페이지를 남긴다.
할당보다 재활용. allocate_pick_candidates는 네 victim 중 가장 풍부한 것보다 더 나은 페이지를 찾아 candidates 큐를 비운다(MAX_POP_TRIES 상한과 resident 대비 중복 제거). 부족분에 대해서만 allocate_new_pages가 배치 원시 함수 heap_alloc_new_pages로 새 저장소를 할당한다. 가장 큰 victim이 이미 매우 풍부하면 (>= FS8) candidate 고르기를 건너뛴다. 뒤섞느니 깨끗한 페이지를 할당하는 편이 낫기 때문이다.
전진 보장. allocate_new_pages는 배치를 채우는 데 필요한 페이지를 항상 최소 하나는 할당하므로, allocate는 쓸 수 있는 페이지를 최소 하나(마지막 것, 호출자용 예약분) 가지고 반환한다.

candidates 큐와 페이지 재활용

candidates 큐(tbb::concurrent_queue<bestspace_entry> m_candidates)는 “이 페이지가 방금 여유 공간을 얻었다”의 새 자리다. 레거시의 second_best 예비 링을 lock-free MPMC 큐로 대체한다.

생산자. 공간을 비우는 어떤 경로든 heap_add_bestpage(thread_p, hfid, page, prev_freespace)로 그 페이지를 추천한다. 이 함수는 레거시 heap_stats_update의 직접 대체물이며, 같은 종류의 호출 지점들에 연결되어 있다. vacuum의 공간 회수, 물리적 레코드 삭제 경로 (heap_delete_physical), 그리고 insert의 복구 undo(heap_rv_undo_insert)다. candidate는 재구축 시 힙 헤더에서도 들어온다.
진입 문턱(tier FS3). heap_add_bestpage는 페이지의 여유 공간이 tier FS3 (약 25%)에 도달할 때만 큐에 넣는다. 레거시 30% HEAP_DROP_FREE_SPACE의 tier 기반 대응물이다.
소비자. allocate만 큐를 비우고, 그것도 필요한 만큼만(MAX_POP_TRIES) 비운다. 그래서 페이지 수천 장을 비우는 대량 vacuum이라도 그만큼의 인덱스 요동을 강제하지 않는다. 페이지는 어떤 샤드가 실제로 다시 채울 때까지 기다린다. 레거시의 1000에 1 쓰기 분산을, 샘플링 카운터가 아니라 구조로 이룬 새 대응물이다.
중복 제거. allocate는 VPID가 이미 샤드에 있는 candidate는 건너뛴다.

registry와 스레드 로컬 캐시

bestspace는 삽입마다 (class_oid, HFID)로 찾아야 하므로 조회 자체가 새 병목이 되어서는 안 된다. bestspace_registry(전역 싱글턴 cubstorage::bestspaces)는 뮤텍스로 보호되는 전역 리스트 앞에 스레드별 캐시를 세운 구조다.

// bestspace_registry::find — src/storage/bestspace.cpp
bestspace *bestspace_registry::find (OID *class_oid, HFID *hfid) {
  bestspace *entry = find_from_cache (class_oid, hfid);  // 스레드 로컬, 락 없음
  if (entry) return entry;
  return find_from_global (class_oid, hfid);             // std::mutex, 그다음 캐싱
}

스레드 로컬 우선. 각 스레드는 최근 쓴 (class_oid, HFID) → bestspace* 엔트리를 최대 TLS_MAX_SIZE (20)개까지 LRU 리스트로 갖는다. 히트하면 락 없이 앞으로 옮긴다.
generation 스탬프 무효화. registry는 원자 m_generation을 갖고 destroy가 이를 올린다. 다음 find에서 캐싱된 generation이 다른 스레드는 자기 스레드 로컬 리스트 전체를 비교 한 번으로 무효화한다. 삭제된 테이블에 스테일 캐시 포인터로 닿는 일은 결코 없다.
뮤텍스로 전역 폴백. 미스는 registry 뮤텍스를 잡고 전역 리스트에서 엔트리를 찾은 뒤, 뮤텍스를 풀고, 그 포인터를 스레드 로컬 캐시에 설치한다.
수명주기. create는 힙 파일의 bestspace가 처음 필요하거나 만들어질 때, destroy(class_oid, vfid|hfid)는 힙 파일이 삭제될 때 호출된다 (vacuum_rv_notify_dropped_file → bestspaces.destroy 참고).

뮤텍스는 콜드 조회와 수명주기 이벤트에서만 건드린다. 정상 상태의 삽입은 힙 파일을 전적으로 스레드 로컬 메모리에서 해석한다.

그림 7 — registry와 스레드 로컬 캐시

그림 7 — 힙 파일을 그 bestspace로 해석하는 과정. 스레드 로컬 LRU 캐시가 흔한 경우를 락 없이 처리한다. 미스가 나면 registry 뮤텍스를 잡아 전역 리스트에서 찾은 뒤, 그 포인터를 다시 캐시에 설치한다. destroy가 올리는 원자 m_generation 덕분에 스레드 로컬 리스트 전체가 비교 한 번으로 버려지므로, 삭제된 테이블에 스테일 포인터로 닿는 일이 없다.

디스크 지속성과 복구

메모리 인덱스는 파생 상태지만, 재시작마다 전체 힙 스캔으로 다시 만드는 것은 너무 비싸다. 그래서 압축된, 재구성 가능한 형태를 지속시킨다. 힙 헤더의 옛 estimates 블록은 사라지고 그 자리에 bestspace 하위 구조체가 들어온다.

// heap_hdr_stats — src/storage/heap_file.c  (차기 버전, 압축)
struct heap_hdr_stats {
  OID   class_oid;
  VFID  ovf_vfid;
  VPID  next_vpid, last_vpid;
  int   unfill_space;
  int   num_pages;  uint64_t num_recs;  uint64_t recs_sumlen;  // 집계 추정치 유지
  struct {
    int  num_candidates;
    cubstorage::bestspace_entry candidates[128];  // 대기 candidate, 인라인으로 지속
    int  num_shards;
    int  num_pages;
    VPID pages[4];                                 // 최대 4장의 전용 저장 페이지
  } bestspace;
  int reserve0, reserve1, reserve2;
};

집계 카운터는 살아남는다. num_pages, num_recs, recs_sumlen은 평균 레코드 크기 추정에 쓰려고 헤더에 남는다(estimates에서 승격됨). best[10] / second_best[10] 링과 커서들은 통째로 삭제된다.
직렬화된 L1 엔트리. 샤드들의 num_shards × 64개 L1 엔트리는 최대 네 장의 전용 힙 페이지(bestspace.pages[4])로 직렬화되며, 각 페이지는 HEAP_PAGE_FLAG_BESTSPACE 로 표시된다. 헤더 보조 함수(heap_create_bestspace, heap_update_bestspace)가 할당·기록·갱신한다.
인라인 candidate. 대기 candidate는 최대 128개까지 헤더에 보관된다 (candidates[128], num_candidates). heap_bestspace_add_candidate / heap_bestspace_clear_candidates가 관리한다.
로깅되는 갱신. 디스크 엔트리 갱신은 새 복구 인덱스 RVHF_UPDATE_BESTSPACE_ENTRIES(redo 핸들러 heap_rv_redo_update)로 redo 로깅된다. 레거시 힌트와 달리 지속 형태는 복구에 참여하므로, 재구축된 인덱스가 일관된 스냅샷에서 출발한다.
필요할 때 재구축. 메모리 bestspace가 없으면(첫 접근 또는 재시작 이후) heap_build_bestspace가 헤더를 읽고 저장 페이지에서 엔트리·candidate를 로드한 뒤 bestspaces.create(class_oid, hfid, entries, num_entries, candidates, num_candidates, num_shards, unfill_space)를 호출한다. compactdb는 지속 형태를 갱신한다.

그림 8 — 디스크 지속성과 재구축

그림 8 — 지속되는 형태. 힙 헤더는 집계 추정치, 최대 128개의 인라인 candidate, 그리고 전용 저장 페이지를 가리키는 최대 네 개의 VPID를 담는다. 그 저장 페이지들은 HEAP_PAGE_FLAG_BESTSPACE로 표시되며 직렬화된 L1 엔트리를 담고, 갱신은 RVHF_UPDATE_BESTSPACE_ENTRIES로 redo 로깅된다. 재시작 뒤에는 heap_build_bestspace가 메모리 인덱스를 다시 만들고, 힙 스캔은 표시된 페이지를 건너뛰어 metadata를 레코드로 읽지 않는다.

L1 엔트리와 candidate가 실제 힙 페이지에 살기 때문에, 힙 스캔은 이들을 건너뛰어야 한다. 술어 heap_page_is_bestspace()(HEAP_PAGE_FLAG_BESTSPACE로 뒷받침됨)는 metadata 페이지를 레코드 페이지로 취급하면 안 되는 약 15개 힙 스캔 지점에서 확인된다. 예로 병렬 힙 스캔(px_scan_input_handler_heap)과 파티션 재분배 (redistribute_partition_data)가 있으며, 이들은 bestspace 저장 페이지를 지나쳐 나아간다.

통합 지점

새 파일 두 개 말고도 PR #7353은 약 20개 파일을 건드린다.

영역	파일	변경
시스템 파라미터	`system_parameter.c/.h`	새 `bestspace_shard_count`(`PRM_ID_BESTSPACE_SHARD_COUNT`, 서버, 사용자 변경 가능, 기본 8, 최소 1, 최대 28). `PRM_ID_HF_MAX_BESTSPACE_ENTRIES`는 `PRM_OBSOLETED` 표시.
Vacuum	`vacuum.c`	비운 페이지를 `heap_add_bestpage`로 추천. 삭제 시 `cubstorage::bestspaces.destroy(class_oid, vfid)`.
병렬 스캔	`px_scan_input_handler_heap.cpp`	`heap_page_is_bestspace`가 참인 페이지 건너뜀.
파티셔닝	`locator_sr.c`	`redistribute_partition_data`가 bestspace 저장 페이지 건너뜀.
Slotted page	`slotted_page.c/.h`, `storage_common.h`	`need_update_best_hint` 헤더 비트, `spage_set_need_update_best_hint`, `spage_get_free_space_without_saving`의 `need_update` out 파라미터, `HEAP_PAGE_INFO_UPDATE_BEST` 제거.
SHOW meta	`show_meta.c`	`SHOW HEAP HEADER`가 `Estimates_*` 컬럼 집합 전체를 버리고 `Last_vpid`, `Unfill_space`, `Num_pages`, `Num_recs`, `Avg_rec_len`을 노출. slotted-header show는 `Need_update_best_hint` 제거.
복구	`recovery.c/.h`	새 `RVHF_UPDATE_BESTSPACE_ENTRIES = 130`(`RV_LAST_LOGID` 상향).
힙 API	`heap_file.h`	`HEAP_DROP_FREE_SPACE`, `HEAP_BESTSPACE`, `heap_stats_update` 제거. `heap_add_bestpage`, `heap_alloc_new_pages`(배치), `heap_page_is_bestspace` 추가.
빌드	`CMakeLists.txt` (×2)	`bestspace.cpp` 컴파일. TBB 링크.

heap_file.c 자체(약 2600/2770 줄 재작성) 안에서는, 레거시 heap_stats_* 관련 코드 (heap_stats_find_page_in_bestspace, heap_stats_sync_bestspace, heap_stats_put/get_second_best, heap_Bestspace)가 제거되고, 새 heap_find_bestpage / heap_find_bestspace / heap_build_bestspace 계층이 cubstorage::bestspaces에 위임한다.

레거시 대 차기 버전

차원	레거시 `heap_Bestspace`	차기 버전 `cubstorage::bestspace`
범위	모든 힙에 대한 프로세스 전역 해시 하나	힙 파일마다(`class_oid`, HFID) 구조 하나
동시성 제어	선택 과정 내내 힙 헤더 WRITE 래치 + 전역 `bestspace_mutex`	샤딩, lock-free(64B 정렬 원자 값에 대한 노드별 CAS). 뮤텍스는 registry 콜드 패스에서만
병렬 단위	힙당 한 번에 삽입자 하나	힙당 독립 샤드 `bestspace_shard_count`개(기본 8)
인덱스 구조	전역 해시 + 디스크 `best[10]` / `second_best[10]` 링	샤드당 64개 슬롯에 대한 3단계 비트맵(`L3`/`L2`/`L1`)
여유 공간 등급	30% 문턱 하나(`HEAP_DROP_FREE_SPACE`)	9개 tier(FS0–FS8)
페이지 재사용	`second_best` 예비 링, 1000에 1 진입	lock-free candidates 큐, 필요 시 비움
공급원	삭제/갱신/vacuum → `heap_stats_update`	삭제 / vacuum / insert-undo → `heap_add_bestpage`(candidate, ≥ FS3)
조회 비용	뮤텍스 아래 해시 프로브, 그다음 헤더 래치 아래 디스크 링	스레드 로컬 registry 히트(락 없음) → 샤드 비트맵 하강
지속성	헤더 `estimates` 링, 로깅 안 함	헤더 하위 구조체 + 전용 페이지, redo 로깅(`RVHF_UPDATE_BESTSPACE_ENTRIES`)
복구	스테일 힌트, 다음 삽입이 재동기화	`heap_build_bestspace`로 지속 스냅샷에서 재구축
튜닝 파라미터	`bestspace_max_entries`(이제 obsolete)	`bestspace_shard_count`(1–28)
스캔 상호작용	힌트가 일반 페이지를 참조	저장 페이지에 `HEAP_PAGE_FLAG_BESTSPACE` 표시, 스캔이 건너뜀

둘 다 여전히 근사적이다. 기록된 여유 공간이 틀릴 수 있고, 코드는 진짜 페이지를 다시 확인해 스스로 치유한다. 바뀐 것은 정확도가 아니라 조율이 어디서 일어나는가다. 중앙에서 래치를 건 헤더 링에서, 분산된 lock-free 클래스별 인덱스로 옮겨 간 것이다.

소스 워크스루

역할별로 묶은 심벌들.

새 여유 공간 인덱스(src/storage/bestspace.hpp, src/storage/bestspace.cpp):

cubstorage::bestspace_entry — 8바이트 페이지 힌트.
bestspace::tier, bestspace::size_to_tier — FS0–FS8 tier 나누기.
bestspace::bitmap, bestspace::L1, bestspace::L2, bestspace::L3 — 3단계 비트맵과 그 리프.
bestspace::atomic_wrapper<T> — 64바이트 정렬 lock-free 래퍼.
bestspace::shard와 그 메서드: find, L3_find/L2_find/L1_find, L1_fix/L1_remove, L2_update/L3_update, allocate, allocate_mark/allocate_unmark, allocate_pick_victims, allocate_pick_candidates, allocate_new_pages, allocate_replace_pages, initialize_by_entries.
bestspace(최상위): find, initialize_by_entries, add_candidates, pop_candidate, size_to_tier, show_stats.
bestspace_registry와 cubstorage::bestspaces: find, find_from_cache/find_from_global, create(×2), destroy(×2), TLS_cache, m_generation.

힙 관리자 통합(src/storage/heap_file.c, heap_file.h):

heap_find_bestpage — 핫패스 진입점: 힙 파일 → bestspace로 해석한 뒤 bestspace::find 호출.
heap_find_bestspace, heap_build_bestspace — registry에서 찾거나 빌드.
heap_create_bestspace, heap_update_bestspace, heap_update_bestspace_chain — 디스크 형태를 지속/갱신.
heap_bestspace_add_candidate, heap_bestspace_clear_candidates — 헤더 candidate 목록.
heap_add_bestpage — 페이지를 candidate로 추천(삭제 / vacuum / insert-undo 경로. tier ≥ FS3에서만 큐에 넣음).
heap_alloc_new_pages — 샤드의 allocate가 쓰는 배치 페이지 할당자.
heap_page_is_bestspace — HEAP_PAGE_FLAG_BESTSPACE에 대한 술어.
heap_hdr_stats.bestspace — 헤더 하위 구조체.

그 밖의 파일: PRM_ID_BESTSPACE_SHARD_COUNT(system_parameter.c); RVHF_UPDATE_BESTSPACE_ENTRIES(recovery.h); px_scan_input_handler_heap.cpp와 locator_sr.c의 heap_page_is_bestspace 호출 지점.

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

라인 힌트는 PR #7353 head 81061660a5(CBRD-26858 브랜치) 기준이며, develop이 아니다. base 브랜치와는 맞지 않고 PR이 바뀌면 흔들린다. 심벌 이름을 기준점으로 삼으라.

심벌	파일	라인 (PR head `81061660a5`)
`bestspace_entry`	`src/storage/bestspace.hpp`	49
`bestspace::tier` (enum)	`src/storage/bestspace.hpp`	83
`bestspace::shard` (class)	`src/storage/bestspace.hpp`	237
`bestspace` (class)	`src/storage/bestspace.hpp`	69
`bestspace_registry`	`src/storage/bestspace.hpp`	357
`bestspace::shard::find`	`src/storage/bestspace.cpp`	302
`bestspace::shard::L3_find`	`src/storage/bestspace.cpp`	341
`bestspace::shard::L1_find`	`src/storage/bestspace.cpp`	490
`bestspace::shard::L1_fix`	`src/storage/bestspace.cpp`	574
`bestspace::shard::allocate`	`src/storage/bestspace.cpp`	789
`bestspace::shard::allocate_pick_candidates`	`src/storage/bestspace.cpp`	680
`bestspace::find`	`src/storage/bestspace.cpp`	892
`bestspace::size_to_tier`	`src/storage/bestspace.cpp`	986
`bestspace_registry::find`	`src/storage/bestspace.cpp`	1150
`bestspace_registry::find_from_cache`	`src/storage/bestspace.cpp`	1163
`cubstorage::bestspaces` (전역)	`src/storage/bestspace.cpp`	1345
`RVHF_UPDATE_BESTSPACE_ENTRIES`	`src/transaction/recovery.h`	187
`heap_page_is_bestspace` (선언)	`src/storage/heap_file.h`	(추가됨)
`heap_add_bestpage` (선언)	`src/storage/heap_file.h`	(추가됨)
`heap_alloc_new_pages` (선언)	`src/storage/heap_file.h`	(추가됨)

교차 확인 노트

이 문서는 미머지 draft를 분석하므로 일반적인 버전 드리프트 주의점에 더해 그 상태 특유의 몇 가지가 있다.

라인 힌트는 PR 브랜치, develop이 아니다. 위치 힌트 표는 브랜치 CBRD-26858의 head 81061660a5에 고정되어 있다. PR이 머지(squash)되면 라인 번호가 모두 바뀐다. 머지 커밋 기준으로 다시 확인하고 다시 고정해야 한다.
heap_file.c 라인 힌트는 뺐다. 힙 쪽 통합 심벌은 이름만 적고 라인은 고정하지 않았다. 그 파일은 아직 유동적인 약 2600/2770줄 재작성이라, 다음 force-push 때 심벌별 라인이 낡을 것이기 때문이다. PR이 안정될 때까지 심벌 이름을 기준으로 삼으라.
bias/round-robin 뼈대는 head에서 비활성이다. bestspace::find가 shard = 0; bias = 0으로 고정하므로, §“find 경로”에서 설명한 몰림 방지 회전은 있지만 켜져 있지 않다. 나중 커밋이 이를 연결하면 “분산은 할당 중이라 건너뛴 샤드에서만 생긴다”는 서술이 낡는다.
레거시 대조는 9장에 고정. 레거시 기준선과 비교 표는 cubrid-heap-manager-detail.md 9장을 그 문서의 updated: 시점으로 교차 확인한 것이다. 그 문서가 바뀌면 비교 표를 다시 확인하라.
printf를 통한 show_stats. 디버그 통계가 stdout으로 출력되고 registry 소멸자가 클래스별 통계를 출력한다. 머지 전에 바뀌거나 제거될 개발 시점 계측이므로, 안정적인 관측 수단으로 다루지 말 것.
ASSM L1/L2/L3 비유는 예시이지 코드 공유 주장이 아니다. §“일반적인 DBMS 설계”의 Oracle ASSM 비유는 설계 계열 관찰(채움 정도로 키를 잡은 블록별 비트맵 계층)이지, CUBRID가 Oracle 구조를 이식했다는 주장이 아니다.

열린 질문

성능 검증이 남아 있다. CBRD-26176의 완료 기준 — INSERT-heavy 부하에서 측정된 부하 분산과 처리량 증가 — 이 변경의 요점이지만 이 정적 분석이 확인할 수 있는 것은 아니다. bestspace_shard_count에 따라 어떻게 확장되는지는 벤치마크가 필요하다.
샤드 수 튜닝과 마이그레이션. 기본 8, 최대 28. 무엇이 선택을 이끄는가 — 코어 수, 테이블별 삽입 동시성, 메모리(샤드당 약 4800 B)? 재구축 시 heap_build_bestspace는 샤드 수를 지속된 bestspace.num_shards가 아니라 라이브 파라미터에서 가져온다(지속된 값은 L1 엔트리를 몇 개 역직렬화할지만 정하고, 남는 엔트리는 candidate 큐로 흘러 들어간다). 그래서 파라미터 변경 후 재시작하면 힙은 새 샤드 수를 채택한다.
candidate 큐와 헤더 candidates[128] 오버플로. 생산자가 allocate를 앞지르면 concurrent 큐가 무제한으로 커지는가? 지속 시점에 128개를 넘는 대기 candidate는 어떻게 처리되는가?
메모리 사용량. 기본 샤드 수에서 열린 힙 파일당 class_oid+HFID마다 약 38 KB 다. obsolete된 bestspace_max_entries에 해당하는 전역 상한이 없다. 테이블/파티션이 많은 스키마라면 합계를 측정할 만하다.
lock-free 롤업의 복구 정확성. L2_update/L3_update의 CAS 재시도 루프는 동시 변경 아래에서 요약을 다시 만든다. 진행 중인 allocate와 크래시 사이의 상호작용은 코드가 안정된 뒤 따져 볼 만하다.
Direct I/O와의 상호작용. CBRD-26176은 CBRD-26141 [POC] Direct I/O 지원의 regression of로 연결되어 있다. bestspace 페이지 I/O가 버퍼드 의미를 가정하는지는 여기서 미해결이다.

출처

PR / 이슈.
- PR #7353 [CBRD-26176] bestspace — head 81061660a5, base develop(draft).
- CBRD-26857 [EPIC] — 힙 파일 여유 공간(best space) 관리 구조 개선 (Sharded Lock-free Bestspace Index).
- CBRD-26858 [조사/설계] — 타사 여유 공간 정책 조사 및 개선 설계 (Oracle freelist/ASSM, PostgreSQL FSM); §“일반적인 DBMS 설계”의 바탕이 된 조사.
- CBRD-26176 — 다수 트랜잭션 동시 INSERT 시 best space 정책 성능 병목 해결.
- 관련: CBRD-26806 (중앙 집중형 metadata 경합 분석), CBRD-26141 ([POC] Direct I/O).
소스 (PR head 81061660a5). src/storage/bestspace.{hpp,cpp}, src/storage/heap_file.{c,h}, src/storage/slotted_page.{c,h}, src/storage/storage_common.h, src/query/vacuum.c, src/query/parallel/px_scan/px_scan_input_handler_heap.cpp, src/transaction/locator_sr.c, src/transaction/recovery.{c,h}, src/base/system_parameter.{c,h}, src/parser/show_meta.c.
교과서. Petrov, Database Internals, 3–4장 (slotted page, 여유 공간) — ../../research/dbms-general/ 캡처 참고.
관련 KB 문서. cubrid-heap-manager.md (힙 기초, 여유 공간 의도), cubrid-heap-manager-detail.md 9장 (레거시 bestspace 구조 전체), cubrid-lockfree-overview.md (CUBRID의 lock-free 구성 요소), cubrid-disk-manager.md (페이지 할당).