[OS] 웹캐싱 기법

웹캐싱 기법

1. 웹캐싱 (web caching)

• 웹캐싱이란 웹 사용자에 의해 빈번히 요청되는 데이터를 사용자와 지리적으로 가까운 웹캐시 서버에 보관해 빠른 서비스를 가능하게 하는 기법을 말한다.
• 웹캐싱 기법은 웹서버 또는 웹 사용자 차원에서의 캐싱뿐 아니라 웹캐싱만을 전담하는 ‘프락시 서버’에 의해 광범위하게 이루어 진다.
• 프락시 서버는 통상적으로 일개 그룹의 웹 사용자에 대한 서비스 지연시간을 줄이기 위해 사용되며, 궁극적으로는 네트워크의 대역폭 절약과 함께 웹서버의 부하를 줄이는 역할도 담당하게 된다.

• 웹 서버쪽에서는 ‘역방향 프락시캐시(reverse proxy cache)가 사용되는데, 이는 일개 그룹에 속한 웹서버의 객채들을 캐싱하여 서버의 부하를 직접적으로 줄이는 역할을 하며, 궁극적으로는 웹 사용자의 지연시간을 줄이는 역할을 하게 된다.

• 캐시에 보관된 웹 객체는 근원지 서버에서 변경될 수 있으므로 캐싱 시스템은 통상적으로 일관성 유지(consistency policy) 기법을 필요로 한다.
• 일관성 유지 기법은 사용자가 요청한 웹 객체가 캐싱되어 있는 경우 이 객체가 근원지 서버에 있는 개체와 동일한지를 확인해서 사용자에게 최신의 정보를 전달하기 위해 필요하다.
• 하지만 전통적인 컴퓨터 시스템과 달리 웹캐시에서는 일관성 유지 여부가 큰 문제를 야기하는 경우는 거의 없다.

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

• 캐싱 기법의 송눙운 ‘캐시 교체 알고리즘(cache replacement algorithm)’에 의해 크게 좌우된다.
• 캐시 교체 알고리즘은 한정된 캐시 공간을 가지고 사용자들의 지속적인 요청을 처리하기 위해 어떠한 객체를 캐시에 보관하고 어떠한 객체를 캐시에서 삭제할지 온라인으로 결정한다.

• 전통적인 캐싱 환경에서와 달리 웹캐싱에서는 캐싱 대상이 되는 객체들의 크기와 인출 비용이 균일하지 않기 때문에 효율적인 교체 알고리즘 설계가 어렵다.

• 웹캐싱에서는 객체를 가지고 있는 근원지 서버의 위치 및 특성에 따라 객체를 캐시로 읽어오는 비용이 다르며, 하나의 URL에 대응하는 파일 단위로 캐싱이 이루어지기 때문에 캐싱 단위의 크기가 균일하지 않다.
• 효율적인 캐시 교체 알고리즘은 이와 같은 객체의 이질성을 고려할 수 있어야 한다.

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

• 캐시 적중률(Hit Rate: HR) : 사용자의 총 요청 중 캐시에서 적중되어 서비스된 요청의 비율을 나타낸다.
• 비용 점감률(Cost-Savings Ratio: CSR) : 웹캐싱에서는 객체들의 크기와 인출 비용이 균일하지 않기 때문에 객체들의 참조 가능성과 이질성을 함께 고려해서 객체들의 가치를 평가하는 것이 바람직하다. 이와 같은 관점에서 캐싱의 목표를 정형화시킨 것이다.
• 바이트 적중률(Byte Hit Rate: BHR) : 사용자에 의해 요청된 총 바이트(데이터의 양)중에서 캐시에 이미 존재해 근원지 서버에서 받아올 필요가 없는 바이트 수의 비율을 나타내주는 척도이다.
• 지연 감소율(Delay Savings Ratio: DSR) : 캐시가 없을 경우의 총 사용자 지연시간 중 캐시가 있음으로 인해 줄어드는 지연시간의 비율을 나타낸다.

2) 참조 가능성의 예측

• 캐시 교체 알고리즘은 미래에 참조될 가능성이 높은 객체를 선별해 한정된 캐시 공간에 보관하는 것이므로 그 효율성은 궁극적으로 미래의 참조 가능성을 얼마나 잘 예측하는 가에 좌우된다고 할 수 있다.
• 캐싱된 객체의 최근 참조 성향(recency)과 참조 빈도(frequency)에 근거해 미래의 참조 성향을 예측해서 캐시 내의 객체를 평가한다.

