Исследование и разработка метода ускорения операции соединения распределенных массивов данных по заданному критерию тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Тырышкина Евгения Сергеевна

• Тырышкина Евгения Сергеевна
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Тырышкина Евгения Сергеевна

Введение

1. Анализ технологий хранилищ данных

1.1. Распределенная файловая система Hadoop

1.2. Принцип NoSQL

2. Сравнение технологий MapReduce, HadoopDB и Apache Spark

3.1 MapReduce

3.2. Технология HadoopDB

3.3. Технология Apache Spark

4. Анализ архитектуры Apache Spark

4.1. Возможности Spark RDD API

4.2. Возможности Spark DataFrame API

4.3. Сравнение Spark RDD API и Spark DataFrame API

5. План выполнения программ в Apache Spark

6. Методы выполнения операции соединения распределенных массивов данных в Apache Spark

6.1. Типы соединений Apache Spark

6.2. Способы ускорения операции соединения в Apache Spark

7. Партиционирование данных

7.1. Типы партиционирования

7.2. Проблемы при партиционировании данных

7.3. Подходы к решению проблемы асимметричного распределения данных

8. Метод ускорения операции соединения распределенных массивов данных на основе заданного критерия

8.1. Применение партиционирования для ускорения операции соединения

8.2. Механизм широковещательного обмена партициями

9. Методика экспериментального исследования разработанного метода

10. Обоснование применимости предлагаемого метода для ускорения операции соединения распределенных массивов данных по заданному критерию

11. Результаты компьютерного эксперимента

12. Заключение

Библиографический список

Приложение

Введение

Актуальность темы исследования

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

Долгое время скорость вычислений увеличивалась за счет увеличения производительности процессоров: каждый год новые процессоры были способны выполнять больше операций в секунду, чем раньше. Эта тенденция создала большую и устойчивую экосистему приложений, работающих только на одном процессоре. Эта тенденция к аппаратной экспансии закончилась примерно в 2005 году: разработчики аппаратного обеспечения столкнулись с жесткими ограничениями по тепловыделению, поэтому им пришлось отказаться от разгона производительности одного процессора и переключиться на перспективное направление распараллеливания ядер центрального процессора, работающих с одинаковой скоростью. Так, для повышения производительности обработка данных стала производиться в кластерных системах, состоящих из множества вычислительных машин.

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

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

В данной работе рассматривается возможность ускорения частного случая операции соединения: левостороннего соединения, то есть в итоговую выборку попадают все значения из левого набора данных, к которым при соответствии критерию соединения добавляются записи из правого набора. Если соответствующая левому набору данных запись не найдена в правом наборе данных, к результату добавляется нулевое значение.

Данная разработка построена на базе HDFS, что является файловой системой для хранения файлов больших размеров с возможностью потокового доступа к информации поблочно распределённой по узлам вычислительного кластера. Используется данная файловая система не только для хранения, но и для обработки информации. Для обработки информации в подобных распределенных файловых системах заложена вычислительная модель MapReduce, получившая название по 2м этапам данной концепции: Map - чтение и преобразование и Reduce - агрегация и запись. Алгоритм, разработанный на основе предлагаемого в работе метода, был разработан во фреймворке Apache Spark, в основе которого также лежит концепция MapReduce, исключающая многократные записи и чтения на диск и более эффективно использующая оперативную память. Выбор данного фреймворка был обусловлен рядом преимуществ, которыми он обладает: предоставляет удобный интерфейс разработчика и высокоуровневые инструменты для создания собственных расширений и утилит; распространяется под свободной лицензией с открытым исходным кодом; используется большим сообществом разработчиков; демонстрирует высокую эффективность; подтвержденную независимыми исследованиями разных компаний.

Во фреймворке Spark предоставляется библиотека Spark SQL, включающая 3 метода выполнения соединений: hash join, sort-merge join, broadcast join [5]. Выбор метода осуществляется на основе входных данных и каждый представленный метод имеет определенные ограничения. Так, broadcast join ограничен объемом входных данных, sort-merge join - наличием этапа сортировки, sort-merge join и

hash join - наличием этапа перемещения, реорганизации данных в файловой системе перед выполнением операции соединения.

В направлении ускорения операций с данными в распределенных файловых системах, в частности ускорение операции соединения, ведутся активные исследования и разработка новых методов. Исследуются способы ускорения операции соединения для определенного аппаратного обеспечения, например, ПЛИС (программируемых логических интегральных схем)[1]. Ведутся исследования, направленные на ускорение соединения данных по определенным типам условий, таким как theta-join, соединяющим строки из нескольких таблиц по критерию соединения, включающему оператор сравнения больше или меньше [2]. А также ускорение операции соединения для специфичного представления исходных данных, например, RDF (Resource Description Framework), который представляет собой модель представления и обмена данными в Интернете и обеспечивает гибкий, расширяемый способ описания ресурсов, их свойств и отношений между ними в машинно-читаемом формате [3].

Таким образом, существует несколько областей активных исследований, связанных с соединением данных. Вот некоторые примеры:

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

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

3. Оптимизация соединения. Исследователи работают над оптимизацией операций соединения, учитывая такие факторы, как оптимизация порядка соединения, оценка селективности предиката соединения и оценка кардинальности соединения. Они стремятся минимизировать вычислительные затраты и улучшить общую эффективность запросов объединения.

4. Техники объединения для больших данных. Большие данные (Big Data) представляют уникальные вызовы для операций соединения из-за объема и разнообразия данных. Исследуются такие техники, как выборка, суммирование данных и приближенные алгоритмы соединения, чтобы эффективно обрабатывать большие объемы данных, сохраняя приемлемую точность.

5. Соединение в потоковых данных. С развитием аналитики в реальном времени, исследователи фокусируются на разработке алгоритмов соединения, которые могут обрабатывать потоковые данные. Они исследуют такие техники, как оконные соединения, соединения на основе времени и инкрементальную обработку соединения для выполнения операций в реальном времени на непрерывно поступающих потоках данных.

6. Оптимизация соединения в облачных средах. Облачные вычисления предоставляют гибкие и масштабируемые ресурсы для обработки данных. Исследователи исследуют техники оптимизации соединения, специфичные для облачных сред, такие как стратегии размещения данных, выделение ресурсов и учет затрат при выполнении операций соединения.

