웹캐싱 기법

이 글은 반효경 저 - "운영체제와 정보기술의 원리"를 공부하고 정리하여 작성하였습니다.

 

1. 웹캐싱

• 캐싱 기법은 저장장치 계층 간의 속도 차이를 완충시켜주기 위해 다야한 분야에서 캐시 메모리, 페이징 기법, 버퍼링 기법 등을 연구되어 옴.
• 90년대 중반부터는 웹의 보편화와 CDN의 활성화로 원격지의 객체를 캐싱하는 기법의 중요성도 높아짐
• 웹캐싱이란 웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해 빠른 서비스를 가능하게 하는 기법
• 웹 사용자 차원에서의 캐싱뿐만 아니라 웹캐싱만을 전담하는 프락시 서버에 의해 광범위하게 이루어지는 중
• 프락시서버는 그룹의 웹 사용자에 대한 서비스 지연시간을 줄이기 위해 사용, 궁극적으로 네트워크 대역폭 절약과 웹서버 부하를 줄이는 역할도 담당
• 웹서버 쪽에선 역방향 프락시캐시가 사용되는데 그룹에 속한 웹서버의 객체들을 캐싱하여 서버의 부하를 직접적으로 줄이고 웹 사용자의 지연시간을 줄이는 역할을 수행

1.1. 캐시 교체 알고리즘

• 한정된 캐시 공간을 가지고 사용자들의 지속적인 요청을 처리하기 위해 어떠한 객체를 캐시에 보관하고 삭제할 지를 온라인으로 결정함.
• 버퍼캐싱과 페이징 등 전통적인 캐싱시스템에서 LRU 알고리즘 등으로 폭넓게 연구됨

1.2. 일관성 유지 기법

• 캐시에 보관된 웹 객체는 근원지 서버에서 변경될 수 있어 캐싱 시스템은 통상적으로 일관성 유지 기법이 필요함
• 일관성 유지 기법은 사용자가 요청한 웹 객체가 캐싱되어 있는 경우 아 객체가 근원지 서버에 있는 객체와 동일한 지를 확인하기 위함
• 하지만 웹캐시에서는 전통적 컴퓨터 시스템과 달리 일관성 유지 여부가 큰 문제는 아니다.

 

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

• 캐시 교체 알고리즘은 미래의 참조를 알지 못하는 상태에서 캐시 공간에 보관할 객체와 삭제할 객체를 결정하는 알고리즘이다.
• 웹캐싱 환경은 객체의 크기들과 인출 비용이 각자 달라 효율적인 교체 알고리즘 설계가 더욱 어렵다.

2.1. 교체 알고리즘의 성능 척도

• 전통적 캐싱 환경에서의 캐시 교체 알고리즘의 목표는 캐시적중률(Hit Rate)를 높이는 것이면 충분했음.
• 캐시적중률: 사용자의 총 요청 중 캐시에서 적중되어 서비스된 요청의 비율
• 요즘에는 객체의 크기와 인출비용이 다 다르기 때문에 참조 가능성과 이질성을 함께 고려하여 객체들의 가치를 평가해야 함.
  1. 캐시적중률 = $\sum h_i / \sum r_i$
  2. 바이트적중률 = $\sum (s_i \cdot h_i) / \sum (s_i \cdot r_i)$
  3. 지연감소율 = $\sum (d_i \cdot h_i) / \sum (d_i \cdot r_i)$
  4. 비용절감률 = $\sum (s_i \cdot h_i) / \sum (s_i \cdot r_i)$
     • $h_i$ : 객체 i의 캐시 적중 횟수
     • $r_i$ : 객체 i의 총 참조 횟수
     • $s_i$ : 객체 i의 크기
     • $d_i$ : 객체 i의 근원지 서버로부터 인출 지연시간
     • $c_i$ : 객체 i의 인출비용

2.2. 참조 가능성의 예측

• 캐시 교체 알고리즘은 미래 참조 가능성을 잘 예측하냐에 따라 좌우됨
• 일반적으로 LRU, LFU 등의 과거 참조 기록에 의한 방법을 사용한다.
• LFU는 최근 참조된 객체에 대한 평가가 어렵고 LRU는 많이 참조된 객체에 대한 평가가 어렵다는 문제점이 있음
• LRU-K는 최근 K번째 참조된 시각에 의거해 가치를 평가하는 방법이 있음
• LRFU(Least Recently Frequently Used)는 과거 시점에서의 각각의 참조가 현재 객체의 참조 가능성을 예측하는 데 기여하고 최근의 참조일수록 기여도를 더 높게 계산함
• 최근의 참조 기여도를 높이기 위해 보통은 감소함수를 사용함.
• 결국은 시간지역성과 객체의 인기도를 고려하여 교체 알고리즘을 설계하게 된다

시간지역성 관점

• 시간지역성의 관점에서 대부분 객체의 직전 참조 시각을 활용하고 LNC-R 알고리즘만 과거 K번째 참조 시각을 이용함

참조인기도 관점

• 참조인기도 면에서는 일부 알고리즘의 경우 객체의 참조횟수를 이용하고 다른 부류에서는 노화기법을 추가해 캐시오염을 방지함
• 노화 기법: 오래전에 이루어진 참조에 대해서는 참조 횟수를 계산할 때 가중치를 높이는 방법

시간지역성 & 참조인기도 관점

• LRV 알고리즘과 MIX 알고리즘은 직전 참조 시각과 객체 참조 횟수를 동시에 고려해 예측
• 최근은 시간지역성에 기반한 GD-SIZE 알고리즘에 참조 인기도를 결합시키는 방법을 연구
• LUV 알고리즘은 버퍼캐싱에서 연구된 LRFU 알고리즘을 웹캐시 특성에 맞게 일반화했고 과거 모든 참조 기록을 이용

