CUBRID Extendible Hash — 코드 수준 심층 분석

이 문서의 위치: 상위 분석 문서인 cubrid-extendible-hash.md는 설계 의도와 이론적 배경을 다룬다. 이 문서는 모든 분기와 필드를 코드 수준에서 추적한다. 각 챕터는 독립적으로 읽을 수 있지만, 순서대로 읽으면 해시 키 유도부터 디렉터리 조회, 버킷 연산, 분할 기반 디렉터리 더블링까지 하나의 키가 흘러가는 전체 흐름을 따라갈 수 있다.

목차:

Ch	제목	상태
1	자료구조 지도	✅
2	파일 생성과 메모리 레이아웃	✅
3	해싱과 디렉터리 주소 결정	✅
4	버킷 내부 탐색	✅
5	여유 있는 버킷에 삽입하기	✅
6	꽉 찬 버킷 분할과 로컬 깊이 증가	✅
7	디렉터리 두 배 확장과 버킷 포인터 연결	✅
8	키 삭제와 버킷 병합	✅
9	디렉터리 축소	✅
10	엣지 경로 복구와 동시성	✅

Chapter 1: 자료구조 지도

이 챕터가 답하는 질문은 하나다: extendible hash 파일의 디스크 상 구조는 정확히 어떻게 생겼고, 각 필드는 무슨 역할을 하는가? 구조체 목록, 바이트를 해석하는 매크로, 나머지 코드가 전제하는 불변 조건, 그리고 논리적 포인터 인덱스를 물리적 (page, offset)으로 변환하는 유일한 함수 ehash_dir_locate까지 — 이 챕터는 그 모든 것의 인벤토리다.

Fagin 이론, 디렉터리 배증 직관, CUBRID의 네 가지 호출 지점은 상위 수준 문서인 cubrid-extendible-hash.md에 있으며 여기서는 반복하지 않는다. 심볼 출처는 src/storage/extendible_hash.c, src/storage/storage_common.h, src/compat/dbtype_def.h다.

1.1 디스크 핸들: `EHID`, `VFID`, `VPID`

모든 것은 storage_common.h에 선언된 12바이트 핸들에서 시작한다:

// ehid -- src/storage/storage_common.h
struct ehid
{
  VFID vfid;     /* Volume and Directory file identifier */
  INT32 pageid;  /* The first (root) page of the directory */
};

EHID는 파일 id가 아니다 — (디렉터리 파일, 그 파일 안의 루트 페이지) 쌍이다. 내장된 VFID는 디렉터리 파일을 가리키고, pageid는 그 파일 안에서 헤더가 위치한 페이지 번호다. 버킷 파일에 접근하려면 헤더 내부 필드를 거쳐야 하며(§1.2), EHID에서 직접 도달할 수 없다.

// vpid / vfid -- src/compat/dbtype_def.h
struct vpid { int32_t pageid; short volid; };  /* a page: page# + which volume */
struct vfid { int32_t fileid; short volid; };  /* a file: file# + which volume */

구조체	필드	역할	존재 이유
`EHID`	`vfid`	디렉터리 파일의 `VFID`	파일 id로 디렉터리 파일을 재오픈할 때 사용; 루트 페이지가 이 파일 안에 있다
`EHID`	`pageid`	`vfid` 안에서 디렉터리 루트 페이지의 번호	단일 진입점: 이 페이지를 fix하면 offset 0에서 헤더에 접근할 수 있다
`VFID`	`fileid`	볼륨 내 파일 번호	파일 관리자에게 파일을 식별시킨다
`VFID`	`volid`	파일이 위치한 볼륨	`(volid, fileid)` 조합이 전역적으로 유일하다
`VPID`	`pageid`	볼륨 내 페이지 번호	페이지 버퍼가 특정 페이지를 식별하는 데 사용
`VPID`	`volid`	페이지가 위치한 볼륨	`(volid, pageid)`가 `pgbuf_fix`가 사용하는 전역 페이지 주소다

불변 조건 — EHID는 유일한 내구성 루트다. 모든 탐색은 ehid->vfid의 ehid->pageid 페이지를 fix하는 것으로 시작한다; 파일 어디에도 EHID를 가리키는 역방향 포인터는 없다. 호출자가 EHID를 직접 영속화해야 한다. EHID를 잃으면 페이지는 살아있어도 파일이 고아 상태가 된다.

1.2 디렉터리 헤더: `EHASH_DIR_HEADER`

첫 번째 디렉터리 페이지는 고정된 헤더로 시작하고, 나머지 공간과 이후 모든 페이지에는 디렉터리 포인터가 채워진다.

// ehash_dir_header -- src/storage/extendible_hash.c
struct ehash_dir_header
{
  /* Fields should be ordered according to their sizes */
  VFID bucket_file;
  VFID overflow_file;
  int local_depth_count[EHASH_HASH_KEY_BITS + 1];
  DB_TYPE key_type;
  short depth;
  char alignment;
};

EHASH_HASH_KEY_BITS는 sizeof(EHASH_HASH_KEY) * 8이고 typedef unsigned int EHASH_HASH_KEY이므로, 유일하게 지원되는 설정에서 32다 (마스킹 매크로에 TODO: ~0: M2 64-bit 주석이 달려 있다). 따라서 local_depth_count는 33개 항목을 가지며 0..32로 인덱싱된다.

필드	역할	존재 이유
`bucket_file`	모든 (비 overflow) 버킷 페이지를 보관하는 파일의 `VFID`	디렉터리와 버킷이 독립적으로 성장할 수 있도록 별도 파일에 분리; 디렉터리 항목은 이 파일 내 `VPID`를 저장한다
`overflow_file`	overflow 버킷 페이지를 보관하는 파일의 `VFID`	긴 문자열 키와 드문 충돌은 별도 파일의 overflow 페이지로 흘러 넘친다
`local_depth_count[i]`	현재 local depth가 `i`인 버킷 수를 세는 히스토그램	O(1) 축소 판단 기준; `ehash_adjust_local_depth`가 점진적으로 유지 관리
`key_type`	해싱되는 키의 `DB_TYPE` (예: `DB_TYPE_STRING`, `DB_TYPE_OBJECT`)	해시 함수, 비교, slot 인코딩 방식을 결정; 모든 버킷에 동일하게 적용
`depth`	디렉터리의 전역 깊이 d	`2^depth`개의 논리 포인터를 노출; `FIND_OFFSET`이 정확히 `depth`개의 상위 비트를 마스킹한다(§1.5)
`alignment`	버킷 페이지의 slot 정렬 단위	slotted 버킷 페이지 레코드의 정렬 기준; 생성 시점에 고정되고 복구 시 재사용된다

필드 순서는 내부 패딩 없이 구조체가 정렬되도록 크기 내림차순으로 배치했으며, 이후 EHASH_DIR_HEADER_SIZE(§1.4)로 올림 처리된다.

불변 조건 — local_depth_count는 충실한 히스토그램이고, 전역 깊이는 모든 로컬 깊이를 지배한다. local_depth_count[i]는 EHASH_BUCKET_HEADER.local_depth == i인 버킷 수를 센다; 모든 split/merge는 ehash_adjust_local_depth로 깊이 변경을 처리한다(이전 값 감소, 새 값 증가, 하나의 로그 액션). 별도로, 모든 버킷은 local_depth <= header.depth를 만족한다: depth를 초과할 split이 필요하면 먼저 디렉터리를 배증해야 한다(Chapter 6–7). 히스토그램이 틀어지면 축소 폭을 잘못 계산하고, local depth가 전역 깊이를 넘으면 잘못된 버킷으로 alias된다.

1.3 디렉터리 항목과 버킷 헤더: `EHASH_DIR_RECORD`, `EHASH_BUCKET_HEADER`

디렉터리 항목은 버킷 포인터 그 자체다:

// ehash_dir_record -- src/storage/extendible_hash.c
struct ehash_dir_record { VPID bucket_vpid; };  /* bucket pointer */

구조체	필드	역할	존재 이유
`EHASH_DIR_RECORD`	`bucket_vpid`	이 슬롯이 가리키는 버킷 페이지의 `VPID`	디렉터리는 이 항목들의 배열이다; `2^depth`개이며 여러 항목이 동일한 버킷을 가리킬 수 있다 — local depth < global depth 상태가 이런 방식으로 표현된다

local depth L의 버킷은 정확히 2^(depth - L)개의 연속된 디렉터리 슬롯에서 동일한 bucket_vpid로 참조된다. 각 버킷 페이지는 1바이트 헤더로 시작한다:

// ehash_bucket_header -- src/storage/extendible_hash.c
struct ehash_bucket_header { char local_depth; };  /* The local depth of the bucket */

구조체	필드	역할	존재 이유
`EHASH_BUCKET_HEADER`	`local_depth`	버킷의 local depth (버킷이 구별하는 pseudo-key 상위 비트 수)	slotted 버킷 페이지의 slot 0에 저장; split 시 형제 버킷의 깊이를 설정하고 어느 디렉터리 슬롯을 재지정할지 산출하는 데 쓰인다

불변 조건 — 버킷 헤더는 slot 0을 점유한다. local_depth 바이트는 slotted 버킷 페이지의 레코드 slot 0이다; 키/값 레코드는 slot 1..n에 위치한다. 버킷 스캔(Chapter 4)은 slot 1에서 시작하고; split/merge는 slot 0에서 깊이를 읽고 쓴다. slot 0에 데이터를 쓰면 local depth와 그것에서 파생되는 모든 디렉터리 폭 계산이 파괴된다.

1.4 페이지 기하 매크로

이 매크로들은 위의 구조체들을 페이지 레이아웃으로 변환한다. DB_PAGESIZE는 설정된 페이지 크기다(일반적으로 16 KB). 필드를 직접 담은 두 매크로는 그대로 보여주고, 나머지 네 가지 파생 카운트/오프셋은 아래 표에 요약했다.

// EHASH_DIR_HEADER_SIZE / EHASH_MAX_STRING_SIZE -- src/storage/extendible_hash.c
#define EHASH_DIR_HEADER_SIZE \
  ((ssize_t) (((sizeof(EHASH_DIR_HEADER) + sizeof(int) - 1 ) / sizeof(int) ) * sizeof(int)))
  /* <- round header size up to a multiple of sizeof(int) (4) */
#define EHASH_MAX_STRING_SIZE \
  (DB_PAGESIZE - (SSIZEOF(EHASH_BUCKET_HEADER) + 16))   /* <- 16 = two slot indices */

매크로	값	존재 이유
`EHASH_DIR_HEADER_SIZE`	`sizeof(EHASH_DIR_HEADER)`를 4바이트 경계로 올림	page 0의 포인터가 이 오프셋에서 시작; `VPID` 항목의 int 정렬을 보장
`EHASH_MAX_STRING_SIZE`	`DB_PAGESIZE - (1 + 16)`	inline으로 저장 가능한 최대 문자열 키 길이; 이를 초과하면 overflow로 이동. `16`은 두 slot 항목을 위해 예약
`EHASH_NUM_FIRST_PAGES`	`(DB_PAGESIZE - EHASH_DIR_HEADER_SIZE) / sizeof(VPID)`	첫 번째 페이지(헤더와 공유)에 들어가는 포인터 수
`EHASH_NUM_NON_FIRST_PAGES`	`DB_PAGESIZE / sizeof(VPID)`	이후 모든 페이지(헤더 없음)에 들어가는 포인터 수

동반 매크로 EHASH_LAST_OFFSET_IN_FIRST_PAGE와 EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE는 expand/shrink 시의 페이지 간 순회를 위해 각 페이지 종류에서 마지막 포인터의 바이트 오프셋을 제공한다.

불변 조건 — 디렉터리는 페이지에 걸쳐 스트라이핑된 하나의 논리 배열이다. 논리적으로 EHASH_DIR_RECORD dir[2^depth]다. 처음 EHASH_NUM_FIRST_PAGES개 항목은 헤더 이후 page 0에 위치하고, 이후 각 페이지는 EHASH_NUM_NON_FIRST_PAGES개를 보유한다. 어떤 항목도 페이지 경계를 걸치지 않는다 — 두 카운트 모두 가용 바이트 안에서 VPID 크기의 배수로 나누어 < sizeof(VPID) 나머지를 패딩으로 남긴다. k번째 항목이 필요한 모든 소비자는 ehash_dir_locate(§1.6)를 호출하며, 어느 코드도 평탄한 주소를 가정하지 않는다.

1.5 비트 필드 매크로 — 좌측 정렬 접두 비트 추출

pseudo-key는 32비트 unsigned int이며, 디렉터리는 MSB 쪽에서 depth개의 상위 비트를 사용한다. 비트 위치는 왼쪽(MSB)에서 1..32로 번호를 매긴다. 모든 추출은 GETBITS를 통한다:

// GETBITS -- src/storage/extendible_hash.c
#define GETBITS(value, pos, n) \
  ( ((value) >> ( EHASH_HASH_KEY_BITS - (pos) - (n) + 1)) & (~(~0UL << (n))) )
  /* shift the wanted field down to bit 0, then mask off the low n bits */

~(~0UL << n)는 n비트 하위 마스크를 만들고, shift 32 - pos - n + 1은 pos 위치 폭 n의 필드를 bit 0으로 내린다(부호 없는 value이므로 우측 시프트는 0으로 채워진다). 동작 예: value = 0xC0000000, pos = 1, n = 3 → shift 29, 0xC0000000 >> 29 = 6 — 깊이 3 디렉터리에서의 인덱스다.

// FIND_OFFSET / GETBIT / SETBIT / CLEARBIT -- src/storage/extendible_hash.c
#define FIND_OFFSET(hash_key, depth) (GETBITS((hash_key), 1, (depth)))         /* leading `depth` bits */
#define GETBIT(word, pos)            (GETBITS((word), (pos), 1))               /* one bit at pos */
#define SETBIT(word,  pos) ( (word) | (1 << (EHASH_HASH_KEY_BITS - (pos))) )   /* set bit pos to 1 */
#define CLEARBIT(word, pos) ( (word) & ~(1 << (EHASH_HASH_KEY_BITS - (pos))) ) /* clear bit pos to 0 */

매크로	반환값 / 효과	존재 이유
`FIND_OFFSET(h, d)`	`h`의 상위 `d`비트로 만든 정수	깊이 `d`에서 pseudo-key `h`에 해당하는 디렉터리 인덱스 — 주소 지정 함수
`GETBIT(w, pos)`	`pos`의 단일 비트 (0 또는 1)	split 시 레코드가 어느 형제 버킷으로 가는지 판별 (이전 local depth 바로 다음 비트)
`SETBIT(w, pos)`	`pos` 비트를 1로 강제한 `w`	구별 비트를 1로 설정한 형제 디렉터리 인덱스
`CLEARBIT(w, pos)`	`pos` 비트를 0으로 강제한 `w`	구별 비트를 0으로 설정한 형제 인덱스; `(CLEARBIT, SETBIT)` 쌍이 두 형제를 구성

불변 조건 — 하위 비트가 아닌 상위 비트. CUBRID는 상위 depth비트(MSB에서 1번으로 시작하는 좌측 정렬 방식)를 추출한다 — 하위 비트를 마스킹하는 교과서 방식과 반대다. 모든 매크로에 EHASH_HASH_KEY_BITS - pos가 하드코딩되어 있으며, 여기에 하위 비트 마스크를 혼용하면 하나의 키가 두 슬롯으로 향해 데이터가 손실된다. Chapter 3에서 이 매크로들을 기반으로 주소 지정 체계를 구축한다.

1.6 포인터 인덱스를 페이지로 변환: `ehash_dir_locate`

ehash_dir_locate는 “디렉터리는 스트라이핑된 하나의 배열”이라는 불변 조건의 함수 형태다: *out_offset_p로 논리 포인터 인덱스를 받아, 두 출력을 물리적 (page_no, byte_offset)으로 덮어쓴다:

// ehash_dir_locate -- src/storage/extendible_hash.c
static void
ehash_dir_locate (int *out_page_no_p, int *out_offset_p)
{
  int page_no, offset;
  offset = *out_offset_p;                          /* <- input: logical pointer index */
  if (offset < EHASH_NUM_FIRST_PAGES)
    {                                               /* branch A: page 0, after the header */
      offset = offset * sizeof (EHASH_DIR_RECORD) + EHASH_DIR_HEADER_SIZE;
      page_no = 0;
    }
  else                                              /* branch B: a later page, no header */
    {
      offset -= EHASH_NUM_FIRST_PAGES;
      page_no = offset / EHASH_NUM_NON_FIRST_PAGES + 1;
      offset = (offset % EHASH_NUM_NON_FIRST_PAGES) * sizeof (EHASH_DIR_RECORD);
    }
  *out_page_no_p = page_no;
  *out_offset_p = offset;
}

정확히 두 분기가 있으며(Figure 1-1 참조), 헤더를 공유하는 첫 번째 페이지에 인덱스가 들어가는지 여부로 갈린다. 오류 분기도 조기 반환도 없다: 이 함수는 음이 아닌 인덱스 전체에서 전함수(total function)이며 절대 실패하지 않는다 — 호출자는 인덱스 대신 카운트를 전달해 해당 수만큼의 항목이 몇 페이지에 걸치는지 알아낼 수도 있다. 이 함수는 create, insert, expand, shrink, dump 전체에서 사용되는 정식 변환 함수다.

flowchart TD
  A["ehash_dir_locate(&page_no, &offset)\n입력: offset = 논리 포인터 인덱스"] --> B{"offset < EHASH_NUM_FIRST_PAGES ?"}
  B -- "예: 분기 A, page 0" --> C["offset = offset * sizeof(VPID) + EHASH_DIR_HEADER_SIZE\npage_no = 0"]
  B -- "아니오: 분기 B, 이후 페이지" --> D["offset -= EHASH_NUM_FIRST_PAGES"]
  D --> E["page_no = offset / EHASH_NUM_NON_FIRST_PAGES + 1\noffset = (offset % EHASH_NUM_NON_FIRST_PAGES) * sizeof(VPID)"]
  C --> F["*out_page_no_p, *out_offset_p에 기록"]
  E --> F

Figure 1-1. ehash_dir_locate의 두 분기. 두 경로 모두 동일한 출력 기록으로 수렴하며, 실패 경로는 존재하지 않는다.

1.7 복구 페이로드: `EHASH_REPETITION`

디렉터리 확장 시 local depth L인 버킷이 점유하는 2^(depth-L)개의 연속 슬롯에 동일한 버킷 VPID를 기록한다. 각 쓰기를 개별 로그로 남기면 로그가 불어나므로, redo 레코드는 런 길이 인코딩(RLE) 페이로드를 담는다:

// ehash_repetition -- src/storage/extendible_hash.c
struct ehash_repetition
{
  /* The "vpid" is repeated "count" times */
  VPID vpid;
  int count;
};

구조체	필드	역할	존재 이유
`EHASH_REPETITION`	`vpid`	기록할 버킷 포인터	하나의 값이 연속된 동일 디렉터리 슬롯 전체를 커버
`EHASH_REPETITION`	`count`	이 `vpid`가 들어갈 연속 슬롯 수	RLE 런 길이; 하나의 작은 레코드로 redo 시 해당 런을 재구성할 수 있다

이 구조체는 모듈 내에서 복구 목적으로만 존재하는 유일한 구조체다. 순방향 로그 기록자(ehash_connect_bucket)와 멱등성 redo 핸들러(ehash_rv_connect_bucket_redo)는 Chapter 10에서 추적한다.

1.8 결과 열거형: `EHASH_RESULT`와 `EH_SEARCH`

EHASH_RESULT는 insert/split/merge 전체에 걸쳐 전달되는 내부 7값 상태 코드다:

// EHASH_RESULT -- src/storage/extendible_hash.c
typedef enum
{
  EHASH_SUCCESSFUL_COMPLETION,
  EHASH_BUCKET_FULL,        /* Bucket full condition; used in insertion */
  EHASH_BUCKET_UNDERFLOW,   /* Bucket underflow condition; used in deletion */
  EHASH_BUCKET_EMPTY,       /* Bucket empty condition; used in deletion */
  EHASH_FULL_SIBLING_BUCKET,
  EHASH_NO_SIBLING_BUCKET,
  EHASH_ERROR_OCCURRED
} EHASH_RESULT;

값	의미
`EHASH_SUCCESSFUL_COMPLETION`	연산 완료, 추가 처리 불필요
`EHASH_BUCKET_FULL`	대상 버킷이 새 레코드를 수용할 수 없음 (split 경로를 유발)
`EHASH_BUCKET_UNDERFLOW`	삭제 후 점유율이 underflow 임계값 아래로 하락
`EHASH_BUCKET_EMPTY`	삭제 후 버킷에 데이터 레코드가 없음 (더 강한 underflow 상태)
`EHASH_FULL_SIBLING_BUCKET`	merge 대상의 형제 버킷이 이 버킷을 흡수하기에 너무 꽉 찬 상태
`EHASH_NO_SIBLING_BUCKET`	형제 슬롯이 독립적으로 merge 가능한 버킷을 가리키지 않음
`EHASH_ERROR_OCCURRED`	latch, I/O, 할당 오류로 연산이 중단됨

EH_SEARCH는 storage_common.h에 선언된, ehash_search의 공개 3값 결과다:

// EH_SEARCH -- src/storage/storage_common.h
typedef enum { EH_KEY_FOUND, EH_KEY_NOTFOUND, EH_ERROR_OCCURRED } EH_SEARCH;

값	의미
`EH_KEY_FOUND`	키 발견; `OID`가 호출자의 `value_ptr`에 복사됨
`EH_KEY_NOTFOUND`	해당 버킷에 키 없음; `value_ptr`은 변경되지 않음
`EH_ERROR_OCCURRED`	확정적인 답을 내기 전에 오류로 탐색 중단

EHASH_RESULT는 모듈 밖으로 노출되지 않고, 공개 API 경계를 넘는 것은 EH_SEARCH(와 insert/delete의 OID * 반환값)뿐이다. 덕분에 공개 계약은 발견/미발견/오류라는 깔끔한 세 값으로 유지된다.

1.9 포인터 관계 전체 조감도

Figure 1-2 — 포인터 조감도: 디렉터리·버킷·overflow 파일과 디렉터리 항목 공유 Figure 1-2. 포인터 조감도. EHID는 외부에서 유지하는 유일한 루트다; page 0의 헤더가 버킷 파일과 overflow 파일 id를 담고, dir[]은 디렉터리 페이지에 걸쳐 스트라이핑되며, 각 bucket_vpid는 버킷 파일을 가리킨다. local depth < global depth인 경우 여러 dir[] 항목이 하나의 버킷을 공유한다.

1.10 챕터 요약 — 핵심 정리

EHID = (디렉터리 VFID, 루트 pageid)가 유일한 내구성 핸들이다. 구조체 어디에도 이것으로 돌아오는 역방향 포인터는 없으며, 모든 탐색은 그 루트 페이지를 fix하는 것으로 시작한다.
디렉터리 헤더(EHASH_DIR_HEADER)는 두 파일 id, 깊이 히스토그램, 키 타입, 전역 깊이, 버킷 정렬 단위를 보유한다. bucket_file/overflow_file은 헤더를 통해 도달하며, EHID에서 직접 접근할 수 없다; local_depth_count[0..32]는 ehash_adjust_local_depth가 점진적으로 유지하는 O(1) 축소 판단 기준이다.
두 가지 깊이 불변 조건이 모든 것을 지배한다: 모든 버킷의 local_depth <= header.depth, 그리고 local_depth_count는 그 깊이들의 충실한 히스토그램이다.
디렉터리는 페이지에 스트라이핑된 하나의 논리 2^depth 배열이다; ehash_dir_locate는 절대 실패하지 않는 정식 인덱스 → (page, offset) 변환 함수다(분기 A = page 0, 분기 B = 이후 페이지).
주소 지정은 32비트 부호 없는 pseudo-key의 상위 (MSB 쪽) depth비트를 사용하며, GETBITS/FIND_OFFSET으로 추출한다; GETBIT/SETBIT/CLEARBIT는 split/merge 시 두 형제 쌍을 계산한다.
버킷 페이지는 local depth를 slot 0에 보관한다(EHASH_BUCKET_HEADER); 여러 디렉터리 항목이 하나의 버킷 페이지를 공유하는 것 자체가 local depth < global depth의 표현 방식이다.
EHASH_REPETITION (vpid, count)은 RLE 복구 페이로드다(순방향 로그/redo 동작은 Chapter 10). EHASH_RESULT(7값)는 모듈 내부에 머물고, 공개 API를 넘는 것은 3값 EH_SEARCH뿐이다.

Chapter 2: 파일 생성과 메모리 레이아웃

이 챕터는 다음 질문에 답한다: Chapter 1에서 정의한 구조체들을 바탕으로, 새로운 해시 파일을 초기 단일-버킷 상태로 어떻게 부트스트랩하는가? xehash_create -> ehash_create_helper 의 분기를 따라 추적하면서, 이후 챕터(Ch 6–8)가 의존하는 시작 불변 조건을 확립한다. Extendible hashing 자체의 의미는 companion 문서인 cubrid-extendible-hash.md(## Algorithm, ## Directory and Buckets 절)를 참고하라. 2.5–2.10에 붙은 /* Branch X-no */ 주석은 제어 흐름을 표시한다.

2.1 두 파일과 디스크립터

해시 테이블은 하나의 볼륨 위에 놓인 두 개의 numerable 파일로 이루어진다: 버킷 파일(FILE_EXTENDIBLE_HASH)과 디렉터리 파일(FILE_EXTENDIBLE_HASH_DIRECTORY). 두 파일 모두 동일한 FILE_EHASH_DES 디스크립터가 헤더에 찍힌다 — 이것이 파일 헤더에 실리는 유일한 애플리케이션 전용 페이로드다.

// struct file_ehash_des -- src/storage/file_manager.h
struct file_ehash_des
{
  OID class_oid;                /* class the index belongs to, or NULL OID */
  int attr_id;                  /* attribute id within that class */
};

필드	역할	존재 이유
`class_oid`	이 인덱스가 속한 클래스의 OID; 없으면 NULL OID	파일 자체만으로 어느 클래스의 인덱스인지 식별 가능하게 함
`attr_id`	`class_oid` 내 인덱싱 대상 애트리뷰트	동일 클래스에 여러 인덱스가 있을 때 구분

FILE_EHASH_DES는 union file_descriptors의 한 멤버(고정 크기 FILE_DESCRIPTORS_SIZE = 64바이트)다. 동일한 디스크립터를 file_create_ehash와 file_create_ehash_dir 양쪽 모두에 전달하므로, 버킷인지 디렉터리인지는 디스크립터가 아니라 파일 타입으로 구분한다. 호출자는 EHID {directory VFID, directory root pageid}만 보관하면 되며, 나머지는 디렉터리 루트를 fix해서 모두 도달 가능하다(Figure 2-1).

flowchart TD
  EHID["EHID (호출자)<br/>vfid=dir VFID, pageid=dir root"]
  DIRH["EHASH_DIR_HEADER (dir pg 0)<br/>depth=0, bucket_file, ldc[0]=1"]
  REC["EHASH_DIR_RECORD[0]<br/>bucket_vpid -> bucket pg 0"]
  BKT["bucket pg 0<br/>slot 0 = 헤더, local_depth=0"]
  EHID --> DIRH --> REC --> BKT
  DIRH -. "bucket_file VFID" .-> BKT

Figure 2-1. ehash_create_helper가 만들어내는 객체 그래프.

2.2 `xehash_create` — 얇은 public 래퍼

xehash_create는 서버 진입점으로, ehash_create_helper (thread_p, ehid_p, key_type, exp_num_entries, class_oid_p, attr_id, is_tmp)에 그대로 위임한다. 진입 계약: 호출자는 ehid_p->vfid.volid(대상 볼륨)를 이미 설정해 두어야 한다; 나머지 EHID 필드는 모두 출력값이다. 이 분리는 역사적 이유에서 비롯된 것이며, 실제 로직은 helper에만 있다.

2.3 `ehash_get_key_size`와 `DB_TYPE_STRING` 센티넬

Helper는 가장 먼저 정렬과 페이지 수 추정에 쓰일 키당 바이트 예산을 결정한다:

// ehash_get_key_size -- src/storage/extendible_hash.c
case DB_TYPE_STRING:
  key_size = 1;             /* Size of each key will vary */
  break;
case DB_TYPE_OBJECT:
  key_size = sizeof (OID);
  break;
#if defined (ENABLE_UNUSED_FUNCTION)
case DB_TYPE_DOUBLE:   key_size = sizeof (double);  break;
// ... condensed: FLOAT, INTEGER, BIGINT, SHORT, DATE/TIME/TIMESTAMP, DATETIME, MONETARY ...
#endif
default:
  er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_INVALID_KEY_TYPE, 1, key_type);
  key_size = -1;            /* <- only error return */
  break;

수정자가 반드시 기억해야 할 두 가지 사실이 있다: (1) DB_TYPE_STRING은 실제 크기가 아닌 1을 반환한다 — 문자열은 가변 길이이며(소스 주석 “Size of each key will vary”), 1은 정렬 최솟값 플레이스홀더다. 실제 문자열 예산은 별도로 계산되며(2.5), 1을 키 폭으로 취급하면 고전적인 버그가 된다. (2) 고정 폭 분기는 ENABLE_UNUSED_FUNCTION으로 격리되어 있다 — 일반 빌드에서는 오류 없이 도달 가능한 케이스가 DB_TYPE_STRING과 DB_TYPE_OBJECT뿐이며, 그 외는 모두 default에 걸려 -1을 반환한다.

INVARIANT — 키 타입은 STRING 또는 OID다. 도달 가능한 모든 경로는 key_type이 {DB_TYPE_STRING, DB_TYPE_OBJECT} 안에 있다고 가정한다. ehash_create_helper는 디버그 빌드에서 이를 assert (key_type == DB_TYPE_STRING || key_type == DB_TYPE_OBJECT)로 검증하고, 릴리스 빌드에서는 -1 반환 시 생성이 중단된다(2.4, 분기 B). 위반 시 (ENABLE_UNUSED_FUNCTION 활성화 후 DB_TYPE_DOUBLE 전달): 고정 폭 경로가 실행되어 20바이트 문자열 허용량이 적용되지 않고 — 페이지 추정이 틀어지나 정확성은 깨지지 않는다.