7. Соединение в графовых базах данных. Графовые базы данных имеют уникальные характеристики, и операции соединения в которых требуют специализированных алгоритмов и оптимизации запросов на основе графов.

Это всего лишь несколько примеров активных исследовательских областей, связанных с соединением данных. Исследовательское сообщество непрерывно работает над решением этих задач и улучшением производительности, масштабируемости и эффективности операций соединения в различных сценариях обработки данных.

Таким образом, тематика диссертационного исследования, посвященная разработке метода ускорения операции соединения распределенных массивов данных по заданному критерию, несомненно, является актуальной.

Объект исследования - операция соединения распределенных массивов данных по заданному критерию.

Предмет исследования - затраты машинного времени на выполнение операции соединения данных в распределенных вычислительных системах.

Цель исследования и научная задача заключается в снижении затрат машинного времени за счет разработки и внедрения метода ускорения операции соединения распределенных массивов данных по заданному критерию.

Для достижения этой цели были сформулированы и поставлены задачи:

1. Провести критический обзор и анализ литературных источников, в которых рассматриваются вопросы проектирования архитектур распределенных хранилищ данных и алгоритмы параллельных вычислений;

2. На основе анализа литературных данных выявить лимитирующие стадии стандартных алгоритмов соединения массивов данных;

3. Разработать метод ускорения операции соединения распределенных массивов данных по заданному критерию;

4. На основе разработанного метода операции соединения распределенных массивов данных создать алгоритм и утилиту для его реализации, позволяющую ускорить процесс их соединения;

5. Выполнить экспериментальные исследования, подтверждающие работоспособность и эффективность разработанного метода;

6. Внедрить разработанный метод в рабочий цикл УК.

Научная новизна

1. Выявлены две ранее до конца не изученные лимитирующие стадии выполнения операции соединения распределенных массивов данных по заданному критерию. Это стадия сортировки и стадия перемещения данных по вычислительному кластеру;

2. Разработан метод ускорения операции соединения массивов данных отличающийся от известных тем, что данные одного из объединяемых датасетов не сортируются и не перемещаются внутри кластера;

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

Практическая значимость работы заключается в возможности применения разработанного метода ускорения операции соединения распределенных массивов данных по заданному критерию для широкого круга задач. На основе разработанного метода создан алгоритм и утилита для реализации этого алгоритма. Экспериментально определено, что увеличение объема массивов данных приводит к увеличению скорости соединения. Показано, что для данных размером 2Tb операция соединения была выполнена на ~ 37% быстрее, чем предложенный алгоритм в Spark SQL, для данных размером 7Tb это ускорение составило уже ~ 47%.

Методы исследования. В данной диссертационной работе применялись методы объектно- ориентированного анализа и проектирования, методологии моделирования и проектирования программных систем, методы модульного программирования. Для оценки результатов и достоверности предложенного метода и разработанного алгоритма были проведены компьютерные эксперименты.

Положения, выносимые на защиту:

1. Метод ускорения операции соединения массивов данных, отличающийся от известных тем, что данные одного из объединяемых датасетов не сортируются и не перемещаются внутри кластера;

2. Разработанный на основе предложенного метода алгоритм и пользовательская библиотека, расширяющая функционал программного продукта Apache Spark;

3. Результаты экспериментальных исследований работы операции соединения распределенных массивов данных стандартными методами библиотеки Spark SQL и разработанного алгоритма на объемах данных от 100Mb до 7Tb.

Соответствие паспорту специальности

Цель исследования и научная задача заключается в снижении затрат машинного времени за счет разработки и внедрения метода ускорения операции соединения распределенных массивов данных по заданному критерию и вносит вклад в следующие области исследований специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», перечисленные в паспорте этой специальности НИУ ВШЭ «Информатика, вычислительная техника и управление»:

1. системы управления базами данных и знаний;

2. модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования;

3. модели, методы, алгоритмы и программная инфраструктура для организации глобально распределенной обработки данных.

Введение диссертации (часть автореферата) на тему «Исследование и разработка метода ускорения операции соединения распределенных массивов данных по заданному критерию»

Апробация работы

1. Y. Tyryshkina. Understanding join strategies in distributed systems. International Seminar on Electron Devices Design and Production (SED-2021), 2021, Czech Republic, pp 1-4. doi:10.1109/SED51197.2021.9444489.

2. Y. Tyryshkina, Accelerating join of distributed datasets by a given criterion. In proceedings of 2022 IEEE Moscow Workshop on Electronic and Networking Technologies (MWENT), 2022, Russian Federation, pp 1-3. doi:10.1109/MWENT55238.2022.9802185.

3. Е. С. Тырышкина, С. Р. Тумковский. Метод ускорения соединения распределенных наборов данных по заданному критерию. Информационно-управляющие системы, 2022, Российская Федерация.

Личный вклад автора состоит в формулировке и постановке задач исследования и их решении, подготовке, реализации, расчёте и анализе экспериментальных и теоретических данных, модификации и использовании программного кода для проведения всевозможных расчётов, подготовки и визуализации графического материала, подготовки текста статей и представлении результатов исследований в российских и международных изданиях и конференциях. Получен акт о внедрении результатов диссертационного исследования в процесс обработки данных в компании "VK" (см. Приложение 1)

Достоверность полученных результатов в диссертационном исследовании подтверждаются:

• тестами, проведенными в соответствии с общепринятыми стандартами;

• соответствием полученных результатов бенчмаркам независимых исследований;

• соответствием результатов компьютерного эксперимента и расчетов предложенным эмпирическим моделям.

Степень разработанности проблемы

Операция соединения сильно влияет на производительность аналитических вычислений, так как использует много ресурсов памяти, сетевых ресурсов и дисковых ресурсов. В Spark SQL для решения актуальной проблемы ускорения операции соединения применяется модуль «Оптимизатор запросов Catalyst». Однако реализованные в данном модуле методы выполнения операции соединения имеют лимитирующие стадии, замедляющие время выполнения запросов. Это стадия сортировки и стадия перемещения данных по вычислительному кластеру.

