분산 공간 데이터 스트림 시스템에서 연산 처리율 기반의 적응적 업스트림 백업 기법

국문 초록 (Abstract)

분산 공간 데이터 스트림 처리에서는 분산 노드의 활용도를 높이고 고장이 발생한 경우 신속하게 시스템을 복구하기 위해 하위 노드에서 처리된 튜플에 대해 상위 노드로 데이터를 백업한다. 그러나 데이터의 유입량이 증가하 고 노드의 연산 결과를 다수의 하위 노드들과 공유할 때 튜플 처리가 지연되면 상위 노드의 삭제 지연으로 인해 백 업 데이터의 손실을 야기할 수 있다. 본 논문에서는 노드들의 데이터 유입량과 하위 노드의 연산 처리율을 분석하고 적응적 업스트림 백업 방법을 적용하여 노드의 평균 부하율을 감소시키고, 노드 연산 결과의 공유에 따른 데이터 손 실을 최소화하는 방법을 제안한다. 그리고 실험에서는 제안 기법을 통해 데이터 손실을 방지하고, 노드 모니터링에 소요되는 CPU 사용률을 평균 20% 감소시키는 결과를 나타낸다.

다국어 초록 (Multilingual Abstract)

In distributed spatial data stream processing, processed tuples of downstream nodes are replicated to the upstream node in order to increase the utilization of distributed nodes and to recover the whole system for the case of system failure. However, while the data input rate increases and multiple downstream nodes share the operation result of the upstream node, the data which stores to output queues as a backup can be lost since the deletion operation delay may be occurred by the delay of the tuple processing of upstream node. In this paper, the adaptive upstream backup scheme based on operation throughput in distributed spatial data stream system is proposed. This method can cut down the average load rate of nodes by efficient spatial operation migration as it processes spatial temporal data stream, and it can minimize the data loss by fluid change of backup mode. The experiments show the proposed approach can prevent data loss and can decrease, on average, 20% of CPU utilization by node monitoring.

참고문헌 (Reference)

1 정원일, "분산 공간 데이터 스트림 처리에서 질의 영역의 겹침을 고려한 공간 연산 배치 기법" 한국산학기술학회 13 (13): 2713-2719, 2012

2 J. Gray, "Why do computers stop and what can be done about it?" Tandem Computers 1985

3 "Tiger/Line Shapefiles"

4 S. R. Ahuja, "The Rapport Multimedia Conferencing System" 52-58, 1988

5 S. Prabhakar, "Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects" 51 (51): 1124-1140, 2002

6 C.S Jensen, "Query and update efficient B+-tree based indexing of moving objects" 768-779, 2004

7 Jensen C.S, "Query and update efficient B+-tree based indexing of moving objects" VLDB 2004

8 B. Gedik, "MobiEyes: Distributed processing of continuou sly moving queries on moving objects in a mobile system" 2004

9 M. A. Shah, "Highly-available, fault-tolerant, parallel dataflows" 2004

10 J.H. Hwang, "High-availability algorithms for distributed stream processing" 2005

11 J. Barlett, "Fault tolerance in Tandem computer systems" Tandem Computers 1986

12 C. Park, "Design and Implementation of a Spatial DSMS based on STREAM" 131-136, 2006

13 Iwerks G.S, "Continuous K-nearest neighbor queries for continuously moving points with updates" VLDB 2003

14 Hu H, "A generic framework for monitoring continuous spatial queries over moving objects" SIGMOD 2005