Система управления потоками данных - Data stream management system

А система управления потоками данных (DSMS) - это компьютерная программная система для управления непрерывным потоки данных. Это похоже на система управления базами данных (СУБД), которая, однако, предназначена для статических данных в обычных базы данных. DSMS также предлагает гибкую обработку запросов, так что необходимую информацию можно выразить с помощью запросов. Однако, в отличие от СУБД, DSMS выполняет непрерывный запрос это не только выполняется один раз, но и устанавливается постоянно. Таким образом, запрос выполняется непрерывно, пока он не будет явно удален. Поскольку большинство DSMS управляются данными, непрерывный запрос дает новые результаты, пока новые данные поступают в систему. Эта основная концепция похожа на Обработка сложных событий так что обе технологии частично объединяются.

Принцип действия

Одной из важных особенностей DSMS является возможность обрабатывать потенциально бесконечные и быстро изменяющиеся потоки данных, предлагая одновременно гибкую обработку, хотя есть только ограниченные ресурсы, такие как основная память. В следующей таблице представлены различные принципы DSMS и их сравнение с традиционной СУБД.

Система управления базами данных (СУБД)Система управления потоками данных (DSMS)
Постоянные данные (отношения)непостоянные потоки данных
Произвольный доступПоследовательный доступ
Одноразовые запросыНепрерывные запросы
(теоретически) неограниченное вторичное хранилищеограниченная основная память
Только текущее состояние имеет значениеУчет порядка ввода
относительно низкая частота обновленияпотенциально чрезвычайно высокая частота обновления
Требуется мало времени или нетТребования в реальном времени
Предполагает точные данныеПредполагает устаревшие / неточные данные
Планируемая обработка запросовПоступление переменных данных и характеристики данных

Модели обработки и потоковой передачи

Одна из самых больших проблем для DSMS - это обработка потенциально бесконечных потоков данных с использованием фиксированного объема памяти и без произвольного доступа к данным. Существуют разные подходы к ограничению количества данных за один проход, которые можно разделить на два класса. С одной стороны, существуют методы сжатия, которые пытаются суммировать данные, а с другой стороны, есть методы окон, которые пытаются разделить данные на (конечные) части.

Краткое содержание

Идея методов сжатия состоит в том, чтобы поддерживать только синопсис данных, но не все (необработанные) точки данных в потоке данных. Алгоритмы варьируются от выбора случайных точек данных, называемых выборкой, до суммирования с использованием гистограмм, вейвлетов или построения эскизов. Одним из простых примеров сжатия является непрерывный расчет среднего значения. Вместо того, чтобы запоминать каждую точку данных, синопсис содержит только сумму и количество элементов. Среднее значение можно рассчитать, разделив сумму на число. Однако следует отметить, что резюме не могут точно отражать данные. Таким образом, обработка, основанная на резюме, может дать неточные результаты.

Windows

Вместо использования синопсисов для сжатия характеристик всех потоков данных, оконные методы просматривают только часть данных. Этот подход основан на идее, что актуальны только самые свежие данные. Поэтому окно непрерывно вырезает часть потока данных, например последние десять элементов потока данных и учитывает только эти элементы во время обработки. Есть разные виды таких окон, например, раздвижные окна, похожие на ФИФО списки или переворачивающиеся окна, вырезавшие непересекающиеся части. Кроме того, окна также можно разделить на окна на основе элементов, например, для учета последних десяти элементов, или окна на основе времени, например, для учета последних десяти секунд данных. Также существуют разные подходы к реализации окон. Существуют, например, подходы, которые используют метки времени или временные интервалы для общесистемных окон или окон на основе буфера для каждого отдельного шага обработки. Обработка запросов в скользящем окне также подходит для реализации в параллельных процессорах за счет использования параллелизма между различными окнами и / или внутри каждого экстента окна.[1]

Обработка запросов

Поскольку существует множество прототипов, стандартизированной архитектуры нет. Однако большинство DSMS основаны на запрос обработка в СУБД с использованием декларативных языков для выражения запросов, которые переводятся в план операторов. Эти планы можно оптимизировать и выполнять. Обработка запроса часто состоит из следующих шагов.

Формулировка непрерывных запросов

Формулировка запросов в основном выполняется с использованием декларативных языков, таких как SQL в СУБД. Поскольку не существует стандартизированных языков запросов для выражения непрерывных запросов, существует множество языков и вариантов. Однако большинство из них основаны на SQL, такой как Язык непрерывных запросов (CQL), StreamSQL и ESP. Существуют также графические подходы, в которых каждый шаг обработки представляет собой прямоугольник, а поток обработки выражается стрелками между прямоугольниками.

Язык сильно зависит от модели обработки. Например, если для обработки используются окна, должно быть выражено определение окна. В StreamSQL, запрос со скользящим окном для последних 10 элементов выглядит следующим образом:

ВЫБРАТЬ AVG(цена) ОТ пример потока [РАЗМЕР 10 ПРОДВИЖЕНИЕ 1 ПАКЕТЫ] ГДЕ ценность > 100.0

