As the amount of data increases rapidly in Internet, the importance of information retrieval and search are being ever more emphasized. Recently, massive-scale search engines such as Google and Yahoo! index tens of billions of web pages, and they process queries in massive-scale parallelism on distributed file system (such as Google File System) using multiple machines. Scalability of parallel search engines is very important because their engines need to support a huge volume of data and a large number of users. Search engines using multi-process/single-thread model are not scalable because they consume large amount of memory resources to process queries in parallel in multiple processes. Therefore, we need to decrease the number of processes by using multi-process/multi-threaded model for the search engine. Multi-process/multi-thread models are more scalable than multi-process/single-thread models because they have processes consisting of multiple threads. However, detailed designs or implementation techniques of multi-process/multi-thread architecture for parallel search engines have not been discussed in the literature.
In this thesis, we design and implement a multi-process/multi-thread model for ODYSSEUS-/Parallel-OOSQL parallel DBMS/search engine that has been under development at KAIST. The proposed model significantly decreases the number of processes of ODYSSEUS/Parallel-OOSQL and reduces the amount of memory usage and context switching overhead. Besides, we propose an effective method for maintaining these processes/threads and increasing the query processing speed. We also conduct experiments to show that the proposed multi-process/multi-thread model is more scalable than the multi-process/single-thread model. The experimental results show that the proposed model outperforms up to 69% in memory usage and 19% in query processing speed.
인터넷 상의 데이터의 양이 폭발적으로 증가함에 따라 정보 검색 기술의 중요성이 대두되고 있다. Google, Yahoo!와 같은 대형 검색 엔진은 수백억 건의 웹 페이지를 색인하고 있으며, 이러한 대량의 데이터에 대하여 많은 사용자의 질의를 처리하기 위해서 여러 대의 머신에서 병렬로 질의를 처리한다. 병렬 정보 검색 엔진은 데이터 양의 증가와 사용자 수의 증가에 유연하게 대응할 수 있어야 하기 때문에 확장성이 높아야 한다. 그러나 멀티프로세스/단일쓰레드 모델을 따르는 병렬 검색 엔진은 여러 대의 머신에서 여러 개의 질의를 동시에 처리하기 위해서 다수의 프로세스가 필요하기 때문에 메모리 자원이 많이 소모되어서 확장성이 낮다. 따라서 병렬 검색 엔진에 멀티프로세스/멀티쓰레드 모델을 사용함으로써 머신 내부에 생성되는 프로세스의 개수를 감소시킬 필요가 있다. 멀티프로세스/멀티쓰레드 모델은 하나의 프로세스에 다수의 쓰레드를 사용하기 때문에 멀티프로세스/단일쓰레드 모델에 비해 확장성이 높다. 그러나 병렬 검색 엔진에 대한 멀티프로세스/멀티쓰레드 아키텍처를 세부적으로 설계하고 구현한 문헌은 잘 알려진 바가 없다.
본 논문에서는 한국과학기술원 전산학과 데이터베이스 및 멀티미디어 연구실에서 개발한 대형 병렬 검색 엔진인 오디세우스/Parallel-OOSQL을 확장하여 멀티프로세스/멀티쓰레드 모델로 설계하고 구현한다. 오디세우스/Parallel-OOSQL 내부에 생성되는 프로세스의 개수를 감소시킴으로써 메모리 사용량과 컨텍스트 스위칭 비용을 감소시킨다. 또한, 생성된 프로세스/쓰레드를 효과적으로 관리하는 방법을 제안하여 질의 처리 속도를 향상시킨다. 마지막으로 실험을 통해 멀티프로세스/멀티쓰레드 모델이 멀티프로세스/단일쓰레드 모델에 비하여 확장성이 향상됨을 보인다. 실험 결과, 메모리 사용량이 최대 69% 감소하며, 질의 처리 시간은 최대 19% 감소함을 보인다.
