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

10장 웹캐싱 기법

웹캐싱

캐싱: 저장장치 계층 간의 속도 차이를 완충시켜주기 위한 기법

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

• 웹의 보편화

• 컨텐츠 전송 네트워크(CDN)

• proxy

  웹캐싱만을 전담, 웹 사용자에 대한 서비스 지연시간을 줄이기 위해 사용, 네트워크 대역폭 절약과 함께 웹서버 부하 줄임

• Reverse proxy

  웹서버의 객체들을 캐싱해 서버의 부하를 직접적으로 줄여 사용자의 지연시간 줄임

캐시 교체 알고리즘: 한정딘 캐시 공간을 가직 사용자들의 지속적인 요청을 처리하기 위해 어떠한 객체를 캐시에 보관하고 어떠한 객체를 캐시에서 삭제할지 온라인으로 결정

일관성 유지 기법 필요: 객체와 근원지 서버에 있는 객체와 동일한지 확인해서 최신의 정보 전달을 위해 필요

웹캐시의 교체 알고리즘

미래에 어떤걸 참조할지 모르는 상태에서 한정된 캐시 공간에 보관할 객체와 삭제할 객체를 동적으로 결정하는 알고리즘

캐싱 대상이 되는 객체들의 크기와 인출 비용이 균일하지 않아 설계가 어려움

교체 알고리즘의 성능 척도

캐시적중률: 사용자의 총 요청 중 캐시에서 적중된 비율

비용절감률: 객체들의 크기와 인출비용, 참조 가능성, 이질성을 함께 고려해 객체들의 가치 평가한 비율

바이트적중률: 사용자에 의해 요청된 총 바이트 중에서 캐시에 이미 존재해 근원지 서버에서 받아올 필요가 없는 바이트 수의 비율

지연감소율: 캐시가 없을 경우의 총 사용자 지연시간 중 캐시가 있어서 줄어드는 지연시간의 비율

참조 가능성의 예측

캐싱된 객체의 최근 참조 성향과 참조 빈도에 근거해 미래의 참조 성향 예측

• LRU

  가장 최근 참조 기록으로 예측

  자주 참조되는 객체와 그렇지 않은 객체를 구별할 수 없다는 단점

• LFU

  참조 횟수가 가장 적은 객체를 캐시에서 삭제

  오래전에 많이 참조된 객체가 우선이라 최근에 참조되는 것이 쫓겨날 수 있다는 단점

• LRU-K

  K번째 참조된 시각에 의거해 가치를 평가

  K번째 참조 시각만 고려하고 K-1번째 참조된 시점들은 무시된다는 단점

• LRFU

  각각의 참조가 현재 객체의 참조 가능성을 예측하는 데 기여, 최근의 참조일 수록 기여도 높게 계산

컴퓨터 프로그램의 참조 성향을 모델링하는데 시간지역성(최근 참조)과 인기도(참조 횟수)이 사용되는 요소

• LNC-R

  시간지역성: 과거 K번째 참조 시각을 이용

  인기도: 일부는 참조 횟수, 일부는 노화 기법을 추가해 캐시오염 방지

• LRV, MIX

  직전 참조 시각과 객체 참조 횟수를 동시에 고려

• LNC-R

  과거 K번째 참조 시각, 참조 인기도 결합

객체의 이질성에 대한 고려

객체의 참조 가능성에 대한 가치와 캐시에서 적중될 경우 실제로 절약할 수 있는 비용 동시 고려

캐시적중률을 높이기 위해서는 크기가 작은 객체에 높은 가치를 부여하는 것이 좋다. SIZE, LRU-MIN

• 웹 객체의 참조 가능성에 대한 예측치와 그 객체의 단위 크기당 비용을 곱해 객체의 전체적인 가치 평가

  비용절감률에 대한 기여도 측면에서 정규화된 가치평가 가능

• GD-SIZE 계열 알고리즘

  노화 메커니즘을 인출 비용에 관계없이 모든 객체에 대해 동일한 값으로 적용

알고리즘의 시간 복잡도

필요한거 찾을 때마다 모두 조사하는 O(n)은 너무 크다. O(logn)이 넘지 않도록 해야한다.

LRU: O(1)

웹캐시의 일관성 유지 기법

• 약한 일관성 유지

  사용자의 요청이 있을 때마다 캐싱된 객체가 변경되었는지 확인하지 않고 변경됐을 가능성이 높은 경우에만 확인

  • adaptive TTL(적응적 TTL)

    최종 변경 시각과 최종 확인 시각을 고려해 변경됐을 가능성이 높다고 판단되는 경우에만 변경 여부 확인

• 강한 일관성 유지

  반드시 최신 정보가 사용자에게 전달될 것을 보장

  • polling-every-time

    근원지 서버에 변경 여부 확인

  • invalidation

    근원지 서버가 모든 프락시서버 기록해뒀다가 변경된 경우 알려줌

웹캐시의 공유 및 협력 기법

• 웹캐시 간의 공유

  인터넷 캐시 프로토콜(ICP)에 의해 이루어짐

  • ICP

    프락시캐시들 사이에서 웹 객체의 검색 및 전송을 지원하기 위한 프로토콜

  사용자가 프로토콜 요구 -> 프락시서버에 없으면 모든 프락시들에게 ICP 질의를 멀티캐스트해 누가 웹 객체 가지고 있는지 확인 -> 답신 오면 프락시는 동료 프락시에게 HTTP 요청을 보내 객체를 받아와 사용자에 전달

  • CARP

    캐시 배열 간 경로지정 프로토콜로 공유 웹 캐시들에 동일한 웹 객체들이 중복 저장되는 것을 막기 위해 URL 공간 분할해 각각의 캐시는 자신에게 배정되는 객체들만 캐싱하게 함

  • 디렉토리 기반 프로토콜

    공유 웹캐시에 저장된 객체들의 위치 정보를 디렉토리에 유지함으로써 멀티캐스트 부담 저하

웹캐시의 사전인출 기법

웹서비스의 응답 지연시간을 줄이기 위한 방법의 일환으로 사용자에 의해 아직 요청되지 않은 객체를 미리 받아오는 기법

• 예측 사전인출 기법

  웹페이지들 간의 관계 그래프 등을 구성해 하나의 웹 페이지가 참조되었을 때 새로운 웹 페이지가 참조될 확률을 과거를 통해 예측하고 사전인출 수행

• 대화식 사전인출 기법

  사용자가 HTML 문서에 대한 요청 시 캐싱하고 있던 HTML 미리 파싱해 포함되거나 연결된 웹 객체 미리 받아와서 후속 요청에 곧바로 전달하는 기법

동적 웹 객체의 캐싱 기법

동적 웹 객체에 관한 부분이 전체 웹서비스 지연시간 중 상당 부분 차지하고 웹서버 과부하 일으키는 주요 요인

적용될 분야

• 웹서버 전위에 설치하는 리버스 프록시
• 웹서버 가속기