2.4 `ehash_create_helper` — 분기 전체 워크스루

분기 주석은 2.5–2.10에 인라인으로 달려 있다. 분기 A, B, J(첫 번째 file_create_ehash)는 되돌릴 것이 없는 상태에서 바로 NULL을 반환하고, 첫 번째 file_alloc 이후의 모든 실패(L, P, Q, R)는 단일 goto exit_on_error(2.10)로 집결한다. 별도 발췌 없는 두 분기: A — null ehid: 어떤 할당보다 먼저 if (ehid_p == NULL) return NULL;; 디스크립터 채우기(A->B)는 class_oid가 제공되면 복사, 없으면 OID_SET_NULL, attr_id는 그대로 — 이 ehdes를 파일 생성 호출 양쪽에 재사용; B — 잘못된 key size: ehash_get_key_size가 이미 er_set을 호출한 후 if (key_size < 0) return NULL;.

2.5 `exp_num_entries` -> 페이지 수 추정

이 추정은 디스크 지역성을 개선할 뿐이며, 정확성에는 영향을 주지 않는다:

// ehash_create_helper -- src/storage/extendible_hash.c
if (exp_num_entries < 0)
  exp_bucket_pages = 1;                                               /* <- one-page collapse */
else
  {
    if (key_type == DB_TYPE_STRING)
      exp_bucket_pages = exp_num_entries * (20 + sizeof (OID) + 4);   /* <- string budget */
    else
      exp_bucket_pages = exp_num_entries * (key_size + sizeof (OID) + 4); /* <- OID budget */
    exp_bucket_pages = CEIL_PTVDIV (exp_bucket_pages, DB_PAGESIZE);
  }

문자열 예산은 센티넬 1을 무시하고 20바이트 허용량 + OID 값 + 슬롯 4바이트를 쓴다. OID 예산은 key_size + sizeof(OID) + 4다. 디렉터리 추정(2.9)도 동일한 방식으로 collapse된다.

2.6 정렬 계산

정렬은 버킷 페이지 슬롯을 패딩하여 키(또는 OID 값)가 자연 경계에 놓이도록 한다:

// ehash_create_helper -- src/storage/extendible_hash.c
if (SSIZEOF (value.pageid) >= key_size)        /* <- value.pageid is an OID field */
  alignment = sizeof (value.pageid);
else
  alignment = (char) key_size;
if (alignment > SSIZEOF (int))
  alignment = sizeof (int);                    /* <- hard cap at sizeof(int) */

도달 가능한 두 키 타입 모두 최종적으로 sizeof(int)로 결정된다: STRING(key_size == 1)은 pageid가 이기고, OBJECT는 상한 조건이 발동된다. 이 alignment 값은 버킷 초기화 데이터(2.7)와 디렉터리 헤더(2.9)로 전달된다.

2.7 버킷 파일과 버킷 페이지 0

버킷 파일이 먼저 생성된다. volid 인계 방식에 주목하라:

// ehash_create_helper -- src/storage/extendible_hash.c
bucket_vfid.volid = ehid_p->vfid.volid;        /* <- bucket borrows the caller's target volid */
if (file_create_ehash (thread_p, exp_bucket_pages, is_tmp, &ehdes, &bucket_vfid) != NO_ERROR)
  { ASSERT_ERROR (); return NULL; }            /* Branch J-no: clean, nothing allocated yet */

직관에 반하는 volid 순서. 버킷 파일이 ehid_p->vfid.volid를 먼저 가져가고, 이후 dir_vfid.volid = bucket_vfid.volid(2.9)가 디렉터리를 같은 볼륨에 배치한다. EHID는 최종적으로 디렉터리 VFID를 담지만, volid는 호출자 -> 버킷 -> 디렉터리 순으로 흐른다. ehid->vfid를 덮어쓰는 것은 마지막 대입이다(2.10).

file_create_ehash는 제네릭 file_create (..., FILE_EXTENDIBLE_HASH, ..., is_tmp, true, vfid)로 형태를 갖추며, 끝의 true가 is_numerable(서수 주소 지정 가능 페이지; ehash_fix_nth_page가 사용, 2.10)이다. 이어서 페이지 0을 init 콜백으로 할당하여 원자적으로 포맷한다:

// ehash_create_helper -- src/storage/extendible_hash.c
init_bucket_data[0] = alignment;  init_bucket_data[1] = 0;  init_bucket_data[2] = is_tmp;
/* triple {alignment, depth, is_temp}; depth HARD-CODED 0 -> seed local depth */
if (file_alloc (thread_p, &bucket_vfid, ehash_initialize_bucket_new_page, init_bucket_data, &bucket_vpid, NULL)
    != NO_ERROR)
  { ASSERT_ERROR (); goto exit_on_error; }      /* Branch L-no */

2.8 `ehash_initialize_bucket_new_page` — 버킷 init 콜백

새 페이지 프레임이 fix된 후 file_alloc이 이 함수를 한 번 호출한다 — args를 해석하고 페이지를 포맷하며 영구 파일이면 로그를 남긴다. 여기서 초기화하는 헤더는 1바이트짜리 EHASH_BUCKET_HEADER다:

// struct ehash_bucket_header -- src/storage/extendible_hash.c
struct ehash_bucket_header
{
  char local_depth;             /* The local depth of the bucket */
};

필드	역할	존재 이유
`local_depth`	이 버킷이 구별하는 해시 키 비트 수	분할/병합(Ch 6, 8) 시 디렉터리의 전역 `depth`와 비교하여 디렉터리 두 배 증가 vs. 로컬 분할 여부 결정

// ehash_initialize_bucket_new_page -- src/storage/extendible_hash.c
alignment = *(char *) args;  offset += sizeof (alignment);
depth     = *((char *) args + offset);  /* ... is_temp read next ... */
pgbuf_set_page_ptype (thread_p, page_p, PAGE_EHASH);                     /* (1) ptype 스탬프 */
spage_initialize (thread_p, page_p, UNANCHORED_KEEP_SEQUENCE, alignment, DONT_SAFEGUARD_RVSPACE); /* (2) */
bucket_header.local_depth = depth;                                       /* (3) 헤더 = depth 0 */
// ... bucket_recdes = &bucket_header, REC_HOME, sizeof (EHASH_BUCKET_HEADER) ...
success = spage_insert (thread_p, page_p, &bucket_recdes, &slot_id);     /* (4) 헤더 -> slot 0 */
if (success != SP_SUCCESS)
  {
    if (success != SP_ERROR)            /* should-never-happen: tiny record refused on empty page */
      { er_set (ER_FATAL_ERROR_SEVERITY, ...); error_code = ER_FAILED; }
    else { ASSERT_ERROR_AND_SET (error_code); }  /* real error already set */
    return error_code;                  /* <- page left fixed, undone by file_alloc */
  }
if (!is_temp)
  log_append_undoredo_data2 (thread_p, RVEH_INIT_BUCKET, NULL, page_p, -1, 0, 2, NULL, args);  /* (5) */
pgbuf_set_dirty (thread_p, page_p, DONT_FREE);
return NO_ERROR;

spage_insert의 세 가지 결과는 인라인으로 주석 처리되어 있다. is_temp가 true면 로그를 생략한다. log_append_undoredo_data2를 통한 RVEH_INIT_BUCKET은 undoredo 방식이며, 2바이트 {alignment, depth} 페이로드가 양방향으로 사용된다. redo 핸들러 ehash_rv_init_bucket_redo는 spage_initialize + spage_insert를 재실행하여 이 함수를 미러링한다(ER_FAILED 대신 er_errid()를 반환하는 점이 차이).

INVARIANT — slot 0에는 버킷 헤더가 있다. 모든 버킷 페이지는 EHASH_BUCKET_HEADER(1바이트 char local_depth)를 슬롯 0에 유지하며, 이는 어떤 데이터 레코드보다도 먼저 삽입된다. UNANCHORED_KEEP_SEQUENCE가 슬롯 순서를 보존한다. 집행: 빈 페이지에서 헤더 spage_insert가 먼저 실행된 후에야 엔트리가 추가될 수 있다. 위반 시, 분할/병합(Ch 6, 8)에서 depth를 읽을 때마다 쓰레기 값을 읽게 된다.

2.9 디렉터리 파일, 헤더, 그리고 단일 엔트리

디렉터리 파일은 두 번째로 생성되며 버킷과 같은 볼륨에 고정된다. 이후 페이지 0은 직접 손으로 작성한다. 페이지에 오버레이하는 헤더는 EHASH_DIR_HEADER이며, 필드는 “크기에 따라 순서대로 선언”되어 있다:

// struct ehash_dir_header -- src/storage/extendible_hash.c
struct ehash_dir_header
{
  VFID bucket_file;             /* bucket file identifier */
  VFID overflow_file;           /* overflow (buckets) file identifier */
  int local_depth_count[EHASH_HASH_KEY_BITS + 1];  /* histogram: count of buckets per local depth */
  DB_TYPE key_type;             /* type of the keys */
  short depth;                  /* global depth of the directory */
  char alignment;               /* alignment value used on slots of bucket pages */
};

필드	역할	존재 이유
`bucket_file`	버킷 파일의 VFID	디렉터리에서 버킷으로 가는 유일한 링크; 버킷 VFID는 `EHID`에 없으므로 여기에 보관 필수
`overflow_file`	긴 문자열 overflow 파일의 VFID, 첫 긴 키 등장 전까지 NULL	버킷 페이지에서 초과 크기 문자열 키를 분리 보관
`local_depth_count[]`	로컬 depth별 버킷 수 히스토그램, `EHASH_HASH_KEY_BITS + 1` 항목	Ch 9가 엔트리를 스캔하지 않고 shrink 조건을 감지할 때 사용
`key_type`	키의 `DB_TYPE` (STRING 또는 OBJECT)	조회/삽입 시 별도 채널 없이 해시 및 비교 가능
`depth`	전역 depth — 디렉터리 인덱스로 사용하는 비트 수	디렉터리 크기(`2^depth`)와 분할 결정(Ch 7)의 기준
`alignment`	2.6에서 넘어온 슬롯 정렬 값	모든 버킷이 포맷될 때 동일한 정렬 공유

각 디렉터리 슬롯은 단일 필드로 된 EHASH_DIR_RECORD다:

// struct ehash_dir_record -- src/storage/extendible_hash.c
struct ehash_dir_record
{
  VPID bucket_vpid;             /* bucket pointer */
};

필드	역할	존재 이유
`bucket_vpid`	이 디렉터리 슬롯이 가리키는 버킷의 VPID	디렉터리는 이 포인터들의 배열; `local_depth < depth`일 때 여러 슬롯이 한 버킷을 가리킬 수 있음

// ehash_create_helper -- src/storage/extendible_hash.c
if (exp_num_entries < 0) exp_dir_pages = 1;       /* one-page collapse */
else { ehash_dir_locate (&exp_dir_pages, &exp_bucket_pages); exp_dir_pages++; }  /* INDEX -> count */
dir_vfid.volid = bucket_vfid.volid;
if (file_create_ehash_dir (...) != NO_ERROR) { ASSERT_ERROR (); goto exit_on_error; } /* Branch P-no */
if (file_alloc (thread_p, &dir_vfid, is_tmp ? file_init_temp_page_type : file_init_page_type,
                &ptype, &dir_vpid, &dir_page_p) != NO_ERROR)   /* generic init, NOT a hash callback */
  { ASSERT_ERROR (); goto exit_on_error; }        /* Branch Q-no */
if (dir_page_p == NULL) { assert_release (false); goto exit_on_error; } /* Branch R-yes: defensive */
#if !defined (NDEBUG)
  pgbuf_check_page_ptype (thread_p, dir_page_p, PAGE_EHASH);   /* dir-create re-checks ptype */
#endif
dir_header_p = (EHASH_DIR_HEADER *) dir_page_p;
dir_header_p->depth = 0;                          /* <- global depth 0 */
// ... key_type, alignment, bucket_file=bucket_vfid, overflow_file=NULL set here ...
dir_header_p->local_depth_count[0] = 1;           /* <- one bucket at local depth 0 */
// ... zero remaining local_depth_count[1..EHASH_HASH_KEY_BITS] ...
dir_record_p = (EHASH_DIR_RECORD *) ((char *) dir_page_p + EHASH_DIR_HEADER_SIZE);
dir_record_p->bucket_vpid = bucket_vpid;          /* <- entry[0] -> bucket page 0 */

뒤따르는 루프는 히스토그램 인덱스 1..EHASH_HASH_KEY_BITS를 0으로 채운다(인덱스 0만 0이 아닌 값). 페이지 0은 내용 전체를 직접 덮어쓰고 충돌 시 파일 자체가 삭제되므로 제네릭 file_init_page_type(해시 콜백 없음)을 사용하지만, 디버그 빌드에서는 PAGE_EHASH가 재확인된다. EHASH_DIR_HEADER_SIZE는 헤더를 int 경계까지 올림 패딩하므로, 첫 번째 EHASH_DIR_RECORD는 헤더 직후에 위치한다.

시작 불변 조건 — depth 0, 엔트리 1개, local depth 0의 버킷 1개. 새로 생성된 테이블은 dir_header.depth == 0, 버킷 페이지 0을 가리키는 EHASH_DIR_RECORD 하나, local_depth == 0, local_depth_count[0] == 1을 가진다 — 이후 모든 알고리즘이 가정하는 기저 상태다(Ch 6은 local depth를 올리기만 하고, Ch 7은 depth를 초과할 때만 두 배 증가한다). 집행: 이 세 가지 쓰기는 페이지가 dirty 처리되고 EHID가 반환되기 전에 무조건 실행된다. 위반 시 (예: local_depth_count[0]을 0으로 두면), 첫 번째 분할의 shrink 검사와 fan-out 산술이 틀린 기준점에서 시작된다.

RVEH_INIT_DIR — redo 전용

// ehash_create_helper -- src/storage/extendible_hash.c
if (!is_tmp)
  log_append_redo_data2 (thread_p, RVEH_INIT_DIR, &dir_vfid, dir_page_p, 0,
                         EHASH_DIR_HEADER_SIZE + sizeof (EHASH_DIR_RECORD), dir_page_p);

이것은 log_append_redo_data2 — redo 전용, undo 없음(출처: “Don’t need UNDO since we are just creating the file. If we abort, the file is removed.”). 롤백 시 exit_on_error가 디렉터리 파일을 제거하므로, 순방향 복구만 이미지가 필요하다. 핸들러 ehash_rv_init_dir_redo는 PAGE_EHASH를 스탬프한 후 log_rv_copy_char로 로그 이미지를 복사하여 시드 상태를 정확히 복원한다.

2.10 성공 테일과 페이지 fix 래퍼

성공 시 helper는 dir_page_p를 dirty+free하고, dir_vfid와 dir_vpid.pageid를 EHID에 복사한 뒤(2.7의 덮어쓰기) return ehid_p를 반환한다. 버킷 파일은 dir_header.bucket_file로만 도달 가능하다. exit_on_error(분기 ERR)는 non-null인 VFID를 모두 파괴한다: 영구 파일은 file_postpone_destroy, 임시 파일은 file_destroy. 이후 챕터들이 사용하는 세 개의 페이지 fix 래퍼는 모두 ehash_fix_old_page에서 수렴된다:

// ehash_fix_old_page -- src/storage/extendible_hash.c
page_p = pgbuf_fix (thread_p, vpid_p, OLD_PAGE, latch_mode, PGBUF_UNCONDITIONAL_LATCH);
if (page_p == NULL)
  {
    if (er_errid () == ER_PB_BAD_PAGEID)         /* <- only this errid gets re-mapped */
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_UNKNOWN_EXT_HASH, 4, /* ...vfid/vpid... */);
    return NULL;                                 /* any other failure returned as-is */
  }
#if !defined (NDEBUG)
  (void) pgbuf_check_page_ptype (thread_p, page_p, PAGE_EHASH);   /* <- ptype guard */
#endif
  return page_p;

vfid는 이 함수에서는 오류 보고 전용이다. 나머지 두 래퍼는 이 함수에 위임한다: ehash_fix_ehid_page는 {ehid->vfid.volid, ehid->pageid}로 디렉터리 루트를 fix하며(EHID->헤더 경로), ehash_fix_nth_page는 file_numerable_find_nth로 다중 페이지 디렉터리에서 offset 번째 페이지를 fix한다(실패 시 ASSERT_ERROR()/NULL).

INVARIANT — 모든 해시 페이지는 PAGE_EHASH ptype을 가진다. 버킷 페이지는 ehash_initialize_bucket_new_page에서, 디렉터리 페이지는 file_init_page_type 인자로 스탬프를 받으며, redo 핸들러가 재스탬프한다. 집행: ehash_fix_old_page는 디버그 빌드에서 매 fix마다 pgbuf_check_page_ptype을 호출한다. 위반 시 (스탬프 없이 페이지 재사용), 비-해시 페이지를 버킷으로 파싱하기 전에 fix 시점에서 pgbuf_check_page_ptype이 트리거된다.

2.11 챕터 요약 — 핵심 정리

해시 테이블은 두 개의 numerable 파일이다 (버킷 + 디렉터리). 두 파일 모두 동일한 FILE_EHASH_DES { class_oid, attr_id } 태그가 붙지만, 이 메타데이터를 알고리즘이 직접 읽지는 않는다.
도달 가능한 키 타입은 DB_TYPE_STRING과 DB_TYPE_OBJECT뿐이다. 고정 폭 케이스는 ENABLE_UNUSED_FUNCTION 아래 컴파일되어 나오지 않으며, DB_TYPE_STRING의 1은 센티넬이다(실제 문자열 예산은 2.5에서 계산).
exp_num_entries < 0이면 두 페이지 추정 모두 1로 collapse된다. 그 외에는 20 + sizeof(OID) + 4(문자열) 또는 key_size + sizeof(OID) + 4(OID)를 CEIL_PTVDIV로 나누며, 이는 지역성 힌트일 뿐이다.
Volid는 호출자 -> 버킷 -> 디렉터리 순으로 흐른다. EHID에 디렉터리 VFID + root pageid가 덮어써지는 것은 마지막 단계다.
버킷 페이지 0은 file_alloc 콜백 ehash_initialize_bucket_new_page가 포맷한다: PAGE_EHASH, spage_initialize, 1바이트 EHASH_BUCKET_HEADER(local_depth = 0)를 slot 0에, RVEH_INIT_BUCKET undoredo(영구 파일 전용).
디렉터리 루트는 EHASH_DIR_HEADER에 직접 작성된다 — depth = 0, local_depth_count[0] = 1, 하나의 EHASH_DIR_RECORD. 이것의 RVEH_INIT_DIR 로그는 redo 전용이다(중단된 생성은 파일 자체를 삭제하므로).
시작 불변 조건: depth=0, 엔트리 1개, local depth 0의 버킷 1개. 모든 해시 페이지는 PAGE_EHASH ptype을 가지며, ehash_fix_old_page가 매 fix마다 재검증한다.

Chapter 3: 해싱과 디렉터리 주소 결정

모든 CRUD 연산은 동일한 방식으로 시작된다. 사용자 키는 고정 폭의 *유사 키(pseudo-key)*로 변환되고, 그 상위 비트로 디렉터리 슬롯을 선택하며, 슬롯의 VPID가 버킷 페이지 하나를 지정한다. 이 챕터는 검색(4장), 삽입(5장), 삭제(8장)이 각자의 로직을 얹기 전에, 그 공통 *주소 결정 골격(addressing skeleton)*을 독립적으로 해부한다. 개념적 배경(전역 깊이 대 지역 깊이, 디렉터리 두 배 확장)은 companion 문서의 “한 그림으로 보는 확장 가능 해싱”과 “Depth” 절을 참조한다.

세 단계로 요약된다. 해시 (ehash_hash → 32비트 EHASH_HASH_KEY), 인덱스 결정 (FIND_OFFSET이 상위 depth 비트를 추출), VPID 조회 (ehash_find_bucket_vpid가 인덱스를 ehash_dir_locate로 물리 주소에 매핑하고, 디렉터리 페이지를 고정(fix)한 뒤 VPID를 읽는다). ehash_find_bucket_vpid_with_hash가 이 세 단계를 연결하는 단일 진입점이며, 모든 CRUD 경로가 이를 호출한다.

3.1 유사 키 타입과 그 폭

유사 키는 레코드 구조체가 아니라 해싱의 출력값인 32비트 부호 없는 정수다.

// EHASH_HASH_KEY -- src/storage/extendible_hash.c
typedef unsigned int EHASH_HASH_KEY;  /* Pseudo_key type */
#define EHASH_HASH_KEY_BITS  (sizeof(EHASH_HASH_KEY) * 8)   /* = 32 */

EHASH_HASH_KEY는 필드가 없는 typedef다. FIND_OFFSET은 **수치적으로 상위 비트(numerically high-order bits)**에서 디렉터리 인덱스를 읽는다. 바이트 배열이 아닌 부호 없는 정수 값을 오른쪽으로 시프트하므로, “상위 비트”란 호스트 바이트 순서와 무관하게 최상위 값 비트를 의미한다. 따라서 해시 함수는 가장 변화량이 큰 출력을 상위 비트에, 체크섬을 하위 비트에 배치한다.

값 영역 (수치적 MSB→LSB)	역할	존재 이유
상위 비트 (`FIND_OFFSET`이 먼저 읽는 쪽)	1차 인덱스 비트	디렉터리가 인덱싱하는 위치에 가장 변화량이 큰 출력이 위치
중간 비트	2차/3차 인덱스 비트	디렉터리 깊이가 깊어질수록 워드 하위 방향으로 탐색
하위 비트	체크섬 (문자열: 부호 있는 바이트 합산을 워드에 더함; OID: XOR 결과를 최저 주소 바이트에 기록)	간단한 혼합; 깊이가 32에 근접할 때만 도달

이는 경향성이지 비트 단위의 고정 레이아웃이 아니다. 문자열 경로는 부호 있는 합을 전체 워드에 더하므로 캐리가 발생할 수 있고 음수가 될 수도 있다. OID 경로는 최저 주소 바이트를 덮어쓰는데, 이는 리틀 엔디언 호스트에서만 수치적 LSB에 해당한다. “낮은 바이트에 체크섬”이라는 설명은 엔디언과 캐리에 따라 달라지므로 고정 구조체처럼 취급해서는 안 된다.

INVARIANT — 전역 깊이(global depth)는 유사 키 폭을 절대 초과하지 않는다. FIND_OFFSET은 32비트 워드에서 depth 비트를 추출하므로 dir_header->depth는 EHASH_HASH_KEY_BITS(32)로 제한된다. 축소(shrink) 장부는 EHASH_HASH_KEY_BITS + 1개의 카운터 슬롯(local_depth_count[33])을 예약하여 깊이 0..32를 인덱싱할 수 있다. 위반 시 (깊이 33 이상) GETBITS가 음수만큼 시프트하게 되어 C에서 정의되지 않은 동작이 발생하고 인덱스가 조용히 오염된다.

FIND_OFFSET은 GETBITS를 별칭(alias)으로 사용하며, 상위 depth 비트를 왼쪽 정렬(pos=1)로 읽는다.

// FIND_OFFSET / GETBITS -- src/storage/extendible_hash.c
#define GETBITS(value, pos, n) \
  ( ((value) >> ( EHASH_HASH_KEY_BITS - (pos) - (n) + 1)) & (~(~0UL << (n))) )
#define FIND_OFFSET(hash_key, depth) (GETBITS((hash_key), 1, (depth)))
/*  pos=1, n=depth: shift the value right by (32 - depth), mask to depth bits */

INVARIANT — 정확히 상위 depth 비트가 슬롯을 선택한다. pos=1, n=depth로 GETBITS는 오른쪽으로 32 - depth만큼 시프트하고 depth 하위 비트를 마스킹하므로, 결과는 값의 최상위 depth 비트 정확히 그것이다. 이것이 디렉터리 두 배 확장(깊이 d → d+1)이 기존 슬롯 i를 형제 슬롯 2i와 2i+1로 분할하는 원리다. 비트 해상도가 한 비트 추가되는 것이다.

3.2 ehash_hash — 타입별 분기

ehash_hash는 DB_TYPE에 대한 switch문이며, 일반 빌드에서는 두 개의 분기만 컴파일된다.

// ehash_hash -- src/storage/extendible_hash.c
  switch (key_type)
    {
    case DB_TYPE_STRING:
      hash_key = ehash_hash_string_type (key, (char *) original_key_p); break;
    case DB_TYPE_OBJECT:
      hash_key = ehash_hash_eight_bytes_type (key); break;   /* OIDs */
#if defined (ENABLE_UNUSED_FUNCTION)
    /* ... BIGINT/DOUBLE/MONETARY -> eight_bytes; FLOAT/DATE/.../INTEGER -> four_bytes; SHORT -> two_bytes ... */
#endif
    default:
      er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);  /* <- hash_key stays 0 */
    }
  return hash_key;

분기. DB_TYPE_STRING → ehash_hash_string_type, DB_TYPE_OBJECT → ehash_hash_eight_bytes_type. 넓은 수치 타입 분기는 #if defined (ENABLE_UNUSED_FUNCTION) 뒤에 숨어 있어 일반 빌드에서는 존재하지 않는다. default 분기는 치명 오류 ER_EH_CORRUPTED를 발생시키고 초기값 그대로인 hash_key = 0을 반환하여, 지원되지 않는 모든 키를 엔트리 0으로 매핑한다. CUBRID는 클래스명 문자열과 OID만 해싱하므로 이 두 분기가 전부다.

3.3 ehash_hash_string_type — 폴딩, 그 다음 3단 패킹

두 단계로 구성된다. 4바이트 중간값으로 **폴딩(fold)**하는 1단계와, 그 결과를 상위 3바이트와 바이트 합산으로 분산시키는 3단 패킹(triple-pass pack) 2단계다. 조기 반환이 있는 것은 1단계뿐이다.

// ehash_hash_string_type (stage 1) -- src/storage/extendible_hash.c
  length = (int) strlen (key_p);
  if (length > 0)                               /* <- empty/all-space string skips folding */
    {
      if (char_isspace (*(char *) (key_p + length - 1)))      /* trailing space present */
        {
          for (p = key_p + length - 1; char_isspace (*p) && (p > key_p); p--) ;  /* scan back, stop at first char */
          length = (int) (p - key_p + 1);
          key_p = new_key_p = (char *) malloc (length + 1);
          if (key_p == NULL)
            return 0;                           /* <- OOM: bail with all-zeros pseudo-key */
          memcpy (key_p, original_key_p, length); *(char *) (key_p + length) = '\0';
        }
      // ... condensed: fold whole 4-byte words into hash_key (+=), then the
      //   leftover bytes, each shift-aligned by its position i ...
      if (new_key_p) free_and_init (new_key_p);
    }

1단계 분기. length > 0 거짓 — 빈 문자열이나 공백만 있는 문자열은 두 폴드 루프를 건너뛰고, hash_key는 0인 채로 2단계로 진입한다. 오류가 아니다. 2단계는 여전히 mht_1/2/3strhash를 0으로 된 중간값 위에서 실행하므로 결정론적인 비제로(non-zero) 유사 키를 산출한다. 후행 공백 있음 — 역방향 스캔((p > key_p) 가드로 첫 번째 문자에서 멈추어 전체 공백 후미는 길이 1로 수렴), length 재계산, original_key_p에서 복사본을 malloc. NULL이면 return 0(엔트리 0) — 문자열 해싱에서 실패할 수 있는 유일한 지점이며, 정상 경로의 return hash_key + Char와 구별되는 별도 탈출구다. 후행 공백 없음 — 폴드를 key_p에 제자리에서 수행하고 아무것도 해제하지 않는다.

2단계는 폴딩된 워드를 재해싱한다.

// ehash_hash_string_type (stage 2) -- src/storage/extendible_hash.c
  memcpy (&copy_psekey, &hash_key, sizeof (EHASH_HASH_KEY));
  copy_psekey[sizeof (EHASH_HASH_KEY)] = '\0';
  hash_key = 0;
  byte = mht_1strhash (copy_psekey, 509); hash_key += (byte << (8 * (sizeof (EHASH_HASH_KEY) - 1)));  /* up 24 */
  byte = mht_2strhash (copy_psekey, 509); hash_key += (byte << (8 * (sizeof (EHASH_HASH_KEY) - 2)));  /* up 16 */
  byte = mht_3strhash (copy_psekey, 509); hash_key += (byte << (8 * (sizeof (EHASH_HASH_KEY) - 3)));  /* up 8 */
  Char = '\0';                                  /* signed char accumulator */
  for (i = 0; i < sizeof (EHASH_HASH_KEY); i++) Char += (char) copy_psekey[i];  /* byte-sum */
  return hash_key + Char;                       /* normal path: add signed sum to the whole word */

mht_1strhash/mht_2strhash/mht_3strhash는 src/base/memory_hash.c에 있는 세 개의 독립적인 문자열 해시 함수로, 각각 mod 509로 축소된다. Mod 509의 범위는 0..508 — 8비트가 아닌 9비트 — 이므로, 각 결과를 시프트한 뒤 더하면 상위 3개 “바이트”가 엄밀히 분리되지 않는다. 255를 초과하는 출력은 다음 바이트로 올림(캐리)이 발생한다. 이는 깔끔한 분리가 아닌 추가 혼합이다. Char는 **부호 있는 char**로 4개의 중간 바이트에 걸쳐 합산되고, return hash_key + Char로 전체 32비트 워드에 더해진다. 캐리가 낮은 바이트를 넘어 전파될 수 있고 음수가 될 수도 있으므로, 하위 비트 교란이지 깔끔한 하위 바이트 기록이 아니다. 이는 바이트를 제자리에서 덮어쓰는 §3.4의 OID 경로와 대조된다.

