온라인 알고리즘의 경쟁 분석과 LRU 캐시·스케줄링 설계

미래 입력이 보이지 않는 상태에서 결정하기

온라인 알고리즘은 입력이 순차적으로 도착할 때 미래 정보를 알지 못한 채 단계별 결정을 즉시 내리는 알고리즘 패러다임이다. 전체 입력을 미리 알고 처리하는 오프라인 알고리즘과 달리 정보 비대칭을 전제로 한다.

성능은 경쟁적 분석(Competitive Analysis)으로 다룬다. 같은 입력에 대한 온라인 알고리즘 비용과 최적 오프라인 비용의 비율인 경쟁비(competitive ratio)를 사용한다. 알고리즘이 c-경쟁적이라는 말은 모든 입력 (I)에 대해 다음을 만족한다는 뜻이다.

Cost_online(I) ≤ c·Cost_OPT(I) + b

보통 (b=0)을 가정한다. 입력 생성자가 어느 정도의 정보를 갖는지도 분석 결과에 영향을 준다. 적대자(adversary)는 Oblivious와 Adaptive로 구분할 수 있으며, Adaptive 모델은 알고리즘의 반응을 알고 입력을 조정할 수 있어 더 강한 하한을 이끌어 낸다.

온라인 스케줄링에서는 동적으로 도착하는 작업을 기계나 코어에 할당하고, 필요하면 선점하거나 마감시간에 대응한다. 목적함수는 최대 완성시간(Cmax), 지연, 흐름시간 등이 될 수 있다. 캐싱에서는 제한된 저장 공간에서 미스가 발생했을 때 어떤 항목을 내보낼지 정해야 하며, LRU(Least Recently Used)는 가장 오래 사용되지 않은 항목을 제거한다. 이 정책은 시간 지역성이 있는 워크로드에서 좋은 성능을 낸다.

분석과 구현에서 먼저 고정할 기준

온라인 정책을 설계할 때는 입력 공간, 적대자 모델, 비용 함수를 먼저 명확히 둬야 한다. 그다음 오프라인 최적해(OPT)를 비교 기준으로 삼고 추가 상수항의 유무를 표시한다. 그리디, 임계값, 무작위화 같은 정책을 선택한 뒤에는 잠금 불변식이나 전위 함수(potential function)로 상한을 증명하고, 반례를 통해 하한을 검증한다.

실제 검증에는 트레이스 리플레이와 합성 워크로드를 사용할 수 있다. 평균과 백분위수 지표를 함께 확인하면 최악 조건의 보장과 평상시 성능을 분리해 볼 수 있다.

페이징 문제에서는 LRU 같은 결정론적 정책이 캐시 크기 (k)에 대해 경쟁비 (k)를 보장한다. 강한 적대자를 두면 보수적인 보장을 얻을 수 있고, 확률적 입력 가정에서는 기대 성능이 더 좋아질 수 있다. 무작위화(Randomization)는 하한을 피하기 위한 선택지가 된다.

운영 단계에서는 알고리즘 자체만으로 충분하지 않다. 해시와 연결리스트 같은 O(1) 갱신 구조, 동시성 제어, 장애 복구, 관측 가능성(telemetry)을 함께 설계해야 한다. 온라인 결정은 되돌리기 어렵거나 롤백 비용이 클 수 있으므로, 상태 전이와 비용을 분리해 관찰하는 편이 낫다.

LRU의 상태를 유지하는 방식

LRU 캐시는 키를 빠르게 찾는 해시와 최근 사용 순서를 보존하는 이중연결리스트를 결합한다. 요청한 키가 캐시에 있으면 값을 반환하고 해당 노드를 MRU 위치로 옮긴다. 없으면 용량을 확인한 뒤 삽입하고, 가득 찼다면 꼬리의 LRU 항목을 제거한다.

⤢✕

이 구조의 불변식은 두 가지다. 해시는 O(1) 접근을 담당하고, 이중연결리스트는 최근성 순서를 유지한다.

LRU를 설계하고 테스트할 때는 키·값 스트림과 캐시 용량 (k)를 입력으로 둔다. 히트 시에는 노드를 재배치하고, 미스 시에는 LRU 항목을 제거한 뒤 삽입한다. 동시성 환경에서는 락 또는 원자성을 보장해야 한다. 조회·갱신 결과와 함께 히트율, eviction 카운터를 노출하고, (k=0), 존재하지 않는 키 조회, 큰 값으로 인한 메모리 압력도 처리 범위에 포함한다.

작업이 들어오는 즉시 배치하는 스케줄러

동일한 기계 (m)대에서 makespan을 최소화할 때 List Scheduling은 도착 순서대로 현재 가용 시점이 가장 빠른 기계에 작업을 즉시 배정한다. 이 방식은 (2 - 1/m)의 경쟁비를 보장한다. (m=1)일 때는 1-경쟁이며, (m→∞)일 때 상한은 2에 근사한다.

배치 처리, CI/CD 빌드 파밍, 쿠버네티스 스케줄러 플러그인에서는 큐 우선순위와 빈도수 기반 tie-breaking을 이 정책과 결합할 수 있다.

마감시간이 중요한 단일 코어 실시간 시스템에서는 선점이 가능할 때 EDF(Earliest Deadline First)를 적용할 수 있다. 타당성 검사와 함께 사용하며, 동적 삽입은 우선순위 큐로 O(log n)에 처리한다. 오버로드 상황에서는 스로틀링과 Admission Control로 QoS를 보장한다.

