운영체제와 정보 기술의 원리 10장. 웹캐싱

10장. 웹캐싱 기법

캐싱

저장장치 계층간의 속도 차이를 완충시켜주기 위해 컴퓨터 구조, 운영체제, 데이터베이스 등에서 연구되어 왔다.

1990년 이후 웹의 보편화와 컨텐츠 전송 네트워크(CDN)의 활성화로 원격지의 객체를 캐싱하는 기법의 중요성이 커지고 있다.

-> 네트워크 병목현상, 웹서비스 지연시간 문제 완화를 위해

웹캐싱

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

웹서버, 웹 사용자 차원의 캐싱 뿐만 아니라 웹캐싱만을 전담하는 프락시서버가 있다.

• 통상적인 프락시서버(포워드): 웹 사용자에 대한 서비스 지연시간을 단축하여 궁극적으로 네트워크 대역폭 및 웹서버 부하를 줄임
• 역방향 프락시캐시: 웹서버의 객체들을 캐싱하여 서버 부하 단축하여 궁극적으로 웹 사용자 지연시간 단축

캐시 교체 알고리즘은 한정된 캐시 공간에서 어떠한 객체를 보관하고 삭제할지 온라인에서 결정한다.

• LRU(Least Recently Used) 알고리즘: 버퍼캐싱 페이징 등 전통적인 캐싱시스템
  웹캐시는 기존 캐시 시스템과 달리 적절한 일관성 유지 기법을 필요로 한다.
• 전통적인 시스템: 일관성 유지를 못하면 시스템에 치명적인 문제점 발생
• 웹캐시: 큰 문제점을 야기하지않는 경우가 대부분

웹캐시의 교체 알고리즘

캐싱 기법은 캐시 교체 알고리즘에 의해 크게 좌우된다.

웹캐싱에서는 캐싱 대상이 되는 객체들의 크기와 인출 비용이 균일하지 않다. (페이징 기법에서는 동일한 크기의 페이지를 캐싱의 대상으로 함)

• 객체를 가지고 있는 근원지 서버의 위치와 특성에 따라 비용 상이
• 하나의 url에 대응하는 파일 단위로 캐싱이 이루어져서 크기 균일X

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

• 전통적 캐싱 환경(크기, 비용 균일): 캐시적중률(Hit-Rate: HR) 높이는 방향
• 웹캐싱: 비용(c_i)은 캐싱목표에 따라 다양하게 정의할 수 있다.
  • 캐시적중률(HR): c_i가 객체의 적중률일 때
  • 바이트적중률(BHR): c_i가 객체의 크기일 때
  • 지연감소율(DSR): c_i가 객체의 인출 지연시간 일 때
  • 비용절감률(CSR): 객체들의 참조 가능성과 이질성을 함께 고려해서 평가한 객체들의 가치2) 참조 가능성의 예측미래의 참조를 알지 못하는 상태에서 가능성이 높은 객체를 선별한다.
• LRU(Least Recently Used): 가장 최근에 사용된 객체를 예측(참조 성향)
• LFU(Least Frequently Used): 가장 빈번히 사용된 객체를 예측(참조 횟수)
• LRU-K: 가장 최근에 사용된 객체 중 K번째 까지 고려

• LRFU: 각각의 참조 시점을 최근성에 근거해 고려

시간지역성(temporal locality): 최근 참조된 객체가 다시 참조될 가능성이 높다.

• 대부분 직전 참조 시각 활용
• LRU-K 알고리즘의 경유 과거 K번째 참조시각 이용:
  • 이질형 객체를 위한 캐싱 기법, 버퍼 캐싱 기법

인기도(popularity): 참조 횟수가 많은 객체일수록 참조될 가능성이 높다.

• 참조 횟수 이용
• 노화 기법을 추가해 캐시오염 방지

시간지역성, 인기도 모두 참조

• LRV, MIX 알고리즘
• LNC-R 알고리즘
• GD-SIZE 알고리즘
• LUV 알고리즘: 버퍼캐싱에서 연구된 LRFU 알고리즘을 웹캐시 특성에 맞게 일반화

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

웹캐싱은 참조가능성 이외에 객체의 크기와 인출 비용을 고려하여 합리적인 가치평가를 해야한다.

• 캐시적중률을 높이기 위한 방법: 크기가 작은 객체에 높은 가치 부여
  • SIZE, LRU-MIN 알고리즘
