웹 캐싱 기법

웹 캐싱 기법

웹캐싱

캐싱 기법은 저장장치 계층 간의 속도 차이를 완충시켜주기 위해 컴퓨터 구조, 운영체제, 데이터베이스 등의 분야에서 각각 캐시 메모리, 페이징 기법, 버퍼링 기법 등으로 널리 연구되어왔다.

웹캐싱이란 웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해 빠른 서비스를 가능하게 하는 기법을 말한다. 웹캐싱 기법은 웹서버 또는 웹 사용자 차원에서의 캐싱뿐 아니라 웹캐싱만을 전담하는 프록시서버에 의해 광범위하게 이루어지고 있다. 프록시서버는 통상적으로 일개 그룹의 웹 사용자에 대한 서비스 지연시간을 줄이기 위해 사용되며, 궁극적으로는 네트워크의 대역폭 절약과 함께 웹서버의 부하를 줄이는 역할도 담당하게 된다. 이와 반대로 웹서버 쪽에는 역방향 프록시캐시가 사용되는데, 이는 일개 그룹에 속한 웹서버의 객체들을 캐싱하여 서버의 부하를 직접적으로 줄이는 역할을 하며, 궁극적으로 웹 사용자의 지연시간을 줄이는 역할을 하게 된다.

캐싱 시스템에서 캐시 교체 알고리즘은 중요하다. 어떤 캐시를 삭제하고 또는 보관할건지 결정하는데 전통적으로 LRU 알고리즘 등이 연구되어왓다. 캐시에 보관된 웹 객체는 근원지 서버에서 변경될 수 있으므로 캐싱 시스템은 통상적으로 일관성 유지기법을 필요로 한다. 이 기법은 사용자가 요청한 웹 객체가 캐싱되어 있는 경우 이 객체가 근원지 서버에 있는 객체와 동일한지를 확인해서 사용자에게 최신의 정보를 전달하기 위해 필요하다. 전통적인 컴퓨터 시스템이 캐시 일관성을 유지하지 못하면 시스템 전체에 치명적인 문제를 야기할 수 있지만, 웹캐시에서는 일관성유지 여부가 큰 문제점을 야기하지 않는 경우가 대부분이다.

---

웹캐시의 교체 알고리즘

캐시 교체 알고리즘은 미래의 참조를 미리 알지 못하는 상태에서 한정된 캐시 공간에 보관하고 있을 객체와 삭제할 객체를 동적으로 결정하는 온라인 알고리즘이다. 전통적인 캐싱 환경에서와 달리 웹캐싱에서는 캐싱 대상이 되는 객체들의 크기와 인출 비용이 균일하지 않기 때문에 효율적인 교체 알고리즘의 설계에 어려움이 따른다. 따라서 효율적인 캐시 교체 알고리즘은 이와 같은 객체의 이질성을 고려할 수 있어야 한다.

교체 알고리즘의 성능 척도

객체의 크기와 인출 비용이 균일한 전통적인 캐싱 환경에서는 사용자가 요청한 객체가 캐시에 존재하는 경우 그 효용이 모두 동일하므로 캐시 교체 알고리즘의 목표는 참조 가능성이 높은 객체를 캐시에 보관해 캐시적중률을 높이는 것으로 충분했다. 그러나 웹캐싱에서는 크기와 인출비용이 균일하지 않기 때문에 객체들의 가치를 평가하는 것이 바람직하다.

참조 가능성의 예측

캐시 교체 알고리즘은 미래의참조 가능성을 얼마나 잘 예측하는가에 효율성이 좌우된다. LRU,LFU가 전통적인 캐싱 기법에서 널리 연구되어온 방법이다. 하지만 이 방법들은 장단점이 있다. LRFU(Least Recently Frequency Used)는 이러한 방법의 문제점을 해결하기 위해 각각의 참조 시점을 그 최근성에 근거해 고려한다. 즉 이 방법은 과거 시점에서의 각각의 참조가 현재 객체의 참조 가능성을 예측하는 데 기여하게 되며, 최근의 참조일수록 기여도를 더 높게 계산한다. 현재 시각에서 이전 참조된 시각들을 뺀 값을 더하는 식이다.

