0. Introduction

 

 

1. 다양한 caching 환경

 

1.1 caching 기법

한정된 빠른 공간(= 캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식

  • 저장장치 계층 간의 속도 차이를 완충시켜주기 위해 컴퓨터 구조, 운영체제, DB 등의 분야에서 각각 다음과 같은 기법 등으로 사용되고 있다.

  • paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용된다.

    • cache memory: CPU와 main memory 사이에 cache memory가 있다. 이 cache memory에 없는 file을 main memory에 요청한다.
    • buffer caching: file system에 대한 read/write 요청을 memory에서 빠르게 서비스하는 방식
    • Web caching: web page를 server에서 가져오는데 동일한 url을 요청할 때를 대비해서 신속히 서비스를 제공하기 위해서, caching 기법으로 제공하는 방법

  • cache 운영의 시간 제약

    • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우, 실제 시스템에서 사용할 수 없다.

    • Buffer caching이나 Web caching의 경우

      • O(1)에서 O(log n) 정도까지 허용

    • Paging system인 경우

      • page fault인 경우에만 OS가 관여한다.
      • 페이지가 이미 메모리에 존재하는 경우, 참조시각 등의 정보를 OS가 알 수 없다.
      • O(1)인 LRU의 list 조작 조차 불가능

 

1.2 웹캐싱이란?

웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해, 빠른 서비스를 제공하여 서비스 지연시간을 줄이고 웹서버 부하도 줄이는 기법

 

2. 웹캐시의 교체 알고리즘(Cache replacement algorithum)

한정된 캐시 공간 안에서 사용자들의 지속적인 요청을 처리하기 위해서, 미래에 참조될 가능성이 높은 객체를 선별한 후, 한정된 캐시 공간 안에 보관할 객체를 온라인으로 결정하는 알고리즘

  • 웹캐시는 객체를 가지고 있는 근원지 서버의 위치 및 특성에 따라 객체를 캐시로 읽어오는 비용이 다르다.

  • 하나의 URL에 대응되는 파일 단위로 캐싱이 이뤄져서 캐싱 단위의 크기가 균일하지 않다.

 

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

캐시 교체 알고리즘의 목표는 참조 가능성이 높은 객체를 캐시에 보관해 ‘캐시적중률(Hit rate)‘을 높이는 것

  • 캐시 적중률

    • 사용자의 총 요청 중 캐시에서 적중되어 서비스된 요청의 비율

  • 하지만, 웹캐싱에서는 객체들의 크기와 인출 비용이 균일하지 않기 때문에 , 객체들의 참조 가능성과 이질성을 함께 고려해야 한다.

  • 이런 경우, 비용절감률(Cost-Savings Ratio: CSR) 로 정형화시킨다.

    • 객체 크기와 인출 비용이 모두 균일하면 비용절감률은 캐시 적중률과 동일한 의미를 가진다.

 

2.2 참조 가능성의 예측

  • 캐시 교체 알고리즘은 전통적인 캐싱 기법인 LRU(Least Recently Used), LFU(Least Frequently Used) 등의 알고리즘처럼 최근 참조 성향과 참조 빈도에 근거해 미래의 참조 성향을 예측하는 방법을 사용한다.

  • 그러면 전통적인 교체 알고리즘들의 구체적인 예를 살펴보고, 웹캐시의 교체 알고리즘은 이들 중 어떤 방법을 채택하는지 알아보자.

 

2.2.1 전통적인 교체 알고리즘

image

  • 과거 참조 기록을 바탕으로 객체 A와 B를 평가한다고 하자.

  • LRU는 최근 참조 성향만을 고려한다.

    • (a) 객체 B가 더 최근(t1)에 참조되었기 때문에, (a) B에 더 높은 가치를 부여한다. 하지만, 이 방법은 자주 참조되는 객체와 그렇지 않은 객체를 구분할 수 없다는 단점이 있다. (b)에서는 A의 가치가 더 높게 평가된다는 사실은 LRU의 문제점을 보여준다.

  • LFU는 참조 횟수만을 고려한다.

    • (a) A의 참조 횟수가 (a) B보다 더 많기 때문에, (a) A에 더 높은 가치를 부여한다. 이 알고리즘의 문제점은 오래 전에 많이 참조된 객체에 높은 가치를 부여해, 새로 참조되기 시작한 객체를 캐시에서 쫓아낼 우려가 있다. 오히려 (c)에서 B의 가치가 더 높게 평가된다는 사실이 LFU의 문제점을 보여준다.

  • 최근 참조 성향과 참조 횟수에 근거해 객체의 참조 가능성을 평가하는 방법은 최근에 참조된 객체가 다시 참조될 가능성이 높다는 점 ( 시간지역성, temporal locality )과, 참조 횟수가 많은 객체일수록 다시 참조될 가능성이 높다는 점 ( 인기도, popularity ), 이 두 가지 사실을 기본으로 가정한다.

  • 위에 두 가지가 컴퓨터 프로그램의 참조 성향을 모델링하는데 널리 사용되는 요소다.

 

2.2.2 웹캐시의 교체 알고리즘

  • 시간지역성 측면 -> 웹 캐시 알고리즘들은 객체의 직전 참조 시각을 활용

  • 참조 인기도 측면 -> 객체 참조 횟수에 노화 기법을 추가하여, 캐시 오염(cache pollution)을 방지한다.

    • 노화 기법: 오래전에 이루어진 참조에 대해 참조 횟수 계산할 때, 가중치를 줄이는 방법

 

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

웹캐싱 같이 캐싱의 단위 객체들의 크기와 인출 비용이 균일하지 않은 환경에서는 이 특성을 고려한 합리적인 가치 평가를 해야 한다.

  • 이 합리적인 평가를 하기 위해서는 객체의 참조 가능성 과 캐시 적중률 로 실제 절약할 수 있는 비용을 동시에 고려해야 한다.

  • 캐시 적중률의 경우, 크기가 작은 객체에 높은 가치를 부여한다. 왜냐하면, 한정된 캐시 공간에 많은 객체를 보관하면 캐시 적중률이 높아지기 때문이다.

 

2.4 알고리즘의 시간 복잡도

캐시 교체 알고리즘이 실제 시스템에 유효하게 사용되기 위해서는 시간 복잡도 측면에서 현실성이 있어야 한다.

  • 시간 복잡도 O(n): cache 내에 있는 객체의 수가 n개라고 할 때, 어떤 객체를 캐시에서 삭제할지 결정하기 위해 n에 비례하는 비교나 연산이 필요하다는 의미

  • proxy cache의 경우, 통상적으로 cache 내에 수백만 개의 객체가 존재하기 때문에 이들을 다 조사하는 시간 복잡도의 방법은 부담이 크기 때문에, 웹 환경에서는 이 알고리즘으로 사용하기 어렵다.

  • LRU

    • 가장 최근에 참조된 시각을 기준으로 객체들의 가치를 일렬로 세워놓고 새롭게 참조된 객체만 가치가 가장 높은 위치로 옮기면 되므로, O(1)의 시간 복잡도 구현이 가능하다.
    • O(1): 캐시 내에 존재하는 객체의 수 n이 커지더라도, 이에 관계없이 캐시에서 이루어지는 비교나 연산이 정해진 적은 횟수로 충분하다는 의미

  • 나머지 알고리즘

    • 힙(heap) 자료구조를 이용해 O(log n)의 시간 복잡도에 각종 캐시 연산을 구현하게 된다. 하지만, 최근 참조 시각을 이용하는 알고리즘에서는 객체의 가치가 시간과 비례하여 다르게 평가되기 때문에, 가치의 대소 관계가 변할 수 있다. 그래서, O(n)의 시간 복잡도가 필요하다.

 

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

cache에 보관된 웹 객체는 근원지 서버에서 변경될 수 있으므로 일관성 유지를 위한 기법으로, 특히 웹캐시의 일관성은 컴퓨터 시스템에서의 캐시와 달리 큰 문제를 야기하지 않으므로, 적응적 TTL(adaptive Time-To-Live) 기법과 같은 약한 일관성 유지 기법을 사용한다.

  • 약한 일관성 유지 기법

    • 사용자의 요청이 있을 때마다 서버에서 일일이 확인하는 게 아닌, 변경될 가능성이 높은 경우에만 확인하는 기법
      • 예) adaptive TTL

  • 강한 일관성 유지 기법

    • 최신 정보가 사용자에게 전달되는 것을 보장하는 기법
      • 예) polling-every-time, invalidation

  • 웹서버와 네트워크의 부담이 커서 득보다 실이 많아 일반적으로 약한 일관성 유지 기법을 사용한다.

 

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