Предложенный метод ускорения операции соединения массивов данных отличается от известных тем, что данные одного из объединяемых датасетов не сортируются и не перемещаются внутри кластера. Разработанный метод направлен на устранение ключевых недостатков существующих подходов к выполнению

операции соединения массивов данных. Разработанная пользовательская библиотека может использоваться в качестве расширения функционала фреймворка Apache Spark и применения во многих аналитических целях.

Список опубликованных статей по теме диссертации.

1. Y. Tyryshkina. Understanding join strategies in distributed systems. International Seminar on Electron Devices Design and Production (SED-2021), 2021, Czech Republic, pp 1-4. doi:10.1109/SED51197.2021.9444489.

2. Y. Tyryshkina, Accelerating join of distributed datasets by a given criterion. In proceedings of 2022 IEEE Moscow Workshop on Electronic and Networking Technologies (MWENT), 2022, Russian Federation, pp 1-3. doi:10.1109/MWENT55238.2022.9802185.

3. Е. С. Тырышкина, С. Р. Тумковский. Метод ускорения соединения распределенных наборов данных по заданному критерию. Информационно-управляющие системы, 2022, Российская Федерация.

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

Трафик данных увеличился до уровней, о которых мы и не подозревали чуть более десяти лет назад, и темпы роста не снижаются. Экспоненциальный рост трафика данных открыл эру больших данных, поступающих из ряда источников, от мобильных приложений, социальных сетей, клиентских баз данных или данных с устройств IoT (Интернет вещей). Таким образом, появляется понятие хранилище данных.

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

Анализ данных используется компаниями для получения подробной информации об эффективности бизнеса, маркетинговых показателей и принятия решений путем сравнения объединенных данных из различных разнородных источников данных. Хранилище данных используется для анализа исторических данных, полученных из транзакционных ресурсов.

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

Любые данные, помещаемые в хранилище, не изменяются и не могут быть изменены, поскольку хранилища данных используются для анализа инцидентов, произошедших ранее, концентрируясь на изменениях данных с течением времени. Хранилище данных должно быть организовано таким образом, чтобы хранимые данные оставались безопасными, надежными и могли легко извлекаться и управляться.

В процесс управления хранилищами данных входят следующие этапы:

Извлечение данных. Большой объем данных собирается из различных источников.

Очистка данных. После того, как данные скомпилированы, они проходят процесс очистки. Данные сканируются на наличие ошибок, и любая найденная ошибка либо исправляется, либо исключается.

Преобразование данных. После очистки формат меняется с базы данных на формат хранилища.

Хранение данных. После преобразования в формат хранилища данные, хранящиеся в хранилище, проходят такие процессы, как консолидация и суммирование, чтобы сделать их более простыми и скоординированными в использовании. Поскольку источники со временем обновляются, в хранилище добавляется больше данных.

Хранилище данных, при успешном внедрении, может принести пользу организации следующими способами:

1. Конкурентное преимущество

Конкурентное преимущество достигается за счет предоставления лицам, принимающим решения, доступа к данным, которые могут раскрыть ранее недоступную и неиспользованную информацию, касающуюся клиентов, требований и тенденций.

2. Повышение качества и скорости принятия решений

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

3. Экономически эффективное принятие решений

Хранилище данных хранит все данные в одном месте и не требует серьезной ИТ-поддержки. Меньше потребности во внешней отраслевой информации, которая является дорогостоящей и сложной для интеграции.

Реляционные базы данных были распространенной технологией на протяжении десятилетий, обеспечивающие хранилище связанных таблиц данных [4]. Эти таблицы имеют фиксированную схему, используют SQL (язык структурированных запросов) для управления данными и поддерживают гарантии ACID (Atomicity, Consistency, Isolation, Durability). ACID — это аббревиатура, расшифровывающаяся как атомарность, согласованность, изолированность, долговечность [5].

В то же время то, что сейчас называют «традиционными базами данных», уступает место инновационным решениям для баз данных. Появление больших данных означает повышенное внимание к новым технологиям, новым задачам и новым наборам навыков, которые необходимо развивать, чтобы не отставать от темпов развития технологий баз данных.

Появление «озер данных» («data lake») в качестве предпочтительного решения для хранения больших данных означает, что традиционные хранилища данных, построенные на реляционных базах данных и способные хранить только структурированные данные трудно применимы. Озера данных обычно основаны на кластерах Hadoop или, например, базах данных NoSQL. Базы данных NoSQL относятся к высокопроизводительным нереляционным хранилищам данных. Они отличаются простотой использования, масштабируемостью, отказоустойчивостью и доступностью [6]. Вместо соединения таблиц нормализованных данных NoSQL хранит неструктурированные или частично структурированные данные, часто в парах ключ-значение или в документах JSON. Базы данных без SQL обычно не предоставляют гарантии ACID за рамками одного раздела базы данных. Сервисы, работающие с большими объемами данными, требующие времени отклика менее секунды, отдают предпочтение хранилищам данных NoSQL. Влияние технологий NoSQL на распределенные облачные системы невозможно переоценить. Распространение новых технологий данных в этой области подорвало решения, которые когда-то полагались исключительно на реляционные базы данных [7].

В кластерной архитектуре все запросы распределяются между несколькими компьютерами, так что запрос отдельного пользователя выполняется несколькими

компьютерными системами. Кластеризация определенно полезна благодаря способности балансировки нагрузки и высокой доступности. Если один узел выходит из строя, запрос обрабатывается другим узлом. Следовательно, вероятность абсолютного отказа системы очень мала или вообще отсутствует.

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

Одной из важных задач при анализе данных является задача их соединения. В настоящее время эта задача широко изучается, предлагаются новые методы ее решения (например [1], [2], [3]), особенно для работы с большими наборами данных в распределенной среде, однако, имеющиеся, в настоящее время методы недостаточно эффективны: требуют больших перемещений данных между вычислительными нодами кластера, используют много оперативной памяти.

Первая проблема, с которой приходится сталкиваться при выполнении запроса на соединение данных в распределенных базах данных — это сортировка и перемещение данных внутри кластера, которое увеличивает нагрузку на сеть, что, несмотря на технический прогресс, остается одним из узких мест в кластерных системах. Вторая проблема заключается в том, что невозможно поместить весь набор данных в оперативную память, и данные многократно перезаписываются на жесткие диски, что также сильно замедляет их обработку. Третья проблема вызвана особенностями данных, а именно тем, что некоторые значения в данных встречаются гораздо чаще, чем другие. В этом случае простая стратегия

