(KO) PostgreSQL 동적 해시 테이블(dynahash) — Larson 선형 해싱, 파티션 공유 해시, simplehash 템플릿
목차
이론적 배경
섹션 제목: “이론적 배경”해시 테이블은 키를 값에 대응시키는 정준 연관 자료구조다. 키를 작은 정수(해시값)로 줄여 버킷 배열을 인덱싱하면 기대 O(1) 시간을 얻는다. Database System Concepts(Silberschatz 7e, ch. 14 “Indexing”)는 모든 해시 테이블이 해결해야 할 두 가지 설계 축을 정의한다. 충돌 해결 — 서로 다른 키가 같은 버킷에 떨어질 때 무엇을 하는가 — 과 크기 조정 — 테이블이 차서 평균 체인 길이(적재율)가 O(1) 한계를 넘을 때 어떻게 하는가다.
충돌 해결에는 두 계열이 있으며, 이 문서 전체의 구조를 이 두 계열이 결정한다.
- 분리 체이닝(separate chaining). 각 버킷이 같은 버킷으로 해시된 항목들의 연결 리스트 헤드를 가진다. 충돌은 리스트에 추가된다. 항목은 할당자가 놓은 곳에 있고 버킷 배열은 포인터만 보관한다. 결정적 성질은 항목의 주소가 그 항목의 수명 동안 변하지 않는다는 것이다. 다른 항목을 삽입하거나 삭제해도 이 항목이 이동하지 않으므로, 호출자는 다른 작업에 걸쳐 해시 테이블 내부 포인터를 안전하게 보관할 수 있다.
- 오픈 어드레싱(open addressing). 모든 항목이 버킷 배열 내부에 산다. 충돌 시 삽입은 빈 슬롯을 찾아 결정론적 순서로 탐침한다. 항목별 할당이 없고 포인터 추적도 없으므로 구조 전체가 밀집해 CPU 캐시에 친화적이다. 대신 탐침, 삭제 압축, 크기 조정 과정에서 항목이 이동하므로 호출자가 안정 포인터를 가질 수 없고 삭제가 까다롭다(전통적으로 묘비 슬롯이 필요하다).
크기 조정의 단순한 답 — 두 배 크기의 새 배열을 할당해 모든 항목을 리해시 — 은 테이블이 두 배가 될 때마다 O(N) stop-the-world 중단을 일으킨다. 크기 예측이 어려운 장수(long-lived) 테이블에는 상각 비용이 수용 가능하더라도 중단 자체가 바람직하지 않고, 재할당 불가능한 고정 공유 메모리 영역에 사는 해시 테이블에는 제자리 배열 두 배화가 아예 불가능하다. 매끄러운 성장의 고전적 답은 Per-Åke Larson의 “Dynamic Hash Tables”(CACM 31(4), April 1988, pp. 446-457)다. dynahash.c 상단의 역사 주석이 이 논문을 이름으로 인용한다. Larson의 방식(Litwin 선형 해싱의 개선)은 테이블을 한 번에 하나의 버킷씩 키운다. “다음 분할할 버킷” 포인터를 유지하고, 확장 단계마다 정확히 그 버킷 하나를 분할해 거기 살던 소수의 항목만 두 버킷으로 재배분한다. 버킷→해시 대응은 두 마스크를 사용한다. low_mask는 테이블 하반부, high_mask는 전체를 커버하며, 넓은 마스크로 매핑한 버킷이 아직 분할되지 않았으면 좁은 마스크로 접는다. 따라서 테이블은 모든 것을 리해시하는 중단 없이 연속적으로 성장하고, 삽입당 최대 작업량은 제한된다.
두 가지 요구사항이 교과서적 해싱이 아닌 PostgreSQL의 시스템 맥락에서 온다.
- 공유 메모리와 탐색 가능성. 다중 프로세스 서버는 여러 백엔드가 공유하는 해시 테이블을 필요로 한다. 해당 테이블은 서버 시작 시 고정 공유 메모리 영역에서 할당되어야 하고, 모든 프로세스에서 동일한 주소로 접근 가능해야 하며, 자신을 만들지 않은 백엔드도 이름으로 찾을 수 있어야 한다.
- 전역 락 없는 동시성. 뜨거운 공유 테이블(버퍼 조회 테이블, 락 테이블) 위의 단일 락은 모든 백엔드를 직렬화한다. 자료구조는 독립적으로 잠글 수 있는 파티션으로 분할을 지원해야 다른 파티션의 작업이 병렬로 진행될 수 있다.
이 두 요구사항은 분리 체이닝(안정 포인터가 이웃 버킷 분할을 거쳐 유효하고, 다른 파티션의 체인이 서로 간섭하지 않는다)과 Larson의 디렉터리-세그먼트 레이아웃(절대 이동하지 않는 고정 디렉터리, 런타임에는 세그먼트 할당만 일어난다)을 강하게 가리킨다. 이것이 dynahash가 구현하는 설계다. 반대 경우 — 로컬, 단일 스레드, 공유 메모리 불필요, 파티셔닝 불필요, 안정 포인터 불필요 — 는 별도 구조(simplehash.h)가 담당하며, 이 두 구조의 대비가 이 문서의 일관된 주제다.
DBMS 공통 설계
섹션 제목: “DBMS 공통 설계”모든 데이터베이스 엔진은 인메모리 해시 테이블의 소동물원을 쌓는다. 버퍼 풀 조회(페이지 식별자 → 프레임), 락 테이블(락 태그 → 락 객체), 카탈로그/릴레이션 캐시, 플랜·준비문 캐시, 쿼리별 그루핑·해시 조인 테이블이 그 예다. 이 테이블들이 어떻게 만들어지는지에 대한 반복되는 관례 집합으로 수렴한다. 그 관례를 먼저 이름 붙이면, 다음 절의 PostgreSQL 심벌들이 공유된 설계 공간 안의 선택지로 읽힌다.
두 해시 테이블, 하나가 아니라
섹션 제목: “두 해시 테이블, 하나가 아니라”성숙한 엔진은 거의 항상 두 가지 해시 테이블 시설을 내장한다. 요구사항이 서로 반대 방향을 당기기 때문이다.
- 범용, 공유 가능 테이블 — 분리 체이닝, 안정 항목 주소, 공유 메모리 거주 가능, 파티션 잠금. 이것이 버퍼 풀과 락 매니저가 필요로 하는 것이다. 여러 프로세스, 다른 코드가 가리키는 장수 항목, 동시성.
- 특화, 로컬, 빠른 테이블 — 오픈 어드레싱, 캐시 밀집, 컴파일 타임 타입 특화, 간접 호출 없음. 이것이 해시 집계나 해시 조인이 하나의 백엔드 안에서 하나의 실행자 노드 내부에서 필요로 하는 것이다. 초당 수백만 건 탐침, 공유 없음, 안정 포인터 요구 없음, 쿼리 끝에 전체 폐기.
dynahash가 첫 번째이고 simplehash가 두 번째다. CUBRID도 범용 mht_* 메모리 해시 테이블과 특화 인라인 구조 사이에 비슷한 분리를 둔다.
부드러운 성장을 위한 디렉터리 + 세그먼트
섹션 제목: “부드러운 성장을 위한 디렉터리 + 세그먼트”공유 가능 테이블은 모놀리식 버킷 배열을 거의 항상 피한다. 표준 레이아웃은 2단계다. 포인터들의 고정 크기 디렉터리, 각 항목이 세그먼트(버킷 헤더들의 연속 구간)를 가리킨다. 성장은 새 세그먼트를 할당하고 (필요하면) 더 큰 디렉터리를 할당한다. 기존 세그먼트는 이동하지 않는다. 이것이 Larson 방식의 한 버킷씩 확장을 공유 메모리와 호환되게 만드는 이유다. 공유 테이블에서 디렉터리는 한 번 크기가 정해지면 (고정 주소를 유지해야 하므로) 런타임에는 세그먼트 할당만 일어난다.
flowchart LR
subgraph dir["디렉터리 (dsize 항목)"]
d0["dir[0]"]
d1["dir[1]"]
d2["dir[2]"]
dn["dir[...]"]
end
subgraph seg0["세그먼트 0 (ssize 버킷 헤더)"]
b0["버킷 0 -> HASHELEMENT -> HASHELEMENT -> NULL"]
b1["버킷 1 -> NULL"]
bk["버킷 ssize-1 -> HASHELEMENT -> NULL"]
end
subgraph seg1["세그먼트 1"]
c0["버킷 ssize -> HASHELEMENT -> NULL"]
ck["..."]
end
d0 --> seg0
d1 --> seg1
d2 --> dn
버킷 번호는 세그먼트 크기로 시프트하고 마스크해 (segment_num, segment_ndx)로 분해된다. 가상 주소가 페이지와 오프셋으로 분해되는 것과 정확히 같은 방식이다.
항목 내장 키와 캐시된 해시값
섹션 제목: “항목 내장 키와 캐시된 해시값”범용 테이블은 각 항목을 작은 고정 헤더(체인의 다음 포인터 + 캐시된 해시값) 뒤에 호출자의 키-데이터 페이로드가 바로 붙는 구조로 저장한다. 캐시된 해시값은 체인 순회 시 정수 비교로 불일치 항목을 걸러내 전체 키 비교 비용을 절약하는 표준 기법이다. 크기 조정 시에도 캐시된 해시를 재사용해 키를 다시 해시하지 않아도 된다.
하위 비트 해시값을 통한 파티션 잠금
섹션 제목: “하위 비트 해시값을 통한 파티션 잠금”뜨거운 공유 테이블을 샤딩하려면 엔진이 해시값의 하위 비트를 파티션 번호로 예약하고 각 파티션에 자체 락을 부여한다. 좋은 해시 함수는 모든 비트를 섞으므로 하위 비트는 항목을 파티션에 고르게 분배한다. 버킷 대응 함수는 같은 하위 비트를 가진 버킷들이 하나의 파티션 안에 머무르도록 구성되어 파티션 전체를 독립적으로 잠글 수 있다. 작업은 파티션을 계산하고, 그 파티션의 락만 획득하며, 다른 파티션의 작업과 충돌하지 않는다. 대가는 테이블이 더 이상 온더플라이로 버킷을 분할할 수 없다는 것이다. 분할은 비행 중인 파티션 경계를 넘어 항목을 이동시키므로, 파티션된 테이블은 미리 크기를 정하고 버킷 수를 확장하지 않는다.
분할 억제를 동반한 순차 스캔
섹션 제목: “분할 억제를 동반한 순차 스캔”체인 해시 테이블 순회는 디렉터리를 버킷 단위로, 각 버킷의 체인을 순서대로 걷는다. 위험은 동시 확장이다. 스캔이 절반쯤 진행된 버킷이 분할되면 항목을 빠뜨리거나 두 번 방문할 수 있다. 표준 방어책은 활성 스캔을 등록하고 스캔이 열려 있는 동안 버킷 분할을 억제하는 것이다(분할을 나중 삽입으로 연기). 스캔이 조회 대비 드물므로 비용이 낮다.
PostgreSQL의 접근법
섹션 제목: “PostgreSQL의 접근법”PostgreSQL의 dynahash.c는 Larson 1988 알고리즘을 직접, 가볍게 현대화한 후손이다. 파일의 역사 주석은 CACM 논문과 1990년 버클리 추가분(“multiple table interface”와 공유 메모리용 “ctl structure”)을 인용한다. 같은 코드가 hash_create 시점의 플래그에 따라 전혀 다른 두 런타임 형태로 컴파일된다. 백엔드 로컬 테이블(자체 메모리 컨텍스트, OOM 시 throw하는 palloc 할당자, 자유 확장)과 공유 메모리 테이블(헤더와 디렉터리를 공유 아레나에 미리 할당, NULL 반환 할당자, 고정 디렉터리)이다. 파일 자체의 헤더 주석은 simplehash 대비 dynahash의 위치를 정확히 설명한다.
// dynahash.c — src/backend/utils/hash/dynahash.c * Compared to simplehash, dynahash has the following benefits: * * - It supports partitioning, which is useful for shared memory access using * locks. * - Shared memory hashes are allocated in a fixed size area at startup and * are discoverable by name from other processes. * - Because entries don't need to be moved in the case of hash conflicts, * dynahash has better performance for large entries. * - Guarantees stable pointers to entries.항목 레이아웃: 헤더 뒤에 키, 그 뒤에 데이터
섹션 제목: “항목 레이아웃: 헤더 뒤에 키, 그 뒤에 데이터”모든 항목은 HASHELEMENT 헤더 — 체인 링크와 캐시된 32비트 해시값 — 와 그 바로 뒤 MAXALIGN 경계에 붙은 호출자 페이로드다. 키가 페이로드 앞머리에 있어야 한다. 두 매크로가 헤더 포인터와 호출자가 실제 보는 키/페이로드 포인터 사이를 변환한다.
// HASHELEMENT — src/include/utils/hsearch.htypedef struct HASHELEMENT{ struct HASHELEMENT *link; /* link to next entry in same bucket */ uint32 hashvalue; /* hash function result for this entry */} HASHELEMENT;
// ELEMENTKEY / ELEMENT_FROM_KEY — src/backend/utils/hash/dynahash.c#define ELEMENTKEY(helem) (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))#define ELEMENT_FROM_KEY(key) \ ((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT))))이것이 dynahash의 “안정 포인터” 보장의 근거다. hash_search는 ELEMENTKEY(currBucket)을 반환한다. 이 포인터는 해당 항목이 제거될 때까지 유효하며, 다른 항목의 삽입, 삭제, 버킷 분할이 일어나도 이동하지 않는다. 버퍼 매니저는 BufferDesc 인접 포인터를 보관할 때, 락 매니저는 PROCLOCK이 LOCK을 참조할 때 이 보장에 의존한다.
디렉터리/세그먼트/버킷 기하학
섹션 제목: “디렉터리/세그먼트/버킷 기하학”제어 헤더 HASHHDR은 (공유 테이블의 경우 공유 메모리에, 각 백엔드는 이를 가리키는 얇은 로컬 HTAB만 보유하며) 크기 조정 상태를 담는다. 디렉터리 dir은 HASHSEGMENT 배열이고, 각 세그먼트는 ssize개의 HASHBUCKET 체인 헤드 배열이다.
// HASHHDR (excerpt) — src/backend/utils/hash/dynahash.cstruct HASHHDR{ FreeListData freeList[NUM_FREELISTS];
/* These fields can change, but not in a partitioned table */ long dsize; /* directory size */ long nsegs; /* number of allocated segments (<= dsize) */ uint32 max_bucket; /* ID of maximum bucket in use */ uint32 high_mask; /* mask to modulo into entire table */ uint32 low_mask; /* mask to modulo into lower half of table */
/* These fields are fixed at hashtable creation */ Size keysize; /* hash key length in bytes */ Size entrysize; /* total user element size in bytes */ long num_partitions; /* # partitions (must be power of 2), or 0 */ long max_dsize; /* 'dsize' limit if directory is fixed size */ long ssize; /* segment size --- must be power of 2 */ int sshift; /* segment shift = log2(ssize) */ int nelem_alloc; /* number of entries to allocate at once */};해시값을 버킷으로 매핑하는 것이 Larson의 두 마스크 기법이다. high_mask(전체 테이블)로 마스크하고, 결과가 아직 존재하지 않는 최고 버킷을 초과하면 low_mask(하반부)로 접는다. 이것이 확장 중간에 2의 거듭제곱이 아닌 버킷 수로 테이블이 존재할 수 있는 이유다.
// calc_bucket — src/backend/utils/hash/dynahash.cstatic inline uint32calc_bucket(HASHHDR *hctl, uint32 hash_val){ uint32 bucket;
bucket = hash_val & hctl->high_mask; if (bucket > hctl->max_bucket) bucket = bucket & hctl->low_mask;
return bucket;}버킷 번호는 이후 sshift로 시프트하고 마스크해 디렉터리 인덱스와 세그먼트 내 인덱스로 분해된다. MOD(x,y) 매크로는 (x) & ((y)-1)이며, ssize가 2의 거듭제곱이므로 유효하다.
// hash_initial_lookup — src/backend/utils/hash/dynahash.cbucket = calc_bucket(hctl, hashvalue);
segment_num = bucket >> hashp->sshift;segment_ndx = MOD(bucket, hashp->ssize);
segp = hashp->dir[segment_num];
if (segp == NULL) hash_corrupted(hashp);
*bucketptr = &segp[segment_ndx];로컬 vs 공유: 하나의 코드 경로, 두 가지 형태
섹션 제목: “로컬 vs 공유: 하나의 코드 경로, 두 가지 형태”hash_create는 HASH_SHARED_MEM으로 분기한다. 공유 테이블의 경우 HTAB 헤더는 TopMemoryContext에 할당되지만 HASHHDR과 디렉터리는 호출자가 제공한 공유 영역(info->hctl)에서 온다. HASH_ATTACH는 두 번째 백엔드가 이미 초기화된 테이블에 바인딩할 때 로컬 상수 몇 개를 복사하고 즉시 반환한다. 로컬 테이블의 경우 헤더, 디렉터리, 세그먼트, 항목 모두가 테이블을 위해 생성된 전용 AllocSet 컨텍스트에 산다. 그 덕분에 hash_destroy가 MemoryContextDelete 한 줄로 끝난다.
// hash_create (excerpt) — src/backend/utils/hash/dynahash.cif (flags & HASH_SHARED_MEM){ hashp->hctl = info->hctl; hashp->dir = (HASHSEGMENT *) (((char *) info->hctl) + sizeof(HASHHDR)); hashp->hcxt = NULL; hashp->isshared = true;
/* hash table already exists, we're just attaching to it */ if (flags & HASH_ATTACH) { /* make local copies of some heavily-used values */ hctl = hashp->hctl; hashp->keysize = hctl->keysize; hashp->ssize = hctl->ssize; hashp->sshift = hctl->sshift; return hashp; }}플래그는 해시/비교/복사 함수도 선택한다. HASH_STRINGS(C 문자열, string_hash/string_compare/strlcpy), HASH_BLOBS(바이너리, tag_hash 또는 4바이트 키용 uint32_hash 빠른 경로, memcmp/memcpy), 또는 HASH_FUNCTION(호출자 제공). HASH_ELEM(키/항목 크기)은 현재 필수이며 hash_create 상단에서 assert된다.
검색/삽입/확장 흐름
섹션 제목: “검색/삽입/확장 흐름”hash_search_with_hash_value는 전체 구조가 합쳐지는 곳이다. 삽입 작업 시 먼저 한 버킷 확장 여부를 확인하고, 디렉터리 조회와 체인 순회 후 액션별로 분기한다. 확장 확인은 파티션됨, 동결됨, 스캔 중인 테이블에는 단락(short-circuit)된다.
flowchart TD
start["hash_search_with_hash_value: key, hash, action"]
enter{"action이 ENTER<br/>또는 ENTER_NULL?"}
expandok{"nentries gt max_bucket<br/>AND 파티션 없음<br/>AND 동결 아님<br/>AND 활성 seq scan 없음?"}
expand["expand_table: 버킷 하나 분할,<br/>체인 재배분"]
lookup["hash_initial_lookup:<br/>calc_bucket → 세그먼트 → 체인 헤드"]
walk["체인 순회: 캐시된 hashvalue 비교,<br/>키 바이트 일치 확인"]
found{"일치 항목 발견?"}
act{"어떤 action?"}
rfind["FIND: ELEMENTKEY 반환 또는 NULL"]
rremove["REMOVE: 언링크, freelist에 푸시,<br/>nentries 감소, 댕글링 포인터 반환"]
renterhit["ENTER 히트: 기존 ELEMENTKEY 반환"]
rentermiss["ENTER 미스: get_hash_entry,<br/>링크 삽입, 키 복사, 호출자가 데이터 채움"]
start --> enter
enter -- yes --> expandok
enter -- no --> lookup
expandok -- yes --> expand --> lookup
expandok -- no --> lookup
lookup --> walk --> found
found --> act
act -- FIND --> rfind
act -- REMOVE --> rremove
act -- ENTER/found --> renterhit
act -- ENTER/not found --> rentermiss
파티션된 공유 테이블
섹션 제목: “파티션된 공유 테이블”HASH_PARTITION으로 표시된 공유 테이블은 온더플라이 확장을 포기하고 동시성을 얻는다. 메커니즘은 freeList[NUM_FREELISTS] 배열이다. 하나의 전역 (nentries, freeList) 쌍을 하나의 락 아래 두는 대신, 카운트와 프리 체인을 32개 슬라이스로 샤딩하고 각 슬라이스에 자체 스핀락을 준다. 해시값의 파티션은 하위 비트이며, 파일 수준 주석은 이것이 calc_bucket과 정렬되는 이유를 설명한다.
// dynahash.c partitioning comment — src/backend/utils/hash/dynahash.c * To use a hash table in partitioned mode, the HASH_PARTITION flag must be * given to hash_create. This prevents any attempt to split buckets on-the-fly. * Therefore, each hash bucket chain operates independently, and no fields * of the hash header change after init except nentries and freeList. ... * We expect callers to use the low-order bits of a lookup key's hash value * as a partition number --- this will work because of the way calc_bucket() * maps hash values to bucket numbers.
// FreeListData / FREELIST_IDX — src/backend/utils/hash/dynahash.ctypedef struct{ slock_t mutex; /* spinlock for this freelist */ long nentries; /* number of entries in associated buckets */ HASHELEMENT *freeList; /* chain of free elements */} FreeListData;
#define IS_PARTITIONED(hctl) ((hctl)->num_partitions != 0)#define FREELIST_IDX(hctl, hashcode) \ (IS_PARTITIONED(hctl) ? (hashcode) % NUM_FREELISTS : 0)두 개의 정준 클라이언트가 버퍼 조회 테이블과 락 테이블이다. 둘 다 HASH_PARTITION 플래그로 ShmemInitHash를 호출해 생성된다.
// buf_table.c — src/backend/storage/buffer/buf_table.cinfo.num_partitions = NUM_BUFFER_PARTITIONS;...SharedBufHash = ShmemInitHash("Shared Buffer Lookup Table", size, size, &info, HASH_ELEM | HASH_BLOBS | HASH_PARTITION);
// lock.c — src/backend/storage/lmgr/lock.cLockMethodLockHash = ShmemInitHash("LOCK hash", init_table_size, max_table_size, &info, HASH_ELEM | HASH_BLOBS | HASH_PARTITION);둘 다 파티션 LWLock을 획득하기 전에 get_hash_value로 파티션을 계산하고, 이미 계산된 해시를 다시 계산하지 않도록 hash_search_with_hash_value를 호출한다. 파티션 락 수는 NUM_FREELISTS(32)와 별개의 상수다. 각 프리리스트의 커버리지가 파티션과 딱 맞지 않을 수 있으므로 각 프리리스트는 자체 스핀락을 가진다.
simplehash의 로빈후드 오픈 어드레싱
섹션 제목: “simplehash의 로빈후드 오픈 어드레싱”로컬, 캐시 바인딩 핫패스를 위해 simplehash.h는 전처리기가 항목 타입별로 인스턴스화하는 별도 구현이다. 호출자가 SH_PREFIX, SH_ELEMENT_TYPE, SH_KEY, SH_HASH_KEY, SH_EQUAL 등을 #define하고 헤더를 포함하면, 간접 호출 없이 타입 안전한 foo_hash, foo_create, foo_insert, foo_lookup 함수를 얻는다. 테이블은 항목들의 단일 평탄 배열(오픈 어드레싱)이며, 두 배로 키우고, 로빈후드 변형 선형 탐침으로 군집화를 억제한다. 헤더 주석이 이 트레이드오프를 정확히 설명한다.
// simplehash.h design notes — src/include/lib/simplehash.h * Compared to dynahash, simplehash has the following benefits: * - Due to the "templated" code generation has known structure sizes and no * indirect function calls ... * - Open addressing has better CPU cache behavior than dynahash's chained * hashtables. ... * of "robin hood" hashing is employed. Robin hood hashing optimizes * chaining lengths by moving elements close to their optimal bucket * ("rich" elements), out of the way if a to-be-inserted element is further * away from its optimal position (i.e. it's "poor").두 테이블 사이의 핵심 대비: simplehash는 안정 포인터 없음(로빈후드 시프팅과 성장 시 리해싱이 항목을 이동시킨다), 공유 메모리 모드 없음, 파티셔닝 없음이다. 그러나 하나의 백엔드에서 수백만 번 탐침하는 소형 항목에는 실질적으로 더 빠르다. 두 테이블은 경쟁자가 아니라 상호 보완 관계다.
소스 탐방
섹션 제목: “소스 탐방”코드는 생성/소멸, 검색(공개 CRUD), 순차 스캔 기계, 내부 성장/할당 유틸리티로 깔끔하게 나뉜다. 두 클라이언트(버퍼 테이블, 락 테이블)는 ShmemInitHash를 호출해 그 위에 올라가고, simplehash.h는 include 트리 안의 완전히 병렬인 구현이다.
생성과 크기 조정 (dynahash.c)
섹션 제목: “생성과 크기 조정 (dynahash.c)”hash_create가 단일 진입점이다. HASH_ELEM을 assert하고, 플래그로 해시/비교/복사 함수를 선택하며, HTAB(로컬 테이블의 경우 전용 메모리 컨텍스트도)을 할당하고, hdefault로 HASHHDR 기본값을 채운 뒤 init_htab을 호출해 디렉터리와 초기 세그먼트를 구축한다. 공유 테이블이나 소형 로컬 테이블의 경우 첫 삽입이 할당하지 않도록 프리리스트에 항목을 미리 할당한다.
hash_create— 생성자. 플래그 디스패치, 함수 선택, 공유 vs 로컬 컨텍스트, 파티션 설정, 미리 할당 루프.hdefault—HASHHDR을 0으로 채우고DEF_DIRSIZE(256),DEF_SEGSIZE(256),NO_MAX_DSIZE,num_partitions = 0을 설정.choose_nelem_alloc— 요청이 2의 거듭제곱으로 반올림되도록 한 번에 할당할 항목 수를 결정(최소 32개).init_htab—next_pow2_int(nelem)으로max_bucket/high_mask/low_mask를 유도하고,nbuckets >= num_partitions를 보장하고, 디렉터리와 초기 세그먼트를 할당하며, 파티션된 테이블의 프리리스트별 스핀락을 초기화.hash_estimate_size/hash_select_dirsize/hash_get_shared_size—ShmemInitHash가 고정 영역을 예약할 때 호출하는 공유 메모리 크기 조정 헬퍼.hash_destroy— 로컬 테이블 전용:MemoryContextDelete(hashp->hcxt)가 모든 것을 해제. 할당자가 기본값인지 assert.
검색: 찾기 / 삽입 / 제거 / 갱신 (dynahash.c)
섹션 제목: “검색: 찾기 / 삽입 / 제거 / 갱신 (dynahash.c)”hash_search가 키를 해시하고 hash_search_with_hash_value에 위임한다. 후자가 실제 작업자다. HASH_ENTER 시 먼저 확장 여부를 확인하고(파티션 없음, 동결 아님, 활성 스캔 없음인 테이블만), 초기 버킷 조회를 하고, 캐시된 해시 후 키를 비교하며 체인을 순회하고, 액션별로 분기한다.
hash_search— 키를 해시한 뒤hash_search_with_hash_value를 호출하는 얇은 래퍼.hash_search_with_hash_value— CRUD 핵심. 확장 트리거,hash_initial_lookup, 체인 순회(hashvalue등치 게이트 후match),HASH_FIND/HASH_REMOVE/HASH_ENTER/HASH_ENTER_NULL분기. 제거 시 항목을 언링크하고 프리리스트에 푸시. 삽입 미스 시get_hash_entry로 프리리스트에서 꺼내 키를 복사.get_hash_value— 파티션된 호출자가 락 획득 전에 파티션을 계산할 수 있도록 내보낸 해시 전용 헬퍼.calc_bucket/hash_initial_lookup— 해시 → 버킷 →(세그먼트, 인덱스)→ 체인 헤드 포인터.hash_update_hash_key— 기존 항목을 제자리에서 재키잉. 저장된 해시로 찾고, 목적지 체인을 찾고, 중복을 실패 처리하고, 버킷이 바뀐 경우에만 재링크(프리리스트를 건드리지 않으므로 OOM 불가).get_hash_entry—freeList[freelist_idx]에서 항목을 팝. 비어 있으면element_alloc으로 새 청크 할당. 파티션된 테이블에서 실패하면 OOM 선언 전에 다른 프리리스트에서 빌림.hash_get_num_entries— 프리리스트 전체의nentries합산(호출자가 모든 파티션 락을 보유해야 함).
제거 경로는 체인 설계의 안정 포인터 성질과 파티션된 프리리스트 부기를 가장 명확하게 보여준다.
// hash_search_with_hash_value, HASH_REMOVE — src/backend/utils/hash/dynahash.ccase HASH_REMOVE: if (currBucket != NULL) { if (IS_PARTITIONED(hctl)) SpinLockAcquire(&(hctl->freeList[freelist_idx].mutex));
Assert(hctl->freeList[freelist_idx].nentries > 0); hctl->freeList[freelist_idx].nentries--;
/* remove record from hash bucket's chain. */ *prevBucketPtr = currBucket->link;
/* add the record to the appropriate freelist. */ currBucket->link = hctl->freeList[freelist_idx].freeList; hctl->freeList[freelist_idx].freeList = currBucket;
if (IS_PARTITIONED(hctl)) SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
return ELEMENTKEY(currBucket); } return NULL;HASH_REMOVE 후 반환된 포인터는 댕글링 포인터임에 주목하라. 항목이 프리리스트로 돌아가 다음 삽입에서 재사용된다. HASH_ENTER 경로는 호출자가 throw할 수 있는 코드 없이 데이터 필드를 채워야 한다는 날카로운 주석으로 끝난다. throw가 일어나면 반쯤 초기화된 항목이 테이블에 링크된 채로 남기 때문이다.
확장: 한 번에 하나의 버킷 (dynahash.c)
섹션 제목: “확장: 한 번에 하나의 버킷 (dynahash.c)”expand_table은 Larson 분할 단계이며, 파티션되지 않은 테이블에서만 도달한다. 정확히 하나의 새 버킷(max_bucket + 1)을 만들고, 새 버킷이 새 영역으로 넘어가면 새 세그먼트를 할당하며(dir_realloc으로 디렉터리를 키울 수도 있다), 2의 거듭제곱을 넘으면 마스크를 재조정하고, 하나의 이전 버킷 항목들을 재배분한다.
// expand_table (excerpt) — src/backend/utils/hash/dynahash.cnew_bucket = hctl->max_bucket + 1;...hctl->max_bucket++;old_bucket = (new_bucket & hctl->low_mask);
if ((uint32) new_bucket > hctl->high_mask){ hctl->low_mask = hctl->high_mask; hctl->high_mask = (uint32) new_bucket | hctl->low_mask;}...for (currElement = *oldlink; currElement != NULL; currElement = nextElement){ nextElement = currElement->link; if ((long) calc_bucket(hctl, currElement->hashvalue) == old_bucket) { *oldlink = currElement; oldlink = &currElement->link; } else { *newlink = currElement; newlink = &currElement->link; }}*oldlink = NULL;*newlink = NULL;확장은 hash_search_with_hash_value의 삽입 경로에서 트리거된다. freeList[0]의 활성 항목 수가 max_bucket을 초과하고(적재율 1) 테이블이 적격일 때다.
// hash_search_with_hash_value, expansion trigger — src/backend/utils/hash/dynahash.cif (action == HASH_ENTER || action == HASH_ENTER_NULL){ if (hctl->freeList[0].nentries > (long) hctl->max_bucket && !IS_PARTITIONED(hctl) && !hashp->frozen && !has_seq_scans(hashp)) (void) expand_table(hashp);}세 억제 조건은 각각 의미가 있다. 파티션된 테이블은 절대 분할할 수 없고(IS_PARTITIONED), 동결된 테이블은 버킷 수 변경을 금지하며(frozen), 열린 hash_seq_search가 있는 테이블은 스캔 중간에 분할하면 안 된다(has_seq_scans). 확장 실패는 치명적이지 않고 테이블이 높은 적재율로 동작할 뿐이다.
expand_table— 단일 버킷 분할. 마스크 재조정. 재배분 루프.dir_realloc— 디렉터리를 두 배로 키움(max_dsize == NO_MAX_DSIZE, 즉 로컬 테이블인 경우만). 이전 포인터를 복사하고 나머지를 0으로 채우고 이전 것을pfree.seg_alloc—ssize개의 버킷 헤드로 구성된 세그먼트 하나를 할당하고 0으로 채움.element_alloc— 하나의 블록에nelem개의 항목을 할당해freeList[freelist_idx]에 연결. 고정 크기 테이블의 경우 false 반환(throw 없음).
순차 스캔 (dynahash.c)
섹션 제목: “순차 스캔 (dynahash.c)”hash_seq_init은 스캔을 기록하고 (테이블이 동결되지 않은 경우) 백엔드별 활성 스캔 목록에 등록해 삽입이 분할을 억제하도록 한다. hash_seq_search는 버킷 단위로 순회하며, 현재 체인을 따라가다 체인이 끝나면 curBucket을 진행시키고, 각 버킷을 (segment_num, segment_ndx)로 분해하고 빈 버킷을 건너뛴다.
// hash_seq_search (excerpt) — src/backend/utils/hash/dynahash.csegment_num = curBucket >> hashp->sshift;segment_ndx = MOD(curBucket, ssize);segp = hashp->dir[segment_num];
while ((curElem = segp[segment_ndx]) == NULL){ /* empty bucket, advance to next */ if (++curBucket > max_bucket) { status->curBucket = curBucket; hash_seq_term(status); return NULL; /* search is done */ } if (++segment_ndx >= ssize) { segment_num++; segment_ndx = 0; segp = hashp->dir[segment_num]; }}hash_seq_init/hash_seq_init_with_hash_value— 전체 스캔 시작, 또는 주어진 해시값을 보유한 버킷 하나로 제한된 스캔 시작.hash_seq_search— 항목을 하나씩 반환. 현재 항목 삭제는 명시적으로 허용. 스캔 중 다른 항목 삭제는 미정의 동작.hash_seq_term— 스캔 종료 정리. 스캔 등록 해제.register_seq_scan/deregister_seq_scan/has_seq_scans— 고정 크기(MAX_SEQ_SCANS= 100) 백엔드별 열린 스캔 스택.expand_table트리거가 참조.hash_freeze— 로컬 테이블을 향후 삽입으로부터 잠금. 스캔에 등록/종료 규율 불필요. 공유 테이블에는 금지.
simplehash 템플릿 (simplehash.h)
섹션 제목: “simplehash 템플릿 (simplehash.h)”파일 전체가 매크로 기계다. SH_MAKE_NAME이 모든 타입과 함수에 사용자 프리픽스를 붙인다. 런타임 구조는 하나의 평탄 항목 배열과 크기 스칼라들이다.
// SH_TYPE — src/include/lib/simplehash.htypedef struct SH_TYPE{ uint64 size; /* size of data/bucket array */ uint32 members; /* how many elements have valid contents */ uint32 sizemask; /* mask for bucket and size calculations */ uint32 grow_threshold; /* boundary after which to grow hashtable */ SH_ELEMENT_TYPE *data; /* hash buckets */#ifndef SH_RAW_ALLOCATOR MemoryContext ctx;#endif void *private_data;} SH_TYPE;크기 조정은 적재율(기본 0.9)로 요청된 항목 수를 올려 2의 거듭제곱으로 반올림한다. 따라서 sizemask = size - 1이고 최적 버킷은 hash & sizemask다.
// SH_UPDATE_PARAMETERS / SH_INITIAL_BUCKET — src/include/lib/simplehash.htb->size = size;tb->sizemask = (uint32) (size - 1);if (tb->size == SH_MAX_SIZE) tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;else tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;...static inline uint32SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash){ return hash & tb->sizemask;}로빈후드 삽입이 파일의 핵심이다. 충돌 시 삽입할 항목의 최적 버킷으로부터의 거리를 충돌하는 항목의 거리와 비교한다. 신입이 더 “가난하면”(최적 버킷에서 더 멀면), 실행(run)을 다음 빈 슬롯으로 한 칸씩 시프트해 “부유한” 거주자를 밀어내고 자리를 차지한다. 하나의 삽입이 탐침(SH_GROW_MAX_DIB, 25) 또는 시프트(SH_GROW_MAX_MOVE, 150)를 너무 많이 요구하면 강제로 테이블을 키운다.
// SH_INSERT_HASH_INTERNAL (excerpt) — src/include/lib/simplehash.hcurhash = SH_ENTRY_HASH(tb, entry);curoptimal = SH_INITIAL_BUCKET(tb, curhash);curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);
if (insertdist > curdist){ /* find next empty bucket, then shift the run forward by one */ ... moveelem = emptyelem; while (moveelem != curelem) { moveelem = SH_PREV(tb, moveelem, startelem); moveentry = &data[moveelem]; memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE)); lastentry = moveentry; } tb->members++; entry->SH_KEY = key; entry->status = SH_STATUS_IN_USE; *found = false; return entry;}조회는 첫 번째 SH_STATUS_EMPTY 슬롯에서 멈추는 단순 선형 탐침이다. 로빈후드 삭제는 묘비를 남기지 않고 뒤로 시프트하므로, 빈 슬롯은 진정으로 “없음”을 의미한다.
// SH_LOOKUP_HASH_INTERNAL — src/include/lib/simplehash.hconst uint32 startelem = SH_INITIAL_BUCKET(tb, hash);uint32 curelem = startelem;while (true){ SH_ELEMENT_TYPE *entry = &tb->data[curelem]; if (entry->status == SH_STATUS_EMPTY) return NULL; if (SH_COMPARE_KEYS(tb, hash, key, entry)) return entry; curelem = SH_NEXT(tb, curelem, startelem);}SH_CREATE/SH_DESTROY/SH_RESET— 생명주기. 생성 시SH_FILLFACTOR로 크기를 올림.SH_INSERT/SH_INSERT_HASH/SH_INSERT_HASH_INTERNAL— 로빈후드 삽입. 임계치 또는SH_GROW_MAX_DIB/SH_GROW_MAX_MOVE에서 성장.SH_LOOKUP/SH_LOOKUP_HASH/SH_LOOKUP_HASH_INTERNAL— 첫 번째 빈 슬롯까지 선형 탐침.SH_DELETE/SH_DELETE_ITEM— 묘비 없이 뒤로 시프트 압축하는 삭제.SH_GROW— 두 배로 키우고 모든 항목을 재배치. 이동이 충돌하지 않도록 비감싸진(non-wrapped) 버킷부터 시작.SH_START_ITERATE/SH_ITERATE— 평탄 배열 순회. 반복 중 삽입된 항목이 두 번 방문되지 않도록 무작위이지만 안정적인 시작 버킷 사용.SH_STAT— 진단(최대/평균 체인 길이, 충돌).
위치 힌트 (2026-06-05 기준, REL_18 273fe94)
섹션 제목: “위치 힌트 (2026-06-05 기준, REL_18 273fe94)”| 심벌 | 파일 | 라인 |
|---|---|---|
HASHELEMENT | hsearch.h | 51 |
HASHCTL | hsearch.h | 65 |
HASHACTION | hsearch.h | 111 |
HASH_SEQ_STATUS | hsearch.h | 120 |
struct HASHHDR | dynahash.c | 168 |
FreeListData | dynahash.c | 153 |
struct HTAB | dynahash.c | 219 |
ELEMENTKEY / ELEMENT_FROM_KEY | dynahash.c | 244 |
FREELIST_IDX | dynahash.c | 212 |
hash_create | dynahash.c | 352 |
hdefault | dynahash.c | 630 |
choose_nelem_alloc | dynahash.c | 657 |
init_htab | dynahash.c | 690 |
hash_estimate_size | dynahash.c | 784 |
hash_select_dirsize | dynahash.c | 831 |
hash_get_shared_size | dynahash.c | 855 |
hash_destroy | dynahash.c | 866 |
get_hash_value | dynahash.c | 912 |
calc_bucket | dynahash.c | 919 |
hash_search | dynahash.c | 956 |
hash_search_with_hash_value | dynahash.c | 969 |
hash_update_hash_key | dynahash.c | 1146 |
get_hash_entry | dynahash.c | 1259 |
hash_get_num_entries | dynahash.c | 1344 |
hash_seq_init | dynahash.c | 1388 |
hash_seq_search | dynahash.c | 1423 |
hash_seq_term | dynahash.c | 1517 |
hash_freeze | dynahash.c | 1537 |
expand_table | dynahash.c | 1554 |
dir_realloc | dynahash.c | 1651 |
seg_alloc | dynahash.c | 1690 |
element_alloc | dynahash.c | 1709 |
hash_initial_lookup | dynahash.c | 1759 |
my_log2 | dynahash.c | 1797 |
SH_TYPE | simplehash.h | 145 |
SH_STATUS | simplehash.h | 175 |
SH_COMPUTE_SIZE | simplehash.h | 310 |
SH_UPDATE_PARAMETERS | simplehash.h | 336 |
SH_INITIAL_BUCKET | simplehash.h | 356 |
SH_DISTANCE_FROM_OPTIMAL | simplehash.h | 385 |
SH_CREATE | simplehash.h | 441 |
SH_GROW | simplehash.h | 493 |
SH_INSERT_HASH_INTERNAL | simplehash.h | 608 |
SH_LOOKUP_HASH_INTERNAL | simplehash.h | 799 |
SH_DELETE | simplehash.h | 856 |
SH_DELETE_ITEM | simplehash.h | 928 |
SH_ITERATE | simplehash.h | 1045 |
소스 검증 (2026-06-05 기준)
섹션 제목: “소스 검증 (2026-06-05 기준)”검증된 사실
섹션 제목: “검증된 사실”-
dynahash는 Larson 1988 동적 해싱으로, 한 번에 하나의 버킷씩 성장한다.
dynahash.c의 역사 주석이 “Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson”을 인용한다.expand_table이 정확히 하나의 버킷을 추가하고(new_bucket = hctl->max_bucket + 1; ... hctl->max_bucket++) 단 하나의 이전 버킷(new_bucket & low_mask)체인을 둘로 분할함을 검증했다. 두 마스크calc_bucket(high_mask로 마스크 후low_mask로 접기)이 선형 해싱 주소 계산이다. -
하나의 코드 베이스가 로컬과 공유 테이블 모두를 제공하며, 플래그로 선택한다.
hash_create에서HASH_SHARED_MEM이hashp->hctl/hashp->dir을 호출자의 공유 영역으로 지정하고isshared = true를 설정함을 검증했다. 비공유 경로는 전용AllocSetContext를 생성한다.HASH_ATTACH는 로컬 상수를 복사한 뒤 조기 반환해 두 번째 백엔드가 기존 테이블에 바인딩하도록 한다. -
항목은 안정 주소를 가진다. 키는 HASHELEMENT 헤더 뒤에 내장된다.
hsearch.h의HASHELEMENT(link+hashvalue)와dynahash.c의ELEMENTKEY/ELEMENT_FROM_KEY매크로(헤더에서MAXALIGN(sizeof(HASHELEMENT))이후에 키 위치)를 검증했다.hash_search는ELEMENTKEY(currBucket)을 반환하며, 제거는 같은 항목을 프리리스트에 푸시할 뿐 재배치하지 않으므로, 살아 있는 동안 주소가 재사용되거나 이동하지 않는다. -
파티션 모드는
(nentries, freeList)를 NUM_FREELISTS=32 스핀락 슬라이스로 샤딩하고 온더플라이 분할을 금지한다.FreeListData가 슬라이스별slock_t mutex를 가짐을 검증했다.FREELIST_IDX가 해시코드를 슬라이스로 매핑한다.expand_table이!IS_PARTITIONED(hctl)을 assert하고,hash_search_with_hash_value확장 트리거가!IS_PARTITIONED(hctl)로 게이팅된다.get_hash_entry는 OOM 선언 전에 다른 프리리스트에서 빌리며, 삭제가 이후 삽입을 보장한다는 호출자 가정을 만족시킨다. -
버퍼 매니저와 락 매니저가 정준 파티션된 클라이언트다.
buf_table.c가HASH_ELEM | HASH_BLOBS | HASH_PARTITION과num_partitions = NUM_BUFFER_PARTITIONS로SharedBufHash를 생성함을 검증했다.lock.c는HASH_PARTITION으로LockMethodLockHash와LockMethodProcLockHash를 생성한다. 둘 다 파티션 LWLock을 획득하기 전에 해시값을 계산하고(get_hash_value), 이미 계산된 해시를 재계산하지 않도록hash_search_with_hash_value를 호출한다. -
확장은 적재율 1에서 트리거되며, 파티셔닝, 동결, 활성 순차 스캔이 억제한다. 트리거 조건
hctl->freeList[0].nentries > (long) hctl->max_bucket && !IS_PARTITIONED && !hashp->frozen && !has_seq_scans(hashp)를 검증했다. 확장 실패는 코드 내 주석에 따라 명시적으로 치명적이지 않다. -
hash_seq_search는 디렉터리를 버킷 단위로 순회하고 스캔을 등록해 분할을 억제한다.hash_seq_init이 (동결되지 않은 경우)register_seq_scan을 호출함을 검증했다.hash_seq_search는sshift/MOD로curBucket을(segment_num, segment_ndx)로 분해하고, 빈 버킷을 건너뛰고,->link체인을 따른다.MAX_SEQ_SCANS는 100이다. -
simplehash는 안정 포인터, 공유 메모리, 파티셔닝이 없는 별도 매크로 템플릿 오픈 어드레싱 로빈후드 해시다.
simplehash.h의SH_TYPE이 단일 평탄SH_ELEMENT_TYPE *data배열임을 검증했다.SH_INSERT_HASH_INTERNAL이 로빈후드 시프팅(insertdist > curdist이면memcpy로 실행을 시프트)을 수행한다.SH_LOOKUP_HASH_INTERNAL은 첫 번째SH_STATUS_EMPTY에서 멈춘다(SH_DELETE가 묘비 없이 뒤로 시프트하므로 유효). 기본SH_FILLFACTOR0.9,SH_MAX_FILLFACTOR0.98,SH_GROW_MAX_DIB25 /SH_GROW_MAX_MOVE150에서 강제 성장. -
HASH_ELEM이 현재 필수이며 키 클래스 플래그는 STRINGS/BLOBS/FUNCTION 중 정확히 하나다.
hash_create상단의Assert(flags & HASH_ELEM), 정수 키를 문자열로 오인하는 것을 방지하는Assert(info->keysize > 8), 4바이트 BLOB 키용uint32_hash빠른 경로를 검증했다.
열린 질문
섹션 제목: “열린 질문”-
실제 파티션된 워크로드에서
get_hash_entry의 프리리스트 빌림 경로가 얼마나 자주 실행되는가. 빌림 루프는 정확성을 위해 존재한다(삭제는 파티션 경계를 넘어서도 이후 삽입이 항목을 찾을 수 있음을 보장해야 한다). 그러나 버퍼·락 테이블 부하 아래서 측정 가능한 핫 경로인지는 코드에서 명확하지 않다. 조사 방법: 경합된 pgbench 실행에서borrow_from_idx루프에 카운터 계측. -
dynahash의 적재율 1 확장 임계치 대 simplehash의 0.9의 실질적 비용. dynahash는 활성 항목이
max_bucket을 초과할 때 분할하고(적재율 ~1), 더 긴 체인을 허용한다. simplehash는 탐침 실행을 짧게 유지하기 위해 0.9에서 성장한다. dynahash의 높은 목표 적재율이 카탈로그/릴레이션캐시 로컬 테이블에서 체인 순회를 실질적으로 늘리는지는 여기서 측정되지 않았다. 조사 방법: 바쁜 릴레이션캐시에서hash_stats(HASH_STATISTICS빌드) 실행. -
현재 공유 테이블 중 NUM_FREELISTS 값 32 이외에서 이점을 얻을 수 있는 것이 있는가. 프리리스트 수는 파티션 락 수와 분리된 컴파일 타임 상수다. 주석은 프리리스트의 커버리지가 파티션과 “더 많거나 더 적을 수 있다”고 언급한다. REL_18의
NUM_BUFFER_PARTITIONS/ 락 파티션 수 기준으로 32가 최적인지는 확립되지 않았다. 조사 방법: 높은 버퍼 퇴거 부하 아래서 프리리스트 스핀락의 캐시 라인 경합 프로파일링.
PostgreSQL 너머 — 비교 설계와 연구 프런티어
섹션 제목: “PostgreSQL 너머 — 비교 설계와 연구 프런티어”-
Larson 1988 / Litwin 선형 해싱 대 확장 해싱. dynahash는 Larson의 선형 해싱 계열(라운드 로빈 순서로 다음 버킷을 분할, 두 마스크 주소 지정)을 따르며, Fagin의 확장 해싱(상위
d비트로 인덱싱된 디렉터리, 오버플로 시 디렉터리 두 배화)을 사용하지 않는다. 확장 해싱은 최악 경우를 두 번의 디스크 접근으로 제한해 온디스크 해시 인덱스의 고전적 선택이다. 선형 해싱은 한 단계에 디렉터리를 두 배화하지 않으므로 인메모리 테이블에서 유리하다.calc_bucket의 두 마스크 방식을 Litwin의h_i/h_{i+1}분할 함수로 매핑하면 계보가 더 선명해진다. Database System Concepts ch. 14에서 둘을 다루고, Database Internals ch. 6에서 스토리지 엔진용 확장 해싱을 다룬다. -
체이닝 + 안정 포인터 대 오픈 어드레싱. 하나의 코드베이스 안의 dynahash/simplehash 분리는 체이닝 대 오픈 어드레싱 트레이드오프의 깔끔한 자연 실험이다. dynahash는 안정 포인터와 파티셔닝을 포인터 추적과 항목별 헤더 비용으로 유지한다. simplehash는 캐시 밀집도와 인라인 비교를 항목 이동 비용으로 유지한다. 비교 마이크로벤치마크(큰 항목, 작업 간 포인터 보유 워크로드 대 작은 항목, 탐침 집약 워크로드)를 돌리면 파일 헤더가 정성적으로 주장하는 교차점을 정량화할 수 있다.
-
로빈후드 해싱 대 Swiss table / hopscotch. simplehash의 로빈후드 변형은 변위 균형으로 탐침 실행 분산을 제한한다. 현대적 대안인 Google의 SwissTable(SIMD 메타데이터 바이트, abseil
flat_hash_map)과 hopscotch 해싱은 오픈 어드레싱 지역성을 더욱 발전시킨다. simplehash를 SwissTable 방식 메타데이터 탐침 설계와 비교하면 PostgreSQL이 슬롯별 상태 바이트와 스칼라 탐침을 유지함으로써 포기하는 것이 무엇인지 분명해진다. -
파티션된 dynahash 대 락프리 / 샤딩된 동시 해시 맵. dynahash는 파티션 외부 LWLock을 사용한다. 락프리 해시 맵(분할 순서 리스트, Cliff Click의 비차단 해시 맵)과 세밀한 샤딩 설계는 파티션별 락을 완전히 제거한다. CMU/EPFL의 “scalable lock manager” 연구(
dbms-papers/scalable-lock-manager.md에 정리)는LockMethodLockHash가 구현하는 파티션된 해시 위의 락 테이블 구조를 재사고한다. dynahash의 조대한 파티션 락을 그 설계와 비교하는 것은 공유 테이블 동시성에 관한 연구 수준의 작업이다. -
CUBRID의 메모리 해시 테이블(
mht_*). CUBRID는 카탈로그와 세션 구조에 범용 체인 메모리 해시 시설을 사용한다. dynahash가 PostgreSQL의 로컬 캐시에 쓰이는 방식과 유사하다. CUBRID의mht_create/mht_get/mht_put리해시 전략과 dynahash의 한 버킷씩 확장을 나란히 비교하면, CUBRID가 Larson의 방식이 피하려 한 stop-the-world 리해시를 치르는지 확인할 수 있다. CUBRID 코드 분석 트리를 참고.
인트리 소스 파일 (REL_18_STABLE, 커밋 273fe94)
섹션 제목: “인트리 소스 파일 (REL_18_STABLE, 커밋 273fe94)”src/backend/utils/hash/dynahash.c— 구현 전체.hash_create,hash_search_with_hash_value,expand_table,get_hash_entry,hash_seq_search, 디렉터리/세그먼트/버킷 기하학, 파티션된 프리리스트, Larson 역사 주석.src/include/utils/hsearch.h— 공개 인터페이스.HASHELEMENT,HASHCTL,HASH_*플래그 비트,HASHACTION,HASH_SEQ_STATUS, 함수 프로토타입.src/include/lib/simplehash.h— 매크로 템플릿 오픈 어드레싱 로빈후드 해시.SH_TYPE,SH_INSERT_HASH_INTERNAL,SH_LOOKUP_HASH_INTERNAL,SH_GROW, 설계 주석 헤더.src/backend/storage/buffer/buf_table.c—SharedBufHash. 정준 파티션된HASH_BLOBS클라이언트.src/backend/storage/lmgr/lock.c—LockMethodLockHash/LockMethodProcLockHash. dynahash 위에 구축된 파티션된 락 테이블.
논문과 교과서 챕터
섹션 제목: “논문과 교과서 챕터”- Larson, P.-Å. (1988). “Dynamic Hash Tables.” Communications of the ACM 31(4):446-457. dynahash가 구현하는 확장 알고리즘.
dynahash.c역사 주석에 이름으로 인용됨. - Litwin, W. (1980). “Linear Hashing: A New Tool for File and Table Addressing.” Proc. VLDB. Larson이 개선한 선형 해싱 방식.
- Fagin, R., Nievergelt, J., Pippenger, N. & Strong, H. R. (1979). “Extendible Hashing — A Fast Access Method for Dynamic Files.” ACM TODS 4(3). dynahash가 사용하지 않는 디렉터리 두 배화 대안.
- Database System Concepts (Silberschatz, Korth, Sudarshan, 7e), ch. 14 “Indexing” — 정적 vs 동적 해싱, 선형 해싱, 확장 해싱(
knowledge/research/dbms-general/database-system-concepts.md). - Database Internals (Petrov 2019), ch. 6 — 확장 해싱과 인메모리 테이블 구조(
knowledge/research/dbms-general/database-internals.md). - “A Scalable Lock Manager for Multicores” — 파티션된 락 테이블 동시성 프런티어(
knowledge/research/dbms-papers/scalable-lock-manager.md).
형제 문서 (교차 참조 — 메커니즘 소유권이 거기 있으며 여기서 중복하지 않는다)
섹션 제목: “형제 문서 (교차 참조 — 메커니즘 소유권이 거기 있으며 여기서 중복하지 않는다)”postgres-shared-memory-ipc.md—ShmemInitHash, 공유 메모리 아레나, 공유 dynahash가 사는 고정 영역을 할당하는ShmemInitStruct.postgres-buffer-manager.md—SharedBufHash와 dynahash의HASH_PARTITION모드를 타는 버퍼 파티션 LWLock.postgres-lock-manager.md—LockMethodLockHash/LockMethodProcLockHash, 파티션된 락 테이블과 그 파티션 LWLock.postgres-memory-contexts.md— 로컬 dynahash가 할당하고MemoryContextDelete로 일괄 소멸하는AllocSet컨텍스트.postgres-architecture-overview.md— dynahash/simplehash 시설의 “base infrastructure” 축 배치.