운영체제 시리즈 16. 웹캐싱

Web caching

기하급수적으로 늘어나는 인터넷 정보에 신속하게 접근할 수 있게 하는 주요 기술이다. 

 

웹 캐싱이란 웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해 빠른 서비스를 가능하게 하는 기법이다.

 

컨텐츠 전송 네크워크 (CDN: Contents Delivery Network) 서비스의 활성화로 거리에 따른 캐싱 기법이 필요하게 된 것이다. 웹 캐싱 기법은 웹 캐싱만을 담당하는 프락시서버에 의해 이루어지고 있다. 서비스 지연시간을 줄이고, 네트워크 대역폭 절약, 웹 서버의 부하를 줄이는 역할을 하고 있다. 웹 서버쪽에서는 역방향 프락시 캐시가 사용된다.

 

웹 캐싱에서는 웹 캐시 교체 알고리즘과 데이터의 일관성 유지 기법이 필요하다.

웹 캐시 교체 알고리즘

웹 캐싱은 근원지 서버의 위치에 따라 캐시로 읽어오는 비용이 다르며, 하나의 URL에 대응하는 파일의 크기가 다르므로 캐싱 단위의 크기가 균일하지 않은 특징이 있다. 따라서 효율적인 알고리즘은 비용과 객체의 이질성을 고려해야 한다. 일반적으로 웹 캐시 알고리즘은 힙(heap)자료구조를 사용하여 O(log n)을 넘지 않는 것이 바람직하다.

성능척도

• 캐시 적중률 : 요청 중 캐시에 있어 서비스된 요청의 비율
• 바이트 적중률 : 사용자에 의해 요청된 총 바이트 중에서 캐시에 이미 존재해 근원지 서버에서 받아올 필요가 없는 바이트의 비율
• 지연 감소율 : 캐시가 없을 경우, 총 사용자 지연시간 중 캐시가 있음으로 인해 줄어드는 지연시간의 비율
• 비용 절감률 : 다양한 환경에서 캐싱의 목표에 따라 다르게 정의하며, 목표에 따른 비용 절감률이다.

참조 가능성 예측

참조성향(recency)과 참조빈도(frequency)에 근거하여 미래의 참조 성향을 예측한다. LRU, LFU의 단점을 보완하기 위해 LRFU(Least Recently Frequently Used)가 사용된다. 이것은 과거 시점의 참조가 현재 객체의 참조 가능성을 예측하는데 기여하며, 최근의 참조일수록 기여도를 더 높게 계산한다. 다시말해, 과거의 참조 빈도가 반영되지만, 최근에 이루어진 참조의 기여도를 더 높게 평가하여 예측하는 방법이다. LRU는 최근의 참조 성향을 고려하고, LFU는 참조 횟수만 고려했다면, LRFU는 둘 다 고려하는 방식인 것이다.

 

• 시간 지역성(temporal locality) : 최근에 참조된 객체가 다시 참조될 가능성이 높다.
• 인기도(popularity) : 참조 횟수가 많은 객체일수록 다시 참조될 가능성이 높다.
• 노화 기법 : 과거에 참조된 기록은 참조 횟수를 계산할 때 가중치를 줄여나가는 기법

 

시간지역성과 인기도는 참조 가능성을 모델링하는데 널리 사용되는 개념이다. 노화 기법을 사용하여 캐시오염을 방지하기도 한다. LRU-K, LRV, MIX 알고리즘 등 다양한 알고리즘 모델이 존재한다.   

객체의 이질성 고려

웹에서는 캐싱 단위 객체가 일정하지 않다. 따라서 참조 가능성 이외에 객체의 크기와 인출 비용을 고려한 효율적인 평가가 필요하다. 이 관점에서 2가지 부류로 나눌 수 있다.

 

1. 첫번째 부류 : 전체적인 가치 = 웹 객체의 참조 가능성에 대한 예측치 * 그 객체의 단위 크기당 비용 
2. GD-SIZE 계열 알고리즘 : 객체의 크기와 비용을 고려하지만 노화 기법을 인출비용과 상관없이 모든 객체에게 동일하게 적용시킨다. (첫번째 부류에서는 노화 메커니즘의 감소치가 객체의 비용에 비례한다)

웹 캐시의 일관성 유지기법

전통적인 컴퓨터와 달리 웹에서는 일관성의 불일치가 큰 문제를 야기하진 않는다. 따라서 일반적으로 약한 일관성 유지 기법(weak consistency)인 TTL(adaptive Time-To-Live)을 사용한다.

 

- 강한 일관성 유지기법

• polling-every-time : 객체에 대한 요청이 있을 때마다 근원지 서버에서 일관성 여부를 확인하는 방법
• invalidation : 근원지 서버가 자신이 가지고 있는 객체의 모든 프락시 서버를 기록해두었다가 객체가 변경되면 모든 프락시 서버에게 알려주는 방법

 

- 약한 일관성 유지기법

• adaptive TTL : 요청이 있을 때, 최종 변경 시각과 최종 확인시간을 고려하여 변경 가능성이 높다고 판단되는 경우에만 근원지 서버에서 일관성 여부를 판단하는 방법이다. LMF(Last Modified Factor)에 의해 임계값 이상인 경우에만 변경가능성이 높다고 판단한다.

기타

• 공유 및 협력 기법 : 일반적으로 인터넷 캐시 프로토콜(ICP: Internet Cache Protocol)에 의해 이루어진다. http는 웹 객체 전송을 위한 프로토콜이 반면, ICP는 공유 웹 캐시들 간의 위치확인용 프로토콜이라 부담이 적다. 이외에도 경러지증 프로토콜(CARP), 디렉토리 기반 프로토콜 등이 있다.
• 사전인출 기법 : 예측사전인출기법(predictive prefetching)과 대화식 사전인출기법(interactive prefetching)으로 나뉜다. 예측사전인출기법은 과거의 그래프로 예측한다. 대화식 사전인출기법은 HTML 문서요청을 했을 때, HTML 문서를 미리 파싱하여 포함되거나 연결된 웹 객체를 미리 인축하는 기법이다.
• 동적 웹 캐싱 : 정적 웹 콘텐츠(HTML, jpg, gif 등)보다 실시간성이 필요한 동적 웹 캐싱을 처리하는 부분이 지연시간과 웹 서버 과부하에 많은 영향을 준다. 최근에는 동적 웹 캐싱에 대한 연구가 많이 일어나고 있다. 동적 웹 콘텐츠 중 캐싱 가능한 곳을 부분적으로 태그를 표시하는 등의 방법을 활용하고 있다.  

정리

웹 캐싱은 전통적인 컴퓨터에서 일어나는 캐싱과 다른 특징을 가진다. 물리적 거리에 따른 비용과 캐싱 단위 크기에 따른 비용이 다르기 때문에 여러 요건이 복합적으로 고려되어야 한다. 일관성 문제에서는 약한 일관성 유지기법을 사용한다. 

 

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.