(KO) CUBRID Extendible Hash — 디렉토리 더블링과 local depth 로 동적으로 자라는 디스크 상주 해시 파일

학술적 배경
DBMS 공통 설계 패턴
CUBRID의 구현
소스 코드 가이드
소스 검증 (2026-04-30 기준)
CUBRID 너머 — 비교 설계와 연구 동향
출처

학술적 배경

Extendible hashing 은 Fagin, Nievergelt, Pippenger, Strong 가 Extendible Hashing — A Fast Access Method for Dynamic Files (TODS 1979) 에서 제안한 디스크 친화적 해시 파일 기법이다. 이 기법이 다루는 질문은 B+Tree 가 깔끔히 풀어 주지 않는 한 가지였다 — 해시 파일은 어떻게 자라는가. 메모리 안에서는 답이 단순하다. 더 큰 배열을 새로 잡고 모든 엔트리를 다시 해시하면 끝난다. 디스 크에서는 그 답이 통하지 않는다. 버킷 하나가 페이지 하나이고, 다 시 해시할 때마다 파일 전체를 한 번 훑어야 하기 때문이다. Litwin (1980) 의 linear hashing 이 한 가지 답을 내놨다 — 어떤 버킷이 넘쳤는지와 무관하게, 미리 정해진 round-robin 순서로 한 번에 한 버킷씩 split 한다. extendible hashing 은 다른 답을 내놨다 — 넘친 그 버킷만 split 하고, 디렉토리는 주소 깊이를 다 써 버린 경우에만 두 배로 늘린다.

자료 구조의 골격은 Database Internals (Petrov) 7장 §“Hash Files” 에 잘 정리되어 있다. 사용자 키에 균일한 해시 함수를 적용 해 고정 폭 정수 (실무에서는 32비트) 의 의사 키 (pseudo-key) 를 뽑는다. 디렉토리 는 이 의사 키의 왼쪽 N 비트 로 색인되는 포인터 배열이고, 여기서 N 은 디렉토리의 전역 깊이 (global depth, d) 다. 디렉토리는 2^d 개의 엔트리를 들고 있다. 각 엔 트리는 페이지 한 장짜리 버킷 을 가리키며, 버킷은 (key, value) 레코드 한 개 이상을 담는다.

각 버킷은 자기만의 지역 깊이 (local depth, d_b) 를 들고 있 다. 그 버킷이 지금까지 왼쪽에서 몇 비트로 구별되어 왔는가 를 나타내는 값이다. 유지되는 불변식 세 가지는 다음과 같다.

모든 버킷을 d_b ≤ d.
d_b < d 이면, 2^(d - d_b) 개의 디렉토리 엔트리가 같은 버 킷을 가리킨다 — 그 버킷은 공유 (shared) 상태다.
d_b = d 이면, 정확히 하나의 디렉토리 엔트리만 그 버킷을 가 리킨다.

insert 가 대상 버킷이 가득 찼다는 사실을 발견했을 때의 분기는 이렇게 갈린다.

d_b < d (공유 버킷) 일 때. sibling 버킷을 새로 하나 잡 고, 레코드를 d_b + 1 번째 비트로 두 버킷에 다시 나눠 담고, 두 버킷의 local depth 를 d_b + 1 로 올린다. 그리고 원래 버 킷을 가리키던 디렉토리 엔트리의 절반을 sibling 으로 다시 연결 한다. 디렉토리 자체의 크기는 그대로다.
d_b = d 일 때. 주소 공간이 바닥났다. 디렉토리를 두 배로 늘린다 (d := d + 1, 옛 포인터를 새 디렉토리에 두 번씩 복사). 그 다음 위의 첫 번째 케이스를 적용한다.

삭제는 그 거꾸로다. 버킷이 underflow 임계 아래로 떨어지고 sibling 이 같은 local depth 이며 두 버킷이 합쳐서 한 페이지에 들어가면, merge 하고 local depth 를 1 줄인다. merge 후 어느 버 킷도 local depth 가 d 가 아니게 되면 디렉토리를 절반으로 줄 인다.

이 설계가 매력적인 이유는 두 가지다.

상수 시간 lookup. 의사 키 한 번이면 디렉토리 엔트리가 정 해지고, 버킷 read 한 번이면 값이 돌아온다. 트리 descent 도 없 고, log-N 비교도 없다.
성장에 rehash 가 없다. 디렉토리 더블링은 O(2^d) 포인터 복사이고, 버킷 split 은 정확히 두 페이지만 건드린다. 다른 버 킷은 손대지 않는다.

대신 비용도 분명하다. 두 단계의 간접 참조 (디렉토리 페이지 + 버 킷 페이지, 즉 lookup 당 두 번의 buffer fix) 가 첫째다. 메모리 안에서 hash-of-hash 로 한 페이지 안에서 끝나는 것과 비교하면 두 번 fix 한다. 디렉토리 크기가 둘째다. 해시 함수가 한쪽으로 몰려 있으면 2^d 포인터 배열이 부풀 수 있다. 이 기법을 쓰는 엔진은 디렉토리를 처음부터 넉넉히 잡거나, 가끔의 더블링 비용을 그냥 받 아들이는 식으로 이 비용을 다룬다.

CUBRID 의 구현은 Fagin 의 도식을 거의 글자 그대로 받아들였다. EHID 가 디렉토리 파일을 가리키고, 슬롯 페이지 형식의 버킷 페 이지에 작은 EHASH_BUCKET_HEADER 가 local depth 를 싣는다. ehash_hash 가 32비트 의사 키를 만들고, split / merge 의 분기 는 local-depth / global-depth 비교에 따른다. CUBRID 특유의 디테 일은 그 가장자리에 있다 — RVEH_* 레코드를 통한 WAL 통합, split / merge 를 둘러싸는 system-op 괄호, 버킷 안에서 도는 슬 롯-페이지 스타일의 binary search, 그리고 현재 빌드가 실제로 허 용하는 좁은 키 타입 집합 (DB_TYPE_STRING, DB_TYPE_OBJECT).

DBMS 공통 설계 패턴

디스크 상주 해시 파일은 여러 엔진에 등장한다. 골격은 비슷하고, 차이는 WAL 통합, 키 타입의 유연성, 그리고 해시 파일을 어디에 쓰는가 에 있다.

Extendible hashing 이 보통 등장하는 자리

PostgreSQL hash 인덱스. 사용자 테이블에 대한 extendible hashing 이다. PG 9.6 까지는 WAL 이 찍히지 않아 복제도 되지 않 았다 — 오래 묵은 불만이었다. PG 10 에서 WAL 레코드와 crash safety 가 들어가면서 그 불만이 풀렸다. 디렉토리는 메타 페이지 에 뿌리내린 버킷 포인터 배열이고, 버킷이 넘치면 사슬로 이어 붙 인 overflow 페이지로 빠진다. PG 는 사용자에게 hash 인덱스를 노 출하고, 카탈로그 테이블의 point lookup 에도 쓴다.
BerkeleyDB DB_HASH. 주된 access method 가운데 하나가 extendible hashing 이다. 디렉토리 분기는 교과서대로 global vs local depth 비교를 따르고, 삭제는 선택적으로 버킷을 압축할 수 있지만 디렉토리는 거의 줄지 않는다.
Oracle hash cluster. cluster key 위의 해시 함수로 묶인 테 이블이다. Fagin 의 의미에서 extendible 은 아니다 (버킷 수가 생성 시점에 고정). 그러나 사용자가 보는 동기 — I/O 한 번의 point lookup — 는 같다.
DB2 LOAD with HASH. B+Tree 벌크 로드처럼 해시 파일을 bottom-up 으로 만드는 벌크-로드 인지 변종이다.
Linear hashing. Litwin 의 한 번에 한 버킷-split 도식이 가 장 큰 대안이다. PostgreSQL 의 hash 인덱스도 9.x 까지는 linear 였다. PG 10 의 다시 쓰기는 디스크 레이아웃은 그대로 두고 WAL 만 손봤다.

CUBRID 의 자리

CUBRID 의 extendible hash 는 사용자가 보는 인덱스 타입이 아니 다. CREATE INDEX ... USING HASH 같은 문법은 없다. 사용자가 얻는 인덱스는 B+Tree 뿐이다. 내부에서는 point lookup 이 워크로 드를 지배하고 range scan 이 필요 없는, 작은 이름 → OID 디렉토 리 한 줌을 떠받친다.

클래스 이름 → OID 디렉토리. SQL 컴파일러가 SELECT … FROM employee 를 처리할 때 식별자 employee 를 그 heap 파일을 소유한 클래스 OID 로 바꿔야 한다. 이 매핑은 boot_Db_parm->classname_table 에 산다. 데이터베이스 부팅 시 점에 만들어지는 영속 extendible hash 파일이며, 생성 자리는 xehash_create (boot_sr.c:5001) 다.
카탈로그 representation 디렉토리 (catalog_Id.xhid). xehash_create (… DB_TYPE_OBJECT, …) 가 system_catalog.c:2635 에서 클래스 OID 를 키로 한 해시 파일 을 만든다. 그 결과로 representation id 가 돌아오고, 옵티마이 저는 이 id 로 카탈로그 heap 에서 스키마 레코드를 찾는다. DROP CLASS 는 이 디렉토리에 ehash_delete 를 발행한다 (system_catalog.c:2230).
UPDATE/DELETE OID 중복 제거. UPDATE 또는 DELETE 문이 같 은 행을 여러 access path 로 만지는 경우 (예 — 두 인덱스의 union 스캔), 실행기는 같은 행에 두 번 적용되는 일을 막아야 한다. qexec_init_upddel_ehash_files (query_executor.c:9822) 는 대상 클래스마다 임시 해시 파일을 하나씩 잡고, 행 OID 를 키로 쓴다. 모든 후보 행은 먼저 ehash_search 로 검사한 다. 없으면 ehash_insert 로 기록한 뒤 update 를 진행하고, 있으면 그 행은 건너뛴다. 파일은 statement 가 끝날 때 qexec_destroy_upddel_ehash_files 가 정리한다.
Hash list / hash set 스캔 (src/query/query_hash_scan.{c,h}). HASH-LIST-SCAN 과 HASH-SET-SCAN 연산자의 in-memory 해시 측 을 위해 EHID 와 디렉토리 파일 형식을 다시 쓴다. 이 경로는 xehash_create 를 거치지 않고 file_create_ehash_dir 를 직 접 호출한다. 디렉토리 표현만 빌리고, 버킷 매니저는 따로 굴리 기 때문이다.

네 자리에 공통된 패턴은 분명하다 — 작은 키로, 작은~중간 크기 의 엔트리 집합을 point lookup 만 하면 되고 range scan 은 필요 없다. 이게 extendible hashing 이 B+Tree 를 이기는 정확 한 워크로드이고, 이 모듈을 만든 이유이기도 하다.