웹캐싱 효과를 극대화 하기 위해 웹캐시 간의 공유 및 협력 기법이 필요하다.

 

4.1 ICP (Internet Cache Protocal, 인터넷 캐시 프로토콜)

동료 proxy cache 사이에서 웹 객체의 검색 및 전송을 지원하기 위한 protocol

  • 사용자가 프락시서버에 웹 객체를 요구했는데, 프락시서버가 그 객체를 캐싱하고 있지 않은 경우, ICP에서 모든 동료 프락시들에게 ICP 질의를 멀티캐스트(multicast)해서 누가 요청된 웹 객체를 가지고 있는지 확인한다.

  • 웹 객체를 가지고 있는 동료 프락시가 답신을 보낸다.

    • 프락시 서버(Proxy server) : 클라이언트와 서버 사이에서 data를 중계하는 역할을 하는 서버

  • ICP 질의를 보냈던 프락시는 답신을 준 프락시에 HTTP 요청을 보내서 해당 객체를 받아온 후 사용자에게 전달한다.

  • HTTP와 ICP의 차이

    • HTTP는 웹 객체의 전송을 위한 프로토콜인 반면, ICP는 공유 웹캐시들 간의 객체 위치를 확인하기 위한 프로토콜
    • HTTP에 비해 매우 부담이 적은 프로토콜

 

