데이터 스트림 관리 시스템

Data stream management system

데이터 스트림 관리 시스템(DSMS)은 연속적인 데이터 스트림을 관리하기 위한 컴퓨터 소프트웨어 시스템입니다.이것은 데이터베이스 관리 시스템(DBMS)과 유사하지만 기존 데이터베이스의 정적 데이터를 위해 설계되었습니다.또한 DBMS는 쿼리를 사용하여 필요한 정보를 표현할 수 있도록 유연한 쿼리 처리를 제공합니다.그러나 DBMS와 달리 DSMS는 한 번만 수행되는 것이 아니라 영구적으로 설치되는 연속 쿼리를 실행합니다.따라서 쿼리는 명시적으로 제거될 때까지 계속 실행됩니다.대부분의 DSMS는 데이터 중심이기 때문에 새로운 데이터가 시스템에 도착하는 한 지속적인 쿼리를 통해 새로운 결과가 생성됩니다.이 기본 개념은 복잡한 이벤트 처리와 유사하므로 두 기술이 부분적으로 병합됩니다.

기능 원리

DSMS의 중요한 기능 중 하나는 메인 메모리와 같은 제한된 리소스만 있어도 유연성이 뛰어난 처리를 동시에 제공함으로써 무한하고 빠르게 변화하는 데이터 스트림을 처리할 수 있다는 것입니다.다음 표는 DSMS의 다양한 원리를 제시하며 기존 DBMS와 비교합니다.

데이터베이스 관리 시스템(DBMS) 데이터 스트림 관리 시스템(DSMS)
지속 데이터(관계) 휘발성 데이터 스트림
랜덤 액세스 시퀀셜 액세스
일회성 쿼리 연속 쿼리
(수직적으로) 무제한 세컨더리 스토리지 한정된 메인 메모리
현재 상태만 관련됨 입력 순서 고려
비교적 낮은 갱신률 잠재적으로 매우 높은 업데이트 속도
시간 요건이 거의 또는 전혀 없음 실시간 요건
정확한 데이터 추정 오래된 데이터/정확하지 않은 데이터라고 가정합니다.
계획 가능한 쿼리 처리 가변 데이터 도착 및 데이터 특성

프로세싱 및 스트리밍 모델

DSMS의 가장 큰 과제 중 하나는 데이터에 대한 랜덤 액세스 없이 고정된 양의 메모리를 사용하여 무한한 데이터 스트림을 처리하는 것입니다.한 번의 경로로 데이터 양을 제한하는 방법은 여러 가지가 있으며, 두 가지 클래스로 나눌 수 있습니다.한편으로 데이터를 요약하는 압축 기법도 있고, 다른 한편으로 데이터를 (확정한) 부분으로 분할하는 창 기법도 있습니다.

Synopses

압축 기술의 기본 개념은 데이터 스트림의 모든 (원시) 데이터 지점이 아닌 데이터의 개요만 유지하는 것입니다.알고리즘은 샘플링이라고 하는 랜덤 데이터 포인트를 선택하는 것부터 히스토그램, 웨이브릿 또는 스케치를 사용한 요약까지 다양합니다.압축의 한 가지 간단한 예는 평균의 연속 계산입니다.시놉시스에는 각 데이터 포인트를 기억하는 대신 항목 수와 합계만 저장됩니다.평균은 합계를 숫자로 나누어 계산할 수 있습니다.단, 시놉스는 데이터를 정확하게 반영할 수 없다는 점에 유의해야 합니다.따라서 Synopses에 기반한 처리에서는 부정확한 결과가 나올 수 있습니다.

창문들