왜 3단 패킹을 상위 바이트에 적용하는가? CUBRID 클래스명은 긴 공통 접두사를 공유한다(_db_class, _db_attribute, 소유자 한정 이름 등). 단순 폴딩은 가장 상관도 높은 정보를 상위 비트에 놓게 되는데, 그 비트가 FIND_OFFSET이 먼저 읽는 위치이므로 접두사를 공유하는 키들이 같은 버킷으로 충돌한다. 세 가지 알고리즘을 폴딩된 중간값에 적용함으로써 선두 비트들의 상관관계를 제거한다.

3.4 ehash_hash_eight_bytes_type — htonl을 이용한 OID 폴딩

OID는 두 개의 32비트 워드를 htonl로 폴딩한 뒤, 최저 주소 바이트에 XOR 체크섬을 기록한다.

// ehash_hash_eight_bytes_type -- src/storage/extendible_hash.c
  for (i = 0; i < sizeof (double) / sizeof (int); i++)   /* two iterations */
    { memcpy (&Int, key_p, sizeof (int)); hash_key += htonl (Int); key_p += sizeof (int); }
  Char = '\0';
  key_p = (char *) &hash_key;
  for (i = 0; i < sizeof (EHASH_HASH_KEY); i++) Char ^= (char) *key_p++;   /* XOR, not sum */
  memcpy (&hash_key, &Char, sizeof (char));      /* overwrite lowest-addressed byte */
  return hash_key;

문자열 경로와의 차이점이 두 가지 있다. htonl은 폴딩 전에 정규 빅 엔디언 바이트 순서를 강제함으로써, 동일한 논리적 OID가 어떤 호스트에서도 동일하게 해싱되도록 한다. 유사 키는 버킷 배치를 결정하고 복구(recovery) 시에도 재현 가능해야 하기 때문이다. 그리고 체크섬은 memcpy로 최저 주소 바이트를 제자리에서 덮어쓰는 XOR 방식인데, 문자열 경로가 부호 있는 합을 전체 워드에 더하는 것과 다르다. htonl 폴딩과 달리 이 최종 덮어쓰기는 바이트 순서가 정규화되지 않는다. 최저 메모리 바이트는 리틀 엔디언에서는 수치적 LSB지만 빅 엔디언에서는 MSB다. 그러나 단일 호스트 내에서는 일관성이 있으며, 디렉터리는 그것으로 충분하다. 조기 반환은 없다.

3.5 ehash_dir_locate — 인덱스를 (page_no, offset)으로 변환

디렉터리는 하나의 평탄한(flat) EHASH_DIR_RECORD 배열을 여러 페이지에 나누어 저장한다. 루트 페이지는 EHASH_DIR_HEADER도 함께 보유하므로 이후 페이지(EHASH_NUM_NON_FIRST_PAGES)보다 슬롯 수가 적다(EHASH_NUM_FIRST_PAGES). ehash_dir_locate는 평탄 인덱스를 (page_no, 바이트 오프셋)으로 매핑한다.

// ehash_dir_locate -- src/storage/extendible_hash.c
  offset = *out_offset_p;                       /* in: the flat entry index */
  if (offset < EHASH_NUM_FIRST_PAGES)
    { offset = offset * sizeof (EHASH_DIR_RECORD) + EHASH_DIR_HEADER_SIZE;  /* skip header */
      page_no = 0; }                            /* root page */
  else
    { offset -= EHASH_NUM_FIRST_PAGES;          /* relative to page 1 */
      page_no = offset / EHASH_NUM_NON_FIRST_PAGES + 1;
      offset = (offset % EHASH_NUM_NON_FIRST_PAGES) * sizeof (EHASH_DIR_RECORD); }
  *out_page_no_p = page_no;
  *out_offset_p = offset;                       /* out: byte offset within page */

EHASH_NUM_FIRST_PAGES는 (DB_PAGESIZE - EHASH_DIR_HEADER_SIZE) / sizeof(EHASH_DIR_RECORD)이고, EHASH_NUM_NON_FIRST_PAGES는 DB_PAGESIZE / sizeof(EHASH_DIR_RECORD)다. 분기. 인덱스 < EHASH_NUM_FIRST_PAGES → 루트 페이지 (바이트 오프셋 = 인덱스 × 레코드 크기 + EHASH_DIR_HEADER_SIZE, page_no = 0). 그 외 → 이후 페이지: 루트 용량을 빼고, 나눗셈과 나머지 연산 하나씩으로 page_no = 몫 + 1, 오프셋 = 나머지 × 레코드 크기 (헤더 스킵 없음 — 비첫 번째 페이지는 순수 엔트리 배열). API 특이점: 동일한 out_offset_p가 인덱스를 입력으로 받아 바이트 오프셋을 출력으로 돌려준다. 주석 블록에 따르면 매크로 스타일의 / + %는 연속 감산에 비해 일정 시간(constant-time) 연산임을 강조한다.

3.6 ehash_find_bucket_vpid — 인덱스를 버킷 VPID로 조회

인덱스(location)가 주어지면 저장된 VPID를 읽는다. ehash_dir_locate를 호출한 뒤 루트 페이지인지 이후 페이지인지 분기한다.

// ehash_find_bucket_vpid -- src/storage/extendible_hash.c
  ehash_dir_locate (&dir_offset, &location);    /* dir_offset<-page_no, location<-byte offset */
  if (dir_offset != 0)                          /* <- non-root directory page */
    {
      dir_page_p = ehash_fix_nth_page (thread_p, &ehid_p->vfid, dir_offset, latch);
      if (dir_page_p == NULL)
        return ER_FAILED;                       /* <- fix failed */
      dir_record_p = (EHASH_DIR_RECORD *) ((char *) dir_page_p + location);
      pgbuf_unfix_and_init (thread_p, dir_page_p);   /* read VPID below, then release */
    }
  else                                          /* <- root page, already pinned by caller */
    dir_record_p = (EHASH_DIR_RECORD *) ((char *) dir_header_p + location);
  *out_vpid_p = dir_record_p->bucket_vpid;
  return NO_ERROR;

인자 순서 교환에 주목한다. ehash_dir_locate (&dir_offset, &location)은 페이지 번호를 dir_offset(out_page_no_p)에 기록하고 바이트 오프셋을 location(입출력 out_offset_p)에 기록한다. 분기. dir_offset이 페이지 번호다. != 0: 디렉터리 페이지 1, 2, … 위의 엔트리; ehash_fix_nth_page가 file_numerable_find_nth로 n번째 번호 지정 페이지를 찾아 고정한다. NULL → ER_FAILED (호출자가 루트를 해제); 그 외 bucket_vpid 값 복사 후 즉시 unfix. == 0: 루트 페이지 위의 엔트리로, 호출자가 dir_header_p로 이미 보유 중; latch를 소비하지 않는다.

INVARIANT — latch 파라미터는 비루트 디렉터리 페이지에만 적용된다. 루트는 ehash_find_bucket_vpid_with_hash가 root_latch 하에 한 번 고정하고, 이 함수는 절대 재고정하지 않는다. latch는 dir_offset != 0 분기에서만 소비되고 반환 전에 해제(pgbuf_unfix_and_init)된다. 위반 시 (루트 분기에서 동일 페이지를 재고정) 스레드가 이미 보유 중인 페이지를 다시 latch하려 시도한다.

3.7 NULL_PAGEID 디렉터리 홀

ehash_find_bucket_vpid는 VPID를 읽는 데 항상 성공하지만, 그 값이 { NULL_PAGEID, … } — 디렉터리 홀(directory hole) — 일 수 있다. 이는 두 배 확장(7장)이나 병합(8장) 이후에 살아있는 버킷을 가리키지 않는 슬롯이다. 이 계층은 NO_ERROR를 반환하고 호출자가 판단하도록 위임한다.

// ehash_search (caller) -- src/storage/extendible_hash.c
  if (bucket_vpid.pageid == NULL_PAGEID)
    { result = EH_KEY_NOTFOUND; goto end; }     /* <- a hole means the key cannot exist here */

검색과 삭제는 홀을 “키 없음”(EH_KEY_NOTFOUND)으로 읽고, 삽입은 “먼저 버킷을 생성하고 연결하라”는 신호로 읽는다. 이것은 정상적인 주소 결정 결과이지 실패가 아니다. ER_FAILED는 페이지 고정 실패에만 예약된다.

3.8 ehash_find_bucket_vpid_with_hash — 모든 CRUD 경로가 호출하는 래퍼

루트를 고정하고, 해싱하고, 인덱스를 계산하고, VPID를 조회한다. 필요에 따라 해시 키(삽입이 분할에 필요)와 인덱스(병합에 필요)를 반환 옵션으로 제공한다.

// ehash_find_bucket_vpid_with_hash -- src/storage/extendible_hash.c
  dir_root_page_p = ehash_fix_ehid_page (thread_p, ehid_p, root_latch);
  if (dir_root_page_p == NULL)
    return NULL;                                   /* <- root fix failed */
  dir_header_p = (EHASH_DIR_HEADER *) dir_root_page_p;
  hash_key = ehash_hash (key_p, dir_header_p->key_type);   /* type from header */
  if (out_hash_key_p) *out_hash_key_p = hash_key;          /* optional out */
  location = FIND_OFFSET (hash_key, dir_header_p->depth);   /* top `depth` bits */
  if (out_location_p) *out_location_p = location;          /* optional out */
  if (ehash_find_bucket_vpid (thread_p, ehid_p, dir_header_p, location, bucket_latch, out_vpid_p) != NO_ERROR)
    {
      pgbuf_unfix_and_init (thread_p, dir_root_page_p);     /* <- release root on failure */
      return NULL;
    }
  return dir_root_page_p;                          /* <- success: caller still holds root */

분기. 루트 고정 실패 (== NULL): NULL 반환, 보유 중인 것 없음. out_hash_key_p/out_location_p 비NULL: 각각 저장; NULL이면 건너뜀. ehash_find_bucket_vpid 실패: 루트 unfix 후 NULL 반환 — 래퍼가 오류 경로에서 루트의 생존 주기를 소유한다. 성공: 여전히 고정된 루트 페이지를 반환한다. 호출자는 root_latch 하에 핀된 루트 페이지, out_vpid_p의 VPID, 선택적으로 해시 키/인덱스를 받으며, 완료 후 루트를 반드시 unfix해야 한다.

root_latch는 루트를, bucket_latch는 비루트 디렉터리 페이지를 제어한다(ehash_search는 둘 다 PGBUF_LATCH_READ로 읽고, 삽입/삭제는 쓰기 latch를 사용한다). 키 타입은 dir_header_p->key_type에서 가져온다(2장).

stateDiagram-v2
  [*] --> 루트고정
  루트고정 --> NULL반환1: 루트 고정 실패
  루트고정 --> 해시계산: root_latch 하에 루트 핀됨
  해시계산 --> 오프셋계산: hash_key 산출, 선택적 출력 저장
  오프셋계산 --> VPID조회: location = 상위 depth 비트
  VPID조회 --> NULL반환2: ehash_find_bucket_vpid ER_FAILED \n 루트 unfix
  VPID조회 --> 성공: NO_ERROR, out_vpid 채워짐
  성공 --> [*]: 핀된 루트 페이지 반환
  NULL반환1 --> [*]
  NULL반환2 --> [*]

Figure 3-1 — ehash_find_bucket_vpid_with_hash, 전체 흐름.

3.9 챕터 요약 — 핵심 정리

주소 결정 골격은 해시 → FIND_OFFSET → VPID 조회이며, ehash_find_bucket_vpid_with_hash로 감싸진다. 이것이 모든 CRUD 경로가 사용하는 단일 진입점이다.
ehash_hash는 두 개의 활성 분기를 가진다. DB_TYPE_STRING → ehash_hash_string_type, DB_TYPE_OBJECT → ehash_hash_eight_bytes_type; default는 ER_EH_CORRUPTED를 발생시키고 0을 반환한다.
FIND_OFFSET은 32비트 EHASH_HASH_KEY에서 수치적 상위 depth 비트를 읽는다(값 오른쪽 시프트, 바이트 순서 독립적). 해시 함수는 가장 변화량이 큰 출력을 그곳에 두고 체크섬을 하위 비트에 배치한다. 문자열 측은 부호 있는 합을 전체 워드에 더하고, OID 측은 XOR을 최저 주소 바이트에 덮어쓰는데, 후자는 리틀 엔디언 호스트에서만 수치적 LSB에 해당한다.
문자열 해싱은 세 가지 mod-509 알고리즘을 상위 바이트에 적용하여 공유된 클래스명 접두사의 상관관계를 제거한다. 유일한 실패 탈출구는 후행 공백 처리에서의 malloc NULL 반환(return 0)이다.
OID 해싱은 엔디언 독립적이고 복구 재현 가능한 폴딩을 위해 htonl을 사용하고, 그 다음 최저 주소 바이트에 체크섬을 XOR로 제자리 기록하며, 조기 반환이 없다.
ehash_dir_locate/ehash_find_bucket_vpid는 루트 대 이후 페이지로 분기한다. 루트는 호출자가 미리 핀해두며(고정 없음, latch 없음), 이후 페이지는 ehash_fix_nth_page로 고정, 읽기, 해제한다. latch는 비루트 분기에서만 소비된다.
NULL_PAGEID VPID는 디렉터리 홀로, NO_ERROR로 반환된다. 이는 “키가 여기 없음”을 의미하는 정상적인 결과이며, 페이지 고정 실패에 예약된 ER_FAILED와 명확히 구별된다.

Chapter 4: 버킷 내부 탐색

Chapter 3는 디렉터리가 해시된 키를 단일 bucket_vpid로 변환하는 시점에서 끝났다. 이 챕터는 그 다음 질문에 답한다: 버킷 페이지가 주어졌을 때, 사용자 키를 어떻게 찾고 OID를 돌려주는가? 읽기 경로는 확장 가능 해시(extendible hash) 연산 중 가장 가벼운 부류에 속한다 — 페이지를 수정하지 않으며 공유 latch만 보유한다. 그러나 버킷 내부 레이아웃과 두 단계 latch 프로토콜은 ehash_insert나 ehash_delete를 손대려는 사람이라면 반드시 이해해야 할 만큼 미묘하다. ehash_search와 그 보조 함수 ehash_locate_slot, ehash_binary_search_bucket, ehash_compare_key, ehash_read_oid_from_record를 순서대로 따라간다. bucket_vpid를 생성하는 디렉터리 탐색은 Chapter 3를, UNANCHORED_KEEP_SEQUENCE 동작 원리는 Chapter 2를, 이론적 배경은 고수준 동반 문서(cubrid-extendible-hash.md, “버킷 구조와 로컬 깊이” 절)를 참조한다.

4.1 버킷 내부 레코드 레이아웃

모든 보조 함수는 버킷 페이지 초기화 시 확정된 레이아웃에 의존한다:

// ehash_initialize_bucket_new_page -- src/storage/extendible_hash.c
spage_initialize (thread_p, page_p, UNANCHORED_KEEP_SEQUENCE, alignment, DONT_SAFEGUARD_RVSPACE);

UNANCHORED_KEEP_SEQUENCE가 핵심 선택이다: 슬롯 배열을 레코드 내용 순서로 정렬하므로, 중간에 레코드를 삽입하더라도 슬롯이 사용자 키의 오름차순을 유지한다 — 이진 탐색이 합법적인 유일한 이유다.

각 데이터 레코드(슬롯 1..N; 슬롯 0은 EHASH_BUCKET_HEADER)는 OID 먼저, 키 나중 구조다 — recdes.data는 sizeof(OID) 바이트(pageid|volid|slotid)를 먼저 담고, 이어서 가변 길이 사용자 키가 온다. B+Tree 리프와 순서가 반대임에 주의하라. 오프셋 0에 고정 폭 OID가 있으므로, 값 읽기 함수는 고정 stride로 복사할 수 있고 비교 함수는 키를 측정하지 않고 += sizeof(OID) 한 번으로 건너뛸 수 있다.

Figure 4-1 — 버킷 페이지 슬롯과 (OID ‖ 키) 레코드 하나의 바이트 레이아웃

Figure 4-1. 버킷 데이터 레코드 하나; 값 읽기와 키 비교가 각각 반대쪽 절반에 접근한다.

4.2 `ehash_search` 전체 흐름

ehash_search는 유일한 공개 진입점이다. 기본값을 설정하고, 첫 번째 가드를 latch 획득 전에 수행한 뒤, Chapter 3의 탐색으로 루트를 fix하고 bucket_vpid를 채운다:

// ehash_search -- src/storage/extendible_hash.c
EH_SEARCH result = EH_KEY_NOTFOUND;   /* <- 비관적 기본값 */
if (ehid_p == NULL || key_p == NULL)
  return EH_KEY_NOTFOUND;             /* <- 가드 1: 잘못된 인수, 페이지 미고정, 직접 반환 */
dir_root_page_p =
  ehash_find_bucket_vpid_with_hash (thread_p, ehid_p, key_p, PGBUF_LATCH_READ, PGBUF_LATCH_READ, &bucket_vpid,
                                    NULL, NULL);          /* <- 루트+버킷 탐색 모두 READ */
if (dir_root_page_p == NULL)
  return EH_ERROR_OCCURRED;            /* <- 가드 2: 디렉터리 오류; 루트 미반환 */
dir_header_p = (EHASH_DIR_HEADER *) dir_root_page_p;     /* <- key_type은 헤더에 존재 */

가드 1 — null ehid/key. 아무것도 fix하지 않은 상태이므로 직접 반환한다; 잘못된 인수는 오류가 아닌 “키 없음”으로 처리한다.

가드 2 — 디렉터리 오류. 헬퍼가 NULL을 반환하면 EH_ERROR_OCCURRED를 직접 반환한다 — 헬퍼가 내부 상태를 정리하므로 페이지가 보유되지 않는다. PGBUF_LATCH_READ, PGBUF_LATCH_READ 쌍은 이 함수를 순수 읽기 연산으로 만든다; 버킷은 여기서 fix되지 않고 VPID만 확인된다. 이 지점 이후에는 루트가 fix된 상태이므로, 나머지 세 종료 경로는 모두 end:를 거친다:

// ehash_search -- src/storage/extendible_hash.c
if (bucket_vpid.pageid == NULL_PAGEID)     /* <- 가드 3: 디렉터리 홀(hole) */
  { result = EH_KEY_NOTFOUND; goto end; }

bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid, &bucket_vpid, PGBUF_LATCH_READ);
if (bucket_page_p == NULL)                 /* <- 가드 4: 버킷 fix 실패 */
  { result = EH_ERROR_OCCURRED; goto end; }

if (ehash_locate_slot (thread_p, bucket_page_p, dir_header_p->key_type, key_p, &slot_id) == false)
  { result = EH_KEY_NOTFOUND; goto end; }  /* <- 가드 5: 키 없음 */
(void) spage_get_record (thread_p, bucket_page_p, slot_id, &recdes, PEEK);   /* <- PEEK: 복사 없음 */
(void) ehash_read_oid_from_record (recdes.data, value_p);                    /* <- OID 추출 */
result = EH_KEY_FOUND;

가드 3 — 디렉터리 홀(NULL_PAGEID). 포인터가 “버킷 없음”을 나타낼 수 있다; 해당 프리픽스가 빈 영역에 매핑되므로 키가 존재할 수 없다. 두 번째 페이지를 fix하지 않고 정리로 점프한다 — 탐색 비용이 하나의 fix로 끝날 수 있는 이유다. 가드 4 — 버킷 fix 실패. bucket_vpid가 non-null이지만 페이지를 fix할 수 없을 때(I/O 오류, 해제됨): EH_ERROR_OCCURRED.

가드 5 — 키 없음. ehash_locate_slot이 false를 반환하면 slot_id는 삽입 예정 위치다(읽기 경로에서는 사용되지 않지만 Chapter 5의 삽입 경로에서 활용된다).

히트 경로. true 반환 시 slot_id가 해당 슬롯을 가리킨다. PEEK으로 호출한 spage_get_record는 페이지 버퍼를 직접 가리키는 recdes를 반환한다 — 복사 없이 latch 보유 중에만 유효하다 — 따라서 OID를 unfix 이전에 value_p에 복사하고 result를 EH_KEY_FOUND로 설정한다.

불변 조건 — 가드 2 이후의 모든 경로는 end:를 거친다. 루트가 fix된 이후의 유일한 출구는 end:다(가드 3·5는 goto end, 히트는 fall-through); 직접 반환하면 그 페이지가 누수된다. 가드 1과 2만 직접 반환하는데, 페이지를 보유하지 않으므로 올바르다.

// ehash_search -- src/storage/extendible_hash.c
end:
  if (bucket_page_p)
    pgbuf_unfix_and_init (thread_p, bucket_page_p);   /* <- 버킷 먼저 해제 */
  if (dir_root_page_p)
    pgbuf_unfix_and_init (thread_p, dir_root_page_p); /* <- 이후 루트 해제 */
  return result;

Latch 해제 순서: 버킷 먼저, 루트 나중. 각 if (ptr)은 어떤 상태에서든 레이블에 도달할 수 있게 하고(가드 3/5는 루트만, 히트 시에는 둘 다), pgbuf_unfix_and_init은 unfix와 포인터 null화를 함께 수행하므로 획득하지 않은 페이지는 no-op이 된다. 리프를 먼저 해제하는 것은 획득 순서의 역순이다.

flowchart TD
  A["ehash_search"] --> B{"ehid 또는 key가 NULL?"}
  B -->|yes| R1["가드 1: NOTFOUND 반환<br/>(페이지 미보유)"]
  B -->|no| C["find_bucket_vpid_with_hash<br/>루트+버킷 READ"]
  C --> D{"루트가 NULL?"}
  D -->|yes| R2["가드 2: ERROR 반환<br/>(페이지 미보유)"]
  D -->|no| E{"bucket_vpid == NULL_PAGEID?"}
  E -->|yes| F1["가드 3: NOTFOUND; goto end"]
  E -->|no| G["ehash_fix_old_page READ"]
  G --> H{"버킷이 NULL?"}
  H -->|yes| F2["가드 4: ERROR; goto end"]
  H -->|no| I{"locate_slot == false?"}
  I -->|yes| F3["가드 5: NOTFOUND; goto end"]
  I -->|no| J["get_record PEEK; read_oid<br/>result=FOUND"]
  F1 --> K["end:"]
  F2 --> K
  F3 --> K
  J --> K
  K --> L["버킷 해제 (보유 시)"] --> M["루트 해제 (보유 시)"] --> N["result 반환"]

Figure 4-2. ehash_search — 다섯 가지 가드 분기와 공유 정리 구간.

4.3 `ehash_locate_slot` — 빈 버킷 엣지 케이스

위임하기 전에 빈 버킷 엣지 케이스를 처리한다:

// ehash_locate_slot -- src/storage/extendible_hash.c
num_record = spage_number_of_records (bucket_page_p) - 1;   /* <- 헤더 슬롯 제외 */
if (num_record < 1)                                         /* <- 헤더만 있는 버킷 */
  {
    if (spage_next_record (bucket_page_p, &first_slot_id, &recdes, PEEK) != S_SUCCESS)
      { er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
        *out_position_p = 1; return false; }                /* <- 손상: 헤더 없음 */
    *out_position_p = first_slot_id + 1;                    /* <- 헤더 바로 다음 삽입 위치 */
    return false;
  }
return ehash_binary_search_bucket (thread_p, bucket_page_p, num_record, key_type, key_p, out_position_p);

두 분기로 나뉜다. num_record < 1 (빈 버킷): false를 반환한다; 삽입 경로에 슬롯 위치를 넘겨주기 위해 first_slot_id = -1로 spage_next_record를 호출해 헤더를 가져온 뒤 *out_position_p = first_slot_id + 1로 그 다음 위치를 설정한다. 중첩 분기는 헤더조차 읽을 수 없을 때만 — 치명적 ER_EH_CORRUPTED. 빈 버킷은 이진 탐색에 진입하지 않는다. num_record >= 1: 이진 탐색으로 위임한다.

불변 조건 — 이진 탐색은 num_record >= 1일 때만 진입한다. do { } while 본문은 종료 조건 검사 전에 실행되므로 num_record == 0이면 high < low로도 안전을 보장받지 못한다; ehash_locate_slot이 빈 버킷 케이스를 루프 외부에서 처리함으로써 이를 보장한다.

4.4 `ehash_binary_search_bucket` — O(log m) 탐색

1..num_record에 대한 이진 탐색:

// ehash_binary_search_bucket -- src/storage/extendible_hash.c
low = 1;
high = num_record;
do
  {
    middle = (high + low) >> 1;                              /* <- 중간 슬롯 */
    if (spage_get_record (thread_p, bucket_page_p, middle, &recdes, PEEK) != S_SUCCESS)
      { er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
        return false; }                                      /* <- 슬롯 읽기 실패 => 손상 */
    bucket_record_p = (char *) recdes.data;
    bucket_record_p += sizeof (OID);                         /* <- OID 건너뛰고 키 바이트 포인터 */
    if (ehash_compare_key (thread_p, bucket_record_p, key_type, key_p, recdes.type, &compare_result) != NO_ERROR)
      return false;                                          /* <- 비교 함수 오류 경로 */
    if (compare_result == 0)
      { *out_position_p = middle; return true; }             /* <- 히트 */
    if (compare_result < 0)
      high = middle - 1;                                     /* <- key < record: 왼쪽으로 */
    else
      low = middle + 1;                                      /* <- key > record: 오른쪽으로 */
  }
while (high >= low);

+= sizeof(OID)는 §4.1 레이아웃에 대한 의존성이다; compare_result는 key - record 의미다(음수 = 키가 먼저 정렬됨). 루프를 벗어나는 경로는 세 가지: 슬롯 손상(→ ER_EH_CORRUPTED, false, 위치 미설정), 비교 함수 오류(알 수 없는 타입, §4.5 → false, 위치 미설정), 히트(== 0 → middle, true).

fall-through 시(high < low, 키 없음) 꼬리 부분이 삽입 위치를 계산한다: if (high < middle) *out_position_p = middle; else *out_position_p = middle + 1; return false; — high가 마지막으로 탐색한 middle 아래로 내려갔다면 키는 middle 위치에, 그렇지 않으면 middle + 1에 삽입된다. 읽기 경로는 이 값을 무시하고, Chapter 5의 삽입 경로가 UNANCHORED_KEEP_SEQUENCE 순서를 유지하며 레코드를 끼워 넣는 데 사용한다.

flowchart TD
  A["low=1, high=num_record"] --> B["middle=(high+low)>>1"]
  B --> C{"get_record 성공?"}
  C -->|no| X1["ER_EH_CORRUPTED; false"]
  C -->|yes| E{"compare_key 성공?"}
  E -->|no| X2["false: 잘못된 키 타입"]
  E -->|yes| F{"compare_result"}
  F -->|== 0| H["*pos=middle; true 히트"]
  F -->|< 0| G1["high=middle-1"]
  F -->|> 0| G2["low=middle+1"]
  G1 --> I{"high >= low?"}
  G2 --> I
  I -->|yes| B
  I -->|no| J{"high < middle?"}
  J -->|yes| K1["*pos=middle"] --> L["false: MISS, 삽입 위치 설정"]
  J -->|no| K2["*pos=middle+1"] --> L

Figure 4-3. ehash_binary_search_bucket — 두 치명적 경로, 히트, 두 가지 미스 위치.

4.5 `ehash_compare_key` — 타입별 3-way 비교

key_type에 따라 분기한다; 두 케이스만 활성화되어 있고 나머지는 ENABLE_UNUSED_FUNCTION으로 펜스 처리되어 있다:

// ehash_compare_key -- src/storage/extendible_hash.c
switch (key_type)
  {
  case DB_TYPE_STRING:
    compare_result = ansisql_strcmp ((char *) key_p, bucket_record_p);   /* <- 콜레이션 인식 비교 */
    break;
  case DB_TYPE_OBJECT:
    compare_result = oid_compare ((OID *) key_p, (OID *) bucket_record_p);  /* <- OID 키 해시 */
    break;
  /* ... condensed: DOUBLE/FLOAT/INTEGER/BIGINT/SHORT/DATE/TIME/TIMESTAMP/
     DATETIME/MONETARY all under ENABLE_UNUSED_FUNCTION ... */
  default:
    /* Unspecified key type: Directory header has been corrupted */
    er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
    return ER_EH_CORRUPTED;            /* <- non-NO_ERROR => 호출자가 false 반환 */
  }

*out_compare_result_p = compare_result;
return NO_ERROR;

**DB_TYPE_STRING**은 OID 다음에 오는 NUL-종료 키 바이트를 ansisql_strcmp로 비교한다. (긴 키 REC_BIGONE/오버플로 처리는 ENABLE_UNUSED_FUNCTION 아래 컴파일 제외됨 — record_type의 유일한 사용처이므로, 활성 경로에서는 이를 무시한다.) **DB_TYPE_OBJECT**는 oid_compare에 위임한다: 해시가 OID 키 인덱스(예: 카탈로그)이므로 양쪽 키 모두 OID다. **default**는 손상된 key_type을 의미하며 ER_EH_CORRUPTED를 반환한다 — §4.4의 exit 2가 이를 false로 전환한다. 결과 값은 NO_ERROR일 때만 기록되며, 상태와 값을 분리함으로써 default가 “비교 불가”와 “동등 비교”를 구분할 수 있게 한다. 호출자는 반드시 반환 코드를 확인해야 한다.

4.6 `ehash_read_oid_from_record` — PEEK으로 값 추출

OID는 오프셋 0에 있으므로(§4.1), 읽기 함수는 키가 아닌 세 개의 고정 필드를 복사한다:

// ehash_read_oid_from_record -- src/storage/extendible_hash.c
oid_p->pageid = *(PAGEID *) record_p;
record_p += sizeof (PAGEID);
oid_p->volid = *(VOLID *) record_p;
record_p += sizeof (VOLID);
oid_p->slotid = *(PGSLOTID *) record_p;
record_p += sizeof (PGSLOTID);
return record_p;                       /* <- 이제 키 바이트를 가리킴 */

