Архитектура Google

Нынче стало модно сравнивать Google с «Матрицей» и «Скайнетом». Некоторых журналистов от таких мыслей берет озноб: «Google строит Суперкомпьютер будущего!»

Они же недоумевают: «В настоящее время в распоряжении компании не менее 100 000 компьютеров. Очень сложно представить не только то, сколько физически могут занимать эти серверы, но и каким образом персоналу удается их обслуживать».

Действительно, когда задумываешься над тем, как работают поисковые системы, голова идёт кругом. Обычный компьютер с Windows на борту трудится несколько минут, чтобы найти файл на своем 200 Gb диске. Google ищет по всему интернету и отвечает на любой запрос за секунду. Как? Постараемся разобраться, попутно ответив и на вопросы, заданные нашими любознательными коллегами.

Сколько серверов обеспечивают работу Google, знают только инсайдеры компании. Может быть, рубеж в 100 000 машин уже взят, может быть, нет. В любом случае, счет идёт на десятки тысяч компьютеров и парк их постоянно эволюционирует.

Прежде всего, разберёмся, зачем такая прорва машин, почему нельзя было ограничиться небольшим количеством новейших суперкомпьютеров? Наверняка, их было бы легче обслуживать, чем тысячи серверов. Однако, создатели Гугла научились не доверять технике, потому что в числе первых приоритетов у них всегда были безопасность и стабильность — вещи, с компьютерами мало совместимые. Компьютеры отказывают, а суперкомпьютеры — тем более. Когда у вас ломается десять машин из десяти тысяч — не беда, в крайнем случае, вы можете выбросить их и поставить новые. Когда у вас ломается суперкомпьютер — это уже ощутимо; его так просто не заменишь, нужно чинить, а значит, связываться с нестандартным железом.

Альтернатива суперкомпьютерам — кластерная архитектура, при которой большое количество стандартных серверов используются для параллельного решения задач. Для глобальной поисковой машины такое решение подходит идеально.

Участвующие в кластере компьютеры разделены на несколько функциональных типов, которые мы подробно рассмотрим далее. Физически же это самые простые серверы, зачастую дешевле и медленнее тех, на которых крутятся сайты средней руки. Обычным проектам незачем делать кластер, поэтому, когда их вычислительные потребности превышают возможности сервера, у администраторов часто нет альтернативы апгрейду, установке дополнительного процессора или RAID-массива. Гуглу же все равно (с технической точки зрения), купить ли один мощный компьютер или два помедленнее. Важна не максимальная производительность юнита, а соотношение цена/скорость. Поэтому в кластер ставится опробованное, чуть устаревшее и потому подешевевшее железо. Любых сложных технических решений администраторы Гугла избегают. Даже RAID и SCSI, обычные для серверов, оказываются неоправданно дорогими.

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

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

Все компьютеры Google собирает специально для себя. Они устанавливаются в стойки, каждая из которых вмещает от 40 до 80 серверов (по 40 юнитов с каждой стороны стойки). При такой плотности размещения вопросы питания и охлаждения становятся критичными. Обычному серверу требуется около 100W, при стандартном КПД блоков питания в 75% получается, что на вход нужно подавать 120–130W. Серверная стойка занимает около 2.3 m2, следовательно, на каждый квадратный метр требуется 4500W. При использовании более мощных машин плотность достигает 8000 W/m2. При этом стандартная плотность, которая предлагается коммерческими датацентрами — от 700 до 1800 W/m2. Поэтому не только серверы, стойки, но и сами датацентры Гуглу приходится подстраивать под себя.

Стоимость альтернативных систем охлаждения и серверов с пониженным энергопотреблением слишком высока. Стойка 10kW потребляет около 10 MWh в месяц. При цене в 15 центов за kW/h (половина идёт на собственно оплату энергии, другая на поддержку систем бесперебойного питания и распределения мощностей) получается, что одна стойка обходится в $1500/месяц. Использование нетрадиционных решений на хардверном уровне, по подсчётам специалистов компании, будет обходиться не менее чем в $5000/месяц за счёт амортизации дорогостоящего оборудования.