전체 데이터 스트림의 특성을 압축하기 위해 synopses를 사용하는 대신, 윈도우 기술은 데이터의 일부만 살펴봅니다.이 접근방식은 최신 데이터만 관련이 있다는 생각에 의해 동기부여가 됩니다.따라서 창은 데이터 스트림의 일부(예: 마지막 10개의 데이터 스트림 요소)를 지속적으로 잘라내고 처리 중에 이러한 요소만 고려합니다.FIFO 목록과 유사한 슬라이딩 윈도우나 분리된 부분을 잘라내는 텀블링 윈도우 등 다양한 종류의 윈도우가 있습니다.또한 창은 요소 기반 창(예: 마지막 10개의 요소를 고려하는 경우) 또는 시간 기반 창(예: 마지막 10초의 데이터를 고려하는 경우)으로 구분할 수 있습니다.또한 윈도우를 구현하기 위한 다양한 접근법이 있습니다.예를 들어 시스템 전체 창 또는 버퍼 기반 창마다 타임스탬프 또는 시간 간격을 사용하는 접근법이 있습니다.슬라이딩 윈도 쿼리 처리는 다른 윈도 간 및/또는 각 윈도 [1]익스텐트 내에서 병렬 처리를 이용하여 병렬 프로세서에서 구현하는데도 적합하다.

쿼리 처리

시제품이 많기 때문에 표준화된 아키텍처가 없습니다.그러나 대부분의 DSMS는 선언적 언어를 사용하여 쿼리를 표현함으로써 DBMS에서의 쿼리 처리를 기반으로 하며, 이는 연산자의 계획으로 변환됩니다.이러한 계획을 최적화하고 실행할 수 있습니다.쿼리 처리는 대개 다음 단계로 구성됩니다.

연속 질의의 공식화

쿼리의 공식화는 대부분 DBMS의 SQL과 같은 선언적 언어를 사용하여 이루어지며, 연속적인 쿼리를 표현할 수 있는 표준화된 쿼리 언어가 없기 때문에 다양한 언어와 변형이 존재합니다.그러나 대부분은 SQL(Continuous Query Language(CQL), 스트림 등)을 기반으로 합니다.SQL 및 ESP.또한 각 처리 단계가 상자이고 처리 흐름이 상자 사이의 화살표로 표현되는 그래픽 방식도 있습니다.

언어는 처리 모델에 따라 크게 달라집니다.예를 들어 처리를 위해 창을 사용하는 경우 창의 정의를 표현해야 합니다.스트림 중SQL은 마지막 10개 요소에 대한 슬라이딩 창이 있는 쿼리로 다음과 같습니다.

선택한다. AVG(가격.) 부터 시험 스트림 [크기 10 발전 1 튜플] 어디에 가치 > 100.0

이 스트림은 마지막 10개의 튜플의 "가격"의 평균값을 지속적으로 계산하지만 가격이 100.0보다 큰 튜플만 고려합니다.

다음 단계에서는 선언 쿼리를 논리 쿼리 플랜으로 변환한다.쿼리 계획은 노드가 연산자이고 가장자리가 처리 흐름을 설명하는 방향 그래프입니다.쿼리 계획의 각 연산자는 필터링 또는 집약과 같은 특정 작업의 의미를 캡슐화합니다.관계형 데이터 스트림을 처리하는 DSMS에서 연산자는 관계형 대수의 연산자와 같거나 비슷하므로 선택, 투영, 결합 및 집합 연산을 위한 연산자가 있습니다.이 오퍼레이터 개념은 DSMS의 매우 유연하고 다용도적인 처리를 가능하게 합니다.

쿼리 최적화

스트리밍 모델에 따라 크게 달라지는 논리 쿼리 계획을 최적화할 수 있습니다.연속 쿼리를 최적화하기 위한 기본 개념은 데이터베이스 시스템의 개념과 동일합니다.관계 데이터 스트림이 있고 논리 쿼리 계획이 관계 대수로부터의 관계 연산자에 기초하고 있는 경우 쿼리 옵티마이저는 대수적 등가를 사용하여 계획을 최적화할 수 있습니다.예를 들어 선택 연산자는 결합 연산자처럼 계산 부하가 높지 않기 때문에 선택 연산자를 소스로 밀어낼 수 있습니다.