соединения приводит к неравномерному разделению данных на партиции на вычислительных узлах. Затраты на обработку таких данных приводят в лучшем случае к значительной задержке общего времени решения задачи соединения, а в худшем - к полной невозможности ее решения.

В данной работе рассматриваются особенности вычислений в распределенной среде, обсуждается архитектура Apache Spark, для которой будет предложена стратегия ускорения решения задачи соединения данных. В качестве основного критерия сравнения архитектуры Apache Spark и MapReduce мы рассматриваем время решения задачи соединения данных. При этом надежность вычислений и удобство разработки мы считаем равными. Рассматриваются типовые стратегии соединения данных, особенности их применения, показываются возможные проблемы и узкие места. Представлен разработанный метод решения задачи соединения распределенных наборов данных по заданному критерию и его экспериментальные исследования.

1. Анализ технологий хранилищ данных

1.1. Распределенная файловая система Hadoop.

В настоящее время крупные аналитические платформы ежедневно обрабатывают десятки терабайт данных. Это привело к появлению новых файловых систем и систем управления базами данных [8]. Одной из таких является файловая система Google (GFS) [9] или распределенная файловая система Hadoop (HDFS). Долгое время самым быстрым и надежным решением для создания приложений в этой файловой системе был Google MapReduce, который является основным компонентом Hadoop и обеспечивает обработку данных [10, 11]. Hadoop работает со структурированными, слабоструктурированными и неструктурированными данными. HDFS масштабируется до сотен/тысяч узлов. HDFS предназначена для поддержки очень больших файлов. Она разбивает эти большие файлы на маленькие части, известные как блоки. Блоки содержат определенный объем данных, которые можно читать или записывать, и HDFS хранит каждый файл как блок. По умолчанию размер блока составляет 128 МБ (размер блока может быть изменен в зависимости от требований пользователей). Hadoop распределяет блоки по нескольким узлам. Блоки данных реплицируются для обеспечения отказоустойчивости, и приложение может указать количество реплик файла. Коэффициент репликации, т.е. общее количество копий по всему кластеру, можно указать во время создания файла и изменить позже. Файлы в HDFS предназначены для однократной записи и в любой момент времени в файл может записывать только одно записывающее устройство. Неймнода (от англ. «NameNode») принимает все решения относительно репликации блоков и получает «Heartbeat» (периодический сигнал, генерируемый аппаратным или программным обеспечением для индикации нормальной работы или для синхронизации других частей компьютерной системы) и «Blockreport» (список всех блоков данных) от каждой ноды данных в кластере. Подробнее архитектура кластера представлена на рисунке 1.

Рисунок 1. Взаимодействие внутри кластера HDFS: JobTracker и TaskTracker

HDFS создает реплику каждого блока данных, который находится на узлах в любом заданном кластере, обеспечивая отказоустойчивость. Если узел выходит из строя, к этим данным по-прежнему можно получить доступ на других узлах, содержащих копию тех же данных в этом кластере HDFS. По умолчанию HDFS создает три копии блоков.

1.2. Принцип NoSQL

Термин «база данных NoSQL» используется для обозначения любой нереляционной базы данных. Базы данных NoSQL появились в конце 2000-х годов, когда стоимость хранения резко снизилась [12]. Прошли те времена, когда нужно было создавать сложную, трудноуправляемую модель данных, чтобы избежать дублирования данных. Разработчики (а не хранилище) становились основной статьей расходов при разработке программного обеспечения, поэтому базы данных NoSQL были оптимизированы для повышения производительности разработчиков. Базы данных NoSQL — это базы данных, которые хранят данные в формате, отличном от реляционных таблиц.

Базы данных NoSQL поддерживают высокую доступность и устойчивость к разделам. Они масштабируются горизонтально на стандартных серверах [13].

Данные на этих узлах разделяются и реплицируются на машинах (или узлах), обеспечивая избыточность и отказоустойчивость. Согласованность обычно настраивается с помощью протоколов консенсуса или механизмов кворума. Они обеспечивают больший контроль при поиске компромиссов между настройкой синхронной и асинхронной репликации в реляционных системах. Если реплики данных потеряют связь с «высокодоступным» кластером базы данных NoSQL, выполнить операцию записи в базу данных будет возможно. Кластер базы данных разрешит операцию записи и обновит каждую реплику данных по мере ее появления. Базы данных NoSQL, поддерживающие несколько реплик с возможностью записи, могут дополнительно повысить доступность, избегая необходимости аварийного переключения при оптимизации целевого времени восстановления. Современные базы данных NoSQL обычно реализуют возможности партиционирования. Управление разделами (партициями) часто встроено в базу данных, а маршрутизация достигается с помощью «ключей» разделов. Высокая доступность и массовая масштабируемость часто более важны для решения аналитических задач, чем механизм связей реляционных таблиц и ссылочная целостность [14].

Далее сравним доступные на данный момент технологии MapReduce, HadoopDB и Apache Spark, чтобы показать преимущества последней по удобству разработки и скорости выполнения запросов.

2. Сравнение технологий MapReduce, HadoopDB и Apache Spark

3.1 MapReduce

MapReduce также относится к категории NoSQL баз данных. MapReduce -инструмент распределенных вычислений, который способен работать на тысячах узлов кластера [15], являющийся моделью программирования для разработки масштабируемых параллельных приложений с большими данными в вычислительных кластерах [16].

