하둡 맵리듀스 성능 향상을 위한 데이터 프리패칭과 스트리밍

이정준(Jung June Lee),김경태(Kyung Tae Kim),윤희용(Hee Yong Youn) 한국컴퓨터정보학회 2015 한국컴퓨터정보학회 학술발표논문집 Vol.23 No.1

최근 소셜 네트워크, 바이오 컴퓨팅, 사물 인터넷 등의 출현으로 인해 기존의 IT환경보다 많은 데이터가 생성되고 있고, 이로 인해 효율적인 대용량 데이터 처리기법에 대한 연구가 진행 되고 있다. 맵리듀스는 데이터 집약적인 연산 어플리케이션에 효과적인 프로그래밍 모델로써, 대표적인 맵리듀스 어플리케이션으로는 아파치 소프트웨어 재단에서 개발 지원중인 하둡 이 있다. 본 논문은 하둡 맵리듀스의 성능 향상을 위해 데이터 프리패칭 기법과 스트리밍 기법을 제안한다. 하둡 맵리듀스의 성능 이슈중 하나는 맵리듀스 과정에서 입력 데이터 전송에 의한 작업 지연이다. 이러한 데이터 전송 시간을 최소화하기 위해, 기존 맵리듀스와는 달리 데이터 전송을 담당하는 프리패칭 스레드를 별도로 생성하였다. 그 결과 데이터의 맵리듀스 작업 중에도 데이터전송이 가능하게 되어 전체 데이터 처리 시간을 줄일 수 있었다. 이러한 프리패칭 기법을 사용해도 하둡 맵리듀스의 특성상 최초 데이터 전송 시에는 작업대기를 하게 되는데, 이 대기시간을 줄이고자 스트리밍 기법을 사용하여 데이터 전송에 의한 대기시간을 추가로 줄일 수 있었다. 제안하는 기법의 성능을 측정하기 위해 수학적인 모델링을 하였으며, 성능 측정결과 기존의 하둡맵리듀스 및 프리패칭 기법만 적용된 맵리듀스 보다 스트리밍 기법이 추가 적용된 맵리듀스의 성능이 향상되었음을 확인 할 수 있었다.

맵리듀스에서 중복기반 조인과 비상충 조인을 이용한 효율적인 SPARQL 질의 처리

김태경,김기성,김형주 한국정보과학회 2012 정보과학회논문지 : 데이타베이스 Vol.39 No.4

최근, 분산 병렬 프레임워크인 맵리듀스를 이용한 SPARQL 질의 처리에 대한 연구가 진행되고 있다. 맵리듀스를 이용해 SPARQL 질의 처리를 하기 위해서는 여러 맵리듀스 잡이 필요하며, 이로 인해 많은 비용이 들게 된다. 최근의 연구들은 대부분 이 맵리듀스 잡의 개수를 줄이는데 초점을 맞추고 있다. 본 논문은 SPARQL 질의 처리시에 맵리듀스 잡의 개수를 줄이기 위한 두 가지 서로 다른 기법을 혼용 할 것을 제안한다. 우리가 적용한 기법은 서로 관련이 없는 조인 키들을 동시에 하나의 맵리듀스 잡에서 수행하는 비상충 조인과 중복을 이용해서 여러 개의 조인 키를 한번에 조인하는 멀티웨이 조인 기법이다. 이 두 가지 기법을 혼용함으로써, 기존에 제안된 기법보다 적은 수의 맵리듀스 잡을 이용해 질의를 처리 할 수 있다. 또한, 이로 인해 발생하는 트리플 패턴 그룹화 문제에 대한 그리디 알고리즘을 제안한다. 우리는 대용량 RDF 데이터를 이용한 실험을 통해 제안하는 알고리즘이 기존 연구보다 맵리듀스 잡의 개수를 줄일 수 있으며, 질의 처리 성능을 향상시킴을 보인다. Recently, there has been a lot of research about SPARQL query processing using MapReduce, a parallel distributed framework. To process a SPARQL query on MapReduce, in general, several MapReduce jobs are required, and these jobs cause additional costs. Therefore, most research has been focused on reducing the number of MapReduce jobs. In this paper, we propose to hybridize two different techniques to reduce the number of MapReduce jobs for processing SPARQL queries. The techniques we hybridize are the non-conflicting join and the duplication-based multi-way joins. The non-conflicting join can process independent joins in one MapReduce job, and the multi-way joins can join many join keys at once by duplicating data. Also, we present a greedy algorithm to solve the triple pattern grouping problem which occurs when hybridizing two techniques. We demonstrate that our framework can reduce MapRedcue jobs, and performs better than the previous approaches, through experiments on the large RDF data.

