LRU-K 교체 정책 설계

LRU-K는 전통적인 LRU의 단점을 보완한 진화된 캐시 교체 알고리즘이다. 핵심 아이디어는 K번 이상 접근된 데이터만 캐시 대상으로 승격시키는 것이다. 이를 통해 순간적인 스파이크 트래픽에 의한 캐시 오염을 방지하고, 진정한 핫 데이터의 지위를 확보한다.

구조적으로 두 개의 논리적 영역으로 나뉜다:

• 히스토리 존: K번 미만 접근된 데이터가 대기하는 임시 공간, FIFO 방식으로 관리
• 캐시 존: K번 이상 접근된 데이터가 시간순으로 배치, LRU 방식으로 관리

구현상에서는 단일 이중 연결 리스트를 분할하여 두 존을 표현한다. 중간 지점을 가리키는 포인터로 경계를 설정한다.

struct CacheEntry {
    frame_id_t fid;
    uint32_t access_cnt;
    bool evictable;
    CacheEntry *prev, *next;
};

CacheEntry *cache_start_;  // 캐시 존 시작
CacheEntry *history_end_;  // 히스토리 존 끝
CacheEntry *list_tail_;    // 전체 리스트 끝

프레임과 노드의 매핑은 해시 테이블로 O(1) 접근을 보장한다. 동시성 제어는 std::scoped_lock을 활용한 RAII 패턴으로 구현하여 예외 안전성을 확보한다.

버퍼 풀 핵심 메커니즘

디스크 블록(페이지)과 메모리 블록(프레임)의 중재자 역할을 수행한다. 핵심 자료구조 구성은 다음과 같다:

class BufferPoolManager {
    // 프레임 저장소: 실제 메모리 버퍼
    std::vector<Page> frame_pool_;
    
    // 논리적 매핑: 페이지 ID → 프레임 인덱스
    std::unordered_map<page_id_t, size_t> frame_map_;
    
    // 가용 프레임 인덱스 큐
    std::deque<size_t> available_frames_;
    
    // 교체 정책 엔진
    std::unique_ptr<LRUKReplacer> eviction_policy_;
};

페이지 할당 흐름:

1. 가용 큐에서 빈 프레임 확보 시도
2. 실패 시 교체 정책에 의한 프레임 회수
   • 더티 페이지는 디스크 동기화
   • 기존 매핑 정보 제거
3. 새 페이지 ID 발급 및 프레임 매핑 구축
4. 디스크로부터 페이지 내장 로드
5. 교체 정책에 프레임 등록 (비퇴출 상태)

페이지 조회 흐름은 할당과 유사하나, 버퍼 히트 시 즉시 반환하는 경로가 추가된다.

Page* FetchPage(page_id_t pid) {
    // 버퍼 히트 확인
    if (auto it = frame_map_.find(pid); it != frame_map_.end()) {
        auto frame_idx = it->second;
        eviction_policy_->RecordAccess(frame_idx);
        return &frame_pool_[frame_idx];
    }
    
    // 미스 처리: NewPage와 동일한 회수/할당 로직
    // ...
}

페이지 사용 완료 시 ReleasePage()를 호출하여 퇴출 가능 상태로 전환한다. SyncPage()는 명시적 디스크 기록을 수행한다.

RAII 기반 페이지 수명 관리

수동 Unpin 호출의 누락은 치명적인 버퍼 누수를 초래한다. 스마트 포인터 개념을 차용한 페이지 가드 패턴으로 이를 해결한다.

PageGuard는 버퍼 풀 매니저와 페이지에 대한 참조를 캡슐화한다. 소멸자에서 자동으로 Unpin을 호출하여 수명 종료를 보장한다.

class PageGuard {
    BufferPoolManager *manager_;
    Page *page_ref_;
    bool modified_;
    
public:
    ~PageGuard() {
        if (page_ref_) {
            manager_->ReleasePage(page_ref_->GetPageId(), modified_);
        }
    }
    
    // 이동 의미론만 허용 (복제 금지)
    PageGuard(PageGuard&&) noexcept;
    PageGuard& operator=(PageGuard&&) noexcept;
    
    void ExplicitRelease();  // 수동 조기 반납
};

다중 스레드 환경을 위한 읽기/쓰기 가드는 락 관리까지 자동화한다. FetchPageRead(), FetchPageWrite()는 각각 공유락, 배타락을 획득한 상태의 가드를 반환한다.

class ReadGuard {
    PageGuard base_guard_;
    
public:
    ~ReadGuard() {
        if (auto *p = base_guard_.GetPage()) {
            p->RUnlock();  // 읽기 락 해제
        }
    }
    
    const char* Data() const;
};

class WriteGuard {
    PageGuard base_guard_;
    
public:
    ~WriteGuard() {
        if (auto *p = base_guard_.GetPage()) {
            p->WUnlock();  // 쓰기 락 해제
        }
    }
    
    char* MutableData();
    template<typename T>
    T* CastAs() {
        return reinterpret_cast<T*>(MutableData());
    }
};

타입 안전한 데이터 접근을 위해 reinterpret_cast를 래핑한다. 이는 포인터 비트 패턴을 재해석하는 저수준 연산으로, 객체 레이아웃이 명확히 정의된 경우에만 사용해야 한다. static_cast는 상속 계층 간 변환에, dynamic_cast는 런타임 타입 검증이 필요한 다형성 변환에, const_cast는 const 제거에 각각 적합하다.