Цифровой журнал «Компьютерра» № 22

Нет ничего проще Герман Царев

Опубликовано 24 июня 2010 года

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

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

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

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

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

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

И так, знакомьтесь – MapReduce. Эта модель программирования для обработки больших объемов данных. Ее создателем считается небезызвестная компания Google. В своей работе она активно применяет этот механизм, что позволяет говорить о его удобности, быстродействии и практичности.

Рассмотрим обработку данных с применением этой технологии. MapReduce включает в себя 3 этапа. Подготовка данных, определение функции map и определении функции reduce. Рассмотрим каждый их этих этапов.

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

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

Определение функции reduce. Функция reduce служит для сборки обработанных частей данных в единый результат. Программист определяет эту функции исходя из поставленной задачи и требуемого результата.

После этого, для запуска обработки данных необходимо вызвать всего одну функцию (ее название зависит от реализации механизма MapReduce, например в Qt подобная функция имеет название mappedReduced), указав в ее параметрах: подготовленные разбитые на части данные, функцию map и функцию reduce.

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

Данная технология реализована для различных языков программирования, например, для С++, С#, Java и других.

Удобной, простой в использовании с одной стороны, и показывающие прекрасные результаты быстродействия с другой, является реализация механизма MapReduce в объектно-ориентированной кроссплатформенной библиотеке Qt.

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

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

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

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

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

К оглавлению