The need for performance enhancement of a large scale Web caching system is becomingly increasing, since the World Wide Web proliferates as the unique channel of information communication. We have identified the I/O bottleneck of a storage subsystem as the major performance limiting factor for a large scale web caching system. Since I/O operations are caused by both metadata operations and data operations, we have proposed new data structures and algorithms that can reduce I/O overhead caused by each of them.
First, we have proposed metadata structures for a large scale Web caching system, which utilizes the benefits of NAND flash memory. We have proposed an efficient index structure for NAND flash memory, called the Dynamic Forest. By accumulating the changes to the index in RAM and writing them together sequentially at the end of the index, Dynamic Forest can significantly reduce write operations. Consequently, a large scale Web caching system adopting Dynamic Forest can achieve lower latency for metadata access. We also have proposed an efficient NAND flash-optimized hash index structure, called Multi Level Dynamic Hashing. Like Dynamic Forest, the proposed hash index structure completely eliminates in place writes for index updates. Consequently, the proposed index structure can minimize the number of write operations and improve the performance for metadata access.
Second, we have proposed an effective admission control algorithm, called Adapitive Frequency-based Admission Control (AFAC), for a large scale Web caching system, which can reduce the I/O load imposed upon storage subsystem. By enforcing the hotness of admitted objects adaptively, AFAC can significantly reduce disk I/O while maintaining a high hit ratio.
The main benefits of our proposed methods are as follows: First, our proposed index structures, specially optimized for NAND flash memory, can make a Web caching system operate fast. Adopting NAND flash memory for storing metadata can make the cache fast alone. However, our proposed structures does not suffer from the in-place update problem and/or wear-out problem of NAND flash memory, while most traditional data structures suffer from the problems and cannot provide the performance level to ours. Second, our proposed admission algorithm can reduce the storage overhead significantly. We have shown this through an extensive set of experiments. In the current Web environment where large volumes of objects such as video are prevalent, the effect of our admission control algorithm can be shine. Moreover, our admission algorithm is self-adaptive, which is a major win over the other admission control algorithm. Third, though we have proposed two index structures as strong candidates for metadata management for a large scale Web caching system, they are inherently general purpose index structure in NAND flash memory environment. In other words, our proposed index structures can be deployed not only to a Web caching system, but to other data processing applications, including embedded database management system.
In summary, we have proposed and evaluated new ways to enhance the performance of a large scale Web caching system. In addition to our arguments, we know that the storage overhead is the real performance limiting factor of a large scale Web caching system by real experiences. Accordingly, we expect that our proposed methods can improve the performance of a large scale Web caching system in practice.
인터넷으로 통칭되는 현 시대의 정보 시스템의 한 가운데에는 월드와이드웹(웹)이 위치하고 있다. 용이한 접근방식 및 그를 뒷받침 하는 개방형 표준에 기인하여 웹은 이미 인터넷 그 자체가 되어버렸으며, 그 참여자 및 정보소통량의 규모는 이미 거대해져 있는 상태이며 계속 증가하는 추세이다. 웹 캐싱은 시스템의 대규모화가 야기하는 문제점을 해결하기 위한 중요한 기술중의 하나이다. 사용자의 입장에서는 보다 신속하게 정보를 접근할 수 있으며 정보 서비스 제공자의 입장에서 네트워크에 소통되는 데이터의 양을 감소시켜 병목현상을 회피할 수 있고, 정보 제공자의 입장에서는 웹 서버의 부하를 줄일 수 있다는점이 웹 캐싱을 통해 기대할 수 있는 장점들이다. 그렇기 때문에 웹 캐싱은 현재의 웹 구조에 있어서 중요한 기반구조의 하나로서 널리 도입되어있는 상황이다. 이에, 필연적으로 웹 캐싱 시스템의 고성능성이 요구된다. 웹 캐싱 시스템이 충분한 성능을 발휘하지 못한다면 웹 캐싱 시스템 자체가 발생하는 병목현상으로 인하여 웹 캐싱에 기대하는 장점이 발휘하지 못하는 동시에 전반적인 웹 서비스의 품질 저하가 나타나기 때문이다. 다수의 클라이언트로부터의 정보 요청을 처리하며, 다량의 웹 객체를 캐싱하는 대규모 웹 캐싱 시스템에 있어서, 전체 처리 성능예 직접적인 연관을 가지고 있는것이 저장시스템 접근성능이다. 따라서, 본 논문에서는 웹 캐싱 시스템의 저장시스템 접근성능을 향상시키기 위한 방법으로써, 메타데이터와 데이터 각각에 대한 성능 향상 방법을 제안하였다.
본 논문에서는 먼저 대규모 웹 캐싱 시스템의 메타데이터 처리성능 향상을 위하여, NAND 플래시 메모리에 특화된 색인 구조 두 가지를 제안하였다. NAND 플래시 메모리는 빠른 접근 속도로 인하여, 메터데이터를 NAND 플래시 메모리를 통해 관리하는 것만으로도 채용한 시스템의 성능향상이 기대되지만, 인플레이스 갱신을 지원하지 못하는 특성에 기인하여 디스크 시스템을 가정하여 연구된 기존의 색인구조로는 충분한 성능을 끌어낼 수 없으며 메모리마모 문제도 발생한다는 단점이 있다. 따라서, 본 논문에서는 순차 연산을 지원하는 기존의 트리색인구조에 대응되는 동적 포레스트와, 해시색인구조에 대응되는 다중 레벨 해시 구조를 제안하였다. 두 가지 색인구조들은 모두 저레벨의 색인구조들이 병합되어 고 레벨의 색인구조를 생성하는 다중 레벨 구조를 지니고 있으며, 각 레벨의 색인구조는 순차적 쓰기연산만을 통해 갱신이 가능함으로써 NAND 플래시 메모리상에서 효율적인 성능을 보장한다. 개별 연산 성능에 대하여 평가 분석한 결과, 제안한 방법은 기존의 대표적인 색인구조인 B트리와 정적 해시에 비하여 삽입 및 삭제 연산에 있어서 쓰기 연산의 수를 현격하게 감소시킴으로써 많은 성능향상을 보장하였다. 비록 검색 연산에 있어서는 다중 레벨 구조로 인해 성능이 저하되었지만, 실제 색인연산 워크로드를 바탕으로 한 테스트에서 전반적인 성능이 수 배 향상됨을 확인하였다. 본 색인구조들은 웹 캐싱 시스템의 메타데이터 처리 성능 향상을 위해 연구되었지만, 본질적으로 범용성을 지니고 있으므로, NAND 플래시메모리에 기반한 다른 응용분야, 즉 내장형 시스템등의 성능 향상을 위해서도 적용될 수 있다.
두 번째 연구 주제로서, 본 논문에서는 웹 캐싱 시스템에 저장되는 데이터의 절대적인 양을 절감함으로써 저장시스템의 성능을 향상시키고자 수락 제어 (admission control) 알고리즘 AFAC를 제안하였다. 사용자가 요청한 웹 정보중에서는 빈번히 요청될 정보 외에도 드물게 요청될 정보도 존재한다. 이들을 구별없이 모두 저장코자 하는 경우, 드물게 요청될 정보를 저장함으로 인하여 효용가치 없는 저장및 그로인한 디스크 연산이 발생함으로 인해, 디스크 병목 및 히트비율 저하가 초래될 수 있다. 이에 본 논문에서는 빈번히 요청될 데이터만을 예측하여 저장을 수락함으로써 저장장치 성능을 향상시키고자 하였다. 제안하는 방법은 빈번히 요청되는 데이터의 판단과정에 있어 자기 적응형 특성을 지니므로, 기존의 수락 제어 알고리즘이 잘못 예측된 설정값으로 인하여 수락 제어가 적절히 이루어지지 못하는 단점을 가지지 않는다. 여러가지 실제 웹 워크로드를 대상으로 한 실험을 통해, 제안한 수락 제어 기법은 모든 워크로드에 대하여 수락제어기법을 적용하지 않은 경우나 기존의 수락 제어 기법을 이용한 경우에 비해 가장 높은 히트 비율을 유지하면서 동시에 디스크 쓰기 연산을 수십-수백배 절감할 수 있음을 보였다.본 수락제어 알고리즘은 특정 객체 갱신 알고리즘을 전제하고 있지 않기에, 상황에 따라 적합한 객체 갱신 알고리즘과 함께 웹 캐시 시스템 성능을 향상시키기 위해 사용될 수 있다.
