Файловый сервер Plan 9

Кен Томпсон
ken@plan9.bell-labs.com

АБСТРАКТНО

В этом документе описана структуру и работа файловых серверов Plan 9. Хотя речь идет о нашем главном файловом сервере Emelie, код также является основой пользовательского уровня файлового сервера kfs.

Введение

Файловый сервер Emelie — это одна из старейших частей системного программного обеспечения, которое все еще используется в Plan 9. Он развился из пользовательской программы, которая обслуживала последовательные линии на многопроцессорной машине Sequent. Хоть текущая реализация не является ни чистой, ни портабильной, она подходит к требованиям конкретного набора компьютеров и их устройств.

Структура процессов

Сервер файловой системы Plan 9 происходит от древней версии ядра Plan 9. Ядро поддерживает: управление процессами, синхронизацию, блокировку и распределение памяти. Отсутствует реализация пользовательских процессов и виртуальной памяти.

Структура файловой системы сервера представляет собой набор процессов ядра, синхронизирующий большую часть передач сообщений. Emelie содержит 26 процессов 10-ти типов.

Количество
Название
Функция
15
srv
Главные процессы файловой системы сервера
1
rah
Блочные read-ahead процессы
1
scp
Процесс sync
1
wcp
Копия WORM процесса
1
con
Консольный процесс
1
ilo
Процесс протокола IL
1
ilt
Процесс таймера IL
2
ethi
Процесс ввода Ethernet
2
etho
Процесс вывода Ethernet
1
flo
Процесс флоппи диска

Серверные процессы

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

Блок данных в устройстве является единицей хранения:

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

Основная структура данных процесса srv является каталоговой записью. Это эквивалент индексного дескриптора Unix, она определяет набор блочных адресов, который указывает файл это, или каталог. В отличие от индексного дескриптора, каталоговая запись также содержит имя файла или каталога:

Каждая каталоговая запись хранит имя файла или каталога, режим защиты, времена доступа, идентификатор пользователя, идентификатор группы, а также информацию об адресации. Запись wuid указывает идентификатор пользователя, совершившего последнюю запись, а size — размер файла в байтах. Первые 6 блоков файла занимает массив dblock. Если файл имеет больший размер, то косвенный блок распределяется таким образом, что содержит следующие BUFSIZE/sizeof(long) блоков файла. Адрес косвенного блока хранится в элементе структуры под названием iblock. Если файл еще больше, то он содержит двойной косвенный блок, указывающий на составляющие косвенные блоки. Адрес двойного косвенного блока хранится в diblock и может указывать на другие (BUFSIZE/sizeof(long))2 блоки данных. Максимальный адресуемый размер файла около 275 GB. Есть и наименьшее ограничение — 232 B, поскольку длина файла поддерживается типом long. Таким образом, даже неаккуратное использование длинных арифметик ограничивается 231 B. Эти цифры основаны на сервере Emelie, который имеет размер блока 16 KB и sizeof(long) равняется 4. Если изменить размер блока, эти цифры будут отличаться.

Описания косвенного и двойного косвенного блоков:

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

Устройство, на котором находятся блоки, является подразумеваемым и происходит от сообщения attach протокола 9P. Это сообщение определяет имя устройства, содержащего корневой каталог.

Буферный кеш

Когда загружен файловый сервер, вся не используемая память распределяется в пуле буферного кеша. В буферном пуле существует две главных операции. Getbuf выполняет поиск буфера, ассоциированного с конкретным блоком на конкретном устройстве. Возвращаемый буфер блокирован, так что вызывающий имеет исключительное использование. Если запрошенный буфер отсутствует в пуле, другой буфер подвергается переразметке и данные считываются из него. Putbuf выполняет разблокировку, если содержимое буфера обозначено как модифицированное, записывается на устройство и после этого подвергается переразметке. Если необходимо специальное распределение или сброс кеша процессора, которые должны быть выполнены посредством физического устройства ввода-вывода для доступа к буферу, то это выполняется между getbuf и putbuf. Содержимое буфера никогда не трогается, за исключением ситуации, когда он заблокирован между вызовами getbuf и putbuf.

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

