캐시

 

 

 

---

 

캐시란 무엇인가?

 

 

---

 

 

 

 

캐시 (cache)

 

--

캐시는

데이터 접근 비용을 줄이기 위해 일부 데이터를 계산이 이뤄지는 곳에서 가까운 위치에 저장하는 자료 구조다.

 

평소에 컴퓨터의 모든 저장소를 동등하게 취급했지만

(여기서 동등하게 취급했다는 것은 모든 저장소에 접근하는 비용이 비슷하게 취급했다는 의미다.)

사실 모든 데이터 저장소가 동등하지 않다.

 

실제 서로 다른 저장 매체들은

저장 용량, 속도, 비용 사이에 트레이드 오프 관계가 존재한다.

 

트레이드 오프(trade-off) 관계는
한 가지 이점을 얻기 위해 다른 이점을 포기하는 상황을 의미한다.

 

 

저장소 종류

 

CPU 자체의 메모리 (레지스터 or 지역적 캐시)

• 속도가 매우 빠름
• 저장 공간이 작음

컴퓨터의 RAM

• CPU 메모리보다 더 큰 공간을 제공
• CPU 메모리보다 속도가 느림

하드 드라이브

• RAM보다 더 큰 공간을 제공
• RAM보다 속도가 매우 느림

 

캐시 (Cache)
- CPU 내부 또는 근처에 위치하며, 보통 L1, L2, L3 캐시로 계층화되어 있음
- L1 > L2 > L3 순으로 속도가 빠름

지역적 캐시 (Local Cache)
- CPU의 특정 코어 내부 또는 코어 근처에 위치하며, 주로 L1 캐시나 L2 캐시가 이에 해당
- 레지스터보다 느리지만, CPU 코어 근처에 위치하여 여전히 매우 빠른 메모리

레지스터 (Register)
- CPU 내부의 가장 핵심적인 부분에 위치
- CPU 내에서 가장 빠른 메모리로 직접 연산에 사용되며, CPU가 즉시 접근 가능

 

 

그래서 일반적으로

캐시 메모리에는 자주 사용하는 데이터들을 저장하고

하드 드라이브에는 가끔 사용하는 데이터들을 저장하여

접근 비용을 최대한 적게 들도록 구성한다.

 

만약 캐시 메모리에 데이터가 가득 차게 되면

어떠한 데이터를 유지하고 어떠한 데이터를 교체할지 결정해야 한다.

 

이 때 교체된 데이터를 캐시에서는 "만료된 데이터"라고 부른다.

--

 

 

 

 

LRU 만료와 캐시

 

--

LRU (Least Recently Used, 최근에 가장 적게 사용된)은

최근에 사용한 정보(데이터)를 캐시에 유지하는 것으로,

주로 컴퓨터에서 캐시 메모리 관리나 페이지 교체 알고리즘에서 사용되는 기법이다.

 

LRU 알고리즘은
가장 오랫동안 사용되지 않은 데이터를 우선적으로 교체하는 방식

LRU 만료 전략은
캐시에서 데이터를 관리할 때, 사용되지 않은지 가장 오래된 항목을 제거하여
새로운 데이터를 저장할 공간을 만드는 전약이다.

 

 

LRU 캐시 구축 방법

LRU 전략을 이용하는 캐시는

1. 임의의 원소(데이터)를 찾는 작업
2. (제거 대상이 될) 최근에 가장 사용하지 않은 윈소를 찾는 작업

위 두 가지 작업을 지원해야 하며, 두 작업 모두 빠르게 수행할 수 있어야 한다.

(캐시의 목적은 데이터를 읽는 연산을 가속시키는 것이기 때문이다.)

 

 

LRU 캐시는

해시 테이블과 큐를 이용하여 구축할 수 있다.

 

해시 테이블은 캐시에 있는 모든 항목을 효율적으로 탐색해 빠른 조회를 수행할 수 있게 해 준다.

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 자료 구조로, 최근에 사용하지 않은 항목을 추적할 수 있게 해 준다.

 

 

LRU 캐시 구조 클래스 [JAVA]

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache<K, V> {
    private final int maxSize;
    private int currentSize;
    private final Map<K, V> ht; // HashTable 역할을 하는 HashMap
    private final LinkedList<K> q; // Queue 역할을 하는 LinkedList

    public LRUCache(int maxSize) {
        this.maxSize = maxSize;
        this.currentSize = 0;
        this.ht = new HashMap<>();
        this.q = new LinkedList<>();
    }
    
    ...
}

 

 

해시 테이블과 큐를 결합하여 구현한 LRU 캐시 구조

 

 

데이터를 키로 탐색하는 예시 코드 [JAVA]

class CacheEntry<K, V> {
    K key;
    V value;
    LinkedList.Node<K> node; // 큐에서의 노드 위치를 가리킵니다.

    CacheEntry(K key, V value, LinkedList.Node<K> node) {
        this.key = key;
        this.value = value;
        this.node = node;
    }
}

public class LRUCache<K, V> {
    private final int maxSize;
    private int currentSize;
    private final HashMap<K, CacheEntry<K, V>> ht;
    private final LinkedList<K> q;

    public LRUCache(int maxSize) {
        this.maxSize = maxSize;
        this.currentSize = 0;
        this.ht = new HashMap<>();
        this.q = new LinkedList<>();
    }

    public V CacheLookup(K key) {
        // 해시 테이블에 해당 키가 존재하는지 확인
        CacheEntry<K, V> entry = ht.get(key);

        if (entry == null) {
            // 캐시에 항목이 없을 때
            if (currentSize >= maxSize) {
                // 캐시가 가득 찼으면 가장 오래된 항목 제거
                K keyToRemove = q.removeLast();
                ht.remove(keyToRemove);
                currentSize--;
            }

            // 느린 데이터 소스에서 데이터를 읽음 (예: 데이터베이스나 파일 시스템)
            V data = slowDataSourceLookup(key);

            // 새 항목을 큐의 가장 앞에 추가하고 해시 테이블에 저장
            q.addFirst(key);
            entry = new CacheEntry<>(key, data, q.getFirstNode());
            ht.put(key, entry);
            currentSize++;
        } else {
            // 이미 캐시에 있는 경우, 해당 항목을 최신으로 업데이트
            q.remove(entry.node);
            q.addFirst(key);
            entry.node = q.getFirstNode();
        }
        return entry.value;
    }

    private V slowDataSourceLookup(K key) {
        // 실제 데이터 소스에서 데이터를 읽어오는 코드 (예시)
        // 여기서는 임의로 null을 반환하지만, 실제로는 데이터베이스 등에서 데이터를 읽어옵니다.
        return null;
    }
}

--

 

 

 

 

다른 만료 전략들

 

--

LRU (Least Recently Used) 만료 전략과 다른 전략으로는

 

• MRU (Most Recently Used, )
• LFU (Least Frequently Used)
• 예측 전략 (Predictive Strategy)

이 존재한다.

 

• LRU  :  가장 오랫동안 사용되지 않은 데이터를 먼저 제거하는 전략
• MRU  :  가장 최근에 사용된 데이터를 먼저 제거하는 전략
• LFU  :  가장 적게 사용된 데이터를 먼저 제거하는 전략
• 예측 전략  :  과거 데이터 접근 패턴을 분석하여 미래의 접근 패턴을 예측하는 전략

--