9. 웹캐싱 기법

1. 웹캐싱

• 캐싱 기법은 저장장치 계층 간의 속도 차이를 완충시켜주기 위해 컴퓨터 구조, 운영체제, 데이터베이스 등의 분야에서 각각 캐시 메모리, 페이징 기법, 버퍼링 기법 등으로 널리 연구되어왔다.
• 웹의 보편화와 컨텐츠 전송 네트워크 서비스의 활성화로 원격지의 객체를 캐싱하는 기법의 중요성이 커지고 있다.
• 웹캐싱 : 웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해 빠른 서비스를 가능하게 하는 기법
• 웹캐싱 기법은 웹서버 또는 웹 사용자 차원에서의 캐싱 뿐 아니라 웹캐싱만을 전담하는 프락시서버에 의해 광범위하게 이루어지고 있다.
• 웹서버 쪽에는 역방향 프락시캐시가 사용되는데, 이는 일개 그룹에 속한 웹서버의 객체들을 캐싱하여 서버의 부하를 직접적으로 줄여 웹 사용자의 지연시간을 줄인다.
• 캐시 교체 알고리즘 : 한정된 캐시 공간에 대해 어떤 객체를 캐시에 보관하거나 삭제할지 온라인으로 결정하는 알고리즘
• 캐시에 보관된 웹 객체는 근원지 서버에서 변경될 수 있으므로 일관성 유지 기법을 필요로 한다.
• 일관성 유지 기법 : 사용자가 요청한 웹 객체가 캐싱되어 있는 경우 이 객체가 근원지 서버에 있는 객체와 동일한지 확인하는 기법
• 하지만 웹캐시에서는 일관성 유지 여부가 큰 문제를 야기하지는 않기 때문에 적절한 일관성 유지 기법이 필요하다.

2. 웹캐시의 교체 알고리즘

• 전통적인 캐싱 환경에서와 달리 웹캐싱에서는 캐싱 대상이 되는 객체들의 크기와 인출 비용이 균일하지 않기 때문에 효율적인 교체 알고리즘의 설계에 어려움이 따른다.
• 객체의 크기와 인출 비용이 균일하지 않기 때문에 객체들의 참조 가능성과 이질성을 함께 고려해서 객체들의 가치를 평가한다. 그래서 캐시적중률 대신 비용절감률을 사용한다.
• 캐시적중률은 객체들의 캐시적중 횟수의 합을 객체들의 총 참조 횟수로 나눈 결과이고, 비용절감률은 객체의 캐시적중 횟수에 해당 객체의 인출 비용을 곱해 합한 결과를 이용한다.
• 참조 가능성 차원에서 캐시 내 객체를 평가하는 가장 일반적인 방법은 LRU, LFU가 있다.
• LRU-K 알고리즘 : 최근 K번째 참조된 시각에 의거해 가치를 평가한다. 
• LRFU 알고리즘 : LRU와 LFU를 혼합해 각각의 참조 시점을 그 최근성에 근거해 고려한다.
• 시간지역성(temporal locality) : 최근에 참조된 객체에 다시 참조될 가능성이 높다.
• 객체의 인기도(popularity) : 참조 횟수가 많은 객체일수록 또다시 참조될 가능성이 높다.
• LRU는 시간지역성을, LFU는 객체의 인기도를 통해 미래에 참조될 객체를 결정한다. LRU-K와 LRFU는 이 두 속성을 모두 고려해 결정한다.
• 노화 기법 : 오래전에 이루어진 참조에 대해서는 참조 횟수를 계산할 때 가중치를 줄여나가는 방법
• 노화 기법을 통해 캐시오염을 방지하는 알고리즘도 존재한다.
• 참조 가능성뿐만 아니라 객체의 이질성도 고려해야 하므로, 참조 가능성에 대한 예측치와 단위 크기당 비용을 곱해 객체의 전체적인 가치를 평가한다.
• 알고리즘의 시간 복잡도는 O(log n) 이하가 바람직하다.

3. 웹캐시의 일관성 유지 기법