• 캐시 교체 알고리즘에서는 페이지 교체에도 사용되는 LRU와 LFU 알고리즘도 있으며 이에 대한 장단점은 가상 메모리 편에 나온다.

• LRU-K 알고리즘 : 최근 K번째 참조된 시각에 의거해 가치를 평가한다. 하지만 K번째 참조 시각만을 고려하고 최근 K-1번 참조된 시점들은 무시된다는 단점이 있다.
• LRFU 알고리즘
  • 각각의 참조 시점을 그 최근성이 근거해 고려한다.
  • 과거 시점에서의 각각의 참조가 현재 객체의 참조 가능성을 예측하는데 기여하게 되며, 최근의 참조일수록 기여도를 더 높게 계산한다.
  • 객체의 참조가능성 p(i)를 계산할 때 겍체 i에 대한 모든 과거 참조 시점과 참조 횟수를 다 이용한다.
  • 과거 시점에서의 각각의 참조가 객체의 가치를 높이는 데 기여하는 바를 각 시점의 최근성에 근거해 계산하고 이를 더하는 것이다.
• 시간 지역성(temporal locality) : 최근 참조된 객체가 다시 참조될 가능성이 높다는 의미를 갖는다.

• 인기도(popularity) : 참조 횟수가 많은 객체일수록 또다시 참조될 가능성이 높다는 의미를 갖는다.

• 시간 지역성과 인기도는 참조성향(program reference behavior)을 모델링하는데 널리 사용되는 요소이다.

• 시간 지역성의 관점에서 대부분의 웹캐싱 알고리즘들은 객체의 직전 참조 시각을 활용한다.
• 반면, LNC-R 알고리즘은 과거 K번째 참조 시각을 활용한다. 이는 버퍼캐싱 기법인 LRU-K 알고리즘을 이질형 객체를 위한 캐싱 기법에 맞게 활용한 것으로 볼 수 있다.

• 일부 알고리즘의 경우 객체의 참조 횟수를 이용하고, 또 다른 부류의 알고리즘들은 여기에 노화 기법을 추가해 캐시 오염(cache pollution)을 방지한다. 이렇게 오래 전에 참조 횟수가 많았다는 이유로 최근에 전혀 참조가 이루어지지 않는 개체들이 캐시 내에 유지되어 성능 저하를 초래하는 캐시오염 현상을 방지할 수 있다.

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

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

• 웹캐싱에서처럼 캐싱의 단위 객체들이 이질적인 환경에서는 참조 가능성 이외에 객체의 크기와 인출 비용을 고려한 합리적인 가치평가를 해야 한다.
• 객체를 캐시에 보관하고 있을지 여부를 결정하는 가치형가 기준은, 객체의 참조 가능성에 의한 가치와 캐시에서 적중될 경우 실제로 절약할 수 있는 비용을 동시에 고려해야 한다.
• 캐시 적중률을 높이기 위해서 교체 알고리즘은 크기가 작은 객체에 높은 가치를 부여하는 것이 좋다. 이는 한정된 캐시 공간에 많은 객체를 보관해 캐시 적중률을 높일 수 있기 때문이다.
• 하지만 많은 알고리즘들은 캐시 적중률이 아닌 비용 절감률을 높이고자 한다. 이와 같은 알고리즘들은 크게 두 분류로 나누어 볼 수 있다.
  • 첫번째 부류는 웹 객체의 참조 가능성에 대한 예측지와 그 객체의 단위 크기당 비용을 곱해 객체의 전체적인 가치를 평가하는 방법이다. 비용 절감률에 대한 기여도 측면에서 정규화된 가치평가가 가능하다.
  • 두번째 부류는 GD-SIZE 계열의 알고리즘이다. GD-SIZE에서는 시간이 흐름에 따라 참조되지 않은 객체의 가치를 감소시키는 노화 메커니즘을, 객체의 인출 비용에 관계없이 모든 객체들에 대해 동일한 값으로 적용시킨다. 첫 번째 부류 알고리즘에서의 노화 메커니즘이 객체의 비용에 비례하는 감소치를 적용하는 것과 차이가 있다.

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

• 캐시 교체 알고리즘이 실제 시스템에서 유효하게 사용되기 위해서는 시간 복잡도 측면에서 현실성이 있어야 한다. 이는 캐싱 알고리즘이 온라인 알고리즘으로서 빈 공간이 필요할 때마다 즉시 삭제할 객체를 선별해야 해서 시간적인 제약 조건이 따르게 되기 때문이다.