빅 데이터를 위한 맵리듀스 프레임워크 기반의 효율적인 쿼드 트리 생성 기법

노현호(Hyun-Ho Noh),민준기(Jun-Ki Min) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.3

소셜 네트워크, 센서 네트워크 등의 다양한 기술의 발전으로 처리하는 데이터의 양은 매우 빠르게 급증하고 있으며 따라서 이러한 대용량 데이터를 복수 개의 컴퓨터들로 구성된 군집(cluster)을 활용해 처리하고자 맵리듀스 프레임워크가 구글에서 제안되었다. 그러나 기존의 데이터 처리 기법들은 맵리듀스 프레임워크에 바로 적용할 수 없으므로 다양한 분야에서 맵리듀스 프레임워크에 적합한 새로운 알고리즘이 개발되고 있다. 본 논문에서는 대용량 데이터에 대한 효율적인 접근을 지원하기 위한 색인 구조의 하나인 쿼드 트리를 맵리듀스 프레임워크를 활용하여 구축하고자 한다. 본 제안 기법은 샘플링 기법을 이용하여 데이터를 균등하게 분할함으로써 구축시간을 단축시킨다. 또한 생성된 쿼드 트리와 맵리듀스를 함께 활용하면 맵리듀스 프레임워크만을 사용하는 것 보다 효율적으로 데이터들을 접근할 수 있음을 실험을 통하여 보였다. Currently, due to advances of various technologies such as social networks and sensor networks, the size of data has extremely increased, and hence, Google proposed a MapReduce framework which is working on a cluster consisting of connected commodity computers to process big data efficiently. However, since the conventional data processing techniques cannot be directly applied to MapReduce frameworks, many algorithms have been re-developed on MapReduce frameworks. In this paper, we construct a quad-tree index with MapReduce frameworks to support efficient access to big data. Our technique reduces the index construction time utilizing a sampling technique to partition a data set evenly. Additionally, in our experiment, we show the efficiency of data access using our constructed quad tree and MapReduce frameworks together compared to data accessing using MapReduce frame works only.

맵리듀스 환경에서 웨이블릿 시놉시스 생성 알고리즘

김철연(Chulyun Kim) 한국정보과학회 2012 정보과학회논문지 : 데이타베이스 Vol.39 No.6

웨이블릿은 데이터베이스 시스템의 질의최적화, 개략 질의처리와 멀티미디어 데이터에 대한 특징 추출 등에 사용되어 온 대표적인 정보 개략화 알고리즘으로 원본 데이터의 정보 손실을 최소화하는 최적의 시놉시스를 생성하는 알고리즘이다. 맵리듀스는 분산처리를 위한 플랫폼으로 구글의 데이터 처리를 위한 플랫폼으로 사용되어 최근 다양한 분야에서 각광을 받고 있다. 맵리듀스 플랫폼은 분산 파일시스템에 저장되어 있는 데이터들을 맵과 리듀스의 2단계 분산 프로세스로 데이터를 처리하는 구조를 가지고 있으며, 다양한 기존의 알고리즘들이 이러한 맵리듀스 플랫폼 상에서 실행될 수 있도록 재구성되고 있다. 이에 본 논문에서는 분산된 맵리듀스 환경에서의 웨이블릿 시놉시스 생성 알고리즘을 제안한다. 제안하는 알고리즘은 한번의 맵리듀스 절차를 통해 웨이블릿 시놉시스를 분산 환경에서 계산할 수 있으며, 분산환경의 네트워크상의 데이터 교환을 최소화하여 선형의 시간복잡도 내에서 최적의 웨이블릿 시놉시스를 계산한다. The Wavelet synopsis is a representative dimensionality reduction method and has been popularly used in query optimization, approximate query answering, feature selection from multimedia data, etc. The MapReduce is a distributed platform which is well known as Google’s data processing platform. A MapReduce phase consists of consecutive map and reduce steps, and many traditional algorithms are being converted to be executable in the MapReduce platform. In this paper we propose a new algorithm to generate wavelet synopses in the distributed MapReduce framework. In the proposed algorithm, the optimal wavelet synopsis can be generated by a single MapReduce phase, and, by minimizing the amount of data communicated through the network of the distributed MapReduce platform, all computations are processed within a linear time complexity.