Концепция MapReduce заключается в том, что процесс обработки данных, хранящихся в одном или нескольких файлах, делится на две фазы: отображение и сокращение (рисунок 2). Результатом обработки являются пары ключ-значение. Каждая фаза имеет ключ-значение в качестве входа и выхода. Ключи и значения не являются внутренними свойствами данных, но они выбираются пользователем, который анализирует данные. Генерация пары ключ-значение Hadoop зависит от набора входных данных и требуемого выхода. Основная задача первого этапа (map) - отфильтровать данные и предоставить возможность группировать данные по ключу, т.е. (k1, v1) ^ List (k2, v2). Второй этап (reduce) использует функцию для соединения значений, связанных одним ключом, для получения результата для этого ключа, то есть (k2, List (v2)) ^ List (k3, v3). Тип входных параметров пары ключ-значение, представленных k1 и v1 соответственно, отличаются от типа выходной пары: k2 и v2. Функция reduce принимает тот же тип входных параметров, что и map, но тип выходных параметров пары ключ-значение операции reduce снова другой: K3 и V3. Ключ - это поле или объект, по которому будет выполняться группировка и агрегация на этапе «reduce». Значение - это поле или объект, к которому будет применяться функция агрегирования.

Данные на выходе из этапа map разделяются и сортируются таким образом, чтобы их можно было распределить данные в соответствии с критерием группировки на следующей стадии по датанодам, которые будут участвовать в вычислении агрегатной функции на этапе reduce.

Input Data

>

>

^ Output Data

Рисунок 2. Диаграмма MapReduce

Вычисление через MapReduce в три этапа:

1. данные считываются из HDFS

2. применяются операции Map и Reduce

3. вычисленный результат записывается обратно в HDFS

Каждая операция MapReduce независима друг от друга, и Hadoop не знает, какая операция MapReduce будет следующей. Иногда для некоторых вычислений бессмысленно читать и записывать промежуточный результат между двумя операциями Map Reduce. В таком случае дисковая память или HDFS расходуются впустую. В многоэтапных задачах каждая следующая итерация заблокирована предыдущей, как следствие сложные вычисления могут потребовать дополнительного времени на ожидание даже при небольшом объеме данных.

Что касается решения задачи соединения данных [17], технология MapReduce гарантирует чрезвычайно высокую надежность вычислений при чрезмерно медленном ее решении, в частности, в результате серьезной неравномерности ключей в партиционированных наборах данных является ее недостатком [18, 19]. Технология MapReduce медленная, так как все задачи в ней решаются многократными повторения операции чтения и записи.

Несмотря на то, что технология MapReduce является классическим решением и лежит в основе многих приложений, основным ее недостатком является низкая скорость вычислений. Написание новых программ, работающих на MapReduce также осложнено отсутсвием удобного API.

3.2. Технология HadoopDB

На основе Hadoop и PostgreSQL разработана платформа HadoopDB (рисунок 3), которая расширяет HDFS следующими четырьмя компонентами [20]:

- Data Connector

- Каталог

- Загрузчик данных (Data Loader)

- Планировщик SQL

Рисунок 3. Архитектура HadoopDB Data Connector. Это интерфейс между независимыми системами баз данных, располагаемыми в узлах кластера, и компонентами TaskTracker. Он расширяет класс InputFormat предоставляемый Hadoop. От каждой задачи MapReduce в коннектор поступают SQL-запрос и параметры подключения, такие как указание на требуемый драйвер JDBC, размер структуры выборки запроса и другие параметры настройки запроса. Коннектор подключается к базе данных, выполняет SQL-запрос и возвращает результат в виде пар "ключ-значение". Теоретически коннектор мог бы подключаться к любой JDBC-совместимой системе баз данных,

располагаемой в кластере. Однако для разных баз данных требуются разные оптимизации запросов на выборку данных. Реализовали коннекторы для MySQL и PostgreSQL. За счет расширения InputFormat из Hadoop обеспечивается органичная интеграция с MapReduce.

Каталог. В каталоге поддерживается метаинформация о базах данных:

- параметры соединения, такие как месторасположение базы данных, класс драйвера и учетные данные;

- метаданные, такие как наборы данных, содержащиеся в кластере, местоположение реплик и свойства разделения данных.

В текущей реализации HadoopDB эта метаинформация сохраняется в формате XML в HDFS. К этому файлу обращаются JobTracker и TaskTracker для выборки информации, требуемой для планирования задач и обработки данных, которые требуются для запроса.

Загрузчик данных (Data Loader). Загрузчик данных отвечает за:

1. глобальное переразделение данных по заданному ключу при их загрузке;

2. разбиение данных, хранимых в одном узле, на несколько более мелких разделов или чанков (chank);

3. массовую загрузку данных в одноузловые базы данных с использованием чанков.

Загрузчик данных состоит из двух основных компонентов: Global Hasher и Local Hasher. Global Hasher выполняет специальное задание MapReduce в Hadoop, которое читает файлы данных, хранимые в HDFS, и переразделяет их на столько частей, сколько имеется узлов в кластере. Работа разделения не вызывает накладные расходы сортировки типичных работ MapReduce. Затем Local Hasher в каждом узле копирует соответствующий раздел из HDFS в локальную файловую систему узла, разделяя его на более мелкие чанки на основе заданного в системе максимального размера чанка. В Global Hasher и Local Hasher используются разные хэш-функции, чтобы у чанков были примерно одинаковые размеры. Эти хэш-функции также отличаются от функции хэш-разделения, используемой в Hadoop

по умолчанию, что обеспечивает лучшую балансировку нагрузки при выполнении заданий MapReduce над данными.

Планировщик SQL. В HadoopDB аналитикам данных предоставляется внешний интерфейс, позволяющий выполнять SQL-запросы [21, 22]. Планировщик SQL является расширением Hive. Hive преобразует HiveQL (вариант SQL) в задания MapReduce, которые подключаются к таблицам, хранимым в виде файлов HDFS. Поскольку каждая таблица хранится в виде отдельного файла HDFS, в Hive не предполагается совместное размещение таблиц на нодах. Поэтому операции над несколькими таблицами выполняются на фазе Reduce задания MapReduce.

Таким образом, видно, что HadoopDB является только надстройкой над технологие MapReduce, расширяя возможности работы с Hadoop засчет реализованных интерфейсов взаимодействия с другими базами данных, что упрощает процесс загрузки данных в хранилище и выполнение SQL запросов. Однако, скорость выполнения запросов остается такой же как у MapReduce, а отсутствие удобного API для разработчиков сильно ограничивает возможности по добавлению пользовательский приложений и дополнений.

З.З.Технология Apache Spark