• 프락시 캐시의 경우 통상적으로 캐시 내에 수십만 개에서 수백만 개의 객체가 존재하며, 삭제 대상을 찾기 위해 매번 이들을 다 조사하는 시간 복잡도 O(n)의 방법은 캐싱 시스템에 너무나 부담이 크다.
• LRU 알고리즘의 경우 가장 최근에 참조된 시각을 기준으로 객체들의 가치를 일렬로 세워놓고 새롭게 참조된 객체만 가치가 가장 높은 위치로 옮겨주면 되므로 리스트 자료구조를 통해 O(1)의 시간 복잡도에 구현이 가능하다.
• LRU를 제외한 알고리즘들은 새롭게 참조된 객체라 하더라도 가장 가치가 높아지는 것은 아니므로, 새롭게 참조된 객체의 가치에 맞는 위치를 찾아주는 연산이 필요하다. 이를 위해 힙(heap) 자료구조를 이용하며 O(log n) 의 시간 복잡도에 각종 캐시 연산을 구하게 된다.
• 그러나 최근 참조 시각을 이용하는 알고리즘에서는 객체의 가치가 시간이 지남에 따라 다르게 평가되기 때문에 참조되지 않은 객체들 간에도 가치의 대소관계가 변할 수 있다. 이떄는 힙을 이용한 구현이 불가능하므로 매 순간 객체들의 가치평가를 새롭게 해주기 위해 O(n)의 시간 복잡도가 필요하다.
• GD-SIZE와 LUV 알고리즘은 최근 참조 시각을 이용하는 알고리즘이지만 참조되지 않은 객체들 간의 대소관계가 변하지 않는 좋은 성질을 가지고 있어 힙을 이용해서 효율적인 구현이 가능하다는 장점이 있다.

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

• 캐싱된 웹 객체가 근원지 서버에서 변경될 수 있으므로 웹캐시에는 사용자에게 유효한 정보를 전달하기 위한 일관성 유지 기법이 필요하다.

• 웹캐시에서는 일관성의 불일치가 큰 문제를 야기하지 않는 경우가 대부분이기 때문에 일반적인 웹캐싱 시스템에서는 적응적 TTL(adaptive Time-To-Live) 기법과 같은 ‘약한 일관성 유지’ 기법을 사용한다.

• 약한 일관성 유지 (weak consistency) 기법 : 변경되었을 가능성이 높은 경우에만 확인하는 기법이다.

• 강한 일관성 유지 (strong consistency) 기법 : 사용자의 요청이 있을 때마다 캐싱된 객체가 변경되었느지 근원지 서버에 일일이 확인하는 기법이다. 최신 정보가 사용자에게 전달되는 것을 보장한다.

• 웹캐싱에서는 강한 일관성 유지 기법을 사용하면 웹서버와 네트워크의 부담이 커져서 득보다는 실이 많아서 약한 일관성 기법을 사용한다.

• 웹 캐시의 일관성 유지를 위한 전형적인 기법들

  • polling-every-time : 강한 일관성 유지 기법으로서 캐시 내에 이미 존재하는 객체에 대한 요청이 있을 때마다 근원지 서버에 객체의 변경 여부를 확인하는 방법이다. 변경 여부를 매번 근원지 서버에 확인하는 과정에서 사용자 지연시간 증가와 네트워크 유통량 증가, 웹서버의 과부하 문제 등을 야기한다.

  • invalidation : 강한 일관성 유지 기법으로서 근원지 서버가 자신의 객체를 캐싱하고 있는 모든 프락시 서버를 기록해 두었다가 해당 객체가 변경된 경우 해당 프락시 서버들에게 변경 사실을 알려주는 방법이다. 근원지 서버가 객체를 캐싱하고 있는 모든 프락시 서버를 기억하고 있어야 하는 부담이 있다.

  • adaptive TTL: 약한 일관성 유지 기법으로서 캐시 내에 이미 존재하는 개체에 대한 요청이 있을 때, 해당 객체에 대한 최종 변경 시각과 최종 확인 시각을 고려해서 변경되었을 가능성이 높다고 판단되는 경우에만 근원지 서버에 변경 여부를 확인하는 방법이다. 변경 가능성은 LMF(Last Modified Factor)에 의해 판단하며 LMF가 임계값(threshold) 이상인 경우에만 변경가능성잉 높다고 봐 근원지 서버에 변경 여부를 확인한다.

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

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

• 웹캐시 간의 공유는 일반적으로 ‘인터넷 캐시 프로토콜’에 의해 이루어 진다.