빅데이터 처리시간 감소와 저장 효율성이 향상을 위한 맵리듀스 기반 빅데이터 처리 기법 구현

이협건,김영운,김기영 한국융합학회 2018 한국융합학회논문지 Vol.9 No.10

맵리듀스는 하둡의 필수 핵심 기술로 하둡 분산 파일 시스템을 기반으로 빅데이터를 처리하는 가장 보편화되어 사용되고 있다. 그러나 기존 맵리듀스 기반 빅데이터 처리 기법은 하둡 분산 파일 시스템에 정해진 블록의 크기대로 파일 나눠 저장되는 특징으로 인해 인프라 자원의 낭비가 극심하다. 이에 본 논문에서는 효율적인 맵리듀스 기반 빅데이터 처리 기법을 제안한다. 제안하는 기법은 처리할 데이터를 사전에 맵리듀스에서 처리하기 적합한 데이터 형태로 변환 및 압축하여 빅데이터 인프라 환경의 저장 효율성을 증가시킨다. 또한 제안하는 기법은 저장 효율성을 중점으로 구현했을 때 발생할 수 있는 데이터 처리 시간의 지연 문제를 해결한다. MapReduce, the Hadoop's essential core technology, is most commonly used to process big data based on the Hadoop distributed file system. However, the existing MapReduce-based big data processing techniques have a feature of dividing and storing files in blocks predefined in the Hadoop distributed file system, thus wasting huge infrastructure resources. Therefore, in this paper, we propose an efficient MapReduce-based big data processing scheme. The proposed method enhances the storage efficiency of a big data infrastructure environment by converting and compressing the data to be processed into a data format in advance suitable for processing by MapReduce. In addition, the proposed method solves the problem of the data processing time delay arising from when implementing with focus on the storage efficiency.

편집거리 계산을 위한 맵리듀스 알고리즘

김진욱 한국차세대컴퓨팅학회 2015 한국차세대컴퓨팅학회 논문지 Vol.11 No.2

편집거리는 근사문자열매칭의 대표적인 점수척도로, 길이가 m, n인 두 문자열에 대한 편집거리는 동적프로그래밍 을 이용하여 O(mn) 시간에 계산할 수 있다. 편집거리 계산을 위한 다양한 알고리즘이 연구되고 있으며 그 중에는 병렬 알고리즘에 대한 연구도 포함되어 있다. 본 논문에서는 두 문자열에 대한 편집거리를 계산하는 맵리듀스 알고 리즘을 제시한다. O(mn) 시간에 동작하는 Wagner와 Fischer의 알고리즘과 O(mn/t) 시간에 동작하는 4-러 시안 알고리즘을 각각 맵리듀스 알고리즘으로 변환하고 설명한다. 그리고 맵리듀스 알고리즘들에 대한 이론적인 비용 분석과 함께 제안하는 알고리즘들이 순차 알고리즘보다 시간 효율성을 갖기 위한 조건도 제시한다. The edit distance metric is one of the most widely used scoring metric for the approximate string matching. Given two strings with lengths m and n, we can compute the edit distance between them in O(mn) time using dynamic programming technique. There are several algorithms for the edit distance problem and some of them are parallel algorithms. In this paper, we present two MapReduce algorithms for the edit distance problem between two strings. We convert the Wagner and Fischer algorithm and the Four-Russians algorithms to the MapReduce algorithms and explain them. In addition, we explain some theoretical analysis for our algorithms using a cost model for MapReduce.

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

