Extensible Markup Language (XML) is a markup language to represent electronic documents readable for both human and machine. By virtue of its simplicity and extensibility, XML has played increasingly important roles to store and transfer data in industrial and academic fields over the past few decades. Accordingly, the size of XML document has grown significantly, especially huge amount of data are periodically produced and accumulated in data logging and scientific areas as new data are collected. The produced XML data are stored in the form of a huge XML file. This leads to growing demand for XML data analysis with multiple user-queries that are prepared in advance when XML data are not completely generated. However conventional XML database systems and XML pub/sub systems do not support this type of workload as they are designed for smaller size of XML documents. The MapReduce framework is more suitable to process the user-queries over large XML data because of its scalability.
In this thesis, we present a parallel method to process multiple twig pattern queries simultaneously by using 2 MapReduce jobs, one for path filtering and another for twig join. In this way, we avoid the long iteration of MapReduce jobs that incurs a lot of redundant I/O cost and queries can share their input scans and intermediate results with each other to save I/O cost.
We also devise an elaborate run-time load balancing scheme inside MapReduce for fair assignment of twig join workloads. Basically, MapReduce follows data-parallelism which divides large data into smaller blocks and processes them in distributed nodes. However a twig join with partitioned inputs yields incomplete join results. Instead, we apply task-parallelism into the MapReduce framework which assigns twig join operations to each reducer. We propose a sophisticated run-time load balancing algorithm for fair assignment of twig join workloads among nodes based on cost estimation of each reducer.
Applying these approaches, we designed HadoopXML, a suite for parallel processing of massive XML data with multiple twig pattern queries on the Hadoop/MapReduce framework. HadoopXML finds path solutions of each path query using the query index in the first MapReduce job. Twig pattern queries are converted to twig joins of the path solutions and performed in the second MapReduce job. This reduces twig join cost by filtering out join inputs that are irrelevant to its twig pattern. Moreover, HadoopXML provides additional I/O optimization techniques such as converting path queries with //, * to root-to-leaf paths and collocating XML blocks and their corresponding label blocks. HadoopXML also provides a data-partitioning scheme for XML document to prevent loss of structural information.
In the second part of this thesis, we present parallel tree labeling algorithms for a large XML document. XML tree labeling is a crucial initial step in XML query processing. We can identify a structural relationship between XML elements with simple comparison of their labels. Without tree labeling scheme, it is inevitable to traverse entire document for XML query processing. However previous tree labeling algorithms are all sequential. This leads to unbearable delay on entire query processing when we need to analyze the massive XML data. To solve this problem, we propose parallel tree labeling algorithms for massive XML data based on the MapReduce framework. First, we present parallel versions of two prominent XML tree labeling schemes. Then we solve performance issues caused by data skewness and MapReduce`s inherited limitations by applying load balancing and data repartitioning technique to our parallel labeling algorithms.
To the best of our knowledge, this is the first attempt to parallelize tree labeling algorithms and multiple twig pattern query processing. Through extensive experiments with synthetic and real-world XML dataset, we prove that our parallel algorithms are profoundly efficient and scalable.
XML 은 W3C에서 제안된 표준 마크업 언어로서, 웹이나 과학과 같은 다양한 분야에서 데이터 저장 및 전송을 위한 인코딩 형식으로 많이 사용되고 있다. 다양한 분야에서 XML이 활용되면서 XML 문서들의 크기도 커지게 되었다. 이러한 XML 문서들은 새로운 정보가 주기적으로 기존 XML문서에 추가되어 크기가 더욱 커지는 특성을 지니고 있다. 이에 따라, 주기적으로 배포되는 데이터에 대해 미리 준비된 다수의 사용자 질의들을 빠른 시간안에 처리할 필요가 생기게 되었다. 그러나 기존 XML 출판/구독 시스템이나 XML 데이터 데이스는 보다 작은 크기의 XML 문서 처리를 단일 서버에서 처리하도록 설계되어 대용량 XML 문서를 충분히 빠른 시간안에 처리할 수 없다. 반면 맵리듀스는 높은 확장성을 제공하는 병렬처리 프레임웍으로써 지속적으로 축적되는 대규모 XML 데이터를 병렬처리하는데 적합하다.
본 논문에서는 미리 주어진 다수의 가지 패턴 질의들을 2 번의 맵리듀스 작업을 사용해 동시 처리하는 기법을 제안한다. 첫 번째 맵리듀스 작업은 가지 패턴 조인의 입력을 필터링하고 두 번째 맵리듀스에서는 이를 사용해 가지 패턴 조인 연산을 수행한다. 이렇게 함으로써 다수의 질의 처리를 위한 맵리듀스 작업의 긴 반복 수행을 피할 수 있다. 또한 질의들은 입력으로 주어진 대용량 XML문서를 읽어들이는 과정을 공유할 수 있으며, 질의들 사이에서 공통되는 단일 경로 패턴들의 결과들을 서로 공유할 수 있어 많은 입출력 비용을 절감할 수 있다.
또한 가지 조인 연산을 동적으로 분산 노드에 균등 분배하기 위한 기법을 제안한다. 기본적으로 맵리듀스 프레임웍은 데이터 병렬화 패러다임을 따른다. 즉, 대용량의 데이터를 분할해 서로 다른 노드에서 분할된 데이터를 처리한다. 분할된 데이터에 대해 가지 조인 연산을 수행하면 불완전한 조인 결과를 얻게된다. 그러므로 데이터 병렬화 대신 작업 병렬화 기법을 사용해, 각각의 리듀서에 가지 조인 연산들을 분배한다. 첫 번째 맵리듀스 작업을 통해 얻은 조인연산의 입력의 크기로부터 리듀서들의 소요 비용을 계산해 동적으로 작업량을 균등분배한다.
이러한 기법들을 바탕으로, Hadoop/MapReduce 프레임웍 위에 다수의 가지 패턴질의를 병렬 처리하기 위한 HadoopXML 시스템을 구현하였다. 추가적으로, 더블 슬래시와(//), 와일드 카드(*)가 나타나는 질의를 유일한 선형 경로로 변환하여 처리하고, XML 블록들과 관련된 레이블 블록들을 같은 노드에 저장하는 등 HadoopXML에 입출력 효율을 높이기 위한 기법들을 적용하였다. 또한 가지 조인 연산 비용을 줄이기 위해 가지 패턴 질의를 단일 경로 질의 해답들의 조인으로 변환하여 처리한다. HadoopXML은 첫 번째 맵리듀스 작업에서 병렬 처리를 위해 XML 문서를 분할할 때 문서의 구조정보가 손실되지 않도록 하는 기법을 제공한다.
다음으로 본 학위 논문에서는 병렬 XML 트리 레이블링 기법을 제안한다. XML 노드들 사이의 관계를 파악하는 것은 XML 질의 처리에 아주 중요한 연산이다. XML 트리 레이블링 기법은 XML 노드들에 고유한 레이블을 부여함으로써, 레이블의 비교만으로 노드들 사이의 관계를 계산할 수 있게 한다. 레이블이 없으면 XML 질의 처리를 위해 전체 XML 문서를 직접 파싱해야하는 비효율이 발생한다. 하지만 기존의 XML 트리 레이블링 기법들은 모두 순차적인 알고리즘이기 때문에, 대용량 XML 문서를 레이블링 하는 과정에서 많은 시간을 소요하게 되고 전체 질의 처리 시간을 심각하게 지연시키게 된다. 그래서 본 논문에서는 가장 널리 사용되고 있는 두 종류의 트리 레이블링 기법을 병렬화한 알고리즘을 제안한다. XML 문서에 나타나는 XML 노드들은 그 종류가 편향되어 나타나는 경향이 있다. 이때 맵리듀스의 기본 셔플링 정책을 사용하면 리듀서들 사이의 작업량 불균형 문제가 나타나게 된다. 이를 해결하기 위해, 작업량 분배 및 데이터 재분할 기법을 병렬 레이블링 기법에 적용하였다. 이를 통해 우리의 병렬 레이블링 알고리즘은 뛰어난 확장성 및 효율성을 제공한다.
본 연구는 주기적으로 실험결과가 대용량 XML문서로 축적되는 생물학 분야등에서 미리 준비된 다수의 질의들을 처리하는데 효과적으로 사용할 수 있다. 현재까지 다수의 가지 패턴 질의를 동시에 대용량 XML 데이터에 대해 병렬 처리하는 연구는 현재까지 찾을 수 없었으며 XML 레이블링 기법의 병렬화 또한 본 연구에서 최초로 시도하였다. 수록된 다양한 실험결과들은 제안하는 시스템 및 병렬 알고리즘이 대용량 XML문서를 처리하는 데 있어 아주 효과적이며 효율적임을 증명한다.
