в рамках исследовательского проекта, так и в системе BSD, для создания системы, которую можно выпускать в массовом порядке. Кроме того, в статье обсуждается накопленный опыт, возможные трудности и уроки, полученные во время преобразования системы из исследовательского прототипа в реальную. И, как это часто бывает в подобных случаях, побочные операции (например, fsck и fsynk) требуют тщательного обдумывания и написания дополнительного кода. Опыт работы с получившейся системой подтвердил результаты проводимого ранее исследования: мягкие обновления прекрасно интегрируются с существующими файловыми системами и реализуют обработку зависимостей метаданных с достаточной производительностью, то есть производительность оказывается меньше оптимальной всего на несколько процентов.
Непротиворечивость файловой системы в случае возникновения системной ошибки традиционно поддерживается за счет использования синхронных операций записи, выполняемых в порядке, зависящем от обновлений метаданных, или за счет использования записей с упреждением с обязательной регистрацией, необходимой для их автоматической группировки. Мягкие обновления как альтернатива этим подходам представляют собой реализацию механизма, который контролирует и обеспечивает выполнение зависимостей обновления с тем, чтобы гарантировать постоянную непротиворечивость образа диска. Использование мягких обновлений позволяет обойтись без специальной регистрации или большинства синхронных операций записи. Действительно, способность мягких обновлений объединять многие операции, прежде выполнявшиеся отдельно и синхронно, сокращает число операций записи на диск на 40 - 70% для среды, где происходит интенсивная работа с файлами (то есть при разработке программ, работе почтовых серверов и так далее). Кроме того, помимо увеличения производительности, мягкие обновления могут поддерживать непротиворечивость образа диска на более высоком уровне. Гарантируя, что все некорректности сводятся лишь к невостребованным блокам и индексным дескрипторам файлов, мягкие обновления позволяют обойтись без необходимости запускать программу проверки файловой системы после каждого сбоя системы, то есть система сразу готова к работе. Операция проверки выполняется в активной файловой системе для восстановления всех потерянных блоков и индексных дескрипторов файлов, когда это удобно и, возможно, в виде фоновой задачи.
История вопроса и введение
В файловой системе метаданные (например, каталоги, индексные дескрипторы и карты свободных блоков) задают структуру необработанной памяти. Метаданные предоставляют указатели и дескрипторы для объединения нескольких секторов на диске в файлы и идентифицируют эти файлы. Чтобы быть полезной для работы постоянной памяти файловая система должна поддерживать целостность своих метаданных на случай непредсказуемых системных сбоев, таких как отключение питания и ошибки файловой системы. Поскольку подобные сбои обычно приводят к потере всей информации во временной памяти, информация в постоянной основной памяти (то есть на диске) всегда должна быть корректной настолько, чтобы можно было однозначно восстановить согласованное состояние файловой системы. А именно, образ файловой системы на диске не должен иметь «повисших» указателей, ссылающихся на неинициализированное пространство, указывать неоднозначную принадлежность ресурсов, которая возникает в том случае, когда на ресурс ссылается несколько указателей, или на используемые ресурсы, указатели на которые отсутствуют. Поддержка такого рода инвариантности в общем случае требует определения четкой последовательности (или атомарной группировки) обновлений небольших объектов метаданных, размещаемых на диске.
Быстрая файловая система BSD (FFS) [McKusick et al, 1984] и ее производные традиционно используют синхронные операции записи на диск для того, чтобы выполнить корректную последовательность изменений, обеспечивающую стабильное состояние памяти. Например, создание файла в системе BSD предусматривает сначала резервирование и инициализацию нового индексного дескриптора файла, а затем заполнение нового элемента каталога, который на него ссылается. При использовании подхода синхронных операций записи файловая система заставляет приложение, которое создает файл, ожидать выполнения операции записи на диск, инициализирующей индексный дескриптор на диске. В результате операции файловой системы, такие как создание и удаление файла, выполняются со скоростью доступа к диску, а не со скоростью процессоров и доступа к памяти в этих системах [McVoy & Kleiman, 1991; Ousterhout, 1990; Seltzer et al, 1993]. Поскольку время доступа к диску намного больше, чем скорость работы других компонентов компьютера, синхронные операции записи снижают производительность системы.
Задача обновления метаданных также может быть решена с помощью других механизмов. Например, один из них позволяет избежать необходимости сохранять состояние системы на диск за счет применения технологий энергонезависимой памяти. При таком подходе необходимо сохранять корректными только обновления и их можно переносить на диск в любом порядке и в тот момент, когда это удобнее. Еще один подход состоит в группировке каждого множества зависимых обновлений в виде атомарной операции в сочетании с определенной формой регистрации записи с упреждением [Chutani et al, 1992; Hagmann, 1987; NCR_Corporation, 1992] или с использованием таблиц теневых страниц [Chamberlin et al, 1981; Chao et al, 1992; Rosenblum & Ousterhout, 1991; Stonebraker, 1987]. В общем и целом эти подходы расширяют образ диска за счет дополнительной информации, которая может использоваться для восстановления перенесенных на диск значений метаданных после любой системной ошибки за исключением случая повреждения физического носителя. Многие современные файловые системы для повышения производительности по сравнению с подходом, предусматривающим синхронные операции записи на диск, успешно используют регистрацию записей с упреждением.
В статье [Ganger & Patt, 1994] был предложен альтернативный подход, получивший название мягкие обновления. В этой же статье была дана оценка его применения в рамках исследовательского прототипа. Файловая система с мягкими обновлениями для изменения метаданных использует отложенные операции записи на диск (то есть кэширование с отложенной записью), контролирует зависимости между обновлениями и выполняет эти зависимости в момент отложенной записи. Поскольку большинство блоков метаданных содержит множество указателей, в тех случаях, когда зависимости записываются только на уровне блоков, часто возникают циклические зависимости. Поэтому мягкие обновления отслеживают зависимости на уровне каждого из указателей, что позволяет записывать блоки в произвольном порядке. Любые обновления со статическими зависимостями в блоке метаданных перед записью блока возвращаются в предыдущее состояние, а после записи - восстанавливаются. Таким образом, циклы зависимостей с выполнением транзакции, ликвидируются. При использовании мягких обновлений приложения всегда «видят» самые последние копии блоков метаданных, а на диске всегда размещаются копии, согласующиеся с другим содержимым.
В данной статье мы описываем интеграцию мягких обновлений в 4.4BSD FFS, используемую в операционных системах NetBSD, OpenBSD, FreeBSD и BSDI. При этом мы обсудим накопленный в процессе работы опыт и расскажем об аспектах, оказавшихся сложнее, чем предполагалось в исследовательских проектах. Как зачастую бывает в подобных случаях, побочные операции, такие, как ограничение использования основной памяти, применяемой при отслеживании зависимостей, полная реализация fsync, семантика системных вызовов, корректное выявление и обработка утерянных ресурсов в fsck, а также четкое и рациональное завершение системного вызова unmount, требуют определенного обдумывания и, в результате, приводят к усложнению кода. Несмотря на эти трудности, опыт эксплуатации системы подтвердил расчеты по производительности, сделанные во время проводимых ранее исследований. В первую очередь необходимо отметить, что использование мягких обновлений в BSD FFS позволяет отказаться от большинства синхронных операций записи на диск и обеспечить производительность, которая на отличается от идеальной на 5%. В то же самое время мягкие обновления позволяют BSD FFS обеспечить более ясную семантику, строгую целостность и гарантии защиты, а кроме того - быстрое восстановление после сбоев (после системного сбоя для дальнейшей безопасной работы использование fsck не требуется).
Зависимости обновлений в быстрой файловой системе BSD
Ряд важных операций файловой системы состоят из серии последовательных модификаций отдельных структур метаданных. Чтобы гарантировать надежное восстановление в случае возникновения непредсказуемых ошибок, зачастую модификации в постоянной памяти должны выполняться в строго определенном порядке. К примеру, при создании нового файла файловая система резервирует индексный дескриптор, инициализирует его и создает в каталоге элемент, который на него указывает. Если работа системы прервана после того, как новый элемент каталога был записана на диск, но до того, как был записан проинициализированный индексный дескриптор файла, согласованность может быть нарушена, поскольку содержимое индексного дескриптора файла на диске некорректно. Чтобы гарантировать согласованность метаданных, проинициализированный индексный дескриптор файла должен быть записан в постоянную память до записи нового элемента каталога. Мы называем это требование зависимостью обновления, поскольку безопасная запись элемента каталога существенно зависит от того, был ли первым записан индексный дескриптор файла. Упорядоченные ограничения определяются тремя простыми правилами.
1) Никогда не определяется указатель на структуру до тех пор, пока она не проинициализирована (например, индексный дескриптор файла должен быть проинициализирован до элемента каталога, который на него ссылается).
2) Никогда повторно не используется ресурс до тех пор, пока не обнулены все указатели на него (например, указатель индексного дескриптора на блок данных должен быть обнулен прежде, чем дисковый блок будет зарезервирован для нового индексного дескриптора).
3) Никогда не удаляется старый указатель на существующий ресурс до тех пор, пока не установлен новый (например, при переименовании файла не удаляйте старое имя индексного дескриптора до тех пор, пока не записано новое имя).
Данный раздел описывает зависимости обновлений, которые возникают в BSD FFS, предполагая, что BSD FFS понимается так, как она описана в [McKusick et al, 1996]. Существует восемь операций BSD FFS, которые требуют упорядоченного обновления для того, чтобы гарантировать надежное восстановление после сбоя: создание файла, удаление файла, создание каталога, удаление каталога, переименование файла/каталога, резервирование блока, работа с косвенным блоком и управление картой свободного места.
BSD FFS управляет двумя основными ресурсами: индексными дескрипторами и блоками данных. Для поддержки данных о резервировании ресурсов используются две битовые карты. Для каждого индексного дескриптора в файловой системе битовая карта индексного дескриптора имеет бит, который устанавливается, если индексный дескриптор используется и обнуляется, если он свободен. Для каждого блока в файловой системе, битовая карта блока данных имеет бит, который устанавливается, если блок свободен и очищается, если он используется. Каждая файловая система FFS разбита на фрагменты фиксированного размера, называемые группами цилиндров. Каждая группа цилиндров имеет блок группы цилиндров, который содержит битовые карты для индексных дескрипторов файлов и блоков данных, размещенных в этой группе цилиндров. Для крупных файловых систем подобная организация позволяет работать с теми фрагментами битовых карт файловой системы, которые активно используются для передачи информации в основную память. Каждый из этих блоков активных групп цилиндров хранится в отдельном буфере ввода/вывода и может записываться на диск независимо от блоков других групп цилиндров.
При создании файла изменяются три структуры метаданных, размещенные в отдельных блоках. Первая из них - это новый индексный дескриптор файла, при инициализации которого полю типа присваивается значение типа нового файла, счетчик ссылок устанавливается в единицу, что свидетельствует о существовании ресурса (то есть, что на него есть ссылка из некоторого каталога), значения полей допуска присваиваются, как указано, а все остальные поля получают значения по умолчанию. Вторая структура - это битовая карта индексных дескрипторов, которая изменяется при резервировании индексного дескриптора. Третья структура - новый элемент каталога, где записывается новое имя и указатель на новый индексный дескриптор. Чтобы гарантировать тот факт, что в битовых картах всегда отражена информация о зарезервированных ресурсах, битовая карта всегда должна записываться на диск до записи индексного дескриптора файла и элемента каталога. Поскольку индексный дескриптор находится в неизвестном состоянии до момента своей инициализации на диске, правило 1 указывает, что существует зависимость обновления, которая требует, чтобы соответствующий индексный дескриптор был записан до соответствующего элемента каталога. Хотя это и не строго обязательно, большинство реализаций быстрых файловых систем BSD также записывают блок каталога перед возвращением вызова функции создания файла. Эта вторая синхронная операция записи гарантирует, что имя файла находится в постоянной памяти, если позже приложение выполняет системный вызов fsync. Если же этого не было сделано, тогда вызов fsync должен иметь возможность найти все не записанные на диск блоки каталогов, содержащие имя файла, и записать их. Аналогичная зависимость обновления между индексным дескриптором файла и элементом каталога существует, когда одному и тому же файлу присваивается второе имя (также называемое жесткой ссылкой), поскольку добавление второго имени требует, чтобы файловая система увеличила счетчик ссылок в индексном дескрипторе и записала индексный дескриптор файла на диск до того, как соответствующий элемент появится в каталоге.
При удалении файла изменяются блок каталога, блок индексного дескриптора файла и одна или несколько битовых карт блоков цилиндров. В блоке каталога соответствующий элемент каталога «удаляется», обычно путем обнуления указателя на индексный дескриптор файла. В блоке индексного дескриптора поле типа соответствующего индексного дескриптора, счетчик ссылок и указатели на блоки тоже обнуляются. Блоки и индексный дескриптор удаленного файла затем добавляются в соответствующие карты свободных блоков и индексных дескрипторов. Правило 2 указывает, что между элементом каталога и индексным дескриптором файла, а также между индексным дескриптором файла и всеми измененными битами карты свободного места существуют зависимости обновлений. Для сохранения традиционно большим значения счетчика ссылок (и снижения сложности на практике) между элементом каталога и индексным дескриптором файла, когда удаляется одно из нескольких имен (жестких ссылок) файла также возникают зависимости обновлений.
Создание и удаление каталогов в основном выполняется также, как и для обычных файлов. Однако, элемент .. - это ссылка из дочернего каталога на родительский, что увеличивает число дополнительных зависимостей обновлений. А именно, при создании счетчик ссылок родителя на диске должен быть увеличен до записи указателя .. нового каталога. Точно также при удалении счетчик ссылок родителя должен быть уменьшен до обнуления указателя .. удаляемого каталога. (Отметим, что это обнуление предполагается при удалении указателя дочернего каталога на блок соответствующего каталога).
При резервировании нового блока состояние его битовой карты обновляется с тем, чтобы отразить факт его использования, и инициализируется содержание блока, то есть в блок записываются новые данные или он обнуляется. Кроме того, указатель на новый блок добавляется в индексный дескриптор или в косвенный блок. Чтобы гарантировать, что расположенная на диске битовая карта всегда отражает зарезервированные ресурсы, битовая карта должна записываться на диск до указателя. Кроме того, поскольку содержимое вновь зарезервированного места на диске неизвестно, правило 1 указывает зависимость обновления между новым блоком и указателям на него. Поскольку реализация этой зависимости обновления с синхронными операциями записи может сократить пропускную способность при создании дынных почти вдвое [Ganger & Patt, 1994], многие реализации игнорируют эту зависимость для обычных блоков данных. Подобное решение снижает уровень целостности и защиты, поскольку вновь зарезервированные блоки в большинстве своем содержат удаленные ранее данные. Мягкие обновления позволяют защитить все зарезервированные блоки так, что производительность при этом практически не сокращается.
Работа с косвенными блоками не приводит к появлению существенно иных зависимостей обновления, но они заслуживают отдельного обсуждения. Резервирование, как отдельных блоков, так и блоков, указывающих на косвенные блоки, выполняется аналогично тому, как обсуждалось выше. Удаление файлов и особенно освобождение зарезервированного места, для косвенных блоков более интересно. Поскольку указатель индексного дескриптора - это единственный способ идентифицировать косвенные блоки и блоки, связанные с ними (прямо или косвенно), обнуления указателя индексного дескриптора, ссылающегося на косвенный блок, достаточно для того, чтобы удалить все восстанавливаемые указатели на вышеуказанные блоки. Как только указатель на диске обнулен, все его блоки могут быть освобождены. Только для частичного усечения файла существуют зависимости обновления между указателями на косвенные блоки и самими блоками, на которые они ссылаются. Некоторые реализации FFS это различие игнорируют, несмотря на то, что оно может значительно сказаться на времени, необходимом для удаления большого файла.
При переименовании файла изменяются два элемента каталога. Создается новый элемент (с новым именем) и он указывает на соответствующий индексный дескриптор, а старый элемент каталога удаляется. Правило 3 говорит о том, что новый элемент каталога должен быть записан на диск до того, как будет удален старый элемент с тем, чтобы избежать ситуации, в которой при перезагрузки будет существовать файл, на который нет указателей. Если счетчик ссылок сохраняется традиционным, переименование предусматривает по крайней мере четыре последовательных обновления диска: одно для увеличения счетчика ссылок индексного дескриптора, второе - для добавления нового элемента каталога, третье - для удаления старого элемента каталога, четвертое - для уменьшения счетчика ссылок. Если новое имя уже существует, тогда добавление нового элемента каталога осуществляется также, как первый шаг процедуры удаления файла, описанной выше. Стоит отметить, что переименование - это одна из файловых операций POSIX, которой действительно требуется атомарное обновление нескольких видимых пользователю структур метаданных с тем, чтобы предоставить идеальную семантику. POSIX не требует указанной семантики и большинство реализаций предоставить ее не могут.
В активной файловой системе битовые карты меняются постоянно. Таким образом, копия битовой карты в основной памяти часто отличается от копии, которая хранится на диске. Если работа системы была прервана без записи состояния битовых карт из основной памяти на диск, некоторые из недавно зарезервированных индексных дескрипторов и блоков данных могут не быть отражены в устаревших копиях битовых карт на диске. Поэтому, программа проверки файловой системы fsck должна быть запущена для всех индексных дескрипторов в файловой системе с тем, чтобы выяснить, какие индексные дескрипторы файлов и блоки действительно используются и привести битовые карты в соответствие с истинным положением вещей [McKusick & Kowalski, 1994]. Дополнительное преимущество мягких обновлений состоит в том, что при данном подходе отслеживается запись битовых карт на диск и эта информация позволяет гарантировать, что ни один вновь зарезервированный индексный дескриптор файла или указатель на вновь зарезервированные блоки данных не будет записан на диск до тех пор, пока на диск не будет записана битовая карта, которая на него указывает. Такое решение гарантирует, что никогда не будет зарезервирован индексный дескриптор или блок данных, который не отмечен в битовой карте на диске. Кроме того, это гарантия, параллельно с другими гарантиями, обеспечиваемыми мягкими обновлениями, означает, что после каждого системного сбоя нет необходимости выполнять операцию fsck. Эта возможность обсуждается в дальнейшем.
Контроль и реализация зависимостей обновления
Данный раздел описывает мягкие обновления BSD структур данных и их использование при реализации зависимостей обновлений, описанных выше. Описанные структуры и алгоритмы позволяют отказаться от всех синхронных операций записи на диск в BSD FFS за исключением частичного усечения файла и системного вызова fsync, который в обязательном порядке требует, чтобы все состояния файла были перенесены на диск до возвращения системного вызова.
Основной атрибут мягких обновлений - это контроль зависимостей на уровне отдельных изменений в кэшированных блоках. Таким образом, для блока, содержащего 64 индексных дескриптора, система может поддерживать до 64 структур зависимостей, то есть по одной для каждого индексного дескриптора в буфере. Точно также для буфера, содержащего блок каталога, в котором имеется 50 имен, система может поддерживать до 50 структур зависимости, то есть по одной для каждого имени в каталоге. При таком уровне детализации информации о зависимостях циклические зависимости между блоками трудностей не вызывают. Например, когда система хочет записать буфер, содержащий индексные дескрипторы файлов, те индексные дескрипторы, которые могут быть записаны без риска - переносятся на диск. Любые индексные дескрипторы, которые не могут быть записаны без риска временно возвращаются в свое безопасное состояние во время выполнения записи на диск. После завершения операций записи на диск такие индексные дескрипторы возвращаются обратно в свое текущее значение. Поскольку буфер блокируется на все время, в течение которого содержимое возвращается в предыдущее состояние, выполняется операция записи на диск и содержимое восстанавливается, то доступ любого процесса к буферу будет запрещен до тех пор, пока буфер не вернется в текущее состояние.
Структуры зависимости
Реализация мягких обновлений использует различные структуры данных для контроля невыполненных зависимостей обновлений в структурах файловой системы.
| Название | Функция | Связанные структуры |
| bmsafemap | Контролирует зависимости битовых карт (указывает на списки структур зависимостей для недавно зарезервированных блоков и индексных дескрипторов) | Блок группы цилиндров |
| inodedep | Контролирует зависимости индексных дескрипторов (информация и указатели на списки всех зависимостей, связанных с индексными дескрипторами, в том числе изменениями счетчика ссылок, указателей блоков и размера файлов) | Блок индексного дескриптора |
| allocdir | Контролирует блок, на который указывает индексный дескриптор (связанный со списками, на которые указывают inodedep и bmsafemap для контроля зависимостей индексного дескриптора, чьи блок и битовая карта записываются на диск) | Блок данных или косвенный Блок или блок каталога |
| indirdep | Контролирует зависимости косвенного блока (указывает на список структур зависимостей для недавно зарезервированных блоков с указателями в косвенном блоке) | Косвенный блок |
| allocindir | Контролирует блок, на который указывает косвенный блок (связан со списком, на который указывает indirdep и bmsafemap для контроля зависимости косвенного блока, чьи блок и битовая карта записываются на диск) | Блок данных или косвенный Блок или блок каталога |
| pagedep | Контролирует зависимости блока каталога (указывает на списки структур diradd и dirrem) | Блок каталога |
| diradd | Контролирует зависимости между новым элементом каталога и указываемым индексным дескриптором | inodedep и блок каталога |
| mkdir | Контролирует создание нового каталога (используется в дополнение к стандартной структуре diradd при выполнении операции mkdir) | inodedep и блок каталога |
| dirrem | Контролирует зависимость между удаляемым элементом каталога и индексным дескриптором, у которого удалены ссылки |
| Сначала pagedep, затем tasklist | ||
| freefrag | Контролирует один блок или фрагмент, отслеживая, чтобы он был освобожден сразу же после того, как блок (содержащий индексный дескриптор с измененным указателем на него) записан на диск | Сначала inodedep, затем tasklist |
| freeblks | Контролирует, чтобы все указатели на блоки были освобождены сразу же после того, как соответствующий блок (содержащий индексный дескриптор с теперь обнуленными указателями на них) записан на диск | Сначала inodedep, затем tasklist |
| freefile | Контролирует индексный дескриптор, который должен быть освобожден сразу же после того, как соответствующий блок (содержащий блок индексного дескриптора с теперь удаленным индексным дескриптором) записан на диск | Сначала inodedep, затем tasklist |
Структура worklist в действительности представляет собой общий заголовок, который является первым элементом каждой структуры зависимости. Она содержит набор связанных указателей и поле типа, которое указывает тип структуры, в которую она встроена. Структура worklist в одном списке объединяет структуры зависимостей нескольких различных типов. Программа мягких обновлений может просматривать по одному эти гетерогенные списки, используя поле типа для определения вида текущей структуры зависимости, и для каждой из них предпринимать соответствующие действия.
Обычно структура worklist служит для объединения набора зависимостей, связанных с буфером. Каждый буфер в системе имеет указатель на заголовок worklist, который в него добавлен. Любые зависимости, связанные с данным буфером, объединены в его список worklist. После того, как буфер заблокирован и перед тем, как буфер начинает записываться на диск, система ввода/вывода передает буфер программе мягких обновлений, чтобы уведомить ее о начале операций записи на диск. Затем программа мягких обновлений просматривает список зависимостей, связанных с буфером, и выполняет все необходимые операции откатки. После того, как операции записи на диск завершены, но перед разблокировкой буфера система ввода/вывода вызывает программу мягких обновлений с тем, чтобы уведомить ее о завершении операций записи. Затем программа мягких обновлений просматривает список зависимостей, связанных с буфером, выполняет необходимые операции восстановления и удаляет зависимости, выполненные в процессе записи данных из буфера на диск.
Программа мягких обновлений поддерживает еще один важный список - tasklist, который содержит фоновые задачи для работающего демона. Структуры зависимостей в основном добавляются в tasklist во время выполнения подпрограммы завершения записи на диск, описывающей задачи, которые обеспечивают безопасность данного обновления диска, но которым может потребоваться блокировка буфера или ввода/вывода и которые, тем самым, не могут быть завершены во время обработки прерывания. Раз в секунду демон синхронизации (выполняющий еще и роль демона, реализующего мягкие обновления) пробуждается и вызывает программу мягких обновлений для обработки всех элементов tasklist. Работа, выполняемая для структуры зависимости, присутствующей в данном списке, определяется типом структуры. Например, для структуры freeblks перечисленные блоки в битовых картах блоков маркируются как свободные. Для структуры dirrem счетчик ссылок соответствующего индексного дескриптора уменьшается, возможно инициируя затем удаление файла.
Состояния зависимостей
Большинство структур зависимостей имеет набор флагов, которые определяют состояние выполнения соответствующей зависимости. Измененные блоки кэш-памяти могут быть записаны на диск в произвольный момент времени. Когда система ввода/вывода передает буфер программе мягких обновлений, (до или после операции записи на диск) состояния, связанные со структурами зависимостей, определяют, какие действия необходимо предпринять. Хотя конкретные их значения отличаются от структуры к структуре, используются три основных флага, имеющие следующий основной смысл.
Флаг ATTACHED показывает, что буфер, с которым связана структура зависимостей, в данный момент на диск не записан. При инициации операции записи на диск для буфера, содержащего зависимость, требующую откатки, флаг ATTACHED в структуре зависимости опускается, чтобы показать, что структура в буфере находится в предыдущем состоянии. После завершения операции записи на диск, обновления, описанные с помощью структур зависимостей, флаг ATTACHED которых опущен, восстанавливаются и поднимается флаг ATTACHED. Таким образом, структура зависимости никогда не удаляется до тех пор, пока ее флаг ATTACHED опущен, поскольку информация, необходимая для выполнения восстановления, будет тогда утеряна.
Флаг DEPCOMPLETE показывает, что все связанные зависимости были выполнены. При инициации операции записи на диск обновление, описываемое структурой зависимости, возвращается в предыдущее состояние, если флаг DEPCOMPLETE опущен. Например, в структуре зависимостей, связанной с вновь зарезервированными индексными дескрипторами файлов или блоками данных, флаг DEPCOMPLETE поднимается, когда соответствующая битовая карта записана на диск.
Флаг DEPCOMPLETE показывает, что все связанные зависимости были выполнены. При инициации операции записи на диск обновление, описываемое структурой зависимости, возвращается в предыдущее состояние, если флаг DEPCOMPLETE опущен. Например, в структуре зависимостей, связанной с вновь зарезервированными индексными дескрипторами файлов или блоками данных, флаг DEPCOMPLETE поднимается, когда соответствующая битовая карта записана на диск.
Флаг COMPLETE показывает, что контролируемое обновление записано на диск. Для некоторых зависимостей обновления будут возвращены в предыдущее состояние во время записи на диск, когда флаг COMPLETE опущен. Например, для вновь зарезервированного блока данных флаг COMPLETE поднимается, когда содержимое блока записано на диск.
В общем флаги поднимаются, когда завершены операции записи на диск и структуры зависимостей могут освобождаться только в том случае, если все флаги ATTACHED, DEPCOMPLETE и COMPLETE подняты. Рассмотрим пример вновь зарезервированного блока данных, который будет контролироваться структурой allocdirect. Сначала, когда происходит резервирование блока, будет поднят флаг ATTACHED. Флаг DEPCOMPLETE будет поднят после того, как битовая карта, резервирующая этот новый блок, записана на диск. Флаг COMPLETE будет поднят после того, как записано содержимое этого блока. Если индексный дескриптор файла, указывающий на этот блок, записан до того, как подняты флаги DEPCOMPLETE и COMPLETE, флаг ATTACHED будет опущен и при этом указатель на блок в этом индексном дескрипторе возвращается в предыдущее значение ноль, индексный дескриптор записывается, а указателю на блок в индексном дескрипторе присваивается номер нового блока. Там, где они отличаются, конкретные значения этих флагов в различных структурах зависимостей описываются в подразделах, приведенных ниже.
Контроль битовой карты зависимостей
 |
