연속집계 질의처리를 위한 계층구조 형식의 자원공유 기법인 B-Int는 집계정보 생성 과정에서 튜플이 입력되면 최하위 계층에 저장하고, 입력된 두 튜플로부터 산출된 집계정보를 상위 계층에 유지한다. 이어 상위 계층의 두 집계정보로부터 하나의 집계정보를 계산하여 상위 계층에 저장한다. 이러한 과정으로 집계정보가 상위 계층에서 관리되는 계층구조를 이룬다. B-Int는 질의처리 과정에서 질의 범위를 만족하는 집계정보를 검색하고, 각 집계 정보에 저장된 집계 값들을 계산하여 질의 결과를 반환한다. 이러한 B-Int 기법의 단점은 계층별 집계정보 유지를 위한 메모리 비용이 많고, 질의처리 시 질의 범위에 부합하는 집계정보를 탐색을 위해 계층별 검색이 발생하여 질의처리 성능이 저하된다는 문제가 있다.

계층구조 기반으로 B-Int의 단점을 개선하기 위해 제안된 L-Int은 계층구조를 좌우로 구축하여 두 범위만 검색하여 질의 결과를 생성한다. L-Int은 대칭 집계정보를 기반으로 질의 범위에 해당하는 계층의 집계정보를 이용하여 질의를 처리할 수 있다. 따라서 L-Int은 B-Int과 비교하면 질의 범위를 만족하는 대상을 검색하는 속도를 개선하였으나, 대칭형의 계층구조를 사용하기 때문에 계층구조 구축시간과 메모리 낭비는 B-Int보다 커지는 문제가 있다. 또한, 질의처리가 지연될 경우 메모리 비용이 증가하는 문제가 있다.

자원공유 기반의 연속집계 질의처리를 지원하는 페인 기법이 제시되었다. 연속집계 질의에서 질의 범위를 규정하는 슬라이딩 윈도우는 질의 범위가 갱신범위보다 크므로 질의처리를 위해 스트림 버퍼 탐색시 중복 영역을 포함하게 되는데, 페인 기법은 이러한 중복 영역의 반복계산을 방지한다. 페인 기법에서는 입력 데이터를 갱신범위와 질의 범위의 최대공약수 단위로 구분하여 튜플들의 집계값을 관리한다. 질의처리 과정에서는 분할 저장된 팬의 집계 값을 이용하여 질의 결과를 반환하므로 튜플 집계 연산은 페인 구조를 생성할 때 한 번만 수행된다. 이는 기존 자원공유 기법에서 동일 튜플에 대한 집계 연산이 중복으로 수행하는 것에 비해 검색 비용이 감소되어 질의처리 성능이 향상된다. 그러나 해당 페인 기법은 단일 질의에만 적용할 수 있으며, 튜플기반 질의와 시간기반 질의가 동시에 수행되는 환경에서는 페인의 크기를 결정 할 수 없다. 또한, 갱신범위와 질의 범위가 서로소이면 팬 크기를 결정할 수 없다. 본 논문에서는 이러한 페인 기법의 단점을 개선하여 연속집계 질의처리에서 유용한 구조로의 확장을 제시한다.

스파크는 인-메모리 기반의 오픈소스 클러스터 컴퓨팅 프레임워크로 빅데이터에 대한 고속의 분석 작업을 지원하며, 일반적인 구성은 아래 <그림 1>과 같다.

<그림 1>에서 스파크 프레임워크는 HDFS(Hadoop file system), RDBMS(Relational database management system), NoSQL 등 다양한 형태의 데이터 소스를 기반으로 동작한다. YARN, Mesos, Spark Scheduler 등의 관리 계층에서는 데이터 소스에 대한 리소스 할당, 작업 스케줄링 및 결함처리 기능을 제공한다. 스파크 프레임워크의 엔진(Engine) 계층의 스파크 코어(Spark Core)는 작업 스케쥴 관리와 조정 및 RDD(Resilient Distributed Data)를 통해 빅데이터에 대한 다양한 연산 작업을 지원한다. Spark SQL, Spark Streaming, MLlib, GraphX 등 라이브러리(Library) 계층에서는 데이터 분석을 위한 용도별 라이브러리를 제공하며, 스파크 APIs 계층은 다양한 프로그래밍 개발을 위한 인터페이스를 제공한다.