이론 ↔ CUBRID 명칭 매핑

이론적 개념	CUBRID 명칭
해시 파일 식별자	`EHID` = `{ VFID vfid; INT32 pageid }` (`storage_common.h:212`)
디렉토리 헤더	`EHASH_DIR_HEADER` (`extendible_hash.c:103`)
디렉토리 엔트리	`EHASH_DIR_RECORD = { VPID bucket_vpid }` (`extendible_hash.c:120`)
버킷 헤더	`EHASH_BUCKET_HEADER = { char local_depth }` (`extendible_hash.c:127`)
의사 키	`EHASH_HASH_KEY = unsigned int` (`extendible_hash.c:99`)
Search 반환 enum	`EH_SEARCH { EH_KEY_FOUND, EH_KEY_NOTFOUND, EH_ERROR_OCCURRED }` (`storage_common.h:381`)
내부 split/merge 결과 enum	`EHASH_RESULT` enum (`extendible_hash.c:132`)
좌측 N 비트 추출	`GETBITS(value, pos, n)` 매크로 (`extendible_hash.c`)
좌측 N 비트로 디렉토리 색인	`FIND_OFFSET(hash_key, depth)` 매크로
WAL 레코드 패밀리	`RVEH_REPLACE`, `RVEH_INSERT`, `RVEH_DELETE`, `RVEH_INIT_BUCKET`, `RVEH_CONNECT_BUCKET`, `RVEH_INC_COUNTER`, `RVEH_INIT_DIR`, `RVEH_INIT_NEW_DIR_PAGE` (`recovery.h:105-112`)

CUBRID의 구현

모듈은 두 파일과 복구 후크 한 줌으로 끝난다. 층별로 보는 게 가 장 자연스럽다 — 디스크 위 레이아웃 (EHID, 디렉토리 파일, 버킷 페이지), read 경로 (ehash_search), write 경로 (ehash_insert 와 split / 디렉토리 더블링), delete 경로 (ehash_delete 와 merge / 디렉토리 축소), 그리고 위의 모든 단 계를 crash-safe 로 만드는 WAL 통합.

전체 구조

flowchart TB
  subgraph EHID["EHID = { vfid, pageid }"]
    DIRROOT["디렉토리 루트 페이지<br/>EHASH_DIR_HEADER<br/>· 첫 번째 디렉토리 chunk"]
    DIRPAGES["디렉토리 페이지 1..N<br/>(EHASH_DIR_RECORD[])"]
    DIRROOT --> DIRPAGES
  end
  subgraph BUCKETS["버킷 파일 (별도 VFID)"]
    BUC0["버킷 0<br/>local_depth=2"]
    BUC1["버킷 1<br/>local_depth=2"]
    BUC2["버킷 2<br/>local_depth=1"]
  end
  DIRROOT -. dir_header.bucket_file .-> BUCKETS
  DIRPAGES -- "VPID 포인터" --> BUC0
  DIRPAGES -- "VPID 포인터" --> BUC1
  DIRPAGES -- "VPID 포인터 x2 (공유)" --> BUC2
  subgraph LOOKUP["Lookup"]
    L1["ehash_hash(key) → 32-bit 의사 키"]
    L2["FIND_OFFSET(pseudo_key, dir.depth) → 엔트리 idx"]
    L3["ehash_dir_locate → (디렉토리 페이지번호, 페이지내 offset)"]
    L4["ehash_locate_slot (버킷 안 binary search)"]
    L1 --> L2 --> L3 --> L4
  end

이 그림은 세 경계를 보여 준다. 첫째, 디렉토리 / 버킷. 디렉 토리는 한 파일이다 (EHID.pageid 에 뿌리내림). 버킷 풀은 다른 파일이고, 그 VFID 는 디렉토리 헤더에 들어 있다. 둘째, 공유 / 유일. d_b < d 인 디렉토리 엔트리는 2^(d - d_b) - 1 개의 형제 엔트리와 같은 버킷 페이지를 공유하고, d_b == d 인 엔트리는 버킷을 단독으로 가진다. 셋째, read / write. lookup 은 주소 사슬을 따라 걷기만 하는 순수 read 다. insert 와 delete 는 디렉토리, sibling 버킷, 그리고 LSN 으로 보호되는 디 스크 상태를 시스템 op 안에서 함께 만질 수 있다.

EHID 와 디스크 위 레이아웃

// EHID — src/storage/storage_common.h:212
typedef struct ehid EHID;
struct ehid
{
  VFID vfid;                  /* The directory file (volid + fileid) */
  INT32 pageid;               /* The first (root) page of the directory */
};

EHID 는 12 바이트다 (4-byte volid, 4-byte fileid, 4-byte pageid; object_representation_constants.h 의 OR_EHID_SIZE 참고). extendible hash 파일에 대한 디스크 위 핸들이다. 카탈로그 레코 드 (object_representation.c:1754 의 or_pack_ehid) 에 박히 고, boot_Db_parm->classname_table 을 들고 있는 데이터베이스 부팅 파라미터 페이지에도 그대로 박힌다.

디렉토리 파일의 첫 페이지는 EHID.pageid 가 가리키며 디렉토리 헤더로 시작한다.

// EHASH_DIR_HEADER — src/storage/extendible_hash.c:103
typedef struct ehash_dir_header EHASH_DIR_HEADER;
struct ehash_dir_header
{
  VFID bucket_file;        /* bucket file identifier */
  VFID overflow_file;      /* overflow (long-string) file identifier */
  int  local_depth_count[EHASH_HASH_KEY_BITS + 1];
                           /* hist[i] = number of buckets with local_depth = i;
                              used to detect when global depth can shrink */
  DB_TYPE key_type;        /* DB_TYPE_STRING or DB_TYPE_OBJECT */
  short   depth;           /* GLOBAL DEPTH d */
  char    alignment;       /* slot alignment for bucket pages */
};

헤더 다음으로, 같은 첫 페이지가 EHASH_NUM_FIRST_PAGES 만큼의 디렉토리 엔트리를 더 들고 다닌다. 이후의 디렉토리 페이지는 헤더 없이 EHASH_NUM_NON_FIRST_PAGES 개씩의 엔트리를 담는다. 엔트리 자체의 모양은 단순하다.

// EHASH_DIR_RECORD — src/storage/extendible_hash.c:120
typedef struct ehash_dir_record EHASH_DIR_RECORD;
struct ehash_dir_record
{
  VPID bucket_vpid;        /* bucket pointer */
};

ehash_dir_locate (extendible_hash.c:384) 는 디렉토리 엔트리 인덱스를 (page_no, in-page offset) 으로 옮기는 함수다.

