웹캐싱

• 웹캐싱 : 웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해 빠른 서비스를 가능하게 하는 기법
• 프락시서버 : 통상적으로 일개 그룹의 웹 사용자에 대한 서비스 지연시간을 줄이기 위해 사용 ⇒ 네트워크의 대역폭 절약과 함께 웹서버의 부하를 줄이는 역할
• 역방향 프락시캐시 : 일개 그룹에 속한 웹서버의 객체들을 캐싱하여 서버의 부하를 직접적으로 줄이는 역할 ⇒ 웹 사용자의 지연시간을 줄이는 역할
• 캐시 교체 알고리즘 (cache replacement algorithm) : 한정된 캐시 공간을 가지고 사용자들의 지속적인 요청을 처리하기 위해 어떠한 객체를 캐시에 보관하고 어떠한 객체를 캐시에서 삭제할지 온라인으로 결정
  • 일관성 유지 기법 : 사용자가 요청한 웹 객체가 캐싱되어 있는 경우 이 객체가 근원지 서버에 있는 객체와 동일한지를 확인해 사용자에게 최신의 정보 전달

웹캐시의 교체 알고리즘

• 캐싱 기법의 성능은 캐시 교체 알고리즘에 크게 좌우됨
• 미래의 참조를 미리 알지 못하는 상태에서 한정된 캐시 공간에 보관하고 있을 객체와 삭제할 객체를 동적으로 결정하는 온라인 알고리즘
• 전통적 캐싱 환경과 웹캐싱 환경이 다른점
  • 캐싱 대상이 되는 객체들의 크기와 인출 비용이 균일하지 않음 (ex. 객체를 가지고 있는 근원지 서버의 위치 및 특성에 따라 객체를 캐시로 읽어오는 비용이 다르며, 하나의 URL에 대응하는 파일 단위로 캐싱이 이루어지기 때문에 캐싱 단위의 크기가 균일하지 않음)

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

1. 캐시적중률 : (캐시에서 적중되어 서비스된 요청/사용자의 총 요청) * 100
2. 바이트 적중률 : (캐시에 이미 존재해 근원지 서버에서 받아올 필요가 없는 바이트 수/사용자의 총 요청 바이트 수) * 100
3. 지연 감소율 : (캐시가 있어서 줄어든 지연시간/캐시가 없을 경우의 총 사용자 지연시간) * 100
4. 비용절감률 : 객체들의 참조가능성과 이질성을 함께 고려해서 평가한 객체들의 가치

• 전통적 캐싱 환경 : 참조 가능성이 높은 객체를 보관해 캐시적중률 높이는 것이 목표
• 웹 캐싱 환경 : 객체의 이질성을 고려할 수 있는 비용절감률 높이는 것이 목표

2. 참조 가능성의 예측

• 시간지역성 (temporal locality) : 최근 참조된 객체가 다시 참조될 가능성이 높다
• 인기도 (popularity) : 참조 횟수가 많은 객체일수록 또다시 참조될 가능성이 높다

1. LRU : 최근 참조 성향만 고려 ⇒ 자주 참조되었는지 여부는 알 수 없음
2. LFU : 참조 횟수만 고려 ⇒ 최근에 참조되었는지 여부는 알 수 없음
3. LRU-K : 최근 K번째 참조된 시각에 의거해 가치 평가 ⇒ K번째 참조 시각만 고려하고 최근 K-1번 참조된 시점들은 무시된다는 단점
4. LRFU : 참조 횟수와 시점을 모두 고려, 최근의 참조일수록 기여도 높게 계산

⇒ 3,4는 시간지역성과 인기도 모두 고려한 알고리즘

1. 시간지역성 측면
   • 대부분의 웹캐싱 알고리즘들은 객체의 직전 참조 시각 활용
   • LNC-R 알고리즘은 과거 K번째 참조 시각 이용
2. 참조 인기도 측면
   • 일부 알고리즘은 참조 횟수를 이용하고 일부는 여기에 노화 기법을 추가해 캐시오염 방지
   • 노화 기법 : 오래전에 이루어진 참조에 대해서는 가중치를 줄여나가는 기법
