본 논문에서는 파일이 요청된 순간에는 파일의 선호도만을 조사하고, 일정 시간이 흐른 후에 선호도가 높은 파일들을 일괄적으로 캐싱하는 새로운 캐싱 전략을 소개한다. 이 전략에서는 일정 기간 동안 캐시의 상태가 변하지 않기 때문에 캐시 조작 비용이 거의 들지 않는 매우 효과적인 자료 구조의 사용이 가능하다는 장점을 가지고 있다. 뿐만 아니라, 국내외 5개 웹 서버로부터 수집한 log 파일을 대상으로 실험한 결과에 의하면, LRU를 사용하였을 때보다 오히려 캐시 히트율이 증가하였으며, 캐시 내 자료 재사용율도 증가하는 장점을 보석 주고 있다. 본 논문에서 제안하는 선호도 기반 게으른 캐싱전략(Popularity Based Lazy Caching Strategy)은 캐시에 포함되지 못한 파일의 선호도가 크게 증가하는 경우에 성능이 떨어지는 단점을 가지고는 있다. 그러나 이러한 경우는 자주발생하지 않으며, 웹 서버를 적응적으로 구현하여 해결할 수 있다.
본 논문에서는 파일이 요청된 순간에는 파일의 선호도만을 조사하고, 일정 시간이 흐른 후에 선호도가 높은 파일들을 일괄적으로 캐싱하는 새로운 캐싱 전략을 소개한다. 이 전략에서는 일정 기간 동안 캐시의 상태가 변하지 않기 때문에 캐시 조작 비용이 거의 들지 않는 매우 효과적인 자료 구조의 사용이 가능하다는 장점을 가지고 있다. 뿐만 아니라, 국내외 5개 웹 서버로부터 수집한 log 파일을 대상으로 실험한 결과에 의하면, LRU를 사용하였을 때보다 오히려 캐시 히트율이 증가하였으며, 캐시 내 자료 재사용율도 증가하는 장점을 보석 주고 있다. 본 논문에서 제안하는 선호도 기반 게으른 캐싱전략(Popularity Based Lazy Caching Strategy)은 캐시에 포함되지 못한 파일의 선호도가 크게 증가하는 경우에 성능이 떨어지는 단점을 가지고는 있다. 그러나 이러한 경우는 자주발생하지 않으며, 웹 서버를 적응적으로 구현하여 해결할 수 있다.
In this paper, we propose a new caching strategy for web servers. The proposed algorithm collects on]y the statistics of the requested file, for example the popularity, when a request arrives. And, at times, only files with higher popularity are cached all together. Because the cache remains unchang...
In this paper, we propose a new caching strategy for web servers. The proposed algorithm collects on]y the statistics of the requested file, for example the popularity, when a request arrives. And, at times, only files with higher popularity are cached all together. Because the cache remains unchanged until the cache is made newly, web server can use very efficient data structure for cache to determine whether a file is in the cache or not. This increases greatly tile efficiency of cache manipulation. Furthermore, the experiment that is performed with real log files built by web servers shows that the cache hit ratio and the cache hit ratio are better than those produced by LRU. The proposed algorithm has a drawback such that the cache hit ratio may decrease when the popularity of files that is not in the cache explodes instantaneously. But in our opinion, such explosion happens infrequently, and it is easy to implement the web servers to adapt them to such unusual cases.
In this paper, we propose a new caching strategy for web servers. The proposed algorithm collects on]y the statistics of the requested file, for example the popularity, when a request arrives. And, at times, only files with higher popularity are cached all together. Because the cache remains unchanged until the cache is made newly, web server can use very efficient data structure for cache to determine whether a file is in the cache or not. This increases greatly tile efficiency of cache manipulation. Furthermore, the experiment that is performed with real log files built by web servers shows that the cache hit ratio and the cache hit ratio are better than those produced by LRU. The proposed algorithm has a drawback such that the cache hit ratio may decrease when the popularity of files that is not in the cache explodes instantaneously. But in our opinion, such explosion happens infrequently, and it is easy to implement the web servers to adapt them to such unusual cases.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
즉, 파일이 요청된 순간어】, 이 파일을 캐싱하는 것이 유리한지 혹은 캐싱하지 않고 캐시를 현상태 그대로 유지한 상태에서 서비스를 하는 것이 유리한지를 판단한다는 점이다. 본 연구에서는 이러한 전통적 캐싱 기법들을 캐시에 파일들이 서비스되는 시점에 캐시에 들어가야 하는 지를 판단하고 이에 따른 행동을 취한다는 관점에서 서비스 시점 캐싱전략, 즉 CST (caching at the service time) 이라 분류하고자 한다. CST 캐싱 전략들의 단점은 캐시 조작의 성능을 높이기 위하여 효과적인 자료구조를 사용하고 있더라도 매 요청마다 캐시를 조작하기 위하여 상당한 자원을 낭비하고 있으며, 자료가 동적으로 삽입과 삭제가 자유로워야 한다는 점 때문에 검색 시간을 줄일 수 있는 매우 효과적인 자료 구조, 예를 들면, 이진 자료검색 등을 사용하지 못하고 있다.
이에, 본 연구에서는 파일이 요구된 시점에서는 캐시에 관련된 판단을 하는 것이 아니라 파일들의 선호도 등 기본적인 캐싱 여부 판단에 유효한 정보만을 축적한 후, 일정기간 동안 조사된 이들 자료를 근거로 하여 파일들을 일괄적으로 캐싱하는 전략을 소개한다. 본 논문에서는 캐싱 여부를 판단하는 기준으로 선호도만을 고려하였다.
웹 서버에서의 캐싱은 웹 서버가 디스크에 있는 파일을 메모리에 캐싱하여 웹 서버가 클라이언트의 요청에 응답하는 요청 처리 시간을 줄이는데 목적이 있다.
파일의 선호도를 사용하여 요청되는 파일들이 어느 정도로 다시 요청되는가를 나타내어 보자. 1'-1 시점부터, , 시점 사이에 기록된 파일 /의 요청 건수를 /丿라표현하고, 1시점부터 i시점까지 처리한 총 요청 건수를 A(分라 표현하자.
이에 본 논문에서는 이러한 현상, 즉 과거의 일정 기간 동안 축적된 자료들로부터, 이들이 가까운 미래에도 많이 요청되면서 서버의 성능 향상에 기여가 예상되는 파 말들을 추출하고 이들을 일괄적으로 캐싱하는 전략을 제안하고자 한다.
본 절에서는 우선 캐싱 알고리즘의 목적을 해석적으로 살펴보고 이에 따라 선호도 기반 캐싱 알고리즘을 제시하고자 한다. 캐싱 알고리즘의 해석적 접근은 어떠한 캐싱 알고리즘을 적용하는 것이 유리한지를 판단할 논리적 기준을 제시하게 될 것이다.
효과적인 캐싱 알고리즘이라면 R(i, f, A)와 p(i, f)의 곱이 최대가 되도록 하여야 한다. 본 논문에서는 선호도가 일정기간 크게 변하지 않는다면 p(i, f) 값만을 고려함으로써 캐시를 일괄적으로 변경하는 PLC 알고리즘을 제시하려 한다.
본 연구에서는 지금까지 웹 서버에서의 캐싱 연구에서와는 달리 웹 서버가 서비스하는 파일들은 매우 독특한 특성을 가지고 있음을 주시하고, 이를 근거로 요청된 각각의 파일을 사용자에게 전송하면서 이를 캐싱할 것인가를 결정하는 기존의 LRU와는 달리 일정기간 동안 단순히 서비스되는 파일들에 대한 통계만을 축적한 후, 이를 근거로 일괄적으로 캐싱하는 것을 가능하게 하는 새로운 캐싱전략인 PLC를 제안하였다. 유명 웹 사이트의 log 파일을 대상으로 실험한 결과, 히트율 측면에서 PLC 전략은 매 파일을 전송할 때에 이를 캐싱하지 않으면서도 기존의 LRU전략보다 높은 효과를 주며, 캐싱으로 인한 웹 서버의 부하를 줄이는 효과를 주고 있음을 확인하였다.
가설 설정
그러나 기존의 디스크 캐시들은 웹 트래픽에 최적화 되어 있지는 않다[1 이. 첫째, 캐싱의 단위가 다르다. 전통적인 파일 시스템의 캐싱 전략은 각각의 디스크 블록에 적용되지만 웹 서버는 전체 파일 단위로 필요로 하기 때문에 파일 단위의 전략이 필요하다.
이다. 문제의 편의를 위하여 캐시의 크기보다 큰 파일은 검토대상에서 제외하여도 좋으므로 如Ml이라고 가정한다. 변수 君의 값은 파일이 캐싱이 되는가 아닌가에 따라 1 혹은 0의 값을 가지게 되므로 pure binary integer programming 에 속한다.
제안 방법
본 논문에서는 캐싱 여부를 판단하는 기준으로 선호도만을 고려하였다. 제안하는 이 전략은, 어찌보면 게으르게, 일정 시간이 흐른 후에야 비로소 캐싱할 파일들을 결정한 후, 일괄적으로 캐싱하고, 그리고 새로운 결정이 내려질 때까지는 캐시를 변경하지 않으므로 선호도 기반 게으른 캐싱 전략(PLC:Popularity based Lazy Caching) 이라부르고자 한다. PLC를 사용하는 경우에, 캐시는 새로운 파일로 채워질 때까지 변하지 않는 read-only 캐시로 변하게 되어, 기존의 웹 서버에서 사용하는 선형 연결 구조보다 훨씬 검색이 빠른 자료구圣의 사용이 가능해진다.
PLC의 성능을 평가하기 위하여 국내외 웹 서버가 생성한 log 파일을 대상으로 성능 평가 실험을 수행하였다. 비교 평가 캐시 교체 전략으로는 가장 대표적인 LRU(Least Recently Used)를 선택하였다.
비교 평가 캐시 교체 전략으로는 가장 대표적인 LRU(Least Recently Used)를 선택하였다. PLC는 캐시의 적중률이나 캐시내 자료 재사용율도 LRU를 사용하였을 때보다 증가하는 결과를 보여주고 있다.
Y축은 S(다른날 H(07/22, a力를 의미한다. 에듀넷 웹서버의 경우, 실험은 첫째 날에서 선호도 순으로 상위 100개 파일의 선호도부터, 100개씩 증가하면서 상위 2000개 파일까지의 선호도가 다른 날에 가지는 선호도를 조사하였다. 이럴 게 조사된 180개의 S(07/22, H(07/22, x刀와 S(다른날 H(07/22, 知丿의 쌍을 산점도로 그린 그래프가 [그림 3] 이다.
비교 평가하기 위하여 파일의 선호도(奇) 만을 고려하는 PLG를 PLC-P 로 부르고 효율冷 W尸成耳)을 고려하는 PLC를 PLC-E 로 부르기로 한다. 실험은 각각의 서버별로, 전통적인 LRU를 사용한 캐시와 3장에서 제안한 PLC-P, PLC-E 를 사용한 캐시에 대하여 캐시의 크기를 변화시키면서 캐시의 히트율을 비교하여 각 캐시의 성능을 평가한다.
보여주고 있다. 각 서버에서 서비스된 CGI가 아닌 파일들 중에서 선호도가 높은 상위 1000개의 파일을 선택하여 파일의 크기를 추출하였다、추출된 데이터를 선호도가 높은 파일부터 왼쪽으로부터 나열한 후 구간을 30 으로 하는 이동평균을 구하여 그린 그래프가 [그림 6] 이다. HP05는 대단히 큰 파일을 서비스하고 있다.
첫번째 실험은'서버에 대하여 캐시의 크기(CS)를 변화시키면서 수행되었다. Threshold는 적용하지 않았다.
대상 데이터
본 논문에서는 제안한 선호도 기반 캐싱 전략의 성능을 평가하기 위해 KE:RIS에서 운영중인 국내의 대표적인 교육 정보 포털 사이트인 에듀넷 (www.edunet4u.net) 에서 운영중인 3개 웹 서버의 로그 파일과 1995년에 사용된 NASA와 CLARKNET의 웹 서버의 로그 파일을 사용하였다. 분석에 사용된 에듀넷의 각 서버를 편의상 각각 HP01, HP05, EDU01 로 부른다.
net) 에서 운영중인 3개 웹 서버의 로그 파일과 1995년에 사용된 NASA와 CLARKNET의 웹 서버의 로그 파일을 사용하였다. 분석에 사용된 에듀넷의 각 서버를 편의상 각각 HP01, HP05, EDU01 로 부른다. NASA 는 미국 플로리다에 위치한 NASA 의 웹 서버의 로그이고 CLARKNETe 워싱턴 DC와 볼티모어 지역의 인터넷 제공자인 Clarknet사의 웹서버의 로그 파일이다.
Threshold는 적용하지 않았다. 에듀넷 서버인 HP01, HP05, EDU01은 캐시의 크기를 512K에서부터 19M까지 11개 조건에 대하여 실험을 하였고 기타, NASA와 CLARKNET서버의 경우는 256K 에서부터 2M가 될 째까지 실험을 수행하였다.
성능/효과
Adaptive-level 메모리 캐싱을 현재 운영중인 웹 서버의 작업 부하를 사용하여 실험한 결과는 파일 전체를 캐싱하거나 고정된 threshold을 사용하는 캐싱에 비하여 확연한 성능의 차이가 나타나지 않으나 크기가 큰 이미지 파일과 동영상 등의 멀티미디어 컨텐츠의 비중이 높아질수록 adaptive-level 메모리 캐싱은 효과적인 캐싱전략이 될 수 있음을 보여준다.
이러한 실험 결과들은 서버가 보유한 파일들의 선호도가 특별한 경우를 제외하면, 캐싱 여부를 고려해야 할 정도로 급격히 변하지는 않는다는 것을 의미한다. 이에 본 논문에서는 이러한 현상, 즉 과거의 일정 기간 동안 축적된 자료들로부터, 이들이 가까운 미래에도 많이 요청되면서 서버의 성능 향상에 기여가 예상되는 파 말들을 추출하고 이들을 일괄적으로 캐싱하는 전략을 제안하고자 한다.
두번째 실험은 특이한 서버인 분류한 HP05가 다른 서버들과는 달리 PLC의 성능이 LRU에 비하여 현저히 떨어지는 이유를 보여준다. LRU의 경우 캐시의 성능은 학 파일의 locality에 의하여 결정되어 진다.
캐싱전략인 PLC를 제안하였다. 유명 웹 사이트의 log 파일을 대상으로 실험한 결과, 히트율 측면에서 PLC 전략은 매 파일을 전송할 때에 이를 캐싱하지 않으면서도 기존의 LRU전략보다 높은 효과를 주며, 캐싱으로 인한 웹 서버의 부하를 줄이는 효과를 주고 있음을 확인하였다. 본 연구에서는 히트율 만을 캐싱 알고리즘의 기준으로 보았으나, 이외의 다양한 기준, 예를 들면, 전송률 등 다양한 기준에 대한 연구도 진행 중에 있다.
후속연구
유명 웹 사이트의 log 파일을 대상으로 실험한 결과, 히트율 측면에서 PLC 전략은 매 파일을 전송할 때에 이를 캐싱하지 않으면서도 기존의 LRU전략보다 높은 효과를 주며, 캐싱으로 인한 웹 서버의 부하를 줄이는 효과를 주고 있음을 확인하였다. 본 연구에서는 히트율 만을 캐싱 알고리즘의 기준으로 보았으나, 이외의 다양한 기준, 예를 들면, 전송률 등 다양한 기준에 대한 연구도 진행 중에 있다.
참고문헌 (12)
Internet Statistics:Web Growth, Internet Growth , http://www/mit.edu/people/mkgray/net
Bestavros. A, Matta., 'Load profiling for efficient route selection in multi-class.,' Network protocols, 1997
Bestavros. A, Cheatham. T. Jr. Stefanescu. D, 'Parallel bin packing using first fit and k- delayed best-fit,' parallel and Distributed Processing, 1990
Mike Reddy & Graham P. Fletcher, 'Intelligent web caching using document life histories: A comparison with existing cache management techniques,' J228, School of Computing University of Glamorgan, Pontypridd, Mid Glamorgan. CF37 1DL,
M. R. Korupolu and M. Dahlin, 'Coordinated placement and replacement for large-scale distributed caches,' Proceedings of the IEEE Workshop on Internet Applications, July 1999
S. Williams, M. Abrams, C. R. Standridge, G. Abdulla, and E. A. Fox, 'Removal policies in network caches for World Wide Web documents,' Proceedings of Sigcomm, pp. 293-304, 1996
Igor Tatarinov, Alex Rousskov, valery Soloviev, 'Static Caching in Web Servers,' ncstrl.ndsu_cs/NDSU-CSOR-TR-97-04. 1997
안효범, 조경산, '웹 서버의 참조 특성 분석과 성능 개선', 정보처리학회논문지A, V.8-A, N.3, pp.201-208, 2001
염미령, '이중 큐 구조를 갖는 웹 서버', 정보처리학회논문지A, V.8-a, N.3, pp293-298, pp. 293-298, 2001
E.P.Markatos, 'Main Memory Caching of web documents,' Proceedings of the 5th International World Wide Web Conference, May 6-10, Paris, 1996
D.W.Chang, H.R.KE, R.C. Chang, 'Adaptive-level memory caches on World Wide Web servers,' Elsevier Computer Networks, 32, 2000, pp. 261-275
※ AI-Helper는 부적절한 답변을 할 수 있습니다.