필드별 읽기는 인코딩을 인메모리 패딩에 독립적으로 유지한다; 전체 stride는 정확히 sizeof(OID)(§4.4가 건너뛴 폭)이므로, 반환값은 키 바이트를 가리킨다 — ehash_search는 이를 (void)로 버리고, 삭제/덤프 경로는 재사용한다. 레코드가 PEEK로 획득되었으므로 record_p는 페이지를 직접 참조하며, value_p로의 이 복사가 OID를 unfix 이후에도 생존하게 한다. 키의 복사는 한 번도 이루어지지 않는다 — 꼬리 부분은 스캔하지 않고 건너뛴다.

4.7 두 페이지 fix 비용

성공적인 ehash_search는 정확히 두 페이지를 fix한다 — 루트와 버킷, 모두 PGBUF_LATCH_READ — 전체 탐색을 그 latch 안에서 수행하고 최종 OID 외에는 아무것도 복사하지 않는다; 가드 3의 디렉터리 홀은 fix 하나로 끝나고, §4.3의 빈 버킷은 이진 탐색 없이 fix 두 개를 사용하며, 리프는 루트보다 먼저 해제된다(§4.2). Chapter 10에서 이 latch들이 동시 split·merge와 어떻게 결합되는지 다룬다.

4.8 챕터 요약 — 핵심 정리

ehash_search는 다섯 개의 가드 분기를 갖는다 — null 인수, 루트 fix 실패, NULL_PAGEID 홀, 버킷 fix 실패, 키 없음; 마지막 세 개만 goto end하며, 루트가 fix된 상태에서 실행되기 때문이다.
불변 조건: 루트 fix 이후의 모든 경로는 end:를 거쳐 버킷 먼저, 루트 나중 순으로 unfix하며, 각 if (ptr) 덕분에 어떤 상태에서도 해당 레이블에 도달할 수 있다.
레코드는 UNANCHORED_KEEP_SEQUENCE 하에 OID 먼저, 키 나중 구조로 슬롯을 사용자 키 순서로 유지한다 — O(log m) 탐색의 유일한 전제 조건이다; ehash_locate_slot은 빈 버킷 엣지(num_record < 1)를 루프 외부에서 처리하며, do/while 본문이 종료 조건 검사 전에 실행되기 때문이다.
ehash_binary_search_bucket은 비교 전 sizeof(OID)를 건너뛰고, 히트 시 슬롯을 반환하며, 미스 시 삽입 위치(middle 또는 middle + 1)를 계산한다; ehash_compare_key는 DB_TYPE_STRING/ansisql_strcmp와 DB_TYPE_OBJECT/oid_compare를 분기하며, default는 ER_EH_CORRUPTED를 발생시킨다 — 상태는 반환 코드로, 3-way 결과는 out-of-band로 전달한다.
ehash_read_oid_from_record는 sizeof(OID) 프리픽스에 대한 필드별 PEEK 복사로 값을 추출하며, 키를 스캔하지 않는다; 히트 시 두 READ-latch 페이지 fix 비용이 발생하고, 디렉터리 홀의 경우 하나만 발생한다.

Chapter 5: 여유 있는 버킷에 삽입하기

이 챕터는 하나의 질문에 답한다: 대상 버킷에 빈 공간이 있을 때 (key, OID) 쌍이 어떻게 기록되는가, 그리고 ehash_insert가 왜 upsert인가? ehash_insert_helper의 낙관적 S-latch 오케스트레이션, ehash_insert_to_bucket의 레코드 처리, WAL 마무리까지 순서대로 추적한다. 분할(split)은 이 챕터에서 다루지 않는다 — 가득 찬 버킷은 EHASH_BUCKET_FULL을 반환하고 X 잠금으로 재시도하는데, 그 재시도와 분할은 챕터 6의 내용이다. 주소 결정은 챕터 3, 버킷 이진 탐색은 챕터 4, upsert/WAL 설계 배경은 컴패니언 문서의 Insert 및 WAL integration — RVEH_* records 절에서 다룬다.

5.1 두 겹의 latch 춤: `ehash_insert`와 `ehash_insert_helper`

ehash_insert는 얇은 래퍼다. ehid_p/key_p에 대한 null 검사를 마친 뒤 ehash_insert_helper (..., S_LOCK, NULL)을 꼬리 호출한다 — 디렉터리에 초기 S(공유) lock을 건다.

S_LOCK은 낙관주의를 인코딩한다: 대부분의 삽입은 여유 있는 기존 버킷에 안착하여 버킷 페이지 하나만 건드리고 디렉터리는 전혀 수정하지 않으므로, 공유 루트 latch 하나로 여러 쓰기 작업이 동시에 진행될 수 있다. lock_type은 헬퍼를 낙관적 첫 시도와 비관적 X 재시도 모두에서 구동하는 역할을 한다.

ehash_insert_helper가 실질적인 드라이버다. 파일이 임시 파일인지 여부를 먼저 파악한 뒤(WAL 방출 여부를 결정), ehash_find_bucket_vpid_with_hash(챕터 3)를 호출해 키를 슬롯으로 변환한다. 이 때 lock_type에 따라 루트 latch를 PGBUF_LATCH_READ(S인 경우) 또는 PGBUF_LATCH_WRITE(X인 경우)로 건다. NULL이 반환되면 에러를 전파한다. 헤더를 확보한 상태에서 버킷에 접근하기 전에 문자열 키의 길이를 먼저 검증한다:

// ehash_insert_helper -- src/storage/extendible_hash.c
if (dir_header_p->key_type == DB_TYPE_STRING)
  { assert (strlen ((char *) key_p) < 256); }   /* <- max class-name length */

Invariant — 문자열 키는 255바이트 이하(NUL 포함 256바이트). 실제 호출자는 클래스 이름을 삽입하며 스키마 수준에서 255자로 제한된다. 긴 문자열 오버플로우 분기는 컴파일 아웃(ENABLE_UNUSED_FUNCTION)되어 있다. 이 규칙이 깨지면 더 긴 키는 ehash_compose_record의 assert (key_size <= 256)에서 걸리거나, 오버플로우 페이지 없이 잘린 레코드를 만들어낸다.

헬퍼는 슬롯에 이미 버킷이 명시되어 있는지 여부에 따라 분기한다(Figure 5-1). 네 개의 리프 중 두 개는 X_LOCK으로 재귀 호출 — 챕터 6으로 넘어가는 다리다.

flowchart TD
  B["find_bucket_vpid_with_hash\nS이면 READ, X이면 WRITE"] -->|"루트 NULL"| ERR["NULL 반환"]
  B --> C{"bucket_vpid NULL?"}
  C -->|"예"| D{"S_LOCK?"}
  D -->|"예"| R1["unfix; X_LOCK으로 재귀"]
  D -->|"X"| E["insert_to_bucket_after_create"]
  E -->|"NO_ERROR"| OK["key_p 반환"]
  E -->|"err"| ERR
  C -->|"아니오"| F["insert_bucket_after_extend_if_need"]
  F -->|"ERROR"| ERR
  F -->|"BUCKET_FULL"| R2["unfix; X_LOCK으로 재귀 -> Ch 6"]
  F -->|"SUCCESS"| OK

Figure 5-1 — ehash_insert_helper의 분기 지도. 두 개의 X_LOCK으로 재귀 리프가 S→X 승격 지점이다.

latch를 제자리에서 업그레이드하는 경로는 없다. 각 승격 지점에서는 루트를 unfix하고 X_LOCK으로 재진입한다 — 슬롯이 비어 있을 때 하나, 기존 버킷이 가득 찼을 때 하나 — 동일한 pgbuf_unfix_and_init + 재귀 호출 패턴을 사용한다:

// ehash_insert_helper -- src/storage/extendible_hash.c
if (VPID_ISNULL (&bucket_vpid))
  {
    if (lock_type == S_LOCK)            /* slot empty under S: RESTART */
      { pgbuf_unfix_and_init (thread_p, dir_root_page_p);
        return ehash_insert_helper (thread_p, ehid_p, key_p, value_p, X_LOCK, existing_ovf_vpid_p); }
    else if (ehash_insert_to_bucket_after_create (/* ... */) != NO_ERROR)   /* under X: create (Ch 2/6) */
      { pgbuf_unfix_and_init (thread_p, dir_root_page_p); return NULL; }
  }
else
  {
    result = ehash_insert_bucket_after_extend_if_need (/* ... */ lock_type, /* ... */);
    if (result == EHASH_ERROR_OCCURRED)
      { pgbuf_unfix_and_init (thread_p, dir_root_page_p); return NULL; }
    else if (result == EHASH_BUCKET_FULL)   /* full under S: RESTART (identical recurse as above) */
      { /* ... unfix + return ehash_insert_helper (..., X_LOCK, ...) ... */ }
  }
pgbuf_unfix_and_init (thread_p, dir_root_page_p);
return (key_p);                         /* <- non-NULL key_p signals success */

Invariant — 분할은 디렉터리 루트에 대한 X latch를 요구한다. 분할은 디렉터리를 두 배로 늘릴 수 있으므로 공유 latch 하에서는 절대 실행될 수 없다. 코드는 S_LOCK 하에서 분할을 거부하는 방식으로 이를 강제한다: ehash_insert_bucket_after_extend_if_need는 EHASH_BUCKET_FULL을 반환하고 헬퍼는 X_LOCK으로 재시작한다. 이 규칙이 깨지면 두 쓰기 작업이 동시에 디렉터리를 두 배로 늘려 팬아웃(fan-out)을 망가뜨릴 수 있다.

5.2 버킷을 고정하고 분할 vs. 삽입을 결정하기: `ehash_insert_bucket_after_extend_if_need`

슬롯에 이미 버킷이 명시되어 있으면 헬퍼는 이 함수에 위임한다. 계약: 버킷에 X(WRITE) latch를 걸고 삽입을 시도한다. X 하에서 가득 찬 경우에만 분할 후 올바른 절반에 재삽입한다. 세 가지 EHASH_RESULT 중 하나를 반환한다(Figure 5-1):

// ehash_insert_bucket_after_extend_if_need -- src/storage/extendible_hash.c
bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid, bucket_vpid_p, PGBUF_LATCH_WRITE);  /* always X */
if (bucket_page_p == NULL)
  { return EHASH_ERROR_OCCURRED; }
result = ehash_insert_to_bucket (thread_p, ehid_p, /* ... */ bucket_page_p, /* ... */);
if (result == EHASH_BUCKET_FULL)
  {
    if (lock_type == S_LOCK)            /* cannot split under S: bubble up for the X restart */
      { pgbuf_unfix_and_init (thread_p, bucket_page_p); return EHASH_BUCKET_FULL; }
    // ... split (Ch 6): ehash_extend_bucket -> &new_bit, re-insert into
    //     target = new_bit ? sibling_page_p : bucket_page_p; unfix sibling ...
  }
pgbuf_unfix_and_init (thread_p, bucket_page_p);
return result;

버킷 페이지는 여기서 항상 X-latch로 고정된다 — 낙관적 S 시도에서도 마찬가지다. 춤에서의 S는 디렉터리 latch를 가리키며, 버킷 쓰기는 잠금 유형에 무관하게 항상 배타적이어야 한다. new_bit와 ehash_extend_bucket은 챕터 6의 내용이다. 이 챕터의 비-full 케이스: ehash_insert_to_bucket이 EHASH_SUCCESSFUL_COMPLETION을 반환하면 EHASH_BUCKET_FULL 블록은 건너뛰고 성공이 상위로 전파된다.

5.3 레코드 수준의 엔진: `ehash_insert_to_bucket`

upsert 로직이 여기 있다. 이 함수는 ehash_locate_slot으로 키를 찾은 뒤 두 경로 중 하나를 택한다. Figure 5-2가 모든 분기를 추적한다.

flowchart TD
  B["locate_slot -> slot_no"] --> C{"키 발견?"}
  C -->|"예(upsert)"| E["이전 레코드를 pre-image로 복사\nwrite_oid가 OID를 제자리 덮어씀"]
  E -->|"alloc 실패"| ERR["ERROR_OCCURRED 반환"]
  E --> LOG
  C -->|"아니오(신규 삽입)"| F["compose_record"]
  F -->|"err"| ERR
  F --> G["spage_insert_at(slot_no)"]
  G -->|"SP_DOESNT_FIT"| FULL["free; BUCKET_FULL 반환"]
  G -->|"SP_SUCCESS 외 다른 값"| ERR
  G -->|"SP_SUCCESS"| LOG
  LOG["WAL 방출: undo 논리적 + redo 물리적\n(is_replaced_oid 분기; §5.5 참조)"] --> Z["free; set_dirty; SUCCESS 반환"]

Figure 5-2 — ehash_insert_to_bucket의 모든 분기. WAL 노드는 §5.5에서 상세히 다룬다.

Step 1 — 위치 탐색. ehash_locate_slot은 true/false를 반환하며 slot_no를 채운다. num_record = spage_number_of_records (bucket_page_p) - 1을 계산하여 이 값이 < 1이면 버킷에는 1바이트짜리 EHASH_BUCKET_HEADER(챕터 2의 local_depth 바이트)만 들어 있다는 뜻이므로 빈 버킷 지름길을 택한다(slot_no = first_slot_id + 1, 헤더 바로 다음 슬롯). 그렇지 않으면 ehash_binary_search_bucket(챕터 4)으로 넘긴다. false가 반환될 때 slot_no는 버킷의 정렬 순서를 유지하는 삽입 위치다.

Step 2a — 키 발견 경로(upsert / OID 교체). 기존 레코드를 peek하여 새로 할당한 bucket_recdes에 복사한다(pre-image, undo용). 그런 다음 라이브 레코드의 OID를 제자리에서 덮어쓴다:

// ehash_insert_to_bucket -- src/storage/extendible_hash.c
if (ehash_locate_slot (thread_p, bucket_page_p, key_type, key_p, &slot_no) == true)
  {
    (void) spage_get_record (thread_p, bucket_page_p, slot_no, &old_bucket_recdes, PEEK);
    bucket_record_p = (char *) old_bucket_recdes.data;
    is_replaced_oid = true;
    if (ehash_allocate_recdes (&bucket_recdes, old_bucket_recdes.length, old_bucket_recdes.type) == NULL)
      { return EHASH_ERROR_OCCURRED; }
    memcpy (bucket_recdes.data, bucket_record_p, bucket_recdes.length);   /* pre-image for undo */
    (void) ehash_write_oid_to_record (bucket_record_p, value_p);          /* <- in-place OID overwrite */
  }

교체는 바이트 단위의 외과적 작업이다 — 앞쪽 sizeof(OID) 바이트만 변경되므로 redo는 sizeof(OID) 크기의 작은 패치 하나로 충분하다(§5.5). alloc 검사 이전에 is_replaced_oid = true를 세팅하는 것은 무해하다: alloc 실패 시 함수는 로깅 없이 반환하기 때문이다.

Step 2b — 키 미발견 경로(신규 삽입). ehash_compose_record(§5.4)가 레코드를 구성한 뒤 선택된 슬롯에 spage_insert_at으로 넘긴다. 이 결과가 이 챕터의 핵심 분기점이다:

// ehash_insert_to_bucket -- src/storage/extendible_hash.c
else   /* not found: ehash_compose_record (..., &bucket_recdes) into bucket_recdes, then: */
  {
    success = spage_insert_at (thread_p, bucket_page_p, slot_no, &bucket_recdes);
    if (success != SP_SUCCESS)
      {
        ehash_free_recdes (&bucket_recdes);
        if (success == SP_DOESNT_FIT)
          { return EHASH_BUCKET_FULL; }   /* <- only "normal" non-success -> split (Ch 6) */
        er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_GENERIC_ERROR, 0);
        return EHASH_ERROR_OCCURRED;       /* every other failure is fatal */
      }
  }

Invariant — EHASH_BUCKET_FULL은 유일하게 복구 가능한 실패 신호다. SP_DOESNT_FIT만이 양호한 실패다(페이지 공간 부족, 분할로 해결). 그 외 SP_SUCCESS가 아닌 모든 결과는 fatal ER_GENERIC_ERROR → EHASH_ERROR_OCCURRED다. 이 규칙이 깨지면 §5.2의 재시도가 망가진 페이지를 상대로 분할과 재삽입을 무한 반복할 것이다. upsert 경로는 레코드 길이를 변경하지 않으므로 절대 full을 보고하지 않는다.

5.4 레코드 바이트 구성: `ehash_compose_record`, `ehash_write_key_to_record`, `ehash_write_oid_to_record`

버킷 레코드는 (OID, key) 구조다. ehash_compose_record가 크기(sizeof(OID) + key_size)를 계산하고 할당한다. ehash_write_key_to_record는 레코드 type을 설정(항상 REC_HOME)하고, OID를 먼저 쓴 뒤 키 본문을 복사한다 — 문자열은 memcpy, DB_TYPE_OBJECT는 *(OID *) 대입, 그 외는 corruption fatal:

// ehash_compose_record -- src/storage/extendible_hash.c
if (key_type == DB_TYPE_STRING)
  { key_size = (short) strlen ((char *) key_p) + 1; assert (key_size <= 256); }  /* +\0; 2nd §5.1 guard */
else
  { key_size = ehash_get_key_size (key_type); if (key_size < 0) return ER_FAILED; }  /* unknown type */
if (ehash_allocate_recdes (recdes_p, sizeof (OID) + key_size, REC_HOME) == NULL) { return ER_FAILED; }
return ehash_write_key_to_record (recdes_p, key_type, key_p, key_size, value_p, is_long_str);

// ehash_write_key_to_record -- src/storage/extendible_hash.c
recdes_p->type = is_long_str ? REC_BIGONE : REC_HOME;
record_p = ehash_write_oid_to_record (recdes_p->data, value_p);   /* OID first: pageid, volid, slotid */
switch (key_type)
  {
  case DB_TYPE_STRING:  memcpy (record_p, (char *) key_p, key_size); break;  /* incl. NUL */
  case DB_TYPE_OBJECT:  *(OID *) record_p = *(OID *) key_p; break;
  // ... other fixed-width cases are #if ENABLE_UNUSED_FUNCTION ...
  default:              /* <- fatal: unknown type */
    er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
    ehash_free_recdes (recdes_p); return ER_EH_CORRUPTED;
  }

ehash_write_oid_to_record는 pageid, volid, slotid를 지나 record_p를 전진시킨 뒤 반환하므로 호출자가 이어서 데이터를 추가할 수 있다.

Invariant — OID는 모든 버킷 레코드의 첫 sizeof(OID) 바이트를 (pageid, volid, slotid) 순서로 차지한다. upsert 덮어쓰기는 동일한 writer를 동일한 앞쪽 바이트에 재사용하며, §5.5의 RVEH_REPLACE redo 레코드도 정확히 그 sizeof(OID) 위치를 기록한다. 이 규칙이 깨지면 upsert가 키를 손상시키고, 챕터 4의 비교 함수들(sizeof(OID)를 건너뛰어 키에 접근)이 쓰레기 값을 읽게 된다.

5.5 WAL 마무리: 논리적 undo, 물리적 redo, `pgbuf_set_dirty`

페이지 수정 후 ehash_insert_to_bucket은 log_recdes를 bucket_recdes.length + sizeof(EHID) 크기로 할당하고 EHID + bucket_recdes 형태로 채운다. bucket_recdes가 무엇을 담고 있는지가 핵심이다: upsert 경로에서는 §5.3 Step 2a에서 복사한 pre-image(이전 OID를 복원하기 위한 undo용)이고, 신규 삽입 경로에서는 슬롯에 막 넣은 새 레코드다. EHID 접두사가 undo를 논리적으로 만든다(고정된 페이지 주소 대신 파일 단위로 재실행); redo는 물리적으로 유지된다. 두 절반 모두 is_replaced_oid에 따라 분기한다:

// ehash_insert_to_bucket -- src/storage/extendible_hash.c
log_record_p = ehash_write_ehid_to_record (log_recdes.data, ehid_p);   /* <- EHID makes undo logical */
memcpy (log_record_p, bucket_recdes.data, bucket_recdes.length);
if (!is_temp)   /* UNDO: pgptr NULL -> page-agnostic. DELETE restores old oid; INSERT deletes key */
  log_append_undo_data2 (thread_p, is_replaced_oid ? RVEH_DELETE : RVEH_INSERT,
                         &ehid_p->vfid, NULL, /* ... */ log_recdes.data);
// ... REDO half: physical, branches on is_replaced_oid ...
if (is_replaced_oid)
  {
    if (!is_temp)   /* byte offset; only the OID-sized patch */
      log_append_redo_data2 (thread_p, RVEH_REPLACE, &ehid_p->vfid, bucket_page_p,
                             (int) (old_bucket_recdes.data - bucket_page_p), sizeof (OID),
                             old_bucket_recdes.data);
  }
else
  {
    // ... prepend rec type as a short (dodges alignment), then the record bytes ...
    if (!is_temp)   /* slot id */
      log_append_redo_data2 (thread_p, RVEH_INSERT, &ehid_p->vfid, bucket_page_p, slot_no,
                             log_recdes.length, log_recdes.data);
  }
// ... free both RECDES buffers ...
pgbuf_set_dirty (thread_p, bucket_page_p, DONT_FREE);   /* caller still holds latch */
return EHASH_SUCCESSFUL_COMPLETION;

upsert undo는 pre-image와 함께 RVEH_DELETE(롤백 시 이전 값 재설치); 신규 삽입 undo는 RVEH_INSERT(롤백 시 키 삭제). redo는 같은 플래그를 기준으로 대칭을 이룬다: upsert의 RVEH_REPLACE 페이로드는 old_bucket_recdes.data — §5.3에서 새 OID로 이미 덮어써진 라이브 레코드 바이트 — 를 old_bucket_recdes.data - bucket_page_p 오프셋에서 정확히 sizeof(OID) 길이로 기록한다. 신규 삽입의 RVEH_INSERT는 slot_no를 키로 사용한다. DONT_FREE는 §5.2의 호출자가 여전히 X latch를 보유하고 있으므로 필수다. is_temp 해시에서는 네 개의 log_append_* 호출이 모두 건너뛰어지지만(충돌 복구 불필요), pgbuf_set_dirty는 그래도 실행된다.

Invariant — 논리적 undo, 물리적 redo, 레코드 단위. undo는 페이지 포인터 없이(NULL) EHID + 전체 레코드를 전달하므로 버킷이 이동하거나 분할된 이후에도 파일 단위로 재실행할 수 있다. redo는 구체적인 페이지 + 오프셋/슬롯과 변경된 바이트만 전달한다. 이 규칙이 깨지면: 물리적 undo는 동시 분할이 레코드를 재배치한 후 실패하고, 논리적 redo는 복구 패스마다 버킷을 다시 탐색해야 해서 성능을 심각하게 떨어뜨린다.

5.6 챕터 요약 — 핵심 정리

ehash_insert는 낙관적으로 시작한다 — 루트에 S_LOCK을 걸고, 삽입이 여유 있는 기존 버킷 하나에 안착하며 디렉터리를 건드리지 않을 것이라 낙관한다.
S→X 승격은 재시작 방식이지 업그레이드 방식이 아니다. 구조적 필요(빈 슬롯 또는 가득 찬 버킷)가 생기면 헬퍼는 루트를 unfix하고 X_LOCK으로 재귀 호출한다. 버킷 페이지는 항상 X-latch로 고정된다.
EHASH_BUCKET_FULL은 “분할하러 가라”는 깨끗한 신호다 — SP_DOESNT_FIT만이 이를 생성한다. 그 외 slotted-page 실패는 모두 fatal이며, upsert 경로는 절대 full을 보고하지 않는다.
삽입은 제자리 OID 덮어쓰기를 통한 upsert다 — ehash_locate_slot이 키를 찾으면 코드는 pre-image를 저장한 뒤 앞쪽 sizeof(OID) 바이트만 덮어쓴다. 키 바이트와 길이는 고정된다.
모든 버킷 레코드는 (OID, key), OID 우선 (sizeof(OID) + key_size). 이 고정된 앞쪽 오프셋이 upsert 덮어쓰기와 RVEH_REPLACE redo 모두의 타겟이다.
undo는 논리적(NULL 페이지 + EHID + 전체 레코드), redo는 물리적(페이지 + 오프셋/슬롯, 변경된 바이트만) — RVEH_DELETE/RVEH_INSERT undo, RVEH_REPLACE/RVEH_INSERT redo.
문자열 키는 255바이트로 제한되며, 두 곳에서 assert된다. 긴 문자열 처리 코드는 컴파일 아웃되어 있다. 분할(ehash_extend_bucket, new_bit 절반 선택)은 챕터 6에서 다룬다.

Chapter 6: 꽉 찬 버킷 분할과 로컬 깊이 증가

ehash_insert_to_bucket이 EHASH_BUCKET_FULL을 반환하면, 해당 키는 해시 접두사상 그 버킷에 속하지만 공간이 없는 상태다. CUBRID는 *분할(split)*을 수행한다: 버킷의 로컬 깊이(local depth)를 올리고, 형제 버킷(sibling)을 할당한 뒤, 두 버킷을 구분하는 비트를 기준으로 레코드를 재분배한다. 이 챕터는 ehash_extend_bucket의 분할 절반 — new_local_depth > dir_header_p->depth라는 디렉토리 크기 판단(Chapter 7 소관) 직전까지 — 을 추적한다. 로컬/글로벌 깊이 모델은 companion 문서를 참조한다.

6.1 시스템 op 브래킷: `ehash_extend_bucket`

ehash_extend_bucket은 트랜잭션 봉투(transactional envelope) 역할을 한다. 중첩 시스템 op를 열고, 어떤 실패라도 발생하면 그것을 abort해 미완성 분할을 물리적으로 원상 복구한다:

// ehash_extend_bucket -- src/storage/extendible_hash.c
if (!is_temp) { log_sysop_start (thread_p); }      /* <- atomic bracket for the whole split+connect */

sibling_page_p = ehash_split_bucket (thread_p, dir_header_p, bucket_page_p, key_p, &old_local_depth,
                                     &new_local_depth, &sibling_vpid, is_temp);
if (sibling_page_p == NULL)
  {
    if (!is_temp) { log_sysop_abort (thread_p); }  /* <- split failed: roll back, return NULL */
    return NULL;
  }

*out_new_bit_p = GETBIT (hash_key, new_local_depth);   /* <- which side does the triggering key land on? */
ehash_adjust_local_depth (thread_p, ehid_p, dir_root_page_p, dir_header_p, old_local_depth, -1, is_temp);
ehash_adjust_local_depth (thread_p, ehid_p, dir_root_page_p, dir_header_p, new_local_depth,  2, is_temp);

불변식 (분할 원자성): log_sysop_start와 log_sysop_commit 사이에서 변경된 모든 페이지는 전부 커밋되거나 전부 되돌려진다. 모든 오류 경로가 log_sysop_abort를 거치도록 설계되어 이를 보장한다. 분할 이후 경로에는 총 다섯 개의 abort 출구가 있다(디렉토리 확장 분기에 하나, Chapter 7의 버킷 연결 코드에 셋, 위의 ehash_split_bucket 실패에 하나). abort 하나라도 빠뜨리면 시스템 op가 형제 버킷을 할당한 채로 커밋되어 참조 불가능한 영구 누수가 발생한다.

ehash_split_bucket이 먼저 실행되며, 분할 절반에서 실패할 수 있는 유일한 단계다(실패 시 자신이 할당한 형제 버킷을 직접 해제한다, 6.6). 그 이후 단계는 모두 무조건 실행되고 실패하지 않으므로, sibling_page_p == NULL이 이 함수에서 유일한 조기 반환 조건이다. is_temp는 모든 로깅 결정에 전파된다: 임시 해시의 경우 시스템 op 브래킷과 모든 로깅은 no-op으로 축소되지만 페이지 변경은 그대로 수행된다.

flowchart TD
  D["ehash_split_bucket"] --> E{"sibling == NULL?"}
  E -- 예 --> F["is_temp 아니면 log_sysop_abort; NULL 반환"]
  E -- 아니오 --> H["out_new_bit; adjust(old,-1); adjust(new,+2)"]
  H --> J["디렉토리 크기 분기 -> Chapter 7"]

Figure 6-1. 분할 절반의 제어 흐름. 유일한 조기 반환은 분할 실패이며, 챕터는 노드 J에서 멈춘다.

6.2 `ehash_split_bucket` — 분할 전 이미지 로깅과 새 깊이 선택

ehash_split_bucket은 old_local_depth, new_local_depth, 형제 VPID를 호출자에게 반환하며, 원본 버킷 페이지는 고정(fixed) 상태를 유지한다(호출자가 나중에 유발 키를 삽입). 더티 마크만 설정한다. 가장 먼저 분할 전 버킷 전체를 undo 이미지로 캡처하고, 헤더를 읽어 새 깊이를 결정한다:

// ehash_split_bucket -- src/storage/extendible_hash.c
if (!is_temp)
  log_append_undo_data2 (thread_p, RVEH_REPLACE, &dir_header_p->bucket_file, bucket_page_p, 0, DB_PAGESIZE,
                         bucket_page_p);                   /* <- full-page undo image, before split */
num_records = spage_number_of_records (bucket_page_p);
if (spage_next_record (bucket_page_p, &first_slot_id, &recdes, PEEK) != S_SUCCESS)   /* <- slot 0 = header */
  { er_set (...ER_EH_CORRUPTED...); return NULL; }          /* <- corruption: caller aborts sysop */

bucket_header_p = (EHASH_BUCKET_HEADER *) recdes.data;
*out_old_local_depth_p = bucket_header_p->local_depth;
if (ehash_find_first_bit_position (thread_p, dir_header_p, bucket_page_p, bucket_header_p, key_p, num_records,
                                   first_slot_id, out_old_local_depth_p, out_new_local_depth_p) != NO_ERROR)
  { return NULL; }                                          /* <- depth-choice failure: caller aborts sysop */

RVEH_REPLACE는 페이지 전체를 논리적으로 교체하는 undo 타입이다: undo 이미지는 분할 전 DB_PAGESIZE 크기의 전체 페이지이므로, abort 시 버킷이 정확히 복원된다. 첫 번째 spage_next_record(first_slot_id == -1에서 시작)는 슬롯 0, 즉 EHASH_BUCKET_HEADER(Chapter 1)를 가져온다. 이 발췌문에서 세 개의 NULL 반환 분기가 드러난다 — 묵시적인 undo-log 단계, 손상 체크(ER_EH_CORRUPTED), ehash_find_first_bit_position 실패(6.3) — 각각 호출자의 시스템 op를 abort시킨다.

