맵리듀스 (MapReduce)

1000대의 서버에 흩어진 로그 1페타바이트에서 단어별 등장 횟수를 세려면? 한 대가 다 읽으면 몇 달이 걸린다. 맵리듀스는 "쪼개서(map) → 모으고(shuffle) → 합친다(reduce)"는 단 두 함수만으로 이 일을 수백 대에 자동으로 나눠 준다. 구글이 2004년 논문으로 공개했고, 하둡·스파크의 뿌리가 됐다.

1. 세 단계: Map · Shuffle · Reduce

Map은 완전히 독립적이라 서버 수만큼 병렬로 돌고, Reduce도 키 그룹별로 병렬이다. 중간의 Shuffle만 네트워크를 크게 쓰는 구간이다.

2. 직접 돌려보기 — 단어 세기

문서 4개를 매퍼 4대가 나눠 처리한다. 다음 단계를 눌러 한 단계씩, 또는 자동 재생으로 전체 흐름을 본다.

3. combiner — shuffle 트래픽을 줄이는 지역 리듀스

매퍼 한 대가 ("사과",1) 을 500번 내보내면, 그 500개가 전부 네트워크를 타고 리듀서로 간다. combiner는 매퍼 쪽에서 미리 ("사과",500) 로 접어서 보낸다. 위 데모에서 체크해 보면 shuffle 단계 칩 개수가 확 줄어드는 걸 볼 수 있다.

4. 고장은 정상이다 — 내결함성

• 죽은 태스크: 워커가 응답 없으면 마스터가 그 태스크만 다른 노드에 재실행. map은 순수 함수라 재실행해도 결과가 같다.
• straggler(느림보): 거의 끝났는데 유독 느린 노드가 있으면, 같은 태스크를 다른 노드에도 동시에 돌리고(추측 실행, speculative execution) 먼저 끝난 쪽을 채택한다.
• 데이터 지역성: 스케줄러는 입력 블록이 이미 저장돼 있는 노드에 map 태스크를 보낸다 — 데이터를 옮기는 대신 계산을 옮긴다.

5. 코드로 정리

# 사용자는 이 두 함수만 작성한다
def map(doc_id, text):
    for word in text.split():
        yield (word.lower(), 1)          # (키, 값) 방출

def reduce(word, counts):
    yield (word, sum(counts))            # [1,1,1,...] → 합

# ── 아래는 프레임워크가 대신 해 주는 일 ──
def run(docs, n_reducers):
    pairs = [kv for d in docs for kv in map(*d)]   # 매퍼들 병렬 실행
    groups = defaultdict(list)
    for k, v in pairs:
        r = hash(k) % n_reducers               # 키 → 리듀서 배정(파티셔닝)
        groups[(r, k)].append(v)               # shuffle: 키별로 모음
    for (r, k), vs in sorted(groups.items()):     # 리듀서는 정렬된 키를 받음
        yield from reduce(k, vs)                  # 리듀서들 병렬 실행

6. 언제 쓰고, 언제 안 쓰나

반복·대화형 워크로드의 단점 때문에 Spark가 등장했다 — 같은 map/reduce 사고방식에 중간 결과를 메모리에 유지하는 방식을 더했다.