CS 전공/리뷰2012. 10. 23. 14:59

이번 ACM CIKM'12에서 발표될 HadoopXML이라 명명한 저희 시스템입니다.

HadoopXML은 대량의 XML 데이터에 대한 다중 XML 질의 처리를 수행하기 위한 Hadoop 기반의 시스템입니다.



XML은 루트 엘리먼트를 루트로 하는 labeled, ordered tree라는 데이터 모델이라는 특성이 있고,

이 XML 문서에 대한 질의는 가지 패턴 질의(twig pattern query)라는 특성이 있습니다.

예를 들어 //A//B[C]//D와 같은 질의는 A밑에 B 엘리먼트가 있고, 이 B 엘리먼트는

C를 포함하여야 하며, D 엘리먼트는 이러한 B 엘리먼트 밑에 존재하여야 한다는 

구조 정보를 기술합니다.


가장 간단한 XML 질의 처리 방법은 XML을 트리 형태(DOM)로 모델링하고 이를 모두 메모리에 올려둔 후 트리의 노드 순회를 통해서 이러한 패턴을 찾는 방법입니다. 하지만, 이런 식의 방법은 트리 내 모든 노드를 순회하여야 하는 문제점이 있지요.

해서 XML 분야에서는 labeling scheme을 이용해서 각 엘리먼트에 레이블을 부여하고, 이들의 레이블 값을 비교함으로써 이러한 패턴 검사를 수행하게 합니다. 예를 들어, A(1:150, 1) B(3:5, 2)

로 레이블된 두 엘리먼트 A, B가 있는 경우 두 값의 interval 값(1:150 vs. 3:5을 비교하고, 어느 한쪽이 다른 쪽의 interval을 포함하는지 등을 검사합니다.  이러한 labeling 기법을 이용하여 기존의 질의 처리를 위한 트리 순회를 레이블 값의 비교를 통한 조인 연산으로 변경한 거지요.


최근의 XML 문서의 크기는 굉장히 큽니다.

예를 들어서 UniProtKB라고 하는 단백질 정보와 단백질간의 관련 정보를 기술하는 XML 문서는 파일 하나의 크기가 108GB 를 넘습니다. 데이터 로깅에서도 Log4j 등을 이용해서 로그 포맷으로 XML이 사용될 수 있을텐데, 이런 경우에도 생성되는 XML 문서의 크기는 매우 크게 되지요.

결국엔 기존의 XML pub/sub 시스템이나 단일 노드에서 동작하는 XML DBMS로는 처리하기가 용이하지 못하게 됩니다. 실제로 저희가 대표적인 open-source XML DBMS인 eXist나 BaseX로 테스트한 경우나 XML pub/sub system인 YFilter로 테스트 한 결과도 그랬습니다.


HadoopXML은 이렇게 크기가 큰 XML 파일을 이들에 대한 질의 처리를 수행합니다. 이러한 작업 기본적으로 Hadoop을 기본으로 수행됩니다. 하지만, 그대로 Hadoop을 가지고 하기엔 여러 가지 문제점들이 있지요.


첫번째 문제는 하나의 큰 XML 문서를 여러 개의 블록들로 분할하게 되면, 각 블록들만 봤을 때는 엘리먼트들의 구조 정보를 알 수 없다는 점입니다. 하나의 트리에 있는 노드를 단순히 같은 수의 노드를 가지는 블록들로 나누는 경우에 한 블록내 노드를 봐서는 이것의 부모나 조상 노드가 뭐였는지 파악하기 힘들죠. HadoopXML은 간단한 테크닉으로 이를 가능하게 합니다.


그리고 또, 하나의 질의를 처리하기 위해 한 MR job을 수행한다면 큰 낭비이겠죠. HadoopXML은

수천개의 질의를 한번의 MR job으로 처리하게 합니다. 이때 여러 가지 최적화를 수행하는데, 첫째는 서로 다른 가지 패턴 질의들 간에 서로 공유되는 경로 패턴들이 존재한다는 점을 착안해서 

가지 패턴들을 먼저 경로 패턴들로 분할하고 경로 패턴들에 대한 질의 결과를 먼저 추출합니다.

이때도 서로 다른 경로 패턴들이 문서 상에서 유일한 경로 패턴들로 매칭되는 점을 착안하여 

유일한 경로 패턴들의 결과들만 추출하게 하는 최적화를 수행합니다.

다음으로는 이러한 경로 패턴의 결과들을 가지고 조인을 통해 원래의 가지 패턴 조인에 대한 결과를 추출하는데 있어 많은 조인 연산들을 어떻게 지정된 reducer들에 분배하는 것이 효과적이냐입니다. 예를 들어 4,000개의 가지 패턴 조인을 16개의 리듀서에 분배하기 위해서 어떻게 grouping

하는 것이 효과적이냐 하는 문제입니다. 예를 들어 A join B join C와 A join B join D와 같은

유사한 입력을 갖는 조인은 같은 reducer에 두는 것이 좋을 것입니다.

만약에 그렇지 않다면, 서로 공유되는 A 와 B 입력은 두 리듀서에 중복해서 전달됨에 따라 I/O

낭비를 초래하겠죠. 그래서 결국엔 query들의 grouping을 어떻게 효과적으로 수행하는가에 대한 

최적화 문제가 있겠고, 이때 고려될 것은 리듀서에 전달되는 경로 패턴의 결과들이 서로 

같게 전달되면서, 조인 비용이 최소가 되도록 배분하는 문제가 되겠습니다.

HadoopXML은 이러한 문제를 해결하도록 고안된, 즉 런타임 시에 데이터 뿐만 아니라 질의도

적절히 배분하여 전체 질의 처리 비용을 최소로 하는 방안을 적용하였습니다.


이렇게 해서 HadoopXML은 108GB 크기의 실제 사용되고 있는 XML(UniprotKB/XML) 파일에 대한

16,000개의 가지패턴 질의들을 단지 2개의 M/R job만으로 30 분 이내에 처리합니다.

실험에 이용된 시스템 환경은 Intel i5, 8GB memory, 7200RPM HDD를 가지는 대당 50만원 정도의 일반 PC 9대(1대 master, 8대 slave) 입니다. 이정도의 규모의 저가의 PC로도 좋은 성능을 보여주었습니다. 


MapReduce에서 조인 문제는 매우 재밌는 주제입니다. Map과 Reduce라는 고정된 dataflow를 갖는 시스템에서 다양한 조인 연산들, 다중 조인 연산들을 어떻게 효과적으로 지원하는지는 아직도 할 분야가 많아보입니다.  저희는 이러한 문제를 풀고 있고 다른 저널 논문들로 이에 대한 해결 방안들을 순차적으로 곧 보일 겁니다. 






Posted by Bart
CS 전공/리뷰2012. 7. 9. 21:42



Posted by Bart
CS 전공/리뷰2012. 6. 11. 08:28

근래 KAIST에서 수행하는 연구 중에는  Hadoop을 이용한 비정형데이터 처리가 있다.

그래서 작게나마 9대의 PC들을 가지고 연구실에서 Hadoop cluster를 구축하였다.

1대는 이미 실험실에 존재하던 서버로 이를 Name node로 설정하였고

나머지 8대는 새로 구입한 것으로 i5 quadcore CPU + 8GB 메모리, 1TB 7200RPM HDD와 256GB SSD를 탑재한 것이다.  이들은 data node로 설정하였다. 그리고 이들 모두를 Gigabit switching hub로 연결하였다.


수행하다보니 꼭 reduce task 에서 임의로 노드들의 eth0 네트워크 인터페이스가 죽어버리는 

현상을 경험하였다. 처음엔 Hadoop 세팅 자체의 문제이거나 ulimit 등의 사소한 문제로 생각하였으나 아니었다. 

 수차례의 닭질 끝에 결국엔 Cent0S에 제공하는 Realtek 네트워크 드라이버가 2.x대로

현재의 8.0대에 비해 현저히 버전이 낮은 상태였고, 옛날 버전의 드라이버가 무언가 문제를 일으킨

것을 찾아내었다.


이것을 파악한 것은 나중의 일이고, 처음엔 이것저것 테스트해보았다. 그중에는 스위칭허브를 100Mbps로 교체해 본 일도 포함되었다. 그런데 교체해보니 느리지만 reduce가 죽어서 100% 완료에 도달못하는 문제는 사라졌다. 

해서 이번에는 네트워크 드라이버들을 모두 업그레이드를 하고,  100Mbps와 1Gigabit switching hub를 교체해서 달아보면서 네트워크 성능이 어떻게 M/R job의 성능에 영향을 미치는지 간단히 측정해 보았다. 물론 이것은 어떠한 데이터를 가지고 어떠한 작업을 수행하느냐에 따라 크게 달라질 것이다.

필자의 데이터는 text 포맷이고, M/R job은 간단히 언급하자면, text에서 유일한 token들을 추리고,

이들이 전체 데이터에서 얼마나 반복되어 나타나는지 count하여, 원 text와 같이 출력하는 일이다.


실험 결과는: 

--------

11GB 데이터 적재 시

1 Gigabit : 222.449s

100Mbps: 1,369.204s 

으로 약 6.15배 차이 


11GB에  M/R 작업 수행 시

1 Gigabit : 3분 48초

100Mbps : 9분 11초

 으로 약 2.41배 차이


를 보여주었다.


이를 Amdahl's law(http://bart7449.tistory.com/244에 대입시켜 보면, 

data loading의 경우 1/( (1-p) + p/10 ) = 6.15 이고

p ~= 0.93 


M/R 작업 수행 시의 경우를 보면,

1 / ( (1-p) + p /10 ) = 2.41 

p ~= 0.65

이라는 결과가 나온다. 


즉, 데이터 로딩의 경우 네트워크가 Hadoop 시스템에서 차지하는 비율이 약 93% 에 이르고, 

M/R 작업의 경우에는 그 비율이 낮아지지만 그래도 과반이 넘는 약 65% 에 이르렀다.


이는 Hadoop 시스템에서 네트워크 성능이 Hadoop 시스템의 전체 성능에 엄청나게 영향을 미치는

요인이라는 얘기가 된다. 우리가 보통 시스템에서  I/O를 얘기를 할 때는 디스크 I/O만을 

크게 고려하는데, Hadoop 시스템에서는 오히려 네트워크 I/O가 더 큰 영향을 미치는 것으로 

판단된다.


네트워크 쪽 하는 사람들은 Hadoop을 network traffic log 등을 분석하는데 이용하는 것으로 아는데, 

bulk data transmission이 많은 이러한 Hadoop 환경에서

네트워크 성능 개선을 통한 Hadoop 시스템 개선이나  또는 Hadoop에 특화된 네트워크 구축 방법이나 개발 등이 좋은 주제가 될 수 있지 않을까?


혹 이와 관련하여 좋은 아이디어 있다면 연락주기를 희망한다.  :) 


 




 