2.3. 객체의 이질성에 대한 고려

• 현대는 참조가능성과 객체의 크기와 인출 비용을 모두 고려해야 함
• 캐시적중률을 높이기 위해선 크기가 작은 객체에 높은 가치를 부여하면 되지만 실제로는 비용절감률을 높이는게 주류
• 첫번째 부류는 웹 객체 참조 가능성에 대한 예측치와 그 객체의 단위 크기당 비용을 곱하여 객체의 전체적인 가치를 평가하는 방법
  • 비용절감률에 대한 기여도 측면에서 정규화된 가치평가가 가능함
  • LNC-R, SW-LFU, SLRU, LRV, LUV 등이 있음
• 두번째 부류는 GD-SIZE 계열의 알고리즘
  • 객체의 크기와 비용을 고려하지만 정규화된 방법으로 고려하진 않음
  • 시간이 흐름에 따라 참조되지 않은 객체의 가치를 감소시키는 노화 메커니즘과 객체의 인출 비용에 관계없이 모든 객체들에 대해 동일한 값을 적용

2.4. 알고리즘의 시간 복잡도

• 시간복잡도 측면에서 현실성이 없다면 쓰일 수 없다. 프락시캐시의 경우 수십만~수백만 객체가 존재하기 때문에 O(N) 이상을 사용해선 안됨.
• 보통은 O(logN)을 넘지 않는 것이 바람직함.
• 새롭게 참조된 객체의 가치에 맞는 위치를 찾아주기 위해서 대부분의 알고리즘들은 힙(heap) 자료구조를 활용하여 O(logN)의 시간복잡도에 각종 캐시 연산을 구현함
• 시간에 따라 객체의 가치가 변하는 경우, 힙을 이용한 구현이 불가능하여 O(N)의 시간복잡도를 필요하게 됨
• 이러한 알고리즘은 근사적인 구현 방법을 사용해 시간 복잡도를 낮춘다.

 

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

• 일반적인 웹캐싱 시스템에서는 적응적 TTL 기법을 사용하여 약한 일관성 유지 기법을 사용
• 약한 일관성 유지 기법이란 변경되었을 가능성이 높은 경우에만 확인하는 기법을 말함
• 강한 일관성 유지 기법
  • Polling-every-time: 캐시 내에 이미 존재하는 객체에 대한 요청이 있을 때마다 근원지 서버에 객체의 변경 여부를 확인하는 방법
  • invalidation: 근원지 서버가 자신의 객체를 캐싱하고 있는 모든 프락시서버를 기록해두었다가 해당 개체가 변경된 경우 해당 프락시서버들에 변경사실을 알려주는 방법
  • 이 둘은 사용자에게 변경되기 이전의 정보를 제공할 가능성이 없는 기법
• 약한 일관성 유지 기법
  • adaptive TTL: 캐시 내에 이미 존재하는 객체에 대한 요청이 있을 때, 해당 객체에 대한 최종 변경 시각과 최종 확인 시각을 고려해 변경되었을 가능성이 높다고 판단되는 경우에만 근원지 서버에 변경 여부를 확인하는 방법. 변경가능성은 LMF에 의해 판단하며 LMF가 임계값 이상인 경우에만 근원지 서버에 변경 여부를 확인
  • LMF = (현재 시각 - 최종확인 시각)/ (최종확인 시각 - 최종변경 시각)

 

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

• 웹캐싱의 효과를 극대화하기 위해 웹캐시 간의 공유 및 협력 기법이 필요함
• 웹캐시 간의 공유는 **인터넷 캐시 프로토콜(ICP)**에 의해 이루어짐
• ICP는 동료 프락시캐시들 사이에서 웹 객체의 검색 및 전송을 지원하는 프로토콜
• 프락시서버에서 사용자가 요구한 웹 객체를 갖고 있지 않은 경우, 모든 주변 프락시에게 ICP 질의를 멀티캐스트하고 이후 답신을 받아 사용자에게 전달
• 웹캐시들 간의 공유를 위한 또 다른 시도로는 캐시 배열 간 경로지정 프로토콜 CARP가 있다.

CARP(Cache Array Routing Protocol)

• 공유 웹캐시들에 동일한 웹 객체들이 중복 저장되는 것을 막기 위해 URL 공간을 분할해, 각각의 캐시는 자신들에게 배정되는 객체들만을 캐싱하게 됨
• 디렉토리 기반 프로토콜에서는 공유 웹캐시에 저장된 객체들의 위치 정보를 디렉토리에 유지함으로써 ICP 프로토콜의 멀티캐스트 부담을 없애고자 함
• 하지만 디렉토리 유지 및 관리에 부담이 생겨 디렉토리 서버 부하를 줄이기 위해 여러 개의 디렉토리 서버를 두기도 함

 

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

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

 

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

• ASP, CGI 등 동적 웹 콘텐츠를 처리하는 부분이 전체 웹서비스 지연시간 중 상당 부분을 차지하고 웹 서버의 과부하를 일으킴
• 요청받은 내용에 대해 프로그램을 실행한 후 그 결과물을 보내주어야 하기 때문에 데이터 관리가 더 어려움
• 현재까지의 동적 웹콘텐츠 캐싱은 주로 웹서버 내부에서 빠른 처리를 위해 웹서버 전위에 설치하는 역방향 프록시캐시 또는 웹서버 가속기 중 일부에서 활용 중
• HTML 등의 규약에 동적 웹콘텐츠 중 캐싱 가능한 곳을 부분적으로 표시하는 태그 등을 활용하여 향후에는 일반적인 웹캐시에서도 이와 같은 기법이 활용

자료

• 운영체제와 정보기술의 원리 (반효경 저, 2020.5)