FIFO Cache — 핵심 개념, 큐 알고리즘 및 작동 방식

FIFO Cache란?

FIFO Cache(First In First Out Cache)는 요소를 관리하기 위해 큐를 사용하는 고정 크기 캐시입니다. 첫 번째로 추가된 요소는 큐의 머리에 배치되며 오버플로우 발생 시 가장 먼저 제거됩니다. 새 요소는 항상 꼬리에 추가되어 제거 순서가 추가 순서와 일치하도록 보장합니다.

액세스할 때마다 요소를 재정렬하는 LRU와 달리, FIFO는 get 요청 시 기존 요소의 위치를 변경하지 않습니다.这使得 알고리즘을 완전히 결정론적으로 만듭니다: 추가 순서를 알면 다음에 어떤 요소가 제거될지 정확히 예측할 수 있습니다. 이러한 예측 가능성은 데이터를 도착 순서대로 처리해야 하는 실시간 시스템에 중요합니다.

FIFO Cache 구현은 여러 데이터 구조로 구축될 수 있습니다: 최대 성능을 위한 원형 버퍼, 유연성을 위한 연결 리스트, 또는 내장 큐가 없는 언어를 위한 두 개의 스택(Two-Stack Queue). 원형 버퍼는 최상의 캐시 지역성과 최소 오버헤드를 제공하지만 maxSize에 대한 메모리 사전 할당이 필요합니다.

FIFO Cache 기본 작업

enqueue(value) 작업은 큐의 꼬리에 요소를 추가합니다. 크기가 maxSize에 도달하면 추가 전에 머리의 요소가 제거됩니다. dequeue() 작업은 머리의 요소를 제거하고 반환합니다 — 가장 오래된 요소의 강제 추출을 위해. peek() 작업은 제거 없이 머리 요소를 반환합니다 — 큐를 변경하지 않고 가장 오래된 요소를 보기 위해.

FIFO Cache 작동 방식

FIFO 알고리즘은 일반 큐의 동작을 모방합니다: 먼저 들어온 것이 먼저 서비스됩니다. 캐싱의 맥락에서 이는 캐시에 가장 오래 있었던 요소가 공간이 필요할 때 제거된다는 것을 의미합니다 — 인기도와 관계없이. FIFO의 제거 정책은 액세스 빈도를 무시하며, 이는 알고리즘의 강점이자 약점입니다.

원형 버퍼로 구현할 때, head(큐 머리의 인덱스)와 tail(꼬리의 인덱스) 두 개의 포인터가 사용됩니다. enqueue 시, 요소는 tail 인덱스에 쓰여지고 tail이 증가합니다. tail이 버퍼 크기에 도달하면 배열의 시작으로 감싸집니다. tail이 head를 따라잡으면 큐가 가득 찬 것이고 head가 이동됩니다(제거). 원형 버퍼는 동적 메모리 할당이 필요 없으며 단편화를 피합니다.

FIFO Cache는 일반적인 워크로드에 대해 40%에서 60%의 hit-ratio를 보여주며, 이는 LIFO보다 높지만 LRU보다는 낮습니다. 그러나 데이터 액세스가 균일하고 핫스팟이 없는 시나리오에서는 FIFO가 훨씬 낮은 구현 복잡성으로 LRU에 필적하는 결과를 보여줄 수 있습니다. 메모리는 효율적으로 사용됩니다: 요소 재정렬을 위한 추가 포인터가 필요하지 않습니다.

캐시 오염 문제

FIFO의 주요 단점은 캐시 오염에 대한 취약성입니다. 다시는 필요하지 않은 대량의 데이터가 캐시에 추가되면 점차 모든 유용한 요소를 제거하고 hit-ratio가 급격히 떨어집니다. LRU는 자주 사용되는 요소가 머리로 이동하여 지속적으로 새로고침되는 반면, 일회성 데이터는 더 빨리 제거되므로 이 문제를 부분적으로 해결합니다. FIFO에서 일회성 데이터는 큐 순서에 의해 자연스럽게 제거될 때까지 캐시에 남아 있습니다.

FIFO, LRU 및 LIFO 비교

FIFO, LRU 및 LIFO 중 선택은 데이터 액세스 패턴과 동작 예측 가능성 요구 사항에 따라 달라집니다. LRU는 대부분의 시나리오에 최적이고, FIFO는 균일한 액세스가 있는 스트리밍 데이터에, LIFO는 스택 구조에 적합합니다.

FIFO는 처리 순서가 도착 순서와 일치해야 하는 시나리오에 이상적입니다: 데이터 버퍼링, 로깅, 이벤트 처리. LRU는 불균일한 액세스(사용자 데이터)가 있는 캐싱에 더 좋습니다. LIFO는 스택 및 실행 취소에만 적용 가능합니다. 대부분의 모바일 애플리케이션에서 LRU가 기본 선택이지만, 엄격한 메모리 제약이나 예측 가능성 요구 사항이 있는 경우 FIFO가 선호될 수 있습니다.

FIFO Cache 사용 사례

FIFO Cache는 제거 예측 가능성이나 데이터 처리 순서가 중요한 시나리오에서 사용됩니다. 주요 사용 사례를 살펴보겠습니다.

