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

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

Администратор

Группа: Главные администраторы
Сообщений: 14349
Регистрация: 12.10.2007
Из: Twilight Zone
Пользователь №: 1

Big Data*,
Блог компании DCA (Data-Centric Alliance)
Привет, Хабр! Этой статьёй я открываю цикл материалов, посвящённых работе с большими данными. Зачем? Хочется сохранить накопленный опыт, свой и команды, так скажем, в энциклопедическом формате – наверняка кому-то он будет полезен.

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

Начинать надо от простого к сложному, поэтому первая статья – о принципах работы с большими данными и парадигме MapReduce.

История вопроса и определение термина

Термин Big Data появился сравнительно недавно. Google Trends показывает начало активного роста употребления словосочетания начиная с 2011 года (ссылка):

При этом уже сейчас термин не использует только ленивый. Особенно часто не по делу термин используют маркетологи. Так что же такое Big Data на самом деле? Раз уж я решил системно изложить и освятить вопрос – необходимо определиться с понятием.

В своей практике я встречался с разными определениями:

· Big Data – это когда данных больше, чем 100Гб (500Гб, 1ТБ, кому что нравится)

· Big Data – это такие данные, которые невозможно обрабатывать в Excel

· Big Data – это такие данные, которые невозможно обработать на одном компьютере

· Вig Data – это вообще любые данные.

· Big Data не существует, ее придумали маркетологи.

В этом цикле статей я буду придерживаться определения с wikipedia:

Большие данные (англ. big data) — серия подходов, инструментов и методов обработки структурированных и неструктурированных данных огромных объёмов и значительного многообразия для получения воспринимаемых человеком результатов, эффективных в условиях непрерывного прироста, распределения по многочисленным узлам вычислительной сети, сформировавшихся в конце 2000-х годов, альтернативных традиционным системам управления базами данных и решениям класса Business Intelligence.

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

Приведу несколько примеров того, что может быть источником данных, для которых необходимы методы работы с большими данными:

· Логи поведения пользователей в интернете

· GPS-сигналы от автомобилей для транспортной компании

· Данные, снимаемые с датчиков в большом адронном коллайдере

· Оцифрованные книги в Российской Государственной Библиотеке

· Информация о транзакциях всех клиентов банка

· Информация о всех покупках в крупной ритейл сети и т.д.

Количество источников данных стремительно растёт, а значит технологии их обработки становятся всё более востребованными.

Принципы работы с большими данными

Исходя из определения Big Data, можно сформулировать основные принципы работы с такими данными:

1. Горизонтальная масштабируемость. Поскольку данных может быть сколь угодно много – любая система, которая подразумевает обработку больших данных, должна быть расширяемой. В 2 раза вырос объём данных – в 2 раза увеличили количество железа в кластере и всё продолжило работать.

2. Отказоустойчивость. Принцип горизонтальной масштабируемости подразумевает, что машин в кластере может быть много. Например, Hadoop-кластер Yahoo имеет более 42000 машин (по этой ссылке можно посмотреть размеры кластера в разных организациях). Это означает, что часть этих машин будет гарантированно выходить из строя. Методы работы с большими данными должны учитывать возможность таких сбоев и переживать их без каких-либо значимых последствий.

3. Локальность данных. В больших распределённых системах данные распределены по большому количеству машин. Если данные физически находятся на одном сервере, а обрабатываются на другом – расходы на передачу данных могут превысить расходы на саму обработку. Поэтому одним из важнейших принципов проектирования BigData-решений является принцип локальности данных – по возможности обрабатываем данные на той же машине, на которой их храним.

Все современные средства работы с большими данными так или иначе следуют этим трём принципам. Для того, чтобы им следовать – необходимо придумывать какие-то методы, способы и парадигмы разработки средств разработки данных. Один из самых классических методов я разберу в сегодняшней статье.

Про MapReduce на хабре уже писали (раз, два, три), но раз уж цикл статей претендует на системное изложение вопросов Big Data – без MapReduce в первой статье не обойтись J

MapReduce – это модель распределенной обработки данных, предложенная компанией Google для обработки больших объёмов данных на компьютерных кластерах. MapReduce неплохо иллюстрируется следующей картинкой (взято по ссылке):

MapReduce предполагает, что данные организованы в виде некоторых записей. Обработка данных происходит в 3 стадии:

1. Стадия Map. На этой стадии данные предобрабатываются при помощи функции map(), которую определяет пользователь. Работа этой стадии заключается в предобработке и фильтрации данных. Работа очень похожа на операцию map в функциональных языках программирования – пользовательская функция применяется к каждой входной записи.

Функция map() примененная к одной входной записи и выдаёт множество пар ключ-значение. Множество – т.е. может выдать только одну запись, может не выдать ничего, а может выдать несколько пар ключ-значение. Что будет находится в ключе и в значении – решать пользователю, но ключ – очень важная вещь, так как данные с одним ключом в будущем попадут в один экземпляр функции reduce.

