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

Эндрю Павло, Эрик Паулсон, Александр Разин, Дэниэль Абади, Дэвид Девитт, Сэмюэль Мэдден, Майкл Стоунбрейкер
Пересказ: Сергей Кузнецов
Оригинал: 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

Содержание

Предисловие переводчика

Аннотация

1. Введение

2. Два подхода к крупномасштабному анализу данных

2.1. MapReduce

2.2. Параллельные СУБД

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

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

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

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

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

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

3.6. Гибкость

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

4. Тесты для оценки производительности

4.1. Тестовая среда

4.2. Исходная MR-задача

4.3. Аналитические задачи

5. Обсуждение

5.1. Аспекты системного уровня

5.2. Аспекты пользовательского уровня

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

7. Благодарности

8. Литература

Предисловие переводчика

Молодежи свойственно увлекаться новыми идеями. Идея MapReduce, выдвинутая и реализованная сначала Google, а потом и сообществом open source в проекте Hadoop почти мгновенно овладела молодыми массами. Причем даже теми представителями компьютерной молодежи, которые получили хорошее образование и последующий практический опыт в области систем управления базами данных. Мне неоднократно приходилось слышать от молодых коллег, что они считают достоинствами MapReduce отсутствие схемы данных (в том числе, и отсутствие поддержки типов данных) и даже потребность в явном программировании конструкций, которые испокон веков поддерживались в СУБД на уровне высокоуровневых языковых конструкций языка SQL. Понятно, что дополнительным стимулом к применению MapReduce была привязка этой технологии к «облачным» вычислениям, возможность практически бесплатно арендовать виртуальный кластер с большим числом узлов и развернуть на нем свою MapReduce программу, почти автоматически достигнув громадной производительности своего приложения.

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

И вот, наконец, ворчание стариков (а больше других ворчали Майкл Стоунбрейкер и Дэвид Девитт) выразилось в инициировании ими чрезвычайно интересного проекта по практическому сравнению технологии MapReduce с технологиями параллельных СУБД категории sharing nothing. Результатам этого проекта и посвящается статья, пересказ которой предлагается вашему вниманию.

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

Финал статьи написан очень мирно, типа «ребята, давайте жить дружно». Другими словами, не отрицайте достижений технологии баз данных, а старайтесь использовать эти достижения в новых технологиях. А сообщество баз данных постарается, в свою очередь, перенять те аспекты технологии MapReduce, которых не достает в современных СУБД.

Статья информативна и увлекательна. Желаю вам приятного чтения.

Сергей Кузнецов

Аннотация

В настоящее время наблюдается значительный энтузиазм вокруг парадигмы MapReduce (MR) для крупномасштабного анализа данных [17]. Хотя основной поток управления этой инфраструктуры поддерживается в параллельных SQL-ориентированных системах управления базами данных (СУБД) уже более 20 лет, некоторые называют MR кардинально новой вычислительной моделью [8, 17]. В этой статье описываются и сравниваются обе парадигмы. Кроме того, для обоих видов систем оценивается производительность и сложность разработки. Для этого определяется эталонный тестовый набор, включающий коллекцию задач, которые пропускались на варианте MR с открытыми кодами и на двух параллельных СУБД. Для каждой задачи на кластере из 100 узлов измеряется производительность для разных уровней распараллеливания. Результаты демонстрируют некоторые интересные соотношения. Хотя процесс загрузки данных и настройки выполнения параллельных СУБД длился гораздо дольше, чем для системы MR, наблюдавшаяся производительность этих СУБД была поразительно более высокой. Приводятся соображения о причинах этой значительной разницы в производительности, и рассматриваются реализационные методы, которые следует позаимствовать в будущих системах из обоих видов архитектур.

1. Введение

В последнее время специализированные издания переполнены новостями о революции «кластерных вычислений». Эта парадигма состоит в использовании большого числа (низкопроизводительных) процессоров, работающих в параллель для решения вычислительной проблемы. По существу, предлагается построение центра данных путем объединения большого числа низкопроизводительных серверов вместо использования меньшего числа высокопроизводительных серверов. Рост интереса к кластерам способствует распространению средств их программирования. Одним из первых и наиболее известных подобных средств является MapReduce (MR) [8]. Подход MapReduce привлекателен тем, что обеспечивает простую модель, на основе которой пользователи могут выражать сравнительно сложные распределенные программы, что порождает значительные интерес в образовательном сообществе. Например, IBM и Google обнародовали планы по обеспечению доступности 1000-процессорного кластера MapReduce для обучения студентов распределенному программированию.