Apache Spark — это технология кластерных вычислений, получившая развитие на основе технологии MapReduce [23, 24]. В отличии от заложенной в модель MapReduce концепции на основе двухэтапной обработки map и reduce, которая использует дисковое хранилище, в Spark применяется подход поэтапной обработки в оперативной памяти. Это позволило существенно увеличить скорость обработки в Spark по сравнению с MapReduce [25, 26, 27, 28]. Использование оперативной памяти в процессе вычислений предоставляет возможность многократного доступа к данным, что необходимо для быстрой работы алгоритмов машинного обучения, где широко применяются итерационные алгоритмы. Кэширование промежуточных результатов в памяти, ускоряет работу таких алгоритмов [29].

Apache Spark представляет собой механизм обработки данных с открытым исходным кодом, созданный для обеспечения высокой производительности и крупномасштабного анализа данных. Spark состоит из пяти основных компонентов: ядро Spark, Spark SQL (для сбора информации о структурированных данных) [30, 31, 32], Spark Streaming (для потоков данных в реальном времени) [33, 34], библиотеки машинного обучения [35, 36, 37] и GraphX [38, 39, 40]. Это помогает Spark хорошо работать для различных рабочих нагрузок больших данных, таких как пакетная обработка, обработка данных в реальном времени, вычисление графов, машинное обучение и интерактивные запросы. Кроме того, Apache Spark также имеет хорошо продуманный интерфейс прикладного программирования (Python, Scala, R [41, 42]), включающий различные параллельные коллекции.

Список литературы диссертационного исследования кандидат наук Тырышкина Евгения Сергеевна, 2024 год

Библиографический список

1. M. Yoshimi, Y. Oge, T. Yoshinaga. Pipelined Parallel Join and Its FPGA-Based Acceleration // ACM Transactions on Reconfigurable Technology and Systems - 2017, Выпуск 10, Раздел 4. doi: 10.1145/3079759.

2. X. Zhang, L. Chen, and M. Wang. Efficient Multi-way Theta-Join Processing Using MapReduce // VLDB Endowment - 2012, Выпуск 5, Номер 11, 1184-1195 стр. doi: 10.14778/2350229.2350238.

3. M. Saleem, A. Potocki, T. Soru, O. Hartig, Axel-Cyrille Ngonga Ngomo. CostFed: Cost-Based Query Optimization for SPARQL Endpoint Federation // SEMANTiCS 2018 - 14th International Conference on Semantic Systems - 2018.

4. О.Л. Голицына, Н.В. Максимов, И.И. Попов. Базы данных. 4-е изд. ИНФРА-М, 2019, 400 с.

5. Muhammad Arshad, M. Nawaz Brohi, Tariq Rahim Soomro, Taher M. Ghazal. NoSQL: Future of BigData Analytics Characteristics and Comparison with RDBMS. - 2023, 1927-1951 стр, D0I:10.1007/978-3-031-12382-5_106.

6. Daniel Balazs Ratai, Zoltan Horvath, Zoltan Porkolab, Melinda Toth. Traquest Model: A Novel Model for ACID Concurrent Computations. Acta Cybernetica - 2021. 435-468 стр. DOI: 10.14232/actacyb.288765.

7. С.А. Мартишин, В.Л. Симонов, М.В. Храпченко. Базы данных: Работа с распределенными базами данных и файловыми системами на примере MongoDB и HDFS с использованием Node.js, Express.js, Apache Spark и Scala. ИНФРА-М, 2020, 235 с.

8. Dr.S.Sudhaka, Dr.N.Satheesh, Dr.S.Balu, Amireddy Srinish Reddy, Dr.G.Murugan. Optimizing Joins in a Map-Reduce for Data Storage and Retrieval Performance Analysis of Query Processing in HDFS for Big Data. International Journal of Advanced Trends in Computer Science and Engineering - 2019, DOI:10.30534/ijatcse/2019/33852019.

9. M. Elkawkagy, H. Elbeh. High Performance Hadoop Distributed File System. International Journal of Networked and Distributed Computing, Выпуск 8, Раздел 3 - 2020, 119 - 123 стр.

10. S. Maitrey, C.K. Jha, MapReduce: Simplified Data Analysis of Big Data, Procedia Computer Science - 2015, Выпуск 57, 563-571 стр, ISSN 1877-0509, doi: 10.1016/j.procs.2015.07.392.

11. Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters. Commun ACM 51(1), 2008, pp 107-113

12. Nayak, A. & Poriya, A. & Poojary, Dikshay. Type of nosql databases and its comparison with relational databases. International Journal of Applied Information Systems -2013, Выпуск 5, 16-19 стр.

13. Nafrees, A C M. & Asra, Sahabdeen. A Systematic Review of Relational Databases and NoSQL Databases // 11th South Eastern University International Arts Research Symposium SEUIARS - 2022, Шри-Ланка.

14. Shaida Begum. An Invigorating Perspective of a Practical Aspect of NoSQL Database. International Journal of Research Publication and Reviews - 2022. 1000-1004 стр. D0I:10.55248/gengpi.2022.3.9.29.

15. T. Y. J. Naga Malleswari and G. Vadivu. MapReduce: A Technical Review. Indian Journal of Science and Technology - 2016, Выпуск 9, Раздел 1, 1-6 стр, doi: 10.17485/ijst/2016/v9i1/78964.

16. K. Shim. MapReduce algorithms for big data analysis. VLDB Endowment - 2012, Выпуск 5, Номер 12, 2016-2017 стр. doi:10.14778/236502.2367563

17. Amer F. Al-Badarneh, Salahaldeen Atef Rababa, An analysis of two-way equi-join algorithms under MapReduce, Journal of King Saud University - Computer and Information Sciences - 2022, Выпуск 34, Раздел 4, 1074-1085 стр.

18. E. Gavagsaz, A. Rezaee, H.H.S. Javadi. Load balancing in join algorithms for skewed data in MapReduce systems. The Journal of Supercomputing - 2019, Выпуск 75, 228-254 стр.

19. Y. C. Kwon, M. Balazinska, B. Howe, and J. Rolia. A study of skew in mapreduce applications // Open Cirrus Summit. - Moscow, 2011.

20. Azza Abouzeid. HadoopDB: an architectural hybrid of MapReduce and DBMS technologies for analytical workloads. VLDB, 2009.

