LRU (Least Recently Used)와 LFU (Least Frequently Used) 알고리즘

LRU와 LFU는 캐시 관리 알고리즘으로, 제한된 크기의 캐시에 데이터를 효율적으로 저장하고 교체하는 방식입니다.

---

1. LRU (Least Recently Used, 가장 오래된 데이터 제거)

LRU는 가장 최근에 사용되지 않은(오래된) 데이터를 제거하는 방식입니다.

LRU 동작 방식

1. 데이터를 요청하면 캐시에 저장 (캐시 공간이 가득 차지 않았다면 그대로 저장)
2. 이미 캐시에 있는 데이터를 요청하면 해당 데이터를 가장 최신 위치로 갱신
3. 캐시가 가득 찼을 때 가장 오래 사용되지 않은 데이터를 제거

LRU 예제

• 캐시 크기: 3
• 요청 순서: [A, B, C, A, D]

1. A 요청 → [A]
2. B 요청 → [A, B]
3. C 요청 → [A, B, C]
4. A 요청 (A가 다시 사용됨) → [B, C, A]
5. D 요청 (캐시 초과 → 가장 오래된 B 제거) → [C, A, D]

📌 특징

• 시간 기반으로 데이터 교체
• 최근 사용된 데이터는 유지됨
• 사용 빈도가 아닌 시간 순서에 따라 캐시 데이터를 유지

---

2. LFU (Least Frequently Used, 가장 적게 사용된 데이터 제거)

LFU는 가장 적게 사용된 데이터를 제거하는 방식입니다.

LFU 동작 방식

1. 데이터를 요청하면 캐시에 저장하고 사용 횟수를 기록
2. 이미 캐시에 있는 데이터를 요청하면 해당 데이터의 사용 횟수 증가
3. 캐시가 가득 찼을 때 가장 적게 사용된 데이터를 제거

LFU 예제

• 캐시 크기: 3
• 요청 순서: [A, B, C, A, D]

1. A 요청 → [A(1)]
2. B 요청 → [A(1), B(1)]
3. C 요청 → [A(1), B(1), C(1)]
4. A 요청 (A 사용 횟수 증가) → [A(2), B(1), C(1)]
5. D 요청 (캐시 초과 → 가장 적게 사용된 B 또는 C 제거, 여기서는 B 제거) → [A(2), C(1), D(1)]

📌 특징

• 사용 빈도가 적은 데이터를 우선적으로 제거
• 사용 횟수를 기반으로 캐시 데이터를 유지
• 단점: 오래된 데이터라도 사용 횟수가 많다면 계속 유지될 수 있음

---

3. LRU vs LFU 비교

비교 항목	LRU (Least Recently Used)	LFU (Least Frequently Used)
기준	최근 사용 여부	사용 횟수
장점	최신 데이터 유지, 단순 구현	자주 사용되는 데이터 유지
단점	자주 사용하는 데이터도 오래 사용 안 하면 제거됨	오랫동안 사용된 데이터가 유지될 가능성 있음
사용 예시	웹 브라우저 캐시, 운영체제 페이지 교체 알고리즘	뉴스 피드 추천 시스템, AI 모델의 데이터 캐싱