µ¥ÀÌÅͺ£À̽º ¿¬±¸È¸Áö(SIGDB)
ÇѱÛÁ¦¸ñ(Korean Title) |
ODYS º´·Ä DBMS/°Ë»ö¿£ÁøÀ» À§ÇÑ ³»°íÀ强 ¹× ºÎÇϱÕÇü ¸ðµâÀÇ ¼³°è ¹× ±¸Çö |
¿µ¹®Á¦¸ñ(English Title) |
Design and Implementation of a Fault Tolerance and Load Balancing Module for the ODYS Parallel DBMS/Search Engine |
ÀúÀÚ(Author) |
±è´öȸ
À±Å¼·
±ÇÇõÀ±
Ȳ±Ô¿µ
Deok-Hoe Kim
Tae-Seob Yun
Hyuk-Yoon Kwon
Kyu-Young Whang
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 29 NO. 02 PP. 0043 ~ 0064 (2013. 08) |
Çѱ۳»¿ë (Korean 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% Çâ»óµÇ¾úÀ½À» º¸ÀδÙ. |
¿µ¹®³»¿ë (English 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?e 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. |
Å°¿öµå(Keyword) |
º´·Ä °Ë»ö ¿£Áø
³»°íÀ强
ºÎÇϱÕÇü
Parallel search engine
fault tolerance
load bala
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|