Posted by Bart
CS 전공/리뷰2012. 1. 17. 23:06

지난 40년간 마그네틱 디스크는 가장 주요한 저장공간이었다.  대용량 데이터들은 디스크에 기록되고 읽혀졌으며, 상대적으로 용량이 작았던 메인 메모리 때문에 데이터 버퍼링 및 메모리의 효율적 사용이 매우 중요하였다.
때문에 Jim Gray의 5분의 규칙(five-minute rule) 과 같이 데이터 버퍼링 또는 캐싱에 대한  경험적 규칙이 얘기되어 왔다.  실제 디스크에 기반한 DBMS에서도 이 버퍼의 성능이 엄청나게 큰 영향을 미쳐왔다. 
 

5분의 규칙은 1987년, 짐 그레이가 SIGMOD Record에서 언급한 것[각주:1]으로 디스크와 메모리의 접근 시간과 용량을 간단히 수식화하여 약 5분 내 다시 참조될 데이터는 메모리에 올려두는 것이 좋다라고 언급한 것이다.
해당 논문이 쓰여지고 10년뒤 97년에 그레이는 다시 그당시의  저장 계층의 특성에 의해 이 규칙이 어떻게 변화되었는지 다시 소개[각주:2]하였고, 또다시 10년 뒤 2008년에는 고츠 그라페(Goetz Graefe)가 SSD의 출현에 의해 이 규칙이 어떻게 변화되는지를 소개하였다[각주:3].(2007년에 짐 그레이가 실종되서 그는 쓰지 못하였다.)  



디스크는 세월이 지남에 따라 그 저장용량(capacity)은  엄청나게 개선되어 왔다. 하지만, 저장 용량에 비해 접근 지연시간(latency)은 크게 개선되지 못하여 왔다. 아래 표를 보자.
 

 

이 표를 보면 디스크의 용량은 80년대 중반에 30MB인것이 2009년에는 500GB로 약 16,667배정도로 크게 늘어났다. 지금은 데스크탑의 경우 하드디스크의 용량이 1TB는 기본이다.  전송속도 또한 개선되었으나, 저장용량에 비해서는 크게 개선되지 못하였다. 가장 개선이 못된 것은 접근 지연시간이다.  마그네틱 구조의 특성상 회전하는 디스크 위에서 디스크 암이 움직여야 하므로 랜덤 I/O를 위핸 접근 지연시간은 현 HDD 구조에서는 피할 수 없는 특성이다. 그리고, 이것은 크게 개선되지 못하였다. 

따라서 저장용량을 bandwidth로 나누어보면, 용량에 비해 bandwidth 개선이 턱없이 부족함을 보이는 것을 확인할 수 있다.  80년대 중반 15초면 다 읽을 수 있던 것을 지금은 직렬 읽기만 해도 5,000초가 걸리고, 랜덤 읽기인 경우에는 약 58일이라는 엄청난 시간이 요구한다.

이에 따라 연구자들은 기존의 HDD를 대체하기 위해 SSD를 연구해 왔고, SSD는 이제 울트라북을 포함한 여러 PC에 널리 이용되고 있다. 하지만, 데이터센터 스케일에서도 SSD를 적용할 수 있을까? 
 

스탠포드대의 연구자들은 램클라우드라는 프로젝트를 통해 SSD나 디스크보다 이제는 DRAM을 주요 저장공간으로 활용해야 한다고 역설한다.  이들은 인터넷 스케일 서비스의 제공에 있어 HDD를 전혀 이용하지 않고, 수백, 수천대의 노드 컴퓨터들을 연결하여 이들의 메인 메모리들에 모든 데이터를 저장, 관리하는 것을 목표로 한다.

  이러한 목표를 제시한 근거에는 여러가지가 있지만, 우선 위 표를 다시 보면 
 짐 그레이의 5분의 규칙에 따라 5분 이내 재참조될 데이터는 메모리에 올려두었던 것이 이제는 30시간 내에 재참조되는 데이터이라면, 메모리에 올려두는 것이 더 낫다라는 결과를 얻게 되었다는 점이다. 즉, 현재는 가급적이면 모든 데이터를 메모리에 올려두는 것이 효과적이라는 것이다. 사실 이러한 현실은 이전의 Jim Gray의 예측과도 일치한다. 그는 예전에 "Memory becomes disk, disk becomes tape, and tape is dead."라 언급하였다.
 즉, 이제는 메모리를 이전의 디스크가 점유했던 주요 저장소로서 활용하고 디스크는 백업과 아카이빙을 위한 용도로 쓰자는 것이다. 
(사실 테입이 완전히 사라진 것은 아니다. 아직 테입은 여러 데이터 센터에서 데이터 백업의 마지막 보루로 사용되고 있다.) 
 
메모리를 디스크처럼 쓰는 경우 가질 수 있는 많은 장점이 있다. 우선 접근지연시간(latency)가 현격하게 줄어든다. 현재의 데이터 센터를 통한 인터넷 서비스들은 인터넷-스케일이라는 규모가 큰 request들을 처리하는 것을 목적으로 한다. 때문에, 단일 노드로 구성되지 않고 데이터 센터에 많은 노드들을 네트워크로 연결하고 이를 통해 부하를 분산하는 분산 시스템이라는 특징을 가진다. 또한, 웹 서비스와 해당 서비스가 처리/제공하는 데이터가 서로 다른 노드에 위치하는 구조로 인해 접근지연시간이 단일 시스템 구조보다 느리다. 메모리를 디스크처럼 쓰는 경우 이러한 환경에서도 접근지연시간을 마이크로 세컨드 단위로 줄일 수 있다.
SSD를 디스크 대신 쓰는 경우에도 접근지연시간을 크게 줄일 수 있을 것이다. 하지만 저자들은 SSD의 접근지연시간은 디스크에 비해 훨씬 빠르지만, 그렇다하더라도 SSD보다 DRAM의 접근 지연시간 특히 쓰기지연시간이 훨씬 빠르므로 DRAM이 보다 경쟁성이 있다고 저자들은 얘기한다.
아래 그림은 디스크 드라이브, 플래시 메모리오 메모리의 특징을 그림으로 도식화한 것이다.
그림에서 보면 가장 덜 빈번하고, 한번에 요구되는 데이터 량이 큰 경우에는 디스크가 가장 경쟁력이 있고, 작은 크기의 데이터에 대한 매우 빈번한 질의에 대해서는 DRAM이 경쟁력이 있다. 그리고, 이들간의 경계는 시간이 지남에 따라 위쪽으로 이동하는 경향을 보인다. 이러한 경계의 이동은 DRAM의 경쟁력이 갈수록 커짐을 의미한다. 


 낮은 접근지연시간은 또한 온라인 트랜잭션 처리 비용을 줄이는데 큰 도움을 준다. 
예를 들어 일관성을 보장하는데 드는 비용, 즉 특정시간에 동시 수행되는 트랜잭션의 수(overlapping transactions)를 O라고 할 때 이는 새 트랜잭션의 도착비율(arrival rate) R과 각 트랜잭션의 운용기간(duration) D의 곱으로 간략히 표현할 수 있다.   O ~ R*D .
동시 수행되어야  할 트랜잭션의 수가 많을 수록 그만큼 트랜잭션들의 일관성을 보장하기위한 비용은 더 높아질  것이다. 
R 즉 새 트랜잭션의 도착 비율은 시스템의 스케일이 커가면서 계속 커지게 된다.
하지만, D 각 트랜잭션의 운용기간은 접근지연시간이 낮아짐에 따라 크게 개선되며 따라서 동시수행되는 트랜잭션 수를 줄어줄 수 있다. 사실 이러한 아이디어는 이전부터 메모리 상주형 DBMS(memory-resident DBMS 또는 in-memory DBMS)라는 형태로 구현되어 왔다. 하지만, 메모리 상주형 DBMS가 단일 또는 몇개의 노드를 이용하는 것에 국한되었던 것에 비해 램클라우드는 최소 수백대의 노드들의 메모리를 하나의 virtual storage로 보고 여기에 데이터를 저장시킨다는 점이 차이가 있다.

