MapReduce has become a dominant framework in big data analysis, and thus there have been significant efforts to implement various data analysis algorithms in MapReduce. Many data analysis algorithms are inherently iterative, repeating the same set of tasks until a convergence. To efficiently support iterative algorithms at scale, a few variants of Hadoop and new platforms have been proposed and actively developed in both academia and industry. Representative systems include HaLoop, iMapReduce, Twister, and Spark. In this dissertation, we analyze the performance of iterative MapReduce systems to obtain lessons and study a new caching mechanism through the lessons.
To better understand the distributed processing of iterative algorithms, we identify and categorize the limitations of MapReduce in handling iterative algorithms, and then, experimentally compare Hadoop and the aforementioned systems using various workloads and metrics. We thoroughly explore the effectiveness of their new caching, communication, and scheduling mechanisms in support of iterative computation. In general, Spark achieved the best performance. Thus, to learn more about Spark, we experimentally investigate the limitations of Spark in handling iterative algorithms. According to our experiment results, the network I/O overhead was the primary factor that affected system performance the most. The disk I/O overhead also affected system performance, but it was less significant than the network I/O overhead. In addition to these overheads, garbage collection is also heavily affected by the caching mechanism, especially when processing iterative algorithms. Thus, we conducted experiments to analyze the effect of garbage collection according to caching mechanisms in the running of iterative algorithms on Spark. The experimental results show that frequent major garbage collection is a major performance degradation factor, with the garbage collection time accounting for up to 46.51% of the total execution time. In the comparison between the memory cache and the disk cache, their difference becomes larger when the size of the variable data is smaller than that of the eden but the sum of the static and variable data is not.
Applying lessons learned from the previous experiments, we study a new Spark memory management system called machine-learning tuning (MLTuning), which automatically optimizes a caching mechanism for Spark. MLTuning comprises two phases: heuristic adjustment phase and regression tuning phase. In the heuristic adjustment phase, the algorithm adaptively tunes the memory by a heuristic rule; in the regression tuning phase, it optimizes the memory by fitting a regression model to the execution logs that are collected during the heuristic adjustment phase. Experimental results indicate that MLTuning can reduce memory overheads and improve the performance of a Spark job by up to 56% compared with existing Spark memory management systems.
We believe that our work will contribute toward the efficient distributed processing of iterative algorithms including machine-learning and deep-learning algorithms.
맵리듀스(MapReduce)는 빅데이터 분석에서 많이 쓰이는 프레임워크다. 그렇기 때문에, 다양한 데이터 분석 알고리즘들을 맵리듀스 기반으로 확장하기 위한 노력이 있어왔다. 많은 데이터 분석 알고리즘들은 본질적으로 같은 세트의 연산을 값들이 수렴할때까지 반복하는 반복 알고리즘이다. 반복 알고리즘을 효율적으로 분산처리 하기 위해서, 하둡(Hadoop)의 변형들이 산업계과 학계에서 활발하게 개발되었다. 그 대표적인 시스템들은 하룹(HaLoop), 아이맵리듀스(iMapReduce), 트위스터(Twister), 스파크(Spark)이다. 본 학위논문에서 반복 맵리듀스 시스템들의 성능 분석을 통해서 얻은 결과들을 바탕으로 새로운 캐싱 정책을 개발하고자 한다.
반복 알고리즘의 분산처리에 대한 이해를 위해서, 반복 알고리즘을 처리할 때의 맵리듀스의 한계에 대해서 분석하였다. 그리고 하둡과 하둡을 변형한 다른 시스템들의 차이를 다양한 작업량과 측정기준들을 활용해서 실험적으로 분석하였다. 이 시스템들이 반복 알고리즘을 처리할 때, 캐시, 통신, 스케줄링의 효용성을 철저하게 분석하였다. 전반적으로, 스파크가 가장 좋은 성능을 보여주었다. 그렇기 때문에 본 학위논문에서는 스파크에 대해 더 자세히 알아보기 위해, 스파크가 반복 알고리즘을 처리할 때의 한계에 대해서 실험을 통하여 조사하였다. 실험 결과에 의하면, 네트워크 통신 오버헤드가 스파크의 성능에 가장 많은 영향을 끼쳤다. 디스크 입출력 오버헤드 또한 시스템의 성능에 영향을 끼쳤지만, 그 크기는 네트워크 통신 오버헤드 보다 적었다. 이 오버헤드에 더해서, 가비지 컬렉션(garbage collection) 오버헤드 또한 성능에 많이 영향을 끼쳤다. 가비지 컬렉션 오버헤드는 캐싱 정책에 따라 성능에 끼치는 영향의 정도가 달랐다. 그래서 캐싱 정책에 따라 가비지 컬렉션이 성능에 끼치는 영향을 조사하기 위하여 추가 실험을 진행하였다. 실험 결과 빈번한 메이저(major) 가비지 컬렉션은 전체 실행 시간의 46.51%까지 영향을 끼칠 수 있는 성능 하락의 주요 요인이었다. 그리고 힙 메모리(heap memory)의 이든 (eden)영역의 크기보다 변동 데이터의 크기가 작고, 변동 데이터와 고정 데이터의 크기의 합은 클때는 메모리 캐시가 디스크 캐시 보다 성능이 좋았다.
본 학위논문에서는 이전 실험의 결과들을 이용해서 MLTuning 이라는 새로운 스파크 메모리 관리 시스템을 개발하였다. MLTuning은 스파크의 캐싱을 자동으로 최적화 해주는 시스템이다. MLTuning은 휴리스틱 조정 단계와 회귀 튜닝 단계, 두 단계로 구성 되어 있다. 휴리스틱 조정 단계에서 알고리즘은 휴리스틱 규칙에 의하여 캐싱을 적응적으로 최적화 한다. 회귀 튜닝 단계에서는 휴리스틱 조정 단계에서 수집한 실행 로그들을 이용해서 회귀 모델을 만들고, 해당 모델을 이용해서 캐싱을 최적화 한다. 실험 결과 MLTuning은 메모리 오버헤드를 줄이고 스파크 응용의 성능을 다른 스파크 메모리 관리 시스템과 비교해서 최대 56%까지 향상시켰다.
본 학위논문의 연구가 머신러닝과 딥러닝 알고리즘들을 포함하는 반복알고리즘의 효율적인 분산처리에 기여할 것으로 기대한다.
