구글은 어떻게 0.1초 만에 검색할까?

병렬 처리(Parallel Computing) 이야기

구글에 있는 데이터의 양은 얼마나 될까? 매일 30억 건 이상의 검색, 4억 2500만 명의 지메일, 수천만 건의 유튜브 비디오, 지도 데이터, 200억 웹페이지 인덱싱만 생각해도 어마어마하다. 여기에 안드로이드와 광고 서비스, 그리고 사용자에게 잘 안 알려진 내부 데이터까지 합하면 어마어마한 데이터가 있을 것이다. 구글이 가지고 있는 데이터의 용량은 알려져 있지 않지만, 세계 32곳 150만 대의 서버가 있다는 데이터 센터 사진들을 보면 그 방대함을 느낄 수 있다.

축구장 크기의 장대한 구글 조지아 데이터 센터

요즘 핫한 빅데이터 시대에 거대한 데이터 처리를 위해 많은 업체들이 고심하고 있다. 내가 몸 담고 있는 초단타매매 업계에서도 엄청난 데이터와 마주한다. 1초에 수십만 건의 거래 주문을 내는 거래소 데이터를 저장하고 빠른 속도로 처리하는 것은 쉽지 않은 일이다. 이렇게 방대한 데이터의 처리에 대한 고민을 먼저 맞닥뜨리고 다양한 해결법을 강구한 업체가 아마 구글일 것이다. 구글이 이러한 데이터 처리를 위해 발표한 맵리듀스(MapReduce) 기법과 그걸 바탕으로 만들어진 하둡(Hadoop) 라이브러리가 많은 사람들에게 사랑을 받고 일반인들도 쉽게 빅데이터를 처리하는 원동력이 되었다. 구글은 어떻게 이런 처리를 하는 것일까? 여러가지 일을 동시에 처리하는 병렬 컴퓨팅의 원리를 통해 알아보자.

무어의 법칙

1990년대에 내가 컴퓨터를 처음 접했을 때부터 컴퓨터 속도는 엄청나게 발전해왔다. 처음에 가지고 놀던 아버지의 매킨토시의 메모리가 1MB 정도였는데 지금 집에 있는 컴퓨터의 메모리는 16G, 약 16000배가 되었다. 시간이 지나면 더 좋은 컴퓨터가 등장하고 그로 인해 처리를 빨리하여서 더 많은 일을 가능케 하였다. 인텔의 공동 설립자 고든 무어는 이를 두고 '컴퓨터 반도체의 성능은 18개월마다 2배가 된다'라는, 소위 말하는 무어의 법칙이라는 것을 내놓는다.

무어의 법칙

이 무어의 법칙은 2000년대 초반까지는 어느 정도 맞아 들어갔다. 그러나 2000년대 중반에 들어서면서 점점 트랜지스터를 더 작게 만들기 어려워지는 한계에 도달하게 된다. 반도체의 공정이 물리적 한계인 10nm(나노) 대가 된 것이다.

무어의 법칙은 끝인가?

그 이후로 프로세서의 속도는 거의 빨라지지 않았다. 그래프에서 반도체의 클럭 스피드인 하늘색을 보면 2005년 즈음부터 더 이상 증가하지 않는다는 것을 볼 수 있다. 이대로 무어의 법칙은 깨지는 것일까?

더 이상 늘릴 수 없다면, 두 개를 연결하자

엔지니어들은 더 이상 한 개의 칩으로 속도를 늘리기 어려워지자 칩 하나에 메모리를 공유하는 두 개의 프로세서를 집어넣는 혁신적인 '듀얼코어'를 선보인다.

이로 인해 무어의 법칙은 그래프의 남색선처럼 계속해서 이어지게 된다. 듀얼 코어를 시작으로 4개를 연결하는 쿼드코어, 8개를 연결하는 옥타코어까지 등장시키면 되는 것이었다. 그러나 기쁨도 잠시, 듀얼코어에게도 문제가 있었다. 코어를 두 개 연결하였지만 속도 2배가 되지 않고 거의 변화가 없는 것이었다. 이유를 분석해보니, 두 개의 코어가 동시에 처리를 할 수 있는, 병렬 처리 시스템(Parallel Computing)이 되어있지 않아서였다.

