Processing data streams is becoming necessary for the monitoring applications such as network traffic monitoring and financial data analysis. Systems for processing data streams must be adaptive because data streams can be often bursty. When input rates exceed system capacity, latency will be high. In many data stream applications, latency is the most critical quality parameter since the query results will lose their value over time.
Under an overload situation, systems can shed load to maintain low latency. In this paper, we present semantic load shedding technique for query responsiveness improvement. Our technique consists of three steps. First, we generate global impact graph(GIP) describing that how important each data is based on the weight of each query and the value-based quality of service(QoS) graph. Next, we calculate the shedding probability of each data based on GIP. Finally, we shed load by the shedding probability that we calculated. We present experimental results that evaluate our technique. The experimental results show that our technique achieves much higher query responsiveness as compared to the previous approach.
최근 센서 네트워크와 유비쿼터스 컴퓨팅의 등장으로 많은 어플리케이션에서 스트림 데이터 처리를 요구하고 있다. 스트림 데이터는 기존의 데이터 처리와는 달리 시스템 외부로부터 연속적으로 입력되어 어플리케이션의 요구사항을 처리한 후 소실되는 데이터를 의미한다. 이들의 예는 센서 네트워크, 네트워크 트래픽 모니터링, 건물 침입 감시시스템, 온라인 경매 시스템, 실시간 주식 데이터 분석 등에서 찾아볼 수 있다[1,2,8,9,10]. 스트림 데이터의 일반적인 특징은 다음과 같다.
먼저, 입력으로 들어오는 데이터의 양(data arrival rate)은 계속적으로 변하기 때문에 예측이 어렵다[2,4]. 예를 들면 월드컵 축구시합이 있는 날 축구 경기장 내에서의 휴대폰 통화량이나 온라인 쇼핑몰에서 유명 신제품을 출시한 날의 네트워크 트래픽 양과 같은 이벤트가 발생하였을 때 스트림 데이터가 순간적으로 늘어날 수 있다. 이와 같은 현상은 시스템에 서비스 거부(DoS: Denial of Service)공격이 발생한 경우처럼 중요한 이벤트가 발생했다는 정보를 알려준다. 많은 어플리케이션에서는 이 같은 현상을 인지하는 것에 관심이 있다.
두 번째로, 스트림 데이터를 다루는 많은 어플리케이션에서는 연속해서 입력되는 데이터 하나하나의 정확한 값보다는 스트림 데이터의 경향에 대해 모니터링 하기를 요구한다[2,7]. 이는 사용자가 대량으로 입력되는 데이터를 실시간으로 모두 파악하는 것이 불가능할 뿐만 아니라 전체 데이터의 개개의 값보다는 시간에 따른 데이터의 변화 경향에 더 관심을 가지고 있기 때문이다. 예를 들면 사용자들은 자동차 경주에서 매 순간의 속도가 아닌 매 랩의 평균 속도, 최고 속도 정보 등에 더 관심이 있다. 따라서 스트림 데이터의 경향을 파악할 수 있도록 도와주는 Max, Min, Average, Sum, Count와 같은 집계 연산자가 스트림 환경에서 중요한 의미를 갖는다[1,2,11].
위에서 열거한 환경에서 어플리케이션은 또한 연속적으로 입력되는 데이터를 바탕으로 한 실시간 처리(real-time processing)를 요구한다[2]. 예를 들어 은행의 네트워크 망에서 데이터를 실시간으로 모니터링 하여 해커의 침입에 대비하는 상황을 생각해볼 수 있다. 해커가 침입하고 있는 징후가 있다는 정보는 가능한 빨리 네트워크 관리자에게 전달되어야 한다. 이 정보는 시간이 지날수록 네트워크 관리자의 관점에서 가치가 떨어지며 정보의 전달이 지연될수록 은행이 입는 피해는 크게 증가할 것이다.
어플리케이션에서 스트림 데이터를 효율적으로 처리하기 위한 새로운 종류의 데이터 스트림 관리 시스템(Data Stream Management System)이 등장하였다. 대표적인 데이터 스트림 관리 시스템으로는 브랜디스(Brandeis) 대학과 브라운(Brown) 대학, MIT(Massachusetts Institute of Technology)에서 공동으로 개발한 Aurora 시스템과 Borealis 시스템 그리고 스탠포드(Stanford) 대학에서 개발한 STREAM(STanford stREam datA Manager) 시스템 등이 있다[3,6,7,12,16].
데이터 스트림 관리 시스템은 시스템의 처리 능력과 현재 로드(load)에 관계없이 스트림 데이터가 생성되는 즉시 시스템으로 입력되는 푸시-기반(push-based) 데이터 모델을 따르고 있다[1]. 이 모델에서 입력 데이터 양이 갑자기 증가하면 데이터가 점차 누적되어 사용자는 질의 결과를 얻기 위해 기대한 것보다 오랜 시간을 기다려야만 한다. 이는 스트림 데이터의 실시간 처리를 요구하는 환경에서 치명적이기 때문에 시스템 과부하 상황에 대한 대처는 매우 중요하다.
시스템에 추가적인 자원을 장착하거나 여러 시스템으로 로드를 분산하여 스트림 데이터를 처리하는 방법을 시도할 수 있으나 일시적인 과부하의 해소를 위해 자원을 소비하는 이와 같은 방법은 경제적이지 못하다[5,13,17].
일시적인 과부하의 발생시 시스템의 로드를 줄이기 위해서 취할 수 있는 한가지 방법은 입력 스트림 데이터의 일부를 처리하지 않고 버리는 것이다. 이를 로드 셰딩(load shedding)이라 하고 STREAM, Aurora와 같은 기존의 데이터 스트림 관리 시스템에서 채택하고 있다.
로드 셰딩에서는 일부 입력 스트림 데이터를 처리하지 않기 때문에 질의 처리 결과는 추정치이다[6]. 그러나 사용자가 스트림 데이터의 정확한 값보다는 데이터의 변화 경향에 관심을 가지고 있다는 면을 고려한다면 추정된 결과라 하더라도 의미가 크게 손상되지 않는다고 할 수 있다. 또한 질의 결과는 시간이 지날수록 가치가 줄어든다는 면을 고려하여 로드 셰딩은 정확도 측면에서 다소 희생을 하더라도 스트림 환경에서 보다 중요한 목표인 사용자가 요구한 시간 내에 질의 결과를 제공하고자 하는 것이다[1,3].
어플리케이션에 따라 입력 스트림 데이터가 질의 결과에 미치는 영향에 차이가 있을 수 있다[1]. 예를 들면, 1분 동안 입력되는 데이터에 대한 최대값을 결과로 생성하는 질의에서 현재까지의 최대값보다 작은 값은 질의 결과에 영향이 없다. 본 논문에서는 질의 결과들에 미치는 데이터의 영향을 바탕으로 질의 처리를 위해 얼마나 중요한 데이터들을 이용할 수 있는지를 나타내는 지표로 데이터의 질(QoD: Quality of Data)이라는 용어를 정의한다.
또한 질의들 간의 중요도에 상대적인 차이가 있다[7]. 예를 들면, 데이터 스트림 관리 시스템에서 일반 사용자가 요청한 질의보다 관리자가 요청한 질의에 대해 우선순위를 더 높게 주는 경우를 생각해볼 수 있다. 시스템이 과부하 상태일 경우 관리자가 요청한 질의를 우선적으로 처리하거나 더 정확한 결과를 제공해 줌으로써 질의들 간의 중요도를 반영할 수 있다.
여러 질의들이 동시에 수행되고 있을 때 수행되는 질의들 사이에 공통된 연산자의 수행 결과를 공유하면 데이터 스트림 관리 시스템의 자원을 효율적으로 이용할 수 있다. 이 때 공유 연산자를 수행하기 전에 셰딩하면 연산자를 공유하는 모든 질의의 결과에 입력 데이터가 동시에 영향을 미칠 수 있다[7]. 그러므로 연산자를 공유하는 각 질의에 대한 중요도와 데이터가 질의 결과에 미치는 영향에 대한 정보를 고려해야 한다.
[1]은 공유 연산자 수행 이전에 데이터를 셰딩할 경우 이 정보를 바탕으로 각 데이터가 연산자를 공유하는 질의 결과들에 미치는 전체적인 영향을 계산한다. 그리고 이를 바탕으로 질의 결과들에 미치는 영향이 가장 작은 데이터를 셰딩한다. 그럼으로써 시스템의 QoD를 높게 유지할 수 있다.
이 기법의 단점은 중요도가 낮은 데이터부터 셰딩함으로써 특정 질의의 결과를 생성하는 데이터를 일방적으로 셰딩할 수 있다는 것이다. 따라서 이 질의에 대한 결과를 생성하지 못할 수 있다. 화재 경보 시스템과 같은 환경에서 이러한 사건의 발생은 치명적일 수 있다.
이러한 경우 예를 들어 [0, 10] 구간의 입력 데이터에 대해 [0, 5) 구간의 데이터를 필요로 하는 질의와 [5, 10] 구간의 데이터를 필요로 하는 두 질의가 있을 때, [0, 5) 구간의 데이터를 일방적으로 셰딩하는 대신 일부 데이터를 [5, 10] 구간에서 셰딩함으로써 두 질의의 결과를 모두 생성할 수 있도록 하는 것이 더 바람직하다.
본 논문에서는 [1]에서 기존의 기법에서 제안한 프로세서 싸이클(processor cycle)을 기준으로 로드 셰딩 시점을 판단하는 모델을 이용한다. 이 모델을 이용하여 로드 셰딩이 필요하다고 판단될 경우 QoD를 주어진 수준으로 유지하면서 특정 구간의 데이터를 일방적으로 셰딩하는 것을 완화함으로써 더 많은 질의 결과를 생성할 수 있도록 하는 로드 셰딩 기법을 제안한다. 또한 우리가 제안하는 기법이 기존 기법에 근접한 QoD를 가지면서 더 많은 질의 결과를 생성할 수 있음을 나타내는 실험 결과를 제시한다.
본 논문의 구성은 다음과 같다. 2장에서 스트림 데이터 처리의 배경 지식과 관련 연구에 대해 설명한다. 3장에서는 질의 응답성 향상을 위한 시맨틱 로드 셰딩 기법을 제안한다. 먼저 프로세서 싸이클을 기준으로 로드 셰딩이 필요한 시점을 판단하는 모델에 대해 기술한 후 질의 응답성 향상을 위한 시맨틱 로드 셰딩 기법을 전역 영향 그래표(GIP:Global Impact graPh) 생성 단계와 셰딩 확률(shedding probability) 결정 단계로 나누어 설명한다. 4장에서는 질의가 결과를 생성할 가능성과 QoD를 측정한 실험 결과를 통해 기존 로드 셰딩 기법과 본 논문에서 제안하는 로드 셰딩 기법의 성능을 비교하고 분석한다. 마지막으로 5장에서는 결론을 맺고 추후 연구 방향을 제시한다.