그렇다면 디스크 전체를 메모리로 대체하는 경우 그 비용은 어떨까? 비현실적이지는 않을까?
여기에 저자들이 조사한 간단한 통계정보가 있다.
 


2009년 당시 Amazon과 UA에서의 데이터량과 그당시의 메모리 가격을 가지고 해당 데이터를 모두 메모리에 얹기 위해서 소요되는 비용을 계산해 보았더니, Amazon의 경우 적게는 2.4만불에서 24만불 정도가 소요될 거라 한다. UA의 데이터는 그보다 더 작을 것이라 한다. 
즉, 메모리는 HDD나 SSD에 비해 빠를 뿐더러 I/O집중인 작업에 보다 싸면서 효과적일 수 있다는 것이다.

그렇다면 메모리 캐싱하고 이 램클라우드하고는 어떻게 틀린가? 인터넷 규모의 서비스를 제공하는 ISP들은 Memcached와 같은 분산 메모리 캐싱을 지원을 한다.  2009년 페이스북은 약 4,000개의 MySQL 서버를 이용해서 데이터 요청을 분산하였다 한다. 작업부하의 분산은 페이스북 자체의 코드로 이루어졌다고 한다. 그러다 이또한 바로 한계에 봉착해서 2,000개의 memcached 를 투입하였다고 한다. 
사실 램클라우드는 인터넷 규모의 서비스 제공에 있어 확장성(scalability)을 제공하기 위해 분산 메모리 구조를 지원한다는 점이서는 memcached와 같은 기존 분산 캐싱 기술들과 크게 유사해 보인다. 차이점은 램클라우드는 캐싱이 아닌 아예 데이터를 통채로 메모리에 올리겠다는 것이다. 페이스북 사례와 같은 경우에는 캐쉬된 데이터와 MySQL에 저장된 실 데이터 간의 불일치에 따른 일관성 유지에 따른 관리의 복잡성이 대두될 수 있다. 또한, 데이터가 캐슁되지 않은 경우에는 결국에는 디스크 접근을 필요로 한다. 데이터 접근의 분데이터가 메모리에 캐싱되어 있다면 메모리 접근지연시간을 보장할 수있지만 만약 해당 데이터가 메모리에 캐싱되어 있지 않으면, 디스크에 접근을 하면서 그만큼 접근지연시간이 늦어질 것이라는 점 때문이다.  

단일 사이트에서 동작하도록 설계된 DBMS의 제한된 확장성의 문제는 여러 곳에서 이미 지적된 바 있다. 이러한 문제를 해결하기 위한 현재의대표적인 기술은 NoSQL이라 볼 수 있다. 하지만 NoSQL은 확장성을 위해 기존의 DBMS가 가졌던 주요한 기능, 관계형 모델 대신 단순한 key-value model과 제한된 일관성 지원 정책 등의 한계를 또한 갖는다. 그리고 이들 또한 대부분 디스크에 기반한 저장소를 기준으로 설계되어 있으며, 관계형 DBMS만큼 범용적이지도, 호환적이지도 않다라고 저자들은 언급한다.

RAMCloud는 이러한 문제들을 해결하면서, 보다 큰 확장성과, 더짧은 접근지연시간을 제공하는 범용의 저장 시스템을 제공하기 위해 고안되었다. 

하지만, 이렇게 모든 데이터를 메모리에 올려놓았을때 문제점은 메모리 자체의 휘발성에 따라 장애 시 데이터가 유실될 수 있다는 점이다. 이에 대한 해결책은 크게 다른 데이터 노드에의 메모리에 데이터를 복제해 두거나 디스크에의 로깅을 생각해 볼 수 있다.

데이터들을 복제해서 모두 메모리에 두는 방식은 synchronous I/O를 가지고도 고성능을 보장할 수 있는 장점이 있지만, 상대적으로 비싼 DRAM이라는 저장장치의 공간을 크게 낭비하게 된다.
반대로, 데이터의 복제나 로그를 디스크에 위치시키는 것은 디스크의 접근지연시간에 따른 비효율성을 피할 수 없다. 때문에 이들은 메모리에의 로그 복제와, 메모리에서 디스크로의 비동기적인 data flushing을 통해 이 문제를 해결하려고 하고 있다.

아래 그림은 초기에 저자들이 생각하는 내고장성을 지원하기 위한 방법을 도식화한것이다. 

데이터에 대한 쓰기 연산은 마스터 노드의 메모리 상에서 바로 처리하고, 그에 따른 로그 엔트리들은 다른 노드들의 메모리에 임시적으로 위치시킨다. 그리고, 비동기적으로 각 노드의 메모리에 저장된 로그 데이터를 디스크에 기록한다.  


하지만, 아직 어떠한 방식으로 장애에 대한 내고장성을 지원하는지에 대해서는 구체적으로 연구결과를 내놓았다고 보기 어렵다. 아직까지는 이 연구는 실제 적용된 시스템이라기 보다는 일종의 비전에 가깝다. 하지만, 기술의 트렌드는 저자들이 생각하는데로 변화해 나갈것이라 생각된다.

RamCloud에 대한 간단한 소개와 그들의 프로젝트 홈페이지는 아래와 같다.

written by bart7449

  1. The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time, ACM SIGMOD Record, 1987 [본문으로]
  2. The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, 1997 [본문으로]
  3. The five-minute rule 20 years later (and how flash memory changes the rules), ACM Queue, 2008 [본문으로]
Posted by Bart
CS 전공/리뷰2012. 1. 6. 10:49


지난 1월 5일 SKKU에 가서 한 발표 자료입니다.
MapReduce의 기본 원리와 특성들, 그리고 해당 프레임워크의 장단점과
개선 연구들을 다루었습니다.
뒷부분의 저희 연구내용 소개는  아직 출판이 안된 관계로 일부 뺐습니다.
Posted by Bart
CS 전공/리뷰2011. 7. 9. 16:29


M. Stonebraker는 J. Gray와 함께 존경받는 DB 계의 두 guru 중의 한분입니다. 이제는 68세의 고령 임에도 아직도 현역으로 왕성한 활동을 하는 분이죠. 과거 버클리 교수로 재직시 Ingres/Postgres와 같은 DBMS 개발에 앞장섰고 퇴직 후 지금은 MIT 겸임교수로, 여러 벤처기업의 투자와 자문을 통해 Vertica나 VoltDB, SciDB같은 여러 DBMS들의 개발에도 참여해 왔습니다. 실무자들에게는 MapReduce를 초기에 D. DeWitt과 함께 신랄하게 깐 양반으로도 유명하지요.

어찌되었던 이 분의 기본적인 생각은  기존 DBMS 벤더들의  One Size Fits All 정책, 즉 모든 기능들을 DBMS가 제공하는 것은 더이상 효과적이지 못하다라는 것이고, 이러한 생각을 3편의 논문으로 연달아 발표하기도 했습니다[각주:1][각주:2][각주:3]. 대표적인 시장이 데이터 웨어하우징 마켓인데요. 데이터 웨어하우스에서는 분석 업무가 주가 되기 때문에 쓰기보다는 읽기가 상대적으로 훨씬 많은 작업 패턴을 보이고 이에 따라 읽기 I/O를 줄이는 것이 중요 이슈입니다. 이를 위해서 기존의 행 단위의 레코드 기록을 하던 DBMS를 열 단위 레코드로 변환하는 컬럼 DB가 웨어하우스 시장에 많이 보급되었지요.  최근의 DBMS 시장 동향은 예전에 올렸던 도 잠깐 살펴보시고요.

이 분이 DW 시장에 대한 자신의 10가지 주장(assertion)에 대한 얘기를 했는데, 여기에서는 그에 대한 간단한 요약을 해볼까 합니다.(본문은 여기에서 확인).

1. Star 또는 snowflake schema는 DW에서 좋은 아이디어.
 - 스키마가 이런 모습이 아니라면 뭔가 이상한거임.
 
2. column store 들이 DW 시장을 row store를 점진적으로 대체할 거임.
 - 가령 200 개의 컬럼을 갖는 행 기반 스토어에서는 1컬럼 값을 읽으려 해도 한행을 load 해야 하므로 199개의 낭비. 본질적으로 읽기 연산에서는 row store가 column store보다 우수할 수가 없다.

3. 데이터 웨어하우스는 메인 메모리나 플래시 메모리에 기록할 대상이 아니다.
 - 데이터의 증가 속도는 스토리지의 비용 감소속도보다 더 빠르다.

4. 대용량 병렬 처리(MPP) 시스템은 DW 시장에서 매우 대중적이 될 것이다.(omnipresent)
  -  "Don't bet on anything that is not in the MPP camp."

5. 자동화된 튜닝이 중요하다.
  -  DW 시장에서는 인건비가 최대 비중. 이 인건비란 시스템과 DBMS 관리에 필요한 인력의 인건비를 의미.   - 자동화된 튜닝 시스템을 만드는 것이 결과적으로  중요.

6. 어플라이언스는 단지 SW 만이어야 한다.
  -  본인의 40년 DBMS 경험에 비추어 특화된 DB 머신이 이기는 경우를 아직 보지 못했다.
 -  범용 머신을 제작하는 벤더들은 DB 머신을 제작하는 곳보다 훨씬 많고, 그만큼 가격도 훨씬 저렴하다. 
 - 본인 경험으로는 DB 어플라이언스란 HW + 패키징 사례로 생각된다. 미리 설정된 범용의 HW와 거기에 미리 잘 조직화되어 적재된 DBMS