6.3 `ehash_find_first_bit_position` — 가장 작은 분리 깊이 탐색

CUBRID는 new_local_depth = old_local_depth + 1을 무조건 쓰지 않는다. old+1 비트에서 모든 레코드가 동일한 비트값을 가지면, 깊이를 1 올려도 이동하는 레코드가 없어 오버플로우가 지속되고 다음 삽입도 무한히 분할을 반복하게 된다. 따라서 ehash_find_first_bit_position은 현재 깊이를 넘어서 레코드들이 처음으로 달라지는 비트를 찾는다:

// ehash_find_first_bit_position -- src/storage/extendible_hash.c
check_bit = 1 << (EHASH_HASH_KEY_BITS - bucket_header_p->local_depth - 1);   /* <- bit just past local_depth */
first_hash_key = ehash_hash (key_p, dir_header_p->key_type);   /* <- pseudo key of the NEW (triggering) key */
for (slot_id = first_slot_id + 1; slot_id < num_recs; slot_id++)
  {
    if (spage_get_record (...) != S_SUCCESS)
      { er_set (...ER_EH_CORRUPTED...); return ER_EH_CORRUPTED; }   /* <- distinct code: corruption */
    if (ehash_get_pseudo_key (..., &next_hash_key) != NO_ERROR)
      { return ER_FAILED; }                                /* <- distinct code: pseudo-key failure */
    difference = (first_hash_key ^ next_hash_key) | difference;   /* <- accumulate all differing bits */
    if (difference & check_bit) { break; }                        /* <- earliest possible split bit found */
  }

XOR는 새 키와 해당 레코드가 다른 비트 위치에서 1이 된다. OR로 누적하면 모든 레코드에 걸쳐 다른 비트의 합집합을 얻는다. break는 최적화다: difference의 check_bit 위치(old depth 바로 다음 비트)가 1이 되는 순간, 이후 레코드가 답을 더 좁힐 수 없으므로 루프를 종료한다. 첫 번째 루프에는 두 개의 서로 다른 오류 코드 반환이 있다: ER_EH_CORRUPTED와 ER_FAILED. 두 번째 루프는 local_depth + 1부터 바깥 방향으로 가장 왼쪽의 set 비트를 찾는다:

// ehash_find_first_bit_position -- src/storage/extendible_hash.c (continued)
bit_position = *out_old_local_depth_p + 1;       /* <- default if loop finds nothing within range */
for (i = bucket_header_p->local_depth + 1; i <= EHASH_HASH_KEY_BITS; i++)
  {
    if (difference & check_bit) { bit_position = i; break; }   /* <- first disagreeing depth = new depth */
    check_bit >>= 1;                               /* <- walk one bit toward the LSB */
  }
bucket_header_p->local_depth = bit_position;       /* <- mutate the in-page header */
*out_new_local_depth_p = bit_position;

불변식 (분리 깊이): new_local_depth는 old_local_depth보다 크면서, 새 키의 pseudo key가 최소 하나의 레코드와 달라지는 가장 작은 깊이다. 적합한 깊이가 없으면 old_local_depth + 1이 폴백으로 사용되어, 새 키가 들어갈 수 있는 공간을 보장한다. 위반 시 결과: 너무 작으면 ehash_insert_bucket_after_extend_if_need의 재귀 호출이 종료되지 않고, 너무 크면 디렉토리가 과도하게 확장되어 엔트리가 낭비된다.

페이지 내 bucket_header_p->local_depth는 즉시 증가된다(undo 이미지는 6.2에서 이미 로깅됨). check_bit는 두 루프가 공유한다 — 첫 번째 루프가 old+1 비트에 남겨두면, 두 번째 루프가 거기서부터 이어서 시프트한다.

6.4 `ehash_get_pseudo_key` — 레코드의 해시 키 추출

스캔과 재분배 모두 ehash_get_pseudo_key를 호출한다. 레코드는 OID + 키 바이트로 구성되므로, OID를 건너뛰고 다시 해싱한다: hash_key = ehash_hash ((char *) recdes_p->data + sizeof (OID), key_type) (REC_BIGONE 분기는 ENABLE_UNUSED_FUNCTION 미정의 시 컴파일에서 제외된다). CUBRID는 pseudo key를 필요할 때마다 재도출한다 — 디렉토리가 주소 지정에 쓰는 32비트 값(Chapter 3)과 동일하며, 분할은 더 깊은 비트를 참조한다.

6.5 `ehash_distribute_records_into_two_bucket` — 새 비트 기준 분배

new_local_depth 위치의 비트가 1인 레코드는 형제 버킷으로, 0인 레코드는 원본 버킷에 남는다. 루프는 슬롯을 한 번만 순회한다:

// ehash_distribute_records_into_two_bucket -- src/storage/extendible_hash.c
for (slot_id = i = first_slot_id + 1; i < num_recs; i++)
  {
    if (spage_get_record (..., slot_id, &recdes, PEEK) != S_SUCCESS) { return ER_FAILED; }
    if (ehash_get_pseudo_key (..., &recdes, ..., &hash_key) != NO_ERROR) { return ER_FAILED; }
    if (GETBIT (hash_key, bucket_header_p->local_depth))     /* <- local_depth already set to new depth */
      {                                                      /* <- 1-bit: move to sibling */
        success = spage_insert (thread_p, sibling_page_p, &recdes, &sibling_slot_id);
        if (success != SP_SUCCESS) { er_set (...ER_GENERIC_ERROR...); return ER_FAILED; }  /* <- caller deallocs */
        (void) spage_delete (thread_p, bucket_page_p, slot_id);   /* <- slot_id NOT advanced: next slides in */
      }
    else { slot_id++; }                                      /* <- 0-bit: keep, advance slot */
  }

이중 커서(dual cursor): i는 검사한 레코드 수를 세고, slot_id는 실제 물리 슬롯 위치다. 이동 시, spage_delete가 컴팩션(compaction)을 수행하므로 다음 레코드가 동일한 slot_id 자리를 차지한다(증가 없음). 유지 시에는 slot_id가 앞으로 나아간다. spage_insert 실패(디버그 주석: “절대 발생하면 안 됨”)가 유일한 오류 분기이며, ER_FAILED를 반환하고 6.6이 정리를 담당한다.

불변식 (순서 보존): 두 반쪽 모두 사용자 키 기준 정렬 순서가 유지된다 — 단방향 순회와 UNANCHORED_KEEP_SEQUENCE 슬롯이 이동된 레코드를 오름차순으로 삽입하며, 컴팩션은 잔류 레코드의 순서를 바꾸지 않는다. 위반 시 결과: ehash_binary_search_bucket(Chapter 4)이 키를 찾지 못해 조회가 손상된다.

6.6 형제 페이지: `file_alloc` + `ehash_initialize_bucket_new_page`

ehash_split_bucket은 3바이트 인자 블롭(arg blob)을 ehash_initialize_bucket_new_page에 넘겨 형제 버킷을 할당한다:

// ehash_split_bucket -- src/storage/extendible_hash.c
init_bucket_data[0] = dir_header_p->alignment;
init_bucket_data[1] = *out_new_local_depth_p;          /* <- sibling is born at the new depth */
init_bucket_data[2] = is_temp;
error_code = file_alloc (..., ehash_initialize_bucket_new_page, init_bucket_data, sibling_vpid_p, &sibling_page_p);
if (error_code != NO_ERROR) { ASSERT_ERROR (); return NULL; }          /* <- alloc failed: caller aborts */
if (sibling_page_p == NULL) { assert_release (false); return NULL; }   /* <- defensive NULL check */

if (ehash_distribute_records_into_two_bucket (...) != NO_ERROR)
  {
    pgbuf_unfix_and_init (thread_p, sibling_page_p);
    if (file_dealloc (..., sibling_vpid_p, FILE_EXTENDIBLE_HASH) != NO_ERROR) { ASSERT_ERROR (); }
    VPID_SET_NULL (sibling_vpid_p);
    return NULL;                                          /* <- sibling cleaned up; caller aborts sysop */
  }
if (!is_temp)
  {
    log_append_redo_data2 (..., RVEH_REPLACE, ..., bucket_page_p, 0, DB_PAGESIZE, bucket_page_p);    /* both */
    log_append_redo_data2 (..., RVEH_REPLACE, ..., sibling_page_p, 0, DB_PAGESIZE, sibling_page_p);  /* pages */
  }
pgbuf_set_dirty (thread_p, sibling_page_p, DONT_FREE);   /* <- bucket_page_p set dirty likewise */
return sibling_page_p;

콜백은 UNANCHORED_KEEP_SEQUENCE 슬롯 페이지를 초기화하고(6.5 순서 불변식의 근원), 슬롯 0에 local_depth = depth인 버킷 헤더를 기록하며, 초기화 인자를 RVEH_INIT_BUCKET undoredo로 로깅한다 — 파일 계층의 undo가 할당 자체를 커버하므로 전체 페이지를 기록하지 않는다. 따라서 원본 버킷에는 RVEH_REPLACE undo(6.2) + redo(여기)가, 형제 버킷에는 RVEH_INIT_BUCKET undoredo + RVEH_REPLACE redo가 붙는다. 크래시 복구 시 두 페이지 모두 redo가 재생되고, abort 시 원본이 복원되고 형제가 회수된다. 분배 실패 분기는 형제를 직접 해제하고 out-VPID를 null로 만든다.

6.7 `ehash_adjust_local_depth`와 `out_new_bit`

히스토그램 local_depth_count[](Chapter 1)는 분할을 반영해야 한다: 버킷 하나가 old_local_depth를 떠나 두 개가 new_local_depth에 자리 잡으므로, -1 후 +2 순서로 조정한다:

// ehash_adjust_local_depth -- src/storage/extendible_hash.c
dir_header_p->local_depth_count[depth] += delta;          /* <- mutate the histogram bucket */
pgbuf_set_dirty (thread_p, dir_root_page_p, DONT_FREE);
offset = CAST_BUFLEN ((char *) (dir_header_p->local_depth_count + depth) - (char *) dir_root_page_p);
redo_inc = delta;  undo_inc = -delta;                     /* <- exact inverse for undo */
if (!is_temp)
  {
    log_append_undoredo_data2 (thread_p, RVEH_INC_COUNTER, &ehid_p->vfid, dir_root_page_p, offset, sizeof (int),
                               sizeof (int), &undo_inc, &redo_inc);     /* <- delta-style log */
  }

RVEH_INC_COUNTER는 값 교체가 아닌 델타(delta) 레코드다: redo는 +delta, undo는 -delta이며, 루트 페이지 내 local_depth_count[depth]의 int 값에 offset 위치에서 적용된다. 역 델타(inverse delta)는 중간에 어떤 값 변경이 있었든 증분을 정확히 되돌리므로 복구가 순서 독립적(order-independent)이다. Chapter 9의 축소(shrink) 로직이 이 히스토그램을 읽는다.

또 다른 출력인 *out_new_bit_p = GETBIT (hash_key, new_local_depth)(6.1 발췌)는 조정 이전에 계산된다. hash_key는 유발 키의 pseudo key이므로, 그 비트가 선택하는 절반으로 이 키가 배치된다(6.5 규칙). 호출자 ehash_insert_bucket_after_extend_if_need는 재시도 대상을 결정하는 데 이 값을 읽는다 — 1이면 형제, 0이면 잔류 버킷 — 분리 깊이 불변식(6.3)에 의해 그 절반에는 반드시 공간이 있다. 제어 흐름은 이어서 Chapter 7의 new_local_depth > dir_header_p->depth 검사로 넘어간다.

6.8 챕터 요약 — 핵심 정리

ehash_extend_bucket은 분할 전체를 log_sysop_start / log_sysop_commit 브래킷으로 감싸고, 모든 실패를 log_sysop_abort로 라우팅한다(총 다섯 개의 abort, 분할 절반에 하나). is_temp는 브래킷과 로깅을 no-op으로 축소한다.
ehash_split_bucket은 분할 전 전체 페이지를 RVEH_REPLACE undo로 로깅한 뒤, 두 페이지 모두 redo로 기록한다. 할당 이전에 세 개의 NULL 반환 분기가 있다(undo 단계, spage_next_record 손상, ehash_find_first_bit_position 실패). 원본 버킷은 fixed 상태를 유지한다.
CUBRID는 old_local_depth + 1을 무조건 쓰지 않는다. ehash_find_first_bit_position이 각 레코드의 pseudo key를 새 키와 XOR한 뒤, 가장 작은 불일치 깊이를 선택한다. 스캔은 두 가지 오류 코드(ER_EH_CORRUPTED, ER_FAILED)를 반환할 수 있다.
ehash_distribute_records_into_two_bucket은 new_local_depth 비트를 기준으로 이중 커서를 사용해 분배한다. 이동 시 slot_id는 제자리(컴팩션으로 다음 레코드가 내려옴), 유지 시 slot_id를 증가시켜 두 절반 모두 정렬 순서를 보존한다.
형제는 새 깊이에서 탄생한다. file_alloc + ehash_initialize_bucket_new_page(RVEH_INIT_BUCKET). 분배 실패 시 file_dealloc으로 형제를 해제하고 out-VPID를 null로 만든다.
두 번의 델타 로깅 ehash_adjust_local_depth 호출 (old에서 -1, new에서 +2)이 RVEH_INC_COUNTER를 역 undo/redo 델타와 함께 기록하므로 복구가 순서 독립적이다.
out_new_bit = GETBIT(hash_key, new_local_depth)가 재시도 절반을 선택한다 (1 → 형제, 0 → 잔류). 분리 깊이 불변식이 해당 절반에 공간이 있음을 보장한다.

Chapter 7: 디렉터리 두 배 확장과 버킷 포인터 연결

6장은 ehash_extend_bucket의 분할(split) 절반 — 디렉터리 크기 결정 조건 new_local_depth > dir_header_p->depth 바로 직전까지 — 을 추적하고, 그 이후 처리를 이 장에 명시적으로 넘겼다. ehash_split_bucket이 레코드를 새로 할당된 형제(sibling) 페이지로 재배분하고 old_local_depth / new_local_depth를 보고한 시점부터 재개한다. 이 장은 디렉터리 변경 후반부(directory-mutation tail) 를 추적한다. 즉, 분할이 버킷의 로컬 깊이를 전역 깊이(global depth)보다 높여 디렉터리 두 배 확장을 강제할 때 어떤 일이 일어나는지, 그리고 하나의 구 버킷을 가리키던 포인터 범위가 원본과 형제 사이에서 어떻게 나뉘는지를 다룬다. 상위 수준 문서(cubrid-extendible-hash.md, Insert — ehash_insert 및 WAL integration — RVEH_* records 섹션)는 로컬 깊이가 전역 깊이를 초과할 때 디렉터리를 두 배로 늘리는 이유를 설명한다. 이 장은 이를 구현하는 세 함수의 모든 분기, 해당 함수가 내보내는 복구 레코드의 모든 필드, 그리고 포인터를 이동시키는 비트 연산을 추적한다.

이 장이 복원하는 고정 불변식(standing invariant). 익스텐더블 해싱은 연산과 연산 사이의 모든 순간에, 모든 버킷의 로컬 깊이가 디렉터리의 전역 깊이를 초과하지 않는다는 불변식을 유지한다.

불변식 (깊이 상한): 모든 버킷은 local_depth <= dir_header_p->depth (전역 깊이)를 만족한다. 버킷을 new_local_depth > depth로 올리는 분할은 일시적으로 이를 위반한다. ehash_expand_directory는 depth를 new_local_depth로 끌어올려 디렉터리가 원본과 형제를 별도로 주소 지정할 수 있는 해상도를 회복시킴으로써 불변식을 복원한다. 위반 시 결과: local_depth > depth인 상태에서는 디렉터리의 슬롯 수가 2^local_depth보다 적어지므로, 서로 다른 두 로컬 프리픽스가 한 슬롯에 충돌한다. 그 결과 {원본, 형제} 중 하나는 주소 지정이 불가능해지고, 해당 버킷의 키에 접근할 수 없게 된다.

7.1 `ehash_extend_bucket`의 후반부 — 오케스트레이션

제어가 후반부에 도달했을 때 형제 페이지가 이미 존재한다. 함수는 먼저 결정 비트(deciding bit) *out_new_bit_p = GETBIT (hash_key, new_local_depth)를 캡처한 뒤, ehash_adjust_local_depth로 깊이별 카운터를 재조정한다(old_local_depth 카운트 -1, new_local_depth 카운트 +2). 이후 선택적으로 디렉터리를 두 배 확장하고 최대 세 번의 ehash_connect_bucket 호출을 수행한다.

// ehash_extend_bucket -- src/storage/extendible_hash.c
// every error block below is identical: pgbuf_unfix_and_init(sibling); if(!is_temp) log_sysop_abort; return NULL;
if (new_local_depth > dir_header_p->depth)              /* <- local outgrew global: must double */
  if (ehash_expand_directory (..., new_local_depth, is_temp) != NO_ERROR) { /* abort, return NULL */ }

if ((new_local_depth - old_local_depth) > 1)            /* <- depth jumped by more than 1 */
  {
    /* First, set all of them to NULL_PAGEID */
    if (ehash_connect_bucket (..., old_local_depth, hash_key, &null_vpid, is_temp) != NO_ERROR) { /* abort */ }
    hash_key = CLEARBIT (hash_key, new_local_depth);    /* <- new MSB 0: lower half */
    if (ehash_connect_bucket (..., new_local_depth, hash_key, bucket_vpid, is_temp) != NO_ERROR) { /* abort */ }
  }

hash_key = SETBIT (hash_key, new_local_depth);          /* <- new MSB 1: upper half */
if (ehash_connect_bucket (..., new_local_depth, hash_key, &sibling_vpid, is_temp) != NO_ERROR) { /* abort */ }

flowchart TD
  A["후반부 진입<br/>형제 페이지 고정, 깊이 보고됨"] --> B["out_new_bit = GETBIT(hash_key, new_local_depth)<br/>카운터 조정: old -1, new +2"]
  B --> C{"new_local_depth ><br/>전역 깊이?"}
  C -->|예| D["ehash_expand_directory<br/>두 배 확장, depth := new_local_depth"]
  C -->|아니오| E
  D --> E{"new_local_depth -<br/>old_local_depth > 1?"}
  E -->|예| F["old_local_depth로 connect -> null_vpid<br/>오래된 넓은 범위를 NULL 처리"]
  F --> G["hash_key = CLEARBIT(new_local_depth)<br/>하위 절반 -> 원본으로 connect"]
  G --> H
  E -->|아니오, 정상 +1| H["hash_key = SETBIT(new_local_depth)<br/>상위 절반 -> 형제로 connect"]
  H --> I["log_sysop_commit<br/>형제 페이지 반환"]

Figure 7-1. ehash_extend_bucket의 디렉터리 변경 후반부. 두 개의 독립적인 게이트(두 배 확장, 다단계 NULL-후-재연결)가 항상 실행되는 최종 형제 connect 앞에 위치한다. 축약 표시된 모든 오류 블록은 형제 페이지를 unfix하고 log_sysop_abort로 처리된다.

두 배 확장 게이트는 디렉터리가 원본과 형제에게 별도의 주소를 줄 해상도가 부족할 때만 실행되며, 그렇지 않으면 건너뛰고 connect 호출이 기존 슬롯을 재지정한다. 다단계 게이트는 분할이 로컬 깊이를 1 초과로 높였을 때만 실행된다. 이 경우 하위 절반과 상위 절반 사이의 슬롯들은 어느 버킷에도 속하지 않는 프리픽스를 가리키므로 먼저 NULL 처리해야 한다. 정상적인 +1 분할에서는 이 분기를 건너뛴다. 최종 형제 connect가 상위 절반을 처리하며, 하위 절반은 여전히 원본을 가리킨다. *out_new_bit_p는 어떠한 변경(mutation)보다 먼저 캡처된다(§7.6). 각 오류 블록(축약 표시)은 외부 log_sysop_start sysop을 중단시켜, §7.3과 §7.5가 내보낸 undo 레코드로 부분적인 변경을 롤백한다.

불변식 (디렉터리 포인터 커버리지): 후반부 완료 후, 영향받은 범위의 모든 슬롯은 {원본, 형제} 중 정확히 하나를 가리킨다. 오래된 통합 범위를 가리키는 슬롯은 없다. >1 분기에서 NULL 패스는 좁은 절반으로 재스탬핑되기 전에 어떤 슬롯도 오래된 넓은 매핑을 유지하지 않도록 보장하며, 형제 connect가 상위 절반을 닫는다. 위반 시 결과: >1 점프에서 NULL 패스를 건너뛰면 중간 프리픽스의 조회가 잘못된 버킷으로 해석되어 키가 조용히 손실되거나 잘못 라우팅된다.

7.2 `EHASH_REPETITION` — 런 길이(run-length) connect 레코드

ehash_connect_bucket은 한 페이지에 동일한 포인터를 수천 개 스탬핑할 수 있다. 포인터마다 WAL 레코드를 하나씩 남기는 대신, CUBRID는 페이지당 단일 런 길이 디스크립터 하나를 기록한다. “같은 vpid를 count번 반복한다”는 형식이다.

// ehash_repetition -- src/storage/extendible_hash.c
struct ehash_repetition          /* typedef'd EHASH_REPETITION */
{
  /* The "vpid" is repeated "count" times */
  VPID vpid;
  int count;
};

필드	역할	존재 이유
`vpid`	이 런의 모든 슬롯에 설정되는 버킷 페이지 ID (volid + pageid). 실제 버킷이거나, NULL 패스 시 `null_vpid` (`{NULL_VOLID, NULL_PAGEID}`).	각 `EHASH_DIR_RECORD.bucket_vpid`에 기록되는 값. 한 번만 전달하면 상수 크기 레코드로 전체 런을 복구 재생할 수 있다.
`count`	`recv->offset`부터 시작하는 연속된 `EHASH_DIR_RECORD` 슬롯 수. `bef_length / sizeof(EHASH_DIR_RECORD)`로 계산.	바이트 범위를 슬롯 수로 변환하여, redo 핸들러가 페이지 레이아웃을 다시 유도하지 않고 루프를 수행할 수 있게 한다. 레코드를 포인터 수에 비례한 O(n)이 아닌 페이지당 O(1)로 만든다.

EHASH_REPETITION은 페이로드와 핸들러 양쪽에서 동일한 의미를 갖는다. 유일한 미묘한 점은 vpid가 센티넬로도 기능한다는 것이다(null_vpid는 NULL 패스에서 합법적인 런 대상이다). RVEH_CONNECT_BUCKET 레코드는 리터럴 사전 이미지 undo(start_offset 위치의 bef_length 바이트)와 이 상수 크기 redo를 함께 묶는다. redo 핸들러 ehash_rv_connect_bucket_redo는 페이로드를 복사하고 recv_p->offset부터 count번 반복하면서, 슬롯과 대상이 !VPID_EQ인 경우에만 repetition.vpid를 기록한다. 이미 올바른 슬롯은 건너뛰어 재생이 멱등성(idempotent)을 갖게 한다.

7.3 `ehash_expand_directory` — 단일 역방향 패스로 두 배 확장

디렉터리는 EHID 파일의 페이지들에 걸쳐 논리적으로 연속된 EHASH_DIR_RECORD 배열이다(0번 페이지는 헤더와 공간을 공유한다). 깊이 d에서 *d′*로 두 배 확장하면 각 구 포인터가 exp_times = 2^(d′-d)번 나타나게 되는데, 이는 마지막 포인터부터 역방향으로 이동하면서 제자리(in place)에서 수행된다. 이렇게 하면 어떤 레코드도 복사되기 전에 덮어쓰이지 않는다. 헤더의 depth 필드는 마지막에 new_depth로 올려진다 — §7.0 깊이 상한 불변식을 해소하는 대입이다.

크기 계산 및 할당. 헤더를 write latch로 고정하고 페이지 수를 읽는다(file_get_num_user_pages 실패가 가장 빠른 오류 경로: ASSERT_ERROR, 헤더 unfix, return error_code, 어떠한 변경도 없이). old_ptrs = 1 << depth, exp_times = 1 << (new_depth - depth), new_ptrs = old_ptrs * exp_times를 계산하고, ehash_dir_locate로 마지막 구 포인터와 마지막 신 포인터를 찾는다.

// ehash_expand_directory -- src/storage/extendible_hash.c
// #ifdef EHASH_DEBUG: check_pages != old_pages -> unfix header, ER_EH_ROOT_CORRUPTED, return ER_FAILED
needed_pages = new_pages - old_pages;
if (needed_pages > 0)                                  /* <- N pages allocated in one call */
  if (file_alloc_multiple (..., ehash_initialize_dir_new_page, &is_temp, needed_pages, NULL) != NO_ERROR)
    { /* ASSERT_ERROR; unfix header; return error_code */ }

EHASH_DEBUG 분기는 check_pages != old_pages일 때 ER_EH_ROOT_CORRUPTED / ER_FAILED를 발생시킨다(릴리스 빌드에서는 no-op). needed_pages > 0 분기만이 디스크에 접근한다. file_alloc_multiple이 모든 페이지를 할당하고 각 페이지마다 ehash_initialize_dir_new_page(§7.4)를 실행하며, 실패 시 헤더를 unfix하고 반환한다. 그렇지 않으면 아무것도 할당되지 않는다.

루프 전 초기 페이지 로깅. 마지막 구 페이지를 소스 커서로, 마지막 신 슬롯의 페이지를 목적지 커서로 고정한다. 소스가 NULL이면 헤더를 unfix한다. 목적지가 NULL이면 헤더와 소스 모두 unfix한다. 재사용되는 목적지 구 페이지(new_dir_nth_page <= old_pages)는 여기서 RVEH_REPLACE undo 사전 이미지가 한 번 기록된다. 두 커서는 이후 동시에 하강한다. 소스는 (old_dir_nth_page, old_dir_offset), 목적지는 (new_dir_nth_page, new_dir_offset).

// ehash_expand_directory (copy loop) -- src/storage/extendible_hash.c
for (j = old_ptrs; j > 0; j--)
  {
    if (old_dir_offset < 0)                  /* <- off top of source page: step back */
      {
        pgbuf_unfix_and_init (thread_p, old_dir_page_p);
        old_dir_page_p = ehash_fix_nth_page (..., --old_dir_nth_page, ...);
        if (old_dir_page_p == NULL) { /* unfix header+new, return ER_FAILED */ }
        old_dir_offset = old_dir_nth_page ? EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE : ..._IN_FIRST_PAGE;
      }
    for (i = 1; i <= exp_times; i++)         /* emit exp_times copies of this source record */
      {
        if (new_dir_offset < 0)              /* <- off top of dest page */
          {
            if (!is_temp)                    /* redo-log the finished dst page */
              log_append_redo_data2 (..., RVEH_REPLACE, ..., new_dir_page_p, 0, DB_PAGESIZE, ...);
            pgbuf_set_dirty (thread_p, new_dir_page_p, FREE);
            new_dir_page_p = ehash_fix_nth_page (..., --new_dir_nth_page, ...);
            if (new_dir_page_p == NULL) { /* unfix header+old, return ER_FAILED */ }
            if (new_dir_nth_page <= old_pages && !is_temp)   /* pre-image of a reused page */
              log_append_undo_data2 (..., RVEH_REPLACE, ..., new_dir_page_p, ...);
            new_dir_offset = new_dir_nth_page ? EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE : ..._IN_FIRST_PAGE;
          }
        if ((char *) new_dir_page_p + new_dir_offset != (char *) old_dir_page_p + old_dir_offset)
          memcpy (... new ..., ... old ..., sizeof (EHASH_DIR_RECORD));   /* <- skip self-copy */
        new_dir_offset -= sizeof (EHASH_DIR_RECORD);
      }
    old_dir_offset -= sizeof (EHASH_DIR_RECORD);
  }

소스 이동 시 fix 실패는 헤더+목적지를 unfix한다. 목적지 이동 시 fix 실패는 헤더+소스를 unfix한다. 마무리: depth를 new_depth로 설정하고, 헤더를 포함하는 목적지 페이지에 RVEH_REPLACE redo 사후 이미지를 기록한 뒤(!is_temp인 경우), 모든 페이지를 unfix한다.

불변식 (역방향, 비덮어쓰기 복사 순서): 목적지 바이트 주소는 항상 소스 바이트 주소와 같거나 그보다 높다. 따라서 소스 레코드는 어떤 패스가 그 위에 쓰기 전에 반드시 먼저 읽힌다. new_ptrs >= old_ptrs이고 두 커서가 함께 하강하므로, 앞에서 뒤로의 순방향 이동은 아직 복사되지 않은 소스 포인터를 덮어쓸 것이다. new != old 가드는 우연히 겹치는 단 하나의 자기 복사(self-copy)를 건너뛴다. 위반 시 결과: 순방향 복사는 이후 목적지 슬롯에 아직 제공되어야 할 소스 포인터를 덮어써서 두 배 확장된 디렉터리를 손상시킨다.

불변식 (RVEH_REPLACE undo는 재사용 페이지에만): nth_page <= old_pages인 목적지 페이지만 undo 사전 이미지를 받는다. 새로 할당된 페이지는 복원할 이전 내용이 없다(ehash_initialize_dir_new_page가 이미 생성 로그를 남겼다). 위반 시 결과: 재사용 페이지의 undo를 생략하면 롤백 능력이 사라진다. 신규 페이지에 undo를 기록하면 존재하지 않았던 내용을 복원하려 시도한다.

7.4 `ehash_initialize_dir_new_page` — 새 디렉터리 페이지 초기화

file_alloc_multiple은 새로 할당된 페이지마다 이 콜백을 한 번 호출하여, 페이지 타입을 표시하고 영구적(persistent) 파일인 경우 할당을 로그에 기록한다.