스파크는 데이터 집합의 추상화 객체 개념으로 RDD를 제공하여, 다수의 노드에 분산하여 복수의 파티션으로 관리되어 장애가 발생해도 데이터 사용 이력 정보를 통해 복구할 수 있다. 또한, 스파크는 RDD를 분산 클러스터의 메모리에 저장하기 때문에 기계학습, 그래프 처리 등 반복계산이 많은 작업에 대해 하둡보다 실행 속도가 빠르다.

집계정보의 연속집계 질의처리 과정에서는 버퍼를 이동하면서 실행하는 범위에 포함되는 튜플들과 동일한 튜플로 구성된 페인과 타임유닛들을 검색한다. 이러한 페인과 타임유닛은 질의의 갱신범위와 질의범위를 고려한 크기로 설정되어야 하며, 등록된 연속질의들과 약수 관계여야 한다.

페인과 타임유닛이 질의 범위와 일치하면 약수관계이며, <그림 2>에서 연속질의와 집계정보의 약수 관계에 대해 예시한다.

<그림 2>에서 연속질의와 페인 및 타임유닛과의 약수 관계를 4가지로 나타낸다. 연속질의 Q₁과 Q₂의 질의 범위에 대해 (a)는 Q₁과 Q₂가 약수 관계로 {P₂,P₃}을 공통범위를 가지며, (b)에서는 Q₂가 P₁의 중간 부분에 걸쳐있어 두 질의가 약수 관계에 있지 않다. 타임유닛은 다수의 페인을 포함 할 수 있으며, (c)에서는 Q₁과 Q₂의 타임유닛이 약수 관계로 {TU₂}을 공통으로 포함하고 있으며, (d)는 Q₁과 Q₂에 대한 공통 타임유닛이 존재하지 않으므로 약수 관계에 있지 않음을 알 수 있다.

임의의 i번째 연속질의에 대해 갱신범위가 s_i, 질의 범위가 r_i(r_i ≥ s _i)이고, m번째 실행되는 범위가 I_i,m=(s_im, s_im + r_i)일 때, 집계정보의 크기가 p이고 k부터 l까지 연속적으로 생성되는 집계정보의 범위의 합이 I_{i, m}과 같으면 페인과 연속질의는 약수 관계이다.

등록된 질의들의 질의 범위와 갱신범위의 최대공약수로 약수 관계를 산출하며, 그 관계가 서로소일 경우 집계정보의 크기는 1로 설정한다. 실험 환경에서 초당 입력률이 일 만개를 상회하므로 타임유닛 집계정보에서의 크기는 1초로 설정한다. 그러나 페인 크기는 튜플 개수가 단위이므로 그 크기가 1인 경우 튜플별 집계정보를 생성하므로 메모리 비용이 증가한다. 따라서 튜플 기반 질의들은 1보다 큰 약수 관계의 페인을 계산해야 한다.

튜플을 기반으로 실행되는 연속질의의 페인 크기를 산출하기 위해 연속질의의 갱신범위와 질의 범위가 서로소가 아니면 NRP(Non relative prime) 질의, 서로소이면 RP(Relative prime) 질의로 구분한다. 이 두 유형의 질의 간의 관계를 n(n ≥ 1)개 질의가 모두 NRP 유형이고, 갱신범위와 질의범위가 모두 서로소가 아닌 SP(Single Pane), n이 1인 단일 RP 유형인 DP(Double Pane), 2 이상의 n개 질의의 갱신범위와 질의범위가 하나라도 서로소의 경우인 GP(Group Pane)으로 정의한다.

SP는 서로소가 아닌 n개의 질의에 대해 갱신범위를 s_i, 질의범위를 r_i라 할 때 약수 관계의 페인 크기는 gcd(s₁, s₂,...s_n, r₁, r₂,...r_n)로부터 페인 크기를 결정한다. DP는 질의범위와 갱신범위의 최대공약수가 1이므로 이 값으로 페인을 구성하면 집계정보 유지 비용이 매우 크다. 이에 단일 서로소 관계의 질의에서 페인 크기는 갱신범위를 s, 1보다 큰 임의의 α에 대해 (sα+p)인 r을 질의범위라고 할 때, 생성 페인의 크기는 질의와 약수관계인 2개의 p와 (s-p)를 활용한다. 이 두개의 팬 크기를 사용하면 질의범위와 갱신범위가 서로소인 질의에서 갱신범위가 2보다 크면 1이 아닌 팬 크기를 사용하여 집계정보를 생성한다. GP는 하나의 페인 크기로 1보다 큰 약수 관계의 페인을 생성할 수 없으므로 질의들을 SP와 DP들의 그룹핑을 통해 1보다 큰 약수관계의 팬 크기를 결정한다.

