재미있게 살자~

이번 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를 갖는 시스템에서 다양한 조인 연산들, 다중 조인 연산들을 어떻게 효과적으로 지원하는지는 아직도 할 분야가 많아보입니다.  저희는 이러한 문제를 풀고 있고 다른 저널 논문들로 이에 대한 해결 방안들을 순차적으로 곧 보일 겁니다.