Технология MapReduce: разделяй и властвуй

Логистика – замечательная штука. Стоит заглянуть в хранилище какого-нибудь гипермаркета и становится ясно: без тщательного упорядочивания товаров в нем и речи не может идти о какой-либо эффективной торговле. Между тем гигантские торговые дома преспокойно открывают свои двери десяткам тысяч потребителей и легко разыскивают в недрах своих бездонных складов требуемые товары.

С информацией дело обстоит примерно так же. Сохранить ее – только одна из задач. Информация требует обработки. Каким бы эффективным ни было хранилище данных, оно не поможет её обработать.

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

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

Как узнать на каких веб-страницах есть эти ключевые слова? Какой ресурс содержит всего одно ключевое слово, а какой сразу несколько? Тут без хорошей индексной базы не обойтись.

Сформировать такую базу на петабайтном массиве данных – задачка нетривиальная. Фактически, требуется поочередно «пройтись» по каждому документу и определить, содержит ли он требуемое слово. Как ни крути, процесс линейный.

Но только не для компании, обладающей кластером из полумиллиона компьютеров.

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

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

Вдохновение из прошлого

Помните, в детстве на уроках Родной речи нам давали задание на внимательность? Найти, например, на странице из «Золотой рыбки» все буквы «О» и подсчитать их количество. Школьники скрупулёзно, стока за строкой, высматривали «О», подчеркивали их, а потом суммировали подчеркнутое.

Теперь представите, насколько быстрее пошло бы дело, если бы мы раздали по строке каждому ученику из класса, который, подсчитав количество букв, сообщил его заранее назначенному «главному по буквам». Если не вдаваться в подробности, технология MapReduce работает именно таким образом.

Конечно, разрабатывая MapReduce, сотрудники Google Джеффри Дин (Jeffrey Dean) и Санджай Гемават (Sanjay Ghemawat) вдохновлялись не школьными заданиями. Они имели другой замечательный источник вдохновения. Еще в конце пятидесятых годов прошлого столетия для обработки данных, представленных линейными списками, был разработан язык программирования Lisp – предок целого семейства языков, использующих парадигму функционального программирования.

Lisp и другие функциональные языки поддерживают интересную программную модель, именуемую Map/Reduce. Из ее названия следует, что работают в ней две процедуры: map, применяющая нужную функцию к каждому элементу списка, и reduce, объединяющая результаты работы map.

 

 

Замечательным свойством модели Map/Reduce является всеядность. С ее помощью, например, удобно: организовать счетчик появления искомых слов в большом файле (построение Term-вектора), или счетчик частоты обращений к заданному адресу, вычислить объем всех веб-страниц со всех URL конкретного хост-узла или же создать список всех адресов, содержащих необходимые данные.

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

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

В самом простом варианте программной модели Google MapReduce, процедура map получает на вход список слов, содержащихся в обрабатываемых документах. Она преобразует каждый элемент в пару, одним элементом которой является слово, а другим — число 1.

Затем за список берётся процедура reduce, которая группирует элементы списка с одинаковыми ключами (то есть, словам) и суммирует единички. В результате на выходе оказывается список всех ключевых слов с количеством их упоминаний в тех или иных документах. А это и есть индексная база поисковой системы.

 

 

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

• автоматическое распараллеливание данных из огромного массива по множеству узлов обработки, выполняющих процедуры Map/Reduce;
• эффективную балансировку загрузки этих вычислительных узлов, не дающей им простаивать или быть перегруженными сверх меры;
• технологию отказоустойчивой работы, предусматривающую тот факт, что при выполнении общего задания часть узлов обработки могут выйти из строя или по какой-либо другой причине перестать обрабатывать данные.

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

Как же им это удалось?

Параллельные вычислители, GFS и все тот же кластер

Наиболее светлой мыслью при проектировании MapReduce была идея разместить модули, реализующие процедуры map и reduce на тех самых чанк-серверах – основе файловой системы GFS. Такой подход приближает хранящиеся в GPS к функциям их обработки. Экономия сетевого трафика на лицо.

Дальше — больше. Как и GFS, технология MapReduce построена по принципу «главный-подчиненные». «Голова» MapReduce – процедура Master — управляет множеством разбросанных по чанк-серверам «работников» (workers), часть из которых отвечает за функцию map (их зовут mappers или «мэпперы»), а остальные, соответственно, за reduce (reducers или «редьюсеры»)