// ehash_dir_locate — src/storage/extendible_hash.c:384
static void
ehash_dir_locate (int *out_page_no_p, int *out_offset_p)
{
  int page_no, offset = *out_offset_p;
  if (offset < EHASH_NUM_FIRST_PAGES)
    {
      offset = offset * sizeof (EHASH_DIR_RECORD) + EHASH_DIR_HEADER_SIZE;
      page_no = 0;
    }
  else
    {
      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;
}

따라서 디렉토리는 외관상 2^depth 개의 EHASH_DIR_RECORD 가 연속해서 늘어선 단일 배열이다. 단지 그 배열이 여러 페이지에 걸쳐 있을 뿐이다. 첫 페이지가 특별한 이유는 단 하나 — 그 안의 배열이 EHASH_DIR_HEADER_SIZE 만큼 뒤에서 시작한다는 점이다.

버킷은 버킷 파일 (별도 VFID, dir_header.bucket_file) 에 산다. 모든 버킷 페이지는 슬롯 페이지 (ptype = PAGE_EHASH) 다. 슬롯 0 이 1바이트짜리 EHASH_BUCKET_HEADER 를 들고 있어서 버킷의 local depth 를 싣는다. 나머지 슬롯에는 (OID || key_bytes) 레코드가 한 개씩 들어 있다. 버킷 페이지의 초기화는 ehash_initialize_bucket_new_page (extendible_hash.c:628) 가 하며, file_alloc 의 page-init 콜백으로 호출된다.

// EHASH_BUCKET_HEADER — src/storage/extendible_hash.c:127
typedef struct ehash_bucket_header EHASH_BUCKET_HEADER;
struct ehash_bucket_header
{
  char local_depth;        /* The local depth d_b of this bucket */
};

버킷 페이지는 UNANCHORED_KEEP_SEQUENCE 슬롯 정렬을 쓴다 (spage_initialize 인자). 슬롯 순서는 insert / delete 마다 바 뀔 수 있고, 슬롯 인덱스 공간이 정렬을 가로질러 안정되지 않는다 는 뜻이다. 이 선택은 의도적이다. 버킷 레코드는 사용자 키 순 서 (슬롯 순서가 아닌) 로 유지되어야 binary search 가 가능하 고, 그러려면 슬롯 페이지 계층이 insert 마다 슬롯 번호를 다시 매겨 줘야 한다.

EHID 생성 — `xehash_create`

공개 생성 함수는 xehash_create (extendible_hash.c:866) 다. 실제 작업은 ehash_create_helper (extendible_hash.c:954) 로 넘긴다.

// xehash_create — src/storage/extendible_hash.c:866
EHID *
xehash_create (THREAD_ENTRY *thread_p, EHID *ehid_p, DB_TYPE key_type, int exp_num_entries,
               OID *class_oid_p, int attr_id, bool is_tmp)
{
  return ehash_create_helper (thread_p, ehid_p, key_type, exp_num_entries,
                              class_oid_p, attr_id, is_tmp);
}

helper 의 단계는 다음과 같다 (extendible_hash.c:954-1178 에서 간추림).

key_type 검증. CUBRID 런타임은 DB_TYPE_STRING 과 DB_TYPE_OBJECT 만 허용하고, 그 외는 ENABLE_UNUSED_FUNCTION 에 막혀 있다. helper 첫머리의 assert (key_type == DB_TYPE_STRING || key_type == DB_TYPE_OBJECT) 가 그 게이트다.
exp_num_entries 로 버킷 페이지 수를 추정한다. 문자열 키 예 산은 엔트리당 20 바이트 키 + OID + 슬롯 오버헤드 (4 바이트) 를 가정하고, OID 키 예산은 실제 키 크기를 쓴다. exp_num_entries < 0 이면 한 페이지짜리로 잡는다.
버킷 페이지의 슬롯 정렬을 max(sizeof(int), sizeof(OID.pageid), key_size) 로 잡되, sizeof(int) 로 cap 한다.
버킷 파일 생성. file_create_ehash 가 FILE_EHASH_DES { class_oid, attr_id } descriptor 와 함께 FILE_EXTENDIBLE_HASH 파일로 등록한다. file_alloc 으로 버 킷 페이지 0 을 잡고, 콜백으로 ehash_initialize_bucket_new_page 를 넘긴다 — 이 콜백이 슬롯 0 에 (local_depth = 0 인) 버킷 헤더를 쓰고 RVEH_INIT_BUCKET 로그를 남긴다.
디렉토리 파일 생성. file_manager.c:3285 의 형제 helper file_create_ehash_dir 가 FILE_EXTENDIBLE_HASH_DIR 로 등 록한다. 페이지 0 을 generic page-type init 으로 잡는다.
디렉토리 루트 페이지에 디렉토리 헤더 를 적는다 — global depth 0, key type, alignment, 버킷 파일 VFID, null overflow file VFID, local_depth_count[0] = 1 (depth 0 인 버킷 한 개).
한 개짜리 디렉토리 엔트리 — 버킷 페이지 0 을 가리키는 — 를 적는다.
RVEH_INIT_DIR 발행 (redo-only 레코드. 생성 트랜잭션이 abort 되면 파일 자체가 복구에 의해 회수되기 때문이다).
채워진 EHID 를 호출자에게 돌려 준다.

따라서 시작 상태는 depth = 0, 디렉토리 엔트리 한 개, local_depth = 0 인 버킷 한 개다. 그 한 버킷이 넘칠 때까지 모든 키가 거기 로 해시된다.

의사 키 — `ehash_hash`

ehash_hash (extendible_hash.c:4347) 는 키 타입에 따라 분기 한다.

// ehash_hash — src/storage/extendible_hash.c:4347 (condensed)
static EHASH_HASH_KEY
ehash_hash (void *original_key_p, DB_TYPE key_type)
{
  switch (key_type)
    {
    case DB_TYPE_STRING:
      return ehash_hash_string_type (key, original_key_p);
    case DB_TYPE_OBJECT:
      return ehash_hash_eight_bytes_type (key);    /* OID is 8 useful bytes */
    /* … other types only under ENABLE_UNUSED_FUNCTION … */
    default:
      er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
    }
}

문자열 변형 (ehash_hash_string_type, extendible_hash.c:4156) 은 뒤쪽 공백을 잘라낸 뒤 키를 4 바이 트씩 잘라 32비트 누산기에 더하는 고전적인 folding 을 수행한 다. 그 다음 memory_hash 의 독립적인 문자열 해시 세 개 — mht_1strhash, mht_2strhash, mht_3strhash — 를 fold 결과 의 4 바이트에 적용한다. 세 결과를 의사 키 상위 3 바이트에 채워 넣고, byte sum 을 하위 1 바이트에 둔다. 의도는 분명하다 — 입 력 문자열이 긴 공통 prefix 를 공유할 때 — customer, customer_address, customer_phone 처럼 클래스 이름에서 자주 나오는 형태 — 도 32비트 의사 키 공간 전체에 비트를 흩어 두는 것이다.

8 바이트 변형 (OID 용) 은 두 정수를 htonl 로 fold 하고 마지 막 byte-sum 패스로 결과를 흩어 둔다. OID 의 (volid, pageid, slotid) 가 이미 거의 고유하므로 목표는 full avalanche 가 아니 라 키 공간의 한 사분면에 몰리지 않게 하기 정도다.

출력은 unsigned int (EHASH_HASH_KEY, extendible_hash.c:99), 32비트다. 따라서 global depth d 는 32 를 넘을 수 없다. GETBITS 매크로가 좌측 정렬된 비트 필드를 뽑고, FIND_OFFSET(hash_key, depth) 가 좌측 depth 개 비트 를 뽑는다.

Lookup — `ehash_search`

Lookup 은 짧다.

// ehash_search — src/storage/extendible_hash.c:1379 (condensed)
EH_SEARCH
ehash_search (THREAD_ENTRY *thread_p, EHID *ehid_p, void *key_p, OID *value_p)
{
  if (ehid_p == NULL || key_p == NULL)
    return EH_KEY_NOTFOUND;

  dir_root_page_p = ehash_find_bucket_vpid_with_hash (
      thread_p, ehid_p, key_p,
      PGBUF_LATCH_READ, PGBUF_LATCH_READ,   /* root S, bucket S */
      &bucket_vpid, NULL, NULL);

  if (bucket_vpid.pageid == NULL_PAGEID) goto end;   /* directory hole */

  bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid,
                                      &bucket_vpid, PGBUF_LATCH_READ);
  if (!ehash_locate_slot (thread_p, bucket_page_p,
                          dir_header_p->key_type, key_p, &slot_id))
    { result = EH_KEY_NOTFOUND; goto end; }

  spage_get_record (thread_p, bucket_page_p, slot_id, &recdes, PEEK);
  ehash_read_oid_from_record (recdes.data, value_p);
  result = EH_KEY_FOUND;
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;
}

ehash_find_bucket_vpid_with_hash (extendible_hash.c:1327) 가 주소 변환 루틴이다. 디렉토리 루트 페이지를 S 래치로 fix 하고, 키를 해시해 location = FIND_OFFSET(pseudo_key, depth) 를 계산 한다. 그 다음 ehash_find_bucket_vpid (extendible_hash.c:1295) 가 그 엔트리가 루트 페이지에 있는지, 아니면 뒤따르는 디렉토리 페이지 어딘가에 있는지를 판단한다. 후자라면 그 페이지도 fix 하 고, bucket_vpid 를 복사해 빠져나온다.

디렉토리 포인터가 NULL_PAGEID 이면 — 한 번 비워졌다가 회수 는 되었지만 아직 merge 로 사라지지 않은 자리 — search 는 즉시 EH_KEY_NOTFOUND 를 돌려 준다.

그 외에는 read 래치로 버킷 페이지를 fix 하고, ehash_locate_slot (extendible_hash.c:2479) 가 버킷 안에서 binary search 를 돌린다. 버킷이 사용자 키 순서로 레코드를 유지하므로 (슬롯 페이지가 unanchored-but-keep-sequence 로 잡혀 있다) binary search 가 가능하다. 비교는 ehash_compare_key (extendible_hash.c:2223) 가 키 타입별로 분기해서 -1 / 0 / +1 을 돌려 준다.

따라서 lookup 의 비용은 두 번의 페이지 fix (디렉토리 루트

버킷 — 자주 쓰는 테이블이라면 거의 항상 buffer-pool hit) 와 버킷 안의 binary search 한 번 (O(log m), m 은 버킷 레 코드 수) 이다.

Insert — `ehash_insert`

공개 진입점은 디렉토리 루트에 shared 래치 만 잡고 ehash_insert_helper 를 부른다. insert 가 디렉토리 확장을 일 으키지 않을 거라는 낙관적 가정이다.

// ehash_insert — src/storage/extendible_hash.c:1461
void *
ehash_insert (THREAD_ENTRY *thread_p, EHID *ehid_p, void *key_p, OID *value_p)
{
  if (ehid_p == NULL || key_p == NULL) return NULL;
  return ehash_insert_helper (thread_p, ehid_p, key_p, value_p, S_LOCK, NULL);
}

ehash_insert_helper (extendible_hash.c:1715) 가 오케스트레 이터다. lock-promotion 패턴은 B+Tree 의 “X 로 root 부터 다시 시작하기” 와 같은 발상이다. helper 가 디렉토리를 X 로 mutate 해야 한다고 판단한 순간, shared 래치를 풀고 X_LOCK 으로 자 기 자신을 다시 호출한다.

flowchart TB
  start["ehash_insert_helper(key, value, lock=S)"]
  start --> resolve["ehash_find_bucket_vpid_with_hash<br/>디렉토리 S/X 래치, 버킷 VPID 해석"]
  resolve --> case_null{"bucket_vpid<br/>== NULL?"}
  case_null -- "예" --> retry1{"lock == S?"}
  retry1 -- "예" --> restart1["디렉토리 release,<br/>X_LOCK 으로 재진입"]
  retry1 -- "아니오" --> create["ehash_insert_to_bucket_after_create<br/>(새 버킷 할당, connect, log sysop)"]
  case_null -- "아니오" --> attempt["ehash_insert_bucket_after_extend_if_need"]
  attempt --> simple["ehash_insert_to_bucket<br/>(write or replace)"]
  simple --> ok{"결과"}
  ok -- "OK" --> done["pgbuf_unfix dir; 키 반환"]
  ok -- "BUCKET_FULL" --> retry2{"lock == S?"}
  retry2 -- "예" --> restart2["디렉토리 release,<br/>X_LOCK 으로 재진입"]
  retry2 -- "아니오" --> split["ehash_extend_bucket<br/>(split + 필요 시 디렉토리 확장)"]
  split --> reinsert["선택된 쪽에 ehash_insert_to_bucket"]
  reinsert --> done

버킷에 끼워 넣기 — `ehash_insert_to_bucket`

직선 경로 — 자리가 있고 키가 아직 없는 경우 — 는 ehash_insert_to_bucket (extendible_hash.c:1837) 이 처리한다.

ehash_locate_slot 으로 키가 들어갈 자리를 찾는다.
found 이면 (키가 이미 있음) — replace. 옛 레코드를 복 사한 뒤, 새 OID 를 그 자리의 OID 슬롯에 in-place 로 쓰고, RVEH_DELETE undo (abort 시 옛 OID 복원) 와 RVEH_REPLACE redo (새 OID 재적용) 를 발행한다. 결국 ehash_insert 의 의미는 upsert 다 — 같은 키로 두 번째 insert 하면 값이 교 체된다.
그 외 — ehash_compose_record 가 (OID || key_bytes) 모양 (작은 변형) 또는 (OID || prefix_vpid || prefix) 모양 (REC_BIGONE, 긴 문자열 overflow 변형. ENABLE_UNUSED_FUNCTION 에 막혀 현재 빌드에서는 비활성) 의 레코드를 만든다. 그 다음 spage_insert_at 으로 결정된 슬롯에 끼워 넣는다.
spage_insert_at 이 SP_DOESNT_FIT 를 돌려주면 버킷이 가 득 찼다는 뜻이다 — EHASH_BUCKET_FULL 을 호출자에게 돌려 준다 (split 경로의 트리거다).
RVEH_INSERT undo / redo 발행. undo 레코드는 EHID + 끼워 넣은 레코드를 함께 들고 다닌다 (undo 핸들러 ehash_rv_insert_undo 가 EHID 를 읽고, ehash_rv_delete 를 호출해 엔트리를 제거한다).
pgbuf_set_dirty (bucket_page_p, DONT_FREE).

WAL 레코드의 모양 — undo 는 EHID + 지울 레코드, redo 는 슬 롯 id + 끼워 넣을 레코드 — 은 logical undo, physical redo 다. 가변 길이 레코드 저장소에 대한 ARIES 의 고전 규율 이다.

버킷 split — `ehash_split_bucket` 과 depth 의 춤