| Рис. 1. Зависимости обновлений битовой карты |
Контроль зависимостей индексных дескрипторов файлов
 |
| Рис. 2. Зависимости при обновлении индексного дескриптора |
Обновление индексных дескрипторов файлов контролируется с помощью структуры inodedep, представленной на рисунке 2. Поля worklist и state аналогичны описанным для структур зависимостей в целом. Поля filesystem ptr и inode number определяют индексный дескриптор файла, о котором идет речь. При резервировании нового индексного дескриптора его структура inodedep присоединяется к списку inodedep head структуры bmsafemap. Здесь inodedep head пополняется новыми структурами inodedep и dep bp указывает на блок группы цилиндров, который содержит соответствующую битовую карту. Другие поля структуры inodedep будут объяснены в последующих подразделах.
Перед тем, как приступить к детальному описанию остальных зависимостей, связанных с индексным дескриптором файла, нам необходимо описать шаги, предпринимаемые при обновлении индексного дескриптора на диске, как это изображено на рисунке 3.
Шаг 1. Ядро вызывает операцию над виртуальными индексными дескрипторами VOP_UPDATE, которая требует, чтобы размещаемая резидентно на диске часть индексного дескриптора файла (которую мы в дальнейшем будем называть дисковым дескриптором) была скопирована из структуры виртуального дескриптора, находящейся в памяти, в соответствующий буфер на диске. Этот дисковый буфер хранит содержимое всего дискового блока и имеет размер, достаточный для того, чтобы вместить 64 дисковых дескриптора. Некоторые зависимости выполняются только тогда, когда индексный дескриптор записан на диск. Для этих случаев структуры зависимостей должны отслеживать выполнение операции записи на диск индексного дескриптора. Таким образом, во время шага 1 вызывается подпрограмма мягких обновление softdep_update_inodeblock, которая перемещает структуру allocdirect из списка incore update в список buffer update, а также перемещает структуры freefile, freeblks, freefrag, diradd и mkdir (описанные ниже) из списка inode wait в список buf wait.
 |
