Dryad vs RDBMS vs Hadoop
Третья статья из цикла статей «Dryad. Big Data от Microsoft»
В первых двух статьях цикла «Dryad. Big Data от Microsoft» был рассмотрен фреймворк распределенных вычислений от Microsoft – Dryad. В частности, подробно были описаны концепции и архитектура ключевых компонентов Dryad – среды исполнения Dryad и языка запросов DryadLINQ.
В третьей заключительной части цикла будет проведено сравнение фреймворка Dryad с другими MPP «инструментами» – реляционными СУБД, GPU-вычислениями и платформой Hadoop.
(Disclaimer: cравнение обсуждаемых ниже платформ/фреймворков в отрыве от контекста [т.е. конкретной задачи] не совсем корректно. Сравниваемые платформы/фреймворки имеют свою область применения, решают специфические классы задач и во многом несопоставимы друг с другом. Я принимаю это допущение только потому, что целью данного сравнения является не узнать «кто лучше», а выявить целесообразность использования Dryad через сравнение с хорошо известными инструментами разработки MPP-приложений.)
1. Dryad vs GPU. Dryad vs MPI
Являясь аспирантом и принимая во внимание наличие академической лицензии у Dryad, я заинтересовался возможностью применения фреймворка Dryad в расчетах для исследований. Но исторически сложилось, что в академической среде моего ВУЗа основными платформами для «scientific computing» являются MPI (Message Passing Interface) и GPU-вычисления.
В отличие от MPI, платформа Dryad основана на shared-nothing архитектуре, не имеющей разделяемых (различными процессами) данных и, как следствие, не нуждающаяся в использовании примитивов синхронизации. Это делает Dryad-кластер не только потенциально более масштабируемым, но и более эффективным по времени для решения задач, использующих параллельные по данным алгоритмы.
Кроме того, такие инфраструктурные задачи, как мониторинг выполнения, обработка отказов, обычно являются зоной ответственности MPI-разработчика, в то время как в Dryad перечисленные задачи входят в зону ответственности фреймворка.
Говоря о GPU-вычислениях, стоит отметить, что, в отличие от Dryad, разработка под GPU довольно сильно связана с аппаратным уровнем, на котором запускается приложение. NVidia и AMD предоставляют свои собственные SDK для разработки под свои графические карты (CUDA и APP, соответственно). Очевидно, что это различные несовместимые друг с другом платформы разработки.
Корпорация зла Microsoft предприняла попытку унифицировать процесс разработки под GPU, выпустив С++ AMP.
Но этот факт - лишнее доказательством, что разрабатывая под GPU, разработчик должен
«оглядываться» на аппаратное обеспечение графического адаптера. Причем «корни» аппаратного
уровня проникают в код настолько глубоко, что могут возникнуть сложности
запуска приложения даже при смене модели графической карты, не говоря уже про смену
вендора. Естественно, это создает дополнительные сложности как при отладке, так
и при миграции на более производительную/подходящую для конкретной задачи аппаратную платформу.
Все это, в конечном итоге, заставляет исследователя заниматься решением инфраструктурных вопросов, связанных с аппаратным обеспечением, отладкой, развертыванием и поддержкой, вместо решения прикладных вопросов предметной области исследования.
Фреймворк Dryad, в отличие от GPU, скрывает от разработчиков распределенных приложений аппаратный уровень, хотя и предъявляет довольно специфические требования к аппаратной платформе для запуска распределенного приложения (требования были рассмотрены в первой статье цикла).
2. Dryad vs Parallel DB
Основное фундаментальное отличие Dryad от СУБД – отсутствие сильной связанности между слоями хранения, слоем исполнения и программной моделью у Dryad и наличие такой связанности у СУБД. Это различие продемонстрировано на иллюстрации во введении (рис. 1).
Тем не менее Dryad «впитал» в себя многие идеи мира как традиционных, так и параллельных СУБД.
Так, как и многие параллельные СУБД (Teradata, IBM DB2 Parallel Edition), Dryad использует shared-nothing архитектуру, шардинг (горизонтальное партицирование), динамическое репартицирование, стратегии партицирования: hash-partitioning, range partitioning и round-robin.
Из мира традиционных СУБД, были взяты концепции оптимизатора запросов и плана исполнения. Эти концепции крайне сильно трансформировались: результатом работы планировщика DryadLINQ является граф исполнения (EPG, Execution Plan Graph), изменяемый динамически на основе политик и собираемой во время исполнения статистики.
Как все СУБД, Dryad используют язык запросов к данным. В Dryad роль языка для написания
запросов исполняет программная модель DryadLINQ. Но в отличие от SQL, DryadLINQ:
+ изначально создавалась для работы со структурами данным и сложными типами;
+ является высокоуровневой абстракцией, не связывающей уровень приложения с уровнем
хранения;
+ имеет нативную поддержку общих паттернов программирования, таких как итерации;
- не поддерживает транзакции и update-операции.
Кроме того, SQL принципиально не подходит для описания алгоритмов машинного обучения, парсинга последовательностей фактов (логов, геномных баз), анализа графов. Также как Dryad неэффективен для решения задач на основе алгоритмов, требующих random-access доступа к данным.
Ниже приведена таблица сравнения решений на основе реляционных СУБД и на основе фреймворков распределенных вычислений.
В заключении сравнения отмечу: наибольшее препятствие широкого распространения решений на основе параллельных СУБД – стоимость решении, которая, в общем случае, составляет сотни тысяч долларов. Сколько бы стоило решение на основе Dryad-кластера можно только предположить; по моему мнению, речь идет у сумме на порядок ниже.
3. Dryad vs Hadoop
Парадигма map/reduce – крайне изящный способ описания алгоритмов параллельных по данным. Возникновение Hadoop, предоставившей инфраструктуру исполнения и программную модель написания map/reduce-приложений, стало революционным скачком в решении проблем Больших Данных.
* Направленный ациклический граф (англ. Directed Acyclic Graph).
** Доступна только beta-версия (на июнь 2013).
*** Любой CLS-совместимый ЯП со статической типизацией.
**** Инфраструктура для развертывания Hadoop-кластера и исполнения Hadoop-задач.
***** Доступно только при установке сторонних компонент экосистемы Hadoop
3.1. Hadoop
Идеологи и разработчики Hadoop, отбросив все лишнее, сделали простую, понятную максимальному кругу разработчиков, крайне эффективную и столь же ограниченную платформу разработки MPP-приложений.
Hadoop прекрасно подходит для map/reduce и не выдерживает никакой критики при разработке под другие распределенные алгоритмы. Отсюда и огромное количество вспомогательных инструментов Hadoop, базирующихся как на вычислительном фреймворке Hadoop MapReduce (таких как, Pig), так и представляющий отдельные вычислительные фреймворки (Hive, Storm, Apache Giraph). И все эти инструменты решают задачи прикладного характера (по сути, обхода ограничений) вместо предоставления единого универсального инструмента решения как парсинга логов, так и подсчета PageRank и анализа графов.
Естественно, установка, настройка и поддержка всей экосистемы Hadoop, необходимой для решения повседневных задач аналитики - это немалые временные и, как следствие, финансовые затраты, которые уходят на решение задач инфраструктурного характера, а не задач бизнеса/исследователя. В ответ на эту проблему появились дистрибьюторы платформы Hadoop в «собранном виде» (крупнейшие из них - Cloudera и Hortonworks). Но это все же не решение проблемы - это лишнее подтверждение ее наличия.
Эволюционным скачком станет программный фреймворк YARN, предоставляющий разработчикам компоненты и API, необходимые для разработки распределенных алгоритмов, отличных от map/reduce. YARN также решает многие проблемы Hadoop v1.0, в числе которых низкая утилизация ресурсов и порог масштабируемости, находящихся сейчас на уровне ~4K вычислительных узлов.
На май 2013 года YARN пока не в release-версии. Учитывая «неторопливость» Apache-community, необходимо принимать во внимание высокую вероятность того, что промежуток времени между выходом release-версии YARN и release-версий распределенных алгоритмов, отличных от map/reduce, написанных с использованием YARN API, может составлять года.
3.2. Dryad
Фреймворк Dryad же изначально позволял разработчикам реализовывать произвольные распределенные алгоритмы. Таким образом, программная модель Hadoop MapReduce (v1.0) - лишь частный случай более общей программной модели Dryad.
Не будем углубляться в проблемы Hadoop с операциями Join, эффективностью расчета PageRank, другие ограничения платформы Hadoop и способами их решения, так как это явно входит за рамки статьи. Вместо этого обсудим возможности фреймворка Dryad, аналогов которых нет у платформы Hadoop.
Dryad имеет внушительный список инструментов по планированию процесса выполнения распределенного приложения, описанные в предыдущих статьях цикла. Так есть параллельный компилятор, преобразующий выражения, написанные на DraydLINQ, в граф выполнения - EPG. EPG проходит стадию оптимизации как перед выполнением (статический оптимизатор), так и во время исполнения (динамическая оптимизация на основе политик и собранной во время исполнения статистики).
Параллельный компилятор, граф выполнения и возможность по статической/динамической оптимизации графа делают планирование/выполнение распределенного приложения открытым для улучшений и оптимизаций.
Концепция направленного ациклического графа позволяет решать множество проблем, связанных с отказоустойчивостью, мониторингом, планирование и управлением ресурсов, значительно более элегантными путями, чем это реализовано в Hadoop (об этом я писал в первой статье цикла).
Обработка отказов вычислительных узлов позволяет не перезапускать все стадию заново.
Обработка «медленных» вычислительных узлов позволяет не «ждать» узлам, «окончившим» работу, самый медленный узел (например, для начала фазы Reduce)
Динамическая агрегация в Dryad позволяет избежать деградации пропускной способности сети перед началом Reduce-стадии.
Еще одна интересная возможность, которой не хватает Hadoop - абстракция понятия канал. Благодаря введенной абстракции, каналом в Dryad может выступать как TCP, так и временный файл и shared memory FIFO. Что позволяет в таких алгоритмах, как расчет PageRank, осуществлять обмен данных между итерациями по каналам с низкой латентностью (например, shared memory FIFO). В то время как в Hadoop передача данных между итерациями всегда будет идти по TCP-каналам, имеющим довольно высокую латентность по сравнению с shared memory.
Источник иллюстрации [7]
Некоторые архитектурные решения Dryad (одно из них, обсуждаемое в прошлой статье, «прикрепление» метаданных к графам выполнения) и нативная поддержка фреймворком высокоуровневых ЯП со статической типизацией, позволили при разработке Dryad-приложений оперировать исключительно строго типизированными данными. В тот время как для разработчиков под Hadoop, привычной практикой является парсинг входных данных и дальнейшее (не самого безопасное) приведение к ожидаемому типу.
3.3. Практика
Ниже приведены листинги приложений, рассчитывающих среднее арифметическое, для Hadoop и Dryad.
// InitialReduce: input is a sequence of raw data tuples;
// produces a single intermediate result as output
static public class Initial extends EvalFunc<Tuple> {
@Override public void exec(Tuple input, Tuple output)
throws IOException {
try {
output.appendField(new DataAtom(sum(input)));
output.appendField(new DataAtom(count(input)));
} catch(RuntimeException t) {
throw new RuntimeException([...]);
}
}
}
// Combiner: input is a sequence of intermediate results;
// produces a single (coalesced) intermediate result
static public class Intermed extends EvalFunc<Tuple> {
@Override public void exec(Tuple input, Tuple output)
throws IOException {
combine(input.getBagField(0), output);
}
}
// FinalReduce: input is one or more intermediate results;
// produces final output of aggregation function
static public class Final extends EvalFunc<DataAtom> {
@Override public void exec(Tuple input, DataAtom output)
throws IOException {
Tuple combined = new Tuple();
if(input.getField(0) instanceof DataBag) {
combine(input.getBagField(0), combined);
} else {
throw new RuntimeException([...]);
}
double sum = combined.getAtomField(0).numval();
double count = combined.getAtomField(1).numval();
double avg = 0;
if (count > 0) {
avg = sum / count;
}
output.setValue(avg);
}
}
static protected void combine(DataBag values, Tuple output)
throws IOException {
double sum = 0;
double count = 0;
for (Iterator it = values.iterator(); it.hasNext();) {
Tuple t = (Tuple) it.next();
sum += t.getAtomField(0).numval();
count += t.getAtomField(1).numval();
}
output.appendField(new DataAtom(sum));
output.appendField(new DataAtom(count));
}
static protected long count(Tuple input)
throws IOException {
DataBag values = input.getBagField(0);
return values.size();
}
static protected double sum(Tuple input)
throws IOException {
DataBag values = input.getBagField(0);
double sum = 0;
for (Iterator it = values.iterator(); it.hasNext();) {
Tuple t = (Tuple) it.next();
sum += t.getAtomField(0).numval();
}
return sum;
}
public static IntPair InitialReduce(IEnumerable<int> g) {
return new IntPair(g.Sum(), g.Count());
}
public static IntPair Combine(IEnumerable<IntPair> g) {
return new IntPair(g.Select(x => x.first).Sum(),
g.Select(x => x.second).Sum());
}
[AssociativeDecomposable("InitialReduce", "Combine")]
public static IntPair PartialSum(IEnumerable<int> g) {
return InitialReduce(g);
}
public static double Average(IEnumerable<int> g) {
IntPair final = g.Aggregate(x => PartialSum(x));
if (final.second == 0) return 0.0;
return (double)final.first / (double)final.second;
}
3.4. Доступность для разработчиков
Dryad является довольно закрытой от профессионального сообщества проприетарной системой с туманным будущим (точнее совсем без такого). В противовес этому, Hadoop является open-source проектом с огромным community-сообществом, ясным способом лицензирования и несколькими крупными дистрибуторами (Cloudera, Hortonworks, etc.).
В заключении главы сравнения с Hadoop отмечу, что получить Hadoop-кластер в свое использование на текущем уровне развития облачных сервисов не представляет проблем: Amazon Web Services предоставляют Hadoop-кластер через свой сервис Amazon Elastic MapReduce, а облачная платформа Windows Azure – через сервис Microsoft HDInsight (я их уже упоминал выше).
С появлением связки «Hadoop + { WA | AWS }» доступность платформы Hadoop для стартапов и исследователей стала крайне высокой. О доступности Dryad говорить не приходиться: коммерческих лицензий нет, про академическое использование - почти нигде не рассказывали.
Hadoop уже дефакто стандарт для работы с Big Data. После будущего релиза YARN, я думаю, ни у кого не останется сомнений, что платформа стала этим стандартом заслужено. У Dryad же как у проекта, я думаю, есть «реинкарнации» - это Naiad (incremental Dryad); а идеи, предложенные в Dryad, наверняка, нашли своем продолжение еще не в одном проекте Microsoft Research.
Заключение
Фреймворк Dryad, имея в своей основе концепцию направленного ациклического графа, наложил на эту концепцию последние идеи мира фреймворков распределенного исполнения приложений, традиционных и параллельных СУБД. Разделение ответственностей, связанных со средой исполнения, распределенным хранилищем и программной моделью, между отдельными модулями позволило Dryad остаться крайне гибкой системой; а тесная интеграции с существующим программным стеком для .NET-разработчиков (.NET Framework, C#, Visual Studio) существенно снижает время, необходимое для начала работы с фреймворком.
Простая и изящная концепция, инновационные идеи, прекрасная архитектора и знакомый стек технологий делают Dryad эффективным инструментом для работы с Big Data. Более эффективным, чем аппаратно-привязанные GPU-вычисления; плохо масштабируемые решения на основе традиционных СУБД; дорогие и ограниченные примитивностью языка SQL решения на основе параллельных СУБД. Dryad превосходит «зацикленный» на модели map/reduce Hadoop, страдающий до появления YARN, то от единичных точек отказа, то от низкой утилизации ресурсов, то элементарно от инертности собственного сообщества.
В то же время все очевидные достоинства Dryad с легкость нивелируются природой этого продукта – это проприетарный продукт Microsoft для внутреннего пользования, судьбу которого Microsoft решает единолично.
Dryad – это новый взгляд, это новое виденье на системы распределенного выполнения приложений. И этот взгляд совсем не похож на Hadoop. Он шире. Настолько, что просто включает программную модель map/reduce, как одно из многих своих состояний. Процесс изучения внутренних принципов платформы Dryad и идей, заложенных в эти принципы, был, пожалуй, самым интересным ИТ-занятием за этого год.
Список источников
- [1] Y. Yu, P. K. Gunda, M. Isard. Distributed Aggregation for Data-Parallel Computing: Interfaces and Implementations, 2009.
- [2] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: Distributed data-parallel programs from sequential building blocks. In Proceedings of European Conference on Computer Systems (EuroSys), 2007.
- [3] Tom White. Hadoop: The Definitive Guide, 3rd Edition. O'Reilly Media / Yahoo Press, 2012.
- [4] Arun C Murthy. The Next Generation of Apache Hadoop MapReduce. Yahoo, 2011.
- [5] D. DeWitt and J. Gray. Parallel database systems: The future of high performance database processing. Communications of the ACM, 36(6), 1992.
- [6] David Tarditi, Sidd Puri, and Jose Oglesby. Accelerator: using data-parallelism to program GPUs for general-purpose uses. In International Conference on Architectural Support for Programming Languages and Operating Systems ASPLOS), Boston, MA, October 2006.
- [7] Jinyang Li. Dryad / DryadLINQ Slides adapted from those of Yuan Yu and Michael Isard, 2009.
