ODYS 병렬 DBMS/검색엔진을 위한 내고장성 및 부하균형 모듈의 설계 및 구현 = Design and Implementation of a Fault Tolerance and Load Balancing Module for the ODYS Parallel DBMS/Search Engine

다국어 초록 (Multilingual Abstract)

As the amount of data increases explosively on Internet, the role of parallel search engines becomes more important. The web search engine is a representative large-scale parallel search engine, which consists of a large number of machines. Thus, there is a high possibility of failure and skewed load over the machines. Therefore, fault tolerance and load balancing features are essential for parallel web search engines to provide a reliable service and an optimized performance. Commercial web search engines such as Google and Yahoo! provide fault tolerance and load balancing features for parallel query processing. However, their details have not been discussed in the literature. Meanwhile, parallel processing framework MapReduce supports fault tolerance and load balancing features over a large number of machines during parallel query processing. Therefore, its method is applicable to the parallel search engine.
In this paper, we design and implement a MapReduce-style fault tolerance and load balancing module for ODYS, which is a parallel search engine that has been under development at KAIST.
In particular, for the environment of running a lot of concurrent short-running queries, we propose a low-overhead process and communication architecture of the fault tolerance and load balancing module. We also propose an index structure for effectively managing the status and the load of slave machines and the status of slave processes. Finally, we conduct experiments to show that the proposed fault tolerance and load balancing module works in an effective way. The result of the experiments shows that ODYS with the fault tolerance and load balancing module provides fault tolerance significant enhancement in performance. ODYS incurs 0.4% of additional query processing time when one out of 400 slave processes is at fault, 86.1% of additional query processing time when one out of 4 slave machines is at fault where the query load is 5 million queries/day. It also provides load balancing while outperforming the naïve configuration of ODYS without load balancing by up to 16.9% in the average query processing time when the query load is 9 million queries/day and two nodes are duplicated in the configuration.

국문 초록 (Abstract)

최근 인터넷 상의 데이터의 양이 폭발적으로 증가함에 따라 분산 저장된 대규모의 데이터에 대한 검색을 병렬적으로 수행하는 병렬 검색 엔진의 역할이 중요해지고 있다. 웹 검색 엔진은 대표적인 대형 병렬 검색 엔진이므로 이를구성하는 머신의 수가 많다. 따라서 일부 머신이 고장 날 가능성이 높고, 각 머신들의 부하에 불균형이 발생하기쉽다. 그러므로 병렬 웹 검색 엔진은 안정적인 정보 검색 서비스를 제공할 수 있도록 하는 내고장성(Fault tolerance)기능과 시스템의 부하를 균형화 하여 전체 시스템의 성능을 최적화하는 부하균형(Load balancing) 기능이 필요하다. Google, Yahoo!와 같은 상용 검색 엔진은 질의를 병렬로 처리하는 과정에서 내고장성 및 부하균형 기능을 지원한다. 그러나 이에 대한 구체적인 방법은 공개되어 있지 않다. 한편, 병렬 처리 프레임워크인 MapReduce는 질의를병렬로 처리하는 과정에서 많은 수의 머신에 대해 내고장성 및 부하균형 기능을 지원한다. 따라서 병렬 검색 엔진에MapReduce 방식의 내고장성 및 부하균형 기능을 적용할 수 있다.
본 논문에서는 한국과학기술원 전산학과 데이터베이스 및 멀티미디어 연구실에서 개발한 병렬 검색 엔진인ODYS를 위한 내고장성 및 부하균형 모듈을 병렬 처리 프레임워크인 MapReduce에서 제공하는 내고장성 및 부하균형 방법에 기반하여 설계하고 구현한다. 특히, 처리 시간이 짧은 수많은 질의를 동시에 처리해야 하는 병렬 검색엔진의 요구조건을 만족시키기 위해 적은 오버헤드로 내고장성 및 부하균형 기능을 수행할 수 있는 프로세스 및통신 구조를 제안한다. 그리고 질의를 처리하는 다수의 슬레이브 머신의 상태 및 부하와 슬레이브 프로세스의 상태를 효과적으로 관리할 수 있는 색인 자료구조를 제안한다. 마지막으로 실험을 통해 본 논문에서 설계하고 구현한모듈이 효율적으로 내고장성 기능을 수행하고, 효과적으로 부하균형 기능을 수행함을 보인다. 실험 결과, 내고장성및 부하균형 모듈을 적용한 ODYS가 하루당 5백만 개의 질의 부하에서 고장이 발생하지 않은 경우에 비해 슬레이브프로세스(400개의 슬레이브 프로세스 중 1개를 고장시킴)에 대해 약 0.4%, 슬레이브 머신(4대의 슬레이브 머신 중1대를 고장시킴)에 대해 약 86.1%의 추가적인 질의 수행 시간으로 내고장성 기능을 수행할 수 있음을 보였다. 또한,부하균형 기능으로 인해 하루당 9백만 개의 질의 부하와 2개의 노드가 복제된 환경에서 부하균형을 하지 않는 나이브한 구성의 ODYS에 비해 평균 질의 수행 시간이 약 16.9% 향상되었음을 보인다.