LRU는 최근 참조 성향만을 고려하고, LFU는 참조 횟수만을 고려하며, LRU-K, LRFU는 이 두 가지를 함께 고려한다는 점을 알 수 있다. 최근에 참조된 객체가 다시 참조될 가능성이 높다는 시간지역성과 참조 횟수가 많은 객체일수록 또다시 참조될 가능성이 높다는 객체의 인기도라고 하며 이 두 가지 개념은 컴퓨터 프로그램의 참조 성향을 모델링하는 데 널리 사용되는 요소이다.

웹 캐시의 교체 알고리즘들은 이러한 요소를 다 고려한다. LRV 알고리즘, MIX 알고리즘, LNC-R 알고리즘 등등이 있다.

객체의 이질성에 대한 고려

웹캐싱에서 캐싱의 단위 객체들이 이질적인 환경에서는 참조 가능성 이외에 객체의 크기와 인출 비용을 고려한 합리적인 가치평가를 해야 한다. 가치평가 기준은 객체의 참조 가능성에 의한 가치와 캐시에서 적중될 경우 실제로 절약할수 있는 비용을 동시에 고려해야 한다.

캐시 적중률을 높이기 위해서 교체 알고리즘은 크기가 작은 객체에 높은 가치를 부여하는 것이 좋다. 이는 한정된 캐시 공간에 많은 객체를 보관해 캐시적중률을 높일 수 있기 때문이다. SIZE와 LRU-MIN이 이와 같은 알고리즘이다. 하지만 많은 알고리즘들은 캐시적중률이 아닌 비용절감률을 높이고자 한다.

그 첫 번째 부류는 웹 객체의 참조 가능성에 대한 예측치와 그 객체의 단위 크기당 비용을 통해 객체의 전체적인 가치를 평가하는 방법이다. 이와 같은 방법은 비용절감률에 대한 기여도 측면에서 정규화된 가치평가가 가능하다는 단점이 있다. LNC-R, SLRU,등이 있다.

두 번째 부류는 GD-SIZE 계열의 알고리즘이다. 이 알고리즘 역시 객체의 크기와 비용을 고려하지만 첫 번째 부류의 알고리즘과 달리 객체의 참조 가능성과 이질성을 정규화된 방법으로 고려하지 않는다. 여기서는 시간이 흐름에 따라 참조되지 않은 객체의 가치를 감소시키는 노화 메커니즘을, 객체의 인출 비용에 관계없이 모든 객체들에 대해 동일한 값으로 적용시킨다.

알고리즘의 시간 복잡도

시간복잡도가 O(log n)을 넘지 않는 것이 바람직하다. LRU는 O(1)이면 된다. LRU를 제외한 나머지 알고리즘들은 새롭게 참조된 객체라 하더라도 가장 가치가 높아지는 것은 아니므로, 새롭게 참조된 객체의 가치에 맞는 위치를 찾아주는 연산이 필요하다. 이 연산을 위해 대부분의 알고리즘들은 힙 자료구조를 이용해 O(log n)을 구현하게 된다. 그러나 최근 참조 시각을 이용하는 알고리즘에서는 시간이 지남에 따라 객체의 가치가 다르게 평가되기 때문에 참조되지 않은 객체들 간에도 가치의 대소관계가 변할 수 있다. 이 떄에는 힙을 이용해서 구현이 불가능하기 때문에 매 순간 객체들의 가치평가를 새롭게 해주어야 하므로 O(n)의 시간 복잡도가 필요하게 된다. 따라서 이들 알고리즘은 근사적인 구현 방법을 사용해 알고리즘의 시간 복잡도를 낮추게 된다.

---

웹캐시의 일관성 유지 기법

웹캐싱 시스템에서는 적응적 TTL(adaptive Time To-Live) 기법과 같은 약한 일관성 유지기법을 사용한다. 이 기법은 사용자의 요청이 있을 때마다 캐싱된 객체가 변경되었는지 근원지 서버에 일일이 확인하는 것이 아니라, 변경되었을 가능성이 높은 경우에만 확인하는 기법을 말한다. 다음과 같은 전형적인 기법들이 있다.

