LIFO Cache: 본질, 스택 알고리즘 및 작동 방식

LIFO Cache란?

LIFO Cache(Last In First Out Cache)는 스택 위에 구현된 고정 크기 캐시입니다. 가득 찬 캐시에 새 요소가 추가되면 가장 최근(맨 위) 요소가 제거되고 새 요소가 그 자리를 차지합니다. “Last In First Out”이라는 이름은 캐시에 마지막으로 들어온 요소가 가장 먼저 제거됨을 의미합니다.

이 정책은 LRU 및 FIFO와 근본적으로 다릅니다. LRU가 가장 관련성이 높은 데이터(마지막 액세스 시간 기준)를 유지하려고 하고 FIFO가 데이터의 “나이”를 보존하는 반면, LIFO는 의도적으로 새 데이터를 희생합니다. 이는 캐싱에 직관에 반하는 것처럼 보일 수 있지만, 특정 시나리오에서는 LIFO가 최적의 솔루션으로 입증됩니다.

LIFO Cache의 전통적인 구현은 배열 또는 연결 리스트를 기반으로 하는 스택을 사용합니다. 배열은 컴팩트한 저장과 캐시 지역성을 제공하지만 maxSize를 위한 메모리를 미리 할당해야 합니다. 연결 리스트는 더 유연하지만 각 요소에 포인터를 위한 추가 메모리가 필요합니다(요소당 8–16바이트).

LIFO Cache 기본 연산

push(value) 연산은 스택 맨 위에 요소를 추가합니다. 크기가 maxSize에 도달하면 삽입 전에 맨 위가 제거됩니다. pop() 연산은 맨 위 요소를 제거하고 반환합니다 — “마지막 작업 실행 취소” 시나리오에 유용합니다. peek() 연산은 맨 위 요소를 제거하지 않고 반환합니다 — 스택을 변경하지 않고 마지막 저장 상태를 확인하기 위함입니다.

LIFO Cache 작동 방식

LIFO Cache의 작동 원리는 매우 간단합니다. 모든 연산은 구조의 한쪽 끝 — 스택 맨 위에서 수행됩니다. 새 요소가 추가되면 맨 위에 배치됩니다. 스택이 가득 차면 맨 위 요소가 제거되고 새 요소가 그 자리를 차지합니다. 제거는 항상 하나의 요소(맨 위)에만 영향을 미치므로 알고리즘은 반복이나 검색이 필요하지 않습니다.

이 특성으로 인해 LIFO Cache는 모든 제거 정책 중에서 가장 빠릅니다. 모든 연산은 추가 데이터 구조 없이 O(1)로 실행됩니다. 검색을 위한 해시 테이블, 재정렬을 위한 이중 연결 리스트가 필요 없습니다 — 스택 맨 위에 대한 단순한 포인터만 있으면 됩니다. 메모리 소비는 최소화되며, 요소 자체의 저장만 필요합니다.

그러나 단순함에는 단점이 있습니다. LIFO Cache는 데이터의 빈도나 마지막 액세스 시간을 고려하지 않습니다. 애플리케이션이 먼저 데이터 A, B, C를 요청하고 다시 A를 요청하면, 캐시가 가득 찼을 때 C(마지막으로 추가된 것)가 제거됩니다. A가 더 이상 관련이 없더라도 말입니다. 일반 캐싱 시나리오의 경우 이로 인해 LIFO가 최악의 선택이 됩니다. 새 데이터가 가장 가치 있는 경우가 많기 때문입니다.

스택 크기 및 메모리 관리

배열 기반 LIFO Cache의 경우 크기는 생성 시 설정되며 동적으로 변경되지 않습니다. 스택이 가득 차고 push가 발생하면 맨 위 요소가 덮어쓰여집니다. 연결 리스트 구현의 경우 필요에 따라 요소별로 메모리가 할당되지만, 제한에 도달하면 이전 노드가 분리되어 가비지 컬렉터에 의해 수집될 수 있습니다. 모바일 애플리케이션에서는 GC에 추가 부하를 주지 않으므로 LIFO Cache에 배열을 사용하는 것이 좋습니다.

LIFO vs LRU 및 FIFO: 전략 비교

제거 전략의 선택은 캐싱 효율성에 직접적인 영향을 미칩니다. LIFO, LRU 및 FIFO는 동일한 질문에 대한 서로 다른 접근 방식을 나타냅니다. 캐시가 가득 찼을 때 어떤 요소를 제거할까요? 각 접근 방식은 고유한 작업 클래스에 최적화되어 있습니다.

