An important property of today`s big data processing is that the same computation is often repeated on datasets evolving over time, such as web and social network data. This style of repeated computation is also used for many iterative algorithms. While repeating full computation of the entire datasets is feasible with distributed computing frameworks such as Hadoop, it is obviously inefficient and wastes resources.
In this dissertation, we present HadUP (Hadoop with Update Processing), a modified Hadoop architecture tailored to large-scale incremental processing for conventional MapReduce algorithms. Several approaches have been proposed to achieve a similar goal using task-level memoization. They keep the previous results of tasks permanently, and reuse them when the same computation on the same task input is needed again. However, task-level memoization detects the change of datasets at a coarse-grained level, which often makes such approaches ineffective. Our analysis reveals that task-level memoization can be effective only if each task processes a few KB of input data. In contrast, HadUP detects and computes the change of datasets at a fine-grained level using deduplication-based snapshot differential algorithm (D-SD) and update propagation.
Update propagation is a key primitive for efficient incremental processing of HadUP. Many applications for today`s big data processing consist of data parallel operations, where an operation transforms one or more input datasets into one output dataset. For each operation, the same computation is concurrently applied to a single input record or a group of input records. The independence between these executions allows us to compute the records to be inserted into or deleted from the output dataset, if those records inserted into or deleted from the input datasets are explicitly given. In this way, update propagation computes the updated result without full recomputation. Our evaluation shows that HadUP provides high performance, especially in an environment where task-level memoization has no benefit, while requiring only a small amount of extra programming cost.
D-SD enables HadUP to detect the change of the application input at a fine-grained level, where this input change is needed to begin update propagation. Given the old and new snapshots of a dataset, we can figure out how the dataset changes by ignoring all the unchanged records between them. However, it is non-trivial if the given dataset is classified as ``big data", because simple snapshot comparison causes large network traffic. We overcome this challenge using a variant of the data deduplication technique, which is mainly used to eliminate duplicate copies of repeating data. Our evaluation shows that D-SD provides high throughput via reduction of network traffic.
현재의 빅데이터 분석 과정에는 웹이나 소셜 데이터처럼 시간에 따라 변화하는 데이터를 반복적으로 처리하는 경우가 많다. 이를 위해 Hadoop과 같은 빅데이터 소프트웨어 플랫폼을 이용하여 전체 데이터를 전부 다시 계산할 수도 있지만, 이는 비효율적이며 자원 낭비이다.
본 학위 논문에서는 맵리듀스(MapReduce)를 위한 대용량 점진적(incremental) 처리를 지원하는 플랫폼인 HadUP(Hadoop with Update Processing)을 제안한다. 기존 연구 중에서는 태스크 수준 메모이제이션 기법(task-level memoization)을 이용하여 이와 비슷한 목적을 달성하려는 시도들이 있었다. 빅데이터 분석을 위해 분산 컴퓨팅을 이용하면 주어진 입력 데이터를 처리하기 위해 다수의 태스크(task)를 생성하는데, 태스크 수준 메모이제이션 기법은 모든 태스크들의 결과를 저장한 후, 동일한 입력 데이터를 처리하는 태스크들이 다시 필요하게 되면, 저장된 결과를 재사용하자는 것이다. 즉, 조금 변경된 입력 데이터를 동일하게 처리하려고 하면, 대부분의 태스크들은 예전과 동일한 입력 데이터를 처리할 것이라는 가정을 기반으로 한다. 하지만 본 논문에서의 분석 결과, 태스크 수준 메모이제이션 기법은 하나의 태스크가 수 KB 정도의 입력 데이터만 처리하는 경우에 효과적이었으며, 일반적인 빅데이터 소프트웨어 플랫폼에서처럼 수십--수백 MB를 할당 받게 되면 효과를 기대할 수가 없었다. 반면, HadUP은 변경 전파 기법(update propagation)과 중복 제거 기반의 스냅샷 차동 알고리즘(Deduplication-based snapshot differential algorithm, D-SD)을 이용하여 비교적 작은 단위로 입력 데이터에서 변경된 부분을 찾고 여기에 영향을 받는 결과만 재계산한다.
변경 전파 기법은 HadUP이 기존의 맵리듀스 알고리즘을 이용하여 효율적인 점진적 처리를 지원하기 위한 기본 요소이다. 빅데이터 분석을 위한 많은 알고리즘들은 확장성(scalability)을 얻기 위해 데이터 병렬 연산(data parallel operation)을 이용한다. 각각의 연산을 처리할 때는 먼저 주어진 데이터를 특정 규칙에 맞게 작은 그룹으로 나눈 다음, 각각의 그룹에 동일한 계산을 적용하여 결과를 얻는다. 이렇게 각각의 그룹은 독립적으로 처리되기 때문에, 만약 입력 데이터에서 어떤 그룹이 추가되거나 삭제되었다는 것을 알면, 연산의 결과가 어떻게 변경될지 계산할 수 있다. 이것이 변경 전파 기법의 기본 개념으로, 이를 이용하면 기존의 맵리듀스 알고리즘을 수정하지 않아도 점진적으로 처리할 수 있다. 실험 결과, HadUP은 태스크 수준 메모이제이션 기법이 전혀 효과가 없는 상황에서도 점진적 처리를 통해 성능 이득을 얻었다. 또한, 기존의 맵리듀스 알고리즘을 그대로 이용할 수 있기 때문에 사용자의 프로그램 개발 비용은 Hadoop과 비슷한 수준이었다.
D-SD는 변경 전파 기법을 시작할 수 있도록 응용프로그램의 입력 데이터가 어떻게 변경되었는지를 효율적으로 알아내는 기법이다. 어떤 데이터의 이전 상태와 현재 상태가 각각 스냅샷(snapshot)으로 주어졌다고 가정하면, 두 개의 스냅샷을 비교하여 변경되지 않은 부분들을 제거함으로써 이 데이터가 어떻게 변경되었는지를 알아낼 수 있다. 데이터가 여러 노드에 분산되어 저장되어 있는 경우에 변경되지 않은 모든 부분들을 제거하기 위해서는 두 스냅샷을 같은 조건으로 분할(partition)하는 과정이 필요하나, 이 과정 중에는 네트워크 전송량이 상당히 높아진다는 문제가 존재한다. 본 학위 논문에서는 중복 제거 기법(deduplication)을 이용하여 변경되지 않은 "대부분의" 데이터를 "효율적으로" 제거할 수 있는 근사 알고리즘(approximate algorithm)인 D-SD를 제안한다. 근사 알고리즘은 변경되지 않은 부분을 모두 제거하지 못하기 때문에 변경 전파 기법 중에 불필요한 계산을 하게 되지만, 그래도 올바른 결과를 얻을 수 있다. 실험 결과, 대부분의 경우, D-SD를 이용하여 얻는 이득이 불필요한 계산에 의한 손해보다 컸다.