| Рис. 3. Этапы обновления индексного дескриптора |
Шаг 2. Ядро вызывает операцию над виртуальными индексными дескрипторами VOP_STRATEGY, которая готовит к записи буфер, содержащий дисковый дескриптор (на рисунке 3 на него ссылается указатель bp). Подпрограмма мягких обновлений softdep_disk_io_initiation выявляет зависимости inodedep и вызывает initiate_write_inodeblock для откатки, если это необходимо.
Шаг 3. Вывод завершается в буфер, на который указывает bp и система ввода/вывода вызывает подпрограмму biodone для того, чтобы уведомить все ожидающие процессы, что запись завершена. Подпрограмма biodone затем вызывает подпрограмму мягких обновлений softdep_disk_write_complete, которая выявляет зависимости inodedep, вызывает handle_written_inodeblok для компенсации откатки и удаляет все зависимости из списков buf wait и buffer update.
Опыт и полученные уроки
Данный раздел описывает различные вопросы, возникшие в процессе преобразования мягких обновлений из исследовательского прототипа в компонент, используемый при создании производственной операционной системы 4.4BSD. Некоторые из этих вопросов были очевидными недостатками еще исследовательского прототипа, а некоторые возникли как следствие сложностей, присущих операционным системам, куда интегрируется эта технология. Другие, однако, стали очевидны только тогда, когда мы получили достаточно большой опыт работы с мягкими обновлениями.
Системный вызов fsynk. Доступ к важному интерфейсу файловой системы осуществляется через системный вызов fsynk. Этот системный вызов требует, чтобы в стабильную память был записан конкретный файл и чтобы системный вызов не возвращался до тех пор, пока не завершены все связанные с ним операции записи. Реализация прототипа мягких обновлений не реализовывала системный вызов fsynk.
Задача выполнения fsynk требует не только записи всех измененных блоков данных файла на диск. Она также требует, чтобы все не записанные еще элементы каталога, которые указывают на файл, тоже были перенесены на диск, как и все не записанные каталоги, находящиеся между файлом и корневым каталогом файловой системы. Сама по себе задача записи на диск блоков данных может оказаться достаточно объемной. Во-первых, система должна проверить, записана ли битовая карта для индексного дескриптора, найти битовую карту и записать ее на диск, если это необходимо. Она должна проверить, найти и записать битовые карты всех новых блоков в файле. Затем, должны быть переправлены на диск все не записанные блоки данных. После блоков данных - любые косвенные блоки данных первого уровня, в которые записаны вновь зарезервированные блоки, после чего то же необходимо сделать с блоками второго, а затем и третьего уровня. Наконец, на диск может быть записан индексный дескриптор, который будет гарантировать, что содержимое файла находится в стабильной памяти. Чтобы гарантировать, что все имена файла также находятся в стабильной памяти, необходимо требовать использования структур данных, которые могут определить, имеются ли какие-либо не сохраненные имена и, если это так, в каких каталогах они встречаются. Для каждого каталога, содержащего такое не сохраненное имя, программа мягких обновлений должна выполнить ту же самую последовательность операций сбрасывания файловых буферов на диск, которые выполнялись и для самого файла.
Хотя системный вызов fsync обязательно должен выполняться синхронно, это не означает, что каждая из операций сбрасывания файловых буферов на диск должна выполняться синхронно. На самом деле все наборы битовых карт или блоков данных передаются в дисковую очередь, а затем программа мягких обновлений ждет завершения всех операций записи на диск. Такой подход более эффективен, поскольку позволяет дисковой подсистеме сортировать все запросы на запись в более эффективном порядке. Таким образом, часть fsync программы мягких обновлений генерирует большинство оставшихся синхронных операций записи в файловой системе.
Демонтируемые файловые системы. Еще один вопрос, связанный с fsync, касается демонтируемых файловых систем. Выполнение umount требует поиска и сбрасывания на диск всех измененных файлов, которые связаны с файловой системой. Сбрасывание файлов на диск может привести к инициации операций, выполняемых в фоновом режиме, таких как удаление файлов, чьи счетчики ссылок стали равны нулю в результате того, что соответствующие им обновленные элементы каталогов были записаны на диск. Таким образом, система должна иметь возможность выполнять поиск всех запросов на фоновые операции и обрабатывать их. Даже в неактивной файловой системе некоторые итерации сбрасывания файлов на диск могут инициировать последующие фоновые операции. 4.4BSD FFS позволяет насильственно демонтировать файловые системы, допускающие демонтаж в момент активной работы файловой системы, что требует дополнительной поддержки.
Удаление каталогов. Реализация прототипа чересчур упрощает последовательность обновлений, выполняемую при удалении каталога. А именно, прототип допускал параллельное удаление имени каталога и удаление его элемента ... Это значит, что при сбое может случится так, что в каталоге не окажется элемента ... Хотя утилиту fsck можно изменить так, чтобы устранить этот дефект, данное решение не приемлемо, когда при восстановлении после сбоя fsck пропускается.
Для корректной работы элемент каталога .. не должен удаляться до тех пор, пока в каталоге заведомо не удалены все ссылки. Решение этой задачи в программе мягких обновлений порождает задержку длительностью до двух минут между «отвязанным» каталогом и тем моментом, когда он действительно будет освобожден (когда будет удален элемент ..). До тех пор, пока элемент каталога .. в действительности не удален, счетчик ссылок его родителя уменьшен не будет. Таким образом, когда пользователь удаляет один или несколько каталогов, счетчик ссылок его бывшего родителя в течение нескольких минут все еще свидетельствует о том, что тот существует. Такое отложенное уменьшение счетчика ссылок не только вызывает вопросы у пользователей, но и приводит к сбою работы некоторых приложений. Например, системный вызов rmdir не будет удалять каталог, счетчик ссылок которого имеет значение больше двух. Эти ограничения означают, что каталог, который недавно имел удаленные из него подкаталоги, не может быть удален до тех пор, пока его бывшие подкаталоги полностью не удалены.
Чтобы решить эти проблемы, касающиеся счетчика ссылок, реализация мягких обновлений в BSD добавляет к полю nlink новое поле, называемое efflink. Поле nlink по прежнему хранится как часть размещаемых на диске метаданных и отражает истинное значение счетчика ссылок индексного дескриптора. Поле efflink поддерживается только в памяти ядра и отражает окончательное значение, которое поле nlink будет иметь тогда, когда завершатся все невыполненные операции. Все интерактивные действия с пользовательскими приложениями сообщают значение поля efflink, создавая иллюзию, что все происходит сразу.
Освобождение блока. Поскольку это было сделано в System V Release 4 UNIX, прототипная система не поддерживала освобождение блока. В 4.4BSD FFS файловая система иногда изменяет положение на диске блоков файла по мере увеличения размера самого файла с тем, чтобы разместить его в физически смежных блоках. Таким образом, блок, который изначально присвоен файлу, может быть заменен по мере увеличения размера файла. Хотя программа прототипа была подготовлена к поддержке обновлений фрагментов полноразмерных блоков в последнем блоке файла, она не была подготовлена к тому, чтобы во внутренних частях индексных дескрипторов и косвенных блоков перераспределялись полноразмерные блоки.
Память, используемая для структур зависимостей. Один из важных вопросов, касающихся мягких обновлений, связан с объемом памяти, отводимым под структуры зависимостей. Эта проблема имеет два аспекта: эффективность использования памяти и ограничение использования.
Прототипная реализация в общем случае применяла две структуры для каждой зависимости обновления. Одна из них была связана с данными, которые должны быть записаны, и одна - с данными, которые зависят от операций записи. Например, каждый раз при резервировании нового блока с резервируемым блоком на диске, битовой картой, из которой блок был зарезервирован, и индексным дескриптором, указывающим на новый дисковый блок, связывались новые структуры зависимостей. Структура, связанная с индексным дескриптором, зависела от того, записаны ли две других. Программа мягких обновлений 4.4BSD использует одну структуру зависимостей (связанную с дисковым блоком) для описания резервирования блока. С каждой битовой картой и каждым индексным дескриптором связана только одна структура зависимостей, и все соответствующие структуры резервирования блока связываются со списками, на которые ссылаются эти структуры. Другими словами, со списком зарезервированных блоков, списком битовых карт и списком индексных дескрипторов связана только одна структура резервирования блока. За счет создания списков, а не использования отдельных структур, требования к памяти были снижены почти на 40%.
В своей повседневной работе мы пришли к выводу, что нагрузка в виде дополнительной динамической памяти, возлагаемая на область резервирования памяти ядра, практически равна количеству памяти, используемому структурами виртуальных индексных дескрипторов и индексными дескрипторами. Для системы с 1000 виртуальных индексных дескрипторов дополнительная пиковая нагрузка на память составляет около 300 Кбайт. Одно исключение из этого общего правила возникает, когда удаляются крупные деревья каталогов. Здесь программа файловой системы может получить сколь угодно дальний прогноз о состоянии диска, определяя объем памяти, выделенной для структур зависимостей, так, чтобы расти без ограничений. Программа мягких обновлений 4.4BSD была изменена с тем, чтобы отслеживать загрузку памяти для этого случая и не позволять ей превзойти настраиваемую верхнюю границу. Когда граница достигнута, новые структуры зависимостей могут создаваться только со скоростью, с которой удаляются старые. Эффект такого ограничения состоит в том, чтобы скорость удаления снижалась до скорости, с которой могут осуществляться обновления диска. Хотя эти ограничения сокращают скорость, с которой мягкие обновления могут нормально удалять файлы, программа работает все еще значительно быстрее, чем выполняются традиционные синхронные операции записи файловой системы. В стабильном состоянии алгоритм удаления мягких обновлений требует около одной операции записи на диск для каждых десяти удаленных файлов, в то время, как традиционная файловая система для каждого удаляемого файла требует по крайней мере двух операций записи на диск.
Утилита fsck. Как и при двойном контроле истинного и эффективного счетчика ссылок, изменения, необходимые для fsck, при реальной эксплуатации становятся очевидными. При реализации файловых систем, не поддерживающих мягкие обновления, для удаления файла требуется несколько миллисекунд. Таким образом, между удалением элемента каталога и освобождением индексного
| Конфигурация файловой системы | Операции записи на диск | Время выполнения | |
| Синхронная | Асинхронная | ||
| Обычная | 1 459 147 | 487 031 | 27 часов 15 минут |
| Асинхронная | 0 | 1 109 711 | 19 часов 43 минуты |
| С мягкими обновлениями | 6 | 1 113 686 | 19 часов 50 минут |
| Конфигурация файловой системы | Операции записи на диск | Время выполнения | |
| Синхронная | Асинхронная | ||
| Обычная | 162 410 | 39 924 | 2 часа 12 минут |
| Асинхронная | 0 | 38 262 | 1 час 44 минуты |
| С мягкими обновлениями | 1124 | 48 850 | 1 час 44 минуты |
Дополнительное преимущество мягких обновлений состоит в том, что fsck может доверять информации о резервировании, хранящейся в битовых картах. Таким образом, необходимо только проверить подмножество индексных дескрипторов в файловой системе, чьи битовые карты свидетельствуют об их использовании. Хотя некоторые из индексных дескрипторов промаркированные как «используемые», на самом деле могут оказаться свободными, ни один из индексных дескрипторов, отмеченный как свободный, никогда не окажется используемым.
Частичное усечение файла. Хотя в общем случае при освобождении все данные в файле удаляются, системный вызов truncate позволяет приложениям удалить только часть файла. Это создает чуть более сложные зависимости обновлений, в том числе необходимость использовать зависимости при освобождении косвенных блоков и необходимость работать с частично удаленными блоками данных. Поскольку эта операция используется крайне редко, ни прототип, ни реализация мягких обновлений BSD для этого случая не оптимизированы; вместо этого применяется традиционных подход синхронизированных операций записи.
Производительность
Мы рассматриваем производительность BSD FFS, поддерживающей мягкие обновления в контексте, сравнивая ее с BSD FFS по умолчанию (называемой в дальнейшем «обычной»), которая использует синхронные операции записи для управления обновлением, а BSD FFS вместе с опцией O_ASYNC (ниже называемой как «асинхронная»), которая игнорирует все зависимости обновлений. При асинхронном режиме все обновления метаданных преобразуются в отложенные операции записи (отложенная операция записи - это операция, при которой буфер просто маркируется как измененный, помещается в список последних используемых и не записывается на диск до тех пор, пока это не нужно для каких-либо иных целей).
| Конфигурация файловой системы | Операции записи на диск | |
| Синхронная | Асинхронная | |
| Обычная | 1 877 794 | 1 613 465 |
| С мягкими обновлениями | 118 102 | 946 519 |
Чтобы дать представление о том, как система выполняет традиционные операции, мы предлагаем данные, касающиеся решения трех различных системных задач. Первая задача - это наш «тест на испытание файловой системы». Он содержит 1000 запусков теста Andrew, 1000 операций копирования и удаления из каталога /etc с произвольно выбранными паузами от 0 до 60 секунд между каждой копией и удалением, а также 500 исполнении приложения find из корневого каталога с произвольно выбранными паузами из 100 секунд между каждым запуском. Результаты этого теста выглядят следующим образом.
Общий итог состоит в том, что асинхронная система и система с мягкими обновлениями требуют на 42% меньше операций записи на диск (и почти не требует синхронизованных операций записи) и их время выполнения на 28% меньше, чем у обычной системы. Это особенно впечатляет, учитывая, что поиск и паузы не используют зависимости обновлений, а тест Andrew существенно ограничивается процессором.
Второй тест состоит из создания и установки системы FreeBSD. Данная задача - это реальный пример среды разработки программ. Результат выглядит следующим образом.
Общий итог состоит в том, что мягкие обновления требуют на 75% меньше операций записи и на 21% меньшее время выполнения. Хотя мягкие обновления инициируют на 30% больше операций записи, чем асинхронная система, время выполнения теста у них одинаково.
Третий тест сравнивает производительность центрального почтового сервера для компании Berkeley Software Design, работающего с и без мягких обновлений. Администратор отказался запускать сервер в асинхронном режиме, поскольку это производственный компьютер и людям явно не хотелось терять свои сообщения электронной почты. В отличие от тестов, описанных выше, которые использовали только один диск, почтовый буферный файл размещается на трех дисках. Статистика была собрана на основе усредненных результатов за три дня работы в каждом режиме в будние дни. Результаты за сутки были следующие.
Обычная файловая система в среднем выполняет более 40 операций записи в секунду, а соотношение синхронных и асинхронных операций записи составляет 1:1. При использовании мягких обновлений число операций записи снижается до 12 в секунду и соотношение синхронных и асинхронных операций записи сокращается до 1:8. Для этого реального приложения мягкие обновления требуют на 70% меньше операций записи, что втрое увеличивает пропускную способность компьютера при обработке почты.
Моментальные снимки файловой системы
Моментальный снимок файловой системы - это зафиксированный в данный момент времени образ файловой системы. Моментальные снимки поддерживают несколько важных возможностей: способность обеспечить резервное копирование файловой системы несколько раз в день, способность выполнять надежные копии активно действующих файловых систем и (что более важно для мягких обновлений) способность выполнять программу проверки файловой системы на активной системе с тем, чтобы выявить утерянные блоки и индексные дескрипторы.
Реализация моментальных снимков в BSD FFS подтвердила свою простоту следующим образом. Во-первых, операции в соответствующей файловой системе быстро завершаются. Во-вторых, допускается завершение всех системных вызовов, записывающих в данный момент времени информацию в такую файловую систему. В-третьих, файловая система синхронизируется с диском, как если бы она была демонтируемой. Наконец, файл с моментальными снимками создается для контроля последовательных изменений в файловой системе; файл с моментальным снимком показан на рисунке 11. Размер этого файла устанавливается равным размеру раздела файловой системы и большинство ее указателей на блок файла маркируются как «некопируемые». Резервируются и копируются несколько стратегических блоков, в частности, содержащие копии карт суперблоков и групп цилиндров. Файл с моментальным снимком также использует выделенный номер блока (1), для маркировки всех блоков как «неиспользуемых» во время выполнения моментального снимка, поскольку нет необходимости копировать блоки, если они позже будут зарезервированы и записаны.
Как только файл с моментальным снимком создан, работа файловой системы продолжается. Каждый раз, когда существующий в файловой системе блок модифицируется, файловая система проверяет, использовался ли блок во время выполнения моментального снимка (то есть не был ли он промаркирован, как «неиспользуемый»). Если это так и если он не был скопирован (то есть, до сих пор промаркирован, как «некопируемый»), резервируется новый блок и помещается в файл с моментальным снимком, чтобы заменить элемент с маркой «некопируемый». Предыдущее содержимое блока копируется во вновь зарезервированный блок файла с моментальным снимком и разрешается продолжить изменение в оригинале. Когда бы файл не был удален, программа моментального снимка проверяет каждый из блоков, который освобождается, и закрепляет за собой все, которые использовались при создании моментального снимка. Блоки, промаркированные как «неиспользуемые», возвращаются в список свободных.
 |