정대영(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.

맵리듀스를 이용한 그리드 기반 k-NN 조인 질의처리 알고리즘

윤들녁,장미영,장재우 한국정보과학회 2014 데이타베이스 연구 Vol.30 No.2

Recently, MapReduce based query processing algorithms have been widely studied to analyze bigdata. K-nearest neighbor(k-NN) join algorithm, which aims to produce the k nearest neighbors ofeach point of a data set S from another data set R, has been considered most important in dataanalysis-based applications. However, the existing k-NN join query processing algorithm suffersfrom high index construction cost which makes them unsuitable for big data processing. Furthermore, to store data partitioning information, the existing algorithm utilizes R-tree which isnot useful in the distributed computing environment. To solve these problems, we propose a newgrid-based k-NN join query processing algorithm. First, to reduce the index construction cost, wedesign a dynamic grid index construction algorithm by considering data distribution. Second, toefficiently perform a k-NN join query in MapReduce, we devise a candidate cell retrieval andpruning method based on data signature. Therefore, our algorithm only retrieves neighboring datafrom the query cell and sends them as an input of MapReduce job. This can greatly reduce thedata transmission and computation overhead. In performance analysis, we prove that our algorithmoutperforms the existing work up to 3 times in terms of query processing time while our algorithmachieves high query result accuracy. 최근 대용량 데이터를 분석하기 위한 맵리듀스 기반 질의처리 알고리즘이 다양하게 연구되고 있다. 특히, k-NN조인 질의처리 알고리즘은 서로 다른 두 개의 데이터베이스 R과 S가 존재할 때, R의 모든 데이터에 대해 가장거리가 가까운 상위 k개의 S데이터를 탐색하는 알고리즘으로써, 데이터 마이닝 및 분석을 기반으로 하는 응용 분야에서 매우 중요하게 활용되고 있다. 그러나, 대표 연구인 보로노이 기반 k-NN 조인 질의처리 알고리즘은 보로노이 인덱스 구축 비용이 매우 크기 때문에, 업데이트가 빈번하게 발생하는 대용량 데이터에 적합하지 못하다. 아울러 보로노이 셀 정보를 저장하기 위해 사용하는 R-트리는 맵리듀스 환경에서의 분산 병렬 처리에 적합하지 않다. 따라서, 본 논문에서는 새로운 그리드 인덱스 기반의 k-NN 조인 질의 처리 알고리즘을 제안한다. 첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 그리드 인덱스 생성 기법을 제안한다. 둘째, 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해, 인접셀 정보를 시그니처로 활용하는 후보영역 탐색및 필터링 알고리즘을 제안한다. 이를 통해, R의 각 데이터가 위치한 그리드 셀의 인접 셀만을 탐색하여 관련 데이터만을 맵리듀스의 입력으로 전송하기 때문에 데이터 입출력 및 연산 시간이 크게 감소하는 장점을 지닌다. 마지막으로 성능 평가를 통해 제안하는 기법이 높은 질의 결과 정확도를 보이는 동시에 질의 처리 시간 측면에서 기존기법에 비해 최대 3배의 높은 질의 처리 성능을 나타낸다.

맵리듀스를 사용한 최대흐름 알고리즘의 구현과 사례 연구

강진아,원중호 한국자료분석학회 2014 Journal of the Korean Data Analysis Society Vol.16 No.6

데이터의 규모가 급속히 증가하고 있는 현 시점에서 이러한 빅 데이터 처리를 위한 분산 컴퓨팅 환경으로 하둡(Hadoop)과 맵리듀스(Mapreduce)가 사실상의 표준으로 떠오르고 있으나, 이 환경에서의 실질적인 데이터 분석을 위한 방법론 개발에 대한 논의는 비교적 적은 편이다. 본 연구는 대표적인 네트워크 데이터 분석 알고리즘인 최대흐름 문제를 맵리듀스 분산 환경에서 처리하는 방법에 대해 소개하고, 맵리듀스를 기반으로 하는 대규모 최대흐름 알고리즘을 파이썬(Python) 언어를 이용하여 구현한 뒤, 하둡 환경에서 수행해보았다. 랜덤 네트워크와 영상 분할 데이터를 이용한 실험을 통해 수행 시간 및 확장성을 측정하였다. 랜덤 네트워크 실험에서는 정점의 수를 1000개부터 100만개까지 사용하였고, 영상 분할 실험에서는 정점의 수를 약 20개부터 크게는 약 17000개까지 사용하여 단일 서버와 분산 서버에서의 수행 시간을 비교하는 실험을 하였다. 이를 통해 맵리듀스 기반 알고리즘의 가능성과 한계에 대해 알아본다. In this ‘big data’ era, in which the sizes of data sets are ever increasing, while Hadoop and the MapReduce framework are emerging as the de-facto standard for big data analysis, it is seldom discussed how to utilize them and develop algorithms for complex data analysis problems. In this paper, we review the maximum flow problem, an important subject in network data analysis and optimization, and a MapReduce-based algorithm for distributedly and efficiently solving a large-scale version of the problem. We implement the algorithm in the Python programming language and conducted experiments on a Hadoop environment. We study the running time and scalability of the implemented algorithm using small-world random networks and image data for segmentation. We test small-world networks with vertex size ranging from 1000 to 1,000,000; and image grid network with vertex size up to 17000 on single-node and multiple-node Hadoop clusters. We discuss our experience with the possibility and the limitation of the tested MapReduce-based distributed algorithm.

맵리듀스 환경에서 블룸 필터를 사용한 적응적 조인 처리

배혜찬(Hye-Chan Bae),이태휘(Taewhi Lee),김형주(Hyoung-Joo Kim) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.4

대용량 데이터의 처리, 분석을 위해 분산 프로그래밍 모델인 맵리듀스가 여러 분야에서 활용되고 있다. 그러나 맵리듀스는 조인 연산을 처리할 때 조인되지 않는 레코드들까지 맵퍼에서 리듀서로 전송하는데, 이는 불필요한 네트워크 비용을 발생시켜 조인 성능을 저하시킨다. 이러한 문제를 개선하기 위해 맵리듀스에서 블룸 필터를 사용하여 리듀서로 전송되는 레코드를 미리 여과하는 조인 방법이 제안되었다. 하지만 블룸 필터에 삽입되는 원소 데이터의 개수가 너무 많아지는 경우, 필터의 이점을 기대할 수 없으며 필터를 사용하기 위한 추가적인 비용으로 인하여 블룸 필터를 사용하지 않고 처리하는 것보다 오히려 성능이 더 저하될 수 있다. 이에 본 논문은 주기적으로 블룸 필터의 효율성을 검사하여 필터의 사용여부를 동적으로 결정하는 적응적 조인 연산 기법을 제안한다. 이를 위해, 우리는 필터에 삽입된 키의 개수를 활용하여 블룸 필터의 양성 오류율을 추정하고, 필터가 비효율적이라고 판단된 경우, 그 시점 이후로는 필터를 사용하지 않고 조인 연산을 처리하도록 한다. 실험을 통하여, 제안한 기법이 기본 맵리듀스 조인과 블룸 필터를 사용한 조인 중 보다 나은 성능을 보이는 연산 방법을 적응적으로 선택함으로써 안정적인 조인 성능을 보장함을 확인한다. MapReduce, a distributed programming model, has been used in many fields to process and analyze large volumes of data. However, MapReduce has a limitation to process join operations in that it transmits all the records, including ones that are not joined, from mappers to reducers. This causes unnecessary network costs and degrades the join performance. To handle this problem, the join technique that filters out the redundant records using Bloom filters was proposed. Nevertheless, if the number of data elements inserted into Bloom filter is too large, the performance of the join processing with Bloom filters can be worse than that without Bloom filters, because of additional costs to use them. This paper proposes an adaptive join processing technique that dynamically determines whether to use Bloom filters by checking the efficiency of them periodically. For this purpose, we estimate the false positive rate of Bloom filters with the numbers of the elements inserted into them. If it is judged that the filters are inefficient, the join operation is processed without them. The experiments show that the proposed technique ensures the stable performance of the join processing by choosing the better technique adaptively between the basic MapReduce join and the join using Bloom filter.