A massively-parallel Web search engine consists of hundreds of thousands of nodes to store large-scale data in a distributed manner and process queries in parallel based on “NoSQL” systems. We focus on two facts that 1) NoSQL systems have very simple and primitive functionality while DBMSs effectively provide high-level functionalities such as SQL, schemas, or indexes, 2) even though we have a large amount of collective memory space over multiple nodes of a large-scale search engine, there is no work reported in the academic world that coordinates memories of multiple nodes as if we had one integrated memory storing the entire index. In this dissertation, therefore, we propose an approach to building a massively-parallel search engine using DBMSs and integrating distributed memory.
In the first part of the dissertation, we claim that building a massively-parallel search engine using a parallel DBMS can be an attractive alternative since it supports a higher-level (i.e., SQL-level) interface than that of a distributed file system for easy and less error-prone application development while providing scalability. For this purpose, we evaluate and estimate the performance of ODYS[65], which is a massively-parallel search engine using a DB-IR tightly integrated parallel DBMS, to verify its commercial-level scalability and efficiency. We estimate the performance based on a hybrid (i.e., analytic and experimental) performance model for the parallel search engine. We show that the estimation error between the model and the actual experiment is less than 2.13% by observing that the bulk of the query processing time is spent at the slave (vs. at the master and network) and by estimating the time spent at the slave based on actual measurement. Using our model, we demonstrate a commercial-level scalability and performance of our architecture. Our proposed system ODYS is capable of handling 1 billion queries per day for 30 billion Web pages by using only 43,472 nodes with an average query response time of 194 ms. By using twice as many (86,944) nodes, ODYS can provide an average query response time of 148 ms. These results show that building a massively-parallel search engine using a parallel DBMS is a viable approach with advantages of supporting the high-level (i.e., DBMS-level), SQL-like programming interface.
In the second part of the dissertation, we propose two-dimensional indexing---a novel in-memory indexing architecture that operates over distributed memory of a massively-parallel search engine. The goal of two-dimensional indexing is to provide a one-integrated-memory view as in a single node system using one large integrated memory. In two-dimensional indexing, we partition the entire index into n × m fragments and distribute them over the memories of multiple nodes in such a way that each fragment is entirely stored in main memory of one node. The proposed architecture is not only scalable as it uses a scaled-out shared-nothing architecture but also is capable of achieving low query response time as it processes queries in main memory. We also propose the concept of the one-memory point, which is the amount of the memory space required to completely store the entire index in main memory providing a one-integrated-memory view. We investigate the one-memory point by analyzing an actual dataset and compare the result with the experiments. We first prove the effectiveness of two-dimensional indexing with single-keyword queries, and then, extend the notion so as to be able to handle multiple-keyword queries. In experiments using the real-life search query set over a database consisting of 100 million Web documents crawled, we show that two-dimensional indexing can effectively provide a one-integrated-memory view without too much of additional memory compared with the single node system using one large integrated memory. This ratio of additional memory is expected to decrease as we use a larger size of the database. We also show that, with a six-node prototype, in an ideal case, it significantly improves the query processing performance over a disk-based search engine with an equivalent amount of in-memory buffer but without two-dimensional indexing by 105.05 times when queuing effects are excluded. This improvement is expected to get larger as the system is scaled-out with a larger number of machines.
We summarize the contributions of this dissertation as follows. First, we have shown that a massively parallel search engine capable of processing real-world scale data and query loads can be implemented using a DB-IR tightly integrated parallel DBMS. We have presented the detailed implementation of such a system, ODYS, that provides higher-level interface and functionalities for easy application development and maintenance while providing superior performance and scalability. Second, we have proposed a notion of two-dimensional indexing that simulates collective distributed memory as one integrated memory for a massively-parallel search engine. For two-dimensional indexing, we partition the entire index into a two-dimensional array of multiple index fragments and completely store them into main memories of the multiple machines. We also have implemented the two-dimensional indexing architecture in ODYS, namely, ODYS/2D-Indexing. Finally, through extensive experiments using real-world scale data and query loads, we have estimated the performance of ODYS and have shown the effectiveness of two-dimensional indexing.
대용량 병렬 웹 검색 엔진은 대규모 데이터를 분산 저장하고 질의들을 병렬로 처리하기 위하여 수십 만대의 노드로 구성된 NoSQL 시스템에 기반하여 구현된다. 본 학위 논문은 다음의 두 가지 사실에 주목한다. 1) NoSQL 시스템이 매우 단순하고 원시적인 기능성(functionality)를 가지는 반면, DBMS는 SQL, 스키마, 인덱스와 같은 높은 수준의 기능성을 효과적으로 제공한다. 2) 대형 검색 엔진을 구성하는 다수의 노드의 메모리 공간을 합하면 큰 용량의 메모리 공간을 확보 할 수 있음에도 불구하고, 이러한 다수의 노드에 존재하는 메모리들을 조직화(coordinate)함으로써 전체 인덱스를 저장할 수 있는 하나의 통합된 메모리를 가진 것과 같은 효과를 보이게 하는 연구가 학계에 보고되지 않았다. 따라서, 본 학위 논문에서는 DBMS를 사용하고 분산 메모리를 통합하여 대용량 병렬 검색엔진을 구축하는 방법을 제안한다.
본 학위 논문의 첫 번째 파트에서는, 병렬 DBMS를 사용하여 대용량 병렬 검색 엔진을 구축하는 것이 매력적인 대안임을 주장한다. 왜냐하면 병렬 DBMS는 분산 파일 시스템(DFS) 보다 높은 수준(즉, SQL-level)의 인터페이스를 지원하므로 응용 프로그램(application)의 개발이 용이하고 개발 과정에서 오류가 발생할 가능성(error-prone)이 적을 뿐만 아니라, 높은 확장성 또한 갖기 때문이다. 이를 위하여, 본 학위 논문에서는 DB-IR이 밀결합된 병렬 DBMS를 사용한 대용량 병렬 검색 엔진인 ODYS[65]의 성능을 평가한다. 이를 위하여, 병렬 검색엔진을 위한 하이브리드(분석적, 실험적) 성능 모델에 기반하여 성능을 예측한다. 먼저, 실측에 기반하여 슬레이브(slave)에서 소요된 질의 처리 시간을 예측하고, 대부분의 질의 처리 시간이 슬레이브에서 소요됨을 관찰함으로써 제안된 성능 모델과 실제 실험 결과 간의 예측 오류가 2.13%보다 작음을 보인다. 그리고 제안된 성능 모델을 사용하여 병렬 DBMS 기반 검색 엔진이 상용 시스템 수준의 확장성과 성능을 보임을 입증한다. 성능 예측 결과, ODYS는 300억 건의 웹 문서에 대하여, 43,472대의 노드를 사용하여 하루 10억 건의 질의를 평균 194ms의 질의 응답 시간으로 처리할 수 있다. 이보다 두 배 많은 수(86,944)의 노드를 사용할 경우, ODYS는 148ms의 질의 응답 시간을 제공할 수 있다. 이러한 결과는 병렬 DBMS를 사용하여 대용량 병렬 검색엔진을 구축하는 것이 충분히 실행 가능한(viable) 방법이며, 동시에 높은 수준(DBMS 수준)의 SQL-like 프로그래밍 인터페이스를 지원하는 장점을 가짐을 보이는 것이다.
본 학위 논문의 두 번째 파트에서는, 대용량 병렬 검색 엔진을 구성하는 다수의 머신의 분산 메모리에서 동작하는 새로운 메모리 기반(in-memory) 색인 구조인 이차원 색인(two-dimensional indexing)을 제안한다. 이차원 색인의 목표는 하나의 대형 메모리 공간을 가지는 단일 노드 시스템에서와 같은 통합-메모리 뷰(one-integrated-memory view)를 제공하는 것이다. 이차원 색인은 전체 인덱스를 n × m 개의 조각(fragment)들로 분할하고, 각 조각들이 하나의 노드의 메모리에 완전히 저장되도록 다수의 메모리들에 분산한다. 제안된 아키텍처는 무공유(shared-nothing) 아키텍처를 사용함에 따라 높은 확장성을 가질 뿐만 아니라, 질의를 메인 메모리에서 처리함에 따라 낮은 질의 응답 시간을 달성할 수 있다. 또한, 우리는 통합-메모리 뷰를 제공하면서 전체 인덱스를 메인 메모리에 완전히 저장하기 위해 필요한 메모리 양인 단일 메모리 지점(one-memory point)의 개념을 제안한다. 우리는 실제 데이터 집합을 분석함으로써 단일 메모리 지점을 조사하고, 그 결과를 실험 결과와 비교한다. 우리는 단일 키워드(single-keyword) 질의에 대한 이차원 색인의 효과를 증명하고, 이어서 이차원 색인의 개념을 확장하여 복수 키워드(multiple-keyword) 질의도 다룰 수 있도록 한다. 1억 건의 웹 문서로 구성된 데이터베이스와 실세계의 질의 집합을 사용한 실험을 통하여, 이차원 색인이 하나의 대형 메모리를 가지는 단일 시스템 대비 그리 크지 않은 추가 메모리로 단일 메모리 뷰를 효과적으로 제공할 수 있음을 보인다. 추가 메모리의 비율은 데이터베이스 크기가 증가함에 따라 감소할 것으로 예측된다. 또한, 여섯 대의 노드로 구성된 프로토타입에서, 동일한 크기의 메모리 기반 버퍼를 가지나 이차원 색인을 사용하지 않은 디스크 기반 검색 엔진의 질의 처리 성능을 105.05배 향상시킴을 보인다. 그리고 시스템이 확장(scale-out)되어 시스템을 구성하는 머신의 수가 증가할 경우, 이러한 성능 향상의 폭은 더욱 커질 것으로 예상된다.
본 학위 논문의 공헌을 요약하면 다음과 같다. 첫째, 실세계 규모의 데이터와 질의 부하를 처리할 수 있는 대용량 병렬 검색 엔진이 DB-IR이 밀결합된 병렬 DBMS를 사용하여 구현될 수 있음을 보였다. 그리고 이러한 시스템인 ODYS의 상세한 구현을 설명하였다. ODYS는 응용 프로그램 개발 및 관리를 용이하게 하는 높은 수준의 인터페이스와 기능성을 제공하면서 우수한 성능과 확장성을 제공한다. 둘째, 분산 메모리 공간을 하나의 통합된 메모리로 보이게 만드는 이차원 색인의 개념을 제안하였다. 이차원 색인을 위하여, 전체 인덱스를 이차원 배열 형태의 다수의 조각들로 분할하고 분할된 조각들을 다수의 머신 내의 메인 메모리에 완전히 저장하였다. 또한, ODYS에 이차원색인 아키텍처를 구현하여 ODYS/2D-Indexing 시스템을 구현하였다. 마지막으로, 실세계 규모의 데이터와 질의 부하를 사용한 광범위한 실험을 통하여, ODYS의 성능을 예측하였고, 이차원 색인 사용의 효과를 보였다.