ehash_insert_to_bucket 이 EHASH_BUCKET_FULL 을 돌려 줬고 호출자가 디렉토리에 X 래치를 들고 있다면, 오케스트레이터는 ehash_extend_bucket (extendible_hash.c:1546) 다. 시스템 op (log_sysop_start / log_sysop_commit) 안에서 돌아가서, 그 도 중 crash 가 나도 디렉토리가 일관성이 깨진 상태로 남지 않게 한 다.

sequenceDiagram
  participant H as ehash_insert_helper
  participant E as ehash_extend_bucket
  participant S as ehash_split_bucket
  participant D as ehash_expand_directory
  participant C as ehash_connect_bucket
  participant L as log_manager (sysop)

  H->>E: 버킷 가득 참, X 래치 보유
  E->>L: log_sysop_start
  E->>S: split_bucket(buc_pgptr, key)
  S->>S: RVEH_REPLACE undo 로깅 (full bucket image)
  S->>S: ehash_find_first_bit_position (새 local depth 계산)
  S->>S: file_alloc 로 sibling 페이지 할당 (ehash_initialize_bucket_new_page 로 init)
  S->>S: ehash_distribute_records_into_two_bucket
  S->>S: 버킷과 sibling 에 대해 RVEH_REPLACE redo 로깅
  S-->>E: sibling 페이지 ptr, old/new local_depth, 새 VPID
  E->>E: ehash_adjust_local_depth (-1 옛 depth, +2 새 depth)
  alt new_local_depth > global depth
    E->>D: ehash_expand_directory (디렉토리 두 배로)
  end
  alt new_local_depth - old_local_depth > 1
    E->>C: 옛 슬롯 범위를 NULL_VPID 로 connect
    E->>C: 아래 절반을 원 버킷에 connect
  end
  E->>C: 위 절반을 sibling 에 connect
  E->>L: log_sysop_commit
  E-->>H: sibling_page_p, new_bit

흥미로운 단계들.

ehash_find_first_bit_position (extendible_hash.c:2545) 은 버킷의 레코드를 훑으면서 (각 레코드의 의사 키를 ehash_get_pseudo_key 로 다시 계산), 첫 레코드의 의사 키와 XOR 한 뒤, 어떤 레코드라도 첫 레코드와 다른 최초의 비트 위 치 를 찾는다. 그 위치가 새 local depth 가 된다. 다시 말해 CUBRID 은 local_depth + 1 을 무조건 적용하지 않는다. 레코 드를 실제로 나눠 주는 가장 작은 local depth 를 고른다. 한쪽 이 비어 있는 split — 곧바로 다시 split 해야 하는 모양 — 을 피하려는 것이다.
ehash_distribute_records_into_two_bucket (extendible_hash.c:2605) 는 레코드를 하나씩 검사한다. 의사 키의 local_depth 번째 비트가 1 이면 sibling 으로, 0 이면 그대로 둔다. 원래 버킷에서의 순서는 두 절반에서도 보존되며, 그 덕에 양쪽 버킷이 사용자 키 순서로 정렬된 채 유지된다 (의 사 키 비트는 사용자 키 정렬과 독립이고, 버킷 안 binary search 는 사용자 키 순서에 의존하기 때문이다).
ehash_expand_directory (extendible_hash.c:2792) 는 디 렉토리를 마지막 엔트리부터 거꾸로 걸으며, 각 옛 엔트리를 확 장된 공간에 2^(new_depth - old_depth) 번씩 복사해 넣는다. 새 디렉토리 페이지가 필요하면 file_alloc_multiple 로 잡고 ehash_initialize_dir_new_page 로 초기화한다 — 이 콜백이 RVEH_INIT_NEW_DIR_PAGE 를 발행한다. 수정된 기존 디렉토리 페이지 각각은 페이지 전체 이미지의 paired RVEH_REPLACE undo+redo 로 로깅된다.
ehash_connect_bucket (extendible_hash.c:3067) 는 디 렉토리 엔트리의 연속된 범위 를 한 VPID 로 다시 쓴다. 다 시 쓸 엔트리 수는 2^(global_depth - local_depth) 다. 범위 의 양 끝은 해시 유래 location 의 하위 (global_depth - local_depth) 비트를 모두 1 (set_bits) 또 는 모두 0 으로 두는 식으로 계산하고, ehash_dir_locate 가 그 끝점들을 페이지번호와 offset 으로 옮긴다. 영향받는 디렉토 리 페이지마다 RVEH_CONNECT_BUCKET 레코드 하나 를 발행 한다. 페이로드는 EHASH_REPETITION = { VPID, count } 다. 짝이 맞는 redo 함수 ehash_rv_connect_bucket_redo (extendible_hash.c:5429) 는 count 슬롯을 다시 쓰면 끝이 다. 그 덕에 WAL 양은 영향받는 디렉토리 페이지당 O(1) 로 유지된다 (O(count * sizeof(VPID)) 가 아니라).
ehash_adjust_local_depth (extendible_hash.c:3633) 는 디렉토리 루트 페이지의 dir_header.local_depth_count[depth] += delta 를 갱신하고, RVEH_INC_COUNTER undo+redo 를 발행한다 (복구 핸들러는 ehash_rv_increment). 이 히스토그램이 나중 디렉토리 축소의 입력이다 — 현재 dir_header.depth 를 local_depth_count[depth] 가 0 으로 떨어지면 디렉토리 폭에 비해 의미 있는 비트 수가 줄어든 것이고, 축소가 이득이라는 신 호다.

디렉토리 엔트리가 NULL 일 때의 버킷 생성

delete 가 디렉토리 엔트리를 NULL_VPID 로 남길 수 있다 (버킷 이 비워져 회수되었지만 디렉토리는 아직 줄지 않은 상태). 다음 insert 가 그 자리로 해시되면 helper 는 ehash_insert_to_bucket_after_create (extendible_hash.c:1472) 를 부른다.

ehash_find_depth (extendible_hash.c:3183) 가 NULL 슬롯 주변을 살피며, 이 엔트리의 범위를 상위 비트가 같은 다른 버 킷들과 구별해 주는 가장 작은 local depth 를 결정한다. 그 결 과 depth 가 새 버킷의 헤더에 들어간다.
file_alloc 으로 버킷 페이지를 잡고, 위에서 결정한 depth 로 ehash_initialize_bucket_new_page 가 초기화한다.
ehash_connect_bucket 으로 그 run 안의 2^(d - d_b) 개 디 렉토리 엔트리를 새 버킷으로 다시 쓴다.
ehash_adjust_local_depth(+1) 로 히스토그램을 갱신한다.
ehash_insert_to_bucket 가 사용자 레코드를 적는다.

전체 시퀀스는 log_sysop_start / log_sysop_commit 으로 묶인 다.

Delete — `ehash_delete`

ehash_delete (extendible_hash.c:3418) 는 ehash_insert 의 거꾸로다. 디렉토리 루트는 S 로, 버킷은 X 로 잡는다. 두 번 째 시도의 promotion 경로는 없다. 일반적인 경우 delete 가 디렉 토리를 mutate 할 일이 없기 때문이다.

// ehash_delete — src/storage/extendible_hash.c:3418 (condensed)
void *
ehash_delete (THREAD_ENTRY *thread_p, EHID *ehid_p, void *key_p)
{
  dir_root_page_p = ehash_find_bucket_vpid_with_hash (
      thread_p, ehid_p, key_p,
      PGBUF_LATCH_READ, PGBUF_LATCH_WRITE,   /* root S, bucket X */
      &bucket_vpid, NULL, &location);

  if (bucket_vpid.pageid == NULL_PAGEID) { /* not found */ }

  bucket_page_p = ehash_fix_old_page (… PGBUF_LATCH_WRITE);
  if (!ehash_locate_slot (… &slot_no)) { /* ER_EH_UNKNOWN_KEY */ }

  spage_get_record (thread_p, bucket_page_p, slot_no, &bucket_recdes, PEEK);

  /* logical undo log: EHID || full record */
  log_append_undo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, NULL,
                         bucket_recdes.type, log_recdes_undo.length, log_recdes_undo.data);
  /* physical redo log: slot-id with key-type prefix */
  log_append_redo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, bucket_page_p,
                         slot_no, log_recdes_redo.length, log_recdes_redo.data);

  spage_delete (thread_p, bucket_page_p, slot_no);
  pgbuf_set_dirty (thread_p, bucket_page_p, DONT_FREE);

  /* Decide whether to merge */
  if (bucket became empty || bucket underflows below EHASH_UNDERFLOW_THRESHOLD)
    {
      if (ehash_check_merge_possible (… S_LOCK …) == EHASH_SUCCESSFUL_COMPLETION)
        do_merge = true;
    }

  pgbuf_unfix dir, bucket;
  if (do_merge) ehash_merge (thread_p, ehid_p, key_p, is_temp);

  return key_p;
}

임계는 다음과 같다.

// src/storage/extendible_hash.c:69-91
#define EHASH_OVERFLOW_RATE   0.9     /* sibling fullness ceiling for merge */
#define EHASH_UNDERFLOW_RATE  0.4     /* below this -> try to merge */
#define EHASH_OVERFLOW_THRESHOLD   (EHASH_OVERFLOW_RATE * DB_PAGESIZE)
#define EHASH_UNDERFLOW_THRESHOLD  (EHASH_UNDERFLOW_RATE * DB_PAGESIZE)

underflow (40 %) 와 overflow (90 %) 의 비대칭이 yo-yo split-merge 진동을 막는다. delete 는 버킷이 40 % 아래로 떨어 졌고 동시에 sibling 이 남은 레코드를 흡수한 뒤에도 90 % 의 자리만 차지할 때만 merge 한다. 다시 말해 — merge 결과가 곧장 다시 split 으로 이어지지 않을 때만 merge 한다.

Merge — `ehash_merge`

ehash_merge (extendible_hash.c:3771) 는 디렉토리를 다시 X 래치로 잡고, 버킷이 여전히 merge 를 원하는지 다시 확인한 다 (그 사이 다른 insert 가 다시 채워 놓았을 수 있다). 결정은 ehash_check_merge_possible (extendible_hash.c:3274) 가 분 기한다.