7. One size fits all DBMS은 복합적인 작업들을 지원하지 못한다. 
 -OLTP와 OLAP를 한 DBMS에서 모두 잘 지원한다는 것은 어려운 일이다.

8.  필수적으로 DW는 고가용성을 지원해야 한다.

9. DBMS는 온라인 프로비저닝 기능을 제공해야 한다.
 - 운영 중에 노드 추가/삭제가 가능해져야 한다.

10. 가상화는 DBMS 세계에서는 성능 문제를 야기한다.
 - CPU 자원은 약간의 오버헤드를 가지고 가상화한다 하더라도, DW는 디스크 I/O가 중요하다. 따라서 물리적인 데이터 배치 정보 등이 디스크 I/O를 향상시키기 위해 중요한데 가상화는 이를 가린다. 
- 가상화의 이점 또한 많지만, 가상화된 I/O는 싸지 않다.

몇 개(2,6, 10)는 논쟁 거리가 될 소지가 좀 보이기도 하는군요. 언제나 CACM에서 M. Stonebraker의 글을 소개할때마다 열띤 논쟁이 벌어지는데요. 에디터가 실을때 마다 하는 얘기 중에 이사람의 글을 오래된 경험자의 글로써 존중 또는 생각되어야 한다는 글귀가 있습니다. 물론, 여러 벤처기업들과의 금전적인 관계가 있기는 하지만..

 

  1. One size fits all: An idea whose time has come and gone, M Stonebraker… - Data Engineering, 2005. ICDE [본문으로]
  2. One size fits all? Part 2: Benchmarking results, M Stonebraker, C Bear, U Çetinteme, CIDR 2005 [본문으로]
  3. The end of an architectural era:(it's time for a complete rewrite), M Stonebraker, S Madden, DJ Abadi,... VLDB 2007 [본문으로]
Posted by Bart
CS 전공/리뷰2011. 6. 6. 21:04
사실 1부에서 다루지 않았던 MapReduce의 성능 개선이나 개량 모델들에 대한 설명을 2부에서 하고 싶었습니다만, 시간 관계상 그게 여의치가 않았습니다.
해서, MapReduce 관련한 survey를 최근에 작성한 것이 있는데 그것으로 땜빵(?)을 할까 합니다.
혹 관심가지고 글을 기다리셨던 분이 계시다면 시간관계상 한글로 번역해서 올리지 못하는 점 죄송합니다.



 
 

Posted by Bart
CS 전공/리뷰2011. 3. 31. 14:08
DB 구조 쪽으로 떠오르는 신성 D. Abadi 교수가 Hadapt라는 회사를 차렸군요. Hadapt는 HadoopDB의 상용화 버전을 만드는 벤처입니다. HadoopDB는 MapReduce의 오픈소스 버전인 Hadoop을 연결 계층으로 이용하여 단일 노드의 DBMS들을 엮는 비공유 구조의 데이터 처리 시스템입니다.
달리 얘기하면, Hadoop에서 파일 시스템 대신에 DBMS를 이용한다고도 할 수 있습니다.

HadoopDB는 MapReduce의 장점인 확장성(scalability)을 그대로 유지하면서, Hadoop의 떨어지는 성능을 노드 단위의 DBMS의 우수한 성능으로 보완하자는 의도로 만들어진 시스템입니다. MapReduce의 성능이 좋지 못한 이유에 대해서는 이전 블로그 글를 참고하시고요. 이 시스템은 PostgreSQL을 하위 DBMS로 활용을 했는데 Hadapt에서는 VectorWise라는 DBMS를 이용했습니다.  아마 Connector들을 더 추가해서 다른 DBMS들도 지원을 할 것은 확실한 것 같고요.

그런데, 재미있는 것은 이 VectorWise에 관여되어 있는 사람이 또 Peter Boncz라는 겁니다. 이 사람 또한 컬럼-기반 DBMS인 MonetDB를 가지고 연구를 많이 한 사람이고요. 거기에 메모리 계층을 고려한 DB 연산의 최적화도 같이 접목시키는 연구를 많이 했죠. 어쨌든 VectorWise는 Ingres에 판권을 맡기고, 만드는 컬럼-기반 DBMS입니다. 컬럼 DBMS는 I/O를 줄이기 위해 기존 행-단위 기록을 했던 방식을 반대로 컬럼(열)-단위로 바꿨습니다. 즉 1행, 2행, 3행 식으로 디스크에 기록을 하는 것이 아니라, 첫번째 열값, 두번째 열값, 세번째 열값 순으로 기록을 합니다. 이렇게 하면 질의 처리 시, 특히 selection 연산의 경우 모든 행들을 읽어서 그중 selection할 대상이 되는 컬럼만 추리는 방식에서 대상이 되는 컬럼만 디스크에서 읽게 함으로써 많은 I/O를 줄일 수 있습니다. 특히 OLAP 업무에 특히 적합한 저장 방식입니다. 이 컬럼-단위 저장에도 몇가지 방식이 있는데 그중 PAX라는 페이지 저장 방식[1]이 주로 활용됩니다. 여기에 더해서 데이터 압축도 합니다. 근래의 컴퓨팅 시스템은 컴퓨팅 사이클보다 디스크 지연시간이 훨씬 bottleneck이기 때문에 압축과 압축해제에 소요되는 컴퓨팅 비용보다 디스크 I/O 때문에 잡아먹는 비용이 더 클 수 있다는 근거로 이런 선택을 한 것이고요.
 재미있는 것은 D. Abadi도 C-Store라는 이름의 컬럼-기반 DBMS를 박사학위 주제로 했던 사람이었다는 거죠(C-Store는 Vertica라는 이름으로 상용화가 되었고, 이 회사는 최근에 HP에 인수됩니다.) 아마 같은 주제를 해왔던 사람이라 다른 컬럼-기반 DBMS를 제치고 썼는지도 모르지요.

아무튼, MapReduce에서 보면 데이터 처리에 있어 I/O 비용이 굉장히 높아서 이를 줄임으로써 throughput을 향상시키려고 할 것이고요. 둘 다 주목적이 데이터 분석이나 처리 업무에 있고, OLTP에 있지 않으니, 둘의 결합은 매우 훌륭하다고 생각됩니다. 

참고로 좀더 알아보니 컬럼-기반 DBMS 를 만드는 회사들이 몇개 더 있군요.
InfoBright라는 회사는 MySQL 기반으로 컬럼 기반 DBMS를 만든다고 하고, 학계에서 만든 시스템으로는C-Store나 MonetDB를 이용해 볼 수 있습니다. 더 많은 리스트는 http://en.wikipedia.org/wiki/Column-oriented_DBMS에서 확인해 볼 수 있습니다.

그나저나 작금의 DBMS 시장은 정말 알게모르게 요동치는 듯 하네요. OLTP에서의 강자들 Oracle과 IBM, MS들은 그대로 있지만, 시장이 점차 커지고 있는 데이터 분석 분야에 신흥 업체들이 계속 출현하고, 또 여러 공룡 업체에 인수되는 현상들이 계속 보입니다. 
Netteza는 IBM에게 Vertica 는 HP에게, Greenplum은 EMC에 Aster는 Teradata 에게 인수되는 등 아주 요동칩니다. 창업과 기업인수가 활발한 미국의 IT 업계가 부럽네요. 

 [1] 
“Weaving Relations for Cache Performance” by Natassa Ailamaki, David DeWitt, Mark Hill, and Marios Skounakis, VLDB Journal, 2001

written by bart7449 
Posted by Bart
CS 전공/리뷰2011. 3. 25. 00:44
목 차
1. 데이터 센터와 클라우드 컴퓨팅
2. MapReduce
3. MapReduce에 관한 논쟁: 장점과 단점
4. MapReduce 개선에 관한 연구들
5. 연구 분야와 도전 과제들
6. 결론 및 향후 전망
관련 연구 


 

1. 데이터 센터와 클라우드 컴퓨팅

 
 
컴퓨터 구조학의 대가인 UC버클리 대 교수 David A. Patterson이 “데이터 센터가 곧 컴퓨터”라고 언급한 바와 같이 현재의 컴퓨팅은 개인이 소유한 PC를 이용한 컴퓨팅에서 데이터 센터가 보유한 무수히 많은 서버들을 이용하여 컴퓨팅을 임대, 사용하는 클라우드 컴퓨팅 으로 빠르게 넘어가고 있다[1].

클라우드 컴퓨팅은 “최소한의 관리만으로 빠르게 제공, 해제될 수 있는 조정 가능한 컴퓨팅 자원의 공유 풀을 접근할 수 있는 요구 중심의 네트워크 접근을 위한 모델”[2]로 정의한다. 클라우드 컴퓨팅을 위한 데이터 센터에서는 많은 계산이 요구되는 대용량 데이터를 많은 저가의 범용 x86 머신에 분배하여 병렬 처리하는 방식으로 확장성(scalability)를 제공한다. 이와 유사한 개념으로 기존에도 그리드 컴퓨팅과 같은 개념이 존재하였지만, 클라우드 컴퓨팅은 데이터 센터라는 지역적으로 집중된 한 곳에 많은 PC들을 설치해놓고 컴퓨팅을 대여, 이용한 만큼 과금한다는 점에서 자발적인 참여와 노드들이 서로 다른 관할권에 속하는 그리드 컴퓨팅과는 구별된다.  

MapReduce[3]는 이러한 데이터 센터 중심의 컴퓨팅에서 “첫 번째 명령어” [1]라고 언급될 정도로 여러 분야 특히 대용량 데이터 분석 및 처리 분야에서 많은 각광을 받고 있다. 2009년 한해 구글에서는 총 3,467K 개의 작업을 평균 488개의 노드를 이용해 처리했다고 밝혔다. 한 해에 데이터는 총 544,130 TB에 이르렀다 한다[4]. MapReduce의 오픈 소스 Java 구현인 Hadoop 또한 많은 분야에서 널리 이용되고 있다[5].
 

 2. MapReduce

MapReduce는 Google에서 정보 검색을 위한 데이터 가공(색인어 추출, 정렬 및 역 인덱스 생성 등)을 목적으로 개발된 분산 환경에서의 병렬 데이터 처리 기법이자 프로그래밍 모델이며, 또한 이를 지원하는 시스템이다[3]. MapReduce는 비공유 구조(shared-nothing)로 연결된 여러 노드 PC들을 가지고 대량의 병렬 처리 방식(MPP; Massively Parallel Processing)으로 대용량 데이터를 처리할 수 있는 방법을 제공한다.  이를 보다 간편하게 하기 위해 MapReduce는 LISP 프로그래밍 언어에서의 map과 reduce 함수의 개념을 차용하여 시스템의 분산 구조를 감추면서 범용 프로그래밍 언어를 이용해 병렬 프로그래밍을 가능하게 한다.

 즉, MapReduce에서는 단순히 Map과 Reduce라는 두 함수의 구현을 통해 데이터 처리를 병렬화할 수 있다. Map과 Reduce가 수행하는 동작은 아래와 같다.

 

Map: (key1, value1) -> (key2, value2)    //(key, value) 쌍을 읽어 다른 (key, value) 쌍에 대응

Reduce: (key2, List_of_value2) -> (key3, value3)   //key2를 기준으로 취합된 value list를 읽어 집계된 값 value 3를 출력


즉, Map 함수는 임의 키-값 쌍을 읽어서 이를 필터링하거나, 다른 값으로 변환하는 작업을 수행하고, Reduce 함수는 Map 함수를 통해 출력된 값들을 새 키 key2를 기준으로 그룹화(grouping) 한 후 여기에 집계 연산(aggregation)을 수행한 결과를 출력한다. 이는 기존 SQL DBMS에서 selection 연산 후 group-by-aggregation을 수행하는 것과 유사하다고도 할 수 있다. 하지만, MapReduce는 이 간단한 두 함수를 이용해 여러 노드들을 대상으로 데이터를 병렬 처리할 수 있는 특징을 가진다.

 그림 1은 MapReduce의 처리 흐름을 나타낸다. 분석할 입력 데이터는 분산 파일 시스템인 GFS(Google File System)[6] 위에 먼저 적재되고, 이 때 데이터는 기본 64MB 크기의 여러 데이터 청크(chunk)들로 분할된다. GFS는 각기 분할된 청크들에 대해 장애로부터의 복구를 위해 2개의 추가적인 복사본을 생성하며 이들을 클러스터를 구성하는 각기 다른 노드 PC들에 위치시킨다.


 


그림 1. MapReduce의 처리 흐름


 
MapReduce 수행 시 이 GFS 상에 적재된 각 청크들은 Map 함수를 수행하는 Mapper 태스크들에 할당된다. Mapper들은 클러스터 상의 여러 노드들에 분산되어 있으며 각기 청크 하나를 받아 Map 함수를 수행하고 그 결과는 Mapper가 수행된 노드의 로컬 디스크에 기록한다. 만약 처리할 청크가 아직 있으면 실행 중에 이미 종료되어 유휴한 Mapper에게 추가로 청크를 할당한다. 이런 방식은 일찍 작업을 종료한 Mapper가 더 많은 청크를 입력받아 처리하도록 함으로써 적절히 부하를 분산시키는 런타임 스케쥴링 효과를 갖는다. 더 이상 처리해야 할 청크가 없고 모든 Mapper가 정상 종료되었다면, MapReduce의 스케쥴러는 Reducer 태스크를 수행한다.
 

 Reducer HTTPS를 이용해 여러 노드들로부터 Key2를 기준으로 각 reducer가 처리해야 할 키-값 쌍을 이전 Mapper들의 로컬 디스크로부터 읽어온다. 이는 집계 연산을 위해 Map 결과를 추가적으로 분할하기 위한 것으로 일반적으로 hash(key2) mod n과 같은 해시 분할을 이용하여 데이터를 n 개의 reducer에 분할시킨다. 이후 key2 값을 기준으로 정렬 연산을 수행하고, 이렇게 해서 정렬된 키-값 쌍들을 동일 키 값을 기준으로 그룹화를 수행한다. 이렇게 해서 각 key2 값을 기준으로 그룹지어진 값들을 대상으로 집계 연산을 수행하고 그 결과를 다시 GFS 상에 다른 키-값 쌍으로 출력한다.
 

Mapper들은 선택적으로 combiner를 가질 수도 있다. 이는 Mapper가 키-값 쌍만을 출력하고 이를 Reducer가 복사, 분할하는데 드는 I/O와 네트워크 대역폭을 절감하고자 각 Mapper가 출력하는 키-값쌍에 대해 미리 그룹화하고 집계 연산을 수행하도록 하는데 이용된다(pre-aggregation).

  데이터 처리 중에 장애 발생 시 Mapper의 경우 같은 청크를 대상으로 다시 수행하거나, 또는 유휴한 다른 Mapper가 해당 청크를 수행하게 함으로써 내고장성을 지원한다. Reducer의 장애의 경우에는 Mapper의 결과는 이미 로컬 디스크에 Mapper의 결과가 실체화된 상태이므로 Mapper의 수행은 건너뛰고 Reducer 작업을 다시 수행한다. 파일의 내구성은 GFS의 데이터 복제에 의존한다.
 

 MapReduce에서는 또한 2 개 이상의 MapReduce 작업을 서로 연결함으로써 보다 복잡한 알고리즘을 구현하는 것도 가능하다. 즉 한 MapReduce 작업이 종료된 후 두 번째 MapReduce 작업이 GFS상의 첫 작업의 결과를 입력으로 하여 동작하는 방식이다. 이 경우에도 각 Map, Reduce 단계의 결과들은 모두 로컬 디스크 또는 분산 파일 시스템 위에 기록됨으로써 내구성이 보장된다.
 

 3. MapReduce에 관한 논쟁: 장점과 단점

MapReduce의 인기에 대해 데이터베이스 연구자들, 특히 병렬 DBMS를 연구해 왔던 학자들은 많은 비판을 가하였다. DBMS 진영의 대표적인 학자들인 M. Stonebraker D. DeWitt MapReduce“A Major Step Backward”라고 비판한 바 있다[7]. 이들은 MapReduce에서의 데이터 병렬 처리 기법은 이미 기존 병렬 DBMS에서 이미 해왔던 것이며, DBMS에서 지원하는 많은 기능들, 예를 들어 스키마, 표준 질의어, 인덱스 기법, 질의 최적화, 압축, 여러 데이터 분할 기법 등 이 빠져 있다고 비판하였다. 이후 2009 SIGMOD에는 이들과 MIT Sam Madden 팀이 같이 Hadoop과 행-기반 DBMS와 열-기반 병렬 DBMS의 성능을 Grep TPC-H 연산 등을 대상으로 비교한 논문을 발표하였다[8]. 여기에서는 데이터 적재 시간을 제외한 나머지 모든 작업에서 MapReduce DBMS, 특히 열-기반 병렬 DBMS보다 못하다라고 언급하였다. MapReduce를 옹호하는 진영은 주로 산업계에서 종사하는 실무자들로 이 비교가 DBMS로 수행하기 좋은 작업들을 대상으로 하였다고 반박하였다. 그들은 MapReduce의 용도는 DBMS와 다르며, 데이터의 일괄 병렬 처리를 위한 시스템으로써 그 의의가 크다고 설명하였다. 반대로 DBMS 진영에서는 연구자들을 중심으로 MapReduce는 이미 연구되었거나 DBMS에서 이미 지원하고 있는 병렬 처리 기법이나 데이터 처리 기법들을 고려하지 않은 매우 순진한(naïve) 시스템이라 비판하였다. 이 기술적 논쟁이 가열되자 ACM에서는 이 두 진영의 의견을 학회지 CACM 2010 1월호에 나란히 올려 이 논쟁을 소개하였다[9, 10]. 

두 진영에서 서로 언급하고 있는 MapReduce의 장단점을 요약하면 다음과 같다.
 

 3.1. MapReduce의 장점

1) 단순하고 사용이 편리

