вторник, февраля 20, 2007

Передовые технологии Гугла

Сравнительно недавний пост в "Интернетных штучках" со списком сервисов Гугла приобрел весьма большую популярность в Рунете. Примечательно, что этот неофициальный список несколько длиннее официальных: и русскоязычного, и англоязычного.
Но гораздо интереснее то, что лежит за этими сервисами: технологии на основе которых они работают. Гугл не зря собирает конференцию по масштабируемым системам. Когда счет пользователей идет на миллионы, технологическия решения должны быть соответствующими.
По ссылке с hrg_tech я нашла слайды с интригующим названием Google Internals. Там перечислены основные Гугловские технологии с кратким описанием. Есть даже более-менее секретная - это то, что Гугл делает собственные свитчи, ну и количественных оценок серверов я раньше не встречала. На слайдах приводится цифра 450000 серверов.
Дальше я перечислю некоторые из известных Гугловских технологий, плюс ссылки, по которым по каждой из них можно узнать подробнее.

Архитектура кластера Гугла
Официальная статья: Web Search for a Planet: The Google Cluster Architecture
Речь идет о Гугловском кластере, который занимается обработкой поисковых запросов. В статье говорится, что для этого используется 15000 серверов средней мощности, но это было некоторое время назад, информация устарела.
Зачем так сложно, почему бы не использовать суперкомпьютеры? А так дешевле. Если объединить кучу серверов средней мощности, вместо того, чтобы использовать несколько очень мощных машин, соотношение цена/качество будет значительно лучше.
Вся система состоит не из одного кластера, а из нескольких, которые находятся в разных точках мира. Очень похоже на то, для чего придумывалась ARPA-net. Только ARPA боялась вооруженного вторжения, а Гугл опасается замелятресений и тому подобных катаклизмов.
При поступлении запроса система балансировки загрузки перенаправляет запрос одному из кластеров, который географически наиболее близок к пользователю. Дальше работа происходит с этим одним конкретным кластером, в котором есть своя балансировка загрузки.
Парочка интересных фактов: Гугл хранит дюжины копий всего веба на своих кластерах; при таком большом количестве серверов у них возникли проблемы с потреблением энергии и охлаждением.

Файловая система Google File System (GFS)
Официальная статья: The Google File System
Эта файловая система проектировалась под миллионы файлов, размером от 100 мб. Ожидались и многогигабайтные файлы. Файлы меньшего размера тоже планировалось поддерживать, но оптимизация для работы с ними не предусматривалась.
Основная идея такая: каждый файл дробится на куски, каждый кусок в нескольких копиях содержится на разных машинах. Размер такого куска - 64 мегабайта и это довольно большой размер для подобных систем. Но в ходе размышлений гугловцы пришли именно к этой цифре. Один файл в среднем хранится в трех копиях, но это количество можно настраивать. По ходу статьи несколько раз упоминается, что они реализовали не POSIX API.
Машины, на которых лежат куски файлов, называются чанксерверы (chunkserver). Ими всеми управляет некая мастер-машина. Мастер занимается балансировкой загрузки, осуществляет сборку мусора, периодически посылает HeartBeat сообщение и делает еще много чего интересного. Клиент, которому нужен файл, обращается сначала к мастеру, который отсылает клиента к нужному чанксерверу. При работе с файлами гарантируется атомарность доступа.
По такому описанию сразу видно слабое место - Мастер-сервер. Если вдруг что с ним случится, то система становится неработоспособной. Чтобы такого не происходило на случай проблем с мастером предусмотрен целый комплекс мер. Текущее состояние мастера постоянно копируется. Как и логи, как и чекпониты. Если с ним вдруг чего случится мониторинговая инфраструктура GFS практически немедленно стартует где-нибудь новый процесс-мастер на основе скопированных данных. Есть еще Теневые Мастеры, которые могут обеспечивать доступ только на чтение, когда с основным Мастер что-нибудь случилось.

MapReduce
Официальная статья: MapReduce: Simplified Data Processing on Large Clusters. В Wikipedia про MapReduce есть неплохая статья.
MapReduce - повзаимствованная из Лиспа идея, которая очень хорошо подходит для обработки больших объемов данных. Обрабтка данных происходит в две стадии. Первая Map, выполняет одну и ту же операцию над независимыми данными. Эту часть удобно выполнять параллельно. Вторая, Reduce, группирует полученные от Map результаты по каким-либо признакам. Ее сложнее выполнять параллельно, но тоже можно. В статье рассказывается о реальных задачах, которые хорошо ложатся на MapReduce.

Bigtable