| Рис. 4. Структура с моментальным снимком файла |
При чтении файла с моментальным снимком, операции чтения блоков, промаркированных как «некопируемые», возвращают содержимое соответствующих блоков файловой системе. Операции чтения скопированных блоков возвращают их содержимое. Операции записи в файл с моментальным снимком не разрешаются. Когда файл с моментальным снимком больше не нужен, он может быть удален таким же образом, как и любой другой файл; его блоки просто возвращаются в список свободных и его индексный дескриптор обнуляется и возвращается в список свободных индексных дескрипторов.
Моментальные снимки могут сохраняться во время перезагрузки. При создании файла с моментальным снимком номер индексного дескриптора файла с моментальным снимком записывается в суперблок. Когда файловая система монтируется, список моментальных снимков просматривается и все перечисленные моментальные снимки активизируются. Единственное ограничение на число моментальных снимков, которые могут существовать в файловой системе, - это размер массива в суперблоке, содержащего список моментальных снимков. Сейчас этот массив может хранить до двадцати моментальных снимков.
Одновременно могут существовать несколько моментальных снимков. Как описано выше, файлы с более ранними моментальными снимками появляются в более поздних моментальных снимках. Если более ранний моментальный снимок удаляется, более поздний моментальный снимок закрепляет за собой его блоки, вместо того, чтобы позволить им вернуться в список свободных. Эта семантика означает, освободить любое пространство в файловой системе можно только удалив самый последний моментальный снимок. Чтобы избежать таких проблем программа поддержки моментальных снимков тщательно проверяет и уничтожает все более ранние моментальные снимки, изменяя их представление за счет обнуления длины файла. Благодаря этой методике при освобождении более раннего моментального снимка освобождается пространство, занимаемое данным моментальным снимком.
Когда блок переписывается, копировать блок позволяют все моментальные снимки. Копия блока выполняется для каждого моментального снимка, в котором размещен блок. Удаление блоков выполняется по-разному. Список моментальных снимков принимается во внимание. Когда обнаружен моментальный снимок, в котором данный блок является активным («не копируемый»), этот моментальный снимок оставляет за собой данный удаленный блок. Просмотр списка моментальных снимков затем прекращается. Другие моментальные снимки, для которых блок активен, оставляют для этого блока запись «не копируемый». Результат в том, что , когда они обращаются к позиции, на которую они будут все еще указывать на удаленный блок. Поскольку моментальный снимок может не быть записан на диск, блок не будет изменен. Поскольку блок требуется моментальному снимку, он не будет зарезервирован для другого использования. Если моментальный снимок, которому требовался удаленный блок, сам удаляется, оставшиеся моментальные снимки дадут возможность востребовать этот блок. Только когда ни один из оставшихся моментальных снимков не претендует на блок (то есть он промаркирован как «не используемый» во всех из них), тогда блок будет возвращен в список свободных.
Перезагрузка файловой системы
После некорректного выключения