EHASH_NO_SIBLING_BUCKET — 버킷의 local depth 가 0 (단일 버 킷 파일) 이거나 sibling 슬롯이 null 이다.
- 그 상황에서 버킷이 비어 있고 local depth > 0 이면, 버 킷 페이지를 file_dealloc 하고, 그 버킷을 가리키던 모든 디렉토리 엔트리를 NULL_VPID 로 리셋하며, local_depth_count[old_depth] 를 1 줄인다. 그 후 ehash_shrink_directory_if_need 가 히스토그램이 global-depth 축소를 허용하는지 본다.
EHASH_FULL_SIBLING_BUCKET — sibling 이 90 % 규칙 아래에서 는 남은 레코드를 받아낼 수 없다. merge 는 포기되고 버킷은 underfill 상태로 남는다.
EHASH_SUCCESSFUL_COMPLETION — 실제 merge. ehash_merge_permanent (extendible_hash.c:3655) 가 레코드 를 sibling 으로 옮기고, sibling 의 local depth 를 ehash_find_depth 로 갱신하고, 비워진 원본 버킷 페이지를 dealloc 하며, 원본을 가리키던 디렉토리 엔트리들을 sibling 으 로 다시 쓴다. 히스토그램은 ehash_adjust_local_depth 두 번 (-2 옛 depth, +1 새 depth) 으로 갱신되고, 이어서 ehash_shrink_directory_if_need 가 디렉토리를 절반으로 줄일 수 있다.

merge 시퀀스 전체는 log_sysop_start / log_sysop_commit 안 에 들어간다 — split 을 둘러싼 것과 같은 system-op 봉투다.

디렉토리 축소 — `ehash_shrink_directory_if_need` / `ehash_shrink_directory`

히스토그램이 트리거하는 축소.

// ehash_shrink_directory_if_need — src/storage/extendible_hash.c:3615
static void
ehash_shrink_directory_if_need (THREAD_ENTRY *thread_p, EHID *ehid_p,
                                EHASH_DIR_HEADER *dir_header_p, bool is_temp)
{
  int i = dir_header_p->depth;
  while (dir_header_p->local_depth_count[i] == 0) i--;
  if ((dir_header_p->depth - i) > 1)
    ehash_shrink_directory (thread_p, ehid_p, i + 1, is_temp);
}

임계는 >= 1 이 아니라 > 1 이다. 디렉토리는 최소 두 단계 의 깊이가 비어 있을 때만 줄인다. 살아 있는 최대 depth 가 경 계에 걸쳐 있을 때 shrink-grow 진동을 피하려는 설계다. ehash_shrink_directory (extendible_hash.c:3982) 는 확장의 거꾸로다. 새 디렉토리를 왼쪽에서 오른쪽으로 걸으며 옛 디렉토리 의 매 2^times 번째 엔트리만 복사하고, 수정된 페이지마다 페이 지 이미지의 paired RVEH_REPLACE undo+redo 를 로깅하며, 뒤따 르는 디렉토리 페이지를 file_dealloc 한다.

동시성과 래치

CUBRID 의 extendible hash 는 페이지 래치만 쓴다. 별도의 hash 단위 lock 은 없다. 규율은 다음과 같다.

Search — 디렉토리 루트 페이지를 S 로, 필요하면 보조 디렉 토리 페이지도 S 로 fix, 그 다음 버킷을 S 로 fix. 세 래치 모 두 잠시 들고 있을 수 있다. 디렉토리 루트와 디렉토리 페이지는 bucket_vpid 가 추출되자마자 풀고, 버킷 S 래치는 binary search 와 값 추출 동안 유지된다.
Insert (빠른 경로, split 없음) — 디렉토리 루트 S 래치, 버킷 X 래치. 버킷 X 래치가 locate ▸ insert ▸ log ▸ set-dirty 를 모두 덮는다.
Insert (split 또는 디렉토리 확장) — 디렉토리 루트 X 래 치로 재시작, 버킷 X 래치, sibling X 래치, 그리고 ehash_connect_bucket / ehash_expand_directory 가 건드리 는 모든 디렉토리 페이지에 X 래치. 한 system op 안에 모두 들 어간다.
Delete (빠른 경로, merge 없음) — 디렉토리 루트 S 래치, 버킷 X 래치. merge 로 promote 되면 둘을 풀고 X / X 로 다시 잡는다.
Merge / shrink — 디렉토리 루트 X, 버킷 X, sibling X, 영향받는 디렉토리 페이지 각각에 X. system-op 괄호 안.

공통 모델은 따라서 페이지 fix → search → 필요하면 promote → log → release 다. B+Tree 와 비슷하지만 트리 경로가 없으 므로 latch-coupling 이 없다. 디렉토리는 한 단계 깊이 (헤더 페이 지 → 본문 페이지 → 버킷 페이지) 이고, descent 는 최대 세 fix 다.

ehash_insert 의 낙관적-S-래치-후-재시작 패턴이 치르는 비용은 — 버킷이 실제로 가득 차 있는 경우의 두 번의 descent 다. 한 번은 S 아래에서 BUCKET_FULL 을 발견하기 위해, 또 한 번은 X 아래에서. 이득은 흔한 경로 — 가득 차지 않은 버킷에 끼워 넣 기 — 가 디렉토리 루트에 X 래치를 한 번도 잡지 않는다는 점이 다. 그래서 무관한 키들의 동시 검색이 insert 에 막히지 않는다. 짧은 이름→OID lookup 이 워크로드를 지배하는 환경 (부팅 시점 의 클래스 해석, query 컴파일) 에서는 이 trade-off 가 잘 맞는 다.

WAL 통합 — `RVEH_*` 레코드

CUBRID 은 extendible hash 용으로 8 개의 별도 복구 인덱스를 발 행한다 (recovery.h:105-112).

인덱스	발행 자리	복구 핸들러	목적
`RVEH_REPLACE = 58`	`ehash_split_bucket`, `ehash_expand_directory`, `ehash_shrink_directory`, `ehash_merge_permanent`	`log_rv_copy_char` / `ehash_rv_…_redo`	디렉토리 또는 버킷 페이지의 페이지 이미지 undo/redo
`RVEH_INSERT = 59`	`ehash_insert_to_bucket`	`ehash_rv_insert_redo` / `ehash_rv_insert_undo`	버킷의 레코드 단위 insertion
`RVEH_DELETE = 60`	`ehash_delete`, `ehash_rv_delete`	`ehash_rv_delete_redo` / `ehash_rv_delete_undo`	버킷의 레코드 단위 deletion
`RVEH_INIT_BUCKET = 61`	`ehash_initialize_bucket_new_page`	`ehash_rv_init_bucket_redo`	새로 할당된 버킷 페이지를 다시 초기화 (슬롯 페이지 init + 헤더)
`RVEH_CONNECT_BUCKET = 62`	`ehash_connect_bucket`	`ehash_rv_connect_bucket_redo`	디렉토리 엔트리 연속 범위를 한 VPID 로 다시 쓰기
`RVEH_INC_COUNTER = 63`	`ehash_adjust_local_depth`	`ehash_rv_increment`	`local_depth_count[i]` 를 ±delta 만큼 조정
`RVEH_INIT_DIR = 64`	`ehash_create_helper`	`ehash_rv_init_dir_redo`	파일 생성 시 디렉토리 루트 페이지 초기화
`RVEH_INIT_NEW_DIR_PAGE = 65`	`ehash_initialize_dir_new_page`	`ehash_rv_init_dir_new_page_redo`	디렉토리 확장 페이지 초기화

이들을 복구 함수 배열에 꽂아 두는 dispatch 표는 transaction/recovery.c:415-452 에 있다. 각 레코드의 데이터 버퍼는 핸들러가 LSN 이 가리키는 페이지 위에서 멱등하게 다시 동작할 수 있도록 충분한 페이로드를 들고 다닌다 — RVEH_INSERT 는 (short rec_type, OID, key_bytes), RVEH_DELETE redo 는 거기에 슬롯 id 가 더해진 형태, RVEH_DELETE undo 는 (EHID, OID, key_bytes) 다. 마지막 형태가 EHID 를 들고 가는 이유는 분명하다 — undo 핸들러가 버킷을 다시 찾아야 하기 때 문이다. 원래 insert 이후 split 이나 merge 가 레코드를 옮겨 두 었을 수 있어서 LSN 의 페이지 정체성을 그대로 믿을 수는 없다.

undo 의 규율은 insert / delete 는 logical, split / merge 는 physical (페이지 이미지 replace) 이다. insert 의 logical undo 는 ehash_rv_insert_undo 가 EHID + 키로 엔트리를 다시 찾 아내고 ehash_rv_delete 를 호출해 제거하는 식이다. physical undo 였다면 슬롯 페이지 상태를 byte 단위로 되돌려야 했을 텐 데, 그 사이에 버킷이 split 되어 옮겨졌다면 그 방식은 깨진다. 반면 split / merge 경로는 physical undo 를 쓴다 (페이지 전체 이미지, DB_PAGESIZE). 이미 X 래치를 잡은 채 system op 안에서 돌고 있고, 재분배에 대한 안전한 logical 역연산 을 계산할 길 이 없기 때문이다. 페이지 이미지 replay 가 옳고 단순하다. 비용 은 — 수정된 페이지마다 페이지 이미지 한 장 — system-op 봉 투에 의해 한정된다. 한 split 이 로깅하는 페이지 이미지는 최대 세 장 (원본 버킷, sibling 버킷, 디렉토리 페이지 한 장) 이다. 견딜 만한 양이다.

CUBRID 안에서의 사용처 — 네 자리

grep -rn "ehash_\|EHID\|xehash_" src/ 로 검증.

클래스 이름 → OID 디렉토리. EHID classname_table 은 데이터베이스 부팅 파라미터에 산다 (boot_sr.c:122). 데이터 베이스의 최초 포맷 시점에 xehash_create (… DB_TYPE_STRING, …, rootclass_oid, …, false) (boot_sr.c:5001) 로 생성되며, 데이터베이스 수명 동안 유지 된다. lookup (ehash_search), CREATE TABLE 의 insert, DROP TABLE 의 delete 는 모두 locator_* (locator 매니저) wrapper 를 거치고, 그 아래에서 표준 공개 API 가 호출된다.
카탈로그 representation 디렉토리. system_catalog.c 안 에서 카탈로그 인덱스 catalog_id_p->xhid 가 xehash_create (… DB_TYPE_OBJECT, 1, oid_Root_class_oid, -1, false) (system_catalog.c:2635) 로 만들어진다. 클래스 OID 를 그 카탈로그 representation 엔트리로 매핑한다. DROP CLASS 는 ehash_delete (thread_p, &catalog_Id.xhid, key) (system_catalog.c:2230) 로 매핑을 지운다.
UPDATE/DELETE OID 중복 제거. qexec_init_upddel_ehash_files (query_executor.c:9822) 가 각 multi-class UPDATE/DELETE 계획의 시작 시점에 xasl->upd_del_class_cnt 만큼의 임시 EHID 를 잡는다. 호출 은 xehash_create (… DB_TYPE_OBJECT, -1, NULL, 0, true) — is_tmp == true 라 logging 이 억제된다. 실행 중에는 qexec_upddel_add_unique_oid_to_ehid (query_executor.c:1015) 가 먼저 ehash_search 를 부른다. OID 가 있으면 그 행은 이미 처리된 것으로 NULL 처리되고, 없 으면 ehash_insert 가 그것을 기록한다. 파일은 statement 가 끝날 때 qexec_destroy_upddel_ehash_files 가 정리한다.
Hash-list / hash-set 스캔. src/query/query_hash_scan.{c,h} 가 EHID ehid 를 임베드 한 FILE_HASH_SCAN 구조체를 정의한다. HASH-LIST-SCAN 과 HASH-SET-SCAN 연산자의 materialized 해시 측을 위해 디렉토 리 파일 형식을 (file_create_ehash_dir 으로) 다시 쓴 다. 이 자리는 xehash_create 를 거치지 않는 유일한 자 리다 — 디렉토리 부분만 만들고 그 위에 자기만의 버킷 로직을 굴린다.

