MapReduce 프레임워크의 작업 완료 시간 단축을 위한 JobTracker 결함 허용 메커니즘

강민구(Minkoo Kang),박기진(Kiejin Park),황병현(Byeonghyeon Hwang) 한국정보과학회 2012 정보과학회 컴퓨팅의 실제 논문지 Vol.18 No.3

클라우드 컴퓨팅 서비스를 제공하기 위해서는 데이터의 분산 저장 및 병렬 처리가 가능한 IT 인프라 구축이 필수적이다. 이를 위해서 대용량 데이터의 분산 처리가 지원되는 MapReduce 프레임워크가 각광 받고 있다. MapReduce 프레임워크는 저비용으로 분산 병렬 처리 시스템을 구축하기에 효과적이지만, 전체 MapReduce 작업의 스케줄링 및 작업 할당을 담당하는 JobTracker가 SPOF(Single Point of Failure)라는 문제가 있다. 이로 인해 MapReduce 작업 도중 JobTracker에 결함이 발생하게 되면 전체 MapReduce 작업을 처음부터 다시 시작해야 하므로 작업 완료 시간이 증가한다. 위와 같은 문제를 해결 하고자 본 논문에서는 MapReduce 프레임워크의 JobTracker 결함 허용 메커니즘을 설계˙구현하고, MapReduce 테스트베드와 결함 주입 기법을 이용하여 성능 평가를 실시하였다. 그 결과, 기존 MapReduce에 비해 JobTracker 결함 허용이 적용된 MapReduce의 평균 작업 완료 시간은 46.5%~64.4% 감소됨을 확인하였다. In order to effectively provide cloud computing, IT infrastructure which supports distributed file system and parallel data processing is essential. To this end, MapReduce framework has been widely used for distributed processing of large-scale data. MapReduce framework has been proven as an efficient way to construct distributed and parallel processing system at relatively low cost. However, it has the problem of single point of failure (SPOF) at JobTracker that is responsible for scheduling and assigning of all MapReduce tasks. When JobTracker has failed, the completion time of the MapReduce job is increased because the entire MapReduce tasks must be restarted. To resolve the above mentioned problem we designed and implemented JobTracker fault-tolerant mechanism for MapReduce framework. The performance of the mechanism is evaluated by using MapReduce testbed and fault-injection method. As a result, the average job completion time of the mechanism is dramatically reduced about 46.5%~64.4% compared to the result of a naive MapReduce.

WSP: Whole-Split Passing Technique for Accelerating Hadoop Map Ttask by Using GPU

구본근 한국정보기술학회 2014 한국정보기술학회논문지 Vol. No.

MapReduce는 대용량 데이터 처리를 위한 분산 처리 프로그래밍 모델이다. Hadoop은 MapReduce를 구현한 프레임워크 중의 하나이며, 분산 파일 시스템인 HDFS를 포함하고 있다. 계산 집약적인 MapReduce 응용은중요한 Hadoop 응용 중의 하나이다. 많은 연구자들은 GPU를 이용하여 이들 응용의 MapReduce 태스크를 고속화하려고 하고 있다. 본 논문에서는 GPU를 이용한 MapReduce 태스크 고속화, 특히 Map 태스크 고속화를 위해 스플릿 전달(Whole Split Passing) 기법을 제안하다. 이 기법은 Map 태스크가 스플릿 내의 한 개 또는 소소의 레코드를 GPU에게 전달하는 대신에 스플릿 전체를 한 번에 전송하는 것이다. 따라서 CPU에서 실행되는 Map 태스크와 GPU에서 실행되는 커널 사이의 데이터 전송 오버헤드를 감소시킬 수 있고, 스플릿 내의 레코드 수만큼의 스레드를 실행할 수 있어 GPU의 병렬 처리 성능을 충분히 사용할 수 있다. 이 기법이 유효함을 보이기 위해 실험을 하였으며, 그 결과는 스플릿 전체를 한 번에 전송하는 기법이 Map 태스크의 실행 시간을 감소시킬 수 있음을 보였다. MapReduce is a programming model for distributed computing to handle large-scale data. Hadoop is one of MapReduce implementation frameworks, and includes a distributed file system called as HDFS. A compute-intensive MapReduce application is an important class of applications. Many research projects try to accelerate MapReduce task of these applications by using GPU. Our work is one of these researches. Especially, we focus on the accelerating Map task by using GPU. In this paper, we propose the whole-split passing technique. Our technique is that Map task transfers the whole-split block to GPU instead of one or a small number of records. Therefore our technique can reduce the communicating overhead between Hadoop Map task and kernel executed on CPU and GPU, respectively, and fully use GPU’s parallel computing power by initiating threads as many as the number of records in split. To show the validation of our technique, we perform experiments. The results of our experiments show that the whole-split passing technique can reduce the execution time of Map task.

