Journal of the Korea Institute of Information and Communication Engineering 하둡성능향상을위한 VPT 개발연구 양일등 1 김성열 2* A Development Study of The VPT for the improvement of Hadoop performance Ill Deung, Yang 1 Seong Ryeol, Kim 2* 1 Department of Computer & Information Engineering, Cheongju University, Cheongju-si 298, Korea 2* Department of Computer & Information Engineering, Cheongju University, Cheongju-si 298, Korea 요약 하둡 MR(MapReduce) 는매퍼 (Mapper) 의출력을리듀서 (Reducer) 의입력으로전달하기위해파티션함수 (Partition Function) 을사용한다. 파티션함수는키에서해쉬값을계산한후리듀서개수로나머지연산을수행하여대상리듀서를결정한다. 기존파티션함수는키의편중도에민감하여잡이균등하게배분될수없었다. 잡이균등하게배분되지못하면특정리듀서들의처리수행시간이길어져전체분산처리수행성능에영향을주게된다. 이에본논문은 VPT(Virtual Partition Table) 을제안하고편중도가심한데이터에 VPT 을적용하여실험을수행하였다. 적용된 VPT 는기존파티션함수와대비하여평균 3 초정도성능향상이발생하였으며, 데이터처리량이증가할수록성능향상폭이증가할것으로예상된다. ABSTRACT Hadoop MR(MapReduce) uses a partition function for passing the outputs of mappers to reducers. The partition function determines target reducers after calculating the hash-value from the key and performing mod-operation by reducer number. The legacy partition function doesn't divide the job effectively because it is so sensitive to key distribution. If the job isn't divided effectively then it can effect the total processing time of the job because some reducers need more time to process. This paper proposes the VPT(Virtual Partition Table) and has tested appling the VPT with a preponderance of data. The applied VPT improved three seconds on average and we figure it will improve more when data is increased.. 키워드 : 하둡, 맵리듀스, 파티션함수 Key word : Hadoop, MapReduce, Partition Function Received 02 July 2015, Revised 27 July 2015, Accepted 11 August 2015 * Corresponding Author Seong Ryeol, Kim(E-mail:srkim@cju.ac.kr, Tel:+82-43-229-8490) Department of Computer & Information Engineering, Cheongju University, Cheongju-si 298, Korea Open Access http://dx.doi.org/10.6109/jkiice.2015.19.9.2029 print ISSN: 2234-4772 online ISSN: 2288-4165 This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. Copyright C The Korea Institute of Information and Communication Engineering.
Ⅰ. 서론 2004년구글에서구글MR(MapReduce)[1] 를발표한이후빅데이터관련솔루션들이주목받기시작했다. 구글 MR는 LISP의 Functional Programming[2] 개념을분산처리에적용한것으로이후많은솔루션들이개발되었다. 이중자바기반의오픈소스인하둡MR[3] 이구현되었으며현재페이스북 [4] 야후등에서 3,000노드이상운영되는대형클러스터에사용되고있다. 하둡MR은오픈소스구조로분산처리가필요한사용자들에게많은관심을받고있으며동작과정이해도용이하다. 하둡MR은데이터가저장되어있는노드에서매퍼 (Mapper) 가데이터를처리하면자동으로리듀서 (Reducer) 로전달되어집계 (Aggregate) 처리를수행한다. 이처럼하둡MR은사용자가매퍼와리듀서만제공하면나머지분산처리에관한모든것을자동으로처리한다. 이러한동작과정에는파티션 (Partition) 과정이포함된다. 파티션과정은매퍼의출력을리듀서에게전달하기위해대상리듀서를결정하는것이다. 분산처리성능은사용자의작업시작요청부터결과확인까지모든시간이포함된다. 따라서좋은처리성능을얻기위해서는리듀서들에게균등한작업배분을해야하며, 특정리듀서에게많은작업이할당되면전체작업완료시간에영향을주게된다. 본논문은하둡MR 성능향상을위해 VPT(Virtual Partition Table) 을제안하고이를적용하여처리성능이향상됨을보인다. Ⅱ. 관련연구 2.1. 하둡MR 하둡MR[3] 는구글MR를기반으로자바기반오픈소스로구현되었다. 대용량데이터가분산저장된병렬클러스터환경에서효과적으로데이터를처리할수있다. 하둡MR는구글MR과용어와개념이매우유사하며구글MR과동일하게마스터 / 슬레이브구조를가진다. 마스터는태스크를할당하고제어하는잡트래커 (Jobtracker) 이며실제태스크를수행하는슬레이브는태스크트래커 (Tasktracker) 이다. 태스크트래커가수행하는태스크는맵태스크와리듀스태스크로구분된다. 파일은 Split 블록으로나누어져 GFS(Google File System)[5] 와유사한 HDFS(Hadoop Distributed File System)[6] 에저장된다. 저장된데이터는맵태스크에의해처리된다. 맵태스크가출력한중간데이타는리듀스태스크의입력이되어미리정의된규칙에따라원하는데이터를필터링하고최종결과는 HDFS에저장된다. 그림 1은하둡MR의동작과정을나타낸다. 그림 1. 하둡 MR 동작과정 [3] Fig. 1 Processing steps of Hadoop MR[3] 2030
하둡성능향상을위한 VPT 개발연구 사용자는 MR프로그램을 JobClient에제출하고 Job Client는공유파일시스템에 Job을저장한다. 저장된잡 (Job) 은잡트래커에의해관리되며각노드에설치된태스크트래커에의해처리된다. 처리된결과는 HDFS에저장되고사용자는최종결과를확인한다. 2.2. MR Partition Function 맵퍼의출력을리듀스의입력으로전달하기위해하둡MR은파티션함수를사용한다. 파티션함수가실행되는곳은그림 2에서 partition 부분이다. 파티션함수는매퍼가출력한데이터를처리할리듀서를결정하기위해매퍼에게입력되는키값에서해쉬값을계산하여그값을전체리듀서개수로나머지연산한다. 따라서입력된키값의분포가매우중요하며키값의분포가한쪽으로편중될경우특정리듀서에게더많은작업이할당된다 [7, 8]. 하둡파티션함수 [1, 3] 에사용되는수식은다음수식 1과같다. P = hash(key) mod R (1) P : The Result of Partition Function key : The Output of a Mapper R : The Number of Reducers key는매퍼에게입력되는키, R은리듀서개수, P는결과값이다. 수식 1은주어진키를해쉬함수의입력으로하고그출력을 R로나머지연산한후결과 P를리턴한다. P는대상리듀서의번호가된다. R 값은 [3] 하둡설정파일에설정된다. 따라서기존파티션함수는키값에따라특정리듀서에게많은작업이편중되어할당될수있다. Ⅲ. VPT(Virtual Partition Table) 제안 3.1. VPT 제안하둡MR 파티션함수는수식 1을사용하여대상리듀서를결정한다. 즉 R값이작을수록특정 P값이집중될확률이높아지며 P값을평균적으로분포시키기위해서는 R값을크게증가시켜야한다. 하지만 R값을크게증가시키면리듀서가출력하는결과파일의개수가증가하여후처리작업이필요하다. 따라서실제 R값을유지하면서 P값을평균적으로분포시키는방법이필요하다. 이에본논문은 VPT을제안하며, 제안하는 VPT는가상 R을사용하여특정리듀서에대한집중도를낮게한다. 그림 2. 하둡내부동작구조 [3] Fig. 2 Internal processing pathways of Hadoop[3] 2031
VPT는실제파티션테이블의데이터가저장된가상파티션테이블을사전구축하고매퍼가 VPT 파티션함수를사용하여파티션을수행한다. 이를통해 R값을증가시키지않고대상리듀서를결정할수있다. VPT의장점은다음과같다. 3.1.1. 사전구축을통한런타임시간감소 VPT 데이터구축은하둡MR에잡을제출전에수행된다. 사전구축된 VPT 데이터는자바컴파일러로컴파일되어 JAR 파일에포함된후압축되어하둡MR에잡으로제출된다. 이후동일잡을실행할때 VPT 데이터를재구축할필요없이기존 JAR 파일을이용하여잡을처리한다. 이것은런타임시에제출된잡의개별매퍼들이각각 VPT 데이터를생성하지않고사전구축된데이터를지속적으로사용할수있는장점을제공한다. 대용량데이터의특성은동일패턴의데이터가반복적으로발생되어패턴을분석한이후에는분석된패턴을지속적으로사용할수있다. 따라서 VPT 데이터를사전구축하여동일한패턴의대용량데이터에지속적으로적용할수있다. 또한 VPT 데이터구축에전체샘플데이터를사용하지않고시스템에설정된 Split 크기만큼사용하기때문에 VPT 데이터생성시간도크기않다. 키의분할여부에따라약간의차이는발생하지만하둡기본 Split 크기인 64M 데이터를처리하는시간은약 7초이하이다. 3.1.2. VPT 데이터직접참조 VPT는데이터를자바클래스형태로 JAR파일에포함하여배포한다. 따라서각매퍼는 JAR 파일에포함된 VPT 데이터를자바소스상에서직접참조될수있는장점을제공하며추가적인네트워크요구가발생하지않는다. 3.2. VPT 동작설명 VPT는전처리단계와 VPT 데이터를참조하는 VPT 파티션함수사용단계로나뉜다. 전처리단계는 JAR파일을하둡MR에배포하기전일회수행되며데이터유형이변경되지않으면재구축필요는없다. 파티션함수사용단계는각매퍼에서 VPT 데이터를참조하여 R 을결정하며, 각단계는다음과같다. 3.2.1. 전처리단계첫번째는전처리단계로샘플데이터를로드하여 VPT 데이터를생성한후자바파일에배열형태로저장한다. 그림 3은전처리단계를나타낸그림으로전체적인흐름은 HDFS에서샘플데이터를패치한후기존파티션함수를사용하여 VPT 데이터를생성한다. 생성된 VPT 데이터는자바파일로저장된다. 파티션된데이터저장크기는 VPT 데이터저장크기와같아야한다. 그림 3. VPT 전처리단계 Fig. 3 VPT preprocessing parse VPT 데이터는자바소스에서직접참조를위해 static으로선언되어야하며자바컴파일러가컴파일할수있는최대 static 배열크기는약 1만개이다. 따라서샘플과 VPT 크기는 1만개로설정한다. 이렇게설정된데이터는각키에대한 HIT개수가누적되어저장된다. 이후실제리듀서개수로생성된파티션테이블에데이터값을누적시키며가장적은데이터값을갖는파티션테이블의인덱스를 VPT에저장한다. 이것은데이터전체크기만큼수행된다. 저장된 VPT는실제리듀서의인덱스가저장되고이후 VPT 파티션함수를통해리듀서를결정하게된다. 다음은 VPT를생성하는생성코드의일부이다. int pt[ ] = new int[pt_cnt]; int sample[ ] = new int[vpt_size]; int VPT[ ] = new int[vpt_size]; for( int i = 0 ; i < sample.length ; i++ ) { sample[i] = 1; 2032
하둡성능향상을위한 VPT 개발연구 for( int i = 0 ; i < sample.length ; i++ ) { sample[key[i].hashcode()%sample.length]++; for( int i = 0 ; i < node_cnt ; i++ ) { pt[i] = 0; int pt_idx = 0; for( int i = 0 ; i < sample.length ; i++ ) { for( int j = 0 ; j < pt.length ; j++ ) { if( pt[j] < pt[pt_idx]) pt_idx = j; pt[pt_idx] = pt[pt_idx] + sample[i]; VPT[i] = pt_idx; pt_cnt :The number of real reducers VPT_SIZE :The size of VPT array key : The array of sample data 여기서 pt 배열변수는 R의누적카운트를저장하는배열, sample 배열변수는기본파티션함수의결과데이터에대한누적카운트를저장하는배열, 그리고 VPT 변수는최종결과가저장되는배열이다. VPT 배열의값들은자바 static 배열로변환되어자바파일에최종저장된다. VPT 알고리즘순서는 sample배열을 1로초기화시키고기존파티션함수를실행시켜각값에대한누적값을저장한다. 이때기존파티션함수의 R은 sample 배열의크기이다. 키데이터를저장하는 key배열에서각데이터에대해파티션함수를수행하고개별키에대한 HIT수를 sample 배열에누적시킨다. 누적된 sample 배열정보를 pt 배열에누적시키며가장작은값을가지는 pt의인덱스를 VPT 배열에최종저장한다. 마지막으로 VPT 배열값을기준으로자바 staitc 배열소스를생성하고자바컴파일러로컴파일한후 JAR형태로압축한다. 이후 JAR 파일은하둡MR에잡으로배포된다. 배포된잡은 VPT 파티션함수에서 VPT 데이터를이용하여해당리듀서를결정한다. 다음은최종저장된 VPT 데이터를나타내며, 리듀서개수가 6개인경우데이터는 0부터 5 까지해당리듀서인덱스값을저장되며, VPT 파티션함수에직접참조된다. public class a { public static int[ ] VPT = { 0,... 4, 5, ; 3.2.2. VPT 파티션함수사용단계 VPT 데이타를기준으로리듀서를결정하는수식은다음의수식 2와같다. VP = VPT[hash(key) mod R] (2) VP : The Result of VPT Partition Function VPT : Virtual Partition Table key : The Output of a Mapper R : The length of VPT VPT는대상리듀서인덱스가저장된매핑테이블, key는매퍼에서사용되는키, R은 VPT의크기이다. 전처리작업으로생성된 VPT staitc 배열에서키값을 R로나머지연산하여 VP를구한다. VP는대상리듀서인덱스번호이다. 다음은 VPT를이용한파티션함수자바코드로하둡MR은사용자가정의한파티션함수를잡안에서설정할수있다. 하둡MR Boot코드에 VPT 데이터를참조하는 VPT 파티션함수를적용시킨다. VPT를적용한신규파티션함수는키에대한 hash 연산후 VPT static 배열크기로나머지연산을수행하고그인덱스에저장된실제리듀스인덱스를반환하다. 따라서 VPT 파티션함수는추가적인연산리소스를발생시키지않는다. public int getpartition(text key, IntWritable value, int numpartitions) { return a.vpt[key.hashcode( ) % a.vpt.length]; 2033
Ⅳ. 실험및평가 4.1. 실험환경아파치하둡사이트 [9] 에서제공하는자료를바탕으로하둡을설치하여운영중인사이트들을살펴보면노드의수가많게는 1,000개이상부터작게는 5개까지다양한크기의하둡클러스터가운영되는것을알수있다. 이는다수노드를운영하는대형클러스터및소수노드를운영하는클러스터에서도하둡이활발히사용되고있음을나타낸다. 따라서실제운영환경에서최소운영단위인 5대의서버급장비에하둡을설치하여클러스터구성하였다. 각장비의하드웨어및소프트웨어구성은표 1과같다. 표 1. 실험환경 Table. 1 Test environment OS Ubuntu 12.04 CPU Intel Core i3-3200 3.30Ghz MEMORY 4G HDD 500G SATA HDD NETWORK 1G Fast Ethernet 총 5대의장비중 4대는 DataNode와 TaskTracker를실행에사용하고, 1대에서는 NameNode와 JobClient 실행에사용하였다. HDFS의 Replication 개수는 3으로지정하였고, Block Size는 64M로설정하였다. 높은유사도데이터와일반텍스트파일데이터를각각 10G씩 HDFS에저장한후하둡 MR 패키지에포함되어있는워드카운트 (WordCount) 프로그램을사용하여실험을수행하였다. 워드카운트프로그램은하둡배포판패키지에기본포함된프로그램이다. 4.2. 실험데이터높은유사도데이터는동일키에대한 R값의편중이발생하도록생성된데이터이며 love, flyn, loves, fyny1, love1 등이다. 높은유사도데이터를생성하여실험한이유는유사도가낮은데이터의경우기존파티션함수를사용해도리듀서의분포가한쪽으로편중되지않기때문에일반파티션함수와 VPT를적용한 VPT 파티션함수와의차이를구분하기어렵다. 이러한높은유사도데이터생성코드는그림 4와같다. int rn = get_random_number(7) string word = abcdefg!@#$1234... string seed_words = {"love", "like", "road", "would", "dis", "icon", "fly" string key = seed_words[rn] rn = get_random_number(10) rn = 10 - rn.length for i=0 to rn int word_rn = get_random_number() % word.length key = key + word[word_rn]; end return key 그림 4. 샘플데이타생성코드 Fig. 4 Code of sample data generation 여기서 seed_words 배열에 prefix 단어를임의선택한후 word배열에서 postfix 글자를추가하여높은유사도데이터를생성한다. 일반텍스트 [10] 파일은구글검색에서텍스트교재를랜덤검색했으며텍스트교재의특성상높은유사도데이터와유사하게 R값이편중되어있다. 4.3. 실험평가워드카운트프로그램에 VPT를적용하지않은 (Non- VPT) 파티션함수와 VPT를적용한파티션함수를설정하고각각실험하였다. 실험은각리듀서개수당 10 회씩행하여평균을구하였다. 다음의그림 5는높은유사도데이터에대한실험결과이고그림 6는일반텍스트파일에대한실험결과이다. 각그래프의 Y축은잡제출부터완료까지총수행시간을초단위로나타내며 X축은리듀서개수이다. 각리듀서구간별수행시간을합하여평균을산출하였으며, 높은유사도데이터의경우 Non-VPT 대비 VPT가평균 2초정도실행시간을단축되었고, 일반텍스트데이터의경우평균 5초정도실행시간이단축되었다. 그러나그림 5와그림 6의실험결과처럼데이터의성격에따라 VPT의성능이동일하지않으며리듀서의개수에따라성능차이가발생하였다. 또한하드웨어증설없이리듀서만추가하면성능향상은발생되지않 2034
하둡성능향상을위한 VPT 개발연구 그림 5. 높은유사도데이터실험결과 Fig. 5 The result of testing of high similarity data 그림 6. 일반텍스트실험결과 Fig. 6 The result of testing of plan text 았다. 그리고 VPT적용 MR이 Non-VPT적용 MR에비해모든구간에서상대적으로성능이매우우수하지못한데이유는데이터분포에따른리듀서재배정에서데이터편중이발생했기때문이다. 따라서하드웨어환경을고려하여최대의성능을이끌어내는리듀서개수튜닝이필요하다는것을확인할수있다. Ⅴ. 결론및향후연구과제하둡 MR는매퍼의출력을리듀서의입력으로전달하기위해파티션함수을사용한다. 파티션함수는키에서해쉬값을계산한후리듀서개수로나머지연산을수행하여대상리듀서를결정한다. 기존파티션함수는키의편중도에민감하여잡이균등하게배분될수없었다. 잡이균등하게배분되지못하면특정리듀서들의처리수행시간이길어져전체분산처리수행성능에영향을주게된다. 본논문에서는 VPT을제안하고 2035
편중도가심한데이터들에 VPT을적용하여실험을수행하였다. 적용된 VPT는기존파티션함수와대비하여평균 3초정도성능향상이발생하였으며, 데이터처리량이증가할수록성능향상폭이증가됨을확인할수있었다. 또한 VPT를적용해도하드웨어의물리적인증설없이논리적인리듀서만증가시키는것만으로는성능향상이발생되지않음을확인할수있어향후연구는최적의리듀서개수를동적으로계산하여자동처리가능한 EVPT (Extended Virtual Partition Table) 연구를수행할계획이다. ACKNOWLEDGMENTS This work was supported by the Research grant of Cheongju University in 2014-2015. REFERENCES [ 1 ] Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004, pp 137-150. [ 2 ] David S. Touretzky, "COMMON LISP: A Gentle Introduction to Symbolic Computation", The Benjamin/Cummings Publishing Company, 1990. [3] Tom White, Hadoop : The Definitive Guide", OREILLY, 2011. [ 4 ] Dhruba Borthakur and the eight members, Apache Hadoop Goes Realtime at Facebook, SIGMOD 11, June 12-16, 2011. [ 5 ] Sanjay Ghemawat and the two members, "The Google File System", Google, 2003. [ 6 ] Konstantin Shvachko and the three members, "The Hadoop Distributed File System", IEEE, 2010. [ 7 ] Nandhini.C, Premadevi.P, A Micro Partitioning Technique in MapReduce for Massive Data Analysis, International Journal of Innovative Research in Computer and Communication Engineering Vol. 2, Issue 3, March 2014. [ 8 ] Kenn Slagter and three members, "An improved partitioning mechanism for optimizing massive data analysis using MapReduce", Springer Science Business Media New York 2013, J Supercomput (2013) 66:539-555. [ 9 ] http://wiki.apache.org/hadoop/poweredby [10] http://www.gutenberg.org/ebooks/18525?msg=welcome _stranger 양일등 (Ill Deung, Yang) 2002 청주대학교컴퓨터정보공학과공학사 2004 청주대학교컴퓨터정보공학과공학석사 2010 청주대학교컴퓨터정보공학과박사과정 2014 ~ 현재 ( 주 ) 인터페이스정보기술부설연구소책임연구원 관심분야 : 웹시스템설계, 소프트웨어공학, 분산처리 김성열 (Seong Ryeol, Kim) 1982 년숭실대학교전자계산학과공학사 1987 년숭실대학교대학원전자계산학과공학석사 1992 년숭실대학교대학원전자계산학과공학박사 1982 년 ~ 1984 년한국전력공사전자계산소근무 1984 년 ~ 1990 년오산대학전자계산과교수 1997 년 ~ 1998 년호주 QUT ISRC 객원교수 1990 년 ~ 현재청주대학교컴퓨터정보공학과교수 관심분야 : 웹시스템설계, 컴퓨터보안, 소프트웨어공학 2036