스트리밍 데이터 버퍼링

오디오 및 비디오 재생 시, 데이터는 연속 스트림으로 도착하여 일시적으로 버퍼에 저장됩니다. FIFO Cache는 첫 번째로 수신된 조각이 첫 번째로 디코딩에 전송되도록 보장합니다 — 이는 지연 없는 부드러운 재생을 보장합니다. 버퍼 크기는 스트림 비트레이트와 허용 가능한 지연에 따라 선택됩니다: 오디오의 경우 일반적으로 2~5초, 비디오의 경우 10~30초. 데이터 재정렬(LRU처럼)이 의미가 없기 때문에 FIFO는 이러한 시나리오에 이상적입니다.

네트워크 요청 큐

동시 네트워크 요청 수를 제한할 때, FIFO Cache를 사용하여 대기 중인 요청을 저장할 수 있습니다. 첫 번째로 추가된 요청이 먼저 실행되어 애플리케이션의 다른 구성 요소 간에 네트워크 리소스의 공정한 분배를 보장합니다. 이 접근 방식은 OkHttp Dispatcher 및 유사한 라이브러리에서 연결 풀 관리에 사용됩니다.

HTTP 응답 캐싱

모바일 장치의 간단한 HTTP 응답 캐시는 종종 FIFO를 사용합니다. 요청에 대한 응답은 도착 순서대로 저장되며, 제한에 도달하면 가장 오래된 것이 제거됩니다. LRU가 사용자 시나리오에 대해 더 나은 hit-ratio를 제공하지만, FIFO는 구현이 더 간단하고 각 응답에 대한 마지막 액세스 시간을 저장할 필요가 없습니다. 균일한 부하의 API의 경우 FIFO와 LRU 간의 hit-ratio 차이는 최소입니다.

터치 이벤트 처리

모바일 애플리케이션에서 터치 이벤트는 제스처 처리 전에 FIFO 큐에 버퍼링됩니다. 각 이벤트는 발생한 순서대로 처리되어야 하며, 그렇지 않으면 제스처가 올바르게 인식되지 않습니다. 크기 제한이 있는 FIFO Cache는 빠른 스와이프 중 버퍼 오버플로를 방지하며, 애플리케이션이 처리할 수 없는 경우 가장 오래된 이벤트를 폐기합니다.

FIFO Cache 코드 예제

모바일 장치에 가장 효율적인 접근 방식인 원형 버퍼를 사용한 Kotlin의 FIFO Cache 구현을 살펴보겠습니다.

class FifoCache<V>(
    private val maxSize: Int
) {
    private val buffer = arrayOfNulls<V>(maxSize)
    private var head = 0
    private var tail = 0
    private var size = 0

    fun enqueue(value: V) {
        if (size == maxSize) {
            // 가장 오래된 요소 제거
            buffer[head] = null
            head = (head + 1) % maxSize
            size--
        }
        buffer[tail] = value
        tail = (tail + 1) % maxSize
        size++
    }

    fun dequeue(): V? {
        if (size == 0) return null
        val result = buffer[head]
        buffer[head] = null
        head = (head + 1) % maxSize
        size--
        return result
    }

    fun peek(): V? {
        return buffer[head]
    }
}

원형 버퍼는 maxSize를 모듈로로 주기적으로 증가하는 head 및 tail 인덱스를 사용합니다. size == maxSize일 때, enqueue는 먼저 head의 요소(가장 오래된 것)를 제거하고 head를 이동시킨 다음 tail에 새 요소를 씁니다. 모듈러 연산은 자동으로 포인터를 배열의 시작으로 감싸서 수동 데이터 복사를 없앱니다.

두 개의 스택을 통한 Swift 구현

Swift에서 편리한 대안은 두 개의 스택(Two-Stack Queue)을 기반으로 한 FIFO 큐입니다. 모든 enqueue 작업은 첫 번째 스택(push)으로 이동하고, dequeue 시 요소는 역순으로 두 번째 스택으로 전송됩니다 — dequeue를 평균적으로 O(1)로 만듭니다.

struct FifoCache<Value> {
    private let maxSize: Int
    private var inStack = [Value]()
    private var outStack = [Value]()

    mutating func enqueue(value: Value) {
        if inStack.count + outStack.count >= maxSize {
            if outStack.isEmpty {
                outStack = inStack.reversed()
                inStack.removeAll()
            }
            outStack.removeLast()
        }
        inStack.append(value)
    }

    mutating func dequeue() -> Value? {
        if outStack.isEmpty {
            outStack = inStack.reversed()
            inStack.removeAll()
        }
        return outStack.popLast()
    }
}

두 개의 스택은 enqueue 및 dequeue에 대해 분할 상환 O(1) 복잡도를 제공합니다. 제거 시 outStack.removeLast()는 가장 오래된 요소(첫 번째 추가된 것)를 제거합니다. 이 접근 방식은 메모리 사전 할당이 필요하지 않지만, 빈번한 스택 역전 중에 가비지 컬렉터에 추가 부하를 줄 수 있습니다. 메모리가 제한된 모바일 애플리케이션의 경우 원형 버퍼가 더 선호됩니다.