빅 데이터의 MapReduce를 이용한 효율적인 병렬 유전자 알고리즘 기법

홍성삼(Sung-Sam Hong),한명묵(Myung-Mook Han) 한국지능시스템학회 2013 한국지능시스템학회논문지 Vol.23 No.5

빅 데이터는 일반적으로 사용되는 데이터 관리 시스템으로 데이터의 처리, 수집, 저장, 탐색, 분석을 할 수 없는 큰 규모의 데이터를 말한다. 빅 데이터 기술인 맵 리듀스(MapReduce)를 이용한 병렬 GA 연구는 Hadoop 분산처리환경을 이용하여, 맵 리듀스에서 GA를 수행함으로써 GA의 병렬처리를 쉽게 구현할 수 있다. 기존의 맵 리듀스를 이용한 GA들은 GA를 맵 리듀스에 적절히 변형하여 적용하였지만 잦은 데이터 입출력에 의한 수행시간 지연으로 우수한 성능을 보이지 못하였다. 본 논문에서는 기존의 맵 리듀스를 이용한 GA의 성능을 개선하기 위해, 맵과 리듀싱과정을 개선하여 맵 리듀스 특징을 이용한 새로운 MRPGA(MapReduce Parallel Genetic Algorithm)기법을 제안하였다. 기존의 PGA의 topology 구성과 migration 및 local search기법을 MRPGA에 적용하여 최적해를 찾을 수 있었다. 제안한 기법은 기존에 맵 리듀스 SGA에 비해 수렴속도가 1.5배 빠르며, sub-generation 반복횟수에 따라 최적해를 빠르게 찾을 수 있었다. 또한, MRPGA를 활용하여 빅 데이터 기술의 처리 및 분석 성능을 향상시킬 수 있다. Big Data is data of big size which is not processed, collected, stored, searched, analyzed by the existing database management system. The parallel genetic algorithm using the Hadoop for BigData technology is easily realized by implementing GA(Genetic Algorithm) using MapReduce in the Hadoop Distribution System. The previous study that the genetic algorithm using MapReduce is proposed suitable transforming for the GA by MapReduce. However, they did not show good performance because of frequently occurring data input and output. In this paper, we proposed the MRPGA(MapReduce Parallel Genetic Algorithm) using improvement Map and Reduce process and the parallel processing characteristic of MapReduce. The optimal solution can be found by using the topology, migration of parallel genetic algorithm and local search algorithm. The convergence speed of the proposal method is 1.5 times faster than that of the existing MapReduce SGA, and is the optimal solution can be found quickly by the number of sub-generation iteration. In addition, the MRPGA is able to improve the processing and analysis performance of Big Data technology.

가상 클러스터 환경에서 하둡 맵리듀스의 성능 향상을 위한 부하분산 기법

정대영(DaeYoung Jung),남윤성(YoonSung Nam),이권용(KwonYong Lee),박성용(SungYong Park) 한국정보과학회 2013 정보과학회 컴퓨팅의 실제 논문지 Vol.19 No.12