polling-every-time: 이 기법은 캐시 내에 이미 존재하는 객체에 대한 요청이 있을 때마다 근원지 서버에 객체의 변경 여부를 확인하는 방법이다.

invalidation: 이 기법은 근원지 서버가 자신의 객체를 캐싱하고 있는 모든 프록시서버를 기록해두었다가 해당 객체가 변경된 경우 해당 프록시서버들에 변경 사실을 알려주는 방법이다.

adaptive TTL: 이 기법은 캐시 내에 이미 존재하는 객체에 대한 요청이 있을 때, 해당 객체에 대한 최종 변경 시각과 최종 확인 시각을 고려해서 변경되었을 가능성이 높다고 판단되는 경우에만 근원지 서버에 변경 여부를 확인하는 방법이다. 변경가능성은 LMF(Last Modified Factor)에 의해 판단하며 LMF가 임계값 이상인 경우에만 변경가능성이 높다고 보아 근원지 서버에 변경 여부를 확인한다.

polling-every-time과 invalidation 기법은 강한 일관성 유지 기법이지만, 전자는 매번 확인하면서 사용자 지연시간 증가와 네트워크 유통량 증가, 웹서버의 과부하 문제 등을 야기한다. invalidation 또한 객체를 캐싱하고 있는 모든 프록시서버를 기억하고 있어야 한다. 따라서 대부분 adaptive TTL 방법을 주료 사용한다.

---

웹캐시의 공유 및 협력 기법

웹캐싱의 효과를 극대화하기 위해서는 웹캐시 간의 공유 및 협력 기법이 필요하다. 웹캐시 간의 공유는 일반적으로 인터넷 캐시 프로토콜에 의해 이루어진다(ICP). 사용자가 프록시서버에 웹 객체를 요구했는데 프록시서버가 그 객체를 캐싱하고 있지 않는 경우 ICP에서는 동료 프록시들에게 ICP질의를 멀티캐스트해서 누가 웹 객체를 가지고 있는지 확인한다. 그 후 그 동료 프록시에게 HTTP요청을 보내어 받아와 사용자에게 전달한다. 그리고 캐시 배열 간 경로지정 프로토콜(CARP)이 있다.

---

웹캐시의 사전인출 기법

웹서비스의 응답 지연시간을 줄이기 위한 방법의 일환으로 사용자에 의해 아직 요청되지 않은 객체를 미리 받아오는 사전인출 기법의 중요성이 증가하고 있다. 예측 사전인출 기법과 대화식 사전인출 기법으로 나누어볼 수 있다. 전자는 하나의 웹페이지가 참조되었을 때 새로운 웹페이지가 참조될 확률을 과거 기록을 통해 예측하는 것이고, 후자는 사용자가 HTML문서에 대한 요청을 했을 때 웹캐시는 캐싱하고 있던 HTML 문서를 미리 파싱해 그 문서에 포함되거나 연결된 웹 객체를 미리 받아와서 후속 요청에 곧바로 전달하는 기법이다.

---

동적 웹 객체의 캐싱 기법

지금까지의 웹캐싱 기법은 실시간으로 변하지 않는 데이터 HTML,JPG,GIF 등의 정적 웹 컨텐츠에 대한 캐싱이었다. 그러나 실시간성을 요구하는 컨텐츠인 ASP, CGI등 동적인 웹 컨텐츠를 처리하는 부분이 전체 웹서비스 지연시간 중 상당한 부분을 차지하며 웹 서버의 과부하를 일으키는 주요 요인으로 분석된다. 동적 웹컨텐츠에 대한 웹캐싱은 정적 웹컨텐츠의 캐싱에 비해 데이터 관리에 어려움이 따른다. 그 이유는 요청받은 내용에 대해 프로그램을 실행한 후 그 결과물을 보내주어야 하기 때문이다. 정적 컨텐츠와는 다르게 말이다. 현재까지 동적 웹컨텐츠 캐싱은 주로 웹서버 내부에서 빠른 처리를 위해 웹서버 전위에 설치하는 역방향 프록시 캐시 또는 웹서버 가속기 중 일부에서 활용하고 있는 실정이다.

---