ЗАНИМАТЕЛЬНАЯ BIG DATA. ПАРАЛЛЕЛЬНЫЕ И РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ В КАРТИНКАХ
АЛЕКСЕЙ ДРАЛЬ
ГЕНЕРАЛЬНЫЙ ДИРЕКТОР BIG DATA TEAM
ОСТРОВ 10-21. ВЛАДИВОСТОК, ОСТРОВ РУССКИЙ
ОБРАЗОВАТЕЛЬНЫЙ ИНТЕНСИВ ДЛЯ ТЕХНОЛОГИЧЕСКИХ ЛИДЕРОВ
Термины Big Data (большие данные) и Data Science (анализ данных) активно употребляются с 2000-х гг. Вы хотите понять, что они значат? Понять, о чем разговаривают люди на конференциях, по телевидению? Или даже решить, какую технологию Big Data использовать на производстве? Данный лонгрид поможет ответить на эти вопросы, а техническим и ИТ-специалистам позволит понять, в каком направлении можно развиваться дальше.
Как я уже рассказал в видео, в многопроцессорных вычислительных системах хорошо выделяются три основных направления: параллельные вычисления, распределенные вычисления, грид-вычисления. Давайте обсудим каждое из них более подробно.
Параллельные вычисления
Вы когда-нибудь слышали про игру «Жизнь» (она же клеточный автомат английского математика Конвея)? Если нет, то обязательно посмотрите видео на youtube (например, это), чтобы восхититься узорами. Правила игры очень простые:
1
Мы берем бесконечную плоскость, разделенную на клетки (как тетрадка в клеточку)
2
В каких-то клетках есть жизнь (начальная конфигурация системы)
3
На каждом следующем шаге эволюции жизнь в каждой клетке зарождается или умирает (в зависимости от «качества жизни» в соседних 8-ми клетках). Если соседей 2 или 3, живая клетка выживает, если нет — умирает (от «одиночества» или «перенаселенности»). Если у мертвой клетки ровно 3 соседа, она рождается
Ваша задача — произвести вычисления (обновление шага эволюции «вселенной») максимально быстро. Для каждой клетки нужно посмотреть на окружение, сделать простейшие вычисления (порядка десятка операций сложения и сравнения) и дать ответ. Если у нас поле 1000 × 10 000 (т. е. 10 млн клеток), то компьютеру нужно будет произвести 100 млн операций, что можно легко сделать за 1 секунду на одном ядре процессора современного ноутбука. А если наша вселенная состоит 100 000 × 100 000 клеток? Тогда, чтобы насладиться игрой, без силы параллелизма вычислений нам не обойтись. Делается это очень легко: мы просто делим нашу вселенную на части (с небольшим нахлестом, чтобы для каждой клетки можно было получить окружение) и каждую часть вселенной обсчитываем отдельным ядром (CPU core). Чем больше ядер, тем быстрее будут вычисления? Да, но есть нюанс. С добавлением одного ядра в систему, где раньше было только одно вычислительное ядро, система не будет работать в 2 раза быстрее. Нам необходимо передавать данные между ядрами после каждого шага эволюции (помните про «нахлест» по клеткам?). В общем случае этот нюанс называется Законом Амдала (см. Википедию, 1967 год).

