캐시, 캐시 알고리즘 및 캐시 프레임워크의 이해와 구현

왜 캐시가 필요한가?

애플리케이션에서 데이터를 반복적으로 데이터베이스에서 조회하는 경우, 시스템 성능은 점차 저하된다. 특히 고빈도로 접근되는 데이터일수록 지연 시간과 리소스 소모가 커지며, DB는 부하로 인해 응답 속도가 떨어지고 전체 서비스 품질이 나빠진다. 이러한 문제를 해결하기 위해 도입된 개념이 바로 캐시다.

캐시는 자주 사용되는 데이터를 임시 저장 공간에 두어, 원본 데이터를 매번 조회하지 않아도 되도록 하는 기술이다. 이를 통해 읽기 작업의 지연을 줄이고, 백엔드 시스템의 부담을 완화할 수 있다.

핵심 캐시 용어 정리

  • 캐시 히트(Cache Hit): 요청한 데이터가 캐시에 존재하여 빠르게 반환되는 경우.
  • 캐시 미스(Cache Miss): 캐시에 데이터가 없어 원본 저장소(예: DB)에서 가져와야 하는 경우.
  • 저장 비용(Storage Cost): 캐시에 데이터를 적재하는 데 드는 시간과 메모리 자원.
  • 인덱싱 비용(Indexing Cost): 캐시 내에서 데이터를 빠르게 탐색하기 위한 인덱스 관리 오버헤드.
  • 유효성 만료(Invalidation): 캐시된 데이터가 더 이상 최신 상태가 아닐 때 제거하거나 갱신하는 과정.
  • 교체 정책(Replacement Policy): 캐시가 가득 찼을 때 어떤 항목을 제거할지 결정하는 알고리즘.

대표적인 캐시 교체 알고리즘

캐시 용량은 제한적이므로, 미스 발생 시 새로운 항목을 저장하기 위해 기존 항목을 제거해야 한다. 이때 어떤 전략을 사용하느냐가 성능에 큰 영향을 미친다.

LRU (Least Recently Used)

가장 최근에 적게 사용된 항목을 제거한다. 최근 접근 이력을 기반으로 하며, 실세계 애플리케이션에서 가장 널리 사용된다. 예를 들어 브라우저의 히스토리나 세션 저장소 등에서 활용된다.

구현은 더블리 링크드 리스트와 해시 맵 조합으로 효율적으로 가능하다. 접근 시 해당 노드를 리스트 앞쪽으로 이동시킨다.

FIFO (First In First Out)

가장 먼저 삽입된 항목부터 제거한다. 큐 구조를 사용하며 구현이 간단하고 오버헤드가 낮지만, 접근 패턴을 반영하지 못해 성능이 상대적으로 떨어진다.

LFU (Least Frequently Used)

사용 빈도가 가장 낮은 항목을 제거한다. 각 항목의 접근 횟수를 카운트하며, 장기적으로 덜 사용되는 데이터를 식별할 수 있다. 그러나 초기에 자주 접근된 후 사용되지 않는 데이터는 오랫동안 캐시에 남을 수 있는 단점이 있다.

ARC (Adaptive Replacement Cache)

LRU와 LFU의 특성을 혼합한 알고리즘로, 두 개의 LRU 리스트를 관리한다. 하나는 새로 추가된 항목(L1), 다른 하나는 반복적으로 접근된 항목(L2)을 저장한다. 이를 통해 접근 패턴에 자동으로 적응하며 높은 히트율을 제공한다. 성능은 우수하나 구현 복잡도가 높다.

Clock 알고리즘

FIFO 기반의 확장형으로, 원형 버퍼 형태의 리스트를 사용한다. 각 항목은 참조 비트(reference bit)를 가지며, 교체 시점에 이 비트를 확인한다. 비트가 켜져 있으면 다음 후보로 넘기고 비트를 끈다. 껐을 경우 해당 항목을 제거한다. Second-Chance 알고리즘보다 포인터 이동이 효율적이며, 성능과 단순성의 균형을 잘 유지한다.

시간 기반 만료 정책

  • Fixed Expiration: 삽입 시점으로부터 일정 시간 후 자동 만료.
  • Sliding Expiration: 마지막 접근 시점을 기준으로 유효 기간을 연장. 활발히 사용되는 항목은 계속 살아남는다.

캐시 엔티티 설계

모든 캐시 알고리즘은 공통적으로 데이터를 담는 기본 단위가 필요하다. 아래는 일반적인 캐시 요소 클래스의 예시다.

public class CacheEntry<K, V> {
    private K key;
    private V value;
    private int accessCount;
    private long lastAccessTime;

    public CacheEntry(K key, V value) {
        this.key = key;
        this.value = value;
        this.accessCount = 1;
        this.lastAccessTime = System.currentTimeMillis();
    }

    // getter/setter 생략
}

공통 삽입 로직

모든 캐시 구현은 키 존재 여부를 먼저 확인하고, 없을 경우 교체 정책에 따라 공간을 확보해야 한다.

protected synchronized void put(K key, V value) {
    CacheEntry<K, V> existing = entryMap.get(key);
    if (existing != null) {
        existing.setValue(value);
        existing.setLastAccessTime(System.currentTimeMillis());
        onAccess(existing); // 알고리즘별 접근 처리
        return;
    }

    if (isAtCapacity()) {
        CacheEntry<K, V> victim = selectEvictionCandidate();
        entryMap.remove(victim.getKey());
        onEvict(victim);
    }

    CacheEntry<K, V> entry = new CacheEntry<>(key, value);
    entryMap.put(key, entry);
    onInsert(entry);
}

LRU 구현 예제

더블리 링크드 리스트를 사용해 최근 사용 순서를 관리한다.

private final Map<K, CacheEntry<K, V>> entryMap = new HashMap<>();
private final LinkedList<CacheEntry<K, V>> lruList = new LinkedList<>();

private void onAccess(CacheEntry<K, V> entry) {
    lruList.remove(entry);
    lruList.addFirst(entry);
}

private void onInsert(CacheEntry<K, V> entry) {
    lruList.addFirst(entry);
}

private CacheEntry<K, V> selectEvictionCandidate() {
    return lruList.removeLast();
}

분산 환경에서의 캐시

단일 서버를 넘어선 애플리케이션에서는 분산 캐시가 필수적이다. Redis, Memcached 같은 외부 캐시 서버를 사용하면 여러 인스턴스 간 데이터 일관성을 유지할 수 있으며, 별도의 메모리 공간으로 운영되어 애플리케이션 자체의 GC 영향을 줄일 수 있다.

또한, 캐시 클러스터링, 샤딩, 복제 등을 통해 가용성과 확장성을 보장할 수 있다.

요약 및 선택 기준

어떤 캐시 알고리즘을 선택할지는 실제 워크로드의 특성에 따라 달라진다.

  • 일반적인 웹 애플리케이션: LRU 또는 Sliding Expiration 기반 정책이 적합.
  • 고정 패턴의 대량 데이터 접근: LFU나 ARC가 더 나은 히트율을 제공할 수 있음.
  • 저지연이 중요한 시스템: FIFO나 Clock처럼 단순하고 예측 가능한 알고리즘이 유리.
  • 외부 캐시 사용: Redis는 LRU 기반 정책을 기본으로 하며, TTL 설정을 통한 유연한 만료 지원.

알고리즘 자체보다도, 데이터 접근 패턴 분석과 모니터링을 통한 지속적인 최적화가 성공적인 캐시 운용의 핵심이다.

태그: cache LRU LFU ARC Clock algorithm

6월 11일 18:33에 게시됨

인기 태그

©2026 괴물 클럽