그룹화는 질의를 특성별로 분류하여 다수의 그룹으로 분할하고, 각 그룹에 속한 질의들이 그룹별로 존재하는 집계정보 리스트를 공유하는 과정으로, 그룹화 기법에서의 그룹은 페인과 타임유닛을 동시에 생성하는 상위그룹(Upper group)과 페인만 생성하는 하위그룹(Lower group)으로 구분한다.

질의 관계에 따라 SP 유형의 상위그룹에 대한 그룹화 구조의 예시는 <그림 3>과 같다.

<그림 3>은 상위그룹의 SP 그룹 구조의 예시로, 시간 흐름에 따라 타임유닛 및 페인의 관계를 나타낸다. 타임유닛은 한 개의 그룹으로 형성될 수있으나, 페인은 여러 개의 그룹으로 분할 생성될 수 있으므로, 그룹은 타임유닛과 페인이 동시에 생성되는 상위그룹 한 개와 페인만 생성하는 다수의 하위그룹이 존재한다. 그리고 각 그룹은 모두 집계 정보 리스트를 가지고 있고, 그룹별로 독립적인 페인 크기를 가진다.

페인 집계정보는 약수 관계의 페인 크기 및 타임유닛의 크기를 기준으로 생성한다. 페인 생성은 입력 스트림 데이터의 튜플들이 페인 크기에 해당하는 완전 상태와 페인 크기와 일치하지는 않으나 타임유닛의 시간 제약을 초과하는 불완전 상태로 구분되고, 집계정보 생성 과정에서의 페인은 임시 메모리에 유지되며 모든 페인들의 집합은 하나의 타임유닛으로 관리된다.

<그림 5>는 t₂부터 t₃까지 타임유닛과 페인의 생성 과정을 나타낸다.

버퍼에서 PP(Pointer position)가 위치까지 집계 정보를 임시메모리에 저장한다. {P₈, P₉, P₁₀, P₁₁}는 완전한 상태의 페인으로 생성되었고 P₁₂는 생성되고 있다. 이후 P₁₂생성과 함께 타임유닛의 종료시간인 t₃튜플이 입력되면 불완전 상태인 P₁₂이 생성되고, {P₈, P₉, P₁₀, P₁₁, P₁₂}로 구성된 타임유닛 TU₃가 집계정보 리스트에 저장된다. 이후 페인은 계속 버퍼에서 튜플을 읽어서 집계 값을 저장하고, 최종 페인 생성이 완료될 때까지 생성된 집계 값을 페인에 저장한다. 연속집계 질의에서 집계 연산은 최소(MIN), 최대(MAX), 개수(COUNT), 합계(SUM), 평균(AVG)을 지원한다. 다른 집계 연산과 달리 평균(AVG)은 완전한 상태와 불완전한 상태의 페인은 구성 튜플 수가 상이하므로 개수(COUNT)와 합계(SUM)으로 나누어 저장함으로써 집계정보의 정확도를 유지한다.

질의처리 과정에서 집계정보의 탐색은 튜플기반 질의는 질의범위가 튜플 단위이므로 저장된 페인을 기준으로 결과를 반환하고, 시간기반 질의는 질의범위가 시간 단위이므로 저장된 타임유닛을 기준으로 결과를 반환한다.

<그림 5>은 튜플기반 Q₁질의와 시간기반 Q₂질의가 동시에 실행되는 상황에서 페인과 타임유닛을 탐색하는 과정을 나타낸다. Q₁질의범위는 페인 크기가 3으로, 여기에는 완전 상태인 P₂와 P₃, 불완전 상태로 t₁시점에서 P₄′와 P₄″로 나뉘는 P₄를 포함하며, {P₂, P₃, P₄′, P₄″}에 저장된 집계정보로부터 결과를 처리한다. Q₂질의는 타임유닛 t단위로 QP를 이동하며 질의처리를 수행하며, 질의범위에는 {P₄″, P₅, P₆, P₇, P₈′}에 해당한다.

집계정보 목록에서 사용되지 않는 페인들은 삭제하며, 이를 위해 질의처리 후 가장 후행하는 QP를 LP로 설정하고 LP가 이전 타임유닛의 위치에서 다음 타임유닛으로 이동할 경우 이전 위치의 타임유닛을 삭제하여 페인 버퍼에서 삭제한다.

