ESH: Design and Implementation of an Optimal Hashing Scheme for Persistent Memory
Dereje Regassa, Heon Young Yeom, 황준석 (2023) · Applied Sciences 13:11528 · DOI ↗
본 연구는 byte-addressable 영구 메모리 (Intel Optane DCPMM) 환경에서 dynamic hashing 의 scalability·load factor·recovery 를 동시 만족하는 ESH (Efficient and Scalable Hashing) scheme 을 제안한다. ESH 는 segment 내 인접 bucket 으로 overflow 를 재분배해 full-table rehashing 빈도를 늦추고, bucket 단위 fine-grained locking 으로 멀티스레드 확장성을 확보한다. Intel Xeon Gold 5218 + 256 GB Optane DCPMM 실측 (10M 레코드 pre-load) 에서 insertion 은 CCEH 대비 30%, Dash 대비 4% 개선, lookup 은 Dash 대비 10% 개선, load factor 91% 를 달성. 1M 레코드 recovery 도 103 ms (CCEH 101.7 ms 와 비교 가능).
- RQ: byte-addressable 영구 메모리 (특히 Intel Optane DCPMM) 위에서 load factor·scalability·crash recovery 를 동시 만족하면서 dynamic hashing 의 full-table rehashing 오버헤드 를 줄일 수 있는 인덱스 구조는 무엇인가?
- 방법론: extendible-hashing 변형 (segment-based, two-layer directory), bucket-level-locking (optimistic, 256-byte bucket = 32 B metadata + 224 B kv), fine-grained-concurrency-control (writer-only lock; reader lock-free), benchmark-evaluation (CCEH·Dash 와 동일 setup 비교)
- 데이터: Intel Xeon Gold 5218 (32 cores / 64 hyper threads), 256 GB Optane DCPMM (2×128 GB), 32 GB DDR4, Ubuntu 18.04 + PMDK 1.8 + GCC 9.0; 10M 레코드 pre-load, uniform·skewed/Zipfian 분포; 8-byte 정수 키-값 + 가변 길이 키 (Dash benchmark).
- 주요 발견: ESH insertion CCEH +30% / Dash +4%; lookup Dash +10%; load factor 최대 91% (경쟁 scheme 초과). Recovery (1M records) 103 ms vs CCEH 101.7 ms. Bucket=256B, segment=1KB, probing distance=4 가 Optane 256-byte write block 과 정합.
- 시사점: 에뮬레이터 기반 PM hashing 평가는 실기기에서 suboptimal. PM 인덱스는 256-byte write block, NUMA, fine-grained locking 을 동시 고려해 재설계해야 한다.
요약
DRAM 시대의 hash 인덱스는 영구 메모리 (PM) 의 비대칭 read/write latency, crash consistency, 256-byte write block 같은 새 제약에 의해 suboptimal 이 된다. 기존 PM-aware 인덱스 (FAST&FAIR, NV-Tree, WORT, CCEH, Dash) 는 tree 와 hash 양 측에서 cache-line awareness, segmentation, fingerprinting 등 다양한 최적화를 도입했지만, load factor 와 scalability 를 동시 에 끌어올린 사례는 드물고, 다수가 PM 에뮬레이터 위에서 평가되어 실기기에서 재현 안 되는 문제가 있다. ESH 는 이 공백을 직접 겨냥한다.
설계 원칙은 세 가지다. (a) 불필요한 PM read/write 최소화 — bucket 을 PM 의 단일 block 으로 취급해 access 오버헤드 감축. (b) bucket 수준 fine-grained locking — 쓰기 시 해당 bucket 만 잠가 다른 thread 가 다른 bucket 에 동시 접근 가능, 읽기는 lock-free. (c) optimistic scaling — cache-line flush·CAS 의존을 줄이고 PM bandwidth 제약 하에서 경량 동시성 제어. 구체 구조는 256-byte bucket (32 B metadata + 224 B 28×8 B kv) × 4 buckets per segment. Metadata 는 lock·state·overflow bit (OB)·overflow records address byte (OFRB)·overflow counter (OC)·membership count 를 담는다. 핵심 idea 는 bucket 가득 시 directory doubling 대신 인접 bucket 으로 overflow 를 재분배 (Algorithm 1) 하고, segment 전체 소진 시에만 segment split / directory doubling 으로 진행하는 ordering 이다.
평가는 Intel Xeon Gold 5218 + 256 GB Optane DCPMM 위에서 CCEH (segment 16KB, bucket 64B) 와 Dash (segment 16KB, bucket 256B) 를 동일 base 로 비교. 10M 레코드 pre-load, MurmurHashUnaligned 사용, uniform·Zipfian skewed 분포. 결과: insertion ESH > Dash > CCEH (CCEH 대비 +30%, Dash 대비 +4%); lookup Dash 대비 +10%; load factor 91% 달성 (경쟁 scheme 추월). Recovery 도 1M records 기준 103 ms 로 CCEH 101.7 ms 와 거의 동일. 황준석 그룹의 4기-5기 ICT 인프라·smart city backend storage 라인의 일환으로, PM 인덱스 재설계의 실증을 제공한다.
핵심 결과
| 지표 | ESH | CCEH | Dash | 개선폭 |
|---|---|---|---|---|
| Insertion (대규모 dataset) | base | −30% | −4% | +30% vs CCEH, +4% vs Dash |
| Lookup | base | — | −10% | +10% vs Dash |
| Load factor (최대) | 91% | < ESH | < ESH | 경쟁 scheme 추월 |
| Recovery (1M records) | 103 ms | 101.7 ms | — | 거의 동등 |
| Bucket / Segment / Probing | 256 B / 1 KB / 4 | 64 B / 16 KB / 4 | 256 B / 16 KB / — | Optane 256-byte block 정합 |
- HW: Intel Xeon Gold 5218 (32 cores / 64 HT), 256 GB Optane DCPMM (2×128 GB), 32 GB DDR4
- SW: Ubuntu 18.04 LTS, PMDK 1.8, GCC 9.0
- Bucket 1개 = 32 B metadata + 224 B kv (28×8 B); segment 1개 = 4 buckets
방법론 노트
ESH 는 extendible-hashing 의 표준 directory–segment–bucket 계층 위에 overflow redistribution 을 얹는다. 키 에 대해 해시 함수 의 하위 bits 가 directory entry 를 결정하며, 최대 의 directory 슬롯이 segment 를 가리킨다. 각 bucket 은 local depth 로 split 시점을 추적:
일 때 bucket overflow → 전통적 directory doubling 이 트리거되어 모든 record 재할당이 발생한다. ESH 는 이 비용을 회피하기 위해 insertion 시 (Algorithm 1):
- target bucket 의 state 와 lock 확인 (consistency gate)
- target bucket 이 full 이면 overflow bit OB=1 설정, 다음 인접 bucket 으로 이동, overflow counter OC + membership count 증가
- 인접 bucket 에 삽입 후 OFRB 에 이동된 bucket 주소 기록
- segment 내 모든 bucket 이 full 일 때만 segment split / directory doubling
이는 재해싱의 amortized cost 를 dramatically 낮춘다. lookup (Algorithm 2) 은 target bucket → membership/OFRB 확인 → 같은 segment 내 인접 bucket 으로 traverse 로 lock-free 수행. concurrency 모델은 writer 만 bucket 단위 lock 획득, reader 는 lock-free 라 multi-thread 환경에서 contention 최소. crash recovery 는 startup 시 directory 를 records 로부터 rebuild — 부분 기록은 invalid 로 폐기.
설계 결정의 두 핵심: (i) bucket size 256 B 는 Optane 컨트롤러의 256-byte write block 과 정합해 write amplification 회피; (ii) segment size 1 KB (CCEH/Dash 의 16 KB 보다 작음) 는 segment 내 traversal 비용을 제한하면서 인접 bucket overflow 재분배의 locality 를 확보. 식별 전략: 동일 hash function (MurmurHashUnaligned), 동일 데이터셋 (10M records), 동일 분포 (uniform + Zipfian) 로 CCEH·Dash 와 head-to-head 비교, 실 Optane DCPMM 측정 (에뮬레이터 X).
연구 계보
CCEH (Nam et al. 2019, USENIX ATC, ref [14]) 와 Dash (Lu et al. 2020, VLDB, ref [18]) 의 PM-aware extendible hashing 계보를 직접 잇는다. CCEH 의 cache-line-sized bucket·intermediate segment idea, Dash 의 256-byte bucket·fingerprinting·PMDK 활용을 흡수하면서, overflow redistribution 으로 rehashing 비용을 더 늦춘다. Tree 기반 PM 인덱스 FAST&FAIR (ref [11]), NV-Tree (ref [12]), WORT (ref [13]) 와는 자매적으로 비교된다. Cuckoo 기반 PCM hashing (ref [47]), level hashing (ref [15]) 는 본 연구에서 DRAM 평가 한정 으로 baseline 에서 제외. Intel Optane 의 ADR / iMC / write-pending queue (ref [20]) 와 NUMA 효과 (ref [24,30,32]) 가 설계 제약 조건을 정의한다. 황준석 의 5기 (2024-2026 직전, 4기 2020-2023 후반) smart city·IoT 인프라 backend storage 작업 라인으로, Dereje Regassa 의 Integrated Program of Smart City Global Convergence (SNU) 과정 결과물이다.
See also
- 황준석
- Dereje Regassa
- Heon Young Yeom
- Applied Sciences
- 영구 메모리
- extendible-hashing
- dynamic-hashing
- storage-systems
- bucket-level-locking
- benchmark-evaluation
인접 그래프
- 인물 3
- 방법론 1
- 수록처 1
- 논문 2