• 비용절감률을 높이는 방법: 대다수의 알고리즘
  • 웹 객체의 참조 가능성 예측치 X 객체의 단위 크기당 비용(LNC-R, SW-LFU, SLRU, LRV, LUV)
    • 비용절감률에 대한 기여도 측면에서 정규화된 가치평가
  • GD-SIZE 계열
    • 참조 가능성과 이질성을 정규화된 방법으로 고려하지 않음

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

캐시 내에 있는 객체의 수가 n 이라 할때, O(n)의 시간복잡도는 부담이 된다. O(logn)을 넘지 않도록 하는 것이 바람직하다.

• LRU: O(1)
• 나머지 대부분의 알고리즘: 힙 자료구조를 이용해 O(logn)
• 최근 참조 시각을 이용하는 알고리즘: O(n) -> 근사적인 구현 방법으로 복잡도 낮춤

웹캐시의 일관성 유지 기법

웹캐싱 시스템에선 적응적 TTL 기법과 같은 약한 일관성 유지 기법 사용

• 약한 일관성 유지: 요청이 있을 시 변경 사항을 모두 확인X, 가능성 높은 것만 확인
  • adaptive TTL: 캐시 내에 존재하는 객체에 대한 요청시 최종 변경 시각, 최종 확인시각을 고려해 변경 가능성이 높을 때만 확인(대부분 이 방식 사용)
  • LMF = (C-V)/(V-M)
  • M: 최종 변경시각, V: 최종 확인 시각, C: 현재시각
• 강한 일관성 유지: 반드시 최신정보가 전달되도록 보장, 웹서버와 네트워크에 부담이 큼
  • polling-every-time: 캐시 내 존재하는 객체에 대한 요청시 근원지 서버 객체 변경 여부 확인
  • invalidation: 근원지 서버가 자신의 객체를 캐싱하고 있는 모든 프락시 서버 기록, 해당 객체 변경시 프락시서버에 변경 사실 전달

웹캐시의 공유 및 협력 기법

웹캐싱의 효과를 극대화하기 위한 방법이며 주로 인터넷 캐시 프로토콜을 통해 이루어짐(ICP)

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

• 사용자가 프락시서버에 웹 객체를 요청했으나 캐싱되어 있지 않은 경우 동료 프락시에게 ICP 질의를 멀티캐스트
• 객체를 가지고 있는 동료 프락시에게 HTTP 요청으로 객체를 받아옴
• 웹 객체 전송을 위한 프로토콜인 HTTP 보다 부담이 매우 적다.
  캐시 배열간 경로지정 프로토콜(CARP): 공유 웹캐시간 중복 저장 방지를 위해 URL 공간 분할

디렉토리 기반 프로토콜: 공유 웹캐시에 저장된 객체의 위치정보를 디렉토리에 유지

• ICP 프로토콜의 멀티캐스트 부담을 없앰
• 디렉토리 유지 및 관리 부담이 생김
• 디렉토리는 공유 프락시 자체 or 별도의 디렉토리 서버에 구현
• 디렉토리 서버 부담을 줄이기 위해 여러개의 디렉토리 서버를 두기도 함

웹캐시의 사전인출 기법

웹서비스 응답 지연시간을 줄이기 위한 방법

• 사전인출 기법: 요청되지 않은 객체를 미리 받아오는 기법
• 예측 사전인출 기법: 웹페이지들 간 관계 그래프를 구성하고 확률 기반 예측
• 대화식 사전인출 기법: HTML 문서 요청 시 캐싱하던 HTML문서를 파싱해 그 문서에 포함시키거나 연결된 링크를 받아옴
• 유효성의 사전확인 기법: 캐싱된 객체의 유효성을 미리 확인 후 변경 여부 확인 없이 보내줌

동적 웹 객체의 캐싱 기법

위에서 다른 웹 캐싱 기법들은 HTML, JPG, GIF 등의 정적 웹 콘첸츠에 대한 캐싱이었다. ASP, CGI 등 동적 웹 콘첸츠는 웹 서비스 지연시간의 주요 원인 중 하나이다.

요청 받은 내용에 대해 프로그램을 실행 후 결과물을 보내주어야 하기 때문에 어려움 발생

HTML 등 규약에 동적 웹콘첸츠 중 캐싱 가능한 곳을 표시하는 태그 등을 활용하는 방안을 연구 중이다..

 

출처 : 운영체제와 정보기술의 원리 - 이화여자대학교출판문화원 출판, 반효경 저