<그림 7>에서 페인 버퍼에 존재하는 질의 포인터는 {QP₁, QP₂, QP₃}이며, 가장 후행하는 QP₂가 LP로 설정된다. 이에 TU₁에 포함되는 {P₁, P₂, P₃}가 삭제 대상이 된다.

실험 환경은 우분투 18.04 64비트 운영체제, Intel Xeon 3.5Ghz CPU, 128GB 메모리로 구성된 시스템에 아파치 스파크 3.0.0을 구성하였다. 실험에 사용된 입력 스트림 데이터는 초당 최대 10만개의 튜플을 임의로 생성하였다. 튜플의 구조는 <RegionID, ObjectID, locX, locY, Tstamp>로 20바이트 크기로 설정하였으며, 집계 처리를 위해 RegionID는 16개 영역으로 분할 처리한다.

실험에서는 제안 자원공유 기법(RS)과 기존의 B-Int, L-Int를 비교 평가하였다.

첫 번째 실험은 단일 튜플 기반 질의에 대해 입력 튜플 수의 증가에 따른 집계정보 생성시간 변화를 분석하였다.

<그림 8>은 입력 튜플 증가에 따른 집계정보 생성시간을 비교하였다. 제안 기법(RS)에서 단일 튜플은 여러 계층이 아닌 하나의 페인에만 속하므로, 튜플의 중복 연산이 불필요하다. 결과에서 B-Int 및 L-Int가 제안 기법보다 전체 평균 36%, 50% 수준의 집계정보 생성시간이 더 소요되고 있다.

두 번째 실험은 단일 질의를 대상으로 입력 튜플 수의 증가가 질의처리 소요시간을 분석하였다.

<그림 9>에서 제안 기법(RS)은 질의 범위에 해당하는 집계정보만을 검색하여 질의처리를 수행하므로 B-Int와 L-Int에 비해 월등하게 우수한 성능을 보여주고 있다.

세 번째 실험은 시간과 튜플 기반 질의가 동시에 수행되는 경우 시간 및 튜플 기반 질의의 비율을 변화시키면서 질의처리 속도를 분석하였다. 실험에는 시간 및 튜플 기반 연속질의 20개의 비율을 조정하여 사용하였고, 입력 튜플은 초당 일 만개로 설정하였다. B-Int와 L-Int는 시간 및 튜플 기반 질의를 동시 수행할 수 없어, 각 기법에서 튜플 기반 질의는 고유의 방법을 적용하고 시간 기반 질의에는 자원을 공유하지 않는 방법을 이용하였다.

<그림 10>에서 질의 비율은 튜플 기반 질의 100%로부터 시간 기반 질의를 10%씩 증가하면서 질의처리 속도의 결과를 나타낸다. 스트림 데이터의 입력이 증가하면 튜플 기반 질의가 시간 기반 질의보다 질의처리 빈도가 높아지므로 실험에서 B-Int와 L-Int의 질의처리 속도가 전반적으로 크다는 것을 알 수 있다. 시간 기반 질의 비율을 증가할수록 튜플의 중복 계산을 방지하는 제안 기법(RS)의 질의처리 속도가 더욱 효과적임을 알 수 있다.

네 번째 실험에서는 연속질의의 수가 증가할 때 자원 사용량의 효과성을 검증한다. NRP 유형의 연속질의를 80%, RP 유형의 연속질의를 20%로 구성하여 10개씩 증가시켰으며, 입력 데이터는 초당 일만개를 사용하여 튜플 입력이 완료된 시점에서 할당된 메모리 사용량을 분석하였다.

<그림 11>에서 수행 질의 수의 변화에 비례하여 B-Int와 L-Int의 메모리 사용량은 증가하고 있다. 제안 기법(RS)은 초기 질의 수 증가에 따라 그룹 수 증대로 다른 기법에 비해 메모리 사용량이 높은 수준을 보이나, 질의 수가 증가할수록 그룹과 약수 관계일 확률이 높아져 질의 수가 20개에서 30개 사이 구간을 기점으로 메모리 사용량의 증가가 둔화되고 있다. 또한, 제안 기법은 앞선 실험에서 검증한 결과와 같이 다른 기법에 비해 상대적으로 질의처리 속도가 우수하므로 질의처리에 사용된 메모리 회수가 빠르게 진행되므로 질의 수 증가에 따른 메모리 사용량이 완화된 것을 알 수 있다.