고성능 컴퓨팅 등의 다양한 분야에서 널리 이용되던 클러스터 컴퓨팅이 최근 클라우드 서비스의 등장으로 클라우드 상에서 가상 클러스터로 구성되고 있다. 대용량 데이터 처리의 대표적 분산처리 플랫폼인 하둡 클러스터의 구성도 클라우드 상으로 이동하는 추세이며 가상 맵리듀스 클러스터의 성능 향상을 위한 연구가 활발히 이루어지고 있다. 맵리듀스는 분산 처리되는 모든 태스크가 종료되어야 최종 결과를 도출할 수 있는 특성을 갖고 있으므로, 태스크들의 완료 시간이 불균등하면 전체 맵리듀스의 성능이 하락한다는 단점이 있다. 하둡 맵리듀스에서는 추론적 실행 기법을 사용하여 이 문제를 해결하고자 하였지만 가상 클러스터에서는 클라우드 자원 낭비와 같은 문제를 발생시킨다. 본 논문은 Xen 기반의 클라우드 상에서 구성된 가상 맵리듀스 클러스터에서 추론적 실행에 의해 발생하는 문제를 해결하는 부하분산 기법을 제안한다. 제안하는 부하분산기법은 Xen 크레딧 스케줄러와 리눅스 스케줄러를 태스크 수행시간에 따라 동적으로 조절하여 태스크의 수행시간 불균등을 해소한다. 실험을 통해 태스크들의 수행시간이 기존의 하둡 맵리듀스에 비해 균등하게 이루어지고 낙오자 태스크의 발생을 방지하여 성능이 향상됨을 볼 수 있었다. Recently, as cloud computing service has been more popular, the clusters, widely used for high performance computing, are gradually configured as virtual clusters on the cloud environments. Hadoop MapReduce cluster, which is one of the representative distributed processing platforms, is also moved into the cloud, so that a lot of researches have been conducted to improve the performance of virtual MapReduce cluster. Since the MapReduce cannot complete a job until all the tasks are finished, unbalanced completion times of tasks result in performance degradation of the MapReduce. Even Hadoop MapReduce uses a speculative execution to solve this problem, it makes other problems including waste of cloud resources in the virtual cluster environments. In this paper, we propose a new load-balancing method to solve the problems occurred by the speculative execution of virtual MapReduce cluster running on the Xen-based clouds. The proposed method dynamically adjusts Xen credit scheduler and Linux scheduler based on the completion times of tasks, and thereby reduces the amount of unbalanced completion times of tasks. We evaluated the proposed method with the original Hadoop MapReduce, and concludes that our load balancing method improves the MapReduce performance by balancing the completion time of tasks and preventing the occurrence of straggler tasks.

Twister 상에서 수행되는 MapReduce 응용의 행태 모니터링

강윤희 한국정보기술학회 2011 Proceedings of KIIT Conference Vol.2011 No.5

최근 대용량 데이터 처리를 위한 요구가 증가함에 따라 프로그래밍 모델인 MapReduce가 관련 응용 개발에 대한 활용되고 있다. 이 논문은 MapReduce 응용의 수행 행태를 모니터링 하기 위해 MapReduce 미들웨어인 Twister의 확장을 기술한다. 이를 위해 Twister 미들웨어 및 응용 내에서 발생하는 사건을 Pub/Sub 기반 메시징으로 수신함으로서 응용의 행태를 모니터링 하도록 Twister 의 확장 서비스로 구성한다. 추가적으로 응용의 Twister 드라이버의 사건을 수신하기위해 신규 토픽을 정의하였다. Twister 에서 MapReduce 응용의 수행 행태를 모니터링하는 기능은 Pub/Sub 메시징 시스템의 구독자 기반으로 구현하였다. 구독자 기반의 행태 모니터링을 위한 Pub/Sub 메시징 시스템의 서비스 구현은 Twister 미들웨어 코드의 내부 수정 없이 MapReduce 응용의 모니터링을 개발할 수 있는 장점이 있다.

An Application of MapReduce Technique over Peer-to-Peer Network

임건길(Jian-Ji Ren),이재기(Jae-Kee Lee) 한국정보과학회 2009 정보과학회 컴퓨팅의 실제 논문지 Vol.15 No.8

본 논문의 목적은 P2P 네트워크 상에서 동적 환경 애플리케이션을 지원하기 위한 MapReduce의 설계이다. MapReduce는 클라우드컴퓨팅 중에서 대용량 데이터의 병렬처리를 위해서 개발된 소프트웨어 프레임워크이다. P2P 기반 네트워크의 특징은 노드 고장이 언제든지 발생할 수 있으며, 이런 노드 고장을 제어하기 위해 Pastry라는 DHT 라우팅 프로토콜의 사용에 초점을 맞추었다. 본 논문의 결과는 프레임워크가 양호한 계산 효율과 확장성을 유지하는 가운데 P2P 네트워크 시스템의 다양한 애플리케이션에 적용될 수 있음을 보이고 있다. 향후 몇 년 동안은 P2P 네트워크와 병렬 컴퓨팅이 산업과 학계에서 매우 중요한 연구 및 개발 주제로 자리 잡을 것으로 확신한다. The objective of this paper describes the design of MapReduce over Peer-to-Peer network for dynamic environments applications. MapReduce is a software framework used for Cloud Computing which processing large data sets in a highly-parallel way. Based on the Peer-to-Peer network character which node failures will happen anytime, we focus on using a DHT routing protocol which named Pastry to handle the problem of node failures. Our results are very promising and indicate that the framework could have a wide application in P2P network systems while maintaining good computational efficiency and scalability. We believe that, P2P networks and parallel computing emerge as very hot research and development topics in industry and academia for many years to come.

