Сравнение подходов к крупномасштабному анализу данных

Эндрю Павло, Эрик Паулсон, Александр Разин, Дэниэль Абади, Дэвид Девитт, Сэмюэль Мэдден, Майкл Стоунбрейкер
Пересказ: Сергей Кузнецов
Оригинал: Andrew Pavlo, Erik Paulson, Alexander Rasin, Daniel J. Abadi, David J. DeWitt, Samuel Madden, Michael Stonebraker. A Comparison of Approaches to Large-Scale Data Analysis. Proceedings of the 35th SIGMOD International Conference on Management of Data, 2009, Providence, Rhode Island, USA

Назад Содержание Вперёд

3. Архитектурные элементы

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

3.1. Поддержка схемы

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

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

Какая бы структура не существовала во вводных файлах MR, она должна быть встроена в программы Map и Reduce. В существующих реализациях MR поддерживается встроенная функциональная возможность манипулирования простыми форматами «ключ/значение», но программисты вынуждены писать явный код для поддержки более сложных структур данных, например, составных ключей. Возможно, этот подход является приемлемым, если набор данных MR не используется в нескольких приложениях. Однако если такое совместное использование данных имеет место, второму программисту придется разбираться в коде, написанном первым программистом, чтобы понять, как следует обрабатывать вводной файл. Во всех SQL-ориентированных СУБД используется более правильный подход, при котором схема отделяется от приложения и хранится в системных каталогах, к которым можно адресовать запросы.

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

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

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

3.2. Индексация

Во всех современных СУБД для убыстрения доступа к данным используются индексы на основе хэширования или B-деревьев. Если ищется некоторое подмножество записей (например, записи служащих, получающих зарплату больше $100000), то использование подходящего индекса сокращает область поиска. Кроме того, в большинстве систем баз данных для одной таблицы поддерживается несколько индексов. Таким образом, оптимизатор запросов может принять решение о том, какой индекс следует использовать для выполнения данного запроса, или же предпочесть произвести для этого простой последовательный поиск.

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

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

3.3. Модель программирования

В течение 1970-х в исследовательском сообществе баз данных велись бурные дебаты между сторонниками реляционного подхода и приверженцами Codasyl [18]. Основным предметом спора было то, как следует писать программу для доступа к данным в СУБД:

1. формулируя свою потребность, а не представляя алгоритм ее удовлетворения (реляционный подход), или
2. представляя алгоритм доступа к данным.

В конце концов, победила первая точка зрения, и прошедшие 30 лет доказали значимость реляционных систем баз данных. Программы на языках высокого уровня, таких как SQL, проще писать, проще изменять и проще понимать новому человеку. Codasyl критиковался за то, что в этом подходе предлагался «язык ассемблера для доступа к базам данных». MR-программирование в чем-то аналогично Codasyl-программированию: человека вынуждают писать алгоритмы на языке низкого уровня для выполнения манипуляций над записями. С другой стороны, для многих людей, привыкших к программированию на процедурных языках, таких как C/C++ или Java, описание задач на декларативном языке, подобном SQL, может быть затруднительно.

По сведениям из сообщества MR, в нем широко распространено совместное использование фрагментов кода MR, предназначенных для выполнения часто встречающихся задач, таких как соединение наборов данных. Для облегчения ноши повторной реализации повторяющихся задач сообщество MR переходит к использованию высокоуровневых языков, реализуемых на основе текущего интерфейса, чтобы перенести эти функциональные средства в систему поддержки времени выполнения. В этом направлении примечательными проектами являются Pig [15] и Hive [2].

3.4. Распределение данных

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

За исключением начального планирования расположения экземпляров Map, MR-программист должен выполнять эти задачи вручную. Например, предположим, что пользователь пишет MR-программу из двух частей для обработки набора документов. Сначала функция Map сканирует документы и создает гистограмму часто встречающихся слов. Затем эти документы передаются функции Reduce, которая группирует файлы по именам сайтов, откуда они происходят. Теперь этот или другой пользователь хочет на основе этой работы найти сайты, содержащие документы с более чем пятью вхождениями слов «Google» или «IBM». При наивной реализации этого запроса, в которой Map выполняется над собранной статистикой, фильтрация выполняется после того, как статистика подсчитана для всех документов и передана обработчикам Reduce, даже если заданному условию удовлетворяет только небольшая часть документов.

Аналогичное вычисление производят следующие представление и оператор выборки на языке SQL:

CREATE VIEW Keywords AS
SELECT siteid, docid, word, COUNT(*) AS wordcount
     FROM Documents
  GROUP BY siteid, docid, word;

SELECT DISTINCT siteid
     FROM Keywords
WHERE (word = ‘IBM’ OR word = ‘Google’) AND wordcount > 5;

В современных СУБД второй запрос был бы переписан таким образом, чтобы в разделе FROM ссылка на таблицу Keywords была заменена определением представления. После этого оптимизатор может выбрать план выполнения запроса, в котором раздел WHERE запроса будет применяться к таблице Documents до вычисления COUNT, что позволит существенно сократить объем вычислений. Если документы распределены по нескольким узлам, то этот фильтр можно применить на каждом узле до группирования документов по сайтам, к которым они относятся, что существенно уменьшит объем данных, передаваемых по сети.

3.5. Стратегия выполнения

Потенциально серьезная проблема производительности MR связана с управлением передачей данных от заданий Map к заданиям Reduce. Напомним, что каждый из N экземпляров MAP производит M выходных файлов, каждый из которых предназначен для соответствующего отдельного экземпляра Reduce. Эти файлы записываются на локальные диски в узлах, в которых выполняется каждый экземпляр Map. Если N = 1000, а M = 500, то на фазе Map данной программы будет произведено 500000 локальных файлов. Когда начинается фаза Reduce, каждому из 500 экземпляров Reduce требуется прочитать свою тысячу входных файлов, и при этом необходимо использовать протокол передачи файлов для «вытаскивания» (pull) каждого из своих входных файлов из узлов, на которых выполнялись экземпляры Map. При наличии сотен одновременно выполняющихся экземпляров Reduce неизбежно два или большее число этих экземпляров будут пытаться одновременно прочитать свои входные файлы с одного и того же узла Map, что приведет к большому числу подводов головок и замедлит скорость чтения данных с диска. Именно поэтому в параллельных системах баз данных разделенные файлы не материализуются, и вместо подхода «вытаскивания» для передачи данных используется подход «проталкивания» (push).

3.6. Гибкость

Несмотря на широкое распространение языка SQL, его регулярно ругают за недостаточно удобные выразительные средства. Некоторые люди считают, что в 1970-х сообщество баз данных допустило ошибку, сфокусировавшись на подъязыках данных, которые можно было бы встраивать в любой язык программирования, вместо того чтобы постараться добавить ко всем языкам высокоуровневые средства доступа к данным. К счастью, разработчики новых сред разработки приложений, таких как Ruby on Rails [21] и LINQ [14], начинают изменять эту ситуацию, используя новые функциональные возможности языков программирования для реализации некоторого паттерна объектно-реляционного отображения. Эти среды программирования позволяют разработчикам извлекать пользу от надежных технологий СУБД, не обременяя себя написанием сложных выражений на SQL.

Сторонники MR утверждают, что SQL не обеспечивает универсальности, свойственной MR. Но почти во всех основных СУБД (коммерческих и категории open-source) теперь обеспечивается поддержка в SQL определяемых пользователями функций, хранимых процедур и определяемых пользователями агрегатов. Все это не обладает универсальностью MR, но способствует повышению уровня гибкости систем баз данных.

3.7. Отказоустойчивость

В средах MR поддерживается более сложная модель обработки сбойных ситуаций, чем в параллельных СУБД. Хотя в обоих классах систем используется некоторая форма репликации для обработки отказов дисков, в подходе MR используются гораздо более искушенные методы обработки отказов узлов при выполнении MR-вычислений. Если в системе MR из-за отказа узла не удается выполнить некоторую единицу работы (т.е. обработку блока данных), то планировщик MR может автоматически перезапустить эту задачу в резервном узле. Эта гибкость частично следует из того, что выводные файлы фазы Map локально материализуются, а не передаются в узлы, выполняющие задачи Reduce, в потоковом режиме. Аналогично, в конвейерах заданий MR, один из которых описывается в п. 4.3.4, промежуточные результаты на каждом шаге материализуются в файлы. Это отличается от подхода параллельных СУБД, в которых в сбойных ситуациях перезапускаются более крупные единицы работы (т.е. транзакции). Этот подход частично обосновывается тем, что СУБД по мере возможности избегают сохранения на диске промежуточных результатов. Поэтому, если во время выполнения какого-либо сложного запроса происходит отказ какого-либо одного узла, то необходимо повторить выполнение всего запроса целиком.

Назад Содержание Вперёд