2. Стадия Shuffle. Проходит незаметно для пользователя. В этой стадии вывод функции map «разбирается по корзинам» – каждая корзина соответствует одному ключу вывода стадии map. В дальнейшем эти корзины послужат входом для reduce.

3. Стадия Reduce. Каждая «корзина» со значениями, сформированная на стадии shuffle, попадает на вход функции reduce().

Функция reduce задаётся пользователем и вычисляет финальный результат для отдельной «корзины». Множество всех значений, возвращённых функцией reduce(), является финальным результатом MapReduce-задачи.

Несколько дополнительных фактов про MapReduce:

1) Все запуски функции map работают независимо и могут работать параллельно, в том числе на разных машинах кластера.

2) Все запуски функции reduce работают независимо и могут работать параллельно, в том числе на разных машинах кластера.

3) Shuffle внутри себя представляет параллельную сортировку, поэтому также может работать на разных машинах кластера. Пункты 1-3 позволяют выполнить принцип горизонтальной масштабируемости.

4) Функция map, как правило, применяется на той же машине, на которой хранятся данные – это позволяет снизить передачу данных по сети (принцип локальности данных).

5) MapReduce – это всегда полное сканирование данных, никаких индексов нет. Это означает, что MapReduce плохо применим, когда ответ требуется очень быстро.

Примеры задач, эффективно решаемых при помощи MapReduce

Начнём с классической задачи – Word Count. Задача формулируется следующим образом: имеется большой корпус документов. Задача – для каждого слова, хотя бы один раз встречающегося в корпусе, посчитать суммарное количество раз, которое оно встретилось в корпусе.

Раз имеем большой корпус документов – пусть один документ будет одной входной записью для MapRreduce–задачи. В MapReduce мы можем только задавать пользовательские функции, что мы и сделаем (будем использовать python-like псевдокод):

def map(doc):
for word in doc:
yield word, 1

def reduce(word, values):
yield word, sum(values)

Функция map превращает входной документ в набор пар (слово, 1), shuffle прозрачно для нас превращает это в пары (слово, [1,1,1,1,1,1]), reduce суммирует эти единички, возвращая финальный ответ для слова.

Обработка логов рекламной системы

Второй пример взят из реальной практики Data-Centric Alliance.

Задача: имеется csv-лог рекламной системы вида:

Необходимо рассчитать среднюю стоимость показа рекламы по городам России.

def map(record):
user_id, country, city, campaign_id, creative_id, payment = record.split(«,»)
payment=float(payment)
if country == «RU»:
yield city, payment

def reduce(city, payments):
yield city, sum(payments)/len(payments)

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

В статье мы рассмотрели несколько вводных моментов про большие данные:

· Что такое Big Data и откуда берётся;

· Каким основным принципам следуют все средства и парадигмы работы с большими данными;

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

Первая статья была больше теоретической, во второй статье мы перейдем к практике, рассмотрим Hadoop – одну из самых известных технологий для работы с большими данными и покажем, как запускать MapReduce-задачи на Hadoop.

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

Спасибо за внимание, готовы ответить на ваши вопросы.

Источник

Спасительная локальность суперкомпьютеров

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

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

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

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

Рис.1. Ресурс параллелизма и использование данных

Ресурс параллелизма в современных суперкомпьютерах растет невероятными темпами — первое значение в 1 MFLOPS было получено в 1966 году на компьютере CDC-6600, содержащем единственный процессор, и до настоящего времени именно увеличение степени параллелизма определяло рост производительности. Все специалисты сходятся во мнении, что на экзафлопсных суперкомпьютерах одновременно будут работать сотни миллионов и миллиарды параллельных процессов и нитей, а если это так, то как обеспечить эффективность их взаимодействия при выполнении приложения?

Эффективное использование данных уже давно стало серьезной проблемой, и еще в середине 90-х годов она удостоилась даже специального термина — «стена памяти» [1]. Задержка при обращении процессора к оперативной памяти для большинства современных систем лежит в диапазоне 150–300 тактов, и пока нет доступных технологий, которые могли бы это значение принципиально уменьшить. Основным решением на сегодня является использование иерархии памяти, однако тут же возникает вопрос: как обеспечить работу с данными в программах и алгоритмах, адекватную введенной иерархии?

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

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

Локальность всюду

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

Иерархия памяти — очень важное понятие, прямо связанное с эффективностью. Для любой современной вычислительной платформы легко написать два варианта программы, реализующих один и тот же алгоритм, но отличающихся друг от друга на порядок по времени работы, причем без использования избыточных операций и каких-либо специальных задержек. Интересно и то, что сама идея иерархии памяти появилась давно. Например, уже в компьютере ILLIAC-IV (1967 год) каждый процессорный элемент имел 6 регистров и 2048 слов оперативной памяти. Кроме того, для всей системы были предусмотрены два диска по 1 Гбит каждый и барабан для долговременного хранения данных объемом 10 12 бит с однократной записью — иерархия памяти в четыре уровня была уже тогда.

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

