Добавлен: 29.10.2018
Просмотров: 48111
Скачиваний: 190
4.3. Реализация файловой системы
331
Рис. 4.14. Ситуация, сложившаяся: а — перед созданием связи; б — после создания связи;
в — после того как владелец (исходный пользователь) удаляет файл
другому файлу, связь, принадлежащая пользователю B, будет указывать на неверный
файл (новый, а не тот, для которого она создавалась). По счетчику в i-узле система
сможет увидеть, что файл по-прежнему используется, но простого способа найти
в каталогах все записи, относящиеся к этому файлу, чтобы их удалить, у нее не будет.
Указатели на каталоги не могут быть сохранены в i-узле, поскольку их количество
может быть неограниченным.
Единственное, что можно сделать, — это удалить запись в каталоге пользователя C,
но оставить нетронутым i-узел, установив его счетчик связей в 1 (см. рис. 4.14, в).
В результате возникнет ситуация, когда B является единственным пользователем,
имеющим в своем каталоге ссылку на файл, которым владеет пользователь C. Если
в системе ведется учет использования ресурсов или выделяются какие-то квоты,
то пользователь C будет по-прежнему получать счета за этот файл, до тех пор пока
пользователь B не примет решение его удалить. Тогда счетчик будет сброшен до нуля,
а файл — удален.
При использовании символической ссылки такой проблемы не возникает, поскольку
указатель на i-узел есть только у владельца файла. А у пользователей, создавших ссыл-
ку на файл, есть только пути к файлам и нет указателей на i-узлы. Файл при удалении
его владельцем уничтожается. Последующие попытки использовать этот файл при по-
мощи символической ссылки не будут иметь успеха, так как система не сможет найти
файл. Удаление символической ссылки никак на файл не повлияет.
Проблема использования символических ссылок заключается в дополнительных
издержках. Файл, в котором содержится путь, должен быть прочитан, затем путь
должен быть разобран и покомпонентно пройден, пока не будет достигнут i-узел. Все
эти действия могут потребовать многократных дополнительных обращений к диску.
Более того, для каждой символической ссылки нужен дополнительный i-узел, равно
как и дополнительный дисковый блок для хранения пути, хотя, если имя пути не
слишком длинное, система в порядке оптимизации может хранить его в самом i-узле.
Преимущество символических ссылок заключается в том, что они могут использовать-
ся для связи с файлами, которые находятся на удаленных компьютерах в любой точке
земного шара. Для этого нужно лишь в дополнение к пути к файлу указать сетевой
адрес машины, на которой он находится.
332
Глава 4. Файловые системы
Символические или иные ссылки вызывают и еще одну проблему. Когда разрешается
использование ссылок, могут появиться два и более путей к файлу. Программы, на-
чинающие свою работу с заданного каталога и ведущие поиск всех файлов в этом ка-
талоге и его подкаталогах, могут обнаруживать файл, на который имеются ссылки, по
нескольку раз. Например, программа, архивирующая все файлы в каталоге и всех его
подкаталогах на магнитную ленту, может сделать множество копий файла, на который
имеются ссылки. Более того, если потом эта лента будет прочитана на другой машине,
то вместо создания ссылок на файл он может быть повторно скопирован, если только
программа архивации не окажется достаточно «умной».
4.3.5. Файловые системы с журнальной структурой
На современные файловые системы оказывают влияние и технологические изменения,
в частности, постоянно растущая скорость центральных процессоров, увеличение ем-
кости и удешевление дисковых накопителей (при не столь впечатляющем увеличении
скорости их работы), рост в геометрической прогрессии объема оперативной памяти.
Единственным параметром, не демонстрирующим столь стремительного роста, остает-
ся время позиционирования блока головок на нужный цилиндр диска (за исключением
твердотельных дисков, у которых данный параметр отсутствует).
Сочетание всех этих факторов свидетельствует о том, что у многих файловых систем
возникает узкое место в росте производительности. Во время исследований, проведен-
ных в университете Беркли, была предпринята попытка смягчить остроту этой пробле-
мы за счет создания совершенно нового типа файловой системы — LFS (Log-structured
File System — файловая система с журнальной структурой). Этот раздел будет посвя-
щен краткому описанию работы LFS. Более полное изложение вопроса можно найти
в исходной статье по LFS Розенблюма и Остераута (Rosenblum and Ousterhout, 1991).
В основу LFS заложена идея о том, что по мере повышения скорости работы цен-
тральных процессоров и увеличения объема оперативной памяти существенно по-
вышается и уровень кэширования дисков. Следовательно, появляется возможность
удовлетворения весьма существенной части всех дисковых запросов на чтение прямо
из кэша файловой системы без обращения к диску. Из этого наблюдения следует, что
в будущем основную массу обращений к диску будут составлять операции записи,
поэтому механизм опережающего чтения, применявшийся в некоторых файловых
системах для извлечения блоков еще до того, как в них возникнет потребность, уже не
дает значительного прироста производительности.
Усложняет ситуацию то, что в большинстве файловых систем запись производится
очень малыми блоками данных. Запись малыми порциями слишком неэффективна,
поскольку записи на диск, занимающей 50 мкс, зачастую предшествуют позициони-
рование на нужный цилиндр, на которое затрачивается 10 мс, и ожидание подхода под
головку нужного сектора, на что уходит 4 мс. При таких параметрах эффективность
работы с диском падает до долей процента.
Чтобы понять, откуда берутся все эти мелкие записи, рассмотрим создание нового
файла в системе UNIX. Для записи этого файла должны быть записаны i-узел для ка-
талога, блок каталога, i-узел для файла и сам файл. Эти записи могут быть отложены,
но если произойдет сбой до того, как будут выполнены все записи, файловая система
столкнется с серьезными проблемами согласованности данных. Поэтому, как правило,
записи i-узлов производятся немедленно.
4.3. Реализация файловой системы
333
Исходя из этих соображений разработчики LFS решили переделать файловую систему
UNIX таким образом, чтобы добиться работы диска с полной пропускной способно-
стью, даже если объем работы состоит из существенного количества небольших про-
извольных записей. В основу была положена идея структурировать весь диск в виде
очень большого журнала.
Периодически, когда в этом возникает особая надобность, все ожидающие осуществле-
ния записи, находящиеся в буфере памяти, собираются в один непрерывного сегмент
и в таком виде записываются на диск в конец журнала. Таким образом, отдельный
сегмент может вперемешку содержать i-узлы, блоки каталога и блоки данных. В начале
каждого сегмента находится сводная информация, в которой сообщается, что может
быть найдено в этом сегменте. Если средний размер сегмента сможет быть доведен
примерно до 1 Мбайт, то будет использоваться практически вся пропускная способ-
ность диска.
В этой конструкции по-прежнему используются i-узлы той же структуры, что и в UNIX,
но теперь они не размещаются в фиксированной позиции на диске, а разбросаны по
всему журналу. Тем не менее, когда определено местоположение i-узла, местополо-
жение блоков определяется обычным образом. Разумеется, теперь нахождение i-узла
значительно усложняется, поскольку его адрес не может быть просто вычислен из его
i-номера, как в UNIX. Для поиска i-узлов ведется массив i-узлов, проиндексированный
по i-номерам. Элемент i в таком массиве указывает на i-узел на диске. Массив хранится
на диске, но также подвергается кэшированию, поэтому наиболее интенсивно исполь-
зующиеся фрагменты большую часть времени будут находиться в памяти.
Подытоживая все ранее сказанное: все записи сначала буферизуются в памяти, и пе-
риодически все, что попало в буфер, записывается на диск в единый сегмент в конец
журнала. Открытие файла теперь состоит из использования массива для определения
местоположения i-узла для этого файла. После определения местоположения i-узла из
него могут быть извлечены адреса блоков. А все блоки будут находиться в сегментах,
расположенных в различных местах журнала.
Если бы диски были безразмерными, то представленное описание на этом и закон-
чилось бы. Но существующие диски не безграничны, поэтому со временем журнал
займет весь диск и новые сегменты не смогут быть записаны в него. К счастью, многие
существующие сегменты могут иметь уже ненужные блоки. К примеру, если файл
перезаписан, его i-узел теперь будет указывать на новые блоки, но старые блоки все
еще будут занимать пространство в ранее записанных сегментах.
Чтобы справиться с этой проблемой, LFS использует очищающий поток, который за-
нимается тем, что осуществляет круговое сканирование журнала с целью уменьшения
его размера. Сначала он считывает краткое содержание первого сегмента журнала,
чтобы увидеть, какие i-узлы и файлы в нем находятся. Затем проверяет текущий массив
i-узлов, чтобы определить, актуальны ли еще i-узлы и используются ли еще файловые
блоки. Если они уже не нужны, то информация выбрасывается. Те i-узлы и блоки,
которые еще используются, перемещаются в память для записи в следующий сегмент.
Затем исходный сегмент помечается как свободный, и журнал может использовать его
для новых данных. Таким же образом очищающий поток перемещается по журналу,
удаляя позади устаревшие сегменты и помещая все актуальные данные в память для их
последующей повторной записи в следующий сегмент. В результате диск становится
большим кольцевым буфером с пишущим потоком, добавляющим впереди новые сег-
менты, и очищающим потоком, удаляющим позади устаревшие сегменты.
334
Глава 4. Файловые системы
Управление использованием блоков на диске в этой системе имеет необычный харак-
тер, поскольку, когда файловый блок опять записывается на диск в новый сегмент,
должен быть найден i-узел файла (который находится где-то в журнале), после чего
он должен быть обновлен и помещен в память для записи в следующий сегмент. Затем
должен быть обновлен массив i-узлов, чтобы в нем присутствовал указатель на новую
копию. Тем не менее такое администрирование вполне осуществимо, и результаты из-
мерения производительности показывают, что все эти сложности вполне оправданны.
Результаты замеров, приведенные в упомянутой ранее статье, свидетельствуют о том,
что при малых записях LFS превосходит UNIX на целый порядок, обладая при этом
производительностью чтения и записи больших объемов данных, которая по крайней
мере не хуже, чем у UNIX.
4.3.6. Журналируемые файловые системы
При всей привлекательности идеи файловых систем с журнальной структурой
они не нашли широкого применения отчасти из-за их крайней несовместимости
с существующими файловыми системами. Тем не менее одна из позаимствованных
у них идей — устойчивость к отказам — может быть внедрена и в более привычные
файловые системы. Основной принцип заключается в журналировании всех наме-
рений файловой системы перед их осуществлением. Поэтому, если система терпит
аварию еще до того, как у нее появляется возможность выполнить запланированные
действия, после перезагрузки она может посмотреть в журнал, определить, что она
собиралась сделать на момент аварии, и завершить свою работу. Такие файловые си-
стемы, которые называются журналируемыми файловыми системами, нашли свое
применение. Журналируемыми являются файловая система NTFS, разработанная
Microsoft, а также файловые системы Linux ext3 и ReiserFS. В OS X журналируемая
файловая система предлагается в качестве дополнительной. Далее будет дано краткое
введение в эту тему.
Чтобы вникнуть в суть проблемы, рассмотрим заурядную, часто встречающуюся опе-
рацию удаления файла. Для этой операции в UNIX нужно выполнить три действия:
1. Удалить файл из его каталога.
2. Освободить i-узел, поместив его в пул свободных i-узлов.
3. Вернуть все дисковые блоки файла в пул свободных дисковых блоков.
В Windows требуются аналогичные действия. В отсутствие отказов системы порядок
выполнения этих трех действий не играет роли, чего нельзя сказать о случае возник-
новения отказа. Представьте, что первое действие завершено, а затем в системе возник
отказ. Не станет файла, из которого возможен доступ к i-узлу и к блокам, занятым
данными файла, но они не будут доступны и для переназначения — они превратятся
в ничто, сокращая объем доступных ресурсов. А если отказ произойдет после второго
действия, то будут потеряны только блоки.
Если последовательность действий изменится и сначала будет освобожден i-узел,
то после перезагрузки системы его можно будет переназначить, но на него будет
по-прежнему указывать старый элемент каталога, приводя к неверному файлу. Если
первыми будут освобождены блоки, то отказ до освобождения i-узла будет означать,
что действующий элемент каталога указывает на i-узел, в котором перечислены бло-
ки, которые теперь находятся в пуле освободившихся блоков и которые в ближайшее
4.3. Реализация файловой системы
335
время, скорее всего, будут использованы повторно, что приведет к произвольному
совместному использованию одних и тех же блоков двумя и более файлами. Ни один
из этих результатов нас не устраивает.
В журналируемой файловой системе сначала делается запись в журнале, в которой
перечисляются три намеченных к выполнению действия. Затем журнальная запись
сбрасывается на диск (дополнительно, возможно, эта же запись считывается с дис-
ка, чтобы убедиться в том, что она было записана правильно). И только после сброса
журнальной записи на диск выполняются различные операции. После успешного
завершения операций журнальная запись удаляется. Теперь после восстановления
системы при ее отказе файловая система может проверить журнал, чтобы опреде-
лить наличие какой-либо незавершенной операции. Если таковая найдется, то все
операции могут быть запущены заново (причем по нескольку раз в случае повторных
отказов), и так может продолжаться до тех пор, пока файл не будет удален по всем
правилам.
При журналировании все операции должны быть идемпонентными, что означает
возможность их повторения необходимое число раз без нанесения какого-либо вреда.
Такие операции, как «обновить битовый массив, пометив i-узел k или блок n свободны-
ми», могут повторяться до тех пор, пока все не завершится должным и вполне безопас-
ным образом. По аналогии с этим поиск в каталоге и удаление любой записи с именем
foobar также является идемпонентным действием. В то же время добавление только
что освободившихся блоков из i-узла k к концу перечня свободных блоков не является
идемпонентным действием, поскольку они уже могут присутствовать в этом перечне.
Более ресурсоемкая операция «просмотреть перечень свободных блоков и добавить
к нему блок n, если он в нем отсутствовал» является идемпонентной. Журналируемые
файловые системы должны выстраивать свои структуры данных и журналируемые
операции таким образом, чтобы все они были идемпонентными. При таких условиях
восстановление после отказа может проводиться быстро и безопасно.
Для придания дополнительной надежности в файловой системе может быть реа-
лизована концепция атомарной транзакции, присущая базам данных. При ее ис-
пользовании группа действий может быть заключена между операциями начала
транзакции — begin transaction и завершения транзакции — end transaction. Распоз-
нающая эти операции файловая система должна либо полностью выполнить все
заключенные в эту пару операции, либо не выполнить ни одной из них, не допуская
никаких других комбинаций.
NTFS обладает исчерпывающей системой журналирования, и ее структура довольно
редко повреждается в результате системных отказов. Ее разработка продолжалась
и после первого выпуска в Windows NT в 1993 году. Первой журналируемой файловой
системой Linux была ReiserFS, но росту ее популярности помешала несовместимость
с применяемой в ту пору стандартной файловой системой ext2. В отличие от нее ext3,
представляющая собой менее амбициозный проект, чем ReiserFS, также журналирует
операции, но при этом обеспечивает совместимость с предыдущей системой ext2
1
.
1
Для Linux существуют и другие журналируемые файловые системы, обладающие своими до-
стоинствами и недостатками. Как минимум необходимо упомянуть ext4, ныне являющуюся
файловой системой по умолчанию в ряде распространенных дистрибутивов Linux. — Примеч.
ред.