21. Chris Fehily. SQL: Visual QuickStart Guide. Peachpit Press, 2008, p 5, ISBN 978-0321-58406-9.

22. D. Du. Apache Hive Essentials: Essential Techniques to Help You Process, and Get Unique Insights from, Big Data, 2nd ed. Birmingham, 2018, p 12. ISBN 978-1-78899-509-2.

23. A. Muneeba. Analysis of Data Processing Framework Using Apache and Spark Technologies in Big Data. 2021.

24. Mavridis I, Karatza H. Performance evaluation of cloud-based log file analysis with Apache Hadoop and Apache Spark. J Syst Softw 125, 2017, pp 133-151.

25. G. Gousios. Big data software analytics with Apache Spark // 40th International Conference on Software Engineering (ICSE 2018) - США, 2018.

26. Gopalani S, Arora R. Comparing apache spark and map reduce with performance analysis using k-means. Int J Comput Appl 113(1), 2015, pp 8-11.

27. Hazarika AV, Ram GJSR, Jain E. Performance comparison of Hadoop and spark engine. In: 2017 International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC). IEEE, pp 671-674.

28. Hussain DM, Surendran D. The efficient fast-response content-based image retrieval using spark and MapReduce model framework. J Ambient Intell Humaniz Comput, 2020. https ://doi. org/10.1007/s1265 2-020-01775 -9.

29. Andrea Manconi, Matteo Gnocchi, Luciano Milanesi, Osvaldo Marullo, Giuliano Armanov. Framing Apache Spark in life sciences. Heliyon - 2023, DOI:10.1016/j.heliyon.2023.e13368

30. Michael Armbrust, Reynold S. Xin, Cheng Lian, Yin Huai, Davies Liu, Joseph K. Bradley, Xiangrui Meng, Tomer Kaftan, Michael J. Franklin, Ali Ghodsi, Matei Zaharia. Spark SQL: Relational Data Processing in Spark. SIGMOD 2015, 2015.

31. Michael Armbrust, Reynold Xin, Yin Huai, Davies Liu, Joseph K. Bradley, Xiangrui Meng, Tomer Kaftan, Michael Franklin, Ali Ghodsi, Matei Zaharia. Spark SQL: Relational Data Processing in Spark. ACM SIGMOD Conference 2015, 2015.

32. Reynold Xin, Joshua Rosen, Matei Zaharia, Michael Franklin, Scott Shenker, Ion Stoica. Shark: SQL and Rich Analytics at Scale. ACM SIGMOD Conference, 2013.

33. Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, Ion Stoica. Discretized Streams: Fault-Tolerant Streaming Computation at Scale. SOSP 2013, 2013.

34. Matei Zaharia, Tathagata Das, Haoyuan Li, Scott Shenker, Ion Stoica. Discretized Streams: An Efficient and Fault-Tolerant Model for Stream Processing on Large Clusters. HotCloud 2012, 2012.

35. Xiangrui Meng, Joseph Bradley, Burak Yavuz, Evan Sparks, Shivaram Venkataraman, Davies Liu, Jeremy Freeman, DB Tsai, Manish Amde, Sean Owen, Doris Xin, Reynold Xin, Michael J. Franklin, Reza Zadeh, Matei Zaharia, and Ameet Talwalkar. MLlib: Machine Learning in Apache Spark.. Journal of Machine Learning Research (JMLR), 2016

36. Ameet Talwalkar, Virginia Smith, Jey Kottalam, Xinghao Pan, Joseph Gonzalez, Michael Franklin, Michael Jordan, Tim Kraska. MLI: An API for Distributed Machine Learning Evan Sparks, ICDM, 2013.

37. Xiangrui Meng, Joseph Bradley, Burak Yavuz, Evan Sparks, Shivaram Venkataraman, Davies Liu, Jeremy Freeman, DB Tsai, Manish Amde, Sean Owen, Doris Xin, Reynold Xin, Michael Franklin, Reza Zadeh, Matei Zaharia, Ameet Talwalkar. MLlib: Machine Learning in Apache Spark. Journal of Machine Learning Research, 17 (34), 2016.

38. Reynold S. Xin, Daniel Crankshaw, Ankur Dave, Joseph E. Gonzalez, Michael J. Franklin, Ion Stoica. GraphX: Unifying Data-Parallel and Graph-Parallel Analytics. OSDI 2014, 2014.

39. Joseph Gonzalez, Reynold Xin, Ankur Dave, Dan Crankshaw, Michael Franklin, Ion Stoica. GraphX: Graph Processing in a Distributed Dataflow Framework. OSDI, 2014.

40. Reynold Xin, Joseph Gonzalez, Michael Franklin, Ion Stoica. GraphX: A Resilient Distributed Graph System on Spark. GRADES (SIGMOD workshop), 2013.

41. Shivaram Venkataraman, Zongheng Yang, Davies Liu, Eric Liang, Hossein Falaki, Xiangrui Meng, Reynold Xin, Ali Ghodsi, Michael Franklin, Ion Stoica, and Matei Zaharia. SparkR: Scaling R Programs with Spark. SIGMOD, 2016.

42. Shivaram Venkataraman, Zongheng Yang, Davies Liu, Eric Liang, Hossein Falaki, Xiangrui Meng, Reynold Xin, Ali Ghodsi, Michael Franklin, Ion Stoica, Matei Zaharia SIGMOD, 2016

43. Janardhanan PS, Samuel P. Optimum parallelism in Spark framework on Hadoop YARN for maximum cluster resource. In: First International Conference on Sustainable Technologies for Computational Intelligence: Proceedings of ICTSCI 2019, vol 1045, 2020 Springer Nature, p 351.

44. Taha Tekdogan, Ali Cakmak. Benchmarking Apache Spark and Hadoop MapReduce on Big Data Classification // ICCBDC '21: Proceedings of the 2021 5th International Conference on Cloud and Big Data Computing - 2021, 15-20 стр. D0I:10.48550/arXiv.2209.1063

45. H. Karau, R. Warren. High Performance Spark: Best Practices for Scaling and Optimizing Apache Spark, O'Reilly - 2017, 10 стр.

46. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, Ion Stoica. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. NSDI 2012, 2012.

47. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, Ion Stoica. Spark: Cluster Computing with Working Sets. HotCloud 2010, 2010.

48. N. Bruno, Y. Kwon, M. Wu. Advanced Join Strategies for Large-Scale Distributed Computation. VLDB Endowment - 2014, Выпуск 7, Номер 13, 1484-1495 стр. doi: 10.14778/2733004.2733020.

49. Amer Al-Badarneh. Join Algorithms under Apache Spark: Revisited // ICCTA '19: Proceedings of the 2019 5th International Conference on Computer and Technology Applications. - 2019, Турция, 56-62 стр, DOI:10.1145/3323933.3324094.

50. Anh-Cang Phan, Thuong-Cang Phan, Ngoan Trieu. A Comparative Study of Join Algorithms in Spark // Future Data and Security Engineering: 7th International Conference, FDSE 2020 - 2020, Вьетнам, 185-198 стр. DOI:10.1007/978-3-030-63924-2_11

51. M. Saitoh, E. A. Elsayed, T. Van Chu, S. Mashimo, and K. Kise. A highperformance and cost-effective hardware merge sorter without feedback datapath // 2018 IEEE 26th Annual International Symposium on FieldProgrammable Custom Computing Machines (FCCM), IEEE - 2018, 197-204 стр.

52. P. Papaphilippou, C. Brooks, and W. Luk. FLiMS: Fast Lightweight Merge Sorter // 2018 International Conference on Field-Programmable Technology (FPT) - 2018, 78-85 стр. DOI: 10.1109/FPT.2018.00022.

53. P. Papaphilippou, H. Pirk and W. Luk. Accelerating the Merge Phase of Sort-Merge Join // 2019 29th International Conference on Field Programmable Logic and Applications (FPL) - 2019, 100-105 стр, doi: 10.1109/FPL.2019.00025.

54. Suzhen Wang, Lu Zhang, Yanpiao Zhang. Research on the Optimization of Spark Big Table Equal Join. Artificial Intelligence and Security - 2019, 430-441 стр. DOI:10.1007/978-3-030-24265-7_37

55. Francisco Garcia-Garcia, Antonio Corral, Luis Iribarne, Michael Vassilakopoulos, Yannis Manolopoulos. Efficient distance join query processing in distributed spatial data management systems. Information Sciences. Выпуск 512 - 2020, 985-1008 стр, ISSN 00200255, DOI: 10.1016/j.ins.2019.10.030.

56. Michail Georgoulakis, Verena Kantere, Laurent D'orazio. Multi-objective query optimization in Spark SQL // IDEAS 2022 - International Database Engineered Applications Symposium - 2022, Венгрия.

57. X. Lian and T. Zhang. The Optimization of Cost-Model for Join Operator on Spark SQL Platform. MATEC Web of Conferences, vol. 173, 2018. doi: 10.1051/matecconf/201817301015.

58. H. Karau and R. Warren, High Performance Spark: Best Practices for Scaling and Optimizing Apache Spark. Sebastopol: O'Reilly Media, Incorporated, 2017. ISBN 978-1-49194320-5 [Page 3.]

59. P. Memarzia, S. Ray, V. Bhavsar. On Improving Data Skew Resilience In Mainmemory Hash Joins - 2018, 226-235 стр. 10.1145/3216122.3216156.

60. С.Р. Гуриков. Основы алгоритмизации и программирования на ру^пинфра-м, 2019. 343 с.

61. Мартин Одерски, Лекс Спун, Билл Веннерс Scala. Профессиональное программирование, 2017. ISBN 978-5-496-02951-3.

62. Myung J., Shim J., Yeon J., Lee S.G. Handling data skew in join algorithms using MapReduce. Expert Syst. Appl. 51, 2016, pp 286-299.

63. Potluri A., Bhattu S.N., Kumar N.N., Subramanyam R.B.V. Design Strategies for Handling Data Skew in MapReduce Framework. In Proceedings of International Conference on Inventive Computation Technologies, 2020, pp. 240-247.

64. Vitorovic A., Elseidy M., Koch C. Load Balancing and Skew Resilience for Parallel Joins. In Proceedings of the 32nd International Conference on Data Engineering, 2016, pp. 313-324.

65. M. Bandle, J. Giceva, T. Neumann. To Partition, or Not to Partition, That is the Join Question in a Real System - 2021, 168-180 стр. 10.1145/3448016.3452831.

66. . B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. Joseph, R. Katz, S. Shenker, I. Stoica. Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center NSDI 2011, 2011.

67. Yang, M. & Koziol, Quincey. Performance Comparison Study of Using Gzip and Bzip2 Data Compression Packages to NASA HDF-EOS Data and Other Scientific Data With Different Approaches. AGU Fall Meeting Abstracts, 2002.

68. Steven S. Skiena. Springer Cham. The Algorithm Design Manual, 2020. https://doi.org/10.1007/978-3-030-54256-6.

69. Bradley N. Miller, David L. Ranum. Problem Solving with Algorithms and Data Structures Using Python 2nd. Franklin, Beedle & Associates Inc., 2011, USA. ISBN:978-1-59028-257-1.

70. M. Armbrust, R. S. Xin, C. Lian, Y. Huai, D. Liu, J. K. Bradley, X. Meng, T. Kaftan, M. J. Franklin, A. Ghodsi, M. Zaharia. Spark SQL: Relational data processing in spark. // 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD'15) - Австралия, 2015, 1383-1394 стр.

Приложение

Приложение 1. Акт о внедрении.

Адрес 125167. г Москва. Ленинградский проспект, д 39. строение 79

ОГРН1027739850962 ИНН 7743001840 КПП 997750001 Тел ♦7(495)-725-63-57 ♦7 (495)-725-63-59

АКТ о внедрении

Утилита для реализации алгоритма ускорения операции соединения распределенных массивов данных по заданному критерию разработанная в рамках кандидатской работы аспиранткой Национального исследовательского университета «Высшая школа экономики» Тырышкиной Евгенией Сергеевной соответствуют всем требованиям и принята для опытной эксплуатации.

Руководитель направления разработки

Швеенков Д.Б

'Ь/лс^л. У-Л