Географически кластеры находятся в разных частях планеты, что позволяет не бояться ни природных катаклизмов, ни массовых отключений электричества. Русские пользователи наверняка помнят, как Яндекс полностью отключился из-за аварии на подстанции. Поисковику, который обслуживает всю планету и при этом котируется на бирже, таких промахов позволять себе не стоит.

На своих серверах Google использует модифицированное ядро Linux и всё программное обеспечение пишет самостоятельно. Во-первых, разработки компании во многом не имеют аналогов. Во-вторых, используя собственные управляющие программы не нужно тратить деньги на покупку лицензии (ужас корпоративных сетей и, кстати, аргумент против распространения кластеров). Софт превращает кластер в единый организм, подчиняет сотни компьютеров выполнению одной задачи.

Когда пользователь вводит запрос в Google, браузер обращается к DNS-серверу, а тот отправляет его на один из кластеров, наиболее близкий и наименее загруженный. После этого все операции проходят внутри этого кластера.

Вкратце разберемся, что собой представляет индекс, главное богатство поисковых машин.

Он не содержит информацию в явном виде: прежде чем «проиндексироваться», страница проходит через ряд преобразователей. Определяется, какие слова встречаются в документе, с какой частотностью, на каких позициях, с какой гарнитурой и так далее. Эти данные формируют так называемый хит-лист (hitlist) и сохраняются в оптимизированном для поиска формате на индексных серверах.

Прямой индекс содержит идентификаторы документов (docID), каждому из которых соответствует список идентификаторов слов (wordID). При поиске же используется инвертированный индекс. В нём, наоборот, каждому wordID соответствует docID-список. Хит-листы используются в обоих индексах.

Параллельно с индексом Гугл хранит кеш, полные текстовые копии страниц, каждой из которых соответствует docID из индекса. Они лежат на архивных серверах (document servers).

Итак, пройдя через аппаратный распределитель нагрузки, запрос попадает на один из веб-серверов, который координирует действия всех других машин. Процесс обработки запроса делится на два основных этапа. На первом слова, введённые пользователем, перекодируются в wordID и индексные серверы с помощью инвертированного индекса формируют список docID, отсортированный по релевантности. На втором этот список через веб-сервер передаётся архивным серверам. Они извлекают заголовки страницы и сниппеты — те куски текста, которые содержат наибольшее количество ключевых слов и кажутся поисковику наиболее релевантным. Вся эта информация возвращается веб-серверу, и он формирует «выдачу» — ту HTML-страницу с результатами, которая предъявляется пользователю.

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

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

Кластер состоит из одного мастер-сервера (master server) и многих дата-серверов (chunkservers), к нему постоянно обращаются клиенты, которые могут быть установлены на отдельных машинах, а могут помещаться на дата-серверах.

Все файлы разделены на блоки (chunks) фиксированной величины. Поскольку Гуглу приходится иметь дело с огромными массивами информации, используется беспрецедентно большой размер — 64Mb. Всем блокам присваиваются уникальные 64-битные идентификаторы (chunk handle), которые хранятся на мастер-сервере в качестве метаданных. В целях безопасности блок после записи копируется ещё на два дата-сервера, таким образом, в любой момент времени всякий файл доступен в трёх экземплярах.

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

Поскольку мастер один, нельзя загружать его большим объемом трафика, иначе в системе появится узкое место. Поток данных никогда не проходит через мастер, вместо этого клиенты запрашивают у него адреса нужных дата-серверов и общаются непосредственно с ними. При этом адреса выдаются клиентам, хранятся у них в кеше определенное время, затем стираются — всё вместе называется арендой дата-сервера.

Клиент, зная, что все файлы делятся на куски по 64Mb, преобразует нужный ему диапазон байт в индекс блока (chunk index) и отправляет его вместе с именем файла мастеру, а в ответ получает идентификатор и названия дата-серверов, на которых хранятся копии.

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

Теперь рассмотрим, как происходит запись новой информации, это позволит нам понять и механизм репликации.

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

1. Клиент обращается к мастеру с запросом о том, какой дата-сервер имеет контроль над нужным блоком. Если контроль не передан никому, мастер выбирает один из трёх серверов с копиями и назначает его главным.