Блочные устройства

Блочное устройство системы ввода-вывода является не чем иным как протокольным стеком фильтров. Существует набор псевдо-устройств, рекурсивно связанных с другими псевдо-устройствами и настоящими устройствами. Протокольный стек компилируется из конфигурационной строки, которая определяет псевдо-устройства и просто устройства. Каждое псевдо-устройство и устройство имеет набор записей, указывающих соответствия операций, которые файловая система требует от устройств. Наиболее важными операциями являются read, write и size.

Стек устройств может быть описан синтаксисом конфигурационной строки, определяющей стек. Конфигурационные строки используются во время установки файловой системы. За описанием смотрите fsconfig(8). В следующем рекурсивном определении, D представляет строку, описывающую блочное устройство.

D = (DD...)
Это набор устройств, соединенных для формирования одного устройства. Размер соединенного устройства равен сумме размеров всех под-устройств.
D = [DD...]
Это чередование индивидуальных устройств. Если в списке есть N устройств, тогда псевдо-устройство является N-путевым блочным чередованием под-устройств. Размер чередуемого устройства равен сумме минимального под-устройства N раз.
D = pDN1.N2
Это раздел под-устройства. Под-устройство разделено на 100 одинаковых частей. Если размер под-устройства не делим на 100, тогда на верхушку будет выброшен какой-то мусор. Псевдо-устройство начинается с N1-й части и продолжается до N2 частей. Так, pD67.33 будет последним третьим устройством D.
D = fD
Это фальшивое WORM (write-once-read-many, т.е. «однократная-запись-многократное-чтение») устройство, сымитированное вторым устройством чтения-записи. Второе устройство разделено на набор блочных флагов и блоков. Флаги используются для генерации ошибок, если блок записан дважды или производится чтение без предыдущей записи.
D = cDD
Это не что иное как кеш/WORM устройство, созданное кешем устройства чтения-записи и WORM устройством. Подробнее об этом чуть позже.
D = o
Это файловая система dump — двухуровневая иерархия всех дампов, отправленных на кеш/WORM. Корневой каталог файловой системы кеш/WORM имеет атрибут «только для чтения» и название от даты создания, например, дамп, полученный 18 февраля 1995 года будет назван /1995/0218 в псевдо-устройстве. /1995/02181 будет вторым дампом, полученным в этот же день.
D = wN1.N2
Это SCSI диск на контроллере N1 и объект N2.
D = lN1.N2
То же, что и w, но один блок из SCSI диска перемещен для переименования.
D = j(D1D2*)D3
D1 — это накопитель со сменой дисков интерфейса SCSI. D2 — это SCSI устройства в накопителе и D3 — это демонтированные участки в накопителе. D1 и D2 должны быть w. D3 должны быть псевдо-устройствами w или l устройств.

Для обоих устройств w и r любые номера конфигурации могут быть заменены итератором формы <N1-N2>. Так,

это чередующиеся SCSI диски в SCSI объекте от 2 до 6, SCSI контроллер 0. Основная файловая система в Emelie описана следующей конфигурационной строкой: Это драйвер кеш/WORM. Кеш — это три чередующихся диска на SCSI контроллере 1, объекты 0, 1, 2, 3, 4 и 5. WORM-половина кеш/WORM — 474 накопителей со сменой дисков.

Процессы read-ahead

Существует набор процессов файловой системы под названием rah, он ожидает сообщения, содержащие устройство и блочный адрес. Когда поступает сообщение, процесс считывает определенный блок из устройства. Эта операция выполняется посредством вызовов getbuf и putbuf, что дает возможность использования блоков после некоторого времени их нахождения в буферном кеше. В противном случае есть вероятность, что блоки могут быть отвергнуты перед использованием.