다만 처리시간이 불확실하면 선점이 지나치게 자주 일어나 오버헤드가 커질 수 있다. 시간 슬라이스 상한과 쿨다운을 두는 방식이 필요하다.

LRU 캐시 구현과 운영 지표

다음 구현은 단일 스레드, 해시 가능한 키, 메모리 내 캐시를 전제로 한다.

# Python 3.10+
from __future__ import annotations
from typing import Any, Optional

class _Node:
    __slots__ = ("k", "v", "prev", "next")
    def __init__(self, k: Any, v: Any):
        self.k, self.v = k, v
        self.prev: Optional[_Node] = None
        self.next: Optional[_Node] = None

class LRUCache:
    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("capacity must be >= 0")
        self.cap = capacity
        self.map: dict[Any, _Node] = {}
        # dummy head/tail
        self.head, self.tail = _Node(None, None), _Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.hits = 0
        self.misses = 0

    def _remove(self, node: _Node):
        p, n = node.prev, node.next
        if p: p.next = n
        if n: n.prev = p
        node.prev = node.next = None

    def _insert_front(self, node: _Node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: Any) -> Optional[Any]:
        if self.cap == 0:
            self.misses += 1
            return None
        node = self.map.get(key)
        if not node:
            self.misses += 1
            return None
        self._remove(node)
        self._insert_front(node)
        self.hits += 1
        return node.v

    def put(self, key: Any, value: Any) -> None:
        if self.cap == 0:
            return
        if key in self.map:
            node = self.map[key]
            node.v = value
            self._remove(node)
            self._insert_front(node)
            return
        # evict if full
        if len(self.map) >= self.cap:
            lru = self.tail.prev
            if lru and lru.k is not None:
                self._remove(lru)
                del self.map[lru.k]
        node = _Node(key, value)
        self.map[key] = node
        self._insert_front(node)

    def hit_ratio(self) -> float:
        total = self.hits + self.misses
        return (self.hits / total) if total else 0.0

# Quick test
if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put("a", 1); cache.put("b", 2)
    assert cache.get("a") == 1  # hit, a becomes MRU
    cache.put("c", 3)           # evict LRU: b
    assert cache.get("b") is None
    assert cache.get("a") == 1
    assert 0.0 <= cache.hit_ratio() <= 1.0

get과 put은 O(1)을 보장한다. 멀티스레드 환경으로 확장할 때는 세그먼트 락, RW 락, 샤딩 기반 파티셔닝을 고려할 수 있다. 운영에서는 히트율, 평균/95퍼센타일 지연, evictions/sec, 메모리 사용량을 확인한다.

용량은 목표 히트율 (H)와 워킹 셋 크기 (W)를 추정한 뒤 (k ≈ α·W), (α≈1.1~1.3)으로 설정한다. 스캔 패턴을 방어하려면 LRU+TTL(만료 시간), LRU-K, 2Q 같은 혼합 정책을 검토한다. 콜드 스타트에는 프리워밍(pre-warm)이나 요청 미러링을 활용할 수 있으며, 장애 복구 시에는 write-through와 write-back 중 하나를 고르고 재시도·일관성 전략을 병행한다.

워크로드에 맞춰 고르는 캐시 정책

정책	성능(평균 히트)	확장성	일관성	안정성(스캔 내성)	운영 편의
LRU	시간 지역성 강한 워크로드에서 우수	해시+리스트로 수평 확장 용이	결정론적, 예측 가능	중간, 스캔에 취약	구현 용이, 광범위 지원
LFU	장기 인기 편향에서 최고	카운터 유지 비용, 근사(LFU-Decay) 필요	인기 급변 시 반응 느림	높음(스캔 강인)	운영 복잡도↑
FIFO	단순, 낮은 오버헤드	매우 용이	순서 의존, 품질 변동	낮음	구현 최단, 디버깅 용이

정책 선택은 시간·빈도 지역성을 포함한 요청 분포, 변동성, 구현과 운영 비용의 트레이드오프에 달려 있다.

CDN과 엣지 캐시에서는 LRU 또는 2Q로 뉴스·영상 트래픽 변화에 대응하며, 오리진 부하를 30~70% 절감한 사례가 있다. 데이터베이스 버퍼 풀은 핀 고정과 스캔 감지를 더한 LRU 변형으로 대용량 스캔 영향을 줄인다. 마이크로서비스 API 캐시는 TTL+LRU와 키 무효화 전략을 결합해 SLA를 안정화할 수 있다. 배치·빌드 파밍에서는 List Scheduling 기반의 큐 우선순위화로 평균 대기시간을 줄이고, 컨테이너 오토스케일링은 스케줄러 대기열 길이와 CPU 포화율을 수평 확장 트리거로 활용한다.

캐시 히트율이 1540%p 개선되고 미스율이 0.6→0.3이 되면 외부 호출 절감으로 평균 지연이 2050% 감소한다. 빌드·배치 스케줄링은 Cmax 근사 보장 (2 - 1/m)으로 최악 지연 상한을 관리할 수 있다. 오리진 트래픽은 30~60% 오프로딩해 네트워크 비용을 줄일 수 있다.

명확한 비용 함수와 경쟁적 벤치마크가 있으면 미래 불확실성 아래에서도 성능 보장을 제시할 수 있다. 지역 정보만으로 결정을 내리는 구조는 구현·운영 복잡도를 완화하고, 예측하기 어려운 워크로드 변화에 대한 회복탄력성을 높인다.