// ehash_initialize_dir_new_page -- src/storage/extendible_hash.c
ehash_initialize_dir_new_page (THREAD_ENTRY * thread_p, PAGE_PTR page_p, void *args)
{
  bool is_temp = *(bool *) args;                 /* <- &is_temp forwarded through file_alloc_multiple */
  pgbuf_set_page_ptype (thread_p, page_p, PAGE_EHASH);
  if (!is_temp)                                  /* <- persistent: log the allocation, zero-length payloads */
    log_append_undoredo_data2 (thread_p, RVEH_INIT_NEW_DIR_PAGE, NULL, page_p, -1, 0, 0, NULL, NULL);
  pgbuf_set_dirty (thread_p, page_p, DONT_FREE);
  return NO_ERROR;
}

RVEH_INIT_NEW_DIR_PAGE undoredo는 양쪽 모두 NULL 데이터를 갖는다. redo 핸들러 ehash_rv_init_dir_new_page_redo는 PAGE_EHASH를 재스탬핑하고 페이지를 dirty로 표시할 뿐이다. 빈 undo 측은 file_alloc_multiple 자체의 할당 undo에 의존한다. is_temp == true 경로는 로깅을 건너뛴다 — 임시 EHID 파일은 복구되지 않는다(곳곳에 등장하는 !is_temp 게이트). args가 void *인 이유는 file_alloc_multiple이 범용적이기 때문이다. 콜백은 이를 bool *로 캐스팅한다.

7.5 `ehash_connect_bucket` — 연속 포인터 런 재지정

이 함수는 hash_key의 처음 local_depth 비트와 일치하는 모든 디렉터리 슬롯을 bucket_vpid로 설정한다. 전역 깊이가 d일 때 그러한 슬롯은 정확히 2^(d - local_depth)개이며, 하위 d - local_depth 비트만 다르기 때문에 연속적으로 배치된다.

런 계산. 헤더를 read latch로 고정하고 dir_header에 memcpy한 뒤 unfix한다. 헤더 고정 실패 시 어떠한 변경도 없이 ER_FAILED를 반환하므로 해제할 sysop이 없다(아래의 루프 내 write latch 실패와 다르다). 이후 location = GETBITS (hash_key, 1, dir_header.depth) (d-bit 디렉터리 인덱스)와 diff = dir_header.depth - local_depth를 계산한다.

// ehash_connect_bucket -- src/storage/extendible_hash.c
if (diff != 0)
  {
    for (set_bits = 0, i = 0; i < diff; i++)
      set_bits = 2 * set_bits + 1;                     /* <- low diff bits all 1 */
    clear_bits = ~set_bits;
    first_ptr_offset = location & clear_bits;          /* <- low diff bits forced to 0 */
    last_ptr_offset  = location | set_bits;            /* <- low diff bits forced to 1 */
    ehash_dir_locate (&first_page, &first_ptr_offset);  ehash_dir_locate (&last_page, &last_ptr_offset);
  }
else                                                   /* <- single pointer (local == global) */
  { first_ptr_offset = location; ehash_dir_locate (&first_page, &first_ptr_offset);
    last_page = first_page; last_ptr_offset = first_ptr_offset; }

diff != 0 분기는 다중 슬롯 런을 처리한다. location & clear_bits는 첫 번째 플랫 인덱스, location | set_bits는 마지막 플랫 인덱스이며, 각각 ehash_dir_locate로 (page, offset) 쌍으로 매핑된다. diff == 0 분기(local_depth == dir_header.depth)는 슬롯 하나로 축소된다. location은 플랫 슬롯 인덱스이며, ehash_dir_locate는 바이트 *_ptr_offset 값을 제자리에서 재작성한다.

페이지별 갱신 루프는 [first_page, last_page] 범위의 각 페이지를 write latch로 고정하고 범위 내 슬롯을 재작성한다.

// ehash_connect_bucket (update loop) -- src/storage/extendible_hash.c
for (i = first_page; i <= last_page; i++)
  {
    page_p = ehash_fix_nth_page (..., i, PGBUF_LATCH_WRITE);
    if (page_p == NULL) return ER_FAILED;              /* <- in-loop fix failure: sysop will abort */
    start_offset = (i == first_page) ? first_ptr_offset : 0;
    end_offset   = (i == last_page)  ? last_ptr_offset + sizeof (EHASH_DIR_RECORD) : DB_PAGESIZE;
    bef_length = end_offset - start_offset;
    repetition.count = bef_length / sizeof (EHASH_DIR_RECORD);   /* <- run length on THIS page */
    if (!is_temp)                                                /* undo = bef_length pre-image bytes; redo = &repetition */
      log_append_undoredo_data2 (..., RVEH_CONNECT_BUCKET, ..., page_p, start_offset, bef_length,
                                 sizeof (EHASH_REPETITION), (char *) page_p + start_offset, &repetition);
    dir_record_p = (EHASH_DIR_RECORD *) ((char *) page_p + start_offset);
    for (j = 0; j < repetition.count; j++)
      { dir_record_p->bucket_vpid = *bucket_vpid_p; dir_record_p++; }   /* <- stamp target vpid */
    pgbuf_set_dirty (thread_p, page_p, FREE);
  }

start_offset / end_offset 삼항식은 런을 페이지에 맞게 잘라낸다. first_page에서는 페이지 중간에서 시작할 수 있고, last_page에서는 페이지 중간에서 끝날 수 있으며, 그 외 경우는 [0, DB_PAGESIZE) 전체를 차지한다. 루프 내 fix 실패는 즉시 ER_FAILED를 반환한다. 호출자의 log_sysop_abort(ehash_extend_bucket의 log_sysop_start로 열린 sysop)가 이미 기록된 부분 갱신을 롤백한다.

불변식 (페이지당 WAL 레코드 하나, redo 페이로드 O(1)): 한 페이지의 런이 몇 개의 포인터를 커버하든, 정확히 하나의 RVEH_CONNECT_BUCKET 레코드가 내보내지며 redo 페이로드는 count에 무관하게 sizeof(EHASH_REPETITION)이다. undo 측은 O(1)이 아니다 — 이전 내용이 임의의 혼합일 수 있으므로 리터럴 사전 이미지 바이트로 기록된다. 그러나 일반적인 재생 경로인 redo 측은 O(1)이다. 위반 시 결과: 슬롯별 로깅을 하면 깊은 디렉터리에서 분할 하나에 비례하는 수의 레코드가 생성되어 런 길이 설계의 의도가 무너진다.

7.6 종합 — 재삽입 결정

ehash_extend_bucket이 sysop을 commit하고 형제 페이지를 반환한 뒤(오류 시 NULL, 이 경우 버킷을 unfix하고 EHASH_ERROR_OCCURRED를 반환), ehash_insert_bucket_after_extend_if_need는 §7.1에서 캡처된 out_new_bit를 사용한다.

// ehash_insert_bucket_after_extend_if_need -- src/storage/extendible_hash.c
target_bucket_page_p = new_bit ? sibling_page_p : bucket_page_p;  /* <- MSB 1 -> sibling, 0 -> original */
result = ehash_insert_to_bucket (..., target_bucket_page_p, ...);

new_bit는 트리거 키의 해시값에서 new_local_depth번째 비트다. §7.1의 connect 호출은 비트-0 슬롯은 모두 원본을, 비트-1 슬롯은 모두 형제를 가리키게 만들었다. 이 if는 overflow 레코드에도 동일한 분할 결과를 반영한다. 버킷이 방금 분할되었으므로 선택된 쪽에는 여유 공간이 있어 재삽입이 재귀하지 않는다 — 6장의 분리 깊이(separating-depth) 불변식이 이를 보장하는 조건과 같다.

7.7 챕터 요약 — 핵심 정리

두 배 확장은 local_depth <= global depth라는 깊이 상한 불변식을 복원한다. 버킷을 전역 깊이 위로 올리는 분할은 이를 일시적으로 위반하며, ehash_expand_directory가 depth를 new_local_depth로 끌어올려 복원한다.
분할 후 두 개의 독립적인 게이트가 실행된다. new_local_depth > depth는 디렉터리를 두 배 확장하고, (new_local_depth - old_local_depth) > 1은 NULL-후-재연결 분기를 트리거한다(Figure 7-1).
ehash_expand_directory는 역방향 이중 커서 이동으로 제자리에서 두 배 확장을 수행하므로, 어떤 소스 포인터도 읽히기 전에 덮어쓰이지 않는다.
재사용되는 디렉터리 페이지는 RVEH_REPLACE undo 사전 이미지를 갖는다. 신규 페이지는 RVEH_INIT_NEW_DIR_PAGE와 파일 관리자의 할당 undo에 의존한다.
EHASH_REPETITION {vpid, count}는 connect redo를 페이지당 O(1)이자 멱등적으로 유지한다. undo 측은 리터럴 사전 이미지 바이트를 가진다.
connect 런은 연속적이며 비트 연산으로 유도된다. set_bits / clear_bits가 location의 하위 depth - local_depth 비트를 마스킹하여 첫 번째와 마지막 플랫 인덱스를 구한다.
세 번의 connect 호출 — 오래된 범위를 NULL 처리, CLEARBIT으로 하위 절반을 원본에 연결, SETBIT으로 상위 절반을 형제에 연결 — 이 포인터 커버리지 불변식을 강제한다. 어떠한 변경보다 먼저 캡처된 out_new_bit는 재삽입 측을 결정하여, 새로 생긴 여유 공간이 트리거 키를 두 번째 분할 없이 수용하도록 한다.

Chapter 8: 키 삭제와 버킷 병합

독자 질문: 키는 어떻게 제거되고, 제거 후 두 버킷이 다시 합쳐지는 시점은 언제인가? 삭제는 삽입(5~7장)을 거울처럼 반영하되, 한 가지 의도적인 비대칭이 있다. 삽입은 hot path에서 directory를 변경할 수 있지만, 삭제는 절대 그렇게 하지 않는다. 일반적인 삭제는 버킷 페이지 하나를 수정하고 로그 레코드 두 건을 기록한 뒤 반환한다. 버킷의 점유율이 하한선 아래로 떨어질 때만 코드는 두 번째 단계로 내려가, 더 강한 latch를 잡고 병합 기계(merge machinery)로 진입한다. 이 장에서는 ehash_delete, ehash_check_merge_possible, ehash_merge, ehash_merge_permanent, ehash_find_depth의 모든 분기를 추적한다. 디렉터리 축소 본체(ehash_shrink_directory_if_need)는 9장에서 다룬다. 새로운 구조체는 없다(세 개의 헤더는 1장 참조).

8.1 삭제의 2단계 구조

ehash_delete는 어떤 system operation 바깥에서도 완전히 실행된다. 레코드를 제거하고 로그를 기록하며, 버킷이 굶주린 상태가 되면 두 latch를 모두 해제하고 ehash_merge를 호출한다. ehash_merge는 루트에 PGBUF_LATCH_WRITE를 잡고 처음부터 다시 내려간다. 단계 경계는 삭제와 병합 재하강 사이의 unfix이며, 병합은 처음부터 루트-WRITE를 소유한다.

왜 S-to-X 승격 경로가 없는가? 삽입은 split이 directory를 변경하기 때문에 루트 latch를 READ→WRITE로 승격한다. 삭제의 hot path는 directory를 변경하지 않으므로 루트는 PGBUF_LATCH_READ를 유지한다. 모든 directory 변경은 ehash_merge 내부의 두 번째 하강에 있다. 승격할 것이 없다.

8.2 하강, 키 미발견 경로, 레코드 제거

// ehash_delete -- src/storage/extendible_hash.c
dir_root_page_p = ehash_find_bucket_vpid_with_hash (thread_p, ehid_p, key_p, PGBUF_LATCH_READ,
                                    PGBUF_LATCH_WRITE, &bucket_vpid, NULL, &location);  /* root S, bucket X */
if (dir_root_page_p == NULL) return NULL;       /* <- descent failed, nothing fixed */
dir_header_p = (EHASH_DIR_HEADER *) dir_root_page_p;
if (bucket_vpid.pageid == NULL_PAGEID)          /* (1) directory slot points at no bucket */
  { pgbuf_unfix_and_init (thread_p, dir_root_page_p); er_set (..., ER_EH_UNKNOWN_KEY, 0); return NULL; }
bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid, &bucket_vpid, PGBUF_LATCH_WRITE);
if (bucket_page_p == NULL) { pgbuf_unfix_and_init (thread_p, dir_root_page_p); return NULL; }
if (ehash_locate_slot (thread_p, bucket_page_p, dir_header_p->key_type, key_p, &slot_no) == false)
  { pgbuf_unfix_and_init (thread_p, bucket_page_p);   /* (2) key absent from a real bucket */
    pgbuf_unfix_and_init (thread_p, dir_root_page_p); er_set (..., ER_EH_UNKNOWN_KEY, 0); return NULL; }

하강(3장)은 루트에 READ, 버킷에 WRITE를 요청한다. 두 가지 서로 다른 키 미발견 경로가 있으며 둘 다 ER_EH_UNKNOWN_KEY를 경고로 올린다. (1) 비어 있는 directory slot(bucket_vpid.pageid == NULL_PAGEID) — 이전 병합(8.7)에 의해 초기화된 slot 등, 해당 항목이 버킷을 가리킨 적 없는 경우로, 루트만 unfix한다. (2) 실제로 fix된 버킷에서 키가 없는 경우(ehash_locate_slot == false), 두 페이지를 모두 unfix한다. slot이 발견되면 레코드를 peek하고, 레코드가 파괴되기 전에 두 로그 디스크립터를 모두 구성한다. spage_delete가 peek된 포인터를 무효화하기 때문이다.

8.3 RVEH_DELETE: 논리적 undo, 물리적 redo

동일한 RVEH_DELETE 인덱스의 undo와 redo 디스크립터는 서로 다른 페이로드를 갖는다 — 충돌 복구 가능한 확장 해싱의 핵심이다.

// ehash_delete -- src/storage/extendible_hash.c
(void) spage_get_record (thread_p, bucket_page_p, slot_no, &bucket_recdes, PEEK);
/* undo recdes = EHID || (value, key) -- file id, NOT page/slot;  redo recdes = type(short) || (value, key) */
(void) spage_delete (thread_p, bucket_page_p, slot_no);     /* <- record gone */
pgbuf_set_dirty (thread_p, bucket_page_p, DONT_FREE);
if (!is_temp)
  { log_append_undo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, NULL, ...);            /* NULL page = logical */
    log_append_redo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, bucket_page_p, slot_no, ...); } /* physical */

불변식 (논리적 undo는 이후의 split에도 살아남아야 한다). undo 레코드는 EHID || (value, key)를 파일에 첨부(page == NULL)하여, 복구 시 물리적 페이지 패치가 아닌 논리적 undo 핸들러(역방향 재삽입)로 강제 진입한다. 물리적 (page, slot) undo는 삭제와 롤백 사이에 concurrent split이 발생하면 다른 버킷이 소유한 slot에 재삽입하게 된다. 논리적 undo는 키를 다시 해시하여 디렉터리 변경과 무관하게 올바른 버킷을 다시 찾는다.

redo 레코드는 순수하게 물리적(bucket_page_p, slot_no)이며, 알려진 페이지 이미지에서 앞 방향으로 재생되고 type || (value, key)를 담아 레코드를 바이트 단위로 복원한다. #if defined (ENABLE_UNUSED_FUNCTION) REC_BIGONE 긴 문자열용 overflow-VPID 블록은 컴파일에서 제외된다(is_long_str는 항상 false, overflow_delete는 도달 불가). is_temp(file_is_temp로 판정)는 모든 로깅을 차단한다 — 임시(temp) 해시는 WAL 트래픽 없이 삭제한다.

8.4 언더플로우 테스트와 0.4 대 0.9의 이유

spage_delete 이후 점유율은 정확히 세 가지 결과 중 하나로 분류된다:

// ehash_delete -- src/storage/extendible_hash.c
if (spage_number_of_records (bucket_page_p) <= 1)          /* slot 0 is the header -> logically empty */
  result = EHASH_BUCKET_EMPTY;
else if ((DB_PAGESIZE - spage_max_space_for_new_record (thread_p, bucket_page_p)) < EHASH_UNDERFLOW_THRESHOLD)
  result = EHASH_BUCKET_UNDERFLOW;                          /* used < 0.4 * PAGESIZE */
else
  result = EHASH_SUCCESSFUL_COMPLETION;                     /* healthy, no merge attempt */

<= 1개의 레코드는 헤더 slot만 남았음을 의미한다. 그 외의 경우 DB_PAGESIZE - max_space가 사용 중인 바이트 수다. 임계값은 EHASH_UNDERFLOW_RATE 0.4와 EHASH_OVERFLOW_RATE 0.9이며, 각각 DB_PAGESIZE를 곱하여 EHASH_UNDERFLOW_THRESHOLD / EHASH_OVERFLOW_THRESHOLD가 된다.

불변식 (히스테리시스가 split-merge 요동을 방지한다). 병합은 0.4 이하에서만 고려되지만, 두 버킷의 합계가 0.9 이하일 때만 허용된다(8.6에서 검사). 두 개의 서로 다른 비율이 이 간격을 강제한다. 하한과 상한이 같다면, 경계에 있는 버킷은 병합 후 오버플로우, 다음 삽입에서 split, 다시 하한 이하, 다시 병합을 반복하며 모든 작업에서 스래싱(thrashing)이 발생한다. 0.4/0.9 간격은 병합된 버킷을 중간 범위에 안착시킨다.

EHASH_SUCCESSFUL_COMPLETION이면 버킷이 건강한 상태다. 프로브를 건너뛰고 두 페이지를 unfix한 뒤 key_p를 반환한다.

8.5 S_LOCK 프로브와 latch 핸드오프

비어 있거나 언더플로우 상태일 때 ehash_delete는 ehash_check_merge_possible의 읽기 전용 S_LOCK 프로브를 실행한 뒤, 두 latch를 모두 내려놓는다 — latch를 잡은 채로는 절대 병합하지 않는다:

// ehash_delete -- src/storage/extendible_hash.c
do_merge = false;
if (result == EHASH_BUCKET_EMPTY || result == EHASH_BUCKET_UNDERFLOW)
  if (ehash_check_merge_possible (thread_p, ehid_p, dir_header_p, &bucket_vpid, bucket_page_p, location,
                                  S_LOCK, &old_local_depth, &sibling_vpid, NULL, NULL, NULL, NULL)
      == EHASH_SUCCESSFUL_COMPLETION)
    do_merge = true;
pgbuf_unfix_and_init (thread_p, bucket_page_p);     /* <- release BEFORE merge */
pgbuf_unfix_and_init (thread_p, dir_root_page_p);
if (do_merge) ehash_merge (thread_p, ehid_p, key_p, is_temp);   /* re-descends from scratch */
return (key_p);

이 프로브는 순수히 조언적(advisory)이다. 두 페이지는 ehash_merge가 실행되기 전에 해제되므로 concurrent 트랜잭션이 버킷을 다시 채울 수 있다. 이 프로브는 형제 버킷이 명백히 없을 때 낭비적인 두 번째 하강을 건너뛸 뿐이며, ehash_merge는 모든 것을 재검증한다(8.7).

8.6 ehash_check_merge_possible: 세 가지 반환 코드

lock_type을 통한 두 가지 모드(S_LOCK = 프로브, X_LOCK = 커밋). 형제 slot은 location과 local_depth 위치(가장 상위 키 비트로부터)의 비트만 다르다. 분기 **(D)**는 깊이가 다른 형제를 거부한다. 버킷은 local_depth가 같을 때만 진정한 버디이기 때문이다. 공간 검사는 num_records > 1일 때만 실행된다. X_LOCK 모드에서 형제는 write-fix 상태로 유지되어 병합에 전달되며, S_LOCK에서는 항상 unfix된다.

// ehash_check_merge_possible -- src/storage/extendible_hash.c
*out_old_local_depth_p = bucket_header_p->local_depth;
if (bucket_header_p->local_depth == 0) return EHASH_NO_SIBLING_BUCKET;  /* (A) lone depth-0 bucket */
ehash_find_bucket_vpid (..., loc, PGBUF_LATCH_READ, sibling_vpid_p);    /* loc = location with local_depth bit flipped */
if (VPID_ISNULL (sibling_vpid_p))            return EHASH_NO_SIBLING_BUCKET;  /* (B) slot empty */
if (VPID_EQ (sibling_vpid_p, bucket_vpid_p)) return EHASH_NO_SIBLING_BUCKET;  /* (C) self       */
sibling_page_p = ehash_fix_old_page (..., lock_type == S_LOCK ? PGBUF_LATCH_READ : PGBUF_LATCH_WRITE);
spage_next_record (sibling_page_p, &first_slot_id, &recdes, COPY);            /* sibling header */
if (sibling_bucket_header.local_depth != bucket_header_p->local_depth)
  { pgbuf_unfix_and_init (thread_p, sibling_page_p); return EHASH_NO_SIBLING_BUCKET; }  /* (D) depth mismatch */
if (spage_number_of_records (bucket_page_p) > 1)         /* space test only when source has records to move */
  if ((sibling_used + bytes_to_transfer) > EHASH_OVERFLOW_THRESHOLD)                /* > 0.9 */
    { pgbuf_unfix_and_init (thread_p, sibling_page_p); return EHASH_FULL_SIBLING_BUCKET; }
if (lock_type == S_LOCK) pgbuf_unfix_and_init (thread_p, sibling_page_p);  /* probe: release */
else *out_sibling_page_p = sibling_page_p;  /* commit: keep WRITE-fixed, + first_slot_id, num_records, loc */
return EHASH_SUCCESSFUL_COMPLETION;

반환 코드	조건	호출자(`ehash_merge`)의 동작
`EHASH_NO_SIBLING_BUCKET`	depth 0 (A), 빈 slot (B), 자기 자신 (C), depth 불일치 (D)	빈 버킷 특수 케이스(8.7) 처리 또는 아무 것도 하지 않음
`EHASH_FULL_SIBLING_BUCKET`	형제 사용량 + 전송량 > 0.9	버킷 unfix, 병합하지 않음
`EHASH_SUCCESSFUL_COMPLETION`	버디 발견, 레코드가 들어맞음	`ehash_merge_permanent` 실행
`EHASH_ERROR_OCCURRED`	fix/스캔 실패	모두 unfix, 반환

8.7 ehash_merge: 재하강, 재검증, 그리고 분기 전환

ehash_merge는 커밋 패스다. 루트-WRITE로 재하강하고, 버킷을 WRITE로 재fix한 뒤, 8.4와 동일한 3방향 분류를 다시 계산한다 — BUCKET_EMPTY / BUCKET_UNDERFLOW / 다시 채워짐(bucket_status = NO_ERROR).

불변식 (concurrent 재충전 시 재검증). concurrent 삽입이 프로브가 latch를 잡지 않는 동안 버킷을 하한 이상으로 채웠을 수 있다. bucket_status를 재계산하여 NO_ERROR일 때 unfix하면, 이미 건강해진 버킷에 병합이 진행되는 것을 막는다(그렇지 않으면 형제를 오버플로우시키거나 레코드를 유실할 수 있다). NO_ERROR이면 전체 if 블록을 건너뛰고 마지막 pgbuf_unfix_and_init (dir_root_page_p)로 제어가 넘어간다.

여전히 비어 있거나 언더플로우 상태이면, ehash_check_merge_possible이 X_LOCK으로 호출되어 형제를 write-latch 상태로 남긴다. 결과는 5방향 switch를 구동한다(그림 8-1):

flowchart TD
  A["루트 X, 버킷 X 재fix"] --> B{"여전히 비어 있음/언더플로우?"}
  B -- "아니오, 재충전됨" --> Z["루트 unfix, 반환"]
  B -- "예" --> C["check_merge_possible X_LOCK"]
  C --> D{"결과"}
  D -- "NO_SIBLING" --> E{"EMPTY이고 depth != 0?"}
  E -- "예" --> F["sysop: dealloc + NULL_VPID 연결\nold -1 조정, 축소?, 커밋"]
  E -- "아니오" --> G["버킷 unfix"]
  D -- "FULL_SIBLING" --> H["버킷 unfix, 병합 없음"]
  D -- "SUCCESSFUL" --> I["sysop: merge_permanent + dealloc\nold -2, new +1 조정, 축소?\n형제 연결, 커밋"]
  D -- "ERROR" --> J["버킷 + 루트 unfix, 반환"]
  D -- "default" --> K["ER_EH_CORRUPTED, unfix"]
  F --> Z
  G --> Z
  H --> Z
  I --> Z

그림 8-1. ehash_merge switch. SUCCESSFUL과 빈 버킷 서브케이스를 제외한 모든 분기는 directory를 변경하지 않고 종료된다.

EHASH_NO_SIBLING_BUCKET — 버디 없음. 버킷이 old_local_depth != 0인 빈 상태이면 해당 페이지는 순수한 낭비이므로 system operation 하에서 회수된다. 실패 시 log_sysop_abort가 트리거된다:

// ehash_merge -- src/storage/extendible_hash.c  (NO_SIBLING_BUCKET arm)
pgbuf_unfix_and_init (thread_p, bucket_page_p);
if ((bucket_status == EHASH_BUCKET_EMPTY) && (old_local_depth != 0))
  { if (!is_temp) log_sysop_start (thread_p);
    if (file_dealloc (..., &bucket_vpid, FILE_EXTENDIBLE_HASH) != NO_ERROR) { /* abort, return */ }
    if (ehash_connect_bucket (..., old_local_depth, hash_key, &null_vpid, is_temp) != NO_ERROR) { /* abort */ }
    ehash_adjust_local_depth (..., old_local_depth, -1, is_temp);   /* one bucket gone */
    ehash_shrink_directory_if_need (thread_p, ehid_p, dir_header_p, is_temp);
    if (!is_temp) log_sysop_commit (thread_p); }

old_local_depth == 0이면 전역 버킷이 하나뿐이다. 비어 있어도 유지된다 — 버킷은 항상 하나 이상 있어야 한다 — 단순히 unfix한다. EHASH_FULL_SIBLING_BUCKET — 버디가 너무 꽉 찼다. 레코드는 이미 삭제되었으므로 버킷을 그냥 해제한다(병합 없음, sysop 없음). EHASH_SUCCESSFUL_COMPLETION — 실제 병합(8.8). **EHASH_ERROR_OCCURRED**는 버킷+루트를 unfix하고 반환한다. **default**는 도달 불가이며, ER_EH_CORRUPTED를 발생시킨다.

8.8 ehash_merge_permanent와 두 번의 adjust 호출

ehash_merge_permanent는 소스 레코드들을 여전히 fix된 형제로 이동하고, 형제의 local depth를 재계산하여 헤더를 다시 쓴다. 변경 전 전체 페이지 RVEH_REPLACE undo/redo 이미지로 변경을 감싸, 복구 시 병합된 페이지를 원자적으로 복원하거나 재생한다.

// ehash_merge_permanent -- src/storage/extendible_hash.c
if (!is_temp)  /* full-page undo image; symmetric redo emitted after the loop */
  log_append_undo_data2 (thread_p, RVEH_REPLACE, &ehid_p->vfid, sibling_page_p, 0, DB_PAGESIZE, sibling_page_p);
for (slot_id = 1; slot_id < num_records; slot_id++)        /* skip header slot 0 */
  { spage_get_record (thread_p, bucket_page_p, slot_id, &recdes, PEEK);
    bucket_record_p = (char *) recdes.data + sizeof (OID);            /* skip assoc-value, point at key */
    is_record_exist = ehash_locate_slot (..., (void *) bucket_record_p, &new_slot_id);
    if (is_record_exist == false)                                    /* re-insert in sort order */
      { if (spage_insert_at (thread_p, sibling_page_p, new_slot_id, &recdes) != SP_SUCCESS) return ER_FAILED; }
    else { er_set (..., ER_EH_CORRUPTED, 0); return ER_FAILED; } }    /* dup key = corruption */
found_depth = ehash_find_depth (thread_p, ehid_p, location, bucket_vpid_p, sibling_vpid_p);
if (found_depth == 0) return ER_FAILED;
sibling_bucket_header.local_depth = dir_header_p->depth - found_depth;   /* recomputed; then spage_update + set_dirty */
*out_new_local_depth_p = sibling_bucket_header.local_depth;

형제에 이미 존재하는 키(is_record_exist == true)는 ER_EH_CORRUPTED다 — 버디들은 서로소인 키 집합을 보유한다. ehash_merge의 SUCCESSFUL 분기로 돌아와 소스를 할당 해제하고 directory 장부를 정리한다:

// ehash_merge -- src/storage/extendible_hash.c  (SUCCESSFUL arm)
file_dealloc (thread_p, &dir_header_p->bucket_file, &bucket_vpid, FILE_EXTENDIBLE_HASH);
ehash_adjust_local_depth (..., old_local_depth, -2, is_temp);
ehash_adjust_local_depth (..., new_local_depth, 1, is_temp);
ehash_shrink_directory_if_need (thread_p, ehid_p, dir_header_p, is_temp);
ehash_connect_bucket (..., new_local_depth, hash_key, &sibling_vpid, is_temp);

불변식 (local_depth_count 보존). 깊이 d인 두 버디를 깊이 d-1인 버킷 하나로 병합하는 것은 d에서 -2, d-1에서 +1을 의미한다. 두 번의 ehash_adjust_local_depth 호출이 이를 강제한다. (old_local_depth, -2)는 병합 전 두 버킷을 제거하고, (new_local_depth, +1)은 병합된 하나를 추가한다. 잘못된 카운트는 허위 축소(항목 고아화)를 유발하거나, 필요한 축소를 막아(페이지 누수) 9장이 이 카운터를 위에서부터 읽기 때문에 문제가 된다. 빈 버킷 서브케이스(8.7)는 퇴화 버전이다. 버킷 하나가 대상 없이 사라지며 단일 (old_local_depth, -1) 호출로 처리된다.

ehash_find_depth는 old_local_depth - 1을 가정하지 않고 new_local_depth를 재계산한다. location 주변의 directory 이웃으로 check_depth를 넓혀가며, 탐색된 모든 항목이 소스, 형제, 또는 NULL을 가리키는 동안 계속하다가 첫 번째 외부 항목에서 멈춘다. 인접 slot이 이미 NULL로 무너진 경우 depth - found_depth가 old_local_depth - 1보다 작을 수 있다. ehash_connect_bucket(7장)은 병합된 영역의 모든 항목을 sibling_vpid로 연결하고(null_vpid는 빈 케이스에서), ehash_shrink_directory_if_need는 동일한 sysop 내에서 실행된다(9장).

