LRU (Least Recently Used) algorithm 알아보기

- 목차

 

함께 보면 좋은 글.

https://westlife0615.tistory.com/17

MySQL Buffer Pool 알아보기

소개.

이번 글에서는 LRU 알고리즘에 대해서 알아보려고 합니다.

LRU 알고리즘은 Least Recently Used Algorithm 의 약자인데요.

Cache Memory 를 구현하기 위해서 흔히 사용되는 알고리즘이자 자료구조입니다.

Cache, Buffer 등은 Data Access 의 속도를 높이기 위해서 데이터 저장 관점에서 사용하는 방식인데요.

흔히 Register - Cache - Memory - Disk 로 이어지는 메모리의 계층 구조를 보신적이 있으신 겁니다.

 

< 출처 : https://www.alibabacloud.com/blog/the-mechanism-behind-measuring-cache-access-latency_599384 >

 

Caching 은 사용 빈도가 높은 데이터들 또는 최근에 사용된 데이터들이 재접근될 확률이 높다는 판단에 의거하여

Faster Memory 영역에 저장하는 방식인데요.

 

LRU Cache 는 최근에 사용된 데이터들를 Faster Memory 영역에 저장하는 방식입니다.

 

이번 글에서는 LRU Cache 에 대해서 알아보려고 합니다.

 

LRU (Least Recently Used) 이란 ?

LRU 는 Least Recently Used 의 약자이구요. 번역을 하면 "가장 최근에 사용된" 으로 해석됩니다.

즉, 가장 최근에 사용된 데이터가 우선순위를 가지게 됩니다.

이러한 관점에서 알고리즘과 자료구조를 구현해야 됩니다.

LRU Cache 구조를 사용하는 여러 어플리케이션들이 있습니다.

대표적으로 MySQL 과 Hadoop DataNode 가 있는데요.

MySQL 은 Buffer Pool 이라는 In-Memory 영역을 가집니다.

그리고 Buffer Pool 은 효율을 위해서 많은 양의 Block 들을 메모리에서 관리하게 되는데,

이때 LRU 알고리즘에 의거하여 최근에 Read 된 Block 들이 메모리에 존재하게 됩니다.

 

LRU Algorithm 구현하기.

아래 예시는 LRU Algorithm 을 구현한 예시입니다.

ChatGPT 에게 질문한 후 답변으로 얻은 예시입니다.

 

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;

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

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

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }

    public static void main(String[] args) {
        // Creating an LRU cache with a maximum size of 3
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        // Function to compute a result (simulated expensive computation)
        Function<Integer, String> expensiveFunction = key -> {
            System.out.println("Computing result for key: " + key);
            return "Result for key " + key;
        };

		cache.compute(1, (key, existingValue) -> existingValue != null ? existingValue : expensiveFunction.apply(key));
	    cache.compute(2, (key, existingValue) -> existingValue != null ? existingValue : expensiveFunction.apply(key));
	    cache.compute(3, (key, existingValue) -> existingValue != null ? existingValue : expensiveFunction.apply(key));
    	cache.compute(4, (key, existingValue) -> existingValue != null ? existingValue : expensiveFunction.apply(key));

	    System.out.println("size is " + cache.size());
    	System.out.println("4 is present " + cache.containsKey(4));
	    System.out.println("3 is present " + cache.containsKey(3));
    	System.out.println("2 is present " + cache.containsKey(2));
	    System.out.println("1 is present " + cache.containsKey(1));
    }
}

 

보통 Java 에서 LRU Cache 를 구현하기 위해서 LinkedHashMap, LinkedHashSet 를 사용합니다.

LinkedHashMap 또는 LinkedHashSet 은 LinkedList 와 Map 또는 Set 의 조합이구요.

여러 Entry 들이 Linked 되어있는 자료구조입니다.

이러한 Link 가 Least-Recently-Used 라는 관점에서 우선순위를 부여하는 Link 이기 때문에

오래된 Entry 를 쉽게 제거할 수 있게 됩니다.

 

즉, Cache Size 와 Recency 에 대한 우선순위 모두 만족시킬 수 있는 자료구조가 됩니다.

 

위 코드 실행의 결과는 아래와 같습니다.

Computing result for key: 1
Computing result for key: 2
Computing result for key: 3
Computing result for key: 4
size is 3
4 is present true
3 is present true
2 is present true
1 is present false