MapReduce는 먼저 Map(), Reduce()라는 두 개의 함수를 구현함으로써 병렬 처리를 가능하게 한다는 것이 큰 장점이다. 데이터의 분산 배치와 실행은 스케쥴러가 담당함으로써 사용자는 분산 시스템의 물리적 구조를 알지 않아도 데이터 병렬화(data parallelism) 방식을 통한 분산 처리를 매우 쉽게 할 수 있는 이점이 있다.
 

 2)  유연성

MapReduce는 특정화된 데이터 모델이나 스키마 정의, 질의 언어에 의존적이지 않다. 사용자는 범용의 프로그래밍 언어를 이용하여 데이터를 어떻게 처리할지 기술한다. 따라서 관계형 데이터 모델로는 표현되기 어려운 다르거나, 비정형적인 데이터 모델들도 지원할 수 있는 유연성을 갖는다.

 3)  저장 구조와의 독립성

MapReduce는 병렬 데이터 처리를 위한 시스템으로 하부 저장구조와 독립적이다. 기본적으로는 MapReduce GFS와 같은 분산 파일 시스템 상의 파일을 입출력으로 하지만, 그외 일반 파일 시스템이나 DBMS 등 다른 저장 구조를 하부에 두는 것도 가능하다.

 4) 내고장성