8.9 챕터 요약 — 핵심 정리

삭제는 설계상 2단계다. ehash_delete는 루트-S/버킷-X 하에서 제거 및 로깅을 수행하며, directory를 절대 변경하지 않는다. 굶주린 버킷은 두 latch를 해제하고 ehash_merge를 호출하며, ehash_merge는 루트-X로 재하강한다. hot path가 directory 읽기 전용이므로 S-to-X 승격 없음.
RVEH_DELETE는 논리적 undo, 물리적 redo다. Undo(EHID || value || key, NULL 페이지)는 롤백 시 키를 다시 해시하여 중간 split에도 살아남는다. Redo(type || value || key, 고정된 page+slot)는 앞 방향으로 재생된다. is_temp는 모든 로깅을 억제한다.
0.4 하한, 0.9 상한, 의도적이다. EHASH_UNDERFLOW_THRESHOLD는 병합 시도 여부를 결정하고, EHASH_OVERFLOW_THRESHOLD(8.6에서)는 들어맞는지 여부를 결정한다. 이 간격은 advisory 프로브가 모든 latch를 내려놓은 후 ehash_merge가 재검증하는 split-merge 스래싱에 대한 히스테리시스다.
ehash_check_merge_possible은 세 가지 코드를 반환한다. NO_SIBLING_BUCKET(depth 0 / 빈 slot / 자기 자신 / depth 불일치), FULL_SIBLING_BUCKET(> 0.9), SUCCESSFUL_COMPLETION(버디가 들어맞음). X_LOCK 모드에서는 병합을 위해 형제를 write-latch 상태로 남긴다.
실제 병합은 레코드를 이동하고, 깊이를 재계산하며, 재연결하고, 재카운트한다. ehash_merge_permanent는 모든 소스 레코드를 형제에 재삽입하고(중복은 ER_EH_CORRUPTED), 전체 페이지 RVEH_REPLACE 이미지 하에서 ehash_find_depth로 깊이를 재계산한다. ehash_merge는 소스를 할당 해제하고 adjust_local_depth(old, -2) + (new, +1)을 발행하여 local_depth_count를 보존한다. local_depth != 0인 빈 버킷 케이스는 퇴화된 병합이다. 할당 해제, 항목을 NULL_VPID로 초기화, 카운트 -1, 하나의 log_sysop 괄호 — 단독 depth-0 버킷은 항상 유지된다.

Chapter 9: 디렉터리 축소

독자 질문: 병합으로 버킷 로컬 깊이가 낮아진 이후, 전역 깊이는 언제, 어떻게 다시 내려오는가? Chapter 8은 ehash_merge가 버킷 쌍을 합치고 로컬 깊이 히스토그램을 갱신하는 과정을 추적했다. 이 챕터는 그 다음 단계를 다룬다 — 히스토그램 기반의 수축 판단(ehash_shrink_directory_if_need)과 실제 배열 반감(ehash_shrink_directory). 수축은 Chapter 7의 디렉터리 배증과 거울 관계다. 디렉터리 페이지 레이아웃과 ehash_dir_locate는 Chapter 7을, 디렉터리가 지연 수축하는 이유는 동반 문서 cubrid-extendible-hash.md를 참고하라.

새 구조체는 등장하지 않는다. 모든 것을 이끄는 단일 필드는 ehash_adjust_local_depth(Chapter 6, 8)가 유지하는 EHASH_DIR_HEADER::local_depth_count다:

// struct ehash_dir_header -- src/storage/extendible_hash.c
  int local_depth_count[EHASH_HASH_KEY_BITS + 1];   /* histogram: index == local depth */
  short depth;                  /* global depth of the directory: 2^depth pointers */

local_depth_count[d]는 로컬 깊이가 d인 버킷 수를 기록하고, depth는 전역 깊이다. 이 히스토그램 덕분에 삭제 시점의 병합이 모든 버킷을 순회하지 않고도 O(depth)번의 정수 읽기만으로 디렉터리가 현재 버킷들에 비해 지나치게 깊은지 판단할 수 있다.

9.1 수축을 안전하게 만드는 히스토그램 불변 조건

불변 조건 (히스토그램 완전성). 모든 레벨 d에서 local_depth_count[d]는 로컬 깊이가 정확히 d인 버킷 수와 같다. 이는 곧 비零 카운트를 가진 최고 d가 dir_header->depth를 초과하지 않는다는 뜻이기도 하다. 병합이 델타 갱신을 빠뜨렸다면, 아래의 스캔에서 확인하는 최고 비零 레벨이 실제 최고 버킷을 잘못 보고하게 되고, ehash_shrink_directory는 살아있는 버킷의 로컬 깊이 아래로 depth를 낮춰 해당 버킷의 sibling 포인터를 고아로 만들고 조회를 망가뜨린다.

이 조건은 히스토그램의 유일한 쓰기 주체인 ehash_adjust_local_depth로 모든 로컬 깊이 변경을 경유하도록 강제함으로써 지켜진다. 이 함수는 RVEH_INC_COUNTER undo/redo를 기록해 복구 시에도 동일한 카운트가 재구성되도록 한다:

// ehash_adjust_local_depth -- src/storage/extendible_hash.c
  dir_header_p->local_depth_count[depth] += delta;          /* <- the only writer of the histogram */
  redo_inc = delta;
  undo_inc = -delta;                                        /* <- undo simply negates the increment */
  if (!is_temp)
    log_append_undoredo_data2 (thread_p, RVEH_INC_COUNTER, ... &undo_inc, &redo_inc);

델타는 두 병합 호출 경로에서 쌍으로 들어온다(Chapter 8). 빈 버킷 경로는 (old_local_depth, -1)을 전달하고, 레코드 이동 경로는 old_local_depth의 버킷 두 개를 new_local_depth = old_local_depth - 1의 버킷 하나로 합치기 위해 (old_local_depth, -2), (new_local_depth, +1) 순으로 델타를 적용한다. 어느 경우든 가장 높은 레벨의 카운트가 줄어드는데, 이것이 수축 트리거가 감시하는 신호다.

Figure 9-1은 이 불변 조건이 묶어주는 관계를 보여준다:

flowchart LR
  subgraph H["dir_header (루트 페이지 0)"]
    D["depth = 전역 깊이"]
    LDC["local_depth_count[0..KEY_BITS]"]
  end
  ALD["ehash_adjust_local_depth\n유일한 쓰기 주체"] -->|"+/- delta + RVEH_INC_COUNTER 로그"| LDC
  MERGE["ehash_merge 경로\n(Chapter 8)"] --> ALD
  LDC -->|"위에서 아래로 스캔"| IFNEED["ehash_shrink_directory_if_need"]
  D -->|"스캔 시작점"| IFNEED
  IFNEED -->|"유휴 레벨 2개 이상이면"| SHRINK["ehash_shrink_directory"]
  SHRINK -->|"새 depth 기록"| D

9.2 `ehash_shrink_directory_if_need` — 수축 트리거

병합 시스템 오퍼레이션 내부에서, 이번 병합의 히스토그램 델타가 적용된 직후에 호출된다. 히스토그램을 위에서 아래로 읽어 물리적 수축이 필요한지 판단한다:

// ehash_shrink_directory_if_need -- src/storage/extendible_hash.c
  int i;
  i = dir_header_p->depth;
  while (dir_header_p->local_depth_count[i] == 0)   /* <- walk down past every empty top level */
    {
      i--;
    }
  if ((dir_header_p->depth - i) > 1)                /* <- need at least two idle levels */
    {
      ehash_shrink_directory (thread_p, ehid_p, i + 1, is_temp);
    }

분기 완전 분석:

i = dir_header_p->depth — 어떤 버킷도 초과할 수 없는 최고 레벨에서 시작한다.
while (local_depth_count[i] == 0) i-- — 버킷이 없는 레벨을 내려가며 탐색한다. ehash_create_helper에서 local_depth_count[0]은 1로 초기화되고 절대 비지 않으므로, 루프는 유한하게 끝나며 버킷을 보유한 가장 높은 레벨 i에 도달한다.
- 루프가 한 번도 돌지 않는 경우 (local_depth_count[depth] != 0) — 전역 깊이에 이미 버킷이 있어 i == depth가 되고, 유휴 레벨이 없다.
- 루프가 k번 도는 경우 — 상위 k개 레벨이 비어 있으며, 생존한 버킷 중 가장 높은 로컬 깊이는 i = depth - k다.
if ((depth - i) > 1) — depth - i는 완전히 유휴인 상위 레벨 수다. 이 값이 1보다 클 때만 수축이 실행된다. 유휴 레벨이 0개 또는 1개이면 수축을 건너뛰고(후자는 히스테리시스 대역), 2개 이상이면 new_depth = i + 1을 요청해 여유 공간으로 유휴 레벨 1개를 남긴다. 유휴 레벨이 세 개여도 호출은 한 번뿐이다 — ehash_shrink_directory는 깊이 차이에서 times를 계산하며 재귀하지 않는다.

불변 조건 (반진동 히스테리시스). 유휴 레벨이 최소 두 개일 때((depth - i) > 1)만 수축하며, i + 1로 수축해 유휴 레벨 하나를 남긴다. 배증(Chapter 7)은 버킷 하나가 new_local_depth > depth를 요구하는 순간 즉시 발동하는 > 0 스타일 트리거다. 수축이 대칭적으로 유휴 레벨 하나에서 발동한다면, 최상위 레벨을 비우는 삭제 하나가 수축을 유발하고, 그 깊이로 버킷을 분할하는 다음 삽입이 즉시 재배증을 유발하는 순환이 생긴다 — 경계 근처에서 삽입/삭제가 교번하는 매 작업마다 O(디렉터리 크기) memcpy가 발생한다. 유휴 레벨 두 개를 요구하고 하나 못 미쳐 멈추는 설계 덕분에 어느 방향으로든 레벨 하나 분량의 변동을 비용 없이 흡수한다. 위반 시 결과: > 0 조건으로 바꾸면 버킷 수가 2의 거듭제곱 근방에서 진동하는 워크로드에서 디렉터리가 memcpy 러닝머신이 된다 — 정확성은 유지되나 처리량이 무너진다.

9.3 `ehash_shrink_directory` — 배열 물리적 반감

ehash_expand_directory(Chapter 7)의 구조적 거울. 배증은 각 구 포인터를 times배 범위로 오른쪽에서 왼쪽으로 펼쳤다. 수축은 목적지가 항상 원본 앞에 오므로 왼쪽에서 오른쪽으로 times번째마다 구 포인터 하나를 샘플링해 압축한다. Figure 9-2가 흐름을 추적하며, 레이블 (A)–(D)는 복사 루프 발췌와 대응한다.

flowchart TD
  A0{"페이지 0 fix 성공?"} -->|아니오| A0r["return (아무것도 고정되지 않음)"]
  A0 -->|예| B{"depth < new_depth?"}
  B -->|예| Babort["WARNING, 페이지 0 unfix, return"]
  B -->|아니오| C["old_ptrs, times, new_ptrs 계산\n페이지 0의 RVEH_REPLACE undo 로그\ndir_header->depth = new_depth"]
  C --> F["루프 i = 1 .. new_ptrs-1"]
  F --> H{"소스 페이지 변경? (A)"}
  H -->|예| H2["구 페이지 unfix, 다음 소스 페이지 fix"]
  H -->|아니오| J
  H2 --> J{"목적 페이지 가득 참? (B)"}
  J -->|예| J2["완성된 목적 페이지 redo, 다음 목적 페이지 fix\nnew_dir_offset = 0, 새 페이지 undo (C)"]
  J -->|아니오| K
  J2 --> K["EHASH_DIR_RECORD 하나 memcpy (D)"]
  K --> F
  F -->|완료| M["마지막 목적 페이지 redo\nfile_numerable_truncate로 new_pages+1까지 자름"]

설정, 조기 반환, 헤더 로깅. 루트 페이지 0을 fix하고, 오래된 요청을 걸러내며, 기하학 값을 계산하고, 페이지 0의 undo 이미지를 로그에 기록한 뒤 새 깊이를 기록한다:

// ehash_shrink_directory -- src/storage/extendible_hash.c
  dir_header_p = (EHASH_DIR_HEADER *) ehash_fix_nth_page (thread_p, &ehid_p->vfid, 0, PGBUF_LATCH_WRITE);
  if (dir_header_p == NULL)
    {
      return;                              /* <- page-0 fix failed; abort shrink, nothing fixed to release */
    }
  if (dir_header_p->depth < new_depth)
    {
      pgbuf_unfix (thread_p, (PAGE_PTR) dir_header_p);
      return;                              /* <- requested depth larger than current; nothing to do */
    }
  old_ptrs = 1 << dir_header_p->depth;
  times = 1 << (dir_header_p->depth - new_depth);   /* <- stride: old slots collapsed into one */
  ret = file_get_num_user_pages (thread_p, &ehid_p->vfid, &old_pages);
  // ... condensed: on error, ASSERT_ERROR + unfix + return ...
  new_ptrs = old_ptrs / times;             /* <- pointer count after the shrink */
  new_dir_page_p = (PAGE_PTR) dir_header_p;   /* <- destination starts ON the header page */
  new_dir_offset = EHASH_DIR_HEADER_SIZE;  /* first pointer sits right after the header */
  if (!is_temp)                            /* <- full-page UNDO of page 0 before any write */
    log_append_undo_data2 (thread_p, RVEH_REPLACE, ... new_dir_page_p ...);
  dir_header_p->depth = new_depth;         /* <- global depth decreases here, under the page-0 X latch */

times = 2^(old_depth - new_depth). 호출자는 항상 new_depth = i + 1을 요청하므로 수축이 실행될 때 times >= 2가 보장된다. 소스와 목적지 커서 모두 페이지 0에서 시작한다 — 생존하는 앞부분 prefix를 같은 배열의 앞쪽으로 덮어쓰는 구조라 첫 페이지에 두 커서가 공존한다. 포인터 0은 결코 이동하지 않으므로 루프는 i = 1에서 시작한다. 루프 진입 전 조기 반환은 정확히 세 가지이며, 반환 시점에 무엇을 잡고 있는지가 각각 다르다: (1) 페이지 0 fix 실패 (ehash_fix_nth_page가 NULL 반환) — 아직 어떤 페이지도 pin되지 않은 상태에서 이루어지는 최초 조기 반환으로, 단순히 return; (2) 오래된 요청 (dir_header_p->depth < new_depth) — 페이지 0이 이미 pin된 상태이므로 pgbuf_unfix로 해제 후 반환; (3) file_get_num_user_pages 오류 — ASSERT_ERROR() 후 페이지 0 unfix 및 반환. 이 세 가지 가드를 통과하면 함수는 복사 루프 실행을 확약한다.

복사 루프 — 모든 분기. 생존하는 포인터 i(1부터 new_ptrs - 1까지)를 순서대로 처리한다:

// ehash_shrink_directory -- src/storage/extendible_hash.c
  for (i = 1; i < new_ptrs; i++)
    {
      old_dir_offset = i * times;                       /* <- sample every times-th old pointer */
      ehash_dir_locate (&old_dir_nth_page, &old_dir_offset);
      if (old_dir_nth_page != prev_pg_no)               /* (A) source crossed a page boundary */
        {
          prev_pg_no = old_dir_nth_page;
          pgbuf_unfix_and_init (thread_p, old_dir_page_p);
          old_dir_page_p = ehash_fix_nth_page (thread_p, &ehid_p->vfid, old_dir_nth_page, PGBUF_LATCH_WRITE);
          // ... condensed: NULL -> set_dirty(new) FREE + return ...
        }
      new_dir_offset += sizeof (EHASH_DIR_RECORD);
      if ((DB_PAGESIZE - new_dir_offset) < SSIZEOF (EHASH_DIR_RECORD))   /* (B) dest page full */
        {
          if (!is_temp)                                 /* finalize filled dest page: full-page REDO */
            log_append_redo_data2 (thread_p, RVEH_REPLACE, ... new_dir_page_p ...);
          pgbuf_set_dirty (thread_p, new_dir_page_p, FREE);
          new_dir_nth_page++;
          new_dir_page_p = ehash_fix_nth_page (thread_p, &ehid_p->vfid, new_dir_nth_page, PGBUF_LATCH_WRITE);
          // ... condensed: NULL -> unfix(old) + return ...
          new_dir_offset = 0;
          if (!is_temp)                                 /* (C) capture this page's pre-image: full-page UNDO */
            log_append_undo_data2 (thread_p, RVEH_REPLACE, ... new_dir_page_p ...);
        }
      memcpy ((char *) new_dir_page_p + new_dir_offset, (char *) old_dir_page_p + old_dir_offset,
              sizeof (EHASH_DIR_RECORD));               /* (D) copy the sampled pointer down */
    }

(A) 소스 페이지 경계 초과. i * times는 플래튼된 포인터 단위로 소스를 인덱싱하며, ehash_dir_locate가 이를 (페이지, 오프셋)으로 변환한다. 페이지가 바뀌면 현재 소스 페이지를 unfix하고 다음 페이지를 fix한다. times >= 2이므로 소스 페이지는 순증가하는 순서로 방문되며, 각 페이지는 한 번씩만 fix된다. fix 실패 시 목적지를 dirty(FREE) 처리하고 반환해 복구가 pre-image로 undo하도록 남긴다.
(B) 목적 페이지 가득 참. 목적지는 반복마다 EHASH_DIR_RECORD 하나씩 늘어난다. 다음 레코드가 들어갈 공간이 없으면 완성된 페이지를 RVEH_REPLACE redo(최종 이미지)로 로깅하고 dirty-FREE 처리한 뒤, 다음 페이지를 new_dir_offset = 0으로 fix한다.
(C) 새 목적 페이지의 undo. 분기 B 내부에서 새 목적 페이지를 fix한 직후, 그 pre-image를 RVEH_REPLACE undo로 로깅한다 — 수정된 페이지당 undo 하나, redo 하나. 수축은 디렉터리의 앞쪽 페이지를 재사용하므로 해당 페이지에는 아직 삭제될 포인터가 남아 있다. pre-image가 있어야 abort 시 더 큰 디렉터리를 복원할 수 있다. (페이지 0의 undo는 루프 전에 이미 기록됐다.)
(D) 복사. 샘플링된 소스 위치에서 압축된 목적지로 EHASH_DIR_RECORD(VPID 하나) 하나를 raw memcpy한다 — 해석 없이 복사한다. 생존하는 슬롯은 이미 올바른 버킷을 가리키고 있기 때문이다. 수축은 어떤 항목이 생존하는지를 바꾸는 것이지, 버킷이 위치하는 곳을 바꾸지 않는다.

루프 종료와 후미 페이지 회수. 마지막으로 부분적으로 채워진 목적 페이지를 redo 로깅하고 flush한 뒤, 뒤에 남은 페이지를 잘라낸다:

// ehash_shrink_directory -- src/storage/extendible_hash.c
  pgbuf_set_dirty (thread_p, new_dir_page_p, FREE);
  new_end_offset = new_ptrs - 1;
  ehash_dir_locate (&new_pages, &new_end_offset);        /* <- page holding the last surviving pointer */
  ret = file_numerable_truncate (thread_p, &ehid_p->vfid, new_pages + 1);   /* <- free trailing pages */
  // ... condensed: on error, ASSERT_ERROR only (best-effort) ...

ehash_dir_locate(new_ptrs - 1)로 new_pages를 구하고, 파일을 new_pages + 1개의 numerable 페이지로 잘라낸다 — 뒤에 남은 모든 구 디렉터리 페이지를 단 한 번의 file_numerable_truncate로 해제한다. 이는 Chapter 8이 버킷 페이지에 사용한 file_dealloc 루프와는 다르다. 잘라내기 오류는 단언(assert)하되 전파하지 않는다. 디렉터리는 이미 논리적으로 올바른 상태이므로 디스크 회수 실패는 최선 노력(best-effort) 정리일 뿐, 트랜잭션 실패가 아니다.

9.4 다음 판단을 위한 히스토그램 일관성 유지

ehash_shrink_directory는 dir_header_p->depth = new_depth를 기록하지만 local_depth_count는 절대 건드리지 않는다 — 이는 올바른 동작이다. 배열을 줄이는 것은 포인터 수를 바꾸는 것이지 각 로컬 깊이에 앉아 있는 버킷 수를 바꾸는 게 아니며, 히스토그램은 이미 병합 후 현실을 반영하고 있다(ehash_adjust_local_depth가 두 호출 경로 모두에서 트리거보다 먼저 실행됐다). 수축 후에도 비零인 가장 높은 레벨은 여전히 i = new_depth - 1이므로, 9.1 불변 조건은 new_depth 자체가 유일한 유휴 헤드룸 레벨인 상태에서 성립한다. 다음 트리거는 new_depth에서 스캔을 시작해 이를 건너뛰고 i = new_depth - 1에 착지하며, new_depth - i == 1(> 1이 아님)을 계산해 수축을 거부한다 — 히스테리시스가 의도하는 안정 상태다. 이후 new_depth까지 다시 분할이 일어나더라도 배증 없이 흡수된다. 히스토그램을 쓰는 것은 ehash_adjust_local_depth뿐이며(Chapter 6, 8), 수축과 배증은 히스토그램의 순수 독자(reader)다. depth 스칼라의 쓰기만이 예외다.

9.5 챕터 요약 — 핵심 정리

히스토그램이 트리거이고, depth가 레버다. ehash_shrink_directory_if_need는 dir_header->depth에서 비零인 최고 레벨 i까지 local_depth_count를 내려가며 스캔한다. dir_header->depth 스칼라를 낮추는 것은 오직 ehash_shrink_directory뿐이다.
유휴 레벨 두 개가 필요하고, 하나를 남긴다. (depth - i) > 1은 수축 전 비어 있는 상위 레벨이 두 개 이상임을 요구하며, 수축 후 i + 1을 목표로 해 유휴 레벨 하나를 남긴다 — grow 트리거에 대한 반진동 히스테리시스. > 0 조건을 쓰면 thrashing이 재발한다.
수축은 구조적 배증을 역으로 실행한다. times = 2^(depth - new_depth), new_ptrs = old_ptrs / times이며, 루프는 왼쪽에서 오른쪽으로 times번째마다 구 포인터를 샘플링해 같은 파일의 앞쪽으로 압축한다 — Chapter 7 팬아웃의 역연산.
수정된 모든 디렉터리 페이지는 RVEH_REPLACE로 pre-image(undo)와 post-image(redo)가 기록된다. 헤더 undo와 depth 쓰기는 루프 전에 처리하며, 후미 페이지는 file_numerable_truncate(new_pages + 1) 한 번으로 회수한다(file_dealloc이 아님). 최선 노력.
수축은 히스토그램을 쓰지 않는다. 포인터 수가 바뀌는 것이지 버킷 로컬 깊이가 바뀌는 게 아니므로, local_depth_count는 이전 병합 델타가 설정한 상태 그대로다 — 다음 판단이 올바른 결과(new_depth - i == 1이므로 거부)를 내리도록 유지된다.
정확성은 9.1 완전성 불변 조건에 달려 있다. 모든 로컬 깊이 변경은 ehash_adjust_local_depth(RVEH_INC_COUNTER 로그)를 통과하므로, 히스토그램은 크래시에도 내구적인 버킷 집계다. 델타 하나가 빠지면 수축이 살아있는 버킷의 로컬 깊이 아래로 depth를 낮춰 조회를 망가뜨린다.

Chapter 10: 엣지 경로 복구와 동시성

이 챕터는 삽입·검색·삭제 생명주기(5~9장) 바깥의 영역 — 크래시 복구와 동시성 제어 — 을 다룬다. 디렉터리 슬롯이 아무 곳도 가리키지 않을 때 무슨 일이 일어나는가, 크래시 이후 구조를 어떻게 재건하는가, 두 트랜잭션이 동시에 같은 해시에 접근하면 무엇이 보장되는가? WAL 이론의 재도출은 생략하고 동반 문서(cubrid-extendible-hash.md의 “Crash Safety” / “Concurrency” 절)의 복구 모델을 그대로 전제한다. RV_fun[] 디스패치 기계 — analysis/redo/undo 패스에서 LOG_RCVINDEX가 undo/redo 함수를 선택하는 방식 — 는 cubrid-recovery-manager-detail.md에서 다루며, 이 챕터는 그 테이블에서 extendible hash에 해당하는 행만 설명한다.

10.1 디렉터리 슬롯이 NULL_VPID일 때 버킷 생성

막 두 배로 늘어난 디렉터리(7장)는 새 슬롯의 대부분을 NULL_VPID로 남긴다. 그 슬롯에 해시되는 첫 삽입은 ehash_insert_helper의 VPID_ISNULL (&bucket_vpid) 분기에 진입한다. S 래치 상태에서는 버킷을 할당할 수 없으므로 래치를 내려놓고 X_LOCK으로 재귀 호출하며, X 래치 상태에서는 ehash_insert_to_bucket_after_create를 호출한다.

// ehash_insert_to_bucket_after_create -- src/storage/extendible_hash.c
found_depth = ehash_find_depth (thread_p, ehid_p, location, &null_vpid, &null_vpid);
if (found_depth == 0) { return ER_FAILED; }          /* <- find_depth signals error with 0 */
init_bucket_data[1] = dir_header_p->depth - found_depth;   /* <- new bucket's local depth */
log_sysop_start (thread_p);                           /* <- atomic allocate+connect+adjust */
error_code = file_alloc (..., ehash_initialize_bucket_new_page, init_bucket_data, bucket_vpid_p, &bucket_page_p);

ehash_find_depth 는 새 버킷의 로컬 depth를 결정한다 — 해당 해시 prefix를 공유하는 연속 슬롯 런을 정확히 커버하는 값이다. location을 기점으로 바깥 방향으로 걸어가며 (check_depth = 2, 2^(check_depth-2)개 sibling 검사), 슬롯이 VPID_ISNULL이거나 VPID_EQ (bucket_vpid_p) 또는 VPID_EQ (sibling_vpid_p)인 경우에만 수락하고 그 외의 경우 루프를 중단해 check_depth - 1을 반환한다. 버킷 생성 경로에서는 두 VPID 인자 모두 &null_vpid이므로 NULL 슬롯만 자격이 있다. 로컬 depth는 dir_header->depth - found_depth로 계산된다 — 빈 런이 깊을수록 슬롯 런이 더 넓다.

file_alloc은 ehash_initialize_bucket_new_page를 실행하며(RVEH_INIT_BUCKET 로그 기록, 10.2), ehash_connect_bucket은 새 VPID를 매칭 슬롯 2^(depth - local_depth)개 전부에 기록하고(7장), ehash_adjust_local_depth(..., +1, ...)로 depth별 카운터를 증가시킨 뒤 system op가 커밋된다. Figure 10-1은 나머지 흐름을 보여 준다: connect 실패 → log_sysop_abort + ER_FAILED; 성공 → log_sysop_commit 후 ehash_insert_to_bucket (별도의 undo 단위).

불변 조건 — 빈 버킷은 첫 키가 들어오기 전에 구조적으로 완전해야 한다. allocate → connect → adjust-depth 세 단계는 레코드 첫 기록 이전에 커밋되는 하나의 system op 안에서 실행된다. 크래시가 발생하면 구조적 op 전체가 롤백되거나(버킷 없음, 슬롯은 여전히 NULL — 다음 삽입이 재생성) 아니면 완전하게 유지된다. 이 순서를 어기면 크래시 후 로컬 depth가 슬롯 런과 맞지 않는 버킷, 또는 참조되지 않는 페이지에 고아 행이 남을 수 있다.

후미의 if (ins_result != EHASH_SUCCESSFUL_COMPLETION) 검사는 있어서는 안 되는 상황에 대한 방어 코드다. 새 페이지의 첫 레코드가 될 만큼 짧은 레코드는 slotted-page 계층에서 거부될 수 없으므로, 거부되면 ER_FATAL_ERROR_SEVERITY로 escalate한다.

flowchart TD
  A["VPID_ISNULL(bucket) under X"] --> B["ehash_find_depth\nlocation, null, null"]
  B -->|returns 0| C["return ER_FAILED"]
  B -->|returns d| D["log_sysop_start"]
  D --> E["file_alloc + init page"]
  E -->|err| F["log_sysop_abort; ER_FAILED"]
  E -->|page NULL| G["assert_release(false); abort; ER_FAILED"]
  E -->|ok| H["ehash_connect_bucket over run"]
  H -->|err| I["unfix; log_sysop_abort; ER_FAILED"]
  H -->|ok| J["adjust_local_depth(+1)"]
  J --> K["log_sysop_commit"]
  K --> L["ehash_insert_to_bucket"]
  L -->|not SUCCESS| M["FATAL er_set; unfix; ER_FAILED"]
  L -->|SUCCESS| N["unfix; NO_ERROR"]

Figure 10-1. ehash_insert_to_bucket_after_create — 모든 분기.

10.2 복구 핸들러 집합: redo/undo 분리

복구 디스패치는 recovery.c의 RV_fun[] 테이블이며, LOG_RCVINDEX를 인덱스로 각 항목을 undo/redo 함수에 바인딩한다. 테이블 워크 자체는 cubrid-recovery-manager-detail.md에서 설명한다. Extendible hash에 해당하는 행은 연속 범위(RVEH_*, recovery.h 기준 인덱스 58~65: RVEH_REPLACE = 58 부터 RVEH_INIT_NEW_DIR_PAGE = 65)로 묶여 있다. 8개 모두 이 모듈 소속이며 — RVEH_REPLACE도 외부 차용이 아니다. split과 directory-double 경로에서 쓰는 전체 페이지 before-image 로거다(10.5).

// RV_fun[] -- src/transaction/recovery.c
{RVEH_REPLACE, "RVEH_REPLACE", log_rv_copy_char, log_rv_copy_char, NULL, NULL},
{RVEH_INSERT, "RVEH_INSERT", ehash_rv_insert_undo, ehash_rv_insert_redo, NULL, NULL},
{RVEH_DELETE, "RVEH_DELETE", ehash_rv_delete_undo, ehash_rv_delete_redo, NULL, NULL},
/* ... RVEH_INIT_BUCKET, RVEH_CONNECT_BUCKET, RVEH_INC_COUNTER, RVEH_INIT_DIR, RVEH_INIT_NEW_DIR_PAGE ... */