또한 DBMS와 같은 비용 기반 최적화 기법도 있습니다. 이 기법에서는 비용이 가장 적게 드는 쿼리 계획이 서로 다른 동등한 쿼리 계획에서 선택됩니다.예를 들어 두 개의 연속 결합 연산자의 순서를 선택하는 것입니다.DBMS에서 이 결정은 대부분 관련된 데이터베이스의 특정 통계에 의해 이루어집니다.단, 데이터 스트림의 데이터는 사전에 알 수 없기 때문에 DSMS에는 이러한 통계 정보가 없지만 일정 시간 데이터 스트림을 관찰하여 통계 정보를 얻을 수 있습니다.이러한 통계를 사용하여 나중에 쿼리를 최적화할 수도 있습니다.따라서 DBMS와 달리 일부 DSMS에서는 런타임 중에도 쿼리를 최적화할 수 있습니다.따라서 DSMS에서는 실행 중인 쿼리 플랜을 새로운 플랜으로 대체하기 위해 몇 가지 플랜 이행 전략이 필요합니다.

쿼리 변환

논리연산자는 연산의 의미만을 담당할 뿐 알고리즘으로 구성되어 있지 않기 때문에 논리 쿼리 플랜은 실행 가능한 대응책으로 변환되어야 합니다.이를 물리적 쿼리 계획이라고 합니다.논리 연산자 계획과 물리 연산자 계획의 구별을 통해 동일한 논리 연산자에 대해 두 개 이상의 구현을 허용합니다.예를 들어, 결합은 논리적으로 동일하지만 Nested 루프 결합이나 Sort-Merge 결합과 같은 다른 알고리즘에 의해 구현될 수 있습니다.이러한 알고리즘은 사용되는 스트림 및 처리 모델에 따라 크게 달라지기도 합니다.마지막으로 쿼리는 물리적 쿼리 계획으로 사용할 수 있습니다.

쿼리 실행

물리적 쿼리 계획은 실행 가능한 알고리즘으로 구성되므로 직접 실행할 수 있습니다.이를 위해 물리적 쿼리 계획이 시스템에 설치됩니다.(쿼리 계획의) 그래프 하단은 센서에 대한 커넥터와 같은 모든 것이 될 수 있는 착신 소스에 연결됩니다.그래프의 상단은 발신 싱크(예: 시각화)에 연결되어 있습니다.대부분의 DSMS는 데이터 구동형이기 때문에 쿼리는 소스에서 들어오는 데이터 요소를 쿼리 플랜을 통해 싱크까지 푸시함으로써 실행됩니다.데이터 요소가 연산자를 통과할 때마다 연산자는 데이터 요소에 대한 특정 연산을 수행하고 그 결과를 모든 후속 연산자에게 전송합니다.

예

「 」를 참조해 주세요.

레퍼런스

  1. ^ De Matteis, Tiziano; Mencagli, Gabriele (25 March 2016). "Parallel Patterns for Window-Based Stateful Operators on Data Streams: An Algorithmic Skeleton Approach". International Journal of Parallel Programming. 45 (2): 382–401. doi:10.1007/s10766-016-0413-x. S2CID 255600.
  2. ^ Abadi; et al. Aurora: A Data Stream Management System. SIGMOD 2003. CiteSeerX 10.1.1.67.8671.
  3. ^ Jianjun Chen; David J. DeWitt; Feng Tian; Yuan Wang (2000). "NiagaraCQ: A Scalable Continuous Query System for Internet Databases" (PDF). Computer Sciences Department. University of Wisconsin–Madison. SIGMOD. Retrieved 21 November 2018.
  4. ^ 아라스, A.STREAM: 스탠포드 데이터 스트림 관리 시스템.테크니컬 리포트2004년, 스탠포드 인포랩.
  5. ^ Chandrasekaran, S. et al., "TelegraphCQ: 불확실한 세상을 위한 연속 데이터 흐름 처리." CIDR 2003.
  • Aggarwal, Charu C. (2007). Data Streams: Models and Algorithms. New York: Springer. ISBN 978-0-387-47534-9.
  • Golab, Lukasz; Özsu, M. Tamer (2010). Data Stream Management. Waterloo, USA: Morgan and Claypool. ISBN 978-1-608-45272-9.

외부 링크