2. Мастер передаёт информацию о главном и двух подчинённых дата-серверах. Клиент кеширует эту информацию. На этом участие мастера в операции завершается до тех пор, пока выданные им права не потеряют силу в результате 60 секундного тайм-аута.

3. Клиент передаёт данные трём дата-серверам, которые сохраняют её в LRU-буфер. Трафик идёт последовательно от ближайшего сервера к следующему, вне зависимости от того, какая иерархия выстроена в кластере в данный момент. Вообще, поток данных в файловой системе Гугла всегда идёт линейно, что позволяет максимально загрузить сеть. Топология сети такова, что по IP адресам всегда можно выяснить реальное расстояние между двумя серверами.

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

5. Главный сервер отправляет своим подчинённым запрос на запись.

6. Подчинённые серверы рапортуют об успешной записи.

7. Главный север сообщает клиенту о завершении операции.

Ошибки на любом из шагов отслеживаются, действия с 3 по 7 могут повторяться несколько раз, прежде чем весь процесс будет запущен заново. Если, например, один из подчинённых серверов не смог полностью записать нужную информацию в блок, он будет повторять попытки. Допустим, одна из попыток окажется успешной после перезагрузки сервера (перезагрузка всегда совершается принудительно простым уничтожением процесса, поэтому занимает несколько секунд). В результате повторной записи файл блока окажется больше, чем два его собрата. Таким образом, Гугл не может гарантировать побайтную точность всех копий, но это и не требуется — главное, чтобы вся информация была успешно записана, а адреса переданы клиенту и мастер-серверу.

Теперь рассмотрим механизм, который позволяет мастеру быть в курсе всего происходящего.

Каждый дата-сервер при запуске отсылает свою адресную информацию, мастер сохраняет её и периодически обновляет с помощью так называемых heartbeat-запросов. Все данные хранятся в оперативной памяти, что обеспечивает нужную скорость коммуникаций.

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

Другой случай ререпликации — профилактический, в целях более точной балансировки нагрузки. Когда к кластеру подключают партию серверов, их нельзя наводнять новыми файлами, иначе образуется так называемый hot spot, место с неоправданно высокой нагрузкой. Поэтому мастер копирует часть уже заполненных блоков, освобождая диски старых серверов.

Каждый блок в системе имеет свою версию (chunk version), которая обновляется после любого успешного изменения. Если дата-сервер некоторое время был недоступен и пропустил ряд операций, а потом вернулся в сеть, часть его информации оказывается просроченной. Если версия файла меньше текущей, он подлежит удалению.

Удаление файлов осуществляется не мгновенно. Сначала файл исчезает из индекса мастера и переименовывается. Если через три дня он не возвращается в индекс, то во время очередной проверки мастер дает команду на удаление. Такой подход имеет несколько преимуществ. Поскольку «уборка мусора» проходит систематически, не возникнет проблем в случае потери единичного запроса на удаление. Кроме того, все действия совершаются во время регулярных сеансов связи мастера с дата-серверами (heartbeat) и потому не требуют дополнительной нагрузки на сеть.

Для Google отказ оборудования является нормой, а не исключением. Серверы и компоненты выходят из строя каждый день. Механизм репликации позволяет сохранить информацию в целостности: блок нельзя восстановить только в том невероятном случае, когда в течение нескольких минут кластер безвозвратно теряет три независимых сервера. В любом случае, опасности подвергается лишь малая доля информации. Гораздо более опасна потеря мастер-сервера, поэтому он защищён ещё надёжнее, чем дата-сервера.

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

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

При отказе мастер-сервера контролирующие службы запускают мастер-процесс на другой машине. Поскольку он фигурирует в сети под доменом (скажем, gfs-master), достаточно поменять DNS-алиас, прописав новый IP-адрес, чтобы вернуть кластеру работоспособность. Это единственный случай поломки оборудования, с которыми файловая система Google не может справиться автономно и требуется вмешательство извне.

 

Ссылки по теме: видеозаписи лекций «Как устроен Гугл» в МФТИ и МИЭМ, 6 и 7 марта 2007 года.