인덱스	Undo 핸들러	Redo 핸들러	Undo 방식
`RVEH_REPLACE` (58)	`log_rv_copy_char`	`log_rv_copy_char`	물리적 — sysop abort 시 전체 페이지 before-image 복원
`RVEH_INSERT` (59)	`ehash_rv_insert_undo`	`ehash_rv_insert_redo`	논리적 — “이 키를 삭제”
`RVEH_DELETE` (60)	`ehash_rv_delete_undo`	`ehash_rv_delete_redo`	논리적 — “이 키를 재삽입”
`RVEH_INIT_BUCKET` (61)	`pgbuf_rv_new_page_undo`	`ehash_rv_init_bucket_redo`	물리적 — undo 시 페이지 해제
`RVEH_CONNECT_BUCKET` (62)	`log_rv_copy_char`	`ehash_rv_connect_bucket_redo`	물리적 — undo 시 before-image 복원
`RVEH_INC_COUNTER` (63)	`ehash_rv_increment`	`ehash_rv_increment`	물리적 — 대칭적인 +/- 델타
`RVEH_INIT_DIR` (64)	NULL	`ehash_rv_init_dir_redo`	redo 전용 (커밋된 create)
`RVEH_INIT_NEW_DIR_PAGE` (65)	`pgbuf_rv_new_page_undo`	`ehash_rv_init_dir_new_page_redo`	물리적 — undo 시 페이지 해제

이 분리가 필요한 이유. 단일 키 insert/delete는 논리적이다. undo 시점에 동시 split이 레코드를 다른 버킷으로 이동시킬 수 있으므로, “페이지 P의 슬롯 N을 바이트 단위로 복원”하는 방식은 틀릴 수 있다. 논리적 undo는 디렉터리(ehash_find_bucket_vpid_with_hash)를 다시 탐색해 현재 버킷에 작용한다. connect/counter와 RVEH_REPLACE는 물리적이다: 커밋(undo 없음)되거나 abort(정확한 바이트 이미지 복원, 이동 불가)되는 log_sysop 안에서 실행된다. RVEH_REPLACE는 델타가 아닌 전체 DB_PAGESIZE 이미지를 담는 유일한 항목으로 — split이 페이지의 임의 부분을 재기록하는 곳에서 사용된다(10.5).

ehash_rv_insert_undo 는 얇은 어댑터다. EHID와 키를 읽고(record_p += sizeof (OID)로 assoc-value OID를 건너뛴다. REC_BIGONE 분기는 컴파일 제외, 10.6) return ehash_rv_delete (...)를 호출하여 merge 로직을 우회한다. ehash_rv_delete_undo 는 대칭이다. EHID와 value OID를 읽은 뒤 ehash_insert_helper (..., S_LOCK, NULL)로 재삽입하며 — 이 과정에서 split이 발생할 수도 있다 — 실패 시 assert (er_errid () != NO_ERROR)로 검증한다.

ehash_rv_delete 는 insert-undo가 공유하는 CLR(Compensation Log Record) 스타일 핵심 함수다. 자체 undo 없이 보상 redo(RVEH_DELETE)만 기록하므로, 복구 도중 두 번째 크래시가 발생해도 전진 재생(forward replay)만 일어나고 후퇴는 없다. ehash_find_bucket_vpid_with_hash (... PGBUF_LATCH_READ, PGBUF_LATCH_WRITE, ...)(디렉터리 root READ, 버킷 WRITE)로 재탐색하며, 뮤테이션 전에 네 가지 조건 — NULL 디렉터리 root, NULL_PAGEID 버킷 VPID, NULL 버킷 페이지, ehash_locate_slot 미스 — 이 감지되면 고정한 것을 모두 해제하고 er_errid ()나 ER_EH_UNKNOWN_KEY를 반환한다. 살아남은 경로에서 삭제를 수행한다:

// ehash_rv_delete -- src/storage/extendible_hash.c
log_append_redo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, bucket_page_p, slot_no, ...);  /* <- compensating redo */
(void) spage_delete (thread_p, bucket_page_p, slot_no); pgbuf_set_dirty (...);
/* Do NOT remove overflow pages here -- their own undo functions handle that */

redo 이미지를 위한 ehash_allocate_recdes가 실패하면 ER_OUT_OF_VIRTUAL_MEMORY를 설정하지만 삭제는 그대로 진행한다. 복구 중에는 로그 추가가 best-effort이며 undo의 효과를 포기해서는 안 되기 때문이다.

Redo 핸들러는 페이지 로컬 replay다. ehash_rv_init_bucket_redo 는 2바이트 {alignment, local_depth} 페이로드로 빈 버킷을 재구성한다. PAGE_EHASH 설정, UNANCHORED_KEEP_SEQUENCE로 spage_initialize, EHASH_BUCKET_HEADER를 슬롯 0에 spage_insert — SP_SUCCESS가 아닌 반환값은 이미 SP_ERROR가 아닌 한 FATAL이며 어느 경우든 er_errid ()를 반환한다. ehash_rv_connect_bucket_redo 는 멱등(idempotent)하게 replay한다. EHASH_REPETITION {vpid, count}(7장)를 읽고 count개의 EHASH_DIR_RECORD를 순회하며, 실제로 달라질 때(!VPID_EQ (...))만 repetition.vpid를 기록하고 dirty를 표시한다. ehash_rv_increment 는 undo와 redo 양쪽에 모두 쓰인다(부호 있는 델타; undo에는 부정값이 전달된다). 두 디렉터리 redo 핸들러는 버킷 초기화 핸들러와 대칭되지 않는다. ehash_rv_init_dir_redo는 페이지 타입을 설정한 뒤 log_rv_copy_char로 로그된 바이트 이미지를 replay하고, ehash_rv_init_dir_new_page_redo는 PAGE_EHASH를 찍고 dirty로 표시하기만 한다. 둘 다 spage_initialize를 실행하지 않는다. RVEH_INIT_DIR의 undo가 NULL인 것은 디렉터리 생성이 커밋된 xehash_create system op 안에서 실행되기 때문이다.

10.3 전체 스캔 반복자: ehash_map과 ehash_apply_each

ehash_map은 모든 항목을 방문하는 유일한 공개 인터페이스다. 디렉터리를 우회해 버킷 파일을 페이지 단위로 순회한다. 버킷 하나는 여러 슬롯에서 도달 가능하므로, 디렉터리 기반 워크는 중복 방문이 생긴다.

// ehash_map -- src/storage/extendible_hash.c
if (ehid_p == NULL) { return ER_FAILED; }                         /* <- nothing fixed yet */
dir_page_p = ehash_fix_ehid_page (..., PGBUF_LATCH_READ);
if (file_get_num_user_pages (..., &num_pages) != NO_ERROR)
  { return ER_FAILED; }                                           /* <- dir_page_p NOT unfixed: a leak */
for (bucket_page_no = 0; apply_error_code == NO_ERROR && bucket_page_no < num_pages; bucket_page_no++) {
    bucket_page_p = ehash_fix_nth_page (..., PGBUF_LATCH_READ);
    if (bucket_page_p == NULL) { pgbuf_unfix_and_init (..., dir_page_p); return ER_FAILED; }
    for (slot_id = first_slot_id + 1; ...; slot_id++)             /* <- slot 0 is the header; skip */
        if (ehash_apply_each (..., &apply_error_code, ...) != NO_ERROR)
          { ...unfix bucket + dir; return ER_FAILED; }
    pgbuf_unfix_and_init (thread_p, bucket_page_p); }

디렉터리는 전체 순회 동안 PGBUF_LATCH_READ 상태를 유지한다. 종료 경로는 균일하지 않다. (a) NULL ehid_p → ER_FAILED, 아무것도 고정되지 않음; (b) file_get_num_user_pages 실패 → dir_page_p를 unfix하지 않은 채 ER_FAILED — 이 경로를 강화할 때 주목해야 할 실제 페이지 leak; (c) ehash_fix_nth_page 실패와 (d) ehash_apply_each 오류는 둘 다 버킷 + 디렉터리를 unfix한 뒤 ER_FAILED; (e) 소프트 콜백 중단 — 콜백이 apply_error_code를 설정하면 for 가드(apply_error_code == NO_ERROR)가 스캔을 중단하고, 정상적인 디렉터리 unfix 후 해당 코드를 반환한다. ehash_apply_each는 먼저 타입별 키를 재구성한다. DB_TYPE_STRING은 복사본을 malloc 후 해제하고, DB_TYPE_OBJECT는 스택의 next_key에 복사하며, 수치형 분기는 컴파일 제외되고, default는 ER_EH_ROOT_CORRUPTED를 발생시킨다. ehash_dump/ehash_dump_bucket은 디버그 전용 출력 함수다.

10.4 임시 파일: 로깅 억제와 전용 소멸자

모든 구조적 함수는 is_temp 플래그(file_is_temp로 조회)를 받는다. 이 플래그가 설정되면 log_sysop_start/log_append_* 호출 전체를 건너뛴다 — sort/hash-join 임시 해시 테이블은 복구 대상이 아니다. 6장의 ehash_extend_bucket이 이 패턴을 보여 주며(if (!is_temp) log_sysop_start (...)), ehash_connect_bucket도 log_append_undoredo_data2를 같은 방식으로 보호한다.

xehash_destroy는 임시 파일만 처리한다. system op 앞에 두 가지 검사가 있다. NULL ehid_p이면 ER_FAILED를 반환하고, 디렉터리 root의 ehash_fix_ehid_page (... PGBUF_LATCH_WRITE) 실패 시에도 log_sysop_start 이전에 ER_FAILED를 반환한다. 이 검사를 통과하면 하나의 log_sysop_start/log_sysop_commit 쌍 안에서 file_destroy를 두 번 호출한다 — 먼저 버킷 파일을 해제하고, 이어서 디렉터리 root를 pgbuf_unfix한 뒤, 마지막으로 ehid_p->vfid를 해제한다(is_temp = true). 각 호출은 if (... != NO_ERROR) { assert_release (false); }로 보호된다. 임시 파일 해제는 실패하지 않아야 하므로, 실패는 로직 버그다. 영구 파일 소멸자는 존재하지 않는다. 영구 해시(유일한 영구 사용자: 클래스명 → OID 카탈로그)는 데이터베이스 수명 동안 존재하며 일반적인 파일 매니저 정리로 회수된다.

10.5 동시성: 페이지 래치, split/double 래치 순서, 두 번 강하 업그레이드

Extendible hashing 내부에는 키·행 수준의 잠금이 없다. 유일한 동기화 수단은 페이지 래치(PGBUF_LATCH_READ = 공유, PGBUF_LATCH_WRITE = 독점)다. 설계의 근거는 하나다. 디렉터리는 한 단계 깊이 — 트리가 아닌 평탄한 배열 — 이므로 디렉터리 레벨 간 래치 커플링이 없다. 읽기 측은 root를 S-latch, 슬롯을 해석하고, 버킷을 latch하면 끝이다.

래치 순서 불변 조건. 모든 변경 경로는 페이지를 같은 중첩 순서로 고정하고 안쪽부터 해제하므로, 두 개의 동시 split은 절대 교착 상태에 빠지지 않는다. ehash_insert_helper → ehash_insert_bucket_after_extend_if_need → ehash_extend_bucket → ehash_split_bucket/ehash_expand_directory 경로를 따라가면 고정 순서는 다음과 같다.

디렉터리 root — ehash_find_bucket_vpid_with_hash가 가장 먼저 고정한다(X 패스에서는 PGBUF_LATCH_WRITE, S 패스에서는 PGBUF_LATCH_READ). ehash_insert_helper가 끝날 때까지 계속 유지된다.
대상 버킷 — ehash_insert_bucket_after_extend_if_need가 PGBUF_LATCH_WRITE로 고정한다.
sibling 버킷 — ehash_split_bucket이 원본 버킷을 고정한 상태에서 새 sibling을 WRITE로 할당·고정한다.
directory-double 페이지 (new_local_depth > dir_header_p->depth인 경우에만) — ehash_expand_directory가 디렉터리 헤더를 PGBUF_LATCH_WRITE로 재고정하고, 이후 이전·새 디렉터리 데이터 페이지를 WRITE로 고정하되 마지막 페이지부터 역순으로(old_dir_nth_page = old_pages, 루프 감소) 처리한다.

// ehash_insert_bucket_after_extend_if_need -- src/storage/extendible_hash.c
bucket_page_p = ehash_fix_old_page (..., bucket_vpid_p, PGBUF_LATCH_WRITE);   /* <- step 2: bucket X */
...
sibling_page_p = ehash_extend_bucket (...);   /* <- step 3-4: sibling + dir-double, all X */

잠금 그래프는 단일 디렉터리 root를 루트로 하는 엄격한 트리 구조다: dir root → bucket → sibling, 또한 dir root → expand pages. 어떤 스레드도 root를 기다리는 동안 버킷을 붙잡고 있지 않다. root는 항상 먼저 획득되며, 버킷을 고정한 뒤 다시 획득하는 일은 없다. 이 전체 순서가 교착 상태가 없음을 보장하는 논거다.

불변 조건 — 구조 변경 삽입은 디렉터리 슬롯을 건드리기 전에 X 래치로 디렉터리 root를 고정하고, 버킷·sibling 래치 전반에 걸쳐 그 상태를 유지한다. S 패스는 절대 변경하지 않는다. ehash_insert_bucket_after_extend_if_need는 ehash_extend_bucket을 호출하기 전에 if (lock_type == S_LOCK) return EHASH_BUCKET_FULL;을 확인한다. 비용은 두 번 강하 패널티 — split을 유발하는 삽입은 디렉터리를 두 번 읽어야 한다. 반면 이득은, 일반적인 경우(버킷에 여유가 있음)가 공유 root 래치 하에서 완료되므로 읽기 측과 비-split 쓰기 측이 root에서 직렬화되지 않아도 된다는 점이다.

삽입은 낙관적 S-then-X 전략을 사용한다. 첫 번째 강하(ehash_insert_helper, lock_type == S_LOCK)는 버킷에 여유가 있기를 기대하며 root를 S-latch한다. 세 가지 상황이 X로의 재시작을 강제한다.

슬롯이 NULL_VPID여서 버킷을 생성해야 하는 경우 (10.1).
버킷이 가득 차 split이 필요한 경우 — ehash_insert_bucket_after_extend_if_need가 S 상태에서 EHASH_BUCKET_FULL을 반환.
(컴파일 제외) 긴 문자열이 overflow 파일을 필요로 하는 경우.

각 경우에 핸들러는 unfix 후 tail-recurse한다.

// ehash_insert_helper -- src/storage/extendible_hash.c
if (VPID_ISNULL (&bucket_vpid)) {
    if (lock_type == S_LOCK) { pgbuf_unfix_and_init (...); return ehash_insert_helper (..., X_LOCK, ...); }  /* <- drop S, redescend */
    else { ...ehash_insert_to_bucket_after_create (...); } }       /* <- under X: create */
else { result = ehash_insert_bucket_after_extend_if_need (...);
       if (result == EHASH_BUCKET_FULL)
         { pgbuf_unfix_and_init (...); return ehash_insert_helper (..., X_LOCK, ...); } }   /* <- redescend to split */

이로 인해 동시 split 윈도우가 열린다(동반 문서의 미해결 과제 3). S-unfix와 X-fix 사이에 다른 스레드가 같은 버킷을 split할 수 있다. 재강하는 ehash_find_bucket_vpid_with_hash에서 다시 시작하며 dir_header_p->depth를 새로 읽고 지금 달라진 버킷을 재탐색한다. 경쟁 split이 이미 여유를 만들었다면 EHASH_BUCKET_FULL 분기는 취해지지 않고 두 번째 split 없이 삽입이 성공한다. 재시도마다 최신 depth로 root에서 다시 시작하기 때문에 이 보장이 성립한다.

stateDiagram-v2
  [*] --> S_descent: 키 삽입
  S_descent --> Done: 버킷에 여유 있음
  S_descent --> Restart_X: 슬롯 NULL 또는 BUCKET_FULL
  Restart_X --> X_descent: root를 X로 재고정
  X_descent --> Done: 경쟁 split이 여유 생성
  X_descent --> Mutate: X 래치 하에서 create 또는 split
  Mutate --> Done: 레코드 삽입 완료

Figure 10-2. 낙관적 S-then-X 삽입 래칭.

flowchart TD
  R["directory root\nLATCH_WRITE, held to end"] --> B["target bucket\nLATCH_WRITE"]
  B --> S["sibling bucket\nLATCH_WRITE"]
  R --> H["dir header re-fix\nLATCH_WRITE"]
  H --> O["old/new dir pages\nLATCH_WRITE, last page backward"]

Figure 10-3. Split/double 래치 중첩 — 단일 디렉터리 root를 루트로 하는 트리; unfix는 안쪽부터, root가 마지막.

10.6 dead code: ENABLE_UNUSED_FUNCTION 경로

모듈의 상당 부분이 #if defined (ENABLE_UNUSED_FUNCTION) 뒤에 숨어 있으며 빌드되지 않는다 — 모든 SQL 스칼라 타입과 임의 길이 키를 지원하려 했던 범용 extendible hash의 잔재다. 현재 라이브 코드는 DB_TYPE_STRING(클래스명, ehash_insert_helper의 assert (strlen ((char *) key_p) < 256)으로 255바이트 제한)과 DB_TYPE_OBJECT(OID)만 지원한다. 죽은 코드 중 주목할 것이 둘 있다. 긴 문자열 overflow 파일 — ehash_create_overflow_file, ehash_compose_overflow, 그리고 두 undo 핸들러와 ehash_apply_each의 REC_BIGONE 분기(256바이트 미만 키는 항상 REC_HOME 하나에 들어가므로 overflow_file은 사실상 항상 NULL); 수치형 키 타입 — switch (key_type)의 DB_TYPE_INTEGER … MONETARY 분기. assertion과 default의 ER_EH_ROOT_CORRUPTED(10.3)가 이 경로를 막아 놓으므로, 문자열이나 OID가 아닌 키는 오류로 처리되며 잘못된 해시가 조용히 발생하지 않는다.

10.7 챕터 요약 — 핵심 정리

NULL 슬롯 생성은 하나의 원자적 구조 op — ehash_insert_to_bucket_after_create는 ehash_find_depth로 depth를 결정한 뒤, 레코드 기록 이전에 커밋되는 하나의 log_sysop 안에서 allocate → connect → adjust-depth를 수행한다.
8개의 RVEH_ 인덱스, 모두 이 모듈 소속* — RVEH_REPLACE (58) 포함(split과 directory-double이 기록하는 전체 페이지 before-image 로거). 복구는 undo 방식으로 분기된다 — 단일 키 insert/delete는 논리적, RVEH_REPLACE/split/connect/counter는 system op 안의 물리적.
ehash_rv_delete는 CLR — 보상 RVEH_DELETE redo만 기록하고 자체 undo는 없으므로, 복구 도중 두 번째 크래시가 발생해도 전진 재생만 일어난다.
Redo 핸들러는 멱등한 페이지 로컬 replay — *_init_dir_*_redo 두 핸들러는 페이지 타입 설정 또는 이미지 복사만 하는 반면, ehash_rv_init_bucket_redo는 spage_initialize를 재실행한다.
ehash_map은 디렉터리가 아닌 버킷 파일을 순회 — file_get_num_user_pages 실패 시 dir 페이지를 leak하는 반면, 나머지 오류 경로는 정상적으로 unfix한다는 점과 소프트 콜백 중단 동작에 주의.
임시 테이블은 로깅을 억제하고 유일한 소멸자를 보유 — is_temp가 모든 log_*를 제어하며, xehash_destroy(두 pre-sysop 검사 이후)는 임시 파일만 해체한다. 영구 해시에는 소멸자가 없다.
동시성은 전체 순서 위의 페이지 래치 전용 — 평탄한 디렉터리는 래치 커플링이 필요 없다. split은 단일 root를 루트로 하는 트리 구조로 dir root → bucket → sibling(+ directory-double 페이지)를 고정하며, 변경 삽입은 최신 depth를 읽으며 X로 재강하한다.

이 리비전 시점의 위치 힌트

아래 줄 번호는 2026-06-23 시점에 관찰한 값이다. 심볼 이름이 정식 앵커이며 줄 번호는 시간이 지나면 어긋나는 힌트다.

Symbol	File	Line
`mht_1strhash`	`src/base/memory_hash.c`	449
`mht_2strhash`	`src/base/memory_hash.c`	468
`mht_3strhash`	`src/base/memory_hash.c`	485
`vpid`	`src/compat/dbtype_def.h`	889
`vfid`	`src/compat/dbtype_def.h`	896
`EHASH_OVERFLOW_RATE`	`src/storage/extendible_hash.c`	69
`EHASH_UNDERFLOW_RATE`	`src/storage/extendible_hash.c`	81
`EHASH_OVERFLOW_THRESHOLD`	`src/storage/extendible_hash.c`	90
`EHASH_UNDERFLOW_THRESHOLD`	`src/storage/extendible_hash.c`	91
`EHASH_HASH_KEY_BITS`	`src/storage/extendible_hash.c`	94
`EHASH_HASH_KEY`	`src/storage/extendible_hash.c`	99
`ehash_dir_header`	`src/storage/extendible_hash.c`	103
`EHASH_DIR_HEADER`	`src/storage/extendible_hash.c`	103
`local_depth_count`	`src/storage/extendible_hash.c`	111
`EHASH_DIR_RECORD`	`src/storage/extendible_hash.c`	119
`ehash_dir_record`	`src/storage/extendible_hash.c`	120
`EHASH_DIR_RECORD`	`src/storage/extendible_hash.c`	120
`ehash_bucket_header`	`src/storage/extendible_hash.c`	127
`EHASH_BUCKET_HEADER`	`src/storage/extendible_hash.c`	127
`EHASH_RESULT`	`src/storage/extendible_hash.c`	132
`EHASH_SUCCESSFUL_COMPLETION`	`src/storage/extendible_hash.c`	134
`EHASH_FULL_SIBLING_BUCKET`	`src/storage/extendible_hash.c`	138
`EHASH_NO_SIBLING_BUCKET`	`src/storage/extendible_hash.c`	139
`EHASH_REPETITION`	`src/storage/extendible_hash.c`	144
`ehash_repetition`	`src/storage/extendible_hash.c`	145
`EHASH_DIR_HEADER_SIZE`	`src/storage/extendible_hash.c`	156
`EHASH_MAX_STRING_SIZE`	`src/storage/extendible_hash.c`	160
`EHASH_NUM_FIRST_PAGES`	`src/storage/extendible_hash.c`	164
`EHASH_LAST_OFFSET_IN_FIRST_PAGE`	`src/storage/extendible_hash.c`	168
`EHASH_NUM_NON_FIRST_PAGES`	`src/storage/extendible_hash.c`	172
`EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE`	`src/storage/extendible_hash.c`	176
`GETBITS`	`src/storage/extendible_hash.c`	193
`FIND_OFFSET`	`src/storage/extendible_hash.c`	209
`GETBIT`	`src/storage/extendible_hash.c`	223
`SETBIT`	`src/storage/extendible_hash.c`	236
`CLEARBIT`	`src/storage/extendible_hash.c`	249
`ehash_dir_locate`	`src/storage/extendible_hash.c`	384
`ehash_allocate_recdes`	`src/storage/extendible_hash.c`	475
`ehash_free_recdes`	`src/storage/extendible_hash.c`	499
`ehash_initialize_bucket_new_page`	`src/storage/extendible_hash.c`	628
`UNANCHORED_KEEP_SEQUENCE`	`src/storage/extendible_hash.c`	661
`ehash_initialize_dir_new_page`	`src/storage/extendible_hash.c`	711
`ehash_initialize_dir_new_page`	`src/storage/extendible_hash.c`	712
`ehash_rv_init_dir_new_page_redo`	`src/storage/extendible_hash.c`	735
`xehash_create`	`src/storage/extendible_hash.c`	866
`ehash_get_key_size`	`src/storage/extendible_hash.c`	879
`ehash_create_helper`	`src/storage/extendible_hash.c`	954
`ehash_fix_old_page`	`src/storage/extendible_hash.c`	1188
`ehash_fix_ehid_page`	`src/storage/extendible_hash.c`	1218
`ehash_fix_nth_page`	`src/storage/extendible_hash.c`	1236
`xehash_destroy`	`src/storage/extendible_hash.c`	1259
`ehash_find_bucket_vpid`	`src/storage/extendible_hash.c`	1295
`ehash_find_bucket_vpid_with_hash`	`src/storage/extendible_hash.c`	1326
`ehash_find_bucket_vpid_with_hash`	`src/storage/extendible_hash.c`	1327
`ehash_search`	`src/storage/extendible_hash.c`	1379
`ehash_insert`	`src/storage/extendible_hash.c`	1461
`ehash_insert_to_bucket_after_create`	`src/storage/extendible_hash.c`	1472
`ehash_extend_bucket`	`src/storage/extendible_hash.c`	1545
`ehash_extend_bucket`	`src/storage/extendible_hash.c`	1546
`ehash_insert_bucket_after_extend_if_need`	`src/storage/extendible_hash.c`	1640
`ehash_insert_bucket_after_extend_if_need`	`src/storage/extendible_hash.c`	1641
`ehash_insert_helper`	`src/storage/extendible_hash.c`	1715
`ehash_insert_to_bucket`	`src/storage/extendible_hash.c`	1837
`ehash_write_key_to_record`	`src/storage/extendible_hash.c`	2067
`ehash_compose_record`	`src/storage/extendible_hash.c`	2172
`ehash_compare_key`	`src/storage/extendible_hash.c`	2223
`ehash_binary_search_bucket`	`src/storage/extendible_hash.c`	2401
`ehash_locate_slot`	`src/storage/extendible_hash.c`	2479
`ehash_get_pseudo_key`	`src/storage/extendible_hash.c`	2509
`ehash_find_first_bit_position`	`src/storage/extendible_hash.c`	2545
`ehash_distribute_records_into_two_bucket`	`src/storage/extendible_hash.c`	2604
`ehash_split_bucket`	`src/storage/extendible_hash.c`	2684
`ehash_expand_directory`	`src/storage/extendible_hash.c`	2792
`ehash_connect_bucket`	`src/storage/extendible_hash.c`	3067
`ehash_find_depth`	`src/storage/extendible_hash.c`	3183
`ehash_check_merge_possible`	`src/storage/extendible_hash.c`	3274
`ehash_delete`	`src/storage/extendible_hash.c`	3418
`RVEH_DELETE`	`src/storage/extendible_hash.c`	3572
`ehash_shrink_directory_if_need`	`src/storage/extendible_hash.c`	3615
`ehash_adjust_local_depth`	`src/storage/extendible_hash.c`	3633
`ehash_merge_permanent`	`src/storage/extendible_hash.c`	3655
`ehash_merge`	`src/storage/extendible_hash.c`	3771
`ehash_shrink_directory`	`src/storage/extendible_hash.c`	3982
`file_numerable_truncate`	`src/storage/extendible_hash.c`	4148
`ehash_hash_string_type`	`src/storage/extendible_hash.c`	4156
`ehash_hash_eight_bytes_type`	`src/storage/extendible_hash.c`	4244
`ehash_hash`	`src/storage/extendible_hash.c`	4347
`ehash_apply_each`	`src/storage/extendible_hash.c`	4395
`ehash_map`	`src/storage/extendible_hash.c`	4518
`ehash_dump`	`src/storage/extendible_hash.c`	4598
`ehash_rv_init_bucket_redo`	`src/storage/extendible_hash.c`	5023
`ehash_rv_init_dir_redo`	`src/storage/extendible_hash.c`	5072
`ehash_rv_insert_redo`	`src/storage/extendible_hash.c`	5089
`ehash_rv_insert_undo`	`src/storage/extendible_hash.c`	5126
`ehash_rv_delete_redo`	`src/storage/extendible_hash.c`	5181
`ehash_rv_delete_undo`	`src/storage/extendible_hash.c`	5220
`ehash_rv_delete`	`src/storage/extendible_hash.c`	5293
`ehash_rv_increment`	`src/storage/extendible_hash.c`	5405
`ehash_rv_connect_bucket_redo`	`src/storage/extendible_hash.c`	5429
`ehash_read_oid_from_record`	`src/storage/extendible_hash.c`	5456
`ehash_write_oid_to_record`	`src/storage/extendible_hash.c`	5471
`ehash_write_ehid_to_record`	`src/storage/extendible_hash.c`	5501
`file_create_ehash`	`src/storage/file_manager.c`	3261
`file_create_ehash_dir`	`src/storage/file_manager.c`	3285
`file_create`	`src/storage/file_manager.c`	3311
`file_ehash_des`	`src/storage/file_manager.h`	114
`ehid`	`src/storage/storage_common.h`	213
`EH_SEARCH`	`src/storage/storage_common.h`	386
`RV_fun`	`src/transaction/recovery.c`	407
`RVEH_REPLACE`	`src/transaction/recovery.h`	105
`RVEH_INSERT`	`src/transaction/recovery.h`	106
`RVEH_DELETE`	`src/transaction/recovery.h`	107
`RVEH_INIT_BUCKET`	`src/transaction/recovery.h`	108
`RVEH_CONNECT_BUCKET`	`src/transaction/recovery.h`	109
`RVEH_INC_COUNTER`	`src/transaction/recovery.h`	110
`RVEH_INIT_DIR`	`src/transaction/recovery.h`	111
`RVEH_INIT_NEW_DIR_PAGE`	`src/transaction/recovery.h`	112

출처

cubrid-extendible-hash.md — 상위 수준 동반 문서. ehash 파일이 사용하는 numerable 파일 타입에 대해서는 cubrid-disk-manager-detail.md도 함께 참고한다.
코드: src/storage/extendible_hash.{c,h}.
방법론: knowledge/methodology/code-analysis-detail-doc.md.