A spatial big data stream is an unbounded and continuous data stream with geospatial features such as point, line, and polygon. With the evolution of Internet-of-Things technology, it has become much easier to acquire spatial big data streams from various sources such as smart cars, road network sensors, smart phones, and geo-tagged Social Network Services. Distributed and real-time processing are required to effectively process spatial big data streams; however, existing approaches such as spatial databases or spatial Hadoop are unable to meet these requirements. Distributed Stream Processing System implemented with spatial operations may be one of the most plausible solutions, but it also has a load imbalance issue. The spatial data streams inherently have a skewed and dynamically changing distribution; therefore, the system may display poor performance unless the entire load is efficiently distributed among workers. Previous studies to solve the load imbalance problem is not directly applicable to processing spatial queries since it does not consider the spatial locality of data. In this paper, we propose a load balancing algorithm, Adaptive Spatial Key Grouping (ASKG), which is specialized for spatial data stream. The main idea of ASKG is to learn the previous distribution of a data stream and utilize it to suggest a new grouping scheme that evenly distributes the incoming data stream into workers. By repeating the procedure periodically, the system can balance loads among workers adaptively to the spatial distribution of data stream. To evaluate the validity of our proposed algorithm in a variety of environments, we performed an evaluation with real datasets by varying the number of workers, input rate, and processing overhead. Compared to two other alternative algorithms, ASKG reduced load imbalance up to around 95%, leading directly to an increase in throughput of up to 147%, and to a decrease in latency of up to 99%.
공간 빅데이터 스트림은 점, 선, 다각형과 같은 공간 속성을 가진 무한하고 연속적인 데이터 스트림을 일컫는다. 사물 인터넷의 발달로 인해 스마트 자동차, 도로망의 센서, 스마트폰과 같은 다양한 소스로부터 공간 빅데이터 스트림을 수집하는 것이 매우 용이해졌다. 공간 빅데이터 스트림을 효과적으로 처리하기 위해서는 실시간 분산 처리가 필수적이지만, 공간 데이터베이스나 공간 하둡과 같은 기존의 접근 방법은 이에 적합하지 않다. 분산 스트림 처리 시스템에 공간 연산 기능을 구현하는 것이 가장 적합한 해결책 중 하나이지만, 이 또한 부하 불균형 문제를 가지고 있다. 공간 데이터 스트림은 왜곡되고 동적으로 변화하는 분포를 가지기 때문에 전체 부하가 분산 클러스터 내의 작업자(worker)들에게 효율적으로 분배되지 않을 경우 전체 시스템의 성능이 저하된다. 부하 불균형 문제를 해결하기 위한 기존 연구들은 데이터간의 공간 지역성을 고려하지 않아 공간 연산 처리에 적합하지 않다. 본 연구에서는 공간 데이터 스트림에 특화된 부하 균형화 알고리즘인 Adaptive Spatial Key Grouping (ASKG)을 제안한다. ASKG의 핵심 아이디어는 공간 데이터 스트림의 최근 분포를 학습하고 이를 기반으로 향후 유입되는 데이터 스트림이 각 작업자에게 고르게 분배되도록 하는 새로운 그룹핑 계획(Grouping scheme)을 제안하는 것이다. 이를 공간 분포의 변화에 맞춰 주기적으로 반복함으로서 적응적으로 부하 불균형을 해결할 수 있다. 제안 방법의 효과를 여러 환경에서 검증하기 위해 실제 데이터를 기반으로 작업자의 수, 입력 속도, 공간 연산 비용을 다양하게 변화시키며 성능을 평가하였다. 다른 두 개의 대안 알고리즘과 비교하여 제안 방법은 부하 불균형을 최대 약 95% 절감하였으며, 이로 인해 처리량은 최대 약 147% 증가하였고 지연 시간은 최대 약 99% 감소하였다.
