04 - 3. 맵리듀스: 더 높은 추상화 레벨의 분할 정복 기법

 

이 절에서는 약간 다른 관점에서 분할 정복을 다룬다.

소프트웨어를 단일 컴퓨터 계산 능력 이상으로 확장하고 컴퓨터 군집(cluster)를 이용하여 문제를 해결하고자 할 때 맵리듀스를 이용한 분할 정복 기법을 적용한다.

 

맵리듀스는 대규모 데이터셋을 생성하고 처리하기 위한 프로그래밍 모델 및 구현이다.

사용자는 키와 값의 쌍을 처리하여 중간 단계의 키/값 쌍을 생성하는 맵 함수와 같은 중간 단계 키에 해당하는 모든 중간 단계 값을 병합하는 리듀스 함수를 지정한다.

 

맵리듀스 프로그래밍 모델에 대한 오픈 소스 구현 코드 중 가장 대표적인 것은 하둡(Hadoop)이다.

하둡은 하둡 분산 파일 시스템(HDFS, Hadoop Distributed File System)에 저장된 데이터를 다루는 맵과 리듀스 함수를 작성할 때 필요한 프로그래밍 툴킷을 제공한다. HDFS는 네트워크를 통해 연결된 수천대의 컴퓨터 클러스터로 쉽게 확장할 수 있으므로 맵리듀스 프로그램은 클러스터 크기에 따라 확장할 수 있다.

 

이 장에서는 하둡을 다루지 않고, 프로그래밍 패러다임의 일환으로 맵리듀스만 다루려 한다.

그리고 맵리듀스와 분할 정복 기법과의 연관성에 대해 살펴보려 한다.

하둡 대신, 단일 컴퓨터에서 멀티스레드를 사용하여 병렬화를 구현한 맵리듀스 오픈 소스를 사용할 것이다.

 

 

 

맵과 리듀스

맵은 컨테이너 C를 입력으로 받아, 컨테이너의 모든 원소에 함수 f(x)를 적용하는 연산이다.

예를 들어 f(x) = x^2을 사용하여 맵 연산을 수행하는 경우는 다음과 같다.

 

- map(C=[1, 2, 3, 4, 5], f(x)=x^2) => [1, 4, 9, 16, 25]

 

 

리듀스는 컨테이너 C의 모든 원소 x에 함수 f(acc, x)를 적용하여 하나의 값으로 축약하는 연산이다.

예를 들어 f(acc, x) = acc + x 함수를 사용하여 리듀스 연산을 수행하는 경우는 다음과 같다.

 

- reduce(C=[1, 2, 3, 4, 5], f(acc, x) = acc + x) => 1 + 2 + 3 + 4 + 5 = 15

 

C++ 표준 라이브러리는 맵과 리듀스 연산을 std::transform()과 std::accumulate(), std::reduce() 함수로 제공한다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
using namespace std;

// 맵 연산 테스트 함수 작성
void transform_test(vector<int>& v) {
	vector<int> Tr;

	cout << "[맵 테스트]" << endl;
	cout << "입력 배열: ";
	for (auto i : v) cout << i << " ";
	cout << endl;

	// std::transform() 함수 사용 : 원본을 바꾸지 않고 별도의 벡터를 만들어 반환
	std::transform(v.begin(), v.end(), std::back_inserter(Tr), [](int x) {
		return std::pow(x, 2);
	});

	cout << "std::transform(), Tr: ";
	for (auto i : Tr) cout << i << " ";
	cout << endl;

	// std::for_each() 함수 사용 : 원본 벡터 자체를 변경
	std::for_each(v.begin(), v.end(), [](int& x) {
		x = pow(x, 2);
	});

	cout << "std::for_each(), v: ";
	for (auto i : v) cout << i << " ";
	cout << endl;
}

void reduce_test(vector<int> v) {
	cout << "\n[리듀스 테스트]" << endl;
	cout << "입력 배열: ";
	for (auto i : v) cout << i << " ";
	cout << endl;

	// std::accumulate() 함수 사용
	int ans = std::accumulate(v.begin(), v.end(), 0, [](int acc, int x) {
		return acc + x;
		});
	cout << "std::accumulate(), ans: " << ans << endl;

}

void map_reduce_test() {
	vector<int> v = { 1, 10, 4, 7, 3, 5, 6, 9, 8, 2 };

	transform_test(v);
	reduce_test(v);
}

 

 

transform_test 함수에서 참조 변수로 벡터를 받았고, for_each 함수에 의해 원본이 변경되었으므로 reduce_test 함수에서도 맵연산이 수행된 벡터가 전달되었다.

 

 

 

---

 

 

맵리듀스 프레임워크를 이용한 부분 통합

맵리듀스 모델을 사용하여 프로그램을 작성하려면 원하는 연산을 맵과 리듀스 두 단계로 표현할 수 있어야 한다.

맵 단계에서는 입력을 중간 단계의 <키, 값> 쌍으로 표현하고, 리듀스 단계에서는 중간 단계의 <키, 값> 쌍을 원하는 방식으로 결합하여 최종 결과를 생성한다.

 

하둡은 맵과 리듀스 연산을 확장성 있고 분산 처리가 가능하게 만듦으로써 컴퓨터 클러스터에서 동작할 수 있고 연산 시간을 크게 단축시킬 수 있다.