캐시는 데이터나 값을 미리 복사해놓는 임시저장소를 의미합니다. 캐시는 접근시간을 최소화하거나, 값을 다시계산하는 시간을 절약하는 경우 사용합니다.
캐시에 데이터를 미리 복사해놓으면 메모리에 접근하거나 하드디스크에 접근하는 것보다 훨씬 빠르게 데이터를 접근할 수 있습니다.
LRU는 Least Recently Used의 약자로 OS의 페이지 교체 알고리즘의 하나로 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘입니다. 캐시에 공간이 부족하면 가장 최근에 사용하지 않은 항목을 제거하죠.
LRU캐시의 구현은 Dobly Linked List를 통해 구현합니다. Head에 가까운 데이터일 수록 최근에 사용한 데이터이며, tail에 가까울 수록 가장 오랫동안 사용하지 않은 데이터로 간주하여, 새로운 데이터를 삽입할 때 가장 먼저 삭제되도록 합니다.
삽입된 데이터를 사용하면 head로 옮겨 우선순위를 높이게 되고 삭제될 우선순위에서 멀어지게 됩니다.