Файловая система Google: колосс против информационного слона

Есть у психологов такая задачка: «Как съесть слона?» «Слон» в данном случае означает неподъёмную задачу. Правильный ответ: «Только по частям». Разделив необъятное на массу небольших удобоваримых порций, можно не зацикливаться на размере целого и справляться с каждой частью по отдельности.

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

Обычно в вычислительных системах задачу учета и организации доступа к сохраняемой на запоминающих устройствах информации выполняет файловая система. Поэтому-то одним из первых проектов Google стала GFS (Google File System) — файловая система, потенциально способная «съесть» целое стадо информационных «слонов».

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

Лидером команды разработчиков GFS в 2000 году стал Говард Гобьов (Howard Hobioff) – выпускник аспирантуры Университета Карнеги — Меллона, научным направлением которого были как раз системы хранения информации. Вместе со своим руководителем Гартом Гибсоном (Garth Gibson) Говард занимался разработкой аппаратных решений для безопасных и масштабируемых объектных хранилищ данных. Нетрадиционный взгляд на проблему помог команде Гобьова отказаться от проверенных сетевых файловых систем и взяться за решение задачи «с нуля».

Они начали с того, что выбрали единицу хранения, с которой будет работать их файловая система. Такой кусочек веб-контента или индексной базы был назван «чанком» (chunk). Расчеты показали, что оптимальным размером чанкa, используемого поисковой системой, будет 64 мегабайта.

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

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

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

Разработчики GFS выделили для работы с метаданными отдельный сервер — так называемый мастер-сервер. Все метаданные мастер-сервер умещает в своей оперативной памяти, что значительно ускоряет обращение к ним со стороны клиентов. Чтобы найти все чанки нужного файла, клиентское приложение обращается к мастер-серверу, который возвращает ему адреса чанк-серверов, хранящих нужные чанки.

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

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

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

Решили эту задачу, как и всегда, внесением избыточности. Каждый из чанков хранится не на одном, а сразу на трех чанк-серверах. Соответственно, мастер-сервер в своих метаданных поддерживает таблицу размещения резервных копий. При этом (по возможности) резервные чанк-сервера выбираются в разных стойках и даже в разных подсетях. Адреса всех трех чанк-серверов для каждого чанкa мастер-сервер и передает клиенту. Откуда будет считан chunk — дело клиентской программы. Но это — чтение данных, весьма простая операция.

С модификацией данных в чанке дело обстоит сложнее. Если клиентская программа желает модифицировать записи в чанкe, она, получив от мастер-сервера адреса чанк-серверов, передает модифицируемые данные ближайшему из них, а тот — остальным двум. Чтобы процесс модификации шёл слаженно, мастер-сервер выбирает из этой троицы чанк-сервер – «хранитель» мастер-копии чанкa. Именно он первым производил модификацию. Зачем такие сложности? Представим, что одновременно тысячи клиентских программ запрашивают операцию модификации одного и того же чанкa. Чтобы этот процесс шел упорядоченно, и нужен «хранитель» мастер-копии. Он формирует специальный список — «порядок мутации» чанкa (mutation order), в котором расписаны все его последовательные модификации. Составив этот список, «хранитель» применяет его сам и передает двум остальным «резервистам». Те, применив «порядок мутаций» на копиях чанка, присылают «хранителю» подтверждение. Только после этого он подтверждает клиентской программе, что модификация прошла успешно. Стоить напомнить, что эта процедура происходит в условиях, когда любой из чанк-серверов может внезапно перестать работать.

Несмотря на простоту и изящность архитектуры, GFS имела узкое место — единственный мастер-сервер, хранящий в своей оперативной памяти все метаданные. Его отказ лишал клиентов доступа ко всем чанкам GFS. Но и здесь решение было найдено. Снэпшоты (от слова snapshots — снимки) оперативной памяти для последних операций мастер-сервера журналируются — сохраняются на диск в специальном журнале. После перезагрузки сервера последний снимок развёртывается в оперативной памяти, восстанавливая предшествующее отказу состояние. Ну а если «полетит» диск мастер-сервера? На этот случай из числа чанк-серверов назначаются теневые мастер-серверы. Им периодически передаются файлы журнала и план действий а случае гибели «командира».

Именно эта архитектура GFS и обнародовала команда Гобьова в 2003 году. В публикациях, конечно, не были раскрыты точные алгоритмы ее работы, но идея представлена столь прозрачно, что сообщество open source спустя некоторое время реализовало её открытый вариант в рамках проекта Apache Hadoop — Hadoop Distributed File System, или сокращённо HDFS.

Сам проект GFS не остался статичной реализацией рассмотренной архитектуры. Он видоизменялся вместе с ростом и развитием интернета. Спустя десятилетие в Google разработали и внедрили вторую версию GFS. Проект GFS 2.0 получил говорящее название Colossus.

Рождение Колосса

Главным пользователем первой версии GFS была поисковая система. Спустя несколько лет у Google появились другие сервисы, и количество клиентов GFS выросло. Это, в свою очередь, увеличило объём создаваемых клиентами файлов. Поскольку метаданные каждого файла мастер-сервер хранит в оперативной памяти, это вызвало проблемы: файловой системе стало не хватать памяти.

Но это ещё не все беды, обрушившиеся на голову разработчиков. Если MapReduce и исследовательские проекты обращались к GFS в пакетном режиме и небольшая задержка с ответом ничему не вредила, то почта Google, её социальная сеть, картографические сервисы и потоковое вещание видео работали с GFS в интерактивном режиме, когда даже секундное промедление недопустимо.

Чтобы устранить нехватку оперативной памяти на мастер-сервере, разработчики Colossus сделали его… распределённым. Теперь сразу несколько мастер-серверов трудились над хранением порции метаданных «в едином порыве». Вторым шагом стал переход к мультиячеечной архитектуре GFS. В типовом ЦОД Google теперь размещалось несколько ячеек. Каждая из них представляла собой подмножество чанк-серверов и распределённую «голову», состоящую из восьми или более мастер-серверов. Все ячейки внутри ЦОДа активно взаимодействовали между собой. Более того, взаимодействие было организовано между такими мультиячейками во всех ЦОДах Google.

Но изменения коснулись не только масштабируемой архитектуры GFS. Изменился размер её «базового кирпичика» — чанка. Первоначальный размер чанкa в 64 мегабайта был ориентирован на хранение индексной базы поискового гиганта. Нынешние сервисы Google зачастую оперируют меньшими объёмами данных, и оставшееся в чанке неиспользуемое пространство попросту пустовало. Разработчики Colossus уменьшили величину чанка до одного мегабайта. Конечно, теперь для хранения файлов стало требоваться больше чанков, что автоматически увеличивает объём метаданных GFS. Но с распределенным мастер-сервером это не было большой проблемой.

В результате система Colossus, заработавшая в боевом режиме в 2009 году, стала настоящим фундаментом империи Google. Фундаментом, легко выдерживающим информационный вал современного интернета.

Что будем искать? Например,ChatGPT

Мы в социальных сетях