Этот поток непрерывно вычисляет среднее значение «цены» последних 10 кортежей, но учитывает только те кортежи, цена которых превышает 100,0.

На следующем этапе декларативный запрос преобразуется в логический план запроса. План запроса - это ориентированный граф, в котором узлы являются операторами, а ребра описывают поток обработки. Каждый оператор в плане запроса инкапсулирует семантику конкретной операции, такой как фильтрация или агрегирование. В DSMS, которые обрабатывают потоки реляционных данных, операторы идентичны или похожи на операторы Реляционная алгебра, так что есть операторы для операций выбора, проекции, соединения и установки. Эта концепция оператора позволяет очень гибко и универсально обрабатывать DSMS.

Оптимизация запросов

Логический план запроса можно оптимизировать, что сильно зависит от модели потоковой передачи. Основные концепции оптимизации непрерывных запросов идентичны концепциям из системы баз данных. Если есть реляционные потоки данных и логический план запроса основан на реляционных операторах из Реляционная алгебра, оптимизатор запросов может использовать алгебраические эквиваленты для оптимизации плана. Это может быть, например, чтобы подтолкнуть операторы выбора к источникам, потому что они не так требовательны к вычислениям, как операторы соединения.

Кроме того, существуют также методы оптимизации на основе затрат, например, в СУБД, где план запроса с наименьшими затратами выбирается из различных эквивалентных планов запроса. Одним из примеров является выбор порядка двух последовательных операторов соединения. В СУБД это решение чаще всего принимается определенной статистикой задействованных баз данных. Но поскольку данные потоков данных заранее неизвестны, такой статистики в DSMS нет. Однако можно наблюдать за потоком данных в течение определенного времени для получения некоторой статистики. Используя эту статистику, запрос также можно оптимизировать позже. Итак, в отличие от СУБД, некоторые DSMS позволяют оптимизировать запрос даже во время выполнения. Следовательно, DSMS нуждается в некоторых стратегиях миграции плана, чтобы заменить текущий план запроса новым.

Преобразование запросов

Поскольку логический оператор отвечает только за семантику операции, но не состоит из каких-либо алгоритмов, логический план запроса должен быть преобразован в исполняемый аналог. Это называется физическим планом запроса. Различие между логическим и физическим планом оператора позволяет реализовать более одной реализации одного и того же логического оператора. Например, соединение логически одинаково, хотя его можно реализовать с помощью разных алгоритмов, таких как Присоединение к вложенному циклу или Сортировка-слияние. Обратите внимание, что эти алгоритмы также сильно зависят от используемого потока и модели обработки. Наконец, запрос доступен в виде физического плана запроса.

Выполнение запросов

Поскольку план физического запроса состоит из исполняемых алгоритмов, он может быть выполнен напрямую. Для этого в систему устанавливается физический план запроса. Нижняя часть графика (плана запроса) связана с входящими источниками, которые могут быть чем угодно, например, соединителями с датчиками. Верхняя часть графика связана с исходящими стоками, которые могут быть, например, визуализацией. Поскольку большинство DSMS управляются данными, запрос выполняется путем проталкивания входящих элементов данных из источника через план запроса в приемник. Каждый раз, когда элемент данных передает оператор, оператор выполняет свою конкретную операцию с элементом данных и передает результат всем последующим операторам.

Примеры

Смотрите также

использованная литература

  1. ^ Де Маттеис, Тициано; Менкагли, Габриэле (25 марта 2016 г.). «Параллельные шаблоны для оконных операторов с отслеживанием состояния в потоках данных: подход с алгоритмическим скелетом». Международный журнал параллельного программирования. 45 (2): 382–401. Дои:10.1007 / s10766-016-0413-х. S2CID  255600.
  2. ^ Абади; и другие. Аврора: система управления потоками данных. SIGMOD 2003. CiteSeerX  10.1.1.67.8671.
  3. ^ Цзяньцзюнь Чен; Дэвид Дж. ДеВитт; Фэн Тянь; Юань Ван (2000). «NiagaraCQ: масштабируемая система непрерывных запросов для баз данных в Интернете» (PDF). Кафедра компьютерных наук. Университет Висконсина-Мэдисона. SIGMOD. Получено 21 ноября 2018.
  4. ^ Арасу А. и др. al. STREAM: Стэнфордская система управления потоками данных. Технический отчет. 2004, Стэнфордская инфолаборатория.
  5. ^ Чандрасекаран, С. и др., «TelegraphCQ: Непрерывная обработка потока данных для неопределенного мира». CIDR 2003.
  • Аггарвал, Чару С. (2007). Потоки данных: модели и алгоритмы. Нью-Йорк: Спрингер. ISBN  978-0-387-47534-9.
  • Голаб, Лукаш; Озсу, М. Тамер (2010). Управление потоком данных. Ватерлоо, США: Морган и Клейпул. ISBN  978-1-608-45272-9.

внешние ссылки