컴퓨터 시스템에서 각 장치의 상대적인 속도는 매우 다르다. 예를 들면 DRAM과 같은 메인 메모리에 비해 하드디스크와 같은 저장장치는 데이터 접근 시간이 매우 크다. 또한, 일반적으로 데이터를 네트워크로부터 가져오는 속도 역시 DRAM의 접근 시간보다 크다. 따라서 메인 메모리의 일부 영역을 데이터 캐시 공간으로 사용하고, 한 번 읽어온 데이터를 캐시에 저장하며, 해당 데이터가 다시 접근될 때 캐시에서 가져오면 데이터 접근 시간을 감소시킬 수 있다. 이러한 목적으로 데이터 캐시 기법이 시스템의 많은 부분에서 널리 사용되고 있다.
새로운 데이터를 캐시에 저장하기 위해서는 캐시에 존재하는 기존 데이터를 제거하여 새로운 데이터를 위한 공간을 마련해야 한다. 따라서 어떤 데이터를 제거할 것인지를 결정하는 교체 기법이 존재한다. 전통적으로 사용되는 기법으로 LRU, 2Q, 그리고 ARC 기법들이 있다. 그리고 현재 많은 기법은 이러한 전통적인 기법을 응용하거나 조합하여 만들어진 것들이다. 캐시 교체 기법의 목표는 미래에 사용가능성이 가장 작은 데이터를 골라 제거하여 캐시 히트율을 높이는 것이다. 따라서 캐시 교체 기법의 성능은 주로 히트율을 사용하여 비교한다.
현재 많이 사용되고 있는 캐시 관리 기법은 LRU, 2Q 그리고 ARC 캐시 알고리즘과 같은 고전적인 캐시 관리 기법을 응용하여 사용하고 있다. 이러한 고전적인 캐시 관리 기법은 데이터를 관리하기 위해서 더블 링크 리스트를 사용하는데, 이러한 리스트는 포인터를 이용하여 데이터들을 연결한다. 또한, 데이터가 캐시 내에 존재하는지, 그리고 존재하면 어느 위치에 있는지를 빠르게 찾기 위해 해시 테이블을 사용해서 데이터를 검색한다. 하지만 이러한 리스트와 해시 테이블 방식은 많은 공간을 차지한다. 아울러 해시 테이블을 검색하고 리스트에 데이터를 삽입하고 삭제하는 관리 작업은 전체 데이터 접근 시간을 증가시켜 성능을 떨어뜨리는 요소로 작용한다.
컴퓨팅 환경은 계속 변화하고 있다. 특히 최근의 변화를 살펴보면, 데이터 소스로부터 데이터를 가져오는 데이터 접근 시간의 감소와 컴퓨터 시스템 메모리의 증가를 들 수 있다. 고전적인 데이터 소스 중 하나인 저장장치의 경우 하드디스크를 대신하여 SSD와 같은 플래시 메모리 저장장치가 널리 사용되고 있다. 그 결과 데이터를 가져오는데 소요되는 입출력 시간이 급격히 감소하였다. 또 다른 변화는 메모리의 증가이며, 그 결과 가져온 데이터를 저장하는 캐시의 크기 역시 매우 크다.
디바이스로부터 데이터를 읽는 속도가 빨라지고, 캐시의 크기가 커질수록 캐시 교체 기법의 효율은 그 중요성이 감소한다. 특히 캐시의 크기가 커질수록 캐시 교체 기법 간 히트율 차이는 감소한다. 반면 거대한 캐시에 존재하는 많은 수의 데이터들을 관리하기 위한 관리 오버헤드가 증가한다. 아울러 디바이스로부터 데이터를 읽어오는 시간이 감소할수록 히트율의 증가로 얻을 수 있는 이득은 감소한다. 본 논문은 이러한 컴퓨팅 환경의 변화에 따라 새로운 기준으로 캐시 교체 기법을 비교하고, 또한 거대 규모 캐시를 위한 교체기 법으로 AP(Associative Pocket) 기법을 제안한다. AP 기법은 세트 연관 사상을 응용하여 만들어진 교체 기법이다.
본 논문에서는 LRU, 2Q, ARC, 그리고 AP 기법의 오버헤드를 측정한다. 특히 각 기법이 데이터를 관리하기 위해 감당해야 하는 메모리 오버헤드를 측정한다. 다음으로 각 캐시 교체 기법의 실행시간을 측정한다. 이러한 비교는 캐시 히트율만 비교하는 전통적인 비교 방법과는 다르며, 캐시 교체 기법의 오버헤드와 히트율 간의 트레이드 오프를 보여준다.
비교 결과에 따르면 AP 기법은 거대 규모 캐시에서 히트율도 전통적인 기법과 유사하면서도 오버헤드가 매우 낮음을 보여준다. 구체적으로 AP 기법은 데이터를 연결하기 위해서 포인터가 사용하지 않으며, 데이터를 검색하기 위해 사용되는 해시 테이블 방식을 사용하지 않기 때문에 연산 오버헤드가 작다. 그리고 AP 기법은 리스트나 해시 테이블을 사용하지 않아서, 다른 기법보다 메모리 공간을 더 적게 사용하며, 그 결과 더 많은 데이터를 캐싱할 수 있다. 그리고 이러한 캐싱 가능한 용량의 차이는 캐시의 크기가 커질수록 더 커진다. AP 기법은 대표적인 캐시 교체 기법인 LRU 보다 약 60% 정도 빠른 데이터 접근 시간을 보여주며, 히트율 면에서 캐시 크기가 커질수록 교체 기법 간의 성능은 비슷하다.