Офицальная статья Bigtable: A Distributed Storage System for Structured Data. Видеолекция про BigTable.
Собственная база данных Гугла. Когда о ней говорят, ее пытаются не называть "базой данных". Употребляется обычно термин вроде "многомерное отображение". Я так понимаю, по каким-то формальным признакам BigTable базой данных не является. Но поскольку "база данных" произнести гораздо проще, чем, скажем, "распределенная система для управления стурктурированными данными", ее все равно называют базой данных и не заморачиваются. Я тоже так поступлю.
BigTable - это распределенная база данных. Там хранят свои данные система индексирования, Google Finance, Google Earth и др. Петабайты данных разбросаны по тысячам серверов.
BigTable разрабатывается с 2004 года. Предполагалось быстрое чтение колонок, а не строк. Каждая таблица многомерна, ячейка определяется не только колонкой и строкой, там еще есть время, версии. Таблицы оптимизированы для хранения в GFS путем разбиения на куски 200 мегабайт размером. Разбиение идет по строкам. Если размер куска начинает сильно увеличиваться, его архивируют.
От использования какой-либо коммерческой базы данных они отказались, ибо не влезало. Плюс дорого очень получалось.

Sawzall

Официальная статья - Interpreting the Data: Parallel Analysis with Sawzall
Sawzall - придуманный гугловцами язык для анализа больших объемов распределенных данных. С помощью него реализуется вышеупомянутый MapReduce. SQL им не хватило. Питон и Awk - не подошли, поскольку у них нет встроенных возможностей для работы на нескольких машинах. C, C++ - все что нужно могут, но это уж очень тяжелая артиллерия в данном случае.
Программа на Sawzall выглядит так

count: table sum of int;
total: table sum of float;
sum_of_squares: table sum of float;
x: float = input;
emit count <- 1;
emit total <- x;
emit sum_of_squares <- x * x;



Оригинальных решений у Гугла много, это лишь некоторые из них. Предполагаю, что подавляющее большинство из них не обнародуется.
Мне вообще очень понравилось как они принимают решения. Они исходят из имеющихся задач и только из них. Их не волнует "как принято" или "как у соседа". Попробовали несколько языков - они не подошли? Придумаем свой. При этом стоимость решения для них тоже является важным фактором, несмотря на то, что в деньгах они могут себя не ограничивать.

15 коммент.:

FX комментирует...

Зачот! Спасибо за статью. :) Столько всего интересного!

Анонимный комментирует...

Спасибо за очень интересный пост! С удовольствием прочитал!

Googlе работает для того чтобы делать, а не для того чтобы показывать другим что они работают правильно

--pavelsh

googlemon комментирует...

Кстати, Toby DiPasquale, который написал Google Internals, не работает и не работал в Гугл. Так, что информация не совсем достоверная. Но все равно - интересное чтиво

Алексей Марков комментирует...

Спасибо! Как обычно интересно и как обычно по делу. :-)

Nikita A Zeemin комментирует...

Насчет сервисов и приложений гугла — наиболее полный список, пожалуй, в Википедии: http://en.wikipedia.org/wiki/List_of_Google_products

CTpaHHoe комментирует...

Спасибо за обзор - коротко и поучительно о многом. Впервые узнал про Sawzall

virens комментирует...

Спасибо, интересная статья. Особенно покорило про "дюжину раз зеркалированный веб". Впечатляет.

Andrey Ekaterenchuk комментирует...

интересно=благодарю(':)')

GiNeR комментирует...

Люблю я этих друзей, но порой они начинают настораживать. Власть ведь она того - портит :)

Alena комментирует...

Всем пожалуйста! :-)


Люблю я этих друзей, но порой они начинают настораживать. Власть ведь она того - портит :)

Угу, мне тоже стало жутковато после прочтения статей.

develop7 комментирует...

Классный пост :) Крайне интересно

Анонимный комментирует...

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

Метод гугля напомнил мне то, как на заре е-волюции работал майрософт со своими разработчиками. То в лесу, то в избе - свободный график. У гугля та же история. Но неадекватных решений пока не вижу.Видимо, все дело в том, что они не потомственные миллионеры)) в отличие от некоторых, что здорово портит характер))))

Успехов, Алена!

Бахти
volandus@mail.ru
http://lady.uz

Alena комментирует...

У гугля та же история. Но неадекватных решений пока не вижу.Видимо, все дело в том, что они не потомственные миллионеры))

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

Успехов, Алена!

Спасибо :-)

Andrey комментирует...

Познвательная статья. Интересно было почитать про "БД" и ФС.

Petrovi4 комментирует...

В Московских ВУЗах гугл проводил семинары, на них рассказывали довольно интересные вещи.
Вот тут есть запись http://video.auditory.ru/google-2007.php