예를 들어, 어떤 책의 내용을 요약해야 하는데 사람이 2명이 있고 책은 한 권 밖에 없다면 2명이 하든 1명이 하든 속도는 별 차이 없는 것과 비슷하다. 당시에는 대부분의 프로그램이 싱글 코어 용으로 제작되어 있었고 프로그래머도 그다지 신경 쓰지 않아서 연산을 순서대로 하나씩 하나씩 하였다. 그렇기 때문에 코어가 둘이라도 한 코어가 일하는 것을 다른 코어가 멍하니 바라보고 있어야만 했다. 이런 비효율을 막고 듀얼 코어를 이용해서 속도를 빠르게 하려면 최대한 동시에 처리할 수 있는 부분을 개발자가 적절히 지정해주어야 했다. 마치 책을 반으로 쪼개서 두 사람에게 나눠주는 작업과 비슷하다.

하지만 동시에 처리할 수 없는 부분도 있다. 예를 들어 책의 1단원을 알아야 2단원을 알 수 있다던가, 책이 시리즈물이라고 해보자. 두 번째 사람은 중간부터 읽어도 앞의 내용을 모르면 이해할 수가 없다. 이런 부분은 순차적으로 해야 하는 것이다. 이러한 순차적인 부분이 많을 수록 코어가 아무리 많아져도 다른 코어는 일이 끝날 때 까지 기다릴 수 밖에 없다.

암달의 법칙