엔진 안에는 그 외의 호출자가 없다. 특히 사용자가 만든 인덱 스는 extendible hashing 을 쓰지 않는다 — B+Tree (btree.c) 뿐이다.

제약과 현재 상태

현재 빌드의 키 타입. DB_TYPE_STRING 과 DB_TYPE_OBJECT 뿐이다. 코드는 DB_TYPE_DOUBLE, DB_TYPE_FLOAT, DB_TYPE_INTEGER, DB_TYPE_BIGINT, DB_TYPE_SHORT, DB_TYPE_DATE, DB_TYPE_TIME, DB_TYPE_TIMESTAMP, DB_TYPE_DATETIME, DB_TYPE_MONETARY 에 대한 분기를 ENABLE_UNUSED_FUNCTION 에 두고 있지만, 그 분기는 현재 빌드 에서 도달할 수 없다. ehash_create_helper 첫머리의 assert 가 다른 어떤 키 타입도 막기 때문이다.
긴 문자열 overflow. 마찬가지로 ENABLE_UNUSED_FUNCTION 게이트 아래에 있다. EHASH_DIR_HEADER::overflow_file 필드 는 VFID_NULL 로 초기화된 채 현재 빌드에서는 채워지지 않는 다. 클래스 이름조차도 그렇다 — ehash_insert_helper 안의 assert (strlen ((char *) key_p) < 256) 이 문자열 키를 256 바이트로 막아 두며, 긴 문자열 코드 경로는 dead code 다.
xehash_destroy (extendible_hash.c:1259) 는 임시 해시 파일에만 동작한다 (file_destroy (…, true) 를 쓴다). 영속 파일은 더 위 계층에서 디렉토리와 버킷 VFID 에 대한 file_destroy 로 간접 삭제된다 (예 — 데이터베이스 wipe 도 중 클래스 이름 테이블이 DROP TABLE 경로로 지워지는 식).
MULTI_VERSION 통합 없음. Extendible hash 는 pre-MVCC 다. 버전 사슬도 없고, MVCC 가시성 필터도 없으며, BTREE_OP_PURPOSE 류의 enum 도 없다. 동시 가시성은 더 위 계층에서 강제된다. 호출 자리가 lock_manager.c 의 디렉토 리 단위 lock 으로 클래스 이름 변경을 직렬화한다.

소스 코드 가이드

anchor 는 심볼명이다. 라인 번호는 updated: 시점에만 유 효하며, 시간이 지나면 흘러간다.

헤더 타입과 레이아웃

EHID (storage_common.h) — 12-byte 공개 핸들 { VFID vfid; INT32 pageid }.
EH_SEARCH (storage_common.h) — ehash_search 의 반환 타 입 (EH_KEY_FOUND, EH_KEY_NOTFOUND, EH_ERROR_OCCURRED).
EHASH_DIR_HEADER (extendible_hash.c) — 디렉토리 루트 페 이지 헤더.
EHASH_DIR_RECORD (extendible_hash.c) — VPID 한 개를 들 고 있는 디렉토리 엔트리.
EHASH_BUCKET_HEADER (extendible_hash.c) — 슬롯 0 의 1 바이트짜리 헤더 (local depth).
EHASH_REPETITION (extendible_hash.c) — RVEH_CONNECT_BUCKET 의 (VPID, count) 페이로드.
EHASH_HASH_KEY (extendible_hash.c) — unsigned int 의 사 키 타입.
EHASH_RESULT enum (extendible_hash.c) — 내부 반환 코드 (SUCCESSFUL_COMPLETION, BUCKET_FULL, BUCKET_UNDERFLOW, BUCKET_EMPTY, FULL_SIBLING_BUCKET, NO_SIBLING_BUCKET, ERROR_OCCURRED).
GETBITS, FIND_OFFSET, GETBIT, SETBIT, CLEARBIT (extendible_hash.c) — 비트 조작 매크로.
EHASH_OVERFLOW_THRESHOLD, EHASH_UNDERFLOW_THRESHOLD, EHASH_DIR_HEADER_SIZE, EHASH_NUM_FIRST_PAGES, EHASH_NUM_NON_FIRST_PAGES, EHASH_HASH_KEY_BITS (extendible_hash.c) — 페이지 기하 상수.
RVEH_* 복구 인덱스 (transaction/recovery.h) — 8 개 레코 드 패밀리.

공개 API

xehash_create (extendible_hash.c) — 영속 / 임시 해시 파 일의 생성자.
xehash_destroy (extendible_hash.c) — 임시 해시 파일 전 용 destructor.
ehash_search (extendible_hash.c) — point lookup.
ehash_insert (extendible_hash.c) — upsert.
ehash_delete (extendible_hash.c) — point delete.
ehash_map (extendible_hash.c) — full-scan apply.
ehash_dump, ehash_print_bucket, ehash_dump_bucket (extendible_hash.c) — 디버그 dumper.

주소 변환

ehash_dir_locate (extendible_hash.c) — 디렉토리 인덱스 → (페이지 번호, offset) 변환기.
ehash_find_bucket_vpid (extendible_hash.c) — 디렉토리 헤 더와 엔트리 인덱스가 주어지면 버킷 VPID 를 돌려 준다.
ehash_find_bucket_vpid_with_hash (extendible_hash.c) — hash-then-locate 편의 wrapper. 세 CRUD 가 모두 사용한다.
ehash_fix_old_page, ehash_fix_ehid_page, ehash_fix_nth_page (extendible_hash.c) — PAGE_EHASH ptype 체크가 들어 있는 페이지 버퍼 fix wrapper.

해시 함수

ehash_hash (extendible_hash.c) — 타입 분기 진입점.
ehash_hash_string_type (extendible_hash.c) — folding + mht_*strhash 삼중 패스.
ehash_hash_eight_bytes_type (extendible_hash.c) — OID 인지 folding.
ehash_get_pseudo_key (extendible_hash.c) — 버킷에서 추 출한 레코드를 다시 해시 (split 도중 사용).

버킷 페이지 연산

ehash_initialize_bucket_new_page (extendible_hash.c) — file_alloc 의 page-init 콜백.
ehash_compose_record (extendible_hash.c) — (OID, key) 를 RECDES 에 패킹.
ehash_write_key_to_record (extendible_hash.c) — 키 바이 트를 타입별로 복사.
ehash_compare_key (extendible_hash.c) — 타입 분기 3-way compare.
ehash_binary_search_bucket (extendible_hash.c) — 슬롯 페이지 안의 log-N search.
ehash_locate_slot (extendible_hash.c) — 빈 버킷 edge 까 지 처리하는 wrapper.
ehash_get_key_size (extendible_hash.c) — 고정 크기 키 타 입.

Insert 경로

ehash_insert_helper (extendible_hash.c) — S→X promotion 을 포함한 최상위 오케스트레이터.
ehash_insert_to_bucket (extendible_hash.c) — 직선 insert; RVEH_INSERT undo+redo 발행.
ehash_insert_to_bucket_after_create (extendible_hash.c) — 디렉토리 엔트리가 NULL 일 때의 버킷 생성.
ehash_insert_bucket_after_extend_if_need (extendible_hash.c) — 버킷 가득 참 시점의 split 호출.
ehash_extend_bucket (extendible_hash.c) — sysop 아래에 서의 split + (필요 시) 디렉토리 더블링 오케스트레이터.
ehash_split_bucket (extendible_hash.c) — 물리적 버킷 split (sibling 할당, 레코드 분배).
ehash_find_first_bit_position (extendible_hash.c) — 레 코드를 실제로 분리해 주는 가장 작은 local-depth bump.
ehash_distribute_records_into_two_bucket (extendible_hash.c) — 슬롯 단위 sibling 이동.
ehash_expand_directory (extendible_hash.c) — 새 페이지 할당까지 포함한 디렉토리 더블링.
ehash_initialize_dir_new_page (extendible_hash.c) — 새 디렉토리 페이지의 init 콜백.

Delete 경로

ehash_delete (extendible_hash.c) — 공개 delete.
ehash_check_merge_possible (extendible_hash.c) — merge 가능성 검사 (sibling 이 존재, 같은 depth, 자리 있음).
ehash_merge (extendible_hash.c) — 재검증 후 merge 수행.
ehash_merge_permanent (extendible_hash.c) — sibling 으 로의 물리적 레코드 이동.
ehash_find_depth (extendible_hash.c) — merge 후 새 local depth 를 디렉토리 주변에서 유도.
ehash_shrink_directory_if_need (extendible_hash.c) — 히 스토그램 트리거 (> 1 slack).
ehash_shrink_directory (extendible_hash.c) — 디렉토리 절반화 (또는 4×, 8×, …) 와 페이지 dealloc.

디렉토리 포인터 유지

ehash_connect_bucket (extendible_hash.c) — 디렉토리 엔 트리 범위를 한 VPID 로 다시 쓰기; RVEH_CONNECT_BUCKET 발 행.
ehash_adjust_local_depth (extendible_hash.c) — local_depth_count[depth] 에 delta 적용; RVEH_INC_COUNTER 발행.

복구 핸들러

ehash_rv_init_bucket_redo (extendible_hash.c) — RVEH_INIT_BUCKET redo.
ehash_rv_init_dir_redo (extendible_hash.c) — RVEH_INIT_DIR redo.
ehash_rv_init_dir_new_page_redo (extendible_hash.c) — RVEH_INIT_NEW_DIR_PAGE redo.
ehash_rv_insert_redo / ehash_rv_insert_undo (extendible_hash.c) — RVEH_INSERT (physical redo, logical undo).
ehash_rv_delete_redo / ehash_rv_delete_undo (extendible_hash.c) — RVEH_DELETE (physical redo, logical undo).
ehash_rv_delete (extendible_hash.c) — _rv_insert_undo 가 사용하는 내부 logical delete; merge 조건을 검사하지 않고 undo 도 logging 하지 않는다 (compensating redo CLR 만 발 행).
ehash_rv_increment (extendible_hash.c) — RVEH_INC_COUNTER.
ehash_rv_connect_bucket_redo (extendible_hash.c) — RVEH_CONNECT_BUCKET.
transaction/recovery.c:415-452 의 RV_fun[] 등록.

