Cloud P2P OLAP: 클라우드 컴퓨팅 환경에서의 Peer-to-Peer OLAP 질의처리기법 및 인덱스 구조 Cloud P2P OLAP: Query Processing Method and Index structure for Peer-to-Peer OLAP on Cloud Computing원문보기
최근 분산 OLAP은 분산 환경에 적용하기 위하여 DHT기반의 P2P OLAP과 그리드 OLAP연구가 활발하게 진행되고 있다. 그러나 클라우드 컴퓨팅 환경에 적용하기 위하여 P2P OLAP은 structured P2P 특성 때문에 다차원 범위 질의에 문제점이 있고, Grid OLAP은 인접성 및 시계열 고려가 없기 때문에 쿼리 자체의 서브 �V 조회 알고리즘 연구에 치중되어 있다. 따라서 본 논문은 클라우드 컴퓨팅에 적합한 환경 제공을 위해 사용자의 조회 결과가 시계열적 특성으로 여러 사용자에 의해 재사용이 가능하고, 서버상의 휘발성 조회 큐브가 사용자 로컬 메모리에서 직접 분석 질의 시 효율이 좋다는 것에 초점을 두어 중앙관리 P2P방식을 제안하였다. 또한 빠른 질의 결과 및 다차원 범위질의를 위한 다단계 Hybrid P2P방식에 인덱스부하 분산 및 성능 향상을 위한 클라우드 시스템을 접목하여 Cloud P2P OLAP을 제안하였다. 이를 위한 인덱스 구조로는 큐브 위상관계 트리와 인접성 2차원 Quadtree에, 시계열 Interval-트리를 접목하였으며, 이는 조회나 갱신 시에 일반 OLAP에 비해 큰 효율성을 보였다.
최근 분산 OLAP은 분산 환경에 적용하기 위하여 DHT기반의 P2P OLAP과 그리드 OLAP연구가 활발하게 진행되고 있다. 그러나 클라우드 컴퓨팅 환경에 적용하기 위하여 P2P OLAP은 structured P2P 특성 때문에 다차원 범위 질의에 문제점이 있고, Grid OLAP은 인접성 및 시계열 고려가 없기 때문에 쿼리 자체의 서브 �V 조회 알고리즘 연구에 치중되어 있다. 따라서 본 논문은 클라우드 컴퓨팅에 적합한 환경 제공을 위해 사용자의 조회 결과가 시계열적 특성으로 여러 사용자에 의해 재사용이 가능하고, 서버상의 휘발성 조회 큐브가 사용자 로컬 메모리에서 직접 분석 질의 시 효율이 좋다는 것에 초점을 두어 중앙관리 P2P방식을 제안하였다. 또한 빠른 질의 결과 및 다차원 범위질의를 위한 다단계 Hybrid P2P방식에 인덱스 부하 분산 및 성능 향상을 위한 클라우드 시스템을 접목하여 Cloud P2P OLAP을 제안하였다. 이를 위한 인덱스 구조로는 큐브 위상관계 트리와 인접성 2차원 Quadtree에, 시계열 Interval-트리를 접목하였으며, 이는 조회나 갱신 시에 일반 OLAP에 비해 큰 효율성을 보였다.
The latest active studies on distributed OLAP to adopt a distributed environment are mainly focused on DHT P2P OLAP and Grid OLAP. However, these approaches have its weak points, the P2P OLAP has limitations to multidimensional range queries in the cloud computing environment due to the nature of st...
The latest active studies on distributed OLAP to adopt a distributed environment are mainly focused on DHT P2P OLAP and Grid OLAP. However, these approaches have its weak points, the P2P OLAP has limitations to multidimensional range queries in the cloud computing environment due to the nature of structured P2P. On the other hand, the Grid OLAP has no regard for adjacency and time series. It focused on its own sub set lookup algorithm. To overcome the above limits, this paper proposes an efficient central managed P2P approach for a cloud computing environment. When a multi-level hybrid P2P method is combined with an index load distribution scheme, the performance of a multi-dimensional range query is enhanced. The proposed scheme makes the OLAP query results of a user to be able to reused by other users' volatile cube search. For this purpose, this paper examines the combination of an aggregation cube hierarchy tree, a quad-tree, and an interval-tree as an efficient index structure. As a result, the proposed cloud P2P OLAP scheme can manage the adjacency and time series factor of an OLAP query. The performance of the proposed scheme is analyzed by a series of experiments to identify its various characteristics.
The latest active studies on distributed OLAP to adopt a distributed environment are mainly focused on DHT P2P OLAP and Grid OLAP. However, these approaches have its weak points, the P2P OLAP has limitations to multidimensional range queries in the cloud computing environment due to the nature of structured P2P. On the other hand, the Grid OLAP has no regard for adjacency and time series. It focused on its own sub set lookup algorithm. To overcome the above limits, this paper proposes an efficient central managed P2P approach for a cloud computing environment. When a multi-level hybrid P2P method is combined with an index load distribution scheme, the performance of a multi-dimensional range query is enhanced. The proposed scheme makes the OLAP query results of a user to be able to reused by other users' volatile cube search. For this purpose, this paper examines the combination of an aggregation cube hierarchy tree, a quad-tree, and an interval-tree as an efficient index structure. As a result, the proposed cloud P2P OLAP scheme can manage the adjacency and time series factor of an OLAP query. The performance of the proposed scheme is analyzed by a series of experiments to identify its various characteristics.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
MOLAP은 빠른 응답을 보이지만, 디스크 공간이 한정되어 모든 조합의 모든 셑을 실체화(Materialized) 하는 데에는 물리적인 한계가 있어, 대규모 데이터의 분석용으로는 적당하지 않다. 따라서 본 논문은 ROLAP의 유연성 및 확장성에, MOLAP의 속도상의 이점을 제공하고자, 클라이언트 큐브 캐시를 관리 가능한 P2P로 공유하는 시스템과, P2P 노드의 큐브 데이터에 대한 정교한 인덱스 구조를 중앙관리 가능하도록 하는 클라우드 시스템 상의 서버 구조를 제안하였다.
본 논문에서 제안하는 Cloud P2P OLAP은 클라우드 시스템을 도입하여 유동적으로 인스턴스를 추가 및 삭제 할 수 있으며, 이로부터 시스템의 확장성 및 가용성을 극대화 할 수 있다. 따리서 선형적인 성능 향상도 꾀할 수 있도록 하였다. 마지막으로 본 논문은 클라우드와 P2P를 결합한 아키텍처를 OLAP 분야에서 사용할 수 있도록 처음으로 제안하였다는 측면에서 매우 의미 있는 연구라고 할 수 있다.
본 논문에서는 ROLAP의 유연성 및 확장성에 MOLAP의 속도상의 이점을 제공하고자 수많은 사용자의 클라이언트를 재활용 가능한 분산 노드화하여 각 노드간에 P2P로 큐브 캐시를 공유하는 시스템을 제안하였다. 이를 최적화된 알고리즘으로 고안하여 비교 및 검증을 수행하였다.
본 논문에서는 추가적으로 Quadtree가 균형이 보장되지 않아 조회 성능에서는 불리한 약점을 가지고 있는 단점을 보완하기 위해 인덱스를 재구성하는 전처리 알고리즘을 추가로 제안하였다. OLAP은 주기적으로 실체화 뷰를 야간시간에 갱신하는 작업을 하는데 이 시점에 Cloud P2P OLAP 또한 인덱스를 재구성 하도록 구성함을 통해 일단위로 균형을 보장 하도록 할 수 있다.
구글의 Bigtable은 B+ 트리와 유사한 인덱스 개념을 다단계의 관리 가능한 분산 시스템으로 확장하여서 높은 효과를 보였다[1]. 본 논문은 이러한 분산 중앙 관리 인덱스 구조에 초점을 두어 OLAP에 다단계의 Hybrid P2P를 접목하였다. 효율적인 인덱스 관리가 제한된 형태로 OLAP에 P2P나 Grid를 도입한 개념은 이미 몇몇 유사 연구가 진행 된 바 있으나, 본 논문에서는 추가로 기존 연구가 간과 하였던 아래와 같은 특성을 전제로 서버에서 범위 질의 및 시계열 관리가 가능한 보다 향상된 알고리즘을 제안하였다.
제안 방법
Cloud P2P OLAP과 일반 OLAP의 비교 실험에서 정해진 시나리오는 최선의 경우와 최악의 경우 그리고 랜덤의 경우 세 경우로 나누어지며, 랜덤의 경우 포함 세 경우 모두 질의 수행 시간 및 질의 수행 시나리오가 정해져 있어 제안 시스템과 일반 시스템의 비교 평가가 가능하도록 하였다. 비교 대상 시스템은 전통적인 방식으로 구현 된 OLAP 이며, 해당 OLAP 은 P2P 네트워크 OLAP 클라이언트를 변형하여 모든 쿼리를 ROLAP 서버에 직접 요청하는 형태로 구현하였다.
구현은 .NET Framework 3.5 하에서 C#을 이용하여 개발 되었으며, P2P 및 Cloud 내 SOA 서비스 통신 프로토콜은 WCF를 이용하여 RPC방식의 SOAP프로토콜을 이용하여 개발하였다. 서버 인덱스를 모니터링 하는 프로그램과 클라이언트 프로그램이 있으며, 클라이언트 프로그램은 모두 WCF Self Hosting 기능을 이용하여 자체 서버 기능을 내장하도록 구현하였다.
2차원 정보를 표현하는 인덱스 구조는 R-트리, KD-트리 등 다양한 인덱스가 존재한다. 그러나 뒤이어 제안하는 시계열 인덱스와의 유기적인 결합을 고려하여 Quad트리를 제안하였다. 인접성에 대한 위치를 파악한 이후에는 최인접 위치부터 시계열 노드 존재 여부를 재귀적으로 확장하며 검색해 나가야 하는데 균형을 위한 메커니즘이 존재하는 경우 split시점에 트리의 깊이 별로 시계열 정보를 요약 하여 가지고 있는 시계열 트리의 전체적인 재구성이 필요하다.
또한 기존 P2P OLAP과 달리 분산 노드들이 중앙 관리 가능하기 때문에 기존 P2P OLAP과 차별되게 집계 질의 자체의 조회 및 조합을 위한 알고리즘 적인 접근을 시도하였다. 그러나 제안하는 Cloud P2P OLAP에서는 클라이언트 인덱스 레이어를 두어 질의 자체를 클라이언트가 수행하도록 하였고, 중앙 클라우드 서버는 쿼리가 가능한 큐브를 가지고 있는 클라이언트를 찾는데 주력하였다. 그리드 OLAP 연구는 쿼리 자체를 중앙 처리 및 그리드 분산 처리 하려고 시도하고 있으며, 그리드 시스템의 특성상 클라이언트에 위임한 경우는 찾아볼 수 없었다.
또한 [23]에서 여러 노드의 프레그먼트를 병합하여 재쿼리 하거나 부분집합을 찾는 것 등의 모든 일련의 과정이 LINQ를 통하면 데이터베이스에 질의 하는 것과 유사하게 빠르게 수행될 수 있으므로, 쿼리 체크, 쿼리조합 등에 대한 알고리즘 적 접근은 큰 의미가 없다. 대신 본 논문에서는 메모리 데이터베이스의 메모리 상태를 직렬화하여 재부팅 후에도 사용 가능 하도록 하였으며, 해당 파일을 복수개의 노드에서 분산하여 파일 청크를 받을 수 있도록 동일 큐브의 주소 목록을 DHT 형태로 공유 하도록 하였다. 이러한 접근은 본 논문의 레이어2 인덱스가 인접성 인덱스를 통해 물리적, 논리적으로 최적의 후보를 선정해 주었다고 할지라도 네트워크 회선 장애 및 회선 부하 등으로 실제 속도가 좋지 않은 경우 복수의 후보 군을 통해 복수 전달 받음으로 인해 실세계에서 가장 네트워크 연결이 빠른 노드로부터 가장 많은 패킷을 전송 받도록 하는 효과도 가지고 있다.
또한 동일한 인스턴스 개수에 대하여 시스템 리소스를 높게 할당해가며 수직적 확장을 통해서도 성능 변화를 테스트 해 보았다. 두 번째로는 P2P를 배제하고 큐브 데이터까지 모두 클라우드 시스템에 올린 경우 성능을 고려하기 위해 인스턴스를 늘려가면서 파일 객체를 클라우드 디스크 상에 읽기 및 쓰기 성능 테스트를 하였다. 두 가지 실험은 모두 Extreme Computing Group[24]에서 제공하는 벤치마크 데이터와 예제 코드를 활용하여 수행되었으며 해당 결과는 아래와 같다.
첫째는 PaaS 플랫폼 서비스 클라우드 상에서 인스턴스의 개수를 증가시키면서 인덱스 서버의 성능의 변화를 살펴보았다. 둘째는 실제 P2P 네트워크를 가정하여 예시 스키마에 대하여 OLAP분석질의를 수행하고 서버 혹은 클라이언트 노드간 데이터를 전송 받는 Cloud P2P OLAP 프로그램을 구현하여, 정해진 시나리오대로 성능 분석을 하였다. 마지막으로 제안하는 알고리즘의 2번째 레이어를 일반적인 접근방식인 R-트리 접근 방식과, 제안하는 Quadtree 변형 접근 방식으로 나누어 각각을 구현하고 둘간의 성능을 삽입과 조회 위주로 비교 평가하였다.
따라서 본 논문은 Quadtree를 이용하여 다차원 범위 질의를 처리하며 다차원 인덱스와 함께 추가 적으로 시계열 인덱스를 위해 Quadtree를 Interval트리와 융합하여 관리하고 있으며, 다각적인 측면에서 Quadtree가 유리함을 검증하였다. 또한 큐브 노드의 포함관계 및 시계열 요소와의 접목을 위해 인덱스를 변형하여 다단계의 Hybrid P2P 형태로 클라우드 상에서 인덱스가 관리되는 Cloud P2P OLAP 구조를 제안하였다.
이로 인하여 인덱스를 여러 개 만들어 동시 테스트를 수행하지 않고 한 개의 인덱스에 대하여 많은 부하를 동시에 주어 성능 테스트를 하더라도 전체 시스템의 부하 테스트가 가능함을 유추할 수 있었다. 따라서 최대 10,000개까지의 노드를 1,000번씩 테스트 하여 평균값으로 성능 검증을 하였다.
[16]에서는 여러 노드에 집계 정보가 분산되어 있으며, 분산된 캐시 데이터에 인덱스 관리 및 조회 로직이 필요하다는 부분에서 기존의 P2P OLAP과 동일한 주제의 알고리즘이 연구되었다. 또한 기존 P2P OLAP과 달리 분산 노드들이 중앙 관리 가능하기 때문에 기존 P2P OLAP과 차별되게 집계 질의 자체의 조회 및 조합을 위한 알고리즘 적인 접근을 시도하였다. 그러나 제안하는 Cloud P2P OLAP에서는 클라이언트 인덱스 레이어를 두어 질의 자체를 클라이언트가 수행하도록 하였고, 중앙 클라우드 서버는 쿼리가 가능한 큐브를 가지고 있는 클라이언트를 찾는데 주력하였다.
[17]에서는 공간 인덱스 구축을 위해 R-트리를 이용하는 P2PR-트리를 제안하였고, [18]에서는 P2P에서 범위 질의 효율을 높이는 연구로서 파티션을 달리하는 kd-트리 인덱스를 제안하였다. 또한 다차원 쿼리를 지원하기 위해 space-filling curves를 제안하여 다차원을 1차원으로 표현 하는 방법을 제안하였다. 최근에는 P2P 범위 질의를 위해 Quadtree를 이용하는 방법도 제안되었다[14].
성능 테스트는 인스턴스 하나에서 복수개의 인덱스를 관리하도록 하고, 이후 인스턴스를 늘려가며 수평적 확장을 해가면서 일정 시간에 작업처리 한 태스크의 수로 테스트 하였다. 또한 동일한 인스턴스 개수에 대하여 시스템 리소스를 높게 할당해가며 수직적 확장을 통해서도 성능 변화를 테스트 해 보았다. 두 번째로는 P2P를 배제하고 큐브 데이터까지 모두 클라우드 시스템에 올린 경우 성능을 고려하기 위해 인스턴스를 늘려가면서 파일 객체를 클라우드 디스크 상에 읽기 및 쓰기 성능 테스트를 하였다.
이를 최적화된 알고리즘으로 고안하여 비교 및 검증을 수행하였다. 또한 인덱스가 중앙 관리되는 하이브리드 P2P하에서 중앙관리 인덱스 서버의 성능 극대화 및 효율적인 관리를 위해 클라우드 시스템 내의 인덱스 서버 활용도를 검증하였다. 본 논문에서 제안하는 방법은 P2P OLAP에서 시계열적인 재활용과 물리적, 논리적 인접성에 대한 고려는 필수적으로 큐브 캐시에 대한 다차원 범위 질의가 가능해야 하고, 그러한 질의는 기존의 DHT 기법의 structured P2P에서는 제약이 심하기 때문에 다단계의 하이브리드 중앙관리 P2P 방식을 활용하도록 발상의 전환을 하였다.
따라서 본 논문은 Quadtree를 이용하여 다차원 범위 질의를 처리하며 다차원 인덱스와 함께 추가 적으로 시계열 인덱스를 위해 Quadtree를 Interval트리와 융합하여 관리하고 있으며, 다각적인 측면에서 Quadtree가 유리함을 검증하였다. 또한 큐브 노드의 포함관계 및 시계열 요소와의 접목을 위해 인덱스를 변형하여 다단계의 Hybrid P2P 형태로 클라우드 상에서 인덱스가 관리되는 Cloud P2P OLAP 구조를 제안하였다.
위의 특성을 이용하여 본 논문은, 각각의 노드가 기 집계된 데이터큐브의 P2P 복제자 역할을 할 뿐 아니라, 서브 파생 큐브에 대한 쿼리를 처리 할 중간 하이브리드 서버 역할을 할 수 있도록 하였다. 또한, 서버 요청은 집계가 존재하지 않는 영역으로 국한 시키고, 복수 클라이언트 노드가 비동기적으로 동시에 서로 데이터를 주고받을 수 있도록 새로운 개념의 Cloud P2P OLAP 시스템을 제안 하였으며, 이를위한 효율적인 인덱스 구조를 제안하였다. 특히 알고리즘 측면에서 물리적, 논리적 인접노드에서 데이터를 가져올 수 있도록 하였고, 시계열적인 특성을 이용하여 서버에 요청하는 데이터의 양을 최소화하고, 과거의 캐시데이터가 최대한 미래에도 활용될 수 있도록 하는데 초점을 두었다.
즉, 상위 노드의 Interval에서 포함되지 않은 구간은 하위의 모든 노드의 Interval을 뒤져도 포함되지 않은 구간임을 보장한다. 또한, 하위의 4개의 노드가 포함하고 있는 Interval이 특정 높이 이상의 Interval트리로 관리되고 Quadtree 자체의 높이가 높아지지 않도록 임계치를 두어 한 노드가 복수개의 클라이언트를 관리하도록 하였다. 이로부터 앞서 고려한 비트 인덱스의 단점을 시구간 배열의 범위만을 재귀적 대표 4 노드에 한하여 관리함으로써 해결하였다.
둘째는 실제 P2P 네트워크를 가정하여 예시 스키마에 대하여 OLAP분석질의를 수행하고 서버 혹은 클라이언트 노드간 데이터를 전송 받는 Cloud P2P OLAP 프로그램을 구현하여, 정해진 시나리오대로 성능 분석을 하였다. 마지막으로 제안하는 알고리즘의 2번째 레이어를 일반적인 접근방식인 R-트리 접근 방식과, 제안하는 Quadtree 변형 접근 방식으로 나누어 각각을 구현하고 둘간의 성능을 삽입과 조회 위주로 비교 평가하였다. 실험에 사용된 스키마 구조는 아래 (그림 9)와 같으며 스키마의 데이터 사이즈 및 예시 쿼리의 평균 수행 시간은 아래 (표 1)과 같다.
또한 인덱스가 중앙 관리되는 하이브리드 P2P하에서 중앙관리 인덱스 서버의 성능 극대화 및 효율적인 관리를 위해 클라우드 시스템 내의 인덱스 서버 활용도를 검증하였다. 본 논문에서 제안하는 방법은 P2P OLAP에서 시계열적인 재활용과 물리적, 논리적 인접성에 대한 고려는 필수적으로 큐브 캐시에 대한 다차원 범위 질의가 가능해야 하고, 그러한 질의는 기존의 DHT 기법의 structured P2P에서는 제약이 심하기 때문에 다단계의 하이브리드 중앙관리 P2P 방식을 활용하도록 발상의 전환을 하였다.
본 논문에서 제안하는 최종 Cloud P2P OLAP 인덱스는 레이어1에서 큐브의 위상관계를 트리화 하였으며, 레이어2에서는 물리적, 논리적 2차원 인접성 인덱스에 시계열 인덱스를 연동하여 Quadtree의 중간 노드에 데이터 영역으로 해당 시계열 범위 정보가 Interval-트리형태로 부분 관리 되도록 하였다. 즉, 상위 노드의 Interval에서 포함되지 않은 구간은 하위의 모든 노드의 Interval을 뒤져도 포함되지 않은 구간임을 보장한다.
본 논문의 인덱스 레이어2에서는 1차원의 물리적 인접성 정보와 1차원의 부서 유사도 정보를 논리적 인접성으로 하는 2차원의 인접성 정보를 새롭게 제안하였다. 물리적 인접성은 네트워크 속도를 위하여 인접해 있는 경우가 유리하며 논리적 인접성은 재귀적으로 트리를 확장한다.
본 논문이 제안한 주요 인덱스 알고리즘에 대하여는 시뮬레이션을 통해 일반적인 그리드 시스템이 사용하고 있는 알고리즘과의 비교 테스트를 수행하였다. 비교 실험에 사용된 R-트리 알고리즘은 여러 R-트리의 변형 중, 최악의 경우에 있어 성능이 가장 좋은 것으로 알려져 있는 PR-트리[25]를 이용하였다.
Cloud P2P OLAP과 일반 OLAP의 비교 실험에서 정해진 시나리오는 최선의 경우와 최악의 경우 그리고 랜덤의 경우 세 경우로 나누어지며, 랜덤의 경우 포함 세 경우 모두 질의 수행 시간 및 질의 수행 시나리오가 정해져 있어 제안 시스템과 일반 시스템의 비교 평가가 가능하도록 하였다. 비교 대상 시스템은 전통적인 방식으로 구현 된 OLAP 이며, 해당 OLAP 은 P2P 네트워크 OLAP 클라이언트를 변형하여 모든 쿼리를 ROLAP 서버에 직접 요청하는 형태로 구현하였다.
5 하에서 C#을 이용하여 개발 되었으며, P2P 및 Cloud 내 SOA 서비스 통신 프로토콜은 WCF를 이용하여 RPC방식의 SOAP프로토콜을 이용하여 개발하였다. 서버 인덱스를 모니터링 하는 프로그램과 클라이언트 프로그램이 있으며, 클라이언트 프로그램은 모두 WCF Self Hosting 기능을 이용하여 자체 서버 기능을 내장하도록 구현하였다. 아래는 구현된 서버 인덱스 모니터링 툴과 클라이언트의 UI이다.
첫째로 마이크로 소프트 애저(Azure)의 플랫폼 서비스[19] 하에서 인스턴스를 늘려가면서 성능 추이를 실험하였다. 성능 테스트는 인스턴스 하나에서 복수개의 인덱스를 관리하도록 하고, 이후 인스턴스를 늘려가며 수평적 확장을 해가면서 일정 시간에 작업처리 한 태스크의 수로 테스트 하였다. 또한 동일한 인스턴스 개수에 대하여 시스템 리소스를 높게 할당해가며 수직적 확장을 통해서도 성능 변화를 테스트 해 보았다.
위의 특성을 이용하여 본 논문은, 각각의 노드가 기 집계된 데이터큐브의 P2P 복제자 역할을 할 뿐 아니라, 서브 파생 큐브에 대한 쿼리를 처리 할 중간 하이브리드 서버 역할을 할 수 있도록 하였다. 또한, 서버 요청은 집계가 존재하지 않는 영역으로 국한 시키고, 복수 클라이언트 노드가 비동기적으로 동시에 서로 데이터를 주고받을 수 있도록 새로운 개념의 Cloud P2P OLAP 시스템을 제안 하였으며, 이를위한 효율적인 인덱스 구조를 제안하였다.
이후 P2P 시스템에 대한 연구가 unstructured P2P 방식에서 DHT 방식의 structured P2P로 발전함에 따라 발전된 P2P 알고리즘들을 접목한 다양한 연구가 OLAP에 접목되어 등장하였다[14]. 이는 P2P의 최신 기법인 Chord를 이용한 DHT 기법에서 해쉬 테이블 대신 Quadtree를 공유하는 형태로 다차원 범위 질의가 가능하도록 하였다.
그러나 천문학적인 크기로 확장될 수 있는 큐브 데이타 자체가 클라우드 시스템에서 관리되는 경우 지속적인 비용이 지불된다는 점과, 성능 측면에서도 단일 노드를 통한 P2P에 비하여 이점이 없음을 실험을 통하여 확인 하였다. 이러한 이유에서 본 제안 시스템에서는 P2P의 중앙관리 인덱스에 한하여 클라우드 시스템을 이용하고 있으며 데이타 자체는 클라이언트 시스템을 통하여 P2P로 전달 받고 각 노드가 데이타를 공유하는 시스템을 고려하였다.
본 논문에서는 ROLAP의 유연성 및 확장성에 MOLAP의 속도상의 이점을 제공하고자 수많은 사용자의 클라이언트를 재활용 가능한 분산 노드화하여 각 노드간에 P2P로 큐브 캐시를 공유하는 시스템을 제안하였다. 이를 최적화된 알고리즘으로 고안하여 비교 및 검증을 수행하였다. 또한 인덱스가 중앙 관리되는 하이브리드 P2P하에서 중앙관리 인덱스 서버의 성능 극대화 및 효율적인 관리를 위해 클라우드 시스템 내의 인덱스 서버 활용도를 검증하였다.
본 논문에서 실험은 크게 3가지 형태로 수행하였다. 첫째는 PaaS 플랫폼 서비스 클라우드 상에서 인스턴스의 개수를 증가시키면서 인덱스 서버의 성능의 변화를 살펴보았다. 둘째는 실제 P2P 네트워크를 가정하여 예시 스키마에 대하여 OLAP분석질의를 수행하고 서버 혹은 클라이언트 노드간 데이터를 전송 받는 Cloud P2P OLAP 프로그램을 구현하여, 정해진 시나리오대로 성능 분석을 하였다.
클라우드 인덱스 서버 성능 및 활용도 검증은 두 가지 실험을 통하여 검증하였다. 첫째로 마이크로 소프트 애저(Azure)의 플랫폼 서비스[19] 하에서 인스턴스를 늘려가면서 성능 추이를 실험하였다. 성능 테스트는 인스턴스 하나에서 복수개의 인덱스를 관리하도록 하고, 이후 인스턴스를 늘려가며 수평적 확장을 해가면서 일정 시간에 작업처리 한 태스크의 수로 테스트 하였다.
클라우드 인덱스 서버 성능 및 활용도 검증은 두 가지 실험을 통하여 검증하였다. 첫째로 마이크로 소프트 애저(Azure)의 플랫폼 서비스[19] 하에서 인스턴스를 늘려가면서 성능 추이를 실험하였다.
클라이언트 노드들의 경험 데이터 및 리소스를 활용하여 수많은 노드의 적은 양의 메모리를 클라우드 시스템에 존재하는 거대한 중앙 메모리 인덱스에 연결하여 구글의 Bigtable와 같이 거대한 메모리 데이터베이스 풀을 만드는 것이 가능하도록 분리된 인덱스 레이어를 제시하였다.
또한, 서버 요청은 집계가 존재하지 않는 영역으로 국한 시키고, 복수 클라이언트 노드가 비동기적으로 동시에 서로 데이터를 주고받을 수 있도록 새로운 개념의 Cloud P2P OLAP 시스템을 제안 하였으며, 이를위한 효율적인 인덱스 구조를 제안하였다. 특히 알고리즘 측면에서 물리적, 논리적 인접노드에서 데이터를 가져올 수 있도록 하였고, 시계열적인 특성을 이용하여 서버에 요청하는 데이터의 양을 최소화하고, 과거의 캐시데이터가 최대한 미래에도 활용될 수 있도록 하는데 초점을 두었다.
본 논문은 이러한 분산 중앙 관리 인덱스 구조에 초점을 두어 OLAP에 다단계의 Hybrid P2P를 접목하였다. 효율적인 인덱스 관리가 제한된 형태로 OLAP에 P2P나 Grid를 도입한 개념은 이미 몇몇 유사 연구가 진행 된 바 있으나, 본 논문에서는 추가로 기존 연구가 간과 하였던 아래와 같은 특성을 전제로 서버에서 범위 질의 및 시계열 관리가 가능한 보다 향상된 알고리즘을 제안하였다.
대상 데이터
본 논문에서 제안하는 Cloud P2P OLAP 시스템은 3가지 인덱스 레이어로 구성되어 있다. 이중 중앙 클라우드 인덱스 서버는 2개의 레이어로 구성되어 있으며, 클라이언트 서버(클라이언트이면서 서버 역할을 하는 거점 서버)는 1개의 인덱스 레이어로 구성되어 있다.
본 논문은 총 5장으로 구성하였다. 제1장은 본 논문의 개요 및 인덱스 고려사항을 기술하고, 제2장에서는 제안하는 연구에 대한 이론적 배경과 기존의 유사 관련 연구 동향을 기술하였다.
본 논문이 제안하는 인덱스의 레이어3에서는 클라이언트 노드의 메모리 DB 서버로서의 역할에 초점을 두고 있다. 최근에는 메모리상에서 SQL과 비슷하게 쿼리를 하여 매우 뛰어난 성능으로 결과를 조회하는 기법이 프로그램 언어 레벨 혹은 가상머신 차원에서 지원되고 있다.
제3장에서는 제안하는 알고리즘의 전체 아키텍처와 서버 측면의 효율적인 인덱스 알고리즘을 제시하였다. 제4장에서는 실험을 해보았으며. 제5장에서는 연구의 결과를 요약하고 분석하였다.
이론/모형
본 논문이 제안한 주요 인덱스 알고리즘에 대하여는 시뮬레이션을 통해 일반적인 그리드 시스템이 사용하고 있는 알고리즘과의 비교 테스트를 수행하였다. 비교 실험에 사용된 R-트리 알고리즘은 여러 R-트리의 변형 중, 최악의 경우에 있어 성능이 가장 좋은 것으로 알려져 있는 PR-트리[25]를 이용하였다. 삽입 성능 비교 결과, 예상하였던 바와 같이 비트맵 인덱스는 크기가 매우 커지는 반면 (그림 15)와 (그림 16)과 같이 삽입 성능은 가장 좋았다.
성능/효과
(1) 성능 측면과 범위질의 가능여부 측면에서 기존 DHT P2P 보다 중앙관리 P2P 가 유리하다.
또한 인스턴스 수를 3개에서 20개 60개로 늘리자 선형적인 성능 향상을 확인 할 수 있었다. (그림 13)에서는 디스크 읽기 쓰기 성능을 인스턴스 수를 달리 하며 테스트 한 결과이며, 읽기에서는 인스턴스를 15배 늘려도 성능이 오히려 다소 저하 되었으며, 쓰기에서는 약간의 성능 개선이 있었으나 비슷함을 확인 할 수 있었다. 이처럼 파일 객체 자체를 여러 인스턴스에 분산 관리 하는 경우에는 클라우드상에 큰 이점은 없음을 알 수 있었으며, 모든 트래픽에 사용한 만큼의 비용 지불이 이루어지므로, 로컬 LAN 상의 P2P가 훨씬 유리함을 확인 할 수 있었다.
삽입 성능 비교 결과, 예상하였던 바와 같이 비트맵 인덱스는 크기가 매우 커지는 반면 (그림 15)와 (그림 16)과 같이 삽입 성능은 가장 좋았다. Quadtree와 PR-트리 는 Interval-트리 접목 전에는 Quadtree가 근소하게 성능이 좋았으나, Interval-트리 접목 후에는 본론에서 언급했던 바와 같이 균형 유지를 위한 노드 split이 없어 현격한 성능 우위를 보여주었다.
Quadtree의 균형 유지를 위한 전처리 알고리즘의 영향도는 (그림 17)과 같이 대략 40% 가량의 성능 개선 효과를 보여주었다. 조회 성능 비교에서는 노드 수에 비례한 부하의 증가가 지수함수 양상을 보이지는 않는 다는 결과를 도출 할 수 있었다.
또한 최근에는 일부 BI기업에서 OLAP전체 시스템을 클라우드 시스템 하에서 운용하는 시도도하고 있다. 그러나 천문학적인 크기로 확장될 수 있는 큐브 데이타 자체가 클라우드 시스템에서 관리되는 경우 지속적인 비용이 지불된다는 점과, 성능 측면에서도 단일 노드를 통한 P2P에 비하여 이점이 없음을 실험을 통하여 확인 하였다. 이러한 이유에서 본 제안 시스템에서는 P2P의 중앙관리 인덱스에 한하여 클라우드 시스템을 이용하고 있으며 데이타 자체는 클라이언트 시스템을 통하여 P2P로 전달 받고 각 노드가 데이타를 공유하는 시스템을 고려하였다.
물리적 인접성은 네트워크 속도를 위하여 인접해 있는 경우가 유리하며 논리적 인접성은 재귀적으로 트리를 확장한다. 또한 시계열을 조회 할 때 업무 유사성이 있는 부서부터 데이터 존재 여부를 파악하는 것이 확률적으로 유리하며 향후 재활용 측면에서도 유리함을 고려하였다. 2차원 정보를 표현하는 인덱스 구조는 R-트리, KD-트리 등 다양한 인덱스가 존재한다.
(그림 12)에서 알 수 있듯이 VM-size를 small에서 medium으로 변경하자 약간의 성능 개선 효과를 얻을 수 있었다. 또한 인스턴스 수를 3개에서 20개 60개로 늘리자 선형적인 성능 향상을 확인 할 수 있었다. (그림 13)에서는 디스크 읽기 쓰기 성능을 인스턴스 수를 달리 하며 테스트 한 결과이며, 읽기에서는 인스턴스를 15배 늘려도 성능이 오히려 다소 저하 되었으며, 쓰기에서는 약간의 성능 개선이 있었으나 비슷함을 확인 할 수 있었다.
따리서 선형적인 성능 향상도 꾀할 수 있도록 하였다. 마지막으로 본 논문은 클라우드와 P2P를 결합한 아키텍처를 OLAP 분야에서 사용할 수 있도록 처음으로 제안하였다는 측면에서 매우 의미 있는 연구라고 할 수 있다.
본 논문에서 제안하는 Cloud P2P OLAP은 클라우드 시스템을 도입하여 유동적으로 인스턴스를 추가 및 삭제 할 수 있으며, 이로부터 시스템의 확장성 및 가용성을 극대화 할 수 있다. 따리서 선형적인 성능 향상도 꾀할 수 있도록 하였다.
본 논문에서 제안하는 다단계(N단계) 하이브리드 P2P 형태에서 N은 전제하고 있는 여러 특성을 고려한 3단계 레이어의 인덱스 메모리 크기에 따라 다단계의 깊이가 유동적으로 결정됨을 의미한다. N의 최소값은 2이며 이 경우는 중앙서버와 1단계의 클라이언트 서버 만 존재하는 P2P 이다.
비교 실험에 사용된 R-트리 알고리즘은 여러 R-트리의 변형 중, 최악의 경우에 있어 성능이 가장 좋은 것으로 알려져 있는 PR-트리[25]를 이용하였다. 삽입 성능 비교 결과, 예상하였던 바와 같이 비트맵 인덱스는 크기가 매우 커지는 반면 (그림 15)와 (그림 16)과 같이 삽입 성능은 가장 좋았다. Quadtree와 PR-트리 는 Interval-트리 접목 전에는 Quadtree가 근소하게 성능이 좋았으나, Interval-트리 접목 후에는 본론에서 언급했던 바와 같이 균형 유지를 위한 노드 split이 없어 현격한 성능 우위를 보여주었다.
최악의 경우 매번 다른 쿼리를 수행하는 경우 일반 OLAP과 동일한 결과가 나왔으며, 시나리오 대로 최상의 경우 초반에만 일반 OLAP 과 동일하고 이후에는 모든 쿼리에 대하여 1초 미만의 응답 속도를 보였다. 시나리오에 따라 랜덤으로 정해진 수행을 하는 경우 또한 (그림 14)와 같이 제안하는 Cloud P2P OLAP이 훨씬 응답 속도가 빠르고 서버에 적은 부하를 주는 것이 확인 되었다.
대신 본 논문에서는 메모리 데이터베이스의 메모리 상태를 직렬화하여 재부팅 후에도 사용 가능 하도록 하였으며, 해당 파일을 복수개의 노드에서 분산하여 파일 청크를 받을 수 있도록 동일 큐브의 주소 목록을 DHT 형태로 공유 하도록 하였다. 이러한 접근은 본 논문의 레이어2 인덱스가 인접성 인덱스를 통해 물리적, 논리적으로 최적의 후보를 선정해 주었다고 할지라도 네트워크 회선 장애 및 회선 부하 등으로 실제 속도가 좋지 않은 경우 복수의 후보 군을 통해 복수 전달 받음으로 인해 실세계에서 가장 네트워크 연결이 빠른 노드로부터 가장 많은 패킷을 전송 받도록 하는 효과도 가지고 있다. 일반적인 DHT기법의 P2P는 찾고 있는 DHT인덱스를 보유한 노드를 찾기 위해 여러 노드를 뒤져나가야 하지만 Cloud P2P OLAP에서는 중앙에서 DHT보유 노드를 찾아주고 해당 노드는 복수개의 노드에 동시 전송 명령을 전달하며, 이를 통해 시계열 데이터의 전파 및 노드 활성화 상태 검증의 두 가지 관리 요소를 동시에 꾀할 수 있다.
조회 성능 비교에서는 노드 수에 비례한 부하의 증가가 지수함수 양상을 보이지는 않는 다는 결과를 도출 할 수 있었다. 이로 인하여 인덱스를 여러 개 만들어 동시 테스트를 수행하지 않고 한 개의 인덱스에 대하여 많은 부하를 동시에 주어 성능 테스트를 하더라도 전체 시스템의 부하 테스트가 가능함을 유추할 수 있었다. 따라서 최대 10,000개까지의 노드를 1,000번씩 테스트 하여 평균값으로 성능 검증을 하였다.
(그림 13)에서는 디스크 읽기 쓰기 성능을 인스턴스 수를 달리 하며 테스트 한 결과이며, 읽기에서는 인스턴스를 15배 늘려도 성능이 오히려 다소 저하 되었으며, 쓰기에서는 약간의 성능 개선이 있었으나 비슷함을 확인 할 수 있었다. 이처럼 파일 객체 자체를 여러 인스턴스에 분산 관리 하는 경우에는 클라우드상에 큰 이점은 없음을 알 수 있었으며, 모든 트래픽에 사용한 만큼의 비용 지불이 이루어지므로, 로컬 LAN 상의 P2P가 훨씬 유리함을 확인 할 수 있었다.
조회 성능 비교 결과 (그림 18)과 같이 100-10000개 노드의 실험에서는 전반적으로 PR-트리가 성능이 더 좋음을 알 수 있다. 그러나 (그림 19)의 경우와 같이 100-1000개 노드인 경우만 확대 하여 비교해 보면, 노드 개수가 600미만 일 때는 Balanced Quadtree+Interval-트리의 조합이 비슷하거나 근소하게 성능이 더 좋음을 알 수 있었다.
Quadtree의 균형 유지를 위한 전처리 알고리즘의 영향도는 (그림 17)과 같이 대략 40% 가량의 성능 개선 효과를 보여주었다. 조회 성능 비교에서는 노드 수에 비례한 부하의 증가가 지수함수 양상을 보이지는 않는 다는 결과를 도출 할 수 있었다. 이로 인하여 인덱스를 여러 개 만들어 동시 테스트를 수행하지 않고 한 개의 인덱스에 대하여 많은 부하를 동시에 주어 성능 테스트를 하더라도 전체 시스템의 부하 테스트가 가능함을 유추할 수 있었다.
(그림 14)는 해당 시나리오를 총 100번 수행한 결과의 누적 값이다. 최악의 경우 매번 다른 쿼리를 수행하는 경우 일반 OLAP과 동일한 결과가 나왔으며, 시나리오 대로 최상의 경우 초반에만 일반 OLAP 과 동일하고 이후에는 모든 쿼리에 대하여 1초 미만의 응답 속도를 보였다. 시나리오에 따라 랜덤으로 정해진 수행을 하는 경우 또한 (그림 14)와 같이 제안하는 Cloud P2P OLAP이 훨씬 응답 속도가 빠르고 서버에 적은 부하를 주는 것이 확인 되었다.
또한 (표 2)에서 알 수 있듯이, 실제 OLAP 데이터 큐브 인덱스를 통한 실험에서도 단일 멀티 코어 PC에서 쓰레드를 늘려서 비동기 수행하는 것은 약간의 성능 개선이 있었으나 선형적인 성능 개선을 이루지는 못했다. 클라우드에서는 단일 인스턴스가 PC에서의 싱글 프로세스 보다 다소 느린 경향이 있었으나 인스턴스를 늘리며 인덱스를 수평적 확장을 함에 따라 선형적인 성능 향상을 가져와 4개의 인스턴스에서 이미 듀얼 코어의 4개 쓰레드 보다 2배 이상의 성능 향상이 있음을 확인 할 수 있었다.
후속연구
이중 중앙 클라우드 인덱스 서버는 2개의 레이어로 구성되어 있으며, 클라이언트 서버(클라이언트이면서 서버 역할을 하는 거점 서버)는 1개의 인덱스 레이어로 구성되어 있다. 복수개의 레이어를 사용함으로써 서로 다른 여러 성능 개선 요소를 모두 해결할 수 있으며 추후 서버 부하를 고려하여 레이어 단위로 Hybrid P2P의 깊이를 확장하도록 하기 위함이다.
질의응답
핵심어
질문
논문에서 추출한 답변
클라우드 시스템의 단점은 무엇인가?
현재 클라우드 시스템이 많은 각광을 받고 있지만, 클라우드 시스템을 데이터베이스 시스템에 적용하기 위하여 서는 해결해야 할 문제점이 많이 있다[2]. 클라우드 상의 데이터베이스 클러스터링 및 대용량 스토리지 서비스는 가상화된 시스템 하에서 일반적인 시스템보다 훨씬 큰 입출력 부하를 가져오면서, 가용성 지대를 넘어서는 경우 보다 많은 네트워크 비용도 소모하는 단점을 지니고 있다.
클라우드의 시스템의 정의는 무엇인가?
클라우드의 시스템의 정의는 여러 가지가 존재하지만, 일반적으로 대규모 서버의 연결된 집단을 통한 플랫폼, 인프라 혹은 서비스 시스템을 말한다. 여기에는 개인 컴퓨터도 포함될 수 있어, 제안하는 Cloud P2P OLAP 시스템에서의 Cloud와 P2P와의 접목은 퍼블릭 클라우드와 프라이빗 클라우드가 접목 된 하이브리드 클라우드 시스템으로 분류가 가능하다.
클라우드 시스템이 각광을 받고 있는 가장 큰 이유는 무엇인가?
여기에는 개인 컴퓨터도 포함될 수 있어, 제안하는 Cloud P2P OLAP 시스템에서의 Cloud와 P2P와의 접목은 퍼블릭 클라우드와 프라이빗 클라우드가 접목 된 하이브리드 클라우드 시스템으로 분류가 가능하다. 클라우드 시스템이 각광을 받고 있는 가장 큰 이유는, 시스템 리소스를 유연하고, 확장 가능하게 사용 할 수 있으며, 이 역시도, 사용한 만큼만 비용 지불 하면 된다는 점 때문이다. 현재 클라우드 시스템이 많은 각광을 받고 있지만, 클라우드 시스템을 데이터베이스 시스템에 적용하기 위하여 서는 해결해야 할 문제점이 많이 있다[2].
참고문헌 (25)
F. Chang, J. Dean, S. Ghemawat, WC. Hsieh, DA. Wallach, M. Burrows, T. Chandra, A. Fikes and RE. Gruber, "Bigtable: A distributed storage system for structured data", Journal ACM Transactions on computer Systems, Vol.26, No.2, pp. 1-14, 2008.
C. Loboz, S.Smyl and S.Nath, research .microsoft.com, "DataGarage: Warehousing Massive Amounts of Performance Data on Commodity Servers", Microsoft Research Technical Report MSR-TR-2010-22, NE Computing, 2010.
S. Russell, V. Yoon and G. Forgionne, "Cloud-based Decision Support Systems and Availability Context: The Probability of Successful Decision Outcomes", Information Systems and E-Business Management, Vol.8, No.3, pp.189-205, 2010.
C. Zhang, H. De Sterck, A. Aboulnaga, H. Djambazian and Rob Sladek, "Case Study of Scientific Data Processing on a Cloud Using Hadoop", High Performance Computing Systems and Applications, vol.5976, No.1, pp.400-415, 2010.
김진수, 김태웅, "OwFS: 대규모 인터넷 서비스를 위한 분산 파일 시스템", 한국정보과학회 정보과학회지, 제27권 제5호, pp.77-85, 2009.
A. Thusoo, J. Sen Sarma, N. Jain, Z. Shao, P. Chakka, N. Zhang, S. Antony, H. Liu and R. Murthy, "Hive - A Petabyte Scale Data Warehouse Using Hadoop", proceeding of international conference on data engineering, pp.996-1005, 2010.
A. Thusoo, Z. Shao, S. Anthony, D. Borthakur, N. Jain, J. Sen Sarma, R. Murthy and H. Liu, "Data warehousing and analytics infrastructure at facebook", Proceeding of international conference on Management of data, 1013-1020, 2010.
M. Arnedo,M. del, P. VillamilandR. Villanueva, "Improving Performance of Declarative Query Execution in DHT-Based Systems", International Conference on Internet and Web Applications and Services, pp.223-228, 2010.
P. Kalnis, WS. Ng, BC. Ooi, D. Papadias and K. Tan, "An adaptive peer-to-peer network for distributed caching of olap results". Proceeding of international conference of Management of data, pp.25-36, 2002.
P. Kalnis, W. Ng, B. Ooi and K. Tan, "Answering similarity queries in peer-to-peer networks", Information Systems, Vol.31, No.1, pp.57-72, 2006.
M. Espil and AA. Vaisman, "Aggregate queries in peer-to-peer OLAP", Proceeding of the ACM international workshop on data warehousing, pp.102-111, 2004.
A. Vaisman, M. Espil and M. Paradela, "P2P OLAP: Data model, implementation and case study", Information Systems, Vol.34, No.2, pp.231-257, 2009.
M. Lawrence and A. Rau-Chaplin, "The OLAP-enabled grid: Model and query processing algorithms", International Symposium on High-performance Computing in an Advanced Collaborative Environment, pp.4, 2006.
A. Vaisman, M. Espil and M. Paradela, "P2P OLAP: Data model, implementation and case study", Information Systems, Vol.34, No.2, pp.231-257, 2009.
A. Mondal, Y. Lifu and M. Kitsuregawa, "P2pr-tree: An r-tree-based spatial index for peer-to-peer environments", Current Trends in Database Technology EDBT2004 Workshops, pp.516-516. 2004.
P. Ganesan, B. Yang and H. Garcia-Molina, "One torus to rule them all: multi-dimensional queries in P2P systems". Proceeding of the international workshop on the Web and Database, pp.19-24, 2004.
Windows Azure Platform, "Windows Azure, Microsoft Hosting, Online Application, Application Hosing", http://www.microsoft.com/windowsazure/windowsazure/, 2010.
SalesForce.com Platform, "Force.com The leading cloud platform for business apps". http://www.salesforce.com/platform/, 2010.
Google AppEngine Platform, "Run your web apps on Google's infrastructure. Easy to build, easy to maintain, easy to scale.". http://code.google.com/intl/en/appengine/, 2010.
F. Dehne, M. Lawrence and A. Rau-Chaplin. "Cooperative caching for grid-enabled OLAP". International Journal of Gridand Utility Computing, Vo.1, No.2, pp.169. 2009.
Extreme Computing Group, "All Azure Benchmark Test Cases". http://azurescope.cloudapp.net/BenchmarkTestCases/, 2010.
L. Arge, M. Berg, H. Haverkort and K. Yi. "The priority R-tree: A practically efficient and worst-case optimal R-tree". ACM Transactionson Algorithms(TALG), Vol.4, No.1, pp.1-30. 2008.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.