MapReduce는 분산 파일 시스템의 데이터 복제(replication)에 기반한 데이터의 내구성(durability) 지원과 함께 Mapper Reducer의 태스크 장애 시 각 태스크의 재수행을 통해 장애로부터의 내고장성을 확보한다. 이 때 Map Reduce 작업이 처음부터 다시 실행되는 것을 막기 위해 Map의 결과는 Mapper가 수행된 노드의 로컬 디스크에 기록된다.
 

 5) 높은 확장성(scalability)

MapReduce의 오픈 소스 구현인 Hadoop 4,000 노드 이상으로 확장될 수 있을 정도로 높은 확장성을 가진다[11]. 처리해야 할 데이터 크기가 커지면 그만큼 높은 작업처리량(throughput)을 가지도록 시스템을 개선해야 한다. 기존의 방식은 HW 성능의 개선을 통해처리량을 향상시키는 scale-up 방식이었던 반면에, MapReduce는 저가의 범용 PC들을 추가로 할당함으로써 확장성을 지원하는 scale-out 방식의 구현을 용이하게 한다.


 3.2. MapReduce의 단점

1)  고정된 단일 데이터 흐름

Map Reduce만을 정의하도록 한 MapReduce는 단순한 인터페이스를 제공함에 반해, 복잡한 알고리즘이나 selection-then-group-by-aggregation 작업이 아닌 알고리즘에서는 효율적이지 않다. 대표적인 것이 Join과 같은 이항 연산자(binary operator)의 지원이나 Loop의 지원이다. MapReduce에서는 이항 연산자를 지원하지 않았다. 때문에 Join은 하나의 MapReduce 작업으로 표현되지 못하고 여러 개의 MapReduce 작업을 직렬로 연결해 표현해야만 했다. Loop의 경우도 매 반복 때마다 계속 입력을 반복해서 읽어야 하는 등의 I/O 낭비가 심하였다. , MapReduce에서는 DAG(Directed Acyclic Graph) 형태로 자신의 워크플로우를 따로 정의하는 작업은 불가능하며, 복잡한 알고리즘의 구현을 위해서는 여러 번의 MapReduce 작업을 수행해야 하는 불편함과 그에 따른 성능 저하가 많다. [12]는 어떻게 반복적인 작업을 MapReduce가 비효율적으로 수행할 수 있는지에 대한 대표적인 예가 될 수 있겠다.
 

 2)  스키마, 인덱스, 고차원 언어 등의 미지원

 MapReduce는 병렬 처리에 대한 두 인터페이스를 제공하는 것 이외에 기존의 DBMS가 제공하는 스키마나 질의 언어, 인덱스 등을 제공하지 못한다. 스키마는 데이터의 무결성(integrity)를 지원하는데 있어서 중요한데, 이의 미비는 결국 프로그램 로직 상에서 무결성을 검증하도록 하게 한다. 이런 경우 프로그램도 복잡해지려니와 하부 데이터 형식의 변경은 프로그램 로직의 변경을 야기하고, 매번 데이터를 읽을 때마다 파싱을 수행해야 하는 부담도 갖는다. SQL과 같은 질의 언어의 미지원도 또한 질의 형식의 재활용이나 손쉬운 질의의 작성을 어렵게 한다. 인덱스는 질의 처리 성능의 향상을 위해 중요하지만 MapReduce는 인덱스를 지원하지 않으며, 데이터의 일괄 처리만을 제공한다. 때문에 DeWitt Stonebraker등은 MapReduce를 단순한 LTE(Load-Transform-Extract) 도구로만 처음에 언급하였다[7].
 

 3)  단순한 스케쥴링

 MapReduce는 기본적으로 런타임 스케쥴링에 기반한다. Hadoop의 예에서, 런타임 스케쥴링에서는 태스크를 수행하는 경우는 1) 실패한 태스크를 재수행하거나 또는 2) 아직 수행되지 않은 태스크를 수행하는 경우 또는 3)태스크가 매우 느린 경우이다.  특히 3)의 경우는 임계값을 설정해 두고 일정 시간 동안에 임계값을 도달하지 못하는 경우 straggler로 판정하고 이를 다시 수행시키는데, 노드 PC 성능이 상이한 경우 이 과정이 효과적이지 못하다.

더불어 한 클러스터에서 여러 MapReduce 작업을 동시에 수행하는 경우에 대해서 효과적인 다중-작업 스케쥴링을 제공하지 못한다.
 

 4)  상대적으로 낮은 성능

 MapReduceDBMS와 비교해 상대적으로 낮은 성능을 보인다. 이러한 시스템에서의 성능 측정은 대개 단위시간당 작업처리량(throughput)이나 시스템의 효율성(efficiency) 등으로 측정할 수 있다. [8]에서 보인 바와 같이 MapReduce는 다른 병렬 DBMS에 비해 데이터 적재 시간 이외에 우수한 성능을 보이지 못했다. DBMS의 경우 테이블에의 적재 이외에 인덱스 생성 시간 등이 소요되어 더 많은 시간이 소요되었다. [14]의 연구는 MapReduce를 이용한 병렬 정렬 연산에 있어 한 노드의 작업처리량이 5MB/sec에 못 미침을 보인다.

 MapReduce의 이러한 낮은 성능은 내고장성 지원을 위해 디스크 I/O를 희생하는 태생적인 이유에 근거한다. 우선 파일을 보관하는 분산파일 시스템은 2개의 replica를 추가로 가짐에 따라 디스크 공간과 I/O를 소비한다. 복제된 이후 읽기 연산은 각기 다른 복사본에 접근함으로써 병렬화를 꾀할 수는 있지만, 대신에 출력의 경우는 한 데이터를 가지고 여러 노드에 분산, 기록해야 한다.
또한 각 태스크는 수행 결과를 다음 태스크에 전달하기 이전에 태스크를 수행한 노드의 로컬 디스크 또는 분산 파일 시스템 상에 기록하는 과정을 먼저 수행한다. 이러한 추가적인 I/O는 DBMS에서는 존재하지 않던 것이었다. 예를 들어 다음과 같은 질의가 있다고 하자.

select distinct b.Name, avg(e.Salary)
from employee e, branch b where

b.Id= e.branchId and b.State ="AZ" 
groupby b.id

이 질의는 애리조나 주에 있는 지점들의 종업원의 봉급 평균을 지점별로 분류해서 출력하도록 한다.
이 질의에 대한 DBMS에서의 질의 플랜은 아래와 같다.

그림 2. 질의 플랜 트리

DBMS에서는 이러한 질의 플랜 트리의 수행에 있어 각 연산자가 다음 연산자에 데이터를 전달하기 전에, 데이터를 디스크에 기록한 다음 전달하지 않는다. 디스크 I/O를 가장 큰 비용으로 산정하여 디스크 I/O를 최대한 줄이고자 노력했기 때문이다. 반대로 MapReduce는 매번 연산자가 다음 연산자에 데이터를 전달 전에 디스크에 기록을 먼저 한다. Map은 로컬 디스크에 기록하고, Reduce는 분산 파일 시스템 위에 기록한다. MapReduce가 이러한 방식을 취하는 이유는 간단하게 내고장성을 지원하기 위해서이다. 반대로 디스크 I/O 때문에 성능은 더디어질수밖에 없다. 
 

여기에 더해 MapReduce 태스크들은 블로킹 연산자이다. 예를 들어 모든 Mapper가  종료되기 전까지 Reducer는 시작될 수가 없다. 이는 한 태스크가 느려지면 그 위의 질의 플랜 상의 다른 연산자들이 수행되지 못하고 대기 상태로 기다리게 한다. 그리고 그만큼 전체 실행 시간은 길어진다.
DBMS에서의 질의 플랜 트리는 각 연산자들의 중간 결과를 디스크에 기록하지 않고, 처리하는 족족 위 연산자에 전달한다. 따라서 각 연산자들이 동일시점에 서로 다른 데이터를 가지고 처리할 수 있는 
 파이프라인 병렬화(pipeline parallelism)가 가능하다. 하지만, MapReduce에서는 이와 같은 같은 병렬화를 수행할 수 없고 하나의 늦은 태스크(straggeler) 때문에 전체 작업이 지연될 수 있다
.
물론 DBMS에서도 Sort 같은 블로킹 연산자들은 존재한다. 하지만, 보다 많은 파이프라인 병렬화를 지원한다.

또한 MapReduce는 인덱스를 지원하지 않고, 데이터를 일괄로 읽음에 따라 I/O를 절약하기 곤란하다. 위의 그림에서 scan 시 인덱스를 이용한 입력 데이터의 생략을 MapReduce는 기대할 수 없었다.