직렬화

or_pack_ehid / or_unpack_ehid (object_representation.c) — 12-byte EHID 디스크 포맷.
OR_GET_EHID / OR_PUT_EHID (object_representation.h) — 바이트 단위 primitive codec.
ehash_read_oid_from_record / ehash_write_oid_to_record (extendible_hash.c) — 버킷 레코드 안 OID 바이트 순서.
ehash_read_ehid_from_record / ehash_write_ehid_to_record (extendible_hash.c) — 로그 레코드용 EHID 페이로드 codec.

이 개정 시점의 위치 힌트 (2026-04-30)

심볼	파일	라인
`EHID` (struct)	`storage_common.h`	212
`EH_SEARCH` (enum)	`storage_common.h`	381
`OR_EHID_SIZE`	`object_representation_constants.h`	87
`EHASH_HASH_KEY` (typedef)	`extendible_hash.c`	99
`EHASH_DIR_HEADER` (struct)	`extendible_hash.c`	103
`EHASH_DIR_RECORD` (struct)	`extendible_hash.c`	120
`EHASH_BUCKET_HEADER` (struct)	`extendible_hash.c`	127
`EHASH_RESULT` (enum)	`extendible_hash.c`	132
`EHASH_REPETITION` (struct)	`extendible_hash.c`	144
`GETBITS` / `FIND_OFFSET` (macros)	`extendible_hash.c`	193
`ehash_dir_locate`	`extendible_hash.c`	384
`ehash_initialize_bucket_new_page`	`extendible_hash.c`	628
`ehash_initialize_dir_new_page`	`extendible_hash.c`	712
`ehash_rv_init_dir_new_page_redo`	`extendible_hash.c`	735
`xehash_create`	`extendible_hash.c`	866
`ehash_get_key_size`	`extendible_hash.c`	879
`ehash_create_helper`	`extendible_hash.c`	954
`ehash_fix_old_page`	`extendible_hash.c`	1188
`ehash_fix_ehid_page`	`extendible_hash.c`	1218
`ehash_fix_nth_page`	`extendible_hash.c`	1236
`xehash_destroy`	`extendible_hash.c`	1259
`ehash_find_bucket_vpid`	`extendible_hash.c`	1295
`ehash_find_bucket_vpid_with_hash`	`extendible_hash.c`	1327
`ehash_search`	`extendible_hash.c`	1379
`ehash_insert`	`extendible_hash.c`	1461
`ehash_insert_to_bucket_after_create`	`extendible_hash.c`	1472
`ehash_extend_bucket`	`extendible_hash.c`	1546
`ehash_insert_bucket_after_extend_if_need`	`extendible_hash.c`	1641
`ehash_insert_helper`	`extendible_hash.c`	1715
`ehash_insert_to_bucket`	`extendible_hash.c`	1837
`ehash_compose_record`	`extendible_hash.c`	2172
`ehash_compare_key`	`extendible_hash.c`	2223
`ehash_binary_search_bucket`	`extendible_hash.c`	2401
`ehash_locate_slot`	`extendible_hash.c`	2479
`ehash_get_pseudo_key`	`extendible_hash.c`	2509
`ehash_find_first_bit_position`	`extendible_hash.c`	2545
`ehash_distribute_records_into_two_bucket`	`extendible_hash.c`	2605
`ehash_split_bucket`	`extendible_hash.c`	2684
`ehash_expand_directory`	`extendible_hash.c`	2792
`ehash_connect_bucket`	`extendible_hash.c`	3067
`ehash_find_depth`	`extendible_hash.c`	3183
`ehash_check_merge_possible`	`extendible_hash.c`	3274
`ehash_delete`	`extendible_hash.c`	3418
`ehash_shrink_directory_if_need`	`extendible_hash.c`	3615
`ehash_adjust_local_depth`	`extendible_hash.c`	3633
`ehash_merge_permanent`	`extendible_hash.c`	3655
`ehash_merge`	`extendible_hash.c`	3771
`ehash_shrink_directory`	`extendible_hash.c`	3982
`ehash_hash_string_type`	`extendible_hash.c`	4156
`ehash_hash_eight_bytes_type`	`extendible_hash.c`	4244
`ehash_hash`	`extendible_hash.c`	4347
`ehash_apply_each`	`extendible_hash.c`	4395
`ehash_map`	`extendible_hash.c`	4518
`ehash_dump`	`extendible_hash.c`	4598
`ehash_rv_init_bucket_redo`	`extendible_hash.c`	5023
`ehash_rv_init_dir_redo`	`extendible_hash.c`	5072
`ehash_rv_insert_redo`	`extendible_hash.c`	5089
`ehash_rv_insert_undo`	`extendible_hash.c`	5126
`ehash_rv_delete_redo`	`extendible_hash.c`	5181
`ehash_rv_delete_undo`	`extendible_hash.c`	5220
`ehash_rv_delete`	`extendible_hash.c`	5293
`ehash_rv_increment`	`extendible_hash.c`	5405
`ehash_rv_connect_bucket_redo`	`extendible_hash.c`	5429
`RVEH_REPLACE … RVEH_INIT_NEW_DIR_PAGE`	`transaction/recovery.h`	105-112
`RV_fun[]` ehash entries	`transaction/recovery.c`	415-452
`xehash_create` (boot, classname_table)	`transaction/boot_sr.c`	5001
`xehash_create` (catalog rep dir)	`storage/system_catalog.c`	2635
`ehash_delete` (catalog rep dir)	`storage/system_catalog.c`	2230
`qexec_init_upddel_ehash_files`	`query/query_executor.c`	9822
`qexec_destroy_upddel_ehash_files`	`query/query_executor.c`	9875
`qexec_upddel_add_unique_oid_to_ehid`	`query/query_executor.c`	1015

소스 검증 (2026-04-30 기준)