Еще большее значение имеет локальность данных в системах с распределенной памятью. Во время работы параллельной программы происходит обмен данными между процессами, на скорость которого влияют и латентность, и пропускная способность, и другие характеристики коммуникационной сети. Чем меньше обменов, тем меньше задержек и выше эффективность программ. Как распределить данные по памяти вычислительных узлов, чтобы минимизировать обмен в процессе выполнения программы? Это исключительно серьезная математическая задача [2], которая далеко не всегда имеет простое решение, однако эта задача принципиально важна для разработки масштабируемых приложений для экзафлопсных суперкомпьютеров, и именно поэтому проектирование алгоритмов без интенсивного обмена данными (communication free algorithms) является одним из приоритетных направлений исследований для всего суперкомпьютерного сообщества.

Заметим, что понимание важности описания локальности расположения данных для создания масштабируемых и переносимых приложений привело к появлению отдельного класса технологий параллельного программирования, опирающихся на модель PGAS (Partitioned Global Address Space). Яркими представителями этого класса являются языки UPC, Coarray Fortran, Fortress, Chapel и X10.

Смежный, но очень важный для систем с распределенной памятью вопрос — топология коммуникационной сети и ее учет параллельными приложениями. Главная проблема заключается в том, чтобы обеспечить хорошее соответствие между локальностью взаимодействия параллельных процессов в приложении и близостью вычислительных узлов. Интересные данные были приведены на конференции ISC 2013 об опыте использования суперкомпьютера Blue Waters в Центре суперкомпьютерных приложений — если из 4116 узлов, выделяемых приложению, всего 1 узел (0,02% от общего числа) выбивается из связного пула узлов и выделяется где-то в другой области коммуникационной сети, то падение эффективности работы приложения на такой конфигурации может достигать 30% и более. Подобные примеры накладывают жесткие требования не только на качество работы планировщиков заданий, которые обязательно должны учитывать локальность при выделении ресурсов приложениям. Здесь важно понимать и четко описывать структуру взаимодействия параллельных процессов внутри самих приложений, но эта информация доступна далеко не всегда. Если в приложении, например, явным образом используется понятие MPI-топологии, то задача упрощается, но в общем случае она очень непроста.

Весьма интересно то, как идеи локальности отражаются в технологиях программирования. В технологии OpenMP предусмотрены два класса переменных: локальные (private) и глобальные (shared). Если нить использует свои локальные переменные, то все происходит без каких-либо задержек и проблем. Но если необходим доступ к глобальной переменной, то начинаются вопросы. Где физически расположить глобальную переменную, чтобы доступ к ней из любой нити был бы одинаково быстрым? Как обеспечить синхронизацию доступа для сохранения корректности данных? Сразу возникает необходимость синхронизации и использования механизмов критической секции или семафоров, и, как следствие, неизбежно падает эффективность.

Другой пример «нелокальности» — коллективные операции в MPI, вовлекающие, как правило, все параллельные процессы приложения. На практике отсутствие локальности в организации параллелизма всегда оборачивается проблемами с эффективностью и масштабируемостью приложений, поэтому использование таких операций стараются минимизировать. Для алгоритмов, в которых не требуется барьерная синхронизация, ввели даже специальное название: synchronization free algorithms, подчеркивая практическую важность этого свойства.

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

Локальность на практике

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

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

Рис. 2. Профили работы с памятью реальных программ

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

Еще одним мощным средством исследования реальных свойств программ является анализ данных мониторинга системного уровня, описывающих характеристики программно-аппаратной среды суперкомпьютеров во время исполнения приложений. В основе подхода Job Digest [4], развиваемого в НИВЦ МГУ, лежит анализ данных от аппаратных датчиков: реальная загрузка процессоров, реальная производительность, особенности использования коммуникационной сети, интенсивность операций ввода-вывода, появление свопинга и т. д. Эти и другие параметры дают содержательную информацию о многих свойствах параллельных приложений. В том числе и о свойствах локальности. На рис. 3 показаны два графика,иллюстрирующих ситуацию с промахами в кэш-память второго уровня для двух разных приложений. Ясно, что у первого приложения локальность использования данных не составляет проблем, однако у второго на локальность явно нужно обратить внимание.

Рис. 3. Job Digest: иллюстрация кэш-промахов для отражения локальности использования данных в приложениях

Литература

Владимир Воеводин (voevodin@parallel.ru) — зам. директора, Вадим Воеводин (vadim_voevodin@mail.ru) — научный сотрудник НИВЦ МГУ. Статья подготовлена на основе материалов доклада, представленного на IV Московском суперкомпьютерном форуме (МСКФ-2013, грант РФФИ 13-07-06046г). Работа выполнена при поддержке Минобрнауки РФ (госконтракт № 14.514.11.4103), стипендии Президента РФ (СП-6815.2013.5) и РФФИ (грант 13-07-00787).

Поделитесь материалом с коллегами и друзьями

Источник