MapReduce 환경에서 재그룹핑을 이용한 Locality Sensitive Hashing 기반의 K-Nearest Neighbor 그래프 생성 알고리즘의 개선

이인회(Inhoe Lee),오혜성(Hyesung Oh),김형주(Hyoung-Joo Kim) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.11

k-Nearest Neighbor(k-NN)그래프는 모든 노드에 대한 k-NN 정보를 나타내는 데이터 구조로써, 협업 필터링, 유사도 탐색과 여러 정보검색 및 추천 시스템에서 k-NN그래프를 활용하고 있다. 이러한 장점에도 불구하고 brute-force방법의 k-NN그래프 생성 방법은 O(n²)의 시간복잡도를 갖기 때문에 빅데이터 셋에 대해서는 처리가 곤란하다. 따라서, 고차원, 희소 데이터에 효율적인 Locality Sensitive Hashing 기법을 (key, value)기반의 분산환경인 MapReduce환경에서 사용하여 k-NN그래프를 생성하는 알고리즘이 연구되고 있다. Locality Sensitive Hashing 기법을 사용하여 사용자를 이웃후보 그룹으로 만들고 후보내의 쌍에 대해서만 brute-force하게 유사도를 계산하는 two-stage 방법을 MapReduce환경에서 사용하였다. 특히, 그래프 생성과정 중 유사도 계산하는 부분이 가장 많은 시간이 소요되므로 후보 그룹을 어떻게 만드는 것인지가 중요하다. 기존의 방법은 사이즈가 큰 후보그룹을 방지하는데 한계점이 있다. 본 논문에서는 효율적인 k-NN 그래프 생성을 위하여 사이즈가 큰 후보그룹을 재구성하는 알고리즘을 제시하였다. 실험을 통해 본 논문에서 제안한 알고리즘이 그래프의 정확성, Scan Rate측면에서 좋은 성능을 보임을 확인하였다. The k nearest neighbor (k-NN) graph construction is an important operation with many web-related applications, including collaborative filtering, similarity search, and many others in data mining and machine learning. Despite its many elegant properties, the brute force k-NN graph construction method has a computational complexity of O(n²), which is prohibitive for large scale data sets. Thus, (Key, Value)-based distributed framework, MapReduce, is gaining increasingly widespread use in Locality Sensitive Hashing which is efficient for high-dimension and sparse data. Based on the two-stage strategy, we engage the locality sensitive hashing technique to divide users into small subsets, and then calculate similarity between pairs in the small subsets using a brute force method on MapReduce. Specifically, generating a candidate group stage is important since brute-force calculation is performed in the following step. However, existing methods do not prevent large candidate groups. In this paper, we proposed an efficient algorithm for approximate k-NN graph construction by regrouping candidate groups. Experimental results show that our approach is more effective than existing methods in terms of graph accuracy and scan rate.

MapReduce 작업처리시간 단축을 위한 선 정렬 기반 태스크 스케줄링 기법

박정효(Jung Hyo Park),김준상(Jun Sang Kim),김창현(Chang Hyeon Kim),이원주(Won Joo Lee),전창호(Chang Ho Jeon) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.11