Сообщения для процессов read-ahead генерируются специальным сервером процессов. Сервер процессов сохраняет относительную отметку блока в каждом открытом файле. Каждый раз, когда открытый файл считывает относительный блок, следующие 110 блочных адресов файла отправляются процессам read-ahead, при этом относительный блок получает метку 100. Начальный относительный блок установлен как 1. Если открыт файл и считано всего лишь несколько байтов, то дальше никаких считываний не предвидится (и не проводится), пока относительный блок установлен как 1 и считывается лишь блочное смещение 0. Это функция должна предохранять некоторые довольно общие действия, как например:

захламляющие файловую систему процессами read-ahead, которые никогда не будут использованы.

Драйвер кеш/WORM

Драйвер кеш/WORM (cache/WORM — cw) является одним из самых больших и сложных драйверов устройств в файловом сервере. В него входят четыре устройства. Драйвер осуществляет чтение/запись псевдо-устройства (cw-устройства) и только чтение псевдо-устройства (dump) путем выполнения операций над своими двумя составляющими устройствами: чтение-запись c-устройство и однократная-запись-многократное-чтение w-устройство. Номера блоков на четырех устройствах достаточно точные, хотя cw адреса и w адреса — высоко согласованные.

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

Часть карты c-устройства состоит из блоков групп записей. Описания приведены ниже.

Для каждого блока в разделе данных c-устройства есть лишь одна структура записи. Группа содержит все w-адреса, у которых одинаковый хэш код. Существует большое количество групп, которые устанавливаются в блоке. Чтобы иметь необходимое количество записей, существует достаточно блоков. Записи в группе поддерживаются в FIFO порядке с age переменной и увеличивающим age генератором. Когда age генератор доходит до переполнения, все age записи в группе масштабируются до нуля.

Следующие шаги конвертируют w-адрес в c-адрес. Группа обнаруживается при помощи:

После того как нужная группа найдена, выполняется линейный поиск записи с группой и waddr.

Штатной переменной в записи является одна из следующих:

Каждый w-адрес имеет состояние. Блоки, которые находятся не на c-устройстве, имеют неявное состояние Cnone. Состояние Cread предназначено для блоков, которые имеют одинаковые с соответствующим блоком w-устройства данные. Так как c-устройство намного быстрее чем w-устройство, Cread блоки хранятся так долго, сколько это возможно и их использование предпочтительнее чем чтение w-устройства. Когда нужно пространство для новых данных, Cread блоки должны сбрасываться из c-устройства. Состояние Cwrite — когда c-устройство содержит данные, новей чем соответствующий блок w-устройства. Это происходит когда записано одно из состояний: Cnone, Cread или Cwrite. Состояние Cdirty — когда c-устройство содержит данные, новей чем соответствующий блок w-устройства, который никогда не был записан. Это происходит когда новый блок размещается в свободном пространстве w-устройства.

Блоки Cwrite и Cdirty создаются и никогда не удаляются. Если же выполняется операция преобразования этих блоков, c-устройство будет постепенно заполнятся и перестанет функционировать. Один раз в день, и посредством выполнения команды, берется дамп cw-устройства. Назначение дампа — поставить в очередь записи, которые были отведены c-устройством для записи на w-устройство. Так как w-устройство — это WORM, блоки не могут быть переписаны. Блоки, которые уже записаны на WORM, должны быть перемещены в неиспользуемую часть w-устройства. Это блоки с состоянием Cwrite.

