Диссертация (1149731), страница 9
Текст из файла (страница 9)
Отдельно рассмотрены системы приближенного анализа данных.1.4.1. Распределенные вычисленияВ литературе описано несколько систем анализа больших данных [4–6,81],основанных на распределенных вычислениях и парадигме map-reduce [3].Система ASTERIX, предложенная в [4], включает в себя следующие слои:система управления данными Asterix, поддерживающая язык AsterixQL икомпиляторы других высокоуровневых языков [82, 83]; алгебраический слойAlgebricks и слой поддержки работ Hadoop map-reduce; и параллельная по данным платформа Hyracks.
Компилятор декларативного языка анализирует запрос и транслирует его в алгебраическое представление в виде направленногоациклического графа, вершинами которого являются логические операторы.Этот граф передается в слой Algebricks для оптимизации, подготовки к параллельному исполнению и генерации кода на языке операторов платформыHyracks.Архитектура системы SCOPE описана в [6].
SCOPE предоставляет высокоуровневый язык спецификации сценариев анализа данных, и контролирует ихисполнение на нескольких этапах: компиляция, оптимизация, распределенныевычисления. Данные в системе SCOPE представляются множествами строк,составленных из типизированных столбцов; у каждого множества строк естьполностью определенная схема.Описанная в [83] платформа Hive поддерживает исполнение запросовсформулированных на декларативном языке запросов HiveQL. Запросы на языке HiveQL компилируются в набор работ map-reduce и исполняются на платформе Hadoop.40Система Stratosphere [81] предлагает стек технологий для параллельнойобработки больших данных, включая анализ данных, декларативный язык запросов, поддержку пользовательских функций, автоматическую оптимизациюи распараллеливание программ, масштабируемый и эффективный вычислитель.
Система состоит из трех слоев: Sopremo, PACT и Nephele. Программав слое Sopremo состоит из набора логических операторов, образующего дерево,аналогичное логическому плану выполнения запроса в реляционных СУБД. Науровне слоя PACT программа транслируется в программную модель, расширяющую модель map-reduce. На этом уровне происходит логическая и физическаяоптимизация сценария анализа данных на основе моделей стоимости. Nepheleпредставляет собой параллельный исполнитель сценариев, сгенерированных напредыдущем слое. На этом уровне программа представляет собой дерево, вершинами которого являются отдельные простые задачи.
В слое Nephele происходит распределение задач и мониторинг их исполнения.1.4.1.1. ЯзыкиВысокоуровневые декларативные языки запросов были предложены в [82,83] для преодоления сложности спецификации сценариев анализа данных и возможности переиспользования методов оптимизации. С одной стороны, за основу многих языков был взят традиционный в реляционных СУБД SQL. С другой стороны, поскольку сценарии, сформулированные в терминах этих языков,предполагают их последующее распределенное исполнение в системах на основепарадигмы map-reduce, то они расширяют язык процедурными элементами.Язык Pig Latin был спроектирован в [82] для спецификации сценариеванализа данных в высокоуровневом декларативном стиле языка SQL и низкоуровневом процедурном стиле работ map-reduce.
Модель данных, на которуюопирается язык, основана на понятиях атома, кортежа, сумки и отображения.Язык Pig Latin включает в себя следующий набор операторов: загрузка (load),множественная обработка (foreach), фильтр (filter), со-группировка (cogroup)реализующая одновременно группировку и соединение, объединение (union), декартово произведение (cross), сортировка (order), поиск уникальных (distinct),сохранение (store), и вложенные (nested) операторы. Сценарии анализа данных,специфицированные на языке Pig Latin, могут быть эффективно выполнены наплатформе Hadoop.41Язык Scope, рассмотренный в [5], представляет собой расширяемый, декларативный аналог SQL.
В языке унаследованы команды выборки, соединения,агрегирования и теоретико-множественных операций.Платформа Hive [83] позволяет также специфицировать запросы на декларативном языке на базе SQL. Для расширения HiveQL система позволяетвстраивать в запросы пользовательские скрипты map-reduce.Также стоит обратить внимание на декларативные языки внутреннегопредставления сценариев анализа данных. Например, в системе ASTERIX [4]есть внутренний язык алгебраического слоя Algebricks и язык платформы исполнения Hyracks.Algebricks, описанный в [4], представляет собой, инвариантный относительно модели, алгебраический слой параллельного исполнения запросов.
Этот слойсостоит из следующих частей: множество логических операторов, множествофизических операторов, система правил трансформации, множество базовыхправил трансформации и отображение физических операторов в операторы исполнения платформы Hyracks. Algebricks поддерживает все реляционные операторы, а также позволяет работать с операторами выбора подплана и группировки.Как уже говорилось, в системе ASTERIX [4] работы передаются в платформу Hyracks в виде направленных ациклических графов, организованных из алгебраических операторов. Язык Hyracks [84] расширяемый и включает в себя библиотеку базовых операторов: чтение/запись файлов, отображения (mappers), сортировки (sorters), соединения (joiners), агрегирования (aggregators); и соединители (connectors): hash-partitioner, hash-partitioningmerger, range-partitioner, replicator, connector.Система Stratosphere [81] поддерживает спецификацию сценариев обработки данных на языке Meteor.
Meteor аналогичен языкам Pig [82] и Jaql [85] всистеме Hadoop, но ориентирован на расширяемость и семантическое богатствомодели операторов Sopremo.1.4.1.2. ОптимизацияЗадача оптимизации запросов, исполняемых в системе распределенныхнеоднородных вычислителей, обсуждается в [86, 87].В статье [86] после детального обзора классических методов оптимизации42и выполнения запросов, рассматриваются подходы к работе в клиент-серверныхархитектурах, такие как передача запроса или данных и выбор исполнителя.Авторы обсуждают двухфазный подход к оптимизации запросов: сначала строится оптимальная последовательность соединений, выбираются алгоритмы истратегии доступа к данным; затем непосредственно перед вычислениями длякаждого оператора в плане выбирается исполнитель. Также в статье детально прорабатывается оптимизация запросов в неоднородных архитектурах базданных на основе оберток.
Завершает обзор рассмотрение вопросов, связанныхс динамическим распределением данных на основе избыточного копирования,кеширования и материализации.В статье [87] предложена система распределенного выполнения запросов,в которой оптимизация основана на модели торгов. Вычислители, не располагающие данными или ресурсами необходимыми для вычисления запроса (илиего части), называются покупателями.
Продавцами наоборот являются вычислители обладающие необходимыми данными и готовыми предоставить ответ заопределенную цену.Другая постановка задачи оптимизации запросов в распределенной средерассматривается в [88–91]: оптимизатор строит эффективный план выполнениясценария работ map-reduce.В системе Hive [83] оптимизация сценариев анализа данных основана наэвристиках, реализованных в виде набора трансформаций, который может бытьлегко изменен.Предложенный в [90] транслятор SQL запросов в эффективные сценарииработ map-reduce, YSmart основан на учете корреляций внутри запроса, определяемых как возможные связи между операциями соединения и/или агрегирования внутри дерева плана.
После однозначного отображения операторованализа данных в примитивные работы map-reduce (SP, AGG, JOIN, SORT)транслятор перестраивает получившийся сценарий, свивая некоторые работына основе правил.Первый оптимизатор сценариев работ map-reduce на основе оценки их стоимости, Statfish был предложен в [89]. Оптимизатор на основе оценки стоимости выполнения планов и WhatIf модуля выбирает наиболее эффективнуюконфигурацию сценария анализа данных. Предложенный подход позволяет оптимизировать как отдельные работы map-reduce, так и сценарии, состоящие из43нескольких работ.Оптимизатор MRShare, представленный в [91], позволяет оптимизироватьгруппу запросов, опираясь на идею, что отдельные работы зачастую реализуютпохожую функциональность.
Оптимизатор на основе простых моделей стоимости преобразует группу запросов в более эффективную, сливая несколько работв отдельные исполняемые сценарии.Оптимизатор Stubby [88] основан на расширяемом наборе трансформаций ориентированного графа операций map-reduce. Авторы выделили несколько ключевых типов трансформаций: вертикальная упаковка между работами,вертикальная упаковка внутри работы, горизонтальная упаковка и преобразование функции распределения данных (partition).
Для поиска оптимальногоплана выполнения сценария обработки данных используется перечислитель наоснове разделения дерева на отдельные оптимизационные единицы.AQUA [92] оптимизирует сценарий работ map-reduce в два этапа. На первом этапе множество соединяемых в запросе таблиц разбивается на группыкаждая группа исполняется внутри одно работы map-reduce. На втором этапеоптимизатор выбирает наиболее эффективную по стоимости стратегию вычисления результата на основе комбинации этих групп.Высокоуровневые скриптовые языки порождают ряд новых задач оптимизации, и система SCOPE, предложенная в [5], уделяет им особое внимание.
Напервом этапе обработки компилятор системы SCOPE анализирует скрипт, делает подстановку представлений и макродиректив, проводит проверку синтаксиса и соответствия типов. Результатом этого этапа является аннотированноеабстрактное синтаксическое дерево, которое передается оптимизатору запросов.Оптимизатор системы SCOPE применяет трансформации на основе моделей стоимости и тем самым строит эффективные планы исполнения получаемых от компилятора деревьев запроса. Система SCOPE опирается на методы оптимизации реляционных запросов и реализует возможность использования богатых и нетривиальных перестроений дерева запроса. Оптимизатор вкачестве результата работы возвращает план выполнения запроса, в которомспецифицированы шаги необходимые для эффективного исполнения скрипта.Оптимизатор SCOPE определяет специфические реализации каждой операции(например, агрегирования на потоках), операций разбиения данных (например,операторы разбиения и слияния), и дополнительные детали реализации (напри-44мер, предварительная сортировка и представление результата агрегирования ввиде набора пар).Оптимизатор системы Stratosphere подробно рассматривается в [81].
Приоптимизации запрос проходит несколько этапов: трансформация PACT представления запроса во внутреннее, статический анализ сценария и перестановкаоператоров, выбор локальных стратегий исполнения и пересылки данных, построения графа задач для исполнителя Nephele.На последнем этапе внутренний компилятор генерирует код реализующий каждый оператор и собирает группы операторов в исполняемые единицыили фазы, получаемые на основе расщепления дерева на компоненты, которыедолжны быть исполнены на одном вычислительном модуле.Архитектура системы непрерывной оптимизации в SCOPE состоит из трехфаз: компиляция/оптимизация, распределение работ, и исполнение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
