Грокаем алгоритмы

Параллельный алгоритм трудно разработать. И так же трудно убедиться в том, что он работает правильно, и понять, какой прирост скорости он обеспечивает. Одно можно заявить твердо: выигрыш по времени не линеен. Следовательно, если процессор вашего компьютера имеет два ядра вместо одного, из этого не следует, что ваш алгоритм по волшебству заработает вдвое быстрее. Это объясняется несколькими причинами.

• Затраты ресурсов на управление параллелизмом — допустим, нужно отсортировать массив из 1000 элементов. Как разбить эту задачу для выполнения на двух ядрах? Выделить каждому ядру 500 элементов, а затем объединить два отсортированных массива в один большой отсор­тированный массив? Слияние двух массивов требует времени.

• Распределение нагрузки — допустим, необходимо выполнить 10 задач, и вы назначаете каждому ядру 5 задач. Однако ядру A достаются все простые задачи, поэтому оно выполняет свою работу за 10 секунд, тогда как ядро B справится со сложными задачами только за минуту. Это означает, что ядро A целых 50 секунд простаивает, пока ядро B выполняет всю работу! Как организовать равномерное распределение работы, чтобы оба ядра трудились с одинаковой интенсивностью?

Если вас интересует теоретическая сторона производительности и масштабируемости, возможно, параллельные алгоритмы — именно то, что вам нужно!

MapReduce

Одна разновидность параллельных алгоритмов в последнее время становится все более популярной: распределенные алгоритмы. Конечно, параллельный алгоритм удобно запустить на компьютере, если для его выполнения потребуется от двух до четырех ядер, а если нужны сотни ядер? Тогда алгоритм записывается так, чтобы он мог выполняться на множестве машин. Алгоритм MapReduce — известный представитель семейства распределенных алгоритмов. Для работы с ним можно воспользоваться популярной системой с открытым кодом Apache Hadoop.

Для чего нужны распределенные алгоритмы?

Предположим, имеется таблица с миллиардами или триллионами запи­сей и вы хотите применить к ней сложный вопрос SQL. Выполнить его в MySQL не удастся, потому что MySQL начнет «тормозить» уже после нескольких миллиардов записей. Используйте MapReduce через Hadoop!

Или, предположим, вам нужно обработать длинный список заданий. Обработка каждого задания занимает 10 секунд, всего требует обработки 1 миллион заданий. Если выполнять эту работу на одном компьютере, она займет несколько месяцев! Если бы ее можно было выполнить на 100 машинах, работа завершилась бы за несколько дней.

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

Функция map

Функция map проста: она получает массив и применяет одну функцию к каждому элементу массива. Скажем, в следующем примере происходит удваивание каждого элемента в массиве:

>>> arr1 = [1, 2, 3, 4, 5]

>>> arr2 = map(lambda x: 2 * x, arr1)

[2, 4, 6, 8, 10]

Массив arr2 теперь содержит значения [2, 4, 6, 8, 10] — все элементы arr1 увеличились вдвое! Удвоение выполняется достаточно быстро. Но представьте, что выполнение применяемой функции требует больше времени. Взгляните на следующий псевдокод:

>>> arr1 = # Список URL

>>> arr2 = map(download_page, arr1)

Имеется список URL-адресов, нужно загрузить каждую страницу и сохранить содержимое в arr2. Для каждого адреса загрузка занимает пару секунд. Для 1000 адресов потребуется пара часов! А теперь представьте, что у вас имеется 100 машин и map автоматически распределяет работу между ними. Тогда в любой момент будут загружаться сразу 100 страниц одновременно, и работа пойдет намного быстрее!

Функция reduce

Функция reduce иногда сбивает людей с толку. Идея заключается в том, что весь список элементов «сокращается» до одного элемента. Напомню, что функция map переходит от одного массива к другому.

С функцией reduce массив преобразуется в один элемент.

Пример:

>>> arr1 = [1, 2, 3, 4, 5]

>>> reduce(lambda x,y: x+y, arr1)

15

В данном случае все элементы в массиве просто суммируются: 1 + 2 + 3 + 4 + 5 = 15! Я не буду рассматривать свертку более подробно, потому что в Интернете хватает руководств по этой теме.

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

Фильтры Блума и HyperLogLog

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