Theme:

캐시 교체 알고리즘 — LRU, LFU, 그리고 Redis의 선택

알고리즘캐시Redis
2026-04-11·6 min read

캐시가 가득 찼을 때, 어떤 데이터를 지워야 가장 효율적일까요?

개념 정의

캐시의 용량은 제한되어 있습니다. 새 데이터를 넣어야 하는데 공간이 없으면, 기존 데이터 중 하나를 교체(eviction) 해야 합니다. 어떤 데이터를 버릴지 결정하는 전략이 캐시 교체 알고리즘 입니다.

왜 필요한가

  • **Redis 메모리 관리 **: maxmemory에 도달했을 때 어떤 키를 삭제할지
  • **CPU 캐시 **: L1/L2/L3 캐시 라인 교체
  • CDN: 어떤 콘텐츠를 캐시에 유지할지
  • Spring Cache: @CacheEvict 정책 설정

캐시 적중률(hit rate)이 교체 알고리즘에 따라 크게 달라지므로, 워크로드에 맞는 알고리즘 선택이 중요합니다.

LRU (Least Recently Used)

** 가장 오래 전에 사용된 항목을 교체 합니다. "최근에 사용한 것은 곧 다시 사용될 가능성이 높다"는 ** 시간적 지역성(temporal locality) 가정에 기반합니다.

LinkedHashMap으로 구현

Java의 LinkedHashMap은 accessOrder=true로 설정하면 접근 순서를 유지합니다.

JAVA
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // 용량 초과 시 가장 오래된 항목 제거
    }
}

// 사용
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.get("a");        // a를 최근 사용으로 이동
cache.put("d", "4");   // b가 제거됨 (가장 오래 전에 사용)

HashMap + DoublyLinkedList로 구현

O(1) get/put을 보장하는 직접 구현입니다.

JAVA
public class LRUCacheManual {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private int capacity;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0, 0); // 더미 헤드
    private Node tail = new Node(0, 0); // 더미 테일

    public LRUCacheManual(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node); // 최근 사용으로 이동
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (map.size() == capacity) {
                Node lru = tail.prev; // 가장 오래된 항목
                removeNode(lru);
                map.remove(lru.key);
            }
            Node newNode = new Node(key, value);
            addToHead(newNode);
            map.put(key, newNode);
        }
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
}

LFU (Least Frequently Used)

** 사용 빈도가 가장 낮은 항목을 교체 **합니다. 빈도가 같으면 가장 오래된 항목을 교체합니다.

JAVA
public class LFUCache {
    private int capacity, minFreq;
    private Map<Integer, int[]> keyToValFreq;         // key → [value, freq]
    private Map<Integer, LinkedHashSet<Integer>> freqToKeys; // freq → keys (순서 유지)

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyToValFreq = new HashMap<>();
        this.freqToKeys = new HashMap<>();
    }

    public int get(int key) {
        if (!keyToValFreq.containsKey(key)) return -1;
        increaseFreq(key);
        return keyToValFreq.get(key)[0];
    }

    public void put(int key, int value) {
        if (capacity == 0) return;

        if (keyToValFreq.containsKey(key)) {
            keyToValFreq.get(key)[0] = value;
            increaseFreq(key);
            return;
        }

        if (keyToValFreq.size() == capacity) {
            // 최소 빈도 중 가장 오래된 키 제거
            LinkedHashSet<Integer> minFreqKeys = freqToKeys.get(minFreq);
            int evictKey = minFreqKeys.iterator().next();
            minFreqKeys.remove(evictKey);
            keyToValFreq.remove(evictKey);
        }

        keyToValFreq.put(key, new int[]{value, 1});
        freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void increaseFreq(int key) {
        int[] valFreq = keyToValFreq.get(key);
        int freq = valFreq[1];

        freqToKeys.get(freq).remove(key);
        if (freqToKeys.get(freq).isEmpty()) {
            freqToKeys.remove(freq);
            if (minFreq == freq) minFreq++;
        }

        valFreq[1] = freq + 1;
        freqToKeys.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }
}

LRU vs LFU 비교

항목LRULFU
교체 기준최근 사용 시점사용 빈도
장점구현 간단, 적응력 좋음인기 데이터 보호
단점스캔에 의한 오염새 데이터에 불리, 빈도 누적 문제
적합 상황일반적인 워크로드인기 데이터가 명확한 경우

스캔 오염(scan pollution) 문제

대량의 데이터를 한 번 순회하면 LRU 캐시가 모두 밀려납니다. 예를 들어 배치 작업으로 DB 전체를 스캔하면, 인기 데이터가 캐시에서 밀려나는 문제가 있습니다.

