캐시 교체 알고리즘

#자료구조/알고리즘

캐시에 모든 데이터를 올려놓고 쓰면 참 좋겠지만, 항상 그렇듯 자원은 무한하지 않다.
캐시가 가득차면 뭔가 버리긴 버려야 한다.

여기선 캐시를 버리는 캐시 교체 매커니즘에 대해 약간 정리를 해본다.

이 매커니즘들은 진짜 하드웨어 캐시나 단순 인메모리 캐시 시스템에서 사용하기도 하고, OS에서 페이지 교체 알고리즘으로 사용하기도 한다. 범용적인 개념이다.
페이지 교체 알고리즘이라고도 부른다.

LRU(Least Recently Used) 교체

가장 오랫동안 사용되지 않은 데이터를 버리는 전략이다.
가장 직관적이고 단순하면서 대부분의 사용사례에 잘 들어맞기도 한다.

캐시의 본질에 가장 가깝기도 해서 대다수의 인메모리 캐시와 OS에서 사용하고 있다.

사용할때마다 최근 참조 시간을 기록해야해서 약간의 오버헤드가 있다는 단점이 있다.

소프트웨어 인메모리 캐시를 구현할 때는 관례적으로 Double Linked List를 많이 사용한다.

LRU 알고리즘과 비슷하면서도 많이 다르다.
Clock 알고리즘이라고도 부른다.

여기선 Clock 사이클을 기반으로 오래된 데이터를 제거한다. 그래서 사이클을 돌리는 백그라운드 시스템이 존재해야 한다.

위의 과정을 반복한다. 대체로 clock 사이클의 주기는 20밀리초 정도로 둔다.

거의 단일비트만 사용하기 때문에 메모리 사용량이 적고 빠를 수 있다는 장점이 있으나, 사용패턴이 잘 맞지 않을 수도 있다.
clock 사이클을 사용사례에 맞게 잘 조정하는 것도 일이고.

가장 적게 참조된 데이터를 먼저 삭제하는 방법이다.

근데 적게 참조되었다고 그게 다시 사용할 일이 적으리란 것은 아니어서 미묘한 결점이 존재한다.

예를 들어, 실제로는 활발하게 사용되고 있지만 최근에 만들어져서 참조횟수가 비교적 적어 삭제대상이 될 수도 있는 것이다.

큐잉 시스템에서 주로 다루는 그 용어가 맞다.

참조 횟수와는 별개로 그냥 가장 오래된 데이터를 먼저 삭제하는 것이다.

오래되었다고 해서 사용되지 않으리란 보장은 없어서 미묘한 부분은 존재한다.

그럼에도 불구하고 꽤 효율성이 입증되고는 있다.
LRU에 비해 구현도 단순해서이기 때문인 것 같다.

그래서 소프트웨어 인메모리 캐시 분야에서는 벤치마크에 따라 LRU를 압도하기도 한다. 이것도 역시 사용패턴에 따라 크게 달라질 수 있을 것이다.