Bf-Tree의 Phantom Record를 통한 Negative Lookup I/O 제거

Context

기존 캐싱 시스템은 데이터 존재 여부를 확인하지 못해 Key 부재 시 반복적인 Disk I/O가 발생하는 한계 존재. 특히 데이터가 없는 쿼리가 빈번한 워크로드에서 Leaf Page 접근 횟수가 증가하며 성능 저하 유발.

Technical Solution

• 데이터 부재 상태를 유효한 정보로 정의하여 캐싱하는 Negative Lookup 구조 설계
• 검색 실패 시 해당 Key를 Phantom Record 형태로 Mini-page에 저장하는 메커니즘 도입
• 이후 동일 Key 요청 시 Disk 접근 없이 Phantom Record 확인만으로 즉시 "not found" 반환
• Mini-page 내 Record Type을 Dirty, Exists, Cache, Tombstone, Phantom으로 세분화하여 상태 관리
• WAL(Write-ahead logging) 및 Checkpointing 기반의 전통적 복구 모델을 유지하며 데이터 영속성 보장