이를 정리한 것이 암달의 법칙(Amdahl's law)이라는 이론이다. 암달의 저주라고도 불리는 이 이론은 순차적으로 해야 하는 부분이 많으면 아무리 자원(=사람, 코어)을 많이 투입해도 주황색 부분 이상 빨라질 수 없다는 것이다. 도표에서 병렬 처리가 가능한 보라색 부분은 코어가 늘어나면 빨라지지만, 주황색 부분은 줄어들 지 않는다. 예전에는 그저 컴퓨터 성능이 좋아지기만 하면 프로그램도 빨라졌지만 이제는 주황색 부분을 최대한 줄이는 설계를 하여서 병렬 처리가 가능하게 짜야하는 것이다. 2005년에 한 저널에서는 이를 두고 '공짜 점심은 끝! 프로그래머도 이제 속도 향상을 위해 노력해야 한다!'라고 표현하였다.

병렬 처리의 시대

병렬 처리의 중요성이 대두되면서 프로그래머들의 설계 방식도 변했다. 예전에 1부터 100까지 더하는 작업은 프로세스 하나가 '1 + 2는.... 3이고.... 3 + 3은 6이고..' 이런 식으로 했다면 이제는 두 프로세서가 하나는 1부터 50을, 나머지는 51부터 100을 더하고 나중에 합치는 작업을 하도록 설계하는 것이다. 심지어 연산 자체를 더 잘게 쪼개서 병렬화 하는 ILP 기술도 도입되었다.

ILP(Instruction Level Parallelism)

원래는 5번이 걸릴 연산을 병렬 처리로 3번 만에 해결한다. 이런 식으로 하드웨어부터 소프트웨어 전문가까지 많은 부분을 병렬화 하려고 노력하기 시작했다. 병렬 처리 설계는 얼핏 단순해보이지만 생각보다 쉽지만은 않다. 순서나 공유자원 등을 고려하지 않는다면 전혀 엉뚱한 결과가 나올 수도 있기 때문이다. 예를 들어, 2 * 2 + 3 * 3을 처리하는데 2*2와 동시에 2+3을 처리해버린다면 전혀 다른 결과가 나올 것이다.

공유 자원에 대한 처리도 조심해야 한다. 예를 들어, 계좌에 100만 원이 있는데 50만 원 입금과 30만 원 출금을 동시에 처리한다고 해보자. A 프로세서는 100만 원에 50만 원을 추가해서 150만 원이 될 것이다. B 프로세서는 A가 아직 업데이트하기 전에 100만 원에서 30만 원을 출금해서 70만 원이 된다. 원래는 120만원이 되어야 하는데 결과가 70만원이나 150만원 중에 무엇이 될지 모르는 상태가 된다. 이러한 상태를 두 프로세서가 계좌를 서로 가지려고 한다 해서 경쟁 상태(Race Condition)라고 한다. 이러한 부분을 철저히 처리하지 않으면 심각한 오류를 야기 할 수도 있다.

병렬 처리 기술이 늘어나자 대용량 데이터를 처리하거나 방대한 계산을 해야 하는 분야에서 병렬 처리를 적극 수용하기 시작했다. 대표적으로 슈퍼 컴퓨터가 있다. 슈퍼 컴퓨터는 어려운 개념이 아니다. 수많은 코어를 붙여서 방대한 계산을 병렬 처리할 수 있도록 만든 컴퓨터인 것이다. 97년에 체스 챔피언을 이긴 슈퍼 컴퓨터인 '딥 블루'는 480개의 코어가 있었고, 우리나라 기상청 슈퍼컴퓨터는 무려 902040개의 코어가 있다고 한다.

병렬 처리의 대중화

병렬 처리의 중요성과 장점이 일반 사람들과 기업에게도 퍼지기 시작했다. 그러나 근본적으로 '코어'가 굉장히 비싼 것이 문제였다. 국가 기관이나 거대 기업들이야 슈퍼 컴퓨터를 이용하거나 다중 코어로 처리하였지만 일반인들은 그럴 수가 없었다. 거기다 일반인에게도 데이터 계산이나 동영상 렌더링과 같은 거대 작업을 해야 할 일이 많이 생기기 시작했다.

한편 그래픽 카드 회사인 엔비디아는 곰곰이 생각해보니 자신들이 이미 화면에 그래픽을 그릴 때 병렬 처리 기술을 사용하고 있었다는 사실을 알게 된다. 4k 화질인 4000 X 8000 정도의 이미지를 화면에 그리려면 3200만 개의 점(픽셀)의 색깔을 계산해서 그려야 한다. 엔비디아는 이러한 그림을 원활하게 보이게 하기 위해서 그래픽카드에 이미 2천 개 정도의 간단하고 싼 코어를 넣어놨었다. 이 작은 코어들이 매번 화면에 보일 색깔을 계산하여서 화면에 표시하는 것이다.

NVidia GTX 780

NVidia GTX 780에는 무려 코어가 2304개가 있다. 물론 CPU처럼 강력한 코어는 아니고 간단한 계산만 가능하지만 말이다. 지금 이 글을 읽는 당신의 컴퓨터에도 수많은 코어가 있는 그래픽 카드가 있다.

엔비디아는 이를 이용해서 저렴한 버전의 슈퍼 컴퓨터인 Cuda를 구현했다. 물론 Cuda는 슈퍼컴퓨터처럼 단순하게 병렬 처리를 할 수는 없었다. 그래픽 카드 안에 있는 코어의 성능이 매우 떨어져서 최대한 간단한 연산으로 바꿔야 했다. 또한 그래픽 카드에서 아무리 병렬로 빠르게 계산하여도 결과물이 방대하면 이를 다시 CPU로 전달하는데 더 많은 시간이 걸렸기 때문에 최대한 결과물을 줄이는 작업도 필요하였다. 한계점도 있었지만 일반인도 사용할 수 있는 저렴한 병렬 시스템의 등장은 획기적이었다. 이러한 Cuda 시스템의 발전으로 연구소, 기업, 일반인들 사이에서도 방대한 병렬 처리가 인기를 끌게 되었다. 내 인턴 시절 두 번째 프로젝트가 바로 이 Cuda를 이용하여서 수만 개의 파생상품 가격을 동시에 계산하는 시스템을 만드는 것이었다.

2000년대 중후반에 웹 기술이 대중화 되면서 컴퓨터 한대로만 병렬 처리를 하는 것이 아닌 여러대의 컴퓨터로 분산처리하는 시도가 시작된다. 이는 사실 한대에서 병렬 처리하는 것보다 훨씬 어려운 일이었다. 컴퓨터마다 성능이 제각각이었고, 작업량을 분석해서 쉬고 있는 컴퓨터나 코어에게 나누어 주어야 하는데 이를 너무 자주 하면 오히려 속도가 느려져서 적절하게 설계를 하여야 했다. 또 계산하는 시간보다 데이터를 전송하는 시간이 더 오래 걸릴 때도 있어서 최대한 원하는 결과로 축소를 시켜서 전송 하도록 해야 했다. 그래서 몇십, 몇백대 정도까지 연결하여서 사용하였지만 그 이상은 거의 시도하지 않았다.

구글의 획기적인 기술, 맵리듀스

하지만 구글은 늘어가는 데이터와 느려지는 검색 속도를 두고 볼 수만은 없었다. 데이터가 적을 때는 문서 하나하나 키워드를 검색해서 결과를 보여주면 되었고, 데이터가 늘어나면 더 좋은 성능의 서버로 바꾸면 되었다. 그러나 고성능 서버는 가격은 비쌌고 데이터가 늘어나는 속도가 서버 속도를 추월하기 시작했다. 결국 구글은 성능이 약하고 싼 데이터 서버(=노드)를 아주 많이 연결하는 방법을 사용하게 된다. 이렇게 하면 위의 Cuda와 비슷한 원리로 간단한 계산과 처리를 약한 서버에서 하고 그 결과를 모아서 최종 결과를 계산하는 방식을 사용하게 되는 것이다.

쉬운 일은 아니었다. 여러 대의 서버를 연결하면 한대에서 처리한 것과 다르게 전송에서 많은 시간을 잡아먹는다. 그러므로 각각 서버에서 최대한 많은 계산을 해서 결과를 작게 만들어서 전송해야 한다. 그런데 각 서버들은 성능이 좋지 않아 복잡한 계산을 하기 어려운 딜레마가 있었다. 게다가 복잡한 설계를 하였을 때 각 서버가 제대로 동작하는지 하나하나 체크하기도 어렵고, 매번 변경점을 모든 서버에 적용시키기도 어려웠다.

이러한 시스템 설계를 간단하고 강력하게 만든 시스템이 바로 구글의 유명한 맵리듀스(MapReduce)이다. 맵리듀스는 복잡한 설계 없이 맵과 리듀스 두 가지 행동 방식을 주면 결과를 계산하는 기술이다. 맵은 주로 데이터를 변환하거나 추출하는 방법이고, 리듀스는 추출해낸 데이터를 처리하는 방법을 말한다.

예를 들어, 데이터가 문장이고

맵 - 문장을 단어 단위로 바꿔라

리듀스 - 각 단어를 세라

라고 정해주면

이렇게 cookies 2번, cloud 2번 등등 각 단어를 센 결과가 나온다.

또 다른 예로, 데이터가 각 반 학생의 성적이고

맵 - 수학 성적을 추출해라

리듀스 - 평균을 내라

라면 반 평균 수학 성적이 결과로 나올 것이다.

왜 이렇게 언뜻 복잡하게 맵과 리듀스로 나누어서 처리하는 것일까? 만약 단지 한 반의 성적을 계산하는 것이라면 그냥 순차 프로그램으로 모든 학생의 수학 성적을 추출해서 평균을 구하면 쉬울 것이다. 그러나 전 세계의 수학 성적 평균을 구한다면 이야기가 다르다. 이러면 많은 서버에 새롭게 성적 평균을 구하는 프로그램을 만들어줘야 한다. 반면 맵리듀스 시스템이라면 데이터가 아무리 커지고 복잡해져도 맵과 리듀스만 정해 주면 말단 노드들은 맵만 처리하고 중간 서버가 리듀스를 하며 데이터 양을 줄이고 그것을 다시 맵 하고를 반복하며 쉽고 명확하게 병렬 처리를 할 수 있는 것이다.

구글은 이러한 기술을 통해 세계 각지의 데이터센터에 있는 데이터를 수많은 서버들이 동시에 병렬 처리하여서 사용자에게 즉시 결과를 보여주는 것이다. 내가 구글에 검색할 때마다 전 세계의 수십만 대의 구글 서버들이 동시에 움직인다니 뭔가 참 신기하다.

구글은 이 맵리듀스 기술을 모든 사람이 쓸 수 있도록 논문으로 공개하였다. 이를 기반으로 많은 오픈소스 빅데이터 처리 프레임워크들이 등장하고, 하둡도 이 중 하나인 것이다. 이를 통해 일반 사람들도 쉽게 빅데이터 분석이나 클라우드 시스템의 병렬 처리를 할 수 있게 되었다.

빅데이터 시대의 병렬 처리

다양한 기업에서 빅데이터 분석을 도입하면서 이러한 병렬 분산 처리 시스템을 도입하는 경우가 늘어나고 있다. NC 소프트에서도 방대해진 게임 로그와 데이터를 하둡을 통해서 처리한다하고 금융 회사나 리테일 회사들도 빅데이터 분석을 위한 시스템을 도입한다고 한다. 그러나 정작 이러한 병렬 처리 시스템은 굉장히 손이 많이 가고 복잡하다는 사실을 간과한다. 마치 한 명이 일처리 할 땐 한명만 신경 쓰면 되지만 여러 곳, 여러 명이 일을 하게 되면 문제가 많이 생기는 것과 비슷하다. 이제 사실 웹서비스, 모바일 앱, 데이터 처리, 게임 등등 모든 부분에서 병렬처리가 이용되고 있다. 이러한 병렬 처리에 대한 한계와 위험성, 비용을 이해하고 도입하는 것이 중요하다.