Redis의 maxmemory-policy

Redis는 다양한 교체 정책을 제공합니다.

PLAINTEXT
# redis.conf
maxmemory 256mb
maxmemory-policy allkeys-lru
정책설명
noeviction교체 안 함, 메모리 초과 시 에러 (기본값)
allkeys-lru모든 키 중 LRU로 교체
allkeys-lfu모든 키 중 LFU로 교체
volatile-lruTTL이 설정된 키 중 LRU로 교체
volatile-lfuTTL이 설정된 키 중 LFU로 교체
allkeys-random모든 키 중 랜덤 교체
volatile-ttlTTL이 가장 짧은 키부터 교체

Redis의 근사 LRU

Redis는 정확한 LRU가 아닌 ** 근사 LRU**를 사용합니다. 모든 키의 사용 시점을 추적하려면 메모리가 많이 필요하기 때문입니다.

PLAINTEXT
알고리즘:
1. 랜덤으로 5개(기본값) 키를 샘플링
2. 그 중 가장 오래 전에 사용된 키를 교체
3. maxmemory-samples 값을 높이면 정확도 증가 (기본값: 5)

샘플 수를 10으로 올리면 정확한 LRU에 가까워지지만, CPU 비용이 증가합니다.

Spring Cache와 교체 전략

JAVA
@Configuration
@EnableCaching
public class CacheConfig {

    @Bean
    public CacheManager cacheManager() {
        CaffeineCacheManager manager = new CaffeineCacheManager("users");
        manager.setCaffeine(Caffeine.newBuilder()
            .maximumSize(1000)        // 최대 1000개
            .expireAfterWrite(10, TimeUnit.MINUTES) // 10분 후 만료
            .recordStats());          // 통계 기록
        return manager;
    }
}

@Service
public class UserService {
    @Cacheable("users")
    public User findById(Long id) {
        return userRepository.findById(id).orElseThrow();
    }

    @CacheEvict(value = "users", key = "#id")
    public void updateUser(Long id, UserDto dto) {
        // 업데이트 후 캐시 무효화
    }
}

Caffeine은 내부적으로 W-TinyLFU 라는 알고리즘을 사용합니다. LRU와 LFU의 장점을 결합한 것으로, 현재 Java 캐시 라이브러리 중 가장 높은 적중률을 보입니다.

기타 교체 알고리즘

알고리즘설명특징
FIFO먼저 들어온 것을 먼저 교체단순하지만 성능 낮음
LRU-K최근 K번째 접근 시점 기준K=2가 실무에서 자주 사용
ARCLRU + LFU 적응형 결합IBM 특허, ZFS에서 사용
W-TinyLFU윈도우 + 빈도 기반Caffeine에서 사용, 최고 수준 적중률
ClockLRU 근사, 원형 버퍼 기반OS 페이지 교체에서 사용

주의할 점

Redis의 기본 정책이 noeviction인 것을 모르는 실수

Redis의 기본 maxmemory-policy는 noeviction입니다. 메모리가 가득 차면 쓰기 명령이 에러를 반환합니다. 프로덕션에서는 반드시 allkeys-lru나 allkeys-lfu 등으로 명시적 설정이 필요합니다.

LRU가 만능이 아닌 상황

일시적으로 대량의 데이터를 스캔하면 LRU 캐시에서 자주 사용되던 인기 데이터가 밀려납니다. 이런 패턴에서는 LFU(빈도 기반)가 더 적합합니다.

정리

  • LRU: 가장 오래 전에 사용된 항목을 교체. LinkedHashMap으로 간단히 구현 가능합니다
  • LFU: 사용 빈도가 가장 낮은 항목을 교체. 인기 데이터 보호에 유리합니다
  • Redis는 ** 근사 LRU/LFU**를 사용하여 메모리 효율과 정확도의 균형을 맞춥니다
  • Spring Cache + Caffeine은 W-TinyLFU 로 높은 적중률을 제공합니다
  • 워크로드 특성(접근 패턴, 스캔 빈도 등)에 따라 적절한 알고리즘을 선택해야 합니다
related posts
댓글 로딩 중...
On This Page
개념 정의왜 필요한가LRU (Least Recently Used)LinkedHashMap으로 구현HashMap + DoublyLinkedList로 구현LFU (Least Frequently Used)LRU vs LFU 비교스캔 오염(scan pollution) 문제Redis의 maxmemory-policyRedis의 근사 LRUSpring Cache와 교체 전략기타 교체 알고리즘주의할 점Redis의 기본 정책이 noeviction인 것을 모르는 실수LRU가 만능이 아닌 상황정리