По горизонтальной оси графика отложено число вычислительных ядер в системе. По вертикальной — ускорение вычислений. Разными цветовым линиями показаны графики с разным объемом «параллелизуемой» составляющей вычислений. Какой кривой лучше всего описывается наш подход к распараллеливанию игры «Жизнь» (зеленой, фиолетовой, красной или синей)?
В частном случае, если 50 % времени в вашей программе будут передаваться данные по сети (например, из одного датацентра в другой), то вы никогда не сможете получите ускорения вычислений более чем в 2 раза, сколько бы вычислительных ядер вы бы ни добавили в систему.
В современном мире выделяются два основных технологических инструмента для распараллеливания вычислений (суперкомпьютерные вычисления). Если мы говорим про много вычислительных ядер в рамках одного компьютера (система с общей памятью), то ускорять вычисления поможет OpenMP (появился в 1997 году). Если у вас под рукой вычислительный кластер из производительных машин, соединенных высокоскоростной сетью (типа InfiniBand, см. Википедию), то вам однозначно нужно познакомиться с MPI (этот протокол зародился еще в 1991 году, см. Википедию).
Где можно познакомиться с MPI?
Автору этой статьи довелось учиться на мехмате МГУ, там ежики плакали и кололись, но продолжали есть кактус студенты упорно продолжают обращать большие матрицы с помощью MPI на вычислительном кластере Ломоносов. Где же это может пригодиться? Да на самом деле почти любая математическая задача (будь то прогнозирование спроса на товары в магазине, загруженность дорог, построение персонализированных рекомендаций фильмов) явно или неявно подразумевает под собой решение таких подзадач (см. курсы линейной алгебры). Но в большей степени такие кластеры используются в задачах «математического моделирования». Примеры направлений исследований можно посмотреть здесь.
А для привлечения внимания оставлю красивые картинки из области моделирования акустических систем. Источник
Кстати, а знаете ли вы, у кого самый большой суперкомпьютер? Чтобы найти ответ на этот вопрос можно воспользоваться международным рейтингом суперкомпьютеров TOP500. Lomonosov-2 (тот самый, про который я писал выше) — самый производительный суперкомпьютер на территории СНГ. Он находится на 72-й позиции в мировом рейтинге (а полтора года назад занимал 52-е место). Как видим, гонка вооружений вычислений идет полным ходом. А началась история суперкомпьютеров с разработки Cray-1 (см. Википедию, 1975–1976 гг.). Вся разработка обошлась в 8 миллионов долларов, а спустя 30–40 лет любой персональный компьютер за $ 1000 будет мощнее первых суперкомпьютеров.
Еще одна важная веха в развитии суперкомпьютеров была зафиксирована в 1984 году, когда советский ученый Карцев Михаил Александрович смог изобрести первый суперкомпьютер, который прошел рубеж производительности в 1 Гигафлопс (1 миллиард операций с действительными числами в секунду). Это был суперкомпьютер M-13 с пиковой мощностью в 2.4 Гигафлопс. К сожалению, про это мало что написано в русскоязычных источниках, но по крайней мере есть отсылки в английской Википедии. Если есть желание погрузиться в историю советских компьютеров, то я советую начать с известного акронима БЭСМ (Большая Электронная Счетная Машина) отсюда. Но это уже совсем другая история, а нам пора переходить к распределенным вычислениям.
Материалы для самостоятельного изучения и полезные ссылки
Страница на Википедии про параллельные вычисления
Страница на Википедии про суперкомпьютер
Экскурсии в суперкомпьютерный комплекс для школьников
Распределенные вычисления
Когда люди говорят про Big Data (или большие данные), они почти почти наверняка имеют в виду распределенные вычисления, Hadoop/Spark стек технологий. Это мое любимое направление, поэтому, чтобы рассказать про то, каким образом строится Big Data экосистема, я записал для вас еще одно видео для лучшего погружения:
И насколько же большой весь зоопарк технологий? Если на видео вы можете насчитать десяток технологий, то на официальном сайте Apache можно сосчитать порядка 350 проектов. Конечно, не все проекты Apache относятся к обработке больших объемов данных, но довольная большая часть из них (50 проектов) относится и самые популярные опенсорсные инструменты / платформы развиваются именно под эгидой Apache (см. Hadoop, Spark, и т. д.). Почему я назвал это зоопарком? Да вы просто посмотрите на эмблемы проектов:
Вот вам и первая загадка: за что отвечает в Big Data экосистеме довольный поросенок с эмблемы в первом ряду? А вот вам и менее дружелюбные на вид (но производительные по сути) слоники:
Но, спасибо разработчикам всей этой большой экосистемы, у нас есть хранитель/управляющий зоопарка (Zookeeper). Apache Zookeeper — это распределенная база данных, которая позволяет всем обитателям зоопарка синхронизироваться между собой. Почему была выбрана именно эта распределенная база данных и какой выбор стоял перед разработчиками, поможет понять следующее видео.
CAP-теорема
Интересно? Больше о CAP-теореме, FLP-теореме можно будет узнать из следующего раздела про грид-вычисления, а мы вернемся к вопросу о точке приложения распределенных вычислений. Какие же компании их используют и для чего? Рассадником распределенных вычислений послужили ИТ-компании с большим охватом аудитории. Это:
Google, которому нужно было хранить весь интернет, в 2003 году (см. статью) изобрел распределенную файловую систему Google File System для хранения большого объема данных на дешевых серверах (дешевые по сравнению с HPC суперкомпьютерами из предыдущего раздела). Они же изобрели известную парадигму вычислений MapReduce (см. статью 2004 года). MapReduce появился в связи с тем, что данные недостаточно просто хранить, из них нужно извлекать полезную информацию (на каких страницах в интернете хранятся самые смешные фотографии котиков, чтобы показать пользователю и т. п.)
Yahoo, который послужил драйвером развития опенсорс-технологий. В свое время известный поисковик и почтовый сервис, который передал пальму лидерства Google. Благодаря поддержке Yahoo появились реализации HDFS (Hadoop Distributed File System, опенсорс реализация GFS) и Hadoop MapReduce (опенсорс реализация Google MapReduce). Большой человеческий поклон им за то, что любой желающий может скачать дистрибутив, легко и совершенно бесплатно установить на свой компьютер для экспериментов или на кластер для боевого использования
Facebook, который придумал Hive, — SQL поверх больших данных, поколоночное хранение данных в HDFS — см. RCFile и ORC (последнее — уже совместная работа с Hortonworks). Социальных данных для анализа в Facebook настолько много, что писать каждый раз MapReduce-задачу было бы большим издевательством над людьми (точнее, разработчиками, которых всегда не хватает). Теперь писать запросы к Big Data может любой желающий, знакомый с SQL-интерфейсом. Но чтобы писать эффективные запросы, все равно придется потратить полгода на обучение и работу над реальными проектам
Ученые из Berkley и Microsoft вложили много усилий в исследования эффективной обработки данных в оперативной (распределенной) памяти компьютеров. Таким образом, получился Apache Spark, который стоит на вооружении практически любой компании, занимающейся обработкой данных
Мне довелось видеть и слышать про эффективное использование Big Data экосистемы в таких компаниях, как Рамблер (прогнозирование интересов пользователей), Яндекс (построение рекомендательной системы), Mail.ru, Amazon AWS, Nvidia, Мегафон, Сбербанк, даже внутри госучреждений (поиск мошенников) и в промышленном секторе (оптимизация выплавки стали). Сейчас, скорее, сложно придумать задачу, которую нельзя было бы решить с помощью этого стека технологий.
Материалы для самостоятельного изучения и полезные ссылки
Вводный курс про работу с распределенной файловой системой HDFS, фреймворком для вычислений Hadoop MapReduce и Apache Spark
Курс для практиков с хорошим погружением в оптимизацию вычислений Hive, Spark (оптимизация запросов), решение графовых задач с помощью Spark GraphFrames
Курс для тех, кто хочет предсказывать будущее на кофейной гуще на основе анализа большого массива данных (подходит как для роли Data Engineer, так и для роли Data Scientist)
грид-вычисления
Ну, вот и последний раздел.
Я не буду вас больше мучать погружением в математику, а дам парочку интересных ссылок:
Очень хороший рассказ про системы распределенного реестра. Там у вас будет и задача Византийских генералов, и FLP- и CAP-теорема, и практические применения на базе BlockChain-технологии. Мне незачем копировать эту информацию здесь. Спасибо автору за материалы
Для тех, кому интересно погрузиться в Data Science (а не инженерную) сторону вещей в парадигме византийских узлов и соединений, я советую познакомиться с таким направлением, как Federated Machine Learning. Это направление появилось совсем недавно, и в 2017 году компания Google опубликовала интересную работу
На этом все, спасибо что дочитали до конца, еще увидимся на просторах интернета
Кому понравилось и хочется еще, заходите в нашу группу BigData Team на Facebook
Личная страница Алексея Драля
Что такое классификация Флинна? Приведите основные методы организации параллельной обработки данных в архитектуре современных вычислительных систем.
Любители математики могут пощекотать свой мозг воспоминаниями усиленного закона больших чисел (УЗБЧ), где этот термин используется в прямом смысле (см. Википедию)
Домашняя работа по этому блоку
Задачи со звездочкой для самостоятельного погружения в распределенные файловые системы (автор вопросов - Антон Горохов):

На работе Вас обрадовали, что ночью сгорели 2 сервера: NameNode и DataNode. Ваша реакция:
– ничего страшного, везде репликация степени 3;
– ничего страшного, функцию Namenode возьмет на себя другая машина спустя какое-то время
все пропало!

При закупке оборудования для HDFS эффективный менеджер проекта интересуется, насколько хорошие (т. е. дорогие) сервера надо покупать. Ваш выбор:
– покупаем дешёвое, HDFS устойчива к отказам
– 1-2 сервера хороших, остальные попроще
– все хорошие, нам нужна устойчивая система .

Говорят, что «HDFS учитывает топологию сети». Как это?
#параллельныевычисления #parallelcomputing #распределенныевычисления #distribuedcomputing #gridcomputing #hadoop #spark #blockchain #scaleup #scaledown #вертикальноемасштабирование #verticalscaling #горизонтальноеgfs #hdfs #многопроцессорныевычислительныесистемы #классификациясистем #multiprocesscomputationalsystems #scaling #bigdata #большиеданные
Больше лонгридов и заданий доступны при записи на курс