LRU
LRU은 최근 가장 오랫동안 사용되지 않은 캐시 항목을 퇴출하는 정책이다 캐시 교체 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.
| 분류 | 알고리즘 · 캐시 교체 알고리즘 |
|---|---|
| 목적 | 최근 가장 오랫동안 사용되지 않은 캐시 항목을 퇴출하는 정책이다 |
| 처리 방식 | 접근할 때마다 항목의 최근 사용 순서를 갱신하고 캐시 용량이 가득 찼을 때 목록 끝의 가장 오래된 항목을 제거한다 |
| 복잡도·성능 | 해시맵+연결 리스트에서 평균 O(1) 조회·갱신, 공간 O(캐시 용량) |
| 필수 조건 | 최근 접근 정보와 캐시 용량·퇴출 대상 정책이 정의되어야 한다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
LRU은 최근 가장 오랫동안 사용되지 않은 캐시 항목을 퇴출하는 정책이다 캐시 교체 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 접근할 때마다 항목의 최근 사용 순서를 갱신하고 캐시 용량이 가득 찼을 때 목록 끝의 가장 오래된 항목을 제거한다. 해시맵과 이중 연결 리스트를 결합하면 갱신·삭제·조회가 평균 O(1) 가능하다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 해시맵+연결 리스트에서 평균 O(1) 조회·갱신, 공간 O(캐시 용량) 올바르게 적용하려면 최근 접근 정보와 캐시 용량·퇴출 대상 정책이 정의되어야 한다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 운영체제 페이지·데이터베이스·웹 캐시에서 참조한다. 순차 스캔으로 기존 인기 데이터를 밀어내는 오염 문제가 있을 수 있다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]