이러한 이유로 MapReduce는 태생적으로 병렬 DBMS에 비해 간단하면서도 내고장성을 지원할 수 있는 반면 상대적으로 낮은 성능을 보일 수 밖에 없다. DBMS 분야에서는 각 연산자의 중간 결과 실체화라는 MapReduce의 가장 큰 특징을 유지하면서 기존의 DBMS에서의 I/O를 줄이기 위한 예전 연구들을 MapReduce에 적용하는 방식으로 성능 향상을 꾀한다. (이는 2부에서 설명한다.)

 5)  상대적으로 어린 시스템

MapReduce40여년의 역사를 가진 DBMS와 비교하여 아직 나온지 얼마 안된 기술임에 따라 여러 개발도구나 BI(business intelligence), 3rd party tool들이 존재하지 않는다. 또한 그 자체도 개선의 여지가 아직 많다. 예로, 오늘까지 MapReduce 논문[3]의 인용횟수는 2,575회이다. 그만큼 인기도 있지만 개선의 여지도 많다고 봐야 한다. 

 
 MapReduce 개선에 관한 연구들과 연구 이슈, 도전 분야는 2부에 계속

 
 

관련 연구

1. David A. Patterson. Technical perspective: the data center is the computer. Communications of ACM, 51(1):105, 2008.

2.   Peter Mell and et al. NIST Definition of Cloud Computing V15, 2009. http://csrc.nist.gov/groups/SNS/cloud-computing

3.   Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data, Processing on Large Clusters, In Proceedings of OSDI 2004 and CACM Vol. 51, No. 1 2008

4.Jeff Dean, Design, Lessons, Advices from Building Large Distributed System, Keynote , LADIS 2009.

5. Hadoop. users List; http://wiki.apache.org/hadoop/PoweredBy

6. S. Ghemawat and et al., The Google File System, In Proceedings of ACM SIGOPS, 2003

7.   David J. DeWitt and Michael Stonebraker, MapReduce: a major step backwards, Database column blog, 2008

8.  Andrew Pavlo and et al. A Comparison of Approaches to Large-Scale Data Analysis, In Proceedings of SIGMOD 2009

9.   Michael Stonebraker and et al. MapReduce and Parallel DBMSs: Friends or Foes?, Communications of ACM, Vol 53, No. 1 pp. 64-71, Jan 2010

10.  Jeffrey Dean and Sanjay Ghemawat, MapReduce: A Flexible Data Processing Tool, Communications of the ACM,  Vol. 53, No. 1 pp. 72-72 Jan 2010

11.  Ajay Anand, Scaling Hadoop to 4000 nodes at Yahoo!, Yahoo! Developer Network, http://developer.yahoo.com/blogs/hadoop/posts/2008/09/scaling_hadoop_to_4000_nodes_a/

12.   J. Cohen, Graph twiddling in a mapreduce world, Computing in Science & Engineering pp. 29—41, 2009, IEEE Computer Society

13.   E. Anderson and et al. Efficiency matters!, ACM SIGOPS Operating Systems Review 44(1):40—45, 2010 ACM

Written by bart7449 

Posted by Bart
CS 전공/리뷰2011. 3. 2. 15:29
 "모든 컴퓨터 아키텍트들은 암달의 법칙을 알고 있다. 그럼에도 불구하고, 우리는 때때로 불가능한 성능 최적화를 위해 막대한 노력을 기울인다. 그리고, 전체 속도향상이 실망스러운 수준임을 확인했을 때에서야 비로소 암달의 법칙을 떠올린다."-In  Computer Architecture: A Quantitative Edition, 4th ed.  John L. Hennessy and David A. Patterson 

"모두들 암달의 법칙을 알고 있지만, 금방 잊어버린다!" - Thomas Puzak

  병렬 처리에 있어 중요한 비교척도로는 속도향상과 효율성이 존재한다. 1개의 프로세서 또는 1개의 노드 추가로 이루어지는 어떠한 알고리즘의 속도향상(speedup)은 다음과 같이 계산된다.
  (식 1)

 여기에서,  n는 프로세서의 수 또는 노드의 수, T1은 직렬 알고리즘의 실행 시간,   Tn 는 n 개의 프로세서 또는 노드를 이용한 병렬 알고리즘의 실행 시간을 의미한다.  속도 향상은 다시 크게 절대 속도향상(absolute speedup)과 상대 속도향상(relative speedup)으로 나뉘는데, 절대 속도 향상은 T1 이 가장 최적의 직렬 알고리즘(best sequential algorithm)의 실행 시간인 반면에, 상대 속도 향상에서는   T1 이 병렬 알고리즘을 한 프로세서에서 실행된 시간이다. 보통 속도향상을 얘기할 때는 상대 속도향상을 의미한다.

효율성(Efficiency)은 한 프로세서 또는 노드가 병렬 처리를 위해 얼마나 잘 활용되는지를 비교하는데 이용된다. 
 (식 2) 

 이상적으로는 병렬 처리에서 속도 향상은 추가되는 n 개의 프로세서 또는 노드의 수에 따라 선형(linear)으로 증가한다. 즉, Speedup(n) = n이 된다.  이 경우 효율성은 1이 된다. 하지만 실제로는 I/O, 네트워크 대역폭(bandwidth), 지연시간(latency) 등 여러 이유로 1이 되지 못한다. 가장 대표적인 이유는 알고리즘의 모든 부분을 병렬화(parallelize) 시킬 수가 없기 때문인데, 이 알고리즘에 남아있는 직렬 처리 부분은 모든 알고리즘의 병렬화의 한계를 결정한다. 이는 암달의 법칙(Amdahl's law)으로 설명된다.  
  

Amdahl's law[각주:1]
 암달의 법칙은 1967년 한 컨퍼런스에서 IBM의 Gene Amdahl이 논한 것으로, 이 공식은 어떤 시스템의 f  비율만큼의 부분이 S만큼 속도향상이 있을 때, 최대로 얻을 수 있는 이상적인 속도향상은 다음과 같이 제약됨을 설명한다. 또한, 여기에서는,  프로그램 수행을 통해 풀고자 하는 문제의 크기가 특정 부분의 속도 향상의 전후에도 언제나 동일한 것으로 가정한다.
 식(3)

1) 만약 속도향상을 이룬 부분이 작다면 (f값이 작다면), 전체 시스템의 속도향상은 미미하다.
2) 만약 f 부분의 속도향상을 무한대(S ∞)로 할 수 있다면, 전체 시스템의 속도향상은 1/(1-f)로 수렴될 수 있다.

예를 들어 전체 시스템의 20%를 2배만큼 속도향상을 시킬 수 있다면, 이로 인해 얻을 수 있는 전체 시스템의 속도향상은:
 (식 4)

로 제한된다. 이 암달의 법칙은 어떠한 프로그램을 병렬화할 때 얻을 수 있는 최대한의 속도향상을 예측하는데 이용되기도 하는데, 이 때는 아래와 같은 형식으로 표현될 수 있다. 
 (식5)

여기에서 f는 프로그램에서 병렬화된 부분을 n은 프로세서 또는 노드의 수를 의미한다.

먼저, 한 프로그램을 하나의 프로세서 또는 노드로 수행시켰을 때의 실행 시간을 1로 한다. 
다음으로 프로그램의 일정 부분 f를 n개의 프로세서나 노드로 병렬화하여 처리한다면, 이 f의 실행 시간은  f/n만큼의 시간이 들게 될 것이다. 반대로, 남은 부분 1-f는 한개의 프로세서 또는 노드로 수행하기 때문에 그대로 원래 만큼의 시간이 소요된다. 즉, 프로그램의 일정 부분 f를 n개의 프로세서나 노드를 이용하여 병렬화하는 경우 전체 수행 시간은 1-f+f/n만큼 소요되고, 이를 원래 시간 1과 비교하면 위의 식 5만큼의 성능 개선이 있다고 설명할 수 있다.

예를 들어, 만약 f=1, n=16, 즉 프로그램의 모든 부분이 병렬화되어 있고,  16개의 프로세서를 이용해 병렬 처리한다면, 속도향상은 16배가 될 것이다. 그리고, 이 경우 효율성은 1(=16/16)이 된다.  하지만, 프로그램의 모든 부분을 병렬화 할 수는 없다. 이런 이유로 실제 프로세서나 노드 수를 늘린다고 해도, 어느 수준 이상에서는 속도향상을 기대할 수 없다.  아래 그림은 암달의 법칙에서 프로세서의 증가에 따른 속도 향상의 한계를 보인다. 

Figure 1a.



그래프를 보면 프로그램의 95%(f=0.95)가 병렬화 되어 있다고 해도, 16개의 프로세서를 가지고 10배 이상의 속도향상을 내지 못한다.  이후로는 아무리 많은 수의 프로세서를 가진다 해도 20배 이상의 속도향상을 낼 수가 없다.  즉, 병렬화 되지 않은 부분이 많을수록 속도향상은 더 적다. 50%의 병렬화를 통해 16 프로세서를 가지고 얻을 수 있는 속도향상은 2배 밖에 되지 못한다. 실제로 프로그램 상에 남아있는 직렬 실행 부분의 비율은 아래 그래프와 같이 병렬화를 통해 얻을 수 있는 속도향상을 제약한다.

Figure 1b.


이러한 이유로 병렬 처리에서 있어서는 프로그램의 직렬화 부분(1-f)를 얼마만큼 줄이느냐, 다른 말로 병렬화 부분(f)을 얼마나 늘이느냐 것이 관건이 되어 왔다. 또한, 실제로는 모든 부분을 병렬화할 수 없기 때문에, 프로세서 수를 계속 늘려도 병렬화의 이점을 추가로 가질 수가 없다. 이에 따라서 병렬 처리는 보통 소수의 프로세서를 가지고서 병렬 처리를 해 왔다.  프로그램의 병렬 부분과 속도향상과의 관계는 위 식에 의해 아래와 유도가 가능하다.
 (식 6)