При наличии этого интереса к MapReduce естественно задать вопрос: «А почему бы вместо этого не использовать какую-нибудь параллельную СУБД?». Параллельные системы баз данных (которые все основаны на общих архитектурных принципах) коммерчески доступны уже почти двадцать лет, и на рынке их около десятка, включая Teradata, Aster Data, Netezza, DATAllegro (и, следовательно, вскоре Microsoft SQL Server через посредство проекта Madison), Dataupia, Vertica, ParAccel, Neoview, Greenplum, DB2 (посредством Database Partitioning Feature) и Oracle (посредством Exadata). Это надежные, высокопроизводительные вычислительные платформы. Подобно MapReduce, они обеспечивают среду высокоуровневого программирования и полную распараллеливаемость. Хотя может показаться, что MR и параллельные системы баз данных нацелены на разную публику, на самом деле, можно написать почти любую задачу параллельной обработки либо в виде некоторого набора запросов к базе данных (возможно, с использованием определяемых пользователями функций и агрегатов для фильтрации и комбинирования данных), либо в виде набора заданий MapReduce.

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

Цель статьи состоит в том, чтобы проанализировать эти отличия и их последствия. Второй раздел статьи начинается с краткого обзора этих двух альтернативных классов систем, после чего в разделе 3 обсуждается их архитектурные особенности. Затем в разделе 4 описывается эталонный тестовый набор, состоящий из разнообразных задач, одна из которых взята из статьи про MR [8], а прочие являются более трудными. Кроме того, приводятся результаты прогонов этого тестового набора на 100-узловом кластере. В испытаниях участвовали публично доступная версия MapReduce с открытыми кодами Hadoop [1], а также две параллельных SQL-ориентированных СУБД – Vertica [3] и система одного из основных поставщиков реляционных СУБД. Также приводятся данные о временных затратах на загрузку и проверку данных, и неформально описываются процедуры, потребовавшиеся для установки и настройки программного обеспечения для каждой задачи.

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

Некоторые читатели могут счесть, что эксперименты, проводимые с использованием 100 узлов, не являются интересными или представительными с точки зрения реальных систем обработки данных. Авторы не согласны с этим предположением в двух отношениях. Во-первых, как демонстрируется в разд. 4, на 100 узлах две параллельные СУБД справляются с разными аналитическими задачами в 3,1-6,5 раз быстрее, чем MapReduce. Хотя, конечно, MR может масштабироваться до тысяч узлов, из-за исключительной эффективности современных СУБД такая массивная аппаратура не требуется даже при наличии наборов данных в 1-2 петабайта (1000 узлов с двухтерабайтной дисковой памятью на узел обладают общей дисковой емкостью в 2 петабайта). Например, в конфигурации Teradata в eBay используются всего 72 узла (в каждом узле два четырехъядерных процессора, 32 гигабайта основной памяти и 104 300-гигабайтных диска) для управления реляционными данными объемом около 2,4 петабайт. В качестве другого примера, хранилище данных Fox Interactive Media реализуется с использованием СУБД Greenplum на 40 узлах. Каждый узел представляет собой машину Sun X4500 с двумя двухъядерными процессорами, дисками общей емкостью в 48500 гигабайт и 16 гигабайтами основной памяти (1 петабайт общей дисковой памяти) [7]. Поскольку петабайтного размера в мире достигают лишь немногие наборы данных, совсем непонятно, скольким пользователям MR на самом деле требуется 1000 узлов.

2. Два подхода к крупномасштабному анализу данных

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

2.1. MapReduce

Одним из привлекательных качеств модели программирования MapReduce является ее простота: MR-программа состоит всего из двух функций, называемых Map и Reduce, которые пишутся пользователем для обработки пар элементов данных «ключ/значение». Входные данные хранятся в наборе разделов в распределенной файловой системе, развернутой в каждом узле кластера. Затем программа вводится в инфраструктуру распределенной обработки и выполняется так, как описывается ниже.