본 논문에서는 MapReduce 작업처리시간을 줄일 수 있는 선 정렬 기반 태스크 스케줄링 기법을 제안한다. 태스크와 그 태스크가 처리할 데이터가 동일 노드에 존재하지 않으면 해당 태스크는 다른 노드로부터 데이터를 전송받아 처리한다. 이때 전송시간으로 인해 MapReduce의 작업처리시간이 증가하는 문제점이 발생한다. 이러한 문제점을 해결하기 위해 본 논문에서는 두 단계로 태스크를 스케줄링한다. 첫 번째 단계에서는 데이터 지역성이 높은 순으로 태스크를 노드 리스트에 정렬한다. 두 번째 단계에서는 데이터의 위치정보를 이용하여 태스크들이 데이터 지역성을 높일 수 있도록 교환하여 스케줄링한다. 본 논문에서는 제안한 스케줄링 기법의 성능평가를 위해 소규모 Hadoop 클러스터를 구현하여 실험하였다. 제안한 기법을 적용하였을 때 작업처리시간이 약 18% 감소하였으며 데이터가 저장된 노드에 할당되지 않은 태스크 수는 약 25% 감소하였다. In this paper, we propose pre-arrangement based task scheduling scheme to reduce MapReduce job processing time. If a task and data to be processed do not locate in same node, the data should be transmitted to node where the task is allocated on. In that case, a job processing time increases owing to data transmission time. To avoid that case, we schedule tasks into two steps. In the first step, tasks are sorted in the order of high data locality. In the second step, tasks are exchanged to improve their data localities based on a location information of data. In performance evaluation, we compare the proposed method based Hadoop with a default Hadoop on a small Hadoop cluster in term of the job processing time and the number of tasks sorted to node without data to be processed by them. The result shows that the proposed method lowers job processing time by around 18%. Also, we confirm that the number of tasks allocated to node without data to be processed by them decreases by around 25%.

MapReduce 시스템을 위한 에너지 관리 알고리즘의 성능평가

김민기,조행래 대한임베디드공학회 2014 대한임베디드공학회논문지 Vol.9 No.2

Analyzing large scale data has become an important activity for many organizations. Since MapReduce is a promising tool for processing the massive data sets, there are increasing studies to evaluate the performance of various algorithms related to MapReduce. In this paper, we first develop a simulation framework that includes MapReduce workload model, data center model, and the model of data access pattern. Then we propose two algorithms that can reduce the energy consumption of MapReduce systems. Using the simulation framework, we evaluate the performance of the proposed algorithms under different application characteristics and configurations of data centers.

Invariant 데이터를 이용한 순환처리를 지원하는MapReduce 기반 분산 데이터 처리 시스템

윤민,장재우,김형일,홍승태,최문철,조희승,최동훈 한국정보과학회 2013 데이타베이스 연구 Vol.29 No.3

Recently, interest in cloud computing which provides IT resources as service form in IT field is increasing. As a result, much research has been done on the distributed data processing that store and manage a large amount of data in many servers. However, the existing systems, such as Hadoop and HaLoop, have problems that do not provide iterative processing efficiently. Threfore,in this paper, we propose a new iterative processing system based on MapReduce. Our proposed system supoort automatic invariant data detection scheme for the layman who does not know MapReduce system. And in-memory caching algorithm in our system can improve the performance for iterative processing. Finally, we show from performance analysis that the proposed scheme greatly improve the performance of iterative processing than the existing systems. 최근 IT 분야에서 인터넷을 기반으로 IT 자원들을 서비스 형태로 제공하는 클라우드 컴퓨팅에 대한 관심이 증대되고 있으며, 이에 따라 대규모 데이터를 수많은 서버들에 분산 저장하고 관리하기 위한 분산 데이터 처리 기법에대한 연구가 활발히 진행되고 있다. 하지만, Hadoop 및 HaLoop 과 같은 기존 연구들은 반복적인 수행을 위한순환 처리 작업에 대해 효율적으로 지원하지 못하는 문제점이 존재한다. 이를 위해 본 논문에서는 비전문 개발자를위한 MapReduce 기반 순환 처리 기법을 제안(이하 Hadoop X)한다. 제안하는 기법은 비전문 개발자가 효율적으로순환 처리 응용을 사용할 수 있도록, invariant 데이터의 자동 검출 기능을 수행한다. 또한, 클러스터 환경의 가용메모리를 활용한 In-memory 캐싱을 수행함으로써, 순환 처리 과정에서의 캐싱 성능을 향상시킨다. 마지막으로 다양한 순환 처리 응용을 통한 성능평가를 수행함으로써, 제안하는 시스템이 기존 시스템보다 향상된 성능을 보임을입증한다.