LRU는 일반적으로 최상의 적중률을 제공하지만 더 많은 메모리가 필요하고 구현이 더 복잡합니다. FIFO는 성능과 적중률 사이의 절충안으로, 스트리밍 데이터에 유용합니다. LIFO는 가장 간단하지만 적중률이 낮습니다. “마지막에 들어온 것이 먼저 나간다”는 의미가 비즈니스 로직(탐색, 실행 취소 작업)과 일치하는 경우에만 사용해야 합니다.

LIFO Cache 사용 사례

일반 캐싱에 대한 제한된 적합성에도 불구하고, LIFO Cache는 데이터 처리 순서가 도착 순서와 반대인 특정 시나리오에서 사용됩니다. 주요 사례를 살펴보겠습니다.

탐색 스택

모바일 애플리케이션에서는 탐색 스택이 사용됩니다. 새 화면이 열리면 스택 맨 위에 배치되고, “뒤로” 버튼을 누르면 제거됩니다. 스택 깊이가 제한된 경우(예: 최대 10개 화면), LIFO Cache는 제한을 초과하면 자동으로 가장 최근 화면을 제거합니다. 이를 통해 이전에 연 화면을 잃지 않고 탐색 스택의 메모리 소비를 제어할 수 있습니다.

실행 취소/다시 실행 스택

실행 취소 메커니즘(Undo)은 LIFO의 전형적인 예입니다. 각 사용자 작업은 스택에 저장됩니다. Undo가 호출되면 마지막 작업이 취소되고 다시 실행 스택으로 이동됩니다. LIFO Cache를 통한 스택 크기 제한은 제한을 초과할 때 가장 오래된 작업(스택 바닥)은 유지되고 가장 최근 작업은 폐기되도록 보장합니다 — 이는 논리적입니다. 사용자는 일반적으로 최근 작업을 취소하고 오래된 작업은 더 이상 관련이 없기 때문입니다.

임시 계산 버퍼링

역추적(backtracking)이 포함된 재귀 계산에서 중간 단계의 결과는 LIFO 순서로 저장됩니다. 버퍼가 오버플로되면 마지막 결과가 폐기됩니다 — 이는 허용 가능합니다. 알고리즘이 필요시 다시 계산할 수 있기 때문입니다. 이 접근 방식은 파서, 컴파일러 및 깊이 제한이 있는 그래프 순회 알고리즘에서 사용됩니다.

LIFO Cache 코드 예제

고정 크기 배열을 사용하는 Kotlin의 LIFO Cache 구현을 살펴보겠습니다. 배열은 모바일 장치에 최고의 성능과 최소한의 메모리 소비를 제공합니다.

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // discard oldest when full
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

인덱스 top은 스택 맨 위를 가리킵니다. push는 top을 증가시키고 값을 씁니다. 배열이 가득 찬 경우(top == maxSize - 1), 쓰기 전에 top이 감소되어 스택 맨 위가 덮어쓰여지며 LIFO 제거가 구현됩니다. pop 메서드는 요소를 반환하고 top을 감소시키며, peek는 스택을 변경하지 않고 맨 위 요소를 읽습니다.

예제: LIFO Cache를 사용한 탐색 스택

Jetpack Compose에서 탐색 깊이를 제한하기 위해 LIFO Cache를 사용하는 것을 고려해 보세요. 새 화면이 열리면 스택에 추가되고, 제한을 초과하면 가장 최근 화면이 제거됩니다.

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

이 예제에서 NavigationStack은 화면 기록을 저장하기 위해 LIFO Cache를 사용합니다. navigateTo가 호출되면 화면이 스택에 추가되고, goBack이 호출되면 마지막 화면이 제거됩니다. 사용자가 10개의 제한으로 11개의 화면을 연 경우, 가장 최근(11번째) 화면이 이전(10번째) 화면을 제거합니다 — 첫 번째 화면은 스택에 남아 있으며, 이는 뒤로 탐색 시 사용자의 기대와 일치합니다. 이 전략은 탐색에서 LRU보다 더 효율적입니다. 오랫동안 열린 화면(“홈”, “프로필”)을 제거하면 예기치 않은 동작이 발생할 수 있습니다.