3. 이후의 알고리즘들
   • LRV, MIX, LUV 알고리즘은 두 가지 모두 고려

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

• 웹캐싱 환경에서는 객체의 참조 가능성뿐 아니라 캐시에서 적중될 경우 실제로 절약할 수 있는 비용까지 고려해야 함
• 캐시적중률을 높이기 위해 크기가 작은 객체에 높은 가치를 부여하는 것이 좋음 (한정된 캐시 공간에 많은 객체 보관가능하기 때문)

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

• 캐시 교체 알고리즘을 실제 사용하기 위해서는 시간 복잡도 측면에서 현실성이 있어야 함
• 일반적으로 캐시 내의 n 개의 객체에 대해 시간복잡도가 O(log n)을 넘지 않는 것이 바람직

웹캐시의 일관성 유지 기법

1. 강한 일관성 유지 기법 (strong consistency)
   • 반드시 최신 정보가 사용자에게 전달되는 것을 보장하는 기법
   • ❌ 웹서버와 네트워크의 부담이 커서 일반적으로 잘 사용하지 않음
   • polling-every-time, invalidation
2. 약한 일관성 유지 기법 (weak consistency)
   • 사용자의 요청이 있을 때마다 캐싱된 객체가 변경되었는지 근원지 서버에 일일이 확인하지 않고, 변경되었을 가능성이 높은 경우만 확인하는 기법
   • adaptive TTL

웹캐시의 공유 및 협력 기법

• ICP (Internet Cache Protocol, 인터넷 캐시 프로토콜)
  • 동료 프락시캐시들 사이에서 웹 객체의 검색 및 전송을 지원하기 위한 프로토콜
  • 사용자가 프락시서버에 웹 객체를 요구했는데 없는 경우, 모든 동료 프락시들에게 ICP 질의를 멀티캐스트해서 누가 요청된 웹 객체를 가지고 있는지 확인 > 요청된 객체를 가지고 있다는 답신이 오면, 질의를 보냈던 프락시는 해당 프락시에게 HTTP 요청을 보내 객체를 받아 사용자에게 전달
• CARP (Cache Array Routing Protocol, 캐시 배열 간 경로지정 프로토콜)
  • 공유 웹캐시들에 동일한 웹 객체들이 중복 저장되는 것을 막기 위해 URL 공간을 분할해 각 캐시는 자신에게 배정되는 객체들만 캐싱하게 함

웹캐시의 사전인출 기법

• 사전인출 (prefetching) : 웹 서비스의 응답 지연시간을 줄이기 위해, 아직 요청되지 않은 객체를 미리 받아오는 기법

1. 예측 사전인출 기법 : 웹페이지들 간 관계 그래프를 구성해 하나의 웹페이지가 참조되었을 때 새로운 웹페이지가 참조될 확률을 과거의 참조 기록을 통해 예측 후 이를 기반으로 사전인출
2. 대화식 사전인출 기법 : 사용자가 HTML문서에 대한 요청을 했을 때 캐싱하고 있던 HTML 문서를 미리 파싱해 그 문서에 포함(embed)되거나 연결(link)된 웹 객체를 사전인출

• 유효성 사전확인 (prevalidation) : 캐싱된 객체의 유효성을 미리 확인해두었다가 해당 객체 요청 시 웹서버에 변경여부 확인하지 않고 바로 보내주는 방법

동적 웹 객체의 캐싱 기법

• 위에서 설명한 웹캐싱 기법들은 모두 정적 웹 콘텐츠에 대한 캐싱에 초점
• 동적 웹 콘텐츠에 대한 웹캐싱은 요청받은 내용에 대해 프로그램을 실행한 후 그 결과물을 보내줘야 하기 때문에 데이터 관리에 어려움이 따름 ⇒ 즉, 동일한 요청에 대해 서로 다른 결과를 초래할 수 있기 때문에 캐싱이 의미가 없음
• 하지만 어느 정도 유사하기 때문에 캐싱 가능한 곳을 부분적으로 표시하는 태그 등을 활용해 부분적으로 캐싱하여 활용될 수 있을 것으로 기대