소스 트리를 가로지르는 grep (grep -rn "ehash_\|EHID\|xehash_ src/) 이 §CUBRID 안에서의 사용처” 에서 나열한 네 자리를 그대로 확인해 준다.

boot_sr.c: boot_Db_parm->classname_table 이 데이터베이스 부팅 시점에 만들어지는 유일한 영속 EHID 다. lookup 은 결국 ehash_search 를 호출하는 locator_* wrapper 를 거친다.
system_catalog.c: 카탈로그 representation 디렉토리가 서버 시작 시점에 만들어진다. DROP CLASS 는 ehash_delete 를 부른다.
query_executor.c: UPDATE/DELETE OID 중복 제거를 위한 임시 EHID. is_tmp=true 라서 logging 이 억제된다.
query_hash_scan.c: 디렉토리 파일 형식만 다시 쓰고, 버킷 로 직은 자체 구현이다.

공개 API 만 보면 그럴 법해 보이지만 사실은 extendible hashing 을 쓰지 않는 서브시스템도 있다.

사용자 인덱스. CREATE INDEX … USING HASH 는 파싱조차 되지 않는다. 사용자 인덱스는 항상 B+Tree (btree.c) 다.
Unique 제약 위반 추적. 문서 brief 의 힌트와 달리, 현재 btree_unique plumbing 은 extendible_hash.c 까지 닿지 않 는다. btree.c 의 unique 제약 강제 경로 (btree_find_oid_and_its_page, BTREE_NEED_UNIQUE_CHECK) 와 글로벌 통계표 (btree_unique_stats, GLOBAL_UNIQUE_STATS_TABLE) 는 모두 B+Tree 서브시스템 안에 서 닫혀 있다 — btree.c 또는 btree_unique.{cpp,hpp} 안에 ehash_* 호출은 등장하지 않는다.
representation 디렉토리 너머의 카탈로그 스캔 / 카탈로그 이름 lookup. 카탈로그 테이블은 heap 으로 저장되고 B+Tree 로 접근된다. extendible hash 를 쓰는 자리는 rep-id 디렉토 리 뿐이다.

구현에는 ENABLE_UNUSED_FUNCTION 으로 막힌 코드가 상당량 있 다 (긴 문자열 overflow, 다중 바이트 숫자 키 타입, 버킷 안 정 렬 fallback 등). 그 어떤 분기도 현재 빌드에서 도달할 수 없다 — ehash_create_helper 의 assert 와 ehash_insert_helper 의 키 길이 cap 이 적극적으로 막아 두기 때문이다. 더 넓은 키 지원 이나 oversized 키가 필요한 미래 변경은 그 경로를 부활시키고 (또 다시 검증해야) 할 것이다.

버킷 레코드의 디스크 위 헤더는 (OID, key_bytes) — OID 가 먼저, 키가 그 뒤다. B+Tree 리프 레코드가 키 → OID 순서인 것과 다르다. 이유는 단순하다 — extendible hash 레코드는 버킷 안에서 키로 물리 정렬되어 있지만 (binary search 가 키 우선 비 교), 레코드 페이로드 는 호출자에게 키보다 값을 먼저 돌려준 다. ehash_search 의 호출자는 OID 만 필요로 하고, ehash_read_oid_from_record 가 가변 길이 키를 스캔하지 않고 OID 를 바로 읽을 수 있다.

ehash_create_helper 의 docstring 은 “이 함수는 이 볼륨에 두 파일을 만든다 — 디렉토리용 한 개와 버킷용 한 개” 라고 적고 있다. 그러나 사실은 — 버킷 파일의 volid 는 ehid->vfid.volid 에서 오고, 디렉토리의 volid 에서 오지 않는다. 버킷 파일이 만들어지는 시점에는 디렉토리의 VFID 가 아직 정해져 있지 않기 때문이다 (bucket_vfid.volid = ehid_p->vfid.volid; 가 file_create_ehash_dir 보다 먼저 실행된다). 두 파일이 결국 같은 볼륨에 자리 잡는 이유는, 디렉토리 파일 생성이 나중에 dir_vfid.volid = bucket_vfid.volid 로 맞춰 주기 때문이다. 결과는 옳지만, 읽는 순서가 살짝 직관에 어긋난다.

ehash_get_key_size 는 DB_TYPE_STRING 인 경우 키 길이가 아 니라 1 을 돌려준다. 문자열 키는 길이가 레코드별로 가변이기 때문이다. 이 값은 sentinel 이고, 호출자는 key_type == DB_TYPE_STRING 을 따로 검사해서 size 계산을 우 회한다.

미해결 질문

카탈로그 lookup 을 위해 PG 스타일 버킷별 overflow 사슬 을 추가할 만한가? CUBRID 의 버킷 크기는 한 페이지다. 어 떤 비정상적인 해시 충돌이 한 해시 주소에 한 페이지를 넘는 레코드를 몰아넣으면, 구현은 local depth 가 충분히 커질 때 까지 재귀적으로 split 하는 식으로 풀어 낸다. 32-bit 의사 키와 mht_*strhash 에서 충돌 공간은 경험적으로 작지만, 극 단적인 클래스 명명 규약 — 모든 클래스가 같은 8자 prefix 로 시작하는 식 — 이라면 원리상 주소 깊이를 다 써 버릴 수도 있 다. PostgreSQL 의 버킷별 overflow 사슬은 이 경우를 디렉토 리 더블링 대신 한 버킷에 긴 사슬을 받아들이는 방식으로 풀 어 낸다. 조사할 거리 — 수천 개 클래스를 가진 실제 CUBRID 배포에서 관찰되는 global-depth 값은 어느 범위인가?
왜 슬롯 0 에 버킷 헤더를 두는가. 슬롯 페이지의 슬롯 0 을 EHASH_BUCKET_HEADER 로 쓰는 선택은 흔치 않다. 페이지 헤더 영역을 따로 잡는 일반적인 방식과 다르기 때문이다. 가 능한 이유는, heap 페이지 슬롯 기계 (spage_initialize, spage_get_record, spage_insert) 를 별도의 “ehash 페이 지” 페이지 버퍼 통합 없이 그대로 다시 쓰려는 것이었을 가능 성이다. 비용은 페이지당 1 바이트짜리 슬롯-0 레코드 오버헤 드다. 검증할 거리 — 버킷을 슬롯 1 부터 스캔하면서 헤더가 페이지 헤더 영역에 있다고 가정하는 코드 경로가 단 하나라도 있는가?
디렉토리에 낙관적 S 래치를 잡을 때의 동시 split 정확 성. ehash_insert_helper 는 디렉토리 루트에 S 래치를 잡 고 버킷 가득 참을 발견한 뒤 풀고 X 로 다시 잡는다. 그 release 와 X fix 사이에 다른 스레드가 같은 버킷을 split 했 을 수 있다. X-fixed 후 다시 시도하는 insert 는 이번에는 가 득 차지 않은 버킷을 보고, BUCKET_FULL 분기는 타지 않으 며, 두 번째 split 없이 insert 가 성공한다. 모든 경우에 양 성 (benign) 인가, 아니면 (디렉토리 상태가 바뀐 뒤의) 새 해시 위치가 첫 패스의 ehash_find_bucket_vpid_with_hash 가 계산한 위치와 다른 창이 있는가? 재귀 호출이 위에서부터 다시 시작하므로 버킷 을 다시 해석할 텐데, ehash_find_bucket_vpid_with_hash 안 의 코멘트가 안전성 속성을 명시적으로 적어 두지는 않았다.
왜 EHASH_OVERFLOW_RATE = 0.9, EHASH_UNDERFLOW_RATE = 0.4 인가? 0.9 / 0.4 의 분리는 의도적으로 보인다 (그 간격이 진동을 막는다). 그러나 구체적인 값은 매개변수화되 지 않았고 코멘트도 없다. 경험적인 워크로드 튜닝의 결과인 지, 아니면 어떤 교과서 참조에서 물려받은 값인지 분명하지 않다.
Logical-undo 와 physical-undo: split-undo 가 이전의 merge 를 알아야 하는 경우는 언제인가? split 경로는 system op 안에서 버킷과 sibling 의 페이지 이미지 (physical) 를 로깅한다. 한 트랜잭션이 insert (split 유발), delete (sibling 을 다시 버킷으로 merge 유발), abort 의 순 서로 진행하면, undo 는 먼저 delete-undo (즉 logical re-insert) 를 replay 하고, 그 다음 split-undo (즉 pre-split 버킷 이미지 복원) 를 replay 한다. 그 순서가 일관된 상태를 만드는가? 아니면 코드에 보이지 않는 system-op 순서 제약이 따로 있는가?
왜 RVEH_CONNECT_BUCKET 이 paired undo+redo 가 아니라 undoredo 로 logging 되는가? 이 단일 레코드는 페이지의 before-image (bef_length 바이트) 와 after-payload (EHASH_REPETITION) 를 함께 들고 다닌다. 그래서 undo 핸들 러는 repetition 을 distinct VPID 리스트로 역산할 줄 알아야 할 텐데 — ehash_rv_connect_bucket_redo 는 그렇게 하지 않는다. 둘 중 하나다 — undo 경로가 실제로 bef_length 바 이트를 그대로 replay 하거나 (“physical undo, structured redo”), 아니면 핸들러가 빠져 있거나. 추적 경로 — RVEH_CONNECT_BUCKET 의 RV_fun[] 엔트리를 읽어서, 별도 의 undo 함수가 등록되어 있는지 아니면 log_rv_copy_char 가 generic page-image-replay undo 로 쓰이고 있는지 확인.
왜 영속 파일에 대한 ehash_destroy 가 없는가? xehash_destroy 는 임시 파일만 처리한다. 영속 클래스 이름 테이블은 개별적으로 destroy 되지 않는다 — 데이터베이스 수 명을 같이하며, 볼륨이 drop 될 때 데이터베이스와 함께 회수 된다. 미래에 영속 extendible hash 파일을 destroy 해야 하는 기능 — 데이터베이스 단위의 온라인 스키마 rename 같은 — 이 생긴다면 영속 파일용 변형이 필요할 것이다. 현재의 모양은 그런 요구가 아직 떠오르지 않았다는 뜻이다.

CUBRID 너머 — 비교 설계와 연구 동향

분석이 아닌 포인터 (pointers).

PostgreSQL pg_class 또는 pg_amop 가 아니라, PG 의 hash index 가 같은 도식이다. 차이는 PG 가 사용자에게 hash 인덱스를 노출한다는 점이다. CUBRID 은 같은 자료 구조 를 내부에서만 쓴다. PG 의 사용자 노출이 워크로드 다변화의 여지를 열어 두지만, B+Tree 가 우세인 점은 두 엔진 모두 마 찬가지다.
Linear hashing — Litwin (1980). 한 번에 한 버킷-split 의 대안 도식이다. PG 9.x 까지의 hash 인덱스가 linear 였다. 한 번에 한쪽으로만 자라기 때문에 디렉토리 더블링이 없는 대 신, 분포가 skewed 되면 일부 버킷이 비대해진다. CUBRID 의 extendible 선택은 넘친 그 버킷 만 split 한다는 점에서 더 워크로드 적응적이다.
Bw-Tree / hash 변형 — 페이지 id 매핑 테이블 + delta 사 슬을 쓰는 lock-free 도식이다. CUBRID 의 in-place 갱신 + 페 이지 래치는 그 반대 방향의 설계점이다. CUBRID 의 단순성 (system op 으로 묶인 짧은 critical section) 이 분석을 단순 하게 만들지만, scale-out 워크로드에서는 lock-free 변형이 유리할 수 있다.
Cuckoo hashing — point lookup 의 또 다른 대안이다. 워 스트 케이스가 보장된 상수 시간 lookup 이지만, insert 시 잦 은 cuckoo eviction 을 견뎌야 하고 디스크 워크로드에는 잘 맞지 않는다. CUBRID 처럼 “point lookup 이 우세이지만 insert 도 견뎌야” 하는 워크로드에는 extendible 이 더 자연 스럽다.
Robin Hood / Hopscotch hashing — 충돌이 잦을 때의 메모 리 안 변형이다. CUBRID 은 디스크 페이지가 단위라 변형의 동 기 자체가 다르다. 메모리 안 hash list scan 측에서는 도입을 검토할 만하다.
Persistent memory hash (예 — Level Hashing, CCEH) — NVRAM 의 등장으로 떠오른 변형들이다. CUBRID 의 디스크 + buffer pool 모델은 persistent memory 위에서도 그대로 동작 하지만, persistent-memory 특화 변형이 latency 면에서 분명히 유리하다. 미래 작업의 방향이다.
메모리 안 hash list / hash set 의 데이터 분배 — CUBRID 의 query_hash_scan.c 가 디렉토리 형식만 다시 쓰는 자리 다. HASH-LIST-SCAN 이 외부 정렬 대신 해시 분배를 쓰는 패턴 은 column-oriented OLAP 엔진 (DuckDB, ClickHouse) 에서도 표준이다. CUBRID 의 재사용은 서로 다른 layer 사이에서 design reuse 가 잘 들어맞는 좋은 예다.

출처

형제 문서

knowledge/code-analysis/cubrid/cubrid-btree.md — 사용자 인덱스가 쓰는 디스크 위 인덱스. 같은 WAL / 페이지 버퍼 substrate, 다른 access 패턴.
knowledge/code-analysis/cubrid/cubrid-page-buffer-manager.md — 모든 ehash 루틴이 쓰는 pgbuf_fix, PGBUF_LATCH_READ / PGBUF_LATCH_WRITE, pgbuf_set_dirty 규율.
knowledge/code-analysis/cubrid/cubrid-heap-manager.md — 버킷 페이지가 다시 쓰는 슬롯 페이지 substrate.
knowledge/code-analysis/cubrid/cubrid-log-manager.md — log_append_undoredo_data2, system-op, 그리고 RV_fun[] 복구 dispatch 표.
knowledge/code-analysis/cubrid/cubrid-recovery-manager.md — RVEH_* 레코드를 소비하는 redo / undo 패스.
knowledge/code-analysis/cubrid/cubrid-catalog-manager.md — rep-id 디렉토리의 호출자.

교재 챕터 (`knowledge/research/dbms-general/`)

Database Internals (Petrov), 7장 §Hash Files — global vs local depth 모델.
Fagin, Nievergelt, Pippenger, Strong, Extendible Hashing — A Fast Access Method for Dynamic Files, ACM TODS 4(3), 1979 — 원전.
Litwin, Linear Hashing: A New Tool for File and Table Addressing, VLDB 1980 — 대안.

CUBRID 소스 (`/data/hgryoo/references/cubrid/`)

src/storage/extendible_hash.c — 구현.
src/storage/extendible_hash.h — 공개 API.
src/storage/storage_common.h — EHID, EH_SEARCH.
src/storage/system_catalog.c, system_catalog.h — 카탈 로그 rep-id 디렉토리 호출자.
src/transaction/boot_sr.c — 클래스 이름 테이블 호출자이 자 데이터베이스 부팅 시점의 생성자.
src/transaction/recovery.h, recovery.c — RVEH_* 코드 와 RV_fun[] 등록.
src/query/query_executor.c — UPDATE/DELETE OID 중복 제거 호출자 (qexec_init_upddel_ehash_files, qexec_upddel_add_unique_oid_to_ehid).
src/query/query_hash_scan.{c,h} — HASH-LIST-SCAN / HASH-SET-SCAN 을 위한 디렉토리 파일 재사용.
src/base/object_representation.c, object_representation.h, object_representation_constants.h — or_pack_ehid / OR_EHID_* codec.
src/storage/file_manager.c, file_manager.h — file_create_ehash, file_create_ehash_dir, FILE_EHASH_DES.