Алгоритм дампа таков: а) Длина дерева на cw-устройстве зависит от того, какие посещенные блоки были модифицированы со времени последнего дампа. Это блоки с состояниями Cwrite и Cdirty. Есть возможность ограничения поиска блоков: так как в каталог, содержащий модифицируемый файл, должен произойти доступ, после модификации файла происходит установка времени модификации каталога, таким образом блок, содержащий его, — будет записан. Каталог, содержащий этот каталог, должен быть модифицирован таким же образом. Прохождение по дереву каталогов не занимает много времени. б) Все Cwrite блоки, найденные при древовидном поиске перемещаются в новые чистые блоки на w-устройстве и конвертируются в состояние Cdump. Все Cdirty блоки конвертируются в состояние Cdump без перемещения. Таким образом, все модифицированные блоки в cw-устройстве имеют w-адреса, указывающие на не записанные WORM блоки. Эти блоки отмечаются для последующей записи на w-устройство с состоянием Cdump. в) Все открытые файлы, указывающие на модифицированные блоки, открываются вновь для указания соответствующих перемещаемых блоков. Это вызывает модификации каталогов, идущих за открытыми файлами. Таким образом инвариант, обсужденный в а) обслуживается. д) Фоновый процесс дампинга медленно проходит по карте c-устройства и записывает все блоки с состоянием Cdump.

Дампу требуются считанные минуты для прохождения дерева и отметки блоков. Он может занимать часы при записи отмеченных блоков на WORM. Если отмеченный блок был перезаписан перед тем как старая копия записана на WORM, то он должен быть принудительно записан на WORM перед перезаписью. Проблемы нет, если другой дамп был взят перед тем как первый закончен. Ново отмеченные блоки добавляются к отмеченным слева от первого дампа.

Если при записи отмеченного блока на WORM происходит ошибка, то состояние дампа конвертируется в Cdump1, в такой ситуации необходимо ручное вмешательство. (Смотрите описание команды cwcmd mvstate в fs(8)). Эти блоки могут вновь записываться, если их состояние конвертировать обратно в Cdump. Также они могут быть конвертированы в Cwrite, так что они будут занимать новые адреса в следующем дампе. В большинстве других случаев, Cdump1 блок ведет себя подобно Cwrite.

Процессы Sync Copy и WORM Copy

Процесс scp запускается каждые 10 секунд, при этом данные записываются в блоки буферного кеша, которые должны быть модифицированы. Это происходит автоматически в важных консольных командах типа halt и dump.

Процесс wcp также запускается каждые 10 секунд и пробует копировать dump блок из кеша в WORM. Копирование происходит на высокой скорости так как копируются dump блоки и нет конкуренции за WORM устройство. Если же есть конкуренция за WORM устройство или больше нет блоков для копирования, процесс переходит в режим ожидания на 10 секунд перед следующим просмотром.

Устройство с автоматической сменой дисков HP WORM состоит из 238 дисков, разделенных на 476 сторон или участков. Участок 0 — это сторона А диска 0. Участок 1 — это сторона А диска 1. Участок 238 — это сторона В диска 0. В Emelie главная файловая система сконфигурирована на обоих сторонах первых 237 дисков, участков 0-236 и 238-474.

Драйверы протокола 9P

Чтобы появиться в своей очереди ввода, описанный файловый сервер находится в ожидании сообщений протокола 9P. Он обрабатывает каждое сообщение и отправляет ответ создателю. Существуют группы процессов, выполняющие ввод-вывод в некоторых сетях или устройствах, при этом результирующие сообщения отправляются в очередь файловой системы.

Для выполнения ввода и вывода Ethernet используются два набора процессов: ethi и etho. Эти процессы отправляют Ethernet сообщения процессам ilo и ilt, которые делают надежную дейтаграмму протокола IL над пакетами IP.

И наконец, последний процесс Emelie — con, считывает консоль и вызывает внутренние подпрограммы для выполнения введенных команд. Так как это лишь один процесс, в данный момент времени может выполняться только одна команда. За описанием команд, доступных в консоли, обращайтесь к man-странице fs(8).

Copyright © 2000 Lucent Technologies Inc. All rights reserved.
Copyright © 2003 Перевод Андрей С. Кухар.