Логистика — замечательная штука. Стоит заглянуть в хранилище какого-нибудь гипермаркета — и становится ясно: без тщательного упорядочивания товаров в нём и речи не может идти о какой-либо эффективной торговле. Между тем гигантские торговые дома преспокойно открывают свои двери десяткам тысяч потребителей и легко разыскивают в недрах своих бездонных складов требуемые товары.
С информацией дело обстоит примерно так же. Сохранить её — только одна из задач. Информация требует обработки. Каким бы эффективным ни было хранилище данных, оно не поможет её обработать.
В компании 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, ориентированная на пакетную обработку данных (мастер раздал задания, подождал, собрал результаты) не могла эффективно учитывать эти постоянные изменения.
Именно поэтому в июле 2010 года Google представила свою новую систему распределенного индексирования интернет-контента Caffeine. В ней трудится обновленный вариант технологии MapReduce, ориентированный на инкрементное формирование распределённой индексной базы.
Теперь индекс Google обновляется не единовременно, но редко, а понемногу, но часто. И это позволяет проиндексировать такие мимолетные, казалось бы, ресурсы, как посты социальных сетей или многочисленные навигационные запросы к сервису Google Maps.
Используя свои лучшие наработки и тщательно исследуя тенденции нашей с вами работы в интернете, Google старается делать упреждающие шаги в развитии своего сердца — поисковой системы.