На вход MapReduce поступает требующий обработки массив, «разрезанный» на M (по числу мэпперов) частей размером от 16 до 64 мегабайт (стоит напомнить, что именно такой размер имеет чанк в файловой системе GFS). Получив адреса M частей массива, Master MapReduce формирует частные задания для M функций мэпперов и раздает каждой из них адрес чанка, который надлежит подвергнуть процедуре map. Поскольку мэпперы работают параллельно и независимо друг от друга, требуется в M раз меньше времени, чем при линейной обработке.

В результате появляется новый, разделенный на части, массив промежуточных данных, содержащих неупорядоченные списки пар ключ-значение. В идеале количество частей этого промежуточного массива должно быть равно R, то есть совпадать с количеством «работников», отвечающих за операцию reduce. Однако на практике массив пар, содержащих один и тот же ключ, может быть значительно больше (например, в том случае, если ключ — это одно из самых популярных слов в поисковых запросах).

Чтобы сократить его размер, MapReduce использует процедуру предварительного агрегирования данных, присваивая таким популярным парам новое промежуточное значение. Эта процедура именуется combine и, по сути, очень похожа на reduce. Необходимо заметить, что combine можно использовать лишь в тех случаях, когда функция, которую используют на стадии reduce для объединения данных, обладает свойствами коммутативности и ассоциативности.

Агрегированный до требуемого размера массив промежуточных данных может поступать на R «работников», выполняющих reduce. Стоит напомнить, что reduce в простейшем виде работает со всеми значениями одного ключа — например, с количеством упоминаний какого-либо слова. Это значит, что на каждый «работник» желательно подать пары с одинаковым ключом. Проблема заключается в том, что они разбросаны по разным частям списка, сформированного мэпперами. Как же быть?

 

 

Последним этапом перед выполнением процедуры reduce является процедура распределения (partitioning), в результате которой пары с одинаковым ключом попадают на одни и те же «работники». Да, процесс требует времени и существенного сетевого трафика, но все это компенсируется скоростью работы на следующем этапе.

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

 

 

R «работников» создают R результирующих файлов, о чем и докладывают мастеру MapReduce. Получив подтверждение от всех «работников», он считает задание выполненным и передает адреса результирующих файлов клиентскому приложению.

Так в недрах кластера Google и рождается индексная база интернета, строятся графы популярности URL и выполняются прочие необходимые для работы поисковой системы операции.

И не только для нее. Разработчики приложений Google, в которых требуется обработка больших массивов данных, быстро оценили достоинства параллельного вычислителя MapReduce и написали свои варианты процедур map и reduce. Именно так пополняется словарная база переводчика Google Translate, так формирует данные об орфографии десятков языков спелл-чекер Google Docs и индексирует голосовые морфемы Google Voice. Применений MapReduce было найдено множество.

Как и в случае с файловой системой GFS, Google пояснили только идеологию MapReduce, не раскрывая конкретных реализаций ее алгоритмов. Однако и этого хватило, чтобы open source сообщество в рамках проекта Hadoop реализовало планировщик распределения задач по узлам вычислительного кластера Hadoop YARN и фреймворк Hadoop MapReduce, позволяющий создавать собственные мэпперы и редьюсеры.

Вскоре MapReduce начал обрабатывать «большие данные» в других поисковых системах, социальных сетях и интернет-магазинах.

Между тем, с момента разработки MapReduce, интернет существенно изменился. Как в плане контента, где наряду с текстовыми данными все большую роль стали играть изображения, видео, звук, картографическая информация, так и в плане социальном. Нынешний интернет-житель в качестве стартовой страницы своего браузера все реже ставит поисковую систему и все чаще – социальную сеть. Контент нынешнего интернета более динамичный — он меняется буквально ежесекундно.

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

Именно поэтому в июле 2010 года Google представила свою новую систему распределенного индексирования интернет-контента Caffeine. В ней трудится обновленный вариант технологии MapReduce, ориентированный на инкрементное формирование распределенной индексной базы.

 

 

Теперь индекс Google обновляется не единовременно, но редко, а понемногу, но часто. И это позволяет проиндексировать такие мимолетные, казалось бы, ресурсы, как посты социальных сетей или многочисленные навигационные запросы к сервису Google Maps.

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