MapReduce의 성능개선을 위한 효율적인 정렬 알고리즘

Abstract

현재 우리는 데이터 폭증시대에 살고 있으며 스마트폰과 같은 디지털 기기의 보급, 소셜네트워크서비스(SNS)의 부상과 모바일 기기의 확산이 결합되면서 급격하게 데이터가 증가 하고 있다.이에 따라 데이터를 분석하고 처리하고자 하는 시도가 활발히 이루어 지게 되었고 이러한 연구는 빅데이터 분석 연구라 불리며 현재 데이터 베이스와 데이터 마이닝 분야에서 가장 활발히 연구되는 주제 이다 특히 대량의 데이터를 분석하고 처리하는 기술과 이를 실생활에 접목하는 기술이 집중적으로 연구 되고 있으며 빅데이터 분석 연구에 가장 널리 사용되는 시스템은 Hadoop 이다. 본 논문은 Hadoop core Project에 해당하는 MapReduce의 정렬 병합 처리시간 단축을 위한 알고리즘 방법을 제안한다. MapReduce잡의 입력 데이터는 논리적인 단위인 입력 split으로 분리 된후 스필릿별로 맵 테스크가 실행 된다. Shard된 데이터를 MapReduce의 단계중 Map함수에서 데이터를 읽어 Reduce함수로 보내는 과정중 Shuffle이 발생하고 Shuffle 단계중 스필과 Reduce 함수 사이에서 데이터의 정렬과 병합이 일어 난다. Shuffle과정중 데이터의 정렬과 병합 과정은 Hadoop의 속도에 가장 영향을 주며 Hadoop에서 제공하는 기본 정렬기법은 작업처리시간이 증가하는 문제점이 발생 하였다. 이러한 문제를 해결하기 위해 본 눈문에서는 정렬알고리즘중 MapReduce에 가장 적합한 정렬알고리즘을 선택 후 제안하는 알고리즘과 함께 적용하여 실험하였다. ASA(American Standard Association:미국 규격협회)에서 제공하는 데이터중 16만건을 기준으로 실험 하였고 shuffle에서 정렬알고리즘의 퀵정렬을 사용하였을 때 Hadoop에서 제공하는 기본 정렬기법에 비해 약 30%이상 감소 하였다. 제안 알고리즘과 퀵정렬을 적용 했을 때 Hadoop에서 제공하는 기본 정렬기법에 비해 약 40%이상 감소 하였다.