Web caching is an important technique for enhancing the performance of web applications and for reducing the load on the web server and the network through the use of local cache. Web caching needs to take into account the characteristics of web data like the expiration time in addition to addressing the problem of maintaining cache consistency as in traditional data caching. The expiration time is a point in time when the cached data becomes invalid as the original data in the web server is updated. TTL(time-to-live) is the duration from the current time to the expiration time. These values can influence cache replacement algorithms and TTL-based consistency maintenance mechanisms. First, in the case of cache replacement algorithms, these values can make the reference probability in the traditional replacement algorithms differ from the probability of taking effect of using cache. Therefore, a new notion of the probability that incorporates the effect of expiration time is necessary for deriving effective replacement algorithms. Next, web caching has the leeway of delaying the refreshment of cache when the web server updates the cached data. This weak consistency allows the TTL-based cache consistency mechanism to be widely used. In the TTL-based consistency maintenance mechanism, the cache server uses the cached data assuming that the original data item is not to be updated during its TTL (i.e., till its expiration time). Therefore, to use this method, we need the TTL of each data item that either the web server assigns or the cache server estimates.
In this dissertation, we propose a method that enhances the performance of web caching by incorporating the expiration time of web data. We introduce the notion of the effective reference probability that incorporates the effect of expiration time into the reference probability used in the existing cache replacement algorithms. We formally define the effective reference probability and derive it theoretically using a probabilistic model. By simply replacing the reference probabilities with the effective reference probability in the existing cache replacement algorithms, we can take the effect of expiration time into account. The results of performance evaluation through experiments show that the replacement algorithms using the effective reference probability always outperform the existing ones. The reason is that the proposed method precisely reflects the theoretical probability of getting the cache effect, and thus, incorporates the influence of the expiration time more effectively. In particular, when the cache fraction is 0.05 and data update is comparatively frequent(i.e., the update frequency is more than 1/10 of the reference frequency), the performance enhancement is more than 30% in LRU-2 and 13% in PSS-ROF(PSS incorporating a refresh overhead factor).
In order to use the effective reference probability and TTL-based consistency maintenance, web data should have its expiration time given or estimated. How-ever, existing two TTL estimation methods (the fixed TTL method and the heuristic method) are devoid of any intuitive interpretation of the estimated TTLs and any theoretical reasoning behind the estimation. This leads us to develop a new method that mends these deficiencies.
We propose the update-risk based TTL estimating method. Here, the update risk for a given TTL is defined as the probability that the original data will be updated within the TTL, so that the assumption that the original one will not be updated within the TTL is falsified. Then, the cache server calculates the value of the TTL using a formula we develop and given update risk assuming the Poisson process as the model of update occurrences. The results of our experiments, performed using the logs of a real cache server, show that a measured ratio of the estimated TTLs having update(s) to all the estimated TTLs closely matches the update risk used to estimate the TTLs. This means the proposed method is applicable in real environments. Moreover, the notion of the update risk is clearer in its intention and semantics than existing methods. These confirm the superiority of our method to the conventional ones. In addition, we reilluminate the two aforementioned conventional methods in light of our method.
In summary, we have established a theoretical basis for estimating and utilizing the expiration time (and the TTL) in web caching, which were devoid of in the existing methods. We have also shown through extensive experiments that the proposed techniques are practically usable.
웹 캐슁은 캐쉬 액세스를 통해 웹 응용의 성능을 향상시키고, 웹 서버와 네트워크의 부하를 감소시키기 위한 중요한 기술이다. 웹 캐슁은 전통적인 데이터 캐슁의 캐쉬 일관성 유지문제를 해결해야 할 뿐 아니라 만기시간과 같은 웹 데이터의 특성을 고려할 필요가 있다. 만기시간이란 서버의 원본 데이터가 갱신되어 캐쉬된 데이터와 원본 데이터가 서로 달라져 캐쉬된 데이터가 유효하지 않게 되는 시점이다. 그리고, TTL(time-to-live)은 현재 시점부터 만기시간까지의 거리이다. 이 값들은 캐쉬 교체 알고리즘과 TTL 기반 일관성 유지 방법에 영향을 미칠 수 있다. 먼저, 캐쉬 교체 알고리즘에서는 이 값들의 영향으로 전통적인 교체 알고리즘에서 사용되는 참조확률이 캐쉬효과를 얻을 확률과 달라질 수 있다. 따라서, 효율적인 교체 알고리즘을 유도하기 위해서 만기시간의 영향을 반영하는 새로운 확률 개념이 필요하다. 다음으로, 웹 환경에서는 기존의 캐슁과는 달리 웹 서버의 데이터 갱신을 지연하여 캐쉬에 반영하는 약 일관성이 허용되므로, TTL 기반 캐쉬 일관성 유지 방법이 많이 사용되고 있다. TTL 기반 일관성 유지 방법에서 캐쉬 서버는 데이터에 부여된 TTL동안에는(즉, 만기되기 이전에는) 원본 데이터 아이템은 갱신되지 않을 것이라고 가정하고 캐쉬된 데이터를 그대로 사용한다. 따라서, 이 방법을 사용하기 위해서 각 데이터 아이템에는 웹 서버에서 부여하거나 캐쉬 서버에서 추정한 TTL이 필요하다.
본 학위논문에서는 웹 데이터의 만기시간(expiration time)을 반영하여 웹 캐쉬의 성능을 향상시키는 방법을 제안한다. 먼저, 기존 캐쉬 교체 알고리즘에서 사용된 참조확률에 만기시간의 영향을 반영한 유효참조확률(effective reference probability)이라는 개념을 도입한다. 그리고, 유효참조확률을 정형적으로 정의한 후, 확률적 모델 하에서 이론적으로 유도한다. 기존의 교체 알고리즘에서 참조확률을 유효참조확률로 간단히 대체하여 기존 교체 알고리즘에 만기시간의 영향을 반영할 수 있다. 실험을 통하여 성능을 측정한 결과, 유효참조확률을 사용한 알고리즘들이 기존의 알고리즘들보다 항상 우수하다. 이것은 제안한 방법이 만기시간을 고려하여 캐쉬효과를 얻을 이론적인 확률을 정확히 반영하므로, 만기시간의 영향을 보다 효과적으로 통합하기 때문이다. 특히, 유효참조확률은 캐쉬비율이 0.05이고 갱신이 비교적 자주 일어날 경우(갱신빈도가 참조빈도의 1/10 이상인 경우)에 LRU-2의 경우 30% 이상, PSS-ROF(refresh overhead factor가 통합된 PSS)의 경우 13%이상 성능을 개선한다.
유효참조확률과 TTL 기반 일관성 유지 방법을 사용하려면, 웹 데이터에 부여되거나 추정한 만기시간이 있어야 한다. 그러나, 기존의 두 가지 추정방법(고정 TTL방법과 휴리스틱 방법)은 추정한 TTL에 대한 직관적 의미 해석이 어렵고, 이론적인 추정근거가 빈약하다. 따라서, 이러한 단점을 보완하는 새로운 방법의 개발이 요구되었다.
본 학위논문에서는 위험도 기반 TTL 설정 방법을 제안한다. 여기에서 위험도란 주어진 TTL 이내에 원본 데이터가 갱신되어 TTL 동안 원본 데이터가 갱신되지 않을 것이라는 가정이 틀릴 확률로 정의한다. 그리고, 캐쉬 서버는 갱신사건 모델을 포아송 과정으로 가정하고, 제안한 수식과 주어진 위험도를 이용하여 TTL 값을 계산한다. 실제 캐쉬 서버의 로그를 이용하여 실험한 결과, 전체 추정한 TTL에 대한 갱신이 발생한 TTL의 측정비율이 TTL을 추정하기 위해 사용된 위험도와 근사하게 일치한다. 이것은 제안한 방법이 실제 환경에 적용될 수 있음을 의미한다. 또한, 위험도란 개념은 그 의미와 목적이 기존 방법들 보다 명확하다. 제안한 방법은 이러한 점에서 기존 방법에 비해 우수하다고 사료된다. 그리고, 제안한 방법의 시각에서 앞서 거론한 기존 방법들을 재조명한다.
결론적으로, 본 학위논문은 기존 방법들에서 부족한, 웹 캐쉬에서 만기시간(또한, TTL)을 추정하고 활용하는 이론적인 기반를 수립하였다. 그리고, 제안한 방법들이 실용적으로 유용함을 실험을 통하여 보였다.