Функция Map читает некоторый набор «записей» из входного файла, производит любые требуемые фильтрации и/или трансформации и выводит некоторый набор промежуточных записей в форме новых пар «ключ/значение». По мере того как функция Map производит эти выходные записи, функция «расщепления» (split) разделяет их на R непересекающихся бакетов, применяя некоторую функцию к значению ключа каждой записи. Эта функция расщепления обычно является хэш-функцией, хотя можно использовать любую детерминированную функцию. Каждый сформированный бакет записывается на локальный диск обрабатывающего узла. Функция Map завершается, произведя R выходных файлов, по одному на каждый бакет.

В общем случае имеется несколько экземпляров функции Map, выполняющихся в разных узлах вычислительного кластера. Термин экземпляр (instance) здесь означает индивидуальный выполняемый вызов либо функции Map, либо функции Reduce. Каждому экземпляру Map планировщиком MR назначается для обработки отдельная часть входного файла. Если имеется M таких отдельных частей, то каждая из M задач Map образует R файлов в дисковой памяти, т.е. всего образуется M × R файлов F_ij, 1 ≤ i ≤ M, 1 ≤ j ≤ R. Ключевое наблюдение состоит в том, что во всех экземплярах Map используется одна и та же хэш-функция. Поэтому все эти экземпляры сохранят все выходные записи с одним и тем же значение хэш-функции в результирующем файле с одним и тем же номером.

На второй фазе MR-программа выполняет R экземпляров функции Reduce, где R обычно – это число узлов. Входные данные каждого экземпляра Reduce R_j состоят из файлов F_ij, 1 ≤ i ≤ M. Эти файлы передаются по сети с локальных дисков узлов Map. Снова заметим, что все выходные записи фазы Map с одним и тем же значением хэш-функции попадают в один и тот же экземпляр Reduce независимо от того, какой экземпляр Map произвел эти данные. Каждый экземпляр Reduce обрабатывает или комбинирует назначенные ему записи и затем пишет записи в выходной файл (в распределенной файловой системе), образующий часть окончательного вывода данного вычисления.

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

2.2. Параллельные СУБД

Системы баз данных, способные функционировать в кластерах узлов без общих ресурсов, существуют с конца 1980-х. Все эти системы поддерживают стандартные реляционные таблицы и SQL, и, таким образом, тот факт, что данные хранятся в нескольких машинах, является прозрачным для конечного пользователя. Многие из этих систем основывались на пионерских исследовательских результатах, полученных при выполнении проектов параллельных СУБД Gamma [10] и Grace [11]. Возможность параллельного исполнения обеспечивается двумя ключевыми аспектами: (1) почти все (или даже все) таблицы разделяются по узлам кластера, и (2) в системе используется оптимизатор, транслирующий команды SQL в план запроса, выполнение которого распределяется по нескольким узлам. Поскольку от программистов требуется только указание своей цели на высокоуровневом языке, они не обременяются деталями уровня хранения данных, такими как варианты индексации или стратегии выполнения соединений.

Рассмотрим SQL-команду для фильтрации записей таблицы T₁ по некоторому предикату, ее соединения со второй таблицей T₂ и вычисления агрегата на результате соединения. Основная схема обработки этой команды на параллельной СУБД включает три фазы. Поскольку таблица T₁ хранится в базе данных, уже разделенная по некоторому атрибуту в некотором наборе узлов, сначала в этих узлах параллельно выполняется подзапрос фильтрации аналогично тому, как выполняется фильтрация в функции Map. Далее, в зависимости от размера таблиц применяется один из двух распространенных параллельных алгоритмов соединения. Например, если в таблице T₂ содержится небольшое число записей, СУБД могла бы реплицировать ее по всем узлам при начальной загрузке данных. Это позволяет параллельно выполнять соединение во всех узлах. После этого в каждом узле вычисляется агрегат с использованием своей части результата соединения. И, наконец, для вычисления окончательного результата по этим частичным агрегатам требуется завершающий шаг «свертки» (roll-up) [9].

Если таблица T₂ имеет большой размер, то ее содержимое будет распределено между несколькими узлами. Если эти таблицы разделены не по тем атрибутам, которые используются в соединении, система будет должна выполнить хэширование как T₂, так и отфильтрованного варианта T₁ с использованием некоторой общей хэш-функции. Перераспределение по узлам T₂ и отфильтрованного варианта T₁ аналогично обработке, которая происходит после завершения функции Map и до начала выполнения Reduce. Как только в каждом узле будут иметься необходимые данные, в них будут выполнены соединение с хэшированием и предварительное вычисление агрегатной функции. На последнем шаге опять потребуется произвести вычисление свертки для получения окончательного результата.

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

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