• 인터넷 캐시 프로토콜(Internet Cache Protocol: ICP) : 동료 프락시 캐시들 사이에서 웹 객체의 검색 및 전송을 지원하기 위한 프로토콜이다.

• 사용자가 프락시 서버에 웹 객체를 요구했는데 프락시서버가 그 객체를 캐싱하고 있지 않은 경우 ICP에서는 모든 동료 프락시들에게 ICP 질의를 멀티캐스트(muticast)해서 누가 요청된 웹 객체를 가지고 있는지 확인한다.
  • 만약 동료들 중 하나가 요청된 객체를 가지고 있다는 답신을 보내오면, ICP 질의를 보냈던 프락시는 객체를 가지고 있는 동료 프락시에게 HTTP 요청을 보내어 해당 객체를 받아온 후 사용자에게 전달한다.
  • ICP는 공유 웹캐시들 간에 객체의 위치를 확인하기 위한 프로토콜로서 HTTP에 비해 매우 부담이 적은 프로토콜이다.
• 캐시 배열 간 경로 지정 프로토콜 (Cache Array Routing Protocol : CARP)
  • 공유 웹캐시들에 동일한 웹 객체들이 중복 저장되는 것을 막기 위해 URL 공간을 분할해, 각각의 캐시는 자신에게 배정되는 객체들만을 캐싱하게 한다.
• 디렉토리 기반 프로토콜 (directory based protocol)
  • 공유 웹캐시에 저장된 객체들의 위치 정보를 디렉토리에 유지함으로써 ICP 프로토콜의 멀티캐스트 부담을 없애고자 한다.
  • 하지만 디렉토리의 유지 및 관리에 또 다른 부담이 생기게 된다.
  • 디렉토리는 공유 프락시 자체 또는 별도의 디렉토리 서버에 구현하게 되며, 디렉토리 서버의 부하 부담을 줄이기 위해 여러 개의 디렉토리 서버를 두기도 한다.

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

• 웹 서비스의 응답 지연시간을 줄이기 위한 방법의 일환으로 사용자에 의해 아직 요청되지 않은 객체를 미리 받아오는 사전인출 기법(prefetching)의 중요성이 증가하고 있다.

• 예측 사전 인출 기법 (predictive prefetching) : 웹 페이지들 간의 관계 그래프(dependency graph) 등을 구성해 하나의 웹 페이지가 참조되었을 때 새로운 웹페이지가 참조될 확률을 과거의 참조 기록을 통해 예측하고 이 확률을 기반으로 사전인출을 수행하는 방법이다.

• 대화식 사전 인출 기법(interactive prefetching) : 사용자가 HTML 문서에 대한 요청을 했을 때 웹 캐시는 캐싱하고 있던 HTML 문서를 미리 파싱(parsing)해 그 문서에 포함(embed)되거나 연결(link)된 웹 객체를 미리 받아와서 사용자의 후속 요청에 곧바로 전달하는 방법이다.

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

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

• 실시간성을 요구하는 컨텐츠, 즉 ASP, CGI 등 동적 웹 콘텐츠(dynamic web contents)를 처리하는 부분이 전체 웹 서비스 지연시간 중 상당 부분을 차지하며, 이 부분이 웹서버의 과부하를 일으키는 주요 요인으로 분석되고 있다.

• 웹서버가 동적 웹콘텐츠에 대한 요청을 받을 경우 단순히 저장장치에 있는 파일을 그대로 보내주는 정적 웹콘텐츠의 요청의 처리와 달리, 요청받은 내용에 대해 프로그램을 실행한 후 그 결과물을 내보내주어야 하므로 데이터 관리에 어려움이 따른다.

• 동적 웹 콘텐츠에 대한 요청의 결과물이 정확히 일치하지 않는다 해도 상당히 유사한 부분을 포함하고 있는 것으로 알려져 있다. 이는 동적 웹 콘텐츠의 요청에 대한 결과를 부분적으로 캐싱하여 추후 그 결과를 활용할 수 있다는 것을 의미한다.

• 현재까지의 동적 웹콘텐츠 캐싱은 주로 웹서버 내부에서 빠른 처리를 위해 웹서버 전위(front-end)에 설치하는 역방향 프락시 캐시(reverse proxy cache) 또는 웹서버 가속기(Web server accelerator)중 일부에서 활용되고 있다.

• 하지만 HTML 등의 규약에 동적 웹콘텐츠 중 캐싱 가능한 곳을 부분적으로 표시하는 태그 등을 활용하고 있어, 향후에는 일반적인 웹캐시에서도 이와 같은 기법이 활용될 수 있을 것으로 기대한다.