LRU Cache

Apr 28, 2024

Redis와 같은 캐시를 사용하다보면 Eviction 정책을 설정하게 된다.

저장 가능한 메모리 공간에 도달 하였을 때 새 공간을 확보하기 위한 방법을 설정하는 것이다.

LRU (Least Recently Used)는 가장 최근에 사용되지 않은 항목을 제거하는 알고리즘이다.

LRU의 동작 원리

LRU는 저장 가능한 공간이 꽉 찼을 때 새로운 데이터가 저장 될 공간을 마련하기 위해 가장 이전에 참조 된 값을 제거한다.

LRU는 값의 참조 정보를 관리하기 위해 해시맵과 양방향 연결 리스트(Doubly Linked List)를 조합한다.
(본 글에서는 양방향 연결 리스트에 대해 설명하지 않는다. 관련 내용은 이전에 정리했던 글을 참고하자.)

LRU 기본 동작 방식의 이해 - Linked List

그림의 연결리스트는 데이터를 최대 3개까지만 저장할 수 있다. 각 노드에는 A, B, C 값이 저장되어 있고, 첫 노드와 마지막 노드를 참조하기 위한 head와 tail이 존재한다.

LRU는 노드의 이동을 통해 참조와 관련된 정보를 관리하는데, 데이터가 조회 또는 업데이트 될 때마다 해당 노드를 head 쪽으로 이동시킨다. (head와 tail의 역할은 바뀔 수 있다. 예시에서 head를 사용했을 뿐이다.)

최근 참조된 노드를 head 쪽으로 이동시키다보면 tail 쪽에는 자연스레 가장 오래전에 참조된 노드가 남게된다.

그럼 구체적으로 노드 B를 조회하는 상황을 살펴보자.

LRU는 데이터 참조 후 값을 반환하며 가장 최근 참조 된 데이터(B)를 head 로 이동시키고, 이 과정에서 노드 리와이어링이 발생한다. (관련 내용은 양방향 연결리스트(Double Linked List) 를 참고하자.)

그럼 만약 새로운 데이터가 추가되는 경우에는 어떻게 동작할까?

노드 D를 추가하는 과정을 살펴보자.

연결 리스트에 저장할 수 있는 최대 노드 수는 3개로 제한되어 있다. 따라서 데이터를 추가 하려면 기존 노드 하나를 제거 해야한다.

LRU는 가장 오래전에 참조 된 데이터를 제거하는 방식으로 동작한다. 즉, tail에 가장 가까운 노드(C)를 제거한다.
구체적인 과정은 다음과 같다.

가장 오래전에 참조 됐던 노드(C)를 리스트에서 제거한다.
head의 다음 노드 자리에 새로운 노드(D)를 추가한다.

Hash Map으로 성능 개선하기

앞선 과정을 통해 LRU가 동작하기 위한 기본 아이디어를 이해하였다.

연결리스트는 데이터 추가, 조회 연산에 O(n)의 성능을 갖는데, LRU는 이러한 성능 한계를 해시맵을 통해 극복한다.

LRU Cache 내부에서 관리하는 해시 맵은 다음 그림과 같은 구조를 갖는다.

VALUE 에는 값을 직접 저장하는 것이 아닌 노드 참조 값을 저장한다. 이를 통해 조회 요청 시 O(1)의 성능으로 값을 참조할 수 있다.

그럼 오퍼레이션이 수행되는 과정을 보면서 해시 테이블과 결합되었을 때의 전체 동작을 이해해보자.

기존 예제와 동일하게 저장할 수 있는 최대 데이터 수는 3으로 가정하였다.

(1) 데이터 추가 (Key = 1, Value = 'A')

링크드 리스트의 첫번째 노드로 'A'를 저장하고, 해시맵에 Key-Value 쌍을 저장한다. 이 때 VALUE는 노드(A)의 참조 값을 가진다.

(2) 데이터 추가 (Key = 2, Value = 'B')

리스트의 두번째 노드로 'B'를 저장한다. 가장 최근 참조된 노드가 head의 우측에 위치하기 때문에 head의 next, 노드(A)의 prev에 노드(B)의 참조 값을 저장한다. 해시맵의 value에는 노드(B)의 참조 값을 저장한다.

(3) 데이터 추가 (Key = 3, Value = 'C')

head의 next, 노드(B)의 prev에 노드(C)의 참조 값을 저장한다. 마찬가지로 해시맵 Key 3의 value에는 노드(C)의 참조 값을 저장한다.

(4) 데이터 추가 (Key=4, Value = 'D')

capacity가 3이므로 노드(D)를 저장하기 이전에 리스트에서 하나의 노드를 제거 해야한다.
가장 오래전에 참조된 노드는 tail의 prev가 가리키는 노드이다.
노드(A)를 리스트에서 제거하고, 해시맵에서도 제거한다. 이후 노드(D)를 연결리스트와 해시맵에 각각 저장한다.

(5) 데이터 조회 (Key=2)

Key=2의 Value에 저장된 노드(B)를 조회한다. 리스트에서 가장 최근 참조된 값을 업데이트 하기 위해 head로 이동시킨다.

References

LRU의 동작 원리