참고문헌 (Reference)

1 이미영, "클라우드 기반 대규모 데이터 처리 및 관리 기술" 24 (24): 41-54, 2009

2 한욱신, "오디세우스객체 관계형 멀티미디어 DBMS의 아키텍처" 45-47, 2000

3 류재준, "오디세우스/Parallel-OOSQL: 오디세우스 정보검색용 밀결합 DBMS를 사용한 병렬 정보 검색 엔진" 한국정보과학회 14 (14): 412-429, 2008

4 류재준, "오디세우스/Parallel-OOSQL: 오디세우스 객체관계형 데이타베이스 관리 시스템을 이용한 병렬 정보검색 시스템" KAIST 2002

5 정재화, "시작하세요 하둡 프로그래밍" 위키북스 2012

6 Luiz, A., "Web Search for a Planet: The Google Cluster Architecture" 23 (23): 22-28, 2003

7 Shvachko, K., "The Hadoop Distributed File System" 1-10, 2010

8 Ghemawat, S., "The Google File System" 29-43, 2003

9 Venner, J., "Pro Hadoop" Apress 2009

10 DeWitt, J., "Parallel Database Systems: the Future of High Performance Database Systems" 35 (35): 85-98, 1992

11 Valduriez, P., "Parallel Database Systems: Open Problems and New Issues" 1 (1): 137-165, 1993

12 Cooper, B., "PNUTS: Yahoo!'s Hosted Data Serving Platform" 1 (1): 1277-1288, 2008

13 MacFarlane, A., "PLIERS: A Parallel Information Retrieval System Using MPI" 1999

14 Yang, C., "Osprey: Implementing MapReduce-Style 내고장성 in a Shared-Nothing Distributed Database" 657-668, 2010

15 Strom, R., "Optimistic Recovery in Distributed Systems" 3 (3): 204-226, 1985

16 Ganesan, P., "Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems" 444-455, 2004

17 Whang, K., "Odysseus: a High-Performance ORDBMS Tightly-Coupled with IR Features" 1104-1105, 2005

18 Whang, K., "ODYS: An Approach to Building a Massively-Parallel Search Engine Using a DB-IR Tightly-Integrated Parallel DBMS for Higher-Level Functionality" 2013

19 Dean, J., "MapReduce: Simplified Data 프로세스ing on Large Clusters" 137-149, 2004

20 Stonebraker, M., "MapReduce and Parallel DBMSs: Friends or Foes?" 64-71, 2010

21 Abouzeid, A., "HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads" 2 (2): 922-933, 2009

22 "Google"

23 Golubchik, L., "Fault Tolerance Issues in Data Declustering for Parallel Database Systems" 17 (17): 1994-, 1994

24 Dean, J., "Designs, Lessons and Advice from Building Large Distributed Systems" 2009

25 Silverschatz, A., "Database System Concepts" McGraw Hill 2010

26 Scheuermann, P., "Data Partitioning and Load Balancing in Parallel Disk Systems" 7 (7): 48-66, 1998

27 Dean, J., "Challenges in Building Large-Scale Inform ation Retrieval Systems" 1 : 1-, 2009

28 Dikenelli, O., "A Load Balancing Approach for Parallel Database Machines" 51-58, 1995