4.2 CARP (Cache Array Routing Protocol, 캐시 배열 간 경로지정 프로토콜)

공유 웹캐시들에 동일한 웹 객체들이 중복 저장되는 것을 막기 위해 URL 공간을 분할해, 각각의 캐시는 자신에게 배정되는 객체들만을 캐싱는 기법

 

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

웹 서비스의 응답 지연시간을 줄이기 위해, 사용자에 의해 아직 요청되지 않은 객체를 미리 받아오는 기법으로 2가지로 나눠진다.

 

5.1 예측 사전인출 기법(predictive prefetching)

  • 웹페이지들 간의 관계 그래프 등을 구성해 하나의 웹 페이지가 참조되었을 때, 과거 참조 기록을 통해 새로운 웹페이지가 참조될 된 것을 기반으로 사전인출을 수행하는 방법

 

5.2 대화식 사전인출 기법(interactive prefetching)

  • 사용자가 HTML 문서를 요청했을 때, 웹캐시는 캐싱하고 있던 HTML 문서를 미리 파싱(parsing)한다. 그래서 그 문서에 포함되거나 연결된 웹 객체를 미리 받아와서 사용자의 후속 요청에 곧바로 전달하는 기법

 

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

 

6.1 정적 웹 페이지와 동적 웹 페이지의 차이

  • 정적 웹 페이지

    • 실시간으로 변하지 않고 서버에 저장되어 있는 HTML+CSS file 그대로 보여주는 방식

  • 동적 웹 페이지

    • 상황에 따라 서버에 저장되어 있는 HTML에 데이터 추가/가공하여 보여주는 방법으로, 실시간성 을 요구하는 콘텐츠를 처리하는 웹 페이지를 말한다.

 

6.2 동적 웹 객체의 캐싱 기법

  • 동적 웹 페이지의 콘텐츠는 실시간성이 있어서, 결과물이 이전과 정확히 일치하지 않지만, 상당 부분 유사하다.

  • 그래서 부분적으로 캐싱하여 추후 그 결과를 활용할 수 있다.

 

Reference