Google File System (GFS) — распределенная файловая система, используемая компанией Google в качестве основы проприентарной, то есть не распространяемой, СУБД BigTable. GFS — кластерная система, оптимизированная для центрального хранилища данных Google и нужд поискового механизма, обладающая повышенной защитой от сбоев. Система предназначена для взаимодействия между вычислительными системами, а не между пользователем и вычислительной системой. Вся информация копируется и хранится в трёх (или более) местах одновременно, при этом система способна очень быстро находить реплицированные копии, если какая-то машина вышла из строя. Задачи автоматического восстановления после сбоя решаются с помощью программ, созданных по модели MapReduce. Является коммерческой тайной компании Google. Она несовместима с POSIX и создавалась Google для своих внутренних потребностей. В GFS файлы делятся на блоки данных по 64 МБ (англ. chunk — кусок). Предполагается, что файлы очень редко переписываются или уменьшаются в размере хранимых данных, а лишь читаются или увеличиваются в размере, посредством добавления в конец новых данных.
Идеология файловой системы GFS (Google File System) Архитектура файловой системы GFS Мастер Метаданные Взаимодействия внутри системы Операции, выполняемые мастером Устойчивость к сбоям и диагностика ошибок
В настоящее время, в условиях роста информации, возникают
задачи хранения и обработки данных очень большого объема. Поэтому эти данные
обрабатывается сразу на нескольких серверах одновременно, которые образуют
кластеры. Для упрощения работы с данными на кластерах и разрабатывают
распределенные файловые системы. Мы подробно рассмотрим пример распределенной
файловой системы Google File System, используемую компанией
Google. (Статья является, фактически, вольным и урезанным переводом оригинальной статьи ).
GFS является наиболее, наверное, известной
распределенной файловой системой. Надежное масштабируемое хранение данных крайне
необходимо для любого приложения, работающего с таким большим массивом данных,
как все документы в интернете. GFS является основной платформой хранения
информации в Google. GFS - большая распределенная файловая
система, способная хранить и обрабатывать огромные объемы информации.
GFS
строилась исходя из следующим критериев:
Файлы в GFS организованы иерархически, при помощи каталогов, как и
в любой другой файловой системе, и идентифицируются своим путем. С файлами в GFS
можно выполнять обычные операции: создание, удаление, открытие, закрытие, чтение
и запись.
Более того, GFS поддерживает резервные копии, или снимки
(snapshot). Можно создавать такие резервные копии для файлов или дерева
директорий, причем с небольшими затратами.
В системе существуют мастер-сервера и чанк-сервера, собственно,
хранящие данные. Как правило, GFS кластер состоит из одной главной машины
мастера (master) и множества машин, хранящих фрагменты файлов чанк-серверы
(chunkservers). Клиенты имеют доступ ко всем этим машинам. Файлы в GFS
разбиваются на куски - чанки (chunk, можно сказать фрагмент). Чанк имеет
фиксированный размер, который может настраиваться. Каждый такой чанк имеет
уникальный и глобальный 64 - битный ключ, который выдается мастером при создании
чанка. Чанк-серверы хранят чанки, как обычные Linux файлы, на локальном жестком
диске. Для надежности каждый чанк может реплицироваться на другие чанк-серверы.
Обычно используются три реплики.
Мастер отвечает за работу с метаданными всей
файловой системы. Метаданные включают в себя пространства имен, информацию о
контроле доступа к данным, отображение файлов в чанки, и текущее положение
чанков. Также мастер контролирует всю глобальную деятельность системы такую, как
управление свободными чанками, сборка мусора (сбор более ненужных чанков) и
перемещение чанков между чанк-серверами. Мастер постоянно обменивается
сообщениями (HeartBeat messages) с чанк-серверами, чтобы отдать инструкции, и
определить их состояние (узнать, живы ли еще).
Клиент взаимодействует с
мастером только для выполнения операций, связанных с метаданными. Все операции с
самими данными производятся напрямую с чанк-серверами. GFS - система не
поддерживает POSIX API, так что разработчикам не пришлось связываться с VNode
уровнем Linux.
Разработчики не используют кеширование данных, правда,
клиенты кешируют метаданные. На чанк-серверах операционная система Linux и так
кеширует наиболее используемые блоки в памяти. Вообще, отказ от кеширования
позволяет не думать о проблеме валидности кеша (cache coherence).
Использование одного мастера существенно упрощает
архитектуру системы. Позволяет производить сложные перемещения чанков,
организовывать репликации, используя глобальные данные. Казалось бы, что наличие
только одного мастера должно являться узким местом системы, но это не так.
Клиенты никогда не читают и не пишут данные через мастера. Вместо этого они
спрашивают у мастера, с каким чанк-сервером они должны контактировать, а далее
они общаются с чанк-серверами напрямую.
Рассмотрим, как происходит чтение
данных клиентом. Сначала, зная размер чанка,
имя файла и смещение
относительно начала файла, клиент определяет номер чанка внутри файла. Затем он
шлет запрос мастеру, содержащий имя файла и номер чанка в этом файле. Мастер
выдает чанк-серверы, по одному в каждой реплике, которые хранят нужный нам чанк.
Также мастер выдает клиенту идентификатор чанка.
Затем клиент решает, какая
из реплик ему нравится больше (как правило та, которая ближе), и шлет запрос,
состоящий из чанка и смещения относительно начала чанка. Дальнейшее чтения
данных, не требует вмешательства мастера. На практике, как правило, клиент в
один запрос на чтение включает сразу несколько чанков, и мастер дает координаты
каждого из чанков в одном ответе.
Размер чанка является важной
характеристикой системы. Как правило, он устанавливается равным 64 мегабайт, что
гораздо больше, чем размер блока в обычной файловой системе. Понятно, что если
необходимо хранить много файлов, размеры которых меньше размера чанка, то будем
расходоваться много лишней памяти. Но выбор такого большого размера чанка
обусловлен задачами, которые приходится компании Google решать на своих
кластерах. Как правило, что-то считать приходится для всех документов в
интернете, и поэтому файлы в этих задачах очень большого размера.
Мастер хранит три важных вида метаданных: пространства
имен файлов и чанков, отображение файла в чанки и положение реплик чанков. Все
метаданные хранятся в памяти мастера. Так как метаданные хранятся в памяти,
операции мастера выполняются быстро. Состояние дел в системе мастер узнает
просто и эффективно. Он выполняется сканирование чанк-серверов в фоновом режиме.
Эти периодические сканирования используются для сборки мусора, дополнительных
репликаций, в случае обнаружения недоступного чанк-сервера и перемещение чанков,
для балансировки нагрузки и свободного места на жестких дисках
чанк-серверов.
Мастер отслеживает положение чанков. При старте чанк-сервера
мастер запоминает его чанки. В процессе работы мастер контролирует все
перемещения чанков и состояния чанк-серверов. Таким образом, он обладает всей
информацией о положении каждого чанка.
Важная часть метаданных - это лог
операций. Мастер хранит последовательность операций критических изменений
метаданных. По этим отметкам в логе операций, определяется логическое время
системы. Именно это логическое время определяет версии файлов и чанков.
Так
как лог операций важная часть, то он должен надежно храниться, и все изменения в
нем должны становиться видимыми для клиентов, только когда изменятся метаданные.
Лог операций реплицируется на несколько удаленных машин, и система реагирует на
клиентскую операцию, только после сохранения этого лога на диск мастера и диски
удаленных машин.
Мастер восстанавливает состояние системы, исполняя лог
операций. Лог операций сохраняет относительно небольшой размер, сохраняя только
последние операции. В процессе работы мастер создает контрольные точки, когда
размер лога превосходит некоторой величины, и восстановить систему можно только
до ближайшей контрольной точки. Далее по логу можно заново воспроизвести
некоторые операции, таким образом, система может откатываться до точки, которая
находится между последней контрольной точкой и текущем временем.
Выше была описана архитектура системы,
которая минимизирует вмешательства мастера в выполнение операций. Теперь же
рассмотрим, как взаимодействуют клиент, мастер и чанк-серверы для перемещения
данных, выполнения атомарных операций записи, и создания резервной копии
(snapshot).
Каждое изменение чанка должно дублироваться на всех репликах и
изменять метаданные. В GFS мастер дает чанк во владение(lease)
одному из серверов, хранящих этот чанк. Такой сервер называется первичной
(primary) репликой. Остальные реплики объявляются вторичными (secondary).
Первичная реплика собирает последовательные изменения чанка, и все реплики
следуют этой последовательности, когда эти изменения происходят.
Механизм
владения чанком устроен таким образом, чтобы минимизировать нагрузку на
мастера. При выделении памяти сначала выжидается 60 секунд. А затем, если
потребуется первичная реплика может запросить мастера на расширение этого
интервала и, как правило, получает положительный ответ. В течение этого
выжидаемого периода мастер может отменить изменения.
Рассмотрим подробно
процесс записи данных. Он изображен по шагам на рисунке, при этом тонким линиям
соответствуют потоки управления, а жирным потоки данных.
Мастер важное звено в системе. Он
управляет репликациями чанков: принимает решения о размещении, создает новые
чанки, а также координирует различную деятельность внутри системы для
сохранения чанков полностью реплицированными, балансировки нагрузки на
чанк-серверы и сборки неиспользуемых ресурсов.
В отличие от большинства
файловых систем GFS не хранит состав файлов в директории. GFS
логически представляет пространство имен, как таблицу, которая отображает
каждый путь в метаданные. Такая таблица может эффективно храниться в памяти в
виде бора (словаря этих самых путей). Каждая вершина в этом дереве
(соответствует либо абсолютному пути к файлу, либо к директории) имеет
соответствующие данные для блокировки чтения и записи(read write lock). Каждое
операция мастера требует установления некоторых блокировок. В этом месте в
системе используются блокировки чтения-записи. Обычно, если операция работает с
/d1/d2/.../dn/leaf, то она устанавливает блокировки на чтение на /d1,
/d1/d2, ..., d1/d2/.../dn и блокировку, либо на чтение, либо на запись на
d1/d2/.../dn/leaf. При этом leaf может быть как директорией, так и
файлом.
Покажем на примере, как механизм блокировок может предотвратить
создание файла /home/user/foo во время резервного копирования
/home/user в /save/user. Операция резервного копирования
устанавливает блокировки на чтение на /home и /save, а так же
блокировки на запись на /home/user и /save/user. Операция создания
файла требует блокировки на чтение /home и /home/user, а также
блокировки на запись на /home/user/foo. Таким образом, вторая операция не
начнет выполняться, пока не закончит выполнение первая, так как есть
конфликтующая блокировка на /home/user. При создании файла не требуется
блокировка на запись родительской директории, достаточно блокировки на чтение,
которая предотвращает удаление этой директории.
Кластеры GFS, являются
сильно распределенными и многоуровневыми. Обычно, такой кластер имеет сотни
чанк-серверов, расположенных на разных стойках. Эти сервера, вообще говоря,
доступны для большого количества клиентов, расположенных в той же или другой
стойке. Соединения между двумя машинами из различных стоек может проходить через
один или несколько свитчей. Многоуровневое распределение представляет очень
сложную задачу надежного, масштабируемого и доступного распространения
данных.
Политика расположения реплик старается удовлетворить следующим
свойствам: максимизация надежности и доступности данных и максимизация
использование сетевой пропускной способности. Реплики должны быть расположены не
только на разных дисках или разных машинах, но и более того на разных стойках.
Это гарантирует, что чанк доступен, даже если целая стойка повреждена или
отключена от сети. При таком расположении чтение занимает время приблизительно
равное пропускной способности сети, зато поток данных при записи должен пройти
через различные стойки.
Когда мастер создает чанк, он выбирает где разместить
реплику. Он исходит из нескольких факторов:
Авторы системы считают
одной из наиболее сложных проблем частые сбои работы компонентов системы.
Количество и качество компонентов делают эти сбои не просто исключением, а
скорее нормой. Сбой компонента может быть вызван недоступностью этого компонента
или, что хуже, наличием испорченных данных. GFS поддерживает систему в
рабочем виде при помощи двух простых стратегий: быстрое восстановление и
репликации.
Быстрое восстановление - это, фактически, перезагрузка машины.
При этом время запуска очень маленькое, что приводит к маленькой заминке, а
затем работа продолжается штатно. Про репликации чанков уже говорилось выше.
Мастер реплицирует чанк, если одна из реплик стала недоступной, либо повредились
данные, содержащие реплику чанка. Поврежденные чанки определяется при помощи
вычисления контрольных сумм.
Еще один вид репликаций в системе, про который
мало было сказано - это репликация мастера. Реплицируется лог операций и
контрольные точки (checkpoints). Каждое изменение файлов в системе происходит
только после записи лога операций на диски мастером, и диски машин, на которые
лог реплицируется. В случае небольших неполадок мастер может перезагрузиться. В
случае проблем с жестким диском или другой жизненно важной инфраструктурой
мастера, GFS стартует нового мастера, на одной из машин, куда реплицировались
данные мастера. Клиенты обращаются к мастеру по DNS, который может быть
переназначен новой машине. Новый мастер является тенью старого, а не точной
копией. Поэтому у него есть доступ к файлам только для чтения. То есть он не
становится полноценным мастером, а лишь поддерживает лог операций и другие
структуры мастера.
Важной частью системы является возможность поддерживать
целостность данных. Обычный GFS кластер состоит из сотен машин, на
которых расположены тысячи жестких дисков, и эти диски при работе с завидным
постоянством выходят из строя, что приводит к порче данных. Система может
восстановить данные с помощью репликаций, но для этого необходимо понять
испортились ли данные. Простое сравнение различных реплик на разных
чанк-серверах является неэффективным. Более того, может происходить
несогласованность данных между различными репликами, ведущая к различию данных.
Поэтому каждый чанк-сервер должен самостоятельно определять целостность данных.
Каждый чанк разбивается на блоки длиной 64 Кбайт. Каждому такому
блоку соответствует 32-битная контрольная сумма. Как и другие метаданные
эти суммы хранятся в памяти, регулярно сохраняются в лог, отдельно от данных
пользователя.
Перед тем как считать данные чанк-сервер проверяет контрольные
суммы блоков чанка, которые пересекаются с затребованными данными пользователем
или другим чанк-сервером. То есть чанк-сервер не распространяет испорченные
данные. В случае несовпадения контрольных сумм, чанк-сервер возвращает ошибку
машине, подавшей запрос, и рапортует о ней мастеру. Пользователь может считать
данные из другой реплики, а мастер создает еще одну копию из данных другой
реплики. После этого мастер дает инструкцию этому чанк-серверу об удалении этой
испорченной реплики.
При добавлении новых данных, верификация контрольных
сумм не происходит, а для блоков записывается новые контрольные суммы. В случае
если диск испорчен, то это определится при попытке чтения этих данных. При
записи чанк-сервер сравнивает только первый и последний блоки, пересекающиеся с
границами, в которые происходит запись, поскольку часть данных на этих блоках не
перезаписывается и необходимо проверить их целостность.