Gustafson's law[각주:2]
 구스타프슨의 법칙은 1988년 Sandia national Lab에 있던 John Gustafson이  고안한 것으로  규모가 충분히 큰 문제들은 효과적으로 병렬화가 가능함을 기술하고 있다. 이는 암달의 법칙이 병렬화를 통해 일정 수준 이상의 속도향상을 기대할 수 없다고 얘기하는 것에 배치되는데, 그렇다고 암달의 법칙이 틀렸다는것은 아니다. 암달의 법칙은 계속 유효하다. 이 법칙은 아래와 같이 표기된다.  
 (식 7)
 여기에서 n은 프로세서 또는 노드의 수, α는 프로그램에서 병렬화되지 않은 부분을 의미한다(, α= 1-f).
이 법칙에 따르면, 만약 n=16이고 α=0.05이라면(95%가 병렬화 되어 있다면), 얻을 수 있는 속도향상은 15.25배(16-0.05*15) 이다. 이는  동일한 조건에서 속도향상은 10배를 넘지 못한다는 암달의 법칙과 상반된다. 이 이유는 무엇인가?

 암달의 법칙이 병렬 처리에 있어 병렬화 전후의 문제 크기는 변하지 않는 것을 가정하는데 반해, 구스타프슨의 법칙은 고정된 처리 시간 개념을 도입하여 보다 큰 문제에 대한 속도향상을 설명한다. 
 즉, 암달의 법칙에서는 고정된 문제 크기를 갖는다고 가정하였는데, 이는 프로세서 수의 증가에 상관없이 문제 크기는 증가하지 않는 것을 기초로 출발하였다.  아래의 그림을 보자.

 그림과 같이 직렬 시스템에서 프로그램을 실행하는데 걸린 시간은 프로그램의 직렬 부분 s와 병렬화 가능한  부분 p의 실행 시간으로 구성된다. 즉, s+p=1 이 병렬화 이전에 소요된 시간이다. 그리고 병렬화를 통해 얻어진 실행시간은 s+p/N이다. 여기에서 N은 프로세서의 수이다. 따라서 전체 속도향상은 식 1에 따라
1/(s+p/N)이 된다. s를 1-f라 하고 p를 f로 치환하면 위의 암달의 법칙(식 5)와 동일한 수식을 얻게 된다.

 반대로, 구스타프슨의 법칙은 주어진 시간 내에 보다 많은 크기의 문제를 해결하는 경우 병렬화가 효과적인 방법이 됨을 설명한다. 아래 그림을 보자 .  


 여기에서는 프로그램을 병렬화하였을 때의 실행 시간을 s+p=1로 하고, 이를 기준으로 프로그램의 직렬 시간과 비교한다. 즉 여기에서 속도향상은 식 1에 따라 s+Np가 된다. 여기에서 s를 α로, N을 n으로 치환하면, 식 7의 구스타프슨 법칙과 같게 된다. 즉 구스타프슨의 법칙은 주어진 시간에 병렬화로 임의 크기의 문제를 해결할 수 있을 때, 직렬 프로그램 실행 시간과의 비교를 통해 속도향상을 측정하는 반면에, 암달의 법칙은 직렬 실행 시간을 기준으로 병렬화를 수행하였을 때 얼마만큼의 속도향상이 있는지를 보인다는 점이 다르다. 병렬화 가능한 부분의 문제 크기가 클수록 구스타프슨 법칙에 따르면, 속도향상이 높게 나올 수 있다. 왜냐하면 문제 크기에 따라 더 많은 프로세서 할당을 통해 병렬 실행 시간 값(p)을 고정시킬 수 있기 때문이다. 예를 들어, 병렬가능한 문제 크기가 100이면, 100개의 프로세서로 할당하면 p=1이 된다. 1000이면, 1000개의 프로세서를 할당해서 p=1로 떨어지게 한다. 반대로 암달의 법칙은 문제 크기와 상관없이 고정된 제한 속도향상 값을 갖는다. 

 자동차를 가지고 두 법칙을 비유하자면, 

1) 자동차로 120Km 떨어진 도시로 이동한다고 하자. 그리고, 60Km/h의 속도로 한시간을 이미 이동하였다. 이제 나머지 절반의 거리를 아무리 빠르게 운전한다 하더라도, 출발지에서 목적지까지의 자동차의  평균 시속은   120Km/h를 넘을 수 없다. 이미 이동하는데 한시간을 써버렸고 아직 60Km의 이동 거리가 남아 있기 때문에 자동차가 남은 거리를 무한대의 시속으로 이동한다 하더라도, 이미 지나간 시간은 돌아오지 못하기 때문이다. (암달의 법칙)

2)  자동차로 120Km/h보다 낮은 속도로 이동하고 있었다고 하자. 남은 시간과 남은 이동거리가 충분하다면, 이전까지 얼마나 많이, 또 얼마나 천천히 운전했냐에 상관없이 자동차의 평균 시속은 120Km/h를 넘을 수 있다. 만약 60Km/h의 속도로 자동차를 한 시간 동안 운전했다면,  이 후 한 시간을 180Km/h 로 운전하거나 또는  150Km/h로 두 시간을 운전한다면, 총 이동 거리에 대한 평균 시속은 120Km/h에 도달하게 된다. (구스타프슨의 법칙)

Karp-Flatt metric[각주:3]
 카프-플랫 척도 1990년에 Alan H. Karp와 Horace P. Flatt에 의해 병렬 프로세서 시스템에서 코드의 병렬화를 측정하기 위해 고안되었다. 이 식은 측정된 속도향상 값을 가지고, 프로그램의 직렬화 부분의 비율을 찾아내는데 효과적이다. 암달이나 구스타프슨의 법칙은 실제 병렬 처리에 있어 스케쥴링, 프로세서간 통신 비용이나 프로세스간 동기화에 소비되는 비용, 프로세서간 불균형한 작업량 등을 고려하지 않는 이상적인 법칙이다. 반면에 이 척도는 실제 실험 결과를 대상으로 직렬화 부분의 비율을 계산할 수 있게 해준다.

 (식 7)
예를 들어, 1개의 프로세서를 가지고 프로그램을 실행하였을 떄 측정된 실행 시간이 5분(T1-5min)이 걸렸고, 10개의 프로세서(n=10)을 가지고 프로그램을 병렬화하였을 때 실행 시간이 1분이 걸렸다면(Tn=1min), 

 (식 8)

으로 해당 코드의 직렬 실행 부분은 1/9(약 11.1%) 임을 식을 통해 유도할 수 있다.  

Superlinear Speedup
  암달의 법칙에 따르면, 병렬화를 통해 얻을 수 있는 속도향상은 선형 이상이 될 수가 없다. 하지만, 특정한 경우에 프로그램의 병렬화는 초선형(superlinear)의 속도향상을 보이기도 한다. 즉, n개의 프로세서로 병렬화를 하였을 때 n배를 초과한 속도 향상이 나오기도 한다. 이렇다고 암달의 법칙이 틀렸다고 할 수는 없다. 다만 암달의 법칙이 초선형의 속도 향상을 보이기도 하는 이유를 설명하지 않는다 정도로 해석하는 것이 맞다. 초선형의 속도향상이 가끔씩 발생하는 이유 중 가장 큰 이유는 메모리 계층 상의 캐시 히트 때문이다.  즉 데이터 처리에 있어 이전에 이용되었던 데이터가 캐시에 남아 있어 메모리나 디스크 IO 없이 빠르게 처리된 경우에는 가끔씩 이런 경우가 목격된다.
  또 다른 이유로는 데이터의 공간 복잡도에서 발생하기도 한다. 예를 들어 x개의 입력을 가지고 2x의 처리 데이터를 작성하는 시스템이 있다고 하자. 이 데이터를 n개의 프로세서에 분할 할당한다고 하면, 각 프로세서는  2x/n  크기의 데이터를 처리할 것이다. 하지만 입력 자체를 n개로 나누어 처리 데이터를 작성한다면, 각 프로세서에 할당되는 데이터의 크기는   2x/n으로  2x/n 보다 훨씬 작게 된다. 병렬 처리 알고리즘의 복잡도가 선형이라면, 그만큼 병렬 실행 시간도 초선형으로 줄어들 수 있다.
 
Acknowledgement
그림 1a.는 Wikipedia의 암달의 법칙에서, 1b.~2b.는 참고문헌 [2]의 논문에서 발췌하였음. 식들은 모두 Online LaTeX Equation Editor를 이용해 작성되었음.

Written by bart7449

  1. Amdahl, G.M. Validity of the single processor approach to achieving large scale computing capabilities, In AFIPS Conference Proceedings, Vol. 30 (Atlantic City, NJ Apr. 18-20). AFIPS Press, Reston, Va., 1967, pp. 483--385 [본문으로]
  2. Gustafson, J.L, Reevaluating Amdahl's law, Communications of ACM , May 1988 Vol. 31, No. 5 pp.532--533 [본문으로]
  3. Karp Alan H. and Flatt Horace P. Measuring Parallel Processor Performance, Communications of ACM, Vol 33, No. 5, May 1990 [본문으로]
Posted by Bart