• 웹캐시에서는 일관성의 불일치가 큰 문제를 야기하지 않는 경우가 대부분이고 일일이 일관성의 불일치를 확인할 경우 네트워크의 부하가 크기 때문에 약한 일관성 유지 기법을 사용한다.
• 약한 일관성 유지(weak consistency) 기법 : 사용자의 요청이 있을 때마다 캐싱된 객체가 변경되었는지 근원지 서버에 일일이 확인하는 것이 아니라 변경되었을 가능성이 높은 경우에만 확인하는 기법 <-> 강한 일관성 유지 기법
• polling-every-time : 캐시 내에 이미 존재하는 객체에 대한 요청이 있을 때마다 근원지 서버에 객체의 변경 여부를 확인하는 방법
• invalidation : 근원지 서버가 자신의 객체를 캐싱하고 있는 모든 프락시서버를 기록해두었다가 해당 객체가 변경된 경우 해당 프락시서버들에 변경 사실을 알려주는 방법
• adaptive TTL(Time-To-Live) : 캐시 내 이미 존재하는 객체에 대한 요청이 있을 때 해당 객체에 대한 최종 변경 시각과 최종 확인 시각을 고려해서 변경되었을 가능성이 높다고 판단되는 경우에만 근원지 서버에 변경 여부를 확인하는 방법
• adaptive TTL에서 변경가능성은 LMF(Last Modified Factor)에 의해 판단하고 LMF가 임계값 이상인 경우에만 변경가능성이 높다고 판단한다.
• LMF = (C-V)/(V-M) (C : 현재 시각, V : 최종 확인 시각, M : 최종 변경 시각)
• 대부분의 상용 프락시서버들은 adaptive TTL 방법을 주로 사용한다.

4. 웹캐시의 공유 및 협력 기법

• 웹캐시 간의 공유는 일반적으로 인터넷 캐시 프로토콜에 의해 이루어진다.
• 인터넷 캐시 프로토콜(Internet Cache Protocol : ICP) : 동료 프락시캐시들 사이에서 웹 객체의 검색 및 전송을 지원하기 위한 프로토콜
• 사용자가 프락시서버에 웹 객체를 요구했는데 프락시서버가 그 객체를 캐싱하고 있지 않은 경우 ICP에서는 모든 동료 프락시들에게 ICP 질의를 멀티캐스트해서 누가 요청된 웹 객체를 가지고 있는지 확인한다.
• 만약 동료들 중 하나가 요청된 객체를 가지고 있다는 답신을 보내오면 ICP 질의를 보냈던 프락시는 객체를 가지고 있는 동료 프락시에게 HTTP 요청을 보내 해당 객체를 받아온 후 사용자에게 전달한다.
• ICP는 공유 웹캐시들 간의 객체 위치를 확인하기 위한 프로토콜로 HTTP에 비해 매우 부담이 적은 프로토콜이다.
• 캐시 배열 간 경로지정 프로토콜(Cache Array Routing Protocol : CARP) : 공유 웹캐시들에 동일한 웹 객체들이 중복 저장되는 것을 막기 위해 URL 공간을 분할해 각각의 캐시는 자신에게 배정되는 객체들만을 캐싱하게 하는 방법
• 디렉토리 기반 프로토콜(directory based protocol) : 공유 웹캐시에 저장된 객체들의 위치 정보를 디렉토리에 유지해 ICP 프로토콜의 멀티캐스트 부담을 없애는 방법

5. 웹캐시의 사전인출 기법

• 사전인출 기법(prefetching) : 사용자에 의해 아직 요청되지 않은 객체를 미리 받아오는 기법
• 웹캐시에서의 사전인출 기법은 예측 사전인출 기법과 대화식 사전인출 기법으로 나누어볼 수 있다.
  • 예측 사전인출 기법(predictive prefetching) : 웹페이지들 간의 관계 그래프 등을 구성해 하나의 웹페이지가 참조되었을 때 새로운 웹페이지가 참조될 확률을 과거의 참조 기록을 통해 예측하고 이 확률을 기반으로 사전인출을 수행하는 방법 
  • 대화식 사전인출 기법(interactive prefetching) : 사용자가 HTML 문서에 대한 요청을 했을 때 웹캐시는 캐싱하고 있던 HTML 문서를 미리 파싱해 그 문서에 포함되거나 연결된 웹 객체를 미리 받아와서 사용자의 후속 요청에 곧바로 전달하는 기법
• 유효성의 사전확인 기법 : 캐싱된 객체의 유효성을 미리 확인해두었다가 사용자가 해당 객체의 요청 시 웹서버에 변경 여부를 확인하지 않고 곧바로 보내주는 방법

6. 동적 웹 객체의 캐싱 기법

• 동적 웹 콘텐츠를 처리하는 부분이 전체 웹서비스 지연시간 중 상당한 부분을 차지하며 이 부분이 웹서버의 과부하를 일으키는 주요 요인으로 분석되고 있다.
• 동일한 URL에 대한 웹 요청인 경우에도 서로 다른 결과를 초래할 수 있기 때문에 캐시에 저장하는 것 자체가 의미가 없다.
• 하지만 동적 웹콘텐츠에 대한 요청의 결과물이 정확히 일치하지는 않는다 해도 상당히 유사한 부분을 포함하고 있는 것으로 알려져 있어, 이를 부분적으로 캐싱해 결과에 활용한다.

 

출처 : 운영체제와 정보기술의 원리